From a36a8eb9ad499eb0f50204e462e9bc1c45544294 Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Sun, 5 Feb 2023 21:35:28 +0100 Subject: Delta store commit --- .../store/map/VersionedMapStoreDeltaImpl.java | 90 ++++++++++++ .../store/map/internal/DeltaDiffCursor.java | 127 +++++++++++++++++ .../store/map/internal/IteratorAsCursor.java | 62 ++++++++ .../refinery/store/map/internal/MapDelta.java | 15 ++ .../store/map/internal/MapTransaction.java | 34 +++++ .../map/internal/UncommittedDeltaArrayStore.java | 31 ++++ .../map/internal/UncommittedDeltaMapStore.java | 47 +++++++ .../store/map/internal/UncommittedDeltaStore.java | 10 ++ .../store/map/internal/VersionedMapDeltaImpl.java | 156 +++++++++++++++++++++ 9 files changed, 572 insertions(+) create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java (limited to 'subprojects/store/src/main/java/tools') diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java new file mode 100644 index 00000000..2bd758e2 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java @@ -0,0 +1,90 @@ +package tools.refinery.store.map; + +import java.util.*; + +import tools.refinery.store.map.internal.DeltaDiffCursor; +import tools.refinery.store.map.internal.MapDelta; +import tools.refinery.store.map.internal.MapTransaction; +import tools.refinery.store.map.internal.VersionedMapDeltaImpl; + +public class VersionedMapStoreDeltaImpl implements VersionedMapStore{ + // Static data + protected final V defaultValue; + + // Dynamic data + protected final Map> states = new HashMap<>(); + protected long nextID = 0; + + public VersionedMapStoreDeltaImpl(V defaultValue) { + super(); + this.defaultValue = defaultValue; + } + + @Override + public VersionedMap createMap() { + return new VersionedMapDeltaImpl<>(this, defaultValue); + } + + @Override + public VersionedMap createMap(long state) { + VersionedMapDeltaImpl result = new VersionedMapDeltaImpl<>(this, defaultValue); + result.restore(state); + return result; + } + + public synchronized MapTransaction appendTransaction(MapDelta[] deltas, MapTransaction previous, long[] versionContainer) { + long version = nextID++; + versionContainer[0] = version; + if(deltas == null) { + states.put(version, previous); + return previous; + } else { + MapTransaction transaction = new MapTransaction<>(deltas, version, previous); + states.put(version, transaction); + return transaction; + } + } + + private synchronized MapTransaction getState(long state) { + return states.get(state); + } + + public void getPath(long to, List[]> forwardTransactions) { + MapTransaction toTransaction = getState(to); + while(toTransaction != null) { + forwardTransactions.add(toTransaction.deltas()); + toTransaction = toTransaction.parent(); + } + } + + public void getPath(long from, long to, + List[]> backwardTransactions, + List[]> forwardTransactions) + { + MapTransaction fromTransaction = getState(from); + MapTransaction toTransaction = getState(to); + while(fromTransaction != toTransaction) { + if(fromTransaction == null || fromTransaction.version() < toTransaction.version()) { + forwardTransactions.add(toTransaction.deltas()); + toTransaction = toTransaction.parent(); + } else { + backwardTransactions.add(fromTransaction.deltas()); + fromTransaction = fromTransaction.parent(); + } + } + } + + + @Override + public synchronized Set getStates() { + return states.keySet(); + } + + @Override + public DiffCursor getDiffCursor(long fromState, long toState) { + List[]> backwardTransactions = new ArrayList<>(); + List[]> forwardTransactions = new ArrayList<>(); + getPath(fromState, toState, backwardTransactions, forwardTransactions); + return new DeltaDiffCursor<>(backwardTransactions, forwardTransactions); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java new file mode 100644 index 00000000..75180bf9 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java @@ -0,0 +1,127 @@ +package tools.refinery.store.map.internal; + +import tools.refinery.store.map.AnyVersionedMap; +import tools.refinery.store.map.DiffCursor; + +import java.util.Collections; +import java.util.List; +import java.util.Set; + +public class DeltaDiffCursor implements DiffCursor { + final List[]> backwardTransactions; + final List[]> forwardTransactions; + + /** + * Denotes the direction of traversal. False means backwards, true means + * forward. + */ + boolean direction; + int listIndex; + int arrayIndex; + + public DeltaDiffCursor(List[]> backwardTransactions, List[]> forwardTransactions) { + this.backwardTransactions = backwardTransactions; + this.forwardTransactions = forwardTransactions; + + if (!backwardTransactions.isEmpty()) { + direction = false; + listIndex = 0; + arrayIndex = backwardTransactions.get(listIndex).length - 1; + } else if (!forwardTransactions.isEmpty()) { + direction = true; + listIndex = forwardTransactions.size() - 1; + arrayIndex = 0; + } else { + direction = true; + listIndex = -1; + } + } + + protected MapDelta getCurrentDelta() { + final List[]> list; + if (!direction) { + list = this.backwardTransactions; + } else { + list = this.forwardTransactions; + } + return list.get(listIndex)[arrayIndex]; + } + + @Override + public K getKey() { + return getCurrentDelta().getKey(); + } + + @Override + public V getValue() { + return getToValue(); + } + + @Override + public boolean isTerminated() { + return this.direction && listIndex == -1; + } + + @Override + public boolean move() { + if (isTerminated()) { + return false; + } else { + if (this.direction) { + if (arrayIndex+1 < forwardTransactions.get(listIndex).length) { + arrayIndex++; + return true; + } else { + if (listIndex-1 >= 0) { + listIndex--; + return true; + } else { + listIndex = -1; + return false; + } + } + } else { + if (arrayIndex > 0) { + arrayIndex--; + return true; + } else { + if (listIndex+1 < backwardTransactions.size()) { + listIndex++; + this.arrayIndex = backwardTransactions.get(listIndex).length - 1; + return true; + } else { + this.direction = true; + if (!this.forwardTransactions.isEmpty()) { + listIndex = forwardTransactions.size() - 1; + arrayIndex = 0; + return true; + } else { + listIndex = -1; + return false; + } + } + } + } + } + } + + @Override + public boolean isDirty() { + return false; + } + + @Override + public Set getDependingMaps() { + return Collections.emptySet(); + } + + @Override + public V getFromValue() { + return getCurrentDelta().getOldValue(); + } + + @Override + public V getToValue() { + return getCurrentDelta().getNewValue(); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java new file mode 100644 index 00000000..4a8e9709 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java @@ -0,0 +1,62 @@ +package tools.refinery.store.map.internal; + +import java.util.*; +import java.util.Map.Entry; + +import tools.refinery.store.map.AnyVersionedMap; +import tools.refinery.store.map.Cursor; +import tools.refinery.store.map.VersionedMap; + +public class IteratorAsCursor implements Cursor { + final Iterator> iterator; + final VersionedMap source; + + private boolean terminated; + private K key; + private V value; + + public IteratorAsCursor(VersionedMap source, Map current) { + this.iterator = current.entrySet().iterator(); + this.source = source; + move(); + } + + @Override + public K getKey() { + return key; + } + + @Override + public V getValue() { + return value; + } + + @Override + public boolean isTerminated() { + return terminated; + } + + @Override + public boolean move() { + terminated = iterator.hasNext(); + if (terminated) { + this.key = null; + this.value = null; + } else { + Entry next = iterator.next(); + this.key = next.getKey(); + this.value = next.getValue(); + } + return !terminated; + } + + @Override + public boolean isDirty() { + return false; + } + + @Override + public Set getDependingMaps() { + return Set.of(this.source); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java new file mode 100644 index 00000000..86e9fe62 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java @@ -0,0 +1,15 @@ +package tools.refinery.store.map.internal; + +public record MapDelta(K key, V oldValue, V newValue) { + public K getKey() { + return key; + } + + public V getOldValue() { + return oldValue; + } + + public V getNewValue() { + return newValue; + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java new file mode 100644 index 00000000..5996048e --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java @@ -0,0 +1,34 @@ +package tools.refinery.store.map.internal; + +import java.util.Arrays; +import java.util.Objects; + +public record MapTransaction(MapDelta[] deltas, long version, MapTransaction parent) { + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + Arrays.hashCode(deltas); + result = prime * result + Objects.hash(parent, version); + return result; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) + return true; + if (obj == null) + return false; + if (getClass() != obj.getClass()) + return false; + @SuppressWarnings("unchecked") + MapTransaction other = (MapTransaction) obj; + return Arrays.equals(deltas, other.deltas) && Objects.equals(parent, other.parent) && version == other.version; + } + + @Override + public String toString() { + return "MapTransaction " + version + " " + Arrays.toString(deltas); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java new file mode 100644 index 00000000..3b3f94ae --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java @@ -0,0 +1,31 @@ +package tools.refinery.store.map.internal; + +import java.util.ArrayList; +import java.util.List; + +public class UncommittedDeltaArrayStore implements UncommittedDeltaStore { + final List> uncommittedOldValues = new ArrayList<>(); + + @Override + public void processChange(K key, V oldValue, V newValue) { + uncommittedOldValues.add(new MapDelta<>(key, oldValue, newValue)); + } + + @Override + public MapDelta[] extractDeltas() { + if (uncommittedOldValues.isEmpty()) { + return null; + } else { + @SuppressWarnings("unchecked") + MapDelta[] result = uncommittedOldValues.toArray(new MapDelta[0]); + return result; + } + } + + @Override + public MapDelta[] extractAndDeleteDeltas() { + MapDelta[] res = extractDeltas(); + this.uncommittedOldValues.clear(); + return res; + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java new file mode 100644 index 00000000..73df5080 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java @@ -0,0 +1,47 @@ +package tools.refinery.store.map.internal; + +import java.util.HashMap; +import java.util.Map; +import java.util.Map.Entry; + +import tools.refinery.store.map.VersionedMap; + +public class UncommittedDeltaMapStore implements UncommittedDeltaStore { + final VersionedMap source; + final Map uncommittedOldValues = new HashMap<>(); + + public UncommittedDeltaMapStore(VersionedMap source) { + this.source = source; + } + + @Override + public void processChange(K key, V oldValue, V newValue) { + this.uncommittedOldValues.putIfAbsent(key, oldValue); + } + + @Override + public MapDelta[] extractDeltas() { + if (uncommittedOldValues.isEmpty()) { + return null; + } else { + @SuppressWarnings("unchecked") + MapDelta[] deltas = new MapDelta[uncommittedOldValues.size()]; + int i = 0; + for (Entry entry : uncommittedOldValues.entrySet()) { + final K key = entry.getKey(); + final V oldValue = entry.getValue(); + final V newValue = source.get(key); + deltas[i] = new MapDelta<>(key, oldValue, newValue); + } + + return deltas; + } + } + + @Override + public MapDelta[] extractAndDeleteDeltas() { + MapDelta[] res = extractDeltas(); + this.uncommittedOldValues.clear(); + return res; + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java new file mode 100644 index 00000000..37e5817c --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java @@ -0,0 +1,10 @@ +package tools.refinery.store.map.internal; + +public interface UncommittedDeltaStore { + void processChange(K key, V oldValue, V newValue); + + MapDelta[] extractDeltas(); + + MapDelta[] extractAndDeleteDeltas(); + +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java new file mode 100644 index 00000000..deedf134 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java @@ -0,0 +1,156 @@ +package tools.refinery.store.map.internal; + +import java.util.*; + +import tools.refinery.store.map.*; + +public class VersionedMapDeltaImpl implements VersionedMap { + protected final VersionedMapStoreDeltaImpl store; + + final Map current; + + final UncommittedDeltaStore uncommittedStore; + MapTransaction previous; + + protected final V defaultValue; + + public VersionedMapDeltaImpl(VersionedMapStoreDeltaImpl store, V defaultValue) { + this.store = store; + this.defaultValue = defaultValue; + + current = new HashMap<>(); + uncommittedStore = new UncommittedDeltaArrayStore<>(); + } + + @Override + public long commit() { + MapDelta[] deltas = uncommittedStore.extractAndDeleteDeltas(); + long[] versionContainer = new long[1]; + this.previous = this.store.appendTransaction(deltas, previous, versionContainer); + return versionContainer[0]; + } + + @Override + public void restore(long state) { + // 1. restore uncommitted states + MapDelta[] uncommitted = this.uncommittedStore.extractAndDeleteDeltas(); + if (uncommitted != null) { + backward(uncommitted); + } + + // 2. get common ancestor + List[]> forward = new ArrayList<>(); + if (this.previous == null) { + this.store.getPath(state, forward); + this.forward(forward); + } else { + List[]> backward = new ArrayList<>(); + this.store.getPath(this.previous.version(), state, backward, forward); + this.backward(backward); + this.forward(forward); + } + } + + protected void forward(List[]> changes) { + for (int i = changes.size() - 1; i >= 0; i--) { + forward(changes.get(i)); + } + } + + protected void backward(List[]> changes) { + for (int i = 0; i < changes.size(); i++) { + backward(changes.get(i)); + } + } + + protected void forward(MapDelta[] changes) { + for (int i = 0; i < changes.length; i++) { + final MapDelta change = changes[i]; + current.put(change.getKey(), change.getNewValue()); + } + } + + protected void backward(MapDelta[] changes) { + for (int i = changes.length - 1; i >= 0; i--) { + final MapDelta change = changes[i]; + current.put(change.getKey(), change.getOldValue()); + } + } + + @Override + public V get(K key) { + return current.getOrDefault(key, defaultValue); + } + + @Override + public Cursor getAll() { + return new IteratorAsCursor<>(this, current); + } + + @Override + public V put(K key, V value) { + if (value == defaultValue) { + V res = current.remove(key); + if (res == null) { + // no changes + return defaultValue; + } else { + uncommittedStore.processChange(key, res, value); + return res; + } + } else { + V oldValue = current.put(key, value); + uncommittedStore.processChange(key, oldValue, value); + return oldValue; + } + } + + @Override + public void putAll(Cursor cursor) { + throw new UnsupportedOperationException(); + + } + + @Override + public long getSize() { + return current.size(); + } + + @Override + public DiffCursor getDiffCursor(long state) { + MapDelta[] backward = this.uncommittedStore.extractDeltas(); + List[]> backwardTransactions = new ArrayList<>(); + List[]> forwardTransactions = new ArrayList<>(); + + if (backward != null) { + backwardTransactions.add(backward); + } + + if (this.previous != null) { + store.getPath(this.previous.version(), state, backwardTransactions, forwardTransactions); + } else { + store.getPath(state, forwardTransactions); + } + + return new DeltaDiffCursor<>(backwardTransactions, forwardTransactions); + } + + @Override + public int contentHashCode(ContentHashCode mode) { + return this.current.hashCode(); + } + + @Override + public boolean contentEquals(AnyVersionedMap other) { + if (other instanceof VersionedMapDeltaImpl versioned) { + if (versioned == this) { + return true; + } else { + return Objects.equals(this.defaultValue, versioned.defaultValue) && + Objects.equals(this.current, versioned.current); + } + } else { + throw new UnsupportedOperationException("Comparing different map implementations is ineffective."); + } + } +} -- cgit v1.2.3-70-g09d2