aboutsummaryrefslogtreecommitdiffstats
path: root/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
diff options
context:
space:
mode:
Diffstat (limited to 'store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java')
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java449
1 files changed, 449 insertions, 0 deletions
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
new file mode 100644
index 00000000..9e63b941
--- /dev/null
+++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
@@ -0,0 +1,449 @@
1package org.eclipse.viatra.solver.data.map.internal;
2
3import java.util.Arrays;
4import java.util.Map;
5
6import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
7
8public 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 @SuppressWarnings("unchecked")
56 @Override
57 public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
58 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
59 K keyCandidate = (K) this.content[2 * selectedHashFragment];
60 if (keyCandidate != null) {
61 if (keyCandidate.equals(key)) {
62 return (V) this.content[2 * selectedHashFragment + 1];
63 } else {
64 return defaultValue;
65 }
66 } else {
67 Node<K, V> nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
68 if (nodeCandidate != null) {
69 int newDepth = depth + 1;
70 int newHash = newHash(hashProvider, key, hash, newDepth);
71 return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth);
72 } else {
73 return defaultValue;
74 }
75 }
76 }
77
78 @SuppressWarnings("unchecked")
79 @Override
80 public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash,
81 int depth) {
82 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
83 K keyCandidate = (K) content[2 * selectedHashFragment];
84 if (keyCandidate != null) {
85 // If has key
86 if (keyCandidate.equals(key)) {
87 // The key is equals to an existing key -> update entry
88 if (value == defaultValue) {
89 return removeEntry(selectedHashFragment, oldValue);
90 } else {
91 return updateValue(value, oldValue, selectedHashFragment);
92 }
93 } else {
94 // The key is not equivalent to an existing key on the same hash bin
95 // -> split entry if it is necessary
96 if (value == defaultValue) {
97 // Value is default -> do not need to add new node
98 oldValue.setOldValue(defaultValue);
99 return this;
100 } else {
101 // Value is not default -> Split entry data to a new node
102 oldValue.setOldValue(defaultValue);
103 return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment);
104 }
105 }
106 } else {
107 // If it does not have key, check for value
108 Node<K, V> nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
109 if (nodeCandidate != null) {
110 // If it has value, it is a subnode -> upate that
111 Node<K, V> newNode = nodeCandidate.putValue(key, value, oldValue, hashProvider, defaultValue,
112 newHash(hashProvider, key, hash, depth + 1), depth + 1);
113 return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue));
114 } else {
115 // If it does not have value, put it in the empty place
116 if (value == defaultValue) {
117 // dont need to add new key-value pair
118 oldValue.setOldValue(defaultValue);
119 return this;
120 } else {
121 return addEntry(key, value, oldValue, selectedHashFragment);
122 }
123
124 }
125 }
126 }
127
128 @SuppressWarnings("unchecked")
129 private Node<K, V> addEntry(K key, V value, OldValueBox<V> oldValue, int selectedHashFragment) {
130 content[2 * selectedHashFragment] = key;
131 oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
132 content[2 * selectedHashFragment + 1] = value;
133 updateHash();
134 return this;
135 }
136
137 /**
138 * Updates an entry in a selected hash-fragment to a non-default value.
139 *
140 * @param value
141 * @param selectedHashFragment
142 * @return
143 */
144 @SuppressWarnings("unchecked")
145 Node<K, V> updateValue(V value, OldValueBox<V> oldValue, int selectedHashFragment) {
146 oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
147 content[2 * selectedHashFragment + 1] = value;
148 updateHash();
149 return this;
150 }
151
152 /**
153 *
154 * @param selectedHashFragment
155 * @param newNode
156 * @return
157 */
158 Node<K, V> updateWithSubNode(int selectedHashFragment, Node<K, V> newNode, boolean deletionHappened) {
159 if (deletionHappened) {
160 if (newNode == null) {
161 // Check whether this node become empty
162 content[2 * selectedHashFragment + 1] = null; // i.e. the new node
163 if (hasContent()) {
164 updateHash();
165 return this;
166 } else {
167 return null;
168 }
169 } else {
170 // check whether newNode is orphan
171 MutableNode<K, V> immutableNewNode = newNode.isMutable();
172 if (immutableNewNode != null) {
173 int orphaned = immutableNewNode.isOrphaned();
174 if (orphaned >= 0) {
175 // orphan subnode data is replaced with data
176 content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2];
177 content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1];
178 updateHash();
179 return this;
180 }
181 }
182 }
183 }
184 // normal behaviour
185 content[2 * selectedHashFragment + 1] = newNode;
186 updateHash();
187 return this;
188
189 }
190
191 private boolean hasContent() {
192 for (Object element : this.content) {
193 if (element != null)
194 return true;
195 }
196 return false;
197 }
198
199 @Override
200 protected MutableNode<K, V> isMutable() {
201 return this;
202 }
203
204 protected int isOrphaned() {
205 int dataFound = -2;
206 for (int i = 0; i < FACTOR; i++) {
207 if (content[i * 2] != null) {
208 if (dataFound >= 0) {
209 return -1;
210 } else {
211 dataFound = i;
212 }
213 } else if (content[i * 2 + 1] != null) {
214 return -3;
215 }
216 }
217 return dataFound;
218 }
219
220 @SuppressWarnings("unchecked")
221 private Node<K, V> moveDownAndSplit(ContinousHashProvider<? super K> hashProvider, K newKey, V newValue,
222 K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) {
223 V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1];
224
225 MutableNode<K, V> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue,
226 hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, depth + 1);
227
228 content[2 * selectedHashFragmentOfCurrentDepth] = null;
229 content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode;
230 updateHash();
231 return this;
232 }
233
234 private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1,
235 int oldHash1, K key2, V value2, int oldHash2, int newdepth) {
236 int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth);
237 int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth);
238 int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth));
239 int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth));
240
241 MutableNode<K, V> subNode = new MutableNode<>();
242 if (newFragment1 != newFragment2) {
243 subNode.content[newFragment1 * 2] = key1;
244 subNode.content[newFragment1 * 2 + 1] = value1;
245
246 subNode.content[newFragment2 * 2] = key2;
247 subNode.content[newFragment2 * 2 + 1] = value2;
248 } else {
249 MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2,
250 newHash2, newdepth + 1);
251 subNode.content[newFragment1 * 2 + 1] = subSubNode;
252 }
253 subNode.updateHash();
254 return subNode;
255 }
256
257 @SuppressWarnings("unchecked")
258 Node<K, V> removeEntry(int selectedHashFragment, OldValueBox<V> oldValue) {
259 content[2 * selectedHashFragment] = null;
260 oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
261 content[2 * selectedHashFragment + 1] = null;
262 if (hasContent()) {
263 updateHash();
264 return this;
265 } else {
266 return null;
267 }
268 }
269
270 @SuppressWarnings("unchecked")
271 @Override
272 public long getSize() {
273 int size = 0;
274 for (int i = 0; i < FACTOR; i++) {
275 if (content[i * 2] != null) {
276 size++;
277 } else {
278 Node<K, V> nodeCandidate = (Node<K, V>) content[i * 2 + 1];
279 if (nodeCandidate != null) {
280 size += nodeCandidate.getSize();
281 }
282 }
283 }
284 return size;
285 }
286
287 @Override
288 protected MutableNode<K, V> toMutable() {
289 return this;
290 }
291
292 @Override
293 public ImmutableNode<K, V> toImmutable(Map<Node<K, V>, ImmutableNode<K, V>> cache) {
294 return ImmutableNode.constructImmutable(this, cache);
295 }
296
297 @SuppressWarnings("unchecked")
298 @Override
299 boolean moveToNext(MapCursor<K, V> cursor) {
300 // 1. try to move to data
301 if (cursor.dataIndex != MapCursor.INDEX_FINISH) {
302 for (int index = cursor.dataIndex + 1; index < FACTOR; index++) {
303 if (this.content[index * 2] != null) {
304 // 1.1 found next data
305 cursor.dataIndex = index;
306 cursor.key = (K) this.content[index * 2];
307 cursor.value = (V) this.content[index * 2 + 1];
308 return true;
309 }
310 }
311 cursor.dataIndex = MapCursor.INDEX_FINISH;
312 }
313
314 // 2. look inside the subnodes
315 for (int index = cursor.nodeIndexStack.peek() + 1; index < FACTOR; index++) {
316 if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) {
317 // 2.1 found next subnode, move down to the subnode
318 Node<K, V> subnode = (Node<K, V>) this.content[index * 2 + 1];
319
320 cursor.dataIndex = MapCursor.INDEX_START;
321 cursor.nodeIndexStack.pop();
322 cursor.nodeIndexStack.push(index);
323 cursor.nodeIndexStack.push(MapCursor.INDEX_START);
324 cursor.nodeStack.push(subnode);
325
326 return subnode.moveToNext(cursor);
327 }
328 }
329 // 3. no subnode found, move up
330 cursor.nodeStack.pop();
331 cursor.nodeIndexStack.pop();
332 if (!cursor.nodeStack.isEmpty()) {
333 Node<K, V> supernode = cursor.nodeStack.peek();
334 return supernode.moveToNext(cursor);
335 } else {
336 cursor.key = null;
337 cursor.value = null;
338 return false;
339 }
340 }
341
342 @Override
343 public void prettyPrint(StringBuilder builder, int depth, int code) {
344 for (int i = 0; i < depth; i++) {
345 builder.append("\t");
346 }
347 if (code >= 0) {
348 builder.append(code);
349 builder.append(":");
350 }
351 builder.append("Mutable(");
352 // print content
353 boolean hadContent = false;
354 for (int i = 0; i < FACTOR; i++) {
355 if (content[2 * i] != null) {
356 if (hadContent) {
357 builder.append(",");
358 }
359 builder.append(i);
360 builder.append(":[");
361 builder.append(content[2 * i].toString());
362 builder.append("]->[");
363 builder.append(content[2 * i + 1].toString());
364 builder.append("]");
365 hadContent = true;
366 }
367 }
368 builder.append(")");
369 // print subnodes
370 for (int i = 0; i < FACTOR; i++) {
371 if (content[2 * i] == null && content[2 * i + 1] != null) {
372 @SuppressWarnings("unchecked")
373 Node<K, V> subNode = (Node<K, V>) content[2 * i + 1];
374 builder.append("\n");
375 subNode.prettyPrint(builder, depth + 1, i);
376 }
377 }
378 }
379
380 @SuppressWarnings({ "unchecked" })
381 @Override
382 public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
383 // check for orphan nodes
384 if (depth > 0) {
385 int orphaned = isOrphaned();
386 if (orphaned >= 0) {
387 throw new IllegalStateException("Orphaned node! " + orphaned + ": " + content[2 * orphaned]);
388 }
389 }
390 // check the place of data
391 for (int i = 0; i < FACTOR; i++) {
392 if (this.content[2 * i] != null) {
393 K key = (K) this.content[2 * i];
394 V value = (V) this.content[2 * i + 1];
395
396 if (value == defaultValue) {
397 throw new IllegalStateException("Node contains default value!");
398 }
399 int hashCode = hashProvider.getHash(key, hashDepth(depth));
400 int shiftDepth = shiftDepth(depth);
401 int selectedHashFragment = hashFragment(hashCode, shiftDepth);
402 if (i != selectedHashFragment) {
403 throw new IllegalStateException("Key " + key + " with hash code " + hashCode
404 + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i);
405 }
406 }
407 }
408 // check subnodes
409 for (int i = 0; i < FACTOR; i++) {
410 if (this.content[2 * i + 1] != null && this.content[2 * i] == null) {
411 Node<K, V> subNode = (Node<K, V>) this.content[2 * i + 1];
412 subNode.checkIntegrity(hashProvider, defaultValue, depth + 1);
413 }
414 }
415 // check the hash
416 int oldHash = this.cachedHash;
417 updateHash();
418 int newHash = this.cachedHash;
419 if (oldHash != newHash) {
420 throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")");
421 }
422 }
423
424 protected void updateHash() {
425 this.cachedHash = Arrays.hashCode(content);
426 }
427
428 @Override
429 public int hashCode() {
430 return this.cachedHash;
431 }
432
433 @Override
434 public boolean equals(Object obj) {
435 if (this == obj)
436 return true;
437 if (obj == null)
438 return false;
439 if (obj instanceof MutableNode<?, ?>) {
440 MutableNode<?, ?> other = (MutableNode<?, ?>) obj;
441 return Arrays.deepEquals(this.content, other.content);
442 } else if (obj instanceof ImmutableNode<?, ?>) {
443 ImmutableNode<?, ?> other = (ImmutableNode<?, ?>) obj;
444 return ImmutableNode.compareImmutableMutable(other, this);
445 } else {
446 return false;
447 }
448 }
449}
generated by cgit v1.2.3-54-g00ecf (git 2.45.2) at 2024-07-21 16:58:25 +0000