1 package org.simantics.datatypes.utils;
3 import java.io.ByteArrayInputStream;
4 import java.io.DataInput;
5 import java.io.DataOutput;
6 import java.io.IOException;
7 import java.util.ArrayList;
8 import java.util.Collection;
9 import java.util.HashMap;
10 import java.util.IdentityHashMap;
11 import java.util.List;
15 import org.simantics.databoard.Bindings;
16 import org.simantics.databoard.accessor.reference.ChildReference;
17 import org.simantics.databoard.binding.Binding;
18 import org.simantics.databoard.binding.error.BindingException;
19 import org.simantics.databoard.binding.error.RuntimeBindingConstructionException;
20 import org.simantics.databoard.binding.impl.BindingPrintContext;
21 import org.simantics.databoard.binding.mutable.Variant;
22 import org.simantics.databoard.serialization.RuntimeSerializerConstructionException;
23 import org.simantics.databoard.serialization.Serializer;
24 import org.simantics.databoard.util.IdentityPair;
25 import org.simantics.datatypes.DatatypeResource;
26 import org.simantics.db.ReadGraph;
27 import org.simantics.db.Resource;
28 import org.simantics.db.WriteGraph;
29 import org.simantics.db.common.primitiverequest.RelatedValue;
30 import org.simantics.db.common.procedure.adapter.TransientCacheListener;
31 import org.simantics.db.common.utils.Logger;
32 import org.simantics.db.exception.DatabaseException;
33 import org.simantics.db.service.Bytes;
34 import org.simantics.db.service.SerialisationSupport;
35 import org.simantics.db.service.XSupport;
36 import org.simantics.layer0.Layer0;
37 import org.simantics.scl.runtime.tuple.Tuple2;
38 import org.simantics.utils.datastructures.Pair;
40 import gnu.trove.list.array.TByteArrayList;
41 import gnu.trove.map.hash.TObjectIntHashMap;
44 * Implementation from http://www.geeksforgeeks.org/b-tree-set-3delete/
48 interface BTreeContentManager {
50 BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException;
51 void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException;
55 class PossibleVariantInputStream extends ByteArrayInputStream {
57 PossibleVariantInputStream(byte[] data, int offset) {
58 super(data, offset, data.length-offset);
61 public int getOffset() {
67 class BTreeContentBinding extends Binding {
69 private final SerialisationSupport ss;
70 private final XSupport xs;
72 public BTreeContentBinding(SerialisationSupport ss, XSupport xs) {
77 private final Serializer serializer = new Serializer() {
80 public void serialize(DataOutput out, TObjectIntHashMap<Object> identities, Object obj) throws IOException {
81 throw new UnsupportedOperationException();
85 public void serialize(DataOutput out, Object obj) throws IOException {
86 byte[] data = serialize(obj);
91 public Object deserialize(DataInput in, List<Object> identities)
93 throw new UnsupportedOperationException();
97 public Object deserialize(DataInput in) throws IOException {
98 throw new UnsupportedOperationException();
102 public void deserializeTo(DataInput in, List<Object> identities,
103 Object dst) throws IOException {
104 throw new UnsupportedOperationException();
108 public void deserializeTo(DataInput in, Object dst) throws IOException {
109 throw new UnsupportedOperationException();
113 public void skip(DataInput in, List<Object> identities)
115 throw new UnsupportedOperationException();
119 public void skip(DataInput in) throws IOException {
120 throw new UnsupportedOperationException();
124 public Integer getConstantSize() {
125 throw new UnsupportedOperationException();
129 public int getSize(Object obj, TObjectIntHashMap<Object> identities)
131 throw new UnsupportedOperationException();
135 public int getSize(Object obj) throws IOException {
136 return serialize(obj).length;
140 public int getMinSize() {
141 throw new UnsupportedOperationException();
144 private void addBE(TByteArrayList bytes, int value) {
146 bytes.add((byte) ((value >>> 24) & 0xFF));
147 bytes.add((byte) ((value >>> 16) & 0xFF));
148 bytes.add((byte) ((value >>> 8) & 0xFF));
149 bytes.add( (byte) (value & 0xFF));
153 private void addBE(TByteArrayList bytes, long value) {
155 bytes.add((byte) ((value >>> 56) & 0xFF));
156 bytes.add((byte) ((value >>> 48) & 0xFF));
157 bytes.add((byte) ((value >>> 40) & 0xFF));
158 bytes.add((byte) ((value >>> 32) & 0xFF));
159 bytes.add((byte) ((value >>> 24) & 0xFF));
160 bytes.add((byte) ((value >>> 16) & 0xFF));
161 bytes.add((byte) ((value >>> 8) & 0xFF));
162 bytes.add( (byte) (value & 0xFF));
166 public byte[] serialize(Object obj) throws IOException {
167 BTreeContentBean bean = (BTreeContentBean)obj;
168 TByteArrayList bytes = new TByteArrayList();
169 bytes.add(bean.leaf ? (byte)1 : (byte)0);
170 addBE(bytes, bean.n);
171 //addLE(bytes, (bean.key.length+1)/2);
172 Binding pbv = PossibleVariant.BINDING;
173 Serializer pbs = pbv.serializer();
174 addBE(bytes, bean.key.length);
175 for(PossibleVariant l : bean.key) {
176 byte[] ser = pbs.serialize(l);
179 addBE(bytes, bean.value.length);
180 for(PossibleResource pr : bean.value) {
183 addBE(bytes, xs.convertDelayedResourceToResource(pr.r).getResourceId());
188 addBE(bytes, bean.c.length);
189 for(PossibleResource pr : bean.c) {
192 addBE(bytes, xs.convertDelayedResourceToResource(pr.r).getResourceId());
197 return bytes.toArray();
200 int readBE4(byte[] bytes, int byteIndex) {
202 (((int)(bytes[byteIndex++] & 0xff))<<24) |
203 (((int)(bytes[byteIndex++] & 0xff))<<16) |
204 (((int)(bytes[byteIndex++] & 0xff))<<8) |
205 (((int)(bytes[byteIndex++] & 0xff)));
209 long readBE8(byte[] bytes, int byteIndex) {
211 (((long)(bytes[byteIndex++] & 0xff))<<56) |
212 (((long)(bytes[byteIndex++] & 0xff))<<48) |
213 (((long)(bytes[byteIndex++] & 0xff))<<40) |
214 (((long)(bytes[byteIndex++] & 0xff))<<32) |
215 (((long)(bytes[byteIndex++] & 0xff))<<24) |
216 (((long)(bytes[byteIndex++] & 0xff))<<16) |
217 (((long)(bytes[byteIndex++] & 0xff))<<8) |
218 (((long)(bytes[byteIndex++] & 0xff)));
222 public Object deserialize(byte[] data) throws IOException {
224 BTreeContentBean result = new BTreeContentBean();
228 result.leaf = (data[0] == 1) ? true : false;
230 result.n = readBE4(data, byteIndex);
233 Binding pbv = PossibleVariant.BINDING;
234 Serializer pbs = pbv.serializer();
236 // Redundant array size
237 int keySize = readBE4(data, byteIndex);
238 result.key = new PossibleVariant[keySize];
240 for(int i=0;i<keySize;i++) {
241 PossibleVariantInputStream is = new PossibleVariantInputStream(data, byteIndex);
242 PossibleVariant v = (PossibleVariant)pbs.deserialize(is);
244 byteIndex = is.getOffset();
247 // Redundant array size
248 int valueSize = readBE4(data, byteIndex);
249 result.value = new PossibleResource[valueSize];
251 for(int i=0;i<valueSize;i++) {
252 boolean has = Bytes.read(data, byteIndex++) > 0;
254 result.value[i] = PossibleResource.read(ss, readBE8(data, byteIndex));
257 result.value[i] = new PossibleResource();
261 // Redundant array size
262 int childSize = readBE4(data, byteIndex);
263 result.c = new PossibleResource[childSize];
265 for(int i=0;i<childSize;i++) {
266 boolean has = Bytes.read(data, byteIndex++) > 0;
268 result.c[i] = PossibleResource.read(ss, readBE8(data, byteIndex));
271 result.c[i] = new PossibleResource();
275 } catch (DatabaseException e) {
288 public void accept(Visitor1 v, Object obj) {
289 throw new UnsupportedOperationException();
293 public <T> T accept(Visitor<T> v) {
294 throw new UnsupportedOperationException();
298 public boolean isInstance(Object obj) {
299 throw new UnsupportedOperationException();
303 public void readFrom(Binding srcBinding, Object src, Object dst)
304 throws BindingException {
305 throw new UnsupportedOperationException();
309 public void assertInstaceIsValid(Object obj, Set<Object> validInstances)
310 throws BindingException {
311 throw new UnsupportedOperationException();
315 public int deepHashValue(Object value,
316 IdentityHashMap<Object, Object> hashedObjects)
317 throws BindingException {
318 throw new UnsupportedOperationException();
322 public int deepCompare(Object o1, Object o2,
323 Set<IdentityPair<Object, Object>> compareHistory)
324 throws BindingException {
325 throw new UnsupportedOperationException();
329 protected void toString(Object value, BindingPrintContext ctx)
330 throws BindingException {
331 throw new UnsupportedOperationException();
335 public int getComponentCount() {
336 throw new UnsupportedOperationException();
340 public Binding getComponentBinding(int index) {
341 throw new UnsupportedOperationException();
345 public Binding getComponentBinding(ChildReference path) {
346 throw new UnsupportedOperationException();
350 public Serializer serializer() throws RuntimeSerializerConstructionException {
356 final public class BTreeUtils implements BTreeContentManager {
358 final private Resource tree;
359 final private Resource ownerRelation;
361 final public Binding CONTENT_BEAN_BINDING;
362 final public DatatypeResource DATA;
366 private Map<Resource, BTreeContentBean> beans;
367 private Map<Resource, Resource> owners;
368 private Resource root;
369 private Resource nodeType;
370 private boolean cached;
372 public BTreeUtils(ReadGraph graph, Resource tree, int t, Resource nodeType, Resource ownerRelation, boolean cached) throws DatabaseException {
374 SerialisationSupport ss = graph.getService(SerialisationSupport.class);
375 XSupport xs = graph.getService(XSupport.class);
377 CONTENT_BEAN_BINDING = new BTreeContentBinding(ss, xs);
378 DATA = DatatypeResource.getInstance(graph);
380 this.ownerRelation = ownerRelation;
381 this.nodeType = nodeType != null ? nodeType : DATA.BTreeNode;
384 this.cached = cached;
386 this.beans = new HashMap<Resource, BTreeContentBean>();
387 this.owners = new HashMap<Resource, Resource>();
389 } catch (RuntimeBindingConstructionException e) {
390 Logger.defaultLogError(e);
391 throw new DatabaseException(e);
395 public static BTreeUtils create(WriteGraph graph, Resource ownerRelation, int t, boolean cached) throws DatabaseException {
397 DatatypeResource DATA = DatatypeResource.getInstance(graph);
398 return create(graph, DATA.BTree, DATA.BTreeNode, ownerRelation, t, cached);
402 public static BTreeUtils create(WriteGraph graph, Resource type, Resource nodeType, Resource ownerRelation, int t, boolean cached) throws DatabaseException {
404 Layer0 L0 = Layer0.getInstance(graph);
405 DatatypeResource DATA = DatatypeResource.getInstance(graph);
406 Resource tree = graph.newResource();
407 graph.claim(tree, L0.InstanceOf, null, type);
409 if(ownerRelation != null)
410 graph.claim(tree, DATA.BTree_HasOwnerRelation, DATA.BTree_HasOwnerRelation_Inverse, ownerRelation);
412 graph.claim(tree, DATA.BTree_HasNodeType, DATA.BTree_HasNodeType_Inverse, nodeType);
414 graph.claimLiteral(tree, DATA.BTree_t, t, Bindings.INTEGER);
417 graph.claimLiteral(tree, DATA.BTree_mod, 0L, Bindings.LONG);
420 BTreeUtils utils = new BTreeUtils(graph, tree, t, nodeType, ownerRelation, cached);
421 Resource node = utils.createNode(graph, utils, t);
422 utils.setRoot(graph, node);
423 utils.setOwner(graph, node, tree, true);
428 public Resource getTree() {
432 public void insert(WriteGraph graph, Variant k, Resource v) throws DatabaseException {
434 Resource r = getRoot(graph);
435 insertImpl(graph, this, r, t, k, v);
439 static class BatchContentManager implements BTreeContentManager {
441 final private BTreeUtils bu;
443 final Map<Resource, BTreeContentBean> beans = new HashMap<Resource, BTreeContentBean>();
445 public BatchContentManager(BTreeUtils bu) {
450 public BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException {
451 BTreeContentBean bean = beans.get(node);
452 if(bean != null) return bean;
453 return bu.getContentBean(graph, node);
457 public void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException {
458 beans.put(node, bean);
461 public void apply(WriteGraph graph) throws DatabaseException {
462 for(Map.Entry<Resource, BTreeContentBean> entry : beans.entrySet()) {
463 bu.setContentBean(graph, entry.getKey(), entry.getValue());
469 public void insertAll(WriteGraph graph, Collection<Pair<Variant, Resource>> values) throws DatabaseException {
471 Resource r = getRoot(graph);
472 BatchContentManager cm = new BatchContentManager(this);
473 for(Pair<Variant, Resource> entry : values) {
474 insertImpl(graph, cm, r, t, entry.first, entry.second);
480 public Resource search(ReadGraph graph, Variant k) throws DatabaseException {
482 Resource r = getRoot(graph);
483 return searchNode(graph, r, k);
489 private int findKey(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, Variant k) throws DatabaseException {
492 while(idx<bean.n && bean.key[idx].v.compareTo(k) < 0)
498 private void insertImpl(WriteGraph graph, BTreeContentManager manager, Resource r, int t, Variant k, Resource v) throws DatabaseException {
500 BTreeContentBean rContent = manager.getContentBean(graph, r);
501 if(rContent.n == 2*t-1) {
502 Resource s = allocateNode(graph, manager, t);
503 BTreeContentBean sContent = manager.getContentBean(graph, s);
505 setOwner(graph, s, tree, true);
506 sContent.leaf = false;
509 setOwner(graph, r, s, true);
510 manager.setContentBean(graph, s, sContent);
511 splitChild(graph, manager, t, s, 1, r);
512 insertNonfull(graph, manager, t, s, k, v);
514 insertNonfull(graph, manager, t, r, k, v);
519 public void remove(WriteGraph graph, Variant k) throws DatabaseException {
521 Resource r = getRoot(graph);
523 BTreeContentBean bean = getContentBean(graph, r);
524 Resource removedResource = removeImpl(graph, this, t, r, bean, k);
525 if (removedResource != null) {
526 removeOwner(graph, removedResource, false);
528 // If the root node has 0 keys, make its first child as the new root
529 // if it has a child, otherwise set root as NULL
532 //BTreeContentBean tmp = bean;
534 removeOwner(graph, r, true);
535 setRoot(graph, bean.c[0].r);
536 setOwner(graph, bean.c[0].r, tree, true);
548 public Resource removeImpl(WriteGraph graph, BTreeContentManager manager, int t, Resource r, BTreeContentBean bean, Variant k) throws DatabaseException {
550 int idx = findKey(graph, manager, bean, k);
552 if(idx < bean.n && bean.key[idx].v.equals(k)) {
553 Resource removedResource = bean.value[idx].r;
555 removeFromLeaf(graph, manager, r, bean, idx);
557 removeFromNonLeaf(graph, manager, r, bean, t, idx);
559 return removedResource;
566 // The key to be removed is present in the sub-tree rooted with this node
567 // The flag indicates whether the key is present in the sub-tree rooted
568 // with the last child of this node
569 boolean flag = ( (idx==bean.n)? true : false );
571 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx].r);
573 // If the child where the key is supposed to exist has less that t keys,
574 // we fill that child
576 fill(graph, manager, r, bean, t, idx);
578 // If the last child has been merged, it must have merged with the previous
579 // child and so we recurse on the (idx-1)th child. Else, we recurse on the
580 // (idx)th child which now has atleast t keys
581 if (flag && idx > bean.n)
582 return removeImpl(graph, manager, t, bean.c[idx-1].r, manager.getContentBean(graph, bean.c[idx-1].r), k);
584 return removeImpl(graph, manager, t, bean.c[idx].r, cContent, k);
591 // A function to get predecessor of keys[idx]
592 Pair<Variant, Resource> getPred(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, int idx) throws DatabaseException {
594 // Keep moving to the right most node until we reach a leaf
595 bean = manager.getContentBean(graph, bean.c[idx].r);
597 bean = manager.getContentBean(graph, bean.c[bean.n].r);
599 // Return the last key of the leaf
600 return new Pair<Variant, Resource>(bean.key[bean.n-1].v, bean.value[bean.n-1].r);
604 Pair<Variant, Resource> getSucc(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, int idx) throws DatabaseException {
606 // Keep moving the left most node starting from C[idx+1] until we reach a leaf
607 bean = manager.getContentBean(graph, bean.c[idx+1].r);
609 bean = manager.getContentBean(graph, bean.c[0].r);
611 // Return the first key of the leaf
612 return new Pair<Variant, Resource>(bean.key[0].v, bean.value[0].r);
616 // A function to fill child C[idx] which has less than t-1 keys
617 void fill(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {
619 // If the previous child(C[idx-1]) has more than t-1 keys, borrow a key
622 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx-1].r);
625 borrowFromPrev(graph, manager, r, bean, idx);
630 // If the next child(C[idx+1]) has more than t-1 keys, borrow a key
634 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx+1].r);
637 borrowFromNext(graph, manager, r, bean, idx);
642 // Merge C[idx] with its sibling
643 // If C[idx] is the last child, merge it with with its previous sibling
644 // Otherwise merge it with its next sibling
646 merge(graph, manager, r, bean, t, idx);
648 merge(graph, manager, r, bean, t, idx-1);
651 // A function to borrow a key from C[idx-1] and insert it
653 void borrowFromPrev(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {
655 BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);
656 BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx-1].r);
658 // The last key from C[idx-1] goes up to the parent and key[idx-1]
659 // from parent is inserted as the first key in C[idx]. Thus, the loses
660 // sibling one key and child gains one key
662 // Moving all key in C[idx] one step ahead
663 for (int i=childContent.n-1; i>=0; --i) {
664 childContent.key[i+1].v = childContent.key[i].v;
665 childContent.value[i+1].r = childContent.value[i].r;
668 // If C[idx] is not a leaf, move all its child pointers one step ahead
669 if (!childContent.leaf) {
670 for(int i=childContent.n; i>=0; --i) {
671 childContent.c[i+1].r = childContent.c[i].r;
672 setOwner(graph, childContent.c[i+1].r, bean.c[idx].r, true);
676 // Setting child's first key equal to keys[idx-1] from the current node
677 childContent.key[0].v = bean.key[idx-1].v;
678 childContent.value[0].r = bean.value[idx-1].r;
680 // Moving sibling's last child as C[idx]'s first child
681 // TODO: is this correct?
683 Resource lastChild = siblingContent.c[siblingContent.n].r;
684 if (lastChild != null) {
685 childContent.c[0].r = lastChild;
686 setOwner(graph, childContent.c[0].r, bean.c[idx].r, true);
690 // Moving the key from the sibling to the parent
691 // This reduces the number of keys in the sibling
692 bean.key[idx-1].v = siblingContent.key[siblingContent.n-1].v;
693 bean.value[idx-1].r = siblingContent.value[siblingContent.n-1].r;
696 siblingContent.reduceSize();
697 //siblingContent.n -= 1;
699 manager.setContentBean(graph, r, bean);
700 manager.setContentBean(graph, bean.c[idx].r, childContent);
701 manager.setContentBean(graph, bean.c[idx-1].r, siblingContent);
705 // A function to borrow a key from the C[idx+1] and place
707 void borrowFromNext(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {
709 BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);
710 BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx+1].r);
712 // keys[idx] is inserted as the last key in C[idx]
713 childContent.key[childContent.n].v = bean.key[idx].v;
714 childContent.value[childContent.n].r = bean.value[idx].r;
716 // Sibling's first child is inserted as the last child
718 if (!childContent.leaf) {
719 childContent.c[childContent.n+1].r = siblingContent.c[0].r;
720 setOwner(graph, childContent.c[childContent.n+1].r, bean.c[idx].r, true);
723 //The first key from sibling is inserted into keys[idx]
724 bean.key[idx].v = siblingContent.key[0].v;
725 bean.value[idx].r = siblingContent.value[0].r;
727 // Moving all keys in sibling one step behind
728 for (int i=1; i<siblingContent.n; ++i) {
729 siblingContent.key[i-1].v = siblingContent.key[i].v;
730 siblingContent.value[i-1].r = siblingContent.value[i].r;
733 // Moving the child pointers one step behind
734 if (!siblingContent.leaf) {
735 for(int i=1; i<=siblingContent.n; ++i)
736 siblingContent.c[i-1].r = siblingContent.c[i].r;
739 // Increasing and decreasing the key count of C[idx] and C[idx+1]
742 siblingContent.reduceSize();
743 //siblingContent.n -= 1;
745 manager.setContentBean(graph, r, bean);
746 manager.setContentBean(graph, bean.c[idx].r, childContent);
747 manager.setContentBean(graph, bean.c[idx+1].r, siblingContent);
751 // A function to merge C[idx] with C[idx+1]
752 // C[idx+1] is freed after merging
753 void merge(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {
755 BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);
756 BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx+1].r);
758 // Pulling a key from the current node and inserting it into (t-1)th
759 // position of C[idx]
760 childContent.key[t-1].v = bean.key[idx].v;
761 childContent.value[t-1].r = bean.value[idx].r;
763 // Copying the keys from C[idx+1] to C[idx] at the end
764 for (int i=0; i<siblingContent.n; ++i) {
765 childContent.key[i+t].v = siblingContent.key[i].v;
766 childContent.value[i+t].r = siblingContent.value[i].r;
769 // Copying the child pointers from C[idx+1] to C[idx]
770 if (!childContent.leaf) {
771 for(int i=0; i<=siblingContent.n; ++i) {
772 childContent.c[i+t].r = siblingContent.c[i].r;
773 setOwner(graph, childContent.c[i+t].r, bean.c[idx].r, true);
777 // Moving all keys after idx in the current node one step before -
778 // to fill the gap created by moving keys[idx] to C[idx]
779 for (int i=idx+1; i<bean.n; ++i) {
780 bean.key[i-1].v = bean.key[i].v;
781 bean.value[i-1].r = bean.value[i].r;
784 // Remove the owner of the merged sibling
785 removeOwner(graph, bean.c[idx+1].r, true);
787 // Moving the child pointers after (idx+1) in the current node one
789 for (int i=idx+2; i<=bean.n; ++i)
790 bean.c[i-1].r = bean.c[i].r;
792 // Updating the key count of child and the current node
793 childContent.n += siblingContent.n+1;
797 // Freeing the memory occupied by sibling
800 manager.setContentBean(graph, r, bean);
801 manager.setContentBean(graph, bean.c[idx].r, childContent);
805 private void removeOwner(WriteGraph graph, Resource r, boolean force) throws DatabaseException {
806 if((ownerRelation != null) || force) {
810 Resource own = ownerRelation != null ? ownerRelation : DATA.BTreeNode_IsOwnedBy;
816 private void removeFromLeaf(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {
818 // Move all the keys after the idx-th pos one place backward
819 for (int i=idx+1; i<bean.n; ++i) {
820 bean.key[i-1].v = bean.key[i].v;
821 bean.value[i-1].r = bean.value[i].r;
824 // Reduce the count of keys
828 manager.setContentBean(graph, r, bean);
832 private void removeFromNonLeaf(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {
834 Variant k = bean.key[idx].v;
836 // If the child that precedes k (C[idx]) has atleast t keys,
837 // find the predecessor 'pred' of k in the subtree rooted at
838 // C[idx]. Replace k by pred. Recursively delete pred
841 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx].r);
843 if (cContent.n >= t) {
845 Pair<Variant, Resource> pred = getPred(graph, manager, bean, idx);
846 bean.key[idx].v = pred.first;
847 bean.value[idx].r = pred.second;
848 removeImpl(graph, manager, t, bean.c[idx].r, cContent, pred.first);
850 manager.setContentBean(graph, r, bean);
853 BTreeContentBean cContentPlus1 = manager.getContentBean(graph, bean.c[idx+1].r);
855 // If the child C[idx] has less that t keys, examine C[idx+1].
856 // If C[idx+1] has atleast t keys, find the successor 'succ' of k in
857 // the subtree rooted at C[idx+1]
859 // Recursively delete succ in C[idx+1]
860 if (cContentPlus1.n >= t) {
861 Pair<Variant, Resource> succ = getSucc(graph, manager, bean, idx);
862 bean.key[idx].v = succ.first;
863 bean.value[idx].r = succ.second;
864 removeImpl(graph, manager, t, bean.c[idx+1].r, cContentPlus1, succ.first);
866 manager.setContentBean(graph, r, bean);
869 // If both C[idx] and C[idx+1] has less that t keys,merge k and all of C[idx+1]
871 // Now C[idx] contains 2t-1 keys
872 // Free C[idx+1] and recursively delete k from C[idx]
875 merge(graph, manager, r, bean, t, idx);
876 removeImpl(graph, manager, t, bean.c[idx].r, cContent, k);
884 private Resource createNode(WriteGraph graph, BTreeContentManager manager, int t) throws DatabaseException {
885 Layer0 L0 = Layer0.getInstance(graph);
886 Resource result = graph.newResource();
888 graph.claim(result, L0.InstanceOf, null, nodeType);
890 graph.claimLiteral(tree, DATA.BTree_mod, mod, Bindings.LONG);
892 graph.addLiteral(result, L0.HasName, L0.NameOf, ""+mod, Bindings.STRING);
893 manager.setContentBean(graph, result, BTreeContentBean.create(t));
897 public Resource searchNode(ReadGraph graph, Resource x, Variant k) throws DatabaseException {
899 BTreeContentBean xContent = getContentBean(graph, x);
902 while(i <= xContent.n && k.compareTo(xContent.key[i-1].v) > 0) i++;
903 if(i <= xContent.n && k.equals(xContent.key[i-1].v)) return xContent.value[i-1].r;
905 if(xContent.leaf) return null;
906 else return searchNode(graph, xContent.c[i-1].r, k);
910 private void splitChild(WriteGraph graph, BTreeContentManager manager, int t, Resource x, int i, Resource y) throws DatabaseException {
912 Resource z = allocateNode(graph, manager, t);
914 BTreeContentBean xContent = manager.getContentBean(graph, x);
915 BTreeContentBean yContent = manager.getContentBean(graph, y);
916 BTreeContentBean zContent = manager.getContentBean(graph, z);
918 zContent.leaf = yContent.leaf;
921 for(int j=1;j<=t-1;j++) {
922 zContent.key[j-1].v = yContent.key[j+t-1].v;
923 zContent.value[j-1].r = yContent.value[j+t-1].r;
924 setOwner(graph, zContent.value[j-1].r, z, false);
927 for(int j=1;j<=t;j++) {
928 zContent.c[j-1].r = yContent.c[j+t-1].r;
929 setOwner(graph, zContent.c[j-1].r, z, true);
936 for(int j=xContent.n+1;j>=i+1;j--) {
937 xContent.c[j+1-1].r = xContent.c[j-1].r;
940 xContent.c[i+1-1].r = z;
941 setOwner(graph, z, x, true);
943 for(int j=xContent.n;j>=i;j--) {
944 xContent.key[j+1-1].v = xContent.key[j-1].v;
945 xContent.value[j+1-1].r = xContent.value[j-1].r;
948 xContent.key[i-1].v = yContent.key[t-1].v;
949 xContent.value[i-1].r = yContent.value[t-1].r;
952 while (yContent.n > t-1) yContent.reduceSize();
954 setOwner(graph, xContent.value[i-1].r, x, true);
956 manager.setContentBean(graph, x, xContent);
957 manager.setContentBean(graph, y, yContent);
958 manager.setContentBean(graph, z, zContent);
962 private void insertNonfull(WriteGraph graph, BTreeContentManager manager, int t, Resource x, Variant k, Resource v) throws DatabaseException {
964 BTreeContentBean xContent = manager.getContentBean(graph, x);
969 while(i >= 1 && k.compareTo(xContent.key[i-1].v) < 0) {
970 xContent.key[i+1-1].v = xContent.key[i-1].v;
971 xContent.value[i+1-1].r = xContent.value[i-1].r;
975 xContent.key[i+1-1].v = k;
976 xContent.value[i+1-1].r = v;
978 setOwner(graph, v, x, false);
979 manager.setContentBean(graph, x, xContent);
981 while(i >= 1 && k.compareTo(xContent.key[i-1].v) < 0) i--;
983 BTreeContentBean xciContent = manager.getContentBean(graph, xContent.c[i-1].r);
984 if(xciContent.n == 2*t-1) {
985 splitChild(graph, manager, t, x, i, xContent.c[i-1].r);
986 xContent = manager.getContentBean(graph, x);
987 if(k.compareTo(xContent.key[i-1].v) > 0) i++;
989 insertNonfull(graph, manager, t, xContent.c[i-1].r, k, v);
994 private void setOwner(WriteGraph graph, Resource r, Resource owner, boolean force) throws DatabaseException {
996 if((ownerRelation != null) || force) {
997 Resource own = ownerRelation != null ? ownerRelation : DATA.BTreeNode_IsOwnedBy;
999 owners.put(r, owner);
1002 graph.claim(r, own, owner);
1008 private Resource getRoot(ReadGraph graph) throws DatabaseException {
1010 if (root != null) return root;
1012 return graph.getPossibleObject(tree, DATA.BTree_root);
1015 private void setRoot(WriteGraph graph, Resource r) throws DatabaseException {
1019 graph.deny(tree, DATA.BTree_root);
1020 graph.claim(tree, DATA.BTree_root, r);
1024 private Resource allocateNode(WriteGraph graph, BTreeContentManager manager, int t) throws DatabaseException {
1025 return createNode(graph, manager, t);
1028 public void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException {
1030 beans.put(node, bean);
1032 graph.claimLiteral(node, DATA.BTreeNode_content, DATA.BTreeNode_Content, bean, CONTENT_BEAN_BINDING );
1036 public void flushCache(WriteGraph graph) throws DatabaseException {
1039 XSupport xs = graph.getService(XSupport.class);
1040 for(Map.Entry<Resource, BTreeContentBean> entry : beans.entrySet()) {
1041 Resource node = xs.convertDelayedResourceToResource(entry.getKey());
1043 graph.claimLiteral(node, DATA.BTreeNode_content, DATA.BTreeNode_Content, entry.getValue(), CONTENT_BEAN_BINDING );
1047 for(Map.Entry<Resource, Resource> entry : owners.entrySet()) {
1048 Resource r = xs.convertDelayedResourceToResource(entry.getKey());
1049 Resource owner = xs.convertDelayedResourceToResource(entry.getValue());
1050 graph.deny(r, ownerRelation);
1051 if (owner != null) {
1052 graph.claim(r, ownerRelation, owner);
1056 Resource tree2 = xs.convertDelayedResourceToResource(tree);
1057 graph.claimLiteral(tree2, DATA.BTree_mod, mod, Bindings.LONG);
1060 Resource root2 = xs.convertDelayedResourceToResource(root);
1061 graph.deny(tree2, DATA.BTree_root);
1062 graph.claim(tree2, DATA.BTree_root, root2);
1066 public BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException {
1068 BTreeContentBean bean = beans.get(node);
1069 if (bean != null) return bean;
1071 return graph.syncRequest(new RelatedValue<BTreeContentBean>(node, DATA.BTreeNode_content, CONTENT_BEAN_BINDING), TransientCacheListener.<BTreeContentBean>instance());
1074 public List<Tuple2> entries(ReadGraph graph) throws DatabaseException {
1075 Resource r = getRoot(graph);
1076 List<Tuple2> results = new ArrayList<Tuple2>();
1077 return collectEntries(graph, r, null, null, results);
1080 private List<Tuple2> collectEntries(ReadGraph graph, Resource x, Variant min, Variant max, List<Tuple2> results) throws DatabaseException {
1082 BTreeContentBean xContent = getContentBean(graph, x);
1084 for (int i = 0; i < xContent.n + 1; i++) {
1085 if (min != null && i < xContent.n && min.compareTo(xContent.key[i].v) > 0) continue;
1087 if (!xContent.leaf) {
1088 Resource child = xContent.c[i].r;
1089 if (child != null) {
1091 // reduce the amount of comparison if we know that the range of the child keys matches
1092 Variant min2 = (min != null && i > 0 && min.compareTo(xContent.key[i - 1].v) < 0) ? null : min;
1093 Variant max2 = (max != null && i < xContent.n - 1 && max.compareTo(xContent.key[i + 1].v) > 0) ? null : max;
1095 collectEntries(graph, child, min2, max2, results);
1099 if (i < xContent.n) {
1100 if (max != null && max.compareTo(xContent.key[i].v) < 0) return results;
1102 results.add(new Tuple2(xContent.key[i].v, xContent.value[i].r));
1108 public List<Tuple2> searchRange(ReadGraph graph, Variant min, Variant max) throws DatabaseException {
1109 Resource r = getRoot(graph);
1110 List<Tuple2> results = new ArrayList<Tuple2>();
1111 return collectEntries(graph, r, min, max, results);