From 26592fc70a026b850616fc4bc9be5a46ab1179a9 Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Mon, 24 Jul 2023 16:51:47 +0200 Subject: Refactoring packages related to VersionedMapDeltaImpl + VersionedMapStoreStateImpl, update builder. - details of the maps goes to internal packages - ModelStoreBuilderImpl uses VersionedMapStoreFactoryBuilder --- .../map/benchmarks/ImmutablePutExecutionPlan.java | 17 +- .../refinery/store/map/ContinousHashProvider.java | 74 --- .../refinery/store/map/ContinuousHashProvider.java | 74 +++ .../tools/refinery/store/map/IteratorAsCursor.java | 64 +++ .../store/map/VersionedMapStoreConfiguration.java | 53 --- .../store/map/VersionedMapStoreDeltaImpl.java | 99 ---- .../store/map/VersionedMapStoreFactoryBuilder.java | 2 +- .../refinery/store/map/VersionedMapStoreImpl.java | 129 ------ .../DeltaBasedVersionedMapStoreFactory.java | 39 -- .../store/map/internal/DeltaDiffCursor.java | 147 ------ .../refinery/store/map/internal/HashClash.java | 23 - .../refinery/store/map/internal/ImmutableNode.java | 413 ----------------- .../store/map/internal/InOrderMapCursor.java | 146 ------ .../store/map/internal/IteratorAsCursor.java | 66 --- .../refinery/store/map/internal/MapCursor.java | 95 ---- .../refinery/store/map/internal/MapDelta.java | 20 - .../refinery/store/map/internal/MapDiffCursor.java | 264 ----------- .../store/map/internal/MapTransaction.java | 39 -- .../refinery/store/map/internal/MutableNode.java | 499 --------------------- .../tools/refinery/store/map/internal/Node.java | 131 ------ .../refinery/store/map/internal/OldValueBox.java | 24 - .../StateBasedVersionedMapStoreFactory.java | 38 -- .../map/internal/UncommittedDeltaArrayStore.java | 36 -- .../map/internal/UncommittedDeltaMapStore.java | 53 --- .../store/map/internal/UncommittedDeltaStore.java | 29 -- .../store/map/internal/VersionedMapDeltaImpl.java | 219 --------- .../store/map/internal/VersionedMapImpl.java | 171 ------- .../VersionedMapStoreFactoryBuilderImpl.java | 18 +- .../delta/DeltaBasedVersionedMapStoreFactory.java | 38 ++ .../store/map/internal/delta/DeltaDiffCursor.java | 147 ++++++ .../store/map/internal/delta/MapDelta.java | 20 + .../store/map/internal/delta/MapTransaction.java | 39 ++ .../internal/delta/UncommittedDeltaArrayStore.java | 36 ++ .../internal/delta/UncommittedDeltaMapStore.java | 53 +++ .../map/internal/delta/UncommittedDeltaStore.java | 29 ++ .../map/internal/delta/VersionedMapDeltaImpl.java | 220 +++++++++ .../internal/delta/VersionedMapStoreDeltaImpl.java | 101 +++++ .../store/map/internal/state/ImmutableNode.java | 413 +++++++++++++++++ .../store/map/internal/state/InOrderMapCursor.java | 146 ++++++ .../store/map/internal/state/MapCursor.java | 95 ++++ .../store/map/internal/state/MapDiffCursor.java | 264 +++++++++++ .../store/map/internal/state/MutableNode.java | 499 +++++++++++++++++++++ .../refinery/store/map/internal/state/Node.java | 131 ++++++ .../store/map/internal/state/OldValueBox.java | 24 + .../state/StateBasedVersionedMapStoreFactory.java | 38 ++ .../map/internal/state/VersionedMapStateImpl.java | 171 +++++++ .../state/VersionedMapStoreStateConfiguration.java | 56 +++ .../internal/state/VersionedMapStoreStateImpl.java | 129 ++++++ .../refinery/store/model/TupleHashProvider.java | 4 +- .../store/model/TupleHashProviderBitMagic.java | 34 -- .../model/internal/ModelStoreBuilderImpl.java | 12 +- .../store/map/tests/InOrderCursorTest.java | 8 +- .../refinery/store/map/tests/MapUnitTests.java | 4 +- .../fuzz/MutableImmutableCompareFuzzTest.java | 18 +- .../store/map/tests/fuzz/SharedStoreFuzzTest.java | 18 +- .../store/map/tests/utils/MapTestEnvironment.java | 6 +- .../store/model/hashtests/HashEfficiencyTest.java | 13 +- 57 files changed, 2849 insertions(+), 2899 deletions(-) delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/ContinousHashProvider.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/ContinuousHashProvider.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/IteratorAsCursor.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreConfiguration.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaBasedVersionedMapStoreFactory.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/OldValueBox.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/StateBasedVersionedMapStoreFactory.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaBasedVersionedMapStoreFactory.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaDiffCursor.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapDelta.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapTransaction.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaArrayStore.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaMapStore.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaStore.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/ImmutableNode.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/InOrderMapCursor.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapCursor.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapDiffCursor.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MutableNode.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/Node.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/OldValueBox.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStateImpl.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateConfiguration.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java (limited to 'subprojects/store/src') diff --git a/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java b/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java index 7e89cd06..4708e6d3 100644 --- a/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java +++ b/subprojects/store/src/jmh/java/tools/refinery/store/map/benchmarks/ImmutablePutExecutionPlan.java @@ -5,12 +5,13 @@ */ package tools.refinery.store.map.benchmarks; +import java.util.Objects; import java.util.Random; -import tools.refinery.store.map.ContinousHashProvider; +import tools.refinery.store.map.ContinuousHashProvider; import tools.refinery.store.map.VersionedMapStore; -import tools.refinery.store.map.VersionedMapStoreImpl; -import tools.refinery.store.map.internal.VersionedMapImpl; +import tools.refinery.store.map.internal.state.VersionedMapStoreStateImpl; +import tools.refinery.store.map.internal.state.VersionedMapStateImpl; import tools.refinery.store.map.tests.utils.MapTestEnvironment; import org.openjdk.jmh.annotations.Level; @@ -35,7 +36,7 @@ public class ImmutablePutExecutionPlan { private String[] values; - private ContinousHashProvider hashProvider = MapTestEnvironment.prepareHashProvider(false); + private ContinuousHashProvider hashProvider = MapTestEnvironment.prepareHashProvider(false); @Setup(Level.Trial) public void setUpTrial() { @@ -43,9 +44,9 @@ public class ImmutablePutExecutionPlan { values = MapTestEnvironment.prepareValues(nValues, true); } - public VersionedMapImpl createSut() { - VersionedMapStore store = new VersionedMapStoreImpl(hashProvider, values[0]); - return (VersionedMapImpl) store.createMap(); + public VersionedMapStateImpl createSut() { + VersionedMapStore store = new VersionedMapStoreStateImpl<>(hashProvider, values[0]); + return (VersionedMapStateImpl) store.createMap(); } public Integer nextKey() { @@ -53,7 +54,7 @@ public class ImmutablePutExecutionPlan { } public boolean isDefault(String value) { - return value == values[0]; + return Objects.equals(value,values[0]); } public String nextValue() { diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/ContinousHashProvider.java b/subprojects/store/src/main/java/tools/refinery/store/map/ContinousHashProvider.java deleted file mode 100644 index 8e451230..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/ContinousHashProvider.java +++ /dev/null @@ -1,74 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map; - -import tools.refinery.store.map.internal.Node; - -/** - * A class representing an equivalence relation for a type {@code K} with a - * continuous hash function. - * - * @author Oszkar Semerath - * - * @param Target java type. - */ -public interface ContinousHashProvider { - public static final int EFFECTIVE_BITS = Node.EFFECTIVE_BITS; - public static final int EFFECTIVE_BIT_MASK = (1 << (EFFECTIVE_BITS)) - 1; - - /** - * Maximal practical depth for differentiating keys. If two keys have the same - * hash code until that depth, the algorithm can stop. - */ - public static final int MAX_PRACTICAL_DEPTH = 500; - - /** - * Provides a hash code for a object {@code key} with a given {@code index}. It - * has the following contracts: - *
    - *
  • If {@link #equals}{@code (key1,key2)}, then - * {@code getHash(key1, index) == getHash(key2, index)} for all values of - * {@code index}.
    • - *
  • If {@code getHash(key1,index) == getHash(key2, index)} for all values of - * {@code index}, then {@link #equals}{@code (key1, key2)}
    • - *
  • In current implementation, we use only the least significant - * {@link #EFFECTIVE_BITS} - *
- * Check {@link #equals} for further details. - * - * @param key The target data object. - * @param index The depth of the the hash code. Needs to be non-negative. - * @return A hash code. - */ - public int getHash(K key, int index); - - public default int getEffectiveHash(K key, int index) { - return getHash(key, index) & EFFECTIVE_BIT_MASK; - } - - public default int compare(K key1, K key2) { - if (key1.equals(key2)) { - return 0; - } else { - for (int i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) { - int hash1 = getEffectiveHash(key1, i); - int hash2 = getEffectiveHash(key2, i); - for(int j = 0; j>>j*Node.BRANCHING_FACTOR_BITS) & factorMask; - int hashFragment2 = (hash2>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask; - var result = Integer.compare(hashFragment1, hashFragment2); - if (result != 0) { - return result; - } - } - } - throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2 - + ") have the same hashcode over the practical depth limitation (" - + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!"); - } - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/ContinuousHashProvider.java b/subprojects/store/src/main/java/tools/refinery/store/map/ContinuousHashProvider.java new file mode 100644 index 00000000..abc044d0 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/ContinuousHashProvider.java @@ -0,0 +1,74 @@ +/* + * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map; + +import tools.refinery.store.map.internal.state.Node; + +/** + * A class representing an equivalence relation for a type {@code K} with a + * continuous hash function. + * + * @author Oszkar Semerath + * + * @param Target java type. + */ +public interface ContinuousHashProvider { + public static final int EFFECTIVE_BITS = Node.EFFECTIVE_BITS; + public static final int EFFECTIVE_BIT_MASK = (1 << (EFFECTIVE_BITS)) - 1; + + /** + * Maximal practical depth for differentiating keys. If two keys have the same + * hash code until that depth, the algorithm can stop. + */ + public static final int MAX_PRACTICAL_DEPTH = 500; + + /** + * Provides a hash code for a object {@code key} with a given {@code index}. It + * has the following contracts: + *
    + *
  • If {@link #equals}{@code (key1,key2)}, then + * {@code getHash(key1, index) == getHash(key2, index)} for all values of + * {@code index}.
    • + *
  • If {@code getHash(key1,index) == getHash(key2, index)} for all values of + * {@code index}, then {@link #equals}{@code (key1, key2)}
    • + *
  • In current implementation, we use only the least significant + * {@link #EFFECTIVE_BITS} + *
+ * Check {@link #equals} for further details. + * + * @param key The target data object. + * @param index The depth of the hash code. Needs to be non-negative. + * @return A hash code. + */ + public int getHash(K key, int index); + + public default int getEffectiveHash(K key, int index) { + return getHash(key, index) & EFFECTIVE_BIT_MASK; + } + + public default int compare(K key1, K key2) { + if (key1.equals(key2)) { + return 0; + } else { + for (int i = 0; i < ContinuousHashProvider.MAX_PRACTICAL_DEPTH; i++) { + int hash1 = getEffectiveHash(key1, i); + int hash2 = getEffectiveHash(key2, i); + for(int j = 0; j>>j*Node.BRANCHING_FACTOR_BITS) & factorMask; + int hashFragment2 = (hash2>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask; + var result = Integer.compare(hashFragment1, hashFragment2); + if (result != 0) { + return result; + } + } + } + throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2 + + ") have the same hashcode over the practical depth limitation (" + + ContinuousHashProvider.MAX_PRACTICAL_DEPTH + ")!"); + } + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/IteratorAsCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/IteratorAsCursor.java new file mode 100644 index 00000000..29b03edf --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/IteratorAsCursor.java @@ -0,0 +1,64 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map; + +import java.util.Iterator; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Set; + +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; + } + + @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/VersionedMapStoreConfiguration.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreConfiguration.java deleted file mode 100644 index b00cd961..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreConfiguration.java +++ /dev/null @@ -1,53 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map; - -public class VersionedMapStoreConfiguration { - - public VersionedMapStoreConfiguration() { - - } - public VersionedMapStoreConfiguration(boolean immutableWhenCommitting, boolean sharedNodeCacheInStore, - boolean sharedNodeCacheInStoreGroups) { - super(); - this.immutableWhenCommitting = immutableWhenCommitting; - this.sharedNodeCacheInStore = sharedNodeCacheInStore; - this.sharedNodeCacheInStoreGroups = sharedNodeCacheInStoreGroups; - } - - /** - * If true root is replaced with immutable node when committed. Frees up memory - * by releasing immutable nodes, but it may decrease performance by recreating - * immutable nodes upon changes (some evidence). - */ - private boolean immutableWhenCommitting = true; - public boolean isImmutableWhenCommitting() { - return immutableWhenCommitting; - } - - /** - * If true, all sub-nodes are cached within a {@link VersionedMapStore}. It - * decreases the memory requirements. It may increase performance by discovering - * existing immutable copy of a node (some evidence). Additional overhead may - * decrease performance (no example found). The option permits the efficient - * implementation of version deletion. - */ - private boolean sharedNodeCacheInStore = true; - public boolean isSharedNodeCacheInStore() { - return sharedNodeCacheInStore; - } - - /** - * If true, all sub-nodes are cached within a group of - * {@link VersionedMapStoreImpl#createSharedVersionedMapStores(int, ContinousHashProvider, Object, VersionedMapStoreConfiguration)}. - * If {@link VersionedMapStoreConfiguration#sharedNodeCacheInStore} is - * false, then it has currently no impact. - */ - private boolean sharedNodeCacheInStoreGroups = true; - public boolean isSharedNodeCacheInStoreGroups() { - return sharedNodeCacheInStoreGroups; - } -} 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 deleted file mode 100644 index 0c61bd09..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java +++ /dev/null @@ -1,99 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map; - -import java.util.*; - -import tools.refinery.store.map.internal.*; - -public class VersionedMapStoreDeltaImpl implements VersionedMapStore { - // Configuration - protected final boolean summarizeChanges; - - // Static data - protected final V defaultValue; - - // Dynamic data - protected final Map> states = new HashMap<>(); - protected long nextID = 0; - - public VersionedMapStoreDeltaImpl(boolean summarizeChanges, V defaultValue) { - this.summarizeChanges = summarizeChanges; - this.defaultValue = defaultValue; - } - - @Override - public VersionedMap createMap() { - return new VersionedMapDeltaImpl<>(this, this.summarizeChanges, this.defaultValue); - } - - @Override - public VersionedMap createMap(long state) { - VersionedMapDeltaImpl result = new VersionedMapDeltaImpl<>(this, this.summarizeChanges, 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 MapTransaction getPath(long to, List[]> forwardTransactions) { - final MapTransaction target = getState(to); - MapTransaction toTransaction = target; - while (toTransaction != null) { - forwardTransactions.add(toTransaction.deltas()); - toTransaction = toTransaction.parent(); - } - return target; - } - - public MapTransaction getPath(long from, long to, - List[]> backwardTransactions, - List[]> forwardTransactions) { - MapTransaction fromTransaction = getState(from); - final MapTransaction target = getState(to); - MapTransaction toTransaction = target; - - while (fromTransaction != toTransaction) { - if (fromTransaction == null || (toTransaction != null && fromTransaction.version() < toTransaction.version())) { - forwardTransactions.add(toTransaction.deltas()); - toTransaction = toTransaction.parent(); - } else { - backwardTransactions.add(fromTransaction.deltas()); - fromTransaction = fromTransaction.parent(); - } - } - return target; - } - - - @Override - public synchronized Set getStates() { - return new HashSet<>(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/VersionedMapStoreFactoryBuilder.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java index 6329a2f6..6b4fc2a0 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java @@ -22,7 +22,7 @@ public interface VersionedMapStoreFactoryBuilder { VersionedMapStoreFactoryBuilder strategy(StoreStrategy strategy); VersionedMapStoreFactoryBuilder stateBasedImmutableWhenCommitting(boolean transformToImmutable); VersionedMapStoreFactoryBuilder stateBasedSharingStrategy(SharingStrategy sharingStrategy); - VersionedMapStoreFactoryBuilder stateBasedHashProvider(ContinousHashProvider hashProvider); + VersionedMapStoreFactoryBuilder stateBasedHashProvider(ContinuousHashProvider hashProvider); VersionedMapStoreFactoryBuilder deltaTransactionStrategy(DeltaTransactionStrategy deltaStrategy); VersionedMapStoreFactory build(); diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java deleted file mode 100644 index a934d59e..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java +++ /dev/null @@ -1,129 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map; - -import tools.refinery.store.map.internal.*; - -import java.util.*; - -public class VersionedMapStoreImpl implements VersionedMapStore { - // Configuration - private final boolean immutableWhenCommitting; - - // Static data - protected final ContinousHashProvider hashProvider; - protected final V defaultValue; - - // Dynamic data - protected final Map> states = new HashMap<>(); - protected final Map, ImmutableNode> nodeCache; - protected long nextID = 0; - - public VersionedMapStoreImpl(ContinousHashProvider hashProvider, V defaultValue, - VersionedMapStoreConfiguration config) { - this.immutableWhenCommitting = config.isImmutableWhenCommitting(); - this.hashProvider = hashProvider; - this.defaultValue = defaultValue; - if (config.isSharedNodeCacheInStore()) { - nodeCache = new HashMap<>(); - } else { - nodeCache = null; - } - } - - private VersionedMapStoreImpl(ContinousHashProvider hashProvider, V defaultValue, - Map, ImmutableNode> nodeCache, VersionedMapStoreConfiguration config) { - this.immutableWhenCommitting = config.isImmutableWhenCommitting(); - this.hashProvider = hashProvider; - this.defaultValue = defaultValue; - this.nodeCache = nodeCache; - } - - public VersionedMapStoreImpl(ContinousHashProvider hashProvider, V defaultValue) { - this(hashProvider, defaultValue, new VersionedMapStoreConfiguration()); - } - - public static List> createSharedVersionedMapStores(int amount, - ContinousHashProvider hashProvider, V defaultValue, - VersionedMapStoreConfiguration config) { - List> result = new ArrayList<>(amount); - if (config.isSharedNodeCacheInStoreGroups()) { - Map, ImmutableNode> nodeCache; - if (config.isSharedNodeCacheInStore()) { - nodeCache = new HashMap<>(); - } else { - nodeCache = null; - } - for (int i = 0; i < amount; i++) { - result.add(new VersionedMapStoreImpl<>(hashProvider, defaultValue, nodeCache, config)); - } - } else { - for (int i = 0; i < amount; i++) { - result.add(new VersionedMapStoreImpl<>(hashProvider, defaultValue, config)); - } - } - return result; - } - - public static List> createSharedVersionedMapStores(int amount, - ContinousHashProvider hashProvider, V defaultValue) { - return createSharedVersionedMapStores(amount, hashProvider, defaultValue, new VersionedMapStoreConfiguration()); - } - - @Override - public synchronized Set getStates() { - return new HashSet<>(states.keySet()); - } - - @Override - public VersionedMap createMap() { - return new VersionedMapImpl<>(this, hashProvider, defaultValue); - } - - @Override - public VersionedMap createMap(long state) { - ImmutableNode data = revert(state); - return new VersionedMapImpl<>(this, hashProvider, defaultValue, data); - } - - public synchronized ImmutableNode revert(long state) { - if (states.containsKey(state)) { - return states.get(state); - } else { - ArrayList existingKeys = new ArrayList<>(states.keySet()); - Collections.sort(existingKeys); - throw new IllegalArgumentException("Store does not contain state " + state + "! Available states: " - + Arrays.toString(existingKeys.toArray())); - } - } - - public synchronized long commit(Node data, VersionedMapImpl mapToUpdateRoot) { - ImmutableNode immutable; - if (data != null) { - immutable = data.toImmutable(this.nodeCache); - } else { - immutable = null; - } - - if (nextID == Long.MAX_VALUE) - throw new IllegalStateException("Map store run out of Id-s"); - long id = nextID++; - this.states.put(id, immutable); - if (this.immutableWhenCommitting) { - mapToUpdateRoot.setRoot(immutable); - } - return id; - } - - @Override - public DiffCursor getDiffCursor(long fromState, long toState) { - VersionedMapImpl map1 = (VersionedMapImpl) createMap(fromState); - VersionedMapImpl map2 = (VersionedMapImpl) createMap(toState); - InOrderMapCursor cursor1 = new InOrderMapCursor<>(map1); - InOrderMapCursor cursor2 = new InOrderMapCursor<>(map2); - return new MapDiffCursor<>(this.defaultValue, cursor1, cursor2); - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaBasedVersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaBasedVersionedMapStoreFactory.java deleted file mode 100644 index fe490f46..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaBasedVersionedMapStoreFactory.java +++ /dev/null @@ -1,39 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import tools.refinery.store.map.VersionedMapStore; -import tools.refinery.store.map.VersionedMapStoreDeltaImpl; -import tools.refinery.store.map.VersionedMapStoreFactory; -import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; - -import java.util.ArrayList; -import java.util.List; - -public class DeltaBasedVersionedMapStoreFactory implements VersionedMapStoreFactory { - private final V defaultValue; - private final boolean summarizeChanges; - - public DeltaBasedVersionedMapStoreFactory(V defaultValue, - VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy deltaTransactionStrategy) { - this.defaultValue = defaultValue; - this.summarizeChanges = deltaTransactionStrategy == VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy.SET; - } - - @Override - public VersionedMapStore createOne() { - return new VersionedMapStoreDeltaImpl<>(summarizeChanges, defaultValue); - } - - @Override - public List> createGroup(int amount) { - List> result = new ArrayList<>(amount); - for(int i=0; i(summarizeChanges,defaultValue)); - } - return result; - } -} 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 deleted file mode 100644 index cc9003e3..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java +++ /dev/null @@ -1,147 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -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; - - boolean started; - /** - * 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; - } - started = false; - } - - 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(!started) { - started = true; - return !isTerminated(); - } else if (isTerminated()) { - return false; - } else { - if (this.direction) { - if (arrayIndex+1 < forwardTransactions.get(listIndex).length) { - arrayIndex++; - return true; - } else { - if (listIndex-1 >= 0) { - listIndex--; - arrayIndex = 0; - 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() { - if(this.direction) { - return getCurrentDelta().getOldValue(); - } else { - return getCurrentDelta().getNewValue(); - } - } - - @Override - public V getToValue() { - if(this.direction) { - return getCurrentDelta().getNewValue(); - } else { - return getCurrentDelta().getOldValue(); - } - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java deleted file mode 100644 index a357fbce..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/HashClash.java +++ /dev/null @@ -1,23 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -enum HashClash { - /** - * Not stuck. - */ - NONE, - - /** - * Clashed, next we should return the key of cursor 1. - */ - STUCK_CURSOR_1, - - /** - * Clashed, next we should return the key of cursor 2. - */ - STUCK_CURSOR_2 -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java deleted file mode 100644 index d052318f..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java +++ /dev/null @@ -1,413 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import java.util.Arrays; -import java.util.Map; - -import tools.refinery.store.map.ContinousHashProvider; - -public class ImmutableNode extends Node { - /** - * Bitmap defining the stored key and values. - */ - final int dataMap; - /** - * Bitmap defining the positions of further nodes. - */ - final int nodeMap; - /** - * Stores Keys, Values, and sub-nodes. Structure: (K,V)*,NODE; NODES are stored - * backwards. - */ - final Object[] content; - - /** - * Hash code derived from immutable hash code - */ - final int precalculatedHash; - - private ImmutableNode(int dataMap, int nodeMap, Object[] content, int precalculatedHash) { - super(); - this.dataMap = dataMap; - this.nodeMap = nodeMap; - this.content = content; - this.precalculatedHash = precalculatedHash; - } - - /** - * Constructor that copies a mutable node to an immutable. - * - * @param node A mutable node. - * @param cache A cache of existing immutable nodes. It can be used to search - * and place reference immutable nodes. It can be null, if no cache - * available. - * @return an immutable version of the input node. - */ - static ImmutableNode constructImmutable(MutableNode node, Map, ImmutableNode> cache) { - // 1. try to return from cache - if (cache != null) { - ImmutableNode cachedResult = cache.get(node); - if (cachedResult != null) { - // 1.1 Already cached, return from cache. - return cachedResult; - } - } - - // 2. otherwise construct a new ImmutableNode - int size = 0; - for (int i = 0; i < node.content.length; i++) { - if (node.content[i] != null) { - size++; - } - } - - int datas = 0; - int nodes = 0; - int resultDataMap = 0; - int resultNodeMap = 0; - final Object[] resultContent = new Object[size]; - int bitPosition = 1; - for (int i = 0; i < FACTOR; i++) { - Object key = node.content[i * 2]; - if (key != null) { - resultDataMap |= bitPosition; - resultContent[datas * 2] = key; - resultContent[datas * 2 + 1] = node.content[i * 2 + 1]; - datas++; - } else { - @SuppressWarnings("unchecked") var subnode = (Node) node.content[i * 2 + 1]; - if (subnode != null) { - ImmutableNode immutableSubNode = subnode.toImmutable(cache); - resultNodeMap |= bitPosition; - resultContent[size - 1 - nodes] = immutableSubNode; - nodes++; - } - } - bitPosition <<= 1; - } - final int resultHash = node.hashCode(); - var newImmutable = new ImmutableNode(resultDataMap, resultNodeMap, resultContent, resultHash); - - // 3. save new immutable. - if (cache != null) { - cache.put(newImmutable, newImmutable); - } - return newImmutable; - } - - private int index(int bitmap, int bitpos) { - return Integer.bitCount(bitmap & (bitpos - 1)); - } - - @Override - public V getValue(K key, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth) { - int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); - int bitposition = 1 << selectedHashFragment; - // If the key is stored as a data - if ((dataMap & bitposition) != 0) { - int keyIndex = 2 * index(dataMap, bitposition); - @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; - if (keyCandidate.equals(key)) { - @SuppressWarnings("unchecked") V value = (V) content[keyIndex + 1]; - return value; - } else { - return defaultValue; - } - } - // the key is stored as a node - else if ((nodeMap & bitposition) != 0) { - int keyIndex = content.length - 1 - index(nodeMap, bitposition); - @SuppressWarnings("unchecked") var subNode = (ImmutableNode) content[keyIndex]; - int newDepth = incrementDepth(depth); - int newHash = newHash(hashProvider, key, hash, newDepth); - return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); - } - // the key is not stored at all - else { - return defaultValue; - } - } - - @Override - public Node putValue(K key, V value, OldValueBox oldValue, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth) { - int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); - int bitPosition = 1 << selectedHashFragment; - if ((dataMap & bitPosition) != 0) { - int keyIndex = 2 * index(dataMap, bitPosition); - @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; - if (keyCandidate.equals(key)) { - if (value == defaultValue) { - // delete - MutableNode mutable = this.toMutable(); - return mutable.removeEntry(selectedHashFragment, oldValue); - } else if (value == content[keyIndex + 1]) { - // dont change - oldValue.setOldValue(value); - return this; - } else { - // update existing value - MutableNode mutable = this.toMutable(); - return mutable.updateValue(value, oldValue, selectedHashFragment); - } - } else { - if (value == defaultValue) { - // dont change - oldValue.setOldValue(defaultValue); - return this; - } else { - // add new key + value - MutableNode mutable = this.toMutable(); - return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); - } - } - } else if ((nodeMap & bitPosition) != 0) { - int keyIndex = content.length - 1 - index(nodeMap, bitPosition); - @SuppressWarnings("unchecked") var subNode = (ImmutableNode) content[keyIndex]; - int newDepth = incrementDepth(depth); - int newHash = newHash(hashProvider, key, hash, newDepth); - var newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth); - - if (subNode == newsubNode) { - // nothing changed - return this; - } else { - MutableNode mutable = toMutable(); - return mutable.updateWithSubNode(selectedHashFragment, newsubNode, - (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); - } - } else { - // add new key + value - MutableNode mutable = this.toMutable(); - return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); - } - } - - @Override - public long getSize() { - int result = Integer.bitCount(this.dataMap); - for (int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) { - @SuppressWarnings("unchecked") var subnode = (ImmutableNode) this.content[this.content.length - 1 - subnodeIndex]; - result += subnode.getSize(); - } - return result; - } - - @Override - protected MutableNode toMutable() { - return new MutableNode<>(this); - } - - @Override - public ImmutableNode toImmutable(Map, ImmutableNode> cache) { - return this; - } - - @Override - protected MutableNode isMutable() { - return null; - } - - @SuppressWarnings("unchecked") - @Override - boolean moveToNext(MapCursor cursor) { - // 1. try to move to data - int datas = Integer.bitCount(this.dataMap); - if (cursor.dataIndex != MapCursor.INDEX_FINISH) { - int newDataIndex = cursor.dataIndex + 1; - if (newDataIndex < datas) { - cursor.dataIndex = newDataIndex; - cursor.key = (K) this.content[newDataIndex * 2]; - cursor.value = (V) this.content[newDataIndex * 2 + 1]; - return true; - } else { - cursor.dataIndex = MapCursor.INDEX_FINISH; - } - } - - // 2. look inside the subnodes - int nodes = Integer.bitCount(this.nodeMap); - if(cursor.nodeIndexStack.peek()==null) { - throw new IllegalStateException("Cursor moved to the next state when the state is empty."); - } - int newNodeIndex = cursor.nodeIndexStack.peek() + 1; - if (newNodeIndex < nodes) { - // 2.1 found next subnode, move down to the subnode - Node subnode = (Node) this.content[this.content.length - 1 - newNodeIndex]; - cursor.dataIndex = MapCursor.INDEX_START; - cursor.nodeIndexStack.pop(); - cursor.nodeIndexStack.push(newNodeIndex); - cursor.nodeIndexStack.push(MapCursor.INDEX_START); - cursor.nodeStack.push(subnode); - return subnode.moveToNext(cursor); - } else { - // 3. no subnode found, move up - cursor.nodeStack.pop(); - cursor.nodeIndexStack.pop(); - if (!cursor.nodeStack.isEmpty()) { - Node supernode = cursor.nodeStack.peek(); - return supernode.moveToNext(cursor); - } else { - cursor.key = null; - cursor.value = null; - return false; - } - } - } - - @Override - @SuppressWarnings("unchecked") - boolean moveToNextInorder(InOrderMapCursor cursor) { - if(cursor.nodeIndexStack.peek()==null) { - throw new IllegalStateException("Cursor moved to the next state when the state is empty."); - } - - int position = cursor.nodeIndexStack.peek(); - for (int index = position + 1; index < FACTOR; index++) { - final int mask = 1< subnode = (Node) this.content[this.content.length - 1 - index(nodeMap, mask)]; - cursor.nodeIndexStack.pop(); - cursor.nodeIndexStack.push(index); - cursor.nodeIndexStack.push(InOrderMapCursor.INDEX_START); - cursor.nodeStack.push(subnode); - - return subnode.moveToNextInorder(cursor); - } - } - - // nothing found - cursor.nodeStack.pop(); - cursor.nodeIndexStack.pop(); - if (!cursor.nodeStack.isEmpty()) { - Node supernode = cursor.nodeStack.peek(); - return supernode.moveToNextInorder(cursor); - } else { - cursor.key = null; - cursor.value = null; - return false; - } - } - - @Override - public void prettyPrint(StringBuilder builder, int depth, int code) { - builder.append("\t".repeat(Math.max(0, depth))); - if (code >= 0) { - builder.append(code); - builder.append(":"); - } - builder.append("Immutable("); - boolean hadContent = false; - int dataMask = 1; - for (int i = 0; i < FACTOR; i++) { - if ((dataMask & dataMap) != 0) { - if (hadContent) { - builder.append(","); - } - builder.append(i); - builder.append(":["); - builder.append(content[2 * index(dataMap, dataMask)].toString()); - builder.append("]->["); - builder.append(content[2 * index(dataMap, dataMask) + 1].toString()); - builder.append("]"); - hadContent = true; - } - dataMask <<= 1; - } - builder.append(")"); - int nodeMask = 1; - for (int i = 0; i < FACTOR; i++) { - if ((nodeMask & nodeMap) != 0) { - @SuppressWarnings("unchecked") Node subNode = (Node) content[content.length - 1 - index(nodeMap, nodeMask)]; - builder.append("\n"); - subNode.prettyPrint(builder, incrementDepth(depth), i); - } - nodeMask <<= 1; - } - } - - @Override - public void checkIntegrity(ContinousHashProvider hashProvider, V defaultValue, int depth) { - if (depth > 0) { - boolean orphaned = Integer.bitCount(dataMap) == 1 && nodeMap == 0; - if (orphaned) { - throw new IllegalStateException("Orphaned node! " + dataMap + ": " + content[0]); - } - } - // check the place of data - - // check subnodes - for (int i = 0; i < Integer.bitCount(nodeMap); i++) { - @SuppressWarnings("unchecked") var subnode = (Node) this.content[this.content.length - 1 - i]; - if (!(subnode instanceof ImmutableNode)) { - throw new IllegalStateException("Immutable node contains mutable subnodes!"); - } else { - subnode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth)); - } - } - } - - @Override - public int hashCode() { - return this.precalculatedHash; - } - - @Override - public boolean equals(Object obj) { - if (this == obj) return true; - if (obj == null) return false; - if (obj instanceof ImmutableNode other) { - return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap && Arrays.deepEquals(content, other.content); - } else if (obj instanceof MutableNode mutableObj) { - return ImmutableNode.compareImmutableMutable(this, mutableObj); - } else { - return false; - } - } - - public static boolean compareImmutableMutable(ImmutableNode immutable, MutableNode mutable) { - int datas = 0; - int nodes = 0; - final int immutableLength = immutable.content.length; - for (int i = 0; i < FACTOR; i++) { - Object key = mutable.content[i * 2]; - // For each key candidate - if (key != null) { - // Check whether a new Key-Value pair can fit into the immutable container - if (datas * 2 + nodes + 2 <= immutableLength) { - if (!immutable.content[datas * 2].equals(key) || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) { - return false; - } - } else return false; - datas++; - } else { - var mutableSubnode = (Node) mutable.content[i * 2 + 1]; - if (mutableSubnode != null) { - if (datas * 2 + nodes + 1 <= immutableLength) { - Object immutableSubNode = immutable.content[immutableLength - 1 - nodes]; - if (!mutableSubnode.equals(immutableSubNode)) { - return false; - } - nodes++; - } else { - return false; - } - } - } - } - - return datas * 2 + nodes == immutable.content.length; - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java deleted file mode 100644 index cb3f366f..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java +++ /dev/null @@ -1,146 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import tools.refinery.store.map.AnyVersionedMap; -import tools.refinery.store.map.ContentHashCode; -import tools.refinery.store.map.Cursor; -import tools.refinery.store.map.VersionedMap; - -import java.util.*; - -public class InOrderMapCursor implements Cursor { - // Constants - static final int INDEX_START = -1; - - // Tree stack - ArrayDeque> nodeStack; - ArrayDeque nodeIndexStack; - - - // Values - K key; - V value; - - // Hash code for checking concurrent modifications - final VersionedMap map; - final int creationHash; - - public InOrderMapCursor(VersionedMapImpl map) { - // Initializing tree stack - super(); - this.nodeStack = new ArrayDeque<>(); - this.nodeIndexStack = new ArrayDeque<>(); - if (map.root != null) { - this.nodeStack.add(map.root); - this.nodeIndexStack.push(INDEX_START); - } - - // Initializing cache - this.key = null; - this.value = null; - - // Initializing state - this.map = map; - this.creationHash = map.contentHashCode(ContentHashCode.APPROXIMATE_FAST); - } - - public K getKey() { - return key; - } - - public V getValue() { - return value; - } - - public boolean isTerminated() { - return this.nodeStack.isEmpty(); - } - - public boolean move() { - if (isDirty()) { - throw new ConcurrentModificationException(); - } - if (!isTerminated()) { - var node = this.nodeStack.peek(); - if (node == null) { - throw new IllegalStateException("Cursor is not terminated but the current node is missing"); - } - boolean result = node.moveToNextInorder(this); - if (this.nodeIndexStack.size() != this.nodeStack.size()) { - throw new IllegalArgumentException("Node stack is corrupted by illegal moves!"); - } - return result; - } - return false; - } - - public boolean skipCurrentNode() { - nodeStack.pop(); - nodeIndexStack.pop(); - return move(); - } - - @Override - public boolean isDirty() { - return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; - } - - @Override - public Set getDependingMaps() { - return Set.of(this.map); - } - - public static boolean sameSubNode(InOrderMapCursor cursor1, InOrderMapCursor cursor2) { - Node nodeOfCursor1 = cursor1.nodeStack.peek(); - Node nodeOfCursor2 = cursor2.nodeStack.peek(); - return Objects.equals(nodeOfCursor1, nodeOfCursor2); - } - - /** - * Compares the state of two cursors started on two {@link VersionedMap} of the same - * {@link tools.refinery.store.map.VersionedMapStore}. - * @param Key type - * @param Value type - * @param cursor1 first cursor - * @param cursor2 second cursor - * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the - * same position. - */ - public static int comparePosition(InOrderMapCursor cursor1, InOrderMapCursor cursor2) { - // If the state does not determine the order, then compare @nodeIndexStack. - Iterator nodeIndexStack1 = cursor1.nodeIndexStack.descendingIterator(); - Iterator nodeIndexStack2 = cursor2.nodeIndexStack.descendingIterator(); - - while(nodeIndexStack1.hasNext() && nodeIndexStack2.hasNext()){ - final int index1 = nodeIndexStack1.next(); - final int index2 = nodeIndexStack2.next(); - if(index1 < index2) { - return 1; - } else if(index1 > index2) { - return -1; - } - } - - return 0; - } - - /** - * Compares the depth of two cursors started on @{@link VersionedMap} of the same - * {@link tools.refinery.store.map.VersionedMapStore}. - * @param Key type - * @param Value type - * @param cursor1 first cursor - * @param cursor2 second cursor - * @return Positive number if cursor 1 is deeper, negative number if cursor 2 is deeper, and 0 if they are at the - * same depth. - */ - public static int compareDepth(InOrderMapCursor cursor1, InOrderMapCursor cursor2) { - int d1 = cursor1.nodeIndexStack.size(); - int d2 = cursor2.nodeIndexStack.size(); - return Integer.compare(d1, d2); - } -} 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 deleted file mode 100644 index d1ab8bb1..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java +++ /dev/null @@ -1,66 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -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; - } - - @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/MapCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java deleted file mode 100644 index d42519b2..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapCursor.java +++ /dev/null @@ -1,95 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import tools.refinery.store.map.AnyVersionedMap; -import tools.refinery.store.map.ContentHashCode; -import tools.refinery.store.map.Cursor; -import tools.refinery.store.map.VersionedMap; - -import java.util.ArrayDeque; -import java.util.ConcurrentModificationException; -import java.util.Set; - -public class MapCursor implements Cursor { - // Constants - static final int INDEX_START = -1; - static final int INDEX_FINISH = -2; - - // Tree stack - ArrayDeque> nodeStack; - ArrayDeque nodeIndexStack; - int dataIndex; - - // Values - K key; - V value; - - // Hash code for checking concurrent modifications - final VersionedMap map; - final int creationHash; - - public MapCursor(Node root, VersionedMap map) { - // Initializing tree stack - super(); - this.nodeStack = new ArrayDeque<>(); - this.nodeIndexStack = new ArrayDeque<>(); - if (root != null) { - this.nodeStack.add(root); - this.nodeIndexStack.push(INDEX_START); - } - - this.dataIndex = INDEX_START; - - // Initializing cache - this.key = null; - this.value = null; - - // Initializing state - this.map = map; - this.creationHash = map.contentHashCode(ContentHashCode.APPROXIMATE_FAST); - } - - public K getKey() { - return key; - } - - public V getValue() { - return value; - } - - public boolean isTerminated() { - return this.nodeStack.isEmpty(); - } - - public boolean move() { - if (isDirty()) { - throw new ConcurrentModificationException(); - } - if (!isTerminated()) { - var node = this.nodeStack.peek(); - if (node == null) { - throw new IllegalStateException("Cursor is not terminated but the current node is missing"); - } - boolean result = node.moveToNext(this); - if (this.nodeIndexStack.size() != this.nodeStack.size()) { - throw new IllegalArgumentException("Node stack is corrupted by illegal moves!"); - } - return result; - } - return false; - } - - @Override - public boolean isDirty() { - return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; - } - - @Override - public Set getDependingMaps() { - return Set.of(this.map); - } -} 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 deleted file mode 100644 index 2674236c..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java +++ /dev/null @@ -1,20 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -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/MapDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java deleted file mode 100644 index fb1d5d2b..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDiffCursor.java +++ /dev/null @@ -1,264 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import tools.refinery.store.map.AnyVersionedMap; -import tools.refinery.store.map.Cursor; -import tools.refinery.store.map.DiffCursor; - -import java.util.Objects; -import java.util.Set; -import java.util.stream.Collectors; -import java.util.stream.Stream; - -/** - * A cursor representing the difference between two states of a map. - * - * @author Oszkar Semerath - */ -public class MapDiffCursor implements DiffCursor, Cursor { - private enum State { - /** - * initialized state. - */ - INIT, - /** - * Unstable state. - */ - MOVING_MOVING_SAME_KEY_SAME_VALUE, - /** - * Both cursors are moving, and they are on the same sub-node. - */ - MOVING_MOVING_SAME_NODE, - /** - * Both cursors are moving, cursor 1 is behind. - */ - MOVING_MOVING_BEHIND1, - /** - * Both cursors are moving, cursor 2 is behind. - */ - MOVING_MOVING_BEHIND2, - /** - * Both cursors are moving, cursor 1 is on the same key as cursor 2, values are different - */ - MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE, - /** - * Cursor 1 is moving, Cursor 2 is terminated. - */ - MOVING_TERMINATED, - /** - * Cursor 1 is terminated , Cursor 2 is moving. - */ - TERMINATED_MOVING, - /** - * Both cursors are terminated. - */ - TERMINATED_TERMINATED, - /** - * Both Cursors are moving, and they are on an incomparable position. - * It is resolved by showing Cursor 1. - */ - MOVING_MOVING_HASH1, - /** - * Both Cursors are moving, and they are on an incomparable position. - * It is resolved by showing Cursor 2. - */ - MOVING_MOVING_HASH2 - } - - /** - * Default nodeId representing missing elements. - */ - private final V defaultValue; - private final InOrderMapCursor cursor1; - private final InOrderMapCursor cursor2; - - // State - State state = State.INIT; - - // Values - private K key; - private V fromValue; - private V toValue; - - - public MapDiffCursor(V defaultValue, InOrderMapCursor cursor1, InOrderMapCursor cursor2) { - super(); - this.defaultValue = defaultValue; - this.cursor1 = cursor1; - this.cursor2 = cursor2; - } - - @Override - public K getKey() { - return key; - } - - @Override - public V getFromValue() { - return fromValue; - } - - @Override - public V getToValue() { - return toValue; - } - - @Override - public V getValue() { - return getToValue(); - } - - public boolean isTerminated() { - return this.state == State.TERMINATED_TERMINATED; - } - - @Override - public boolean isDirty() { - return this.cursor1.isDirty() || this.cursor2.isDirty(); - } - - @Override - public Set getDependingMaps() { - return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()).map(AnyVersionedMap.class::cast).collect(Collectors.toUnmodifiableSet()); - } - - private boolean isInStableState() { - return this.state != State.MOVING_MOVING_SAME_KEY_SAME_VALUE - && this.state != State.MOVING_MOVING_SAME_NODE && this.state != State.INIT; - } - - private boolean updateAndReturnWithResult() { - return switch (this.state) { - case INIT -> throw new IllegalStateException("DiffCursor terminated without starting!"); - case MOVING_MOVING_SAME_KEY_SAME_VALUE, MOVING_MOVING_SAME_NODE -> - throw new IllegalStateException("DiffCursor terminated in unstable state!"); - case MOVING_MOVING_BEHIND1, MOVING_TERMINATED, MOVING_MOVING_HASH1 -> { - this.key = this.cursor1.getKey(); - this.fromValue = this.cursor1.getValue(); - this.toValue = this.defaultValue; - yield true; - } - case MOVING_MOVING_BEHIND2, TERMINATED_MOVING, MOVING_MOVING_HASH2 -> { - this.key = this.cursor2.getKey(); - this.fromValue = this.defaultValue; - this.toValue = cursor2.getValue(); - yield true; - } - case MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE -> { - this.key = this.cursor1.getKey(); - this.fromValue = this.cursor1.getValue(); - this.toValue = this.cursor2.getValue(); - yield true; - } - case TERMINATED_TERMINATED -> { - this.key = null; - this.fromValue = null; - this.toValue = null; - yield false; - } - }; - } - - public boolean move() { - do { - this.state = moveOne(this.state); - } while (!isInStableState()); - return updateAndReturnWithResult(); - } - - private State moveOne(State currentState) { - return switch (currentState) { - case INIT, MOVING_MOVING_HASH2, MOVING_MOVING_SAME_KEY_SAME_VALUE, MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE -> { - boolean cursor1Moved = cursor1.move(); - boolean cursor2Moved = cursor2.move(); - yield recalculateStateAfterCursorMovement(cursor1Moved, cursor2Moved); - } - case MOVING_MOVING_SAME_NODE -> { - boolean cursor1Moved = cursor1.skipCurrentNode(); - boolean cursor2Moved = cursor2.skipCurrentNode(); - yield recalculateStateAfterCursorMovement(cursor1Moved, cursor2Moved); - } - case MOVING_MOVING_BEHIND1 -> { - boolean cursorMoved = cursor1.move(); - if (cursorMoved) { - yield recalculateStateBasedOnCursorRelation(); - } else { - yield State.TERMINATED_MOVING; - } - } - case MOVING_MOVING_BEHIND2 -> { - boolean cursorMoved = cursor2.move(); - if (cursorMoved) { - yield recalculateStateBasedOnCursorRelation(); - } else { - yield State.MOVING_TERMINATED; - } - } - case TERMINATED_MOVING -> { - boolean cursorMoved = cursor2.move(); - if (cursorMoved) { - yield State.TERMINATED_MOVING; - } else { - yield State.TERMINATED_TERMINATED; - } - } - case MOVING_TERMINATED -> { - boolean cursorMoved = cursor1.move(); - if (cursorMoved) { - yield State.MOVING_TERMINATED; - } else { - yield State.TERMINATED_TERMINATED; - } - } - case MOVING_MOVING_HASH1 -> State.MOVING_MOVING_HASH2; - case TERMINATED_TERMINATED -> throw new IllegalStateException("Trying to move while terminated!"); - }; - } - - private State recalculateStateAfterCursorMovement(boolean cursor1Moved, boolean cursor2Moved) { - if (cursor1Moved && cursor2Moved) { - return recalculateStateBasedOnCursorRelation(); - } else if (cursor1Moved) { - return State.MOVING_TERMINATED; - } else if (cursor2Moved) { - return State.TERMINATED_MOVING; - } else { - return State.TERMINATED_TERMINATED; - } - } - - private State recalculateStateBasedOnCursorRelation() { - final int relation = InOrderMapCursor.comparePosition(cursor1, cursor2); - - if (relation > 0) { - return State.MOVING_MOVING_BEHIND1; - } else if (relation < 0) { - return State.MOVING_MOVING_BEHIND2; - } - - if (InOrderMapCursor.sameSubNode(cursor1, cursor2)) { - return State.MOVING_MOVING_SAME_NODE; - } else if (Objects.equals(cursor1.getKey(), cursor2.getKey())) { - if (Objects.equals(cursor1.getValue(), cursor2.getValue())) { - return State.MOVING_MOVING_SAME_KEY_SAME_VALUE; - } else { - return State.MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE; - } - } - - final int depth = InOrderMapCursor.compareDepth(cursor1, cursor2); - - if (depth > 0) { - return State.MOVING_MOVING_BEHIND1; - } else if (depth < 0) { - return State.MOVING_MOVING_BEHIND2; - } else { - return State.MOVING_MOVING_HASH1; - } - - } -} 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 deleted file mode 100644 index d63522cd..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java +++ /dev/null @@ -1,39 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -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/MutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java deleted file mode 100644 index bb85deb9..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java +++ /dev/null @@ -1,499 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import tools.refinery.store.map.ContinousHashProvider; - -import java.util.Arrays; -import java.util.Map; - -public class MutableNode extends Node { - int cachedHash; - protected boolean cachedHashValid; - protected Object[] content; - - protected MutableNode() { - this.content = new Object[2 * FACTOR]; - invalidateHash(); - } - - public static MutableNode initialize(K key, V value, ContinousHashProvider hashProvider, V defaultValue) { - if (value == defaultValue) { - return null; - } else { - int hash = hashProvider.getHash(key, 0); - int fragment = hashFragment(hash, 0); - MutableNode res = new MutableNode<>(); - res.content[2 * fragment] = key; - res.content[2 * fragment + 1] = value; - res.invalidateHash(); - return res; - } - } - - /** - * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode} - * - * @param node to be transformed - */ - protected MutableNode(ImmutableNode node) { - this.content = new Object[2 * FACTOR]; - int dataUsed = 0; - int nodeUsed = 0; - for (int i = 0; i < FACTOR; i++) { - int bitPosition = 1 << i; - if ((node.dataMap & bitPosition) != 0) { - content[2 * i] = node.content[dataUsed * 2]; - content[2 * i + 1] = node.content[dataUsed * 2 + 1]; - dataUsed++; - } else if ((node.nodeMap & bitPosition) != 0) { - content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed]; - nodeUsed++; - } - } - this.cachedHashValid = false; - } - - @Override - public V getValue(K key, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth) { - int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); - @SuppressWarnings("unchecked") K keyCandidate = (K) this.content[2 * selectedHashFragment]; - if (keyCandidate != null) { - if (keyCandidate.equals(key)) { - @SuppressWarnings("unchecked") V value = (V) this.content[2 * selectedHashFragment + 1]; - return value; - } else { - return defaultValue; - } - } else { - @SuppressWarnings("unchecked") var nodeCandidate = (Node) content[2 * selectedHashFragment + 1]; - if (nodeCandidate != null) { - int newDepth = incrementDepth(depth); - int newHash = newHash(hashProvider, key, hash, newDepth); - return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); - } else { - return defaultValue; - } - } - } - - @Override - public Node putValue(K key, V value, OldValueBox oldValueBox, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth) { - int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); - @SuppressWarnings("unchecked") K keyCandidate = (K) content[2 * selectedHashFragment]; - if (keyCandidate != null) { - // If it has key - if (keyCandidate.equals(key)) { - // The key is equals to an existing key -> update entry - if (value == defaultValue) { - return removeEntry(selectedHashFragment, oldValueBox); - } else { - return updateValue(value, oldValueBox, selectedHashFragment); - } - } else { - // The key is not equivalent to an existing key on the same hash bin - // -> split entry if it is necessary - if (value == defaultValue) { - // Value is default -> do not need to add new node - oldValueBox.setOldValue(defaultValue); - return this; - } else { - // Value is not default -> Split entry data to a new node - oldValueBox.setOldValue(defaultValue); - return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment); - } - } - } - // If it does not have key, check for value - @SuppressWarnings("unchecked") var nodeCandidate = (Node) content[2 * selectedHashFragment + 1]; - if (nodeCandidate != null) { - // If it has value, it is a sub-node -> update that - int newDepth = incrementDepth(depth); - var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, newHash(hashProvider, key, hash, newDepth), newDepth); - return updateWithSubNode(selectedHashFragment, newNode, (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); - } else { - // If it does not have value, put it in the empty place - if (value == defaultValue) { - // don't need to add new key-value pair - oldValueBox.setOldValue(defaultValue); - return this; - } else { - return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue); - } - } - } - - private Node addEntry(K key, V value, OldValueBox oldValueBox, int selectedHashFragment, V defaultValue) { - content[2 * selectedHashFragment] = key; - oldValueBox.setOldValue(defaultValue); - content[2 * selectedHashFragment + 1] = value; - invalidateHash(); - return this; - } - - /** - * Updates an entry in a selected hash-fragment to a non-default value. - * - * @param value new value - * @param selectedHashFragment position of the value - * @return updated node - */ - @SuppressWarnings("unchecked") - Node updateValue(V value, OldValueBox oldValue, int selectedHashFragment) { - oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); - content[2 * selectedHashFragment + 1] = value; - invalidateHash(); - return this; - } - - /** - * Updates an entry in a selected hash-fragment with a subtree. - * - * @param selectedHashFragment position of the value - * @param newNode the subtree - * @return updated node - */ - Node updateWithSubNode(int selectedHashFragment, Node newNode, boolean deletionHappened) { - if (deletionHappened) { - if (newNode == null) { - // Check whether this node become empty - content[2 * selectedHashFragment + 1] = null; // i.e. the new node - if (hasContent()) { - invalidateHash(); - return this; - } else { - return null; - } - } else { - // check whether newNode is orphan - MutableNode immutableNewNode = newNode.isMutable(); - if (immutableNewNode != null) { - int orphaned = immutableNewNode.isOrphaned(); - if (orphaned >= 0) { - // orphan sub-node data is replaced with data - content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2]; - content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1]; - invalidateHash(); - return this; - } - } - } - } - // normal behaviour - content[2 * selectedHashFragment + 1] = newNode; - invalidateHash(); - return this; - } - - private boolean hasContent() { - for (Object element : this.content) { - if (element != null) return true; - } - return false; - } - - @Override - protected MutableNode isMutable() { - return this; - } - - protected int isOrphaned() { - int dataFound = -2; - for (int i = 0; i < FACTOR; i++) { - if (content[i * 2] != null) { - if (dataFound >= 0) { - return -1; - } else { - dataFound = i; - } - } else if (content[i * 2 + 1] != null) { - return -3; - } - } - return dataFound; - } - - @SuppressWarnings("unchecked") - private Node moveDownAndSplit(ContinousHashProvider hashProvider, K newKey, V newValue, K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) { - V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1]; - - MutableNode newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, incrementDepth(depth)); - - content[2 * selectedHashFragmentOfCurrentDepth] = null; - content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode; - invalidateHash(); - return this; - } - - // Pass everything as parameters for performance. - @SuppressWarnings("squid:S107") - private MutableNode newNodeWithTwoEntries(ContinousHashProvider hashProvider, K key1, V value1, int oldHash1, K key2, V value2, int oldHash2, int newDepth) { - int newHash1 = newHash(hashProvider, key1, oldHash1, newDepth); - int newHash2 = newHash(hashProvider, key2, oldHash2, newDepth); - int newFragment1 = hashFragment(newHash1, shiftDepth(newDepth)); - int newFragment2 = hashFragment(newHash2, shiftDepth(newDepth)); - - MutableNode subNode = new MutableNode<>(); - if (newFragment1 != newFragment2) { - subNode.content[newFragment1 * 2] = key1; - subNode.content[newFragment1 * 2 + 1] = value1; - - subNode.content[newFragment2 * 2] = key2; - subNode.content[newFragment2 * 2 + 1] = value2; - } else { - MutableNode subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newDepth)); - subNode.content[newFragment1 * 2 + 1] = subSubNode; - } - subNode.invalidateHash(); - return subNode; - } - - @SuppressWarnings("unchecked") - Node removeEntry(int selectedHashFragment, OldValueBox oldValue) { - content[2 * selectedHashFragment] = null; - oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); - content[2 * selectedHashFragment + 1] = null; - if (hasContent()) { - invalidateHash(); - return this; - } else { - return null; - } - } - - @SuppressWarnings("unchecked") - @Override - public long getSize() { - int size = 0; - for (int i = 0; i < FACTOR; i++) { - if (content[i * 2] != null) { - size++; - } else { - Node nodeCandidate = (Node) content[i * 2 + 1]; - if (nodeCandidate != null) { - size += nodeCandidate.getSize(); - } - } - } - return size; - } - - @Override - protected MutableNode toMutable() { - return this; - } - - @Override - public ImmutableNode toImmutable(Map, ImmutableNode> cache) { - return ImmutableNode.constructImmutable(this, cache); - } - - @SuppressWarnings("unchecked") - @Override - boolean moveToNext(MapCursor cursor) { - // 1. try to move to data - if (cursor.dataIndex != MapCursor.INDEX_FINISH) { - for (int index = cursor.dataIndex + 1; index < FACTOR; index++) { - if (this.content[index * 2] != null) { - // 1.1 found next data - cursor.dataIndex = index; - cursor.key = (K) this.content[index * 2]; - cursor.value = (V) this.content[index * 2 + 1]; - return true; - } - } - cursor.dataIndex = MapCursor.INDEX_FINISH; - } - - // 2. look inside the sub-nodes - if(cursor.nodeIndexStack.peek()==null) { - throw new IllegalStateException("Cursor moved to the next state when the state is empty."); - } - for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) { - if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) { - // 2.1 found next sub-node, move down to the sub-node - Node subnode = (Node) this.content[index * 2 + 1]; - - cursor.dataIndex = MapCursor.INDEX_START; - cursor.nodeIndexStack.pop(); - cursor.nodeIndexStack.push(index); - cursor.nodeIndexStack.push(MapCursor.INDEX_START); - cursor.nodeStack.push(subnode); - - return subnode.moveToNext(cursor); - } - } - // 3. no sub-node found, move up - cursor.nodeStack.pop(); - cursor.nodeIndexStack.pop(); - if (!cursor.nodeStack.isEmpty()) { - Node supernode = cursor.nodeStack.peek(); - return supernode.moveToNext(cursor); - } else { - cursor.key = null; - cursor.value = null; - return false; - } - } - - @Override - @SuppressWarnings("unchecked") - boolean moveToNextInorder(InOrderMapCursor cursor) { - if(cursor.nodeIndexStack.peek()==null || cursor.nodeStack.peek()==null) { - throw new IllegalStateException("Cursor moved to the next state when the state is empty."); - } - - int position = cursor.nodeIndexStack.peek(); - - for (int index = position + 1; index < FACTOR; index++) { - // data found - if (this.content[index * 2] != null) { - cursor.nodeIndexStack.pop(); - cursor.nodeIndexStack.push(index); - - cursor.key = (K) this.content[index * 2]; - cursor.value = (V) this.content[index * 2 + 1]; - return true; - } else if (this.content[index * 2 +1] != null) { - // sub-node found - Node subnode = (Node) this.content[index * 2 +1]; - cursor.nodeIndexStack.pop(); - cursor.nodeIndexStack.push(index); - cursor.nodeIndexStack.push(InOrderMapCursor.INDEX_START); - cursor.nodeStack.push(subnode); - - return subnode.moveToNextInorder(cursor); - } - } - - // nothing found - cursor.nodeStack.pop(); - cursor.nodeIndexStack.pop(); - if (!cursor.nodeStack.isEmpty()) { - Node supernode = cursor.nodeStack.peek(); - return supernode.moveToNextInorder(cursor); - } else { - cursor.key = null; - cursor.value = null; - return false; - } - } - - @Override - public void prettyPrint(StringBuilder builder, int depth, int code) { - builder.append("\t".repeat(Math.max(0, depth))); - if (code >= 0) { - builder.append(code); - builder.append(":"); - } - builder.append("Mutable("); - // print content - boolean hadContent = false; - for (int i = 0; i < FACTOR; i++) { - if (content[2 * i] != null) { - if (hadContent) { - builder.append(","); - } - builder.append(i); - builder.append(":["); - builder.append(content[2 * i].toString()); - builder.append("]->["); - builder.append(content[2 * i + 1].toString()); - builder.append("]"); - hadContent = true; - } - } - builder.append(")"); - // print sub-nodes - for (int i = 0; i < FACTOR; i++) { - if (content[2 * i] == null && content[2 * i + 1] != null) { - @SuppressWarnings("unchecked") Node subNode = (Node) content[2 * i + 1]; - builder.append("\n"); - subNode.prettyPrint(builder, incrementDepth(depth), i); - } - } - } - - @Override - public void checkIntegrity(ContinousHashProvider hashProvider, V defaultValue, int depth) { - // check for orphan nodes - if (depth > 0) { - int orphaned = isOrphaned(); - if (orphaned >= 0) { - throw new IllegalStateException("Orphaned node! " + orphaned + ": " + content[2 * orphaned]); - } - } - // check the place of data - for (int i = 0; i < FACTOR; i++) { - if (this.content[2 * i] != null) { - @SuppressWarnings("unchecked") K key = (K) this.content[2 * i]; - @SuppressWarnings("unchecked") V value = (V) this.content[2 * i + 1]; - - if (value == defaultValue) { - throw new IllegalStateException("Node contains default value!"); - } - int hashCode = hashProvider.getHash(key, hashDepth(depth)); - int shiftDepth = shiftDepth(depth); - int selectedHashFragment = hashFragment(hashCode, shiftDepth); - if (i != selectedHashFragment) { - throw new IllegalStateException("Key " + key + " with hash code " + hashCode + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i); - } - } - } - // check sub-nodes - for (int i = 0; i < FACTOR; i++) { - if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { - @SuppressWarnings("unchecked") var subNode = (Node) this.content[2 * i + 1]; - subNode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth)); - } - } - // check the hash - if (cachedHashValid) { - int oldHash = this.cachedHash; - invalidateHash(); - int newHash = hashCode(); - if (oldHash != newHash) { - throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")"); - } - } - } - - protected void invalidateHash() { - this.cachedHashValid = false; - } - - @Override - public int hashCode() { - if (!this.cachedHashValid) { - this.cachedHash = Arrays.hashCode(content); - this.cachedHashValid = true; - } - return this.cachedHash; - } - - @Override - public boolean equals(Object obj) { - if (this == obj) return true; - if (obj == null) return false; - if (obj instanceof MutableNode mutableObj) { - if (obj.hashCode() != this.hashCode()) { - return false; - } else { - for (int i = 0; i < FACTOR * 2; i++) { - Object thisContent = this.content[i]; - if (thisContent != null && !thisContent.equals(mutableObj.content[i])) { - return false; - } - } - return true; - } - } else if (obj instanceof ImmutableNode immutableObj) { - return ImmutableNode.compareImmutableMutable(immutableObj, this); - } else { - return false; - } - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java deleted file mode 100644 index 4b44f760..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java +++ /dev/null @@ -1,131 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import java.util.Map; - -import tools.refinery.store.map.ContinousHashProvider; - -public abstract class Node { - public static final int BRANCHING_FACTOR_BITS = 5; - public static final int FACTOR = 1 << BRANCHING_FACTOR_BITS; - protected static final int NUMBER_OF_FACTORS = Integer.SIZE / BRANCHING_FACTOR_BITS; - protected static final int FACTOR_MASK = FACTOR - 1; - public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS; - public static final int FACTOR_SELECTION_BITS = 32 - Integer.numberOfLeadingZeros(NUMBER_OF_FACTORS); - public static final int FACTOR_SELECTION_MASK = (1 << FACTOR_SELECTION_BITS) - 1; - public static final int INCREMENT_BIG_STEP = (1 << FACTOR_SELECTION_BITS) - NUMBER_OF_FACTORS; - - /** - * Increments the depth of the search in the tree. The depth parameter has two - * components: the least few bits selects the fragment of the hashcode, the - * other part selects the continuous hash. - * - * @param depth parameter encoding the fragment and the depth - * @return new depth. - */ - protected int incrementDepth(int depth) { - int newDepth = depth + 1; - if ((newDepth & FACTOR_SELECTION_MASK) == NUMBER_OF_FACTORS) { - newDepth += INCREMENT_BIG_STEP; - } - return newDepth; - } - - /** - * Calculates the index for the continuous hash. - * - * @param depth The depth of the node in the tree. - * @return The index of the continuous hash. - */ - protected static int hashDepth(int depth) { - return depth >> FACTOR_SELECTION_BITS; - } - - /** - * Calculates the which segment of a single hash should be used. - * - * @param depth The depth of the node in the tree. - * @return The segment of a hash code. - */ - protected static int shiftDepth(int depth) { - return depth & FACTOR_SELECTION_MASK; - } - - /** - * Selects a segments from a complete hash for a given depth. - * - * @param hash A complete hash. - * @param shiftDepth The index of the segment. - * @return The segment as an integer. - */ - protected static int hashFragment(int hash, int shiftDepth) { - if (shiftDepth < 0 || Node.NUMBER_OF_FACTORS < shiftDepth) - throw new IllegalArgumentException("Invalid shift depth! valid interval=[0;5], input=" + shiftDepth); - return (hash >>> shiftDepth * BRANCHING_FACTOR_BITS) & FACTOR_MASK; - } - - /** - * Returns the hash code for a given depth. It may calculate new hash code, or - * reuse a hash code calculated for depth-1. - * - * @param key The key. - * @param hash Hash code for depth-1 - * @param depth The depth. - * @return The new hash code. - */ - protected int newHash(final ContinousHashProvider hashProvider, K key, int hash, int depth) { - final int shiftDepth = shiftDepth(depth); - if (shiftDepth == 0) { - final int hashDepth = hashDepth(depth); - if (hashDepth >= ContinousHashProvider.MAX_PRACTICAL_DEPTH) { - throw new IllegalArgumentException( - "Key " + key + " have the clashing hashcode over the practical depth limitation (" - + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!"); - } - return hashProvider.getHash(key, hashDepth); - } else { - return hash; - } - } - - public abstract V getValue(K key, ContinousHashProvider hashProvider, V defaultValue, int hash, - int depth); - - public abstract Node putValue(K key, V value, OldValueBox old, - ContinousHashProvider hashProvider, V defaultValue, int hash, int depth); - - public abstract long getSize(); - - abstract MutableNode toMutable(); - - public abstract ImmutableNode toImmutable(Map, ImmutableNode> cache); - - protected abstract MutableNode isMutable(); - - /** - * Moves a {@link MapCursor} to its next position. - * - * @param cursor the cursor - * @return Whether there was a next value to move on. - */ - abstract boolean moveToNext(MapCursor cursor); - abstract boolean moveToNextInorder(InOrderMapCursor cursor); - - ///////// FOR printing - public abstract void prettyPrint(StringBuilder builder, int depth, int code); - - - @Override - public String toString() { - StringBuilder stringBuilder = new StringBuilder(); - prettyPrint(stringBuilder, 0, -1); - return stringBuilder.toString(); - } - - public void checkIntegrity(ContinousHashProvider hashProvider, V defaultValue, int depth) { - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/OldValueBox.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/OldValueBox.java deleted file mode 100644 index 354af51d..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/OldValueBox.java +++ /dev/null @@ -1,24 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -public class OldValueBox{ - V oldValue; - boolean isSet = false; - - public V getOldValue() { - if(!isSet) throw new IllegalStateException(); - isSet = false; - return oldValue; - } - - public void setOldValue(V ouldValue) { - if(isSet) throw new IllegalStateException(); - this.oldValue = ouldValue; - isSet = true; - } - -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/StateBasedVersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/StateBasedVersionedMapStoreFactory.java deleted file mode 100644 index 1c3ab27b..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/StateBasedVersionedMapStoreFactory.java +++ /dev/null @@ -1,38 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import tools.refinery.store.map.*; - -import java.util.List; - -public class StateBasedVersionedMapStoreFactory implements VersionedMapStoreFactory { - private final V defaultValue; - private final ContinousHashProvider continousHashProvider; - private final VersionedMapStoreConfiguration config; - - public StateBasedVersionedMapStoreFactory(V defaultValue, Boolean transformToImmutable, VersionedMapStoreFactoryBuilder.SharingStrategy sharingStrategy, ContinousHashProvider continousHashProvider) { - this.defaultValue = defaultValue; - this.continousHashProvider = continousHashProvider; - - this.config = new VersionedMapStoreConfiguration( - transformToImmutable, - sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE || sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP, - sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP); - } - - @Override - public VersionedMapStore createOne() { - return new VersionedMapStoreImpl<>(continousHashProvider, defaultValue, config); - - } - - @Override - public List> createGroup(int amount) { - return VersionedMapStoreImpl.createSharedVersionedMapStores(amount, continousHashProvider, defaultValue, - config); - } -} 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 deleted file mode 100644 index ba59cfef..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java +++ /dev/null @@ -1,36 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -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 deleted file mode 100644 index 61a34351..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java +++ /dev/null @@ -1,53 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import java.util.*; -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) { - if(!uncommittedOldValues.containsKey(key)) { - this.uncommittedOldValues.put(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 deleted file mode 100644 index 438b5561..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java +++ /dev/null @@ -1,29 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -public interface UncommittedDeltaStore { - void processChange(K key, V oldValue, V newValue); - - MapDelta[] extractDeltas(); - - MapDelta[] extractAndDeleteDeltas(); - - default void checkIntegrity() { - MapDelta[] extractedDeltas = extractDeltas(); - if(extractedDeltas != null) { - for(var uncommittedOldValue : extractedDeltas) { - if(uncommittedOldValue == null) { - throw new IllegalArgumentException("Null entry in deltas!"); - } - if(uncommittedOldValue.getKey() == null) { - throw new IllegalStateException("Null key in deltas!"); - } - } - } - } - -} 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 deleted file mode 100644 index ae47feda..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java +++ /dev/null @@ -1,219 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -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, boolean summarizeChanges, V defaultValue) { - this.store = store; - this.defaultValue = defaultValue; - - current = new HashMap<>(); - if (summarizeChanges) { - this.uncommittedStore = new UncommittedDeltaMapStore<>(this); - } else { - this.uncommittedStore = new UncommittedDeltaArrayStore<>(); - } - } - - @Override - public V getDefaultValue() { - return defaultValue; - } - - @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 - final MapTransaction parent; - List[]> forward = new ArrayList<>(); - if (this.previous == null) { - parent = this.store.getPath(state, forward); - this.forward(forward); - } else { - List[]> backward = new ArrayList<>(); - parent = this.store.getPath(this.previous.version(), state, backward, forward); - this.backward(backward); - this.forward(forward); - } - this.previous = parent; - } - - 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]; - K key = change.getKey(); - V newValue = change.getNewValue(); - - if(newValue == defaultValue) { - current.remove(key); - } else { - current.put(key,newValue); - } - } - } - - protected void backward(MapDelta[] changes) { - for (int i = changes.length - 1; i >= 0; i--) { - final MapDelta change = changes[i]; - K key = change.getKey(); - V oldValue = change.oldValue(); - - if(oldValue == defaultValue) { - current.remove(key); - } else { - current.put(key,oldValue); - } - } - } - - @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) { - final V oldValue; - if (Objects.equals(value, defaultValue)) { - final V res = current.remove(key); - if (res == null) { - // no changes: default > default - oldValue = defaultValue; - } else { - oldValue = res; - } - } else { - final var mapValue = current.put(key, value); - if (mapValue == null) { - oldValue = defaultValue; - } else { - oldValue = mapValue; - } - } - if(!Objects.equals(oldValue,value)) { - uncommittedStore.processChange(key, oldValue, value); - } - return oldValue; - } - - @Override - public void putAll(Cursor cursor) { - if (cursor.getDependingMaps().contains(this)) { - List keys = new ArrayList<>(); - List values = new ArrayList<>(); - while (cursor.move()) { - keys.add(cursor.getKey()); - values.add(cursor.getValue()); - } - for (int i = 0; i < keys.size(); i++) { - this.put(keys.get(i), values.get(i)); - } - } else { - while (cursor.move()) { - this.put(cursor.getKey(), cursor.getValue()); - } - } - } - - @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."); - } - } - - @Override - public void checkIntegrity() { - this.uncommittedStore.checkIntegrity(); - - for (var entry : this.current.entrySet()) { - var value = entry.getValue(); - if (value == this.defaultValue) { - throw new IllegalStateException("Default value stored in map!"); - } else if (value == null) { - throw new IllegalStateException("null value stored in map!"); - } - } - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java deleted file mode 100644 index c107f7e0..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java +++ /dev/null @@ -1,171 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.map.internal; - -import tools.refinery.store.map.*; - -import java.util.Iterator; -import java.util.LinkedList; -import java.util.List; -import java.util.Objects; - -/** - * Not threadSafe in itself - * - * @param - * @param - * @author Oszkar Semerath - */ -public class VersionedMapImpl implements VersionedMap { - protected final VersionedMapStoreImpl store; - - protected final ContinousHashProvider hashProvider; - protected final V defaultValue; - protected Node root; - - private final OldValueBox oldValueBox = new OldValueBox<>(); - - public VersionedMapImpl( - VersionedMapStoreImpl store, - ContinousHashProvider hashProvider, - V defaultValue) { - this.store = store; - this.hashProvider = hashProvider; - this.defaultValue = defaultValue; - this.root = null; - } - - public VersionedMapImpl( - VersionedMapStoreImpl store, - ContinousHashProvider hashProvider, - V defaultValue, Node data) { - this.store = store; - this.hashProvider = hashProvider; - this.defaultValue = defaultValue; - this.root = data; - } - - @Override - public V getDefaultValue() { - return defaultValue; - } - - public ContinousHashProvider getHashProvider() { - return hashProvider; - } - - @Override - public V put(K key, V value) { - if (root != null) { - root = root.putValue(key, value, oldValueBox, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); - return oldValueBox.getOldValue(); - } else { - root = MutableNode.initialize(key, value, hashProvider, defaultValue); - return defaultValue; - } - } - - @Override - public void putAll(Cursor cursor) { - if (cursor.getDependingMaps().contains(this)) { - List keys = new LinkedList<>(); - List values = new LinkedList<>(); - while (cursor.move()) { - keys.add(cursor.getKey()); - values.add(cursor.getValue()); - } - Iterator keyIterator = keys.iterator(); - Iterator valueIterator = values.iterator(); - while (keyIterator.hasNext()) { - var key = keyIterator.next(); - var value = valueIterator.next(); - this.put(key,value); - } - } else { - while (cursor.move()) { - this.put(cursor.getKey(), cursor.getValue()); - } - } - } - - @Override - public V get(K key) { - if (root != null) { - return root.getValue(key, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); - } else { - return defaultValue; - } - } - - @Override - public long getSize() { - if (root == null) { - return 0; - } else { - return root.getSize(); - } - } - - @Override - public Cursor getAll() { - return new MapCursor<>(this.root, this); - } - - @Override - public DiffCursor getDiffCursor(long toVersion) { - InOrderMapCursor fromCursor = new InOrderMapCursor<>(this); - VersionedMapImpl toMap = (VersionedMapImpl) this.store.createMap(toVersion); - InOrderMapCursor toCursor = new InOrderMapCursor<>(toMap); - return new MapDiffCursor<>(this.defaultValue, fromCursor, toCursor); - } - - - @Override - public long commit() { - return this.store.commit(root, this); - } - - public void setRoot(Node root) { - this.root = root; - } - - @Override - public void restore(long state) { - root = this.store.revert(state); - } - - public String prettyPrint() { - if (this.root != null) { - StringBuilder s = new StringBuilder(); - this.root.prettyPrint(s, 0, -1); - return s.toString(); - } else { - return "empty tree"; - } - } - - @Override - public void checkIntegrity() { - if (this.root != null) { - this.root.checkIntegrity(hashProvider, defaultValue, 0); - } - } - - @Override - public int contentHashCode(ContentHashCode mode) { - // Calculating the root hashCode is always fast, because {@link Node} caches its hashCode. - if(root == null) { - return 0; - } else { - return root.hashCode(); - } - } - - @Override - public boolean contentEquals(AnyVersionedMap other) { - return other instanceof VersionedMapImpl otherImpl && Objects.equals(root, otherImpl.root); - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java index cf117d95..47470236 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java @@ -5,9 +5,11 @@ */ package tools.refinery.store.map.internal; -import tools.refinery.store.map.ContinousHashProvider; +import tools.refinery.store.map.ContinuousHashProvider; import tools.refinery.store.map.VersionedMapStoreFactory; import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; +import tools.refinery.store.map.internal.delta.DeltaBasedVersionedMapStoreFactory; +import tools.refinery.store.map.internal.state.StateBasedVersionedMapStoreFactory; public class VersionedMapStoreFactoryBuilderImpl implements VersionedMapStoreFactoryBuilder { @@ -16,14 +18,14 @@ public class VersionedMapStoreFactoryBuilderImpl implements VersionedMapSt private StoreStrategy strategy = null; private Boolean transformToImmutable = null; private SharingStrategy sharingStrategy = null; - private ContinousHashProvider continousHashProvider = null; + private ContinuousHashProvider continuousHashProvider = null; private DeltaTransactionStrategy deltaTransactionStrategy = null; private StoreStrategy checkStrategy() { StoreStrategy currentStrategy = strategy; currentStrategy = mergeStrategies(currentStrategy, transformToImmutable, StoreStrategy.STATE); currentStrategy = mergeStrategies(currentStrategy, sharingStrategy, StoreStrategy.STATE); - currentStrategy = mergeStrategies(currentStrategy, continousHashProvider, StoreStrategy.STATE); + currentStrategy = mergeStrategies(currentStrategy, continuousHashProvider, StoreStrategy.STATE); currentStrategy = mergeStrategies(currentStrategy, deltaTransactionStrategy, StoreStrategy.DELTA); return currentStrategy; } @@ -77,8 +79,8 @@ public class VersionedMapStoreFactoryBuilderImpl implements VersionedMapSt } @Override - public VersionedMapStoreFactoryBuilder stateBasedHashProvider(ContinousHashProvider hashProvider) { - this.continousHashProvider = hashProvider; + public VersionedMapStoreFactoryBuilder stateBasedHashProvider(ContinuousHashProvider hashProvider) { + this.continuousHashProvider = hashProvider; checkStrategy(); return this; } @@ -110,13 +112,13 @@ public class VersionedMapStoreFactoryBuilderImpl implements VersionedMapSt } return switch (strategyToUse) { case STATE -> { - if(continousHashProvider == null) { + if(continuousHashProvider == null) { throw new IllegalArgumentException("Continuous hash provider is missing!"); } yield new StateBasedVersionedMapStoreFactory<>(defaultValue, getOrDefault(transformToImmutable,true), getOrDefault(sharingStrategy, SharingStrategy.SHARED_NODE_CACHE_IN_GROUP), - continousHashProvider); + continuousHashProvider); } case DELTA -> new DeltaBasedVersionedMapStoreFactory<>(defaultValue, getOrDefault(deltaTransactionStrategy, DeltaTransactionStrategy.LIST)); @@ -130,7 +132,7 @@ public class VersionedMapStoreFactoryBuilderImpl implements VersionedMapSt ", strategy=" + strategy + ", stateBasedImmutableWhenCommitting=" + transformToImmutable + ", stateBasedNodeSharingStrategy=" + sharingStrategy + - ", hashProvider=" + continousHashProvider + + ", hashProvider=" + continuousHashProvider + ", deltaStorageStrategy=" + deltaTransactionStrategy + '}'; } diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaBasedVersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaBasedVersionedMapStoreFactory.java new file mode 100644 index 00000000..cedcdc0b --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaBasedVersionedMapStoreFactory.java @@ -0,0 +1,38 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +import tools.refinery.store.map.VersionedMapStore; +import tools.refinery.store.map.VersionedMapStoreFactory; +import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; + +import java.util.ArrayList; +import java.util.List; + +public class DeltaBasedVersionedMapStoreFactory implements VersionedMapStoreFactory { + private final V defaultValue; + private final boolean summarizeChanges; + + public DeltaBasedVersionedMapStoreFactory(V defaultValue, + VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy deltaTransactionStrategy) { + this.defaultValue = defaultValue; + this.summarizeChanges = deltaTransactionStrategy == VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy.SET; + } + + @Override + public VersionedMapStore createOne() { + return new VersionedMapStoreDeltaImpl<>(summarizeChanges, defaultValue); + } + + @Override + public List> createGroup(int amount) { + List> result = new ArrayList<>(amount); + for(int i=0; i(summarizeChanges,defaultValue)); + } + return result; + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaDiffCursor.java new file mode 100644 index 00000000..ce10b246 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/DeltaDiffCursor.java @@ -0,0 +1,147 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +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; + + boolean started; + /** + * 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; + } + started = false; + } + + 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(!started) { + started = true; + return !isTerminated(); + } else if (isTerminated()) { + return false; + } else { + if (this.direction) { + if (arrayIndex+1 < forwardTransactions.get(listIndex).length) { + arrayIndex++; + return true; + } else { + if (listIndex-1 >= 0) { + listIndex--; + arrayIndex = 0; + 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() { + if(this.direction) { + return getCurrentDelta().getOldValue(); + } else { + return getCurrentDelta().getNewValue(); + } + } + + @Override + public V getToValue() { + if(this.direction) { + return getCurrentDelta().getNewValue(); + } else { + return getCurrentDelta().getOldValue(); + } + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapDelta.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapDelta.java new file mode 100644 index 00000000..0c0cc906 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapDelta.java @@ -0,0 +1,20 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +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/delta/MapTransaction.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapTransaction.java new file mode 100644 index 00000000..7f9ccd7f --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/MapTransaction.java @@ -0,0 +1,39 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +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/delta/UncommittedDeltaArrayStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaArrayStore.java new file mode 100644 index 00000000..1f6a9000 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaArrayStore.java @@ -0,0 +1,36 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +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/delta/UncommittedDeltaMapStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaMapStore.java new file mode 100644 index 00000000..644884a6 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaMapStore.java @@ -0,0 +1,53 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +import java.util.*; +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) { + if(!uncommittedOldValues.containsKey(key)) { + this.uncommittedOldValues.put(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/delta/UncommittedDeltaStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaStore.java new file mode 100644 index 00000000..ecd33c5f --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/UncommittedDeltaStore.java @@ -0,0 +1,29 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +public interface UncommittedDeltaStore { + void processChange(K key, V oldValue, V newValue); + + MapDelta[] extractDeltas(); + + MapDelta[] extractAndDeleteDeltas(); + + default void checkIntegrity() { + MapDelta[] extractedDeltas = extractDeltas(); + if(extractedDeltas != null) { + for(var uncommittedOldValue : extractedDeltas) { + if(uncommittedOldValue == null) { + throw new IllegalArgumentException("Null entry in deltas!"); + } + if(uncommittedOldValue.getKey() == null) { + throw new IllegalStateException("Null key in deltas!"); + } + } + } + } + +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java new file mode 100644 index 00000000..5bb864ac --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapDeltaImpl.java @@ -0,0 +1,220 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +import java.util.*; + +import tools.refinery.store.map.*; +import tools.refinery.store.map.IteratorAsCursor; + +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, boolean summarizeChanges, V defaultValue) { + this.store = store; + this.defaultValue = defaultValue; + + current = new HashMap<>(); + if (summarizeChanges) { + this.uncommittedStore = new UncommittedDeltaMapStore<>(this); + } else { + this.uncommittedStore = new UncommittedDeltaArrayStore<>(); + } + } + + @Override + public V getDefaultValue() { + return defaultValue; + } + + @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 + final MapTransaction parent; + List[]> forward = new ArrayList<>(); + if (this.previous == null) { + parent = this.store.getPath(state, forward); + this.forward(forward); + } else { + List[]> backward = new ArrayList<>(); + parent = this.store.getPath(this.previous.version(), state, backward, forward); + this.backward(backward); + this.forward(forward); + } + this.previous = parent; + } + + 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]; + K key = change.getKey(); + V newValue = change.getNewValue(); + + if(newValue == defaultValue) { + current.remove(key); + } else { + current.put(key,newValue); + } + } + } + + protected void backward(MapDelta[] changes) { + for (int i = changes.length - 1; i >= 0; i--) { + final MapDelta change = changes[i]; + K key = change.getKey(); + V oldValue = change.oldValue(); + + if(oldValue == defaultValue) { + current.remove(key); + } else { + current.put(key,oldValue); + } + } + } + + @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) { + final V oldValue; + if (Objects.equals(value, defaultValue)) { + final V res = current.remove(key); + if (res == null) { + // no changes: default > default + oldValue = defaultValue; + } else { + oldValue = res; + } + } else { + final var mapValue = current.put(key, value); + if (mapValue == null) { + oldValue = defaultValue; + } else { + oldValue = mapValue; + } + } + if(!Objects.equals(oldValue,value)) { + uncommittedStore.processChange(key, oldValue, value); + } + return oldValue; + } + + @Override + public void putAll(Cursor cursor) { + if (cursor.getDependingMaps().contains(this)) { + List keys = new ArrayList<>(); + List values = new ArrayList<>(); + while (cursor.move()) { + keys.add(cursor.getKey()); + values.add(cursor.getValue()); + } + for (int i = 0; i < keys.size(); i++) { + this.put(keys.get(i), values.get(i)); + } + } else { + while (cursor.move()) { + this.put(cursor.getKey(), cursor.getValue()); + } + } + } + + @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."); + } + } + + @Override + public void checkIntegrity() { + this.uncommittedStore.checkIntegrity(); + + for (var entry : this.current.entrySet()) { + var value = entry.getValue(); + if (value == this.defaultValue) { + throw new IllegalStateException("Default value stored in map!"); + } else if (value == null) { + throw new IllegalStateException("null value stored in map!"); + } + } + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java new file mode 100644 index 00000000..7f56ea77 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/delta/VersionedMapStoreDeltaImpl.java @@ -0,0 +1,101 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.delta; + +import tools.refinery.store.map.DiffCursor; +import tools.refinery.store.map.VersionedMap; +import tools.refinery.store.map.VersionedMapStore; + +import java.util.*; + +public class VersionedMapStoreDeltaImpl implements VersionedMapStore { + // Configuration + protected final boolean summarizeChanges; + + // Static data + protected final V defaultValue; + + // Dynamic data + protected final Map> states = new HashMap<>(); + protected long nextID = 0; + + public VersionedMapStoreDeltaImpl(boolean summarizeChanges, V defaultValue) { + this.summarizeChanges = summarizeChanges; + this.defaultValue = defaultValue; + } + + @Override + public VersionedMap createMap() { + return new VersionedMapDeltaImpl<>(this, this.summarizeChanges, this.defaultValue); + } + + @Override + public VersionedMap createMap(long state) { + VersionedMapDeltaImpl result = new VersionedMapDeltaImpl<>(this, this.summarizeChanges, 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 MapTransaction getPath(long to, List[]> forwardTransactions) { + final MapTransaction target = getState(to); + MapTransaction toTransaction = target; + while (toTransaction != null) { + forwardTransactions.add(toTransaction.deltas()); + toTransaction = toTransaction.parent(); + } + return target; + } + + public MapTransaction getPath(long from, long to, + List[]> backwardTransactions, + List[]> forwardTransactions) { + MapTransaction fromTransaction = getState(from); + final MapTransaction target = getState(to); + MapTransaction toTransaction = target; + + while (fromTransaction != toTransaction) { + if (fromTransaction == null || (toTransaction != null && fromTransaction.version() < toTransaction.version())) { + forwardTransactions.add(toTransaction.deltas()); + toTransaction = toTransaction.parent(); + } else { + backwardTransactions.add(fromTransaction.deltas()); + fromTransaction = fromTransaction.parent(); + } + } + return target; + } + + + @Override + public synchronized Set getStates() { + return new HashSet<>(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/state/ImmutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/ImmutableNode.java new file mode 100644 index 00000000..722f9ed7 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/ImmutableNode.java @@ -0,0 +1,413 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import java.util.Arrays; +import java.util.Map; + +import tools.refinery.store.map.ContinuousHashProvider; + +public class ImmutableNode extends Node { + /** + * Bitmap defining the stored key and values. + */ + final int dataMap; + /** + * Bitmap defining the positions of further nodes. + */ + final int nodeMap; + /** + * Stores Keys, Values, and sub-nodes. Structure: (K,V)*,NODE; NODES are stored + * backwards. + */ + final Object[] content; + + /** + * Hash code derived from immutable hash code + */ + final int precalculatedHash; + + private ImmutableNode(int dataMap, int nodeMap, Object[] content, int precalculatedHash) { + super(); + this.dataMap = dataMap; + this.nodeMap = nodeMap; + this.content = content; + this.precalculatedHash = precalculatedHash; + } + + /** + * Constructor that copies a mutable node to an immutable. + * + * @param node A mutable node. + * @param cache A cache of existing immutable nodes. It can be used to search + * and place reference immutable nodes. It can be null, if no cache + * available. + * @return an immutable version of the input node. + */ + static ImmutableNode constructImmutable(MutableNode node, Map, ImmutableNode> cache) { + // 1. try to return from cache + if (cache != null) { + ImmutableNode cachedResult = cache.get(node); + if (cachedResult != null) { + // 1.1 Already cached, return from cache. + return cachedResult; + } + } + + // 2. otherwise construct a new ImmutableNode + int size = 0; + for (int i = 0; i < node.content.length; i++) { + if (node.content[i] != null) { + size++; + } + } + + int datas = 0; + int nodes = 0; + int resultDataMap = 0; + int resultNodeMap = 0; + final Object[] resultContent = new Object[size]; + int bitPosition = 1; + for (int i = 0; i < FACTOR; i++) { + Object key = node.content[i * 2]; + if (key != null) { + resultDataMap |= bitPosition; + resultContent[datas * 2] = key; + resultContent[datas * 2 + 1] = node.content[i * 2 + 1]; + datas++; + } else { + @SuppressWarnings("unchecked") var subnode = (Node) node.content[i * 2 + 1]; + if (subnode != null) { + ImmutableNode immutableSubNode = subnode.toImmutable(cache); + resultNodeMap |= bitPosition; + resultContent[size - 1 - nodes] = immutableSubNode; + nodes++; + } + } + bitPosition <<= 1; + } + final int resultHash = node.hashCode(); + var newImmutable = new ImmutableNode(resultDataMap, resultNodeMap, resultContent, resultHash); + + // 3. save new immutable. + if (cache != null) { + cache.put(newImmutable, newImmutable); + } + return newImmutable; + } + + private int index(int bitmap, int bitpos) { + return Integer.bitCount(bitmap & (bitpos - 1)); + } + + @Override + public V getValue(K key, ContinuousHashProvider hashProvider, V defaultValue, int hash, int depth) { + int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); + int bitposition = 1 << selectedHashFragment; + // If the key is stored as a data + if ((dataMap & bitposition) != 0) { + int keyIndex = 2 * index(dataMap, bitposition); + @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; + if (keyCandidate.equals(key)) { + @SuppressWarnings("unchecked") V value = (V) content[keyIndex + 1]; + return value; + } else { + return defaultValue; + } + } + // the key is stored as a node + else if ((nodeMap & bitposition) != 0) { + int keyIndex = content.length - 1 - index(nodeMap, bitposition); + @SuppressWarnings("unchecked") var subNode = (ImmutableNode) content[keyIndex]; + int newDepth = incrementDepth(depth); + int newHash = newHash(hashProvider, key, hash, newDepth); + return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); + } + // the key is not stored at all + else { + return defaultValue; + } + } + + @Override + public Node putValue(K key, V value, OldValueBox oldValue, ContinuousHashProvider hashProvider, V defaultValue, int hash, int depth) { + int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); + int bitPosition = 1 << selectedHashFragment; + if ((dataMap & bitPosition) != 0) { + int keyIndex = 2 * index(dataMap, bitPosition); + @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; + if (keyCandidate.equals(key)) { + if (value == defaultValue) { + // delete + MutableNode mutable = this.toMutable(); + return mutable.removeEntry(selectedHashFragment, oldValue); + } else if (value == content[keyIndex + 1]) { + // don't change + oldValue.setOldValue(value); + return this; + } else { + // update existing value + MutableNode mutable = this.toMutable(); + return mutable.updateValue(value, oldValue, selectedHashFragment); + } + } else { + if (value == defaultValue) { + // don't change + oldValue.setOldValue(defaultValue); + return this; + } else { + // add new key + value + MutableNode mutable = this.toMutable(); + return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); + } + } + } else if ((nodeMap & bitPosition) != 0) { + int keyIndex = content.length - 1 - index(nodeMap, bitPosition); + @SuppressWarnings("unchecked") var subNode = (ImmutableNode) content[keyIndex]; + int newDepth = incrementDepth(depth); + int newHash = newHash(hashProvider, key, hash, newDepth); + var newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth); + + if (subNode == newsubNode) { + // nothing changed + return this; + } else { + MutableNode mutable = toMutable(); + return mutable.updateWithSubNode(selectedHashFragment, newsubNode, + (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); + } + } else { + // add new key + value + MutableNode mutable = this.toMutable(); + return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); + } + } + + @Override + public long getSize() { + int result = Integer.bitCount(this.dataMap); + for (int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) { + @SuppressWarnings("unchecked") var subnode = (ImmutableNode) this.content[this.content.length - 1 - subnodeIndex]; + result += subnode.getSize(); + } + return result; + } + + @Override + protected MutableNode toMutable() { + return new MutableNode<>(this); + } + + @Override + public ImmutableNode toImmutable(Map, ImmutableNode> cache) { + return this; + } + + @Override + protected MutableNode isMutable() { + return null; + } + + @SuppressWarnings("unchecked") + @Override + boolean moveToNext(MapCursor cursor) { + // 1. try to move to data + int datas = Integer.bitCount(this.dataMap); + if (cursor.dataIndex != MapCursor.INDEX_FINISH) { + int newDataIndex = cursor.dataIndex + 1; + if (newDataIndex < datas) { + cursor.dataIndex = newDataIndex; + cursor.key = (K) this.content[newDataIndex * 2]; + cursor.value = (V) this.content[newDataIndex * 2 + 1]; + return true; + } else { + cursor.dataIndex = MapCursor.INDEX_FINISH; + } + } + + // 2. look inside the subnodes + int nodes = Integer.bitCount(this.nodeMap); + if(cursor.nodeIndexStack.peek()==null) { + throw new IllegalStateException("Cursor moved to the next state when the state is empty."); + } + int newNodeIndex = cursor.nodeIndexStack.peek() + 1; + if (newNodeIndex < nodes) { + // 2.1 found next subnode, move down to the subnode + Node subnode = (Node) this.content[this.content.length - 1 - newNodeIndex]; + cursor.dataIndex = MapCursor.INDEX_START; + cursor.nodeIndexStack.pop(); + cursor.nodeIndexStack.push(newNodeIndex); + cursor.nodeIndexStack.push(MapCursor.INDEX_START); + cursor.nodeStack.push(subnode); + return subnode.moveToNext(cursor); + } else { + // 3. no subnode found, move up + cursor.nodeStack.pop(); + cursor.nodeIndexStack.pop(); + if (!cursor.nodeStack.isEmpty()) { + Node supernode = cursor.nodeStack.peek(); + return supernode.moveToNext(cursor); + } else { + cursor.key = null; + cursor.value = null; + return false; + } + } + } + + @Override + @SuppressWarnings("unchecked") + boolean moveToNextInorder(InOrderMapCursor cursor) { + if(cursor.nodeIndexStack.peek()==null) { + throw new IllegalStateException("Cursor moved to the next state when the state is empty."); + } + + int position = cursor.nodeIndexStack.peek(); + for (int index = position + 1; index < FACTOR; index++) { + final int mask = 1< subnode = (Node) this.content[this.content.length - 1 - index(nodeMap, mask)]; + cursor.nodeIndexStack.pop(); + cursor.nodeIndexStack.push(index); + cursor.nodeIndexStack.push(InOrderMapCursor.INDEX_START); + cursor.nodeStack.push(subnode); + + return subnode.moveToNextInorder(cursor); + } + } + + // nothing found + cursor.nodeStack.pop(); + cursor.nodeIndexStack.pop(); + if (!cursor.nodeStack.isEmpty()) { + Node supernode = cursor.nodeStack.peek(); + return supernode.moveToNextInorder(cursor); + } else { + cursor.key = null; + cursor.value = null; + return false; + } + } + + @Override + public void prettyPrint(StringBuilder builder, int depth, int code) { + builder.append("\t".repeat(Math.max(0, depth))); + if (code >= 0) { + builder.append(code); + builder.append(":"); + } + builder.append("Immutable("); + boolean hadContent = false; + int dataMask = 1; + for (int i = 0; i < FACTOR; i++) { + if ((dataMask & dataMap) != 0) { + if (hadContent) { + builder.append(","); + } + builder.append(i); + builder.append(":["); + builder.append(content[2 * index(dataMap, dataMask)].toString()); + builder.append("]->["); + builder.append(content[2 * index(dataMap, dataMask) + 1].toString()); + builder.append("]"); + hadContent = true; + } + dataMask <<= 1; + } + builder.append(")"); + int nodeMask = 1; + for (int i = 0; i < FACTOR; i++) { + if ((nodeMask & nodeMap) != 0) { + @SuppressWarnings("unchecked") Node subNode = (Node) content[content.length - 1 - index(nodeMap, nodeMask)]; + builder.append("\n"); + subNode.prettyPrint(builder, incrementDepth(depth), i); + } + nodeMask <<= 1; + } + } + + @Override + public void checkIntegrity(ContinuousHashProvider hashProvider, V defaultValue, int depth) { + if (depth > 0) { + boolean orphaned = Integer.bitCount(dataMap) == 1 && nodeMap == 0; + if (orphaned) { + throw new IllegalStateException("Orphaned node! " + dataMap + ": " + content[0]); + } + } + // check the place of data + + // check subnodes + for (int i = 0; i < Integer.bitCount(nodeMap); i++) { + @SuppressWarnings("unchecked") var subnode = (Node) this.content[this.content.length - 1 - i]; + if (!(subnode instanceof ImmutableNode)) { + throw new IllegalStateException("Immutable node contains mutable subnodes!"); + } else { + subnode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth)); + } + } + } + + @Override + public int hashCode() { + return this.precalculatedHash; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) return true; + if (obj == null) return false; + if (obj instanceof ImmutableNode other) { + return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap && Arrays.deepEquals(content, other.content); + } else if (obj instanceof MutableNode mutableObj) { + return ImmutableNode.compareImmutableMutable(this, mutableObj); + } else { + return false; + } + } + + public static boolean compareImmutableMutable(ImmutableNode immutable, MutableNode mutable) { + int datas = 0; + int nodes = 0; + final int immutableLength = immutable.content.length; + for (int i = 0; i < FACTOR; i++) { + Object key = mutable.content[i * 2]; + // For each key candidate + if (key != null) { + // Check whether a new Key-Value pair can fit into the immutable container + if (datas * 2 + nodes + 2 <= immutableLength) { + if (!immutable.content[datas * 2].equals(key) || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) { + return false; + } + } else return false; + datas++; + } else { + var mutableSubnode = (Node) mutable.content[i * 2 + 1]; + if (mutableSubnode != null) { + if (datas * 2 + nodes + 1 <= immutableLength) { + Object immutableSubNode = immutable.content[immutableLength - 1 - nodes]; + if (!mutableSubnode.equals(immutableSubNode)) { + return false; + } + nodes++; + } else { + return false; + } + } + } + } + + return datas * 2 + nodes == immutable.content.length; + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/InOrderMapCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/InOrderMapCursor.java new file mode 100644 index 00000000..7cc91004 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/InOrderMapCursor.java @@ -0,0 +1,146 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import tools.refinery.store.map.AnyVersionedMap; +import tools.refinery.store.map.ContentHashCode; +import tools.refinery.store.map.Cursor; +import tools.refinery.store.map.VersionedMap; + +import java.util.*; + +public class InOrderMapCursor implements Cursor { + // Constants + static final int INDEX_START = -1; + + // Tree stack + ArrayDeque> nodeStack; + ArrayDeque nodeIndexStack; + + + // Values + K key; + V value; + + // Hash code for checking concurrent modifications + final VersionedMap map; + final int creationHash; + + public InOrderMapCursor(VersionedMapStateImpl map) { + // Initializing tree stack + super(); + this.nodeStack = new ArrayDeque<>(); + this.nodeIndexStack = new ArrayDeque<>(); + if (map.root != null) { + this.nodeStack.add(map.root); + this.nodeIndexStack.push(INDEX_START); + } + + // Initializing cache + this.key = null; + this.value = null; + + // Initializing state + this.map = map; + this.creationHash = map.contentHashCode(ContentHashCode.APPROXIMATE_FAST); + } + + public K getKey() { + return key; + } + + public V getValue() { + return value; + } + + public boolean isTerminated() { + return this.nodeStack.isEmpty(); + } + + public boolean move() { + if (isDirty()) { + throw new ConcurrentModificationException(); + } + if (!isTerminated()) { + var node = this.nodeStack.peek(); + if (node == null) { + throw new IllegalStateException("Cursor is not terminated but the current node is missing"); + } + boolean result = node.moveToNextInorder(this); + if (this.nodeIndexStack.size() != this.nodeStack.size()) { + throw new IllegalArgumentException("Node stack is corrupted by illegal moves!"); + } + return result; + } + return false; + } + + public boolean skipCurrentNode() { + nodeStack.pop(); + nodeIndexStack.pop(); + return move(); + } + + @Override + public boolean isDirty() { + return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; + } + + @Override + public Set getDependingMaps() { + return Set.of(this.map); + } + + public static boolean sameSubNode(InOrderMapCursor cursor1, InOrderMapCursor cursor2) { + Node nodeOfCursor1 = cursor1.nodeStack.peek(); + Node nodeOfCursor2 = cursor2.nodeStack.peek(); + return Objects.equals(nodeOfCursor1, nodeOfCursor2); + } + + /** + * Compares the state of two cursors started on two {@link VersionedMap} of the same + * {@link tools.refinery.store.map.VersionedMapStore}. + * @param Key type + * @param Value type + * @param cursor1 first cursor + * @param cursor2 second cursor + * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the + * same position. + */ + public static int comparePosition(InOrderMapCursor cursor1, InOrderMapCursor cursor2) { + // If the state does not determine the order, then compare @nodeIndexStack. + Iterator nodeIndexStack1 = cursor1.nodeIndexStack.descendingIterator(); + Iterator nodeIndexStack2 = cursor2.nodeIndexStack.descendingIterator(); + + while(nodeIndexStack1.hasNext() && nodeIndexStack2.hasNext()){ + final int index1 = nodeIndexStack1.next(); + final int index2 = nodeIndexStack2.next(); + if(index1 < index2) { + return 1; + } else if(index1 > index2) { + return -1; + } + } + + return 0; + } + + /** + * Compares the depth of two cursors started on @{@link VersionedMap} of the same + * {@link tools.refinery.store.map.VersionedMapStore}. + * @param Key type + * @param Value type + * @param cursor1 first cursor + * @param cursor2 second cursor + * @return Positive number if cursor 1 is deeper, negative number if cursor 2 is deeper, and 0 if they are at the + * same depth. + */ + public static int compareDepth(InOrderMapCursor cursor1, InOrderMapCursor cursor2) { + int d1 = cursor1.nodeIndexStack.size(); + int d2 = cursor2.nodeIndexStack.size(); + return Integer.compare(d1, d2); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapCursor.java new file mode 100644 index 00000000..0db50d04 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapCursor.java @@ -0,0 +1,95 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import tools.refinery.store.map.AnyVersionedMap; +import tools.refinery.store.map.ContentHashCode; +import tools.refinery.store.map.Cursor; +import tools.refinery.store.map.VersionedMap; + +import java.util.ArrayDeque; +import java.util.ConcurrentModificationException; +import java.util.Set; + +public class MapCursor implements Cursor { + // Constants + static final int INDEX_START = -1; + static final int INDEX_FINISH = -2; + + // Tree stack + ArrayDeque> nodeStack; + ArrayDeque nodeIndexStack; + int dataIndex; + + // Values + K key; + V value; + + // Hash code for checking concurrent modifications + final VersionedMap map; + final int creationHash; + + public MapCursor(Node root, VersionedMap map) { + // Initializing tree stack + super(); + this.nodeStack = new ArrayDeque<>(); + this.nodeIndexStack = new ArrayDeque<>(); + if (root != null) { + this.nodeStack.add(root); + this.nodeIndexStack.push(INDEX_START); + } + + this.dataIndex = INDEX_START; + + // Initializing cache + this.key = null; + this.value = null; + + // Initializing state + this.map = map; + this.creationHash = map.contentHashCode(ContentHashCode.APPROXIMATE_FAST); + } + + public K getKey() { + return key; + } + + public V getValue() { + return value; + } + + public boolean isTerminated() { + return this.nodeStack.isEmpty(); + } + + public boolean move() { + if (isDirty()) { + throw new ConcurrentModificationException(); + } + if (!isTerminated()) { + var node = this.nodeStack.peek(); + if (node == null) { + throw new IllegalStateException("Cursor is not terminated but the current node is missing"); + } + boolean result = node.moveToNext(this); + if (this.nodeIndexStack.size() != this.nodeStack.size()) { + throw new IllegalArgumentException("Node stack is corrupted by illegal moves!"); + } + return result; + } + return false; + } + + @Override + public boolean isDirty() { + return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; + } + + @Override + public Set getDependingMaps() { + return Set.of(this.map); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapDiffCursor.java new file mode 100644 index 00000000..083bf8cf --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MapDiffCursor.java @@ -0,0 +1,264 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import tools.refinery.store.map.AnyVersionedMap; +import tools.refinery.store.map.Cursor; +import tools.refinery.store.map.DiffCursor; + +import java.util.Objects; +import java.util.Set; +import java.util.stream.Collectors; +import java.util.stream.Stream; + +/** + * A cursor representing the difference between two states of a map. + * + * @author Oszkar Semerath + */ +public class MapDiffCursor implements DiffCursor, Cursor { + private enum State { + /** + * initialized state. + */ + INIT, + /** + * Unstable state. + */ + MOVING_MOVING_SAME_KEY_SAME_VALUE, + /** + * Both cursors are moving, and they are on the same sub-node. + */ + MOVING_MOVING_SAME_NODE, + /** + * Both cursors are moving, cursor 1 is behind. + */ + MOVING_MOVING_BEHIND1, + /** + * Both cursors are moving, cursor 2 is behind. + */ + MOVING_MOVING_BEHIND2, + /** + * Both cursors are moving, cursor 1 is on the same key as cursor 2, values are different + */ + MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE, + /** + * Cursor 1 is moving, Cursor 2 is terminated. + */ + MOVING_TERMINATED, + /** + * Cursor 1 is terminated , Cursor 2 is moving. + */ + TERMINATED_MOVING, + /** + * Both cursors are terminated. + */ + TERMINATED_TERMINATED, + /** + * Both Cursors are moving, and they are on an incomparable position. + * It is resolved by showing Cursor 1. + */ + MOVING_MOVING_HASH1, + /** + * Both Cursors are moving, and they are on an incomparable position. + * It is resolved by showing Cursor 2. + */ + MOVING_MOVING_HASH2 + } + + /** + * Default nodeId representing missing elements. + */ + private final V defaultValue; + private final InOrderMapCursor cursor1; + private final InOrderMapCursor cursor2; + + // State + State state = State.INIT; + + // Values + private K key; + private V fromValue; + private V toValue; + + + public MapDiffCursor(V defaultValue, InOrderMapCursor cursor1, InOrderMapCursor cursor2) { + super(); + this.defaultValue = defaultValue; + this.cursor1 = cursor1; + this.cursor2 = cursor2; + } + + @Override + public K getKey() { + return key; + } + + @Override + public V getFromValue() { + return fromValue; + } + + @Override + public V getToValue() { + return toValue; + } + + @Override + public V getValue() { + return getToValue(); + } + + public boolean isTerminated() { + return this.state == State.TERMINATED_TERMINATED; + } + + @Override + public boolean isDirty() { + return this.cursor1.isDirty() || this.cursor2.isDirty(); + } + + @Override + public Set getDependingMaps() { + return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()).map(AnyVersionedMap.class::cast).collect(Collectors.toUnmodifiableSet()); + } + + private boolean isInStableState() { + return this.state != State.MOVING_MOVING_SAME_KEY_SAME_VALUE + && this.state != State.MOVING_MOVING_SAME_NODE && this.state != State.INIT; + } + + private boolean updateAndReturnWithResult() { + return switch (this.state) { + case INIT -> throw new IllegalStateException("DiffCursor terminated without starting!"); + case MOVING_MOVING_SAME_KEY_SAME_VALUE, MOVING_MOVING_SAME_NODE -> + throw new IllegalStateException("DiffCursor terminated in unstable state!"); + case MOVING_MOVING_BEHIND1, MOVING_TERMINATED, MOVING_MOVING_HASH1 -> { + this.key = this.cursor1.getKey(); + this.fromValue = this.cursor1.getValue(); + this.toValue = this.defaultValue; + yield true; + } + case MOVING_MOVING_BEHIND2, TERMINATED_MOVING, MOVING_MOVING_HASH2 -> { + this.key = this.cursor2.getKey(); + this.fromValue = this.defaultValue; + this.toValue = cursor2.getValue(); + yield true; + } + case MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE -> { + this.key = this.cursor1.getKey(); + this.fromValue = this.cursor1.getValue(); + this.toValue = this.cursor2.getValue(); + yield true; + } + case TERMINATED_TERMINATED -> { + this.key = null; + this.fromValue = null; + this.toValue = null; + yield false; + } + }; + } + + public boolean move() { + do { + this.state = moveOne(this.state); + } while (!isInStableState()); + return updateAndReturnWithResult(); + } + + private State moveOne(State currentState) { + return switch (currentState) { + case INIT, MOVING_MOVING_HASH2, MOVING_MOVING_SAME_KEY_SAME_VALUE, MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE -> { + boolean cursor1Moved = cursor1.move(); + boolean cursor2Moved = cursor2.move(); + yield recalculateStateAfterCursorMovement(cursor1Moved, cursor2Moved); + } + case MOVING_MOVING_SAME_NODE -> { + boolean cursor1Moved = cursor1.skipCurrentNode(); + boolean cursor2Moved = cursor2.skipCurrentNode(); + yield recalculateStateAfterCursorMovement(cursor1Moved, cursor2Moved); + } + case MOVING_MOVING_BEHIND1 -> { + boolean cursorMoved = cursor1.move(); + if (cursorMoved) { + yield recalculateStateBasedOnCursorRelation(); + } else { + yield State.TERMINATED_MOVING; + } + } + case MOVING_MOVING_BEHIND2 -> { + boolean cursorMoved = cursor2.move(); + if (cursorMoved) { + yield recalculateStateBasedOnCursorRelation(); + } else { + yield State.MOVING_TERMINATED; + } + } + case TERMINATED_MOVING -> { + boolean cursorMoved = cursor2.move(); + if (cursorMoved) { + yield State.TERMINATED_MOVING; + } else { + yield State.TERMINATED_TERMINATED; + } + } + case MOVING_TERMINATED -> { + boolean cursorMoved = cursor1.move(); + if (cursorMoved) { + yield State.MOVING_TERMINATED; + } else { + yield State.TERMINATED_TERMINATED; + } + } + case MOVING_MOVING_HASH1 -> State.MOVING_MOVING_HASH2; + case TERMINATED_TERMINATED -> throw new IllegalStateException("Trying to move while terminated!"); + }; + } + + private State recalculateStateAfterCursorMovement(boolean cursor1Moved, boolean cursor2Moved) { + if (cursor1Moved && cursor2Moved) { + return recalculateStateBasedOnCursorRelation(); + } else if (cursor1Moved) { + return State.MOVING_TERMINATED; + } else if (cursor2Moved) { + return State.TERMINATED_MOVING; + } else { + return State.TERMINATED_TERMINATED; + } + } + + private State recalculateStateBasedOnCursorRelation() { + final int relation = InOrderMapCursor.comparePosition(cursor1, cursor2); + + if (relation > 0) { + return State.MOVING_MOVING_BEHIND1; + } else if (relation < 0) { + return State.MOVING_MOVING_BEHIND2; + } + + if (InOrderMapCursor.sameSubNode(cursor1, cursor2)) { + return State.MOVING_MOVING_SAME_NODE; + } else if (Objects.equals(cursor1.getKey(), cursor2.getKey())) { + if (Objects.equals(cursor1.getValue(), cursor2.getValue())) { + return State.MOVING_MOVING_SAME_KEY_SAME_VALUE; + } else { + return State.MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE; + } + } + + final int depth = InOrderMapCursor.compareDepth(cursor1, cursor2); + + if (depth > 0) { + return State.MOVING_MOVING_BEHIND1; + } else if (depth < 0) { + return State.MOVING_MOVING_BEHIND2; + } else { + return State.MOVING_MOVING_HASH1; + } + + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MutableNode.java new file mode 100644 index 00000000..408ed62c --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/MutableNode.java @@ -0,0 +1,499 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import tools.refinery.store.map.ContinuousHashProvider; + +import java.util.Arrays; +import java.util.Map; + +public class MutableNode extends Node { + int cachedHash; + protected boolean cachedHashValid; + protected Object[] content; + + protected MutableNode() { + this.content = new Object[2 * FACTOR]; + invalidateHash(); + } + + public static MutableNode initialize(K key, V value, ContinuousHashProvider hashProvider, V defaultValue) { + if (value == defaultValue) { + return null; + } else { + int hash = hashProvider.getHash(key, 0); + int fragment = hashFragment(hash, 0); + MutableNode res = new MutableNode<>(); + res.content[2 * fragment] = key; + res.content[2 * fragment + 1] = value; + res.invalidateHash(); + return res; + } + } + + /** + * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode} + * + * @param node to be transformed + */ + protected MutableNode(ImmutableNode node) { + this.content = new Object[2 * FACTOR]; + int dataUsed = 0; + int nodeUsed = 0; + for (int i = 0; i < FACTOR; i++) { + int bitPosition = 1 << i; + if ((node.dataMap & bitPosition) != 0) { + content[2 * i] = node.content[dataUsed * 2]; + content[2 * i + 1] = node.content[dataUsed * 2 + 1]; + dataUsed++; + } else if ((node.nodeMap & bitPosition) != 0) { + content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed]; + nodeUsed++; + } + } + this.cachedHashValid = false; + } + + @Override + public V getValue(K key, ContinuousHashProvider hashProvider, V defaultValue, int hash, int depth) { + int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); + @SuppressWarnings("unchecked") K keyCandidate = (K) this.content[2 * selectedHashFragment]; + if (keyCandidate != null) { + if (keyCandidate.equals(key)) { + @SuppressWarnings("unchecked") V value = (V) this.content[2 * selectedHashFragment + 1]; + return value; + } else { + return defaultValue; + } + } else { + @SuppressWarnings("unchecked") var nodeCandidate = (Node) content[2 * selectedHashFragment + 1]; + if (nodeCandidate != null) { + int newDepth = incrementDepth(depth); + int newHash = newHash(hashProvider, key, hash, newDepth); + return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); + } else { + return defaultValue; + } + } + } + + @Override + public Node putValue(K key, V value, OldValueBox oldValueBox, ContinuousHashProvider hashProvider, V defaultValue, int hash, int depth) { + int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); + @SuppressWarnings("unchecked") K keyCandidate = (K) content[2 * selectedHashFragment]; + if (keyCandidate != null) { + // If it has key + if (keyCandidate.equals(key)) { + // The key is equals to an existing key -> update entry + if (value == defaultValue) { + return removeEntry(selectedHashFragment, oldValueBox); + } else { + return updateValue(value, oldValueBox, selectedHashFragment); + } + } else { + // The key is not equivalent to an existing key on the same hash bin + // -> split entry if it is necessary + if (value == defaultValue) { + // Value is default -> do not need to add new node + oldValueBox.setOldValue(defaultValue); + return this; + } else { + // Value is not default -> Split entry data to a new node + oldValueBox.setOldValue(defaultValue); + return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment); + } + } + } + // If it does not have key, check for value + @SuppressWarnings("unchecked") var nodeCandidate = (Node) content[2 * selectedHashFragment + 1]; + if (nodeCandidate != null) { + // If it has value, it is a sub-node -> update that + int newDepth = incrementDepth(depth); + var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, newHash(hashProvider, key, hash, newDepth), newDepth); + return updateWithSubNode(selectedHashFragment, newNode, (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); + } else { + // If it does not have value, put it in the empty place + if (value == defaultValue) { + // don't need to add new key-value pair + oldValueBox.setOldValue(defaultValue); + return this; + } else { + return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue); + } + } + } + + private Node addEntry(K key, V value, OldValueBox oldValueBox, int selectedHashFragment, V defaultValue) { + content[2 * selectedHashFragment] = key; + oldValueBox.setOldValue(defaultValue); + content[2 * selectedHashFragment + 1] = value; + invalidateHash(); + return this; + } + + /** + * Updates an entry in a selected hash-fragment to a non-default value. + * + * @param value new value + * @param selectedHashFragment position of the value + * @return updated node + */ + @SuppressWarnings("unchecked") + Node updateValue(V value, OldValueBox oldValue, int selectedHashFragment) { + oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); + content[2 * selectedHashFragment + 1] = value; + invalidateHash(); + return this; + } + + /** + * Updates an entry in a selected hash-fragment with a subtree. + * + * @param selectedHashFragment position of the value + * @param newNode the subtree + * @return updated node + */ + Node updateWithSubNode(int selectedHashFragment, Node newNode, boolean deletionHappened) { + if (deletionHappened) { + if (newNode == null) { + // Check whether this node become empty + content[2 * selectedHashFragment + 1] = null; // i.e. the new node + if (hasContent()) { + invalidateHash(); + return this; + } else { + return null; + } + } else { + // check whether newNode is orphan + MutableNode immutableNewNode = newNode.isMutable(); + if (immutableNewNode != null) { + int orphaned = immutableNewNode.isOrphaned(); + if (orphaned >= 0) { + // orphan sub-node data is replaced with data + content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2]; + content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1]; + invalidateHash(); + return this; + } + } + } + } + // normal behaviour + content[2 * selectedHashFragment + 1] = newNode; + invalidateHash(); + return this; + } + + private boolean hasContent() { + for (Object element : this.content) { + if (element != null) return true; + } + return false; + } + + @Override + protected MutableNode isMutable() { + return this; + } + + protected int isOrphaned() { + int dataFound = -2; + for (int i = 0; i < FACTOR; i++) { + if (content[i * 2] != null) { + if (dataFound >= 0) { + return -1; + } else { + dataFound = i; + } + } else if (content[i * 2 + 1] != null) { + return -3; + } + } + return dataFound; + } + + @SuppressWarnings("unchecked") + private Node moveDownAndSplit(ContinuousHashProvider hashProvider, K newKey, V newValue, K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) { + V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1]; + + MutableNode newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, incrementDepth(depth)); + + content[2 * selectedHashFragmentOfCurrentDepth] = null; + content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode; + invalidateHash(); + return this; + } + + // Pass everything as parameters for performance. + @SuppressWarnings("squid:S107") + private MutableNode newNodeWithTwoEntries(ContinuousHashProvider hashProvider, K key1, V value1, int oldHash1, K key2, V value2, int oldHash2, int newDepth) { + int newHash1 = newHash(hashProvider, key1, oldHash1, newDepth); + int newHash2 = newHash(hashProvider, key2, oldHash2, newDepth); + int newFragment1 = hashFragment(newHash1, shiftDepth(newDepth)); + int newFragment2 = hashFragment(newHash2, shiftDepth(newDepth)); + + MutableNode subNode = new MutableNode<>(); + if (newFragment1 != newFragment2) { + subNode.content[newFragment1 * 2] = key1; + subNode.content[newFragment1 * 2 + 1] = value1; + + subNode.content[newFragment2 * 2] = key2; + subNode.content[newFragment2 * 2 + 1] = value2; + } else { + MutableNode subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newDepth)); + subNode.content[newFragment1 * 2 + 1] = subSubNode; + } + subNode.invalidateHash(); + return subNode; + } + + @SuppressWarnings("unchecked") + Node removeEntry(int selectedHashFragment, OldValueBox oldValue) { + content[2 * selectedHashFragment] = null; + oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); + content[2 * selectedHashFragment + 1] = null; + if (hasContent()) { + invalidateHash(); + return this; + } else { + return null; + } + } + + @SuppressWarnings("unchecked") + @Override + public long getSize() { + int size = 0; + for (int i = 0; i < FACTOR; i++) { + if (content[i * 2] != null) { + size++; + } else { + Node nodeCandidate = (Node) content[i * 2 + 1]; + if (nodeCandidate != null) { + size += nodeCandidate.getSize(); + } + } + } + return size; + } + + @Override + protected MutableNode toMutable() { + return this; + } + + @Override + public ImmutableNode toImmutable(Map, ImmutableNode> cache) { + return ImmutableNode.constructImmutable(this, cache); + } + + @SuppressWarnings("unchecked") + @Override + boolean moveToNext(MapCursor cursor) { + // 1. try to move to data + if (cursor.dataIndex != MapCursor.INDEX_FINISH) { + for (int index = cursor.dataIndex + 1; index < FACTOR; index++) { + if (this.content[index * 2] != null) { + // 1.1 found next data + cursor.dataIndex = index; + cursor.key = (K) this.content[index * 2]; + cursor.value = (V) this.content[index * 2 + 1]; + return true; + } + } + cursor.dataIndex = MapCursor.INDEX_FINISH; + } + + // 2. look inside the sub-nodes + if(cursor.nodeIndexStack.peek()==null) { + throw new IllegalStateException("Cursor moved to the next state when the state is empty."); + } + for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) { + if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) { + // 2.1 found next sub-node, move down to the sub-node + Node subnode = (Node) this.content[index * 2 + 1]; + + cursor.dataIndex = MapCursor.INDEX_START; + cursor.nodeIndexStack.pop(); + cursor.nodeIndexStack.push(index); + cursor.nodeIndexStack.push(MapCursor.INDEX_START); + cursor.nodeStack.push(subnode); + + return subnode.moveToNext(cursor); + } + } + // 3. no sub-node found, move up + cursor.nodeStack.pop(); + cursor.nodeIndexStack.pop(); + if (!cursor.nodeStack.isEmpty()) { + Node supernode = cursor.nodeStack.peek(); + return supernode.moveToNext(cursor); + } else { + cursor.key = null; + cursor.value = null; + return false; + } + } + + @Override + @SuppressWarnings("unchecked") + boolean moveToNextInorder(InOrderMapCursor cursor) { + if(cursor.nodeIndexStack.peek()==null || cursor.nodeStack.peek()==null) { + throw new IllegalStateException("Cursor moved to the next state when the state is empty."); + } + + int position = cursor.nodeIndexStack.peek(); + + for (int index = position + 1; index < FACTOR; index++) { + // data found + if (this.content[index * 2] != null) { + cursor.nodeIndexStack.pop(); + cursor.nodeIndexStack.push(index); + + cursor.key = (K) this.content[index * 2]; + cursor.value = (V) this.content[index * 2 + 1]; + return true; + } else if (this.content[index * 2 +1] != null) { + // sub-node found + Node subnode = (Node) this.content[index * 2 +1]; + cursor.nodeIndexStack.pop(); + cursor.nodeIndexStack.push(index); + cursor.nodeIndexStack.push(InOrderMapCursor.INDEX_START); + cursor.nodeStack.push(subnode); + + return subnode.moveToNextInorder(cursor); + } + } + + // nothing found + cursor.nodeStack.pop(); + cursor.nodeIndexStack.pop(); + if (!cursor.nodeStack.isEmpty()) { + Node supernode = cursor.nodeStack.peek(); + return supernode.moveToNextInorder(cursor); + } else { + cursor.key = null; + cursor.value = null; + return false; + } + } + + @Override + public void prettyPrint(StringBuilder builder, int depth, int code) { + builder.append("\t".repeat(Math.max(0, depth))); + if (code >= 0) { + builder.append(code); + builder.append(":"); + } + builder.append("Mutable("); + // print content + boolean hadContent = false; + for (int i = 0; i < FACTOR; i++) { + if (content[2 * i] != null) { + if (hadContent) { + builder.append(","); + } + builder.append(i); + builder.append(":["); + builder.append(content[2 * i].toString()); + builder.append("]->["); + builder.append(content[2 * i + 1].toString()); + builder.append("]"); + hadContent = true; + } + } + builder.append(")"); + // print sub-nodes + for (int i = 0; i < FACTOR; i++) { + if (content[2 * i] == null && content[2 * i + 1] != null) { + @SuppressWarnings("unchecked") Node subNode = (Node) content[2 * i + 1]; + builder.append("\n"); + subNode.prettyPrint(builder, incrementDepth(depth), i); + } + } + } + + @Override + public void checkIntegrity(ContinuousHashProvider hashProvider, V defaultValue, int depth) { + // check for orphan nodes + if (depth > 0) { + int orphaned = isOrphaned(); + if (orphaned >= 0) { + throw new IllegalStateException("Orphaned node! " + orphaned + ": " + content[2 * orphaned]); + } + } + // check the place of data + for (int i = 0; i < FACTOR; i++) { + if (this.content[2 * i] != null) { + @SuppressWarnings("unchecked") K key = (K) this.content[2 * i]; + @SuppressWarnings("unchecked") V value = (V) this.content[2 * i + 1]; + + if (value == defaultValue) { + throw new IllegalStateException("Node contains default value!"); + } + int hashCode = hashProvider.getHash(key, hashDepth(depth)); + int shiftDepth = shiftDepth(depth); + int selectedHashFragment = hashFragment(hashCode, shiftDepth); + if (i != selectedHashFragment) { + throw new IllegalStateException("Key " + key + " with hash code " + hashCode + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i); + } + } + } + // check sub-nodes + for (int i = 0; i < FACTOR; i++) { + if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { + @SuppressWarnings("unchecked") var subNode = (Node) this.content[2 * i + 1]; + subNode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth)); + } + } + // check the hash + if (cachedHashValid) { + int oldHash = this.cachedHash; + invalidateHash(); + int newHash = hashCode(); + if (oldHash != newHash) { + throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")"); + } + } + } + + protected void invalidateHash() { + this.cachedHashValid = false; + } + + @Override + public int hashCode() { + if (!this.cachedHashValid) { + this.cachedHash = Arrays.hashCode(content); + this.cachedHashValid = true; + } + return this.cachedHash; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) return true; + if (obj == null) return false; + if (obj instanceof MutableNode mutableObj) { + if (obj.hashCode() != this.hashCode()) { + return false; + } else { + for (int i = 0; i < FACTOR * 2; i++) { + Object thisContent = this.content[i]; + if (thisContent != null && !thisContent.equals(mutableObj.content[i])) { + return false; + } + } + return true; + } + } else if (obj instanceof ImmutableNode immutableObj) { + return ImmutableNode.compareImmutableMutable(immutableObj, this); + } else { + return false; + } + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/Node.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/Node.java new file mode 100644 index 00000000..0ecf2712 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/Node.java @@ -0,0 +1,131 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import java.util.Map; + +import tools.refinery.store.map.ContinuousHashProvider; + +public abstract class Node { + public static final int BRANCHING_FACTOR_BITS = 5; + public static final int FACTOR = 1 << BRANCHING_FACTOR_BITS; + protected static final int NUMBER_OF_FACTORS = Integer.SIZE / BRANCHING_FACTOR_BITS; + protected static final int FACTOR_MASK = FACTOR - 1; + public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS; + public static final int FACTOR_SELECTION_BITS = 32 - Integer.numberOfLeadingZeros(NUMBER_OF_FACTORS); + public static final int FACTOR_SELECTION_MASK = (1 << FACTOR_SELECTION_BITS) - 1; + public static final int INCREMENT_BIG_STEP = (1 << FACTOR_SELECTION_BITS) - NUMBER_OF_FACTORS; + + /** + * Increments the depth of the search in the tree. The depth parameter has two + * components: the least few bits selects the fragment of the hashcode, the + * other part selects the continuous hash. + * + * @param depth parameter encoding the fragment and the depth + * @return new depth. + */ + protected int incrementDepth(int depth) { + int newDepth = depth + 1; + if ((newDepth & FACTOR_SELECTION_MASK) == NUMBER_OF_FACTORS) { + newDepth += INCREMENT_BIG_STEP; + } + return newDepth; + } + + /** + * Calculates the index for the continuous hash. + * + * @param depth The depth of the node in the tree. + * @return The index of the continuous hash. + */ + protected static int hashDepth(int depth) { + return depth >> FACTOR_SELECTION_BITS; + } + + /** + * Calculates the which segment of a single hash should be used. + * + * @param depth The depth of the node in the tree. + * @return The segment of a hash code. + */ + protected static int shiftDepth(int depth) { + return depth & FACTOR_SELECTION_MASK; + } + + /** + * Selects a segments from a complete hash for a given depth. + * + * @param hash A complete hash. + * @param shiftDepth The index of the segment. + * @return The segment as an integer. + */ + protected static int hashFragment(int hash, int shiftDepth) { + if (shiftDepth < 0 || Node.NUMBER_OF_FACTORS < shiftDepth) + throw new IllegalArgumentException("Invalid shift depth! valid interval=[0;5], input=" + shiftDepth); + return (hash >>> shiftDepth * BRANCHING_FACTOR_BITS) & FACTOR_MASK; + } + + /** + * Returns the hash code for a given depth. It may calculate new hash code, or + * reuse a hash code calculated for depth-1. + * + * @param key The key. + * @param hash Hash code for depth-1 + * @param depth The depth. + * @return The new hash code. + */ + protected int newHash(final ContinuousHashProvider hashProvider, K key, int hash, int depth) { + final int shiftDepth = shiftDepth(depth); + if (shiftDepth == 0) { + final int hashDepth = hashDepth(depth); + if (hashDepth >= ContinuousHashProvider.MAX_PRACTICAL_DEPTH) { + throw new IllegalArgumentException( + "Key " + key + " have the clashing hashcode over the practical depth limitation (" + + ContinuousHashProvider.MAX_PRACTICAL_DEPTH + ")!"); + } + return hashProvider.getHash(key, hashDepth); + } else { + return hash; + } + } + + public abstract V getValue(K key, ContinuousHashProvider hashProvider, V defaultValue, int hash, + int depth); + + public abstract Node putValue(K key, V value, OldValueBox old, + ContinuousHashProvider hashProvider, V defaultValue, int hash, int depth); + + public abstract long getSize(); + + abstract MutableNode toMutable(); + + public abstract ImmutableNode toImmutable(Map, ImmutableNode> cache); + + protected abstract MutableNode isMutable(); + + /** + * Moves a {@link MapCursor} to its next position. + * + * @param cursor the cursor + * @return Whether there was a next value to move on. + */ + abstract boolean moveToNext(MapCursor cursor); + abstract boolean moveToNextInorder(InOrderMapCursor cursor); + + ///////// FOR printing + public abstract void prettyPrint(StringBuilder builder, int depth, int code); + + + @Override + public String toString() { + StringBuilder stringBuilder = new StringBuilder(); + prettyPrint(stringBuilder, 0, -1); + return stringBuilder.toString(); + } + + public void checkIntegrity(ContinuousHashProvider hashProvider, V defaultValue, int depth) { + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/OldValueBox.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/OldValueBox.java new file mode 100644 index 00000000..1b0a4b0c --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/OldValueBox.java @@ -0,0 +1,24 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +public class OldValueBox{ + V oldValue; + boolean isSet = false; + + public V getOldValue() { + if(!isSet) throw new IllegalStateException(); + isSet = false; + return oldValue; + } + + public void setOldValue(V ouldValue) { + if(isSet) throw new IllegalStateException(); + this.oldValue = ouldValue; + isSet = true; + } + +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java new file mode 100644 index 00000000..9409ace0 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/StateBasedVersionedMapStoreFactory.java @@ -0,0 +1,38 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import tools.refinery.store.map.*; + +import java.util.List; + +public class StateBasedVersionedMapStoreFactory implements VersionedMapStoreFactory { + private final V defaultValue; + private final ContinuousHashProvider continuousHashProvider; + private final VersionedMapStoreStateConfiguration config; + + public StateBasedVersionedMapStoreFactory(V defaultValue, Boolean transformToImmutable, VersionedMapStoreFactoryBuilder.SharingStrategy sharingStrategy, ContinuousHashProvider continuousHashProvider) { + this.defaultValue = defaultValue; + this.continuousHashProvider = continuousHashProvider; + + this.config = new VersionedMapStoreStateConfiguration( + transformToImmutable, + sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE || sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP, + sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP); + } + + @Override + public VersionedMapStore createOne() { + return new VersionedMapStoreStateImpl<>(continuousHashProvider, defaultValue, config); + + } + + @Override + public List> createGroup(int amount) { + return VersionedMapStoreStateImpl.createSharedVersionedMapStores(amount, continuousHashProvider, defaultValue, + config); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStateImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStateImpl.java new file mode 100644 index 00000000..817fc70b --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStateImpl.java @@ -0,0 +1,171 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import tools.refinery.store.map.*; + +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; +import java.util.Objects; + +/** + * Not threadSafe in itself + * + * @param + * @param + * @author Oszkar Semerath + */ +public class VersionedMapStateImpl implements VersionedMap { + protected final VersionedMapStoreStateImpl store; + + protected final ContinuousHashProvider hashProvider; + protected final V defaultValue; + protected Node root; + + private final OldValueBox oldValueBox = new OldValueBox<>(); + + public VersionedMapStateImpl( + VersionedMapStoreStateImpl store, + ContinuousHashProvider hashProvider, + V defaultValue) { + this.store = store; + this.hashProvider = hashProvider; + this.defaultValue = defaultValue; + this.root = null; + } + + public VersionedMapStateImpl( + VersionedMapStoreStateImpl store, + ContinuousHashProvider hashProvider, + V defaultValue, Node data) { + this.store = store; + this.hashProvider = hashProvider; + this.defaultValue = defaultValue; + this.root = data; + } + + @Override + public V getDefaultValue() { + return defaultValue; + } + + public ContinuousHashProvider getHashProvider() { + return hashProvider; + } + + @Override + public V put(K key, V value) { + if (root != null) { + root = root.putValue(key, value, oldValueBox, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); + return oldValueBox.getOldValue(); + } else { + root = MutableNode.initialize(key, value, hashProvider, defaultValue); + return defaultValue; + } + } + + @Override + public void putAll(Cursor cursor) { + if (cursor.getDependingMaps().contains(this)) { + List keys = new LinkedList<>(); + List values = new LinkedList<>(); + while (cursor.move()) { + keys.add(cursor.getKey()); + values.add(cursor.getValue()); + } + Iterator keyIterator = keys.iterator(); + Iterator valueIterator = values.iterator(); + while (keyIterator.hasNext()) { + var key = keyIterator.next(); + var value = valueIterator.next(); + this.put(key,value); + } + } else { + while (cursor.move()) { + this.put(cursor.getKey(), cursor.getValue()); + } + } + } + + @Override + public V get(K key) { + if (root != null) { + return root.getValue(key, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); + } else { + return defaultValue; + } + } + + @Override + public long getSize() { + if (root == null) { + return 0; + } else { + return root.getSize(); + } + } + + @Override + public Cursor getAll() { + return new MapCursor<>(this.root, this); + } + + @Override + public DiffCursor getDiffCursor(long toVersion) { + InOrderMapCursor fromCursor = new InOrderMapCursor<>(this); + VersionedMapStateImpl toMap = (VersionedMapStateImpl) this.store.createMap(toVersion); + InOrderMapCursor toCursor = new InOrderMapCursor<>(toMap); + return new MapDiffCursor<>(this.defaultValue, fromCursor, toCursor); + } + + + @Override + public long commit() { + return this.store.commit(root, this); + } + + public void setRoot(Node root) { + this.root = root; + } + + @Override + public void restore(long state) { + root = this.store.revert(state); + } + + public String prettyPrint() { + if (this.root != null) { + StringBuilder s = new StringBuilder(); + this.root.prettyPrint(s, 0, -1); + return s.toString(); + } else { + return "empty tree"; + } + } + + @Override + public void checkIntegrity() { + if (this.root != null) { + this.root.checkIntegrity(hashProvider, defaultValue, 0); + } + } + + @Override + public int contentHashCode(ContentHashCode mode) { + // Calculating the root hashCode is always fast, because {@link Node} caches its hashCode. + if(root == null) { + return 0; + } else { + return root.hashCode(); + } + } + + @Override + public boolean contentEquals(AnyVersionedMap other) { + return other instanceof VersionedMapStateImpl otherImpl && Objects.equals(root, otherImpl.root); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateConfiguration.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateConfiguration.java new file mode 100644 index 00000000..45f30cc7 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateConfiguration.java @@ -0,0 +1,56 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import tools.refinery.store.map.ContinuousHashProvider; +import tools.refinery.store.map.VersionedMapStore; + +public class VersionedMapStoreStateConfiguration { + + public VersionedMapStoreStateConfiguration() { + + } + public VersionedMapStoreStateConfiguration(boolean immutableWhenCommitting, boolean sharedNodeCacheInStore, + boolean sharedNodeCacheInStoreGroups) { + super(); + this.immutableWhenCommitting = immutableWhenCommitting; + this.sharedNodeCacheInStore = sharedNodeCacheInStore; + this.sharedNodeCacheInStoreGroups = sharedNodeCacheInStoreGroups; + } + + /** + * If true root is replaced with immutable node when committed. Frees up memory + * by releasing immutable nodes, but it may decrease performance by recreating + * immutable nodes upon changes (some evidence). + */ + private boolean immutableWhenCommitting = true; + public boolean isImmutableWhenCommitting() { + return immutableWhenCommitting; + } + + /** + * If true, all sub-nodes are cached within a {@link VersionedMapStore}. It + * decreases the memory requirements. It may increase performance by discovering + * existing immutable copy of a node (some evidence). Additional overhead may + * decrease performance (no example found). The option permits the efficient + * implementation of version deletion. + */ + private boolean sharedNodeCacheInStore = true; + public boolean isSharedNodeCacheInStore() { + return sharedNodeCacheInStore; + } + + /** + * If true, all sub-nodes are cached within a group of + * {@link VersionedMapStoreStateImpl#createSharedVersionedMapStores(int, ContinuousHashProvider, Object, VersionedMapStoreStateConfiguration)}. + * If {@link VersionedMapStoreStateConfiguration#sharedNodeCacheInStore} is + * false, then it has currently no impact. + */ + private boolean sharedNodeCacheInStoreGroups = true; + public boolean isSharedNodeCacheInStoreGroups() { + return sharedNodeCacheInStoreGroups; + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java new file mode 100644 index 00000000..0651772a --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/state/VersionedMapStoreStateImpl.java @@ -0,0 +1,129 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.map.internal.state; + +import tools.refinery.store.map.*; + +import java.util.*; + +public class VersionedMapStoreStateImpl implements VersionedMapStore { + // Configuration + private final boolean immutableWhenCommitting; + + // Static data + protected final ContinuousHashProvider hashProvider; + protected final V defaultValue; + + // Dynamic data + protected final Map> states = new HashMap<>(); + protected final Map, ImmutableNode> nodeCache; + protected long nextID = 0; + + public VersionedMapStoreStateImpl(ContinuousHashProvider hashProvider, V defaultValue, + VersionedMapStoreStateConfiguration config) { + this.immutableWhenCommitting = config.isImmutableWhenCommitting(); + this.hashProvider = hashProvider; + this.defaultValue = defaultValue; + if (config.isSharedNodeCacheInStore()) { + nodeCache = new HashMap<>(); + } else { + nodeCache = null; + } + } + + private VersionedMapStoreStateImpl(ContinuousHashProvider hashProvider, V defaultValue, + Map, ImmutableNode> nodeCache, VersionedMapStoreStateConfiguration config) { + this.immutableWhenCommitting = config.isImmutableWhenCommitting(); + this.hashProvider = hashProvider; + this.defaultValue = defaultValue; + this.nodeCache = nodeCache; + } + + public VersionedMapStoreStateImpl(ContinuousHashProvider hashProvider, V defaultValue) { + this(hashProvider, defaultValue, new VersionedMapStoreStateConfiguration()); + } + + public static List> createSharedVersionedMapStores(int amount, + ContinuousHashProvider hashProvider, V defaultValue, + VersionedMapStoreStateConfiguration config) { + List> result = new ArrayList<>(amount); + if (config.isSharedNodeCacheInStoreGroups()) { + Map, ImmutableNode> nodeCache; + if (config.isSharedNodeCacheInStore()) { + nodeCache = new HashMap<>(); + } else { + nodeCache = null; + } + for (int i = 0; i < amount; i++) { + result.add(new VersionedMapStoreStateImpl<>(hashProvider, defaultValue, nodeCache, config)); + } + } else { + for (int i = 0; i < amount; i++) { + result.add(new VersionedMapStoreStateImpl<>(hashProvider, defaultValue, config)); + } + } + return result; + } + + public static List> createSharedVersionedMapStores(int amount, + ContinuousHashProvider hashProvider, V defaultValue) { + return createSharedVersionedMapStores(amount, hashProvider, defaultValue, new VersionedMapStoreStateConfiguration()); + } + + @Override + public synchronized Set getStates() { + return new HashSet<>(states.keySet()); + } + + @Override + public VersionedMap createMap() { + return new VersionedMapStateImpl<>(this, hashProvider, defaultValue); + } + + @Override + public VersionedMap createMap(long state) { + ImmutableNode data = revert(state); + return new VersionedMapStateImpl<>(this, hashProvider, defaultValue, data); + } + + public synchronized ImmutableNode revert(long state) { + if (states.containsKey(state)) { + return states.get(state); + } else { + ArrayList existingKeys = new ArrayList<>(states.keySet()); + Collections.sort(existingKeys); + throw new IllegalArgumentException("Store does not contain state " + state + "! Available states: " + + Arrays.toString(existingKeys.toArray())); + } + } + + public synchronized long commit(Node data, VersionedMapStateImpl mapToUpdateRoot) { + ImmutableNode immutable; + if (data != null) { + immutable = data.toImmutable(this.nodeCache); + } else { + immutable = null; + } + + if (nextID == Long.MAX_VALUE) + throw new IllegalStateException("Map store run out of Id-s"); + long id = nextID++; + this.states.put(id, immutable); + if (this.immutableWhenCommitting) { + mapToUpdateRoot.setRoot(immutable); + } + return id; + } + + @Override + public DiffCursor getDiffCursor(long fromState, long toState) { + VersionedMapStateImpl map1 = (VersionedMapStateImpl) createMap(fromState); + VersionedMapStateImpl map2 = (VersionedMapStateImpl) createMap(toState); + InOrderMapCursor cursor1 = new InOrderMapCursor<>(map1); + InOrderMapCursor cursor2 = new InOrderMapCursor<>(map2); + return new MapDiffCursor<>(this.defaultValue, cursor1, cursor2); + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java b/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java index fdd4425e..3c94541f 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java +++ b/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProvider.java @@ -5,12 +5,12 @@ */ package tools.refinery.store.model; -import tools.refinery.store.map.ContinousHashProvider; +import tools.refinery.store.map.ContinuousHashProvider; import tools.refinery.store.tuple.Tuple; import tools.refinery.store.tuple.Tuple1; import tools.refinery.store.tuple.Tuple2; -public class TupleHashProvider implements ContinousHashProvider { +public class TupleHashProvider implements ContinuousHashProvider { protected static final int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java b/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java deleted file mode 100644 index 14116a90..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/model/TupleHashProviderBitMagic.java +++ /dev/null @@ -1,34 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.model; - -import tools.refinery.store.map.ContinousHashProvider; -import tools.refinery.store.tuple.Tuple; - -public class TupleHashProviderBitMagic implements ContinousHashProvider { - - @Override - public int getHash(Tuple key, int index) { - if(key.getSize() == 1) { - return key.get(0); - } - - int result = 0; - final int startBitIndex = index*30; - final int finalBitIndex = startBitIndex+30; - final int arity = key.getSize(); - - for(int i = startBitIndex; i<=finalBitIndex; i++) { - final int selectedKey = key.get(i%arity); - final int selectedPosition = 1<<(i/arity); - if((selectedKey&selectedPosition) != 0) { - result |= 1<<(i%30); - } - } - - return result; - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java index aafbe130..2cc7b19c 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/ModelStoreBuilderImpl.java @@ -8,10 +8,10 @@ package tools.refinery.store.model.internal; import tools.refinery.store.adapter.AdapterUtils; import tools.refinery.store.adapter.ModelAdapterBuilder; import tools.refinery.store.map.VersionedMapStore; -import tools.refinery.store.map.VersionedMapStoreImpl; +import tools.refinery.store.map.VersionedMapStoreFactory; +import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; import tools.refinery.store.model.ModelStore; import tools.refinery.store.model.ModelStoreBuilder; -import tools.refinery.store.model.TupleHashProvider; import tools.refinery.store.representation.AnySymbol; import tools.refinery.store.representation.Symbol; import tools.refinery.store.tuple.Tuple; @@ -77,8 +77,12 @@ public class ModelStoreBuilderImpl implements ModelStoreBuilder { private void createStores(Map> stores, SymbolEquivalenceClass equivalenceClass, List symbols) { int size = symbols.size(); - var storeGroup = VersionedMapStoreImpl.createSharedVersionedMapStores(size, TupleHashProvider.INSTANCE, - equivalenceClass.defaultValue()); + VersionedMapStoreFactory mapFactory = VersionedMapStore + .builder() + .strategy(VersionedMapStoreFactoryBuilder.StoreStrategy.DELTA) + .defaultValue(equivalenceClass.defaultValue()) + .build(); + var storeGroup = mapFactory.createGroup(size); for (int i = 0; i < size; i++) { stores.put(symbols.get(i), storeGroup.get(i)); } diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java index 4ada4ea4..98756460 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java @@ -8,8 +8,8 @@ package tools.refinery.store.map.tests; import org.junit.jupiter.api.Test; import tools.refinery.store.map.VersionedMapStore; import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; -import tools.refinery.store.map.internal.InOrderMapCursor; -import tools.refinery.store.map.internal.VersionedMapImpl; +import tools.refinery.store.map.internal.state.InOrderMapCursor; +import tools.refinery.store.map.internal.state.VersionedMapStateImpl; import tools.refinery.store.map.tests.utils.MapTestEnvironment; import static org.junit.jupiter.api.Assertions.*; @@ -26,7 +26,7 @@ class InOrderCursorTest { .build() .createOne(); - VersionedMapImpl map = (VersionedMapImpl) store.createMap(); + VersionedMapStateImpl map = (VersionedMapStateImpl) store.createMap(); checkMove(map,0); map.put(1,"A"); @@ -44,7 +44,7 @@ class InOrderCursorTest { } - private void checkMove(VersionedMapImpl map, int num) { + private void checkMove(VersionedMapStateImpl map, int num) { InOrderMapCursor cursor = new InOrderMapCursor<>(map); for(int i=0; i store = new VersionedMapStoreImpl<>(TupleHashProvider.INSTANCE, false); + VersionedMapStore store = new VersionedMapStoreStateImpl<>(TupleHashProvider.INSTANCE, false); var map = store.createMap(); var out1 = map.put(Tuple.of(0), true); assertEquals(false, out1); diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java index 420dade6..abfb4791 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableImmutableCompareFuzzTest.java @@ -17,10 +17,10 @@ import org.junit.jupiter.params.ParameterizedTest; import org.junit.jupiter.params.provider.Arguments; import org.junit.jupiter.params.provider.MethodSource; -import tools.refinery.store.map.ContinousHashProvider; +import tools.refinery.store.map.ContinuousHashProvider; import tools.refinery.store.map.VersionedMapStore; -import tools.refinery.store.map.VersionedMapStoreImpl; -import tools.refinery.store.map.internal.VersionedMapImpl; +import tools.refinery.store.map.internal.state.VersionedMapStoreStateImpl; +import tools.refinery.store.map.internal.state.VersionedMapStateImpl; import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; import tools.refinery.store.map.tests.utils.MapTestEnvironment; @@ -28,11 +28,11 @@ class MutableImmutableCompareFuzzTest { private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean nullDefault, int commitFrequency, boolean evilHash) { String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); - ContinousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); + ContinuousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); - VersionedMapStore store = new VersionedMapStoreImpl<>(chp, values[0]); - VersionedMapImpl immutable = (VersionedMapImpl) store.createMap(); - VersionedMapImpl mutable = (VersionedMapImpl) store.createMap(); + VersionedMapStore store = new VersionedMapStoreStateImpl<>(chp, values[0]); + VersionedMapStateImpl immutable = (VersionedMapStateImpl) store.createMap(); + VersionedMapStateImpl mutable = (VersionedMapStateImpl) store.createMap(); Random r = new Random(seed); @@ -40,8 +40,8 @@ class MutableImmutableCompareFuzzTest { commitFrequency); } - private void iterativeRandomPutsAndCommitsAndCompare(String scenario, VersionedMapImpl immutable, - VersionedMapImpl mutable, int steps, int maxKey, String[] values, Random r, + private void iterativeRandomPutsAndCommitsAndCompare(String scenario, VersionedMapStateImpl immutable, + VersionedMapStateImpl mutable, int steps, int maxKey, String[] values, Random r, int commitFrequency) { for (int i = 0; i < steps; i++) { int index = i + 1; diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java index 680d962d..b17766b7 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SharedStoreFuzzTest.java @@ -18,10 +18,10 @@ import org.junit.jupiter.params.ParameterizedTest; import org.junit.jupiter.params.provider.Arguments; import org.junit.jupiter.params.provider.MethodSource; -import tools.refinery.store.map.ContinousHashProvider; +import tools.refinery.store.map.ContinuousHashProvider; import tools.refinery.store.map.VersionedMapStore; -import tools.refinery.store.map.VersionedMapStoreImpl; -import tools.refinery.store.map.internal.VersionedMapImpl; +import tools.refinery.store.map.internal.state.VersionedMapStoreStateImpl; +import tools.refinery.store.map.internal.state.VersionedMapStateImpl; import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; import tools.refinery.store.map.tests.utils.MapTestEnvironment; @@ -31,9 +31,9 @@ class SharedStoreFuzzTest { private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean nullDefault, int commitFrequency, boolean evilHash) { String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); - ContinousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); + ContinuousHashProvider chp = MapTestEnvironment.prepareHashProvider(evilHash); - List> stores = VersionedMapStoreImpl.createSharedVersionedMapStores(5, chp, values[0]); + List> stores = VersionedMapStoreStateImpl.createSharedVersionedMapStores(5, chp, values[0]); iterativeRandomPutsAndCommitsThenRestore(scenario, stores, steps, maxKey, values, seed, commitFrequency); } @@ -42,9 +42,9 @@ class SharedStoreFuzzTest { int steps, int maxKey, String[] values, int seed, int commitFrequency) { // 1. maps with versions Random r = new Random(seed); - List> versioneds = new LinkedList<>(); + List> versioneds = new LinkedList<>(); for (VersionedMapStore store : stores) { - versioneds.add((VersionedMapImpl) store.createMap()); + versioneds.add((VersionedMapStateImpl) store.createMap()); } List> index2Version = new LinkedList<>(); @@ -66,9 +66,9 @@ class SharedStoreFuzzTest { } } // 2. create a non-versioned and - List> reference = new LinkedList<>(); + List> reference = new LinkedList<>(); for (VersionedMapStore store : stores) { - reference.add((VersionedMapImpl) store.createMap()); + reference.add((VersionedMapStateImpl) store.createMap()); } r = new Random(seed); diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java index e7348370..401f2866 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/utils/MapTestEnvironment.java @@ -6,7 +6,7 @@ package tools.refinery.store.map.tests.utils; import tools.refinery.store.map.*; -import tools.refinery.store.map.internal.VersionedMapImpl; +import tools.refinery.store.map.internal.state.VersionedMapStateImpl; import java.util.*; import java.util.Map.Entry; @@ -28,7 +28,7 @@ public class MapTestEnvironment { return values; } - public static ContinousHashProvider prepareHashProvider(final boolean evil) { + public static ContinuousHashProvider prepareHashProvider(final boolean evil) { // Use maxPrime = 2147483629 return (key, index) -> { @@ -187,7 +187,7 @@ public class MapTestEnvironment { //System.out.println(cursor.getKey() + " " + ((VersionedMapImpl) versionedMap).getHashProvider() // .getHash(cursor.getKey(), 0)); if (previous != null) { - int comparisonResult = ((VersionedMapImpl) versionedMap).getHashProvider().compare(previous, + int comparisonResult = ((VersionedMapStateImpl) versionedMap).getHashProvider().compare(previous, cursor.getKey()); assertTrue(comparisonResult < 0, scenario + " Cursor order is not incremental!"); } diff --git a/subprojects/store/src/test/java/tools/refinery/store/model/hashtests/HashEfficiencyTest.java b/subprojects/store/src/test/java/tools/refinery/store/model/hashtests/HashEfficiencyTest.java index 4d4f5e26..5b595da7 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/model/hashtests/HashEfficiencyTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/model/hashtests/HashEfficiencyTest.java @@ -3,7 +3,7 @@ * * SPDX-License-Identifier: EPL-2.0 */ -package tools.refinery.store.model.hashtests; +package tools.refinery.store.model.hashTests; import static org.junit.jupiter.api.Assertions.assertEquals; @@ -14,10 +14,9 @@ import java.util.Random; import org.junit.jupiter.api.Test; -import tools.refinery.store.map.ContinousHashProvider; +import tools.refinery.store.map.ContinuousHashProvider; import tools.refinery.store.tuple.Tuple; import tools.refinery.store.model.TupleHashProvider; -import tools.refinery.store.model.TupleHashProviderBitMagic; class HashEfficiencyTest { @@ -95,7 +94,7 @@ class HashEfficiencyTest { List p = nRandoms(2, amount, 1);; assertEquals(amount,p.size()); } - private static double calculateHashClashes(List tuples, ContinousHashProvider chp) { + private static double calculateHashClashes(List tuples, ContinuousHashProvider chp) { int sumClashes = 0; for(int i = 0; i chp, Tuple a, Tuple b) { + private static int calculateHashClash(ContinuousHashProvider chp, Tuple a, Tuple b) { if(a.equals(b)) return 0; final int bits = 5; final int segments = Integer.SIZE/bits; @@ -131,11 +130,9 @@ class HashEfficiencyTest { } public static void main(String[] args) { List hashNames = new LinkedList<>(); - List> hashes = new LinkedList<>(); + List> hashes = new LinkedList<>(); hashNames.add("PrimeGroup"); hashes.add(new TupleHashProvider()); - hashNames.add("BitMagic"); - hashes.add(new TupleHashProviderBitMagic()); int[] arities = new int[] {2,3,4,5}; int[] sizes = new int[] {32*32,32*32*8}; -- cgit v1.2.3-70-g09d2