aboutsummaryrefslogtreecommitdiffstats
path: root/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
diff options
context:
space:
mode:
authorLibravatar Kristóf Marussy <kristof@marussy.com>2021-10-05 00:36:47 +0200
committerLibravatar Kristóf Marussy <kristof@marussy.com>2021-10-05 00:36:47 +0200
commitc3e27396c62f191b4343df151e5a86bfa63a32f3 (patch)
tree4f698c9ba0320a5c740c53877c3f75c00240dca4 /store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
parentfix(web): improve accessibility (diff)
downloadrefinery-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/MutableNode.java')
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java456
1 files changed, 0 insertions, 456 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
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 @@
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 @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}
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2024-09-05 09:19:15 +0000