diff options
author | Kristóf Marussy <marussy@mit.bme.hu> | 2021-09-29 02:45:57 +0200 |
---|---|---|
committer | Kristóf Marussy <marussy@mit.bme.hu> | 2021-09-29 03:16:01 +0200 |
commit | a155f6ba02e08a75ce6e474a86900b8363f506e8 (patch) | |
tree | b78804c1c0f0968a9625f0656e08f5dadc16924c /store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java | |
parent | Simplify branding (diff) | |
download | refinery-a155f6ba02e08a75ce6e474a86900b8363f506e8.tar.gz refinery-a155f6ba02e08a75ce6e474a86900b8363f506e8.tar.zst refinery-a155f6ba02e08a75ce6e474a86900b8363f506e8.zip |
build: migration to Gradle 7
Diffstat (limited to 'store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java')
-rw-r--r-- | store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java | 379 |
1 files changed, 379 insertions, 0 deletions
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 new file mode 100644 index 00000000..04a9b19a --- /dev/null +++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java | |||
@@ -0,0 +1,379 @@ | |||
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 backwards. | ||
19 | */ | ||
20 | final Object[] content; | ||
21 | |||
22 | /** | ||
23 | * Hash code derived from immutable hash code | ||
24 | */ | ||
25 | final int precalculatedHash; | ||
26 | |||
27 | private ImmutableNode(int dataMap, int nodeMap, Object[] content, int precalculatedHash) { | ||
28 | super(); | ||
29 | this.dataMap = dataMap; | ||
30 | this.nodeMap = nodeMap; | ||
31 | this.content = content; | ||
32 | this.precalculatedHash = precalculatedHash; | ||
33 | } | ||
34 | |||
35 | /** | ||
36 | * Constructor that copies a mutable node to an immutable. | ||
37 | * | ||
38 | * @param node A mutable node. | ||
39 | * @param cache A cache of existing immutable nodes. It can be used to search | ||
40 | * and place reference immutable nodes. It can be null, if no cache | ||
41 | * available. | ||
42 | * @return an immutable version of the input node. | ||
43 | */ | ||
44 | @SuppressWarnings("unchecked") | ||
45 | static <K,V> ImmutableNode<K,V> constructImmutable(MutableNode<K,V> node, Map<Node<K, V>, ImmutableNode<K, V>> cache) { | ||
46 | // 1. try to return from cache | ||
47 | if(cache != null) { | ||
48 | ImmutableNode<K, V> cachedResult = cache.get(node); | ||
49 | if(cachedResult != null) { | ||
50 | // 1.1 Already cached, return from cache. | ||
51 | return cachedResult; | ||
52 | } | ||
53 | } | ||
54 | |||
55 | // 2. otherwise construct a new ImmutableNode | ||
56 | int size = 0; | ||
57 | for(int i = 0; i<node.content.length; i++) { | ||
58 | if(node.content[i]!=null) { | ||
59 | size++; | ||
60 | } | ||
61 | } | ||
62 | |||
63 | int datas = 0; | ||
64 | int nodes = 0; | ||
65 | int resultDataMap = 0; | ||
66 | int resultNodeMap = 0; | ||
67 | final Object[] resultContent = new Object[size]; | ||
68 | int bitposition = 1; | ||
69 | for(int i = 0; i<FACTOR; i++) { | ||
70 | Object key = node.content[i*2]; | ||
71 | if(key != null) { | ||
72 | resultDataMap |= bitposition; | ||
73 | resultContent[datas*2] = key; | ||
74 | resultContent[datas*2+1] = node.content[i*2+1]; | ||
75 | datas++; | ||
76 | } else { | ||
77 | Node<K,V> subnode = (Node<K, V>) node.content[i*2+1]; | ||
78 | if(subnode != null) { | ||
79 | ImmutableNode<K, V> immutableSubnode = subnode.toImmutable(cache); | ||
80 | resultNodeMap |=bitposition; | ||
81 | resultContent[size-1-nodes] = immutableSubnode; | ||
82 | nodes++; | ||
83 | } | ||
84 | } | ||
85 | bitposition<<=1; | ||
86 | } | ||
87 | final int resultHash = node.hashCode(); | ||
88 | ImmutableNode<K,V> newImmutable = new ImmutableNode<>(resultDataMap, resultNodeMap, resultContent, resultHash); | ||
89 | |||
90 | // 3. save new immutable. | ||
91 | if(cache != null) { | ||
92 | cache.put(newImmutable, newImmutable); | ||
93 | } | ||
94 | return newImmutable; | ||
95 | } | ||
96 | |||
97 | private int index(int bitmap, int bitpos) { | ||
98 | return Integer.bitCount(bitmap & (bitpos-1)); | ||
99 | } | ||
100 | |||
101 | @SuppressWarnings("unchecked") | ||
102 | @Override | ||
103 | public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { | ||
104 | int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); | ||
105 | int bitposition = 1 << selectedHashFragment; | ||
106 | // If the key is stored as a data | ||
107 | if((dataMap & bitposition) != 0) { | ||
108 | int keyIndex = 2*index(dataMap, bitposition); | ||
109 | K keyCandidate = (K) content[keyIndex]; | ||
110 | if(keyCandidate.equals(key)) { | ||
111 | return (V) content[keyIndex+1]; | ||
112 | } else { | ||
113 | return defaultValue; | ||
114 | } | ||
115 | } | ||
116 | // the key is stored as a node | ||
117 | else if((nodeMap & bitposition) != 0) { | ||
118 | int keyIndex = content.length-1-index(nodeMap, bitposition); | ||
119 | ImmutableNode<K,V> subNode = (ImmutableNode<K,V>) content[keyIndex]; | ||
120 | int newDepth = depth+1; | ||
121 | int newHash = newHash(hashProvider, key, hash, newDepth); | ||
122 | return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); | ||
123 | } | ||
124 | // the key is not stored at all | ||
125 | else { | ||
126 | return defaultValue; | ||
127 | } | ||
128 | } | ||
129 | |||
130 | @SuppressWarnings("unchecked") | ||
131 | @Override | ||
132 | public Node<K,V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { | ||
133 | int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); | ||
134 | int bitposition = 1 << selectedHashFragment; | ||
135 | if((dataMap & bitposition) != 0) { | ||
136 | int keyIndex = 2*index(dataMap, bitposition); | ||
137 | K keyCandidate = (K) content[keyIndex]; | ||
138 | if(keyCandidate.equals(key)) { | ||
139 | if(value == defaultValue) { | ||
140 | // delete | ||
141 | MutableNode<K, V> mutable = this.toMutable(); | ||
142 | return mutable.removeEntry(selectedHashFragment,oldValue); | ||
143 | } else if(value == content[keyIndex+1]) { | ||
144 | // dont change | ||
145 | oldValue.setOldValue(value); | ||
146 | return this; | ||
147 | } else { | ||
148 | // update existing value | ||
149 | MutableNode<K, V> mutable = this.toMutable(); | ||
150 | return mutable.updateValue(value, oldValue, selectedHashFragment); | ||
151 | } | ||
152 | } else { | ||
153 | if(value == defaultValue) { | ||
154 | // dont change | ||
155 | oldValue.setOldValue(defaultValue); | ||
156 | return this; | ||
157 | } else { | ||
158 | // add new key + value | ||
159 | MutableNode<K, V> mutable = this.toMutable(); | ||
160 | return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); | ||
161 | } | ||
162 | } | ||
163 | } else if((nodeMap & bitposition)!=0) { | ||
164 | |||
165 | int keyIndex = content.length-1-index(nodeMap, bitposition); | ||
166 | ImmutableNode<K,V> subNode = (ImmutableNode<K,V>) content[keyIndex]; | ||
167 | int newDepth = depth+1; | ||
168 | int newHash = newHash(hashProvider, key, hash, newDepth); | ||
169 | Node<K,V> newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth); | ||
170 | |||
171 | if(subNode == newsubNode) { | ||
172 | // nothing changed | ||
173 | return this; | ||
174 | } else { | ||
175 | MutableNode<K, V> mutable = toMutable(); | ||
176 | return mutable.updateWithSubNode(selectedHashFragment, newsubNode, value.equals(defaultValue)); | ||
177 | } | ||
178 | } else { | ||
179 | // add new key + value | ||
180 | MutableNode<K, V> mutable = this.toMutable(); | ||
181 | return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); | ||
182 | } | ||
183 | } | ||
184 | |||
185 | |||
186 | @SuppressWarnings("unchecked") | ||
187 | @Override | ||
188 | public long getSize() { | ||
189 | int result = Integer.bitCount(this.dataMap); | ||
190 | for(int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) { | ||
191 | ImmutableNode<K,V> subnode = | ||
192 | (ImmutableNode<K, V>) this.content[this.content.length-1-subnodeIndex]; | ||
193 | result += subnode.getSize(); | ||
194 | } | ||
195 | return result; | ||
196 | } | ||
197 | |||
198 | @Override | ||
199 | protected MutableNode<K,V> toMutable() { | ||
200 | return new MutableNode<>(this); | ||
201 | } | ||
202 | |||
203 | @Override | ||
204 | public ImmutableNode<K, V> toImmutable( | ||
205 | Map<Node<K, V>, ImmutableNode<K, V>> cache) { | ||
206 | return this; | ||
207 | } | ||
208 | |||
209 | @Override | ||
210 | protected MutableNode<K, V> isMutable() { | ||
211 | return null; | ||
212 | } | ||
213 | |||
214 | @SuppressWarnings("unchecked") | ||
215 | @Override | ||
216 | boolean moveToNext(MapCursor<K, V> cursor) { | ||
217 | // 1. try to move to data | ||
218 | int datas = Integer.bitCount(this.dataMap); | ||
219 | if(cursor.dataIndex != MapCursor.INDEX_FINISH) { | ||
220 | int newDataIndex = cursor.dataIndex + 1; | ||
221 | if(newDataIndex < datas) { | ||
222 | cursor.dataIndex = newDataIndex; | ||
223 | cursor.key = (K) this.content[newDataIndex*2]; | ||
224 | cursor.value = (V) this.content[newDataIndex*2+1]; | ||
225 | return true; | ||
226 | } else { | ||
227 | cursor.dataIndex = MapCursor.INDEX_FINISH; | ||
228 | } | ||
229 | } | ||
230 | |||
231 | // 2. look inside the subnodes | ||
232 | int nodes = Integer.bitCount(this.nodeMap); | ||
233 | int newNodeIndex = cursor.nodeIndexStack.peek() + 1; | ||
234 | if(newNodeIndex < nodes) { | ||
235 | // 2.1 found next subnode, move down to the subnode | ||
236 | Node<K, V> subnode = (Node<K, V>) this.content[this.content.length-1-newNodeIndex]; | ||
237 | cursor.dataIndex = MapCursor.INDEX_START; | ||
238 | cursor.nodeIndexStack.pop(); | ||
239 | cursor.nodeIndexStack.push(newNodeIndex); | ||
240 | cursor.nodeIndexStack.push(MapCursor.INDEX_START); | ||
241 | cursor.nodeStack.push(subnode); | ||
242 | return subnode.moveToNext(cursor); | ||
243 | } else { | ||
244 | // 3. no subnode found, move up | ||
245 | cursor.nodeStack.pop(); | ||
246 | cursor.nodeIndexStack.pop(); | ||
247 | if(!cursor.nodeStack.isEmpty()) { | ||
248 | Node<K, V> supernode = cursor.nodeStack.peek(); | ||
249 | return supernode.moveToNext(cursor); | ||
250 | } else { | ||
251 | cursor.key = null; | ||
252 | cursor.value = null; | ||
253 | return false; | ||
254 | } | ||
255 | } | ||
256 | } | ||
257 | |||
258 | @Override | ||
259 | public void prettyPrint(StringBuilder builder, int depth, int code) { | ||
260 | for(int i = 0; i<depth; i++) { | ||
261 | builder.append("\t"); | ||
262 | } | ||
263 | if(code>=0) { | ||
264 | builder.append(code); | ||
265 | builder.append(":"); | ||
266 | } | ||
267 | builder.append("Immutable("); | ||
268 | boolean hadContent = false; | ||
269 | int dataMask = 1; | ||
270 | for(int i = 0; i<FACTOR; i++) { | ||
271 | if((dataMask & dataMap) != 0) { | ||
272 | if(hadContent) { | ||
273 | builder.append(","); | ||
274 | } | ||
275 | builder.append(i); | ||
276 | builder.append(":["); | ||
277 | builder.append(content[2*index(dataMap, dataMask)].toString()); | ||
278 | builder.append("]->["); | ||
279 | builder.append(content[2*index(dataMap, dataMask)+1].toString()); | ||
280 | builder.append("]"); | ||
281 | hadContent = true; | ||
282 | } | ||
283 | dataMask<<=1; | ||
284 | } | ||
285 | builder.append(")"); | ||
286 | int nodeMask = 1; | ||
287 | for(int i = 0; i<FACTOR; i++) { | ||
288 | if((nodeMask & nodeMap)!=0) { | ||
289 | @SuppressWarnings("unchecked") | ||
290 | Node<K,V> subNode = (Node<K, V>) content[content.length-1-index(nodeMap, nodeMask)]; | ||
291 | builder.append("\n"); | ||
292 | subNode.prettyPrint(builder, depth+1, i); | ||
293 | } | ||
294 | nodeMask<<=1; | ||
295 | } | ||
296 | } | ||
297 | |||
298 | @SuppressWarnings("unchecked") | ||
299 | @Override | ||
300 | public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) { | ||
301 | if(depth>0) { | ||
302 | boolean orphaned = Integer.bitCount(dataMap) == 1 && nodeMap == 0; | ||
303 | if(orphaned) { | ||
304 | throw new IllegalStateException("Orphaned node! " + dataMap + ": " + content[0]); | ||
305 | } | ||
306 | } | ||
307 | // check the place of data | ||
308 | |||
309 | // check subnodes | ||
310 | for(int i = 0; i<Integer.bitCount(nodeMap); i++) { | ||
311 | Node<K,V> subnode = (Node<K, V>) this.content[this.content.length-1-i]; | ||
312 | if(! (subnode instanceof ImmutableNode<?,?>)) { | ||
313 | throw new IllegalStateException("Immutable node contains mutable subnodes!"); | ||
314 | } else { | ||
315 | subnode.checkIntegrity(hashProvider, defaultValue, depth+1); | ||
316 | } | ||
317 | } | ||
318 | } | ||
319 | |||
320 | @Override | ||
321 | public int hashCode() { | ||
322 | return this.precalculatedHash; | ||
323 | } | ||
324 | |||
325 | @Override | ||
326 | public boolean equals(Object obj) { | ||
327 | if (this == obj) | ||
328 | return true; | ||
329 | if (obj == null) | ||
330 | return false; | ||
331 | if (obj instanceof ImmutableNode<?,?>) { | ||
332 | ImmutableNode<?,?> other = (ImmutableNode<?,?>) obj; | ||
333 | if (precalculatedHash != other.precalculatedHash || dataMap != other.dataMap || nodeMap != other.nodeMap || !Arrays.deepEquals(content, other.content)) | ||
334 | return false; | ||
335 | else return true; | ||
336 | } else if(obj instanceof MutableNode<?,?>) { | ||
337 | return ImmutableNode.compareImmutableMutable(this, (MutableNode<?, ?>) obj); | ||
338 | } else { | ||
339 | return false; | ||
340 | } | ||
341 | } | ||
342 | public static boolean compareImmutableMutable( | ||
343 | ImmutableNode<?, ?> immutable, | ||
344 | MutableNode<?, ?> mutable) | ||
345 | { | ||
346 | int datas = 0; | ||
347 | int nodes = 0; | ||
348 | final int immutableLength = immutable.content.length; | ||
349 | for(int i = 0; i<FACTOR; i++) { | ||
350 | Object key = mutable.content[i*2]; | ||
351 | // For each key candidate | ||
352 | if(key != null) { | ||
353 | // Check whether a new Key-Value pair can fit into the immutable container | ||
354 | if(datas*2+nodes+2 <= immutableLength) { | ||
355 | if( !immutable.content[datas*2].equals(key) || | ||
356 | !immutable.content[datas*2+1].equals(mutable.content[i*2+1])) | ||
357 | { | ||
358 | return false; | ||
359 | } | ||
360 | } else return false; | ||
361 | datas++; | ||
362 | } else { | ||
363 | Node<?,?> mutableSubnode = (Node<?, ?>) mutable.content[i*2+1]; | ||
364 | if(mutableSubnode != null) { | ||
365 | if(datas*2+nodes+1 <= immutableLength) { | ||
366 | Object immutableSubnode = immutable.content[immutableLength-1-nodes]; | ||
367 | if(!mutableSubnode.equals(immutableSubnode)) { | ||
368 | return false; | ||
369 | } | ||
370 | nodes++; | ||
371 | } else { | ||
372 | return false; | ||
373 | } | ||
374 | } | ||
375 | } | ||
376 | } | ||
377 | return true; | ||
378 | } | ||
379 | } | ||