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