src/WINNT/afsd/cm_btree.c

   1 /*
   2  * Copyright 2007 Secure Endpoints Inc.
   3  *
   4  * All Rights Reserved.
   5  *
   6  * This software has been released under the terms of the IBM Public
   7  * License.  For details, see the LICENSE file in the top-level source
   8  * directory or online at http://www.openafs.org/dl/license10.html
   9  *
  10  * Thanks to Jan Jannink for B+ tree algorithms.
  11  */
  12
  13 #include <windows.h>
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <assert.h>
  17 #include "afsd.h"
  18
  19 #ifdef USE_BPLUS
  20 #include "cm_btree.h"
  21
  22 /******************* statistics globals  *********************************/
  23 afs_uint32 bplus_lookup_hits = 0;
  24 afs_uint32 bplus_lookup_hits_inexact = 0;
  25 afs_uint32 bplus_lookup_misses = 0;
  26 afs_uint32 bplus_lookup_ambiguous = 0;
  27 afs_uint32 bplus_create_entry = 0;
  28 afs_uint32 bplus_remove_entry = 0;
  29 afs_uint32 bplus_build_tree = 0;
  30 afs_uint32 bplus_free_tree = 0;
  31 afs_uint32 bplus_dv_error = 0;
  32
  33 afs_uint64 bplus_lookup_time = 0;
  34 afs_uint64 bplus_create_time = 0;
  35 afs_uint64 bplus_remove_time = 0;
  36 afs_uint64 bplus_build_time = 0;
  37 afs_uint64 bplus_free_time = 0;
  38
  39 /***********************   private functions   *************************/
  40 static void initFreeNodePool(Tree *B, int quantity);
  41 static Nptr getFreeNode(Tree *B);
  42 static void putFreeNode(Tree *B, Nptr self);
  43 static void cleanupNodePool(Tree *B);
  44
  45 static Nptr descendToLeaf(Tree *B, Nptr curr);
  46 static int getSlot(Tree *B, Nptr curr);
  47 static int findKey(Tree *B, Nptr curr, int lo, int hi);
  48 static int bestMatch(Tree *B, Nptr curr, int slot);
  49
  50 static Nptr getDataNode(Tree *B, keyT key, dataT data);
  51 static Nptr descendSplit(Tree *B, Nptr curr);
  52 static void insertEntry(Tree *B, Nptr node, int slot, Nptr sibling, Nptr downPtr);
  53 static void placeEntry(Tree *B, Nptr node, int slot, Nptr downPtr);
  54 static Nptr split(Tree *B, Nptr node);
  55 static void makeNewRoot(Tree *B, Nptr oldRoot, Nptr newNode);
  56
  57 static Nptr descendBalance(Tree *B, Nptr curr, Nptr left, Nptr right, Nptr lAnc, Nptr rAnc, Nptr parent);
  58 static void collapseRoot(Tree *B, Nptr oldRoot, Nptr newRoot);
  59 static void removeEntry(Tree *B, Nptr curr, int slot);
  60 static Nptr merge(Tree *B, Nptr left, Nptr right, Nptr anchor);
  61 static Nptr shift(Tree *B, Nptr left, Nptr right, Nptr anchor);
  62
  63 static void _clrentry(Nptr node, int entry);
  64 static void _pushentry(Nptr node, int entry, int offset);
  65 static void _pullentry(Nptr node, int entry, int offset);
  66 static void _xferentry(Nptr srcNode, int srcEntry, Nptr destNode, int destEntry);
  67 static void _setentry(Nptr node, int entry, keyT key, Nptr downNode);
  68
  69 #ifdef DEBUG_BTREE
  70 static int _isRoot(Tree *B, Nptr n)
  71 {
  72     int flagset = ((n->flags & isROOT) == isROOT);
  73
  74     if (!isnode(n))
  75         return 0;
  76
  77     if (flagset && n != getroot(B))
  78         DebugBreak();
  79
  80     return flagset;
  81 }
  82
  83 static int _isFew(Tree *B, Nptr n)
  84 {
  85     int flagset = ((n->flags & FEWEST) == FEWEST);
  86     int fanout = getminfanout(B, n);
  87     int entries = numentries(n);
  88     int mincnt  = entries <= fanout;
  89
  90     if (!isnode(n))
  91         return 0;
  92
  93     if (flagset && !mincnt || !flagset && mincnt)
  94         DebugBreak();
  95
  96     return flagset;
  97 }
  98
  99 static int _isFull(Tree *B, Nptr n)
 100 {
 101     int flagset = ((n->flags & isFULL) == isFULL);
 102     int maxcnt  = numentries(n) == getfanout(B);
 103
 104     if (!isnode(n))
 105         return 0;
 106
 107     if (flagset && !maxcnt || !flagset && maxcnt)
 108         DebugBreak();
 109
 110     return flagset;
 111 }
 112 #endif /* DEBUG_BTREE */
 113
 114 /***********************************************************************\
 115 |       B+tree Initialization and Cleanup Routines                      |
 116 \***********************************************************************/
 117
 118 /********************   Set up B+tree structure   **********************/
 119 Tree *initBtree(unsigned int poolsz, unsigned int fanout, KeyCmp keyCmp)
 120 {
 121     Tree *B;
 122     keyT empty = {NULL};
 123     dataT data = {0,0,0,0};
 124
 125     if (fanout > MAX_FANOUT)
 126         fanout = MAX_FANOUT;
 127
 128     setbplustree(B, malloc(sizeof(Tree)));
 129     memset(B, 0, sizeof(Tree));
 130     setfanout(B, fanout);
 131     setminfanout(B, (fanout + 1) >> 1);
 132     initFreeNodePool(B, poolsz);
 133
 134     setleaf(B, getFreeNode(B));         /* set up the first leaf node */
 135     setroot(B, getleaf(B));             /* the root is initially the leaf */
 136     setflag(getroot(B), isLEAF);
 137     setflag(getroot(B), isROOT);
 138     setflag(getroot(B), FEWEST);
 139     inittreeheight(B);
 140
 141     setfunkey(B,empty);
 142     setfundata(B,data);
 143     setcomparekeys(B, keyCmp);
 144
 145 #ifdef DEBUG_BTREE
 146     sprintf(B->message, "INIT:  B+tree of fanout %d at %10p.\n", fanout, (void *)B);
 147     OutputDebugString(B->message);
 148 #endif
 149
 150   return B;
 151 }
 152
 153 /********************   Clean up B+tree structure   ********************/
 154 /*
 155  *  dirlock must be write locked
 156  */
 157 void freeBtree(Tree *B)
 158 {
 159 #ifdef DEBUG_BTREE
 160     sprintf(B->message, "FREE:  B+tree at %10p.\n", (void *) B);
 161     OutputDebugString(B->message);
 162 #endif
 163
 164     cleanupNodePool(B);
 165
 166     memset(B, 0, sizeof(*B));
 167     free((void *) B);
 168 }
 169
 170
 171 /***********************************************************************\
 172 |       Find location for data                                          |
 173 \***********************************************************************/
 174
 175 /**********************   top level lookup   **********************/
 176 Nptr bplus_Lookup(Tree *B, keyT key)
 177 {
 178     Nptr        findNode;
 179
 180 #ifdef DEBUG_BTREE
 181     sprintf(B->message, "LOOKUP:  key %s.\n", key.name);
 182     OutputDebugString(B->message);
 183 #endif
 184
 185     setfunkey(B, key);                  /* set search key */
 186     findNode = descendToLeaf(B, getroot(B));    /* start search from root node */
 187
 188 #ifdef DEBUG_BTREE
 189     if (findNode) {
 190         int         slot;
 191         Nptr        dataNode;
 192         dataT       data;
 193
 194         slot = findKey(B, findNode, 1, numentries(findNode));
 195         dataNode = getnode(findNode, slot);
 196         data = getdatavalue(dataNode);
 197
 198         sprintf(B->message, "LOOKUP: %s found on page %d value (%d.%d.%d).\n",
 199                  key.name,
 200                  getnodenumber(B, findNode),
 201                  data.fid.volume,
 202                  data.fid.vnode,
 203                  data.fid.unique);
 204     } else
 205         sprintf(B->message, "LOOKUP: not found!\n");
 206     OutputDebugString(B->message);
 207 #endif
 208
 209     return findNode;
 210 }
 211
 212 /**********************   `recurse' down B+tree   **********************/
 213 static Nptr descendToLeaf(Tree *B, Nptr curr)
 214 {
 215     int slot;
 216     Nptr        findNode;
 217     Nptr    prev[64];
 218     int depth;
 219
 220     memset(prev, 0, sizeof(prev));
 221
 222     for (depth = 0, slot = getSlot(B, curr); isinternal(curr); depth++, slot = getSlot(B, curr)) {
 223         prev[depth] = curr;
 224         if (slot == 0)
 225             curr = getfirstnode(curr);
 226         else
 227             curr = getnode(curr, slot);
 228 #ifdef DEBUG_BTREE
 229         if ( !isnode(curr) )
 230             DebugBreak();
 231 #endif
 232     }
 233     if ((slot > 0) && !comparekeys(B)(getfunkey(B), getkey(curr, slot), 0))
 234         findNode = curr;                        /* correct key value found */
 235     else
 236         findNode = NONODE;                      /* key value not in tree */
 237
 238     return findNode;
 239 }
 240
 241 /********************   find slot for search key   *********************/
 242 static int getSlot(Tree *B, Nptr curr)
 243 {
 244     int slot, entries;
 245
 246     entries = numentries(curr);         /* need this if root is ever empty */
 247     slot = !entries ? 0 : findKey(B, curr, 1, entries);
 248
 249     return slot;
 250 }
 251
 252
 253 /********************   recursive binary search   **********************/
 254 static int findKey(Tree *B, Nptr curr, int lo, int hi)
 255 {
 256     int mid, findslot = BTERROR;
 257
 258     if (hi == lo) {
 259         findslot = bestMatch(B, curr, lo);              /* recursion base case */
 260
 261 #ifdef DEBUG_BTREE
 262         if (findslot == BTERROR) {
 263             sprintf(B->message, "Bad key ordering on node %d\n", getnodenumber(B, curr));
 264             OutputDebugString(B->message);
 265         }
 266 #endif
 267     } else {
 268         mid = (lo + hi) >> 1;
 269         switch (findslot = bestMatch(B, curr, mid)) {
 270         case BTLOWER:                           /* check lower half of range */
 271             findslot = findKey(B, curr, lo, mid - 1);           /* never in 2-3+trees */
 272             break;
 273         case BTUPPER:                           /* check upper half of range */
 274             findslot = findKey(B, curr, mid + 1, hi);
 275             break;
 276         case BTERROR:
 277             sprintf(B->message, "Bad key ordering on node %d\n", getnodenumber(B, curr));
 278             OutputDebugString(B->message);
 279         }
 280     }
 281     return findslot;
 282 }
 283
 284
 285 /************   comparison of key with a target key slot   *************/
 286 static int bestMatch(Tree *B, Nptr curr, int slot)
 287 {
 288     int diff, comp, findslot;
 289
 290     diff = comparekeys(B)(getfunkey(B), getkey(curr, slot), 0);
 291     if (diff < 0) {             /* also check previous slot */
 292         if ((slot == 1) ||
 293              ((comp = comparekeys(B)(getfunkey(B), getkey(curr, slot - 1), 0)) >= 0))
 294         {
 295             findslot = slot - 1;
 296         }
 297         else if (comp < diff) {
 298             findslot = BTERROR;         /* inconsistent ordering of keys */
 299 #ifdef DEBUG_BTREE
 300             DebugBreak();
 301 #endif
 302         }
 303         else {
 304             findslot = BTLOWER;         /* key must be below in node ordering */
 305         }
 306     } else {                    /* or check following slot */
 307         if ((slot == numentries(curr)) ||
 308              ((comp = comparekeys(B)(getfunkey(B), getkey(curr, slot + 1), 0)) < 0))
 309         {
 310             findslot = slot;
 311         }
 312         else if (comp == 0) {
 313             findslot = slot + 1;
 314         }
 315         else if (comp > diff) {
 316             findslot = BTERROR;         /* inconsistent ordering of keys */
 317 #ifdef DEBUG_BTREE
 318             DebugBreak();
 319 #endif
 320         }
 321         else {
 322             findslot = BTUPPER;         /* key must be above in node ordering */
 323         }
 324     }
 325     return findslot;
 326 }
 327
 328
 329 /***********************************************************************\
 330 |       Insert new data into tree                                       |
 331 \***********************************************************************/
 332
 333
 334 /**********************   top level insert call   **********************/
 335 void insert(Tree *B, keyT key, dataT data)
 336 {
 337     Nptr newNode;
 338
 339 #ifdef DEBUG_BTREE
 340     sprintf(B->message, "INSERT:  key %s.\n", key.name);
 341     OutputDebugString(B->message);
 342 #endif
 343
 344     setfunkey(B, key);                          /* set insertion key */
 345     setfundata(B, data);                        /* a node containing data */
 346     setsplitpath(B, NONODE);
 347     newNode = descendSplit(B, getroot(B));      /* insertion point search from root */
 348     if (newNode != getsplitpath(B))             /* indicates the root node has split */
 349         makeNewRoot(B, getroot(B), newNode);
 350 }
 351
 352
 353 /*****************   recurse down and split back up   ******************/
 354 static Nptr
 355 descendSplit(Tree *B, Nptr curr)
 356 {
 357     Nptr        downNode = NONODE, sibling = NONODE;
 358     int slot;
 359
 360 #ifdef DEBUG_BTREE
 361     if (!isnode(curr))
 362         DebugBreak();
 363 #endif
 364     if (!isfull(curr))
 365         setsplitpath(B, NONODE);
 366     else if (getsplitpath(B) == NONODE)
 367         setsplitpath(B, curr);                  /* indicates where nodes must split */
 368
 369     slot = getSlot(B, curr);                    /* is null only if the root is empty */
 370     if (isinternal(curr)) {     /* continue recursion to leaves */
 371         if (slot == 0)
 372             downNode = descendSplit(B, getfirstnode(curr));
 373         else
 374             downNode = descendSplit(B, getnode(curr, slot));
 375     } else if ((slot > 0) && !comparekeys(B)(getfunkey(B), getkey(curr, slot), 0)) {
 376         if (!(gettreeflags(B) & TREE_FLAG_UNIQUE_KEYS)) {
 377             downNode = getDataNode(B, getfunkey(B), getfundata(B));
 378             getdatanext(downNode) = getnode(curr,slot);
 379             setnode(curr, slot, downNode);
 380         }
 381         downNode = NONODE;
 382         setsplitpath(B, NONODE);
 383     }
 384     else
 385         downNode = getDataNode(B, getfunkey(B), getfundata(B)); /* an insertion takes place */
 386
 387     if (downNode != NONODE) {                   /* insert only where necessary */
 388         if (getsplitpath(B) != NONODE)
 389             sibling = split(B, curr);           /* a sibling node is prepared */
 390         insertEntry(B, curr, slot, sibling, downNode);
 391     }
 392
 393     return sibling;
 394 }
 395
 396 /***************   determine location of inserted key   ****************/
 397 static void
 398 insertEntry(Tree *B, Nptr currNode, int slot, Nptr sibling, Nptr downPtr)
 399 {
 400     int split, i, j, k, x, y;
 401     keyT key;
 402
 403 #ifdef DEBUG_BTREE
 404     sprintf(B->message, "INSERT:  slot %d, down node %d.\n", slot, getnodenumber(B, downPtr));
 405     OutputDebugString(B->message);
 406 #endif
 407
 408     if (sibling == NONODE) {            /* no split occurred */
 409         placeEntry(B, currNode, slot + 1, downPtr);
 410     }
 411     else {                              /* split entries between the two */
 412         if isinternal(currNode) {
 413             i = 1;
 414             split = getfanout(B) - getminfanout(B, currNode);
 415         } else if (isroot(currNode)) {
 416             /* split the root node and turn it into just a leaf */
 417             i = 0;
 418             split = getminfanout(B, currNode);
 419         } else  {
 420             i = 0;
 421             split = getminfanout(B, currNode);
 422         }
 423         j = (slot != split ? 1 : 0);
 424         k = (slot >= split ? 1 : 0);
 425
 426         /*
 427          * Move entries from the top half of the current node to
 428          * to the sibling node.
 429          * The number of entries to move is dependent upon where
 430          * the new entry is going to be added in relationship to
 431          * the split slot. (slots are 1-based).  If order to produce
 432          * a balanced tree, if the insertion slot is greater than
 433          * the split we move one less entry as the new entry will
 434          * be inserted into the sibling.
 435          *
 436          * If the node that is being split is an internal node (i != 0)
 437          * then we move one less entry due to the extra down pointer
 438          * when the split slot is not equal to the insertion slot
 439          */
 440         for (x = split + k + j * i, y = 1; x <= getfanout(B); x++, y++) {
 441             xferentry(currNode, x, sibling, y); /* copy entries to sibling */
 442             clrentry(currNode, x);
 443             decentries(currNode);
 444             incentries(sibling);
 445
 446 #ifdef DEBUG_BTREE
 447             if (getkey(sibling, numentries(sibling)).name == NULL)
 448                 DebugBreak();
 449 #endif
 450         }
 451         clrflag(currNode, isFULL);
 452         if (numentries(currNode) == getminfanout(B, currNode))
 453             setflag(currNode, FEWEST);          /* never happens in even size nodes */
 454
 455 #ifdef DEBUG_BTREE
 456         if (numentries(sibling) > getfanout(B))
 457             DebugBreak();
 458 #endif
 459         if (numentries(sibling) == getfanout(B))
 460             setflag(sibling, isFULL);           /* only ever happens in 2-3+trees */
 461
 462         if (numentries(sibling) > getminfanout(B, sibling))
 463             clrflag(sibling, FEWEST);
 464
 465         if (i) {                                /* set first pointer of internal node */
 466             if (j) {
 467                 setfirstnode(sibling, getnode(currNode, split + k));
 468                 decentries(currNode);
 469                 if (numentries(currNode) == getminfanout(B, currNode))
 470                     setflag(currNode, FEWEST);
 471                 else
 472                     clrflag(currNode, FEWEST);
 473             }
 474             else
 475                 setfirstnode(sibling, downPtr);
 476         }
 477
 478         if (j) {                                /* insert new entry into correct spot */
 479             if (k)
 480                 placeEntry(B, sibling, slot - split + 1 - i, downPtr);
 481             else
 482                 placeEntry(B, currNode, slot + 1, downPtr);
 483
 484             /* set key separating nodes */
 485             if (isleaf(sibling))
 486                 key = getkey(sibling, 1);
 487             else {
 488                 Nptr leaf = getfirstnode(sibling);
 489                 while ( isinternal(leaf) )
 490                     leaf = getfirstnode(leaf);
 491                 key = getkey(leaf, 1);
 492             }
 493             setfunkey(B, key);
 494         }
 495         else if (!i)
 496             placeEntry(B, sibling, 1, downPtr);
 497     }
 498 }
 499
 500 /************   place key into appropriate node & slot   ***************/
 501 static void
 502 placeEntry(Tree *B, Nptr node, int slot, Nptr downPtr)
 503 {
 504     int x;
 505
 506 #ifdef DEBUG_BTREE
 507     if (isfull(node))
 508         DebugBreak();
 509 #endif
 510
 511 #ifdef DEBUG_BTREE
 512     if (numentries(node) != 0 && getkey(node, numentries(node)).name == NULL)
 513         DebugBreak();
 514 #endif
 515     for (x = numentries(node); x >= slot && x != 0; x--)        /* make room for new entry */
 516         pushentry(node, x, 1);
 517     setentry(node, slot, getfunkey(B), downPtr);/* place it in correct slot */
 518
 519     incentries(node);                           /* adjust entry counter */
 520 #ifdef DEBUG_BTREE
 521         if (getkey(node, numentries(node)).name == NULL)
 522                 DebugBreak();
 523 #endif
 524
 525     if (numentries(node) == getfanout(B))
 526         setflag(node, isFULL);
 527     if (numentries(node) > getminfanout(B, node))
 528         clrflag(node, FEWEST);
 529     else
 530         setflag(node, FEWEST);
 531 }
 532
 533
 534 /*****************   split full node and set flags   *******************/
 535 static Nptr
 536 split(Tree *B, Nptr node)
 537 {
 538     Nptr sibling;
 539
 540     sibling = getFreeNode(B);
 541
 542     setflag(sibling, FEWEST);                   /* set up node flags */
 543
 544     if (isleaf(node)) {
 545         setflag(sibling, isLEAF);
 546         setnextnode(sibling, getnextnode(node));/* adjust leaf pointers */
 547         setnextnode(node, sibling);
 548     }
 549     if (getsplitpath(B) == node)
 550         setsplitpath(B, NONODE);                /* no more splitting needed */
 551
 552     if (isroot(node))
 553         clrflag(node, isROOT);
 554
 555     return sibling;
 556 }
 557
 558
 559 /**********************   build new root node   ************************/
 560 static void
 561 makeNewRoot(Tree *B, Nptr oldRoot, Nptr newNode)
 562 {
 563     setroot(B, getFreeNode(B));
 564
 565     setfirstnode(getroot(B), oldRoot);  /* old root becomes new root's child */
 566     setentry(getroot(B), 1, getfunkey(B), newNode);     /* old root's sibling also */
 567     incentries(getroot(B));
 568 #ifdef DEBUG_BTREE
 569     if (numentries(getroot(B)) > getfanout(B))
 570         DebugBreak();
 571 #endif
 572
 573     /* the oldRoot's isROOT flag was cleared in split() */
 574     setflag(getroot(B), isROOT);
 575     setflag(getroot(B), FEWEST);
 576     clrflag(getroot(B), isLEAF);
 577     inctreeheight(B);
 578 }
 579
 580
 581 /***********************************************************************\
 582 |       Delete data from tree                                           |
 583 \***********************************************************************/
 584
 585 /**********************   top level delete call   **********************\
 586 |
 587 |       The recursive call for deletion carries 5 additional parameters
 588 |       which may be needed to rebalance the B+tree when removing the key.
 589 |       These parameters are:
 590 |               1. immediate left neighbor of the current node
 591 |               2. immediate right neighbor of the current node
 592 |               3. the anchor of the current node and left neighbor
 593 |               4. the anchor of the current node and right neighbor
 594 |               5. the parent of the current node
 595 |
 596 |       All of these parameters are simple to calculate going along the
 597 |       recursive path to the leaf nodes and the point of key deletion.
 598 |       At that time, the algorithm determines which node manipulations
 599 |       are most efficient, that is, cause the least rearranging of data,
 600 |       and minimize the need for non-local key manipulation.
 601 |
 602 \***********************************************************************/
 603 void delete(Tree *B, keyT key)
 604 {
 605     Nptr newNode;
 606
 607 #ifdef DEBUG_BTREE
 608     sprintf(B->message, "DELETE:  key %s.\n", key.name);
 609     OutputDebugString(B->message);
 610 #endif
 611
 612     setfunkey(B, key);                  /* set deletion key */
 613     setmergepath(B, NONODE);
 614     newNode = descendBalance(B, getroot(B), NONODE, NONODE, NONODE, NONODE, NONODE);
 615     if (isnode(newNode)) {
 616 #ifdef DEBUG_BTREE
 617         sprintf(B->message, "DELETE: collapsing node %d", getnodenumber(B, newNode));
 618         OutputDebugString(B->message);
 619 #endif
 620         collapseRoot(B, getroot(B), newNode);   /* remove root when superfluous */
 621     }
 622 }
 623
 624
 625 /**********************   remove old root node   ***********************/
 626 static void
 627 collapseRoot(Tree *B, Nptr oldRoot, Nptr newRoot)
 628 {
 629
 630 #ifdef DEBUG_BTREE
 631     sprintf(B->message, "COLLAPSE:  old %d, new %d.\n", getnodenumber(B, oldRoot), getnodenumber(B, newRoot));
 632     OutputDebugString(B->message);
 633     showNode(B, "collapseRoot oldRoot", oldRoot);
 634     showNode(B, "collapseRoot newRoot", newRoot);
 635 #endif
 636
 637     setroot(B, newRoot);
 638     setflag(newRoot, isROOT);
 639     clrflag(newRoot, FEWEST);
 640     putFreeNode(B, oldRoot);
 641     dectreeheight(B);                   /* the height of the tree decreases */
 642 }
 643
 644
 645 /****************   recurse down and balance back up   *****************/
 646 static Nptr
 647 descendBalance(Tree *B, Nptr curr, Nptr left, Nptr right, Nptr lAnc, Nptr rAnc, Nptr parent)
 648 {
 649     Nptr        newMe=NONODE, myLeft=NONODE, myRight=NONODE, lAnchor=NONODE, rAnchor=NONODE, newNode=NONODE;
 650     int slot = 0, notleft = 0, notright = 0, fewleft = 0, fewright = 0, test = 0;
 651
 652 #ifdef DEBUG_BTREE
 653     sprintf(B->message, "descendBalance curr %d, left %d, right %d, lAnc %d, rAnc %d, parent %d\n",
 654              curr ? getnodenumber(B, curr) : -1,
 655              left ? getnodenumber(B, left) : -1,
 656              right ? getnodenumber(B, right) : -1,
 657              lAnc ? getnodenumber(B, lAnc) : -1,
 658              rAnc ? getnodenumber(B, rAnc) : -1,
 659              parent ? getnodenumber(B, parent) : -1);
 660     OutputDebugString(B->message);
 661 #endif
 662
 663     if (!isfew(curr))
 664         setmergepath(B,NONODE);
 665     else if (getmergepath(B) == NONODE)
 666         setmergepath(B, curr);          /* mark which nodes may need rebalancing */
 667
 668     slot = getSlot(B, curr);
 669
 670     if (isinternal(curr))       /* set up next recursion call's parameters */
 671     {
 672         if (slot == 0) {
 673             newNode = getfirstnode(curr);
 674             myLeft = !isnode(left) ? NONODE : getlastnode(left);
 675             lAnchor = lAnc;
 676         }
 677         else {
 678             newNode = getnode(curr, slot);
 679             if (slot == 1)
 680                 myLeft = getfirstnode(curr);
 681             else
 682                 myLeft = getnode(curr, slot - 1);
 683             lAnchor = curr;
 684         }
 685
 686         if (slot == numentries(curr)) {
 687             myRight = !isnode(right) ? NONODE : getfirstnode(right);
 688             rAnchor = rAnc;
 689         }
 690         else {
 691             myRight = getnode(curr, slot + 1);
 692             rAnchor = curr;
 693         }
 694         newMe = descendBalance(B, newNode, myLeft, myRight, lAnchor, rAnchor, curr);
 695     }
 696     else if ((slot > 0) && !comparekeys(B)(getfunkey(B), getkey(curr, slot), 0))
 697     {
 698         Nptr        next;
 699         int         exact = 0;
 700         int         count = 0;
 701
 702         newNode = getnode(curr, slot);
 703         next = getdatanext(newNode);
 704
 705         /*
 706          * We only delete exact matches.
 707          */
 708         if (!comparekeys(B)(getfunkey(B), getdatakey(newNode), EXACT_MATCH)) {
 709             /* exact match, free the first entry */
 710             setnode(curr, slot, next);
 711
 712             if (next == NONODE) {
 713                 /* delete this key as there are no more data values */
 714                 newMe = newNode;
 715             } else {
 716                 /* otherwise, there are more and we leave the key in place */
 717                 setnode(curr, slot, next);
 718                 putFreeNode(B, newNode);
 719
 720                 /* but do not delete the key */
 721                 newMe = NONODE;
 722                 setmergepath(B, NONODE);
 723             }
 724         } else if (next == NONODE) {
 725             /*
 726              * we didn't find an exact match and there are no more
 727              * choices.  so we leave it alone and remove nothing.
 728              */
 729             newMe = NONODE;
 730             setmergepath(B, NONODE);
 731         } else {
 732             /* The first data node doesn't match but there are other
 733              * options.  So we must determine if any of the next nodes
 734              * are the one we are looking for.
 735              */
 736             Nptr prev = newNode;
 737
 738             while ( next ) {
 739                 if (!comparekeys(B)(getfunkey(B), getdatakey(next), EXACT_MATCH)) {
 740                     /* we found the one to delete */
 741                     getdatanext(prev) = getdatanext(next);
 742                     putFreeNode(B, next);
 743                     break;
 744                 }
 745                 prev = next;
 746                 next = getdatanext(next);
 747             }
 748
 749             /* do not delete the key */
 750             newMe = NONODE;
 751             setmergepath(B, NONODE);
 752         }
 753     }
 754     else
 755     {
 756         newMe = NONODE;         /* no deletion possible, key not found */
 757         setmergepath(B, NONODE);
 758     }
 759
 760 /*****************   rebalancing tree after deletion   *****************\
 761 |
 762 |       The simplest B+tree rebalancing consists of the following rules.
 763 |
 764 |       If a node underflows:
 765 |       CASE 1 check if it is the root, and collapse it if it is,
 766 |       CASE 2 otherwise, check if both of its neighbors are minimum
 767 |           sized and merge the underflowing node with one of them,
 768 |       CASE 3 otherwise shift surplus entries to the underflowing node.
 769 |
 770 |       The choice of which neighbor to use is optional.  However, the
 771 |       rebalancing rules that follow also ensure whenever possible
 772 |       that the merges and shifts which do occur use a neighbor whose
 773 |       anchor is the parent of the underflowing node.
 774 |
 775 |       Cases 3, 4, 5 below are more an optimization than a requirement,
 776 |       and can be omitted, with a change of the action value in case 6,
 777 |       which actually corresponds to the third case described above.
 778 |
 779 \***********************************************************************/
 780
 781     /* begin deletion, working upwards from leaves */
 782
 783     if (newMe != NONODE) {      /* this node removal doesn't consider duplicates */
 784 #ifdef DEBUG_BTREE
 785         sprintf(B->message, "descendBalance DELETE:  slot %d, node %d.\n", slot, getnodenumber(B, curr));
 786         OutputDebugString(B->message);
 787 #endif
 788
 789         removeEntry(B, curr, slot + (newMe != newNode));        /* removes one of two */
 790
 791 #ifdef DEBUG_BTREE
 792         showNode(B, "descendBalance curr", curr);
 793 #endif
 794     }
 795
 796     if (getmergepath(B) == NONODE)
 797         newNode = NONODE;
 798     else {              /* tree rebalancing rules for node merges and shifts */
 799         notleft = !isnode(left);
 800         notright = !isnode(right);
 801         if (!notleft)
 802             fewleft = isfew(left);              /* only used when defined */
 803         if (!notright)
 804             fewright = isfew(right);
 805
 806         /* CASE 1:  prepare root node (curr) for removal */
 807         if (notleft && notright) {
 808             test = isleaf(curr);                /* check if B+tree has become empty */
 809             newNode = test ? NONODE : getfirstnode(curr);
 810         }
 811         /* CASE 2:  the merging of two nodes is a must */
 812         else if ((notleft || fewleft) && (notright || fewright)) {
 813             test = (lAnc != parent);
 814             newNode = test ? merge(B, curr, right, rAnc) : merge(B, left, curr, lAnc);
 815         }
 816         /* CASE 3: choose the better of a merge or a shift */
 817         else if (!notleft && fewleft && !notright && !fewright) {
 818             test = (rAnc != parent) && (curr == getmergepath(B));
 819             newNode = test ? merge(B, left, curr, lAnc) : shift(B, curr, right, rAnc);
 820         }
 821         /* CASE 4: also choose between a merge or a shift */
 822         else if (!notleft && !fewleft && !notright && fewright) {
 823             test = !(lAnc == parent) && (curr == getmergepath(B));
 824             newNode = test ? merge(B, curr, right, rAnc) : shift(B, left, curr, lAnc);
 825         }
 826         /* CASE 5: choose the more effective of two shifts */
 827         else if (lAnc == rAnc) {                /* => both anchors are the parent */
 828             test = (numentries(left) <= numentries(right));
 829             newNode = test ? shift(B, curr, right, rAnc) : shift(B, left, curr, lAnc);
 830         }
 831         /* CASE 6: choose the shift with more local effect */
 832         else {                          /* if omitting cases 3,4,5 use below */
 833             test = (lAnc == parent);            /* test = (!notleft && !fewleft); */
 834             newNode = test ? shift(B, left, curr, lAnc) : shift(B, curr, right, rAnc);
 835         }
 836     }
 837
 838 #ifdef DEBUG_BTREE
 839     sprintf(B->message, "descendBalance returns %d\n", getnodenumber(B, newNode));
 840     OutputDebugString(B->message);
 841 #endif
 842     return newNode;
 843 }
 844
 845
 846 /****************   remove key and pointer from node   *****************/
 847 static void
 848 removeEntry(Tree *B, Nptr curr, int slot)
 849 {
 850     int x;
 851
 852     putFreeNode(B, getnode(curr, slot));        /* return deleted node to free list */
 853     for (x = slot; x < numentries(curr); x++)
 854         pullentry(curr, x, 1);                  /* adjust node with removed key */
 855     decentries(curr);
 856     clrflag(curr, isFULL);                      /* keep flag information up to date */
 857     if (numentries(curr) > getminfanout(B, curr))
 858         clrflag(curr, FEWEST);
 859     else
 860         setflag(curr, FEWEST);
 861 }
 862
 863
 864 /*******   merge a node pair & set emptied node up for removal   *******/
 865 static Nptr
 866 merge(Tree *B, Nptr left, Nptr right, Nptr anchor)
 867 {
 868     int x, y, z;
 869
 870 #ifdef DEBUG_BTREE
 871     sprintf(B->message, "MERGE:  left %d, right %d.\n", getnodenumber(B, left), getnodenumber(B, right));
 872     OutputDebugString(B->message);
 873     showNode(B, "pre-merge anchor", anchor);
 874     showNode(B, "pre-merge left", left);
 875     showNode(B, "pre-merge right", right);
 876 #endif
 877
 878     if (isinternal(left)) {
 879         incentries(left);                       /* copy key separating the nodes */
 880 #ifdef DEBUG_BTREE
 881         if (numentries(left) > getfanout(B))
 882             DebugBreak();
 883 #endif
 884         setfunkey(B, getkey(right, 1)); /* defined but maybe just deleted */
 885         z = getSlot(B, anchor);         /* needs the just calculated key */
 886         setfunkey(B, getkey(anchor, z));        /* set slot to delete in anchor */
 887         setentry(left, numentries(left), getfunkey(B), getfirstnode(right));
 888     }
 889     else
 890         setnextnode(left, getnextnode(right));
 891
 892     for (x = numentries(left) + 1, y = 1; y <= numentries(right); x++, y++) {
 893         incentries(left);
 894 #ifdef DEBUG_BTREE
 895         if (numentries(left) > getfanout(B))
 896             DebugBreak();
 897 #endif
 898         xferentry(right, y, left, x);   /* transfer entries to left node */
 899     }
 900     clearentries(right);
 901
 902     if (numentries(left) > getminfanout(B, left))
 903         clrflag(left, FEWEST);
 904     if (numentries(left) == getfanout(B))
 905         setflag(left, isFULL);          /* never happens in even size nodes */
 906
 907     if (getmergepath(B) == left || getmergepath(B) == right)
 908         setmergepath(B, NONODE);                /* indicate rebalancing is complete */
 909
 910 #ifdef DEBUG_BTREE
 911     showNode(B, "post-merge anchor", anchor);
 912     showNode(B, "post-merge left", left);
 913     showNode(B, "post-merge right", right);
 914 #endif
 915     return right;
 916 }
 917
 918
 919 /******   shift entries in a node pair & adjust anchor key value   *****/
 920 static Nptr
 921 shift(Tree *B, Nptr left, Nptr right, Nptr anchor)
 922 {
 923     int i, x, y, z;
 924
 925 #ifdef DEBUG_BTREE
 926     sprintf(B->message, "SHIFT:  left %d, right %d, anchor %d.\n",
 927              getnodenumber(B, left),
 928              getnodenumber(B, right),
 929              getnodenumber(B, anchor));
 930     OutputDebugString(B->message);
 931     showNode(B, "pre-shift anchor", anchor);
 932     showNode(B, "pre-shift left", left);
 933     showNode(B, "pre-shift right", right);
 934 #endif
 935
 936     i = isinternal(left);
 937
 938     if (numentries(left) < numentries(right)) { /* shift entries to left */
 939         y = (numentries(right) - numentries(left)) >> 1;
 940         x = numentries(left) + y;
 941         setfunkey(B, getkey(right, y + 1 - i)); /* set new anchor key value */
 942         z = getSlot(B, anchor);                 /* find slot in anchor node */
 943 #ifdef DEBUG_BTREE
 944         if (z == 0 && !isroot(anchor))
 945             DebugBreak();
 946 #endif
 947         if (i) {                                        /* move out old anchor value */
 948             decentries(right);                  /* adjust for shifting anchor */
 949             incentries(left);
 950 #ifdef DEBUG_BTREE
 951             if (numentries(left) > getfanout(B))
 952                 DebugBreak();
 953 #endif
 954             setentry(left, numentries(left), getkey(anchor, z), getfirstnode(right));
 955             setfirstnode(right, getnode(right, y + 1 - i));
 956         }
 957         clrflag(right, isFULL);
 958         setkey(anchor, z, getfunkey(B));                /* set new anchor value */
 959         for (z = y, y -= i; y > 0; y--, x--) {
 960             decentries(right);                  /* adjust entry count */
 961             incentries(left);
 962 #ifdef DEBUG_BTREE
 963             if (numentries(left) > getfanout(B))
 964                 DebugBreak();
 965 #endif
 966             xferentry(right, y, left, x);               /* transfer entries over */
 967         }
 968
 969         for (x = 1; x <= numentries(right); x++)        /* adjust reduced node */
 970             pullentry(right, x, z);
 971     }
 972     else if (numentries(left) > numentries(right)) {                                    /* shift entries to right */
 973         y = (numentries(left) - numentries(right)) >> 1;
 974         x = numentries(left) - y + 1;
 975
 976         for (z = numentries(right); z > 0; z--) /* adjust increased node */
 977             pushentry(right, z, y);
 978
 979         setfunkey(B, getkey(left, x));                  /* set new anchor key value */
 980         z = getSlot(B, anchor) + 1;
 981         if (i) {
 982             decentries(left);
 983             incentries(right);
 984 #ifdef DEBUG_BTREE
 985             if (numentries(right) > getfanout(B))
 986                 DebugBreak();
 987 #endif
 988             setentry(right, y, getkey(anchor, z), getfirstnode(right));
 989             setfirstnode(right, getnode(left, x));
 990         }
 991         clrflag(left, isFULL);
 992         setkey(anchor, z, getfunkey(B));
 993         for (x = numentries(left) + i, y -= i; y > 0; y--, x--) {
 994             decentries(left);
 995             incentries(right);
 996 #ifdef DEBUG_BTREE
 997             if (numentries(right) > getfanout(B))
 998                 DebugBreak();
 999 #endif
1000             xferentry(left, x, right, y);               /* transfer entries over */
1001             clrentry(left, x);
1002         }
1003     }
1004 #ifdef DEBUG_BTREE
1005     else {
1006         DebugBreak();
1007     }
1008 #endif /* DEBUG_BTREE */
1009
1010     if (numentries(left) > getminfanout(B, left))               /* adjust node flags */
1011         clrflag(left, FEWEST);                  /* never happens in 2-3+trees */
1012     else
1013         setflag(left, FEWEST);
1014     if (numentries(right) > getminfanout(B, right))
1015         clrflag(right, FEWEST);                 /* never happens in 2-3+trees */
1016     else
1017         setflag(right, FEWEST);
1018     setmergepath(B, NONODE);
1019
1020 #ifdef DEBUG_BTREE
1021     sprintf(B->message, "SHIFT:  left %d, right %d.\n", getnodenumber(B, left), getnodenumber(B, right));
1022     OutputDebugString(B->message);
1023     showNode(B, "post-shift anchor", anchor);
1024     showNode(B, "post-shift left", left);
1025     showNode(B, "post-shift right", right);
1026 #endif
1027
1028     return NONODE;
1029 }
1030
1031
1032 static void
1033 _clrentry(Nptr node, int entry)
1034 {
1035     if (getkey(node,entry).name != NULL) {
1036         free(getkey(node,entry).name);
1037         getkey(node,entry).name = NULL;
1038     }
1039     getnode(node,entry) = NONODE;
1040 }
1041
1042 static void
1043 _pushentry(Nptr node, int entry, int offset)
1044 {
1045     if (getkey(node,entry + offset).name != NULL)
1046         free(getkey(node,entry + offset).name);
1047 #ifdef DEBUG_BTREE
1048     if (entry == 0)
1049         DebugBreak();
1050 #endif
1051     getkey(node,entry + offset).name = strdup(getkey(node,entry).name);
1052 #ifdef DEBUG_BTREE
1053     if ( getnode(node, entry) == NONODE )
1054         DebugBreak();
1055 #endif
1056     getnode(node,entry + offset) = getnode(node,entry);
1057 }
1058
1059 static void
1060 _pullentry(Nptr node, int entry, int offset)
1061 {
1062     if (getkey(node,entry).name != NULL)
1063         free(getkey(node,entry).name);
1064     getkey(node,entry).name = strdup(getkey(node,entry + offset).name);
1065 #ifdef DEBUG_BTREE
1066     if ( getnode(node, entry + offset) == NONODE )
1067         DebugBreak();
1068 #endif
1069     getnode(node,entry) = getnode(node,entry + offset);
1070 }
1071
1072 static void
1073 _xferentry(Nptr srcNode, int srcEntry, Nptr destNode, int destEntry)
1074 {
1075     if (getkey(destNode,destEntry).name != NULL)
1076         free(getkey(destNode,destEntry).name);
1077     getkey(destNode,destEntry).name = strdup(getkey(srcNode,srcEntry).name);
1078 #ifdef DEBUG_BTREE
1079     if ( getnode(srcNode, srcEntry) == NONODE )
1080         DebugBreak();
1081 #endif
1082     getnode(destNode,destEntry) = getnode(srcNode,srcEntry);
1083 }
1084
1085 static void
1086 _setentry(Nptr node, int entry, keyT key, Nptr downNode)
1087 {
1088     if (getkey(node,entry).name != NULL)
1089         free(getkey(node,entry).name);
1090     getkey(node,entry).name = strdup(key.name);
1091 #ifdef DEBUG_BTREE
1092     if ( downNode == NONODE )
1093         DebugBreak();
1094 #endif
1095     getnode(node,entry) = downNode;
1096 }
1097
1098
1099 /***********************************************************************\
1100 |       Empty Node Utilities                                            |
1101 \***********************************************************************/
1102
1103 /*********************   Set up initial pool of free nodes   ***********/
1104 static void
1105 initFreeNodePool(Tree *B, int quantity)
1106 {
1107     int i;
1108     Nptr        n, p;
1109
1110     setfirstallnode(B, NONODE);
1111     setfirstfreenode(B, NONODE);
1112
1113     for (i = 0, p = NONODE; i < quantity; i++) {
1114         n = malloc(sizeof(*n));
1115         memset(n, 0, sizeof(*n));
1116         setnodenumber(B,n,i);
1117
1118         if (p) {
1119             setnextnode(p, n);          /* insert node into free node list */
1120             setallnode(p, n);
1121         } else {
1122             setfirstfreenode(B, n);
1123             setfirstallnode(B, n);
1124         }
1125         p = n;
1126     }
1127     setnextnode(p, NONODE);             /* indicates end of free node list */
1128     setallnode(p, NONODE);              /* indicates end of all node list */
1129
1130     setpoolsize(B, quantity);
1131 }
1132
1133
1134 /*******************   Cleanup Free Node Pool **************************/
1135
1136 static void
1137 cleanupNodePool(Tree *B)
1138 {
1139     int i, j;
1140     Nptr node, next;
1141
1142     for ( i=0, node = getfirstallnode(B); node != NONODE && i<getpoolsize(B); node = next, i++ ) {
1143         if (isdata(node)) {
1144             if ( getdatakey(node).name ) {
1145                 free(getdatakey(node).name);
1146                 getdatakey(node).name = NULL;
1147             }
1148             if ( getdatavalue(node).longname ) {
1149                 free(getdatavalue(node).longname);
1150                 getdatavalue(node).longname = NULL;
1151             }
1152         } else { /* data node */
1153             for ( j=1; j<=getfanout(B); j++ ) {
1154                 if (getkey(node, j).name)
1155                     free(getkey(node, j).name);
1156             }
1157         }
1158         next = getallnode(node);
1159         free(node);
1160     }
1161 }
1162
1163 /**************   take a free B+tree node from the pool   **************/
1164 static Nptr
1165 getFreeNode(Tree *B)
1166 {
1167     Nptr newNode = getfirstfreenode(B);
1168
1169     if (newNode != NONODE) {
1170         setfirstfreenode(B, getnextnode(newNode));      /* adjust free node list */
1171         setnextnode(newNode, NONODE);                   /* remove node from list */
1172     }
1173     else {
1174         newNode = malloc(sizeof(*newNode));
1175         memset(newNode, 0, sizeof(*newNode));
1176
1177         setallnode(newNode, getfirstallnode(B));
1178         setfirstallnode(B, newNode);
1179         setnodenumber(B, newNode, getpoolsize(B));
1180         setpoolsize(B, getpoolsize(B) + 1);
1181     }
1182
1183     clearflags(newNode);                        /* Sets MAGIC */
1184     return newNode;
1185 }
1186
1187
1188 /*************   return a deleted B+tree node to the pool   ************/
1189 static void
1190 putFreeNode(Tree *B, Nptr node)
1191 {
1192     int i;
1193
1194     if (isntnode(node))
1195         return;
1196
1197     if (isdata(node)) {
1198         if ( getdatakey(node).name )
1199             free(getdatakey(node).name);
1200     } else {    /* data node */
1201         for ( i=1; i<=getfanout(B); i++ ) {
1202             if (getkey(node, i).name)
1203                 free(getkey(node, i).name);
1204         }
1205     }
1206
1207     /* free nodes do not have MAGIC set */
1208     memset(&nAdr(node), 0, sizeof(nAdr(node)));
1209     setnextnode(node, getfirstfreenode(B));     /* add node to list */
1210     setfirstfreenode(B, node);                  /* set it to be list head */
1211 }
1212
1213
1214 /*******   fill a free data node with a key and associated data   ******/
1215 static Nptr
1216 getDataNode(Tree *B, keyT key, dataT data)
1217 {
1218     Nptr        newNode = getFreeNode(B);
1219
1220     setflag(newNode, isDATA);
1221     getdatakey(newNode).name = strdup(key.name);
1222     getdatavalue(newNode) = data;
1223     getdatanext(newNode) = NONODE;
1224
1225     return newNode;
1226 }
1227
1228
1229 #ifdef DEBUG_BTREE
1230 /***********************************************************************\
1231 |       B+tree Printing Utilities                                       |
1232 \***********************************************************************/
1233
1234 /***********************   B+tree node printer   ***********************/
1235 void showNode(Tree *B, const char * where, Nptr n)
1236 {
1237     int x;
1238
1239     sprintf(B->message, "-  --  --  --  --  --  --  --  --  --  --  --  -\n");
1240     OutputDebugString(B->message);
1241     sprintf(B->message, "| %-20s                        |\n", where);
1242     OutputDebugString(B->message);
1243     sprintf(B->message, "| node %6d                 ", getnodenumber(B, n));
1244     OutputDebugString(B->message);
1245     sprintf(B->message, "  magic    %4x  |\n", getmagic(n));
1246     OutputDebugString(B->message);
1247     sprintf(B->message, "-  --  --  --  --  --  --  --  --  --  --  --  -\n");
1248     OutputDebugString(B->message);
1249     sprintf(B->message, "| flags   %1d%1d%1d%1d ", isfew(n), isfull(n), isroot(n), isleaf(n));
1250     OutputDebugString(B->message);
1251     sprintf(B->message, "| keys = %5d ", numentries(n));
1252     OutputDebugString(B->message);
1253     sprintf(B->message, "| node = %6d  |\n", getnodenumber(B, getfirstnode(n)));
1254     OutputDebugString(B->message);
1255     for (x = 1; x <= numentries(n); x++) {
1256         sprintf(B->message, "| entry %6d ", x);
1257         OutputDebugString(B->message);
1258         sprintf(B->message, "| key = %6s ", getkey(n, x).name);
1259         OutputDebugString(B->message);
1260         sprintf(B->message, "| node = %6d  |\n", getnodenumber(B, getnode(n, x)));
1261         OutputDebugString(B->message);
1262     }
1263     sprintf(B->message, "-  --  --  --  --  --  --  --  --  --  --  --  -\n");
1264     OutputDebugString(B->message);
1265 }
1266
1267 /******************   B+tree class variable printer   ******************/
1268 void showBtree(Tree *B)
1269 {
1270     sprintf(B->message, "-  --  --  --  --  --  -\n");
1271     OutputDebugString(B->message);
1272     sprintf(B->message, "|  B+tree  %10p  |\n", (void *) B);
1273     OutputDebugString(B->message);
1274     sprintf(B->message, "-  --  --  --  --  --  -\n");
1275     OutputDebugString(B->message);
1276     sprintf(B->message, "|  root        %6d  |\n", getnodenumber(B, getroot(B)));
1277     OutputDebugString(B->message);
1278     sprintf(B->message, "|  leaf        %6d  |\n", getnodenumber(B, getleaf(B)));
1279     OutputDebugString(B->message);
1280     sprintf(B->message, "|  fanout         %3d  |\n", getfanout(B) + 1);
1281     OutputDebugString(B->message);
1282     sprintf(B->message, "|  minfanout      %3d  |\n", getminfanout(B, getroot(B)) + 1);
1283     OutputDebugString(B->message);
1284     sprintf(B->message, "|  height         %3d  |\n", gettreeheight(B));
1285     OutputDebugString(B->message);
1286     sprintf(B->message, "|  freenode    %6d  |\n", getnodenumber(B, getfirstfreenode(B)));
1287     OutputDebugString(B->message);
1288     sprintf(B->message, "|  theKey      %6s  |\n", getfunkey(B).name);
1289     OutputDebugString(B->message);
1290     sprintf(B->message, "|  theData     %d.%d.%d |\n", getfundata(B).volume,
1291              getfundata(B).vnode, getfundata(B).unique);
1292     OutputDebugString(B->message);
1293     sprintf(B->message, "-  --  --  --  --  --  -\n");
1294     OutputDebugString(B->message);
1295 }
1296
1297 void
1298 listBtreeNodes(Tree *B, const char * parent_desc, Nptr node)
1299 {
1300     int i;
1301     char thisnode[64];
1302     dataT data;
1303
1304     if (isntnode(node)) {
1305         sprintf(B->message, "%s - NoNode!!!\n");
1306         OutputDebugString(B->message);
1307         return;
1308     }
1309
1310     if (!isnode(node))
1311     {
1312         data = getdatavalue(node);
1313         sprintf(B->message, "%s - data node %d (%d.%d.%d)\n",
1314                  parent_desc, getnodenumber(B, node),
1315                  data.fid.volume, data.fid.vnode, data.fid.unique);
1316         OutputDebugString(B->message);
1317         return;
1318     } else
1319         showNode(B, parent_desc, node);
1320
1321     if ( isinternal(node) || isroot(node) ) {
1322         sprintf(thisnode, "parent %6d", getnodenumber(B , node));
1323
1324         OutputDebugString(B->message);
1325         for ( i= isinternal(node) ? 0 : 1; i <= numentries(node); i++ ) {
1326             listBtreeNodes(B, thisnode, i == 0 ? getfirstnode(node) : getnode(node, i));
1327         }
1328     }
1329 }
1330
1331 /***********************   B+tree data printer   ***********************/
1332 void
1333 listBtreeValues(Tree *B, Nptr n, int num)
1334 {
1335     int slot;
1336     keyT prev = {""};
1337     dataT data;
1338
1339     for (slot = 1; (n != NONODE) && num && numentries(n); num--) {
1340         if (comparekeys(B)(getkey(n, slot),prev, 0) < 0) {
1341             sprintf(B->message, "BOMB %8s\n", getkey(n, slot).name);
1342             OutputDebugString(B->message);
1343             DebugBreak();
1344         }
1345         prev = getkey(n, slot);
1346         data = getdatavalue(getnode(n, slot));
1347         sprintf(B->message, "%8s (%d.%d.%d)\n",
1348                 prev.name, data.fid.volume, data.fid.vnode, data.fid.unique);
1349         OutputDebugString(B->message);
1350         if (++slot > numentries(n))
1351             n = getnextnode(n), slot = 1;
1352     }
1353     sprintf(B->message, "\n\n");
1354     OutputDebugString(B->message);
1355 }
1356
1357 /********************   entire B+tree data printer   *******************/
1358 void
1359 listAllBtreeValues(Tree *B)
1360 {
1361     listBtreeValues(B, getleaf(B), BTERROR);
1362 }
1363 #endif /* DEBUG_BTREE */
1364
1365 void
1366 findAllBtreeValues(Tree *B)
1367 {
1368     int num = -1;
1369     Nptr n = getleaf(B), l;
1370     int slot;
1371     keyT prev = {""};
1372
1373     for (slot = 1; (n != NONODE) && num && numentries(n); num--) {
1374         if (comparekeys(B)(getkey(n, slot),prev, 0) < 0) {
1375             sprintf(B->message,"BOMB %8s\n", getkey(n, slot).name);
1376             OutputDebugString(B->message);
1377 #ifdef DEBUG_BTREE
1378             DebugBreak();
1379 #endif
1380         }
1381         prev = getkey(n, slot);
1382         l = bplus_Lookup(B, prev);
1383         if ( l != n ){
1384             if (l == NONODE)
1385                 sprintf(B->message,"BOMB %8s cannot be found\n", prev.name);
1386             else
1387                 sprintf(B->message,"BOMB lookup(%8s) finds wrong node\n", prev.name);
1388             OutputDebugString(B->message);
1389 #ifdef DEBUG_BTREE
1390             DebugBreak();
1391 #endif
1392         }
1393
1394         if (++slot > numentries(n))
1395             n = getnextnode(n), slot = 1;
1396     }
1397 }
1398
1399 /*
1400  * the return must be -1, 0, or 1.  stricmp() in MSVC 8.0
1401  * does not return only those values.
1402  */
1403 static int
1404 compareKeys(keyT key1, keyT key2, int flags)
1405 {
1406     int comp;
1407
1408     if (flags & EXACT_MATCH)
1409         comp = strcmp(key1.name, key2.name);
1410     else
1411         comp = stricmp(key1.name, key2.name);
1412     return (comp < 0 ? -1 : (comp > 0 ? 1 : 0));
1413 }
1414
1415 /* Look up a file name in directory.
1416
1417    On entry:
1418        op->scp->dirlock is read locked
1419
1420    On exit:
1421        op->scp->dirlock is read locked
1422 */
1423 int
1424 cm_BPlusDirLookup(cm_dirOp_t * op, char *entry, cm_fid_t * cfid)
1425 {
1426     int rc = EINVAL;
1427     keyT key = {entry};
1428     Nptr leafNode = NONODE;
1429     LARGE_INTEGER start, end;
1430
1431     if (op->scp->dirBplus == NULL ||
1432         op->dataVersion != op->scp->dirDataVersion) {
1433         rc = EINVAL;
1434         goto done;
1435     }
1436
1437     QueryPerformanceCounter(&start);
1438
1439     leafNode = bplus_Lookup(op->scp->dirBplus, key);
1440     if (leafNode != NONODE) {
1441         int         slot;
1442         Nptr        firstDataNode, dataNode, nextDataNode;
1443         int         exact = 0;
1444         int         count = 0;
1445
1446         /* Found a leaf that matches the key via a case-insensitive
1447          * match.  There may be one or more data nodes that match.
1448          * If we have an exact match, return that.
1449          * If we have an ambiguous match, return an error.
1450          * If we have only one inexact match, return that.
1451          */
1452         slot = findKey(op->scp->dirBplus, leafNode, 1, numentries(leafNode));
1453         firstDataNode = getnode(leafNode, slot);
1454
1455         for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1456             count++;
1457             if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1458                 exact = 1;
1459                 break;
1460             }
1461             nextDataNode = getdatanext(dataNode);
1462         }
1463
1464         if (exact) {
1465             *cfid = getdatavalue(dataNode).fid;
1466             rc = 0;
1467             bplus_lookup_hits++;
1468         } else if (count == 1) {
1469             *cfid = getdatavalue(firstDataNode).fid;
1470             rc = CM_ERROR_INEXACT_MATCH;
1471             bplus_lookup_hits_inexact++;
1472         } else {
1473             rc = CM_ERROR_AMBIGUOUS_FILENAME;
1474             bplus_lookup_ambiguous++;
1475         }
1476     } else {
1477             rc = ENOENT;
1478         bplus_lookup_misses++;
1479     }
1480
1481     QueryPerformanceCounter(&end);
1482
1483     bplus_lookup_time += (end.QuadPart - start.QuadPart);
1484
1485   done:
1486     return rc;
1487 }
1488
1489
1490 /*
1491    On entry:
1492        op->scp->dirlock is write locked
1493
1494    On exit:
1495        op->scp->dirlock is write locked
1496 */
1497 long cm_BPlusDirCreateEntry(cm_dirOp_t * op, char *entry, cm_fid_t * cfid)
1498 {
1499     long rc = 0;
1500     keyT key = {entry};
1501     dataT  data;
1502     LARGE_INTEGER start, end;
1503     char shortName[13];
1504
1505     if (op->scp->dirBplus == NULL ||
1506         op->dataVersion != op->scp->dirDataVersion) {
1507         rc = EINVAL;
1508         goto done;
1509     }
1510
1511     data.fid.cell = cfid->cell;
1512     data.fid.volume = cfid->volume;
1513     data.fid.vnode = cfid->vnode;
1514     data.fid.unique = cfid->unique;
1515     data.longname = NULL;
1516
1517     QueryPerformanceCounter(&start);
1518     bplus_create_entry++;
1519
1520     insert(op->scp->dirBplus, key, data);
1521     if (!cm_Is8Dot3(entry)) {
1522         cm_dirFid_t dfid;
1523         dfid.vnode = htonl(data.fid.vnode);
1524         dfid.unique = htonl(data.fid.unique);
1525
1526         cm_Gen8Dot3NameInt(entry, &dfid, shortName, NULL);
1527
1528         key.name = shortName;
1529         data.longname = strdup(entry);
1530         insert(op->scp->dirBplus, key, data);
1531     }
1532
1533     QueryPerformanceCounter(&end);
1534
1535     bplus_create_time += (end.QuadPart - start.QuadPart);
1536
1537   done:
1538
1539     return rc;
1540 }
1541
1542 /*
1543    On entry:
1544        op->scp->dirlock is write locked
1545
1546    On exit:
1547        op->scp->dirlock is write locked
1548 */
1549 int  cm_BPlusDirDeleteEntry(cm_dirOp_t * op, char *entry)
1550 {
1551     long rc = 0;
1552     keyT key = {entry};
1553     Nptr leafNode = NONODE;
1554     LARGE_INTEGER start, end;
1555
1556     if (op->scp->dirBplus == NULL ||
1557         op->dataVersion != op->scp->dirDataVersion) {
1558         rc = EINVAL;
1559         goto done;
1560     }
1561
1562     QueryPerformanceCounter(&start);
1563
1564     bplus_remove_entry++;
1565
1566     if (op->scp->dirBplus) {
1567         if (!cm_Is8Dot3(entry)) {
1568             cm_dirFid_t dfid;
1569             cm_fid_t fid;
1570             char shortName[13];
1571
1572             leafNode = bplus_Lookup(op->scp->dirBplus, key);
1573             if (leafNode != NONODE) {
1574                 int         slot;
1575                 Nptr        firstDataNode, dataNode, nextDataNode;
1576                 int         exact = 0;
1577                 int         count = 0;
1578
1579                 /* Found a leaf that matches the key via a case-insensitive
1580                  * match.  There may be one or more data nodes that match.
1581                  * If we have an exact match, return that.
1582                  * If we have an ambiguous match, return an error.
1583                  * If we have only one inexact match, return that.
1584                  */
1585                 slot = findKey(op->scp->dirBplus, leafNode, 1, numentries(leafNode));
1586                 firstDataNode = getnode(leafNode, slot);
1587
1588                 for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1589                     count++;
1590                     if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1591                         exact = 1;
1592                         break;
1593                     }
1594                     nextDataNode = getdatanext(dataNode);
1595                 }
1596
1597                 if (exact) {
1598                     fid = getdatavalue(dataNode).fid;
1599                     rc = 0;
1600                 } else if (count == 1) {
1601                     fid = getdatavalue(firstDataNode).fid;
1602                     rc = CM_ERROR_INEXACT_MATCH;
1603                 } else {
1604                     rc = CM_ERROR_AMBIGUOUS_FILENAME;
1605                 }
1606             }
1607
1608
1609             if (rc != CM_ERROR_AMBIGUOUS_FILENAME) {
1610                 dfid.vnode = htonl(fid.vnode);
1611                 dfid.unique = htonl(fid.unique);
1612                 cm_Gen8Dot3NameInt(entry, &dfid, shortName, NULL);
1613
1614                 /* delete first the long name and then the short name */
1615                 delete(op->scp->dirBplus, key);
1616                 key.name = shortName;
1617                 delete(op->scp->dirBplus, key);
1618             }
1619         } else {
1620             char * longname = NULL;
1621             /* We need to lookup the 8dot3 name to determine what the
1622              * matching long name is
1623              */
1624             leafNode = bplus_Lookup(op->scp->dirBplus, key);
1625             if (leafNode != NONODE) {
1626                 int         slot;
1627                 Nptr        firstDataNode, dataNode, nextDataNode;
1628                 int         exact = 0;
1629                 int         count = 0;
1630
1631                 /* Found a leaf that matches the key via a case-insensitive
1632                  * match.  There may be one or more data nodes that match.
1633                  * If we have an exact match, return that.
1634                  * If we have an ambiguous match, return an error.
1635                  * If we have only one inexact match, return that.
1636                  */
1637                 slot = findKey(op->scp->dirBplus, leafNode, 1, numentries(leafNode));
1638                 firstDataNode = getnode(leafNode, slot);
1639
1640                 for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1641                     count++;
1642                     if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1643                         exact = 1;
1644                         break;
1645                     }
1646                     nextDataNode = getdatanext(dataNode);
1647                 }
1648
1649                 if (exact) {
1650                     longname = getdatavalue(dataNode).longname;
1651                     rc = 0;
1652                 } else if (count == 1) {
1653                     longname = getdatavalue(firstDataNode).longname;
1654                     rc = CM_ERROR_INEXACT_MATCH;
1655                 } else {
1656                     rc = CM_ERROR_AMBIGUOUS_FILENAME;
1657                 }
1658             }
1659
1660             if (rc != CM_ERROR_AMBIGUOUS_FILENAME) {
1661                                 if (longname) {
1662                                         key.name = longname;
1663                                         delete(op->scp->dirBplus, key);
1664                         key.name = entry;
1665                                 }
1666                 delete(op->scp->dirBplus, key);
1667             }
1668         }
1669     }
1670
1671     QueryPerformanceCounter(&end);
1672
1673     bplus_remove_time += (end.QuadPart - start.QuadPart);
1674
1675   done:
1676     return rc;
1677
1678 }
1679
1680 static
1681 int cm_BPlusDirFoo(struct cm_scache *scp, struct cm_dirEntry *dep,
1682                    void *dummy, osi_hyper_t *entryOffsetp)
1683 {
1684     keyT   key = {dep->name};
1685     dataT  data;
1686     char   shortName[13];
1687
1688     data.fid.cell = scp->fid.cell;
1689     data.fid.volume = scp->fid.volume;
1690     data.fid.vnode = ntohl(dep->fid.vnode);
1691     data.fid.unique = ntohl(dep->fid.unique);
1692     data.longname = NULL;
1693
1694     /* the Write lock is held in cm_BPlusDirBuildTree() */
1695     insert(scp->dirBplus, key, data);
1696     if (!cm_Is8Dot3(dep->name)) {
1697         cm_dirFid_t dfid;
1698         dfid.vnode = dep->fid.vnode;
1699         dfid.unique = dep->fid.unique;
1700
1701         cm_Gen8Dot3NameInt(dep->name, &dfid, shortName, NULL);
1702
1703         key.name = shortName;
1704         data.longname = strdup(dep->name);
1705         insert(scp->dirBplus, key, data);
1706     }
1707
1708 #ifdef BTREE_DEBUG
1709     findAllBtreeValues(scp->dirBplus);
1710 #endif
1711     return 0;
1712 }
1713
1714
1715 /*
1716  *   scp->dirlock must be writeLocked before call
1717  *
1718  *   scp->mutex must not be held
1719  */
1720 long cm_BPlusDirBuildTree(cm_scache_t *scp, cm_user_t *userp, cm_req_t* reqp)
1721 {
1722     long rc = 0;
1723     osi_hyper_t thyper;
1724     LARGE_INTEGER start, end;
1725
1726     osi_assert(scp->dirBplus == NULL);
1727
1728     QueryPerformanceCounter(&start);
1729     bplus_build_tree++;
1730
1731     if (scp->dirBplus == NULL) {
1732         scp->dirBplus = initBtree(64, MAX_FANOUT, compareKeys);
1733     }
1734     if (scp->dirBplus == NULL) {
1735         rc = ENOMEM;
1736     } else {
1737         thyper.LowPart = 0;
1738         thyper.HighPart = 0;
1739         rc = cm_ApplyDir(scp, cm_BPlusDirFoo, NULL, &thyper, userp, reqp, NULL);
1740     }
1741
1742     QueryPerformanceCounter(&end);
1743
1744     bplus_build_time += (end.QuadPart - start.QuadPart);
1745
1746     return rc;
1747 }
1748
1749 int cm_MemDumpBPlusStats(FILE *outputFile, char *cookie, int lock)
1750 {
1751     int zilch;
1752     char output[128];
1753
1754     sprintf(output, "%s - B+ Lookup    Hits: %-8d\r\n", cookie, bplus_lookup_hits);
1755     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1756     sprintf(output, "%s -      Inexact Hits: %-8d\r\n", cookie, bplus_lookup_hits_inexact);
1757     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1758     sprintf(output, "%s -    Ambiguous Hits: %-8d\r\n", cookie, bplus_lookup_ambiguous);
1759     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1760     sprintf(output, "%s -            Misses: %-8d\r\n", cookie, bplus_lookup_misses);
1761     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1762     sprintf(output, "%s -            Create: %-8d\r\n", cookie, bplus_create_entry);
1763     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1764     sprintf(output, "%s -            Remove: %-8d\r\n", cookie, bplus_remove_entry);
1765     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1766     sprintf(output, "%s -        Build Tree: %-8d\r\n", cookie, bplus_build_tree);
1767     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1768     sprintf(output, "%s -         Free Tree: %-8d\r\n", cookie, bplus_free_tree);
1769     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1770     sprintf(output, "%s -          DV Error: %-8d\r\n", cookie, bplus_dv_error);
1771     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1772
1773     sprintf(output, "%s - B+ Time    Lookup: %-16I64d\r\n", cookie, bplus_lookup_time);
1774     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1775     sprintf(output, "%s -            Create: %-16I64d\r\n", cookie, bplus_create_time);
1776     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1777     sprintf(output, "%s -            Remove: %-16I64d\r\n", cookie, bplus_remove_time);
1778     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1779     sprintf(output, "%s -             Build: %-16I64d\r\n", cookie, bplus_build_time);
1780     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1781     sprintf(output, "%s -              Free: %-16I64d\r\n", cookie, bplus_free_time);
1782     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1783
1784     return(0);
1785 }
1786
1787 void cm_BPlusDumpStats(void)
1788 {
1789     afsi_log("B+ Lookup    Hits: %-8d", bplus_lookup_hits);
1790     afsi_log("     Inexact Hits: %-8d", bplus_lookup_hits_inexact);
1791     afsi_log("   Ambiguous Hits: %-8d", bplus_lookup_ambiguous);
1792     afsi_log("           Misses: %-8d", bplus_lookup_misses);
1793     afsi_log("           Create: %-8d", bplus_create_entry);
1794     afsi_log("           Remove: %-8d", bplus_remove_entry);
1795     afsi_log("       Build Tree: %-8d", bplus_build_tree);
1796     afsi_log("        Free Tree: %-8d", bplus_free_tree);
1797     afsi_log("         DV Error: %-8d", bplus_dv_error);
1798
1799     afsi_log("B+ Time    Lookup: %-16I64d", bplus_lookup_time);
1800     afsi_log("           Create: %-16I64d", bplus_create_time);
1801     afsi_log("           Remove: %-16I64d", bplus_remove_time);
1802     afsi_log("            Build: %-16I64d", bplus_build_time);
1803     afsi_log("             Free: %-16I64d", bplus_free_time);
1804 }
1805 #endif /* USE_BPLUS */