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                         this.mod = 0;
 384                         this.cached = cached;
 385                         if (cached) {
 386                                 this.beans = new HashMap<Resource, BTreeContentBean>();
 387                                 this.owners = new HashMap<Resource, Resource>();
 388                         }
 389                 } catch (RuntimeBindingConstructionException e) {
 390                         Logger.defaultLogError(e);
 391                         throw new DatabaseException(e);
 392                 }
 393         }
 394
 395         public static BTreeUtils create(WriteGraph graph, Resource ownerRelation, int t, boolean cached) throws DatabaseException {
 396
 397                 DatatypeResource DATA = DatatypeResource.getInstance(graph);
 398                 return create(graph, DATA.BTree, DATA.BTreeNode, ownerRelation, t, cached);
 399
 400         }
 401
 402         public static BTreeUtils create(WriteGraph graph, Resource type, Resource nodeType, Resource ownerRelation, int t, boolean cached) throws DatabaseException {
 403
 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);
 408
 409                 if(ownerRelation != null)
 410                         graph.claim(tree, DATA.BTree_HasOwnerRelation, DATA.BTree_HasOwnerRelation_Inverse, ownerRelation);
 411                 if(nodeType != null)
 412                         graph.claim(tree, DATA.BTree_HasNodeType, DATA.BTree_HasNodeType_Inverse, nodeType);
 413
 414                 graph.claimLiteral(tree, DATA.BTree_t, t, Bindings.INTEGER);
 415
 416                 if (!cached) {
 417                         graph.claimLiteral(tree, DATA.BTree_mod, 0L, Bindings.LONG);
 418                 }
 419
 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);
 424
 425                 return utils;
 426         }
 427
 428         public Resource getTree() {
 429                 return tree;
 430         }
 431
 432         public void insert(WriteGraph graph, Variant k, Resource v) throws DatabaseException {
 433
 434                 Resource r = getRoot(graph);
 435                 insertImpl(graph, this, r, t, k, v);
 436
 437         }
 438
 439         static class BatchContentManager implements BTreeContentManager {
 440
 441                 final private BTreeUtils bu;
 442
 443                 final Map<Resource, BTreeContentBean> beans = new HashMap<Resource, BTreeContentBean>();
 444
 445                 public BatchContentManager(BTreeUtils bu) {
 446                         this.bu = bu;
 447                 }
 448
 449                 @Override
 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);
 454                 }
 455
 456                 @Override
 457                 public void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException {
 458                         beans.put(node, bean);
 459                 }
 460
 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());
 464                         }
 465                 }
 466
 467         }
 468
 469         public void insertAll(WriteGraph graph, Collection<Pair<Variant, Resource>> values) throws DatabaseException {
 470
 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);
 475                 }
 476                 cm.apply(graph);
 477
 478         }
 479
 480         public Resource search(ReadGraph graph, Variant k) throws DatabaseException {
 481
 482                 Resource r = getRoot(graph);
 483                 return searchNode(graph, r, k);
 484
 485         }
 486
 487         // Implementation
 488
 489         private int findKey(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, Variant k) throws DatabaseException {
 490
 491                 int idx = 0;
 492                 while(idx<bean.n && bean.key[idx].v.compareTo(k) < 0)
 493                         idx++;
 494                 return idx;
 495
 496         }
 497
 498         private void insertImpl(WriteGraph graph, BTreeContentManager manager, Resource r, int t, Variant k, Resource v) throws DatabaseException {
 499
 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);
 504                         setRoot(graph, s);
 505                         setOwner(graph, s, tree, true);
 506                         sContent.leaf = false;
 507                         sContent.n = 0;
 508                         sContent.c[0].r = r;
 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);
 513                 } else {
 514                         insertNonfull(graph, manager, t, r, k, v);
 515                 }
 516
 517         }
 518
 519         public void remove(WriteGraph graph, Variant k) throws DatabaseException {
 520
 521                 Resource r = getRoot(graph);
 522
 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);
 527
 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
 530                     if (bean.n==0)
 531                     {
 532                         //BTreeContentBean tmp = bean;
 533                         if (!bean.leaf) {
 534                                 removeOwner(graph, r, true);
 535                                 setRoot(graph, bean.c[0].r);
 536                                 setOwner(graph, bean.c[0].r, tree, true);
 537                         }
 538
 539                         // Free the old root
 540                         //delete tmp;
 541
 542                     }
 543                 }
 544
 545
 546         }
 547
 548         public Resource removeImpl(WriteGraph graph, BTreeContentManager manager, int t, Resource r, BTreeContentBean bean, Variant k) throws DatabaseException {
 549
 550                 int idx = findKey(graph, manager, bean, k);
 551
 552                 if(idx < bean.n && bean.key[idx].v.equals(k)) {
 553                         Resource removedResource = bean.value[idx].r;
 554                         if(bean.leaf)
 555                                 removeFromLeaf(graph, manager, r, bean, idx);
 556                         else
 557                                 removeFromNonLeaf(graph, manager, r, bean, t, idx);
 558
 559                         return removedResource;
 560                 } else {
 561
 562                 if (bean.leaf) {
 563                         return null;
 564                 }
 565
 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 );
 570
 571                 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx].r);
 572
 573                 // If the child where the key is supposed to exist has less that t keys,
 574                 // we fill that child
 575                 if (cContent.n < t)
 576                     fill(graph, manager, r, bean, t, idx);
 577
 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);
 583                 else
 584                         return removeImpl(graph, manager, t, bean.c[idx].r, cContent, k);
 585
 586                 }
 587
 588
 589         }
 590
 591         // A function to get predecessor of keys[idx]
 592         Pair<Variant, Resource> getPred(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, int idx) throws DatabaseException {
 593
 594             // Keep moving to the right most node until we reach a leaf
 595         bean = manager.getContentBean(graph, bean.c[idx].r);
 596             while (!bean.leaf)
 597                 bean = manager.getContentBean(graph, bean.c[bean.n].r);
 598
 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);
 601
 602         }
 603
 604         Pair<Variant, Resource> getSucc(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, int idx) throws DatabaseException {
 605
 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);
 608             while (!bean.leaf)
 609                 bean = manager.getContentBean(graph, bean.c[0].r);
 610
 611             // Return the first key of the leaf
 612             return new Pair<Variant, Resource>(bean.key[0].v, bean.value[0].r);
 613
 614         }
 615
 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 {
 618
 619             // If the previous child(C[idx-1]) has more than t-1 keys, borrow a key
 620             // from that child
 621             if (idx!=0) {
 622                 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx-1].r);
 623
 624                 if (cContent.n>=t) {
 625                         borrowFromPrev(graph, manager, r, bean, idx);
 626                         return;
 627                 }
 628             }
 629
 630         // If the next child(C[idx+1]) has more than t-1 keys, borrow a key
 631         // from that child
 632
 633             if (idx!=bean.n) {
 634                 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx+1].r);
 635
 636                 if (cContent.n>=t) {
 637                         borrowFromNext(graph, manager, r, bean, idx);
 638                         return;
 639                 }
 640             }
 641
 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
 645                 if (idx != bean.n)
 646                         merge(graph, manager, r, bean, t, idx);
 647                 else
 648                         merge(graph, manager, r, bean, t, idx-1);
 649         }
 650
 651         // A function to borrow a key from C[idx-1] and insert it
 652         // into C[idx]
 653         void borrowFromPrev(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {
 654
 655         BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);
 656         BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx-1].r);
 657
 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
 661
 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;
 666             }
 667
 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);
 673                 }
 674             }
 675
 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;
 679
 680             // Moving sibling's last child as C[idx]'s first child
 681             // TODO: is this correct?
 682             if (!bean.leaf) {
 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);
 687                 }
 688             }
 689
 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;
 694
 695             childContent.n += 1;
 696             siblingContent.reduceSize();
 697             //siblingContent.n -= 1;
 698
 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);
 702
 703         }
 704
 705         // A function to borrow a key from the C[idx+1] and place
 706         // it in C[idx]
 707         void borrowFromNext(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {
 708
 709         BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);
 710         BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx+1].r);
 711
 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;
 715
 716             // Sibling's first child is inserted as the last child
 717             // into C[idx]
 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);
 721             }
 722
 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;
 726
 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;
 731             }
 732
 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;
 737             }
 738
 739             // Increasing and decreasing the key count of C[idx] and C[idx+1]
 740             // respectively
 741             childContent.n += 1;
 742             siblingContent.reduceSize();
 743             //siblingContent.n -= 1;
 744
 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);
 748
 749         }
 750
 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 {
 754
 755         BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);
 756         BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx+1].r);
 757
 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;
 762
 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;
 767             }
 768
 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);
 774                 }
 775             }
 776
 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;
 782             }
 783
 784         // Remove the owner of the merged sibling
 785         removeOwner(graph, bean.c[idx+1].r, true);
 786
 787             // Moving the child pointers after (idx+1) in the current node one
 788             // step before
 789             for (int i=idx+2; i<=bean.n; ++i)
 790                 bean.c[i-1].r = bean.c[i].r;
 791
 792             // Updating the key count of child and the current node
 793             childContent.n += siblingContent.n+1;
 794             bean.reduceSize();
 795             //bean.n--;
 796
 797             // Freeing the memory occupied by sibling
 798             // delete(sibling);
 799
 800             manager.setContentBean(graph, r, bean);
 801             manager.setContentBean(graph, bean.c[idx].r, childContent);
 802
 803         }
 804
 805         private void removeOwner(WriteGraph graph, Resource r, boolean force) throws DatabaseException {
 806                 if((ownerRelation != null) || force) {
 807                         if (cached) {
 808                                 owners.put(r, null);
 809                         } else {
 810                                 Resource own = ownerRelation != null ? ownerRelation : DATA.BTreeNode_IsOwnedBy;
 811                                 graph.deny(r, own);
 812                         }
 813                 }
 814         }
 815
 816         private void removeFromLeaf(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {
 817
 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;
 822             }
 823
 824             // Reduce the count of keys
 825             bean.reduceSize();
 826             //bean.n--;
 827
 828             manager.setContentBean(graph, r, bean);
 829
 830         }
 831
 832         private void removeFromNonLeaf(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {
 833
 834                 Variant k = bean.key[idx].v;
 835
 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
 839                 // in C[idx]
 840
 841         BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx].r);
 842
 843                 if (cContent.n >= t) {
 844
 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);
 849
 850                         manager.setContentBean(graph, r, bean);
 851                 } else {
 852
 853                 BTreeContentBean cContentPlus1 = manager.getContentBean(graph, bean.c[idx+1].r);
 854
 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]
 858                         // Replace k by succ
 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);
 865
 866                                 manager.setContentBean(graph, r, bean);
 867                         }
 868
 869                         // If both C[idx] and C[idx+1] has less that t keys,merge k and all of C[idx+1]
 870                         // into C[idx]
 871                         // Now C[idx] contains 2t-1 keys
 872                         // Free C[idx+1] and recursively delete k from C[idx]
 873                         else {
 874
 875                                 merge(graph, manager, r, bean, t, idx);
 876                                 removeImpl(graph, manager, t, bean.c[idx].r, cContent, k);
 877
 878                         }
 879
 880                 }
 881
 882         }
 883
 884         private Resource createNode(WriteGraph graph, BTreeContentManager manager, int t) throws DatabaseException {
 885                 Layer0 L0 = Layer0.getInstance(graph);
 886                 Resource result = graph.newResource();
 887                 mod++;
 888                 graph.claim(result, L0.InstanceOf, null, nodeType);
 889                 if (!cached) {
 890                         graph.claimLiteral(tree, DATA.BTree_mod, mod, Bindings.LONG);
 891                 }
 892                 graph.addLiteral(result, L0.HasName, L0.NameOf, ""+mod, Bindings.STRING);
 893                 manager.setContentBean(graph, result, BTreeContentBean.create(t));
 894                 return result;
 895         }
 896
 897         public Resource searchNode(ReadGraph graph, Resource x, Variant k) throws DatabaseException {
 898
 899                 BTreeContentBean xContent = getContentBean(graph, x);
 900
 901                 int i=1;
 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;
 904
 905                 if(xContent.leaf) return null;
 906                 else return searchNode(graph, xContent.c[i-1].r, k);
 907
 908         }
 909
 910         private void splitChild(WriteGraph graph, BTreeContentManager manager, int t, Resource x, int i, Resource y) throws DatabaseException {
 911
 912                 Resource z = allocateNode(graph, manager, t);
 913
 914                 BTreeContentBean xContent = manager.getContentBean(graph, x);
 915                 BTreeContentBean yContent = manager.getContentBean(graph, y);
 916                 BTreeContentBean zContent = manager.getContentBean(graph, z);
 917
 918                 zContent.leaf = yContent.leaf;
 919                 zContent.n = t-1;
 920
 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);
 925                 }
 926                 if(!yContent.leaf) {
 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);
 930                         }
 931                 }
 932
 933                 //yContent.n = t-1;
 934
 935
 936                 for(int j=xContent.n+1;j>=i+1;j--) {
 937                         xContent.c[j+1-1].r = xContent.c[j-1].r;
 938                 }
 939
 940                 xContent.c[i+1-1].r = z;
 941                 setOwner(graph, z, x, true);
 942
 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;
 946                 }
 947
 948                 xContent.key[i-1].v = yContent.key[t-1].v;
 949                 xContent.value[i-1].r = yContent.value[t-1].r;
 950                 xContent.n++;
 951
 952                 while (yContent.n > t-1) yContent.reduceSize();
 953
 954                 setOwner(graph, xContent.value[i-1].r, x, true);
 955
 956                 manager.setContentBean(graph, x, xContent);
 957                 manager.setContentBean(graph, y, yContent);
 958                 manager.setContentBean(graph, z, zContent);
 959
 960         }
 961
 962         private void insertNonfull(WriteGraph graph, BTreeContentManager manager, int t, Resource x, Variant k, Resource v) throws DatabaseException {
 963
 964                 BTreeContentBean xContent = manager.getContentBean(graph, x);
 965
 966                 int i = xContent.n;
 967
 968                 if(xContent.leaf) {
 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;
 972                                 i--;
 973                         }
 974
 975                         xContent.key[i+1-1].v = k;
 976                         xContent.value[i+1-1].r = v;
 977                         xContent.n++;
 978                         setOwner(graph, v, x, false);
 979                         manager.setContentBean(graph, x, xContent);
 980                 } else {
 981                         while(i >= 1 && k.compareTo(xContent.key[i-1].v) < 0) i--;
 982                         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++;
 988                         }
 989                         insertNonfull(graph, manager, t, xContent.c[i-1].r, k, v);
 990                 }
 991
 992         }
 993
 994         private void setOwner(WriteGraph graph, Resource r, Resource owner, boolean force) throws DatabaseException {
 995                 if (r != null) {
 996                         if((ownerRelation != null) || force) {
 997                                 Resource own = ownerRelation != null ? ownerRelation : DATA.BTreeNode_IsOwnedBy;
 998                                 if (cached) {
 999                                         owners.put(r, owner);
1000                                 } else {
1001                                         graph.deny(r, own);
1002                                         graph.claim(r, own, owner);
1003                                 }
1004                         }
1005                 }
1006         }
1007
1008         private Resource getRoot(ReadGraph graph) throws DatabaseException {
1009                 if (cached) {
1010                         if (root != null) return root;
1011                 }
1012                 return graph.getPossibleObject(tree, DATA.BTree_root);
1013         }
1014
1015         private void setRoot(WriteGraph graph, Resource r) throws DatabaseException {
1016                 if (cached) {
1017                         this.root = r;
1018                 } else {
1019                         graph.deny(tree, DATA.BTree_root);
1020                         graph.claim(tree, DATA.BTree_root, r);
1021                 }
1022         }
1023
1024         private Resource allocateNode(WriteGraph graph, BTreeContentManager manager, int t) throws DatabaseException {
1025                 return createNode(graph, manager, t);
1026         }
1027
1028         public void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException {
1029                 if (cached) {
1030                         beans.put(node, bean);
1031                 } else {
1032                         graph.claimLiteral(node, DATA.BTreeNode_content, DATA.BTreeNode_Content, bean, CONTENT_BEAN_BINDING );
1033                 }
1034         }
1035
1036         public void flushCache(WriteGraph graph) throws DatabaseException {
1037                 assert(cached);
1038
1039                 XSupport xs = graph.getService(XSupport.class);
1040                 for(Map.Entry<Resource, BTreeContentBean> entry : beans.entrySet()) {
1041                         Resource node = xs.convertDelayedResourceToResource(entry.getKey());
1042                         if (node != null) {
1043                                 graph.claimLiteral(node, DATA.BTreeNode_content, DATA.BTreeNode_Content, entry.getValue(), CONTENT_BEAN_BINDING );
1044                         }
1045                 }
1046
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);
1053                         }
1054                 }
1055
1056                 Resource tree2 = xs.convertDelayedResourceToResource(tree);
1057                 graph.claimLiteral(tree2, DATA.BTree_mod, mod, Bindings.LONG);
1058
1059                 if (root != null) {
1060                         Resource root2 = xs.convertDelayedResourceToResource(root);
1061                         graph.deny(tree2, DATA.BTree_root);
1062                         graph.claim(tree2, DATA.BTree_root, root2);
1063                 }
1064         }
1065
1066         public BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException {
1067                 if (cached) {
1068                         BTreeContentBean bean = beans.get(node);
1069                         if (bean != null) return bean;
1070                 }
1071                 return graph.syncRequest(new RelatedValue<BTreeContentBean>(node, DATA.BTreeNode_content, CONTENT_BEAN_BINDING), TransientCacheListener.<BTreeContentBean>instance());
1072         }
1073
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);
1078         }
1079
1080         private List<Tuple2> collectEntries(ReadGraph graph, Resource x, Variant min, Variant max, List<Tuple2> results) throws DatabaseException {
1081
1082                 BTreeContentBean xContent = getContentBean(graph, x);
1083
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;
1086
1087                         if (!xContent.leaf) {
1088                                 Resource child = xContent.c[i].r;
1089                                 if (child != null) {
1090
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;
1094
1095                                         collectEntries(graph, child, min2, max2, results);
1096                                 }
1097                         }
1098
1099                         if (i < xContent.n) {
1100                                 if (max != null && max.compareTo(xContent.key[i].v) < 0) return results;
1101
1102                                 results.add(new Tuple2(xContent.key[i].v, xContent.value[i].r));
1103                         }
1104                 }
1105                 return results;
1106         }
1107
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);
1112         }
1113
1114 }