diff options
author | 2021-10-05 00:36:47 +0200 | |
---|---|---|
committer | 2021-10-05 00:36:47 +0200 | |
commit | c3e27396c62f191b4343df151e5a86bfa63a32f3 (patch) | |
tree | 4f698c9ba0320a5c740c53877c3f75c00240dca4 /store/src/main/java/org/eclipse/viatra/solver/data/map/internal | |
parent | fix(web): improve accessibility (diff) | |
download | refinery-c3e27396c62f191b4343df151e5a86bfa63a32f3.tar.gz refinery-c3e27396c62f191b4343df151e5a86bfa63a32f3.tar.zst refinery-c3e27396c62f191b4343df151e5a86bfa63a32f3.zip |
chore: change package name
Diffstat (limited to 'store/src/main/java/org/eclipse/viatra/solver/data/map/internal')
8 files changed, 0 insertions, 1479 deletions
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/HashClash.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/HashClash.java deleted file mode 100644 index c70fb8b8..00000000 --- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/HashClash.java +++ /dev/null | |||
@@ -1,18 +0,0 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | enum HashClash { | ||
4 | /** | ||
5 | * Not stuck. | ||
6 | */ | ||
7 | NONE, | ||
8 | |||
9 | /** | ||
10 | * Clashed, next we should return the key of cursor 1. | ||
11 | */ | ||
12 | STUCK_CURSOR_1, | ||
13 | |||
14 | /** | ||
15 | * Clashed, next we should return the key of cursor 2. | ||
16 | */ | ||
17 | STUCK_CURSOR_2 | ||
18 | } | ||
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java deleted file mode 100644 index b507763f..00000000 --- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java +++ /dev/null | |||
@@ -1,378 +0,0 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.Arrays; | ||
4 | import java.util.Map; | ||
5 | |||
6 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | ||
7 | |||
8 | public class ImmutableNode<K, V> extends Node<K, V> { | ||
9 | /** | ||
10 | * Bitmap defining the stored key and values. | ||
11 | */ | ||
12 | final int dataMap; | ||
13 | /** | ||
14 | * Bitmap defining the positions of further nodes. | ||
15 | */ | ||
16 | final int nodeMap; | ||
17 | /** | ||
18 | * Stores Keys, Values, and subnodes. Structure: (K,V)*,NODE; NODES are stored | ||
19 | * backwards. | ||
20 | */ | ||
21 | final Object[] content; | ||
22 | |||
23 | /** | ||
24 | * Hash code derived from immutable hash code | ||
25 | */ | ||
26 | final int precalculatedHash; | ||
27 | |||
28 | private ImmutableNode(int dataMap, int nodeMap, Object[] content, int precalculatedHash) { | ||
29 | super(); | ||
30 | this.dataMap = dataMap; | ||
31 | this.nodeMap = nodeMap; | ||
32 | this.content = content; | ||
33 | this.precalculatedHash = precalculatedHash; | ||
34 | } | ||
35 | |||
36 | /** | ||
37 | * Constructor that copies a mutable node to an immutable. | ||
38 | * | ||
39 | * @param node A mutable node. | ||
40 | * @param cache A cache of existing immutable nodes. It can be used to search | ||
41 | * and place reference immutable nodes. It can be null, if no cache | ||
42 | * available. | ||
43 | * @return an immutable version of the input node. | ||
44 | */ | ||
45 | static <K, V> ImmutableNode<K, V> constructImmutable(MutableNode<K, V> node, | ||
46 | Map<Node<K, V>, ImmutableNode<K, V>> cache) { | ||
47 | // 1. try to return from cache | ||
48 | if (cache != null) { | ||
49 | ImmutableNode<K, V> cachedResult = cache.get(node); | ||
50 | if (cachedResult != null) { | ||
51 | // 1.1 Already cached, return from cache. | ||
52 | return cachedResult; | ||
53 | } | ||
54 | } | ||
55 | |||
56 | // 2. otherwise construct a new ImmutableNode | ||
57 | int size = 0; | ||
58 | for (int i = 0; i < node.content.length; i++) { | ||
59 | if (node.content[i] != null) { | ||
60 | size++; | ||
61 | } | ||
62 | } | ||
63 | |||
64 | int datas = 0; | ||
65 | int nodes = 0; | ||
66 | int resultDataMap = 0; | ||
67 | int resultNodeMap = 0; | ||
68 | final Object[] resultContent = new Object[size]; | ||
69 | int bitposition = 1; | ||
70 | for (int i = 0; i < FACTOR; i++) { | ||
71 | Object key = node.content[i * 2]; | ||
72 | if (key != null) { | ||
73 | resultDataMap |= bitposition; | ||
74 | resultContent[datas * 2] = key; | ||
75 | resultContent[datas * 2 + 1] = node.content[i * 2 + 1]; | ||
76 | datas++; | ||
77 | } else { | ||
78 | @SuppressWarnings("unchecked") | ||
79 | var subnode = (Node<K, V>) node.content[i * 2 + 1]; | ||
80 | if (subnode != null) { | ||
81 | ImmutableNode<K, V> immutableSubnode = subnode.toImmutable(cache); | ||
82 | resultNodeMap |= bitposition; | ||
83 | resultContent[size - 1 - nodes] = immutableSubnode; | ||
84 | nodes++; | ||
85 | } | ||
86 | } | ||
87 | bitposition <<= 1; | ||
88 | } | ||
89 | final int resultHash = node.hashCode(); | ||
90 | var newImmutable = new ImmutableNode<K, V>(resultDataMap, resultNodeMap, resultContent, resultHash); | ||
91 | |||
92 | // 3. save new immutable. | ||
93 | if (cache != null) { | ||
94 | cache.put(newImmutable, newImmutable); | ||
95 | } | ||
96 | return newImmutable; | ||
97 | } | ||
98 | |||
99 | private int index(int bitmap, int bitpos) { | ||
100 | return Integer.bitCount(bitmap & (bitpos - 1)); | ||
101 | } | ||
102 | |||
103 | @Override | ||
104 | public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { | ||
105 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); | ||
106 | int bitposition = 1 << selectedHashFragment; | ||
107 | // If the key is stored as a data | ||
108 | if ((dataMap & bitposition) != 0) { | ||
109 | int keyIndex = 2 * index(dataMap, bitposition); | ||
110 | @SuppressWarnings("unchecked") | ||
111 | K keyCandidate = (K) content[keyIndex]; | ||
112 | if (keyCandidate.equals(key)) { | ||
113 | @SuppressWarnings("unchecked") | ||
114 | V value = (V) content[keyIndex + 1]; | ||
115 | return value; | ||
116 | } else { | ||
117 | return defaultValue; | ||
118 | } | ||
119 | } | ||
120 | // the key is stored as a node | ||
121 | else if ((nodeMap & bitposition) != 0) { | ||
122 | int keyIndex = content.length - 1 - index(nodeMap, bitposition); | ||
123 | @SuppressWarnings("unchecked") | ||
124 | var subNode = (ImmutableNode<K, V>) content[keyIndex]; | ||
125 | int newDepth = depth + 1; | ||
126 | int newHash = newHash(hashProvider, key, hash, newDepth); | ||
127 | return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); | ||
128 | } | ||
129 | // the key is not stored at all | ||
130 | else { | ||
131 | return defaultValue; | ||
132 | } | ||
133 | } | ||
134 | |||
135 | @Override | ||
136 | public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, | ||
137 | V defaultValue, int hash, int depth) { | ||
138 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); | ||
139 | int bitposition = 1 << selectedHashFragment; | ||
140 | if ((dataMap & bitposition) != 0) { | ||
141 | int keyIndex = 2 * index(dataMap, bitposition); | ||
142 | @SuppressWarnings("unchecked") | ||
143 | K keyCandidate = (K) content[keyIndex]; | ||
144 | if (keyCandidate.equals(key)) { | ||
145 | if (value == defaultValue) { | ||
146 | // delete | ||
147 | MutableNode<K, V> mutable = this.toMutable(); | ||
148 | return mutable.removeEntry(selectedHashFragment, oldValue); | ||
149 | } else if (value == content[keyIndex + 1]) { | ||
150 | // dont change | ||
151 | oldValue.setOldValue(value); | ||
152 | return this; | ||
153 | } else { | ||
154 | // update existing value | ||
155 | MutableNode<K, V> mutable = this.toMutable(); | ||
156 | return mutable.updateValue(value, oldValue, selectedHashFragment); | ||
157 | } | ||
158 | } else { | ||
159 | if (value == defaultValue) { | ||
160 | // dont change | ||
161 | oldValue.setOldValue(defaultValue); | ||
162 | return this; | ||
163 | } else { | ||
164 | // add new key + value | ||
165 | MutableNode<K, V> mutable = this.toMutable(); | ||
166 | return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); | ||
167 | } | ||
168 | } | ||
169 | } else if ((nodeMap & bitposition) != 0) { | ||
170 | int keyIndex = content.length - 1 - index(nodeMap, bitposition); | ||
171 | @SuppressWarnings("unchecked") | ||
172 | var subNode = (ImmutableNode<K, V>) content[keyIndex]; | ||
173 | int newDepth = depth + 1; | ||
174 | int newHash = newHash(hashProvider, key, hash, newDepth); | ||
175 | var newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth); | ||
176 | |||
177 | if (subNode == newsubNode) { | ||
178 | // nothing changed | ||
179 | return this; | ||
180 | } else { | ||
181 | MutableNode<K, V> mutable = toMutable(); | ||
182 | return mutable.updateWithSubNode(selectedHashFragment, newsubNode, value.equals(defaultValue)); | ||
183 | } | ||
184 | } else { | ||
185 | // add new key + value | ||
186 | MutableNode<K, V> mutable = this.toMutable(); | ||
187 | return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); | ||
188 | } | ||
189 | } | ||
190 | |||
191 | @Override | ||
192 | public long getSize() { | ||
193 | int result = Integer.bitCount(this.dataMap); | ||
194 | for (int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) { | ||
195 | @SuppressWarnings("unchecked") | ||
196 | var subnode = (ImmutableNode<K, V>) this.content[this.content.length - 1 - subnodeIndex]; | ||
197 | result += subnode.getSize(); | ||
198 | } | ||
199 | return result; | ||
200 | } | ||
201 | |||
202 | @Override | ||
203 | protected MutableNode<K, V> toMutable() { | ||
204 | return new MutableNode<>(this); | ||
205 | } | ||
206 | |||
207 | @Override | ||
208 | public ImmutableNode<K, V> toImmutable(Map<Node<K, V>, ImmutableNode<K, V>> cache) { | ||
209 | return this; | ||
210 | } | ||
211 | |||
212 | @Override | ||
213 | protected MutableNode<K, V> isMutable() { | ||
214 | return null; | ||
215 | } | ||
216 | |||
217 | @SuppressWarnings("unchecked") | ||
218 | @Override | ||
219 | boolean moveToNext(MapCursor<K, V> cursor) { | ||
220 | // 1. try to move to data | ||
221 | int datas = Integer.bitCount(this.dataMap); | ||
222 | if (cursor.dataIndex != MapCursor.INDEX_FINISH) { | ||
223 | int newDataIndex = cursor.dataIndex + 1; | ||
224 | if (newDataIndex < datas) { | ||
225 | cursor.dataIndex = newDataIndex; | ||
226 | cursor.key = (K) this.content[newDataIndex * 2]; | ||
227 | cursor.value = (V) this.content[newDataIndex * 2 + 1]; | ||
228 | return true; | ||
229 | } else { | ||
230 | cursor.dataIndex = MapCursor.INDEX_FINISH; | ||
231 | } | ||
232 | } | ||
233 | |||
234 | // 2. look inside the subnodes | ||
235 | int nodes = Integer.bitCount(this.nodeMap); | ||
236 | int newNodeIndex = cursor.nodeIndexStack.peek() + 1; | ||
237 | if (newNodeIndex < nodes) { | ||
238 | // 2.1 found next subnode, move down to the subnode | ||
239 | Node<K, V> subnode = (Node<K, V>) this.content[this.content.length - 1 - newNodeIndex]; | ||
240 | cursor.dataIndex = MapCursor.INDEX_START; | ||
241 | cursor.nodeIndexStack.pop(); | ||
242 | cursor.nodeIndexStack.push(newNodeIndex); | ||
243 | cursor.nodeIndexStack.push(MapCursor.INDEX_START); | ||
244 | cursor.nodeStack.push(subnode); | ||
245 | return subnode.moveToNext(cursor); | ||
246 | } else { | ||
247 | // 3. no subnode found, move up | ||
248 | cursor.nodeStack.pop(); | ||
249 | cursor.nodeIndexStack.pop(); | ||
250 | if (!cursor.nodeStack.isEmpty()) { | ||
251 | Node<K, V> supernode = cursor.nodeStack.peek(); | ||
252 | return supernode.moveToNext(cursor); | ||
253 | } else { | ||
254 | cursor.key = null; | ||
255 | cursor.value = null; | ||
256 | return false; | ||
257 | } | ||
258 | } | ||
259 | } | ||
260 | |||
261 | @Override | ||
262 | public void prettyPrint(StringBuilder builder, int depth, int code) { | ||
263 | for (int i = 0; i < depth; i++) { | ||
264 | builder.append("\t"); | ||
265 | } | ||
266 | if (code >= 0) { | ||
267 | builder.append(code); | ||
268 | builder.append(":"); | ||
269 | } | ||
270 | builder.append("Immutable("); | ||
271 | boolean hadContent = false; | ||
272 | int dataMask = 1; | ||
273 | for (int i = 0; i < FACTOR; i++) { | ||
274 | if ((dataMask & dataMap) != 0) { | ||
275 | if (hadContent) { | ||
276 | builder.append(","); | ||
277 | } | ||
278 | builder.append(i); | ||
279 | builder.append(":["); | ||
280 | builder.append(content[2 * index(dataMap, dataMask)].toString()); | ||
281 | builder.append("]->["); | ||
282 | builder.append(content[2 * index(dataMap, dataMask) + 1].toString()); | ||
283 | builder.append("]"); | ||
284 | hadContent = true; | ||
285 | } | ||
286 | dataMask <<= 1; | ||
287 | } | ||
288 | builder.append(")"); | ||
289 | int nodeMask = 1; | ||
290 | for (int i = 0; i < FACTOR; i++) { | ||
291 | if ((nodeMask & nodeMap) != 0) { | ||
292 | @SuppressWarnings("unchecked") | ||
293 | Node<K, V> subNode = (Node<K, V>) content[content.length - 1 - index(nodeMap, nodeMask)]; | ||
294 | builder.append("\n"); | ||
295 | subNode.prettyPrint(builder, depth + 1, i); | ||
296 | } | ||
297 | nodeMask <<= 1; | ||
298 | } | ||
299 | } | ||
300 | |||
301 | @Override | ||
302 | public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) { | ||
303 | if (depth > 0) { | ||
304 | boolean orphaned = Integer.bitCount(dataMap) == 1 && nodeMap == 0; | ||
305 | if (orphaned) { | ||
306 | throw new IllegalStateException("Orphaned node! " + dataMap + ": " + content[0]); | ||
307 | } | ||
308 | } | ||
309 | // check the place of data | ||
310 | |||
311 | // check subnodes | ||
312 | for (int i = 0; i < Integer.bitCount(nodeMap); i++) { | ||
313 | @SuppressWarnings("unchecked") | ||
314 | var subnode = (Node<K, V>) this.content[this.content.length - 1 - i]; | ||
315 | if (!(subnode instanceof ImmutableNode<?, ?>)) { | ||
316 | throw new IllegalStateException("Immutable node contains mutable subnodes!"); | ||
317 | } else { | ||
318 | subnode.checkIntegrity(hashProvider, defaultValue, depth + 1); | ||
319 | } | ||
320 | } | ||
321 | } | ||
322 | |||
323 | @Override | ||
324 | public int hashCode() { | ||
325 | return this.precalculatedHash; | ||
326 | } | ||
327 | |||
328 | @Override | ||
329 | public boolean equals(Object obj) { | ||
330 | if (this == obj) | ||
331 | return true; | ||
332 | if (obj == null) | ||
333 | return false; | ||
334 | if (obj instanceof ImmutableNode<?, ?> other) { | ||
335 | return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap | ||
336 | && Arrays.deepEquals(content, other.content); | ||
337 | } else if (obj instanceof MutableNode<?, ?> mutableObj) { | ||
338 | return ImmutableNode.compareImmutableMutable(this, mutableObj); | ||
339 | } else { | ||
340 | return false; | ||
341 | } | ||
342 | } | ||
343 | |||
344 | public static boolean compareImmutableMutable(ImmutableNode<?, ?> immutable, MutableNode<?, ?> mutable) { | ||
345 | int datas = 0; | ||
346 | int nodes = 0; | ||
347 | final int immutableLength = immutable.content.length; | ||
348 | for (int i = 0; i < FACTOR; i++) { | ||
349 | Object key = mutable.content[i * 2]; | ||
350 | // For each key candidate | ||
351 | if (key != null) { | ||
352 | // Check whether a new Key-Value pair can fit into the immutable container | ||
353 | if (datas * 2 + nodes + 2 <= immutableLength) { | ||
354 | if (!immutable.content[datas * 2].equals(key) | ||
355 | || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) { | ||
356 | return false; | ||
357 | } | ||
358 | } else | ||
359 | return false; | ||
360 | datas++; | ||
361 | } else { | ||
362 | var mutableSubnode = (Node<?, ?>) mutable.content[i * 2 + 1]; | ||
363 | if (mutableSubnode != null) { | ||
364 | if (datas * 2 + nodes + 1 <= immutableLength) { | ||
365 | Object immutableSubnode = immutable.content[immutableLength - 1 - nodes]; | ||
366 | if (!mutableSubnode.equals(immutableSubnode)) { | ||
367 | return false; | ||
368 | } | ||
369 | nodes++; | ||
370 | } else { | ||
371 | return false; | ||
372 | } | ||
373 | } | ||
374 | } | ||
375 | } | ||
376 | return true; | ||
377 | } | ||
378 | } | ||
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java deleted file mode 100644 index cc5a3982..00000000 --- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java +++ /dev/null | |||
@@ -1,131 +0,0 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.ArrayDeque; | ||
4 | import java.util.ConcurrentModificationException; | ||
5 | import java.util.Iterator; | ||
6 | import java.util.List; | ||
7 | |||
8 | import org.eclipse.viatra.solver.data.map.Cursor; | ||
9 | import org.eclipse.viatra.solver.data.map.VersionedMap; | ||
10 | |||
11 | public class MapCursor<K,V> implements Cursor<K,V> { | ||
12 | // Constants | ||
13 | static final int INDEX_START = -1; | ||
14 | static final int INDEX_FINISH = -2; | ||
15 | |||
16 | // Tree stack | ||
17 | ArrayDeque<Node<K,V>> nodeStack; | ||
18 | ArrayDeque<Integer> nodeIndexStack; | ||
19 | int dataIndex; | ||
20 | |||
21 | // Values | ||
22 | K key; | ||
23 | V value; | ||
24 | |||
25 | // Hash code for checking concurrent modifications | ||
26 | final VersionedMap<K,V> map; | ||
27 | final int creationHash; | ||
28 | |||
29 | public MapCursor(Node<K, V> root, VersionedMap<K,V> map) { | ||
30 | // Initializing tree stack | ||
31 | super(); | ||
32 | this.nodeStack = new ArrayDeque<>(); | ||
33 | this.nodeIndexStack = new ArrayDeque<>(); | ||
34 | if(root != null) { | ||
35 | this.nodeStack.add(root); | ||
36 | this.nodeIndexStack.push(INDEX_START); | ||
37 | } | ||
38 | |||
39 | this.dataIndex = INDEX_START; | ||
40 | |||
41 | // Initializing cache | ||
42 | this.key = null; | ||
43 | this.value = null; | ||
44 | |||
45 | // Initializing state | ||
46 | this.map=map; | ||
47 | this.creationHash = map.hashCode(); | ||
48 | } | ||
49 | |||
50 | public K getKey() { | ||
51 | return key; | ||
52 | } | ||
53 | |||
54 | public V getValue() { | ||
55 | return value; | ||
56 | } | ||
57 | |||
58 | public boolean isTerminated() { | ||
59 | return this.nodeStack.isEmpty(); | ||
60 | } | ||
61 | |||
62 | public boolean move() { | ||
63 | if(isDirty()) { | ||
64 | throw new ConcurrentModificationException(); | ||
65 | } | ||
66 | if(!isTerminated()) { | ||
67 | boolean result = this.nodeStack.peek().moveToNext(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 | public boolean skipCurrentNode() { | ||
76 | nodeStack.pop(); | ||
77 | nodeIndexStack.pop(); | ||
78 | dataIndex = INDEX_FINISH; | ||
79 | return move(); | ||
80 | } | ||
81 | @Override | ||
82 | public boolean isDirty() { | ||
83 | return this.map.hashCode() != this.creationHash; | ||
84 | } | ||
85 | @Override | ||
86 | public List<VersionedMap<?, ?>> getDependingMaps() { | ||
87 | return List.of(this.map); | ||
88 | } | ||
89 | |||
90 | public static <K,V> boolean sameSubnode(MapCursor<K,V> cursor1, MapCursor<K,V> cursor2) { | ||
91 | Node<K, V> nodeOfCursor1 = cursor1.nodeStack.peek(); | ||
92 | Node<K, V> nodeOfCursor2 = cursor2.nodeStack.peek(); | ||
93 | if(nodeOfCursor1 != null && nodeOfCursor2 != null) { | ||
94 | return nodeOfCursor1.equals(nodeOfCursor2); | ||
95 | } else { | ||
96 | return false; | ||
97 | } | ||
98 | } | ||
99 | |||
100 | /** | ||
101 | * | ||
102 | * @param <K> | ||
103 | * @param <V> | ||
104 | * @param cursor1 | ||
105 | * @param cursor2 | ||
106 | * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the same position. | ||
107 | */ | ||
108 | public static <K,V> int compare(MapCursor<K,V> cursor1, MapCursor<K,V> cursor2) { | ||
109 | // two cursors are equally deep | ||
110 | Iterator<Integer> stack1 = cursor1.nodeIndexStack.descendingIterator(); | ||
111 | Iterator<Integer> stack2 = cursor2.nodeIndexStack.descendingIterator(); | ||
112 | if(stack1.hasNext()) { | ||
113 | if(!stack2.hasNext()) { | ||
114 | // stack 2 has no more element, thus stack 1 is deeper | ||
115 | return 1; | ||
116 | } | ||
117 | int val1 = stack1.next(); | ||
118 | int val2 = stack2.next(); | ||
119 | if(val1 < val2) { | ||
120 | return -1; | ||
121 | } else if(val2 < val1) { | ||
122 | return 1; | ||
123 | } | ||
124 | } | ||
125 | if(stack2.hasNext()) { | ||
126 | // stack 2 has more element, thus stack 2 is deeper | ||
127 | return 1; | ||
128 | } | ||
129 | return Integer.compare(cursor1.dataIndex, cursor2.dataIndex); | ||
130 | } | ||
131 | } | ||
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java deleted file mode 100644 index 35d20539..00000000 --- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java +++ /dev/null | |||
@@ -1,221 +0,0 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.List; | ||
4 | import java.util.stream.Stream; | ||
5 | |||
6 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | ||
7 | import org.eclipse.viatra.solver.data.map.Cursor; | ||
8 | import org.eclipse.viatra.solver.data.map.DiffCursor; | ||
9 | import org.eclipse.viatra.solver.data.map.VersionedMap; | ||
10 | |||
11 | /** | ||
12 | * A cursor representing the difference between two states of a map. | ||
13 | * | ||
14 | * @author Oszkar Semerath | ||
15 | * | ||
16 | */ | ||
17 | public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> { | ||
18 | /** | ||
19 | * Default value representing missing elements. | ||
20 | */ | ||
21 | private V defaultValue; | ||
22 | private MapCursor<K, V> cursor1; | ||
23 | private MapCursor<K, V> cursor2; | ||
24 | private ContinousHashProvider<? super K> hashProvider; | ||
25 | |||
26 | // Values | ||
27 | private K key; | ||
28 | private V fromValue; | ||
29 | private V toValue; | ||
30 | |||
31 | // State | ||
32 | /** | ||
33 | * Positive number if cursor 1 is behind, negative number if cursor 2 is behind, | ||
34 | * and 0 if they are at the same position. | ||
35 | */ | ||
36 | private int cursorRelation; | ||
37 | private HashClash hashClash = HashClash.NONE; | ||
38 | |||
39 | public MapDiffCursor(ContinousHashProvider<? super K> hashProvider, V defaultValue, Cursor<K, V> cursor1, | ||
40 | Cursor<K, V> cursor2) { | ||
41 | super(); | ||
42 | this.hashProvider = hashProvider; | ||
43 | this.defaultValue = defaultValue; | ||
44 | this.cursor1 = (MapCursor<K, V>) cursor1; | ||
45 | this.cursor2 = (MapCursor<K, V>) cursor2; | ||
46 | } | ||
47 | |||
48 | @Override | ||
49 | public K getKey() { | ||
50 | return key; | ||
51 | } | ||
52 | |||
53 | @Override | ||
54 | public V getFromValue() { | ||
55 | return fromValue; | ||
56 | } | ||
57 | |||
58 | @Override | ||
59 | public V getToValue() { | ||
60 | return toValue; | ||
61 | } | ||
62 | |||
63 | @Override | ||
64 | public V getValue() { | ||
65 | return getToValue(); | ||
66 | } | ||
67 | |||
68 | public boolean isTerminated() { | ||
69 | return cursor1.isTerminated() && cursor2.isTerminated(); | ||
70 | } | ||
71 | |||
72 | @Override | ||
73 | public boolean isDirty() { | ||
74 | return this.cursor1.isDirty() || this.cursor2.isDirty(); | ||
75 | } | ||
76 | |||
77 | @Override | ||
78 | public List<VersionedMap<?, ?>> getDependingMaps() { | ||
79 | return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()).toList(); | ||
80 | } | ||
81 | |||
82 | protected void updateState() { | ||
83 | if (!isTerminated()) { | ||
84 | this.cursorRelation = MapCursor.compare(cursor1, cursor2); | ||
85 | if (cursorRelation > 0 || cursor2.isTerminated()) { | ||
86 | this.key = cursor1.getKey(); | ||
87 | this.fromValue = cursor1.getValue(); | ||
88 | this.toValue = defaultValue; | ||
89 | } else if (cursorRelation < 0 || cursor1.isTerminated()) { | ||
90 | this.key = cursor2.getKey(); | ||
91 | this.fromValue = defaultValue; | ||
92 | this.toValue = cursor1.getValue(); | ||
93 | } else { | ||
94 | // cursor1 = cursor2 | ||
95 | if (cursor1.getKey().equals(cursor2.getKey())) { | ||
96 | this.key = cursor1.getKey(); | ||
97 | this.fromValue = cursor1.getValue(); | ||
98 | this.toValue = defaultValue; | ||
99 | } else { | ||
100 | resolveHashClashWithFirstEntry(); | ||
101 | } | ||
102 | } | ||
103 | } | ||
104 | } | ||
105 | |||
106 | protected void resolveHashClashWithFirstEntry() { | ||
107 | int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key); | ||
108 | if (compareResult < 0) { | ||
109 | this.hashClash = HashClash.STUCK_CURSOR_2; | ||
110 | this.cursorRelation = 0; | ||
111 | this.key = cursor1.key; | ||
112 | this.fromValue = cursor1.value; | ||
113 | this.toValue = defaultValue; | ||
114 | } else if (compareResult > 0) { | ||
115 | this.hashClash = HashClash.STUCK_CURSOR_1; | ||
116 | this.cursorRelation = 0; | ||
117 | this.key = cursor2.key; | ||
118 | this.fromValue = defaultValue; | ||
119 | this.toValue = cursor2.value; | ||
120 | } else { | ||
121 | throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); | ||
122 | } | ||
123 | } | ||
124 | |||
125 | protected boolean isInHashClash() { | ||
126 | return this.hashClash != HashClash.NONE; | ||
127 | } | ||
128 | |||
129 | protected void resolveHashClashWithSecondEntry() { | ||
130 | switch (this.hashClash) { | ||
131 | case STUCK_CURSOR_1: | ||
132 | this.hashClash = HashClash.NONE; | ||
133 | this.cursorRelation = 0; | ||
134 | this.key = cursor1.key; | ||
135 | this.fromValue = cursor1.value; | ||
136 | this.toValue = defaultValue; | ||
137 | break; | ||
138 | case STUCK_CURSOR_2: | ||
139 | this.hashClash = HashClash.NONE; | ||
140 | this.cursorRelation = 0; | ||
141 | this.key = cursor2.key; | ||
142 | this.fromValue = defaultValue; | ||
143 | this.toValue = cursor2.value; | ||
144 | break; | ||
145 | default: | ||
146 | throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); | ||
147 | } | ||
148 | } | ||
149 | |||
150 | protected boolean sameValues() { | ||
151 | if (this.fromValue == null) { | ||
152 | return this.toValue == null; | ||
153 | } else { | ||
154 | return this.fromValue.equals(this.toValue); | ||
155 | } | ||
156 | } | ||
157 | |||
158 | protected boolean moveOne() { | ||
159 | if (isTerminated()) { | ||
160 | return false; | ||
161 | } | ||
162 | if (this.cursorRelation > 0 || cursor2.isTerminated()) { | ||
163 | return cursor1.move(); | ||
164 | } else if (this.cursorRelation < 0 || cursor1.isTerminated()) { | ||
165 | return cursor2.move(); | ||
166 | } else { | ||
167 | boolean moved1 = cursor1.move(); | ||
168 | boolean moved2 = cursor2.move(); | ||
169 | return moved1 && moved2; | ||
170 | } | ||
171 | } | ||
172 | |||
173 | private boolean skipNode() { | ||
174 | if (isTerminated()) { | ||
175 | throw new IllegalStateException("DiffCursor tries to skip when terminated!"); | ||
176 | } | ||
177 | boolean update1 = cursor1.skipCurrentNode(); | ||
178 | boolean update2 = cursor2.skipCurrentNode(); | ||
179 | updateState(); | ||
180 | return update1 && update2; | ||
181 | } | ||
182 | |||
183 | protected boolean moveToConsistentState() { | ||
184 | if (!isTerminated()) { | ||
185 | boolean changed; | ||
186 | boolean lastResult = true; | ||
187 | do { | ||
188 | changed = false; | ||
189 | if (MapCursor.sameSubnode(cursor1, cursor2)) { | ||
190 | lastResult = skipNode(); | ||
191 | changed = true; | ||
192 | } | ||
193 | if (sameValues()) { | ||
194 | lastResult = moveOne(); | ||
195 | changed = true; | ||
196 | } | ||
197 | updateState(); | ||
198 | } while (changed && !isTerminated()); | ||
199 | return lastResult; | ||
200 | } else { | ||
201 | return false; | ||
202 | } | ||
203 | } | ||
204 | |||
205 | public boolean move() { | ||
206 | if (!isTerminated()) { | ||
207 | if (isInHashClash()) { | ||
208 | this.resolveHashClashWithSecondEntry(); | ||
209 | return true; | ||
210 | } else { | ||
211 | if (moveOne()) { | ||
212 | return moveToConsistentState(); | ||
213 | } else { | ||
214 | return false; | ||
215 | } | ||
216 | } | ||
217 | |||
218 | } else | ||
219 | return false; | ||
220 | } | ||
221 | } | ||
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java deleted file mode 100644 index b5fee673..00000000 --- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java +++ /dev/null | |||
@@ -1,456 +0,0 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.Arrays; | ||
4 | import java.util.Map; | ||
5 | |||
6 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | ||
7 | |||
8 | public class MutableNode<K, V> extends Node<K, V> { | ||
9 | int cachedHash; | ||
10 | protected Object[] content; | ||
11 | |||
12 | protected MutableNode() { | ||
13 | this.content = new Object[2 * FACTOR]; | ||
14 | updateHash(); | ||
15 | } | ||
16 | |||
17 | public static <K, V> MutableNode<K, V> initialize(K key, V value, ContinousHashProvider<? super K> hashProvider, | ||
18 | V defaultValue) { | ||
19 | if (value == defaultValue) { | ||
20 | return null; | ||
21 | } else { | ||
22 | int hash = hashProvider.getHash(key, 0); | ||
23 | int fragment = hashFragment(hash, 0); | ||
24 | MutableNode<K, V> res = new MutableNode<>(); | ||
25 | res.content[2 * fragment] = key; | ||
26 | res.content[2 * fragment + 1] = value; | ||
27 | res.updateHash(); | ||
28 | return res; | ||
29 | } | ||
30 | } | ||
31 | |||
32 | /** | ||
33 | * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode} | ||
34 | * | ||
35 | * @param node | ||
36 | */ | ||
37 | protected MutableNode(ImmutableNode<K, V> node) { | ||
38 | this.content = new Object[2 * FACTOR]; | ||
39 | int dataUsed = 0; | ||
40 | int nodeUsed = 0; | ||
41 | for (int i = 0; i < FACTOR; i++) { | ||
42 | int bitposition = 1 << i; | ||
43 | if ((node.dataMap & bitposition) != 0) { | ||
44 | content[2 * i] = node.content[dataUsed * 2]; | ||
45 | content[2 * i + 1] = node.content[dataUsed * 2 + 1]; | ||
46 | dataUsed++; | ||
47 | } else if ((node.nodeMap & bitposition) != 0) { | ||
48 | content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed]; | ||
49 | nodeUsed++; | ||
50 | } | ||
51 | } | ||
52 | this.cachedHash = node.hashCode(); | ||
53 | } | ||
54 | |||
55 | @Override | ||
56 | public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { | ||
57 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); | ||
58 | @SuppressWarnings("unchecked") | ||
59 | K keyCandidate = (K) this.content[2 * selectedHashFragment]; | ||
60 | if (keyCandidate != null) { | ||
61 | if (keyCandidate.equals(key)) { | ||
62 | @SuppressWarnings("unchecked") | ||
63 | V value = (V) this.content[2 * selectedHashFragment + 1]; | ||
64 | return value; | ||
65 | } else { | ||
66 | return defaultValue; | ||
67 | } | ||
68 | } else { | ||
69 | @SuppressWarnings("unchecked") | ||
70 | var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1]; | ||
71 | if (nodeCandidate != null) { | ||
72 | int newDepth = depth + 1; | ||
73 | int newHash = newHash(hashProvider, key, hash, newDepth); | ||
74 | return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); | ||
75 | } else { | ||
76 | return defaultValue; | ||
77 | } | ||
78 | } | ||
79 | } | ||
80 | |||
81 | @Override | ||
82 | public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, | ||
83 | V defaultValue, int hash, int depth) { | ||
84 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); | ||
85 | @SuppressWarnings("unchecked") | ||
86 | K keyCandidate = (K) content[2 * selectedHashFragment]; | ||
87 | if (keyCandidate != null) { | ||
88 | // If has key | ||
89 | if (keyCandidate.equals(key)) { | ||
90 | // The key is equals to an existing key -> update entry | ||
91 | if (value == defaultValue) { | ||
92 | return removeEntry(selectedHashFragment, oldValue); | ||
93 | } else { | ||
94 | return updateValue(value, oldValue, selectedHashFragment); | ||
95 | } | ||
96 | } else { | ||
97 | // The key is not equivalent to an existing key on the same hash bin | ||
98 | // -> split entry if it is necessary | ||
99 | if (value == defaultValue) { | ||
100 | // Value is default -> do not need to add new node | ||
101 | oldValue.setOldValue(defaultValue); | ||
102 | return this; | ||
103 | } else { | ||
104 | // Value is not default -> Split entry data to a new node | ||
105 | oldValue.setOldValue(defaultValue); | ||
106 | return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment); | ||
107 | } | ||
108 | } | ||
109 | } else { | ||
110 | // If it does not have key, check for value | ||
111 | @SuppressWarnings("unchecked") | ||
112 | var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1]; | ||
113 | if (nodeCandidate != null) { | ||
114 | // If it has value, it is a subnode -> upate that | ||
115 | var newNode = nodeCandidate.putValue(key, value, oldValue, hashProvider, defaultValue, | ||
116 | newHash(hashProvider, key, hash, depth + 1), depth + 1); | ||
117 | return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue)); | ||
118 | } else { | ||
119 | // If it does not have value, put it in the empty place | ||
120 | if (value == defaultValue) { | ||
121 | // dont need to add new key-value pair | ||
122 | oldValue.setOldValue(defaultValue); | ||
123 | return this; | ||
124 | } else { | ||
125 | return addEntry(key, value, oldValue, selectedHashFragment); | ||
126 | } | ||
127 | |||
128 | } | ||
129 | } | ||
130 | } | ||
131 | |||
132 | private Node<K, V> addEntry(K key, V value, OldValueBox<V> oldValueBox, int selectedHashFragment) { | ||
133 | content[2 * selectedHashFragment] = key; | ||
134 | @SuppressWarnings("unchecked") | ||
135 | V oldValue = (V) content[2 * selectedHashFragment + 1]; | ||
136 | oldValueBox.setOldValue(oldValue); | ||
137 | content[2 * selectedHashFragment + 1] = value; | ||
138 | updateHash(); | ||
139 | return this; | ||
140 | } | ||
141 | |||
142 | /** | ||
143 | * Updates an entry in a selected hash-fragment to a non-default value. | ||
144 | * | ||
145 | * @param value | ||
146 | * @param selectedHashFragment | ||
147 | * @return | ||
148 | */ | ||
149 | @SuppressWarnings("unchecked") | ||
150 | Node<K, V> updateValue(V value, OldValueBox<V> oldValue, int selectedHashFragment) { | ||
151 | oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); | ||
152 | content[2 * selectedHashFragment + 1] = value; | ||
153 | updateHash(); | ||
154 | return this; | ||
155 | } | ||
156 | |||
157 | /** | ||
158 | * | ||
159 | * @param selectedHashFragment | ||
160 | * @param newNode | ||
161 | * @return | ||
162 | */ | ||
163 | Node<K, V> updateWithSubNode(int selectedHashFragment, Node<K, V> newNode, boolean deletionHappened) { | ||
164 | if (deletionHappened) { | ||
165 | if (newNode == null) { | ||
166 | // Check whether this node become empty | ||
167 | content[2 * selectedHashFragment + 1] = null; // i.e. the new node | ||
168 | if (hasContent()) { | ||
169 | updateHash(); | ||
170 | return this; | ||
171 | } else { | ||
172 | return null; | ||
173 | } | ||
174 | } else { | ||
175 | // check whether newNode is orphan | ||
176 | MutableNode<K, V> immutableNewNode = newNode.isMutable(); | ||
177 | if (immutableNewNode != null) { | ||
178 | int orphaned = immutableNewNode.isOrphaned(); | ||
179 | if (orphaned >= 0) { | ||
180 | // orphan subnode data is replaced with data | ||
181 | content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2]; | ||
182 | content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1]; | ||
183 | updateHash(); | ||
184 | return this; | ||
185 | } | ||
186 | } | ||
187 | } | ||
188 | } | ||
189 | // normal behaviour | ||
190 | content[2 * selectedHashFragment + 1] = newNode; | ||
191 | updateHash(); | ||
192 | return this; | ||
193 | |||
194 | } | ||
195 | |||
196 | private boolean hasContent() { | ||
197 | for (Object element : this.content) { | ||
198 | if (element != null) | ||
199 | return true; | ||
200 | } | ||
201 | return false; | ||
202 | } | ||
203 | |||
204 | @Override | ||
205 | protected MutableNode<K, V> isMutable() { | ||
206 | return this; | ||
207 | } | ||
208 | |||
209 | protected int isOrphaned() { | ||
210 | int dataFound = -2; | ||
211 | for (int i = 0; i < FACTOR; i++) { | ||
212 | if (content[i * 2] != null) { | ||
213 | if (dataFound >= 0) { | ||
214 | return -1; | ||
215 | } else { | ||
216 | dataFound = i; | ||
217 | } | ||
218 | } else if (content[i * 2 + 1] != null) { | ||
219 | return -3; | ||
220 | } | ||
221 | } | ||
222 | return dataFound; | ||
223 | } | ||
224 | |||
225 | @SuppressWarnings("unchecked") | ||
226 | private Node<K, V> moveDownAndSplit(ContinousHashProvider<? super K> hashProvider, K newKey, V newValue, | ||
227 | K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) { | ||
228 | V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1]; | ||
229 | |||
230 | MutableNode<K, V> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, | ||
231 | hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, depth + 1); | ||
232 | |||
233 | content[2 * selectedHashFragmentOfCurrentDepth] = null; | ||
234 | content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode; | ||
235 | updateHash(); | ||
236 | return this; | ||
237 | } | ||
238 | |||
239 | // Pass everything as parameters for performance. | ||
240 | @SuppressWarnings("squid:S107") | ||
241 | private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1, | ||
242 | int oldHash1, K key2, V value2, int oldHash2, int newdepth) { | ||
243 | int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth); | ||
244 | int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth); | ||
245 | int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth)); | ||
246 | int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth)); | ||
247 | |||
248 | MutableNode<K, V> subNode = new MutableNode<>(); | ||
249 | if (newFragment1 != newFragment2) { | ||
250 | subNode.content[newFragment1 * 2] = key1; | ||
251 | subNode.content[newFragment1 * 2 + 1] = value1; | ||
252 | |||
253 | subNode.content[newFragment2 * 2] = key2; | ||
254 | subNode.content[newFragment2 * 2 + 1] = value2; | ||
255 | } else { | ||
256 | MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, | ||
257 | newHash2, newdepth + 1); | ||
258 | subNode.content[newFragment1 * 2 + 1] = subSubNode; | ||
259 | } | ||
260 | subNode.updateHash(); | ||
261 | return subNode; | ||
262 | } | ||
263 | |||
264 | @SuppressWarnings("unchecked") | ||
265 | Node<K, V> removeEntry(int selectedHashFragment, OldValueBox<V> oldValue) { | ||
266 | content[2 * selectedHashFragment] = null; | ||
267 | oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); | ||
268 | content[2 * selectedHashFragment + 1] = null; | ||
269 | if (hasContent()) { | ||
270 | updateHash(); | ||
271 | return this; | ||
272 | } else { | ||
273 | return null; | ||
274 | } | ||
275 | } | ||
276 | |||
277 | @SuppressWarnings("unchecked") | ||
278 | @Override | ||
279 | public long getSize() { | ||
280 | int size = 0; | ||
281 | for (int i = 0; i < FACTOR; i++) { | ||
282 | if (content[i * 2] != null) { | ||
283 | size++; | ||
284 | } else { | ||
285 | Node<K, V> nodeCandidate = (Node<K, V>) content[i * 2 + 1]; | ||
286 | if (nodeCandidate != null) { | ||
287 | size += nodeCandidate.getSize(); | ||
288 | } | ||
289 | } | ||
290 | } | ||
291 | return size; | ||
292 | } | ||
293 | |||
294 | @Override | ||
295 | protected MutableNode<K, V> toMutable() { | ||
296 | return this; | ||
297 | } | ||
298 | |||
299 | @Override | ||
300 | public ImmutableNode<K, V> toImmutable(Map<Node<K, V>, ImmutableNode<K, V>> cache) { | ||
301 | return ImmutableNode.constructImmutable(this, cache); | ||
302 | } | ||
303 | |||
304 | @SuppressWarnings("unchecked") | ||
305 | @Override | ||
306 | boolean moveToNext(MapCursor<K, V> cursor) { | ||
307 | // 1. try to move to data | ||
308 | if (cursor.dataIndex != MapCursor.INDEX_FINISH) { | ||
309 | for (int index = cursor.dataIndex + 1; index < FACTOR; index++) { | ||
310 | if (this.content[index * 2] != null) { | ||
311 | // 1.1 found next data | ||
312 | cursor.dataIndex = index; | ||
313 | cursor.key = (K) this.content[index * 2]; | ||
314 | cursor.value = (V) this.content[index * 2 + 1]; | ||
315 | return true; | ||
316 | } | ||
317 | } | ||
318 | cursor.dataIndex = MapCursor.INDEX_FINISH; | ||
319 | } | ||
320 | |||
321 | // 2. look inside the subnodes | ||
322 | for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) { | ||
323 | if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) { | ||
324 | // 2.1 found next subnode, move down to the subnode | ||
325 | Node<K, V> subnode = (Node<K, V>) this.content[index * 2 + 1]; | ||
326 | |||
327 | cursor.dataIndex = MapCursor.INDEX_START; | ||
328 | cursor.nodeIndexStack.pop(); | ||
329 | cursor.nodeIndexStack.push(index); | ||
330 | cursor.nodeIndexStack.push(MapCursor.INDEX_START); | ||
331 | cursor.nodeStack.push(subnode); | ||
332 | |||
333 | return subnode.moveToNext(cursor); | ||
334 | } | ||
335 | } | ||
336 | // 3. no subnode found, move up | ||
337 | cursor.nodeStack.pop(); | ||
338 | cursor.nodeIndexStack.pop(); | ||
339 | if (!cursor.nodeStack.isEmpty()) { | ||
340 | Node<K, V> supernode = cursor.nodeStack.peek(); | ||
341 | return supernode.moveToNext(cursor); | ||
342 | } else { | ||
343 | cursor.key = null; | ||
344 | cursor.value = null; | ||
345 | return false; | ||
346 | } | ||
347 | } | ||
348 | |||
349 | @Override | ||
350 | public void prettyPrint(StringBuilder builder, int depth, int code) { | ||
351 | for (int i = 0; i < depth; i++) { | ||
352 | builder.append("\t"); | ||
353 | } | ||
354 | if (code >= 0) { | ||
355 | builder.append(code); | ||
356 | builder.append(":"); | ||
357 | } | ||
358 | builder.append("Mutable("); | ||
359 | // print content | ||
360 | boolean hadContent = false; | ||
361 | for (int i = 0; i < FACTOR; i++) { | ||
362 | if (content[2 * i] != null) { | ||
363 | if (hadContent) { | ||
364 | builder.append(","); | ||
365 | } | ||
366 | builder.append(i); | ||
367 | builder.append(":["); | ||
368 | builder.append(content[2 * i].toString()); | ||
369 | builder.append("]->["); | ||
370 | builder.append(content[2 * i + 1].toString()); | ||
371 | builder.append("]"); | ||
372 | hadContent = true; | ||
373 | } | ||
374 | } | ||
375 | builder.append(")"); | ||
376 | // print subnodes | ||
377 | for (int i = 0; i < FACTOR; i++) { | ||
378 | if (content[2 * i] == null && content[2 * i + 1] != null) { | ||
379 | @SuppressWarnings("unchecked") | ||
380 | Node<K, V> subNode = (Node<K, V>) content[2 * i + 1]; | ||
381 | builder.append("\n"); | ||
382 | subNode.prettyPrint(builder, depth + 1, i); | ||
383 | } | ||
384 | } | ||
385 | } | ||
386 | |||
387 | @Override | ||
388 | public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) { | ||
389 | // check for orphan nodes | ||
390 | if (depth > 0) { | ||
391 | int orphaned = isOrphaned(); | ||
392 | if (orphaned >= 0) { | ||
393 | throw new IllegalStateException("Orphaned node! " + orphaned + ": " + content[2 * orphaned]); | ||
394 | } | ||
395 | } | ||
396 | // check the place of data | ||
397 | for (int i = 0; i < FACTOR; i++) { | ||
398 | if (this.content[2 * i] != null) { | ||
399 | @SuppressWarnings("unchecked") | ||
400 | K key = (K) this.content[2 * i]; | ||
401 | @SuppressWarnings("unchecked") | ||
402 | V value = (V) this.content[2 * i + 1]; | ||
403 | |||
404 | if (value == defaultValue) { | ||
405 | throw new IllegalStateException("Node contains default value!"); | ||
406 | } | ||
407 | int hashCode = hashProvider.getHash(key, hashDepth(depth)); | ||
408 | int shiftDepth = shiftDepth(depth); | ||
409 | int selectedHashFragment = hashFragment(hashCode, shiftDepth); | ||
410 | if (i != selectedHashFragment) { | ||
411 | throw new IllegalStateException("Key " + key + " with hash code " + hashCode | ||
412 | + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i); | ||
413 | } | ||
414 | } | ||
415 | } | ||
416 | // check subnodes | ||
417 | for (int i = 0; i < FACTOR; i++) { | ||
418 | if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { | ||
419 | @SuppressWarnings("unchecked") | ||
420 | var subNode = (Node<K, V>) this.content[2 * i + 1]; | ||
421 | subNode.checkIntegrity(hashProvider, defaultValue, depth + 1); | ||
422 | } | ||
423 | } | ||
424 | // check the hash | ||
425 | int oldHash = this.cachedHash; | ||
426 | updateHash(); | ||
427 | int newHash = this.cachedHash; | ||
428 | if (oldHash != newHash) { | ||
429 | throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")"); | ||
430 | } | ||
431 | } | ||
432 | |||
433 | protected void updateHash() { | ||
434 | this.cachedHash = Arrays.hashCode(content); | ||
435 | } | ||
436 | |||
437 | @Override | ||
438 | public int hashCode() { | ||
439 | return this.cachedHash; | ||
440 | } | ||
441 | |||
442 | @Override | ||
443 | public boolean equals(Object obj) { | ||
444 | if (this == obj) | ||
445 | return true; | ||
446 | if (obj == null) | ||
447 | return false; | ||
448 | if (obj instanceof MutableNode<?, ?> mutableObj) { | ||
449 | return Arrays.deepEquals(this.content, mutableObj.content); | ||
450 | } else if (obj instanceof ImmutableNode<?, ?> immutableObj) { | ||
451 | return ImmutableNode.compareImmutableMutable(immutableObj, this); | ||
452 | } else { | ||
453 | return false; | ||
454 | } | ||
455 | } | ||
456 | } | ||
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java deleted file mode 100644 index d40f980a..00000000 --- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java +++ /dev/null | |||
@@ -1,85 +0,0 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.Map; | ||
4 | |||
5 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | ||
6 | |||
7 | public abstract class Node<K,V>{ | ||
8 | public static final int BRANCHING_FACTOR_BITS = 5; | ||
9 | public static final int FACTOR = 1<<BRANCHING_FACTOR_BITS; | ||
10 | protected static final int NUMBER_OF_FACTORS = Integer.SIZE / BRANCHING_FACTOR_BITS; | ||
11 | protected static final int FACTOR_MASK = FACTOR-1; | ||
12 | public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS; | ||
13 | |||
14 | /** | ||
15 | * Calculates the index for the continuous hash. | ||
16 | * @param depth The depth of the node in the tree. | ||
17 | * @return The index of the continuous hash. | ||
18 | */ | ||
19 | protected static int hashDepth(int depth) { | ||
20 | return depth/NUMBER_OF_FACTORS; | ||
21 | } | ||
22 | |||
23 | /** | ||
24 | * Calculates the which segment of a single hash should be used. | ||
25 | * @param depth The depth of the node in the tree. | ||
26 | * @return The segment of a hash code. | ||
27 | */ | ||
28 | protected static int shiftDepth(int depth) { | ||
29 | return depth%NUMBER_OF_FACTORS; | ||
30 | } | ||
31 | /** | ||
32 | * Selects a segments from a complete hash for a given depth. | ||
33 | * @param hash A complete hash. | ||
34 | * @param shiftDepth The index of the segment. | ||
35 | * @return The segment as an integer. | ||
36 | */ | ||
37 | protected static int hashFragment(int hash, int shiftDepth) { | ||
38 | if(shiftDepth<0 || Node.NUMBER_OF_FACTORS<shiftDepth) throw new IllegalArgumentException("Invalid shift depth! valid intervall=[0;5], input="+shiftDepth); | ||
39 | return (hash >>> shiftDepth*BRANCHING_FACTOR_BITS) & FACTOR_MASK; | ||
40 | } | ||
41 | |||
42 | /** | ||
43 | * Returns the hash code for a given depth. It may calculate new hash code, or reuse a hash code calculated for depth-1. | ||
44 | * @param key The key. | ||
45 | * @param hash Hash code for depth-1 | ||
46 | * @param depth The depth. | ||
47 | * @return The new hash code. | ||
48 | */ | ||
49 | protected int newHash(final ContinousHashProvider<? super K> hashProvider, K key, int hash, int depth) { | ||
50 | final int hashDepth = hashDepth(depth); | ||
51 | if(hashDepth>=ContinousHashProvider.MAX_PRACTICAL_DEPTH) { | ||
52 | throw new IllegalArgumentException("Key "+key+" have the clashing hashcode over the practical depth limitation ("+ContinousHashProvider.MAX_PRACTICAL_DEPTH+")!"); | ||
53 | } | ||
54 | return depth%NUMBER_OF_FACTORS == 0? | ||
55 | hashProvider.getHash(key, hashDepth) : | ||
56 | hash; | ||
57 | } | ||
58 | |||
59 | |||
60 | public abstract V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth); | ||
61 | public abstract Node<K,V> putValue(K key, V value, OldValueBox<V> old, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth); | ||
62 | public abstract long getSize(); | ||
63 | |||
64 | abstract MutableNode<K, V> toMutable(); | ||
65 | public abstract ImmutableNode<K, V> toImmutable( | ||
66 | Map<Node<K, V>,ImmutableNode<K, V>> cache); | ||
67 | protected abstract MutableNode<K, V> isMutable(); | ||
68 | /** | ||
69 | * Moves a {@link MapCursor} to its next position. | ||
70 | * @param cursor the cursor | ||
71 | * @return Whether there was a next value to move on. | ||
72 | */ | ||
73 | abstract boolean moveToNext(MapCursor<K,V> cursor); | ||
74 | |||
75 | ///////// FOR printing | ||
76 | public abstract void prettyPrint(StringBuilder builder, int depth, int code); | ||
77 | @Override | ||
78 | public String toString() { | ||
79 | StringBuilder stringBuilder = new StringBuilder(); | ||
80 | prettyPrint(stringBuilder, 0, -1); | ||
81 | return stringBuilder.toString(); | ||
82 | } | ||
83 | public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {} | ||
84 | |||
85 | } | ||
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java deleted file mode 100644 index 23502857..00000000 --- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java +++ /dev/null | |||
@@ -1,19 +0,0 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | public class OldValueBox<V>{ | ||
4 | V oldValue; | ||
5 | boolean isSet = false; | ||
6 | |||
7 | public V getOldValue() { | ||
8 | if(!isSet) throw new IllegalStateException(); | ||
9 | isSet = false; | ||
10 | return oldValue; | ||
11 | } | ||
12 | |||
13 | public void setOldValue(V ouldValue) { | ||
14 | if(isSet) throw new IllegalStateException(); | ||
15 | this.oldValue = ouldValue; | ||
16 | isSet = true; | ||
17 | } | ||
18 | |||
19 | } | ||
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java deleted file mode 100644 index de41e602..00000000 --- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java +++ /dev/null | |||
@@ -1,171 +0,0 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | ||
2 | |||
3 | import java.util.Iterator; | ||
4 | import java.util.LinkedList; | ||
5 | import java.util.List; | ||
6 | |||
7 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | ||
8 | import org.eclipse.viatra.solver.data.map.Cursor; | ||
9 | import org.eclipse.viatra.solver.data.map.DiffCursor; | ||
10 | import org.eclipse.viatra.solver.data.map.VersionedMap; | ||
11 | import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl; | ||
12 | |||
13 | /** | ||
14 | * Not threadSafe in itself | ||
15 | * @author Oszkar Semerath | ||
16 | * | ||
17 | * @param <K> | ||
18 | * @param <V> | ||
19 | */ | ||
20 | public class VersionedMapImpl<K,V> implements VersionedMap<K,V>{ | ||
21 | protected final VersionedMapStoreImpl<K,V> store; | ||
22 | |||
23 | protected final ContinousHashProvider<K> hashProvider; | ||
24 | protected final V defaultValue; | ||
25 | protected Node<K,V> root; | ||
26 | |||
27 | private OldValueBox<V> oldValueBox = new OldValueBox<>(); | ||
28 | |||
29 | public VersionedMapImpl( | ||
30 | VersionedMapStoreImpl<K,V> store, | ||
31 | ContinousHashProvider<K> hashProvider, | ||
32 | V defaultValue) | ||
33 | { | ||
34 | this.store = store; | ||
35 | this.hashProvider = hashProvider; | ||
36 | this.defaultValue = defaultValue; | ||
37 | this.root = null; | ||
38 | } | ||
39 | public VersionedMapImpl( | ||
40 | VersionedMapStoreImpl<K,V> store, | ||
41 | ContinousHashProvider<K> hashProvider, | ||
42 | V defaultValue, Node<K,V> data) | ||
43 | { | ||
44 | this.store = store; | ||
45 | this.hashProvider = hashProvider; | ||
46 | this.defaultValue = defaultValue; | ||
47 | this.root = data; | ||
48 | } | ||
49 | |||
50 | public V getDefaultValue() { | ||
51 | return defaultValue; | ||
52 | } | ||
53 | public ContinousHashProvider<K> getHashProvider() { | ||
54 | return hashProvider; | ||
55 | } | ||
56 | @Override | ||
57 | public V put(K key, V value) { | ||
58 | if(root!=null) { | ||
59 | root = root.putValue(key, value, oldValueBox, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); | ||
60 | return oldValueBox.getOldValue(); | ||
61 | } else { | ||
62 | root = MutableNode.initialize(key, value, hashProvider, defaultValue); | ||
63 | return defaultValue; | ||
64 | } | ||
65 | } | ||
66 | |||
67 | @Override | ||
68 | public void putAll(Cursor<K, V> cursor) { | ||
69 | if(cursor.getDependingMaps().contains(this)) { | ||
70 | List<K> keys = new LinkedList<>(); | ||
71 | List<V> values = new LinkedList<>(); | ||
72 | while(cursor.move()) { | ||
73 | keys.add(cursor.getKey()); | ||
74 | values.add(cursor.getValue()); | ||
75 | } | ||
76 | Iterator<K> keyIterator = keys.iterator(); | ||
77 | Iterator<V> valueIterator = values.iterator(); | ||
78 | while(keyIterator.hasNext()) { | ||
79 | this.put(keyIterator.next(), valueIterator.next()); | ||
80 | } | ||
81 | } else { | ||
82 | while(cursor.move()) { | ||
83 | this.put(cursor.getKey(), cursor.getValue()); | ||
84 | } | ||
85 | } | ||
86 | } | ||
87 | |||
88 | @Override | ||
89 | public V get(K key) { | ||
90 | if(root!=null) { | ||
91 | return root.getValue(key, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); | ||
92 | } else { | ||
93 | return defaultValue; | ||
94 | } | ||
95 | } | ||
96 | @Override | ||
97 | public long getSize() { | ||
98 | if(root == null) { | ||
99 | return 0; | ||
100 | } else { | ||
101 | return root.getSize(); | ||
102 | } | ||
103 | } | ||
104 | |||
105 | @Override | ||
106 | public Cursor<K, V> getAll() { | ||
107 | return new MapCursor<>(this.root,this); | ||
108 | } | ||
109 | @Override | ||
110 | public DiffCursor<K, V> getDiffCursor(long toVersion) { | ||
111 | Cursor<K, V> fromCursor = this.getAll(); | ||
112 | VersionedMap<K, V> toMap = this.store.createMap(toVersion); | ||
113 | Cursor<K, V> toCursor = toMap.getAll(); | ||
114 | return new MapDiffCursor<>(this.hashProvider,this.defaultValue, fromCursor, toCursor); | ||
115 | |||
116 | } | ||
117 | |||
118 | |||
119 | @Override | ||
120 | public long commit() { | ||
121 | return this.store.commit(root,this); | ||
122 | } | ||
123 | public void setRoot(Node<K, V> root) { | ||
124 | this.root = root; | ||
125 | } | ||
126 | |||
127 | @Override | ||
128 | public void restore(long state) { | ||
129 | root = this.store.revert(state); | ||
130 | } | ||
131 | |||
132 | @Override | ||
133 | public int hashCode() { | ||
134 | final int prime = 31; | ||
135 | int result = 1; | ||
136 | result = prime * result + ((root == null) ? 0 : root.hashCode()); | ||
137 | return result; | ||
138 | } | ||
139 | |||
140 | @Override | ||
141 | public boolean equals(Object obj) { | ||
142 | if (this == obj) | ||
143 | return true; | ||
144 | if (obj == null) | ||
145 | return false; | ||
146 | if (getClass() != obj.getClass()) | ||
147 | return false; | ||
148 | VersionedMapImpl<?,?> other = (VersionedMapImpl<?,?>) obj; | ||
149 | if (root == null) { | ||
150 | if (other.root != null) | ||
151 | return false; | ||
152 | } else if (!root.equals(other.root)) | ||
153 | return false; | ||
154 | return true; | ||
155 | } | ||
156 | public void prettyPrint() { | ||
157 | StringBuilder s = new StringBuilder(); | ||
158 | if(this.root != null) { | ||
159 | this.root.prettyPrint(s, 0, -1); | ||
160 | System.out.println(s.toString()); | ||
161 | } else { | ||
162 | System.out.println("empty tree"); | ||
163 | } | ||
164 | } | ||
165 | public void checkIntegrity() { | ||
166 | if(this.root != null) { | ||
167 | this.root.checkIntegrity(hashProvider, defaultValue, 0); | ||
168 | } | ||
169 | } | ||
170 | |||
171 | } | ||