rom/filesys/SFS/FS/btreenodes.c

   1 #include "asmsupport.h"
   2
   3 #include <exec/types.h>
   4 #include <proto/exec.h>
   5
   6 #include "btreenodes.h"
   7 #include "btreenodes_protos.h"
   8
   9 #include "adminspaces_protos.h"
  10 #include "cachebuffers_protos.h"
  11 #include "debug.h"
  12 #include "req_protos.h"
  13 #include "globals.h"
  14
  15 extern void setchecksum(struct CacheBuffer *);
  16 extern LONG readcachebuffercheck(struct CacheBuffer **,ULONG,ULONG);
  17 extern void outputcachebuffer(struct CacheBuffer *cb);
  18
  19 /*
  20
  21 The idea behind a multiway tree is that multiway trees do
  22 not require a very good balance to be effective.
  23
  24 x-Way trees
  25
  26 We store new nodes in a leaf-container which can contain
  27 upto x nodes.  When the leaf-container is full it is split
  28 into two seperate leaf-containers containing x/2 and x/2+1
  29 nodes.  A node-container is created which keeps track of the
  30 two leaf-containers.  The new leaf-containers will be split
  31 when they are full as well, and so on.
  32
  33 At some point the node-container will be full.  When this
  34 happens we split it in much the same way we split the
  35 leaf-containers.  In effect this will mean adding a new
  36 level to the tree.
  37
  38 When deleting a leaf from a leaf-container we will check if
  39 the container contains less than x/2 leafs.  If this is the
  40 case we attempt to merge the leaf-container with the next or
  41 previous leaf-container (or both).  For this to work the
  42 total number of free leafs in the next and previous
  43 container must be equal to the number of leafs in the
  44 current leaf-container.
  45
  46 */
  47
  48
  49
  50 /* Internal functions */
  51
  52 LONG splitbtreecontainer(BLCK rootblock,struct CacheBuffer *cb);
  53 WORD getbnodeindex(struct BTreeContainer *btc);
  54 struct BNode *searchforbnode(ULONG key,struct BTreeContainer *btc);
  55 struct BNode *insertbnode(ULONG key,struct BTreeContainer *btc);
  56 void removebnode(ULONG key,struct BTreeContainer *btc);
  57
  58
  59
  60 static void __inline copywordsforward(UWORD *src,UWORD *dst,UWORD len) {
  61   while(len-->0) {
  62     *dst++=*src++;
  63   }
  64 }
  65
  66 static void __inline copywordsbackward(UWORD *src,UWORD *dst,UWORD len) {
  67   while(len-->0) {
  68     *--dst=*--src;
  69   }
  70 }
  71
  72
  73
  74 LONG getparentbtreecontainer(BLCK rootblock,struct CacheBuffer **io_cb) {
  75   ULONG childkey=BE2L(((struct fsBNodeContainer *)((*io_cb)->data))->btc.bnode[0].be_key);
  76   BLCK childblock=(*io_cb)->blckno;
  77   LONG errorcode=0;
  78
  79   _XDEBUG((DEBUG_NODES,"getparentbtreecontainer: Getting parent of block %ld\n",(*io_cb)->blckno));
  80
  81   /* This function gets the BTreeContainer parent of the passed in CacheBuffer.  If
  82      there is no parent this function sets io_cb to 0 */
  83
  84   if(rootblock!=childblock) {
  85     while((errorcode=readcachebuffercheck(io_cb,rootblock,BNODECONTAINER_ID))==0) {
  86       struct fsBNodeContainer *bnc=(*io_cb)->data;
  87       struct BTreeContainer *btc=&bnc->btc;
  88       struct BNode *bn;
  89       WORD n=BE2W(btc->be_nodecount);
  90
  91       if(btc->isleaf==TRUE) {
  92         #ifdef CHECKCODE_BNODES
  93           dreq("getparentbtreecontainer() couldn't find parent for bnodecontainer at block %ld!\nPlease notify the author!",childblock);
  94           outputcachebuffer(*io_cb);
  95           errorcode=INTERR_BTREE;
  96         #endif
  97
  98         break;
  99       }
 100
 101       while(n-->0) {
 102         if(BE2L(btc->bnode[n].be_data)==childblock) {
 103           return(0);    /* Found parent!! */
 104         }
 105       }
 106
 107       bn=searchforbnode(childkey,btc);    /* This searchforbnode() doesn't have to get EXACT key matches. */
 108       rootblock=BE2L(bn->be_data);
 109     }
 110   }
 111
 112   *io_cb=0;
 113
 114   return(errorcode);
 115 }
 116
 117
 118
 119 LONG createbnode(BLCK rootblock,ULONG key,struct CacheBuffer **returned_cb,struct BNode **returned_bnode) {
 120   LONG errorcode;
 121
 122   _XDEBUG((DEBUG_NODES,"createbnode: Creating BNode with key %ld, using %ld as root.\n",key,rootblock));
 123
 124   while((errorcode=findbnode(rootblock, key, returned_cb, returned_bnode))==0) {
 125     struct fsBNodeContainer *bnc=(*returned_cb)->data;
 126     struct BTreeContainer *btc=&bnc->btc;
 127     LONG extbranches=(globals->bytes_block-sizeof(struct fsBNodeContainer))/btc->nodesize;
 128
 129     #ifdef CHECKCODE_BNODES
 130       if(*returned_bnode!=0 && BE2L((*returned_bnode)->be_key)==key) {
 131         dreq("createbnode: findbnode() says key %ld already exists!",key);
 132         outputcachebuffer(*returned_cb);
 133       }
 134     #endif
 135
 136     _XDEBUG((DEBUG_NODES,"createbnode: findbnode found block %ld\n",(*returned_cb)->blckno));
 137
 138     if(BE2W(btc->be_nodecount)<extbranches) {
 139       /* Simply insert new node in this BTreeContainer */
 140
 141       _XDEBUG((DEBUG_NODES,"createbnode: Simple insert\n"));
 142
 143       preparecachebuffer(*returned_cb);
 144
 145       *returned_bnode=insertbnode(key,btc);
 146
 147       setchecksum(*returned_cb);
 148      //  errorcode=storecachebuffer(*returned_cb);
 149       break;
 150     }
 151     else if((errorcode=splitbtreecontainer(rootblock,*returned_cb))!=0) {
 152       break;
 153     }
 154
 155     /* Loop and try insert it the normal way again :-) */
 156   }
 157
 158   return(errorcode);
 159 }
 160
 161
 162
 163 LONG splitbtreecontainer(BLCK rootblock,struct CacheBuffer *cb) {
 164   struct CacheBuffer *cbparent;
 165   struct BNode *bn;
 166   LONG errorcode;
 167
 168   _XDEBUG((DEBUG_NODES,"splitbtreecontainer: splitting block %ld\n",cb->blckno));
 169
 170   lockcachebuffer(cb);
 171
 172   cbparent=cb;
 173   if((errorcode=getparentbtreecontainer(rootblock,&cbparent))==0) {
 174     if(cbparent==0) {
 175       /* We need to create Root tree-container */
 176
 177       _XDEBUG((DEBUG_NODES,"splitbtreecontainer: creating root tree-container\n"));
 178
 179       cbparent=cb;
 180       if((errorcode=allocadminspace(&cb))==0) {
 181         struct fsBNodeContainer *bnc=cb->data;
 182         struct fsBNodeContainer *bncparent=cbparent->data;
 183         struct BTreeContainer *btcparent=&bncparent->btc;
 184
 185         CopyMemQuick(cbparent->data,cb->data,globals->bytes_block);
 186         bnc->bheader.be_ownblock=L2BE(cb->blckno);
 187
 188         _XDEBUG((DEBUG_NODES,"splitbtreecontainer: allocated admin space for root\n"));
 189
 190         lockcachebuffer(cb);          /* Lock cachebuffer which now contains the data previously in root.
 191                                          It must be locked here, otherwise preparecachebuffer below could
 192                                          kill it. */
 193
 194         if((errorcode=storecachebuffer(cb))==0) {
 195           preparecachebuffer(cbparent);
 196           clearcachebuffer(cbparent);        /* Not strictly needed, but makes things more clear. */
 197
 198           bncparent->bheader.id=BNODECONTAINER_ID;
 199           bncparent->bheader.be_ownblock=L2BE(cbparent->blckno);
 200
 201           btcparent->isleaf=FALSE;
 202           btcparent->nodesize=sizeof(struct BNode);
 203           btcparent->be_nodecount=0;
 204
 205           bn=insertbnode(0,btcparent);
 206           bn->be_data=L2BE(cb->blckno);
 207
 208           errorcode=storecachebuffer(cbparent);
 209         }
 210
 211         unlockcachebuffer(cbparent);  /* Unlock cachebuffer which was root, and still is root */
 212       }
 213     }
 214
 215     if(errorcode==0) {
 216       struct fsBNodeContainer *bncparent=cbparent->data;
 217       struct BTreeContainer *btcparent=&bncparent->btc;
 218       LONG branches=(globals->bytes_block-sizeof(struct fsBNodeContainer))/btcparent->nodesize;
 219
 220       if(BE2W(btcparent->be_nodecount)==branches) {
 221         /* We need to split the parent tree-container first! */
 222
 223         errorcode=splitbtreecontainer(rootblock,cbparent);
 224
 225         if(errorcode==0) {
 226           cbparent=cb;
 227           if((errorcode=getparentbtreecontainer(rootblock,&cbparent))==0) {
 228             /* cbparent might have changed after the split */
 229             bncparent=cbparent->data;
 230             btcparent=&bncparent->btc;
 231           }
 232         }
 233       }
 234
 235       if(errorcode==0) {
 236         struct CacheBuffer *cbnew;
 237
 238         /* We can split this container and add it to the parent
 239            because the parent has enough room. */
 240
 241         lockcachebuffer(cbparent);
 242
 243         if((errorcode=allocadminspace(&cbnew))==0) {
 244           struct fsBNodeContainer *bncnew=cbnew->data;
 245           struct BTreeContainer *btcnew=&bncnew->btc;
 246           struct fsBNodeContainer *bnc=cb->data;
 247           struct BTreeContainer *btc=&bnc->btc;
 248           LONG branches=(globals->bytes_block-sizeof(struct fsBNodeContainer))/btc->nodesize;
 249           ULONG newkey;
 250           ULONG newblckno=cbnew->blckno;
 251
 252           bncnew->bheader.id=BNODECONTAINER_ID;
 253           bncnew->bheader.be_ownblock=L2BE(cbnew->blckno);
 254
 255           btcnew->isleaf=btc->isleaf;
 256           btcnew->nodesize=btc->nodesize;
 257
 258           btcnew->be_nodecount=W2BE(branches-branches/2);
 259
 260           copywordsforward((UWORD *)((UBYTE *)btc->bnode+branches/2*btc->nodesize),(UWORD *)btcnew->bnode,(branches-branches/2)*btc->nodesize/2);
 261
 262           newkey=BE2L(btcnew->bnode[0].be_key);
 263
 264           if((errorcode=storecachebuffer(cbnew))==0) {
 265
 266             preparecachebuffer(cb);
 267
 268             btc->be_nodecount=W2BE(branches/2);
 269
 270             if((errorcode=storecachebuffer(cb))==0) {
 271               preparecachebuffer(cbparent);
 272
 273               bn=insertbnode(newkey,btcparent);
 274               bn->be_data=L2BE(newblckno);
 275
 276               errorcode=storecachebuffer(cbparent);
 277             }
 278           }
 279         }
 280
 281         unlockcachebuffer(cbparent);
 282       }
 283     }
 284   }
 285
 286   unlockcachebuffer(cb);
 287
 288   return(errorcode);
 289 }
 290
 291
 292
 293 LONG findbnode(BLCK rootblock, ULONG key, struct CacheBuffer **returned_cb, struct BNode **returned_bnode) {
 294   LONG errorcode;
 295
 296   /* This function finds the BNode with the given key.  If no exact match can be
 297      found then this function will return either the next or previous closest
 298      match (don't rely on this).
 299
 300      If there were no BNode's at all, then *returned_cb will be the Rootblock
 301      and *returned_bnode will be zero.
 302
 303      Any error will be returned.  If non-zero then don't rely on the contents
 304      of *returned_cb and *returned_bnode. */
 305
 306   _XDEBUG((DEBUG_NODES,"findbnode: Looking for BNode with key %ld, from root %ld\n",key,rootblock));
 307
 308   while((errorcode=readcachebuffercheck(returned_cb, rootblock, BNODECONTAINER_ID))==0) {
 309     struct fsBNodeContainer *bnc=(*returned_cb)->data;
 310     struct BTreeContainer *btc=&bnc->btc;
 311
 312     if(BE2W(btc->be_nodecount)==0) {
 313       *returned_bnode=0;
 314       break;
 315     }
 316
 317     *returned_bnode=searchforbnode(key, btc);
 318     if(btc->isleaf==TRUE) {
 319       break;
 320     }
 321     rootblock=BE2L((*returned_bnode)->be_data);
 322   }
 323
 324   _XDEBUG((DEBUG_NODES,"findbnode: *returned_cb->blckno = %ld, Exiting with errorcode %ld\n",(*returned_cb)->blckno,errorcode));
 325
 326   return(errorcode);
 327 }
 328
 329
 330
 331 struct BNode *searchforbnode(ULONG key, struct BTreeContainer *tc) {
 332   struct BNode *tn;
 333   WORD n=BE2W(tc->be_nodecount)-1;
 334
 335   /* This function looks for the BNode equal to the key.  If no
 336      exact match is available then the BNode which is slightly
 337      lower than key will be returned.  If no such BNode exists
 338      either, then the first BNode in this block is returned.
 339
 340      This function will return the first BNode even if there
 341      are no BNode's at all in this block (this can only happen
 342      for the Root of the tree).  Be sure to check if the Root
 343      is not empty before calling this function. */
 344
 345   tn=(struct BNode *)((UBYTE *)tc->bnode+n*tc->nodesize);
 346
 347   for(;;) {
 348     if(n<=0 || key >= BE2L(tn->be_key)) {
 349       return(tn);
 350     }
 351     tn=(struct BNode *)((UBYTE *)tn-tc->nodesize);
 352     n--;
 353   }
 354 }
 355
 356
 357
 358 struct BNode *insertbnode(ULONG key,struct BTreeContainer *btc) {
 359   struct BNode *bn=btc->bnode;
 360   UWORD *src;
 361   UWORD *dst;
 362
 363   bn=(struct BNode *)((UBYTE *)bn+btc->nodesize*(BE2W(btc->be_nodecount)-1));
 364
 365   src=(UWORD *)((UBYTE *)bn+btc->nodesize);
 366   dst=src+btc->nodesize/2;
 367
 368   /* This routine inserts a node sorted into a BTreeContainer.  It does
 369      this by starting at the end, and moving the nodes one by one to
 370      a higher slot until the empty slot has the correct position for
 371      this key.  Donot use this function on completely filled
 372      BTreeContainers! */
 373
 374   for(;;) {
 375     if(bn<btc->bnode || key > BE2L(bn->be_key)) {
 376       bn=(struct BNode *)((UBYTE *)bn+btc->nodesize);
 377       bn->be_key=L2BE(key);
 378       btc->be_nodecount = W2BE(BE2W(btc->be_nodecount)+1);
 379       break;
 380     }
 381     else {
 382       WORD l=btc->nodesize/2;
 383
 384       while(l-->0) {
 385         *--dst=*--src;
 386       }
 387     }
 388
 389     bn=(struct BNode *)((UBYTE *)bn-btc->nodesize);
 390   }
 391
 392   return(bn);
 393 }
 394
 395
 396
 397 LONG deleteinternalnode(BLCK rootblock,struct CacheBuffer *cb,ULONG key) {
 398   struct fsBNodeContainer *bnc=cb->data;
 399   struct BTreeContainer *btc=&bnc->btc;
 400   UWORD branches=(globals->bytes_block-sizeof(struct fsBNodeContainer))/btc->nodesize;
 401   LONG errorcode;
 402
 403   /* Deletes specified internal node. */
 404
 405   preparecachebuffer(cb);
 406
 407   removebnode(key,btc);
 408
 409   if((errorcode=storecachebuffer(cb))==0) {
 410
 411     /* Now checks if the container still contains enough nodes,
 412        and takes action accordingly. */
 413
 414     _XDEBUG((DEBUG_NODES,"deleteinternalnode: branches = %ld, btc->nodecount = %ld\n",branches,BE2W(btc->be_nodecount)));
 415
 416     if(BE2W(btc->be_nodecount)<(branches+1)/2) {
 417       struct CacheBuffer *cbparent=cb;
 418
 419       /* nodecount has become to low.  We need to merge this Container
 420          with a neighbouring Container, or we need to steal a few nodes
 421          from a neighbouring Container. */
 422
 423       lockcachebuffer(cb);
 424
 425       /* We get the parent of the container here, so we can find out what
 426          containers neighbour the container which currently hasn't got enough nodes. */
 427
 428       if((errorcode=getparentbtreecontainer(rootblock,&cbparent))==0) {
 429         if(cbparent!=0) {
 430           struct fsBNodeContainer *bncparent=cbparent->data;
 431           struct BTreeContainer *btcparent=&bncparent->btc;
 432           WORD n;
 433
 434           _XDEBUG((DEBUG_NODES,"deleteinternalnode: get parent returned block %ld.\n",cbparent->blckno));
 435
 436           for(n=0; n<BE2W(btcparent->be_nodecount); n++) {
 437             if(BE2L(btcparent->bnode[n].be_data)==cb->blckno) {
 438               break;
 439             }
 440           }
 441
 442           /* n is now the offset of our own bnode. */
 443
 444           lockcachebuffer(cbparent);
 445
 446           if(n<BE2W(btcparent->be_nodecount)-1) {      // Check if we have a next neighbour.
 447             struct CacheBuffer *cb_next;
 448
 449             _XDEBUG((DEBUG_NODES,"deleteinternalnode: using next container.\n"));
 450
 451             if((errorcode=readcachebuffercheck(&cb_next,BE2L(btcparent->bnode[n+1].be_data),BNODECONTAINER_ID))==0) {
 452               struct fsBNodeContainer *bnc_next=cb_next->data;
 453               struct BTreeContainer *btc_next=&bnc_next->btc;
 454
 455               lockcachebuffer(cb_next);
 456
 457               if(BE2W(btc_next->be_nodecount)+BE2W(btc->be_nodecount)>branches) {    // Check if we need to steal nodes.
 458                 WORD nodestosteal=(BE2W(btc_next->be_nodecount)+BE2W(btc->be_nodecount))/2-BE2W(btc->be_nodecount);
 459
 460                 /* Merging them is not possible.  Steal a few nodes then. */
 461
 462                 preparecachebuffer(cb);
 463
 464                 copywordsforward((UWORD *)btc_next->bnode,(UWORD *)((UBYTE *)btc->bnode+BE2W(btc->be_nodecount)*btc->nodesize),nodestosteal*btc->nodesize/2);
 465                 btc->be_nodecount=W2BE(BE2W(btc->be_nodecount)+nodestosteal);
 466
 467                 if((errorcode=storecachebuffer(cb))==0) {
 468                   preparecachebuffer(cb_next);
 469
 470                   copywordsforward((UWORD *)((UBYTE *)btc_next->bnode+btc_next->nodesize*nodestosteal),(UWORD *)btc_next->bnode,(btc->nodesize/2)*(BE2W(btc_next->be_nodecount) - nodestosteal));
 471                   btc_next->be_nodecount=W2BE(BE2W(btc_next->be_nodecount)-nodestosteal);
 472
 473                   if((errorcode=storecachebuffer(cb_next))==0) {
 474                     preparecachebuffer(cbparent);
 475
 476                     btcparent->bnode[n+1].be_key=btc_next->bnode[0].be_key; // BE->BE Copy!
 477
 478                     errorcode=storecachebuffer(cbparent);
 479                   }
 480                 }
 481               }
 482               else {   // Merging is possible.
 483                 preparecachebuffer(cb);
 484
 485                 copywordsforward((UWORD *)btc_next->bnode,(UWORD *)((UBYTE *)btc->bnode+btc->nodesize*BE2W(btc->be_nodecount)),btc->nodesize*BE2W(btc_next->be_nodecount)/2);
 486                 btc->be_nodecount=W2BE(BE2W(btc->be_nodecount)+BE2W(btc_next->be_nodecount));
 487
 488                 if((errorcode=storecachebuffer(cb))==0) {
 489                   if((errorcode=freeadminspace(cb_next->blckno))==0) {
 490                     errorcode=deleteinternalnode(rootblock,cbparent,BE2L(btcparent->bnode[n+1].be_key));
 491                   }
 492                 }
 493               }
 494
 495               unlockcachebuffer(cb_next);
 496             }
 497           }
 498           else if(n>0) {       // Check if we have a previous neighbour.
 499             struct CacheBuffer *cb2;
 500
 501             _XDEBUG((DEBUG_NODES,"deleteinternalnode: using prev container.\n"));
 502
 503             if((errorcode=readcachebuffercheck(&cb2,BE2L(btcparent->bnode[n-1].be_data),BNODECONTAINER_ID))==0) {
 504               struct fsBNodeContainer *bnc2=cb2->data;
 505               struct BTreeContainer *btc2=&bnc2->btc;
 506
 507               lockcachebuffer(cb2);
 508
 509               if(BE2W(btc2->be_nodecount)+BE2W(btc->be_nodecount)>branches) {
 510                 WORD nodestosteal=(BE2W(btc2->be_nodecount)+BE2W(btc->be_nodecount))/2-BE2W(btc->be_nodecount);
 511
 512                 /* Merging them is not possible.  Steal a few nodes then. */
 513
 514                 preparecachebuffer(cb);
 515
 516                 copywordsbackward((UWORD *)((UBYTE *)btc->bnode+BE2W(btc->be_nodecount)*btc->nodesize),(UWORD *)((UBYTE *)btc->bnode+(BE2W(btc->be_nodecount)+nodestosteal)*btc->nodesize),BE2W(btc->be_nodecount)*btc->nodesize/2);
 517                 btc->be_nodecount=W2BE(BE2W(btc->be_nodecount)+nodestosteal);
 518                 copywordsforward((UWORD *)((UBYTE *)btc2->bnode+(BE2W(btc2->be_nodecount)-nodestosteal)*btc2->nodesize),(UWORD *)btc->bnode,nodestosteal*btc->nodesize/2);
 519
 520                 if((errorcode=storecachebuffer(cb))==0) {
 521
 522                   preparecachebuffer(cb2);
 523
 524                   btc2->be_nodecount=W2BE(BE2W(btc2->be_nodecount)-nodestosteal);
 525
 526                   if((errorcode=storecachebuffer(cb2))==0) {
 527                     preparecachebuffer(cbparent);
 528
 529                     btcparent->bnode[n].be_key=btc->bnode[0].be_key; // BE->BE copy!
 530
 531                     errorcode=storecachebuffer(cbparent);
 532                   }
 533                 }
 534               }
 535               else {
 536                 preparecachebuffer(cb2);
 537
 538                 copywordsforward((UWORD *)btc->bnode,(UWORD *)((UBYTE *)btc2->bnode+BE2W(btc2->be_nodecount)*btc2->nodesize),BE2W(btc->be_nodecount)*btc->nodesize/2);
 539                 btc2->be_nodecount=W2BE(BE2W(btc2->be_nodecount)+BE2W(btc->be_nodecount));
 540
 541                 if((errorcode=storecachebuffer(cb2))==0) {
 542                   if((errorcode=freeadminspace(cb->blckno))==0) {
 543                     errorcode=deleteinternalnode(rootblock,cbparent,BE2L(btcparent->bnode[n].be_key));
 544                   }
 545                 }
 546               }
 547
 548               unlockcachebuffer(cb2);
 549             }
 550           }
 551           /*
 552           else {
 553             // Never happens, except for root and then we don't care.
 554           }
 555           */
 556
 557           unlockcachebuffer(cbparent);
 558
 559         }
 560         else if(BE2W(btc->be_nodecount)==1) {
 561           /* No parent, so must be root. */
 562
 563           _XDEBUG((DEBUG_NODES,"deleteinternalnode: no parent so must be root\n"));
 564
 565           if(btc->isleaf==FALSE) {
 566             struct CacheBuffer *cb2;
 567             struct fsBNodeContainer *bnc=cb->data;
 568
 569             /* The current root has only 1 node.  We now copy the data of this node into the
 570                root and promote that data to be the new root.  The rootblock number stays the
 571                same that way. */
 572
 573             preparecachebuffer(cb);
 574
 575             if((errorcode=readcachebuffercheck(&cb2,BE2L(btc->bnode[0].be_data),BNODECONTAINER_ID))==0) {
 576
 577               CopyMemQuick(cb2->data,cb->data,globals->bytes_block);
 578               bnc->bheader.be_ownblock=L2BE(cb->blckno);
 579
 580               if((errorcode=storecachebuffer(cb))==0) {
 581                 errorcode=freeadminspace(cb2->blckno);
 582               }
 583             }
 584             else {
 585               dumpcachebuffer(cb);
 586             }
 587           }
 588           /* If not, then root contains leafs. */
 589         }
 590
 591         _XDEBUG((DEBUG_NODES,"deleteinternalnode: almost done\n"));
 592
 593         /* otherwise, it must be the root, and the root is allowed
 594            to contain less than the minimum amount of nodes. */
 595
 596       }
 597
 598       unlockcachebuffer(cb);
 599     }
 600   }
 601
 602   return(errorcode);
 603 }
 604
 605
 606
 607 LONG deletebnode(BLCK rootblock,ULONG key) {
 608   struct CacheBuffer *cb;
 609   struct BNode *bn;
 610   LONG errorcode;
 611
 612   if((errorcode=findbnode(rootblock,key,&cb,&bn))==0) {
 613     #ifdef CHECKCODE_BNODES
 614       if(bn==0 || BE2L(bn->be_key)!=key) {
 615         dreq("deletebnode: key %ld doesn't exist!",key);
 616         outputcachebuffer(cb);
 617         return(INTERR_BTREE);
 618       }
 619     #endif
 620
 621     _XDEBUG((DEBUG_NODES,"deletebnode: key %ld\n",key));
 622
 623     errorcode=deleteinternalnode(rootblock,cb,key);
 624   }
 625
 626   return(errorcode);
 627 }
 628
 629
 630
 631 void removebnode(ULONG key,struct BTreeContainer *btc) {
 632   struct BNode *bn=btc->bnode;
 633   WORD n=0;
 634
 635   _XDEBUG((DEBUG_NODES,"removebnode: key %ld\n",key));
 636
 637   /* This routine removes a node from a BTreeContainer indentified
 638      by its key.  If no such key exists this routine does nothing.
 639      It correctly handles empty BTreeContainers. */
 640
 641   while(n<BE2W(btc->be_nodecount)) {
 642     if(BE2L(bn->be_key) == key) {
 643       btc->be_nodecount = W2BE(BE2W(btc->be_nodecount)-1);
 644
 645       copywordsforward((UWORD *)((UBYTE *)bn+btc->nodesize),(UWORD *)bn,(BE2W(btc->be_nodecount)-n)*btc->nodesize/2);
 646       break;
 647     }
 648     bn=(struct BNode *)((UBYTE *)bn+btc->nodesize);
 649     n++;
 650   }
 651 }
 652
 653
 654
 655 struct BNode *next(struct BTreeContainer *tc, struct BNode *tn) {
 656   if((UBYTE *)tn == (UBYTE *)tc->bnode + (BE2W(tc->be_nodecount)-1)*tc->nodesize) {
 657     return(0);
 658   }
 659   else {
 660     return((struct BNode *)((UBYTE *)tn+tc->nodesize));
 661   }
 662 }
 663
 664
 665
 666 struct BNode *previous(struct BTreeContainer *tc, struct BNode *tn) {
 667   if(tn==tc->bnode) {
 668     return(0);
 669   }
 670   else {
 671     return((struct BNode *)((UBYTE *)tn-tc->nodesize));
 672   }
 673 }
 674
 675
 676
 677 LONG nextbnode(BLCK rootblock, struct CacheBuffer **io_cb, struct BNode **io_bnode) {
 678   struct BNode *bn;
 679   ULONG key=BE2L((*io_bnode)->be_key);
 680   BLCK blockwithnext=0;
 681   LONG errorcode;
 682
 683   /* This function locates the next BNode in the tree.  If there is no next
 684      BNode then this function will return no error and zero *io_bnode. */
 685
 686   while((errorcode=readcachebuffercheck(io_cb, rootblock, BNODECONTAINER_ID))==0) {
 687     struct fsBNodeContainer *bnc=(*io_cb)->data;
 688     struct BTreeContainer *btc=&bnc->btc;
 689
 690     bn=searchforbnode(key, btc);
 691
 692     if((*io_bnode=next(btc, bn))!=0) {
 693       blockwithnext=BE2L((*io_bnode)->be_data);
 694     }
 695
 696     if(btc->isleaf==TRUE) {
 697       /* Traversed the tree to the end. */
 698
 699       if(*io_bnode!=0 || blockwithnext==0) {  // Checks if next is in this block, or no next was found ever.
 700         break;
 701       }
 702
 703       errorcode=findbnode(blockwithnext, key, io_cb, io_bnode);
 704       break;
 705     }
 706
 707     rootblock=BE2L(bn->be_data);
 708   }
 709
 710   return(errorcode);
 711 }
 712
 713
 714
 715 LONG previousbnode(BLCK rootblock, struct CacheBuffer **io_cb, struct BNode **io_bnode) {
 716   struct BNode *bn;
 717
 718   /* This function locates the previous BNode in the tree.  If there is no previous
 719      BNode then this function will return no error and zero *io_bnode.
 720
 721      This function will not walk the tree again if the Previous BNode is in the same
 722      block as the current one. */
 723
 724   if((bn=previous(&((struct fsBNodeContainer *)((*io_cb)->data))->btc, *io_bnode))!=0) {   // Quick check if there is a direct Previous available.
 725     *io_bnode=bn;
 726     return(0);
 727   }
 728   else {
 729     ULONG key=BE2L((*io_bnode)->be_key);
 730     BLCK blockwithprevious=0;
 731     LONG errorcode;
 732
 733     /* No direct previous was available, so we walk the tree: */
 734
 735     while((errorcode=readcachebuffercheck(io_cb, rootblock, BNODECONTAINER_ID))==0) {
 736       struct fsBNodeContainer *bnc=(*io_cb)->data;
 737       struct BTreeContainer *btc=&bnc->btc;
 738
 739       bn=searchforbnode(key, btc);
 740
 741       if((*io_bnode=previous(btc, bn))!=0) {
 742         blockwithprevious=BE2L((*io_bnode)->be_data);
 743       }
 744
 745       if(btc->isleaf==TRUE) {
 746         /* Traversed the tree to the end. */
 747
 748         if(*io_bnode!=0 || blockwithprevious==0) {  // Checks if previous is in this block, or no previous was found ever.
 749           break;
 750         }
 751
 752         errorcode=findbnode(blockwithprevious, key, io_cb, io_bnode);
 753         break;
 754       }
 755
 756       rootblock=BE2L(bn->be_data);
 757     }
 758
 759     return(errorcode);
 760   }
 761 }
 762
 763
 764
 765 LONG lastbnode(BLCK rootblock, struct CacheBuffer **returned_cb, struct BNode **returned_bnode) {
 766   return(findbnode(rootblock, 0xFFFFFFFF, returned_cb, returned_bnode));
 767 }