From bd4a77df9e4cda57806c9df2b272b40e82e9ae65 Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Sun, 1 Aug 2021 21:59:06 +0200 Subject: Hashprovide + Node update to make better equals/hashcodes services --- .../solver/data/map/ContinousHashProvider.java | 13 +- .../solver/data/map/internal/ImmutableNode.java | 29 +- .../solver/data/map/internal/MutableNode.java | 380 ++++++++++++--------- .../viatra/solver/data/map/internal/Node.java | 8 +- 4 files changed, 253 insertions(+), 177 deletions(-) (limited to 'model-data/src') diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java index 79ca4412..6ab45c7c 100644 --- a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java @@ -48,12 +48,17 @@ public interface ContinousHashProvider { if (key1.equals(key2)) { return 0; } else { - for (var i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) { + for (int i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) { int hash1 = getEffectiveHash(key1, i); int hash2 = getEffectiveHash(key2, i); - var result = Integer.compare(hash1, hash2); - if (result != 0) { - return result; + for(int j = 0; j>>j*Node.branchingFactorBit) & factorMask; + int hashFragment2 = (hash2>>>j*Node.branchingFactorBit) & factorMask; + var result = Integer.compare(hashFragment1, hashFragment2); + if (result != 0) { + return result; + } } } throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2 diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java index 832742d0..5f293f70 100644 --- a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java @@ -174,7 +174,7 @@ public class ImmutableNode extends Node { return this; } else { MutableNode mutable = toMutable(); - Node result = mutable.updateSubNode(selectedHashFragment, newsubNode); + Node result = mutable.updateWithSubNode(selectedHashFragment, newsubNode, value.equals(defaultValue)); return result; } } else { @@ -209,6 +209,11 @@ public class ImmutableNode extends Node { return this; } + @Override + protected MutableNode isMutable() { + return null; + } + @SuppressWarnings("unchecked") @Override boolean moveToNext(MapCursor cursor) { @@ -293,6 +298,28 @@ public class ImmutableNode extends Node { } } + @SuppressWarnings("unchecked") + @Override + public void checkIntegrity(ContinousHashProvider hashProvider, VALUE defaultValue, int depth) { + if(depth>0) { + boolean orphaned = Integer.bitCount(dataMap) == 1 && nodeMap == 0; + if(orphaned) { + throw new IllegalStateException("Orphaned node! " + dataMap + ": " + content[0]); + } + } + // check the place of data + + // check subnodes + for(int i = 0; i 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); + } + } + } + @Override public int hashCode() { return this.precalculatedHash; diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java index d32e5fc9..f28405da 100644 --- a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java @@ -5,69 +5,69 @@ import java.util.Map; import org.eclipse.viatra.solver.data.map.ContinousHashProvider; -public class MutableNode extends Node { +public class MutableNode extends Node { int cachedHash; protected Object[] content; - + protected MutableNode() { - this.content = new Object[2*factor]; + this.content = new Object[2 * factor]; updateHash(); } - public static MutableNode initialize( - KEY key, VALUE value, - ContinousHashProvider hashProvider, - VALUE defaultValue) - { - if(value == defaultValue) { + + public static MutableNode initialize(KEY key, VALUE value, + ContinousHashProvider hashProvider, VALUE defaultValue) { + if (value == defaultValue) { return null; } else { int hash = hashProvider.getHash(key, 0); int fragment = hashFragment(hash, 0); MutableNode res = new MutableNode(); - res.content[2*fragment] = key; - res.content[2*fragment+1] = value; + res.content[2 * fragment] = key; + res.content[2 * fragment + 1] = value; res.updateHash(); return res; } } - + /** * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode} + * * @param node */ - protected MutableNode(ImmutableNode node) { - this.content = new Object[2*factor]; - int dataUsed=0; - int nodeUsed=0; - for(int i=0; i node) { + this.content = new Object[2 * factor]; + int dataUsed = 0; + int nodeUsed = 0; + for (int i = 0; i < factor; i++) { int bitposition = 1 << i; - if((node.dataMap & bitposition) != 0) { - content[2*i] = node.content[dataUsed*2]; - content[2*i+1] = node.content[dataUsed*2+1]; + if ((node.dataMap & bitposition) != 0) { + content[2 * i] = node.content[dataUsed * 2]; + content[2 * i + 1] = node.content[dataUsed * 2 + 1]; dataUsed++; - } else if((node.nodeMap & bitposition) != 0) { - content[2*i+1] = node.content[node.content.length-1-nodeUsed]; + } else if ((node.nodeMap & bitposition) != 0) { + content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed]; nodeUsed++; } } this.cachedHash = node.hashCode(); } - + @SuppressWarnings("unchecked") @Override - public VALUE getValue(KEY key, ContinousHashProvider hashProvider, VALUE defaultValue, int hash, int depth) { - int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); - KEY keyCandidate = (KEY) this.content[2*selectedHashFragment]; - if(keyCandidate != null) { - if(keyCandidate.equals(key)) { - return (VALUE) this.content[2*selectedHashFragment+1]; + public VALUE getValue(KEY key, ContinousHashProvider hashProvider, VALUE defaultValue, int hash, + int depth) { + int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); + KEY keyCandidate = (KEY) this.content[2 * selectedHashFragment]; + if (keyCandidate != null) { + if (keyCandidate.equals(key)) { + return (VALUE) this.content[2 * selectedHashFragment + 1]; } else { return defaultValue; } } else { - Node nodeCandidate = (Node) content[2*selectedHashFragment+1]; - if(nodeCandidate != null) { - int newDepth = depth+1; + Node nodeCandidate = (Node) content[2 * selectedHashFragment + 1]; + if (nodeCandidate != null) { + int newDepth = depth + 1; int newHash = newHash(hashProvider, key, hash, newDepth); return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); } else { @@ -75,32 +75,26 @@ public class MutableNode extends Node { } } } - - private boolean hasContent() { - for(Object element : this.content) { - if(element != null) return true; - } - return false; - } - + @SuppressWarnings("unchecked") @Override - public Node putValue(KEY key, VALUE value, ContinousHashProvider hashProvider, VALUE defaultValue, int hash, int depth) { - int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); - KEY keyCandidate = (KEY) content[2*selectedHashFragment]; - if(keyCandidate != null) { + public Node putValue(KEY key, VALUE value, ContinousHashProvider hashProvider, + VALUE defaultValue, int hash, int depth) { + int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); + KEY keyCandidate = (KEY) content[2 * selectedHashFragment]; + if (keyCandidate != null) { // If has key - if(keyCandidate.equals(key)) { + if (keyCandidate.equals(key)) { // The key is equals to an existing key -> update entry - if(value == defaultValue) { + if (value == defaultValue) { return removeEntry(selectedHashFragment); } else { - return updateValue(value,selectedHashFragment); + return updateValue(value, selectedHashFragment); } } else { // The key is not equivalent to an existing key on the same hash bin - // -> split entry if it is necessary - if(value == defaultValue) { + // -> split entry if it is necessary + if (value == defaultValue) { // Value is default -> do not need to add new node return this; } else { @@ -110,85 +104,130 @@ public class MutableNode extends Node { } } else { // If it does not have key, check for value - Node nodeCandidate = (Node) content[2*selectedHashFragment+1]; - if(nodeCandidate != null) { + Node nodeCandidate = (Node) content[2 * selectedHashFragment + 1]; + if (nodeCandidate != null) { // If it has value, it is a subnode -> upate that - Node newNode = nodeCandidate.putValue(key, value, hashProvider, defaultValue, newHash(hashProvider, key, hash, depth+1), depth+1); - return updateSubNode(selectedHashFragment,newNode); + Node newNode = nodeCandidate.putValue(key, value, hashProvider, defaultValue, + newHash(hashProvider, key, hash, depth + 1), depth + 1); + return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue)); } else { // If it does not have value, put it in the empty place - if(value == defaultValue) { + if (value == defaultValue) { // dont need to add new key-value pair return this; } else { return addEntry(key, value, selectedHashFragment); } - + } } } private Node addEntry(KEY key, VALUE value, int selectedHashFragment) { - content[2*selectedHashFragment] = key; - content[2*selectedHashFragment+1] = value; + content[2 * selectedHashFragment] = key; + content[2 * selectedHashFragment + 1] = value; updateHash(); return this; } + /** * Updates an entry in a selected hash-fragment to a non-default value. + * * @param value * @param selectedHashFragment * @return */ Node updateValue(VALUE value, int selectedHashFragment) { - content[2*selectedHashFragment+1] = value; + content[2 * selectedHashFragment + 1] = value; updateHash(); return this; } - + /** * * @param selectedHashFragment * @param newNode * @return */ - Node updateSubNode(int selectedHashFragment, Node newNode) { - content[2*selectedHashFragment+1] = newNode; - for(int i = 0; i updateWithSubNode(int selectedHashFragment, Node newNode, boolean deletionHappened) { + if (deletionHappened) { + if (newNode == null) { + // Check whether this node become empty + content[2 * selectedHashFragment + 1] = null; // i.e. the new node + if (hasContent()) { + updateHash(); + return this; + } else { + return null; + } + } else { + // check whether newNode is orphan; + MutableNode immutableNewNode = newNode.isMutable(); + if (immutableNewNode != null) { + int orphaned = immutableNewNode.isOrphaned(); + if (orphaned >= 0) { + // orphan subnode data is replaced with data + content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2]; + content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1]; + updateHash(); + return this; + } + } + } + } + // normal behaviour + content[2 * selectedHashFragment + 1] = newNode; + updateHash(); + return this; + + } + + private boolean hasContent() { + for (Object element : this.content) { + if (element != null) + return true; + } + return false; + } + + @Override + protected MutableNode isMutable() { + return this; + } + + protected int isOrphaned() { + int dataFound = -2; + for (int i = 0; i < factor; i++) { + if (content[i * 2] != null) { + if (dataFound >= 0) { + return -1; + } else { + dataFound = i; + } + } else if (content[i * 2 + 1] != null) { + return -3; } } - return null; + return dataFound; } - + @SuppressWarnings("unchecked") - private Node moveDownAndSplit( - ContinousHashProvider hashProvider, - KEY newKey, VALUE newValue, KEY previousKey, - int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) - { - VALUE previousValue = (VALUE) content[2*selectedHashFragmentOfCurrentDepth+1]; - - //final int newHash = newHash(hashProvider, newKey, hashOfNewKey, newDepth); - MutableNode newSubNode = newNodeWithTwoEntries( - hashProvider, - previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)), - newKey, newValue, hashOfNewKey, - depth+1); - - content[2*selectedHashFragmentOfCurrentDepth] = null; - content[2*selectedHashFragmentOfCurrentDepth+1] = newSubNode; + private Node moveDownAndSplit(ContinousHashProvider hashProvider, KEY newKey, + VALUE newValue, KEY previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) { + VALUE previousValue = (VALUE) content[2 * selectedHashFragmentOfCurrentDepth + 1]; + + // final int newHash = newHash(hashProvider, newKey, hashOfNewKey, newDepth); + MutableNode newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, + hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, depth + 1); + + content[2 * selectedHashFragmentOfCurrentDepth] = null; + content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode; updateHash(); return this; } - private MutableNode newNodeWithTwoEntries( - ContinousHashProvider hashProvider, - KEY key1, VALUE value1, int oldHash1, - KEY key2, VALUE value2, int oldHash2, - int newdepth) - { + + private MutableNode newNodeWithTwoEntries(ContinousHashProvider hashProvider, KEY key1, + VALUE value1, int oldHash1, KEY key2, VALUE value2, int oldHash2, int newdepth) { // final int depthLimit = 4000; // if(newdepth>depthLimit) { // final int newHashes = 4000/numberOfFactors; @@ -199,101 +238,97 @@ public class MutableNode extends Node { int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth); int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth)); int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth)); - - MutableNode subNode = new MutableNode(); - if(newFragment1 != newFragment2) { - subNode.content[newFragment1*2]=key1; - subNode.content[newFragment1*2+1]=value1; - - subNode.content[newFragment2*2]=key2; - subNode.content[newFragment2*2+1]=value2; + + MutableNode subNode = new MutableNode(); + if (newFragment1 != newFragment2) { + subNode.content[newFragment1 * 2] = key1; + subNode.content[newFragment1 * 2 + 1] = value1; + + subNode.content[newFragment2 * 2] = key2; + subNode.content[newFragment2 * 2 + 1] = value2; } else { - MutableNode subSubNode = newNodeWithTwoEntries( - hashProvider, - key1, value1, newHash1, - key2, value2, newHash2, - newdepth+1); - subNode.content[newFragment1*2+1] = subSubNode; + MutableNode subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, + value2, newHash2, newdepth + 1); + subNode.content[newFragment1 * 2 + 1] = subSubNode; } subNode.updateHash(); return subNode; } - + Node removeEntry(int selectedHashFragment) { - content[2*selectedHashFragment] = null; - content[2*selectedHashFragment+1] = null; - if(hasContent()) { + content[2 * selectedHashFragment] = null; + content[2 * selectedHashFragment + 1] = null; + if (hasContent()) { updateHash(); return this; } else { return null; } } - + @SuppressWarnings("unchecked") @Override public long getSize() { int size = 0; - for(int i=0; i nodeCandidate = (Node) content[i*2+1]; - if(nodeCandidate!=null) { - size+=nodeCandidate.getSize(); - } + } else { + Node nodeCandidate = (Node) content[i * 2 + 1]; + if (nodeCandidate != null) { + size += nodeCandidate.getSize(); + } } } return size; } @Override - protected MutableNode toMutable() { + protected MutableNode toMutable() { return this; } - + @Override public ImmutableNode toImmutable(Map, ImmutableNode> cache) { - return ImmutableNode.constructImmutable(this,cache); + return ImmutableNode.constructImmutable(this, cache); } - + @SuppressWarnings("unchecked") @Override boolean moveToNext(MapCursor cursor) { // 1. try to move to data - if(cursor.dataIndex != MapCursor.IndexFinish) { - for(int index = cursor.dataIndex+1; index < factor; index++) { - if(this.content[index*2]!=null) { + if (cursor.dataIndex != MapCursor.IndexFinish) { + for (int index = cursor.dataIndex + 1; index < factor; index++) { + if (this.content[index * 2] != null) { // 1.1 found next data cursor.dataIndex = index; - cursor.key = (KEY) this.content[index*2]; - cursor.value = (VALUE) this.content[index*2+1]; + cursor.key = (KEY) this.content[index * 2]; + cursor.value = (VALUE) this.content[index * 2 + 1]; return true; } } cursor.dataIndex = MapCursor.IndexFinish; } - + // 2. look inside the subnodes - for(int index = cursor.nodeIndexStack.peek()+1; index < factor; index++) { - if(this.content[index*2]==null && this.content[index*2+1] !=null) { + for (int index = cursor.nodeIndexStack.peek() + 1; index < factor; index++) { + if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) { // 2.1 found next subnode, move down to the subnode - Node subnode = (Node) this.content[index*2+1]; - + Node subnode = (Node) this.content[index * 2 + 1]; + cursor.dataIndex = MapCursor.IndexStart; cursor.nodeIndexStack.pop(); cursor.nodeIndexStack.push(index); cursor.nodeIndexStack.push(MapCursor.IndexStart); cursor.nodeStack.push(subnode); - - + return subnode.moveToNext(cursor); } } // 3. no subnode found, move up cursor.nodeStack.pop(); cursor.nodeIndexStack.pop(); - if(!cursor.nodeStack.isEmpty()) { + if (!cursor.nodeStack.isEmpty()) { Node supernode = cursor.nodeStack.peek(); return supernode.moveToNext(cursor); } else { @@ -302,89 +337,98 @@ public class MutableNode extends Node { return false; } } - + @Override public void prettyPrint(StringBuilder builder, int depth, int code) { - for(int i = 0; i=0) { + if (code >= 0) { builder.append(code); builder.append(":"); } builder.append("Mutable("); // print content boolean hadContent = false; - for(int i = 0; i["); - builder.append(content[2*i+1].toString()); + builder.append(content[2 * i + 1].toString()); builder.append("]"); hadContent = true; } } builder.append(")"); // print subnodes - for(int i = 0; i subNode = (Node) content[2*i+1]; + Node subNode = (Node) content[2 * i + 1]; builder.append("\n"); - subNode.prettyPrint(builder, depth+1, i); + subNode.prettyPrint(builder, depth + 1, i); } } } - @SuppressWarnings({"unchecked"}) + + @SuppressWarnings({ "unchecked" }) @Override public void checkIntegrity(ContinousHashProvider hashProvider, VALUE defaultValue, int depth) { - for(int i = 0; i0) { + int orphaned = isOrphaned(); + if(orphaned>=0) { + throw new IllegalStateException("Orphaned node! " + orphaned + ": " + content[2 * orphaned]); + } + } + // check the place of data + for (int i = 0; i < factor; i++) { + if (this.content[2 * i] != null) { + KEY key = (KEY) this.content[2 * i]; + VALUE value = (VALUE) this.content[2 * i + 1]; + + if (value == defaultValue) { 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); + if (i != selectedHashFragment) { + throw new IllegalStateException("Key " + key + " with hash code " + hashCode + + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i); } } } - for(int i = 0; i subNode = (Node) this.content[2*i+1]; - subNode.checkIntegrity(hashProvider, defaultValue, depth+1); + // check subnodes + for (int i = 0; i < factor; i++) { + if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { + Node subNode = (Node) this.content[2 * i + 1]; + subNode.checkIntegrity(hashProvider, defaultValue, depth + 1); } } + // 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 (oldHash != newHash) { + throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")"); } } - - + protected void updateHash() { this.cachedHash = Arrays.hashCode(content); } - + @Override public int hashCode() { return this.cachedHash; } - - + @Override public boolean equals(Object obj) { if (this == obj) @@ -392,10 +436,10 @@ public class MutableNode extends Node { if (obj == null) return false; if (obj instanceof MutableNode) { - MutableNode other = (MutableNode) obj; + MutableNode other = (MutableNode) obj; return Arrays.deepEquals(this.content, other.content); - } else if(obj instanceof ImmutableNode) { - ImmutableNode other = (ImmutableNode) obj; + } else if (obj instanceof ImmutableNode) { + ImmutableNode other = (ImmutableNode) obj; return ImmutableNode.compareImmutableMutable(other, this); } else { return false; diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java index f19ca06f..2176af87 100644 --- a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java @@ -5,8 +5,8 @@ import java.util.Map; import org.eclipse.viatra.solver.data.map.ContinousHashProvider; public abstract class Node{ - protected static final int branchingFactorBit = 5; - protected static final int factor = 1<{ * @return The segment as an integer. */ protected static int hashFragment(int hash, int shiftDepth) { - if(shiftDepth<0 && 5