From b8982d4b49d385b94ecfb00ac5838d3b98f46636 Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Sat, 4 Feb 2023 03:11:49 +0100 Subject: Performance improvements by replacing hash depth calculation with shifting, improving code quality. + formatting --- .../refinery/store/map/internal/ImmutableNode.java | 65 ++++----- .../refinery/store/map/internal/MutableNode.java | 156 ++++++++++----------- .../tools/refinery/store/map/internal/Node.java | 87 ++++++++---- .../store/map/internal/VersionedMapImpl.java | 32 ++++- 4 files changed, 193 insertions(+), 147 deletions(-) (limited to 'subprojects/store/src/main') 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 extends Node { * available. * @return an immutable version of the input node. */ - static ImmutableNode constructImmutable(MutableNode node, - Map, ImmutableNode> cache) { + static ImmutableNode constructImmutable(MutableNode node, Map, ImmutableNode> cache) { // 1. try to return from cache if (cache != null) { ImmutableNode cachedResult = cache.get(node); @@ -75,8 +74,7 @@ public class ImmutableNode extends Node { resultContent[datas * 2 + 1] = node.content[i * 2 + 1]; datas++; } else { - @SuppressWarnings("unchecked") - var subnode = (Node) node.content[i * 2 + 1]; + @SuppressWarnings("unchecked") var subnode = (Node) node.content[i * 2 + 1]; if (subnode != null) { ImmutableNode immutableSubnode = subnode.toImmutable(cache); resultNodeMap |= bitposition; @@ -107,11 +105,9 @@ public class ImmutableNode extends Node { // If the key is stored as a data if ((dataMap & bitposition) != 0) { int keyIndex = 2 * index(dataMap, bitposition); - @SuppressWarnings("unchecked") - K keyCandidate = (K) content[keyIndex]; + @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; if (keyCandidate.equals(key)) { - @SuppressWarnings("unchecked") - V value = (V) content[keyIndex + 1]; + @SuppressWarnings("unchecked") V value = (V) content[keyIndex + 1]; return value; } else { return defaultValue; @@ -120,9 +116,8 @@ public class ImmutableNode extends Node { // the key is stored as a node else if ((nodeMap & bitposition) != 0) { int keyIndex = content.length - 1 - index(nodeMap, bitposition); - @SuppressWarnings("unchecked") - var subNode = (ImmutableNode) content[keyIndex]; - int newDepth = depth + 1; + @SuppressWarnings("unchecked") var subNode = (ImmutableNode) content[keyIndex]; + int newDepth = incrementDepth(depth); int newHash = newHash(hashProvider, key, hash, newDepth); return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); } @@ -133,14 +128,12 @@ public class ImmutableNode extends Node { } @Override - public Node putValue(K key, V value, OldValueBox oldValue, ContinousHashProvider hashProvider, - V defaultValue, int hash, int depth) { + public Node putValue(K key, V value, OldValueBox oldValue, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth) { int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); int bitposition = 1 << selectedHashFragment; if ((dataMap & bitposition) != 0) { int keyIndex = 2 * index(dataMap, bitposition); - @SuppressWarnings("unchecked") - K keyCandidate = (K) content[keyIndex]; + @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex]; if (keyCandidate.equals(key)) { if (value == defaultValue) { // delete @@ -151,7 +144,7 @@ public class ImmutableNode extends Node { oldValue.setOldValue(value); return this; } else { - // update existing nodeId + // update existing value MutableNode mutable = this.toMutable(); return mutable.updateValue(value, oldValue, selectedHashFragment); } @@ -161,16 +154,15 @@ public class ImmutableNode extends Node { oldValue.setOldValue(defaultValue); return this; } else { - // add new key + nodeId + // add new key + value MutableNode mutable = this.toMutable(); return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); } } } else if ((nodeMap & bitposition) != 0) { int keyIndex = content.length - 1 - index(nodeMap, bitposition); - @SuppressWarnings("unchecked") - var subNode = (ImmutableNode) content[keyIndex]; - int newDepth = depth + 1; + @SuppressWarnings("unchecked") var subNode = (ImmutableNode) content[keyIndex]; + int newDepth = incrementDepth(depth); int newHash = newHash(hashProvider, key, hash, newDepth); var newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth); @@ -179,10 +171,11 @@ public class ImmutableNode extends Node { return this; } else { MutableNode mutable = toMutable(); - return mutable.updateWithSubNode(selectedHashFragment, newsubNode, value.equals(defaultValue)); + return mutable.updateWithSubNode(selectedHashFragment, newsubNode, + (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); } } else { - // add new key + nodeId + // add new key + value MutableNode mutable = this.toMutable(); return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); } @@ -192,8 +185,7 @@ public class ImmutableNode extends Node { public long getSize() { int result = Integer.bitCount(this.dataMap); for (int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) { - @SuppressWarnings("unchecked") - var subnode = (ImmutableNode) this.content[this.content.length - 1 - subnodeIndex]; + @SuppressWarnings("unchecked") var subnode = (ImmutableNode) this.content[this.content.length - 1 - subnodeIndex]; result += subnode.getSize(); } return result; @@ -289,10 +281,9 @@ public class ImmutableNode extends Node { int nodeMask = 1; for (int i = 0; i < FACTOR; i++) { if ((nodeMask & nodeMap) != 0) { - @SuppressWarnings("unchecked") - Node subNode = (Node) content[content.length - 1 - index(nodeMap, nodeMask)]; + @SuppressWarnings("unchecked") Node subNode = (Node) content[content.length - 1 - index(nodeMap, nodeMask)]; builder.append("\n"); - subNode.prettyPrint(builder, depth + 1, i); + subNode.prettyPrint(builder, incrementDepth(depth), i); } nodeMask <<= 1; } @@ -310,12 +301,11 @@ public class ImmutableNode extends Node { // check subnodes for (int i = 0; i < Integer.bitCount(nodeMap); i++) { - @SuppressWarnings("unchecked") - var subnode = (Node) this.content[this.content.length - 1 - i]; + @SuppressWarnings("unchecked") var subnode = (Node) this.content[this.content.length - 1 - i]; if (!(subnode instanceof ImmutableNode)) { throw new IllegalStateException("Immutable node contains mutable subnodes!"); } else { - subnode.checkIntegrity(hashProvider, defaultValue, depth + 1); + subnode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth)); } } } @@ -327,13 +317,10 @@ public class ImmutableNode extends Node { @Override public boolean equals(Object obj) { - if (this == obj) - return true; - if (obj == null) - return false; + if (this == obj) return true; + if (obj == null) return false; if (obj instanceof ImmutableNode other) { - return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap - && Arrays.deepEquals(content, other.content); + return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap && Arrays.deepEquals(content, other.content); } else if (obj instanceof MutableNode mutableObj) { return ImmutableNode.compareImmutableMutable(this, mutableObj); } else { @@ -351,12 +338,10 @@ public class ImmutableNode extends Node { if (key != null) { // Check whether a new Key-Value pair can fit into the immutable container if (datas * 2 + nodes + 2 <= immutableLength) { - if (!immutable.content[datas * 2].equals(key) - || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) { + if (!immutable.content[datas * 2].equals(key) || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) { return false; } - } else - return false; + } else return false; datas++; } else { 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; public class MutableNode extends Node { int cachedHash; + protected boolean cachedHashValid; protected Object[] content; protected MutableNode() { this.content = new Object[2 * FACTOR]; - updateHash(); + invalidateHash(); } - public static MutableNode initialize(K key, V value, ContinousHashProvider hashProvider, - V defaultValue) { + public static MutableNode initialize(K key, V value, ContinousHashProvider hashProvider, V defaultValue) { if (value == defaultValue) { return null; } else { @@ -24,7 +24,7 @@ public class MutableNode extends Node { MutableNode res = new MutableNode<>(); res.content[2 * fragment] = key; res.content[2 * fragment + 1] = value; - res.updateHash(); + res.invalidateHash(); return res; } } @@ -32,7 +32,7 @@ public class MutableNode extends Node { /** * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode} * - * @param node + * @param node to be transformed */ protected MutableNode(ImmutableNode node) { this.content = new Object[2 * FACTOR]; @@ -49,27 +49,24 @@ public class MutableNode extends Node { nodeUsed++; } } - this.cachedHash = node.hashCode(); + this.cachedHashValid = false; } @Override public V getValue(K key, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth) { int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); - @SuppressWarnings("unchecked") - K keyCandidate = (K) this.content[2 * selectedHashFragment]; + @SuppressWarnings("unchecked") K keyCandidate = (K) this.content[2 * selectedHashFragment]; if (keyCandidate != null) { if (keyCandidate.equals(key)) { - @SuppressWarnings("unchecked") - V value = (V) this.content[2 * selectedHashFragment + 1]; + @SuppressWarnings("unchecked") V value = (V) this.content[2 * selectedHashFragment + 1]; return value; } else { return defaultValue; } } else { - @SuppressWarnings("unchecked") - var nodeCandidate = (Node) content[2 * selectedHashFragment + 1]; + @SuppressWarnings("unchecked") var nodeCandidate = (Node) content[2 * selectedHashFragment + 1]; if (nodeCandidate != null) { - int newDepth = depth + 1; + int newDepth = incrementDepth(depth); int newHash = newHash(hashProvider, key, hash, newDepth); return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); } else { @@ -79,11 +76,9 @@ public class MutableNode extends Node { } @Override - public Node putValue(K key, V value, OldValueBox oldValueBox, ContinousHashProvider hashProvider, - V defaultValue, int hash, int depth) { + public Node putValue(K key, V value, OldValueBox oldValueBox, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth) { int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); - @SuppressWarnings("unchecked") - K keyCandidate = (K) content[2 * selectedHashFragment]; + @SuppressWarnings("unchecked") K keyCandidate = (K) content[2 * selectedHashFragment]; if (keyCandidate != null) { // If has key if (keyCandidate.equals(key)) { @@ -107,18 +102,17 @@ public class MutableNode extends Node { } } } else { - // If it does not have key, check for nodeId - @SuppressWarnings("unchecked") - var nodeCandidate = (Node) content[2 * selectedHashFragment + 1]; + // If it does not have key, check for value + @SuppressWarnings("unchecked") var nodeCandidate = (Node) content[2 * selectedHashFragment + 1]; if (nodeCandidate != null) { - // If it has nodeId, it is a subnode -> upate that - var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, - newHash(hashProvider, key, hash, depth + 1), depth + 1); - return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue)); + // If it has value, it is a subnode -> upate that + int newDepth = incrementDepth(depth); + var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, newHash(hashProvider, key, hash, newDepth), newDepth); + return updateWithSubNode(selectedHashFragment, newNode, (value == null && defaultValue == null) || (value != null && value.equals(defaultValue))); } else { - // If it does not have nodeId, put it in the empty place + // If it does not have value, put it in the empty place if (value == defaultValue) { - // dont need to add new key-nodeId pair + // dont need to add new key-value pair oldValueBox.setOldValue(defaultValue); return this; } else { @@ -133,30 +127,31 @@ public class MutableNode extends Node { content[2 * selectedHashFragment] = key; oldValueBox.setOldValue(defaultValue); content[2 * selectedHashFragment + 1] = value; - updateHash(); + invalidateHash(); return this; } /** - * Updates an entry in a selected hash-fragment to a non-default nodeId. + * Updates an entry in a selected hash-fragment to a non-default value. * - * @param value - * @param selectedHashFragment - * @return + * @param value new value + * @param selectedHashFragment position of the value + * @return updated node */ @SuppressWarnings("unchecked") Node updateValue(V value, OldValueBox oldValue, int selectedHashFragment) { oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); content[2 * selectedHashFragment + 1] = value; - updateHash(); + invalidateHash(); return this; } /** + * Updates an entry in a selected hash-fragment with a subtree. * - * @param selectedHashFragment - * @param newNode - * @return + * @param selectedHashFragment position of the value + * @param newNode the subtree + * @return updated node */ Node updateWithSubNode(int selectedHashFragment, Node newNode, boolean deletionHappened) { if (deletionHappened) { @@ -164,7 +159,7 @@ public class MutableNode extends Node { // Check whether this node become empty content[2 * selectedHashFragment + 1] = null; // i.e. the new node if (hasContent()) { - updateHash(); + invalidateHash(); return this; } else { return null; @@ -178,7 +173,7 @@ public class MutableNode extends Node { // orphan subnode data is replaced with data content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2]; content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1]; - updateHash(); + invalidateHash(); return this; } } @@ -186,15 +181,13 @@ public class MutableNode extends Node { } // normal behaviour content[2 * selectedHashFragment + 1] = newNode; - updateHash(); + invalidateHash(); return this; - } private boolean hasContent() { for (Object element : this.content) { - if (element != null) - return true; + if (element != null) return true; } return false; } @@ -221,23 +214,20 @@ public class MutableNode extends Node { } @SuppressWarnings("unchecked") - private Node moveDownAndSplit(ContinousHashProvider hashProvider, K newKey, V newValue, - K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) { + private Node moveDownAndSplit(ContinousHashProvider hashProvider, K newKey, V newValue, K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) { V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1]; - MutableNode newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, - hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, depth + 1); + MutableNode newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, incrementDepth(depth)); content[2 * selectedHashFragmentOfCurrentDepth] = null; content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode; - updateHash(); + invalidateHash(); return this; } // Pass everything as parameters for performance. @SuppressWarnings("squid:S107") - private MutableNode newNodeWithTwoEntries(ContinousHashProvider hashProvider, K key1, V value1, - int oldHash1, K key2, V value2, int oldHash2, int newdepth) { + private MutableNode newNodeWithTwoEntries(ContinousHashProvider hashProvider, K key1, V value1, int oldHash1, K key2, V value2, int oldHash2, int newdepth) { int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth); int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth); int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth)); @@ -251,11 +241,10 @@ public class MutableNode extends Node { subNode.content[newFragment2 * 2] = key2; subNode.content[newFragment2 * 2 + 1] = value2; } else { - MutableNode subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, - newHash2, newdepth + 1); + MutableNode subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newdepth)); subNode.content[newFragment1 * 2 + 1] = subSubNode; } - subNode.updateHash(); + subNode.invalidateHash(); return subNode; } @@ -265,7 +254,7 @@ public class MutableNode extends Node { oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); content[2 * selectedHashFragment + 1] = null; if (hasContent()) { - updateHash(); + invalidateHash(); return this; } else { return null; @@ -374,10 +363,9 @@ public class MutableNode extends Node { // print subnodes for (int i = 0; i < FACTOR; i++) { if (content[2 * i] == null && content[2 * i + 1] != null) { - @SuppressWarnings("unchecked") - Node subNode = (Node) content[2 * i + 1]; + @SuppressWarnings("unchecked") Node subNode = (Node) content[2 * i + 1]; builder.append("\n"); - subNode.prettyPrint(builder, depth + 1, i); + subNode.prettyPrint(builder, incrementDepth(depth), i); } } } @@ -394,57 +382,69 @@ public class MutableNode extends Node { // check the place of data for (int i = 0; i < FACTOR; i++) { if (this.content[2 * i] != null) { - @SuppressWarnings("unchecked") - K key = (K) this.content[2 * i]; - @SuppressWarnings("unchecked") - V value = (V) this.content[2 * i + 1]; + @SuppressWarnings("unchecked") K key = (K) this.content[2 * i]; + @SuppressWarnings("unchecked") V value = (V) this.content[2 * i + 1]; if (value == defaultValue) { - throw new IllegalStateException("Node contains default nodeId!"); + throw new IllegalStateException("Node contains default value!"); } int hashCode = hashProvider.getHash(key, hashDepth(depth)); int shiftDepth = shiftDepth(depth); int selectedHashFragment = hashFragment(hashCode, shiftDepth); if (i != selectedHashFragment) { - throw new IllegalStateException("Key " + key + " with hash code " + hashCode - + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i); + throw new IllegalStateException("Key " + key + " with hash code " + hashCode + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i); } } } // check subnodes for (int i = 0; i < FACTOR; i++) { if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { - @SuppressWarnings("unchecked") - var subNode = (Node) this.content[2 * i + 1]; - subNode.checkIntegrity(hashProvider, defaultValue, depth + 1); + @SuppressWarnings("unchecked") var subNode = (Node) this.content[2 * i + 1]; + subNode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth)); } } // check the hash - int oldHash = this.cachedHash; - updateHash(); - int newHash = this.cachedHash; - if (oldHash != newHash) { - throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")"); + if (cachedHashValid) { + int oldHash = this.cachedHash; + invalidateHash(); + int newHash = hashCode(); + if (oldHash != newHash) { + throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")"); + } } } - protected void updateHash() { - this.cachedHash = Arrays.hashCode(content); + protected void invalidateHash() { + this.cachedHashValid = false; } @Override public int hashCode() { - return this.cachedHash; + if (this.cachedHashValid) { + return this.cachedHash; + } else { + this.cachedHash = Arrays.hashCode(content); + this.cachedHashValid = true; + return this.cachedHash; + } } @Override public boolean equals(Object obj) { - if (this == obj) - return true; - if (obj == null) - return false; + if (this == obj) return true; + if (obj == null) return false; if (obj instanceof MutableNode mutableObj) { - return Arrays.deepEquals(this.content, mutableObj.content); + if (obj.hashCode() != this.hashCode()) { + return false; + } else { + for (int i = 0; i < FACTOR * 2; i++) { + Object thisContent = this.content[i]; + if (thisContent != null && !thisContent.equals(mutableObj.content[i])) { + return false; + } + } + return true; + } } else if (obj instanceof ImmutableNode immutableObj) { return ImmutableNode.compareImmutableMutable(immutableObj, this); } 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; import tools.refinery.store.map.ContinousHashProvider; -public abstract class Node{ +public abstract class Node { public static final int BRANCHING_FACTOR_BITS = 5; - public static final int FACTOR = 1<> FACTOR_SELECTION_BITS; } /** * Calculates the which segment of a single hash should be used. + * * @param depth The depth of the node in the tree. * @return The segment of a hash code. */ protected static int shiftDepth(int depth) { - return depth%NUMBER_OF_FACTORS; + return depth & FACTOR_SELECTION_MASK; } + /** * Selects a segments from a complete hash for a given depth. - * @param hash A complete hash. + * + * @param hash A complete hash. * @param shiftDepth The index of the segment. * @return The segment as an integer. */ protected static int hashFragment(int hash, int shiftDepth) { - if(shiftDepth<0 || Node.NUMBER_OF_FACTORS= ContinousHashProvider.MAX_PRACTICAL_DEPTH) { + throw new IllegalArgumentException( + "Key " + key + " have the clashing hashcode over the practical depth limitation (" + + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!"); + } + return hashProvider.getHash(key, hashDepth); + } else { + return hash; } - return depth%NUMBER_OF_FACTORS == 0? - hashProvider.getHash(key, hashDepth) : - hash; } + public abstract V getValue(K key, ContinousHashProvider hashProvider, V defaultValue, int hash, + int depth); + + public abstract Node putValue(K key, V value, OldValueBox old, + ContinousHashProvider hashProvider, V defaultValue, int hash, int depth); - public abstract V getValue(K key, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth); - public abstract Node putValue(K key, V value, OldValueBox old, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth); public abstract long getSize(); abstract MutableNode toMutable(); - public abstract ImmutableNode toImmutable( - Map,ImmutableNode> cache); + + public abstract ImmutableNode toImmutable(Map, ImmutableNode> cache); + protected abstract MutableNode isMutable(); + /** * Moves a {@link MapCursor} to its next position. + * * @param cursor the cursor - * @return Whether there was a next nodeId to move on. + * @return Whether there was a next value to move on. */ - abstract boolean moveToNext(MapCursor cursor); + abstract boolean moveToNext(MapCursor cursor); ///////// FOR printing public abstract void prettyPrint(StringBuilder builder, int depth, int code); + @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); prettyPrint(stringBuilder, 0, -1); return stringBuilder.toString(); } - public void checkIntegrity(ContinousHashProvider hashProvider, V defaultValue, int depth) {} + public void checkIntegrity(ContinousHashProvider hashProvider, V defaultValue, int depth) { + } } 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 implements VersionedMap { protected final VersionedMapStoreImpl store; protected final ContinousHashProvider hashProvider; - protected final V defaultValue; protected Node root; @@ -109,6 +108,7 @@ public class VersionedMapImpl implements VersionedMap { @Override public DiffCursor getDiffCursor(long toVersion) { + Cursor fromCursor = this.getAll(); VersionedMap toMap = this.store.createMap(toVersion); Cursor toCursor = toMap.getAll(); @@ -131,13 +131,35 @@ public class VersionedMapImpl implements VersionedMap { root = this.store.revert(state); } - public void prettyPrint() { - StringBuilder s = new StringBuilder(); + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + ((root == null) ? 0 : root.hashCode()); + return result; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) + return true; + if (obj == null) + return false; + if (getClass() != obj.getClass()) + return false; + VersionedMapImpl other = (VersionedMapImpl) obj; + if (root == null) { + return other.root == null; + } else return root.equals(other.root); + } + + public String prettyPrint() { if (this.root != null) { + StringBuilder s = new StringBuilder(); this.root.prettyPrint(s, 0, -1); - System.out.println(s.toString()); + return s.toString(); } else { - System.out.println("empty tree"); + return "empty tree"; } } -- cgit v1.2.3-54-g00ecf