diff options
Diffstat (limited to 'subprojects/store/src')
4 files changed, 193 insertions, 147 deletions
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java index 9397dede..e437aceb 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java | |||
@@ -42,8 +42,7 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
42 | * available. | 42 | * available. |
43 | * @return an immutable version of the input node. | 43 | * @return an immutable version of the input node. |
44 | */ | 44 | */ |
45 | static <K, V> ImmutableNode<K, V> constructImmutable(MutableNode<K, V> node, | 45 | static <K, V> ImmutableNode<K, V> constructImmutable(MutableNode<K, V> node, Map<Node<K, V>, ImmutableNode<K, V>> cache) { |
46 | Map<Node<K, V>, ImmutableNode<K, V>> cache) { | ||
47 | // 1. try to return from cache | 46 | // 1. try to return from cache |
48 | if (cache != null) { | 47 | if (cache != null) { |
49 | ImmutableNode<K, V> cachedResult = cache.get(node); | 48 | ImmutableNode<K, V> cachedResult = cache.get(node); |
@@ -75,8 +74,7 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
75 | resultContent[datas * 2 + 1] = node.content[i * 2 + 1]; | 74 | resultContent[datas * 2 + 1] = node.content[i * 2 + 1]; |
76 | datas++; | 75 | datas++; |
77 | } else { | 76 | } else { |
78 | @SuppressWarnings("unchecked") | 77 | @SuppressWarnings("unchecked") var subnode = (Node<K, V>) node.content[i * 2 + 1]; |
79 | var subnode = (Node<K, V>) node.content[i * 2 + 1]; | ||
80 | if (subnode != null) { | 78 | if (subnode != null) { |
81 | ImmutableNode<K, V> immutableSubnode = subnode.toImmutable(cache); | 79 | ImmutableNode<K, V> immutableSubnode = subnode.toImmutable(cache); |
82 | resultNodeMap |= bitposition; | 80 | resultNodeMap |= bitposition; |
@@ -107,11 +105,9 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
107 | // If the key is stored as a data | 105 | // If the key is stored as a data |
108 | if ((dataMap & bitposition) != 0) { | 106 | if ((dataMap & bitposition) != 0) { |
109 | int keyIndex = 2 * index(dataMap, bitposition); | 107 | int keyIndex = 2 * index(dataMap, bitposition); |
110 | @SuppressWarnings("unchecked") | 108 | @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; |
111 | K keyCandidate = (K) content[keyIndex]; | ||
112 | if (keyCandidate.equals(key)) { | 109 | if (keyCandidate.equals(key)) { |
113 | @SuppressWarnings("unchecked") | 110 | @SuppressWarnings("unchecked") V value = (V) content[keyIndex + 1]; |
114 | V value = (V) content[keyIndex + 1]; | ||
115 | return value; | 111 | return value; |
116 | } else { | 112 | } else { |
117 | return defaultValue; | 113 | return defaultValue; |
@@ -120,9 +116,8 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
120 | // the key is stored as a node | 116 | // the key is stored as a node |
121 | else if ((nodeMap & bitposition) != 0) { | 117 | else if ((nodeMap & bitposition) != 0) { |
122 | int keyIndex = content.length - 1 - index(nodeMap, bitposition); | 118 | int keyIndex = content.length - 1 - index(nodeMap, bitposition); |
123 | @SuppressWarnings("unchecked") | 119 | @SuppressWarnings("unchecked") var subNode = (ImmutableNode<K, V>) content[keyIndex]; |
124 | var subNode = (ImmutableNode<K, V>) content[keyIndex]; | 120 | int newDepth = incrementDepth(depth); |
125 | int newDepth = depth + 1; | ||
126 | int newHash = newHash(hashProvider, key, hash, newDepth); | 121 | int newHash = newHash(hashProvider, key, hash, newDepth); |
127 | return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); | 122 | return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); |
128 | } | 123 | } |
@@ -133,14 +128,12 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
133 | } | 128 | } |
134 | 129 | ||
135 | @Override | 130 | @Override |
136 | public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, | 131 | public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { |
137 | V defaultValue, int hash, int depth) { | ||
138 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); | 132 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); |
139 | int bitposition = 1 << selectedHashFragment; | 133 | int bitposition = 1 << selectedHashFragment; |
140 | if ((dataMap & bitposition) != 0) { | 134 | if ((dataMap & bitposition) != 0) { |
141 | int keyIndex = 2 * index(dataMap, bitposition); | 135 | int keyIndex = 2 * index(dataMap, bitposition); |
142 | @SuppressWarnings("unchecked") | 136 | @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; |
143 | K keyCandidate = (K) content[keyIndex]; | ||
144 | if (keyCandidate.equals(key)) { | 137 | if (keyCandidate.equals(key)) { |
145 | if (value == defaultValue) { | 138 | if (value == defaultValue) { |
146 | // delete | 139 | // delete |
@@ -151,7 +144,7 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
151 | oldValue.setOldValue(value); | 144 | oldValue.setOldValue(value); |
152 | return this; | 145 | return this; |
153 | } else { | 146 | } else { |
154 | // update existing nodeId | 147 | // update existing value |
155 | MutableNode<K, V> mutable = this.toMutable(); | 148 | MutableNode<K, V> mutable = this.toMutable(); |
156 | return mutable.updateValue(value, oldValue, selectedHashFragment); | 149 | return mutable.updateValue(value, oldValue, selectedHashFragment); |
157 | } | 150 | } |
@@ -161,16 +154,15 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
161 | oldValue.setOldValue(defaultValue); | 154 | oldValue.setOldValue(defaultValue); |
162 | return this; | 155 | return this; |
163 | } else { | 156 | } else { |
164 | // add new key + nodeId | 157 | // add new key + value |
165 | MutableNode<K, V> mutable = this.toMutable(); | 158 | MutableNode<K, V> mutable = this.toMutable(); |
166 | return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); | 159 | return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); |
167 | } | 160 | } |
168 | } | 161 | } |
169 | } else if ((nodeMap & bitposition) != 0) { | 162 | } else if ((nodeMap & bitposition) != 0) { |
170 | int keyIndex = content.length - 1 - index(nodeMap, bitposition); | 163 | int keyIndex = content.length - 1 - index(nodeMap, bitposition); |
171 | @SuppressWarnings("unchecked") | 164 | @SuppressWarnings("unchecked") var subNode = (ImmutableNode<K, V>) content[keyIndex]; |
172 | var subNode = (ImmutableNode<K, V>) content[keyIndex]; | 165 | int newDepth = incrementDepth(depth); |
173 | int newDepth = depth + 1; | ||
174 | int newHash = newHash(hashProvider, key, hash, newDepth); | 166 | int newHash = newHash(hashProvider, key, hash, newDepth); |
175 | var newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth); | 167 | var newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth); |
176 | 168 | ||
@@ -179,10 +171,11 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
179 | return this; | 171 | return this; |
180 | } else { | 172 | } else { |
181 | MutableNode<K, V> mutable = toMutable(); | 173 | MutableNode<K, V> mutable = toMutable(); |
182 | return mutable.updateWithSubNode(selectedHashFragment, newsubNode, value.equals(defaultValue)); | 174 | return mutable.updateWithSubNode(selectedHashFragment, newsubNode, |
175 | (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); | ||
183 | } | 176 | } |
184 | } else { | 177 | } else { |
185 | // add new key + nodeId | 178 | // add new key + value |
186 | MutableNode<K, V> mutable = this.toMutable(); | 179 | MutableNode<K, V> mutable = this.toMutable(); |
187 | return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); | 180 | return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); |
188 | } | 181 | } |
@@ -192,8 +185,7 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
192 | public long getSize() { | 185 | public long getSize() { |
193 | int result = Integer.bitCount(this.dataMap); | 186 | int result = Integer.bitCount(this.dataMap); |
194 | for (int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) { | 187 | for (int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) { |
195 | @SuppressWarnings("unchecked") | 188 | @SuppressWarnings("unchecked") var subnode = (ImmutableNode<K, V>) this.content[this.content.length - 1 - subnodeIndex]; |
196 | var subnode = (ImmutableNode<K, V>) this.content[this.content.length - 1 - subnodeIndex]; | ||
197 | result += subnode.getSize(); | 189 | result += subnode.getSize(); |
198 | } | 190 | } |
199 | return result; | 191 | return result; |
@@ -289,10 +281,9 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
289 | int nodeMask = 1; | 281 | int nodeMask = 1; |
290 | for (int i = 0; i < FACTOR; i++) { | 282 | for (int i = 0; i < FACTOR; i++) { |
291 | if ((nodeMask & nodeMap) != 0) { | 283 | if ((nodeMask & nodeMap) != 0) { |
292 | @SuppressWarnings("unchecked") | 284 | @SuppressWarnings("unchecked") Node<K, V> subNode = (Node<K, V>) content[content.length - 1 - index(nodeMap, nodeMask)]; |
293 | Node<K, V> subNode = (Node<K, V>) content[content.length - 1 - index(nodeMap, nodeMask)]; | ||
294 | builder.append("\n"); | 285 | builder.append("\n"); |
295 | subNode.prettyPrint(builder, depth + 1, i); | 286 | subNode.prettyPrint(builder, incrementDepth(depth), i); |
296 | } | 287 | } |
297 | nodeMask <<= 1; | 288 | nodeMask <<= 1; |
298 | } | 289 | } |
@@ -310,12 +301,11 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
310 | 301 | ||
311 | // check subnodes | 302 | // check subnodes |
312 | for (int i = 0; i < Integer.bitCount(nodeMap); i++) { | 303 | for (int i = 0; i < Integer.bitCount(nodeMap); i++) { |
313 | @SuppressWarnings("unchecked") | 304 | @SuppressWarnings("unchecked") var subnode = (Node<K, V>) this.content[this.content.length - 1 - i]; |
314 | var subnode = (Node<K, V>) this.content[this.content.length - 1 - i]; | ||
315 | if (!(subnode instanceof ImmutableNode<?, ?>)) { | 305 | if (!(subnode instanceof ImmutableNode<?, ?>)) { |
316 | throw new IllegalStateException("Immutable node contains mutable subnodes!"); | 306 | throw new IllegalStateException("Immutable node contains mutable subnodes!"); |
317 | } else { | 307 | } else { |
318 | subnode.checkIntegrity(hashProvider, defaultValue, depth + 1); | 308 | subnode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth)); |
319 | } | 309 | } |
320 | } | 310 | } |
321 | } | 311 | } |
@@ -327,13 +317,10 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
327 | 317 | ||
328 | @Override | 318 | @Override |
329 | public boolean equals(Object obj) { | 319 | public boolean equals(Object obj) { |
330 | if (this == obj) | 320 | if (this == obj) return true; |
331 | return true; | 321 | if (obj == null) return false; |
332 | if (obj == null) | ||
333 | return false; | ||
334 | if (obj instanceof ImmutableNode<?, ?> other) { | 322 | if (obj instanceof ImmutableNode<?, ?> other) { |
335 | return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap | 323 | return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap && Arrays.deepEquals(content, other.content); |
336 | && Arrays.deepEquals(content, other.content); | ||
337 | } else if (obj instanceof MutableNode<?, ?> mutableObj) { | 324 | } else if (obj instanceof MutableNode<?, ?> mutableObj) { |
338 | return ImmutableNode.compareImmutableMutable(this, mutableObj); | 325 | return ImmutableNode.compareImmutableMutable(this, mutableObj); |
339 | } else { | 326 | } else { |
@@ -351,12 +338,10 @@ public class ImmutableNode<K, V> extends Node<K, V> { | |||
351 | if (key != null) { | 338 | if (key != null) { |
352 | // Check whether a new Key-Value pair can fit into the immutable container | 339 | // Check whether a new Key-Value pair can fit into the immutable container |
353 | if (datas * 2 + nodes + 2 <= immutableLength) { | 340 | if (datas * 2 + nodes + 2 <= immutableLength) { |
354 | if (!immutable.content[datas * 2].equals(key) | 341 | if (!immutable.content[datas * 2].equals(key) || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) { |
355 | || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) { | ||
356 | return false; | 342 | return false; |
357 | } | 343 | } |
358 | } else | 344 | } else return false; |
359 | return false; | ||
360 | datas++; | 345 | datas++; |
361 | } else { | 346 | } else { |
362 | var mutableSubnode = (Node<?, ?>) mutable.content[i * 2 + 1]; | 347 | var mutableSubnode = (Node<?, ?>) mutable.content[i * 2 + 1]; |
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java index 7c3cf7e8..9d15a0d7 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java | |||
@@ -7,15 +7,15 @@ import tools.refinery.store.map.ContinousHashProvider; | |||
7 | 7 | ||
8 | public class MutableNode<K, V> extends Node<K, V> { | 8 | public class MutableNode<K, V> extends Node<K, V> { |
9 | int cachedHash; | 9 | int cachedHash; |
10 | protected boolean cachedHashValid; | ||
10 | protected Object[] content; | 11 | protected Object[] content; |
11 | 12 | ||
12 | protected MutableNode() { | 13 | protected MutableNode() { |
13 | this.content = new Object[2 * FACTOR]; | 14 | this.content = new Object[2 * FACTOR]; |
14 | updateHash(); | 15 | invalidateHash(); |
15 | } | 16 | } |
16 | 17 | ||
17 | public static <K, V> MutableNode<K, V> initialize(K key, V value, ContinousHashProvider<? super K> hashProvider, | 18 | public static <K, V> MutableNode<K, V> initialize(K key, V value, ContinousHashProvider<? super K> hashProvider, V defaultValue) { |
18 | V defaultValue) { | ||
19 | if (value == defaultValue) { | 19 | if (value == defaultValue) { |
20 | return null; | 20 | return null; |
21 | } else { | 21 | } else { |
@@ -24,7 +24,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
24 | MutableNode<K, V> res = new MutableNode<>(); | 24 | MutableNode<K, V> res = new MutableNode<>(); |
25 | res.content[2 * fragment] = key; | 25 | res.content[2 * fragment] = key; |
26 | res.content[2 * fragment + 1] = value; | 26 | res.content[2 * fragment + 1] = value; |
27 | res.updateHash(); | 27 | res.invalidateHash(); |
28 | return res; | 28 | return res; |
29 | } | 29 | } |
30 | } | 30 | } |
@@ -32,7 +32,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
32 | /** | 32 | /** |
33 | * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode} | 33 | * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode} |
34 | * | 34 | * |
35 | * @param node | 35 | * @param node to be transformed |
36 | */ | 36 | */ |
37 | protected MutableNode(ImmutableNode<K, V> node) { | 37 | protected MutableNode(ImmutableNode<K, V> node) { |
38 | this.content = new Object[2 * FACTOR]; | 38 | this.content = new Object[2 * FACTOR]; |
@@ -49,27 +49,24 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
49 | nodeUsed++; | 49 | nodeUsed++; |
50 | } | 50 | } |
51 | } | 51 | } |
52 | this.cachedHash = node.hashCode(); | 52 | this.cachedHashValid = false; |
53 | } | 53 | } |
54 | 54 | ||
55 | @Override | 55 | @Override |
56 | public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { | 56 | public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { |
57 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); | 57 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); |
58 | @SuppressWarnings("unchecked") | 58 | @SuppressWarnings("unchecked") K keyCandidate = (K) this.content[2 * selectedHashFragment]; |
59 | K keyCandidate = (K) this.content[2 * selectedHashFragment]; | ||
60 | if (keyCandidate != null) { | 59 | if (keyCandidate != null) { |
61 | if (keyCandidate.equals(key)) { | 60 | if (keyCandidate.equals(key)) { |
62 | @SuppressWarnings("unchecked") | 61 | @SuppressWarnings("unchecked") V value = (V) this.content[2 * selectedHashFragment + 1]; |
63 | V value = (V) this.content[2 * selectedHashFragment + 1]; | ||
64 | return value; | 62 | return value; |
65 | } else { | 63 | } else { |
66 | return defaultValue; | 64 | return defaultValue; |
67 | } | 65 | } |
68 | } else { | 66 | } else { |
69 | @SuppressWarnings("unchecked") | 67 | @SuppressWarnings("unchecked") var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1]; |
70 | var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1]; | ||
71 | if (nodeCandidate != null) { | 68 | if (nodeCandidate != null) { |
72 | int newDepth = depth + 1; | 69 | int newDepth = incrementDepth(depth); |
73 | int newHash = newHash(hashProvider, key, hash, newDepth); | 70 | int newHash = newHash(hashProvider, key, hash, newDepth); |
74 | return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); | 71 | return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); |
75 | } else { | 72 | } else { |
@@ -79,11 +76,9 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
79 | } | 76 | } |
80 | 77 | ||
81 | @Override | 78 | @Override |
82 | public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValueBox, ContinousHashProvider<? super K> hashProvider, | 79 | public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValueBox, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) { |
83 | V defaultValue, int hash, int depth) { | ||
84 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); | 80 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); |
85 | @SuppressWarnings("unchecked") | 81 | @SuppressWarnings("unchecked") K keyCandidate = (K) content[2 * selectedHashFragment]; |
86 | K keyCandidate = (K) content[2 * selectedHashFragment]; | ||
87 | if (keyCandidate != null) { | 82 | if (keyCandidate != null) { |
88 | // If has key | 83 | // If has key |
89 | if (keyCandidate.equals(key)) { | 84 | if (keyCandidate.equals(key)) { |
@@ -107,18 +102,17 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
107 | } | 102 | } |
108 | } | 103 | } |
109 | } else { | 104 | } else { |
110 | // If it does not have key, check for nodeId | 105 | // If it does not have key, check for value |
111 | @SuppressWarnings("unchecked") | 106 | @SuppressWarnings("unchecked") var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1]; |
112 | var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1]; | ||
113 | if (nodeCandidate != null) { | 107 | if (nodeCandidate != null) { |
114 | // If it has nodeId, it is a subnode -> upate that | 108 | // If it has value, it is a subnode -> upate that |
115 | var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, | 109 | int newDepth = incrementDepth(depth); |
116 | newHash(hashProvider, key, hash, depth + 1), depth + 1); | 110 | var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, newHash(hashProvider, key, hash, newDepth), newDepth); |
117 | return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue)); | 111 | return updateWithSubNode(selectedHashFragment, newNode, (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); |
118 | } else { | 112 | } else { |
119 | // If it does not have nodeId, put it in the empty place | 113 | // If it does not have value, put it in the empty place |
120 | if (value == defaultValue) { | 114 | if (value == defaultValue) { |
121 | // dont need to add new key-nodeId pair | 115 | // dont need to add new key-value pair |
122 | oldValueBox.setOldValue(defaultValue); | 116 | oldValueBox.setOldValue(defaultValue); |
123 | return this; | 117 | return this; |
124 | } else { | 118 | } else { |
@@ -133,30 +127,31 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
133 | content[2 * selectedHashFragment] = key; | 127 | content[2 * selectedHashFragment] = key; |
134 | oldValueBox.setOldValue(defaultValue); | 128 | oldValueBox.setOldValue(defaultValue); |
135 | content[2 * selectedHashFragment + 1] = value; | 129 | content[2 * selectedHashFragment + 1] = value; |
136 | updateHash(); | 130 | invalidateHash(); |
137 | return this; | 131 | return this; |
138 | } | 132 | } |
139 | 133 | ||
140 | /** | 134 | /** |
141 | * Updates an entry in a selected hash-fragment to a non-default nodeId. | 135 | * Updates an entry in a selected hash-fragment to a non-default value. |
142 | * | 136 | * |
143 | * @param value | 137 | * @param value new value |
144 | * @param selectedHashFragment | 138 | * @param selectedHashFragment position of the value |
145 | * @return | 139 | * @return updated node |
146 | */ | 140 | */ |
147 | @SuppressWarnings("unchecked") | 141 | @SuppressWarnings("unchecked") |
148 | Node<K, V> updateValue(V value, OldValueBox<V> oldValue, int selectedHashFragment) { | 142 | Node<K, V> updateValue(V value, OldValueBox<V> oldValue, int selectedHashFragment) { |
149 | oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); | 143 | oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); |
150 | content[2 * selectedHashFragment + 1] = value; | 144 | content[2 * selectedHashFragment + 1] = value; |
151 | updateHash(); | 145 | invalidateHash(); |
152 | return this; | 146 | return this; |
153 | } | 147 | } |
154 | 148 | ||
155 | /** | 149 | /** |
150 | * Updates an entry in a selected hash-fragment with a subtree. | ||
156 | * | 151 | * |
157 | * @param selectedHashFragment | 152 | * @param selectedHashFragment position of the value |
158 | * @param newNode | 153 | * @param newNode the subtree |
159 | * @return | 154 | * @return updated node |
160 | */ | 155 | */ |
161 | Node<K, V> updateWithSubNode(int selectedHashFragment, Node<K, V> newNode, boolean deletionHappened) { | 156 | Node<K, V> updateWithSubNode(int selectedHashFragment, Node<K, V> newNode, boolean deletionHappened) { |
162 | if (deletionHappened) { | 157 | if (deletionHappened) { |
@@ -164,7 +159,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
164 | // Check whether this node become empty | 159 | // Check whether this node become empty |
165 | content[2 * selectedHashFragment + 1] = null; // i.e. the new node | 160 | content[2 * selectedHashFragment + 1] = null; // i.e. the new node |
166 | if (hasContent()) { | 161 | if (hasContent()) { |
167 | updateHash(); | 162 | invalidateHash(); |
168 | return this; | 163 | return this; |
169 | } else { | 164 | } else { |
170 | return null; | 165 | return null; |
@@ -178,7 +173,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
178 | // orphan subnode data is replaced with data | 173 | // orphan subnode data is replaced with data |
179 | content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2]; | 174 | content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2]; |
180 | content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1]; | 175 | content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1]; |
181 | updateHash(); | 176 | invalidateHash(); |
182 | return this; | 177 | return this; |
183 | } | 178 | } |
184 | } | 179 | } |
@@ -186,15 +181,13 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
186 | } | 181 | } |
187 | // normal behaviour | 182 | // normal behaviour |
188 | content[2 * selectedHashFragment + 1] = newNode; | 183 | content[2 * selectedHashFragment + 1] = newNode; |
189 | updateHash(); | 184 | invalidateHash(); |
190 | return this; | 185 | return this; |
191 | |||
192 | } | 186 | } |
193 | 187 | ||
194 | private boolean hasContent() { | 188 | private boolean hasContent() { |
195 | for (Object element : this.content) { | 189 | for (Object element : this.content) { |
196 | if (element != null) | 190 | if (element != null) return true; |
197 | return true; | ||
198 | } | 191 | } |
199 | return false; | 192 | return false; |
200 | } | 193 | } |
@@ -221,23 +214,20 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
221 | } | 214 | } |
222 | 215 | ||
223 | @SuppressWarnings("unchecked") | 216 | @SuppressWarnings("unchecked") |
224 | private Node<K, V> moveDownAndSplit(ContinousHashProvider<? super K> hashProvider, K newKey, V newValue, | 217 | private Node<K, V> moveDownAndSplit(ContinousHashProvider<? super K> hashProvider, K newKey, V newValue, K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) { |
225 | K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) { | ||
226 | V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1]; | 218 | V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1]; |
227 | 219 | ||
228 | MutableNode<K, V> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, | 220 | MutableNode<K, V> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, incrementDepth(depth)); |
229 | hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, depth + 1); | ||
230 | 221 | ||
231 | content[2 * selectedHashFragmentOfCurrentDepth] = null; | 222 | content[2 * selectedHashFragmentOfCurrentDepth] = null; |
232 | content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode; | 223 | content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode; |
233 | updateHash(); | 224 | invalidateHash(); |
234 | return this; | 225 | return this; |
235 | } | 226 | } |
236 | 227 | ||
237 | // Pass everything as parameters for performance. | 228 | // Pass everything as parameters for performance. |
238 | @SuppressWarnings("squid:S107") | 229 | @SuppressWarnings("squid:S107") |
239 | private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1, | 230 | private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1, int oldHash1, K key2, V value2, int oldHash2, int newdepth) { |
240 | int oldHash1, K key2, V value2, int oldHash2, int newdepth) { | ||
241 | int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth); | 231 | int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth); |
242 | int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth); | 232 | int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth); |
243 | int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth)); | 233 | int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth)); |
@@ -251,11 +241,10 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
251 | subNode.content[newFragment2 * 2] = key2; | 241 | subNode.content[newFragment2 * 2] = key2; |
252 | subNode.content[newFragment2 * 2 + 1] = value2; | 242 | subNode.content[newFragment2 * 2 + 1] = value2; |
253 | } else { | 243 | } else { |
254 | MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, | 244 | MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newdepth)); |
255 | newHash2, newdepth + 1); | ||
256 | subNode.content[newFragment1 * 2 + 1] = subSubNode; | 245 | subNode.content[newFragment1 * 2 + 1] = subSubNode; |
257 | } | 246 | } |
258 | subNode.updateHash(); | 247 | subNode.invalidateHash(); |
259 | return subNode; | 248 | return subNode; |
260 | } | 249 | } |
261 | 250 | ||
@@ -265,7 +254,7 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
265 | oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); | 254 | oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); |
266 | content[2 * selectedHashFragment + 1] = null; | 255 | content[2 * selectedHashFragment + 1] = null; |
267 | if (hasContent()) { | 256 | if (hasContent()) { |
268 | updateHash(); | 257 | invalidateHash(); |
269 | return this; | 258 | return this; |
270 | } else { | 259 | } else { |
271 | return null; | 260 | return null; |
@@ -374,10 +363,9 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
374 | // print subnodes | 363 | // print subnodes |
375 | for (int i = 0; i < FACTOR; i++) { | 364 | for (int i = 0; i < FACTOR; i++) { |
376 | if (content[2 * i] == null && content[2 * i + 1] != null) { | 365 | if (content[2 * i] == null && content[2 * i + 1] != null) { |
377 | @SuppressWarnings("unchecked") | 366 | @SuppressWarnings("unchecked") Node<K, V> subNode = (Node<K, V>) content[2 * i + 1]; |
378 | Node<K, V> subNode = (Node<K, V>) content[2 * i + 1]; | ||
379 | builder.append("\n"); | 367 | builder.append("\n"); |
380 | subNode.prettyPrint(builder, depth + 1, i); | 368 | subNode.prettyPrint(builder, incrementDepth(depth), i); |
381 | } | 369 | } |
382 | } | 370 | } |
383 | } | 371 | } |
@@ -394,57 +382,69 @@ public class MutableNode<K, V> extends Node<K, V> { | |||
394 | // check the place of data | 382 | // check the place of data |
395 | for (int i = 0; i < FACTOR; i++) { | 383 | for (int i = 0; i < FACTOR; i++) { |
396 | if (this.content[2 * i] != null) { | 384 | if (this.content[2 * i] != null) { |
397 | @SuppressWarnings("unchecked") | 385 | @SuppressWarnings("unchecked") K key = (K) this.content[2 * i]; |
398 | K key = (K) this.content[2 * i]; | 386 | @SuppressWarnings("unchecked") V value = (V) this.content[2 * i + 1]; |
399 | @SuppressWarnings("unchecked") | ||
400 | V value = (V) this.content[2 * i + 1]; | ||
401 | 387 | ||
402 | if (value == defaultValue) { | 388 | if (value == defaultValue) { |
403 | throw new IllegalStateException("Node contains default nodeId!"); | 389 | throw new IllegalStateException("Node contains default value!"); |
404 | } | 390 | } |
405 | int hashCode = hashProvider.getHash(key, hashDepth(depth)); | 391 | int hashCode = hashProvider.getHash(key, hashDepth(depth)); |
406 | int shiftDepth = shiftDepth(depth); | 392 | int shiftDepth = shiftDepth(depth); |
407 | int selectedHashFragment = hashFragment(hashCode, shiftDepth); | 393 | int selectedHashFragment = hashFragment(hashCode, shiftDepth); |
408 | if (i != selectedHashFragment) { | 394 | if (i != selectedHashFragment) { |
409 | throw new IllegalStateException("Key " + key + " with hash code " + hashCode | 395 | throw new IllegalStateException("Key " + key + " with hash code " + hashCode + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i); |
410 | + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i); | ||
411 | } | 396 | } |
412 | } | 397 | } |
413 | } | 398 | } |
414 | // check subnodes | 399 | // check subnodes |
415 | for (int i = 0; i < FACTOR; i++) { | 400 | for (int i = 0; i < FACTOR; i++) { |
416 | if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { | 401 | if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { |
417 | @SuppressWarnings("unchecked") | 402 | @SuppressWarnings("unchecked") var subNode = (Node<K, V>) this.content[2 * i + 1]; |
418 | var subNode = (Node<K, V>) this.content[2 * i + 1]; | 403 | subNode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth)); |
419 | subNode.checkIntegrity(hashProvider, defaultValue, depth + 1); | ||
420 | } | 404 | } |
421 | } | 405 | } |
422 | // check the hash | 406 | // check the hash |
423 | int oldHash = this.cachedHash; | 407 | if (cachedHashValid) { |
424 | updateHash(); | 408 | int oldHash = this.cachedHash; |
425 | int newHash = this.cachedHash; | 409 | invalidateHash(); |
426 | if (oldHash != newHash) { | 410 | int newHash = hashCode(); |
427 | throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")"); | 411 | if (oldHash != newHash) { |
412 | throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")"); | ||
413 | } | ||
428 | } | 414 | } |
429 | } | 415 | } |
430 | 416 | ||
431 | protected void updateHash() { | 417 | protected void invalidateHash() { |
432 | this.cachedHash = Arrays.hashCode(content); | 418 | this.cachedHashValid = false; |
433 | } | 419 | } |
434 | 420 | ||
435 | @Override | 421 | @Override |
436 | public int hashCode() { | 422 | public int hashCode() { |
437 | return this.cachedHash; | 423 | if (this.cachedHashValid) { |
424 | return this.cachedHash; | ||
425 | } else { | ||
426 | this.cachedHash = Arrays.hashCode(content); | ||
427 | this.cachedHashValid = true; | ||
428 | return this.cachedHash; | ||
429 | } | ||
438 | } | 430 | } |
439 | 431 | ||
440 | @Override | 432 | @Override |
441 | public boolean equals(Object obj) { | 433 | public boolean equals(Object obj) { |
442 | if (this == obj) | 434 | if (this == obj) return true; |
443 | return true; | 435 | if (obj == null) return false; |
444 | if (obj == null) | ||
445 | return false; | ||
446 | if (obj instanceof MutableNode<?, ?> mutableObj) { | 436 | if (obj instanceof MutableNode<?, ?> mutableObj) { |
447 | return Arrays.deepEquals(this.content, mutableObj.content); | 437 | if (obj.hashCode() != this.hashCode()) { |
438 | return false; | ||
439 | } else { | ||
440 | for (int i = 0; i < FACTOR * 2; i++) { | ||
441 | Object thisContent = this.content[i]; | ||
442 | if (thisContent != null && !thisContent.equals(mutableObj.content[i])) { | ||
443 | return false; | ||
444 | } | ||
445 | } | ||
446 | return true; | ||
447 | } | ||
448 | } else if (obj instanceof ImmutableNode<?, ?> immutableObj) { | 448 | } else if (obj instanceof ImmutableNode<?, ?> immutableObj) { |
449 | return ImmutableNode.compareImmutableMutable(immutableObj, this); | 449 | return ImmutableNode.compareImmutableMutable(immutableObj, this); |
450 | } else { | 450 | } else { |
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java index 2260cd5b..c49be280 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java | |||
@@ -4,82 +4,121 @@ import java.util.Map; | |||
4 | 4 | ||
5 | import tools.refinery.store.map.ContinousHashProvider; | 5 | import tools.refinery.store.map.ContinousHashProvider; |
6 | 6 | ||
7 | public abstract class Node<K,V>{ | 7 | public abstract class Node<K, V> { |
8 | public static final int BRANCHING_FACTOR_BITS = 5; | 8 | public static final int BRANCHING_FACTOR_BITS = 5; |
9 | public static final int FACTOR = 1<<BRANCHING_FACTOR_BITS; | 9 | public static final int FACTOR = 1 << BRANCHING_FACTOR_BITS; |
10 | protected static final int NUMBER_OF_FACTORS = Integer.SIZE / 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; | 11 | protected static final int FACTOR_MASK = FACTOR - 1; |
12 | public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS; | 12 | public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS; |
13 | public static final int FACTOR_SELECTION_BITS = 32 - Integer.numberOfLeadingZeros(NUMBER_OF_FACTORS); | ||
14 | public static final int FACTOR_SELECTION_MASK = (1 << FACTOR_SELECTION_BITS) - 1; | ||
15 | public static final int INCREMENT_BIG_STEP = (1 << FACTOR_SELECTION_BITS) - NUMBER_OF_FACTORS; | ||
16 | |||
17 | /** | ||
18 | * Increments the depth of the search in the tree. The depth parameter has two | ||
19 | * components: the least few bits selects the fragment of the hashcode, the | ||
20 | * other part selects the continuous hash. | ||
21 | * | ||
22 | * @param depth parameter encoding the fragment and the depth | ||
23 | * @return new depth. | ||
24 | */ | ||
25 | protected int incrementDepth(int depth) { | ||
26 | int newDepth = depth + 1; | ||
27 | if ((newDepth & FACTOR_SELECTION_MASK) == NUMBER_OF_FACTORS) { | ||
28 | newDepth += INCREMENT_BIG_STEP; | ||
29 | } | ||
30 | return newDepth; | ||
31 | } | ||
13 | 32 | ||
14 | /** | 33 | /** |
15 | * Calculates the index for the continuous hash. | 34 | * Calculates the index for the continuous hash. |
35 | * | ||
16 | * @param depth The depth of the node in the tree. | 36 | * @param depth The depth of the node in the tree. |
17 | * @return The index of the continuous hash. | 37 | * @return The index of the continuous hash. |
18 | */ | 38 | */ |
19 | protected static int hashDepth(int depth) { | 39 | protected static int hashDepth(int depth) { |
20 | return depth/NUMBER_OF_FACTORS; | 40 | return depth >> FACTOR_SELECTION_BITS; |
21 | } | 41 | } |
22 | 42 | ||
23 | /** | 43 | /** |
24 | * Calculates the which segment of a single hash should be used. | 44 | * Calculates the which segment of a single hash should be used. |
45 | * | ||
25 | * @param depth The depth of the node in the tree. | 46 | * @param depth The depth of the node in the tree. |
26 | * @return The segment of a hash code. | 47 | * @return The segment of a hash code. |
27 | */ | 48 | */ |
28 | protected static int shiftDepth(int depth) { | 49 | protected static int shiftDepth(int depth) { |
29 | return depth%NUMBER_OF_FACTORS; | 50 | return depth & FACTOR_SELECTION_MASK; |
30 | } | 51 | } |
52 | |||
31 | /** | 53 | /** |
32 | * Selects a segments from a complete hash for a given depth. | 54 | * Selects a segments from a complete hash for a given depth. |
33 | * @param hash A complete hash. | 55 | * |
56 | * @param hash A complete hash. | ||
34 | * @param shiftDepth The index of the segment. | 57 | * @param shiftDepth The index of the segment. |
35 | * @return The segment as an integer. | 58 | * @return The segment as an integer. |
36 | */ | 59 | */ |
37 | protected static int hashFragment(int hash, int shiftDepth) { | 60 | 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); | 61 | if (shiftDepth < 0 || Node.NUMBER_OF_FACTORS < shiftDepth) |
39 | return (hash >>> shiftDepth*BRANCHING_FACTOR_BITS) & FACTOR_MASK; | 62 | throw new IllegalArgumentException("Invalid shift depth! valid interval=[0;5], input=" + shiftDepth); |
63 | return (hash >>> shiftDepth * BRANCHING_FACTOR_BITS) & FACTOR_MASK; | ||
40 | } | 64 | } |
41 | 65 | ||
42 | /** | 66 | /** |
43 | * Returns the hash code for a given depth. It may calculate new hash code, or reuse a hash code calculated for depth-1. | 67 | * Returns the hash code for a given depth. It may calculate new hash code, or |
44 | * @param key The key. | 68 | * reuse a hash code calculated for depth-1. |
45 | * @param hash Hash code for depth-1 | 69 | * |
70 | * @param key The key. | ||
71 | * @param hash Hash code for depth-1 | ||
46 | * @param depth The depth. | 72 | * @param depth The depth. |
47 | * @return The new hash code. | 73 | * @return The new hash code. |
48 | */ | 74 | */ |
49 | protected int newHash(final ContinousHashProvider<? super K> hashProvider, K key, int hash, int depth) { | 75 | protected int newHash(final ContinousHashProvider<? super K> hashProvider, K key, int hash, int depth) { |
50 | final int hashDepth = hashDepth(depth); | 76 | final int shiftDepth = shiftDepth(depth); |
51 | if(hashDepth>=ContinousHashProvider.MAX_PRACTICAL_DEPTH) { | 77 | if (shiftDepth == 0) { |
52 | throw new IllegalArgumentException("Key "+key+" have the clashing hashcode over the practical depth limitation ("+ContinousHashProvider.MAX_PRACTICAL_DEPTH+")!"); | 78 | final int hashDepth = hashDepth(depth); |
79 | if (hashDepth >= ContinousHashProvider.MAX_PRACTICAL_DEPTH) { | ||
80 | throw new IllegalArgumentException( | ||
81 | "Key " + key + " have the clashing hashcode over the practical depth limitation (" | ||
82 | + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!"); | ||
83 | } | ||
84 | return hashProvider.getHash(key, hashDepth); | ||
85 | } else { | ||
86 | return hash; | ||
53 | } | 87 | } |
54 | return depth%NUMBER_OF_FACTORS == 0? | ||
55 | hashProvider.getHash(key, hashDepth) : | ||
56 | hash; | ||
57 | } | 88 | } |
58 | 89 | ||
90 | public abstract V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, | ||
91 | int depth); | ||
92 | |||
93 | public abstract Node<K, V> putValue(K key, V value, OldValueBox<V> old, | ||
94 | ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth); | ||
59 | 95 | ||
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(); | 96 | public abstract long getSize(); |
63 | 97 | ||
64 | abstract MutableNode<K, V> toMutable(); | 98 | abstract MutableNode<K, V> toMutable(); |
65 | public abstract ImmutableNode<K, V> toImmutable( | 99 | |
66 | Map<Node<K, V>,ImmutableNode<K, V>> cache); | 100 | public abstract ImmutableNode<K, V> toImmutable(Map<Node<K, V>, ImmutableNode<K, V>> cache); |
101 | |||
67 | protected abstract MutableNode<K, V> isMutable(); | 102 | protected abstract MutableNode<K, V> isMutable(); |
103 | |||
68 | /** | 104 | /** |
69 | * Moves a {@link MapCursor} to its next position. | 105 | * Moves a {@link MapCursor} to its next position. |
106 | * | ||
70 | * @param cursor the cursor | 107 | * @param cursor the cursor |
71 | * @return Whether there was a next nodeId to move on. | 108 | * @return Whether there was a next value to move on. |
72 | */ | 109 | */ |
73 | abstract boolean moveToNext(MapCursor<K,V> cursor); | 110 | abstract boolean moveToNext(MapCursor<K, V> cursor); |
74 | 111 | ||
75 | ///////// FOR printing | 112 | ///////// FOR printing |
76 | public abstract void prettyPrint(StringBuilder builder, int depth, int code); | 113 | public abstract void prettyPrint(StringBuilder builder, int depth, int code); |
114 | |||
77 | @Override | 115 | @Override |
78 | public String toString() { | 116 | public String toString() { |
79 | StringBuilder stringBuilder = new StringBuilder(); | 117 | StringBuilder stringBuilder = new StringBuilder(); |
80 | prettyPrint(stringBuilder, 0, -1); | 118 | prettyPrint(stringBuilder, 0, -1); |
81 | return stringBuilder.toString(); | 119 | return stringBuilder.toString(); |
82 | } | 120 | } |
83 | public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {} | ||
84 | 121 | ||
122 | public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) { | ||
123 | } | ||
85 | } | 124 | } |
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java index 301bcb95..57256472 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java | |||
@@ -18,7 +18,6 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> { | |||
18 | protected final VersionedMapStoreImpl<K, V> store; | 18 | protected final VersionedMapStoreImpl<K, V> store; |
19 | 19 | ||
20 | protected final ContinousHashProvider<K> hashProvider; | 20 | protected final ContinousHashProvider<K> hashProvider; |
21 | |||
22 | protected final V defaultValue; | 21 | protected final V defaultValue; |
23 | protected Node<K, V> root; | 22 | protected Node<K, V> root; |
24 | 23 | ||
@@ -109,6 +108,7 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> { | |||
109 | 108 | ||
110 | @Override | 109 | @Override |
111 | public DiffCursor<K, V> getDiffCursor(long toVersion) { | 110 | public DiffCursor<K, V> getDiffCursor(long toVersion) { |
111 | |||
112 | Cursor<K, V> fromCursor = this.getAll(); | 112 | Cursor<K, V> fromCursor = this.getAll(); |
113 | VersionedMap<K, V> toMap = this.store.createMap(toVersion); | 113 | VersionedMap<K, V> toMap = this.store.createMap(toVersion); |
114 | Cursor<K, V> toCursor = toMap.getAll(); | 114 | Cursor<K, V> toCursor = toMap.getAll(); |
@@ -131,13 +131,35 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> { | |||
131 | root = this.store.revert(state); | 131 | root = this.store.revert(state); |
132 | } | 132 | } |
133 | 133 | ||
134 | public void prettyPrint() { | 134 | @Override |
135 | StringBuilder s = new StringBuilder(); | 135 | public int hashCode() { |
136 | final int prime = 31; | ||
137 | int result = 1; | ||
138 | result = prime * result + ((root == null) ? 0 : root.hashCode()); | ||
139 | return result; | ||
140 | } | ||
141 | |||
142 | @Override | ||
143 | public boolean equals(Object obj) { | ||
144 | if (this == obj) | ||
145 | return true; | ||
146 | if (obj == null) | ||
147 | return false; | ||
148 | if (getClass() != obj.getClass()) | ||
149 | return false; | ||
150 | VersionedMapImpl<?, ?> other = (VersionedMapImpl<?, ?>) obj; | ||
151 | if (root == null) { | ||
152 | return other.root == null; | ||
153 | } else return root.equals(other.root); | ||
154 | } | ||
155 | |||
156 | public String prettyPrint() { | ||
136 | if (this.root != null) { | 157 | if (this.root != null) { |
158 | StringBuilder s = new StringBuilder(); | ||
137 | this.root.prettyPrint(s, 0, -1); | 159 | this.root.prettyPrint(s, 0, -1); |
138 | System.out.println(s.toString()); | 160 | return s.toString(); |
139 | } else { | 161 | } else { |
140 | System.out.println("empty tree"); | 162 | return "empty tree"; |
141 | } | 163 | } |
142 | } | 164 | } |
143 | 165 | ||