diff options
author | 2023-07-18 15:38:59 +0200 | |
---|---|---|
committer | 2023-07-18 15:38:59 +0200 | |
commit | 89e142514ae45d793c7dbe38f728b33451261338 (patch) | |
tree | 17cebb157c5b3e65871384a0d71eb7f2dd54625b /subprojects/store/src | |
parent | Initialization bugs with empty DeltaDiffCursor fixed (diff) | |
download | refinery-89e142514ae45d793c7dbe38f728b33451261338.tar.gz refinery-89e142514ae45d793c7dbe38f728b33451261338.tar.zst refinery-89e142514ae45d793c7dbe38f728b33451261338.zip |
Fixing long-standing bug with state based diff cursor.
By implementing an InOrderMapCursor cursor, and a MapDiffCursor that synchronize two cursors.
Diffstat (limited to 'subprojects/store/src')
13 files changed, 611 insertions, 343 deletions
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 113874e7..beeed110 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 | |||
@@ -1,9 +1,6 @@ | |||
1 | package tools.refinery.store.map; | 1 | package tools.refinery.store.map; |
2 | 2 | ||
3 | import tools.refinery.store.map.internal.ImmutableNode; | 3 | import tools.refinery.store.map.internal.*; |
4 | import tools.refinery.store.map.internal.MapDiffCursor; | ||
5 | import tools.refinery.store.map.internal.Node; | ||
6 | import tools.refinery.store.map.internal.VersionedMapImpl; | ||
7 | 4 | ||
8 | import java.util.*; | 5 | import java.util.*; |
9 | 6 | ||
@@ -93,7 +90,7 @@ public class VersionedMapStoreImpl<K, V> implements VersionedMapStore<K, V> { | |||
93 | } else { | 90 | } else { |
94 | ArrayList<Long> existingKeys = new ArrayList<>(states.keySet()); | 91 | ArrayList<Long> existingKeys = new ArrayList<>(states.keySet()); |
95 | Collections.sort(existingKeys); | 92 | Collections.sort(existingKeys); |
96 | throw new IllegalArgumentException("Store does not contain state " + state + "! Avaliable states: " | 93 | throw new IllegalArgumentException("Store does not contain state " + state + "! Available states: " |
97 | + Arrays.toString(existingKeys.toArray())); | 94 | + Arrays.toString(existingKeys.toArray())); |
98 | } | 95 | } |
99 | } | 96 | } |
@@ -118,10 +115,10 @@ public class VersionedMapStoreImpl<K, V> implements VersionedMapStore<K, V> { | |||
118 | 115 | ||
119 | @Override | 116 | @Override |
120 | public DiffCursor<K, V> getDiffCursor(long fromState, long toState) { | 117 | public DiffCursor<K, V> getDiffCursor(long fromState, long toState) { |
121 | VersionedMap<K, V> map1 = createMap(fromState); | 118 | VersionedMapImpl<K, V> map1 = (VersionedMapImpl<K, V>) createMap(fromState); |
122 | VersionedMap<K, V> map2 = createMap(toState); | 119 | VersionedMapImpl<K, V> map2 = (VersionedMapImpl<K, V>) createMap(toState); |
123 | Cursor<K, V> cursor1 = map1.getAll(); | 120 | InOrderMapCursor<K, V> cursor1 = new InOrderMapCursor<>(map1); |
124 | Cursor<K, V> cursor2 = map2.getAll(); | 121 | InOrderMapCursor<K, V> cursor2 = new InOrderMapCursor<>(map2); |
125 | return new MapDiffCursor<>(this.hashProvider, this.defaultValue, cursor1, cursor2); | 122 | return new MapDiffCursor<>(this.defaultValue, cursor1, cursor2); |
126 | } | 123 | } |
127 | } | 124 | } |
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 914bab08..92446711 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 | |||
@@ -15,7 +15,7 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
15 | */ | 15 | */ |
16 | final int nodeMap; | 16 | final int nodeMap; |
17 | /** | 17 | /** |
18 | * Stores Keys, Values, and subnodes. Structure: (K,V)*,NODE; NODES are stored | 18 | * Stores Keys, Values, and sub-nodes. Structure: (K,V)*,NODE; NODES are stored |
19 | * backwards. | 19 | * backwards. |
20 | */ | 20 | */ |
21 | final Object[] content; | 21 | final Object[] content; |
@@ -65,24 +65,24 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
65 | int resultDataMap = 0; | 65 | int resultDataMap = 0; |
66 | int resultNodeMap = 0; | 66 | int resultNodeMap = 0; |
67 | final Object[] resultContent = new Object[size]; | 67 | final Object[] resultContent = new Object[size]; |
68 | int bitposition = 1; | 68 | int bitPosition = 1; |
69 | for (int i = 0; i < FACTOR; i++) { | 69 | for (int i = 0; i < FACTOR; i++) { |
70 | Object key = node.content[i * 2]; | 70 | Object key = node.content[i * 2]; |
71 | if (key != null) { | 71 | if (key != null) { |
72 | resultDataMap |= bitposition; | 72 | resultDataMap |= bitPosition; |
73 | resultContent[datas * 2] = key; | 73 | resultContent[datas * 2] = key; |
74 | resultContent[datas * 2 + 1] = node.content[i * 2 + 1]; | 74 | resultContent[datas * 2 + 1] = node.content[i * 2 + 1]; |
75 | datas++; | 75 | datas++; |
76 | } else { | 76 | } else { |
77 | @SuppressWarnings("unchecked") var subnode = (Node<K, V>) node.content[i * 2 + 1]; | 77 | @SuppressWarnings("unchecked") var subnode = (Node<K, V>) node.content[i * 2 + 1]; |
78 | if (subnode != null) { | 78 | if (subnode != null) { |
79 | ImmutableNode<K, V> immutableSubnode = subnode.toImmutable(cache); | 79 | ImmutableNode<K, V> immutableSubNode = subnode.toImmutable(cache); |
80 | resultNodeMap |= bitposition; | 80 | resultNodeMap |= bitPosition; |
81 | resultContent[size - 1 - nodes] = immutableSubnode; | 81 | resultContent[size - 1 - nodes] = immutableSubNode; |
82 | nodes++; | 82 | nodes++; |
83 | } | 83 | } |
84 | } | 84 | } |
85 | bitposition <<= 1; | 85 | bitPosition <<= 1; |
86 | } | 86 | } |
87 | final int resultHash = node.hashCode(); | 87 | final int resultHash = node.hashCode(); |
88 | var newImmutable = new ImmutableNode<K, V>(resultDataMap, resultNodeMap, resultContent, resultHash); | 88 | var newImmutable = new ImmutableNode<K, V>(resultDataMap, resultNodeMap, resultContent, resultHash); |
@@ -130,9 +130,9 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
130 | @Override | 130 | @Override |
131 | public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { | 131 | public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { |
132 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); | 132 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); |
133 | int bitposition = 1 << selectedHashFragment; | 133 | int bitPosition = 1 << selectedHashFragment; |
134 | if ((dataMap & bitposition) != 0) { | 134 | if ((dataMap & bitPosition) != 0) { |
135 | int keyIndex = 2 * index(dataMap, bitposition); | 135 | int keyIndex = 2 * index(dataMap, bitPosition); |
136 | @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; | 136 | @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; |
137 | if (keyCandidate.equals(key)) { | 137 | if (keyCandidate.equals(key)) { |
138 | if (value == defaultValue) { | 138 | if (value == defaultValue) { |
@@ -159,8 +159,8 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
159 | return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); | 159 | return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); |
160 | } | 160 | } |
161 | } | 161 | } |
162 | } else if ((nodeMap & bitposition) != 0) { | 162 | } else if ((nodeMap & bitPosition) != 0) { |
163 | int keyIndex = content.length - 1 - index(nodeMap, bitposition); | 163 | int keyIndex = content.length - 1 - index(nodeMap, bitPosition); |
164 | @SuppressWarnings("unchecked") var subNode = (ImmutableNode<K, V>) content[keyIndex]; | 164 | @SuppressWarnings("unchecked") var subNode = (ImmutableNode<K, V>) content[keyIndex]; |
165 | int newDepth = incrementDepth(depth); | 165 | int newDepth = incrementDepth(depth); |
166 | int newHash = newHash(hashProvider, key, hash, newDepth); | 166 | int newHash = newHash(hashProvider, key, hash, newDepth); |
@@ -254,6 +254,49 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
254 | } | 254 | } |
255 | 255 | ||
256 | @Override | 256 | @Override |
257 | @SuppressWarnings("unchecked") | ||
258 | boolean moveToNextInorder(InOrderMapCursor<K, V> cursor) { | ||
259 | if(cursor.nodeIndexStack.peek()==null) { | ||
260 | throw new IllegalStateException("Cursor moved to the next state when the state is empty."); | ||
261 | } | ||
262 | |||
263 | int position = cursor.nodeIndexStack.peek(); | ||
264 | for (int index = position + 1; index < FACTOR; index++) { | ||
265 | final int mask = 1<<index; | ||
266 | if((this.dataMap & mask) != 0) { | ||
267 | // data found | ||
268 | cursor.nodeIndexStack.pop(); | ||
269 | cursor.nodeIndexStack.push(index); | ||
270 | |||
271 | cursor.key = (K) this.content[2 * index(dataMap, mask)]; | ||
272 | cursor.value = (V) this.content[2 * index(dataMap, mask) +1]; | ||
273 | return true; | ||
274 | } else if((this.nodeMap & mask) != 0) { | ||
275 | // node found | ||
276 | Node<K,V> subnode = (Node<K, V>) this.content[this.content.length - 1 - index(nodeMap, mask)]; | ||
277 | cursor.nodeIndexStack.pop(); | ||
278 | cursor.nodeIndexStack.push(index); | ||
279 | cursor.nodeIndexStack.push(InOrderMapCursor.INDEX_START); | ||
280 | cursor.nodeStack.push(subnode); | ||
281 | |||
282 | return subnode.moveToNextInorder(cursor); | ||
283 | } | ||
284 | } | ||
285 | |||
286 | // nothing found | ||
287 | cursor.nodeStack.pop(); | ||
288 | cursor.nodeIndexStack.pop(); | ||
289 | if (!cursor.nodeStack.isEmpty()) { | ||
290 | Node<K, V> supernode = cursor.nodeStack.peek(); | ||
291 | return supernode.moveToNextInorder(cursor); | ||
292 | } else { | ||
293 | cursor.key = null; | ||
294 | cursor.value = null; | ||
295 | return false; | ||
296 | } | ||
297 | } | ||
298 | |||
299 | @Override | ||
257 | public void prettyPrint(StringBuilder builder, int depth, int code) { | 300 | public void prettyPrint(StringBuilder builder, int depth, int code) { |
258 | builder.append("\t".repeat(Math.max(0, depth))); | 301 | builder.append("\t".repeat(Math.max(0, depth))); |
259 | if (code >= 0) { | 302 | if (code >= 0) { |
@@ -348,8 +391,8 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
348 | var mutableSubnode = (Node<?, ?>) mutable.content[i * 2 + 1]; | 391 | var mutableSubnode = (Node<?, ?>) mutable.content[i * 2 + 1]; |
349 | if (mutableSubnode != null) { | 392 | if (mutableSubnode != null) { |
350 | if (datas * 2 + nodes + 1 <= immutableLength) { | 393 | if (datas * 2 + nodes + 1 <= immutableLength) { |
351 | Object immutableSubnode = immutable.content[immutableLength - 1 - nodes]; | 394 | Object immutableSubNode = immutable.content[immutableLength - 1 - nodes]; |
352 | if (!mutableSubnode.equals(immutableSubnode)) { | 395 | if (!mutableSubnode.equals(immutableSubNode)) { |
353 | return false; | 396 | return false; |
354 | } | 397 | } |
355 | nodes++; | 398 | nodes++; |
@@ -359,6 +402,7 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
359 | } | 402 | } |
360 | } | 403 | } |
361 | } | 404 | } |
362 | return true; | 405 | |
406 | return datas * 2 + nodes == immutable.content.length; | ||
363 | } | 407 | } |
364 | } | 408 | } |
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..c559d9ad --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/InOrderMapCursor.java | |||
@@ -0,0 +1,141 @@ | |||
1 | package tools.refinery.store.map.internal; | ||
2 | |||
3 | import tools.refinery.store.map.AnyVersionedMap; | ||
4 | import tools.refinery.store.map.ContentHashCode; | ||
5 | import tools.refinery.store.map.Cursor; | ||
6 | import tools.refinery.store.map.VersionedMap; | ||
7 | |||
8 | import java.util.*; | ||
9 | |||
10 | public class InOrderMapCursor<K, V> implements Cursor<K, V> { | ||
11 | // Constants | ||
12 | static final int INDEX_START = -1; | ||
13 | |||
14 | // Tree stack | ||
15 | ArrayDeque<Node<K, V>> nodeStack; | ||
16 | ArrayDeque<Integer> nodeIndexStack; | ||
17 | |||
18 | |||
19 | // Values | ||
20 | K key; | ||
21 | V value; | ||
22 | |||
23 | // Hash code for checking concurrent modifications | ||
24 | final VersionedMap<K, V> map; | ||
25 | final int creationHash; | ||
26 | |||
27 | public InOrderMapCursor(VersionedMapImpl<K, V> map) { | ||
28 | // Initializing tree stack | ||
29 | super(); | ||
30 | this.nodeStack = new ArrayDeque<>(); | ||
31 | this.nodeIndexStack = new ArrayDeque<>(); | ||
32 | if (map.root != null) { | ||
33 | this.nodeStack.add(map.root); | ||
34 | this.nodeIndexStack.push(INDEX_START); | ||
35 | } | ||
36 | |||
37 | // Initializing cache | ||
38 | this.key = null; | ||
39 | this.value = null; | ||
40 | |||
41 | // Initializing state | ||
42 | this.map = map; | ||
43 | this.creationHash = map.contentHashCode(ContentHashCode.APPROXIMATE_FAST); | ||
44 | } | ||
45 | |||
46 | public K getKey() { | ||
47 | return key; | ||
48 | } | ||
49 | |||
50 | public V getValue() { | ||
51 | return value; | ||
52 | } | ||
53 | |||
54 | public boolean isTerminated() { | ||
55 | return this.nodeStack.isEmpty(); | ||
56 | } | ||
57 | |||
58 | public boolean move() { | ||
59 | if (isDirty()) { | ||
60 | throw new ConcurrentModificationException(); | ||
61 | } | ||
62 | if (!isTerminated()) { | ||
63 | var node = this.nodeStack.peek(); | ||
64 | if (node == null) { | ||
65 | throw new IllegalStateException("Cursor is not terminated but the current node is missing"); | ||
66 | } | ||
67 | boolean result = node.moveToNextInorder(this); | ||
68 | if (this.nodeIndexStack.size() != this.nodeStack.size()) { | ||
69 | throw new IllegalArgumentException("Node stack is corrupted by illegal moves!"); | ||
70 | } | ||
71 | return result; | ||
72 | } | ||
73 | return false; | ||
74 | } | ||
75 | |||
76 | public boolean skipCurrentNode() { | ||
77 | nodeStack.pop(); | ||
78 | nodeIndexStack.pop(); | ||
79 | return move(); | ||
80 | } | ||
81 | |||
82 | @Override | ||
83 | public boolean isDirty() { | ||
84 | return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; | ||
85 | } | ||
86 | |||
87 | @Override | ||
88 | public Set<AnyVersionedMap> getDependingMaps() { | ||
89 | return Set.of(this.map); | ||
90 | } | ||
91 | |||
92 | public static <K, V> boolean sameSubNode(InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) { | ||
93 | Node<K, V> nodeOfCursor1 = cursor1.nodeStack.peek(); | ||
94 | Node<K, V> nodeOfCursor2 = cursor2.nodeStack.peek(); | ||
95 | return Objects.equals(nodeOfCursor1, nodeOfCursor2); | ||
96 | } | ||
97 | |||
98 | /** | ||
99 | * Compares the state of two cursors started on two {@link VersionedMap} of the same | ||
100 | * {@link tools.refinery.store.map.VersionedMapStore}. | ||
101 | * @param <K> Key type | ||
102 | * @param <V> Value type | ||
103 | * @param cursor1 first cursor | ||
104 | * @param cursor2 second cursor | ||
105 | * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the | ||
106 | * same position. | ||
107 | */ | ||
108 | public static <K, V> int comparePosition(InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) { | ||
109 | // If the state does not determine the order, then compare @nodeIndexStack. | ||
110 | Iterator<Integer> nodeIndexStack1 = cursor1.nodeIndexStack.descendingIterator(); | ||
111 | Iterator<Integer> nodeIndexStack2 = cursor2.nodeIndexStack.descendingIterator(); | ||
112 | |||
113 | while(nodeIndexStack1.hasNext() && nodeIndexStack2.hasNext()){ | ||
114 | final int index1 = nodeIndexStack1.next(); | ||
115 | final int index2 = nodeIndexStack2.next(); | ||
116 | if(index1 < index2) { | ||
117 | return 1; | ||
118 | } else if(index1 > index2) { | ||
119 | return -1; | ||
120 | } | ||
121 | } | ||
122 | |||
123 | return 0; | ||
124 | } | ||
125 | |||
126 | /** | ||
127 | * Compares the depth of two cursors started on @{@link VersionedMap} of the same | ||
128 | * {@link tools.refinery.store.map.VersionedMapStore}. | ||
129 | * @param <K> Key type | ||
130 | * @param <V> Value type | ||
131 | * @param cursor1 first cursor | ||
132 | * @param cursor2 second cursor | ||
133 | * @return Positive number if cursor 1 is deeper, negative number if cursor 2 is deeper, and 0 if they are at the | ||
134 | * same depth. | ||
135 | */ | ||
136 | public static <K, V> int compareDepth(InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) { | ||
137 | int d1 = cursor1.nodeIndexStack.size(); | ||
138 | int d2 = cursor2.nodeIndexStack.size(); | ||
139 | return Integer.compare(d1, d2); | ||
140 | } | ||
141 | } | ||
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 50fcfcd3..7e4f82e8 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 | |||
@@ -7,7 +7,6 @@ import tools.refinery.store.map.VersionedMap; | |||
7 | 7 | ||
8 | import java.util.ArrayDeque; | 8 | import java.util.ArrayDeque; |
9 | import java.util.ConcurrentModificationException; | 9 | import java.util.ConcurrentModificationException; |
10 | import java.util.Iterator; | ||
11 | import java.util.Set; | 10 | import java.util.Set; |
12 | 11 | ||
13 | public class MapCursor<K, V> implements Cursor<K, V> { | 12 | public class MapCursor<K, V> implements Cursor<K, V> { |
@@ -79,13 +78,6 @@ public class MapCursor<K, V> implements Cursor<K, V> { | |||
79 | return false; | 78 | return false; |
80 | } | 79 | } |
81 | 80 | ||
82 | public boolean skipCurrentNode() { | ||
83 | nodeStack.pop(); | ||
84 | nodeIndexStack.pop(); | ||
85 | dataIndex = INDEX_FINISH; | ||
86 | return move(); | ||
87 | } | ||
88 | |||
89 | @Override | 81 | @Override |
90 | public boolean isDirty() { | 82 | public boolean isDirty() { |
91 | return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; | 83 | return this.map.contentHashCode(ContentHashCode.APPROXIMATE_FAST) != this.creationHash; |
@@ -95,55 +87,4 @@ public class MapCursor<K, V> implements Cursor<K, V> { | |||
95 | public Set<AnyVersionedMap> getDependingMaps() { | 87 | public Set<AnyVersionedMap> getDependingMaps() { |
96 | return Set.of(this.map); | 88 | return Set.of(this.map); |
97 | } | 89 | } |
98 | |||
99 | public static <K, V> boolean sameSubNode(MapCursor<K, V> cursor1, MapCursor<K, V> cursor2) { | ||
100 | Node<K, V> nodeOfCursor1 = cursor1.nodeStack.peek(); | ||
101 | Node<K, V> nodeOfCursor2 = cursor2.nodeStack.peek(); | ||
102 | if (nodeOfCursor1 != null && nodeOfCursor2 != null) { | ||
103 | return nodeOfCursor1.equals(nodeOfCursor2); | ||
104 | } else { | ||
105 | return false; | ||
106 | } | ||
107 | } | ||
108 | |||
109 | /** | ||
110 | * Compares the state of two cursors started on two @{@link VersionedMap of the }same | ||
111 | * {@link tools.refinery.store.map.VersionedMapStore}. | ||
112 | * @param <K> Key type | ||
113 | * @param <V> Value type | ||
114 | * @param cursor1 first cursor | ||
115 | * @param cursor2 second cursor | ||
116 | * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the | ||
117 | * same position. | ||
118 | */ | ||
119 | public static <K, V> int compare(MapCursor<K, V> cursor1, MapCursor<K, V> cursor2) { | ||
120 | // Checking the state of the cursors | ||
121 | if(!cursor1.isTerminated() && cursor2.isTerminated()) return -1; | ||
122 | else if(cursor1.isTerminated() && !cursor2.isTerminated()) return 1; | ||
123 | else if(cursor1.isTerminated() && cursor2.isTerminated()) return 0; | ||
124 | |||
125 | // If the state does not determine the order, then compare @nodeIndexStack. | ||
126 | Iterator<Integer> stack1 = cursor1.nodeIndexStack.descendingIterator(); | ||
127 | Iterator<Integer> stack2 = cursor2.nodeIndexStack.descendingIterator(); | ||
128 | if (stack1.hasNext()) { | ||
129 | if (!stack2.hasNext()) { | ||
130 | // stack 2 has no more element, thus stack 1 is deeper | ||
131 | return 1; | ||
132 | } | ||
133 | int val1 = stack1.next(); | ||
134 | int val2 = stack2.next(); | ||
135 | if (val1 < val2) { | ||
136 | return -1; | ||
137 | } else if (val2 < val1) { | ||
138 | return 1; | ||
139 | } | ||
140 | } | ||
141 | if (stack2.hasNext()) { | ||
142 | // stack 2 has more element, thus stack 2 is deeper | ||
143 | return 1; | ||
144 | } | ||
145 | |||
146 | // two cursors are equally deep decide by data index | ||
147 | return Integer.compare(cursor1.dataIndex, cursor2.dataIndex); | ||
148 | } | ||
149 | } | 90 | } |
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 6c076ce5..59e8d738 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 | |||
@@ -1,7 +1,6 @@ | |||
1 | package tools.refinery.store.map.internal; | 1 | package tools.refinery.store.map.internal; |
2 | 2 | ||
3 | import tools.refinery.store.map.AnyVersionedMap; | 3 | import tools.refinery.store.map.AnyVersionedMap; |
4 | import tools.refinery.store.map.ContinousHashProvider; | ||
5 | import tools.refinery.store.map.Cursor; | 4 | import tools.refinery.store.map.Cursor; |
6 | import tools.refinery.store.map.DiffCursor; | 5 | import tools.refinery.store.map.DiffCursor; |
7 | 6 | ||
@@ -14,37 +13,78 @@ import java.util.stream.Stream; | |||
14 | * A cursor representing the difference between two states of a map. | 13 | * A cursor representing the difference between two states of a map. |
15 | * | 14 | * |
16 | * @author Oszkar Semerath | 15 | * @author Oszkar Semerath |
17 | * | ||
18 | */ | 16 | */ |
19 | public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> { | 17 | public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> { |
18 | private enum State { | ||
19 | /** | ||
20 | * initialized state. | ||
21 | */ | ||
22 | INIT, | ||
23 | /** | ||
24 | * Unstable state. | ||
25 | */ | ||
26 | MOVING_MOVING_SAME_KEY_SAME_VALUE, | ||
27 | /** | ||
28 | * Both cursors are moving, and they are on the same sub-node. | ||
29 | */ | ||
30 | MOVING_MOVING_SAME_NODE, | ||
31 | /** | ||
32 | * Both cursors are moving, cursor 1 is behind. | ||
33 | */ | ||
34 | MOVING_MOVING_BEHIND1, | ||
35 | /** | ||
36 | * Both cursors are moving, cursor 2 is behind. | ||
37 | */ | ||
38 | MOVING_MOVING_BEHIND2, | ||
39 | /** | ||
40 | * Both cursors are moving, cursor 1 is on the same key as cursor 2, values are different | ||
41 | */ | ||
42 | MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE, | ||
43 | /** | ||
44 | * Cursor 1 is moving, Cursor 2 is terminated. | ||
45 | */ | ||
46 | MOVING_TERMINATED, | ||
47 | /** | ||
48 | * Cursor 1 is terminated , Cursor 2 is moving. | ||
49 | */ | ||
50 | TERMINATED_MOVING, | ||
51 | /** | ||
52 | * Both cursors are terminated. | ||
53 | */ | ||
54 | TERMINATED_TERMINATED, | ||
55 | /** | ||
56 | * Both Cursors are moving, and they are on an incomparable position. | ||
57 | * It is resolved by showing Cursor 1. | ||
58 | */ | ||
59 | MOVING_MOVING_HASH1, | ||
60 | /** | ||
61 | * Both Cursors are moving, and they are on an incomparable position. | ||
62 | * It is resolved by showing Cursor 2. | ||
63 | */ | ||
64 | MOVING_MOVING_HASH2 | ||
65 | } | ||
66 | |||
20 | /** | 67 | /** |
21 | * Default nodeId representing missing elements. | 68 | * Default nodeId representing missing elements. |
22 | */ | 69 | */ |
23 | private final V defaultValue; | 70 | private final V defaultValue; |
24 | private final MapCursor<K, V> cursor1; | 71 | private final InOrderMapCursor<K, V> cursor1; |
25 | private final MapCursor<K, V> cursor2; | 72 | private final InOrderMapCursor<K, V> cursor2; |
26 | private final ContinousHashProvider<? super K> hashProvider; | 73 | |
74 | // State | ||
75 | State state = State.INIT; | ||
27 | 76 | ||
28 | // Values | 77 | // Values |
29 | private K key; | 78 | private K key; |
30 | private V fromValue; | 79 | private V fromValue; |
31 | private V toValue; | 80 | private V toValue; |
32 | 81 | ||
33 | // State | ||
34 | /** | ||
35 | * Positive number if cursor 1 is behind, negative number if cursor 2 is behind, | ||
36 | * and 0 if they are at the same position. | ||
37 | */ | ||
38 | private int cursorRelation; | ||
39 | private HashClash hashClash = HashClash.NONE; | ||
40 | 82 | ||
41 | public MapDiffCursor(ContinousHashProvider<? super K> hashProvider, V defaultValue, Cursor<K, V> cursor1, | 83 | public MapDiffCursor(V defaultValue, InOrderMapCursor<K, V> cursor1, InOrderMapCursor<K, V> cursor2) { |
42 | Cursor<K, V> cursor2) { | ||
43 | super(); | 84 | super(); |
44 | this.hashProvider = hashProvider; | ||
45 | this.defaultValue = defaultValue; | 85 | this.defaultValue = defaultValue; |
46 | this.cursor1 = (MapCursor<K, V>) cursor1; | 86 | this.cursor1 = cursor1; |
47 | this.cursor2 = (MapCursor<K, V>) cursor2; | 87 | this.cursor2 = cursor2; |
48 | } | 88 | } |
49 | 89 | ||
50 | @Override | 90 | @Override |
@@ -68,7 +108,7 @@ public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> { | |||
68 | } | 108 | } |
69 | 109 | ||
70 | public boolean isTerminated() { | 110 | public boolean isTerminated() { |
71 | return cursor1.isTerminated() && cursor2.isTerminated(); | 111 | return this.state == State.TERMINATED_TERMINATED; |
72 | } | 112 | } |
73 | 113 | ||
74 | @Override | 114 | @Override |
@@ -78,148 +118,142 @@ public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> { | |||
78 | 118 | ||
79 | @Override | 119 | @Override |
80 | public Set<AnyVersionedMap> getDependingMaps() { | 120 | public Set<AnyVersionedMap> getDependingMaps() { |
81 | return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()) | 121 | return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()).map(AnyVersionedMap.class::cast).collect(Collectors.toUnmodifiableSet()); |
82 | .map(AnyVersionedMap.class::cast) | ||
83 | .collect(Collectors.toUnmodifiableSet()); | ||
84 | } | ||
85 | |||
86 | protected void updateState() { | ||
87 | if (!isTerminated()) { | ||
88 | this.cursorRelation = MapCursor.compare(cursor1, cursor2); | ||
89 | if (cursorRelation > 0 || cursor2.isTerminated()) { | ||
90 | this.key = cursor1.getKey(); | ||
91 | this.fromValue = cursor1.getValue(); | ||
92 | this.toValue = defaultValue; | ||
93 | } else if (cursorRelation < 0 || cursor1.isTerminated()) { | ||
94 | this.key = cursor2.getKey(); | ||
95 | this.fromValue = defaultValue; | ||
96 | this.toValue = cursor1.getValue(); | ||
97 | } else { | ||
98 | // cursor1 = cursor2 | ||
99 | if (cursor1.getKey().equals(cursor2.getKey())) { | ||
100 | this.key = cursor1.getKey(); | ||
101 | this.fromValue = cursor1.getValue(); | ||
102 | this.toValue = defaultValue; | ||
103 | } else { | ||
104 | resolveHashClashWithFirstEntry(); | ||
105 | } | ||
106 | } | ||
107 | } | ||
108 | } | 122 | } |
109 | 123 | ||
110 | protected void resolveHashClashWithFirstEntry() { | 124 | private boolean isInStableState() { |
111 | int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key); | 125 | return this.state != State.MOVING_MOVING_SAME_KEY_SAME_VALUE |
112 | if (compareResult < 0) { | 126 | && this.state != State.MOVING_MOVING_SAME_NODE && this.state != State.INIT; |
113 | this.hashClash = HashClash.STUCK_CURSOR_2; | ||
114 | this.cursorRelation = 0; | ||
115 | this.key = cursor1.key; | ||
116 | this.fromValue = cursor1.value; | ||
117 | this.toValue = defaultValue; | ||
118 | } else if (compareResult > 0) { | ||
119 | this.hashClash = HashClash.STUCK_CURSOR_1; | ||
120 | this.cursorRelation = 0; | ||
121 | this.key = cursor2.key; | ||
122 | this.fromValue = defaultValue; | ||
123 | this.toValue = cursor2.value; | ||
124 | } else { | ||
125 | throw new IllegalArgumentException("Inconsistent compare result for diffCursor"); | ||
126 | } | ||
127 | } | 127 | } |
128 | 128 | ||
129 | protected boolean isInHashClash() { | 129 | private boolean updateAndReturnWithResult() { |
130 | return this.hashClash != HashClash.NONE; | 130 | return switch (this.state) { |
131 | case INIT -> throw new IllegalStateException("DiffCursor terminated without starting!"); | ||
132 | case MOVING_MOVING_SAME_KEY_SAME_VALUE, MOVING_MOVING_SAME_NODE -> | ||
133 | throw new IllegalStateException("DiffCursor terminated in unstable state!"); | ||
134 | case MOVING_MOVING_BEHIND1, MOVING_TERMINATED, MOVING_MOVING_HASH1 -> { | ||
135 | this.key = this.cursor1.getKey(); | ||
136 | this.fromValue = this.cursor1.getValue(); | ||
137 | this.toValue = this.defaultValue; | ||
138 | yield true; | ||
139 | } | ||
140 | case MOVING_MOVING_BEHIND2, TERMINATED_MOVING, MOVING_MOVING_HASH2 -> { | ||
141 | this.key = this.cursor2.getKey(); | ||
142 | this.fromValue = this.defaultValue; | ||
143 | this.toValue = cursor2.getValue(); | ||
144 | yield true; | ||
145 | } | ||
146 | case MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE -> { | ||
147 | this.key = this.cursor1.getKey(); | ||
148 | this.fromValue = this.cursor1.getValue(); | ||
149 | this.toValue = this.cursor2.getValue(); | ||
150 | yield true; | ||
151 | } | ||
152 | case TERMINATED_TERMINATED -> { | ||
153 | this.key = null; | ||
154 | this.fromValue = null; | ||
155 | this.toValue = null; | ||
156 | yield false; | ||
157 | } | ||
158 | }; | ||
131 | } | 159 | } |
132 | 160 | ||
133 | protected void resolveHashClashWithSecondEntry() { | 161 | public boolean move() { |
134 | switch (this.hashClash) { | 162 | do { |
135 | case STUCK_CURSOR_1 -> { | 163 | this.state = moveOne(this.state); |
136 | this.hashClash = HashClash.NONE; | 164 | } while (!isInStableState()); |
137 | this.cursorRelation = 0; | 165 | return updateAndReturnWithResult(); |
138 | this.key = cursor1.key; | ||
139 | this.fromValue = cursor1.value; | ||
140 | this.toValue = defaultValue; | ||
141 | } | ||
142 | case STUCK_CURSOR_2 -> { | ||
143 | this.hashClash = HashClash.NONE; | ||
144 | this.cursorRelation = 0; | ||
145 | this.key = cursor2.key; | ||
146 | this.fromValue = defaultValue; | ||
147 | this.toValue = cursor2.value; | ||
148 | } | ||
149 | default -> throw new IllegalArgumentException("Inconsistent compare result for diffCursor"); | ||
150 | } | ||
151 | } | 166 | } |
152 | 167 | ||
153 | /** | 168 | private State moveOne(State currentState) { |
154 | * Checks if two states has the same values, i.e., there is no difference. | 169 | return switch (currentState) { |
155 | * @return whether two states has the same values | 170 | case INIT, MOVING_MOVING_HASH2, MOVING_MOVING_SAME_KEY_SAME_VALUE, MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE -> { |
156 | */ | 171 | boolean cursor1Moved = cursor1.move(); |
157 | protected boolean sameValues() { | 172 | boolean cursor2Moved = cursor2.move(); |
158 | if(cursor1.isTerminated() || cursor2.isTerminated()) return false; | 173 | yield recalculateStateAfterCursorMovement(cursor1Moved, cursor2Moved); |
159 | else return Objects.equals(this.fromValue, this.toValue); | 174 | } |
175 | case MOVING_MOVING_SAME_NODE -> { | ||
176 | boolean cursor1Moved = cursor1.skipCurrentNode(); | ||
177 | boolean cursor2Moved = cursor2.skipCurrentNode(); | ||
178 | yield recalculateStateAfterCursorMovement(cursor1Moved, cursor2Moved); | ||
179 | } | ||
180 | case MOVING_MOVING_BEHIND1 -> { | ||
181 | boolean cursorMoved = cursor1.move(); | ||
182 | if (cursorMoved) { | ||
183 | yield recalculateStateBasedOnCursorRelation(); | ||
184 | } else { | ||
185 | yield State.TERMINATED_MOVING; | ||
186 | } | ||
187 | } | ||
188 | case MOVING_MOVING_BEHIND2 -> { | ||
189 | boolean cursorMoved = cursor2.move(); | ||
190 | if (cursorMoved) { | ||
191 | yield recalculateStateBasedOnCursorRelation(); | ||
192 | } else { | ||
193 | yield State.MOVING_TERMINATED; | ||
194 | } | ||
195 | } | ||
196 | case TERMINATED_MOVING -> { | ||
197 | boolean cursorMoved = cursor2.move(); | ||
198 | if (cursorMoved) { | ||
199 | yield State.TERMINATED_MOVING; | ||
200 | } else { | ||
201 | yield State.TERMINATED_TERMINATED; | ||
202 | } | ||
203 | } | ||
204 | case MOVING_TERMINATED -> { | ||
205 | boolean cursorMoved = cursor1.move(); | ||
206 | if (cursorMoved) { | ||
207 | yield State.MOVING_TERMINATED; | ||
208 | } else { | ||
209 | yield State.TERMINATED_TERMINATED; | ||
210 | } | ||
211 | } | ||
212 | case MOVING_MOVING_HASH1 -> State.MOVING_MOVING_HASH2; | ||
213 | case TERMINATED_TERMINATED -> throw new IllegalStateException("Trying to move while terminated!"); | ||
214 | }; | ||
160 | } | 215 | } |
161 | 216 | ||
162 | protected boolean moveOne() { | 217 | private State recalculateStateAfterCursorMovement(boolean cursor1Moved, boolean cursor2Moved) { |
163 | if (isTerminated()) { | 218 | if (cursor1Moved && cursor2Moved) { |
164 | return false; | 219 | return recalculateStateBasedOnCursorRelation(); |
165 | } | 220 | } else if (cursor1Moved) { |
166 | if (this.cursorRelation > 0 || cursor2.isTerminated()) { | 221 | return State.MOVING_TERMINATED; |
167 | return cursor1.move(); | 222 | } else if (cursor2Moved) { |
168 | } else if (this.cursorRelation < 0 || cursor1.isTerminated()) { | 223 | return State.TERMINATED_MOVING; |
169 | return cursor2.move(); | ||
170 | } else { | 224 | } else { |
171 | boolean moved1 = cursor1.move(); | 225 | return State.TERMINATED_TERMINATED; |
172 | boolean moved2 = cursor2.move(); | ||
173 | return moved1 && moved2; | ||
174 | } | 226 | } |
175 | } | 227 | } |
176 | 228 | ||
177 | private boolean skipNode() { | 229 | private State recalculateStateBasedOnCursorRelation() { |
178 | if (isTerminated()) { | 230 | final int relation = InOrderMapCursor.comparePosition(cursor1, cursor2); |
179 | throw new IllegalStateException("DiffCursor tries to skip when terminated!"); | ||
180 | } | ||
181 | boolean update1 = cursor1.skipCurrentNode(); | ||
182 | boolean update2 = cursor2.skipCurrentNode(); | ||
183 | updateState(); | ||
184 | return update1 && update2; | ||
185 | } | ||
186 | 231 | ||
187 | protected boolean moveToConsistentState() { | 232 | if (relation > 0) { |
188 | if (!isTerminated()) { | 233 | return State.MOVING_MOVING_BEHIND1; |
189 | boolean changed; | 234 | } else if (relation < 0) { |
190 | boolean lastResult = true; | 235 | return State.MOVING_MOVING_BEHIND2; |
191 | do { | ||
192 | changed = false; | ||
193 | if (MapCursor.sameSubNode(cursor1, cursor2)) { | ||
194 | lastResult = skipNode(); | ||
195 | changed = true; | ||
196 | } | ||
197 | if (sameValues()) { | ||
198 | lastResult = moveOne(); | ||
199 | changed = true; | ||
200 | } | ||
201 | updateState(); | ||
202 | } while (changed && !isTerminated()); | ||
203 | return lastResult; | ||
204 | } else { | ||
205 | return false; | ||
206 | } | 236 | } |
207 | } | ||
208 | 237 | ||
209 | public boolean move() { | 238 | if (InOrderMapCursor.sameSubNode(cursor1, cursor2)) { |
210 | if (!isTerminated()) { | 239 | return State.MOVING_MOVING_SAME_NODE; |
211 | if (isInHashClash()) { | 240 | } else if (Objects.equals(cursor1.getKey(), cursor2.getKey())) { |
212 | this.resolveHashClashWithSecondEntry(); | 241 | if (Objects.equals(cursor1.getValue(), cursor2.getValue())) { |
213 | return true; | 242 | return State.MOVING_MOVING_SAME_KEY_SAME_VALUE; |
214 | } else { | 243 | } else { |
215 | if (moveOne()) { | 244 | return State.MOVING_MOVING_SAME_KEY_DIFFERENT_VALUE; |
216 | return moveToConsistentState(); | ||
217 | } else { | ||
218 | return false; | ||
219 | } | ||
220 | } | 245 | } |
246 | } | ||
247 | |||
248 | final int depth = InOrderMapCursor.compareDepth(cursor1, cursor2); | ||
249 | |||
250 | if (depth > 0) { | ||
251 | return State.MOVING_MOVING_BEHIND1; | ||
252 | } else if (depth < 0) { | ||
253 | return State.MOVING_MOVING_BEHIND2; | ||
254 | } else { | ||
255 | return State.MOVING_MOVING_HASH1; | ||
256 | } | ||
221 | 257 | ||
222 | } else | ||
223 | return false; | ||
224 | } | 258 | } |
225 | } | 259 | } |
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 cdc66a10..81bf6188 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 | |||
@@ -39,12 +39,12 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
39 | int dataUsed = 0; | 39 | int dataUsed = 0; |
40 | int nodeUsed = 0; | 40 | int nodeUsed = 0; |
41 | for (int i = 0; i < FACTOR; i++) { | 41 | for (int i = 0; i < FACTOR; i++) { |
42 | int bitposition = 1 << i; | 42 | int bitPosition = 1 << i; |
43 | if ((node.dataMap & bitposition) != 0) { | 43 | if ((node.dataMap & bitPosition) != 0) { |
44 | content[2 * i] = node.content[dataUsed * 2]; | 44 | content[2 * i] = node.content[dataUsed * 2]; |
45 | content[2 * i + 1] = node.content[dataUsed * 2 + 1]; | 45 | content[2 * i + 1] = node.content[dataUsed * 2 + 1]; |
46 | dataUsed++; | 46 | dataUsed++; |
47 | } else if ((node.nodeMap & bitposition) != 0) { | 47 | } else if ((node.nodeMap & bitPosition) != 0) { |
48 | content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed]; | 48 | content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed]; |
49 | nodeUsed++; | 49 | nodeUsed++; |
50 | } | 50 | } |
@@ -80,7 +80,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
80 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); | 80 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); |
81 | @SuppressWarnings("unchecked") K keyCandidate = (K) content[2 * selectedHashFragment]; | 81 | @SuppressWarnings("unchecked") K keyCandidate = (K) content[2 * selectedHashFragment]; |
82 | if (keyCandidate != null) { | 82 | if (keyCandidate != null) { |
83 | // If has key | 83 | // If it has key |
84 | if (keyCandidate.equals(key)) { | 84 | if (keyCandidate.equals(key)) { |
85 | // The key is equals to an existing key -> update entry | 85 | // The key is equals to an existing key -> update entry |
86 | if (value == defaultValue) { | 86 | if (value == defaultValue) { |
@@ -101,24 +101,22 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
101 | return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment); | 101 | return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment); |
102 | } | 102 | } |
103 | } | 103 | } |
104 | } | ||
105 | // If it does not have key, check for value | ||
106 | @SuppressWarnings("unchecked") var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1]; | ||
107 | if (nodeCandidate != null) { | ||
108 | // If it has value, it is a sub-node -> update that | ||
109 | int newDepth = incrementDepth(depth); | ||
110 | var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, newHash(hashProvider, key, hash, newDepth), newDepth); | ||
111 | return updateWithSubNode(selectedHashFragment, newNode, (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); | ||
104 | } else { | 112 | } else { |
105 | // If it does not have key, check for value | 113 | // If it does not have value, put it in the empty place |
106 | @SuppressWarnings("unchecked") var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1]; | 114 | if (value == defaultValue) { |
107 | if (nodeCandidate != null) { | 115 | // don't need to add new key-value pair |
108 | // If it has value, it is a subnode -> upate that | 116 | oldValueBox.setOldValue(defaultValue); |
109 | int newDepth = incrementDepth(depth); | 117 | return this; |
110 | var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, newHash(hashProvider, key, hash, newDepth), newDepth); | ||
111 | return updateWithSubNode(selectedHashFragment, newNode, (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); | ||
112 | } else { | 118 | } else { |
113 | // If it does not have value, put it in the empty place | 119 | return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue); |
114 | if (value == defaultValue) { | ||
115 | // dont need to add new key-value pair | ||
116 | oldValueBox.setOldValue(defaultValue); | ||
117 | return this; | ||
118 | } else { | ||
119 | return addEntry(key, value, oldValueBox, selectedHashFragment, defaultValue); | ||
120 | } | ||
121 | |||
122 | } | 120 | } |
123 | } | 121 | } |
124 | } | 122 | } |
@@ -170,7 +168,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
170 | if (immutableNewNode != null) { | 168 | if (immutableNewNode != null) { |
171 | int orphaned = immutableNewNode.isOrphaned(); | 169 | int orphaned = immutableNewNode.isOrphaned(); |
172 | if (orphaned >= 0) { | 170 | if (orphaned >= 0) { |
173 | // orphan subnode data is replaced with data | 171 | // orphan sub-node data is replaced with data |
174 | content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2]; | 172 | content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2]; |
175 | content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1]; | 173 | content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1]; |
176 | invalidateHash(); | 174 | invalidateHash(); |
@@ -227,11 +225,11 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
227 | 225 | ||
228 | // Pass everything as parameters for performance. | 226 | // Pass everything as parameters for performance. |
229 | @SuppressWarnings("squid:S107") | 227 | @SuppressWarnings("squid:S107") |
230 | private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1, int oldHash1, K key2, V value2, int oldHash2, int newdepth) { | 228 | private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1, int oldHash1, K key2, V value2, int oldHash2, int newDepth) { |
231 | int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth); | 229 | int newHash1 = newHash(hashProvider, key1, oldHash1, newDepth); |
232 | int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth); | 230 | int newHash2 = newHash(hashProvider, key2, oldHash2, newDepth); |
233 | int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth)); | 231 | int newFragment1 = hashFragment(newHash1, shiftDepth(newDepth)); |
234 | int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth)); | 232 | int newFragment2 = hashFragment(newHash2, shiftDepth(newDepth)); |
235 | 233 | ||
236 | MutableNode<K, V> subNode = new MutableNode<>(); | 234 | MutableNode<K, V> subNode = new MutableNode<>(); |
237 | if (newFragment1 != newFragment2) { | 235 | if (newFragment1 != newFragment2) { |
@@ -241,7 +239,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
241 | subNode.content[newFragment2 * 2] = key2; | 239 | subNode.content[newFragment2 * 2] = key2; |
242 | subNode.content[newFragment2 * 2 + 1] = value2; | 240 | subNode.content[newFragment2 * 2 + 1] = value2; |
243 | } else { | 241 | } else { |
244 | MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newdepth)); | 242 | MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newDepth)); |
245 | subNode.content[newFragment1 * 2 + 1] = subSubNode; | 243 | subNode.content[newFragment1 * 2 + 1] = subSubNode; |
246 | } | 244 | } |
247 | subNode.invalidateHash(); | 245 | subNode.invalidateHash(); |
@@ -305,13 +303,13 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
305 | cursor.dataIndex = MapCursor.INDEX_FINISH; | 303 | cursor.dataIndex = MapCursor.INDEX_FINISH; |
306 | } | 304 | } |
307 | 305 | ||
308 | // 2. look inside the subnodes | 306 | // 2. look inside the sub-nodes |
309 | if(cursor.nodeIndexStack.peek()==null) { | 307 | if(cursor.nodeIndexStack.peek()==null) { |
310 | throw new IllegalStateException("Cursor moved to the next state when the state is empty."); | 308 | throw new IllegalStateException("Cursor moved to the next state when the state is empty."); |
311 | } | 309 | } |
312 | for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) { | 310 | for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) { |
313 | if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) { | 311 | if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) { |
314 | // 2.1 found next subnode, move down to the subnode | 312 | // 2.1 found next sub-node, move down to the sub-node |
315 | Node<K, V> subnode = (Node<K, V>) this.content[index * 2 + 1]; | 313 | Node<K, V> subnode = (Node<K, V>) this.content[index * 2 + 1]; |
316 | 314 | ||
317 | cursor.dataIndex = MapCursor.INDEX_START; | 315 | cursor.dataIndex = MapCursor.INDEX_START; |
@@ -323,7 +321,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
323 | return subnode.moveToNext(cursor); | 321 | return subnode.moveToNext(cursor); |
324 | } | 322 | } |
325 | } | 323 | } |
326 | // 3. no subnode found, move up | 324 | // 3. no sub-node found, move up |
327 | cursor.nodeStack.pop(); | 325 | cursor.nodeStack.pop(); |
328 | cursor.nodeIndexStack.pop(); | 326 | cursor.nodeIndexStack.pop(); |
329 | if (!cursor.nodeStack.isEmpty()) { | 327 | if (!cursor.nodeStack.isEmpty()) { |
@@ -337,6 +335,49 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
337 | } | 335 | } |
338 | 336 | ||
339 | @Override | 337 | @Override |
338 | @SuppressWarnings("unchecked") | ||
339 | boolean moveToNextInorder(InOrderMapCursor<K,V> cursor) { | ||
340 | if(cursor.nodeIndexStack.peek()==null || cursor.nodeStack.peek()==null) { | ||
341 | throw new IllegalStateException("Cursor moved to the next state when the state is empty."); | ||
342 | } | ||
343 | |||
344 | int position = cursor.nodeIndexStack.peek(); | ||
345 | |||
346 | for (int index = position + 1; index < FACTOR; index++) { | ||
347 | // data found | ||
348 | if (this.content[index * 2] != null) { | ||
349 | cursor.nodeIndexStack.pop(); | ||
350 | cursor.nodeIndexStack.push(index); | ||
351 | |||
352 | cursor.key = (K) this.content[index * 2]; | ||
353 | cursor.value = (V) this.content[index * 2 + 1]; | ||
354 | return true; | ||
355 | } else if (this.content[index * 2 +1] != null) { | ||
356 | // sub-node found | ||
357 | Node<K,V> subnode = (Node<K, V>) this.content[index * 2 +1]; | ||
358 | cursor.nodeIndexStack.pop(); | ||
359 | cursor.nodeIndexStack.push(index); | ||
360 | cursor.nodeIndexStack.push(InOrderMapCursor.INDEX_START); | ||
361 | cursor.nodeStack.push(subnode); | ||
362 | |||
363 | return subnode.moveToNextInorder(cursor); | ||
364 | } | ||
365 | } | ||
366 | |||
367 | // nothing found | ||
368 | cursor.nodeStack.pop(); | ||
369 | cursor.nodeIndexStack.pop(); | ||
370 | if (!cursor.nodeStack.isEmpty()) { | ||
371 | Node<K, V> supernode = cursor.nodeStack.peek(); | ||
372 | return supernode.moveToNextInorder(cursor); | ||
373 | } else { | ||
374 | cursor.key = null; | ||
375 | cursor.value = null; | ||
376 | return false; | ||
377 | } | ||
378 | } | ||
379 | |||
380 | @Override | ||
340 | public void prettyPrint(StringBuilder builder, int depth, int code) { | 381 | public void prettyPrint(StringBuilder builder, int depth, int code) { |
341 | builder.append("\t".repeat(Math.max(0, depth))); | 382 | builder.append("\t".repeat(Math.max(0, depth))); |
342 | if (code >= 0) { | 383 | if (code >= 0) { |
@@ -361,7 +402,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
361 | } | 402 | } |
362 | } | 403 | } |
363 | builder.append(")"); | 404 | builder.append(")"); |
364 | // print subnodes | 405 | // print sub-nodes |
365 | for (int i = 0; i < FACTOR; i++) { | 406 | for (int i = 0; i < FACTOR; i++) { |
366 | if (content[2 * i] == null && content[2 * i + 1] != null) { | 407 | if (content[2 * i] == null && content[2 * i + 1] != null) { |
367 | @SuppressWarnings("unchecked") Node<K, V> subNode = (Node<K, V>) content[2 * i + 1]; | 408 | @SuppressWarnings("unchecked") Node<K, V> subNode = (Node<K, V>) content[2 * i + 1]; |
@@ -397,7 +438,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
397 | } | 438 | } |
398 | } | 439 | } |
399 | } | 440 | } |
400 | // check subnodes | 441 | // check sub-nodes |
401 | for (int i = 0; i < FACTOR; i++) { | 442 | for (int i = 0; i < FACTOR; i++) { |
402 | if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { | 443 | if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { |
403 | @SuppressWarnings("unchecked") var subNode = (Node<K, V>) this.content[2 * i + 1]; | 444 | @SuppressWarnings("unchecked") var subNode = (Node<K, V>) this.content[2 * i + 1]; |
@@ -421,13 +462,11 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
421 | 462 | ||
422 | @Override | 463 | @Override |
423 | public int hashCode() { | 464 | public int hashCode() { |
424 | if (this.cachedHashValid) { | 465 | if (!this.cachedHashValid) { |
425 | return this.cachedHash; | ||
426 | } else { | ||
427 | this.cachedHash = Arrays.hashCode(content); | 466 | this.cachedHash = Arrays.hashCode(content); |
428 | this.cachedHashValid = true; | 467 | this.cachedHashValid = true; |
429 | return this.cachedHash; | ||
430 | } | 468 | } |
469 | return this.cachedHash; | ||
431 | } | 470 | } |
432 | 471 | ||
433 | @Override | 472 | @Override |
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 c49be280..3dd332da 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 | |||
@@ -108,10 +108,12 @@ public abstract class Node<K, V> { | |||
108 | * @return Whether there was a next value to move on. | 108 | * @return Whether there was a next value to move on. |
109 | */ | 109 | */ |
110 | abstract boolean moveToNext(MapCursor<K, V> cursor); | 110 | abstract boolean moveToNext(MapCursor<K, V> cursor); |
111 | abstract boolean moveToNextInorder(InOrderMapCursor<K, V> cursor); | ||
111 | 112 | ||
112 | ///////// FOR printing | 113 | ///////// FOR printing |
113 | public abstract void prettyPrint(StringBuilder builder, int depth, int code); | 114 | public abstract void prettyPrint(StringBuilder builder, int depth, int code); |
114 | 115 | ||
116 | |||
115 | @Override | 117 | @Override |
116 | public String toString() { | 118 | public String toString() { |
117 | StringBuilder stringBuilder = new StringBuilder(); | 119 | StringBuilder stringBuilder = new StringBuilder(); |
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 fb359431..2ceca463 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 | |||
@@ -75,7 +75,9 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> { | |||
75 | Iterator<K> keyIterator = keys.iterator(); | 75 | Iterator<K> keyIterator = keys.iterator(); |
76 | Iterator<V> valueIterator = values.iterator(); | 76 | Iterator<V> valueIterator = values.iterator(); |
77 | while (keyIterator.hasNext()) { | 77 | while (keyIterator.hasNext()) { |
78 | this.put(keyIterator.next(), valueIterator.next()); | 78 | var key = keyIterator.next(); |
79 | var value = valueIterator.next(); | ||
80 | this.put(key,value); | ||
79 | } | 81 | } |
80 | } else { | 82 | } else { |
81 | while (cursor.move()) { | 83 | while (cursor.move()) { |
@@ -109,12 +111,10 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> { | |||
109 | 111 | ||
110 | @Override | 112 | @Override |
111 | public DiffCursor<K, V> getDiffCursor(long toVersion) { | 113 | public DiffCursor<K, V> getDiffCursor(long toVersion) { |
112 | 114 | InOrderMapCursor<K, V> fromCursor = new InOrderMapCursor<>(this); | |
113 | Cursor<K, V> fromCursor = this.getAll(); | 115 | VersionedMapImpl<K, V> toMap = (VersionedMapImpl<K, V>) this.store.createMap(toVersion); |
114 | VersionedMap<K, V> toMap = this.store.createMap(toVersion); | 116 | InOrderMapCursor<K, V> toCursor = new InOrderMapCursor<>(toMap); |
115 | Cursor<K, V> toCursor = toMap.getAll(); | 117 | return new MapDiffCursor<>(this.defaultValue, fromCursor, toCursor); |
116 | return new MapDiffCursor<>(this.hashProvider, this.defaultValue, fromCursor, toCursor); | ||
117 | |||
118 | } | 118 | } |
119 | 119 | ||
120 | 120 | ||
@@ -152,7 +152,11 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> { | |||
152 | @Override | 152 | @Override |
153 | public int contentHashCode(ContentHashCode mode) { | 153 | public int contentHashCode(ContentHashCode mode) { |
154 | // Calculating the root hashCode is always fast, because {@link Node} caches its hashCode. | 154 | // Calculating the root hashCode is always fast, because {@link Node} caches its hashCode. |
155 | return Objects.hashCode(root); | 155 | if(root == null) { |
156 | return 0; | ||
157 | } else { | ||
158 | return root.hashCode(); | ||
159 | } | ||
156 | } | 160 | } |
157 | 161 | ||
158 | @Override | 162 | @Override |
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 6d82f5d7..c850d334 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 | |||
@@ -4,11 +4,9 @@ import tools.refinery.store.map.Cursor; | |||
4 | import tools.refinery.store.map.DiffCursor; | 4 | import tools.refinery.store.map.DiffCursor; |
5 | import tools.refinery.store.map.VersionedMap; | 5 | import tools.refinery.store.map.VersionedMap; |
6 | import tools.refinery.store.map.VersionedMapStore; | 6 | import tools.refinery.store.map.VersionedMapStore; |
7 | import tools.refinery.store.map.internal.MapDiffCursor; | ||
8 | import tools.refinery.store.model.Interpretation; | 7 | import tools.refinery.store.model.Interpretation; |
9 | import tools.refinery.store.model.InterpretationListener; | 8 | import tools.refinery.store.model.InterpretationListener; |
10 | import tools.refinery.store.model.Model; | 9 | import tools.refinery.store.model.Model; |
11 | import tools.refinery.store.model.TupleHashProvider; | ||
12 | import tools.refinery.store.representation.AnySymbol; | 10 | import tools.refinery.store.representation.AnySymbol; |
13 | import tools.refinery.store.representation.Symbol; | 11 | import tools.refinery.store.representation.Symbol; |
14 | import tools.refinery.store.tuple.Tuple; | 12 | import tools.refinery.store.tuple.Tuple; |
@@ -19,16 +17,13 @@ import java.util.List; | |||
19 | public class VersionedInterpretation<T> implements Interpretation<T> { | 17 | public class VersionedInterpretation<T> implements Interpretation<T> { |
20 | private final ModelImpl model; | 18 | private final ModelImpl model; |
21 | private final Symbol<T> symbol; | 19 | private final Symbol<T> symbol; |
22 | private final VersionedMapStore<Tuple, T> store; | ||
23 | private final VersionedMap<Tuple, T> map; | 20 | private final VersionedMap<Tuple, T> map; |
24 | private final List<InterpretationListener<T>> listeners = new ArrayList<>(); | 21 | private final List<InterpretationListener<T>> listeners = new ArrayList<>(); |
25 | private final List<InterpretationListener<T>> restoreListeners = new ArrayList<>(); | 22 | private final List<InterpretationListener<T>> restoreListeners = new ArrayList<>(); |
26 | 23 | ||
27 | private VersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMapStore<Tuple, T> store, | 24 | private VersionedInterpretation(ModelImpl model, Symbol<T> symbol, VersionedMap<Tuple, T> map) { |
28 | VersionedMap<Tuple, T> map) { | ||
29 | this.model = model; | 25 | this.model = model; |
30 | this.symbol = symbol; | 26 | this.symbol = symbol; |
31 | this.store = store; | ||
32 | this.map = map; | 27 | this.map = map; |
33 | } | 28 | } |
34 | 29 | ||
@@ -111,9 +106,7 @@ public class VersionedInterpretation<T> implements Interpretation<T> { | |||
111 | 106 | ||
112 | @Override | 107 | @Override |
113 | public DiffCursor<Tuple, T> getDiffCursor(long to) { | 108 | public DiffCursor<Tuple, T> getDiffCursor(long to) { |
114 | var fromCursor = getAll(); | 109 | return map.getDiffCursor(to); |
115 | var toCursor = store.createMap(to).getAll(); | ||
116 | return new MapDiffCursor<>(TupleHashProvider.INSTANCE, symbol.defaultValue(), fromCursor, toCursor); | ||
117 | } | 110 | } |
118 | 111 | ||
119 | public long commit() { | 112 | public long commit() { |
@@ -148,7 +141,7 @@ public class VersionedInterpretation<T> implements Interpretation<T> { | |||
148 | @SuppressWarnings("unchecked") | 141 | @SuppressWarnings("unchecked") |
149 | var typedSymbol = (Symbol<T>) symbol; | 142 | var typedSymbol = (Symbol<T>) symbol; |
150 | var map = store.createMap(); | 143 | var map = store.createMap(); |
151 | return new VersionedInterpretation<>(model, typedSymbol, store, map); | 144 | return new VersionedInterpretation<>(model, typedSymbol, map); |
152 | } | 145 | } |
153 | 146 | ||
154 | static <T> VersionedInterpretation<T> of(ModelImpl model, AnySymbol symbol, VersionedMapStore<Tuple, T> store, | 147 | static <T> VersionedInterpretation<T> of(ModelImpl model, AnySymbol symbol, VersionedMapStore<Tuple, T> store, |
@@ -156,6 +149,6 @@ public class VersionedInterpretation<T> implements Interpretation<T> { | |||
156 | @SuppressWarnings("unchecked") | 149 | @SuppressWarnings("unchecked") |
157 | var typedSymbol = (Symbol<T>) symbol; | 150 | var typedSymbol = (Symbol<T>) symbol; |
158 | var map = store.createMap(state); | 151 | var map = store.createMap(state); |
159 | return new VersionedInterpretation<>(model, typedSymbol, store, map); | 152 | return new VersionedInterpretation<>(model, typedSymbol, map); |
160 | } | 153 | } |
161 | } | 154 | } |
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..05cf5a74 --- /dev/null +++ b/subprojects/store/src/test/java/tools/refinery/store/map/tests/InOrderCursorTest.java | |||
@@ -0,0 +1,49 @@ | |||
1 | package tools.refinery.store.map.tests; | ||
2 | |||
3 | import org.junit.jupiter.api.Test; | ||
4 | import tools.refinery.store.map.VersionedMapStoreBuilder; | ||
5 | import tools.refinery.store.map.internal.InOrderMapCursor; | ||
6 | import tools.refinery.store.map.internal.VersionedMapImpl; | ||
7 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; | ||
8 | |||
9 | import static org.junit.jupiter.api.Assertions.*; | ||
10 | |||
11 | class InOrderCursorTest { | ||
12 | @Test | ||
13 | void testCursor() { | ||
14 | var store = VersionedMapStoreBuilder.<Integer,String>builder() | ||
15 | .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE) | ||
16 | .setStateBasedImmutableWhenCommitting(true) | ||
17 | .setHashProvider(MapTestEnvironment.prepareHashProvider(false)) | ||
18 | .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy.SHARED_NODE_CACHE) | ||
19 | .setDefaultValue("x") | ||
20 | .buildOne(); | ||
21 | |||
22 | VersionedMapImpl<Integer,String> map = (VersionedMapImpl<Integer,String>) store.createMap(); | ||
23 | checkMove(map,0); | ||
24 | |||
25 | map.put(1,"A"); | ||
26 | map.commit(); | ||
27 | checkMove(map,1); | ||
28 | |||
29 | |||
30 | map.put(2,"B"); | ||
31 | map.commit(); | ||
32 | checkMove(map,2); | ||
33 | |||
34 | map.put(3,"C"); | ||
35 | map.commit(); | ||
36 | checkMove(map,3); | ||
37 | |||
38 | } | ||
39 | |||
40 | private void checkMove(VersionedMapImpl<Integer,String> map, int num) { | ||
41 | InOrderMapCursor<Integer,String> cursor = new InOrderMapCursor<>(map); | ||
42 | for(int i=0; i<num; i++) { | ||
43 | assertTrue(cursor.move()); | ||
44 | assertFalse(cursor.isTerminated()); | ||
45 | } | ||
46 | assertFalse(cursor.move()); | ||
47 | assertTrue(cursor.isTerminated()); | ||
48 | } | ||
49 | } | ||
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 bf409a74..b087906d 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,7 +5,10 @@ import org.junit.jupiter.api.Timeout; | |||
5 | import org.junit.jupiter.params.ParameterizedTest; | 5 | import org.junit.jupiter.params.ParameterizedTest; |
6 | import org.junit.jupiter.params.provider.Arguments; | 6 | import org.junit.jupiter.params.provider.Arguments; |
7 | import org.junit.jupiter.params.provider.MethodSource; | 7 | import org.junit.jupiter.params.provider.MethodSource; |
8 | import tools.refinery.store.map.*; | 8 | import tools.refinery.store.map.DiffCursor; |
9 | import tools.refinery.store.map.VersionedMap; | ||
10 | import tools.refinery.store.map.VersionedMapStore; | ||
11 | import tools.refinery.store.map.VersionedMapStoreBuilder; | ||
9 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; | 12 | import tools.refinery.store.map.tests.fuzz.utils.FuzzTestUtils; |
10 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; | 13 | import tools.refinery.store.map.tests.utils.MapTestEnvironment; |
11 | 14 | ||
@@ -16,87 +19,104 @@ import static org.junit.jupiter.api.Assertions.fail; | |||
16 | import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*; | 19 | import static tools.refinery.store.map.tests.fuzz.utils.FuzzTestCollections.*; |
17 | 20 | ||
18 | class DiffCursorFuzzTest { | 21 | class DiffCursorFuzzTest { |
19 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, | 22 | private void runFuzzTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean nullDefault, |
20 | boolean nullDefault, int commitFrequency, VersionedMapStoreBuilder<Integer, String> builder) { | 23 | int commitFrequency, boolean commitBeforeDiffCursor, |
24 | VersionedMapStoreBuilder<Integer, String> builder) { | ||
21 | String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); | 25 | String[] values = MapTestEnvironment.prepareValues(maxValue, nullDefault); |
22 | 26 | ||
23 | VersionedMapStore<Integer, String> store = builder.setDefaultValue(values[0]).buildOne(); | 27 | VersionedMapStore<Integer, String> store = builder.setDefaultValue(values[0]).buildOne(); |
24 | iterativeRandomPutsAndCommitsThenDiffCursor(scenario, store, steps, maxKey, values, seed, commitFrequency); | 28 | iterativeRandomPutsAndCommitsThenDiffCursor(scenario, store, steps, maxKey, values, seed, commitFrequency, |
29 | commitBeforeDiffCursor); | ||
25 | } | 30 | } |
26 | 31 | ||
27 | private void iterativeRandomPutsAndCommitsThenDiffCursor(String scenario, VersionedMapStore<Integer, String> store, | 32 | private void iterativeRandomPutsAndCommitsThenDiffCursor(String scenario, VersionedMapStore<Integer, String> store, |
28 | int steps, int maxKey, String[] values, int seed, int commitFrequency) { | 33 | int steps, int maxKey, String[] values, int seed, |
29 | // 1. build a map with versions | 34 | int commitFrequency, boolean commitBeforeDiffCursor) { |
30 | Random r = new Random(seed); | 35 | |
31 | VersionedMap<Integer, String> versioned = store.createMap(); | ||
32 | int largestCommit = -1; | 36 | int largestCommit = -1; |
33 | 37 | ||
34 | for (int i = 0; i < steps; i++) { | 38 | { |
35 | int index = i + 1; | 39 | // 1. build a map with versions |
36 | int nextKey = r.nextInt(maxKey); | 40 | Random r = new Random(seed); |
37 | String nextValue = values[r.nextInt(values.length)]; | 41 | VersionedMap<Integer, String> versioned = store.createMap(); |
38 | try { | 42 | for (int i = 0; i < steps; i++) { |
39 | versioned.put(nextKey, nextValue); | 43 | int index = i + 1; |
40 | } catch (Exception exception) { | 44 | int nextKey = r.nextInt(maxKey); |
41 | exception.printStackTrace(); | 45 | String nextValue = values[r.nextInt(values.length)]; |
42 | fail(scenario + ":" + index + ": exception happened: " + exception); | ||
43 | } | ||
44 | if (index % commitFrequency == 0) { | ||
45 | long version = versioned.commit(); | ||
46 | largestCommit = (int) version; | ||
47 | } | ||
48 | if (index % 10000 == 0) | ||
49 | System.out.println(scenario + ":" + index + "/" + steps + " building finished"); | ||
50 | } | ||
51 | // 2. create a non-versioned map, | ||
52 | VersionedMap<Integer, String> moving = store.createMap(); | ||
53 | Random r2 = new Random(seed + 1); | ||
54 | |||
55 | final int diffTravelFrequency = commitFrequency * 2; | ||
56 | for (int i = 0; i < steps; i++) { | ||
57 | int index = i + 1; | ||
58 | if (index % diffTravelFrequency == 0) { | ||
59 | // diff-travel | ||
60 | long travelToVersion = r2.nextInt(largestCommit + 1); | ||
61 | DiffCursor<Integer, String> diffCursor = moving.getDiffCursor(travelToVersion); | ||
62 | moving.putAll(diffCursor); | ||
63 | |||
64 | } else { | ||
65 | // random puts | ||
66 | int nextKey = r2.nextInt(maxKey); | ||
67 | String nextValue = values[r2.nextInt(values.length)]; | ||
68 | try { | 46 | try { |
69 | moving.put(nextKey, nextValue); | 47 | versioned.put(nextKey, nextValue); |
70 | } catch (Exception exception) { | 48 | } catch (Exception exception) { |
71 | exception.printStackTrace(); | 49 | exception.printStackTrace(); |
72 | fail(scenario + ":" + index + ": exception happened: " + exception); | 50 | fail(scenario + ":" + index + ": exception happened: " + exception); |
73 | } | 51 | } |
74 | if (index % commitFrequency == 0) { | 52 | if (index % commitFrequency == 0) { |
75 | versioned.commit(); | 53 | long version = versioned.commit(); |
54 | largestCommit = (int) version; | ||
76 | } | 55 | } |
77 | if (index % 10000 == 0) | 56 | if (index % 10000 == 0) |
78 | System.out.println(scenario + ":" + index + "/" + steps + " building finished"); | 57 | System.out.println(scenario + ":" + index + "/" + steps + " building finished"); |
79 | } | 58 | } |
80 | } | 59 | } |
81 | 60 | ||
61 | { | ||
62 | // 2. create a non-versioned map, | ||
63 | VersionedMap<Integer, String> moving = store.createMap(); | ||
64 | Random r2 = new Random(seed + 1); | ||
65 | |||
66 | final int diffTravelFrequency = commitFrequency * 2; | ||
67 | for (int i = 0; i < steps; i++) { | ||
68 | int index = i + 1; | ||
69 | if (index % diffTravelFrequency == 0) { | ||
70 | // diff-travel | ||
71 | long travelToVersion = r2.nextInt(largestCommit + 1); | ||
72 | |||
73 | VersionedMap<Integer, String> oracle = store.createMap(travelToVersion); | ||
74 | |||
75 | if(commitBeforeDiffCursor) { | ||
76 | moving.commit(); | ||
77 | } | ||
78 | DiffCursor<Integer, String> diffCursor = moving.getDiffCursor(travelToVersion); | ||
79 | moving.putAll(diffCursor); | ||
80 | moving.commit(); | ||
81 | |||
82 | MapTestEnvironment.compareTwoMaps(scenario + ":c" + index, oracle, moving); | ||
83 | |||
84 | moving.restore(travelToVersion); | ||
85 | |||
86 | } else { | ||
87 | // random puts | ||
88 | int nextKey = r2.nextInt(maxKey); | ||
89 | String nextValue = values[r2.nextInt(values.length)]; | ||
90 | try { | ||
91 | moving.put(nextKey, nextValue); | ||
92 | } catch (Exception exception) { | ||
93 | exception.printStackTrace(); | ||
94 | fail(scenario + ":" + index + ": exception happened: " + exception); | ||
95 | } | ||
96 | if (index % 10000 == 0) | ||
97 | System.out.println(scenario + ":" + index + "/" + steps + " building finished"); | ||
98 | } | ||
99 | } | ||
100 | } | ||
82 | } | 101 | } |
83 | 102 | ||
84 | public static final String title = "DiffCursor {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} " + | 103 | public static final String title = "DiffCursor {index}/{0} Steps={1} Keys={2} Values={3} nullDefault={4} " + |
85 | "commit frequency={5} seed={6} config={7}"; | 104 | "commit frequency={5} seed={6} commit before diff={7} config={8}"; |
86 | 105 | ||
87 | @ParameterizedTest(name = title) | 106 | @ParameterizedTest(name = title) |
88 | @MethodSource | 107 | @MethodSource |
89 | @Timeout(value = 10) | 108 | @Timeout(value = 10) |
90 | @Tag("fuzz") | 109 | @Tag("fuzz") |
91 | void parametrizedFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, | 110 | void parametrizedFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, |
92 | int seed, VersionedMapStoreBuilder<Integer, String> builder) { | 111 | int commitFrequency, int seed, boolean commitBeforeDiffCursor, |
93 | runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, | 112 | VersionedMapStoreBuilder<Integer, String> builder) { |
94 | noKeys, noValues, nullDefault, commitFrequency, builder); | 113 | runFuzzTest("DiffCursorS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, |
114 | noKeys, noValues, nullDefault, commitFrequency, commitBeforeDiffCursor, builder); | ||
95 | } | 115 | } |
96 | 116 | ||
97 | static Stream<Arguments> parametrizedFuzz() { | 117 | static Stream<Arguments> parametrizedFuzz() { |
98 | return FuzzTestUtils.permutationWithSize(new Object[]{100}, keyCounts, valueCounts, nullDefaultOptions, | 118 | return FuzzTestUtils.permutationWithSize(new Object[]{500}, keyCounts, valueCounts, nullDefaultOptions, |
99 | commitFrequencyOptions, randomSeedOptions, storeConfigs); | 119 | commitFrequencyOptions, randomSeedOptions, new Object[]{false,true}, storeConfigs); |
100 | } | 120 | } |
101 | 121 | ||
102 | @ParameterizedTest(name = title) | 122 | @ParameterizedTest(name = title) |
@@ -104,9 +124,9 @@ class DiffCursorFuzzTest { | |||
104 | @Tag("fuzz") | 124 | @Tag("fuzz") |
105 | @Tag("slow") | 125 | @Tag("slow") |
106 | void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, | 126 | void parametrizedSlowFuzz(int ignoredTests, int steps, int noKeys, int noValues, boolean nullDefault, int commitFrequency, |
107 | int seed, VersionedMapStoreBuilder<Integer, String> builder) { | 127 | int seed, boolean commitBeforeDiffCursor, VersionedMapStoreBuilder<Integer, String> builder) { |
108 | runFuzzTest("MutableImmutableCompareS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, | 128 | runFuzzTest("DiffCursorS" + steps + "K" + noKeys + "V" + noValues + "s" + seed, seed, steps, noKeys, noValues, |
109 | nullDefault, commitFrequency, builder); | 129 | nullDefault, commitFrequency, commitBeforeDiffCursor, builder); |
110 | } | 130 | } |
111 | 131 | ||
112 | static Stream<Arguments> parametrizedSlowFuzz() { | 132 | static Stream<Arguments> parametrizedSlowFuzz() { |
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 index fb6b28d8..b344d9b9 100644 --- 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 | |||
@@ -5,23 +5,25 @@ import tools.refinery.store.map.tests.utils.MapTestEnvironment; | |||
5 | 5 | ||
6 | public final class FuzzTestCollections { | 6 | public final class FuzzTestCollections { |
7 | public static final Object[] stepCounts = {FuzzTestUtils.FAST_STEP_COUNT}; | 7 | public static final Object[] stepCounts = {FuzzTestUtils.FAST_STEP_COUNT}; |
8 | public static final Object[] keyCounts = {1, 32, 32 * 32}; | 8 | public static final Object[] keyCounts = {1 , 32, 32 * 32}; |
9 | public static final Object[] valueCounts = {2, 3}; | 9 | public static final Object[] valueCounts = {2, 3}; |
10 | public static final Object[] nullDefaultOptions = {false, true}; | 10 | public static final Object[] nullDefaultOptions = {false, true}; |
11 | public static final Object[] commitFrequencyOptions = {10, 10, 100}; | 11 | public static final Object[] commitFrequencyOptions = {1, 10, 100}; |
12 | public static final Object[] randomSeedOptions = {1/*, 2, 3*/}; | 12 | public static final Object[] randomSeedOptions = {1}; |
13 | public static final Object[] storeConfigs = { | 13 | public static final Object[] storeConfigs = { |
14 | // State based | 14 | // State based |
15 | VersionedMapStoreBuilder.<Integer,String>builder() | 15 | VersionedMapStoreBuilder.<Integer,String>builder() |
16 | .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE) | 16 | .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE) |
17 | .setStateBasedImmutableWhenCommitting(true) | 17 | .setStateBasedImmutableWhenCommitting(true) |
18 | .setHashProvider(MapTestEnvironment.prepareHashProvider(false)) | 18 | .setHashProvider(MapTestEnvironment.prepareHashProvider(false)) |
19 | .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy.SHARED_NODE_CACHE), | 19 | .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy |
20 | .SHARED_NODE_CACHE), | ||
20 | VersionedMapStoreBuilder.<Integer,String>builder() | 21 | VersionedMapStoreBuilder.<Integer,String>builder() |
21 | .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE) | 22 | .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE) |
22 | .setStateBasedImmutableWhenCommitting(true) | 23 | .setStateBasedImmutableWhenCommitting(true) |
23 | .setHashProvider(MapTestEnvironment.prepareHashProvider(true)) | 24 | .setHashProvider(MapTestEnvironment.prepareHashProvider(true)) |
24 | .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy.SHARED_NODE_CACHE), | 25 | .setStateBasedNodeSharingStrategy(VersionedMapStoreBuilder.StateStorageStrategy |
26 | .SHARED_NODE_CACHE), | ||
25 | VersionedMapStoreBuilder.<Integer,String>builder() | 27 | VersionedMapStoreBuilder.<Integer,String>builder() |
26 | .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE) | 28 | .setStrategy(VersionedMapStoreBuilder.StoreStrategy.STATE) |
27 | .setStateBasedImmutableWhenCommitting(false) | 29 | .setStateBasedImmutableWhenCommitting(false) |
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 69ae811e..0e695aaa 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 | |||
@@ -57,13 +57,15 @@ public class MapTestEnvironment<K, V> { | |||
57 | VersionedMap<K, V> map2, List<Throwable> errors) { | 57 | VersionedMap<K, V> map2, List<Throwable> errors) { |
58 | map1.checkIntegrity(); | 58 | map1.checkIntegrity(); |
59 | map2.checkIntegrity(); | 59 | map2.checkIntegrity(); |
60 | |||
61 | assertContentEqualsList(map1, map2, title + ": map1.contentEquals(map2)", errors); | ||
62 | assertContentEqualsList(map2, map1, title + ": map2.contentEquals(map1)", errors); | ||
60 | assertEqualsList(map1.getSize(), map2.getSize(), title + ": Sizes not equal", errors); | 63 | assertEqualsList(map1.getSize(), map2.getSize(), title + ": Sizes not equal", errors); |
64 | |||
61 | for (var mode : ContentHashCode.values()) { | 65 | for (var mode : ContentHashCode.values()) { |
62 | assertEqualsList(map1.contentHashCode(mode), map2.contentHashCode(mode), | 66 | assertEqualsList(map1.contentHashCode(mode), map2.contentHashCode(mode), |
63 | title + ": " + mode + " hashCode check", errors); | 67 | title + ": " + mode + " hashCode check", errors); |
64 | } | 68 | } |
65 | assertContentEqualsList(map1, map2, title + ": map1.contentEquals(map2)", errors); | ||
66 | assertContentEqualsList(map2, map1, title + ": map2.contentEquals(map1)", errors); | ||
67 | } | 69 | } |
68 | 70 | ||
69 | private static void assertEqualsList(Object o1, Object o2, String message, List<Throwable> errors) { | 71 | private static void assertEqualsList(Object o1, Object o2, String message, List<Throwable> errors) { |
@@ -177,7 +179,8 @@ public class MapTestEnvironment<K, V> { | |||
177 | K previous = null; | 179 | K previous = null; |
178 | Cursor<K, V> cursor = versionedMap.getAll(); | 180 | Cursor<K, V> cursor = versionedMap.getAll(); |
179 | while (cursor.move()) { | 181 | while (cursor.move()) { |
180 | System.out.println(cursor.getKey() + " " + ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().getHash(cursor.getKey(), 0)); | 182 | //System.out.println(cursor.getKey() + " " + ((VersionedMapImpl<K, V>) versionedMap).getHashProvider() |
183 | // .getHash(cursor.getKey(), 0)); | ||
181 | if (previous != null) { | 184 | if (previous != null) { |
182 | int comparisonResult = ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().compare(previous, | 185 | int comparisonResult = ((VersionedMapImpl<K, V>) versionedMap).getHashProvider().compare(previous, |
183 | cursor.getKey()); | 186 | cursor.getKey()); |
@@ -185,7 +188,6 @@ public class MapTestEnvironment<K, V> { | |||
185 | } | 188 | } |
186 | previous = cursor.getKey(); | 189 | previous = cursor.getKey(); |
187 | } | 190 | } |
188 | System.out.println(); | ||
189 | } | 191 | } |
190 | 192 | ||
191 | public void printComparison() { | 193 | public void printComparison() { |