bundles/org.simantics.datatypes/src/org/simantics/datatypes/utils/BTreeUtils.java

   1 package org.simantics.datatypes.utils;
   2
   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;
  12 import java.util.Map;
  13 import java.util.Set;
  14
  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;
  39
  40 import gnu.trove.list.array.TByteArrayList;
  41 import gnu.trove.map.hash.TObjectIntHashMap;
  42
  43 /*
  44  * Implementation from http://www.geeksforgeeks.org/b-tree-set-3delete/
  45  *
  46  */
  47
  48 interface BTreeContentManager {
  49
  50         BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException;
  51         void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException;
  52
  53 }
  54
  55 class PossibleVariantInputStream extends ByteArrayInputStream {
  56
  57         PossibleVariantInputStream(byte[] data, int offset) {
  58                 super(data, offset, data.length-offset);
  59         }
  60
  61         public int getOffset() {
  62                 return pos;
  63         }
  64
  65 }
  66
  67 class BTreeContentBinding extends Binding {
  68
  69         private final SerialisationSupport ss;
  70         private final XSupport xs;
  71
  72         public BTreeContentBinding(SerialisationSupport ss, XSupport xs) {
  73                 this.ss = ss;
  74                 this.xs = xs;
  75         }
  76
  77         private final Serializer serializer = new Serializer() {
  78
  79                 @Override
  80                 public void serialize(DataOutput out, TObjectIntHashMap<Object> identities, Object obj) throws IOException {
  81                         throw new UnsupportedOperationException();
  82                 }
  83
  84                 @Override
  85                 public void serialize(DataOutput out, Object obj) throws IOException {
  86                         byte[] data = serialize(obj);
  87                         out.write(data);
  88                 }
  89
  90                 @Override
  91                 public Object deserialize(DataInput in, List<Object> identities)
  92                                 throws IOException {
  93                         throw new UnsupportedOperationException();
  94                 }
  95
  96                 @Override
  97                 public Object deserialize(DataInput in) throws IOException {
  98                         throw new UnsupportedOperationException();
  99                 }
 100
 101                 @Override
 102                 public void deserializeTo(DataInput in, List<Object> identities,
 103                                 Object dst) throws IOException {
 104                         throw new UnsupportedOperationException();
 105                 }
 106
 107                 @Override
 108                 public void deserializeTo(DataInput in, Object dst) throws IOException {
 109                         throw new UnsupportedOperationException();
 110                 }
 111
 112                 @Override
 113                 public void skip(DataInput in, List<Object> identities)
 114                                 throws IOException {
 115                         throw new UnsupportedOperationException();
 116                 }
 117
 118                 @Override
 119                 public void skip(DataInput in) throws IOException {
 120                         throw new UnsupportedOperationException();
 121                 }
 122
 123                 @Override
 124                 public Integer getConstantSize() {
 125                         throw new UnsupportedOperationException();
 126                 }
 127
 128                 @Override
 129                 public int getSize(Object obj, TObjectIntHashMap<Object> identities)
 130                                 throws IOException {
 131                         throw new UnsupportedOperationException();
 132                 }
 133
 134                 @Override
 135                 public int getSize(Object obj) throws IOException {
 136                         return serialize(obj).length;
 137                 }
 138
 139                 @Override
 140                 public int getMinSize() {
 141                         throw new UnsupportedOperationException();
 142                 }
 143
 144                 private void addBE(TByteArrayList bytes, int value) {
 145
 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));
 150
 151                 }
 152
 153                 private void addBE(TByteArrayList bytes, long value) {
 154
 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));
 163
 164                 }
 165
 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);
 177                                 bytes.add(ser);
 178                         }
 179                         addBE(bytes, bean.value.length);
 180                         for(PossibleResource pr : bean.value) {
 181                                 if(pr.r != null) {
 182                                         bytes.add((byte)1);
 183                                         addBE(bytes, xs.convertDelayedResourceToResource(pr.r).getResourceId());
 184                                 } else {
 185                                         bytes.add((byte)0);
 186                                 }
 187                         }
 188                         addBE(bytes, bean.c.length);
 189                         for(PossibleResource pr : bean.c) {
 190                                 if(pr.r != null) {
 191                                         bytes.add((byte)1);
 192                                         addBE(bytes, xs.convertDelayedResourceToResource(pr.r).getResourceId());
 193                                 } else {
 194                                         bytes.add((byte)0);
 195                                 }
 196                         }
 197                         return bytes.toArray();
 198                 }
 199
 200                 int readBE4(byte[] bytes, int byteIndex) {
 201                         int result = (int)
 202                                 (((int)(bytes[byteIndex++] & 0xff))<<24) |
 203                                         (((int)(bytes[byteIndex++] & 0xff))<<16) |
 204                                         (((int)(bytes[byteIndex++] & 0xff))<<8) |
 205                                 (((int)(bytes[byteIndex++] & 0xff)));
 206                         return result;
 207                 }
 208
 209                 long readBE8(byte[] bytes, int byteIndex) {
 210                         long result = (long)
 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)));
 219                         return result;
 220                 }
 221
 222                 public Object deserialize(byte[] data) throws IOException {
 223
 224                         BTreeContentBean result = new BTreeContentBean();
 225
 226                         try {
 227
 228                                 result.leaf = (data[0] == 1) ? true : false;
 229                                 int byteIndex = 1;
 230                                 result.n = readBE4(data, byteIndex);
 231                                 byteIndex += 4;
 232
 233                                 Binding pbv = PossibleVariant.BINDING;
 234                                 Serializer pbs = pbv.serializer();
 235
 236                                 // Redundant array size
 237                                 int keySize = readBE4(data, byteIndex);
 238                                 result.key = new PossibleVariant[keySize];
 239                                 byteIndex += 4;
 240                                 for(int i=0;i<keySize;i++) {
 241                                         PossibleVariantInputStream is = new PossibleVariantInputStream(data, byteIndex);
 242                                         PossibleVariant v = (PossibleVariant)pbs.deserialize(is);
 243                                         result.key[i] = v;
 244                                         byteIndex = is.getOffset();
 245                                 }
 246
 247                                 // Redundant array size
 248                                 int valueSize = readBE4(data, byteIndex);
 249                                 result.value = new PossibleResource[valueSize];
 250                                 byteIndex += 4;
 251                                 for(int i=0;i<valueSize;i++) {
 252                                         boolean has = Bytes.read(data, byteIndex++) > 0;
 253                                         if(has) {
 254                                                 result.value[i] = PossibleResource.read(ss, readBE8(data, byteIndex));
 255                                                 byteIndex += 8;
 256                                         } else {
 257                                                 result.value[i] = new PossibleResource();
 258                                         }
 259                                 }
 260
 261                                 // Redundant array size
 262                                 int childSize = readBE4(data, byteIndex);
 263                                 result.c = new PossibleResource[childSize];
 264                                 byteIndex += 4;
 265                                 for(int i=0;i<childSize;i++) {
 266                                         boolean has = Bytes.read(data, byteIndex++) > 0;
 267                                         if(has) {
 268                                                 result.c[i] = PossibleResource.read(ss, readBE8(data, byteIndex));
 269                                                 byteIndex += 8;
 270                                         } else {
 271                                                 result.c[i] = new PossibleResource();
 272                                         }
 273                                 }
 274
 275                         } catch (DatabaseException e) {
 276
 277                                 e.printStackTrace();
 278
 279                         }
 280
 281                         return result;
 282
 283                 }
 284
 285         };
 286
 287         @Override
 288         public void accept(Visitor1 v, Object obj) {
 289                 throw new UnsupportedOperationException();
 290         }
 291
 292         @Override
 293         public <T> T accept(Visitor<T> v) {
 294                 throw new UnsupportedOperationException();
 295         }
 296
 297         @Override
 298         public boolean isInstance(Object obj) {
 299                 throw new UnsupportedOperationException();
 300         }
 301
 302         @Override
 303         public void readFrom(Binding srcBinding, Object src, Object dst)
 304                         throws BindingException {
 305                 throw new UnsupportedOperationException();
 306         }
 307
 308         @Override
 309         public void assertInstaceIsValid(Object obj, Set<Object> validInstances)
 310                         throws BindingException {
 311                 throw new UnsupportedOperationException();
 312         }
 313
 314         @Override
 315         public int deepHashValue(Object value,
 316                         IdentityHashMap<Object, Object> hashedObjects)
 317                         throws BindingException {
 318                 throw new UnsupportedOperationException();
 319         }
 320
 321         @Override
 322         public int deepCompare(Object o1, Object o2,
 323                         Set<IdentityPair<Object, Object>> compareHistory)
 324                         throws BindingException {
 325                 throw new UnsupportedOperationException();
 326         }
 327
 328         @Override
 329         protected void toString(Object value, BindingPrintContext ctx)
 330                         throws BindingException {
 331                 throw new UnsupportedOperationException();
 332         }
 333
 334         @Override
 335         public int getComponentCount() {
 336                 throw new UnsupportedOperationException();
 337         }
 338
 339         @Override
 340         public Binding getComponentBinding(int index) {
 341                 throw new UnsupportedOperationException();
 342         }
 343
 344         @Override
 345         public Binding getComponentBinding(ChildReference path) {
 346                 throw new UnsupportedOperationException();
 347         }
 348
 349         @Override
 350         public Serializer serializer() throws RuntimeSerializerConstructionException {
 351                 return serializer;
 352         }
 353
 354 }
 355
 356 final public class BTreeUtils implements BTreeContentManager {
 357
 358         final private Resource tree;
 359         final private Resource ownerRelation;
 360
 361         final public Binding CONTENT_BEAN_BINDING;
 362         final public DatatypeResource DATA;
 363
 364         private long mod;
 365         private int t;
 366         private Map<Resource, BTreeContentBean> beans;
 367         private Map<Resource, Resource> owners;
 368         private Resource root;
 369         private Resource nodeType;
 370         private boolean cached;
 371
 372         public BTreeUtils(ReadGraph graph, Resource tree, int t, Resource nodeType, Resource ownerRelation, boolean cached) throws DatabaseException {
 373                 try {
 374                         SerialisationSupport ss = graph.getService(SerialisationSupport.class);
 375                         XSupport xs = graph.getService(XSupport.class);
 376
 377                         CONTENT_BEAN_BINDING = new BTreeContentBinding(ss, xs);
 378                         DATA = DatatypeResource.getInstance(graph);
 379                         this.tree = tree;
 380                         this.ownerRelation = ownerRelation;
 381                         this.nodeType = nodeType != null ? nodeType : DATA.BTreeNode;
 382                         this.t = t;
 383                         Long possibleMod = graph.getPossibleRelatedValue(tree, DATA.BTree_mod, Bindings.LONG);
 384                         this.mod = possibleMod != null ? possibleMod : 0;
 385                         this.cached = cached;
 386                         if (cached) {
 387                                 this.beans = new HashMap<Resource, BTreeContentBean>();
 388                                 this.owners = new HashMap<Resource, Resource>();
 389                         }
 390                 } catch (RuntimeBindingConstructionException e) {
 391                         Logger.defaultLogError(e);
 392                         throw new DatabaseException(e);
 393                 }
 394         }
 395
 396         public static BTreeUtils create(WriteGraph graph, Resource ownerRelation, int t, boolean cached) throws DatabaseException {
 397
 398                 DatatypeResource DATA = DatatypeResource.getInstance(graph);
 399                 return create(graph, DATA.BTree, DATA.BTreeNode, ownerRelation, t, cached);
 400
 401         }
 402
 403         public static BTreeUtils create(WriteGraph graph, Resource type, Resource nodeType, Resource ownerRelation, int t, boolean cached) throws DatabaseException {
 404
 405                 Layer0 L0 = Layer0.getInstance(graph);
 406                 DatatypeResource DATA = DatatypeResource.getInstance(graph);
 407                 Resource tree = graph.newResource();
 408                 graph.claim(tree, L0.InstanceOf, null, type);
 409
 410                 if(ownerRelation != null)
 411                         graph.claim(tree, DATA.BTree_HasOwnerRelation, DATA.BTree_HasOwnerRelation_Inverse, ownerRelation);
 412                 if(nodeType != null)
 413                         graph.claim(tree, DATA.BTree_HasNodeType, DATA.BTree_HasNodeType_Inverse, nodeType);
 414
 415                 graph.claimLiteral(tree, DATA.BTree_t, t, Bindings.INTEGER);
 416
 417                 if (!cached) {
 418                         graph.claimLiteral(tree, DATA.BTree_mod, 0L, Bindings.LONG);
 419                 }
 420
 421                 BTreeUtils utils = new BTreeUtils(graph, tree, t, nodeType, ownerRelation, cached);
 422                 Resource node = utils.createNode(graph, utils, t);
 423                 utils.setRoot(graph, node);
 424                 utils.setOwner(graph, node, tree, true);
 425
 426                 return utils;
 427         }
 428
 429         public Resource getTree() {
 430                 return tree;
 431         }
 432
 433         public void insert(WriteGraph graph, Variant k, Resource v) throws DatabaseException {
 434
 435                 Resource r = getRoot(graph);
 436                 insertImpl(graph, this, r, t, k, v);
 437
 438         }
 439
 440         static class BatchContentManager implements BTreeContentManager {
 441
 442                 final private BTreeUtils bu;
 443
 444                 final Map<Resource, BTreeContentBean> beans = new HashMap<Resource, BTreeContentBean>();
 445
 446                 public BatchContentManager(BTreeUtils bu) {
 447                         this.bu = bu;
 448                 }
 449
 450                 @Override
 451                 public BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException {
 452                         BTreeContentBean bean = beans.get(node);
 453                         if(bean != null) return bean;
 454                         return bu.getContentBean(graph, node);
 455                 }
 456
 457                 @Override
 458                 public void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException {
 459                         beans.put(node, bean);
 460                 }
 461
 462                 public void apply(WriteGraph graph) throws DatabaseException {
 463                         for(Map.Entry<Resource, BTreeContentBean> entry : beans.entrySet()) {
 464                                 bu.setContentBean(graph, entry.getKey(), entry.getValue());
 465                         }
 466                 }
 467
 468         }
 469
 470         public void insertAll(WriteGraph graph, Collection<Pair<Variant, Resource>> values) throws DatabaseException {
 471
 472                 Resource r = getRoot(graph);
 473                 BatchContentManager cm = new BatchContentManager(this);
 474                 for(Pair<Variant, Resource> entry : values) {
 475                         insertImpl(graph, cm, r, t, entry.first, entry.second);
 476                 }
 477                 cm.apply(graph);
 478
 479         }
 480
 481         public Resource search(ReadGraph graph, Variant k) throws DatabaseException {
 482
 483                 Resource r = getRoot(graph);
 484                 return searchNode(graph, r, k);
 485
 486         }
 487
 488         // Implementation
 489
 490         private int findKey(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, Variant k) throws DatabaseException {
 491
 492                 int idx = 0;
 493                 while(idx<bean.n && bean.key[idx].v.compareTo(k) < 0)
 494                         idx++;
 495                 return idx;
 496
 497         }
 498
 499         private void insertImpl(WriteGraph graph, BTreeContentManager manager, Resource r, int t, Variant k, Resource v) throws DatabaseException {
 500
 501                 BTreeContentBean rContent = manager.getContentBean(graph, r);
 502                 if(rContent.n == 2*t-1) {
 503                         Resource s = allocateNode(graph, manager, t);
 504                         BTreeContentBean sContent = manager.getContentBean(graph, s);
 505                         setRoot(graph, s);
 506                         setOwner(graph, s, tree, true);
 507                         sContent.leaf = false;
 508                         sContent.n = 0;
 509                         sContent.c[0].r = r;
 510                         setOwner(graph, r, s, true);
 511                         manager.setContentBean(graph, s, sContent);
 512                         splitChild(graph, manager, t, s, 1, r);
 513                         insertNonfull(graph, manager, t, s, k, v);
 514                 } else {
 515                         insertNonfull(graph, manager, t, r, k, v);
 516                 }
 517
 518         }
 519
 520         public void remove(WriteGraph graph, Variant k) throws DatabaseException {
 521
 522                 Resource r = getRoot(graph);
 523
 524                 BTreeContentBean bean = getContentBean(graph, r);
 525                 Resource removedResource = removeImpl(graph, this, t, r, bean, k);
 526                 if (removedResource != null) {
 527                         removeOwner(graph, removedResource, false);
 528
 529                     // If the root node has 0 keys, make its first child as the new root
 530                     //  if it has a child, otherwise set root as NULL
 531                     if (bean.n==0)
 532                     {
 533                         //BTreeContentBean tmp = bean;
 534                         if (!bean.leaf) {
 535                                 removeOwner(graph, r, true);
 536                                 setRoot(graph, bean.c[0].r);
 537                                 setOwner(graph, bean.c[0].r, tree, true);
 538                         }
 539
 540                         // Free the old root
 541                         //delete tmp;
 542
 543                     }
 544                 }
 545
 546
 547         }
 548
 549         public Resource removeImpl(WriteGraph graph, BTreeContentManager manager, int t, Resource r, BTreeContentBean bean, Variant k) throws DatabaseException {
 550
 551                 int idx = findKey(graph, manager, bean, k);
 552
 553                 if(idx < bean.n && bean.key[idx].v.equals(k)) {
 554                         Resource removedResource = bean.value[idx].r;
 555                         if(bean.leaf)
 556                                 removeFromLeaf(graph, manager, r, bean, idx);
 557                         else
 558                                 removeFromNonLeaf(graph, manager, r, bean, t, idx);
 559
 560                         return removedResource;
 561                 } else {
 562
 563                 if (bean.leaf) {
 564                         return null;
 565                 }
 566
 567                 // The key to be removed is present in the sub-tree rooted with this node
 568                 // The flag indicates whether the key is present in the sub-tree rooted
 569                 // with the last child of this node
 570                 boolean flag = ( (idx==bean.n)? true : false );
 571
 572                 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx].r);
 573
 574                 // If the child where the key is supposed to exist has less that t keys,
 575                 // we fill that child
 576                 if (cContent.n < t)
 577                     fill(graph, manager, r, bean, t, idx);
 578
 579                 // If the last child has been merged, it must have merged with the previous
 580                 // child and so we recurse on the (idx-1)th child. Else, we recurse on the
 581                 // (idx)th child which now has atleast t keys
 582                 if (flag && idx > bean.n)
 583                         return removeImpl(graph, manager, t, bean.c[idx-1].r, manager.getContentBean(graph, bean.c[idx-1].r), k);
 584                 else
 585                         return removeImpl(graph, manager, t, bean.c[idx].r, cContent, k);
 586
 587                 }
 588
 589
 590         }
 591
 592         // A function to get predecessor of keys[idx]
 593         Pair<Variant, Resource> getPred(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, int idx) throws DatabaseException {
 594
 595             // Keep moving to the right most node until we reach a leaf
 596         bean = manager.getContentBean(graph, bean.c[idx].r);
 597             while (!bean.leaf)
 598                 bean = manager.getContentBean(graph, bean.c[bean.n].r);
 599
 600             // Return the last key of the leaf
 601             return new Pair<Variant, Resource>(bean.key[bean.n-1].v, bean.value[bean.n-1].r);
 602
 603         }
 604
 605         Pair<Variant, Resource> getSucc(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, int idx) throws DatabaseException {
 606
 607             // Keep moving the left most node starting from C[idx+1] until we reach a leaf
 608         bean = manager.getContentBean(graph, bean.c[idx+1].r);
 609             while (!bean.leaf)
 610                 bean = manager.getContentBean(graph, bean.c[0].r);
 611
 612             // Return the first key of the leaf
 613             return new Pair<Variant, Resource>(bean.key[0].v, bean.value[0].r);
 614
 615         }
 616
 617         // A function to fill child C[idx] which has less than t-1 keys
 618         void fill(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {
 619
 620             // If the previous child(C[idx-1]) has more than t-1 keys, borrow a key
 621             // from that child
 622             if (idx!=0) {
 623                 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx-1].r);
 624
 625                 if (cContent.n>=t) {
 626                         borrowFromPrev(graph, manager, r, bean, idx);
 627                         return;
 628                 }
 629             }
 630
 631         // If the next child(C[idx+1]) has more than t-1 keys, borrow a key
 632         // from that child
 633
 634             if (idx!=bean.n) {
 635                 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx+1].r);
 636
 637                 if (cContent.n>=t) {
 638                         borrowFromNext(graph, manager, r, bean, idx);
 639                         return;
 640                 }
 641             }
 642
 643         // Merge C[idx] with its sibling
 644         // If C[idx] is the last child, merge it with with its previous sibling
 645         // Otherwise merge it with its next sibling
 646                 if (idx != bean.n)
 647                         merge(graph, manager, r, bean, t, idx);
 648                 else
 649                         merge(graph, manager, r, bean, t, idx-1);
 650         }
 651
 652         // A function to borrow a key from C[idx-1] and insert it
 653         // into C[idx]
 654         void borrowFromPrev(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {
 655
 656         BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);
 657         BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx-1].r);
 658
 659             // The last key from C[idx-1] goes up to the parent and key[idx-1]
 660             // from parent is inserted as the first key in C[idx]. Thus, the  loses
 661             // sibling one key and child gains one key
 662
 663             // Moving all key in C[idx] one step ahead
 664             for (int i=childContent.n-1; i>=0; --i) {
 665                 childContent.key[i+1].v = childContent.key[i].v;
 666                 childContent.value[i+1].r = childContent.value[i].r;
 667             }
 668
 669             // If C[idx] is not a leaf, move all its child pointers one step ahead
 670             if (!childContent.leaf) {
 671                 for(int i=childContent.n; i>=0; --i) {
 672                     childContent.c[i+1].r = childContent.c[i].r;
 673                                 setOwner(graph, childContent.c[i+1].r, bean.c[idx].r, true);
 674                 }
 675             }
 676
 677             // Setting child's first key equal to keys[idx-1] from the current node
 678             childContent.key[0].v = bean.key[idx-1].v;
 679             childContent.value[0].r = bean.value[idx-1].r;
 680
 681             // Moving sibling's last child as C[idx]'s first child
 682             // TODO: is this correct?
 683             if (!bean.leaf) {
 684                 Resource lastChild = siblingContent.c[siblingContent.n].r;
 685                 if (lastChild != null) {
 686                         childContent.c[0].r = lastChild;
 687                                 setOwner(graph, childContent.c[0].r, bean.c[idx].r, true);
 688                 }
 689             }
 690
 691             // Moving the key from the sibling to the parent
 692             // This reduces the number of keys in the sibling
 693             bean.key[idx-1].v = siblingContent.key[siblingContent.n-1].v;
 694             bean.value[idx-1].r = siblingContent.value[siblingContent.n-1].r;
 695
 696             childContent.n += 1;
 697             siblingContent.reduceSize();
 698             //siblingContent.n -= 1;
 699
 700             manager.setContentBean(graph, r, bean);
 701             manager.setContentBean(graph, bean.c[idx].r, childContent);
 702             manager.setContentBean(graph, bean.c[idx-1].r, siblingContent);
 703
 704         }
 705
 706         // A function to borrow a key from the C[idx+1] and place
 707         // it in C[idx]
 708         void borrowFromNext(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {
 709
 710         BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);
 711         BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx+1].r);
 712
 713             // keys[idx] is inserted as the last key in C[idx]
 714         childContent.key[childContent.n].v = bean.key[idx].v;
 715         childContent.value[childContent.n].r = bean.value[idx].r;
 716
 717             // Sibling's first child is inserted as the last child
 718             // into C[idx]
 719             if (!childContent.leaf) {
 720                 childContent.c[childContent.n+1].r = siblingContent.c[0].r;
 721                         setOwner(graph, childContent.c[childContent.n+1].r, bean.c[idx].r, true);
 722             }
 723
 724             //The first key from sibling is inserted into keys[idx]
 725             bean.key[idx].v = siblingContent.key[0].v;
 726             bean.value[idx].r = siblingContent.value[0].r;
 727
 728             // Moving all keys in sibling one step behind
 729             for (int i=1; i<siblingContent.n; ++i) {
 730                 siblingContent.key[i-1].v = siblingContent.key[i].v;
 731                 siblingContent.value[i-1].r = siblingContent.value[i].r;
 732             }
 733
 734             // Moving the child pointers one step behind
 735             if (!siblingContent.leaf) {
 736                 for(int i=1; i<=siblingContent.n; ++i)
 737                         siblingContent.c[i-1].r = siblingContent.c[i].r;
 738             }
 739
 740             // Increasing and decreasing the key count of C[idx] and C[idx+1]
 741             // respectively
 742             childContent.n += 1;
 743             siblingContent.reduceSize();
 744             //siblingContent.n -= 1;
 745
 746             manager.setContentBean(graph, r, bean);
 747             manager.setContentBean(graph, bean.c[idx].r, childContent);
 748             manager.setContentBean(graph, bean.c[idx+1].r, siblingContent);
 749
 750         }
 751
 752         // A function to merge C[idx] with C[idx+1]
 753         // C[idx+1] is freed after merging
 754         void merge(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {
 755
 756         BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);
 757         BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx+1].r);
 758
 759             // Pulling a key from the current node and inserting it into (t-1)th
 760             // position of C[idx]
 761         childContent.key[t-1].v = bean.key[idx].v;
 762         childContent.value[t-1].r = bean.value[idx].r;
 763
 764             // Copying the keys from C[idx+1] to C[idx] at the end
 765             for (int i=0; i<siblingContent.n; ++i) {
 766                 childContent.key[i+t].v = siblingContent.key[i].v;
 767                 childContent.value[i+t].r = siblingContent.value[i].r;
 768             }
 769
 770             // Copying the child pointers from C[idx+1] to C[idx]
 771             if (!childContent.leaf) {
 772                 for(int i=0; i<=siblingContent.n; ++i) {
 773                         childContent.c[i+t].r = siblingContent.c[i].r;
 774                                 setOwner(graph, childContent.c[i+t].r, bean.c[idx].r, true);
 775                 }
 776             }
 777
 778             // Moving all keys after idx in the current node one step before -
 779             // to fill the gap created by moving keys[idx] to C[idx]
 780             for (int i=idx+1; i<bean.n; ++i) {
 781                 bean.key[i-1].v = bean.key[i].v;
 782                 bean.value[i-1].r = bean.value[i].r;
 783             }
 784
 785         // Remove the owner of the merged sibling
 786         removeOwner(graph, bean.c[idx+1].r, true);
 787
 788             // Moving the child pointers after (idx+1) in the current node one
 789             // step before
 790             for (int i=idx+2; i<=bean.n; ++i)
 791                 bean.c[i-1].r = bean.c[i].r;
 792
 793             // Updating the key count of child and the current node
 794             childContent.n += siblingContent.n+1;
 795             bean.reduceSize();
 796             //bean.n--;
 797
 798             // Freeing the memory occupied by sibling
 799             // delete(sibling);
 800
 801             manager.setContentBean(graph, r, bean);
 802             manager.setContentBean(graph, bean.c[idx].r, childContent);
 803
 804         }
 805
 806         private void removeOwner(WriteGraph graph, Resource r, boolean force) throws DatabaseException {
 807                 if((ownerRelation != null) || force) {
 808                         if (cached) {
 809                                 owners.put(r, null);
 810                         } else {
 811                                 Resource own = ownerRelation != null ? ownerRelation : DATA.BTreeNode_IsOwnedBy;
 812                                 graph.deny(r, own);
 813                         }
 814                 }
 815         }
 816
 817         private void removeFromLeaf(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {
 818
 819             // Move all the keys after the idx-th pos one place backward
 820             for (int i=idx+1; i<bean.n; ++i) {
 821                 bean.key[i-1].v = bean.key[i].v;
 822                 bean.value[i-1].r = bean.value[i].r;
 823             }
 824
 825             // Reduce the count of keys
 826             bean.reduceSize();
 827             //bean.n--;
 828
 829             manager.setContentBean(graph, r, bean);
 830
 831         }
 832
 833         private void removeFromNonLeaf(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {
 834
 835                 Variant k = bean.key[idx].v;
 836
 837                 // If the child that precedes k (C[idx]) has atleast t keys,
 838                 // find the predecessor 'pred' of k in the subtree rooted at
 839                 // C[idx]. Replace k by pred. Recursively delete pred
 840                 // in C[idx]
 841
 842         BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx].r);
 843
 844                 if (cContent.n >= t) {
 845
 846                         Pair<Variant, Resource> pred = getPred(graph, manager, bean, idx);
 847                         bean.key[idx].v = pred.first;
 848                         bean.value[idx].r = pred.second;
 849                         removeImpl(graph, manager, t, bean.c[idx].r, cContent, pred.first);
 850
 851                         manager.setContentBean(graph, r, bean);
 852                 } else {
 853
 854                 BTreeContentBean cContentPlus1 = manager.getContentBean(graph, bean.c[idx+1].r);
 855
 856                         // If the child C[idx] has less that t keys, examine C[idx+1].
 857                         // If C[idx+1] has atleast t keys, find the successor 'succ' of k in
 858                         // the subtree rooted at C[idx+1]
 859                         // Replace k by succ
 860                         // Recursively delete succ in C[idx+1]
 861                         if (cContentPlus1.n >= t) {
 862                                 Pair<Variant, Resource> succ = getSucc(graph, manager, bean, idx);
 863                                 bean.key[idx].v = succ.first;
 864                                 bean.value[idx].r = succ.second;
 865                                 removeImpl(graph, manager, t, bean.c[idx+1].r, cContentPlus1, succ.first);
 866
 867                                 manager.setContentBean(graph, r, bean);
 868                         }
 869
 870                         // If both C[idx] and C[idx+1] has less that t keys,merge k and all of C[idx+1]
 871                         // into C[idx]
 872                         // Now C[idx] contains 2t-1 keys
 873                         // Free C[idx+1] and recursively delete k from C[idx]
 874                         else {
 875
 876                                 merge(graph, manager, r, bean, t, idx);
 877                                 removeImpl(graph, manager, t, bean.c[idx].r, cContent, k);
 878
 879                         }
 880
 881                 }
 882
 883         }
 884
 885         private Resource createNode(WriteGraph graph, BTreeContentManager manager, int t) throws DatabaseException {
 886                 Layer0 L0 = Layer0.getInstance(graph);
 887                 Resource result = graph.newResource();
 888                 mod++;
 889                 graph.claim(result, L0.InstanceOf, null, nodeType);
 890                 if (!cached) {
 891                         graph.claimLiteral(tree, DATA.BTree_mod, mod, Bindings.LONG);
 892                 }
 893                 graph.addLiteral(result, L0.HasName, L0.NameOf, ""+mod, Bindings.STRING);
 894                 manager.setContentBean(graph, result, BTreeContentBean.create(t));
 895                 return result;
 896         }
 897
 898         public Resource searchNode(ReadGraph graph, Resource x, Variant k) throws DatabaseException {
 899
 900                 BTreeContentBean xContent = getContentBean(graph, x);
 901
 902                 int i=1;
 903                 while(i <= xContent.n && k.compareTo(xContent.key[i-1].v) > 0) i++;
 904                 if(i <= xContent.n && k.equals(xContent.key[i-1].v)) return xContent.value[i-1].r;
 905
 906                 if(xContent.leaf) return null;
 907                 else return searchNode(graph, xContent.c[i-1].r, k);
 908
 909         }
 910
 911         private void splitChild(WriteGraph graph, BTreeContentManager manager, int t, Resource x, int i, Resource y) throws DatabaseException {
 912
 913                 Resource z = allocateNode(graph, manager, t);
 914
 915                 BTreeContentBean xContent = manager.getContentBean(graph, x);
 916                 BTreeContentBean yContent = manager.getContentBean(graph, y);
 917                 BTreeContentBean zContent = manager.getContentBean(graph, z);
 918
 919                 zContent.leaf = yContent.leaf;
 920                 zContent.n = t-1;
 921
 922                 for(int j=1;j<=t-1;j++) {
 923                         zContent.key[j-1].v = yContent.key[j+t-1].v;
 924                         zContent.value[j-1].r = yContent.value[j+t-1].r;
 925                         setOwner(graph, zContent.value[j-1].r, z, false);
 926                 }
 927                 if(!yContent.leaf) {
 928                         for(int j=1;j<=t;j++) {
 929                                 zContent.c[j-1].r = yContent.c[j+t-1].r;
 930                                 setOwner(graph, zContent.c[j-1].r, z, true);
 931                         }
 932                 }
 933
 934                 //yContent.n = t-1;
 935
 936
 937                 for(int j=xContent.n+1;j>=i+1;j--) {
 938                         xContent.c[j+1-1].r = xContent.c[j-1].r;
 939                 }
 940
 941                 xContent.c[i+1-1].r = z;
 942                 setOwner(graph, z, x, true);
 943
 944                 for(int j=xContent.n;j>=i;j--) {
 945                         xContent.key[j+1-1].v = xContent.key[j-1].v;
 946                         xContent.value[j+1-1].r = xContent.value[j-1].r;
 947                 }
 948
 949                 xContent.key[i-1].v = yContent.key[t-1].v;
 950                 xContent.value[i-1].r = yContent.value[t-1].r;
 951                 xContent.n++;
 952
 953                 while (yContent.n > t-1) yContent.reduceSize();
 954
 955                 setOwner(graph, xContent.value[i-1].r, x, true);
 956
 957                 manager.setContentBean(graph, x, xContent);
 958                 manager.setContentBean(graph, y, yContent);
 959                 manager.setContentBean(graph, z, zContent);
 960
 961         }
 962
 963         private void insertNonfull(WriteGraph graph, BTreeContentManager manager, int t, Resource x, Variant k, Resource v) throws DatabaseException {
 964
 965                 BTreeContentBean xContent = manager.getContentBean(graph, x);
 966
 967                 int i = xContent.n;
 968
 969                 if(xContent.leaf) {
 970                         while(i >= 1 && k.compareTo(xContent.key[i-1].v) < 0) {
 971                                 xContent.key[i+1-1].v = xContent.key[i-1].v;
 972                                 xContent.value[i+1-1].r = xContent.value[i-1].r;
 973                                 i--;
 974                         }
 975
 976                         xContent.key[i+1-1].v = k;
 977                         xContent.value[i+1-1].r = v;
 978                         xContent.n++;
 979                         setOwner(graph, v, x, false);
 980                         manager.setContentBean(graph, x, xContent);
 981                 } else {
 982                         while(i >= 1 && k.compareTo(xContent.key[i-1].v) < 0) i--;
 983                         i++;
 984                         BTreeContentBean xciContent = manager.getContentBean(graph, xContent.c[i-1].r);
 985                         if(xciContent.n == 2*t-1) {
 986                                 splitChild(graph, manager, t, x, i, xContent.c[i-1].r);
 987                                 xContent = manager.getContentBean(graph, x);
 988                                 if(k.compareTo(xContent.key[i-1].v) > 0) i++;
 989                         }
 990                         insertNonfull(graph, manager, t, xContent.c[i-1].r, k, v);
 991                 }
 992
 993         }
 994
 995         private void setOwner(WriteGraph graph, Resource r, Resource owner, boolean force) throws DatabaseException {
 996                 if (r != null) {
 997                         if((ownerRelation != null) || force) {
 998                                 Resource own = ownerRelation != null ? ownerRelation : DATA.BTreeNode_IsOwnedBy;
 999                                 if (cached) {
1000                                         owners.put(r, owner);
1001                                 } else {
1002                                         graph.deny(r, own);
1003                                         graph.claim(r, own, owner);
1004                                 }
1005                         }
1006                 }
1007         }
1008
1009         private Resource getRoot(ReadGraph graph) throws DatabaseException {
1010                 if (cached) {
1011                         if (root != null) return root;
1012                 }
1013                 return graph.getPossibleObject(tree, DATA.BTree_root);
1014         }
1015
1016         private void setRoot(WriteGraph graph, Resource r) throws DatabaseException {
1017                 if (cached) {
1018                         this.root = r;
1019                 } else {
1020                         graph.deny(tree, DATA.BTree_root);
1021                         graph.claim(tree, DATA.BTree_root, r);
1022                 }
1023         }
1024
1025         private Resource allocateNode(WriteGraph graph, BTreeContentManager manager, int t) throws DatabaseException {
1026                 return createNode(graph, manager, t);
1027         }
1028
1029         public void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException {
1030                 if (cached) {
1031                         beans.put(node, bean);
1032                 } else {
1033                         graph.claimLiteral(node, DATA.BTreeNode_content, DATA.BTreeNode_Content, bean, CONTENT_BEAN_BINDING );
1034                 }
1035         }
1036
1037         public void flushCache(WriteGraph graph) throws DatabaseException {
1038                 assert(cached);
1039
1040                 XSupport xs = graph.getService(XSupport.class);
1041                 for(Map.Entry<Resource, BTreeContentBean> entry : beans.entrySet()) {
1042                         Resource node = xs.convertDelayedResourceToResource(entry.getKey());
1043                         if (node != null) {
1044                                 graph.claimLiteral(node, DATA.BTreeNode_content, DATA.BTreeNode_Content, entry.getValue(), CONTENT_BEAN_BINDING );
1045                         }
1046                 }
1047
1048                 for(Map.Entry<Resource, Resource> entry : owners.entrySet()) {
1049                         Resource r = xs.convertDelayedResourceToResource(entry.getKey());
1050                         Resource owner = xs.convertDelayedResourceToResource(entry.getValue());
1051                         graph.deny(r, ownerRelation);
1052                         if (owner != null) {
1053                                 graph.claim(r, ownerRelation, owner);
1054                         }
1055                 }
1056
1057                 Resource tree2 = xs.convertDelayedResourceToResource(tree);
1058                 graph.claimLiteral(tree2, DATA.BTree_mod, mod, Bindings.LONG);
1059
1060                 if (root != null) {
1061                         Resource root2 = xs.convertDelayedResourceToResource(root);
1062                         graph.deny(tree2, DATA.BTree_root);
1063                         graph.claim(tree2, DATA.BTree_root, root2);
1064                 }
1065         }
1066
1067         public BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException {
1068                 if (cached) {
1069                         BTreeContentBean bean = beans.get(node);
1070                         if (bean != null) return bean;
1071                 }
1072                 return graph.syncRequest(new RelatedValue<BTreeContentBean>(node, DATA.BTreeNode_content, CONTENT_BEAN_BINDING), TransientCacheListener.<BTreeContentBean>instance());
1073         }
1074
1075         public List<Tuple2> entries(ReadGraph graph) throws DatabaseException {
1076                 Resource r = getRoot(graph);
1077                 List<Tuple2> results = new ArrayList<Tuple2>();
1078                 return collectEntries(graph, r, null, null, results);
1079         }
1080
1081         private List<Tuple2> collectEntries(ReadGraph graph, Resource x, Variant min, Variant max, List<Tuple2> results) throws DatabaseException {
1082
1083                 BTreeContentBean xContent = getContentBean(graph, x);
1084
1085                 for (int i = 0; i < xContent.n + 1; i++) {
1086                         if (min != null && i < xContent.n && min.compareTo(xContent.key[i].v) > 0) continue;
1087
1088                         if (!xContent.leaf) {
1089                                 Resource child = xContent.c[i].r;
1090                                 if (child != null) {
1091
1092                                         // reduce the amount of comparison if we know that the range of the child keys matches
1093                                         Variant min2 = (min != null && i > 0 && min.compareTo(xContent.key[i - 1].v) < 0) ? null : min;
1094                                         Variant max2 = (max != null && i < xContent.n - 1 && max.compareTo(xContent.key[i + 1].v) > 0) ? null : max;
1095
1096                                         collectEntries(graph, child, min2, max2, results);
1097                                 }
1098                         }
1099
1100                         if (i < xContent.n) {
1101                                 if (max != null && max.compareTo(xContent.key[i].v) < 0) return results;
1102
1103                                 results.add(new Tuple2(xContent.key[i].v, xContent.value[i].r));
1104                         }
1105                 }
1106                 return results;
1107         }
1108
1109         public List<Tuple2> searchRange(ReadGraph graph, Variant min, Variant max) throws DatabaseException {
1110                 Resource r = getRoot(graph);
1111                 List<Tuple2> results = new ArrayList<Tuple2>();
1112                 return collectEntries(graph, r, min, max, results);
1113         }
1114
1115 }