From a155f6ba02e08a75ce6e474a86900b8363f506e8 Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Wed, 29 Sep 2021 02:45:57 +0200 Subject: build: migration to Gradle 7 --- .../solver/data/map/internal/ImmutableNode.java | 379 +++++++++++++++++ .../viatra/solver/data/map/internal/MapCursor.java | 131 ++++++ .../solver/data/map/internal/MapDiffCursor.java | 214 ++++++++++ .../solver/data/map/internal/MutableNode.java | 449 +++++++++++++++++++++ .../viatra/solver/data/map/internal/Node.java | 85 ++++ .../solver/data/map/internal/OldValueBox.java | 19 + .../solver/data/map/internal/VersionedMapImpl.java | 171 ++++++++ 7 files changed, 1448 insertions(+) create mode 100644 store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java create mode 100644 store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java create mode 100644 store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java create mode 100644 store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java create mode 100644 store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java create mode 100644 store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java create mode 100644 store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java (limited to 'store/src/main/java/org/eclipse/viatra/solver/data/map/internal') diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java new file mode 100644 index 00000000..04a9b19a --- /dev/null +++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java @@ -0,0 +1,379 @@ +package org.eclipse.viatra.solver.data.map.internal; + +import java.util.Arrays; +import java.util.Map; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; + +public class ImmutableNode extends Node { + /** + * Bitmap defining the stored key and values. + */ + final int dataMap; + /** + * Bitmap defining the positions of further nodes. + */ + final int nodeMap; + /** + * Stores Keys, Values, and subnodes. Structure: (K,V)*,NODE; NODES are stored backwards. + */ + final Object[] content; + + /** + * Hash code derived from immutable hash code + */ + final int precalculatedHash; + + private ImmutableNode(int dataMap, int nodeMap, Object[] content, int precalculatedHash) { + super(); + this.dataMap = dataMap; + this.nodeMap = nodeMap; + this.content = content; + this.precalculatedHash = precalculatedHash; + } + + /** + * Constructor that copies a mutable node to an immutable. + * + * @param node A mutable node. + * @param cache A cache of existing immutable nodes. It can be used to search + * and place reference immutable nodes. It can be null, if no cache + * available. + * @return an immutable version of the input node. + */ + @SuppressWarnings("unchecked") + static ImmutableNode constructImmutable(MutableNode node, Map, ImmutableNode> cache) { + // 1. try to return from cache + if(cache != null) { + ImmutableNode cachedResult = cache.get(node); + if(cachedResult != null) { + // 1.1 Already cached, return from cache. + return cachedResult; + } + } + + // 2. otherwise construct a new ImmutableNode + int size = 0; + for(int i = 0; i subnode = (Node) node.content[i*2+1]; + if(subnode != null) { + ImmutableNode immutableSubnode = subnode.toImmutable(cache); + resultNodeMap |=bitposition; + resultContent[size-1-nodes] = immutableSubnode; + nodes++; + } + } + bitposition<<=1; + } + final int resultHash = node.hashCode(); + ImmutableNode newImmutable = new ImmutableNode<>(resultDataMap, resultNodeMap, resultContent, resultHash); + + // 3. save new immutable. + if(cache != null) { + cache.put(newImmutable, newImmutable); + } + return newImmutable; + } + + private int index(int bitmap, int bitpos) { + return Integer.bitCount(bitmap & (bitpos-1)); + } + + @SuppressWarnings("unchecked") + @Override + public V getValue(K key, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth) { + int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); + int bitposition = 1 << selectedHashFragment; + // If the key is stored as a data + if((dataMap & bitposition) != 0) { + int keyIndex = 2*index(dataMap, bitposition); + K keyCandidate = (K) content[keyIndex]; + if(keyCandidate.equals(key)) { + return (V) content[keyIndex+1]; + } else { + return defaultValue; + } + } + // the key is stored as a node + else if((nodeMap & bitposition) != 0) { + int keyIndex = content.length-1-index(nodeMap, bitposition); + ImmutableNode subNode = (ImmutableNode) content[keyIndex]; + int newDepth = depth+1; + int newHash = newHash(hashProvider, key, hash, newDepth); + return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); + } + // the key is not stored at all + else { + return defaultValue; + } + } + + @SuppressWarnings("unchecked") + @Override + 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); + K keyCandidate = (K) content[keyIndex]; + if(keyCandidate.equals(key)) { + if(value == defaultValue) { + // delete + MutableNode mutable = this.toMutable(); + return mutable.removeEntry(selectedHashFragment,oldValue); + } else if(value == content[keyIndex+1]) { + // dont change + oldValue.setOldValue(value); + return this; + } else { + // update existing value + MutableNode mutable = this.toMutable(); + return mutable.updateValue(value, oldValue, selectedHashFragment); + } + } else { + if(value == defaultValue) { + // dont change + oldValue.setOldValue(defaultValue); + return this; + } else { + // 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); + ImmutableNode subNode = (ImmutableNode) content[keyIndex]; + int newDepth = depth+1; + int newHash = newHash(hashProvider, key, hash, newDepth); + Node newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth); + + if(subNode == newsubNode) { + // nothing changed + return this; + } else { + MutableNode mutable = toMutable(); + return mutable.updateWithSubNode(selectedHashFragment, newsubNode, value.equals(defaultValue)); + } + } else { + // add new key + value + MutableNode mutable = this.toMutable(); + return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth); + } + } + + + @SuppressWarnings("unchecked") + @Override + public long getSize() { + int result = Integer.bitCount(this.dataMap); + for(int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) { + ImmutableNode subnode = + (ImmutableNode) this.content[this.content.length-1-subnodeIndex]; + result += subnode.getSize(); + } + return result; + } + + @Override + protected MutableNode toMutable() { + return new MutableNode<>(this); + } + + @Override + public ImmutableNode toImmutable( + Map, ImmutableNode> cache) { + return this; + } + + @Override + protected MutableNode isMutable() { + return null; + } + + @SuppressWarnings("unchecked") + @Override + boolean moveToNext(MapCursor cursor) { + // 1. try to move to data + int datas = Integer.bitCount(this.dataMap); + if(cursor.dataIndex != MapCursor.INDEX_FINISH) { + int newDataIndex = cursor.dataIndex + 1; + if(newDataIndex < datas) { + cursor.dataIndex = newDataIndex; + cursor.key = (K) this.content[newDataIndex*2]; + cursor.value = (V) this.content[newDataIndex*2+1]; + return true; + } else { + cursor.dataIndex = MapCursor.INDEX_FINISH; + } + } + + // 2. look inside the subnodes + int nodes = Integer.bitCount(this.nodeMap); + int newNodeIndex = cursor.nodeIndexStack.peek() + 1; + if(newNodeIndex < nodes) { + // 2.1 found next subnode, move down to the subnode + Node subnode = (Node) this.content[this.content.length-1-newNodeIndex]; + cursor.dataIndex = MapCursor.INDEX_START; + cursor.nodeIndexStack.pop(); + cursor.nodeIndexStack.push(newNodeIndex); + cursor.nodeIndexStack.push(MapCursor.INDEX_START); + cursor.nodeStack.push(subnode); + return subnode.moveToNext(cursor); + } else { + // 3. no subnode found, move up + cursor.nodeStack.pop(); + cursor.nodeIndexStack.pop(); + if(!cursor.nodeStack.isEmpty()) { + Node supernode = cursor.nodeStack.peek(); + return supernode.moveToNext(cursor); + } else { + cursor.key = null; + cursor.value = null; + return false; + } + } + } + + @Override + public void prettyPrint(StringBuilder builder, int depth, int code) { + for(int i = 0; i=0) { + builder.append(code); + builder.append(":"); + } + builder.append("Immutable("); + boolean hadContent = false; + int dataMask = 1; + for(int i = 0; i["); + builder.append(content[2*index(dataMap, dataMask)+1].toString()); + builder.append("]"); + hadContent = true; + } + dataMask<<=1; + } + builder.append(")"); + int nodeMask = 1; + for(int i = 0; i subNode = (Node) content[content.length-1-index(nodeMap, nodeMask)]; + builder.append("\n"); + subNode.prettyPrint(builder, depth+1, i); + } + nodeMask<<=1; + } + } + + @SuppressWarnings("unchecked") + @Override + public void checkIntegrity(ContinousHashProvider hashProvider, V 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; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) + return true; + if (obj == null) + return false; + if (obj instanceof ImmutableNode) { + ImmutableNode other = (ImmutableNode) obj; + if (precalculatedHash != other.precalculatedHash || dataMap != other.dataMap || nodeMap != other.nodeMap || !Arrays.deepEquals(content, other.content)) + return false; + else return true; + } else if(obj instanceof MutableNode) { + return ImmutableNode.compareImmutableMutable(this, (MutableNode) obj); + } else { + return false; + } + } + public static boolean compareImmutableMutable( + ImmutableNode immutable, + MutableNode mutable) + { + int datas = 0; + int nodes = 0; + final int immutableLength = immutable.content.length; + for(int i = 0; i mutableSubnode = (Node) mutable.content[i*2+1]; + if(mutableSubnode != null) { + if(datas*2+nodes+1 <= immutableLength) { + Object immutableSubnode = immutable.content[immutableLength-1-nodes]; + if(!mutableSubnode.equals(immutableSubnode)) { + return false; + } + nodes++; + } else { + return false; + } + } + } + } + return true; + } +} diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java new file mode 100644 index 00000000..cc5a3982 --- /dev/null +++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java @@ -0,0 +1,131 @@ +package org.eclipse.viatra.solver.data.map.internal; + +import java.util.ArrayDeque; +import java.util.ConcurrentModificationException; +import java.util.Iterator; +import java.util.List; + +import org.eclipse.viatra.solver.data.map.Cursor; +import org.eclipse.viatra.solver.data.map.VersionedMap; + +public class MapCursor implements Cursor { + // Constants + static final int INDEX_START = -1; + static final int INDEX_FINISH = -2; + + // Tree stack + ArrayDeque> nodeStack; + ArrayDeque nodeIndexStack; + int dataIndex; + + // Values + K key; + V value; + + // Hash code for checking concurrent modifications + final VersionedMap map; + final int creationHash; + + public MapCursor(Node root, VersionedMap map) { + // Initializing tree stack + super(); + this.nodeStack = new ArrayDeque<>(); + this.nodeIndexStack = new ArrayDeque<>(); + if(root != null) { + this.nodeStack.add(root); + this.nodeIndexStack.push(INDEX_START); + } + + this.dataIndex = INDEX_START; + + // Initializing cache + this.key = null; + this.value = null; + + // Initializing state + this.map=map; + this.creationHash = map.hashCode(); + } + + public K getKey() { + return key; + } + + public V getValue() { + return value; + } + + public boolean isTerminated() { + return this.nodeStack.isEmpty(); + } + + public boolean move() { + if(isDirty()) { + throw new ConcurrentModificationException(); + } + if(!isTerminated()) { + boolean result = this.nodeStack.peek().moveToNext(this); + if(this.nodeIndexStack.size() != this.nodeStack.size()) { + throw new IllegalArgumentException("Node stack is corrupted by illegal moves!"); + } + return result; + } + return false; + } + public boolean skipCurrentNode() { + nodeStack.pop(); + nodeIndexStack.pop(); + dataIndex = INDEX_FINISH; + return move(); + } + @Override + public boolean isDirty() { + return this.map.hashCode() != this.creationHash; + } + @Override + public List> getDependingMaps() { + return List.of(this.map); + } + + public static boolean sameSubnode(MapCursor cursor1, MapCursor cursor2) { + Node nodeOfCursor1 = cursor1.nodeStack.peek(); + Node nodeOfCursor2 = cursor2.nodeStack.peek(); + if(nodeOfCursor1 != null && nodeOfCursor2 != null) { + return nodeOfCursor1.equals(nodeOfCursor2); + } else { + return false; + } + } + + /** + * + * @param + * @param + * @param cursor1 + * @param cursor2 + * @return Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the same position. + */ + public static int compare(MapCursor cursor1, MapCursor cursor2) { + // two cursors are equally deep + Iterator stack1 = cursor1.nodeIndexStack.descendingIterator(); + Iterator stack2 = cursor2.nodeIndexStack.descendingIterator(); + if(stack1.hasNext()) { + if(!stack2.hasNext()) { + // stack 2 has no more element, thus stack 1 is deeper + return 1; + } + int val1 = stack1.next(); + int val2 = stack2.next(); + if(val1 < val2) { + return -1; + } else if(val2 < val1) { + return 1; + } + } + if(stack2.hasNext()) { + // stack 2 has more element, thus stack 2 is deeper + return 1; + } + return Integer.compare(cursor1.dataIndex, cursor2.dataIndex); + } +} diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java new file mode 100644 index 00000000..e97e4aa1 --- /dev/null +++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java @@ -0,0 +1,214 @@ +package org.eclipse.viatra.solver.data.map.internal; + +import java.util.List; +import java.util.stream.Collectors; +import java.util.stream.Stream; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; +import org.eclipse.viatra.solver.data.map.Cursor; +import org.eclipse.viatra.solver.data.map.DiffCursor; +import org.eclipse.viatra.solver.data.map.VersionedMap; + +/** + * A cursor representing the difference between two states of a map. + * @author Oszkar Semerath + * + */ +public class MapDiffCursor implements DiffCursor, Cursor{ + /** + * Default value representing missing elements. + */ + private V defaultValue; + private MapCursor cursor1; + private MapCursor cursor2; + private ContinousHashProvider hashProvider; + + // Values + private K key; + private V fromValue; + private V toValue; + + // State + /** + * Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the same position. + */ + private int cursorRelation; + /** + * Denotes a state when two cursors are in the same position, but they contain different keys. + * Possible values: + *
    + *
  • 0: not stuck
    • + *
  • 1: hashClash, next it should return the key of cursor 1.
    • + *
  • 2: hashClash, next it should return the key of cursor 2.
    • + *
+ */ + private int hashClash=0; + + public MapDiffCursor(ContinousHashProvider hashProvider, V defaultValue, Cursor cursor1, Cursor cursor2) { + super(); + this.hashProvider = hashProvider; + this.defaultValue = defaultValue; + this.cursor1 = (MapCursor) cursor1; + this.cursor2 = (MapCursor) cursor2; + } + @Override + public K getKey() { + return key; + } + @Override + public V getFromValue() { + return fromValue; + } + @Override + public V getToValue() { + return toValue; + } + @Override + public V getValue() { + return getToValue(); + } + public boolean isTerminated() { + return cursor1.isTerminated() && cursor2.isTerminated(); + } + @Override + public boolean isDirty() { + return this.cursor1.isDirty() || this.cursor2.isDirty(); + } + @Override + public List> getDependingMaps() { + return Stream.concat( + cursor1.getDependingMaps().stream(), + cursor2.getDependingMaps().stream() + ).collect(Collectors.toList()); + } + + protected void updateState() { + if(!isTerminated()) { + this.cursorRelation = MapCursor.compare(cursor1, cursor2); + if(cursorRelation > 0 || cursor2.isTerminated()) { + this.key = cursor1.getKey(); + this.fromValue = cursor1.getValue(); + this.toValue = defaultValue; + } else if(cursorRelation < 0 || cursor1.isTerminated()){ + this.key = cursor2.getKey(); + this.fromValue = defaultValue; + this.toValue = cursor1.getValue(); + } else { + // cursor1 = cursor2 + if(cursor1.getKey().equals(cursor2.getKey())) { + this.key = cursor1.getKey(); + this.fromValue = cursor1.getValue(); + this.toValue = defaultValue; + } else { + resolveHashClash1(); + } + } + } + } + protected void resolveHashClash1() { + int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key); + if(compareResult<0) { + this.hashClash = 2; + this.cursorRelation = 0; + this.key = cursor1.key; + this.fromValue = cursor1.value; + this.toValue = defaultValue; + } else if(compareResult>0) { + this.hashClash = 1; + this.cursorRelation = 0; + this.key = cursor2.key; + this.fromValue = defaultValue; + this.toValue = cursor2.value; + } else { + throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); + } + } + protected boolean isInHashClash() { + return this.hashClash != 0; + } + protected void resolveHashClash2() { + if(hashClash == 1) { + this.hashClash = 0; + this.cursorRelation = 0; + this.key = cursor1.key; + this.fromValue = cursor1.value; + this.toValue = defaultValue; + } else if(hashClash == 2) { + this.hashClash = 0; + this.cursorRelation = 0; + this.key = cursor2.key; + this.fromValue = defaultValue; + this.toValue = cursor2.value; + } else throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); + } + + + protected boolean sameValues() { + if(this.fromValue == null) { + return this.toValue == null; + } else { + return this.fromValue.equals(this.toValue); + } + } + protected boolean moveOne() { + if(isTerminated()) { + return false; + } + if(this.cursorRelation > 0 || cursor2.isTerminated()) { + return cursor1.move(); + } else if(this.cursorRelation < 0 || cursor1.isTerminated()) { + return cursor2.move(); + } else { + boolean moved1 = cursor1.move(); + boolean moved2 = cursor2.move(); + return moved1 && moved2; + } + } + private boolean skipNode() { + if(isTerminated()) { + throw new IllegalStateException("DiffCursor tries to skip when terminated!"); + } + boolean update1 = cursor1.skipCurrentNode(); + boolean update2 = cursor2.skipCurrentNode(); + updateState(); + return update1 && update2; + } + + protected boolean moveToConsistentState() { + if(!isTerminated()) { + boolean changed; + boolean lastResult = true; + do { + changed = false; + if(MapCursor.sameSubnode(cursor1, cursor2)) { + lastResult = skipNode(); + changed = true; + } + if(sameValues()) { + lastResult = moveOne(); + changed = true; + } + updateState(); + } while(changed && !isTerminated()); + return lastResult; + } else { + return false; + } + } + + public boolean move() { + if(!isTerminated()) { + if(isInHashClash()) { + this.resolveHashClash2(); + return true; + } else { + if(moveOne()) { + return moveToConsistentState(); + } else { + return false; + } + } + + } else return false; + } +} diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java new file mode 100644 index 00000000..9e63b941 --- /dev/null +++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java @@ -0,0 +1,449 @@ +package org.eclipse.viatra.solver.data.map.internal; + +import java.util.Arrays; +import java.util.Map; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; + +public class MutableNode extends Node { + int cachedHash; + protected Object[] content; + + protected MutableNode() { + this.content = new Object[2 * FACTOR]; + updateHash(); + } + + public static MutableNode initialize(K key, V value, ContinousHashProvider hashProvider, + V 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.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 < 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]; + dataUsed++; + } 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 V getValue(K key, ContinousHashProvider hashProvider, V defaultValue, int hash, int depth) { + int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); + K keyCandidate = (K) this.content[2 * selectedHashFragment]; + if (keyCandidate != null) { + if (keyCandidate.equals(key)) { + return (V) this.content[2 * selectedHashFragment + 1]; + } else { + return defaultValue; + } + } else { + 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 { + return defaultValue; + } + } + } + + @SuppressWarnings("unchecked") + @Override + public Node putValue(K key, V value, OldValueBox oldValue, ContinousHashProvider hashProvider, V defaultValue, int hash, + int depth) { + int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); + K keyCandidate = (K) content[2 * selectedHashFragment]; + if (keyCandidate != null) { + // If has key + if (keyCandidate.equals(key)) { + // The key is equals to an existing key -> update entry + if (value == defaultValue) { + return removeEntry(selectedHashFragment, oldValue); + } else { + return updateValue(value, oldValue, 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) { + // Value is default -> do not need to add new node + oldValue.setOldValue(defaultValue); + return this; + } else { + // Value is not default -> Split entry data to a new node + oldValue.setOldValue(defaultValue); + return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment); + } + } + } else { + // If it does not have key, check for value + 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, oldValue, 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) { + // dont need to add new key-value pair + oldValue.setOldValue(defaultValue); + return this; + } else { + return addEntry(key, value, oldValue, selectedHashFragment); + } + + } + } + } + + @SuppressWarnings("unchecked") + private Node addEntry(K key, V value, OldValueBox oldValue, int selectedHashFragment) { + content[2 * selectedHashFragment] = key; + oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); + 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 + */ + @SuppressWarnings("unchecked") + Node updateValue(V value, OldValueBox oldValue, int selectedHashFragment) { + oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); + content[2 * selectedHashFragment + 1] = value; + updateHash(); + return this; + } + + /** + * + * @param selectedHashFragment + * @param newNode + * @return + */ + Node 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 dataFound; + } + + @SuppressWarnings("unchecked") + 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); + + content[2 * selectedHashFragmentOfCurrentDepth] = null; + content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode; + updateHash(); + return this; + } + + 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)); + 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; + } else { + MutableNode subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, + newHash2, newdepth + 1); + subNode.content[newFragment1 * 2 + 1] = subSubNode; + } + subNode.updateHash(); + return subNode; + } + + @SuppressWarnings("unchecked") + Node removeEntry(int selectedHashFragment, OldValueBox oldValue) { + content[2 * selectedHashFragment] = null; + oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]); + 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 < FACTOR; i++) { + if (content[i * 2] != null) { + size++; + } else { + Node nodeCandidate = (Node) content[i * 2 + 1]; + if (nodeCandidate != null) { + size += nodeCandidate.getSize(); + } + } + } + return size; + } + + @Override + protected MutableNode toMutable() { + return this; + } + + @Override + public ImmutableNode toImmutable(Map, ImmutableNode> cache) { + return ImmutableNode.constructImmutable(this, cache); + } + + @SuppressWarnings("unchecked") + @Override + boolean moveToNext(MapCursor cursor) { + // 1. try to move to data + if (cursor.dataIndex != MapCursor.INDEX_FINISH) { + 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 = (K) this.content[index * 2]; + cursor.value = (V) this.content[index * 2 + 1]; + return true; + } + } + cursor.dataIndex = MapCursor.INDEX_FINISH; + } + + // 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) { + // 2.1 found next subnode, move down to the subnode + Node subnode = (Node) this.content[index * 2 + 1]; + + cursor.dataIndex = MapCursor.INDEX_START; + cursor.nodeIndexStack.pop(); + cursor.nodeIndexStack.push(index); + cursor.nodeIndexStack.push(MapCursor.INDEX_START); + cursor.nodeStack.push(subnode); + + return subnode.moveToNext(cursor); + } + } + // 3. no subnode found, move up + cursor.nodeStack.pop(); + cursor.nodeIndexStack.pop(); + if (!cursor.nodeStack.isEmpty()) { + Node supernode = cursor.nodeStack.peek(); + return supernode.moveToNext(cursor); + } else { + cursor.key = null; + cursor.value = null; + return false; + } + } + + @Override + public void prettyPrint(StringBuilder builder, int depth, int code) { + for (int i = 0; i < depth; i++) { + builder.append("\t"); + } + if (code >= 0) { + builder.append(code); + builder.append(":"); + } + builder.append("Mutable("); + // print content + boolean hadContent = false; + for (int i = 0; i < FACTOR; i++) { + if (content[2 * i] != null) { + if (hadContent) { + builder.append(","); + } + builder.append(i); + builder.append(":["); + builder.append(content[2 * i].toString()); + builder.append("]->["); + builder.append(content[2 * i + 1].toString()); + builder.append("]"); + hadContent = true; + } + } + builder.append(")"); + // 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]; + builder.append("\n"); + subNode.prettyPrint(builder, depth + 1, i); + } + } + } + + @SuppressWarnings({ "unchecked" }) + @Override + public void checkIntegrity(ContinousHashProvider hashProvider, V defaultValue, int depth) { + // check for orphan nodes + if (depth > 0) { + 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) { + K key = (K) this.content[2 * i]; + V value = (V) 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); + } + } + } + // 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 + ")"); + } + } + + protected void updateHash() { + this.cachedHash = Arrays.hashCode(content); + } + + @Override + public int hashCode() { + return this.cachedHash; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) + return true; + if (obj == null) + return false; + if (obj instanceof MutableNode) { + MutableNode other = (MutableNode) obj; + return Arrays.deepEquals(this.content, other.content); + } else if (obj instanceof ImmutableNode) { + ImmutableNode other = (ImmutableNode) obj; + return ImmutableNode.compareImmutableMutable(other, this); + } else { + return false; + } + } +} diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java new file mode 100644 index 00000000..d40f980a --- /dev/null +++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java @@ -0,0 +1,85 @@ +package org.eclipse.viatra.solver.data.map.internal; + +import java.util.Map; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; + +public abstract class Node{ + public static final int BRANCHING_FACTOR_BITS = 5; + public static final int FACTOR = 1< 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); + protected abstract MutableNode isMutable(); + /** + * Moves a {@link MapCursor} to its next position. + * @param cursor the cursor + * @return Whether there was a next value to move on. + */ + 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) {} + +} diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java new file mode 100644 index 00000000..23502857 --- /dev/null +++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/OldValueBox.java @@ -0,0 +1,19 @@ +package org.eclipse.viatra.solver.data.map.internal; + +public class OldValueBox{ + V oldValue; + boolean isSet = false; + + public V getOldValue() { + if(!isSet) throw new IllegalStateException(); + isSet = false; + return oldValue; + } + + public void setOldValue(V ouldValue) { + if(isSet) throw new IllegalStateException(); + this.oldValue = ouldValue; + isSet = true; + } + +} diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java new file mode 100644 index 00000000..de41e602 --- /dev/null +++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java @@ -0,0 +1,171 @@ +package org.eclipse.viatra.solver.data.map.internal; + +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; + +import org.eclipse.viatra.solver.data.map.ContinousHashProvider; +import org.eclipse.viatra.solver.data.map.Cursor; +import org.eclipse.viatra.solver.data.map.DiffCursor; +import org.eclipse.viatra.solver.data.map.VersionedMap; +import org.eclipse.viatra.solver.data.map.VersionedMapStoreImpl; + +/** + * Not threadSafe in itself + * @author Oszkar Semerath + * + * @param + * @param + */ +public class VersionedMapImpl implements VersionedMap{ + protected final VersionedMapStoreImpl store; + + protected final ContinousHashProvider hashProvider; + protected final V defaultValue; + protected Node root; + + private OldValueBox oldValueBox = new OldValueBox<>(); + + public VersionedMapImpl( + VersionedMapStoreImpl store, + ContinousHashProvider hashProvider, + V defaultValue) + { + this.store = store; + this.hashProvider = hashProvider; + this.defaultValue = defaultValue; + this.root = null; + } + public VersionedMapImpl( + VersionedMapStoreImpl store, + ContinousHashProvider hashProvider, + V defaultValue, Node data) + { + this.store = store; + this.hashProvider = hashProvider; + this.defaultValue = defaultValue; + this.root = data; + } + + public V getDefaultValue() { + return defaultValue; + } + public ContinousHashProvider getHashProvider() { + return hashProvider; + } + @Override + public V put(K key, V value) { + if(root!=null) { + root = root.putValue(key, value, oldValueBox, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); + return oldValueBox.getOldValue(); + } else { + root = MutableNode.initialize(key, value, hashProvider, defaultValue); + return defaultValue; + } + } + + @Override + public void putAll(Cursor cursor) { + if(cursor.getDependingMaps().contains(this)) { + List keys = new LinkedList<>(); + List values = new LinkedList<>(); + while(cursor.move()) { + keys.add(cursor.getKey()); + values.add(cursor.getValue()); + } + Iterator keyIterator = keys.iterator(); + Iterator valueIterator = values.iterator(); + while(keyIterator.hasNext()) { + this.put(keyIterator.next(), valueIterator.next()); + } + } else { + while(cursor.move()) { + this.put(cursor.getKey(), cursor.getValue()); + } + } + } + + @Override + public V get(K key) { + if(root!=null) { + return root.getValue(key, hashProvider, defaultValue, hashProvider.getHash(key, 0), 0); + } else { + return defaultValue; + } + } + @Override + public long getSize() { + if(root == null) { + return 0; + } else { + return root.getSize(); + } + } + + @Override + public Cursor getAll() { + return new MapCursor<>(this.root,this); + } + @Override + public DiffCursor getDiffCursor(long toVersion) { + Cursor fromCursor = this.getAll(); + VersionedMap toMap = this.store.createMap(toVersion); + Cursor toCursor = toMap.getAll(); + return new MapDiffCursor<>(this.hashProvider,this.defaultValue, fromCursor, toCursor); + + } + + + @Override + public long commit() { + return this.store.commit(root,this); + } + public void setRoot(Node root) { + this.root = root; + } + + @Override + public void restore(long state) { + root = this.store.revert(state); + } + + @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) { + if (other.root != null) + return false; + } else if (!root.equals(other.root)) + return false; + return true; + } + public void prettyPrint() { + StringBuilder s = new StringBuilder(); + if(this.root != null) { + this.root.prettyPrint(s, 0, -1); + System.out.println(s.toString()); + } else { + System.out.println("empty tree"); + } + } + public void checkIntegrity() { + if(this.root != null) { + this.root.checkIntegrity(hashProvider, defaultValue, 0); + } + } + +} -- cgit v1.2.3-54-g00ecf