diff options
author | Oszkár Semeráth <semerath@mit.bme.hu> | 2023-07-24 15:15:53 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2023-07-24 15:15:53 +0200 |
commit | a505730484320969f7ed5a8595581c4eddd97c90 (patch) | |
tree | 9c14b8d3ae13dacf0662422723ff7f880ab70839 /subprojects/store | |
parent | Merge pull request #27 from kris7t/ordered-result-set (diff) | |
parent | Enabled QueryTransactionTest (diff) | |
download | refinery-a505730484320969f7ed5a8595581c4eddd97c90.tar.gz refinery-a505730484320969f7ed5a8595581c4eddd97c90.tar.zst refinery-a505730484320969f7ed5a8595581c4eddd97c90.zip |
Merge pull request #30 from OszkarSemerath/datastructure
Datastructure
Diffstat (limited to 'subprojects/store')
45 files changed, 2351 insertions, 812 deletions
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 edd4f53e..7e89cd06 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 | |||
@@ -40,7 +40,7 @@ public class ImmutablePutExecutionPlan { | |||
40 | @Setup(Level.Trial) | 40 | @Setup(Level.Trial) |
41 | public void setUpTrial() { | 41 | public void setUpTrial() { |
42 | random = new Random(); | 42 | random = new Random(); |
43 | values = MapTestEnvironment.prepareValues(nValues); | 43 | values = MapTestEnvironment.prepareValues(nValues, true); |
44 | } | 44 | } |
45 | 45 | ||
46 | public VersionedMapImpl<Integer, String> createSut() { | 46 | public VersionedMapImpl<Integer, String> createSut() { |
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/AnyVersionedMap.java b/subprojects/store/src/main/java/tools/refinery/store/map/AnyVersionedMap.java index 25fc91e6..01099eb0 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/AnyVersionedMap.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/AnyVersionedMap.java | |||
@@ -42,4 +42,9 @@ public sealed interface AnyVersionedMap extends Versioned permits VersionedMap { | |||
42 | @SuppressWarnings("squid:S1133") | 42 | @SuppressWarnings("squid:S1133") |
43 | @Deprecated(since = "0.0.0") | 43 | @Deprecated(since = "0.0.0") |
44 | boolean equals(Object obj); | 44 | boolean equals(Object obj); |
45 | |||
46 | /** | ||
47 | * Checks the integrity of the map, and throws an exception if an inconsistency is detected. | ||
48 | */ | ||
49 | void checkIntegrity(); | ||
45 | } | 50 | } |
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java index 9bbde24d..c8226c3e 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMap.java | |||
@@ -6,6 +6,8 @@ | |||
6 | package tools.refinery.store.map; | 6 | package tools.refinery.store.map; |
7 | 7 | ||
8 | public non-sealed interface VersionedMap<K, V> extends AnyVersionedMap { | 8 | public non-sealed interface VersionedMap<K, V> extends AnyVersionedMap { |
9 | V getDefaultValue(); | ||
10 | |||
9 | V get(K key); | 11 | V get(K key); |
10 | 12 | ||
11 | Cursor<K, V> getAll(); | 13 | Cursor<K, V> getAll(); |
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java index 5aafa338..b24c404c 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStore.java | |||
@@ -5,15 +5,21 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.map; | 6 | package tools.refinery.store.map; |
7 | 7 | ||
8 | import tools.refinery.store.map.internal.VersionedMapStoreFactoryBuilderImpl; | ||
9 | |||
8 | import java.util.Set; | 10 | import java.util.Set; |
9 | 11 | ||
10 | public interface VersionedMapStore<K, V> { | 12 | public interface VersionedMapStore<K, V> { |
11 | |||
12 | public VersionedMap<K, V> createMap(); | ||
13 | 13 | ||
14 | public VersionedMap<K, V> createMap(long state); | 14 | VersionedMap<K, V> createMap(); |
15 | 15 | ||
16 | public Set<Long> getStates(); | 16 | VersionedMap<K, V> createMap(long state); |
17 | |||
18 | Set<Long> getStates(); | ||
19 | |||
20 | DiffCursor<K,V> getDiffCursor(long fromState, long toState); | ||
17 | 21 | ||
18 | public DiffCursor<K,V> getDiffCursor(long fromState, long toState); | 22 | static <K,V> VersionedMapStoreFactoryBuilder<K,V> builder() { |
19 | } \ No newline at end of file | 23 | return new VersionedMapStoreFactoryBuilderImpl<>(); |
24 | } | ||
25 | } | ||
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java new file mode 100644 index 00000000..0c61bd09 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreDeltaImpl.java | |||
@@ -0,0 +1,99 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map; | ||
7 | |||
8 | import java.util.*; | ||
9 | |||
10 | import tools.refinery.store.map.internal.*; | ||
11 | |||
12 | public class VersionedMapStoreDeltaImpl<K, V> implements VersionedMapStore<K, V> { | ||
13 | // Configuration | ||
14 | protected final boolean summarizeChanges; | ||
15 | |||
16 | // Static data | ||
17 | protected final V defaultValue; | ||
18 | |||
19 | // Dynamic data | ||
20 | protected final Map<Long, MapTransaction<K, V>> states = new HashMap<>(); | ||
21 | protected long nextID = 0; | ||
22 | |||
23 | public VersionedMapStoreDeltaImpl(boolean summarizeChanges, V defaultValue) { | ||
24 | this.summarizeChanges = summarizeChanges; | ||
25 | this.defaultValue = defaultValue; | ||
26 | } | ||
27 | |||
28 | @Override | ||
29 | public VersionedMap<K, V> createMap() { | ||
30 | return new VersionedMapDeltaImpl<>(this, this.summarizeChanges, this.defaultValue); | ||
31 | } | ||
32 | |||
33 | @Override | ||
34 | public VersionedMap<K, V> createMap(long state) { | ||
35 | VersionedMapDeltaImpl<K, V> result = new VersionedMapDeltaImpl<>(this, this.summarizeChanges, this.defaultValue); | ||
36 | result.restore(state); | ||
37 | return result; | ||
38 | } | ||
39 | |||
40 | public synchronized MapTransaction<K, V> appendTransaction(MapDelta<K, V>[] deltas, MapTransaction<K, V> previous, long[] versionContainer) { | ||
41 | long version = nextID++; | ||
42 | versionContainer[0] = version; | ||
43 | if (deltas == null) { | ||
44 | states.put(version, previous); | ||
45 | return previous; | ||
46 | } else { | ||
47 | MapTransaction<K, V> transaction = new MapTransaction<>(deltas, version, previous); | ||
48 | states.put(version, transaction); | ||
49 | return transaction; | ||
50 | } | ||
51 | } | ||
52 | |||
53 | private synchronized MapTransaction<K, V> getState(long state) { | ||
54 | return states.get(state); | ||
55 | } | ||
56 | |||
57 | public MapTransaction<K, V> getPath(long to, List<MapDelta<K, V>[]> forwardTransactions) { | ||
58 | final MapTransaction<K, V> target = getState(to); | ||
59 | MapTransaction<K, V> toTransaction = target; | ||
60 | while (toTransaction != null) { | ||
61 | forwardTransactions.add(toTransaction.deltas()); | ||
62 | toTransaction = toTransaction.parent(); | ||
63 | } | ||
64 | return target; | ||
65 | } | ||
66 | |||
67 | public MapTransaction<K, V> getPath(long from, long to, | ||
68 | List<MapDelta<K, V>[]> backwardTransactions, | ||
69 | List<MapDelta<K, V>[]> forwardTransactions) { | ||
70 | MapTransaction<K, V> fromTransaction = getState(from); | ||
71 | final MapTransaction<K, V> target = getState(to); | ||
72 | MapTransaction<K, V> toTransaction = target; | ||
73 | |||
74 | while (fromTransaction != toTransaction) { | ||
75 | if (fromTransaction == null || (toTransaction != null && fromTransaction.version() < toTransaction.version())) { | ||
76 | forwardTransactions.add(toTransaction.deltas()); | ||
77 | toTransaction = toTransaction.parent(); | ||
78 | } else { | ||
79 | backwardTransactions.add(fromTransaction.deltas()); | ||
80 | fromTransaction = fromTransaction.parent(); | ||
81 | } | ||
82 | } | ||
83 | return target; | ||
84 | } | ||
85 | |||
86 | |||
87 | @Override | ||
88 | public synchronized Set<Long> getStates() { | ||
89 | return new HashSet<>(states.keySet()); | ||
90 | } | ||
91 | |||
92 | @Override | ||
93 | public DiffCursor<K, V> getDiffCursor(long fromState, long toState) { | ||
94 | List<MapDelta<K, V>[]> backwardTransactions = new ArrayList<>(); | ||
95 | List<MapDelta<K, V>[]> forwardTransactions = new ArrayList<>(); | ||
96 | getPath(fromState, toState, backwardTransactions, forwardTransactions); | ||
97 | return new DeltaDiffCursor<>(backwardTransactions, forwardTransactions); | ||
98 | } | ||
99 | } | ||
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactory.java b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactory.java new file mode 100644 index 00000000..baf6ab50 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactory.java | |||
@@ -0,0 +1,24 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map; | ||
7 | |||
8 | import java.util.List; | ||
9 | |||
10 | public interface VersionedMapStoreFactory<K,V> { | ||
11 | /** | ||
12 | * Constructs a new instance of {@link VersionedMap}. | ||
13 | * @return The new instance. | ||
14 | */ | ||
15 | VersionedMapStore<K,V> createOne(); | ||
16 | |||
17 | /** | ||
18 | * Constructs a group of {@link VersionedMap}s with the same configuration. If possible, the stores share | ||
19 | * resources with each other. | ||
20 | * @param amount The amount of new instances to be created. | ||
21 | * @return A list of new stores with the given number of elements. | ||
22 | */ | ||
23 | List<VersionedMapStore<K, V>> createGroup(int amount); | ||
24 | } | ||
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 new file mode 100644 index 00000000..6329a2f6 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreFactoryBuilder.java | |||
@@ -0,0 +1,29 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map; | ||
7 | |||
8 | public interface VersionedMapStoreFactoryBuilder<K,V> { | ||
9 | enum StoreStrategy { | ||
10 | STATE, DELTA | ||
11 | } | ||
12 | |||
13 | enum DeltaTransactionStrategy { | ||
14 | LIST, SET | ||
15 | } | ||
16 | |||
17 | enum SharingStrategy { | ||
18 | NO_NODE_CACHE, SHARED_NODE_CACHE, SHARED_NODE_CACHE_IN_GROUP | ||
19 | } | ||
20 | |||
21 | VersionedMapStoreFactoryBuilder<K,V> defaultValue(V defaultValue); | ||
22 | VersionedMapStoreFactoryBuilder<K,V> strategy(StoreStrategy strategy); | ||
23 | VersionedMapStoreFactoryBuilder<K,V> stateBasedImmutableWhenCommitting(boolean transformToImmutable); | ||
24 | VersionedMapStoreFactoryBuilder<K,V> stateBasedSharingStrategy(SharingStrategy sharingStrategy); | ||
25 | VersionedMapStoreFactoryBuilder<K,V> stateBasedHashProvider(ContinousHashProvider<K> hashProvider); | ||
26 | VersionedMapStoreFactoryBuilder<K,V> deltaTransactionStrategy(DeltaTransactionStrategy deltaStrategy); | ||
27 | |||
28 | VersionedMapStoreFactory<K,V> build(); | ||
29 | } | ||
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 index aade4aeb..a934d59e 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/VersionedMapStoreImpl.java | |||
@@ -5,10 +5,7 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.map; | 6 | package tools.refinery.store.map; |
7 | 7 | ||
8 | import tools.refinery.store.map.internal.ImmutableNode; | 8 | import tools.refinery.store.map.internal.*; |
9 | import tools.refinery.store.map.internal.MapDiffCursor; | ||
10 | import tools.refinery.store.map.internal.Node; | ||
11 | import tools.refinery.store.map.internal.VersionedMapImpl; | ||
12 | 9 | ||
13 | import java.util.*; | 10 | import java.util.*; |
14 | 11 | ||
@@ -98,7 +95,7 @@ public class VersionedMapStoreImpl<K, V> implements VersionedMapStore<K, V> { | |||
98 | } else { | 95 | } else { |
99 | ArrayList<Long> existingKeys = new ArrayList<>(states.keySet()); | 96 | ArrayList<Long> existingKeys = new ArrayList<>(states.keySet()); |
100 | Collections.sort(existingKeys); | 97 | Collections.sort(existingKeys); |
101 | throw new IllegalArgumentException("Store does not contain state " + state + "! Avaliable states: " | 98 | throw new IllegalArgumentException("Store does not contain state " + state + "! Available states: " |
102 | + Arrays.toString(existingKeys.toArray())); | 99 | + Arrays.toString(existingKeys.toArray())); |
103 | } | 100 | } |
104 | } | 101 | } |
@@ -123,10 +120,10 @@ public class VersionedMapStoreImpl<K, V> implements VersionedMapStore<K, V> { | |||
123 | 120 | ||
124 | @Override | 121 | @Override |
125 | public DiffCursor<K, V> getDiffCursor(long fromState, long toState) { | 122 | public DiffCursor<K, V> getDiffCursor(long fromState, long toState) { |
126 | VersionedMap<K, V> map1 = createMap(fromState); | 123 | VersionedMapImpl<K, V> map1 = (VersionedMapImpl<K, V>) createMap(fromState); |
127 | VersionedMap<K, V> map2 = createMap(toState); | 124 | VersionedMapImpl<K, V> map2 = (VersionedMapImpl<K, V>) createMap(toState); |
128 | Cursor<K, V> cursor1 = map1.getAll(); | 125 | InOrderMapCursor<K, V> cursor1 = new InOrderMapCursor<>(map1); |
129 | Cursor<K, V> cursor2 = map2.getAll(); | 126 | InOrderMapCursor<K, V> cursor2 = new InOrderMapCursor<>(map2); |
130 | return new MapDiffCursor<>(this.hashProvider, this.defaultValue, cursor1, cursor2); | 127 | return new MapDiffCursor<>(this.defaultValue, cursor1, cursor2); |
131 | } | 128 | } |
132 | } | 129 | } |
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 new file mode 100644 index 00000000..fe490f46 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaBasedVersionedMapStoreFactory.java | |||
@@ -0,0 +1,39 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.internal; | ||
7 | |||
8 | import tools.refinery.store.map.VersionedMapStore; | ||
9 | import tools.refinery.store.map.VersionedMapStoreDeltaImpl; | ||
10 | import tools.refinery.store.map.VersionedMapStoreFactory; | ||
11 | import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; | ||
12 | |||
13 | import java.util.ArrayList; | ||
14 | import java.util.List; | ||
15 | |||
16 | public class DeltaBasedVersionedMapStoreFactory<K, V> implements VersionedMapStoreFactory<K, V> { | ||
17 | private final V defaultValue; | ||
18 | private final boolean summarizeChanges; | ||
19 | |||
20 | public DeltaBasedVersionedMapStoreFactory(V defaultValue, | ||
21 | VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy deltaTransactionStrategy) { | ||
22 | this.defaultValue = defaultValue; | ||
23 | this.summarizeChanges = deltaTransactionStrategy == VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy.SET; | ||
24 | } | ||
25 | |||
26 | @Override | ||
27 | public VersionedMapStore<K, V> createOne() { | ||
28 | return new VersionedMapStoreDeltaImpl<>(summarizeChanges, defaultValue); | ||
29 | } | ||
30 | |||
31 | @Override | ||
32 | public List<VersionedMapStore<K, V>> createGroup(int amount) { | ||
33 | List<VersionedMapStore<K, V>> result = new ArrayList<>(amount); | ||
34 | for(int i=0; i<amount; i++) { | ||
35 | result.add(new VersionedMapStoreDeltaImpl<>(summarizeChanges,defaultValue)); | ||
36 | } | ||
37 | return result; | ||
38 | } | ||
39 | } | ||
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java new file mode 100644 index 00000000..cc9003e3 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/DeltaDiffCursor.java | |||
@@ -0,0 +1,147 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.internal; | ||
7 | |||
8 | import tools.refinery.store.map.AnyVersionedMap; | ||
9 | import tools.refinery.store.map.DiffCursor; | ||
10 | |||
11 | import java.util.Collections; | ||
12 | import java.util.List; | ||
13 | import java.util.Set; | ||
14 | |||
15 | public class DeltaDiffCursor<K, V> implements DiffCursor<K, V> { | ||
16 | final List<MapDelta<K, V>[]> backwardTransactions; | ||
17 | final List<MapDelta<K, V>[]> forwardTransactions; | ||
18 | |||
19 | boolean started; | ||
20 | /** | ||
21 | * Denotes the direction of traversal. False means backwards, true means | ||
22 | * forward. | ||
23 | */ | ||
24 | boolean direction; | ||
25 | int listIndex; | ||
26 | int arrayIndex; | ||
27 | |||
28 | public DeltaDiffCursor(List<MapDelta<K, V>[]> backwardTransactions, List<MapDelta<K, V>[]> forwardTransactions) { | ||
29 | this.backwardTransactions = backwardTransactions; | ||
30 | this.forwardTransactions = forwardTransactions; | ||
31 | |||
32 | if (!backwardTransactions.isEmpty()) { | ||
33 | direction = false; | ||
34 | listIndex = 0; | ||
35 | arrayIndex = backwardTransactions.get(listIndex).length - 1; | ||
36 | } else if (!forwardTransactions.isEmpty()) { | ||
37 | direction = true; | ||
38 | listIndex = forwardTransactions.size() - 1; | ||
39 | arrayIndex = 0; | ||
40 | } else { | ||
41 | direction = true; | ||
42 | listIndex = -1; | ||
43 | } | ||
44 | started = false; | ||
45 | } | ||
46 | |||
47 | protected MapDelta<K, V> getCurrentDelta() { | ||
48 | final List<MapDelta<K, V>[]> list; | ||
49 | if (!direction) { | ||
50 | list = this.backwardTransactions; | ||
51 | } else { | ||
52 | list = this.forwardTransactions; | ||
53 | } | ||
54 | return list.get(listIndex)[arrayIndex]; | ||
55 | } | ||
56 | |||
57 | @Override | ||
58 | public K getKey() { | ||
59 | return getCurrentDelta().getKey(); | ||
60 | } | ||
61 | |||
62 | @Override | ||
63 | public V getValue() { | ||
64 | return getToValue(); | ||
65 | } | ||
66 | |||
67 | @Override | ||
68 | public boolean isTerminated() { | ||
69 | return this.direction && listIndex == -1; | ||
70 | } | ||
71 | |||
72 | |||
73 | @Override | ||
74 | public boolean move() { | ||
75 | if(!started) { | ||
76 | started = true; | ||
77 | return !isTerminated(); | ||
78 | } else if (isTerminated()) { | ||
79 | return false; | ||
80 | } else { | ||
81 | if (this.direction) { | ||
82 | if (arrayIndex+1 < forwardTransactions.get(listIndex).length) { | ||
83 | arrayIndex++; | ||
84 | return true; | ||
85 | } else { | ||
86 | if (listIndex-1 >= 0) { | ||
87 | listIndex--; | ||
88 | arrayIndex = 0; | ||
89 | return true; | ||
90 | } else { | ||
91 | listIndex = -1; | ||
92 | return false; | ||
93 | } | ||
94 | } | ||
95 | } else { | ||
96 | if (arrayIndex > 0) { | ||
97 | arrayIndex--; | ||
98 | return true; | ||
99 | } else { | ||
100 | if (listIndex+1 < backwardTransactions.size()) { | ||
101 | listIndex++; | ||
102 | this.arrayIndex = backwardTransactions.get(listIndex).length - 1; | ||
103 | return true; | ||
104 | } else { | ||
105 | this.direction = true; | ||
106 | if (!this.forwardTransactions.isEmpty()) { | ||
107 | listIndex = forwardTransactions.size() - 1; | ||
108 | arrayIndex = 0; | ||
109 | return true; | ||
110 | } else { | ||
111 | listIndex = -1; | ||
112 | return false; | ||
113 | } | ||
114 | } | ||
115 | } | ||
116 | } | ||
117 | } | ||
118 | } | ||
119 | |||
120 | @Override | ||
121 | public boolean isDirty() { | ||
122 | return false; | ||
123 | } | ||
124 | |||
125 | @Override | ||
126 | public Set<AnyVersionedMap> getDependingMaps() { | ||
127 | return Collections.emptySet(); | ||
128 | } | ||
129 | |||
130 | @Override | ||
131 | public V getFromValue() { | ||
132 | if(this.direction) { | ||
133 | return getCurrentDelta().getOldValue(); | ||
134 | } else { | ||
135 | return getCurrentDelta().getNewValue(); | ||
136 | } | ||
137 | } | ||
138 | |||
139 | @Override | ||
140 | public V getToValue() { | ||
141 | if(this.direction) { | ||
142 | return getCurrentDelta().getNewValue(); | ||
143 | } else { | ||
144 | return getCurrentDelta().getOldValue(); | ||
145 | } | ||
146 | } | ||
147 | } | ||
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 index 61b3d1b8..a357fbce 100644 --- 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 | |||
@@ -10,12 +10,12 @@ enum HashClash { | |||
10 | * Not stuck. | 10 | * Not stuck. |
11 | */ | 11 | */ |
12 | NONE, | 12 | NONE, |
13 | 13 | ||
14 | /** | 14 | /** |
15 | * Clashed, next we should return the key of cursor 1. | 15 | * Clashed, next we should return the key of cursor 1. |
16 | */ | 16 | */ |
17 | STUCK_CURSOR_1, | 17 | STUCK_CURSOR_1, |
18 | 18 | ||
19 | /** | 19 | /** |
20 | * Clashed, next we should return the key of cursor 2. | 20 | * Clashed, next we should return the key of cursor 2. |
21 | */ | 21 | */ |
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 index 03dffc15..d052318f 100644 --- 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 | |||
@@ -20,7 +20,7 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
20 | */ | 20 | */ |
21 | final int nodeMap; | 21 | final int nodeMap; |
22 | /** | 22 | /** |
23 | * Stores Keys, Values, and subnodes. Structure: (K,V)*,NODE; NODES are stored | 23 | * Stores Keys, Values, and sub-nodes. Structure: (K,V)*,NODE; NODES are stored |
24 | * backwards. | 24 | * backwards. |
25 | */ | 25 | */ |
26 | final Object[] content; | 26 | final Object[] content; |
@@ -47,8 +47,7 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
47 | * available. | 47 | * available. |
48 | * @return an immutable version of the input node. | 48 | * @return an immutable version of the input node. |
49 | */ | 49 | */ |
50 | static <K, V> ImmutableNode<K, V> constructImmutable(MutableNode<K, V> node, | 50 | static <K, V> ImmutableNode<K, V> constructImmutable(MutableNode<K, V> node, Map<Node<K, V>, ImmutableNode<K, V>> cache) { |
51 | Map<Node<K, V>, ImmutableNode<K, V>> cache) { | ||
52 | // 1. try to return from cache | 51 | // 1. try to return from cache |
53 | if (cache != null) { | 52 | if (cache != null) { |
54 | ImmutableNode<K, V> cachedResult = cache.get(node); | 53 | ImmutableNode<K, V> cachedResult = cache.get(node); |
@@ -71,25 +70,24 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
71 | int resultDataMap = 0; | 70 | int resultDataMap = 0; |
72 | int resultNodeMap = 0; | 71 | int resultNodeMap = 0; |
73 | final Object[] resultContent = new Object[size]; | 72 | final Object[] resultContent = new Object[size]; |
74 | int bitposition = 1; | 73 | int bitPosition = 1; |
75 | for (int i = 0; i < FACTOR; i++) { | 74 | for (int i = 0; i < FACTOR; i++) { |
76 | Object key = node.content[i * 2]; | 75 | Object key = node.content[i * 2]; |
77 | if (key != null) { | 76 | if (key != null) { |
78 | resultDataMap |= bitposition; | 77 | resultDataMap |= bitPosition; |
79 | resultContent[datas * 2] = key; | 78 | resultContent[datas * 2] = key; |
80 | resultContent[datas * 2 + 1] = node.content[i * 2 + 1]; | 79 | resultContent[datas * 2 + 1] = node.content[i * 2 + 1]; |
81 | datas++; | 80 | datas++; |
82 | } else { | 81 | } else { |
83 | @SuppressWarnings("unchecked") | 82 | @SuppressWarnings("unchecked") var subnode = (Node<K, V>) node.content[i * 2 + 1]; |
84 | var subnode = (Node<K, V>) node.content[i * 2 + 1]; | ||
85 | if (subnode != null) { | 83 | if (subnode != null) { |
86 | ImmutableNode<K, V> immutableSubnode = subnode.toImmutable(cache); | 84 | ImmutableNode<K, V> immutableSubNode = subnode.toImmutable(cache); |
87 | resultNodeMap |= bitposition; | 85 | resultNodeMap |= bitPosition; |
88 | resultContent[size - 1 - nodes] = immutableSubnode; | 86 | resultContent[size - 1 - nodes] = immutableSubNode; |
89 | nodes++; | 87 | nodes++; |
90 | } | 88 | } |
91 | } | 89 | } |
92 | bitposition <<= 1; | 90 | bitPosition <<= 1; |
93 | } | 91 | } |
94 | final int resultHash = node.hashCode(); | 92 | final int resultHash = node.hashCode(); |
95 | var newImmutable = new ImmutableNode<K, V>(resultDataMap, resultNodeMap, resultContent, resultHash); | 93 | var newImmutable = new ImmutableNode<K, V>(resultDataMap, resultNodeMap, resultContent, resultHash); |
@@ -112,11 +110,9 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
112 | // If the key is stored as a data | 110 | // If the key is stored as a data |
113 | if ((dataMap & bitposition) != 0) { | 111 | if ((dataMap & bitposition) != 0) { |
114 | int keyIndex = 2 * index(dataMap, bitposition); | 112 | int keyIndex = 2 * index(dataMap, bitposition); |
115 | @SuppressWarnings("unchecked") | 113 | @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; |
116 | K keyCandidate = (K) content[keyIndex]; | ||
117 | if (keyCandidate.equals(key)) { | 114 | if (keyCandidate.equals(key)) { |
118 | @SuppressWarnings("unchecked") | 115 | @SuppressWarnings("unchecked") V value = (V) content[keyIndex + 1]; |
119 | V value = (V) content[keyIndex + 1]; | ||
120 | return value; | 116 | return value; |
121 | } else { | 117 | } else { |
122 | return defaultValue; | 118 | return defaultValue; |
@@ -125,9 +121,8 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
125 | // the key is stored as a node | 121 | // the key is stored as a node |
126 | else if ((nodeMap & bitposition) != 0) { | 122 | else if ((nodeMap & bitposition) != 0) { |
127 | int keyIndex = content.length - 1 - index(nodeMap, bitposition); | 123 | int keyIndex = content.length - 1 - index(nodeMap, bitposition); |
128 | @SuppressWarnings("unchecked") | 124 | @SuppressWarnings("unchecked") var subNode = (ImmutableNode<K, V>) content[keyIndex]; |
129 | var subNode = (ImmutableNode<K, V>) content[keyIndex]; | 125 | int newDepth = incrementDepth(depth); |
130 | int newDepth = depth + 1; | ||
131 | int newHash = newHash(hashProvider, key, hash, newDepth); | 126 | int newHash = newHash(hashProvider, key, hash, newDepth); |
132 | return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); | 127 | return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); |
133 | } | 128 | } |
@@ -138,14 +133,12 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
138 | } | 133 | } |
139 | 134 | ||
140 | @Override | 135 | @Override |
141 | public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, | 136 | public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { |
142 | V defaultValue, int hash, int depth) { | ||
143 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); | 137 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); |
144 | int bitposition = 1 << selectedHashFragment; | 138 | int bitPosition = 1 << selectedHashFragment; |
145 | if ((dataMap & bitposition) != 0) { | 139 | if ((dataMap & bitPosition) != 0) { |
146 | int keyIndex = 2 * index(dataMap, bitposition); | 140 | int keyIndex = 2 * index(dataMap, bitPosition); |
147 | @SuppressWarnings("unchecked") | 141 | @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; |
148 | K keyCandidate = (K) content[keyIndex]; | ||
149 | if (keyCandidate.equals(key)) { | 142 | if (keyCandidate.equals(key)) { |
150 | if (value == defaultValue) { | 143 | if (value == defaultValue) { |
151 | // delete | 144 | // delete |
@@ -156,7 +149,7 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
156 | oldValue.setOldValue(value); | 149 | oldValue.setOldValue(value); |
157 | return this; | 150 | return this; |
158 | } else { | 151 | } else { |
159 | // update existing nodeId | 152 | // update existing value |
160 | MutableNode<K, V> mutable = this.toMutable(); | 153 | MutableNode<K, V> mutable = this.toMutable(); |
161 | return mutable.updateValue(value, oldValue, selectedHashFragment); | 154 | return mutable.updateValue(value, oldValue, selectedHashFragment); |
162 | } | 155 | } |
@@ -166,16 +159,15 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
166 | oldValue.setOldValue(defaultValue); | 159 | oldValue.setOldValue(defaultValue); |
167 | return this; | 160 | return this; |
168 | } else { | 161 | } else { |
169 | // add new key + nodeId | 162 | // add new key + value |
170 | MutableNode<K, V> mutable = this.toMutable(); | 163 | MutableNode<K, V> mutable = this.toMutable(); |
171 | return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); | 164 | return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); |
172 | } | 165 | } |
173 | } | 166 | } |
174 | } else if ((nodeMap & bitposition) != 0) { | 167 | } else if ((nodeMap & bitPosition) != 0) { |
175 | int keyIndex = content.length - 1 - index(nodeMap, bitposition); | 168 | int keyIndex = content.length - 1 - index(nodeMap, bitPosition); |
176 | @SuppressWarnings("unchecked") | 169 | @SuppressWarnings("unchecked") var subNode = (ImmutableNode<K, V>) content[keyIndex]; |
177 | var subNode = (ImmutableNode<K, V>) content[keyIndex]; | 170 | int newDepth = incrementDepth(depth); |
178 | int newDepth = depth + 1; | ||
179 | int newHash = newHash(hashProvider, key, hash, newDepth); | 171 | int newHash = newHash(hashProvider, key, hash, newDepth); |
180 | var newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth); | 172 | var newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth); |
181 | 173 | ||
@@ -184,10 +176,11 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
184 | return this; | 176 | return this; |
185 | } else { | 177 | } else { |
186 | MutableNode<K, V> mutable = toMutable(); | 178 | MutableNode<K, V> mutable = toMutable(); |
187 | return mutable.updateWithSubNode(selectedHashFragment, newsubNode, value.equals(defaultValue)); | 179 | return mutable.updateWithSubNode(selectedHashFragment, newsubNode, |
180 | (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); | ||
188 | } | 181 | } |
189 | } else { | 182 | } else { |
190 | // add new key + nodeId | 183 | // add new key + value |
191 | MutableNode<K, V> mutable = this.toMutable(); | 184 | MutableNode<K, V> mutable = this.toMutable(); |
192 | return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); | 185 | return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); |
193 | } | 186 | } |
@@ -197,8 +190,7 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
197 | public long getSize() { | 190 | public long getSize() { |
198 | int result = Integer.bitCount(this.dataMap); | 191 | int result = Integer.bitCount(this.dataMap); |
199 | for (int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) { | 192 | for (int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) { |
200 | @SuppressWarnings("unchecked") | 193 | @SuppressWarnings("unchecked") var subnode = (ImmutableNode<K, V>) this.content[this.content.length - 1 - subnodeIndex]; |
201 | var subnode = (ImmutableNode<K, V>) this.content[this.content.length - 1 - subnodeIndex]; | ||
202 | result += subnode.getSize(); | 194 | result += subnode.getSize(); |
203 | } | 195 | } |
204 | return result; | 196 | return result; |
@@ -238,6 +230,9 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
238 | 230 | ||
239 | // 2. look inside the subnodes | 231 | // 2. look inside the subnodes |
240 | int nodes = Integer.bitCount(this.nodeMap); | 232 | int nodes = Integer.bitCount(this.nodeMap); |
233 | if(cursor.nodeIndexStack.peek()==null) { | ||
234 | throw new IllegalStateException("Cursor moved to the next state when the state is empty."); | ||
235 | } | ||
241 | int newNodeIndex = cursor.nodeIndexStack.peek() + 1; | 236 | int newNodeIndex = cursor.nodeIndexStack.peek() + 1; |
242 | if (newNodeIndex < nodes) { | 237 | if (newNodeIndex < nodes) { |
243 | // 2.1 found next subnode, move down to the subnode | 238 | // 2.1 found next subnode, move down to the subnode |
@@ -264,10 +259,51 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
264 | } | 259 | } |
265 | 260 | ||
266 | @Override | 261 | @Override |
267 | public void prettyPrint(StringBuilder builder, int depth, int code) { | 262 | @SuppressWarnings("unchecked") |
268 | for (int i = 0; i < depth; i++) { | 263 | boolean moveToNextInorder(InOrderMapCursor<K, V> cursor) { |
269 | builder.append("\t"); | 264 | if(cursor.nodeIndexStack.peek()==null) { |
265 | throw new IllegalStateException("Cursor moved to the next state when the state is empty."); | ||
270 | } | 266 | } |
267 | |||
268 | int position = cursor.nodeIndexStack.peek(); | ||
269 | for (int index = position + 1; index < FACTOR; index++) { | ||
270 | final int mask = 1<<index; | ||
271 | if((this.dataMap & mask) != 0) { | ||
272 | // data found | ||
273 | cursor.nodeIndexStack.pop(); | ||
274 | cursor.nodeIndexStack.push(index); | ||
275 | |||
276 | cursor.key = (K) this.content[2 * index(dataMap, mask)]; | ||
277 | cursor.value = (V) this.content[2 * index(dataMap, mask) +1]; | ||
278 | return true; | ||
279 | } else if((this.nodeMap & mask) != 0) { | ||
280 | // node found | ||
281 | Node<K,V> subnode = (Node<K, V>) this.content[this.content.length - 1 - index(nodeMap, mask)]; | ||
282 | cursor.nodeIndexStack.pop(); | ||
283 | cursor.nodeIndexStack.push(index); | ||
284 | cursor.nodeIndexStack.push(InOrderMapCursor.INDEX_START); | ||
285 | cursor.nodeStack.push(subnode); | ||
286 | |||
287 | return subnode.moveToNextInorder(cursor); | ||
288 | } | ||
289 | } | ||
290 | |||
291 | // nothing found | ||
292 | cursor.nodeStack.pop(); | ||
293 | cursor.nodeIndexStack.pop(); | ||
294 | if (!cursor.nodeStack.isEmpty()) { | ||
295 | Node<K, V> supernode = cursor.nodeStack.peek(); | ||
296 | return supernode.moveToNextInorder(cursor); | ||
297 | } else { | ||
298 | cursor.key = null; | ||
299 | cursor.value = null; | ||
300 | return false; | ||
301 | } | ||
302 | } | ||
303 | |||
304 | @Override | ||
305 | public void prettyPrint(StringBuilder builder, int depth, int code) { | ||
306 | builder.append("\t".repeat(Math.max(0, depth))); | ||
271 | if (code >= 0) { | 307 | if (code >= 0) { |
272 | builder.append(code); | 308 | builder.append(code); |
273 | builder.append(":"); | 309 | builder.append(":"); |
@@ -294,10 +330,9 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
294 | int nodeMask = 1; | 330 | int nodeMask = 1; |
295 | for (int i = 0; i < FACTOR; i++) { | 331 | for (int i = 0; i < FACTOR; i++) { |
296 | if ((nodeMask & nodeMap) != 0) { | 332 | if ((nodeMask & nodeMap) != 0) { |
297 | @SuppressWarnings("unchecked") | 333 | @SuppressWarnings("unchecked") Node<K, V> subNode = (Node<K, V>) content[content.length - 1 - index(nodeMap, nodeMask)]; |
298 | Node<K, V> subNode = (Node<K, V>) content[content.length - 1 - index(nodeMap, nodeMask)]; | ||
299 | builder.append("\n"); | 334 | builder.append("\n"); |
300 | subNode.prettyPrint(builder, depth + 1, i); | 335 | subNode.prettyPrint(builder, incrementDepth(depth), i); |
301 | } | 336 | } |
302 | nodeMask <<= 1; | 337 | nodeMask <<= 1; |
303 | } | 338 | } |
@@ -315,12 +350,11 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
315 | 350 | ||
316 | // check subnodes | 351 | // check subnodes |
317 | for (int i = 0; i < Integer.bitCount(nodeMap); i++) { | 352 | for (int i = 0; i < Integer.bitCount(nodeMap); i++) { |
318 | @SuppressWarnings("unchecked") | 353 | @SuppressWarnings("unchecked") var subnode = (Node<K, V>) this.content[this.content.length - 1 - i]; |
319 | var subnode = (Node<K, V>) this.content[this.content.length - 1 - i]; | ||
320 | if (!(subnode instanceof ImmutableNode<?, ?>)) { | 354 | if (!(subnode instanceof ImmutableNode<?, ?>)) { |
321 | throw new IllegalStateException("Immutable node contains mutable subnodes!"); | 355 | throw new IllegalStateException("Immutable node contains mutable subnodes!"); |
322 | } else { | 356 | } else { |
323 | subnode.checkIntegrity(hashProvider, defaultValue, depth + 1); | 357 | subnode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth)); |
324 | } | 358 | } |
325 | } | 359 | } |
326 | } | 360 | } |
@@ -332,13 +366,10 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
332 | 366 | ||
333 | @Override | 367 | @Override |
334 | public boolean equals(Object obj) { | 368 | public boolean equals(Object obj) { |
335 | if (this == obj) | 369 | if (this == obj) return true; |
336 | return true; | 370 | if (obj == null) return false; |
337 | if (obj == null) | ||
338 | return false; | ||
339 | if (obj instanceof ImmutableNode<?, ?> other) { | 371 | if (obj instanceof ImmutableNode<?, ?> other) { |
340 | return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap | 372 | return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap && Arrays.deepEquals(content, other.content); |
341 | && Arrays.deepEquals(content, other.content); | ||
342 | } else if (obj instanceof MutableNode<?, ?> mutableObj) { | 373 | } else if (obj instanceof MutableNode<?, ?> mutableObj) { |
343 | return ImmutableNode.compareImmutableMutable(this, mutableObj); | 374 | return ImmutableNode.compareImmutableMutable(this, mutableObj); |
344 | } else { | 375 | } else { |
@@ -356,19 +387,17 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
356 | if (key != null) { | 387 | if (key != null) { |
357 | // Check whether a new Key-Value pair can fit into the immutable container | 388 | // Check whether a new Key-Value pair can fit into the immutable container |
358 | if (datas * 2 + nodes + 2 <= immutableLength) { | 389 | if (datas * 2 + nodes + 2 <= immutableLength) { |
359 | if (!immutable.content[datas * 2].equals(key) | 390 | if (!immutable.content[datas * 2].equals(key) || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) { |
360 | || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) { | ||
361 | return false; | 391 | return false; |
362 | } | 392 | } |
363 | } else | 393 | } else return false; |
364 | return false; | ||
365 | datas++; | 394 | datas++; |
366 | } else { | 395 | } else { |
367 | var mutableSubnode = (Node<?, ?>) mutable.content[i * 2 + 1]; | 396 | var mutableSubnode = (Node<?, ?>) mutable.content[i * 2 + 1]; |
368 | if (mutableSubnode != null) { | 397 | if (mutableSubnode != null) { |
369 | if (datas * 2 + nodes + 1 <= immutableLength) { | 398 | if (datas * 2 + nodes + 1 <= immutableLength) { |
370 | Object immutableSubnode = immutable.content[immutableLength - 1 - nodes]; | 399 | Object immutableSubNode = immutable.content[immutableLength - 1 - nodes]; |
371 | if (!mutableSubnode.equals(immutableSubnode)) { | 400 | if (!mutableSubnode.equals(immutableSubNode)) { |
372 | return false; | 401 | return false; |
373 | } | 402 | } |
374 | nodes++; | 403 | nodes++; |
@@ -378,6 +407,7 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
378 | } | 407 | } |
379 | } | 408 | } |
380 | } | 409 | } |
381 | return true; | 410 | |
411 | return datas * 2 + nodes == immutable.content.length; | ||
382 | } | 412 | } |
383 | } | 413 | } |
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 new file mode 100644 index 00000000..cb3f366f --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java | |||
@@ -0,0 +1,146 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.internal; | ||
7 | |||
8 | import tools.refinery.store.map.AnyVersionedMap; | ||
9 | import tools.refinery.store.map.ContentHashCode; | ||
10 | import tools.refinery.store.map.Cursor; | ||
11 | import tools.refinery.store.map.VersionedMap; | ||
12 | |||
13 | import java.util.*; | ||
14 | |||
15 | public class InOrderMapCursor<K, V> implements Cursor<K, V> { | ||
16 | // Constants | ||
17 | static final int INDEX_START = -1; | ||
18 | |||
19 | // Tree stack | ||
20 | ArrayDeque<Node<K, V>> nodeStack; | ||
21 | ArrayDeque<Integer> nodeIndexStack; | ||
22 | |||
23 | |||
24 | // Values | ||
25 | K key; | ||
26 | V value; | ||
27 | |||
28 | // Hash code for checking concurrent modifications | ||
29 | final VersionedMap<K, V> map; | ||
30 | final int creationHash; | ||
31 | |||
32 | public InOrderMapCursor(VersionedMapImpl<K, V> map) { | ||
33 | // Initializing tree stack | ||
34 | super(); | ||
35 | this.nodeStack = new ArrayDeque<>(); | ||
36 | this.nodeIndexStack = new ArrayDeque<>(); | ||
37 | if (map.root != null) { | ||
38 | this.nodeStack.add(map.root); | ||
39 | this.nodeIndexStack.push(INDEX_START); | ||
40 | } | ||
41 | |||
42 | // Initializing cache | ||
43 | this.key = null; | ||
44 | this.value = null; | ||
45 | |||
46 | // Initializing state | ||
47 | this.map = map; | ||
48 | this.creationHash = map.contentHashCode(ContentHashCode.APPROXIMATE_FAST); | ||
49 | } | ||
50 | |||
51 | public K getKey() { | ||
52 | return key; | ||
53 | } | ||
54 | |||
55 | public V getValue() { | ||
56 | return value; | ||
57 | } | ||
58 | |||
59 | public boolean isTerminated() { | ||
60 | return this.nodeStack.isEmpty(); | ||
61 | } | ||
62 | |||
63 | public boolean move() { | ||
64 | if (isDirty()) { | ||
65 | throw new ConcurrentModificationException(); | ||
66 | } | ||
67 | if (!isTerminated()) { | ||
68 | var node = this.nodeStack.peek(); | ||
69 | if (node == null) { | ||
70 | throw new IllegalStateException("Cursor is not terminated but the current node is missing"); | ||
71 | } | ||
72 | boolean result = node.moveToNextInorder(this); | ||
73 | if (this.nodeIndexStack.size() != this.nodeStack.size()) { | ||
74 | throw new IllegalArgumentException("Node stack is corrupted by illegal moves!"); | ||
75 | } | ||
76 | return result; | ||
77 | } | ||
78 | return false; | ||
79 | } | ||
80 | |||
81 | public boolean skipCurrentNode() { | ||
82 | nodeStack.pop(); | ||
83 | nodeIndexStack.pop(); | ||
84 | return move(); | ||
85 | } | ||
86 | |||
87 | @Override | ||
88 | public boolean isDirty() { | ||
89 | return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; | ||
90 | } | ||
91 | |||
92 | @Override | ||
93 | public Set<AnyVersionedMap> getDependingMaps() { | ||
94 | return Set.of(this.map); | ||
95 | } | ||
96 | |||
97 | public static <K, V> boolean sameSubNode(InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) { | ||
98 | Node<K, V> nodeOfCursor1 = cursor1.nodeStack.peek(); | ||
99 | Node<K, V> nodeOfCursor2 = cursor2.nodeStack.peek(); | ||
100 | return Objects.equals(nodeOfCursor1, nodeOfCursor2); | ||
101 | } | ||
102 | |||
103 | /** | ||
104 | * Compares the state of two cursors started on two {@link VersionedMap} of the same | ||
105 | * {@link tools.refinery.store.map.VersionedMapStore}. | ||
106 | * @param <K> Key type | ||
107 | * @param <V> Value type | ||
108 | * @param cursor1 first cursor | ||
109 | * @param cursor2 second cursor | ||
110 | * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the | ||
111 | * same position. | ||
112 | */ | ||
113 | public static <K, V> int comparePosition(InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) { | ||
114 | // If the state does not determine the order, then compare @nodeIndexStack. | ||
115 | Iterator<Integer> nodeIndexStack1 = cursor1.nodeIndexStack.descendingIterator(); | ||
116 | Iterator<Integer> nodeIndexStack2 = cursor2.nodeIndexStack.descendingIterator(); | ||
117 | |||
118 | while(nodeIndexStack1.hasNext() && nodeIndexStack2.hasNext()){ | ||
119 | final int index1 = nodeIndexStack1.next(); | ||
120 | final int index2 = nodeIndexStack2.next(); | ||
121 | if(index1 < index2) { | ||
122 | return 1; | ||
123 | } else if(index1 > index2) { | ||
124 | return -1; | ||
125 | } | ||
126 | } | ||
127 | |||
128 | return 0; | ||
129 | } | ||
130 | |||
131 | /** | ||
132 | * Compares the depth of two cursors started on @{@link VersionedMap} of the same | ||
133 | * {@link tools.refinery.store.map.VersionedMapStore}. | ||
134 | * @param <K> Key type | ||
135 | * @param <V> Value type | ||
136 | * @param cursor1 first cursor | ||
137 | * @param cursor2 second cursor | ||
138 | * @return Positive number if cursor 1 is deeper, negative number if cursor 2 is deeper, and 0 if they are at the | ||
139 | * same depth. | ||
140 | */ | ||
141 | public static <K, V> int compareDepth(InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) { | ||
142 | int d1 = cursor1.nodeIndexStack.size(); | ||
143 | int d2 = cursor2.nodeIndexStack.size(); | ||
144 | return Integer.compare(d1, d2); | ||
145 | } | ||
146 | } | ||
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java new file mode 100644 index 00000000..d1ab8bb1 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/IteratorAsCursor.java | |||
@@ -0,0 +1,66 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.internal; | ||
7 | |||
8 | import java.util.*; | ||
9 | import java.util.Map.Entry; | ||
10 | |||
11 | import tools.refinery.store.map.AnyVersionedMap; | ||
12 | import tools.refinery.store.map.Cursor; | ||
13 | import tools.refinery.store.map.VersionedMap; | ||
14 | |||
15 | public class IteratorAsCursor<K, V> implements Cursor<K, V> { | ||
16 | final Iterator<Entry<K, V>> iterator; | ||
17 | final VersionedMap<K, V> source; | ||
18 | |||
19 | private boolean terminated; | ||
20 | private K key; | ||
21 | private V value; | ||
22 | |||
23 | public IteratorAsCursor(VersionedMap<K, V> source, Map<K, V> current) { | ||
24 | this.iterator = current.entrySet().iterator(); | ||
25 | this.source = source; | ||
26 | } | ||
27 | |||
28 | @Override | ||
29 | public K getKey() { | ||
30 | return key; | ||
31 | } | ||
32 | |||
33 | @Override | ||
34 | public V getValue() { | ||
35 | return value; | ||
36 | } | ||
37 | |||
38 | @Override | ||
39 | public boolean isTerminated() { | ||
40 | return terminated; | ||
41 | } | ||
42 | |||
43 | @Override | ||
44 | public boolean move() { | ||
45 | terminated = !iterator.hasNext(); | ||
46 | if (terminated) { | ||
47 | this.key = null; | ||
48 | this.value = null; | ||
49 | } else { | ||
50 | Entry<K, V> next = iterator.next(); | ||
51 | this.key = next.getKey(); | ||
52 | this.value = next.getValue(); | ||
53 | } | ||
54 | return !terminated; | ||
55 | } | ||
56 | |||
57 | @Override | ||
58 | public boolean isDirty() { | ||
59 | return false; | ||
60 | } | ||
61 | |||
62 | @Override | ||
63 | public Set<AnyVersionedMap> getDependingMaps() { | ||
64 | return Set.of(this.source); | ||
65 | } | ||
66 | } | ||
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 index f34ec7bb..d42519b2 100644 --- 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 | |||
@@ -12,7 +12,6 @@ import tools.refinery.store.map.VersionedMap; | |||
12 | 12 | ||
13 | import java.util.ArrayDeque; | 13 | import java.util.ArrayDeque; |
14 | import java.util.ConcurrentModificationException; | 14 | import java.util.ConcurrentModificationException; |
15 | import java.util.Iterator; | ||
16 | import java.util.Set; | 15 | import java.util.Set; |
17 | 16 | ||
18 | public class MapCursor<K, V> implements Cursor<K, V> { | 17 | public class MapCursor<K, V> implements Cursor<K, V> { |
@@ -84,13 +83,6 @@ public class MapCursor<K, V> implements Cursor<K, V> { | |||
84 | return false; | 83 | return false; |
85 | } | 84 | } |
86 | 85 | ||
87 | public boolean skipCurrentNode() { | ||
88 | nodeStack.pop(); | ||
89 | nodeIndexStack.pop(); | ||
90 | dataIndex = INDEX_FINISH; | ||
91 | return move(); | ||
92 | } | ||
93 | |||
94 | @Override | 86 | @Override |
95 | public boolean isDirty() { | 87 | public boolean isDirty() { |
96 | return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; | 88 | return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; |
@@ -100,46 +92,4 @@ public class MapCursor<K, V> implements Cursor<K, V> { | |||
100 | public Set<AnyVersionedMap> getDependingMaps() { | 92 | public Set<AnyVersionedMap> getDependingMaps() { |
101 | return Set.of(this.map); | 93 | return Set.of(this.map); |
102 | } | 94 | } |
103 | |||
104 | public static <K, V> boolean sameSubnode(MapCursor<K, V> cursor1, MapCursor<K, V> cursor2) { | ||
105 | Node<K, V> nodeOfCursor1 = cursor1.nodeStack.peek(); | ||
106 | Node<K, V> nodeOfCursor2 = cursor2.nodeStack.peek(); | ||
107 | if (nodeOfCursor1 != null && nodeOfCursor2 != null) { | ||
108 | return nodeOfCursor1.equals(nodeOfCursor2); | ||
109 | } else { | ||
110 | return false; | ||
111 | } | ||
112 | } | ||
113 | |||
114 | /** | ||
115 | * @param <K> | ||
116 | * @param <V> | ||
117 | * @param cursor1 | ||
118 | * @param cursor2 | ||
119 | * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the | ||
120 | * same position. | ||
121 | */ | ||
122 | public static <K, V> int compare(MapCursor<K, V> cursor1, MapCursor<K, V> cursor2) { | ||
123 | // two cursors are equally deep | ||
124 | Iterator<Integer> stack1 = cursor1.nodeIndexStack.descendingIterator(); | ||
125 | Iterator<Integer> stack2 = cursor2.nodeIndexStack.descendingIterator(); | ||
126 | if (stack1.hasNext()) { | ||
127 | if (!stack2.hasNext()) { | ||
128 | // stack 2 has no more element, thus stack 1 is deeper | ||
129 | return 1; | ||
130 | } | ||
131 | int val1 = stack1.next(); | ||
132 | int val2 = stack2.next(); | ||
133 | if (val1 < val2) { | ||
134 | return -1; | ||
135 | } else if (val2 < val1) { | ||
136 | return 1; | ||
137 | } | ||
138 | } | ||
139 | if (stack2.hasNext()) { | ||
140 | // stack 2 has more element, thus stack 2 is deeper | ||
141 | return 1; | ||
142 | } | ||
143 | return Integer.compare(cursor1.dataIndex, cursor2.dataIndex); | ||
144 | } | ||
145 | } | 95 | } |
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java new file mode 100644 index 00000000..2674236c --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapDelta.java | |||
@@ -0,0 +1,20 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.internal; | ||
7 | |||
8 | public record MapDelta<K, V>(K key, V oldValue, V newValue) { | ||
9 | public K getKey() { | ||
10 | return key; | ||
11 | } | ||
12 | |||
13 | public V getOldValue() { | ||
14 | return oldValue; | ||
15 | } | ||
16 | |||
17 | public V getNewValue() { | ||
18 | return newValue; | ||
19 | } | ||
20 | } | ||
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 index d31f1a05..fb1d5d2b 100644 --- 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 | |||
@@ -6,10 +6,10 @@ | |||
6 | package tools.refinery.store.map.internal; | 6 | package tools.refinery.store.map.internal; |
7 | 7 | ||
8 | import tools.refinery.store.map.AnyVersionedMap; | 8 | import tools.refinery.store.map.AnyVersionedMap; |
9 | import tools.refinery.store.map.ContinousHashProvider; | ||
10 | import tools.refinery.store.map.Cursor; | 9 | import tools.refinery.store.map.Cursor; |
11 | import tools.refinery.store.map.DiffCursor; | 10 | import tools.refinery.store.map.DiffCursor; |
12 | 11 | ||
12 | import java.util.Objects; | ||
13 | import java.util.Set; | 13 | import java.util.Set; |
14 | import java.util.stream.Collectors; | 14 | import java.util.stream.Collectors; |
15 | import java.util.stream.Stream; | 15 | import java.util.stream.Stream; |
@@ -18,37 +18,78 @@ import java.util.stream.Stream; | |||
18 | * A cursor representing the difference between two states of a map. | 18 | * A cursor representing the difference between two states of a map. |
19 | * | 19 | * |
20 | * @author Oszkar Semerath | 20 | * @author Oszkar Semerath |
21 | * | ||
22 | */ | 21 | */ |
23 | public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> { | 22 | public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> { |
23 | private enum State { | ||
24 | /** | ||
25 | * initialized state. | ||
26 | */ | ||
27 | INIT, | ||
28 | /** | ||
29 | * Unstable state. | ||
30 | */ | ||
31 | MOVING_MOVING_SAME_KEY_SAME_VALUE, | ||
32 | /** | ||
33 | * Both cursors are moving, and they are on the same sub-node. | ||
34 | */ | ||
35 | MOVING_MOVING_SAME_NODE, | ||
36 | /** | ||
37 | * Both cursors are moving, cursor 1 is behind. | ||
38 | */ | ||
39 | MOVING_MOVING_BEHIND1, | ||
40 | /** | ||
41 | * Both cursors are moving, cursor 2 is behind. | ||
42 | */ | ||
43 | MOVING_MOVING_BEHIND2, | ||
44 | /** | ||
45 | * Both cursors are moving, cursor 1 is on the same key as cursor 2, values are different | ||
46 | */ | ||
47 | MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE, | ||
48 | /** | ||
49 | * Cursor 1 is moving, Cursor 2 is terminated. | ||
50 | */ | ||
51 | MOVING_TERMINATED, | ||
52 | /** | ||
53 | * Cursor 1 is terminated , Cursor 2 is moving. | ||
54 | */ | ||
55 | TERMINATED_MOVING, | ||
56 | /** | ||
57 | * Both cursors are terminated. | ||
58 | */ | ||
59 | TERMINATED_TERMINATED, | ||
60 | /** | ||
61 | * Both Cursors are moving, and they are on an incomparable position. | ||
62 | * It is resolved by showing Cursor 1. | ||
63 | */ | ||
64 | MOVING_MOVING_HASH1, | ||
65 | /** | ||
66 | * Both Cursors are moving, and they are on an incomparable position. | ||
67 | * It is resolved by showing Cursor 2. | ||
68 | */ | ||
69 | MOVING_MOVING_HASH2 | ||
70 | } | ||
71 | |||
24 | /** | 72 | /** |
25 | * Default nodeId representing missing elements. | 73 | * Default nodeId representing missing elements. |
26 | */ | 74 | */ |
27 | private final V defaultValue; | 75 | private final V defaultValue; |
28 | private final MapCursor<K, V> cursor1; | 76 | private final InOrderMapCursor<K, V> cursor1; |
29 | private final MapCursor<K, V> cursor2; | 77 | private final InOrderMapCursor<K, V> cursor2; |
30 | private final ContinousHashProvider<? super K> hashProvider; | 78 | |
79 | // State | ||
80 | State state = State.INIT; | ||
31 | 81 | ||
32 | // Values | 82 | // Values |
33 | private K key; | 83 | private K key; |
34 | private V fromValue; | 84 | private V fromValue; |
35 | private V toValue; | 85 | private V toValue; |
36 | 86 | ||
37 | // State | ||
38 | /** | ||
39 | * Positive number if cursor 1 is behind, negative number if cursor 2 is behind, | ||
40 | * and 0 if they are at the same position. | ||
41 | */ | ||
42 | private int cursorRelation; | ||
43 | private HashClash hashClash = HashClash.NONE; | ||
44 | 87 | ||
45 | public MapDiffCursor(ContinousHashProvider<? super K> hashProvider, V defaultValue, Cursor<K, V> cursor1, | 88 | public MapDiffCursor(V defaultValue, InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) { |
46 | Cursor<K, V> cursor2) { | ||
47 | super(); | 89 | super(); |
48 | this.hashProvider = hashProvider; | ||
49 | this.defaultValue = defaultValue; | 90 | this.defaultValue = defaultValue; |
50 | this.cursor1 = (MapCursor<K, V>) cursor1; | 91 | this.cursor1 = cursor1; |
51 | this.cursor2 = (MapCursor<K, V>) cursor2; | 92 | this.cursor2 = cursor2; |
52 | } | 93 | } |
53 | 94 | ||
54 | @Override | 95 | @Override |
@@ -72,7 +113,7 @@ public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> { | |||
72 | } | 113 | } |
73 | 114 | ||
74 | public boolean isTerminated() { | 115 | public boolean isTerminated() { |
75 | return cursor1.isTerminated() && cursor2.isTerminated(); | 116 | return this.state == State.TERMINATED_TERMINATED; |
76 | } | 117 | } |
77 | 118 | ||
78 | @Override | 119 | @Override |
@@ -82,148 +123,142 @@ public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> { | |||
82 | 123 | ||
83 | @Override | 124 | @Override |
84 | public Set<AnyVersionedMap> getDependingMaps() { | 125 | public Set<AnyVersionedMap> getDependingMaps() { |
85 | return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()) | 126 | return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()).map(AnyVersionedMap.class::cast).collect(Collectors.toUnmodifiableSet()); |
86 | .map(AnyVersionedMap.class::cast) | ||
87 | .collect(Collectors.toUnmodifiableSet()); | ||
88 | } | 127 | } |
89 | 128 | ||
90 | protected void updateState() { | 129 | private boolean isInStableState() { |
91 | if (!isTerminated()) { | 130 | return this.state != State.MOVING_MOVING_SAME_KEY_SAME_VALUE |
92 | this.cursorRelation = MapCursor.compare(cursor1, cursor2); | 131 | && this.state != State.MOVING_MOVING_SAME_NODE && this.state != State.INIT; |
93 | if (cursorRelation > 0 || cursor2.isTerminated()) { | ||
94 | this.key = cursor1.getKey(); | ||
95 | this.fromValue = cursor1.getValue(); | ||
96 | this.toValue = defaultValue; | ||
97 | } else if (cursorRelation < 0 || cursor1.isTerminated()) { | ||
98 | this.key = cursor2.getKey(); | ||
99 | this.fromValue = defaultValue; | ||
100 | this.toValue = cursor1.getValue(); | ||
101 | } else { | ||
102 | // cursor1 = cursor2 | ||
103 | if (cursor1.getKey().equals(cursor2.getKey())) { | ||
104 | this.key = cursor1.getKey(); | ||
105 | this.fromValue = cursor1.getValue(); | ||
106 | this.toValue = defaultValue; | ||
107 | } else { | ||
108 | resolveHashClashWithFirstEntry(); | ||
109 | } | ||
110 | } | ||
111 | } | ||
112 | } | 132 | } |
113 | 133 | ||
114 | protected void resolveHashClashWithFirstEntry() { | 134 | private boolean updateAndReturnWithResult() { |
115 | int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key); | 135 | return switch (this.state) { |
116 | if (compareResult < 0) { | 136 | case INIT -> throw new IllegalStateException("DiffCursor terminated without starting!"); |
117 | this.hashClash = HashClash.STUCK_CURSOR_2; | 137 | case MOVING_MOVING_SAME_KEY_SAME_VALUE, MOVING_MOVING_SAME_NODE -> |
118 | this.cursorRelation = 0; | 138 | throw new IllegalStateException("DiffCursor terminated in unstable state!"); |
119 | this.key = cursor1.key; | 139 | case MOVING_MOVING_BEHIND1, MOVING_TERMINATED, MOVING_MOVING_HASH1 -> { |
120 | this.fromValue = cursor1.value; | 140 | this.key = this.cursor1.getKey(); |
121 | this.toValue = defaultValue; | 141 | this.fromValue = this.cursor1.getValue(); |
122 | } else if (compareResult > 0) { | 142 | this.toValue = this.defaultValue; |
123 | this.hashClash = HashClash.STUCK_CURSOR_1; | 143 | yield true; |
124 | this.cursorRelation = 0; | 144 | } |
125 | this.key = cursor2.key; | 145 | case MOVING_MOVING_BEHIND2, TERMINATED_MOVING, MOVING_MOVING_HASH2 -> { |
126 | this.fromValue = defaultValue; | 146 | this.key = this.cursor2.getKey(); |
127 | this.toValue = cursor2.value; | 147 | this.fromValue = this.defaultValue; |
128 | } else { | 148 | this.toValue = cursor2.getValue(); |
129 | throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); | 149 | yield true; |
130 | } | 150 | } |
151 | case MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE -> { | ||
152 | this.key = this.cursor1.getKey(); | ||
153 | this.fromValue = this.cursor1.getValue(); | ||
154 | this.toValue = this.cursor2.getValue(); | ||
155 | yield true; | ||
156 | } | ||
157 | case TERMINATED_TERMINATED -> { | ||
158 | this.key = null; | ||
159 | this.fromValue = null; | ||
160 | this.toValue = null; | ||
161 | yield false; | ||
162 | } | ||
163 | }; | ||
131 | } | 164 | } |
132 | 165 | ||
133 | protected boolean isInHashClash() { | 166 | public boolean move() { |
134 | return this.hashClash != HashClash.NONE; | 167 | do { |
168 | this.state = moveOne(this.state); | ||
169 | } while (!isInStableState()); | ||
170 | return updateAndReturnWithResult(); | ||
135 | } | 171 | } |
136 | 172 | ||
137 | protected void resolveHashClashWithSecondEntry() { | 173 | private State moveOne(State currentState) { |
138 | switch (this.hashClash) { | 174 | return switch (currentState) { |
139 | case STUCK_CURSOR_1: | 175 | case INIT, MOVING_MOVING_HASH2, MOVING_MOVING_SAME_KEY_SAME_VALUE, MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE -> { |
140 | this.hashClash = HashClash.NONE; | 176 | boolean cursor1Moved = cursor1.move(); |
141 | this.cursorRelation = 0; | 177 | boolean cursor2Moved = cursor2.move(); |
142 | this.key = cursor1.key; | 178 | yield recalculateStateAfterCursorMovement(cursor1Moved, cursor2Moved); |
143 | this.fromValue = cursor1.value; | 179 | } |
144 | this.toValue = defaultValue; | 180 | case MOVING_MOVING_SAME_NODE -> { |
145 | break; | 181 | boolean cursor1Moved = cursor1.skipCurrentNode(); |
146 | case STUCK_CURSOR_2: | 182 | boolean cursor2Moved = cursor2.skipCurrentNode(); |
147 | this.hashClash = HashClash.NONE; | 183 | yield recalculateStateAfterCursorMovement(cursor1Moved, cursor2Moved); |
148 | this.cursorRelation = 0; | 184 | } |
149 | this.key = cursor2.key; | 185 | case MOVING_MOVING_BEHIND1 -> { |
150 | this.fromValue = defaultValue; | 186 | boolean cursorMoved = cursor1.move(); |
151 | this.toValue = cursor2.value; | 187 | if (cursorMoved) { |
152 | break; | 188 | yield recalculateStateBasedOnCursorRelation(); |
153 | default: | 189 | } else { |
154 | throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); | 190 | yield State.TERMINATED_MOVING; |
155 | } | 191 | } |
192 | } | ||
193 | case MOVING_MOVING_BEHIND2 -> { | ||
194 | boolean cursorMoved = cursor2.move(); | ||
195 | if (cursorMoved) { | ||
196 | yield recalculateStateBasedOnCursorRelation(); | ||
197 | } else { | ||
198 | yield State.MOVING_TERMINATED; | ||
199 | } | ||
200 | } | ||
201 | case TERMINATED_MOVING -> { | ||
202 | boolean cursorMoved = cursor2.move(); | ||
203 | if (cursorMoved) { | ||
204 | yield State.TERMINATED_MOVING; | ||
205 | } else { | ||
206 | yield State.TERMINATED_TERMINATED; | ||
207 | } | ||
208 | } | ||
209 | case MOVING_TERMINATED -> { | ||
210 | boolean cursorMoved = cursor1.move(); | ||
211 | if (cursorMoved) { | ||
212 | yield State.MOVING_TERMINATED; | ||
213 | } else { | ||
214 | yield State.TERMINATED_TERMINATED; | ||
215 | } | ||
216 | } | ||
217 | case MOVING_MOVING_HASH1 -> State.MOVING_MOVING_HASH2; | ||
218 | case TERMINATED_TERMINATED -> throw new IllegalStateException("Trying to move while terminated!"); | ||
219 | }; | ||
156 | } | 220 | } |
157 | 221 | ||
158 | protected boolean sameValues() { | 222 | private State recalculateStateAfterCursorMovement(boolean cursor1Moved, boolean cursor2Moved) { |
159 | if (this.fromValue == null) { | 223 | if (cursor1Moved && cursor2Moved) { |
160 | return this.toValue == null; | 224 | return recalculateStateBasedOnCursorRelation(); |
225 | } else if (cursor1Moved) { | ||
226 | return State.MOVING_TERMINATED; | ||
227 | } else if (cursor2Moved) { | ||
228 | return State.TERMINATED_MOVING; | ||
161 | } else { | 229 | } else { |
162 | return this.fromValue.equals(this.toValue); | 230 | return State.TERMINATED_TERMINATED; |
163 | } | 231 | } |
164 | } | 232 | } |
165 | 233 | ||
166 | protected boolean moveOne() { | 234 | private State recalculateStateBasedOnCursorRelation() { |
167 | if (isTerminated()) { | 235 | final int relation = InOrderMapCursor.comparePosition(cursor1, cursor2); |
168 | return false; | 236 | |
169 | } | 237 | if (relation > 0) { |
170 | if (this.cursorRelation > 0 || cursor2.isTerminated()) { | 238 | return State.MOVING_MOVING_BEHIND1; |
171 | return cursor1.move(); | 239 | } else if (relation < 0) { |
172 | } else if (this.cursorRelation < 0 || cursor1.isTerminated()) { | 240 | return State.MOVING_MOVING_BEHIND2; |
173 | return cursor2.move(); | ||
174 | } else { | ||
175 | boolean moved1 = cursor1.move(); | ||
176 | boolean moved2 = cursor2.move(); | ||
177 | return moved1 && moved2; | ||
178 | } | 241 | } |
179 | } | ||
180 | 242 | ||
181 | private boolean skipNode() { | 243 | if (InOrderMapCursor.sameSubNode(cursor1, cursor2)) { |
182 | if (isTerminated()) { | 244 | return State.MOVING_MOVING_SAME_NODE; |
183 | throw new IllegalStateException("DiffCursor tries to skip when terminated!"); | 245 | } else if (Objects.equals(cursor1.getKey(), cursor2.getKey())) { |
246 | if (Objects.equals(cursor1.getValue(), cursor2.getValue())) { | ||
247 | return State.MOVING_MOVING_SAME_KEY_SAME_VALUE; | ||
248 | } else { | ||
249 | return State.MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE; | ||
250 | } | ||
184 | } | 251 | } |
185 | boolean update1 = cursor1.skipCurrentNode(); | ||
186 | boolean update2 = cursor2.skipCurrentNode(); | ||
187 | updateState(); | ||
188 | return update1 && update2; | ||
189 | } | ||
190 | 252 | ||
191 | protected boolean moveToConsistentState() { | 253 | final int depth = InOrderMapCursor.compareDepth(cursor1, cursor2); |
192 | if (!isTerminated()) { | 254 | |
193 | boolean changed; | 255 | if (depth > 0) { |
194 | boolean lastResult = true; | 256 | return State.MOVING_MOVING_BEHIND1; |
195 | do { | 257 | } else if (depth < 0) { |
196 | changed = false; | 258 | return State.MOVING_MOVING_BEHIND2; |
197 | if (MapCursor.sameSubnode(cursor1, cursor2)) { | ||
198 | lastResult = skipNode(); | ||
199 | changed = true; | ||
200 | } | ||
201 | if (sameValues()) { | ||
202 | lastResult = moveOne(); | ||
203 | changed = true; | ||
204 | } | ||
205 | updateState(); | ||
206 | } while (changed && !isTerminated()); | ||
207 | return lastResult; | ||
208 | } else { | 259 | } else { |
209 | return false; | 260 | return State.MOVING_MOVING_HASH1; |
210 | } | 261 | } |
211 | } | ||
212 | |||
213 | public boolean move() { | ||
214 | if (!isTerminated()) { | ||
215 | if (isInHashClash()) { | ||
216 | this.resolveHashClashWithSecondEntry(); | ||
217 | return true; | ||
218 | } else { | ||
219 | if (moveOne()) { | ||
220 | return moveToConsistentState(); | ||
221 | } else { | ||
222 | return false; | ||
223 | } | ||
224 | } | ||
225 | 262 | ||
226 | } else | ||
227 | return false; | ||
228 | } | 263 | } |
229 | } | 264 | } |
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java new file mode 100644 index 00000000..d63522cd --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MapTransaction.java | |||
@@ -0,0 +1,39 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.internal; | ||
7 | |||
8 | import java.util.Arrays; | ||
9 | import java.util.Objects; | ||
10 | |||
11 | public record MapTransaction<K, V>(MapDelta<K, V>[] deltas, long version, MapTransaction<K, V> parent) { | ||
12 | |||
13 | @Override | ||
14 | public int hashCode() { | ||
15 | final int prime = 31; | ||
16 | int result = 1; | ||
17 | result = prime * result + Arrays.hashCode(deltas); | ||
18 | result = prime * result + Objects.hash(parent, version); | ||
19 | return result; | ||
20 | } | ||
21 | |||
22 | @Override | ||
23 | public boolean equals(Object obj) { | ||
24 | if (this == obj) | ||
25 | return true; | ||
26 | if (obj == null) | ||
27 | return false; | ||
28 | if (getClass() != obj.getClass()) | ||
29 | return false; | ||
30 | @SuppressWarnings("unchecked") | ||
31 | MapTransaction<K, V> other = (MapTransaction<K, V>) obj; | ||
32 | return Arrays.equals(deltas, other.deltas) && Objects.equals(parent, other.parent) && version == other.version; | ||
33 | } | ||
34 | |||
35 | @Override | ||
36 | public String toString() { | ||
37 | return "MapTransaction " + version + " " + Arrays.toString(deltas); | ||
38 | } | ||
39 | } | ||
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 index 1129ee5a..bb85deb9 100644 --- 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 | |||
@@ -12,15 +12,15 @@ import java.util.Map; | |||
12 | 12 | ||
13 | public class MutableNode<K, V> extends Node<K, V> { | 13 | public class MutableNode<K, V> extends Node<K, V> { |
14 | int cachedHash; | 14 | int cachedHash; |
15 | protected boolean cachedHashValid; | ||
15 | protected Object[] content; | 16 | protected Object[] content; |
16 | 17 | ||
17 | protected MutableNode() { | 18 | protected MutableNode() { |
18 | this.content = new Object[2 * FACTOR]; | 19 | this.content = new Object[2 * FACTOR]; |
19 | updateHash(); | 20 | invalidateHash(); |
20 | } | 21 | } |
21 | 22 | ||
22 | public static <K, V> MutableNode<K, V> initialize(K key, V value, ContinousHashProvider<? super K> hashProvider, | 23 | public static <K, V> MutableNode<K, V> initialize(K key, V value, ContinousHashProvider<? super K> hashProvider, V defaultValue) { |
23 | V defaultValue) { | ||
24 | if (value == defaultValue) { | 24 | if (value == defaultValue) { |
25 | return null; | 25 | return null; |
26 | } else { | 26 | } else { |
@@ -29,7 +29,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
29 | MutableNode<K, V> res = new MutableNode<>(); | 29 | MutableNode<K, V> res = new MutableNode<>(); |
30 | res.content[2 * fragment] = key; | 30 | res.content[2 * fragment] = key; |
31 | res.content[2 * fragment + 1] = value; | 31 | res.content[2 * fragment + 1] = value; |
32 | res.updateHash(); | 32 | res.invalidateHash(); |
33 | return res; | 33 | return res; |
34 | } | 34 | } |
35 | } | 35 | } |
@@ -37,44 +37,41 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
37 | /** | 37 | /** |
38 | * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode} | 38 | * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode} |
39 | * | 39 | * |
40 | * @param node | 40 | * @param node to be transformed |
41 | */ | 41 | */ |
42 | protected MutableNode(ImmutableNode<K, V> node) { | 42 | protected MutableNode(ImmutableNode<K, V> node) { |
43 | this.content = new Object[2 * FACTOR]; | 43 | this.content = new Object[2 * FACTOR]; |
44 | int dataUsed = 0; | 44 | int dataUsed = 0; |
45 | int nodeUsed = 0; | 45 | int nodeUsed = 0; |
46 | for (int i = 0; i < FACTOR; i++) { | 46 | for (int i = 0; i < FACTOR; i++) { |
47 | int bitposition = 1 << i; | 47 | int bitPosition = 1 << i; |
48 | if ((node.dataMap & bitposition) != 0) { | 48 | if ((node.dataMap & bitPosition) != 0) { |
49 | content[2 * i] = node.content[dataUsed * 2]; | 49 | content[2 * i] = node.content[dataUsed * 2]; |
50 | content[2 * i + 1] = node.content[dataUsed * 2 + 1]; | 50 | content[2 * i + 1] = node.content[dataUsed * 2 + 1]; |
51 | dataUsed++; | 51 | dataUsed++; |
52 | } else if ((node.nodeMap & bitposition) != 0) { | 52 | } else if ((node.nodeMap & bitPosition) != 0) { |
53 | content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed]; | 53 | content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed]; |
54 | nodeUsed++; | 54 | nodeUsed++; |
55 | } | 55 | } |
56 | } | 56 | } |
57 | this.cachedHash = node.hashCode(); | 57 | this.cachedHashValid = false; |
58 | } | 58 | } |
59 | 59 | ||
60 | @Override | 60 | @Override |
61 | public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { | 61 | public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { |
62 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); | 62 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); |
63 | @SuppressWarnings("unchecked") | 63 | @SuppressWarnings("unchecked") K keyCandidate = (K) this.content[2 * selectedHashFragment]; |
64 | K keyCandidate = (K) this.content[2 * selectedHashFragment]; | ||
65 | if (keyCandidate != null) { | 64 | if (keyCandidate != null) { |
66 | if (keyCandidate.equals(key)) { | 65 | if (keyCandidate.equals(key)) { |
67 | @SuppressWarnings("unchecked") | 66 | @SuppressWarnings("unchecked") V value = (V) this.content[2 * selectedHashFragment + 1]; |
68 | V value = (V) this.content[2 * selectedHashFragment + 1]; | ||
69 | return value; | 67 | return value; |
70 | } else { | 68 | } else { |
71 | return defaultValue; | 69 | return defaultValue; |
72 | } | 70 | } |
73 | } else { | 71 | } else { |
74 | @SuppressWarnings("unchecked") | 72 | @SuppressWarnings("unchecked") var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1]; |
75 | var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1]; | ||
76 | if (nodeCandidate != null) { | 73 | if (nodeCandidate != null) { |
77 | int newDepth = depth + 1; | 74 | int newDepth = incrementDepth(depth); |
78 | int newHash = newHash(hashProvider, key, hash, newDepth); | 75 | int newHash = newHash(hashProvider, key, hash, newDepth); |
79 | return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); | 76 | return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); |
80 | } else { | 77 | } else { |
@@ -84,13 +81,11 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
84 | } | 81 | } |
85 | 82 | ||
86 | @Override | 83 | @Override |
87 | public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValueBox, ContinousHashProvider<? super K> hashProvider, | 84 | public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValueBox, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { |
88 | V defaultValue, int hash, int depth) { | ||
89 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); | 85 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); |
90 | @SuppressWarnings("unchecked") | 86 | @SuppressWarnings("unchecked") K keyCandidate = (K) content[2 * selectedHashFragment]; |
91 | K keyCandidate = (K) content[2 * selectedHashFragment]; | ||
92 | if (keyCandidate != null) { | 87 | if (keyCandidate != null) { |
93 | // If has key | 88 | // If it has key |
94 | if (keyCandidate.equals(key)) { | 89 | if (keyCandidate.equals(key)) { |
95 | // The key is equals to an existing key -> update entry | 90 | // The key is equals to an existing key -> update entry |
96 | if (value == defaultValue) { | 91 | if (value == defaultValue) { |
@@ -111,25 +106,22 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
111 | return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment); | 106 | return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment); |
112 | } | 107 | } |
113 | } | 108 | } |
109 | } | ||
110 | // If it does not have key, check for value | ||
111 | @SuppressWarnings("unchecked") var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1]; | ||
112 | if (nodeCandidate != null) { | ||
113 | // If it has value, it is a sub-node -> update that | ||
114 | int newDepth = incrementDepth(depth); | ||
115 | var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, newHash(hashProvider, key, hash, newDepth), newDepth); | ||
116 | return updateWithSubNode(selectedHashFragment, newNode, (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); | ||
114 | } else { | 117 | } else { |
115 | // If it does not have key, check for nodeId | 118 | // If it does not have value, put it in the empty place |
116 | @SuppressWarnings("unchecked") | 119 | if (value == defaultValue) { |
117 | var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1]; | 120 | // don't need to add new key-value pair |
118 | if (nodeCandidate != null) { | 121 | oldValueBox.setOldValue(defaultValue); |
119 | // If it has nodeId, it is a subnode -> upate that | 122 | return this; |
120 | var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, | ||
121 | newHash(hashProvider, key, hash, depth + 1), depth + 1); | ||
122 | return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue)); | ||
123 | } else { | 123 | } else { |
124 | // If it does not have nodeId, put it in the empty place | 124 | return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue); |
125 | if (value == defaultValue) { | ||
126 | // dont need to add new key-nodeId pair | ||
127 | oldValueBox.setOldValue(defaultValue); | ||
128 | return this; | ||
129 | } else { | ||
130 | return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue); | ||
131 | } | ||
132 | |||
133 | } | 125 | } |
134 | } | 126 | } |
135 | } | 127 | } |
@@ -138,30 +130,31 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
138 | content[2 * selectedHashFragment] = key; | 130 | content[2 * selectedHashFragment] = key; |
139 | oldValueBox.setOldValue(defaultValue); | 131 | oldValueBox.setOldValue(defaultValue); |
140 | content[2 * selectedHashFragment + 1] = value; | 132 | content[2 * selectedHashFragment + 1] = value; |
141 | updateHash(); | 133 | invalidateHash(); |
142 | return this; | 134 | return this; |
143 | } | 135 | } |
144 | 136 | ||
145 | /** | 137 | /** |
146 | * Updates an entry in a selected hash-fragment to a non-default nodeId. | 138 | * Updates an entry in a selected hash-fragment to a non-default value. |
147 | * | 139 | * |
148 | * @param value | 140 | * @param value new value |
149 | * @param selectedHashFragment | 141 | * @param selectedHashFragment position of the value |
150 | * @return | 142 | * @return updated node |
151 | */ | 143 | */ |
152 | @SuppressWarnings("unchecked") | 144 | @SuppressWarnings("unchecked") |
153 | Node<K, V> updateValue(V value, OldValueBox<V> oldValue, int selectedHashFragment) { | 145 | Node<K, V> updateValue(V value, OldValueBox<V> oldValue, int selectedHashFragment) { |
154 | oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); | 146 | oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); |
155 | content[2 * selectedHashFragment + 1] = value; | 147 | content[2 * selectedHashFragment + 1] = value; |
156 | updateHash(); | 148 | invalidateHash(); |
157 | return this; | 149 | return this; |
158 | } | 150 | } |
159 | 151 | ||
160 | /** | 152 | /** |
153 | * Updates an entry in a selected hash-fragment with a subtree. | ||
161 | * | 154 | * |
162 | * @param selectedHashFragment | 155 | * @param selectedHashFragment position of the value |
163 | * @param newNode | 156 | * @param newNode the subtree |
164 | * @return | 157 | * @return updated node |
165 | */ | 158 | */ |
166 | Node<K, V> updateWithSubNode(int selectedHashFragment, Node<K, V> newNode, boolean deletionHappened) { | 159 | Node<K, V> updateWithSubNode(int selectedHashFragment, Node<K, V> newNode, boolean deletionHappened) { |
167 | if (deletionHappened) { | 160 | if (deletionHappened) { |
@@ -169,7 +162,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
169 | // Check whether this node become empty | 162 | // Check whether this node become empty |
170 | content[2 * selectedHashFragment + 1] = null; // i.e. the new node | 163 | content[2 * selectedHashFragment + 1] = null; // i.e. the new node |
171 | if (hasContent()) { | 164 | if (hasContent()) { |
172 | updateHash(); | 165 | invalidateHash(); |
173 | return this; | 166 | return this; |
174 | } else { | 167 | } else { |
175 | return null; | 168 | return null; |
@@ -180,10 +173,10 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
180 | if (immutableNewNode != null) { | 173 | if (immutableNewNode != null) { |
181 | int orphaned = immutableNewNode.isOrphaned(); | 174 | int orphaned = immutableNewNode.isOrphaned(); |
182 | if (orphaned >= 0) { | 175 | if (orphaned >= 0) { |
183 | // orphan subnode data is replaced with data | 176 | // orphan sub-node data is replaced with data |
184 | content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2]; | 177 | content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2]; |
185 | content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1]; | 178 | content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1]; |
186 | updateHash(); | 179 | invalidateHash(); |
187 | return this; | 180 | return this; |
188 | } | 181 | } |
189 | } | 182 | } |
@@ -191,15 +184,13 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
191 | } | 184 | } |
192 | // normal behaviour | 185 | // normal behaviour |
193 | content[2 * selectedHashFragment + 1] = newNode; | 186 | content[2 * selectedHashFragment + 1] = newNode; |
194 | updateHash(); | 187 | invalidateHash(); |
195 | return this; | 188 | return this; |
196 | |||
197 | } | 189 | } |
198 | 190 | ||
199 | private boolean hasContent() { | 191 | private boolean hasContent() { |
200 | for (Object element : this.content) { | 192 | for (Object element : this.content) { |
201 | if (element != null) | 193 | if (element != null) return true; |
202 | return true; | ||
203 | } | 194 | } |
204 | return false; | 195 | return false; |
205 | } | 196 | } |
@@ -226,27 +217,24 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
226 | } | 217 | } |
227 | 218 | ||
228 | @SuppressWarnings("unchecked") | 219 | @SuppressWarnings("unchecked") |
229 | private Node<K, V> moveDownAndSplit(ContinousHashProvider<? super K> hashProvider, K newKey, V newValue, | 220 | private Node<K, V> moveDownAndSplit(ContinousHashProvider<? super K> hashProvider, K newKey, V newValue, K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) { |
230 | K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) { | ||
231 | V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1]; | 221 | V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1]; |
232 | 222 | ||
233 | MutableNode<K, V> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, | 223 | MutableNode<K, V> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, incrementDepth(depth)); |
234 | hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, depth + 1); | ||
235 | 224 | ||
236 | content[2 * selectedHashFragmentOfCurrentDepth] = null; | 225 | content[2 * selectedHashFragmentOfCurrentDepth] = null; |
237 | content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode; | 226 | content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode; |
238 | updateHash(); | 227 | invalidateHash(); |
239 | return this; | 228 | return this; |
240 | } | 229 | } |
241 | 230 | ||
242 | // Pass everything as parameters for performance. | 231 | // Pass everything as parameters for performance. |
243 | @SuppressWarnings("squid:S107") | 232 | @SuppressWarnings("squid:S107") |
244 | private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1, | 233 | private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1, int oldHash1, K key2, V value2, int oldHash2, int newDepth) { |
245 | int oldHash1, K key2, V value2, int oldHash2, int newdepth) { | 234 | int newHash1 = newHash(hashProvider, key1, oldHash1, newDepth); |
246 | int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth); | 235 | int newHash2 = newHash(hashProvider, key2, oldHash2, newDepth); |
247 | int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth); | 236 | int newFragment1 = hashFragment(newHash1, shiftDepth(newDepth)); |
248 | int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth)); | 237 | int newFragment2 = hashFragment(newHash2, shiftDepth(newDepth)); |
249 | int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth)); | ||
250 | 238 | ||
251 | MutableNode<K, V> subNode = new MutableNode<>(); | 239 | MutableNode<K, V> subNode = new MutableNode<>(); |
252 | if (newFragment1 != newFragment2) { | 240 | if (newFragment1 != newFragment2) { |
@@ -256,11 +244,10 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
256 | subNode.content[newFragment2 * 2] = key2; | 244 | subNode.content[newFragment2 * 2] = key2; |
257 | subNode.content[newFragment2 * 2 + 1] = value2; | 245 | subNode.content[newFragment2 * 2 + 1] = value2; |
258 | } else { | 246 | } else { |
259 | MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, | 247 | MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newDepth)); |
260 | newHash2, newdepth + 1); | ||
261 | subNode.content[newFragment1 * 2 + 1] = subSubNode; | 248 | subNode.content[newFragment1 * 2 + 1] = subSubNode; |
262 | } | 249 | } |
263 | subNode.updateHash(); | 250 | subNode.invalidateHash(); |
264 | return subNode; | 251 | return subNode; |
265 | } | 252 | } |
266 | 253 | ||
@@ -270,7 +257,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
270 | oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); | 257 | oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); |
271 | content[2 * selectedHashFragment + 1] = null; | 258 | content[2 * selectedHashFragment + 1] = null; |
272 | if (hasContent()) { | 259 | if (hasContent()) { |
273 | updateHash(); | 260 | invalidateHash(); |
274 | return this; | 261 | return this; |
275 | } else { | 262 | } else { |
276 | return null; | 263 | return null; |
@@ -321,10 +308,13 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
321 | cursor.dataIndex = MapCursor.INDEX_FINISH; | 308 | cursor.dataIndex = MapCursor.INDEX_FINISH; |
322 | } | 309 | } |
323 | 310 | ||
324 | // 2. look inside the subnodes | 311 | // 2. look inside the sub-nodes |
312 | if(cursor.nodeIndexStack.peek()==null) { | ||
313 | throw new IllegalStateException("Cursor moved to the next state when the state is empty."); | ||
314 | } | ||
325 | for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) { | 315 | for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) { |
326 | if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) { | 316 | if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) { |
327 | // 2.1 found next subnode, move down to the subnode | 317 | // 2.1 found next sub-node, move down to the sub-node |
328 | Node<K, V> subnode = (Node<K, V>) this.content[index * 2 + 1]; | 318 | Node<K, V> subnode = (Node<K, V>) this.content[index * 2 + 1]; |
329 | 319 | ||
330 | cursor.dataIndex = MapCursor.INDEX_START; | 320 | cursor.dataIndex = MapCursor.INDEX_START; |
@@ -336,7 +326,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
336 | return subnode.moveToNext(cursor); | 326 | return subnode.moveToNext(cursor); |
337 | } | 327 | } |
338 | } | 328 | } |
339 | // 3. no subnode found, move up | 329 | // 3. no sub-node found, move up |
340 | cursor.nodeStack.pop(); | 330 | cursor.nodeStack.pop(); |
341 | cursor.nodeIndexStack.pop(); | 331 | cursor.nodeIndexStack.pop(); |
342 | if (!cursor.nodeStack.isEmpty()) { | 332 | if (!cursor.nodeStack.isEmpty()) { |
@@ -350,10 +340,51 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
350 | } | 340 | } |
351 | 341 | ||
352 | @Override | 342 | @Override |
353 | public void prettyPrint(StringBuilder builder, int depth, int code) { | 343 | @SuppressWarnings("unchecked") |
354 | for (int i = 0; i < depth; i++) { | 344 | boolean moveToNextInorder(InOrderMapCursor<K,V> cursor) { |
355 | builder.append("\t"); | 345 | if(cursor.nodeIndexStack.peek()==null || cursor.nodeStack.peek()==null) { |
346 | throw new IllegalStateException("Cursor moved to the next state when the state is empty."); | ||
356 | } | 347 | } |
348 | |||
349 | int position = cursor.nodeIndexStack.peek(); | ||
350 | |||
351 | for (int index = position + 1; index < FACTOR; index++) { | ||
352 | // data found | ||
353 | if (this.content[index * 2] != null) { | ||
354 | cursor.nodeIndexStack.pop(); | ||
355 | cursor.nodeIndexStack.push(index); | ||
356 | |||
357 | cursor.key = (K) this.content[index * 2]; | ||
358 | cursor.value = (V) this.content[index * 2 + 1]; | ||
359 | return true; | ||
360 | } else if (this.content[index * 2 +1] != null) { | ||
361 | // sub-node found | ||
362 | Node<K,V> subnode = (Node<K, V>) this.content[index * 2 +1]; | ||
363 | cursor.nodeIndexStack.pop(); | ||
364 | cursor.nodeIndexStack.push(index); | ||
365 | cursor.nodeIndexStack.push(InOrderMapCursor.INDEX_START); | ||
366 | cursor.nodeStack.push(subnode); | ||
367 | |||
368 | return subnode.moveToNextInorder(cursor); | ||
369 | } | ||
370 | } | ||
371 | |||
372 | // nothing found | ||
373 | cursor.nodeStack.pop(); | ||
374 | cursor.nodeIndexStack.pop(); | ||
375 | if (!cursor.nodeStack.isEmpty()) { | ||
376 | Node<K, V> supernode = cursor.nodeStack.peek(); | ||
377 | return supernode.moveToNextInorder(cursor); | ||
378 | } else { | ||
379 | cursor.key = null; | ||
380 | cursor.value = null; | ||
381 | return false; | ||
382 | } | ||
383 | } | ||
384 | |||
385 | @Override | ||
386 | public void prettyPrint(StringBuilder builder, int depth, int code) { | ||
387 | builder.append("\t".repeat(Math.max(0, depth))); | ||
357 | if (code >= 0) { | 388 | if (code >= 0) { |
358 | builder.append(code); | 389 | builder.append(code); |
359 | builder.append(":"); | 390 | builder.append(":"); |
@@ -376,13 +407,12 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
376 | } | 407 | } |
377 | } | 408 | } |
378 | builder.append(")"); | 409 | builder.append(")"); |
379 | // print subnodes | 410 | // print sub-nodes |
380 | for (int i = 0; i < FACTOR; i++) { | 411 | for (int i = 0; i < FACTOR; i++) { |
381 | if (content[2 * i] == null && content[2 * i + 1] != null) { | 412 | if (content[2 * i] == null && content[2 * i + 1] != null) { |
382 | @SuppressWarnings("unchecked") | 413 | @SuppressWarnings("unchecked") Node<K, V> subNode = (Node<K, V>) content[2 * i + 1]; |
383 | Node<K, V> subNode = (Node<K, V>) content[2 * i + 1]; | ||
384 | builder.append("\n"); | 414 | builder.append("\n"); |
385 | subNode.prettyPrint(builder, depth + 1, i); | 415 | subNode.prettyPrint(builder, incrementDepth(depth), i); |
386 | } | 416 | } |
387 | } | 417 | } |
388 | } | 418 | } |
@@ -399,57 +429,67 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
399 | // check the place of data | 429 | // check the place of data |
400 | for (int i = 0; i < FACTOR; i++) { | 430 | for (int i = 0; i < FACTOR; i++) { |
401 | if (this.content[2 * i] != null) { | 431 | if (this.content[2 * i] != null) { |
402 | @SuppressWarnings("unchecked") | 432 | @SuppressWarnings("unchecked") K key = (K) this.content[2 * i]; |
403 | K key = (K) this.content[2 * i]; | 433 | @SuppressWarnings("unchecked") V value = (V) this.content[2 * i + 1]; |
404 | @SuppressWarnings("unchecked") | ||
405 | V value = (V) this.content[2 * i + 1]; | ||
406 | 434 | ||
407 | if (value == defaultValue) { | 435 | if (value == defaultValue) { |
408 | throw new IllegalStateException("Node contains default nodeId!"); | 436 | throw new IllegalStateException("Node contains default value!"); |
409 | } | 437 | } |
410 | int hashCode = hashProvider.getHash(key, hashDepth(depth)); | 438 | int hashCode = hashProvider.getHash(key, hashDepth(depth)); |
411 | int shiftDepth = shiftDepth(depth); | 439 | int shiftDepth = shiftDepth(depth); |
412 | int selectedHashFragment = hashFragment(hashCode, shiftDepth); | 440 | int selectedHashFragment = hashFragment(hashCode, shiftDepth); |
413 | if (i != selectedHashFragment) { | 441 | if (i != selectedHashFragment) { |
414 | throw new IllegalStateException("Key " + key + " with hash code " + hashCode | 442 | throw new IllegalStateException("Key " + key + " with hash code " + hashCode + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i); |
415 | + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i); | ||
416 | } | 443 | } |
417 | } | 444 | } |
418 | } | 445 | } |
419 | // check subnodes | 446 | // check sub-nodes |
420 | for (int i = 0; i < FACTOR; i++) { | 447 | for (int i = 0; i < FACTOR; i++) { |
421 | if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { | 448 | if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { |
422 | @SuppressWarnings("unchecked") | 449 | @SuppressWarnings("unchecked") var subNode = (Node<K, V>) this.content[2 * i + 1]; |
423 | var subNode = (Node<K, V>) this.content[2 * i + 1]; | 450 | subNode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth)); |
424 | subNode.checkIntegrity(hashProvider, defaultValue, depth + 1); | ||
425 | } | 451 | } |
426 | } | 452 | } |
427 | // check the hash | 453 | // check the hash |
428 | int oldHash = this.cachedHash; | 454 | if (cachedHashValid) { |
429 | updateHash(); | 455 | int oldHash = this.cachedHash; |
430 | int newHash = this.cachedHash; | 456 | invalidateHash(); |
431 | if (oldHash != newHash) { | 457 | int newHash = hashCode(); |
432 | throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")"); | 458 | if (oldHash != newHash) { |
459 | throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")"); | ||
460 | } | ||
433 | } | 461 | } |
434 | } | 462 | } |
435 | 463 | ||
436 | protected void updateHash() { | 464 | protected void invalidateHash() { |
437 | this.cachedHash = Arrays.hashCode(content); | 465 | this.cachedHashValid = false; |
438 | } | 466 | } |
439 | 467 | ||
440 | @Override | 468 | @Override |
441 | public int hashCode() { | 469 | public int hashCode() { |
470 | if (!this.cachedHashValid) { | ||
471 | this.cachedHash = Arrays.hashCode(content); | ||
472 | this.cachedHashValid = true; | ||
473 | } | ||
442 | return this.cachedHash; | 474 | return this.cachedHash; |
443 | } | 475 | } |
444 | 476 | ||
445 | @Override | 477 | @Override |
446 | public boolean equals(Object obj) { | 478 | public boolean equals(Object obj) { |
447 | if (this == obj) | 479 | if (this == obj) return true; |
448 | return true; | 480 | if (obj == null) return false; |
449 | if (obj == null) | ||
450 | return false; | ||
451 | if (obj instanceof MutableNode<?, ?> mutableObj) { | 481 | if (obj instanceof MutableNode<?, ?> mutableObj) { |
452 | return Arrays.deepEquals(this.content, mutableObj.content); | 482 | if (obj.hashCode() != this.hashCode()) { |
483 | return false; | ||
484 | } else { | ||
485 | for (int i = 0; i < FACTOR * 2; i++) { | ||
486 | Object thisContent = this.content[i]; | ||
487 | if (thisContent != null && !thisContent.equals(mutableObj.content[i])) { | ||
488 | return false; | ||
489 | } | ||
490 | } | ||
491 | return true; | ||
492 | } | ||
453 | } else if (obj instanceof ImmutableNode<?, ?> immutableObj) { | 493 | } else if (obj instanceof ImmutableNode<?, ?> immutableObj) { |
454 | return ImmutableNode.compareImmutableMutable(immutableObj, this); | 494 | return ImmutableNode.compareImmutableMutable(immutableObj, this); |
455 | } else { | 495 | } else { |
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 index 958d645f..4b44f760 100644 --- 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 | |||
@@ -9,82 +9,123 @@ import java.util.Map; | |||
9 | 9 | ||
10 | import tools.refinery.store.map.ContinousHashProvider; | 10 | import tools.refinery.store.map.ContinousHashProvider; |
11 | 11 | ||
12 | public abstract class Node<K,V>{ | 12 | public abstract class Node<K, V> { |
13 | public static final int BRANCHING_FACTOR_BITS = 5; | 13 | public static final int BRANCHING_FACTOR_BITS = 5; |
14 | public static final int FACTOR = 1<<BRANCHING_FACTOR_BITS; | 14 | public static final int FACTOR = 1 << BRANCHING_FACTOR_BITS; |
15 | protected static final int NUMBER_OF_FACTORS = Integer.SIZE / BRANCHING_FACTOR_BITS; | 15 | protected static final int NUMBER_OF_FACTORS = Integer.SIZE / BRANCHING_FACTOR_BITS; |
16 | protected static final int FACTOR_MASK = FACTOR-1; | 16 | protected static final int FACTOR_MASK = FACTOR - 1; |
17 | public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS; | 17 | public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS; |
18 | public static final int FACTOR_SELECTION_BITS = 32 - Integer.numberOfLeadingZeros(NUMBER_OF_FACTORS); | ||
19 | public static final int FACTOR_SELECTION_MASK = (1 << FACTOR_SELECTION_BITS) - 1; | ||
20 | public static final int INCREMENT_BIG_STEP = (1 << FACTOR_SELECTION_BITS) - NUMBER_OF_FACTORS; | ||
21 | |||
22 | /** | ||
23 | * Increments the depth of the search in the tree. The depth parameter has two | ||
24 | * components: the least few bits selects the fragment of the hashcode, the | ||
25 | * other part selects the continuous hash. | ||
26 | * | ||
27 | * @param depth parameter encoding the fragment and the depth | ||
28 | * @return new depth. | ||
29 | */ | ||
30 | protected int incrementDepth(int depth) { | ||
31 | int newDepth = depth + 1; | ||
32 | if ((newDepth & FACTOR_SELECTION_MASK) == NUMBER_OF_FACTORS) { | ||
33 | newDepth += INCREMENT_BIG_STEP; | ||
34 | } | ||
35 | return newDepth; | ||
36 | } | ||
18 | 37 | ||
19 | /** | 38 | /** |
20 | * Calculates the index for the continuous hash. | 39 | * Calculates the index for the continuous hash. |
40 | * | ||
21 | * @param depth The depth of the node in the tree. | 41 | * @param depth The depth of the node in the tree. |
22 | * @return The index of the continuous hash. | 42 | * @return The index of the continuous hash. |
23 | */ | 43 | */ |
24 | protected static int hashDepth(int depth) { | 44 | protected static int hashDepth(int depth) { |
25 | return depth/NUMBER_OF_FACTORS; | 45 | return depth >> FACTOR_SELECTION_BITS; |
26 | } | 46 | } |
27 | 47 | ||
28 | /** | 48 | /** |
29 | * Calculates the which segment of a single hash should be used. | 49 | * Calculates the which segment of a single hash should be used. |
50 | * | ||
30 | * @param depth The depth of the node in the tree. | 51 | * @param depth The depth of the node in the tree. |
31 | * @return The segment of a hash code. | 52 | * @return The segment of a hash code. |
32 | */ | 53 | */ |
33 | protected static int shiftDepth(int depth) { | 54 | protected static int shiftDepth(int depth) { |
34 | return depth%NUMBER_OF_FACTORS; | 55 | return depth & FACTOR_SELECTION_MASK; |
35 | } | 56 | } |
57 | |||
36 | /** | 58 | /** |
37 | * Selects a segments from a complete hash for a given depth. | 59 | * Selects a segments from a complete hash for a given depth. |
38 | * @param hash A complete hash. | 60 | * |
61 | * @param hash A complete hash. | ||
39 | * @param shiftDepth The index of the segment. | 62 | * @param shiftDepth The index of the segment. |
40 | * @return The segment as an integer. | 63 | * @return The segment as an integer. |
41 | */ | 64 | */ |
42 | protected static int hashFragment(int hash, int shiftDepth) { | 65 | protected static int hashFragment(int hash, int shiftDepth) { |
43 | if(shiftDepth<0 || Node.NUMBER_OF_FACTORS<shiftDepth) throw new IllegalArgumentException("Invalid shift depth! valid intervall=[0;5], input="+shiftDepth); | 66 | if (shiftDepth < 0 || Node.NUMBER_OF_FACTORS < shiftDepth) |
44 | return (hash >>> shiftDepth*BRANCHING_FACTOR_BITS) & FACTOR_MASK; | 67 | throw new IllegalArgumentException("Invalid shift depth! valid interval=[0;5], input=" + shiftDepth); |
68 | return (hash >>> shiftDepth * BRANCHING_FACTOR_BITS) & FACTOR_MASK; | ||
45 | } | 69 | } |
46 | 70 | ||
47 | /** | 71 | /** |
48 | * Returns the hash code for a given depth. It may calculate new hash code, or reuse a hash code calculated for depth-1. | 72 | * Returns the hash code for a given depth. It may calculate new hash code, or |
49 | * @param key The key. | 73 | * reuse a hash code calculated for depth-1. |
50 | * @param hash Hash code for depth-1 | 74 | * |
75 | * @param key The key. | ||
76 | * @param hash Hash code for depth-1 | ||
51 | * @param depth The depth. | 77 | * @param depth The depth. |
52 | * @return The new hash code. | 78 | * @return The new hash code. |
53 | */ | 79 | */ |
54 | protected int newHash(final ContinousHashProvider<? super K> hashProvider, K key, int hash, int depth) { | 80 | protected int newHash(final ContinousHashProvider<? super K> hashProvider, K key, int hash, int depth) { |
55 | final int hashDepth = hashDepth(depth); | 81 | final int shiftDepth = shiftDepth(depth); |
56 | if(hashDepth>=ContinousHashProvider.MAX_PRACTICAL_DEPTH) { | 82 | if (shiftDepth == 0) { |
57 | throw new IllegalArgumentException("Key "+key+" have the clashing hashcode over the practical depth limitation ("+ContinousHashProvider.MAX_PRACTICAL_DEPTH+")!"); | 83 | final int hashDepth = hashDepth(depth); |
84 | if (hashDepth >= ContinousHashProvider.MAX_PRACTICAL_DEPTH) { | ||
85 | throw new IllegalArgumentException( | ||
86 | "Key " + key + " have the clashing hashcode over the practical depth limitation (" | ||
87 | + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!"); | ||
88 | } | ||
89 | return hashProvider.getHash(key, hashDepth); | ||
90 | } else { | ||
91 | return hash; | ||
58 | } | 92 | } |
59 | return depth%NUMBER_OF_FACTORS == 0? | ||
60 | hashProvider.getHash(key, hashDepth) : | ||
61 | hash; | ||
62 | } | 93 | } |
63 | 94 | ||
95 | public abstract V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, | ||
96 | int depth); | ||
97 | |||
98 | public abstract Node<K, V> putValue(K key, V value, OldValueBox<V> old, | ||
99 | ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth); | ||
64 | 100 | ||
65 | public abstract V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth); | ||
66 | public abstract Node<K,V> putValue(K key, V value, OldValueBox<V> old, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth); | ||
67 | public abstract long getSize(); | 101 | public abstract long getSize(); |
68 | 102 | ||
69 | abstract MutableNode<K, V> toMutable(); | 103 | abstract MutableNode<K, V> toMutable(); |
70 | public abstract ImmutableNode<K, V> toImmutable( | 104 | |
71 | Map<Node<K, V>,ImmutableNode<K, V>> cache); | 105 | public abstract ImmutableNode<K, V> toImmutable(Map<Node<K, V>, ImmutableNode<K, V>> cache); |
106 | |||
72 | protected abstract MutableNode<K, V> isMutable(); | 107 | protected abstract MutableNode<K, V> isMutable(); |
108 | |||
73 | /** | 109 | /** |
74 | * Moves a {@link MapCursor} to its next position. | 110 | * Moves a {@link MapCursor} to its next position. |
111 | * | ||
75 | * @param cursor the cursor | 112 | * @param cursor the cursor |
76 | * @return Whether there was a next nodeId to move on. | 113 | * @return Whether there was a next value to move on. |
77 | */ | 114 | */ |
78 | abstract boolean moveToNext(MapCursor<K,V> cursor); | 115 | abstract boolean moveToNext(MapCursor<K, V> cursor); |
116 | abstract boolean moveToNextInorder(InOrderMapCursor<K, V> cursor); | ||
79 | 117 | ||
80 | ///////// FOR printing | 118 | ///////// FOR printing |
81 | public abstract void prettyPrint(StringBuilder builder, int depth, int code); | 119 | public abstract void prettyPrint(StringBuilder builder, int depth, int code); |
120 | |||
121 | |||
82 | @Override | 122 | @Override |
83 | public String toString() { | 123 | public String toString() { |
84 | StringBuilder stringBuilder = new StringBuilder(); | 124 | StringBuilder stringBuilder = new StringBuilder(); |
85 | prettyPrint(stringBuilder, 0, -1); | 125 | prettyPrint(stringBuilder, 0, -1); |
86 | return stringBuilder.toString(); | 126 | return stringBuilder.toString(); |
87 | } | 127 | } |
88 | public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {} | ||
89 | 128 | ||
129 | public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) { | ||
130 | } | ||
90 | } | 131 | } |
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 new file mode 100644 index 00000000..1c3ab27b --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/StateBasedVersionedMapStoreFactory.java | |||
@@ -0,0 +1,38 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.internal; | ||
7 | |||
8 | import tools.refinery.store.map.*; | ||
9 | |||
10 | import java.util.List; | ||
11 | |||
12 | public class StateBasedVersionedMapStoreFactory<K, V> implements VersionedMapStoreFactory<K, V> { | ||
13 | private final V defaultValue; | ||
14 | private final ContinousHashProvider<K> continousHashProvider; | ||
15 | private final VersionedMapStoreConfiguration config; | ||
16 | |||
17 | public StateBasedVersionedMapStoreFactory(V defaultValue, Boolean transformToImmutable, VersionedMapStoreFactoryBuilder.SharingStrategy sharingStrategy, ContinousHashProvider<K> continousHashProvider) { | ||
18 | this.defaultValue = defaultValue; | ||
19 | this.continousHashProvider = continousHashProvider; | ||
20 | |||
21 | this.config = new VersionedMapStoreConfiguration( | ||
22 | transformToImmutable, | ||
23 | sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE || sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP, | ||
24 | sharingStrategy == VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE_IN_GROUP); | ||
25 | } | ||
26 | |||
27 | @Override | ||
28 | public VersionedMapStore<K, V> createOne() { | ||
29 | return new VersionedMapStoreImpl<>(continousHashProvider, defaultValue, config); | ||
30 | |||
31 | } | ||
32 | |||
33 | @Override | ||
34 | public List<VersionedMapStore<K, V>> createGroup(int amount) { | ||
35 | return VersionedMapStoreImpl.createSharedVersionedMapStores(amount, continousHashProvider, defaultValue, | ||
36 | config); | ||
37 | } | ||
38 | } | ||
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java new file mode 100644 index 00000000..ba59cfef --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaArrayStore.java | |||
@@ -0,0 +1,36 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.internal; | ||
7 | |||
8 | import java.util.ArrayList; | ||
9 | import java.util.List; | ||
10 | |||
11 | public class UncommittedDeltaArrayStore<K, V> implements UncommittedDeltaStore<K, V> { | ||
12 | final List<MapDelta<K, V>> uncommittedOldValues = new ArrayList<>(); | ||
13 | |||
14 | @Override | ||
15 | public void processChange(K key, V oldValue, V newValue) { | ||
16 | uncommittedOldValues.add(new MapDelta<>(key, oldValue, newValue)); | ||
17 | } | ||
18 | |||
19 | @Override | ||
20 | public MapDelta<K, V>[] extractDeltas() { | ||
21 | if (uncommittedOldValues.isEmpty()) { | ||
22 | return null; | ||
23 | } else { | ||
24 | @SuppressWarnings("unchecked") | ||
25 | MapDelta<K, V>[] result = uncommittedOldValues.toArray(new MapDelta[0]); | ||
26 | return result; | ||
27 | } | ||
28 | } | ||
29 | |||
30 | @Override | ||
31 | public MapDelta<K, V>[] extractAndDeleteDeltas() { | ||
32 | MapDelta<K, V>[] res = extractDeltas(); | ||
33 | this.uncommittedOldValues.clear(); | ||
34 | return res; | ||
35 | } | ||
36 | } | ||
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java new file mode 100644 index 00000000..61a34351 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaMapStore.java | |||
@@ -0,0 +1,53 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.internal; | ||
7 | |||
8 | import java.util.*; | ||
9 | import java.util.Map.Entry; | ||
10 | |||
11 | import tools.refinery.store.map.VersionedMap; | ||
12 | |||
13 | public class UncommittedDeltaMapStore<K, V> implements UncommittedDeltaStore<K, V> { | ||
14 | final VersionedMap<K, V> source; | ||
15 | final Map<K, V> uncommittedOldValues = new HashMap<>(); | ||
16 | |||
17 | public UncommittedDeltaMapStore(VersionedMap<K, V> source) { | ||
18 | this.source = source; | ||
19 | } | ||
20 | |||
21 | @Override | ||
22 | public void processChange(K key, V oldValue, V newValue) { | ||
23 | if(!uncommittedOldValues.containsKey(key)) { | ||
24 | this.uncommittedOldValues.put(key,oldValue); | ||
25 | } | ||
26 | } | ||
27 | |||
28 | @Override | ||
29 | public MapDelta<K, V>[] extractDeltas() { | ||
30 | if (uncommittedOldValues.isEmpty()) { | ||
31 | return null; | ||
32 | } else { | ||
33 | @SuppressWarnings("unchecked") | ||
34 | MapDelta<K,V>[] deltas = new MapDelta[uncommittedOldValues.size()]; | ||
35 | int i = 0; | ||
36 | for (Entry<K, V> entry : uncommittedOldValues.entrySet()) { | ||
37 | final K key = entry.getKey(); | ||
38 | final V oldValue = entry.getValue(); | ||
39 | final V newValue = source.get(key); | ||
40 | deltas[i++] = new MapDelta<>(key, oldValue, newValue); | ||
41 | } | ||
42 | |||
43 | return deltas; | ||
44 | } | ||
45 | } | ||
46 | |||
47 | @Override | ||
48 | public MapDelta<K, V>[] extractAndDeleteDeltas() { | ||
49 | MapDelta<K, V>[] res = extractDeltas(); | ||
50 | this.uncommittedOldValues.clear(); | ||
51 | return res; | ||
52 | } | ||
53 | } | ||
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java new file mode 100644 index 00000000..438b5561 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/UncommittedDeltaStore.java | |||
@@ -0,0 +1,29 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.internal; | ||
7 | |||
8 | public interface UncommittedDeltaStore<K, V> { | ||
9 | void processChange(K key, V oldValue, V newValue); | ||
10 | |||
11 | MapDelta<K, V>[] extractDeltas(); | ||
12 | |||
13 | MapDelta<K, V>[] extractAndDeleteDeltas(); | ||
14 | |||
15 | default void checkIntegrity() { | ||
16 | MapDelta<K, V>[] extractedDeltas = extractDeltas(); | ||
17 | if(extractedDeltas != null) { | ||
18 | for(var uncommittedOldValue : extractedDeltas) { | ||
19 | if(uncommittedOldValue == null) { | ||
20 | throw new IllegalArgumentException("Null entry in deltas!"); | ||
21 | } | ||
22 | if(uncommittedOldValue.getKey() == null) { | ||
23 | throw new IllegalStateException("Null key in deltas!"); | ||
24 | } | ||
25 | } | ||
26 | } | ||
27 | } | ||
28 | |||
29 | } | ||
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java new file mode 100644 index 00000000..ae47feda --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapDeltaImpl.java | |||
@@ -0,0 +1,219 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.internal; | ||
7 | |||
8 | import java.util.*; | ||
9 | |||
10 | import tools.refinery.store.map.*; | ||
11 | |||
12 | public class VersionedMapDeltaImpl<K, V> implements VersionedMap<K, V> { | ||
13 | protected final VersionedMapStoreDeltaImpl<K, V> store; | ||
14 | |||
15 | final Map<K, V> current; | ||
16 | |||
17 | final UncommittedDeltaStore<K, V> uncommittedStore; | ||
18 | MapTransaction<K, V> previous; | ||
19 | |||
20 | protected final V defaultValue; | ||
21 | |||
22 | public VersionedMapDeltaImpl(VersionedMapStoreDeltaImpl<K, V> store, boolean summarizeChanges, V defaultValue) { | ||
23 | this.store = store; | ||
24 | this.defaultValue = defaultValue; | ||
25 | |||
26 | current = new HashMap<>(); | ||
27 | if (summarizeChanges) { | ||
28 | this.uncommittedStore = new UncommittedDeltaMapStore<>(this); | ||
29 | } else { | ||
30 | this.uncommittedStore = new UncommittedDeltaArrayStore<>(); | ||
31 | } | ||
32 | } | ||
33 | |||
34 | @Override | ||
35 | public V getDefaultValue() { | ||
36 | return defaultValue; | ||
37 | } | ||
38 | |||
39 | @Override | ||
40 | public long commit() { | ||
41 | MapDelta<K, V>[] deltas = uncommittedStore.extractAndDeleteDeltas(); | ||
42 | long[] versionContainer = new long[1]; | ||
43 | this.previous = this.store.appendTransaction(deltas, previous, versionContainer); | ||
44 | return versionContainer[0]; | ||
45 | } | ||
46 | |||
47 | @Override | ||
48 | public void restore(long state) { | ||
49 | // 1. restore uncommitted states | ||
50 | MapDelta<K, V>[] uncommitted = this.uncommittedStore.extractAndDeleteDeltas(); | ||
51 | if (uncommitted != null) { | ||
52 | backward(uncommitted); | ||
53 | } | ||
54 | |||
55 | // 2. get common ancestor | ||
56 | final MapTransaction<K,V> parent; | ||
57 | List<MapDelta<K, V>[]> forward = new ArrayList<>(); | ||
58 | if (this.previous == null) { | ||
59 | parent = this.store.getPath(state, forward); | ||
60 | this.forward(forward); | ||
61 | } else { | ||
62 | List<MapDelta<K, V>[]> backward = new ArrayList<>(); | ||
63 | parent = this.store.getPath(this.previous.version(), state, backward, forward); | ||
64 | this.backward(backward); | ||
65 | this.forward(forward); | ||
66 | } | ||
67 | this.previous = parent; | ||
68 | } | ||
69 | |||
70 | protected void forward(List<MapDelta<K, V>[]> changes) { | ||
71 | for (int i = changes.size() - 1; i >= 0; i--) { | ||
72 | forward(changes.get(i)); | ||
73 | } | ||
74 | } | ||
75 | |||
76 | protected void backward(List<MapDelta<K, V>[]> changes) { | ||
77 | for (int i = 0; i < changes.size(); i++) { | ||
78 | backward(changes.get(i)); | ||
79 | } | ||
80 | } | ||
81 | |||
82 | protected void forward(MapDelta<K, V>[] changes) { | ||
83 | for (int i = 0; i < changes.length; i++) { | ||
84 | final MapDelta<K, V> change = changes[i]; | ||
85 | K key = change.getKey(); | ||
86 | V newValue = change.getNewValue(); | ||
87 | |||
88 | if(newValue == defaultValue) { | ||
89 | current.remove(key); | ||
90 | } else { | ||
91 | current.put(key,newValue); | ||
92 | } | ||
93 | } | ||
94 | } | ||
95 | |||
96 | protected void backward(MapDelta<K, V>[] changes) { | ||
97 | for (int i = changes.length - 1; i >= 0; i--) { | ||
98 | final MapDelta<K, V> change = changes[i]; | ||
99 | K key = change.getKey(); | ||
100 | V oldValue = change.oldValue(); | ||
101 | |||
102 | if(oldValue == defaultValue) { | ||
103 | current.remove(key); | ||
104 | } else { | ||
105 | current.put(key,oldValue); | ||
106 | } | ||
107 | } | ||
108 | } | ||
109 | |||
110 | @Override | ||
111 | public V get(K key) { | ||
112 | return current.getOrDefault(key, defaultValue); | ||
113 | } | ||
114 | |||
115 | @Override | ||
116 | public Cursor<K, V> getAll() { | ||
117 | return new IteratorAsCursor<>(this, current); | ||
118 | } | ||
119 | |||
120 | @Override | ||
121 | public V put(K key, V value) { | ||
122 | final V oldValue; | ||
123 | if (Objects.equals(value, defaultValue)) { | ||
124 | final V res = current.remove(key); | ||
125 | if (res == null) { | ||
126 | // no changes: default > default | ||
127 | oldValue = defaultValue; | ||
128 | } else { | ||
129 | oldValue = res; | ||
130 | } | ||
131 | } else { | ||
132 | final var mapValue = current.put(key, value); | ||
133 | if (mapValue == null) { | ||
134 | oldValue = defaultValue; | ||
135 | } else { | ||
136 | oldValue = mapValue; | ||
137 | } | ||
138 | } | ||
139 | if(!Objects.equals(oldValue,value)) { | ||
140 | uncommittedStore.processChange(key, oldValue, value); | ||
141 | } | ||
142 | return oldValue; | ||
143 | } | ||
144 | |||
145 | @Override | ||
146 | public void putAll(Cursor<K, V> cursor) { | ||
147 | if (cursor.getDependingMaps().contains(this)) { | ||
148 | List<K> keys = new ArrayList<>(); | ||
149 | List<V> values = new ArrayList<>(); | ||
150 | while (cursor.move()) { | ||
151 | keys.add(cursor.getKey()); | ||
152 | values.add(cursor.getValue()); | ||
153 | } | ||
154 | for (int i = 0; i < keys.size(); i++) { | ||
155 | this.put(keys.get(i), values.get(i)); | ||
156 | } | ||
157 | } else { | ||
158 | while (cursor.move()) { | ||
159 | this.put(cursor.getKey(), cursor.getValue()); | ||
160 | } | ||
161 | } | ||
162 | } | ||
163 | |||
164 | @Override | ||
165 | public long getSize() { | ||
166 | return current.size(); | ||
167 | } | ||
168 | |||
169 | @Override | ||
170 | public DiffCursor<K, V> getDiffCursor(long state) { | ||
171 | MapDelta<K, V>[] backward = this.uncommittedStore.extractDeltas(); | ||
172 | List<MapDelta<K, V>[]> backwardTransactions = new ArrayList<>(); | ||
173 | List<MapDelta<K, V>[]> forwardTransactions = new ArrayList<>(); | ||
174 | |||
175 | if (backward != null) { | ||
176 | backwardTransactions.add(backward); | ||
177 | } | ||
178 | |||
179 | if (this.previous != null) { | ||
180 | store.getPath(this.previous.version(), state, backwardTransactions, forwardTransactions); | ||
181 | } else { | ||
182 | store.getPath(state, forwardTransactions); | ||
183 | } | ||
184 | |||
185 | return new DeltaDiffCursor<>(backwardTransactions, forwardTransactions); | ||
186 | } | ||
187 | |||
188 | @Override | ||
189 | public int contentHashCode(ContentHashCode mode) { | ||
190 | return this.current.hashCode(); | ||
191 | } | ||
192 | |||
193 | @Override | ||
194 | public boolean contentEquals(AnyVersionedMap other) { | ||
195 | if (other instanceof VersionedMapDeltaImpl<?, ?> versioned) { | ||
196 | if (versioned == this) { | ||
197 | return true; | ||
198 | } else { | ||
199 | return Objects.equals(this.defaultValue, versioned.defaultValue) && Objects.equals(this.current, versioned.current); | ||
200 | } | ||
201 | } else { | ||
202 | throw new UnsupportedOperationException("Comparing different map implementations is ineffective."); | ||
203 | } | ||
204 | } | ||
205 | |||
206 | @Override | ||
207 | public void checkIntegrity() { | ||
208 | this.uncommittedStore.checkIntegrity(); | ||
209 | |||
210 | for (var entry : this.current.entrySet()) { | ||
211 | var value = entry.getValue(); | ||
212 | if (value == this.defaultValue) { | ||
213 | throw new IllegalStateException("Default value stored in map!"); | ||
214 | } else if (value == null) { | ||
215 | throw new IllegalStateException("null value stored in map!"); | ||
216 | } | ||
217 | } | ||
218 | } | ||
219 | } | ||
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 index 7abece0d..c107f7e0 100644 --- 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 | |||
@@ -23,7 +23,6 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> { | |||
23 | protected final VersionedMapStoreImpl<K, V> store; | 23 | protected final VersionedMapStoreImpl<K, V> store; |
24 | 24 | ||
25 | protected final ContinousHashProvider<K> hashProvider; | 25 | protected final ContinousHashProvider<K> hashProvider; |
26 | |||
27 | protected final V defaultValue; | 26 | protected final V defaultValue; |
28 | protected Node<K, V> root; | 27 | protected Node<K, V> root; |
29 | 28 | ||
@@ -49,6 +48,7 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> { | |||
49 | this.root = data; | 48 | this.root = data; |
50 | } | 49 | } |
51 | 50 | ||
51 | @Override | ||
52 | public V getDefaultValue() { | 52 | public V getDefaultValue() { |
53 | return defaultValue; | 53 | return defaultValue; |
54 | } | 54 | } |
@@ -80,7 +80,9 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> { | |||
80 | Iterator<K> keyIterator = keys.iterator(); | 80 | Iterator<K> keyIterator = keys.iterator(); |
81 | Iterator<V> valueIterator = values.iterator(); | 81 | Iterator<V> valueIterator = values.iterator(); |
82 | while (keyIterator.hasNext()) { | 82 | while (keyIterator.hasNext()) { |
83 | this.put(keyIterator.next(), valueIterator.next()); | 83 | var key = keyIterator.next(); |
84 | var value = valueIterator.next(); | ||
85 | this.put(key,value); | ||
84 | } | 86 | } |
85 | } else { | 87 | } else { |
86 | while (cursor.move()) { | 88 | while (cursor.move()) { |
@@ -114,11 +116,10 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> { | |||
114 | 116 | ||
115 | @Override | 117 | @Override |
116 | public DiffCursor<K, V> getDiffCursor(long toVersion) { | 118 | public DiffCursor<K, V> getDiffCursor(long toVersion) { |
117 | Cursor<K, V> fromCursor = this.getAll(); | 119 | InOrderMapCursor<K, V> fromCursor = new InOrderMapCursor<>(this); |
118 | VersionedMap<K, V> toMap = this.store.createMap(toVersion); | 120 | VersionedMapImpl<K, V> toMap = (VersionedMapImpl<K, V>) this.store.createMap(toVersion); |
119 | Cursor<K, V> toCursor = toMap.getAll(); | 121 | InOrderMapCursor<K, V> toCursor = new InOrderMapCursor<>(toMap); |
120 | return new MapDiffCursor<>(this.hashProvider, this.defaultValue, fromCursor, toCursor); | 122 | return new MapDiffCursor<>(this.defaultValue, fromCursor, toCursor); |
121 | |||
122 | } | 123 | } |
123 | 124 | ||
124 | 125 | ||
@@ -136,16 +137,17 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> { | |||
136 | root = this.store.revert(state); | 137 | root = this.store.revert(state); |
137 | } | 138 | } |
138 | 139 | ||
139 | public void prettyPrint() { | 140 | public String prettyPrint() { |
140 | StringBuilder s = new StringBuilder(); | ||
141 | if (this.root != null) { | 141 | if (this.root != null) { |
142 | StringBuilder s = new StringBuilder(); | ||
142 | this.root.prettyPrint(s, 0, -1); | 143 | this.root.prettyPrint(s, 0, -1); |
143 | System.out.println(s.toString()); | 144 | return s.toString(); |
144 | } else { | 145 | } else { |
145 | System.out.println("empty tree"); | 146 | return "empty tree"; |
146 | } | 147 | } |
147 | } | 148 | } |
148 | 149 | ||
150 | @Override | ||
149 | public void checkIntegrity() { | 151 | public void checkIntegrity() { |
150 | if (this.root != null) { | 152 | if (this.root != null) { |
151 | this.root.checkIntegrity(hashProvider, defaultValue, 0); | 153 | this.root.checkIntegrity(hashProvider, defaultValue, 0); |
@@ -155,7 +157,11 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> { | |||
155 | @Override | 157 | @Override |
156 | public int contentHashCode(ContentHashCode mode) { | 158 | public int contentHashCode(ContentHashCode mode) { |
157 | // Calculating the root hashCode is always fast, because {@link Node} caches its hashCode. | 159 | // Calculating the root hashCode is always fast, because {@link Node} caches its hashCode. |
158 | return Objects.hashCode(root); | 160 | if(root == null) { |
161 | return 0; | ||
162 | } else { | ||
163 | return root.hashCode(); | ||
164 | } | ||
159 | } | 165 | } |
160 | 166 | ||
161 | @Override | 167 | @Override |
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 new file mode 100644 index 00000000..cf117d95 --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapStoreFactoryBuilderImpl.java | |||
@@ -0,0 +1,137 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.internal; | ||
7 | |||
8 | import tools.refinery.store.map.ContinousHashProvider; | ||
9 | import tools.refinery.store.map.VersionedMapStoreFactory; | ||
10 | import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; | ||
11 | |||
12 | public class VersionedMapStoreFactoryBuilderImpl<K, V> implements VersionedMapStoreFactoryBuilder<K, V> { | ||
13 | |||
14 | private boolean defaultSet = false; | ||
15 | private V defaultValue; | ||
16 | private StoreStrategy strategy = null; | ||
17 | private Boolean transformToImmutable = null; | ||
18 | private SharingStrategy sharingStrategy = null; | ||
19 | private ContinousHashProvider<K> continousHashProvider = null; | ||
20 | private DeltaTransactionStrategy deltaTransactionStrategy = null; | ||
21 | |||
22 | private StoreStrategy checkStrategy() { | ||
23 | StoreStrategy currentStrategy = strategy; | ||
24 | currentStrategy = mergeStrategies(currentStrategy, transformToImmutable, StoreStrategy.STATE); | ||
25 | currentStrategy = mergeStrategies(currentStrategy, sharingStrategy, StoreStrategy.STATE); | ||
26 | currentStrategy = mergeStrategies(currentStrategy, continousHashProvider, StoreStrategy.STATE); | ||
27 | currentStrategy = mergeStrategies(currentStrategy, deltaTransactionStrategy, StoreStrategy.DELTA); | ||
28 | return currentStrategy; | ||
29 | } | ||
30 | |||
31 | private StoreStrategy mergeStrategies(StoreStrategy old, StoreStrategy newStrategy) { | ||
32 | if (old != null && newStrategy != null && old != newStrategy) { | ||
33 | throw new IllegalArgumentException("Mixed strategy parametrization in VersionedMap builder!"); | ||
34 | } | ||
35 | |||
36 | if (old != null) { | ||
37 | return old; | ||
38 | } else { | ||
39 | return newStrategy; | ||
40 | } | ||
41 | } | ||
42 | |||
43 | private StoreStrategy mergeStrategies(StoreStrategy old, Object parameter, StoreStrategy newStrategy) { | ||
44 | if (parameter != null) { | ||
45 | return mergeStrategies(old, newStrategy); | ||
46 | } else { | ||
47 | return old; | ||
48 | } | ||
49 | } | ||
50 | |||
51 | @Override | ||
52 | public VersionedMapStoreFactoryBuilder<K, V> defaultValue(V defaultValue) { | ||
53 | this.defaultSet = true; | ||
54 | this.defaultValue = defaultValue; | ||
55 | return this; | ||
56 | } | ||
57 | |||
58 | @Override | ||
59 | public VersionedMapStoreFactoryBuilder<K, V> strategy(StoreStrategy strategy) { | ||
60 | this.strategy = strategy; | ||
61 | checkStrategy(); | ||
62 | return this; | ||
63 | } | ||
64 | |||
65 | @Override | ||
66 | public VersionedMapStoreFactoryBuilder<K, V> stateBasedImmutableWhenCommitting(boolean transformToImmutable) { | ||
67 | this.transformToImmutable = transformToImmutable; | ||
68 | checkStrategy(); | ||
69 | return this; | ||
70 | } | ||
71 | |||
72 | @Override | ||
73 | public VersionedMapStoreFactoryBuilder<K, V> stateBasedSharingStrategy(SharingStrategy sharingStrategy) { | ||
74 | this.sharingStrategy = sharingStrategy; | ||
75 | checkStrategy(); | ||
76 | return this; | ||
77 | } | ||
78 | |||
79 | @Override | ||
80 | public VersionedMapStoreFactoryBuilder<K, V> stateBasedHashProvider(ContinousHashProvider<K> hashProvider) { | ||
81 | this.continousHashProvider = hashProvider; | ||
82 | checkStrategy(); | ||
83 | return this; | ||
84 | } | ||
85 | |||
86 | @Override | ||
87 | public VersionedMapStoreFactoryBuilder<K, V> deltaTransactionStrategy(DeltaTransactionStrategy deltaTransactionStrategy) { | ||
88 | this.deltaTransactionStrategy = deltaTransactionStrategy; | ||
89 | checkStrategy(); | ||
90 | return this; | ||
91 | } | ||
92 | |||
93 | private <T> T getOrDefault(T value, T defaultValue) { | ||
94 | if(value != null) { | ||
95 | return value; | ||
96 | } else { | ||
97 | return defaultValue; | ||
98 | } | ||
99 | } | ||
100 | |||
101 | @Override | ||
102 | public VersionedMapStoreFactory<K, V> build() { | ||
103 | if (!defaultSet) { | ||
104 | throw new IllegalArgumentException("Default value is missing!"); | ||
105 | } | ||
106 | var strategyToUse = checkStrategy(); | ||
107 | if (strategyToUse == null) { | ||
108 | return new DeltaBasedVersionedMapStoreFactory<>(defaultValue, | ||
109 | getOrDefault(deltaTransactionStrategy, DeltaTransactionStrategy.LIST)); | ||
110 | } | ||
111 | return switch (strategyToUse) { | ||
112 | case STATE -> { | ||
113 | if(continousHashProvider == null) { | ||
114 | throw new IllegalArgumentException("Continuous hash provider is missing!"); | ||
115 | } | ||
116 | yield new StateBasedVersionedMapStoreFactory<>(defaultValue, | ||
117 | getOrDefault(transformToImmutable,true), | ||
118 | getOrDefault(sharingStrategy, SharingStrategy.SHARED_NODE_CACHE_IN_GROUP), | ||
119 | continousHashProvider); | ||
120 | } | ||
121 | case DELTA -> new DeltaBasedVersionedMapStoreFactory<>(defaultValue, | ||
122 | getOrDefault(deltaTransactionStrategy, DeltaTransactionStrategy.LIST)); | ||
123 | }; | ||
124 | } | ||
125 | |||
126 | @Override | ||
127 | public String toString() { | ||
128 | return "VersionedMapStoreBuilder{" + | ||
129 | "defaultValue=" + defaultValue + | ||
130 | ", strategy=" + strategy + | ||
131 | ", stateBasedImmutableWhenCommitting=" + transformToImmutable + | ||
132 | ", stateBasedNodeSharingStrategy=" + sharingStrategy + | ||
133 | ", hashProvider=" + continousHashProvider + | ||
134 | ", deltaStorageStrategy=" + deltaTransactionStrategy + | ||
135 | '}'; | ||
136 | } | ||
137 | } | ||
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 fe1c2ab5..fdd4425e 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 | |||
@@ -7,39 +7,43 @@ package tools.refinery.store.model; | |||
7 | 7 | ||
8 | import tools.refinery.store.map.ContinousHashProvider; | 8 | import tools.refinery.store.map.ContinousHashProvider; |
9 | import tools.refinery.store.tuple.Tuple; | 9 | import tools.refinery.store.tuple.Tuple; |
10 | import tools.refinery.store.tuple.Tuple1; | ||
11 | import tools.refinery.store.tuple.Tuple2; | ||
10 | 12 | ||
11 | public class TupleHashProvider implements ContinousHashProvider<Tuple> { | 13 | public class TupleHashProvider implements ContinousHashProvider<Tuple> { |
12 | protected static final int[] primes = new int[] { 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, | 14 | protected static final int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, |
13 | 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, | 15 | 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, |
14 | 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, | 16 | 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, |
15 | 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, | 17 | 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, |
16 | 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, | 18 | 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, |
17 | 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, | 19 | 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, |
18 | 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, | 20 | 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, |
19 | 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, | 21 | 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, |
20 | 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, | 22 | 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, |
21 | 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, | 23 | 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, |
22 | 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, | 24 | 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, |
23 | 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, | 25 | 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, |
24 | 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, | 26 | 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, |
25 | 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, | 27 | 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, |
26 | 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, | 28 | 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, |
27 | 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, | 29 | 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, |
28 | 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, | 30 | 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, |
29 | 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, | 31 | 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, |
30 | 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, | 32 | 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, |
31 | 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, | 33 | 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, |
32 | 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, | 34 | 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, |
33 | 2797, 2801, 2803, 2819, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, | 35 | 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, |
34 | 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, | 36 | 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, |
35 | 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, | 37 | 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, |
36 | 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, | 38 | 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, |
37 | 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, | 39 | 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, |
38 | 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911 }; | 40 | 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, |
41 | 3907, 3911 }; | ||
39 | 42 | ||
40 | public static final long LARGEST_PRIME_30_BITS = 1073741789; | 43 | protected static final long LARGEST_PRIME_30_BITS_LONG = 1073741789; |
41 | 44 | protected static final int LARGEST_PRIME_30_BITS_INTEGER = 1073741789; | |
42 | public static final int MAX_MODEL_SIZE = (int) LARGEST_PRIME_30_BITS; | 45 | protected static final int LARGEST_BINARY_INDEX_1 = LARGEST_PRIME_30_BITS_INTEGER / 4; |
46 | public static final int MAX_MODEL_SIZE = LARGEST_PRIME_30_BITS_INTEGER; | ||
43 | 47 | ||
44 | public static final TupleHashProvider INSTANCE = new TupleHashProvider(); | 48 | public static final TupleHashProvider INSTANCE = new TupleHashProvider(); |
45 | 49 | ||
@@ -52,15 +56,68 @@ public class TupleHashProvider implements ContinousHashProvider<Tuple> { | |||
52 | 56 | ||
53 | @Override | 57 | @Override |
54 | public int getHash(Tuple key, int index) { | 58 | public int getHash(Tuple key, int index) { |
55 | if (index >= primes.length) { | 59 | if(key instanceof Tuple1 t1) { |
56 | throw new IllegalArgumentException("Not enough prime numbers to support index"); | 60 | return t1.value0(); |
61 | } else if(key instanceof Tuple2 t2){ | ||
62 | if(index == 0) { | ||
63 | return murmur3T2(t2.value0(), t2.value1()); | ||
64 | } else if(index == 1) { | ||
65 | return lagrangeT2I0Quick(t2); | ||
66 | } else if(index == 2) { | ||
67 | return lagrangeT2I1Quick(t2); | ||
68 | } else { | ||
69 | return lagrangeTXIX(key, index-1); | ||
70 | } | ||
71 | } else { | ||
72 | return lagrangeTXIX(key, index); | ||
57 | } | 73 | } |
74 | |||
75 | } | ||
76 | |||
77 | private static int lagrangeT2I0Quick(Tuple2 t2) { | ||
78 | int result = 2 * t2.value0() + t2.value1(); | ||
79 | if (result > LARGEST_PRIME_30_BITS_INTEGER) { | ||
80 | return result % LARGEST_PRIME_30_BITS_INTEGER; | ||
81 | } else | ||
82 | return result; | ||
83 | } | ||
84 | private static int lagrangeT2I1Quick(Tuple2 t2) { | ||
85 | int value0 = t2.value0(); | ||
86 | int value1 = t2.value1(); | ||
87 | if(value0 < LARGEST_BINARY_INDEX_1 && value1 < LARGEST_BINARY_INDEX_1) { | ||
88 | return 3* value0 + value1; | ||
89 | } else { | ||
90 | return lagrangeTXIX(t2, 1); | ||
91 | } | ||
92 | } | ||
93 | |||
94 | private static int lagrangeTXIX(Tuple key, int index) { | ||
58 | long accumulator = 0; | 95 | long accumulator = 0; |
59 | final int prime = primes[index]; | 96 | final int prime = primes[index]; |
60 | for (int i = 0; i < key.getSize(); i++) { | 97 | for (int i = 0; i < key.getSize(); i++) { |
61 | accumulator = (prime * accumulator + key.get(i)) % MAX_MODEL_SIZE; | 98 | accumulator = (prime * accumulator + key.get(i)) % LARGEST_PRIME_30_BITS_LONG; |
62 | } | 99 | } |
63 | 100 | ||
64 | return (int) accumulator; | 101 | return (int) accumulator; |
65 | } | 102 | } |
103 | |||
104 | private static int murmur3T2(int v0, int v1) | ||
105 | { | ||
106 | int h = 0; | ||
107 | |||
108 | h = murmur32Scramble(v0, h); | ||
109 | h = murmur32Scramble(v1, h); | ||
110 | |||
111 | return h; | ||
112 | } | ||
113 | |||
114 | private static int murmur32Scramble(int k, int h) { | ||
115 | k *= 0xcc9e2d51; | ||
116 | k = (k << 15) | (k >>> 17); | ||
117 | k *= 0x1b873593; | ||
118 | h ^= k; | ||
119 | h = (h << 13) | (h >>> 19); | ||
120 | h = h * 5 + 0xe6546b64; | ||
121 | return h; | ||
122 | } | ||
66 | } | 123 | } |
diff --git a/subprojects/store/src/main/java/tools/refinery/store/model/internal/VersionedInterpretation.java b/subprojects/store/src/main/java/tools/refinery/store/model/internal/VersionedInterpretation.java index 86101ce3..404be65f 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/model/internal/VersionedInterpretation.java +++ b/subprojects/store/src/main/java/tools/refinery/store/model/internal/VersionedInterpretation.java | |||
@@ -9,11 +9,9 @@ import tools.refinery.store.map.Cursor; | |||
9 | import tools.refinery.store.map.DiffCursor; | 9 | import tools.refinery.store.map.DiffCursor; |
10 | import tools.refinery.store.map.VersionedMap; | 10 | import tools.refinery.store.map.VersionedMap; |
11 | import tools.refinery.store.map.VersionedMapStore; | 11 | import tools.refinery.store.map.VersionedMapStore; |
12 | import tools.refinery.store.map.internal.MapDiffCursor; | ||
13 | import tools.refinery.store.model.Interpretation; | 12 | import tools.refinery.store.model.Interpretation; |
14 | import tools.refinery.store.model.InterpretationListener; | 13 | import tools.refinery.store.model.InterpretationListener; |
15 | import tools.refinery.store.model.Model; | 14 | import tools.refinery.store.model.Model; |
16 | import tools.refinery.store.model.TupleHashProvider; | ||
17 | import tools.refinery.store.representation.AnySymbol; | 15 | import tools.refinery.store.representation.AnySymbol; |
18 | import tools.refinery.store.representation.Symbol; | 16 | import tools.refinery.store.representation.Symbol; |
19 | import tools.refinery.store.tuple.Tuple; | 17 | import tools.refinery.store.tuple.Tuple; |
@@ -24,16 +22,13 @@ import java.util.List; | |||
24 | public class VersionedInterpretation<T> implements Interpretation<T> { | 22 | public class VersionedInterpretation<T> implements Interpretation<T> { |
25 | private final ModelImpl model; | 23 | private final ModelImpl model; |
26 | private final Symbol<T> symbol; | 24 | private final Symbol<T> symbol; |
27 | private final VersionedMapStore<Tuple, T> store; | ||
28 | private final VersionedMap<Tuple, T> map; | 25 | private final VersionedMap<Tuple, T> map; |
29 | private final List<InterpretationListener<T>> listeners = new ArrayList<>(); | 26 | private final List<InterpretationListener<T>> listeners = new ArrayList<>(); |
30 | private final List<InterpretationListener<T>> restoreListeners = new ArrayList<>(); | 27 | private final List<InterpretationListener<T>> restoreListeners = new ArrayList<>(); |
31 | 28 | ||
32 | private VersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMapStore<Tuple, T> store, | 29 | private VersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMap<Tuple, T> map) { |
33 | VersionedMap<Tuple, T> map) { | ||
34 | this.model = model; | 30 | this.model = model; |
35 | this.symbol = symbol; | 31 | this.symbol = symbol; |
36 | this.store = store; | ||
37 | this.map = map; | 32 | this.map = map; |
38 | } | 33 | } |
39 | 34 | ||
@@ -116,9 +111,7 @@ public class VersionedInterpretation<T> implements Interpretation<T> { | |||
116 | 111 | ||
117 | @Override | 112 | @Override |
118 | public DiffCursor<Tuple, T> getDiffCursor(long to) { | 113 | public DiffCursor<Tuple, T> getDiffCursor(long to) { |
119 | var fromCursor = getAll(); | 114 | return map.getDiffCursor(to); |
120 | var toCursor = store.createMap(to).getAll(); | ||
121 | return new MapDiffCursor<>(TupleHashProvider.INSTANCE, symbol.defaultValue(), fromCursor, toCursor); | ||
122 | } | 115 | } |
123 | 116 | ||
124 | public long commit() { | 117 | public long commit() { |
@@ -153,7 +146,7 @@ public class VersionedInterpretation<T> implements Interpretation<T> { | |||
153 | @SuppressWarnings("unchecked") | 146 | @SuppressWarnings("unchecked") |
154 | var typedSymbol = (Symbol<T>) symbol; | 147 | var typedSymbol = (Symbol<T>) symbol; |
155 | var map = store.createMap(); | 148 | var map = store.createMap(); |
156 | return new VersionedInterpretation<>(model, typedSymbol, store, map); | 149 | return new VersionedInterpretation<>(model, typedSymbol, map); |
157 | } | 150 | } |
158 | 151 | ||
159 | static <T> VersionedInterpretation<T> of(ModelImpl model, AnySymbol symbol, VersionedMapStore<Tuple, T> store, | 152 | static <T> VersionedInterpretation<T> of(ModelImpl model, AnySymbol symbol, VersionedMapStore<Tuple, T> store, |
@@ -161,6 +154,6 @@ public class VersionedInterpretation<T> implements Interpretation<T> { | |||
161 | @SuppressWarnings("unchecked") | 154 | @SuppressWarnings("unchecked") |
162 | var typedSymbol = (Symbol<T>) symbol; | 155 | var typedSymbol = (Symbol<T>) symbol; |
163 | var map = store.createMap(state); | 156 | var map = store.createMap(state); |
164 | return new VersionedInterpretation<>(model, typedSymbol, store, map); | 157 | return new VersionedInterpretation<>(model, typedSymbol, map); |
165 | } | 158 | } |
166 | } | 159 | } |
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 new file mode 100644 index 00000000..4ada4ea4 --- /dev/null +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java | |||
@@ -0,0 +1,56 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.tests; | ||
7 | |||
8 | import org.junit.jupiter.api.Test; | ||
9 | import tools.refinery.store.map.VersionedMapStore; | ||
10 | import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; | ||
11 | import tools.refinery.store.map.internal.InOrderMapCursor; | ||
12 | import tools.refinery.store.map.internal.VersionedMapImpl; | ||
13 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; | ||
14 | |||
15 | import static org.junit.jupiter.api.Assertions.*; | ||
16 | |||
17 | class InOrderCursorTest { | ||
18 | @Test | ||
19 | void testCursor() { | ||
20 | var store = VersionedMapStore.<Integer,String>builder() | ||
21 | .strategy(VersionedMapStoreFactoryBuilder.StoreStrategy.STATE) | ||
22 | .stateBasedImmutableWhenCommitting(true) | ||
23 | .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(false)) | ||
24 | .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE) | ||
25 | .defaultValue("x") | ||
26 | .build() | ||
27 | .createOne(); | ||
28 | |||
29 | VersionedMapImpl<Integer,String> map = (VersionedMapImpl<Integer,String>) store.createMap(); | ||
30 | checkMove(map,0); | ||
31 | |||
32 | map.put(1,"A"); | ||
33 | map.commit(); | ||
34 | checkMove(map,1); | ||
35 | |||
36 | |||
37 | map.put(2,"B"); | ||
38 | map.commit(); | ||
39 | checkMove(map,2); | ||
40 | |||
41 | map.put(3,"C"); | ||
42 | map.commit(); | ||
43 | checkMove(map,3); | ||
44 | |||
45 | } | ||
46 | |||
47 | private void checkMove(VersionedMapImpl<Integer,String> map, int num) { | ||
48 | InOrderMapCursor<Integer,String> cursor = new InOrderMapCursor<>(map); | ||
49 | for(int i=0; i<num; i++) { | ||
50 | assertTrue(cursor.move()); | ||
51 | assertFalse(cursor.isTerminated()); | ||
52 | } | ||
53 | assertFalse(cursor.move()); | ||
54 | assertTrue(cursor.isTerminated()); | ||
55 | } | ||
56 | } | ||
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/MapUnitTests.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/MapUnitTests.java index 153f2e78..2be49bd9 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/MapUnitTests.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/MapUnitTests.java | |||
@@ -23,4 +23,75 @@ class MapUnitTests { | |||
23 | var out2 = map.put(Tuple.of(1), true); | 23 | var out2 = map.put(Tuple.of(1), true); |
24 | assertEquals(false, out2); | 24 | assertEquals(false, out2); |
25 | } | 25 | } |
26 | |||
27 | @Test | ||
28 | void deltaRestoreTest() { | ||
29 | VersionedMapStore<Integer,String> store = | ||
30 | VersionedMapStore.<Integer,String>builder().defaultValue("x").build().createOne(); | ||
31 | var map = store.createMap(); | ||
32 | map.put(1,"val"); | ||
33 | var version1 = map.commit(); | ||
34 | map.put(1,"x"); | ||
35 | map.restore(version1); | ||
36 | System.out.println(map.getSize()); | ||
37 | assertEquals(1,map.getSize()); | ||
38 | } | ||
39 | |||
40 | @Test | ||
41 | void deltaRestoreTest2() { | ||
42 | VersionedMapStore<Integer,String> store = | ||
43 | VersionedMapStore.<Integer,String>builder().defaultValue("x").build().createOne(); | ||
44 | var map = store.createMap(); | ||
45 | map.put(1,"x"); | ||
46 | var version1 = map.commit(); | ||
47 | map.put(1,"1"); | ||
48 | map.restore(version1); | ||
49 | System.out.println(map.getSize()); | ||
50 | assertEquals(0,map.getSize()); | ||
51 | } | ||
52 | @Test | ||
53 | void deltaRestoreTest3() { | ||
54 | VersionedMapStore<Integer,String> store = | ||
55 | VersionedMapStore.<Integer,String>builder().defaultValue("x").build().createOne(); | ||
56 | var map = store.createMap(); | ||
57 | map.commit(); | ||
58 | map.put(1,"1"); | ||
59 | map.put(2,"x"); | ||
60 | assertEquals(1,map.getSize()); | ||
61 | var version1 = map.commit(); | ||
62 | map.put(1,"x"); | ||
63 | assertEquals(0,map.getSize()); | ||
64 | map.put(2,"2"); | ||
65 | assertEquals(1,map.getSize()); | ||
66 | map.put(2,"x"); | ||
67 | assertEquals(0,map.getSize()); | ||
68 | var version2 = map.commit(); | ||
69 | map.restore(version1); | ||
70 | assertEquals(1,map.getSize()); | ||
71 | map.restore(version2); | ||
72 | assertEquals(0,map.getSize()); | ||
73 | } | ||
74 | |||
75 | @Test | ||
76 | void deltaRestoreTest4() { | ||
77 | VersionedMapStore<Integer,String> store = | ||
78 | VersionedMapStore.<Integer,String>builder().defaultValue("x").build().createOne(); | ||
79 | var map = store.createMap(); | ||
80 | map.commit(); | ||
81 | map.put(1,"1"); | ||
82 | map.put(2,"x"); | ||
83 | assertEquals(1,map.getSize()); | ||
84 | var version1 = map.commit(); | ||
85 | map.put(1,"x"); | ||
86 | assertEquals(0,map.getSize()); | ||
87 | map.put(2,"2"); | ||
88 | assertEquals(1,map.getSize()); | ||
89 | map.put(2,"x"); | ||
90 | assertEquals(0,map.getSize()); | ||
91 | var version2 = map.commit(); | ||
92 | map.restore(version1); | ||
93 | assertEquals(1,map.getSize()); | ||
94 | map.restore(version2); | ||
95 | assertEquals(0,map.getSize()); | ||
96 | } | ||
26 | } | 97 | } |
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/CommitFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/CommitFuzzTest.java index eabe5bd1..58206eda 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/CommitFuzzTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/CommitFuzzTest.java | |||
@@ -5,33 +5,32 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.map.tests.fuzz; | 6 | package tools.refinery.store.map.tests.fuzz; |
7 | 7 | ||
8 | import static org.junit.jupiter.api.Assertions.fail; | ||
9 | |||
10 | import java.util.Random; | ||
11 | import java.util.stream.Stream; | ||
12 | |||
13 | import org.junit.jupiter.api.Tag; | 8 | import org.junit.jupiter.api.Tag; |
14 | import org.junit.jupiter.api.Timeout; | 9 | import org.junit.jupiter.api.Timeout; |
15 | import org.junit.jupiter.params.ParameterizedTest; | 10 | import org.junit.jupiter.params.ParameterizedTest; |
16 | import org.junit.jupiter.params.provider.Arguments; | 11 | import org.junit.jupiter.params.provider.Arguments; |
17 | import org.junit.jupiter.params.provider.MethodSource; | 12 | import org.junit.jupiter.params.provider.MethodSource; |
18 | |||
19 | import tools.refinery.store.map.ContinousHashProvider; | ||
20 | import tools.refinery.store.map.VersionedMapStore; | 13 | import tools.refinery.store.map.VersionedMapStore; |
21 | import tools.refinery.store.map.VersionedMapStoreImpl; | 14 | import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; |
22 | import tools.refinery.store.map.internal.VersionedMapImpl; | ||
23 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; | 15 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; |
24 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; | 16 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; |
25 | 17 | ||
18 | import java.util.Random; | ||
19 | import java.util.stream.Stream; | ||
20 | |||
21 | import static org.junit.jupiter.api.Assertions.fail; | ||
22 | import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*; | ||
23 | |||
26 | class CommitFuzzTest { | 24 | class CommitFuzzTest { |
27 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, | ||
28 | boolean evilHash) { | ||
29 | String[] values = MapTestEnvironment.prepareValues(maxValue); | ||
30 | ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash); | ||
31 | 25 | ||
32 | VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]); | 26 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, |
33 | VersionedMapImpl<Integer, String> sut = (VersionedMapImpl<Integer, String>) store.createMap(); | 27 | boolean nullDefault, int commitFrequency, |
34 | MapTestEnvironment<Integer, String> e = new MapTestEnvironment<Integer, String>(sut); | 28 | VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
29 | String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); | ||
30 | |||
31 | VersionedMapStore<Integer, String> store = builder.defaultValue(values[0]).build().createOne(); | ||
32 | var sut = store.createMap(); | ||
33 | MapTestEnvironment<Integer, String> e = new MapTestEnvironment<>(sut); | ||
35 | 34 | ||
36 | Random r = new Random(seed); | 35 | Random r = new Random(seed); |
37 | 36 | ||
@@ -39,24 +38,13 @@ class CommitFuzzTest { | |||
39 | } | 38 | } |
40 | 39 | ||
41 | private void iterativeRandomPutsAndCommits(String scenario, int steps, int maxKey, String[] values, | 40 | private void iterativeRandomPutsAndCommits(String scenario, int steps, int maxKey, String[] values, |
42 | MapTestEnvironment<Integer, String> e, Random r, int commitFrequency) { | 41 | MapTestEnvironment<Integer, String> e, Random r, int commitFrequency) { |
43 | int stopAt = -1; | ||
44 | for (int i = 0; i < steps; i++) { | 42 | for (int i = 0; i < steps; i++) { |
45 | int index = i + 1; | 43 | int index = i + 1; |
46 | int nextKey = r.nextInt(maxKey); | 44 | int nextKey = r.nextInt(maxKey); |
47 | String nextValue = values[r.nextInt(values.length)]; | 45 | String nextValue = values[r.nextInt(values.length)]; |
48 | if (index == stopAt) { | ||
49 | System.out.println("issue!"); | ||
50 | System.out.println("State before:"); | ||
51 | e.printComparison(); | ||
52 | e.sut.prettyPrint(); | ||
53 | System.out.println("Next: put(" + nextKey + "," + nextValue + ")"); | ||
54 | } | ||
55 | try { | 46 | try { |
56 | e.put(nextKey, nextValue); | 47 | e.put(nextKey, nextValue); |
57 | if (index == stopAt) { | ||
58 | e.sut.prettyPrint(); | ||
59 | } | ||
60 | e.checkEquivalence(scenario + ":" + index); | 48 | e.checkEquivalence(scenario + ":" + index); |
61 | } catch (Exception exception) { | 49 | } catch (Exception exception) { |
62 | exception.printStackTrace(); | 50 | exception.printStackTrace(); |
@@ -64,35 +52,37 @@ class CommitFuzzTest { | |||
64 | } | 52 | } |
65 | MapTestEnvironment.printStatus(scenario, index, steps, null); | 53 | MapTestEnvironment.printStatus(scenario, index, steps, null); |
66 | if (index % commitFrequency == 0) { | 54 | if (index % commitFrequency == 0) { |
67 | e.sut.commit(); | 55 | e.commit(); |
68 | } | 56 | } |
69 | } | 57 | } |
70 | } | 58 | } |
71 | 59 | ||
72 | @ParameterizedTest(name = "Commit {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") | 60 | public static final String title = "Commit {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} commit frequency={5} " + |
61 | "seed={6} config={7}"; | ||
62 | |||
63 | @ParameterizedTest(name = title) | ||
73 | @MethodSource | 64 | @MethodSource |
74 | @Timeout(value = 10) | 65 | @Timeout(value = 10) |
75 | @Tag("fuzz") | 66 | @Tag("fuzz") |
76 | void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, | 67 | void parametrizedFastFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, |
77 | boolean evilHash) { | 68 | int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
78 | runFuzzTest("CommitS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, | 69 | runFuzzTest("CommitS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, |
79 | commitFrequency, evilHash); | 70 | nullDefault, commitFrequency, builder); |
80 | } | 71 | } |
81 | 72 | ||
82 | static Stream<Arguments> parametrizedFastFuzz() { | 73 | static Stream<Arguments> parametrizedFastFuzz() { |
83 | return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 }, | 74 | return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions, |
84 | new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 }, | 75 | commitFrequencyOptions, randomSeedOptions, storeConfigs); |
85 | new Object[] { false, true }); | ||
86 | } | 76 | } |
87 | 77 | ||
88 | @ParameterizedTest(name = "Commit {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") | 78 | @ParameterizedTest(name = title) |
89 | @MethodSource | 79 | @MethodSource |
90 | @Tag("fuzz") | 80 | @Tag("fuzz") |
91 | @Tag("slow") | 81 | @Tag("slow") |
92 | void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, | 82 | void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, |
93 | boolean evilHash) { | 83 | int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
94 | runFuzzTest("CommitS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, | 84 | runFuzzTest("CommitS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, |
95 | commitFrequency, evilHash); | 85 | nullDefault, commitFrequency, builder); |
96 | } | 86 | } |
97 | 87 | ||
98 | static Stream<Arguments> parametrizedSlowFuzz() { | 88 | static Stream<Arguments> parametrizedSlowFuzz() { |
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java index b0502a2b..c49911b8 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/ContentEqualsFuzzTest.java | |||
@@ -10,8 +10,10 @@ import org.junit.jupiter.api.Timeout; | |||
10 | import org.junit.jupiter.params.ParameterizedTest; | 10 | import org.junit.jupiter.params.ParameterizedTest; |
11 | import org.junit.jupiter.params.provider.Arguments; | 11 | import org.junit.jupiter.params.provider.Arguments; |
12 | import org.junit.jupiter.params.provider.MethodSource; | 12 | import org.junit.jupiter.params.provider.MethodSource; |
13 | import tools.refinery.store.map.*; | 13 | import tools.refinery.store.map.Cursor; |
14 | import tools.refinery.store.map.internal.VersionedMapImpl; | 14 | import tools.refinery.store.map.VersionedMap; |
15 | import tools.refinery.store.map.VersionedMapStore; | ||
16 | import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; | ||
15 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; | 17 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; |
16 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; | 18 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; |
17 | 19 | ||
@@ -22,23 +24,25 @@ import java.util.List; | |||
22 | import java.util.Random; | 24 | import java.util.Random; |
23 | import java.util.stream.Stream; | 25 | import java.util.stream.Stream; |
24 | 26 | ||
25 | import static org.junit.jupiter.api.Assertions.*; | 27 | import static org.junit.jupiter.api.Assertions.fail; |
28 | import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*; | ||
26 | 29 | ||
27 | class ContentEqualsFuzzTest { | 30 | class ContentEqualsFuzzTest { |
28 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, | 31 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, |
29 | boolean evilHash) { | 32 | boolean nullDefault, int commitFrequency, |
30 | String[] values = MapTestEnvironment.prepareValues(maxValue); | 33 | VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
31 | ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash); | 34 | String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); |
35 | |||
32 | 36 | ||
33 | Random r = new Random(seed); | 37 | Random r = new Random(seed); |
34 | 38 | ||
35 | iterativeRandomPutsAndCommitsThenCompare(scenario, chp, steps, maxKey, values, r, commitFrequency); | 39 | iterativeRandomPutsAndCommitsThenCompare(scenario, builder, steps, maxKey, values, r, commitFrequency); |
36 | } | 40 | } |
37 | 41 | ||
38 | private void iterativeRandomPutsAndCommitsThenCompare(String scenario, ContinousHashProvider<Integer> chp, | 42 | private void iterativeRandomPutsAndCommitsThenCompare(String scenario, VersionedMapStoreFactoryBuilder<Integer, String> builder, |
39 | int steps, int maxKey, String[] values, Random r, | 43 | int steps, int maxKey, String[] values, Random r, |
40 | int commitFrequency) { | 44 | int commitFrequency) { |
41 | VersionedMapStore<Integer, String> store1 = new VersionedMapStoreImpl<Integer, String>(chp, values[0]); | 45 | VersionedMapStore<Integer, String> store1 = builder.defaultValue(values[0]).build().createOne(); |
42 | VersionedMap<Integer, String> sut1 = store1.createMap(); | 46 | VersionedMap<Integer, String> sut1 = store1.createMap(); |
43 | 47 | ||
44 | // Fill one map | 48 | // Fill one map |
@@ -68,7 +72,7 @@ class ContentEqualsFuzzTest { | |||
68 | // Randomize the order of the content | 72 | // Randomize the order of the content |
69 | Collections.shuffle(content, r); | 73 | Collections.shuffle(content, r); |
70 | 74 | ||
71 | VersionedMapStore<Integer, String> store2 = new VersionedMapStoreImpl<Integer, String>(chp, values[0]); | 75 | VersionedMapStore<Integer, String> store2 = builder.defaultValue(values[0]).build().createOne(); |
72 | VersionedMap<Integer, String> sut2 = store2.createMap(); | 76 | VersionedMap<Integer, String> sut2 = store2.createMap(); |
73 | int index2 = 1; | 77 | int index2 = 1; |
74 | for (SimpleEntry<Integer, String> entry : content) { | 78 | for (SimpleEntry<Integer, String> entry : content) { |
@@ -78,40 +82,39 @@ class ContentEqualsFuzzTest { | |||
78 | } | 82 | } |
79 | 83 | ||
80 | // Check the integrity of the maps | 84 | // Check the integrity of the maps |
81 | ((VersionedMapImpl<Integer, String>) sut1).checkIntegrity(); | 85 | sut1.checkIntegrity(); |
82 | ((VersionedMapImpl<Integer, String>) sut2).checkIntegrity(); | 86 | sut2.checkIntegrity(); |
83 | 87 | ||
84 | // Compare the two maps | 88 | // Compare the two maps |
85 | MapTestEnvironment.compareTwoMaps(scenario, sut1, sut2); | 89 | MapTestEnvironment.compareTwoMaps(scenario, sut1, sut2); |
86 | } | 90 | } |
87 | 91 | ||
88 | @ParameterizedTest(name = "Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} " + | 92 | public static final String title = "Compare {index}/{0} Steps={1} Keys={2} Values={3} defaultNull={4} commit frequency={5}" + |
89 | "evil-hash={6}") | 93 | "seed={6} config={7}"; |
94 | |||
95 | @ParameterizedTest(name = title) | ||
90 | @MethodSource | 96 | @MethodSource |
91 | @Timeout(value = 10) | 97 | @Timeout(value = 10) |
92 | @Tag("fuzz") | 98 | @Tag("fuzz") |
93 | void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, | 99 | void parametrizedFastFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, |
94 | boolean evilHash) { | 100 | int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
95 | runFuzzTest("CompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, | 101 | runFuzzTest("CompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, |
96 | commitFrequency, evilHash); | 102 | nullDefault, commitFrequency, builder); |
97 | } | 103 | } |
98 | 104 | ||
99 | static Stream<Arguments> parametrizedFastFuzz() { | 105 | static Stream<Arguments> parametrizedFastFuzz() { |
100 | return FuzzTestUtils.permutationWithSize(new Object[]{FuzzTestUtils.FAST_STEP_COUNT}, new Object[]{3, 32, | 106 | return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions, |
101 | 32 * 32}, | 107 | commitFrequencyOptions, randomSeedOptions, storeConfigs); |
102 | new Object[]{2, 3}, new Object[]{1, 10, 100}, new Object[]{1, 2, 3}, | ||
103 | new Object[]{false, true}); | ||
104 | } | 108 | } |
105 | 109 | ||
106 | @ParameterizedTest(name = "Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} " + | 110 | @ParameterizedTest(name = title) |
107 | "evil-hash={6}") | ||
108 | @MethodSource | 111 | @MethodSource |
109 | @Tag("fuzz") | 112 | @Tag("fuzz") |
110 | @Tag("slow") | 113 | @Tag("slow") |
111 | void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, | 114 | void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean defaultNull, int commitFrequency, |
112 | boolean evilHash) { | 115 | int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
113 | runFuzzTest("CompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, | 116 | runFuzzTest("CompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, |
114 | commitFrequency, evilHash); | 117 | defaultNull, commitFrequency, builder); |
115 | } | 118 | } |
116 | 119 | ||
117 | static Stream<Arguments> parametrizedSlowFuzz() { | 120 | static Stream<Arguments> parametrizedSlowFuzz() { |
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java index 8274336e..5a4f8038 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/DiffCursorFuzzTest.java | |||
@@ -5,115 +5,133 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.map.tests.fuzz; | 6 | package tools.refinery.store.map.tests.fuzz; |
7 | 7 | ||
8 | import static org.junit.jupiter.api.Assertions.fail; | ||
9 | |||
10 | import java.util.Random; | ||
11 | import java.util.stream.Stream; | ||
12 | |||
13 | import org.junit.jupiter.api.Tag; | 8 | import org.junit.jupiter.api.Tag; |
14 | import org.junit.jupiter.api.Timeout; | 9 | import org.junit.jupiter.api.Timeout; |
15 | import org.junit.jupiter.params.ParameterizedTest; | 10 | import org.junit.jupiter.params.ParameterizedTest; |
16 | import org.junit.jupiter.params.provider.Arguments; | 11 | import org.junit.jupiter.params.provider.Arguments; |
17 | import org.junit.jupiter.params.provider.MethodSource; | 12 | import org.junit.jupiter.params.provider.MethodSource; |
18 | |||
19 | import tools.refinery.store.map.ContinousHashProvider; | ||
20 | import tools.refinery.store.map.DiffCursor; | 13 | import tools.refinery.store.map.DiffCursor; |
14 | import tools.refinery.store.map.VersionedMap; | ||
21 | import tools.refinery.store.map.VersionedMapStore; | 15 | import tools.refinery.store.map.VersionedMapStore; |
22 | import tools.refinery.store.map.VersionedMapStoreImpl; | 16 | import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; |
23 | import tools.refinery.store.map.internal.VersionedMapImpl; | ||
24 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; | 17 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; |
25 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; | 18 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; |
26 | 19 | ||
20 | import java.util.Random; | ||
21 | import java.util.stream.Stream; | ||
22 | |||
23 | import static org.junit.jupiter.api.Assertions.fail; | ||
24 | import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*; | ||
25 | |||
27 | class DiffCursorFuzzTest { | 26 | class DiffCursorFuzzTest { |
28 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, | 27 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean nullDefault, |
29 | boolean evilHash) { | 28 | int commitFrequency, boolean commitBeforeDiffCursor, |
30 | String[] values = MapTestEnvironment.prepareValues(maxValue); | 29 | VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
31 | ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash); | 30 | String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); |
32 | 31 | ||
33 | VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]); | 32 | VersionedMapStore<Integer, String> store = builder.defaultValue(values[0]).build().createOne(); |
34 | iterativeRandomPutsAndCommitsThenDiffcursor(scenario, store, steps, maxKey, values, seed, commitFrequency); | 33 | iterativeRandomPutsAndCommitsThenDiffCursor(scenario, store, steps, maxKey, values, seed, commitFrequency, |
34 | commitBeforeDiffCursor); | ||
35 | } | 35 | } |
36 | 36 | ||
37 | private void iterativeRandomPutsAndCommitsThenDiffcursor(String scenario, VersionedMapStore<Integer, String> store, | 37 | private void iterativeRandomPutsAndCommitsThenDiffCursor(String scenario, VersionedMapStore<Integer, String> store, |
38 | int steps, int maxKey, String[] values, int seed, int commitFrequency) { | 38 | int steps, int maxKey, String[] values, int seed, |
39 | // 1. build a map with versions | 39 | int commitFrequency, boolean commitBeforeDiffCursor) { |
40 | Random r = new Random(seed); | 40 | |
41 | VersionedMapImpl<Integer, String> versioned = (VersionedMapImpl<Integer, String>) store.createMap(); | ||
42 | int largestCommit = -1; | 41 | int largestCommit = -1; |
43 | 42 | ||
44 | for (int i = 0; i < steps; i++) { | 43 | { |
45 | int index = i + 1; | 44 | // 1. build a map with versions |
46 | int nextKey = r.nextInt(maxKey); | 45 | Random r = new Random(seed); |
47 | String nextValue = values[r.nextInt(values.length)]; | 46 | VersionedMap<Integer, String> versioned = store.createMap(); |
48 | try { | 47 | for (int i = 0; i < steps; i++) { |
49 | versioned.put(nextKey, nextValue); | 48 | int index = i + 1; |
50 | } catch (Exception exception) { | 49 | int nextKey = r.nextInt(maxKey); |
51 | exception.printStackTrace(); | 50 | String nextValue = values[r.nextInt(values.length)]; |
52 | fail(scenario + ":" + index + ": exception happened: " + exception); | ||
53 | } | ||
54 | if (index % commitFrequency == 0) { | ||
55 | long version = versioned.commit(); | ||
56 | largestCommit = (int) version; | ||
57 | } | ||
58 | if (index % 10000 == 0) | ||
59 | System.out.println(scenario + ":" + index + "/" + steps + " building finished"); | ||
60 | } | ||
61 | // 2. create a non-versioned map, | ||
62 | VersionedMapImpl<Integer, String> moving = (VersionedMapImpl<Integer, String>) store.createMap(); | ||
63 | Random r2 = new Random(seed + 1); | ||
64 | |||
65 | final int diffTravelFrequency = commitFrequency * 2; | ||
66 | for (int i = 0; i < steps; i++) { | ||
67 | int index = i + 1; | ||
68 | if (index % diffTravelFrequency == 0) { | ||
69 | // difftravel | ||
70 | long travelToVersion = r2.nextInt(largestCommit + 1); | ||
71 | DiffCursor<Integer, String> diffCursor = moving.getDiffCursor(travelToVersion); | ||
72 | moving.putAll(diffCursor); | ||
73 | |||
74 | } else { | ||
75 | // random puts | ||
76 | int nextKey = r2.nextInt(maxKey); | ||
77 | String nextValue = values[r2.nextInt(values.length)]; | ||
78 | try { | 51 | try { |
79 | moving.put(nextKey, nextValue); | 52 | versioned.put(nextKey, nextValue); |
80 | } catch (Exception exception) { | 53 | } catch (Exception exception) { |
81 | exception.printStackTrace(); | 54 | exception.printStackTrace(); |
82 | fail(scenario + ":" + index + ": exception happened: " + exception); | 55 | fail(scenario + ":" + index + ": exception happened: " + exception); |
83 | } | 56 | } |
84 | if (index % commitFrequency == 0) { | 57 | if (index % commitFrequency == 0) { |
85 | versioned.commit(); | 58 | long version = versioned.commit(); |
59 | largestCommit = (int) version; | ||
86 | } | 60 | } |
87 | if (index % 10000 == 0) | 61 | if (index % 10000 == 0) |
88 | System.out.println(scenario + ":" + index + "/" + steps + " building finished"); | 62 | System.out.println(scenario + ":" + index + "/" + steps + " building finished"); |
89 | } | 63 | } |
90 | } | 64 | } |
91 | 65 | ||
66 | { | ||
67 | // 2. create a non-versioned map, | ||
68 | VersionedMap<Integer, String> moving = store.createMap(); | ||
69 | Random r2 = new Random(seed + 1); | ||
70 | |||
71 | final int diffTravelFrequency = commitFrequency * 2; | ||
72 | for (int i = 0; i < steps; i++) { | ||
73 | int index = i + 1; | ||
74 | if (index % diffTravelFrequency == 0) { | ||
75 | // diff-travel | ||
76 | long travelToVersion = r2.nextInt(largestCommit + 1); | ||
77 | |||
78 | VersionedMap<Integer, String> oracle = store.createMap(travelToVersion); | ||
79 | |||
80 | if(commitBeforeDiffCursor) { | ||
81 | moving.commit(); | ||
82 | } | ||
83 | DiffCursor<Integer, String> diffCursor = moving.getDiffCursor(travelToVersion); | ||
84 | moving.putAll(diffCursor); | ||
85 | moving.commit(); | ||
86 | |||
87 | MapTestEnvironment.compareTwoMaps(scenario + ":c" + index, oracle, moving); | ||
88 | |||
89 | moving.restore(travelToVersion); | ||
90 | |||
91 | } else { | ||
92 | // random puts | ||
93 | int nextKey = r2.nextInt(maxKey); | ||
94 | String nextValue = values[r2.nextInt(values.length)]; | ||
95 | try { | ||
96 | moving.put(nextKey, nextValue); | ||
97 | } catch (Exception exception) { | ||
98 | exception.printStackTrace(); | ||
99 | fail(scenario + ":" + index + ": exception happened: " + exception); | ||
100 | } | ||
101 | if (index % 10000 == 0) | ||
102 | System.out.println(scenario + ":" + index + "/" + steps + " building finished"); | ||
103 | } | ||
104 | } | ||
105 | } | ||
92 | } | 106 | } |
93 | 107 | ||
94 | @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") | 108 | public static final String title = "DiffCursor {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} " + |
109 | "commit frequency={5} seed={6} commit before diff={7} config={8}"; | ||
110 | |||
111 | @ParameterizedTest(name = title) | ||
95 | @MethodSource | 112 | @MethodSource |
96 | @Timeout(value = 10) | 113 | @Timeout(value = 10) |
97 | @Tag("fuzz") | 114 | @Tag("fuzz") |
98 | void parametrizedFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, | 115 | void parametrizedFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, |
99 | boolean evilHash) { | 116 | int commitFrequency, int seed, boolean commitBeforeDiffCursor, |
100 | runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, | 117 | VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
101 | noKeys, noValues, commitFrequency, evilHash); | 118 | runFuzzTest("DiffCursorS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, |
119 | noKeys, noValues, nullDefault, commitFrequency, commitBeforeDiffCursor, builder); | ||
102 | } | 120 | } |
103 | 121 | ||
104 | static Stream<Arguments> parametrizedFuzz() { | 122 | static Stream<Arguments> parametrizedFuzz() { |
105 | return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 }, | 123 | return FuzzTestUtils.permutationWithSize(new Object[]{100}, keyCounts, valueCounts, nullDefaultOptions, |
106 | new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 }, | 124 | commitFrequencyOptions, randomSeedOptions, new Object[]{false,true}, storeConfigs); |
107 | new Object[] { false, true }); | ||
108 | } | 125 | } |
109 | @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") | 126 | |
127 | @ParameterizedTest(name = title) | ||
110 | @MethodSource | 128 | @MethodSource |
111 | @Tag("fuzz") | 129 | @Tag("fuzz") |
112 | @Tag("slow") | 130 | @Tag("slow") |
113 | void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, | 131 | void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, |
114 | boolean evilHash) { | 132 | int seed, boolean commitBeforeDiffCursor, VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
115 | runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, | 133 | runFuzzTest("DiffCursorS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, |
116 | commitFrequency, evilHash); | 134 | nullDefault, commitFrequency, commitBeforeDiffCursor, builder); |
117 | } | 135 | } |
118 | 136 | ||
119 | static Stream<Arguments> parametrizedSlowFuzz() { | 137 | static Stream<Arguments> parametrizedSlowFuzz() { |
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadFuzzTest.java index ab2b9435..3b55434c 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadFuzzTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadFuzzTest.java | |||
@@ -5,95 +5,96 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.map.tests.fuzz; | 6 | package tools.refinery.store.map.tests.fuzz; |
7 | 7 | ||
8 | import static org.junit.jupiter.api.Assertions.assertEquals; | ||
9 | import static org.junit.jupiter.api.Assertions.fail; | ||
10 | |||
11 | import java.util.Collections; | ||
12 | import java.util.LinkedList; | ||
13 | import java.util.List; | ||
14 | import java.util.stream.Stream; | ||
15 | |||
16 | import org.junit.jupiter.api.Tag; | 8 | import org.junit.jupiter.api.Tag; |
17 | import org.junit.jupiter.api.Timeout; | 9 | import org.junit.jupiter.api.Timeout; |
18 | import org.junit.jupiter.params.ParameterizedTest; | 10 | import org.junit.jupiter.params.ParameterizedTest; |
19 | import org.junit.jupiter.params.provider.Arguments; | 11 | import org.junit.jupiter.params.provider.Arguments; |
20 | import org.junit.jupiter.params.provider.MethodSource; | 12 | import org.junit.jupiter.params.provider.MethodSource; |
21 | |||
22 | import tools.refinery.store.map.ContinousHashProvider; | ||
23 | import tools.refinery.store.map.VersionedMapStore; | 13 | import tools.refinery.store.map.VersionedMapStore; |
24 | import tools.refinery.store.map.VersionedMapStoreImpl; | 14 | import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; |
25 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; | 15 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; |
26 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; | 16 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; |
27 | 17 | ||
18 | import java.util.Collections; | ||
19 | import java.util.LinkedList; | ||
20 | import java.util.List; | ||
21 | import java.util.stream.Stream; | ||
22 | |||
23 | import static org.junit.jupiter.api.Assertions.assertEquals; | ||
24 | import static org.junit.jupiter.api.Assertions.fail; | ||
25 | import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*; | ||
26 | |||
28 | class MultiThreadFuzzTest { | 27 | class MultiThreadFuzzTest { |
29 | public static final int noThreads = 32; | 28 | public static final int noThreads = 10; |
30 | 29 | ||
31 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, | 30 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean nullDefault, int commitFrequency, VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
32 | boolean evilHash) { | 31 | String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); |
33 | String[] values = MapTestEnvironment.prepareValues(maxValue); | 32 | |
34 | ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash); | 33 | VersionedMapStore<Integer, String> store = builder.defaultValue(values[0]).build().createOne(); |
35 | 34 | ||
36 | VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]); | ||
37 | |||
38 | // initialize runnables | 35 | // initialize runnables |
39 | MultiThreadTestRunnable[] runnables = new MultiThreadTestRunnable[noThreads]; | 36 | MultiThreadTestRunnable[] runnables = new MultiThreadTestRunnable[noThreads]; |
40 | for(int i = 0; i<noThreads; i++) { | 37 | for (int i = 0; i < noThreads; i++) { |
41 | runnables[i] = new MultiThreadTestRunnable(scenario+"-T"+(i+1), store, steps, maxKey, values, seed, commitFrequency); | 38 | runnables[i] = new MultiThreadTestRunnable(scenario + "-T" + (i + 1), store, steps, maxKey, values, seed |
39 | , commitFrequency); | ||
42 | } | 40 | } |
43 | 41 | ||
44 | // initialize threads | 42 | // initialize threads |
45 | Thread[] threads = new Thread[noThreads]; | 43 | Thread[] threads = new Thread[noThreads]; |
46 | for(int i = 0; i<noThreads; i++) { | 44 | for (int i = 0; i < noThreads; i++) { |
47 | threads[i] = new Thread(runnables[i]); | 45 | threads[i] = new Thread(runnables[i]); |
48 | } | 46 | } |
49 | 47 | ||
50 | // start threads; | 48 | // start threads; |
51 | for(int i = 0; i<noThreads; i++) { | 49 | for (int i = 0; i < noThreads; i++) { |
52 | threads[i].start(); | 50 | runnables[i].run(); |
51 | //threads[i].start(); | ||
53 | } | 52 | } |
54 | 53 | ||
55 | // wait all the threads; | 54 | // wait all the threads; |
56 | for(int i = 0; i<noThreads; i++) { | 55 | for (int i = 0; i < noThreads; i++) { |
57 | try { | 56 | try { |
58 | threads[i].join(); | 57 | threads[i].join(); |
59 | } catch (InterruptedException e) { | 58 | } catch (InterruptedException e) { |
60 | fail("Thread "+i+" interrupted."); | 59 | fail("Thread " + i + " interrupted."); |
61 | } | 60 | } |
62 | } | 61 | } |
63 | 62 | ||
64 | // collect errors | 63 | // collect errors |
65 | List<Throwable> errors = new LinkedList<>(); | 64 | List<Throwable> errors = new LinkedList<>(); |
66 | for(int i = 0; i<noThreads; i++) { | 65 | for (int i = 0; i < noThreads; i++) { |
67 | errors.addAll(runnables[i].getErrors()); | 66 | errors.addAll(runnables[i].getErrors()); |
68 | } | 67 | } |
69 | 68 | ||
70 | assertEquals(Collections.EMPTY_LIST, errors); | 69 | assertEquals(Collections.EMPTY_LIST, errors); |
71 | } | 70 | } |
72 | 71 | ||
73 | @ParameterizedTest(name = "Multithread {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") | 72 | static final String title = "MultiThread {index}/{0} Steps={1} Keys={2} Values={3} defaultNull={4} commit " + |
73 | "frequency={5} seed={6} config={7}"; | ||
74 | |||
75 | @ParameterizedTest(name = title) | ||
74 | @MethodSource | 76 | @MethodSource |
75 | @Timeout(value = 10) | 77 | @Timeout(value = 10) |
76 | @Tag("fuzz") | 78 | @Tag("fuzz") |
77 | void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, | 79 | void parametrizedFastFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean defaultNull, |
78 | boolean evilHash) { | 80 | int commitFrequency, int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
79 | runFuzzTest("MultithreadS" + steps + "K" + noKeys + "V" + noValues + "CF" + commitFrequency + "s" + seed, seed, steps, noKeys, noValues, | 81 | runFuzzTest("MultiThreadS" + steps + "K" + noKeys + "V" + noValues + defaultNull + "CF" + commitFrequency + |
80 | commitFrequency, evilHash); | 82 | "s" + seed, seed, steps, noKeys, noValues, defaultNull, commitFrequency, builder); |
81 | } | 83 | } |
82 | 84 | ||
83 | static Stream<Arguments> parametrizedFastFuzz() { | 85 | static Stream<Arguments> parametrizedFastFuzz() { |
84 | return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 }, | 86 | return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions, |
85 | new Object[] { 2, 3 }, new Object[] { 10, 100 }, new Object[] { 1, 2, 3 }, | 87 | new Object[]{10, 100}, randomSeedOptions, storeConfigs); |
86 | new Object[] { false, true }); | ||
87 | } | 88 | } |
88 | 89 | ||
89 | @ParameterizedTest(name = "Multithread {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") | 90 | @ParameterizedTest(name = title) |
90 | @MethodSource | 91 | @MethodSource |
91 | @Tag("fuzz") | 92 | @Tag("fuzz") |
92 | @Tag("slow") | 93 | @Tag("slow") |
93 | void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, | 94 | void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, |
94 | boolean evilHash) { | 95 | int commitFrequency, int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
95 | runFuzzTest("RestoreS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, | 96 | runFuzzTest("RestoreS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, |
96 | commitFrequency, evilHash); | 97 | nullDefault, commitFrequency, builder); |
97 | } | 98 | } |
98 | 99 | ||
99 | static Stream<Arguments> parametrizedSlowFuzz() { | 100 | static Stream<Arguments> parametrizedSlowFuzz() { |
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java index 502c8362..9b2e591a 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MultiThreadTestRunnable.java | |||
@@ -13,22 +13,22 @@ import java.util.List; | |||
13 | import java.util.Map; | 13 | import java.util.Map; |
14 | import java.util.Random; | 14 | import java.util.Random; |
15 | 15 | ||
16 | import tools.refinery.store.map.VersionedMap; | ||
16 | import tools.refinery.store.map.VersionedMapStore; | 17 | import tools.refinery.store.map.VersionedMapStore; |
17 | import tools.refinery.store.map.internal.VersionedMapImpl; | ||
18 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; | 18 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; |
19 | 19 | ||
20 | public class MultiThreadTestRunnable implements Runnable { | 20 | public class MultiThreadTestRunnable implements Runnable { |
21 | String scenario; | 21 | final String scenario; |
22 | VersionedMapStore<Integer, String> store; | 22 | final VersionedMapStore<Integer, String> store; |
23 | int steps; | 23 | final int steps; |
24 | int maxKey; | 24 | final int maxKey; |
25 | String[] values; | 25 | final String[] values; |
26 | int seed; | 26 | final int seed; |
27 | int commitFrequency; | 27 | final int commitFrequency; |
28 | List<Throwable> errors = new LinkedList<>(); | 28 | final List<Throwable> errors = new LinkedList<>(); |
29 | 29 | ||
30 | public MultiThreadTestRunnable(String scenario, VersionedMapStore<Integer, String> store, int steps, | 30 | public MultiThreadTestRunnable(String scenario, VersionedMapStore<Integer, String> store, int steps, |
31 | int maxKey, String[] values, int seed, int commitFrequency) { | 31 | int maxKey, String[] values, int seed, int commitFrequency) { |
32 | super(); | 32 | super(); |
33 | this.scenario = scenario; | 33 | this.scenario = scenario; |
34 | this.store = store; | 34 | this.store = store; |
@@ -43,16 +43,24 @@ public class MultiThreadTestRunnable implements Runnable { | |||
43 | AssertionError error = new AssertionError(message); | 43 | AssertionError error = new AssertionError(message); |
44 | errors.add(error); | 44 | errors.add(error); |
45 | } | 45 | } |
46 | 46 | ||
47 | public List<Throwable> getErrors() { | 47 | public List<Throwable> getErrors() { |
48 | return errors; | 48 | return errors; |
49 | } | 49 | } |
50 | 50 | ||
51 | @Override | 51 | @Override |
52 | public void run() { | 52 | public void run() { |
53 | try{ | ||
54 | task(); | ||
55 | } catch(Exception e) { | ||
56 | e.printStackTrace(); | ||
57 | } | ||
58 | } | ||
59 | |||
60 | private void task() { | ||
53 | // 1. build a map with versions | 61 | // 1. build a map with versions |
54 | Random r = new Random(seed); | 62 | Random r = new Random(seed); |
55 | VersionedMapImpl<Integer, String> versioned = (VersionedMapImpl<Integer, String>) store.createMap(); | 63 | VersionedMap<Integer, String> versioned = store.createMap(); |
56 | Map<Integer, Long> index2Version = new HashMap<>(); | 64 | Map<Integer, Long> index2Version = new HashMap<>(); |
57 | 65 | ||
58 | for (int i = 0; i < steps; i++) { | 66 | for (int i = 0; i < steps; i++) { |
@@ -71,10 +79,10 @@ public class MultiThreadTestRunnable implements Runnable { | |||
71 | } | 79 | } |
72 | MapTestEnvironment.printStatus(scenario, index, steps, "building"); | 80 | MapTestEnvironment.printStatus(scenario, index, steps, "building"); |
73 | } | 81 | } |
74 | // 2. create a non-versioned | 82 | // 2. create a non-versioned |
75 | VersionedMapImpl<Integer, String> reference = (VersionedMapImpl<Integer, String>) store.createMap(); | 83 | VersionedMap<Integer, String> reference = store.createMap(); |
76 | r = new Random(seed); | 84 | r = new Random(seed); |
77 | Random r2 = new Random(seed+1); | 85 | Random r2 = new Random(seed + 1); |
78 | 86 | ||
79 | for (int i = 0; i < steps; i++) { | 87 | for (int i = 0; i < steps; i++) { |
80 | int index = i + 1; | 88 | int index = i + 1; |
@@ -89,13 +97,17 @@ public class MultiThreadTestRunnable implements Runnable { | |||
89 | // go back to an existing state and compare to the reference | 97 | // go back to an existing state and compare to the reference |
90 | if (index % (commitFrequency) == 0) { | 98 | if (index % (commitFrequency) == 0) { |
91 | versioned.restore(index2Version.get(i)); | 99 | versioned.restore(index2Version.get(i)); |
92 | MapTestEnvironment.compareTwoMaps(scenario + ":" + index, reference, versioned,errors); | 100 | MapTestEnvironment.compareTwoMaps(scenario + ":" + index, reference, versioned, null); |
93 | 101 | ||
94 | // go back to a random state (probably created by another thread) | 102 | // go back to a random state (probably created by another thread) |
95 | List<Long> states = new ArrayList<>(store.getStates()); | 103 | List<Long> states = new ArrayList<>(store.getStates()); |
104 | states.sort(Long::compare); | ||
96 | Collections.shuffle(states, r2); | 105 | Collections.shuffle(states, r2); |
97 | for(Long state : states.subList(0, Math.min(states.size(), 100))) { | 106 | for (Long state : states.subList(0, Math.min(states.size(), 100))) { |
98 | versioned.restore(state); | 107 | long x = state; |
108 | versioned.restore(x); | ||
109 | var clean = store.createMap(x); | ||
110 | MapTestEnvironment.compareTwoMaps(scenario + ":" + index, clean, versioned, null); | ||
99 | } | 111 | } |
100 | versioned.restore(index2Version.get(i)); | 112 | versioned.restore(index2Version.get(i)); |
101 | } | 113 | } |
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableFuzzTest.java index 32dde0da..fdcd7f9f 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableFuzzTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/MutableFuzzTest.java | |||
@@ -6,6 +6,7 @@ | |||
6 | package tools.refinery.store.map.tests.fuzz; | 6 | package tools.refinery.store.map.tests.fuzz; |
7 | 7 | ||
8 | import static org.junit.jupiter.api.Assertions.fail; | 8 | import static org.junit.jupiter.api.Assertions.fail; |
9 | import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*; | ||
9 | 10 | ||
10 | import java.util.Random; | 11 | import java.util.Random; |
11 | import java.util.stream.Stream; | 12 | import java.util.stream.Stream; |
@@ -16,21 +17,18 @@ import org.junit.jupiter.params.ParameterizedTest; | |||
16 | import org.junit.jupiter.params.provider.Arguments; | 17 | import org.junit.jupiter.params.provider.Arguments; |
17 | import org.junit.jupiter.params.provider.MethodSource; | 18 | import org.junit.jupiter.params.provider.MethodSource; |
18 | 19 | ||
19 | import tools.refinery.store.map.ContinousHashProvider; | 20 | import tools.refinery.store.map.*; |
20 | import tools.refinery.store.map.VersionedMapStore; | ||
21 | import tools.refinery.store.map.VersionedMapStoreImpl; | ||
22 | import tools.refinery.store.map.internal.VersionedMapImpl; | ||
23 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; | 21 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; |
24 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; | 22 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; |
25 | 23 | ||
26 | class MutableFuzzTest { | 24 | class MutableFuzzTest { |
27 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean evilHash) { | 25 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, |
28 | String[] values = MapTestEnvironment.prepareValues(maxValue); | 26 | boolean nullDefault, VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
29 | ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash); | 27 | String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); |
30 | 28 | ||
31 | VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]); | 29 | VersionedMapStore<Integer, String> store = builder.defaultValue(values[0]).build().createOne(); |
32 | VersionedMapImpl<Integer, String> sut = (VersionedMapImpl<Integer, String>) store.createMap(); | 30 | VersionedMap<Integer, String> sut = store.createMap(); |
33 | MapTestEnvironment<Integer, String> e = new MapTestEnvironment<Integer, String>(sut); | 31 | MapTestEnvironment<Integer, String> e = new MapTestEnvironment<>(sut); |
34 | 32 | ||
35 | Random r = new Random(seed); | 33 | Random r = new Random(seed); |
36 | 34 | ||
@@ -38,24 +36,14 @@ class MutableFuzzTest { | |||
38 | } | 36 | } |
39 | 37 | ||
40 | private void iterativeRandomPuts(String scenario, int steps, int maxKey, String[] values, | 38 | private void iterativeRandomPuts(String scenario, int steps, int maxKey, String[] values, |
41 | MapTestEnvironment<Integer, String> e, Random r) { | 39 | MapTestEnvironment<Integer, String> e, Random r) { |
42 | int stopAt = -1; | ||
43 | for (int i = 0; i < steps; i++) { | 40 | for (int i = 0; i < steps; i++) { |
44 | int index = i + 1; | 41 | int index = i + 1; |
45 | int nextKey = r.nextInt(maxKey); | 42 | int nextKey = r.nextInt(maxKey); |
46 | String nextValue = values[r.nextInt(values.length)]; | 43 | String nextValue = values[r.nextInt(values.length)]; |
47 | if (index == stopAt) { | 44 | |
48 | System.out.println("issue!"); | ||
49 | System.out.println("State before:"); | ||
50 | e.printComparison(); | ||
51 | e.sut.prettyPrint(); | ||
52 | System.out.println("Next: put(" + nextKey + "," + nextValue + ")"); | ||
53 | } | ||
54 | try { | 45 | try { |
55 | e.put(nextKey, nextValue); | 46 | e.put(nextKey, nextValue); |
56 | if (index == stopAt) { | ||
57 | e.sut.prettyPrint(); | ||
58 | } | ||
59 | e.checkEquivalence(scenario + ":" + index); | 47 | e.checkEquivalence(scenario + ":" + index); |
60 | } catch (Exception exception) { | 48 | } catch (Exception exception) { |
61 | exception.printStackTrace(); | 49 | exception.printStackTrace(); |
@@ -65,30 +53,34 @@ class MutableFuzzTest { | |||
65 | } | 53 | } |
66 | } | 54 | } |
67 | 55 | ||
68 | @ParameterizedTest(name = "Mutable {index}/{0} Steps={1} Keys={2} Values={3} seed={4} evil-hash={5}") | 56 | final String title = "Mutable {index}/{0} Steps={1} Keys={2} Values={3} defaultNull={4} seed={5} " + |
57 | "config={6}"; | ||
58 | |||
59 | @ParameterizedTest(name = title) | ||
69 | @MethodSource | 60 | @MethodSource |
70 | @Timeout(value = 10) | 61 | @Timeout(value = 10) |
71 | @Tag("fuzz") | 62 | @Tag("fuzz") |
72 | void parametrizedFuzz(int test, int steps, int noKeys, int noValues, int seed, boolean evilHash) { | 63 | void parametrizedFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean defaultNull, int seed, |
64 | VersionedMapStoreFactoryBuilder<Integer, String> builder) { | ||
73 | runFuzzTest( | 65 | runFuzzTest( |
74 | "MutableS" + steps + "K" + noKeys + "V" + noValues + "s" + seed + "H" + (evilHash ? "Evil" : "Normal"), | 66 | "MutableS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, |
75 | seed, steps, noKeys, noValues, evilHash); | 67 | seed, steps, noKeys, noValues, defaultNull, builder); |
76 | } | 68 | } |
77 | 69 | ||
78 | static Stream<Arguments> parametrizedFuzz() { | 70 | static Stream<Arguments> parametrizedFuzz() { |
79 | return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, | 71 | return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions, |
80 | new Object[] { 3, 32, 32 * 32, 32 * 32 * 32 * 32 }, new Object[] { 2, 3 }, new Object[] { 1, 2, 3 }, | 72 | randomSeedOptions, storeConfigs); |
81 | new Object[] { false, true }); | ||
82 | } | 73 | } |
83 | 74 | ||
84 | @ParameterizedTest(name = "Mutable {index}/{0} Steps={1} Keys={2} Values={3} seed={4} evil-hash={5}") | 75 | @ParameterizedTest(name = title) |
85 | @MethodSource | 76 | @MethodSource |
86 | @Tag("fuzz") | 77 | @Tag("fuzz") |
87 | @Tag("slow") | 78 | @Tag("slow") |
88 | void parametrizedSlowFuzz(int test, int steps, int noKeys, int noValues, int seed, boolean evilHash) { | 79 | void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int seed, |
80 | VersionedMapStoreFactoryBuilder<Integer, String> builder) { | ||
89 | runFuzzTest( | 81 | runFuzzTest( |
90 | "MutableS" + steps + "K" + noKeys + "V" + noValues + "s" + seed + "H" + (evilHash ? "Evil" : "Normal"), | 82 | "MutableS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, |
91 | seed, steps, noKeys, noValues, evilHash); | 83 | seed, steps, noKeys, noValues, nullDefault, builder); |
92 | } | 84 | } |
93 | 85 | ||
94 | static Stream<Arguments> parametrizedSlowFuzz() { | 86 | static Stream<Arguments> parametrizedSlowFuzz() { |
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 347c49be..420dade6 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 | |||
@@ -6,6 +6,7 @@ | |||
6 | package tools.refinery.store.map.tests.fuzz; | 6 | package tools.refinery.store.map.tests.fuzz; |
7 | 7 | ||
8 | import static org.junit.jupiter.api.Assertions.fail; | 8 | import static org.junit.jupiter.api.Assertions.fail; |
9 | import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*; | ||
9 | 10 | ||
10 | import java.util.Random; | 11 | import java.util.Random; |
11 | import java.util.stream.Stream; | 12 | import java.util.stream.Stream; |
@@ -24,12 +25,12 @@ import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; | |||
24 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; | 25 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; |
25 | 26 | ||
26 | class MutableImmutableCompareFuzzTest { | 27 | class MutableImmutableCompareFuzzTest { |
27 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, | 28 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, |
28 | boolean evilHash) { | 29 | boolean nullDefault, int commitFrequency, boolean evilHash) { |
29 | String[] values = MapTestEnvironment.prepareValues(maxValue); | 30 | String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); |
30 | ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash); | 31 | ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash); |
31 | 32 | ||
32 | VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]); | 33 | VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<>(chp, values[0]); |
33 | VersionedMapImpl<Integer, String> immutable = (VersionedMapImpl<Integer, String>) store.createMap(); | 34 | VersionedMapImpl<Integer, String> immutable = (VersionedMapImpl<Integer, String>) store.createMap(); |
34 | VersionedMapImpl<Integer, String> mutable = (VersionedMapImpl<Integer, String>) store.createMap(); | 35 | VersionedMapImpl<Integer, String> mutable = (VersionedMapImpl<Integer, String>) store.createMap(); |
35 | 36 | ||
@@ -40,8 +41,8 @@ class MutableImmutableCompareFuzzTest { | |||
40 | } | 41 | } |
41 | 42 | ||
42 | private void iterativeRandomPutsAndCommitsAndCompare(String scenario, VersionedMapImpl<Integer, String> immutable, | 43 | private void iterativeRandomPutsAndCommitsAndCompare(String scenario, VersionedMapImpl<Integer, String> immutable, |
43 | VersionedMapImpl<Integer, String> mutable, int steps, int maxKey, String[] values, Random r, | 44 | VersionedMapImpl<Integer, String> mutable, int steps, int maxKey, String[] values, Random r, |
44 | int commitFrequency) { | 45 | int commitFrequency) { |
45 | for (int i = 0; i < steps; i++) { | 46 | for (int i = 0; i < steps; i++) { |
46 | int index = i + 1; | 47 | int index = i + 1; |
47 | int nextKey = r.nextInt(maxKey); | 48 | int nextKey = r.nextInt(maxKey); |
@@ -62,30 +63,31 @@ class MutableImmutableCompareFuzzTest { | |||
62 | } | 63 | } |
63 | } | 64 | } |
64 | 65 | ||
65 | @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") | 66 | @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} " + |
67 | "commit frequency={5} seed={6} evil-hash={7}") | ||
66 | @MethodSource | 68 | @MethodSource |
67 | @Timeout(value = 10) | 69 | @Timeout(value = 10) |
68 | @Tag("fuzz") | 70 | @Tag("fuzz") |
69 | void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, | 71 | void parametrizedFastFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, |
70 | boolean evilHash) { | 72 | int seed, boolean evilHash) { |
71 | runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, | 73 | runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, |
72 | noKeys, noValues, commitFrequency, evilHash); | 74 | noKeys, noValues, nullDefault, commitFrequency, evilHash); |
73 | } | 75 | } |
74 | 76 | ||
75 | static Stream<Arguments> parametrizedFastFuzz() { | 77 | static Stream<Arguments> parametrizedFastFuzz() { |
76 | return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 }, | 78 | return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions, |
77 | new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 }, | 79 | commitFrequencyOptions, randomSeedOptions, new Object[]{false, true}); |
78 | new Object[] { false, true }); | ||
79 | } | 80 | } |
80 | 81 | ||
81 | @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") | 82 | @ParameterizedTest(name = "Mutable-Immutable Compare {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} " + |
83 | "commit frequency={5} seed={6} evil-hash={7}") | ||
82 | @MethodSource | 84 | @MethodSource |
83 | @Tag("fuzz") | 85 | @Tag("fuzz") |
84 | @Tag("slow") | 86 | @Tag("slow") |
85 | void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, | 87 | void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, |
86 | boolean evilHash) { | 88 | int seed, boolean evilHash) { |
87 | runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, | 89 | runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, |
88 | noKeys, noValues, commitFrequency, evilHash); | 90 | noKeys, noValues, nullDefault, commitFrequency, evilHash); |
89 | } | 91 | } |
90 | 92 | ||
91 | static Stream<Arguments> parametrizedSlowFuzz() { | 93 | static Stream<Arguments> parametrizedSlowFuzz() { |
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java index f7b9d61e..0b399c3a 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/RestoreFuzzTest.java | |||
@@ -5,42 +5,41 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.map.tests.fuzz; | 6 | package tools.refinery.store.map.tests.fuzz; |
7 | 7 | ||
8 | import static org.junit.jupiter.api.Assertions.fail; | ||
9 | |||
10 | import java.util.HashMap; | ||
11 | import java.util.Map; | ||
12 | import java.util.Random; | ||
13 | import java.util.stream.Stream; | ||
14 | |||
15 | import org.junit.jupiter.api.Tag; | 8 | import org.junit.jupiter.api.Tag; |
16 | import org.junit.jupiter.api.Timeout; | 9 | import org.junit.jupiter.api.Timeout; |
17 | import org.junit.jupiter.params.ParameterizedTest; | 10 | import org.junit.jupiter.params.ParameterizedTest; |
18 | import org.junit.jupiter.params.provider.Arguments; | 11 | import org.junit.jupiter.params.provider.Arguments; |
19 | import org.junit.jupiter.params.provider.MethodSource; | 12 | import org.junit.jupiter.params.provider.MethodSource; |
20 | 13 | import tools.refinery.store.map.VersionedMap; | |
21 | import tools.refinery.store.map.ContinousHashProvider; | ||
22 | import tools.refinery.store.map.VersionedMapStore; | 14 | import tools.refinery.store.map.VersionedMapStore; |
23 | import tools.refinery.store.map.VersionedMapStoreImpl; | 15 | import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; |
24 | import tools.refinery.store.map.internal.VersionedMapImpl; | ||
25 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; | 16 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; |
26 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; | 17 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; |
27 | 18 | ||
19 | import java.util.HashMap; | ||
20 | import java.util.Map; | ||
21 | import java.util.Random; | ||
22 | import java.util.stream.Stream; | ||
23 | |||
24 | import static org.junit.jupiter.api.Assertions.fail; | ||
25 | import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*; | ||
26 | |||
28 | class RestoreFuzzTest { | 27 | class RestoreFuzzTest { |
29 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, | 28 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, |
30 | boolean evilHash) { | 29 | boolean nullDefault, int commitFrequency, |
31 | String[] values = MapTestEnvironment.prepareValues(maxValue); | 30 | VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
32 | ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash); | 31 | String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); |
33 | 32 | ||
34 | VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]); | 33 | VersionedMapStore<Integer, String> store = builder.defaultValue(values[0]).build().createOne(); |
35 | 34 | ||
36 | iterativeRandomPutsAndCommitsThenRestore(scenario, store, steps, maxKey, values, seed, commitFrequency); | 35 | iterativeRandomPutsAndCommitsThenRestore(scenario, store, steps, maxKey, values, seed, commitFrequency); |
37 | } | 36 | } |
38 | 37 | ||
39 | private void iterativeRandomPutsAndCommitsThenRestore(String scenario, VersionedMapStore<Integer, String> store, | 38 | private void iterativeRandomPutsAndCommitsThenRestore(String scenario, VersionedMapStore<Integer, String> store, |
40 | int steps, int maxKey, String[] values, int seed, int commitFrequency) { | 39 | int steps, int maxKey, String[] values, int seed, int commitFrequency) { |
41 | // 1. build a map with versions | 40 | // 1. build a map with versions |
42 | Random r = new Random(seed); | 41 | Random r = new Random(seed); |
43 | VersionedMapImpl<Integer, String> versioned = (VersionedMapImpl<Integer, String>) store.createMap(); | 42 | VersionedMap<Integer, String> versioned = store.createMap(); |
44 | Map<Integer, Long> index2Version = new HashMap<>(); | 43 | Map<Integer, Long> index2Version = new HashMap<>(); |
45 | 44 | ||
46 | for (int i = 0; i < steps; i++) { | 45 | for (int i = 0; i < steps; i++) { |
@@ -60,7 +59,7 @@ class RestoreFuzzTest { | |||
60 | MapTestEnvironment.printStatus(scenario, index, steps, "building"); | 59 | MapTestEnvironment.printStatus(scenario, index, steps, "building"); |
61 | } | 60 | } |
62 | // 2. create a non-versioned and | 61 | // 2. create a non-versioned and |
63 | VersionedMapImpl<Integer, String> reference = (VersionedMapImpl<Integer, String>) store.createMap(); | 62 | VersionedMap<Integer, String> reference = store.createMap(); |
64 | r = new Random(seed); | 63 | r = new Random(seed); |
65 | 64 | ||
66 | for (int i = 0; i < steps; i++) { | 65 | for (int i = 0; i < steps; i++) { |
@@ -82,30 +81,32 @@ class RestoreFuzzTest { | |||
82 | 81 | ||
83 | } | 82 | } |
84 | 83 | ||
85 | @ParameterizedTest(name = "Restore {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") | 84 | public static final String title = "Commit {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} commit frequency={5} " + |
85 | "seed={6} config={7}"; | ||
86 | |||
87 | @ParameterizedTest(name = title) | ||
86 | @MethodSource | 88 | @MethodSource |
87 | @Timeout(value = 10) | 89 | @Timeout(value = 10) |
88 | @Tag("smoke") | 90 | @Tag("smoke") |
89 | void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, | 91 | void parametrizedFastFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, |
90 | boolean evilHash) { | 92 | int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
91 | runFuzzTest("RestoreS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, | 93 | runFuzzTest("RestoreS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, |
92 | commitFrequency, evilHash); | 94 | nullDefault, commitFrequency, builder); |
93 | } | 95 | } |
94 | 96 | ||
95 | static Stream<Arguments> parametrizedFastFuzz() { | 97 | static Stream<Arguments> parametrizedFastFuzz() { |
96 | return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 }, | 98 | return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions, |
97 | new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 }, | 99 | commitFrequencyOptions, randomSeedOptions, storeConfigs); |
98 | new Object[] { false, true }); | ||
99 | } | 100 | } |
100 | 101 | ||
101 | @ParameterizedTest(name = "Restore {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") | 102 | @ParameterizedTest(name = title) |
102 | @MethodSource | 103 | @MethodSource |
103 | @Tag("smoke") | 104 | @Tag("smoke") |
104 | @Tag("slow") | 105 | @Tag("slow") |
105 | void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, | 106 | void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, |
106 | boolean evilHash) { | 107 | int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) { |
107 | runFuzzTest("RestoreS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, | 108 | runFuzzTest("RestoreS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, |
108 | commitFrequency, evilHash); | 109 | nullDefault, commitFrequency, builder); |
109 | } | 110 | } |
110 | 111 | ||
111 | static Stream<Arguments> parametrizedSlowFuzz() { | 112 | static Stream<Arguments> parametrizedSlowFuzz() { |
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 4b4172d0..680d962d 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 | |||
@@ -25,10 +25,12 @@ import tools.refinery.store.map.internal.VersionedMapImpl; | |||
25 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; | 25 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; |
26 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; | 26 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; |
27 | 27 | ||
28 | import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*; | ||
29 | |||
28 | class SharedStoreFuzzTest { | 30 | class SharedStoreFuzzTest { |
29 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, | 31 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, |
30 | boolean evilHash) { | 32 | boolean nullDefault, int commitFrequency, boolean evilHash) { |
31 | String[] values = MapTestEnvironment.prepareValues(maxValue); | 33 | String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); |
32 | ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash); | 34 | ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash); |
33 | 35 | ||
34 | List<VersionedMapStore<Integer, String>> stores = VersionedMapStoreImpl.createSharedVersionedMapStores(5, chp, values[0]); | 36 | List<VersionedMapStore<Integer, String>> stores = VersionedMapStoreImpl.createSharedVersionedMapStores(5, chp, values[0]); |
@@ -37,22 +39,22 @@ class SharedStoreFuzzTest { | |||
37 | } | 39 | } |
38 | 40 | ||
39 | private void iterativeRandomPutsAndCommitsThenRestore(String scenario, List<VersionedMapStore<Integer, String>> stores, | 41 | private void iterativeRandomPutsAndCommitsThenRestore(String scenario, List<VersionedMapStore<Integer, String>> stores, |
40 | int steps, int maxKey, String[] values, int seed, int commitFrequency) { | 42 | int steps, int maxKey, String[] values, int seed, int commitFrequency) { |
41 | // 1. maps with versions | 43 | // 1. maps with versions |
42 | Random r = new Random(seed); | 44 | Random r = new Random(seed); |
43 | List<VersionedMapImpl<Integer, String>> versioneds = new LinkedList<>(); | 45 | List<VersionedMapImpl<Integer, String>> versioneds = new LinkedList<>(); |
44 | for(VersionedMapStore<Integer, String> store : stores) { | 46 | for (VersionedMapStore<Integer, String> store : stores) { |
45 | versioneds.add((VersionedMapImpl<Integer, String>) store.createMap()); | 47 | versioneds.add((VersionedMapImpl<Integer, String>) store.createMap()); |
46 | } | 48 | } |
47 | 49 | ||
48 | List<Map<Integer, Long>> index2Version = new LinkedList<>(); | 50 | List<Map<Integer, Long>> index2Version = new LinkedList<>(); |
49 | for(int i = 0; i<stores.size(); i++) { | 51 | for (int i = 0; i < stores.size(); i++) { |
50 | index2Version.add(new HashMap<>()); | 52 | index2Version.add(new HashMap<>()); |
51 | } | 53 | } |
52 | 54 | ||
53 | for (int i = 0; i < steps; i++) { | 55 | for (int i = 0; i < steps; i++) { |
54 | int stepIndex = i + 1; | 56 | int stepIndex = i + 1; |
55 | for (int storeIndex = 0; storeIndex<versioneds.size(); storeIndex++) { | 57 | for (int storeIndex = 0; storeIndex < versioneds.size(); storeIndex++) { |
56 | int nextKey = r.nextInt(maxKey); | 58 | int nextKey = r.nextInt(maxKey); |
57 | String nextValue = values[r.nextInt(values.length)]; | 59 | String nextValue = values[r.nextInt(values.length)]; |
58 | versioneds.get(storeIndex).put(nextKey, nextValue); | 60 | versioneds.get(storeIndex).put(nextKey, nextValue); |
@@ -61,18 +63,18 @@ class SharedStoreFuzzTest { | |||
61 | index2Version.get(storeIndex).put(i, version); | 63 | index2Version.get(storeIndex).put(i, version); |
62 | } | 64 | } |
63 | MapTestEnvironment.printStatus(scenario, stepIndex, steps, "building"); | 65 | MapTestEnvironment.printStatus(scenario, stepIndex, steps, "building"); |
64 | } | 66 | } |
65 | } | 67 | } |
66 | // 2. create a non-versioned and | 68 | // 2. create a non-versioned and |
67 | List<VersionedMapImpl<Integer, String>> reference = new LinkedList<>(); | 69 | List<VersionedMapImpl<Integer, String>> reference = new LinkedList<>(); |
68 | for(VersionedMapStore<Integer, String> store : stores) { | 70 | for (VersionedMapStore<Integer, String> store : stores) { |
69 | reference.add((VersionedMapImpl<Integer, String>) store.createMap()); | 71 | reference.add((VersionedMapImpl<Integer, String>) store.createMap()); |
70 | } | 72 | } |
71 | r = new Random(seed); | 73 | r = new Random(seed); |
72 | 74 | ||
73 | for (int i = 0; i < steps; i++) { | 75 | for (int i = 0; i < steps; i++) { |
74 | int index = i + 1; | 76 | int index = i + 1; |
75 | for (int storeIndex = 0; storeIndex<versioneds.size(); storeIndex++) { | 77 | for (int storeIndex = 0; storeIndex < versioneds.size(); storeIndex++) { |
76 | int nextKey = r.nextInt(maxKey); | 78 | int nextKey = r.nextInt(maxKey); |
77 | String nextValue = values[r.nextInt(values.length)]; | 79 | String nextValue = values[r.nextInt(values.length)]; |
78 | reference.get(storeIndex).put(nextKey, nextValue); | 80 | reference.get(storeIndex).put(nextKey, nextValue); |
@@ -81,35 +83,36 @@ class SharedStoreFuzzTest { | |||
81 | MapTestEnvironment.compareTwoMaps(scenario + ":" + index, reference.get(storeIndex), versioneds.get(storeIndex)); | 83 | MapTestEnvironment.compareTwoMaps(scenario + ":" + index, reference.get(storeIndex), versioneds.get(storeIndex)); |
82 | } | 84 | } |
83 | } | 85 | } |
84 | MapTestEnvironment.printStatus(scenario, index, steps, "comparison"); | 86 | MapTestEnvironment.printStatus(scenario, index, steps, "comparison"); |
85 | } | 87 | } |
86 | 88 | ||
87 | } | 89 | } |
88 | 90 | ||
89 | @ParameterizedTest(name = "Shared Store {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") | 91 | @ParameterizedTest(name = "Shared Store {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} commit " + |
92 | "frequency={4} seed={5} evil-hash={6}") | ||
90 | @MethodSource | 93 | @MethodSource |
91 | @Timeout(value = 10) | 94 | @Timeout(value = 10) |
92 | @Tag("smoke") | 95 | @Tag("smoke") |
93 | void parametrizedFastFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, | 96 | void parametrizedFastFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, |
94 | boolean evilHash) { | 97 | int seed, boolean evilHash) { |
95 | runFuzzTest("SharedS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, | 98 | runFuzzTest("SharedS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, |
96 | commitFrequency, evilHash); | 99 | nullDefault, commitFrequency, evilHash); |
97 | } | 100 | } |
98 | 101 | ||
99 | static Stream<Arguments> parametrizedFastFuzz() { | 102 | static Stream<Arguments> parametrizedFastFuzz() { |
100 | return FuzzTestUtils.permutationWithSize(new Object[] { FuzzTestUtils.FAST_STEP_COUNT }, new Object[] { 3, 32, 32 * 32 }, | 103 | return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions, |
101 | new Object[] { 2, 3 }, new Object[] { 1, 10, 100 }, new Object[] { 1, 2, 3 }, | 104 | commitFrequencyOptions, randomSeedOptions, new Object[]{false, true}); |
102 | new Object[] { false, true }); | ||
103 | } | 105 | } |
104 | 106 | ||
105 | @ParameterizedTest(name = "Shared Store {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5} evil-hash={6}") | 107 | @ParameterizedTest(name = "Shared Store {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} commit " + |
108 | "frequency={4} seed={5} evil-hash={6}") | ||
106 | @MethodSource | 109 | @MethodSource |
107 | @Tag("smoke") | 110 | @Tag("smoke") |
108 | @Tag("slow") | 111 | @Tag("slow") |
109 | void parametrizedSlowFuzz(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, | 112 | void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, |
110 | boolean evilHash) { | 113 | int seed, boolean evilHash) { |
111 | runFuzzTest("SharedS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, | 114 | runFuzzTest("SharedS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, |
112 | commitFrequency, evilHash); | 115 | nullDefault, commitFrequency, evilHash); |
113 | } | 116 | } |
114 | 117 | ||
115 | static Stream<Arguments> parametrizedSlowFuzz() { | 118 | static Stream<Arguments> parametrizedSlowFuzz() { |
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SingleThreadFuzzTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SingleThreadFuzzTest.java new file mode 100644 index 00000000..1337cf3a --- /dev/null +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/SingleThreadFuzzTest.java | |||
@@ -0,0 +1,66 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.tests.fuzz; | ||
7 | |||
8 | import org.junit.jupiter.api.Tag; | ||
9 | import org.junit.jupiter.api.Timeout; | ||
10 | import org.junit.jupiter.params.ParameterizedTest; | ||
11 | import org.junit.jupiter.params.provider.Arguments; | ||
12 | import org.junit.jupiter.params.provider.MethodSource; | ||
13 | import tools.refinery.store.map.VersionedMapStore; | ||
14 | import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; | ||
15 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; | ||
16 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; | ||
17 | |||
18 | import java.util.stream.Stream; | ||
19 | |||
20 | import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*; | ||
21 | |||
22 | class SingleThreadFuzzTest { | ||
23 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean nullDefault, int commitFrequency, VersionedMapStoreFactoryBuilder<Integer, String> builder) { | ||
24 | String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); | ||
25 | |||
26 | VersionedMapStore<Integer, String> store = builder.defaultValue(values[0]).build().createOne(); | ||
27 | |||
28 | // initialize runnables | ||
29 | MultiThreadTestRunnable runnable = new MultiThreadTestRunnable(scenario, store, steps, maxKey, values, seed, commitFrequency); | ||
30 | |||
31 | // start threads; | ||
32 | runnable.run(); | ||
33 | } | ||
34 | |||
35 | static final String title = "SingleThread {index}/{0} Steps={1} Keys={2} Values={3} defaultNull={4} commit " + | ||
36 | "frequency={5} seed={6} config={7}"; | ||
37 | |||
38 | @ParameterizedTest(name = title) | ||
39 | @MethodSource | ||
40 | @Timeout(value = 10) | ||
41 | @Tag("fuzz") | ||
42 | void parametrizedFastFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean defaultNull, | ||
43 | int commitFrequency, int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) { | ||
44 | runFuzzTest("SingleThreadS" + steps + "K" + noKeys + "V" + noValues + defaultNull + "CF" + commitFrequency + | ||
45 | "s" + seed, seed, steps, noKeys, noValues, defaultNull, commitFrequency, builder); | ||
46 | } | ||
47 | |||
48 | static Stream<Arguments> parametrizedFastFuzz() { | ||
49 | return FuzzTestUtils.permutationWithSize(stepCounts, keyCounts, valueCounts, nullDefaultOptions, | ||
50 | new Object[]{10, 100}, randomSeedOptions, storeConfigs); | ||
51 | } | ||
52 | |||
53 | @ParameterizedTest(name = title) | ||
54 | @MethodSource | ||
55 | @Tag("fuzz") | ||
56 | @Tag("slow") | ||
57 | void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, | ||
58 | int commitFrequency, int seed, VersionedMapStoreFactoryBuilder<Integer, String> builder) { | ||
59 | runFuzzTest("SingleThreadS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, | ||
60 | nullDefault, commitFrequency, builder); | ||
61 | } | ||
62 | |||
63 | static Stream<Arguments> parametrizedSlowFuzz() { | ||
64 | return FuzzTestUtils.changeStepCount(RestoreFuzzTest.parametrizedFastFuzz(), 1); | ||
65 | } | ||
66 | } | ||
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java new file mode 100644 index 00000000..4c3ecb09 --- /dev/null +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestCollections.java | |||
@@ -0,0 +1,44 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.map.tests.fuzz.utils; | ||
7 | |||
8 | import tools.refinery.store.map.VersionedMapStore; | ||
9 | import tools.refinery.store.map.VersionedMapStoreFactoryBuilder; | ||
10 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; | ||
11 | |||
12 | public final class FuzzTestCollections { | ||
13 | public static final Object[] stepCounts = {FuzzTestUtils.FAST_STEP_COUNT}; | ||
14 | public static final Object[] keyCounts = {1 , 32, 32 * 32}; | ||
15 | public static final Object[] valueCounts = {2, 3}; | ||
16 | public static final Object[] nullDefaultOptions = {false, true}; | ||
17 | public static final Object[] commitFrequencyOptions = {1, 10, 100}; | ||
18 | public static final Object[] randomSeedOptions = {1}; | ||
19 | public static final Object[] storeConfigs = { | ||
20 | // State based | ||
21 | VersionedMapStore.<Integer,String>builder() | ||
22 | .stateBasedImmutableWhenCommitting(true) | ||
23 | .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(false)) | ||
24 | .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE), | ||
25 | VersionedMapStore.<Integer,String>builder() | ||
26 | .stateBasedImmutableWhenCommitting(true) | ||
27 | .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(true)) | ||
28 | .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE), | ||
29 | VersionedMapStore.<Integer,String>builder() | ||
30 | .stateBasedImmutableWhenCommitting(false) | ||
31 | .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(false)) | ||
32 | .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.SHARED_NODE_CACHE), | ||
33 | VersionedMapStore.<Integer,String>builder() | ||
34 | .stateBasedImmutableWhenCommitting(false) | ||
35 | .stateBasedHashProvider(MapTestEnvironment.prepareHashProvider(false)) | ||
36 | .stateBasedSharingStrategy(VersionedMapStoreFactoryBuilder.SharingStrategy.NO_NODE_CACHE), | ||
37 | |||
38 | // Delta based | ||
39 | VersionedMapStore.<Integer,String>builder() | ||
40 | .deltaTransactionStrategy(VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy.SET), | ||
41 | VersionedMapStore.<Integer,String>builder() | ||
42 | .deltaTransactionStrategy(VersionedMapStoreFactoryBuilder.DeltaTransactionStrategy.LIST) | ||
43 | }; | ||
44 | } | ||
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtils.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtils.java index a819d348..32675635 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtils.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtils.java | |||
@@ -13,7 +13,7 @@ import java.util.stream.Stream; | |||
13 | import org.junit.jupiter.params.provider.Arguments; | 13 | import org.junit.jupiter.params.provider.Arguments; |
14 | 14 | ||
15 | public final class FuzzTestUtils { | 15 | public final class FuzzTestUtils { |
16 | public static final int FAST_STEP_COUNT = 500; | 16 | public static final int FAST_STEP_COUNT = 250; |
17 | public static final int SLOW_STEP_COUNT = 32 * 32 * 32 * 32; | 17 | public static final int SLOW_STEP_COUNT = 32 * 32 * 32 * 32; |
18 | 18 | ||
19 | private FuzzTestUtils() { | 19 | private FuzzTestUtils() { |
@@ -56,14 +56,12 @@ public final class FuzzTestUtils { | |||
56 | 56 | ||
57 | public static Stream<Arguments> permutationWithSize(Object[]... valueOption) { | 57 | public static Stream<Arguments> permutationWithSize(Object[]... valueOption) { |
58 | int size = 1; | 58 | int size = 1; |
59 | for (int i = 0; i < valueOption.length; i++) { | 59 | for (Object[] objects : valueOption) { |
60 | size *= valueOption[i].length; | 60 | size *= objects.length; |
61 | } | 61 | } |
62 | Object[][] newValueOption = new Object[valueOption.length + 1][]; | 62 | Object[][] newValueOption = new Object[valueOption.length + 1][]; |
63 | newValueOption[0] = new Object[] { size }; | 63 | newValueOption[0] = new Object[]{size}; |
64 | for (int i = 1; i < newValueOption.length; i++) { | 64 | System.arraycopy(valueOption, 0, newValueOption, 1, newValueOption.length - 1); |
65 | newValueOption[i] = valueOption[i - 1]; | ||
66 | } | ||
67 | return permutation(newValueOption); | 65 | return permutation(newValueOption); |
68 | } | 66 | } |
69 | } | 67 | } |
diff --git a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtilsTest.java b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtilsTest.java index dc621574..951d6336 100644 --- a/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtilsTest.java +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/fuzz/utils/FuzzTestUtilsTest.java | |||
@@ -6,31 +6,36 @@ | |||
6 | package tools.refinery.store.map.tests.fuzz.utils; | 6 | package tools.refinery.store.map.tests.fuzz.utils; |
7 | 7 | ||
8 | import static org.junit.jupiter.api.Assertions.assertEquals; | 8 | import static org.junit.jupiter.api.Assertions.assertEquals; |
9 | import static org.junit.jupiter.api.Assertions.assertTrue; | ||
9 | 10 | ||
10 | import java.util.List; | 11 | import java.util.List; |
12 | import java.util.Optional; | ||
11 | 13 | ||
12 | import org.junit.jupiter.api.Test; | 14 | import org.junit.jupiter.api.Test; |
15 | import org.junit.jupiter.params.provider.Arguments; | ||
13 | 16 | ||
14 | class FuzzTestUtilsTest { | 17 | class FuzzTestUtilsTest { |
15 | @Test | 18 | @Test |
16 | void permutationInternalTest() { | 19 | void permutationInternalTest() { |
17 | List<List<Object>> res = FuzzTestUtils.permutationInternal(0, new Object[] { 1, 2, 3 }, | 20 | List<List<Object>> res = FuzzTestUtils.permutationInternal(0, new Object[]{1, 2, 3}, |
18 | new Object[] { 'a', 'b', 'c' }, new Object[] { "alpha", "beta", "gamma", "delta" }); | 21 | new Object[]{'a', 'b', 'c'}, new Object[]{"alpha", "beta", "gamma", "delta"}); |
19 | assertEquals(3 * 3 * 4, res.size()); | 22 | assertEquals(3 * 3 * 4, res.size()); |
20 | } | 23 | } |
21 | 24 | ||
22 | @Test | 25 | @Test |
23 | void permutationTest1() { | 26 | void permutationTest1() { |
24 | var res = FuzzTestUtils.permutation(new Object[] { 1, 2, 3 }, new Object[] { 'a', 'b', 'c' }, | 27 | var res = FuzzTestUtils.permutation(new Object[]{1, 2, 3}, new Object[]{'a', 'b', 'c'}, |
25 | new Object[] { "alpha", "beta", "gamma", "delta" }); | 28 | new Object[]{"alpha", "beta", "gamma", "delta"}); |
26 | assertEquals(3 * 3 * 4, res.count()); | 29 | assertEquals(3 * 3 * 4, res.count()); |
27 | } | 30 | } |
28 | 31 | ||
29 | @Test | 32 | @Test |
30 | void permutationTest2() { | 33 | void permutationTest2() { |
31 | var res = FuzzTestUtils.permutation(new Object[] { 1, 2, 3 }, new Object[] { 'a', 'b', 'c' }, | 34 | var res = FuzzTestUtils.permutation(new Object[]{1, 2, 3}, new Object[]{'a', 'b', 'c'}, |
32 | new Object[] { "alpha", "beta", "gamma", "delta" }); | 35 | new Object[]{"alpha", "beta", "gamma", "delta"}); |
33 | var arguments = res.findFirst().get().get(); | 36 | Optional<Arguments> first = res.findFirst(); |
37 | assertTrue(first.isPresent()); | ||
38 | var arguments = first.get().get(); | ||
34 | assertEquals(1, arguments[0]); | 39 | assertEquals(1, arguments[0]); |
35 | assertEquals('a', arguments[1]); | 40 | assertEquals('a', arguments[1]); |
36 | assertEquals("alpha", arguments[2]); | 41 | assertEquals("alpha", arguments[2]); |
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 f861f496..e7348370 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 | |||
@@ -14,9 +14,14 @@ import java.util.Map.Entry; | |||
14 | import static org.junit.jupiter.api.Assertions.*; | 14 | import static org.junit.jupiter.api.Assertions.*; |
15 | 15 | ||
16 | public class MapTestEnvironment<K, V> { | 16 | public class MapTestEnvironment<K, V> { |
17 | public static String[] prepareValues(int maxValue) { | 17 | public static String[] prepareValues(int maxValue, boolean nullDefault) { |
18 | String[] values = new String[maxValue]; | 18 | String[] values = new String[maxValue]; |
19 | values[0] = "DEFAULT"; | 19 | if (nullDefault) { |
20 | values[0] = null; | ||
21 | } else { | ||
22 | values[0] = "DEFAULT"; | ||
23 | } | ||
24 | |||
20 | for (int i = 1; i < values.length; i++) { | 25 | for (int i = 1; i < values.length; i++) { |
21 | values[i] = "VAL" + i; | 26 | values[i] = "VAL" + i; |
22 | } | 27 | } |
@@ -26,23 +31,18 @@ public class MapTestEnvironment<K, V> { | |||
26 | public static ContinousHashProvider<Integer> prepareHashProvider(final boolean evil) { | 31 | public static ContinousHashProvider<Integer> prepareHashProvider(final boolean evil) { |
27 | // Use maxPrime = 2147483629 | 32 | // Use maxPrime = 2147483629 |
28 | 33 | ||
29 | ContinousHashProvider<Integer> chp = new ContinousHashProvider<Integer>() { | 34 | return (key, index) -> { |
30 | 35 | if (evil && index < 15 && index < key / 3) { | |
31 | @Override | 36 | return 7; |
32 | public int getHash(Integer key, int index) { | 37 | } |
33 | if (evil && index < 15 && index < key / 3) { | 38 | int result = 1; |
34 | return 7; | 39 | final int prime = 31; |
35 | } | ||
36 | int result = 1; | ||
37 | final int prime = 31; | ||
38 | 40 | ||
39 | result = prime * result + key; | 41 | result = prime * result + key; |
40 | result = prime * result + index; | 42 | result = prime * result + index; |
41 | 43 | ||
42 | return result; | 44 | return result; |
43 | } | ||
44 | }; | 45 | }; |
45 | return chp; | ||
46 | } | 46 | } |
47 | 47 | ||
48 | public static void printStatus(String scenario, int actual, int max, String stepName) { | 48 | public static void printStatus(String scenario, int actual, int max, String stepName) { |
@@ -60,29 +60,17 @@ public class MapTestEnvironment<K, V> { | |||
60 | 60 | ||
61 | public static <K, V> void compareTwoMaps(String title, VersionedMap<K, V> map1, | 61 | public static <K, V> void compareTwoMaps(String title, VersionedMap<K, V> map1, |
62 | VersionedMap<K, V> map2, List<Throwable> errors) { | 62 | VersionedMap<K, V> map2, List<Throwable> errors) { |
63 | assertEqualsList(map1.getSize(), map2.getSize(), title + ": Sizes not equal", errors); | 63 | map1.checkIntegrity(); |
64 | map2.checkIntegrity(); | ||
64 | 65 | ||
65 | Cursor<K, V> cursor1 = map1.getAll(); | 66 | assertContentEqualsList(map1, map2, title + ": map1.contentEquals(map2)", errors); |
66 | Cursor<K, V> cursor2 = map2.getAll(); | 67 | assertContentEqualsList(map2, map1, title + ": map2.contentEquals(map1)", errors); |
67 | while (!cursor1.isTerminated()) { | 68 | assertEqualsList(map1.getSize(), map2.getSize(), title + ": Sizes not equal", errors); |
68 | if (cursor2.isTerminated()) { | ||
69 | fail("cursor 2 terminated before cursor1"); | ||
70 | } | ||
71 | assertEqualsList(cursor1.getKey(), cursor2.getKey(), title + ": Keys not equal", errors); | ||
72 | assertEqualsList(cursor2.getValue(), cursor2.getValue(), title + ": Values not equal", errors); | ||
73 | cursor1.move(); | ||
74 | cursor2.move(); | ||
75 | } | ||
76 | if (!cursor2.isTerminated()) { | ||
77 | fail("cursor 1 terminated before cursor 2"); | ||
78 | } | ||
79 | 69 | ||
80 | for (var mode : ContentHashCode.values()) { | 70 | for (var mode : ContentHashCode.values()) { |
81 | assertEqualsList(map1.contentHashCode(mode), map2.contentHashCode(mode), | 71 | assertEqualsList(map1.contentHashCode(mode), map2.contentHashCode(mode), |
82 | title + ": " + mode + " hashCode check", errors); | 72 | title + ": " + mode + " hashCode check", errors); |
83 | } | 73 | } |
84 | assertContentEqualsList(map1, map2, title + ": map1.contentEquals(map2)", errors); | ||
85 | assertContentEqualsList(map2, map1, title + ": map2.contentEquals(map1)", errors); | ||
86 | } | 74 | } |
87 | 75 | ||
88 | private static void assertEqualsList(Object o1, Object o2, String message, List<Throwable> errors) { | 76 | private static void assertEqualsList(Object o1, Object o2, String message, List<Throwable> errors) { |
@@ -112,29 +100,35 @@ public class MapTestEnvironment<K, V> { | |||
112 | } | 100 | } |
113 | } | 101 | } |
114 | 102 | ||
115 | public VersionedMapImpl<K, V> sut; | 103 | final private VersionedMap<K, V> sut; |
116 | Map<K, V> oracle = new HashMap<K, V>(); | 104 | final private V defaultValue; |
105 | Map<K, V> oracle = new HashMap<>(); | ||
117 | 106 | ||
118 | public MapTestEnvironment(VersionedMapImpl<K, V> sut) { | 107 | public MapTestEnvironment(VersionedMap<K, V> sut) { |
119 | this.sut = sut; | 108 | this.sut = sut; |
109 | this.defaultValue = sut.getDefaultValue(); | ||
120 | } | 110 | } |
121 | 111 | ||
122 | public void put(K key, V value) { | 112 | public void put(K key, V value) { |
123 | V oldSutValue = sut.put(key, value); | 113 | V oldSutValue = sut.put(key, value); |
124 | V oldOracleValue; | 114 | V oldOracleValue; |
125 | if (value != sut.getDefaultValue()) { | 115 | if (value != defaultValue) { |
126 | oldOracleValue = oracle.put(key, value); | 116 | oldOracleValue = oracle.put(key, value); |
127 | } else { | 117 | } else { |
128 | oldOracleValue = oracle.remove(key); | 118 | oldOracleValue = oracle.remove(key); |
129 | } | 119 | } |
130 | if (oldSutValue == sut.getDefaultValue() && oldOracleValue != null) { | 120 | if (oldSutValue == defaultValue && oldOracleValue != null) { |
131 | fail("After put, SUT old nodeId was default, but oracle old value was " + oldOracleValue); | 121 | fail("After put, SUT old nodeId was default, but oracle old value was " + oldOracleValue); |
132 | } | 122 | } |
133 | if (oldSutValue != sut.getDefaultValue()) { | 123 | if (oldSutValue != defaultValue) { |
134 | assertEquals(oldOracleValue, oldSutValue); | 124 | assertEquals(oldOracleValue, oldSutValue); |
135 | } | 125 | } |
136 | } | 126 | } |
137 | 127 | ||
128 | public long commit(){ | ||
129 | return sut.commit(); | ||
130 | } | ||
131 | |||
138 | public void checkEquivalence(String title) { | 132 | public void checkEquivalence(String title) { |
139 | // 0. Checking integrity | 133 | // 0. Checking integrity |
140 | try { | 134 | try { |
@@ -181,7 +175,7 @@ public class MapTestEnvironment<K, V> { | |||
181 | long sutSize = sut.getSize(); | 175 | long sutSize = sut.getSize(); |
182 | if (oracleSize != sutSize || oracleSize != elementsInSutEntrySet) { | 176 | if (oracleSize != sutSize || oracleSize != elementsInSutEntrySet) { |
183 | printComparison(); | 177 | printComparison(); |
184 | fail(title + ": Non-equivalent size() result: SUT.getSize()=" + sutSize + ", SUT.entryset.size=" | 178 | fail(title + ": Non-equivalent size() result: SUT.getSize()=" + sutSize + ", SUT.entrySet.size=" |
185 | + elementsInSutEntrySet + ", Oracle=" + oracleSize + "!"); | 179 | + elementsInSutEntrySet + ", Oracle=" + oracleSize + "!"); |
186 | } | 180 | } |
187 | } | 181 | } |
@@ -190,7 +184,8 @@ public class MapTestEnvironment<K, V> { | |||
190 | K previous = null; | 184 | K previous = null; |
191 | Cursor<K, V> cursor = versionedMap.getAll(); | 185 | Cursor<K, V> cursor = versionedMap.getAll(); |
192 | while (cursor.move()) { | 186 | while (cursor.move()) { |
193 | System.out.println(cursor.getKey() + " " + ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().getHash(cursor.getKey(), 0)); | 187 | //System.out.println(cursor.getKey() + " " + ((VersionedMapImpl<K, V>) versionedMap).getHashProvider() |
188 | // .getHash(cursor.getKey(), 0)); | ||
194 | if (previous != null) { | 189 | if (previous != null) { |
195 | int comparisonResult = ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().compare(previous, | 190 | int comparisonResult = ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().compare(previous, |
196 | cursor.getKey()); | 191 | cursor.getKey()); |
@@ -198,7 +193,6 @@ public class MapTestEnvironment<K, V> { | |||
198 | } | 193 | } |
199 | previous = cursor.getKey(); | 194 | previous = cursor.getKey(); |
200 | } | 195 | } |
201 | System.out.println(); | ||
202 | } | 196 | } |
203 | 197 | ||
204 | public void printComparison() { | 198 | public void printComparison() { |