aboutsummaryrefslogtreecommitdiffstats
path: root/store/src/main/java/tools/refinery/data/map/internal/ImmutableNode.java
diff options
context:
space:
mode:
Diffstat (limited to 'store/src/main/java/tools/refinery/data/map/internal/ImmutableNode.java')
-rw-r--r--store/src/main/java/tools/refinery/data/map/internal/ImmutableNode.java378
1 files changed, 378 insertions, 0 deletions
diff --git a/store/src/main/java/tools/refinery/data/map/internal/ImmutableNode.java b/store/src/main/java/tools/refinery/data/map/internal/ImmutableNode.java
new file mode 100644
index 00000000..99e27bb6
--- /dev/null
+++ b/store/src/main/java/tools/refinery/data/map/internal/ImmutableNode.java
@@ -0,0 +1,378 @@
1package tools.refinery.data.map.internal;
2
3import java.util.Arrays;
4import java.util.Map;
5
6import tools.refinery.data.map.ContinousHashProvider;
7
8public 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}
generated by cgit v1.2.3-54-g00ecf (git 2.45.2) at 2024-07-20 03:07:30 +0000