--- /dev/null
+package org.simantics.datatypes.utils;\r
+\r
+import java.io.ByteArrayInputStream;\r
+import java.io.DataInput;\r
+import java.io.DataOutput;\r
+import java.io.IOException;\r
+import java.util.ArrayList;\r
+import java.util.Collection;\r
+import java.util.HashMap;\r
+import java.util.IdentityHashMap;\r
+import java.util.List;\r
+import java.util.Map;\r
+import java.util.Set;\r
+\r
+import org.simantics.databoard.Bindings;\r
+import org.simantics.databoard.accessor.reference.ChildReference;\r
+import org.simantics.databoard.binding.Binding;\r
+import org.simantics.databoard.binding.error.BindingException;\r
+import org.simantics.databoard.binding.error.RuntimeBindingConstructionException;\r
+import org.simantics.databoard.binding.impl.BindingPrintContext;\r
+import org.simantics.databoard.binding.mutable.Variant;\r
+import org.simantics.databoard.serialization.RuntimeSerializerConstructionException;\r
+import org.simantics.databoard.serialization.Serializer;\r
+import org.simantics.databoard.util.IdentityPair;\r
+import org.simantics.datatypes.DatatypeResource;\r
+import org.simantics.db.ReadGraph;\r
+import org.simantics.db.Resource;\r
+import org.simantics.db.WriteGraph;\r
+import org.simantics.db.common.primitiverequest.RelatedValue;\r
+import org.simantics.db.common.procedure.adapter.TransientCacheListener;\r
+import org.simantics.db.common.utils.Logger;\r
+import org.simantics.db.exception.DatabaseException;\r
+import org.simantics.db.service.Bytes;\r
+import org.simantics.db.service.SerialisationSupport;\r
+import org.simantics.db.service.XSupport;\r
+import org.simantics.layer0.Layer0;\r
+import org.simantics.scl.runtime.tuple.Tuple2;\r
+import org.simantics.utils.datastructures.Pair;\r
+\r
+import gnu.trove.list.array.TByteArrayList;\r
+import gnu.trove.map.hash.TObjectIntHashMap;\r
+\r
+/*\r
+ * Implementation from http://www.geeksforgeeks.org/b-tree-set-3delete/\r
+ * \r
+ */\r
+\r
+interface BTreeContentManager {\r
+ \r
+ BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException;\r
+ void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException;\r
+ \r
+}\r
+\r
+class PossibleVariantInputStream extends ByteArrayInputStream {\r
+ \r
+ PossibleVariantInputStream(byte[] data, int offset) {\r
+ super(data, offset, data.length-offset);\r
+ }\r
+ \r
+ public int getOffset() {\r
+ return pos;\r
+ }\r
+ \r
+}\r
+\r
+class BTreeContentBinding extends Binding {\r
+\r
+ private final SerialisationSupport ss;\r
+ private final XSupport xs;\r
+ \r
+ public BTreeContentBinding(SerialisationSupport ss, XSupport xs) {\r
+ this.ss = ss;\r
+ this.xs = xs;\r
+ }\r
+ \r
+ private final Serializer serializer = new Serializer() {\r
+\r
+ @Override\r
+ public void serialize(DataOutput out, TObjectIntHashMap<Object> identities, Object obj) throws IOException {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public void serialize(DataOutput out, Object obj) throws IOException {\r
+ byte[] data = serialize(obj);\r
+ out.write(data);\r
+ }\r
+\r
+ @Override\r
+ public Object deserialize(DataInput in, List<Object> identities)\r
+ throws IOException {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public Object deserialize(DataInput in) throws IOException {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public void deserializeTo(DataInput in, List<Object> identities,\r
+ Object dst) throws IOException {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public void deserializeTo(DataInput in, Object dst) throws IOException {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public void skip(DataInput in, List<Object> identities)\r
+ throws IOException {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public void skip(DataInput in) throws IOException {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public Integer getConstantSize() {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public int getSize(Object obj, TObjectIntHashMap<Object> identities)\r
+ throws IOException {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public int getSize(Object obj) throws IOException {\r
+ return serialize(obj).length;\r
+ }\r
+\r
+ @Override\r
+ public int getMinSize() {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+ \r
+ private void addBE(TByteArrayList bytes, int value) {\r
+ \r
+ bytes.add((byte) ((value >>> 24) & 0xFF));\r
+ bytes.add((byte) ((value >>> 16) & 0xFF));\r
+ bytes.add((byte) ((value >>> 8) & 0xFF));\r
+ bytes.add( (byte) (value & 0xFF));\r
+\r
+ }\r
+ \r
+ private void addBE(TByteArrayList bytes, long value) {\r
+ \r
+ bytes.add((byte) ((value >>> 56) & 0xFF));\r
+ bytes.add((byte) ((value >>> 48) & 0xFF));\r
+ bytes.add((byte) ((value >>> 40) & 0xFF));\r
+ bytes.add((byte) ((value >>> 32) & 0xFF));\r
+ bytes.add((byte) ((value >>> 24) & 0xFF));\r
+ bytes.add((byte) ((value >>> 16) & 0xFF));\r
+ bytes.add((byte) ((value >>> 8) & 0xFF));\r
+ bytes.add( (byte) (value & 0xFF));\r
+\r
+ }\r
+\r
+ public byte[] serialize(Object obj) throws IOException {\r
+ BTreeContentBean bean = (BTreeContentBean)obj;\r
+ TByteArrayList bytes = new TByteArrayList();\r
+ bytes.add(bean.leaf ? (byte)1 : (byte)0);\r
+ addBE(bytes, bean.n);\r
+ //addLE(bytes, (bean.key.length+1)/2);\r
+ Binding pbv = PossibleVariant.BINDING;\r
+ Serializer pbs = pbv.serializer();\r
+ addBE(bytes, bean.key.length);\r
+ for(PossibleVariant l : bean.key) {\r
+ byte[] ser = pbs.serialize(l);\r
+ bytes.add(ser);\r
+ }\r
+ addBE(bytes, bean.value.length);\r
+ for(PossibleResource pr : bean.value) {\r
+ if(pr.r != null) {\r
+ bytes.add((byte)1);\r
+ addBE(bytes, xs.convertDelayedResourceToResource(pr.r).getResourceId());\r
+ } else {\r
+ bytes.add((byte)0);\r
+ }\r
+ }\r
+ addBE(bytes, bean.c.length);\r
+ for(PossibleResource pr : bean.c) {\r
+ if(pr.r != null) {\r
+ bytes.add((byte)1);\r
+ addBE(bytes, xs.convertDelayedResourceToResource(pr.r).getResourceId());\r
+ } else {\r
+ bytes.add((byte)0);\r
+ }\r
+ }\r
+ return bytes.toArray();\r
+ }\r
+ \r
+ int readBE4(byte[] bytes, int byteIndex) {\r
+ int result = (int) \r
+ (((int)(bytes[byteIndex++] & 0xff))<<24) |\r
+ (((int)(bytes[byteIndex++] & 0xff))<<16) | \r
+ (((int)(bytes[byteIndex++] & 0xff))<<8) | \r
+ (((int)(bytes[byteIndex++] & 0xff)));\r
+ return result;\r
+ }\r
+ \r
+ long readBE8(byte[] bytes, int byteIndex) {\r
+ long result = (long) \r
+ (((long)(bytes[byteIndex++] & 0xff))<<56) |\r
+ (((long)(bytes[byteIndex++] & 0xff))<<48) | \r
+ (((long)(bytes[byteIndex++] & 0xff))<<40) | \r
+ (((long)(bytes[byteIndex++] & 0xff))<<32) | \r
+ (((long)(bytes[byteIndex++] & 0xff))<<24) | \r
+ (((long)(bytes[byteIndex++] & 0xff))<<16) | \r
+ (((long)(bytes[byteIndex++] & 0xff))<<8) | \r
+ (((long)(bytes[byteIndex++] & 0xff))); \r
+ return result;\r
+ }\r
+ \r
+ public Object deserialize(byte[] data) throws IOException {\r
+ \r
+ BTreeContentBean result = new BTreeContentBean();\r
+\r
+ try {\r
+ \r
+ result.leaf = (data[0] == 1) ? true : false;\r
+ int byteIndex = 1;\r
+ result.n = readBE4(data, byteIndex);\r
+ byteIndex += 4;\r
+ \r
+ Binding pbv = PossibleVariant.BINDING;\r
+ Serializer pbs = pbv.serializer();\r
+\r
+ // Redundant array size\r
+ int keySize = readBE4(data, byteIndex);\r
+ result.key = new PossibleVariant[keySize];\r
+ byteIndex += 4;\r
+ for(int i=0;i<keySize;i++) {\r
+ PossibleVariantInputStream is = new PossibleVariantInputStream(data, byteIndex);\r
+ PossibleVariant v = (PossibleVariant)pbs.deserialize(is);\r
+ result.key[i] = v;\r
+ byteIndex = is.getOffset();\r
+ }\r
+ \r
+ // Redundant array size\r
+ int valueSize = readBE4(data, byteIndex);\r
+ result.value = new PossibleResource[valueSize];\r
+ byteIndex += 4;\r
+ for(int i=0;i<valueSize;i++) {\r
+ boolean has = Bytes.read(data, byteIndex++) > 0;\r
+ if(has) {\r
+ result.value[i] = PossibleResource.read(ss, readBE8(data, byteIndex));\r
+ byteIndex += 8;\r
+ } else {\r
+ result.value[i] = new PossibleResource();\r
+ }\r
+ }\r
+ \r
+ // Redundant array size\r
+ int childSize = readBE4(data, byteIndex);\r
+ result.c = new PossibleResource[childSize];\r
+ byteIndex += 4;\r
+ for(int i=0;i<childSize;i++) {\r
+ boolean has = Bytes.read(data, byteIndex++) > 0;\r
+ if(has) {\r
+ result.c[i] = PossibleResource.read(ss, readBE8(data, byteIndex));\r
+ byteIndex += 8;\r
+ } else {\r
+ result.c[i] = new PossibleResource();\r
+ }\r
+ }\r
+ \r
+ } catch (DatabaseException e) {\r
+ \r
+ e.printStackTrace();\r
+ \r
+ }\r
+ \r
+ return result;\r
+ \r
+ }\r
+ \r
+ };\r
+ \r
+ @Override\r
+ public void accept(Visitor1 v, Object obj) {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public <T> T accept(Visitor<T> v) {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public boolean isInstance(Object obj) {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public void readFrom(Binding srcBinding, Object src, Object dst)\r
+ throws BindingException {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public void assertInstaceIsValid(Object obj, Set<Object> validInstances)\r
+ throws BindingException {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public int deepHashValue(Object value,\r
+ IdentityHashMap<Object, Object> hashedObjects)\r
+ throws BindingException {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public int deepCompare(Object o1, Object o2,\r
+ Set<IdentityPair<Object, Object>> compareHistory)\r
+ throws BindingException {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ protected void toString(Object value, BindingPrintContext ctx)\r
+ throws BindingException {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public int getComponentCount() {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public Binding getComponentBinding(int index) {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+\r
+ @Override\r
+ public Binding getComponentBinding(ChildReference path) {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+ \r
+ @Override\r
+ public Serializer serializer() throws RuntimeSerializerConstructionException {\r
+ return serializer;\r
+ }\r
+ \r
+}\r
+\r
+final public class BTreeUtils implements BTreeContentManager {\r
+\r
+ final private Resource tree;\r
+ final private Resource ownerRelation;\r
+ \r
+ final public Binding CONTENT_BEAN_BINDING;\r
+ final public DatatypeResource DATA;\r
+ \r
+ private long mod;\r
+ private int t;\r
+ private Map<Resource, BTreeContentBean> beans;\r
+ private Map<Resource, Resource> owners;\r
+ private Resource root;\r
+ private Resource nodeType;\r
+ private boolean cached;\r
+\r
+ public BTreeUtils(ReadGraph graph, Resource tree, int t, Resource nodeType, Resource ownerRelation, boolean cached) throws DatabaseException {\r
+ try {\r
+ SerialisationSupport ss = graph.getService(SerialisationSupport.class);\r
+ XSupport xs = graph.getService(XSupport.class);\r
+ \r
+ CONTENT_BEAN_BINDING = new BTreeContentBinding(ss, xs);\r
+ DATA = DatatypeResource.getInstance(graph);\r
+ this.tree = tree;\r
+ this.ownerRelation = ownerRelation;\r
+ this.nodeType = nodeType != null ? nodeType : DATA.BTreeNode;\r
+ this.t = t;\r
+ this.mod = 0;\r
+ this.cached = cached;\r
+ if (cached) {\r
+ this.beans = new HashMap<Resource, BTreeContentBean>();\r
+ this.owners = new HashMap<Resource, Resource>();\r
+ }\r
+ } catch (RuntimeBindingConstructionException e) {\r
+ Logger.defaultLogError(e);\r
+ throw new DatabaseException(e);\r
+ }\r
+ }\r
+ \r
+ public static BTreeUtils create(WriteGraph graph, Resource ownerRelation, int t, boolean cached) throws DatabaseException {\r
+ \r
+ DatatypeResource DATA = DatatypeResource.getInstance(graph);\r
+ return create(graph, DATA.BTree, DATA.BTreeNode, ownerRelation, t, cached);\r
+ \r
+ }\r
+\r
+ public static BTreeUtils create(WriteGraph graph, Resource type, Resource nodeType, Resource ownerRelation, int t, boolean cached) throws DatabaseException {\r
+ \r
+ Layer0 L0 = Layer0.getInstance(graph);\r
+ DatatypeResource DATA = DatatypeResource.getInstance(graph);\r
+ Resource tree = graph.newResource();\r
+ graph.claim(tree, L0.InstanceOf, null, type);\r
+ \r
+ if(ownerRelation != null)\r
+ graph.claim(tree, DATA.BTree_HasOwnerRelation, DATA.BTree_HasOwnerRelation_Inverse, ownerRelation);\r
+ if(nodeType != null)\r
+ graph.claim(tree, DATA.BTree_HasNodeType, DATA.BTree_HasNodeType_Inverse, nodeType);\r
+ \r
+ graph.claimLiteral(tree, DATA.BTree_t, t, Bindings.INTEGER);\r
+ \r
+ if (!cached) {\r
+ graph.claimLiteral(tree, DATA.BTree_mod, 0L, Bindings.LONG);\r
+ }\r
+\r
+ BTreeUtils utils = new BTreeUtils(graph, tree, t, nodeType, ownerRelation, cached);\r
+ Resource node = utils.createNode(graph, utils, t); \r
+ utils.setRoot(graph, node);\r
+ utils.setOwner(graph, node, tree, true);\r
+ \r
+ return utils; \r
+ } \r
+ \r
+ public Resource getTree() {\r
+ return tree;\r
+ }\r
+\r
+ public void insert(WriteGraph graph, Variant k, Resource v) throws DatabaseException {\r
+\r
+ Resource r = getRoot(graph);\r
+ insertImpl(graph, this, r, t, k, v);\r
+ \r
+ }\r
+\r
+ static class BatchContentManager implements BTreeContentManager {\r
+\r
+ final private BTreeUtils bu;\r
+ \r
+ final Map<Resource, BTreeContentBean> beans = new HashMap<Resource, BTreeContentBean>();\r
+ \r
+ public BatchContentManager(BTreeUtils bu) {\r
+ this.bu = bu;\r
+ }\r
+ \r
+ @Override\r
+ public BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException {\r
+ BTreeContentBean bean = beans.get(node);\r
+ if(bean != null) return bean;\r
+ return bu.getContentBean(graph, node);\r
+ }\r
+\r
+ @Override\r
+ public void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException {\r
+ beans.put(node, bean);\r
+ }\r
+ \r
+ public void apply(WriteGraph graph) throws DatabaseException {\r
+ for(Map.Entry<Resource, BTreeContentBean> entry : beans.entrySet()) {\r
+ bu.setContentBean(graph, entry.getKey(), entry.getValue());\r
+ }\r
+ }\r
+ \r
+ }\r
+ \r
+ public void insertAll(WriteGraph graph, Collection<Pair<Variant, Resource>> values) throws DatabaseException {\r
+\r
+ Resource r = getRoot(graph);\r
+ BatchContentManager cm = new BatchContentManager(this);\r
+ for(Pair<Variant, Resource> entry : values) {\r
+ insertImpl(graph, cm, r, t, entry.first, entry.second);\r
+ }\r
+ cm.apply(graph);\r
+ \r
+ }\r
+\r
+ public Resource search(ReadGraph graph, Variant k) throws DatabaseException {\r
+\r
+ Resource r = getRoot(graph);\r
+ return searchNode(graph, r, k);\r
+ \r
+ }\r
+ \r
+ // Implementation\r
+\r
+ private int findKey(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, Variant k) throws DatabaseException {\r
+\r
+ int idx = 0;\r
+ while(idx<bean.n && bean.key[idx].v.compareTo(k) < 0)\r
+ idx++;\r
+ return idx;\r
+\r
+ }\r
+ \r
+ private void insertImpl(WriteGraph graph, BTreeContentManager manager, Resource r, int t, Variant k, Resource v) throws DatabaseException {\r
+\r
+ BTreeContentBean rContent = manager.getContentBean(graph, r);\r
+ if(rContent.n == 2*t-1) {\r
+ Resource s = allocateNode(graph, manager, t);\r
+ BTreeContentBean sContent = manager.getContentBean(graph, s);\r
+ setRoot(graph, s);\r
+ setOwner(graph, s, tree, true);\r
+ sContent.leaf = false;\r
+ sContent.n = 0;\r
+ sContent.c[0].r = r;\r
+ setOwner(graph, r, s, true);\r
+ manager.setContentBean(graph, s, sContent);\r
+ splitChild(graph, manager, t, s, 1, r);\r
+ insertNonfull(graph, manager, t, s, k, v);\r
+ } else {\r
+ insertNonfull(graph, manager, t, r, k, v);\r
+ }\r
+ \r
+ }\r
+\r
+ public void remove(WriteGraph graph, Variant k) throws DatabaseException {\r
+\r
+ Resource r = getRoot(graph);\r
+ \r
+ BTreeContentBean bean = getContentBean(graph, r);\r
+ Resource removedResource = removeImpl(graph, this, t, r, bean, k);\r
+ if (removedResource != null) {\r
+ removeOwner(graph, removedResource, false);\r
+ \r
+ // If the root node has 0 keys, make its first child as the new root\r
+ // if it has a child, otherwise set root as NULL\r
+ if (bean.n==0)\r
+ {\r
+ //BTreeContentBean tmp = bean;\r
+ if (!bean.leaf) {\r
+ removeOwner(graph, r, true);\r
+ setRoot(graph, bean.c[0].r);\r
+ setOwner(graph, bean.c[0].r, tree, true);\r
+ }\r
+ \r
+ // Free the old root\r
+ //delete tmp;\r
+ \r
+ }\r
+ }\r
+\r
+ \r
+ }\r
+ \r
+ public Resource removeImpl(WriteGraph graph, BTreeContentManager manager, int t, Resource r, BTreeContentBean bean, Variant k) throws DatabaseException {\r
+ \r
+ int idx = findKey(graph, manager, bean, k);\r
+ \r
+ if(idx < bean.n && bean.key[idx].v.equals(k)) {\r
+ Resource removedResource = bean.value[idx].r;\r
+ if(bean.leaf)\r
+ removeFromLeaf(graph, manager, r, bean, idx);\r
+ else\r
+ removeFromNonLeaf(graph, manager, r, bean, t, idx);\r
+ \r
+ return removedResource;\r
+ } else {\r
+ \r
+ if (bean.leaf) {\r
+ return null;\r
+ }\r
+ \r
+ // The key to be removed is present in the sub-tree rooted with this node\r
+ // The flag indicates whether the key is present in the sub-tree rooted\r
+ // with the last child of this node\r
+ boolean flag = ( (idx==bean.n)? true : false );\r
+ \r
+ BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx].r);\r
+ \r
+ // If the child where the key is supposed to exist has less that t keys,\r
+ // we fill that child\r
+ if (cContent.n < t)\r
+ fill(graph, manager, r, bean, t, idx);\r
+ \r
+ // If the last child has been merged, it must have merged with the previous\r
+ // child and so we recurse on the (idx-1)th child. Else, we recurse on the\r
+ // (idx)th child which now has atleast t keys\r
+ if (flag && idx > bean.n)\r
+ return removeImpl(graph, manager, t, bean.c[idx-1].r, manager.getContentBean(graph, bean.c[idx-1].r), k);\r
+ else\r
+ return removeImpl(graph, manager, t, bean.c[idx].r, cContent, k);\r
+ \r
+ }\r
+ \r
+ \r
+ }\r
+ \r
+ // A function to get predecessor of keys[idx]\r
+ Pair<Variant, Resource> getPred(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, int idx) throws DatabaseException {\r
+ \r
+ // Keep moving to the right most node until we reach a leaf\r
+ bean = manager.getContentBean(graph, bean.c[idx].r);\r
+ while (!bean.leaf)\r
+ bean = manager.getContentBean(graph, bean.c[bean.n].r);\r
+ \r
+ // Return the last key of the leaf\r
+ return new Pair<Variant, Resource>(bean.key[bean.n-1].v, bean.value[bean.n-1].r);\r
+ \r
+ }\r
+ \r
+ Pair<Variant, Resource> getSucc(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, int idx) throws DatabaseException {\r
+ \r
+ // Keep moving the left most node starting from C[idx+1] until we reach a leaf\r
+ bean = manager.getContentBean(graph, bean.c[idx+1].r);\r
+ while (!bean.leaf)\r
+ bean = manager.getContentBean(graph, bean.c[0].r);\r
+\r
+ // Return the first key of the leaf\r
+ return new Pair<Variant, Resource>(bean.key[0].v, bean.value[0].r);\r
+ \r
+ }\r
+ \r
+ // A function to fill child C[idx] which has less than t-1 keys\r
+ void fill(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {\r
+\r
+ // If the previous child(C[idx-1]) has more than t-1 keys, borrow a key\r
+ // from that child\r
+ if (idx!=0) {\r
+ BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx-1].r);\r
+\r
+ if (cContent.n>=t) {\r
+ borrowFromPrev(graph, manager, r, bean, idx);\r
+ return;\r
+ }\r
+ }\r
+ \r
+ // If the next child(C[idx+1]) has more than t-1 keys, borrow a key\r
+ // from that child\r
+\r
+ if (idx!=bean.n) {\r
+ BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx+1].r);\r
+\r
+ if (cContent.n>=t) {\r
+ borrowFromNext(graph, manager, r, bean, idx);\r
+ return;\r
+ }\r
+ }\r
+\r
+ // Merge C[idx] with its sibling\r
+ // If C[idx] is the last child, merge it with with its previous sibling\r
+ // Otherwise merge it with its next sibling\r
+ if (idx != bean.n)\r
+ merge(graph, manager, r, bean, t, idx);\r
+ else\r
+ merge(graph, manager, r, bean, t, idx-1);\r
+ }\r
+ \r
+ // A function to borrow a key from C[idx-1] and insert it\r
+ // into C[idx]\r
+ void borrowFromPrev(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {\r
+ \r
+ BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);\r
+ BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx-1].r);\r
+ \r
+ // The last key from C[idx-1] goes up to the parent and key[idx-1]\r
+ // from parent is inserted as the first key in C[idx]. Thus, the loses\r
+ // sibling one key and child gains one key\r
+ \r
+ // Moving all key in C[idx] one step ahead\r
+ for (int i=childContent.n-1; i>=0; --i) {\r
+ childContent.key[i+1].v = childContent.key[i].v;\r
+ childContent.value[i+1].r = childContent.value[i].r;\r
+ }\r
+ \r
+ // If C[idx] is not a leaf, move all its child pointers one step ahead\r
+ if (!childContent.leaf) {\r
+ for(int i=childContent.n; i>=0; --i) {\r
+ childContent.c[i+1].r = childContent.c[i].r;\r
+ setOwner(graph, childContent.c[i+1].r, bean.c[idx].r, true);\r
+ }\r
+ }\r
+\r
+ // Setting child's first key equal to keys[idx-1] from the current node\r
+ childContent.key[0].v = bean.key[idx-1].v;\r
+ childContent.value[0].r = bean.value[idx-1].r;\r
+ \r
+ // Moving sibling's last child as C[idx]'s first child\r
+ // TODO: is this correct?\r
+ if (!bean.leaf) {\r
+ Resource lastChild = siblingContent.c[siblingContent.n].r;\r
+ if (lastChild != null) {\r
+ childContent.c[0].r = lastChild;\r
+ setOwner(graph, childContent.c[0].r, bean.c[idx].r, true);\r
+ }\r
+ }\r
+\r
+ // Moving the key from the sibling to the parent\r
+ // This reduces the number of keys in the sibling\r
+ bean.key[idx-1].v = siblingContent.key[siblingContent.n-1].v;\r
+ bean.value[idx-1].r = siblingContent.value[siblingContent.n-1].r;\r
+\r
+ childContent.n += 1;\r
+ siblingContent.reduceSize();\r
+ //siblingContent.n -= 1;\r
+\r
+ manager.setContentBean(graph, r, bean);\r
+ manager.setContentBean(graph, bean.c[idx].r, childContent);\r
+ manager.setContentBean(graph, bean.c[idx-1].r, siblingContent);\r
+\r
+ }\r
+ \r
+ // A function to borrow a key from the C[idx+1] and place\r
+ // it in C[idx]\r
+ void borrowFromNext(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {\r
+\r
+ BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);\r
+ BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx+1].r);\r
+\r
+ // keys[idx] is inserted as the last key in C[idx]\r
+ childContent.key[childContent.n].v = bean.key[idx].v;\r
+ childContent.value[childContent.n].r = bean.value[idx].r;\r
+ \r
+ // Sibling's first child is inserted as the last child\r
+ // into C[idx]\r
+ if (!childContent.leaf) {\r
+ childContent.c[childContent.n+1].r = siblingContent.c[0].r;\r
+ setOwner(graph, childContent.c[childContent.n+1].r, bean.c[idx].r, true);\r
+ }\r
+ \r
+ //The first key from sibling is inserted into keys[idx]\r
+ bean.key[idx].v = siblingContent.key[0].v;\r
+ bean.value[idx].r = siblingContent.value[0].r;\r
+ \r
+ // Moving all keys in sibling one step behind\r
+ for (int i=1; i<siblingContent.n; ++i) {\r
+ siblingContent.key[i-1].v = siblingContent.key[i].v;\r
+ siblingContent.value[i-1].r = siblingContent.value[i].r;\r
+ }\r
+ \r
+ // Moving the child pointers one step behind\r
+ if (!siblingContent.leaf) {\r
+ for(int i=1; i<=siblingContent.n; ++i)\r
+ siblingContent.c[i-1].r = siblingContent.c[i].r;\r
+ }\r
+ \r
+ // Increasing and decreasing the key count of C[idx] and C[idx+1]\r
+ // respectively\r
+ childContent.n += 1;\r
+ siblingContent.reduceSize();\r
+ //siblingContent.n -= 1;\r
+ \r
+ manager.setContentBean(graph, r, bean);\r
+ manager.setContentBean(graph, bean.c[idx].r, childContent);\r
+ manager.setContentBean(graph, bean.c[idx+1].r, siblingContent);\r
+ \r
+ }\r
+ \r
+ // A function to merge C[idx] with C[idx+1]\r
+ // C[idx+1] is freed after merging\r
+ void merge(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {\r
+ \r
+ BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);\r
+ BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx+1].r);\r
+\r
+ // Pulling a key from the current node and inserting it into (t-1)th\r
+ // position of C[idx]\r
+ childContent.key[t-1].v = bean.key[idx].v;\r
+ childContent.value[t-1].r = bean.value[idx].r;\r
+ \r
+ // Copying the keys from C[idx+1] to C[idx] at the end\r
+ for (int i=0; i<siblingContent.n; ++i) {\r
+ childContent.key[i+t].v = siblingContent.key[i].v;\r
+ childContent.value[i+t].r = siblingContent.value[i].r;\r
+ }\r
+ \r
+ // Copying the child pointers from C[idx+1] to C[idx]\r
+ if (!childContent.leaf) {\r
+ for(int i=0; i<=siblingContent.n; ++i) {\r
+ childContent.c[i+t].r = siblingContent.c[i].r;\r
+ setOwner(graph, childContent.c[i+t].r, bean.c[idx].r, true);\r
+ }\r
+ }\r
+ \r
+ // Moving all keys after idx in the current node one step before -\r
+ // to fill the gap created by moving keys[idx] to C[idx]\r
+ for (int i=idx+1; i<bean.n; ++i) {\r
+ bean.key[i-1].v = bean.key[i].v;\r
+ bean.value[i-1].r = bean.value[i].r;\r
+ }\r
+\r
+ // Remove the owner of the merged sibling\r
+ removeOwner(graph, bean.c[idx+1].r, true);\r
+ \r
+ // Moving the child pointers after (idx+1) in the current node one\r
+ // step before\r
+ for (int i=idx+2; i<=bean.n; ++i)\r
+ bean.c[i-1].r = bean.c[i].r;\r
+ \r
+ // Updating the key count of child and the current node\r
+ childContent.n += siblingContent.n+1;\r
+ bean.reduceSize();\r
+ //bean.n--;\r
+ \r
+ // Freeing the memory occupied by sibling\r
+ // delete(sibling);\r
+ \r
+ manager.setContentBean(graph, r, bean);\r
+ manager.setContentBean(graph, bean.c[idx].r, childContent);\r
+\r
+ }\r
+ \r
+ private void removeOwner(WriteGraph graph, Resource r, boolean force) throws DatabaseException {\r
+ if((ownerRelation != null) || force) {\r
+ if (cached) {\r
+ owners.put(r, null);\r
+ } else {\r
+ Resource own = ownerRelation != null ? ownerRelation : DATA.BTreeNode_IsOwnedBy;\r
+ graph.deny(r, own);\r
+ }\r
+ }\r
+ }\r
+ \r
+ private void removeFromLeaf(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {\r
+\r
+ // Move all the keys after the idx-th pos one place backward\r
+ for (int i=idx+1; i<bean.n; ++i) {\r
+ bean.key[i-1].v = bean.key[i].v;\r
+ bean.value[i-1].r = bean.value[i].r;\r
+ }\r
+ \r
+ // Reduce the count of keys\r
+ bean.reduceSize();\r
+ //bean.n--;\r
+ \r
+ manager.setContentBean(graph, r, bean);\r
+ \r
+ }\r
+\r
+ private void removeFromNonLeaf(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {\r
+\r
+ Variant k = bean.key[idx].v;\r
+ \r
+ // If the child that precedes k (C[idx]) has atleast t keys,\r
+ // find the predecessor 'pred' of k in the subtree rooted at\r
+ // C[idx]. Replace k by pred. Recursively delete pred\r
+ // in C[idx]\r
+ \r
+ BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx].r);\r
+\r
+ if (cContent.n >= t) {\r
+ \r
+ Pair<Variant, Resource> pred = getPred(graph, manager, bean, idx);\r
+ bean.key[idx].v = pred.first;\r
+ bean.value[idx].r = pred.second;\r
+ removeImpl(graph, manager, t, bean.c[idx].r, cContent, pred.first);\r
+ \r
+ manager.setContentBean(graph, r, bean);\r
+ } else {\r
+\r
+ BTreeContentBean cContentPlus1 = manager.getContentBean(graph, bean.c[idx+1].r);\r
+\r
+ // If the child C[idx] has less that t keys, examine C[idx+1].\r
+ // If C[idx+1] has atleast t keys, find the successor 'succ' of k in\r
+ // the subtree rooted at C[idx+1]\r
+ // Replace k by succ\r
+ // Recursively delete succ in C[idx+1]\r
+ if (cContentPlus1.n >= t) {\r
+ Pair<Variant, Resource> succ = getSucc(graph, manager, bean, idx);\r
+ bean.key[idx].v = succ.first;\r
+ bean.value[idx].r = succ.second;\r
+ removeImpl(graph, manager, t, bean.c[idx+1].r, cContentPlus1, succ.first);\r
+ \r
+ manager.setContentBean(graph, r, bean);\r
+ }\r
+\r
+ // If both C[idx] and C[idx+1] has less that t keys,merge k and all of C[idx+1]\r
+ // into C[idx]\r
+ // Now C[idx] contains 2t-1 keys\r
+ // Free C[idx+1] and recursively delete k from C[idx]\r
+ else {\r
+ \r
+ merge(graph, manager, r, bean, t, idx);\r
+ removeImpl(graph, manager, t, bean.c[idx].r, cContent, k);\r
+ \r
+ }\r
+ \r
+ }\r
+ \r
+ }\r
+\r
+ private Resource createNode(WriteGraph graph, BTreeContentManager manager, int t) throws DatabaseException {\r
+ Layer0 L0 = Layer0.getInstance(graph);\r
+ Resource result = graph.newResource();\r
+ mod++;\r
+ graph.claim(result, L0.InstanceOf, null, nodeType);\r
+ if (!cached) {\r
+ graph.claimLiteral(tree, DATA.BTree_mod, mod, Bindings.LONG);\r
+ }\r
+ graph.addLiteral(result, L0.HasName, L0.NameOf, ""+mod, Bindings.STRING);\r
+ manager.setContentBean(graph, result, BTreeContentBean.create(t));\r
+ return result;\r
+ }\r
+ \r
+ public Resource searchNode(ReadGraph graph, Resource x, Variant k) throws DatabaseException {\r
+\r
+ BTreeContentBean xContent = getContentBean(graph, x);\r
+\r
+ int i=1;\r
+ while(i <= xContent.n && k.compareTo(xContent.key[i-1].v) > 0) i++;\r
+ if(i <= xContent.n && k.equals(xContent.key[i-1].v)) return xContent.value[i-1].r;\r
+ \r
+ if(xContent.leaf) return null;\r
+ else return searchNode(graph, xContent.c[i-1].r, k);\r
+ \r
+ }\r
+\r
+ private void splitChild(WriteGraph graph, BTreeContentManager manager, int t, Resource x, int i, Resource y) throws DatabaseException {\r
+ \r
+ Resource z = allocateNode(graph, manager, t);\r
+ \r
+ BTreeContentBean xContent = manager.getContentBean(graph, x);\r
+ BTreeContentBean yContent = manager.getContentBean(graph, y);\r
+ BTreeContentBean zContent = manager.getContentBean(graph, z);\r
+\r
+ zContent.leaf = yContent.leaf;\r
+ zContent.n = t-1;\r
+ \r
+ for(int j=1;j<=t-1;j++) {\r
+ zContent.key[j-1].v = yContent.key[j+t-1].v;\r
+ zContent.value[j-1].r = yContent.value[j+t-1].r;\r
+ setOwner(graph, zContent.value[j-1].r, z, false);\r
+ }\r
+ if(!yContent.leaf) {\r
+ for(int j=1;j<=t;j++) {\r
+ zContent.c[j-1].r = yContent.c[j+t-1].r;\r
+ setOwner(graph, zContent.c[j-1].r, z, true);\r
+ }\r
+ }\r
+\r
+ //yContent.n = t-1;\r
+\r
+ \r
+ for(int j=xContent.n+1;j>=i+1;j--) {\r
+ xContent.c[j+1-1].r = xContent.c[j-1].r; \r
+ }\r
+ \r
+ xContent.c[i+1-1].r = z;\r
+ setOwner(graph, z, x, true);\r
+\r
+ for(int j=xContent.n;j>=i;j--) {\r
+ xContent.key[j+1-1].v = xContent.key[j-1].v; \r
+ xContent.value[j+1-1].r = xContent.value[j-1].r; \r
+ }\r
+ \r
+ xContent.key[i-1].v = yContent.key[t-1].v;\r
+ xContent.value[i-1].r = yContent.value[t-1].r;\r
+ xContent.n++;\r
+\r
+ while (yContent.n > t-1) yContent.reduceSize();\r
+ \r
+ setOwner(graph, xContent.value[i-1].r, x, true);\r
+ \r
+ manager.setContentBean(graph, x, xContent);\r
+ manager.setContentBean(graph, y, yContent);\r
+ manager.setContentBean(graph, z, zContent);\r
+ \r
+ }\r
+ \r
+ private void insertNonfull(WriteGraph graph, BTreeContentManager manager, int t, Resource x, Variant k, Resource v) throws DatabaseException {\r
+\r
+ BTreeContentBean xContent = manager.getContentBean(graph, x);\r
+\r
+ int i = xContent.n;\r
+ \r
+ if(xContent.leaf) {\r
+ while(i >= 1 && k.compareTo(xContent.key[i-1].v) < 0) {\r
+ xContent.key[i+1-1].v = xContent.key[i-1].v;\r
+ xContent.value[i+1-1].r = xContent.value[i-1].r;\r
+ i--;\r
+ }\r
+ \r
+ xContent.key[i+1-1].v = k;\r
+ xContent.value[i+1-1].r = v;\r
+ xContent.n++;\r
+ setOwner(graph, v, x, false);\r
+ manager.setContentBean(graph, x, xContent);\r
+ } else {\r
+ while(i >= 1 && k.compareTo(xContent.key[i-1].v) < 0) i--;\r
+ i++;\r
+ BTreeContentBean xciContent = manager.getContentBean(graph, xContent.c[i-1].r);\r
+ if(xciContent.n == 2*t-1) {\r
+ splitChild(graph, manager, t, x, i, xContent.c[i-1].r);\r
+ xContent = manager.getContentBean(graph, x);\r
+ if(k.compareTo(xContent.key[i-1].v) > 0) i++;\r
+ }\r
+ insertNonfull(graph, manager, t, xContent.c[i-1].r, k, v);\r
+ }\r
+ \r
+ }\r
+ \r
+ private void setOwner(WriteGraph graph, Resource r, Resource owner, boolean force) throws DatabaseException {\r
+ if (r != null) {\r
+ if((ownerRelation != null) || force) {\r
+ Resource own = ownerRelation != null ? ownerRelation : DATA.BTreeNode_IsOwnedBy;\r
+ if (cached) {\r
+ owners.put(r, owner);\r
+ } else {\r
+ graph.deny(r, own);\r
+ graph.claim(r, own, owner);\r
+ }\r
+ }\r
+ }\r
+ }\r
+ \r
+ private Resource getRoot(ReadGraph graph) throws DatabaseException {\r
+ if (cached) {\r
+ if (root != null) return root;\r
+ }\r
+ return graph.getPossibleObject(tree, DATA.BTree_root);\r
+ }\r
+ \r
+ private void setRoot(WriteGraph graph, Resource r) throws DatabaseException {\r
+ if (cached) {\r
+ this.root = r;\r
+ } else {\r
+ graph.deny(tree, DATA.BTree_root);\r
+ graph.claim(tree, DATA.BTree_root, r);\r
+ }\r
+ }\r
+\r
+ private Resource allocateNode(WriteGraph graph, BTreeContentManager manager, int t) throws DatabaseException {\r
+ return createNode(graph, manager, t);\r
+ }\r
+ \r
+ public void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException {\r
+ if (cached) {\r
+ beans.put(node, bean);\r
+ } else {\r
+ graph.claimLiteral(node, DATA.BTreeNode_content, DATA.BTreeNode_Content, bean, CONTENT_BEAN_BINDING );\r
+ }\r
+ }\r
+ \r
+ public void flushCache(WriteGraph graph) throws DatabaseException {\r
+ assert(cached);\r
+ \r
+ XSupport xs = graph.getService(XSupport.class);\r
+ for(Map.Entry<Resource, BTreeContentBean> entry : beans.entrySet()) {\r
+ Resource node = xs.convertDelayedResourceToResource(entry.getKey());\r
+ if (node != null) {\r
+ graph.claimLiteral(node, DATA.BTreeNode_content, DATA.BTreeNode_Content, entry.getValue(), CONTENT_BEAN_BINDING );\r
+ }\r
+ }\r
+\r
+ for(Map.Entry<Resource, Resource> entry : owners.entrySet()) {\r
+ Resource r = xs.convertDelayedResourceToResource(entry.getKey());\r
+ Resource owner = xs.convertDelayedResourceToResource(entry.getValue());\r
+ graph.deny(r, ownerRelation);\r
+ if (owner != null) {\r
+ graph.claim(r, ownerRelation, owner);\r
+ }\r
+ }\r
+ \r
+ Resource tree2 = xs.convertDelayedResourceToResource(tree);\r
+ graph.claimLiteral(tree2, DATA.BTree_mod, mod, Bindings.LONG);\r
+ \r
+ if (root != null) {\r
+ Resource root2 = xs.convertDelayedResourceToResource(root);\r
+ graph.deny(tree2, DATA.BTree_root);\r
+ graph.claim(tree2, DATA.BTree_root, root2);\r
+ }\r
+ }\r
+ \r
+ public BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException {\r
+ if (cached) {\r
+ BTreeContentBean bean = beans.get(node);\r
+ if (bean != null) return bean;\r
+ }\r
+ return graph.syncRequest(new RelatedValue<BTreeContentBean>(node, DATA.BTreeNode_content, CONTENT_BEAN_BINDING), TransientCacheListener.<BTreeContentBean>instance());\r
+ }\r
+ \r
+ public List<Tuple2> entries(ReadGraph graph) throws DatabaseException {\r
+ Resource r = getRoot(graph);\r
+ List<Tuple2> results = new ArrayList<Tuple2>();\r
+ return collectEntries(graph, r, null, null, results);\r
+ }\r
+ \r
+ private List<Tuple2> collectEntries(ReadGraph graph, Resource x, Variant min, Variant max, List<Tuple2> results) throws DatabaseException {\r
+\r
+ BTreeContentBean xContent = getContentBean(graph, x);\r
+\r
+ for (int i = 0; i < xContent.n + 1; i++) {\r
+ if (min != null && i < xContent.n && min.compareTo(xContent.key[i].v) > 0) continue;\r
+ \r
+ if (!xContent.leaf) {\r
+ Resource child = xContent.c[i].r;\r
+ if (child != null) {\r
+ \r
+ // reduce the amount of comparison if we know that the range of the child keys matches\r
+ Variant min2 = (min != null && i > 0 && min.compareTo(xContent.key[i - 1].v) < 0) ? null : min; \r
+ Variant max2 = (max != null && i < xContent.n - 1 && max.compareTo(xContent.key[i + 1].v) > 0) ? null : max;\r
+\r
+ collectEntries(graph, child, min2, max2, results);\r
+ }\r
+ }\r
+ \r
+ if (i < xContent.n) {\r
+ if (max != null && max.compareTo(xContent.key[i].v) < 0) return results;\r
+\r
+ results.add(new Tuple2(xContent.key[i].v, xContent.value[i].r));\r
+ }\r
+ }\r
+ return results;\r
+ }\r
+ \r
+ public List<Tuple2> searchRange(ReadGraph graph, Variant min, Variant max) throws DatabaseException {\r
+ Resource r = getRoot(graph);\r
+ List<Tuple2> results = new ArrayList<Tuple2>();\r
+ return collectEntries(graph, r, min, max, results);\r
+ }\r
+ \r
+}\r
Code Review / simantics / platform.git / blobdiff