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 leaf node in which data nodes can be found                 |
 173 \***********************************************************************/
 174
 175 /**********************   top level lookup   **********************/
 176 Nptr bplus_Lookup(Tree *B, keyT key)
 177 {
 178     Nptr        leafNode;
 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     leafNode = descendToLeaf(B, getroot(B));    /* start search from root node */
 187
 188 #ifdef DEBUG_BTREE
 189     if (leafNode) {
 190         int         slot;
 191         Nptr        dataNode;
 192         dataT       data;
 193
 194         slot = getSlot(B, leafNode);
 195         if (slot <= BTERROR)
 196             return NONODE;
 197
 198         dataNode = getnode(leafNode, slot);
 199         data = getdatavalue(dataNode);
 200
 201         sprintf(B->message, "LOOKUP: %s found on page %d value (%d.%d.%d).\n",
 202                  key.name,
 203                  getnodenumber(B, leafNode),
 204                  data.fid.volume,
 205                  data.fid.vnode,
 206                  data.fid.unique);
 207     } else
 208         sprintf(B->message, "LOOKUP: not found!\n");
 209     OutputDebugString(B->message);
 210 #endif
 211
 212     return leafNode;
 213 }
 214
 215 /**********************   `recurse' down B+tree   **********************/
 216 static Nptr descendToLeaf(Tree *B, Nptr curr)
 217 {
 218     int slot;
 219     Nptr        findNode;
 220     Nptr    prev[64];
 221     int depth;
 222
 223     memset(prev, 0, sizeof(prev));
 224
 225     for (depth = 0, slot = getSlot(B, curr); (slot >= 0) && isinternal(curr); depth++, slot = getSlot(B, curr)) {
 226         prev[depth] = curr;
 227         if (slot == 0)
 228             curr = getfirstnode(curr);
 229         else if (slot > 0)
 230             curr = getnode(curr, slot);
 231         else /* BTERROR, BTLOWER, BTUPPER */ {
 232             curr = NONODE;
 233             break;
 234         }
 235 #ifdef DEBUG_BTREE
 236         if ( !isnode(curr) )
 237             DebugBreak();
 238 #endif
 239     }
 240     if ((slot > 0) && !comparekeys(B)(getfunkey(B), getkey(curr, slot), 0))
 241         findNode = curr;                        /* correct key value found */
 242     else
 243         findNode = NONODE;                      /* key value not in tree */
 244
 245     return findNode;
 246 }
 247
 248 /********************   find slot for search key   *********************/
 249 static int getSlot(Tree *B, Nptr curr)
 250 {
 251     int slot, entries;
 252
 253     entries = numentries(curr);         /* need this if root is ever empty */
 254     slot = !entries ? 0 : findKey(B, curr, 1, entries);
 255
 256     return slot;
 257 }
 258
 259
 260 /********************   recursive binary search   **********************/
 261 static int findKey(Tree *B, Nptr curr, int lo, int hi)
 262 {
 263     int mid, findslot = BTERROR;
 264
 265     if (hi == lo) {
 266         findslot = bestMatch(B, curr, lo);              /* recursion base case */
 267
 268 #ifdef DEBUG_BTREE
 269         if (findslot == BTERROR) {
 270             sprintf(B->message, "FINDKEY: (lo %d hi %d) Bad key ordering on node %d (0x%p)\n",
 271                     lo, hi, getnodenumber(B, curr), curr);
 272             osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
 273         }
 274 #endif
 275     } else {
 276         mid = (lo + hi) >> 1;
 277         switch (findslot = bestMatch(B, curr, mid)) {
 278         case BTLOWER:                           /* check lower half of range */
 279             findslot = findKey(B, curr, lo, mid - 1);           /* never in 2-3+trees */
 280             break;
 281         case BTUPPER:                           /* check upper half of range */
 282             findslot = findKey(B, curr, mid + 1, hi);
 283             break;
 284         case BTERROR:
 285             sprintf(B->message, "FINDKEY: (lo %d hi %d) Bad key ordering on node %d (0x%p)\n",
 286                     lo, hi, getnodenumber(B, curr), curr);
 287             osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
 288         }
 289     }
 290
 291     if (isleaf(curr) && findslot == 0)
 292     {
 293         sprintf(B->message, "FINDKEY: (lo %d hi %d) findslot %d is invalid for leaf nodes, bad key ordering on node %d (0x%p)\n",
 294                 lo, hi, findslot, getnodenumber(B, curr), curr);
 295         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
 296     }
 297     return findslot;
 298 }
 299
 300
 301 /************   comparison of key with a target key slot   *************/
 302 static int bestMatch(Tree *B, Nptr curr, int slot)
 303 {
 304     int diff, comp=2, findslot;
 305
 306     diff = comparekeys(B)(getfunkey(B), getkey(curr, slot), 0);
 307     if (diff == 0) {
 308         findslot = slot;
 309     } else if (diff < 0) {              /* also check previous slot */
 310         if (slot == 1) {
 311             if (isleaf(curr))
 312                  findslot = BTLOWER;    /* not found in the tree */
 313             else
 314                  findslot = 0;
 315         }
 316         else if ((comp = comparekeys(B)(getfunkey(B), getkey(curr, slot - 1), 0)) >= 0) {
 317             findslot = slot - 1;
 318         } else if (comp < diff) {
 319             findslot = BTERROR;         /* inconsistent ordering of keys */
 320 #ifdef DEBUG_BTREE
 321             DebugBreak();
 322 #endif
 323         } else {
 324             findslot = BTLOWER;         /* key must be below in node ordering */
 325         }
 326     } else {                    /* or check following slot */
 327         if (slot == numentries(curr)) {
 328             if (isleaf(curr) && numentries(curr) == getfanout(B))
 329                 findslot = BTUPPER;
 330             else
 331                 findslot = slot;
 332         } else if ((comp = comparekeys(B)(getfunkey(B), getkey(curr, slot + 1), 0)) < 0) {
 333             findslot = slot;
 334         } else if (comp == 0) {
 335             findslot = slot + 1;
 336         } else if (comp > diff) {
 337             findslot = BTERROR;         /* inconsistent ordering of keys */
 338 #ifdef DEBUG_BTREE
 339             DebugBreak();
 340 #endif
 341         } else {
 342             findslot = BTUPPER;         /* key must be above in node ordering */
 343         }
 344     }
 345
 346     if (findslot == BTERROR || isleaf(curr) && findslot == 0)
 347     {
 348         sprintf(B->message, "BESTMATCH: node %d (0x%p) slot %d diff %d comp %d findslot %d\n",
 349                 getnodenumber(B, curr), curr, slot, diff, comp, findslot);
 350         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
 351     }
 352     return findslot;
 353 }
 354
 355
 356 /***********************************************************************\
 357 |       Insert new data into tree                                       |
 358 \***********************************************************************/
 359
 360
 361 /**********************   top level insert call   **********************/
 362 void insert(Tree *B, keyT key, dataT data)
 363 {
 364     Nptr newNode;
 365
 366 #ifdef DEBUG_BTREE
 367     sprintf(B->message, "INSERT:  key %s.\n", key.name);
 368     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
 369 #endif
 370
 371     setfunkey(B, key);                          /* set insertion key */
 372     setfundata(B, data);                        /* a node containing data */
 373     setsplitpath(B, NONODE);
 374     newNode = descendSplit(B, getroot(B));      /* insertion point search from root */
 375     if (newNode != getsplitpath(B))             /* indicates the root node has split */
 376         makeNewRoot(B, getroot(B), newNode);
 377 }
 378
 379
 380 /*****************   recurse down and split back up   ******************/
 381 static Nptr
 382 descendSplit(Tree *B, Nptr curr)
 383 {
 384     Nptr        downNode = NONODE, sibling = NONODE;
 385     int slot;
 386
 387 #ifdef DEBUG_BTREE
 388     if (!isnode(curr))
 389         DebugBreak();
 390 #endif
 391     if (!isfull(curr))
 392         setsplitpath(B, NONODE);
 393     else if (getsplitpath(B) == NONODE)
 394         setsplitpath(B, curr);                  /* indicates where nodes must split */
 395
 396     slot = getSlot(B, curr);                    /* is null only if the root is empty */
 397     if (slot == BTERROR)
 398         return NONODE;
 399
 400     if (isleaf(curr)) {
 401         if (slot == BTLOWER)
 402             slot = 0;
 403         else if (slot == BTUPPER)
 404             slot = getfanout(B);
 405     }
 406
 407     if (isinternal(curr)) {     /* continue recursion to leaves */
 408         if (slot == 0)
 409             downNode = descendSplit(B, getfirstnode(curr));
 410         else
 411             downNode = descendSplit(B, getnode(curr, slot));
 412     } else if ((slot > 0) && !comparekeys(B)(getfunkey(B), getkey(curr, slot), 0)) {
 413         if (!(gettreeflags(B) & TREE_FLAG_UNIQUE_KEYS)) {
 414             downNode = getDataNode(B, getfunkey(B), getfundata(B));
 415             getdatanext(downNode) = getnode(curr,slot);
 416             setnode(curr, slot, downNode);
 417         }
 418         downNode = NONODE;
 419         setsplitpath(B, NONODE);
 420     }
 421     else
 422         downNode = getDataNode(B, getfunkey(B), getfundata(B)); /* an insertion takes place */
 423
 424     if (downNode != NONODE) {                   /* insert only where necessary */
 425         if (getsplitpath(B) != NONODE)
 426             sibling = split(B, curr);           /* a sibling node is prepared */
 427         insertEntry(B, curr, slot, sibling, downNode);
 428     }
 429
 430     return sibling;
 431 }
 432
 433 /***************   determine location of inserted key   ****************/
 434 static void
 435 insertEntry(Tree *B, Nptr currNode, int slot, Nptr sibling, Nptr downPtr)
 436 {
 437     int split, i, j, k, x, y;
 438     keyT key;
 439
 440 #ifdef DEBUG_BTREE
 441     sprintf(B->message, "INSERT:  slot %d, down node %d.\n", slot, getnodenumber(B, downPtr));
 442     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
 443 #endif
 444
 445     if (sibling == NONODE) {            /* no split occurred */
 446         placeEntry(B, currNode, slot + 1, downPtr);
 447     }
 448     else {                              /* split entries between the two */
 449         if isinternal(currNode) {
 450             i = 1;
 451             split = getfanout(B) - getminfanout(B, currNode);
 452         } else if (isroot(currNode)) {
 453             /* split the root node and turn it into just a leaf */
 454             i = 0;
 455             split = getminfanout(B, currNode);
 456         } else  {
 457             i = 0;
 458             split = getminfanout(B, currNode);
 459         }
 460         j = (slot != split ? 1 : 0);
 461         k = (slot >= split ? 1 : 0);
 462
 463         /*
 464          * Move entries from the top half of the current node to
 465          * to the sibling node.
 466          * The number of entries to move is dependent upon where
 467          * the new entry is going to be added in relationship to
 468          * the split slot. (slots are 1-based).  If order to produce
 469          * a balanced tree, if the insertion slot is greater than
 470          * the split we move one less entry as the new entry will
 471          * be inserted into the sibling.
 472          *
 473          * If the node that is being split is an internal node (i != 0)
 474          * then we move one less entry due to the extra down pointer
 475          * when the split slot is not equal to the insertion slot
 476          */
 477         for (x = split + k + j * i, y = 1; x <= getfanout(B); x++, y++) {
 478             xferentry(currNode, x, sibling, y); /* copy entries to sibling */
 479             clrentry(currNode, x);
 480             decentries(currNode);
 481             incentries(sibling);
 482
 483 #ifdef DEBUG_BTREE
 484             if (getkey(sibling, numentries(sibling)).name == NULL)
 485                 DebugBreak();
 486 #endif
 487         }
 488         clrflag(currNode, isFULL);
 489         if (numentries(currNode) == getminfanout(B, currNode))
 490             setflag(currNode, FEWEST);          /* never happens in even size nodes */
 491
 492 #ifdef DEBUG_BTREE
 493         if (numentries(sibling) > getfanout(B))
 494             DebugBreak();
 495 #endif
 496         if (numentries(sibling) == getfanout(B))
 497             setflag(sibling, isFULL);           /* only ever happens in 2-3+trees */
 498
 499         if (numentries(sibling) > getminfanout(B, sibling))
 500             clrflag(sibling, FEWEST);
 501
 502         if (i) {                                /* set first pointer of internal node */
 503             if (j) {
 504                 setfirstnode(sibling, getnode(currNode, split + k));
 505                 decentries(currNode);
 506                 if (numentries(currNode) == getminfanout(B, currNode))
 507                     setflag(currNode, FEWEST);
 508                 else
 509                     clrflag(currNode, FEWEST);
 510             }
 511             else
 512                 setfirstnode(sibling, downPtr);
 513         }
 514
 515         if (j) {                                /* insert new entry into correct spot */
 516             if (k)
 517                 placeEntry(B, sibling, slot - split + 1 - i, downPtr);
 518             else
 519                 placeEntry(B, currNode, slot + 1, downPtr);
 520
 521             /* set key separating nodes */
 522             if (isleaf(sibling))
 523                 key = getkey(sibling, 1);
 524             else {
 525                 Nptr leaf = getfirstnode(sibling);
 526                 while ( isinternal(leaf) )
 527                     leaf = getfirstnode(leaf);
 528                 key = getkey(leaf, 1);
 529             }
 530             setfunkey(B, key);
 531         }
 532         else if (!i)
 533             placeEntry(B, sibling, 1, downPtr);
 534     }
 535 }
 536
 537 /************   place key into appropriate node & slot   ***************/
 538 static void
 539 placeEntry(Tree *B, Nptr node, int slot, Nptr downPtr)
 540 {
 541     int x;
 542
 543 #ifdef DEBUG_BTREE
 544     if (isfull(node))
 545         DebugBreak();
 546 #endif
 547
 548 #ifdef DEBUG_BTREE
 549     if (numentries(node) != 0 && getkey(node, numentries(node)).name == NULL)
 550         DebugBreak();
 551 #endif
 552     for (x = numentries(node); x >= slot && x != 0; x--)        /* make room for new entry */
 553         pushentry(node, x, 1);
 554     setentry(node, slot, getfunkey(B), downPtr);/* place it in correct slot */
 555
 556     incentries(node);                           /* adjust entry counter */
 557 #ifdef DEBUG_BTREE
 558         if (getkey(node, numentries(node)).name == NULL)
 559                 DebugBreak();
 560 #endif
 561
 562     if (numentries(node) == getfanout(B))
 563         setflag(node, isFULL);
 564     if (numentries(node) > getminfanout(B, node))
 565         clrflag(node, FEWEST);
 566     else
 567         setflag(node, FEWEST);
 568 }
 569
 570
 571 /*****************   split full node and set flags   *******************/
 572 static Nptr
 573 split(Tree *B, Nptr node)
 574 {
 575     Nptr sibling;
 576
 577     sibling = getFreeNode(B);
 578
 579     setflag(sibling, FEWEST);                   /* set up node flags */
 580
 581     if (isleaf(node)) {
 582         setflag(sibling, isLEAF);
 583         setnextnode(sibling, getnextnode(node));/* adjust leaf pointers */
 584         setnextnode(node, sibling);
 585     }
 586     if (getsplitpath(B) == node)
 587         setsplitpath(B, NONODE);                /* no more splitting needed */
 588
 589     if (isroot(node))
 590         clrflag(node, isROOT);
 591
 592     return sibling;
 593 }
 594
 595
 596 /**********************   build new root node   ************************/
 597 static void
 598 makeNewRoot(Tree *B, Nptr oldRoot, Nptr newNode)
 599 {
 600     setroot(B, getFreeNode(B));
 601
 602     setfirstnode(getroot(B), oldRoot);  /* old root becomes new root's child */
 603     setentry(getroot(B), 1, getfunkey(B), newNode);     /* old root's sibling also */
 604     incentries(getroot(B));
 605 #ifdef DEBUG_BTREE
 606     if (numentries(getroot(B)) > getfanout(B))
 607         DebugBreak();
 608 #endif
 609
 610     /* the oldRoot's isROOT flag was cleared in split() */
 611     setflag(getroot(B), isROOT);
 612     setflag(getroot(B), FEWEST);
 613     clrflag(getroot(B), isLEAF);
 614     inctreeheight(B);
 615 }
 616
 617
 618 /***********************************************************************\
 619 |       Delete data from tree                                           |
 620 \***********************************************************************/
 621
 622 /**********************   top level delete call   **********************\
 623 |
 624 |       The recursive call for deletion carries 5 additional parameters
 625 |       which may be needed to rebalance the B+tree when removing the key.
 626 |       These parameters are:
 627 |               1. immediate left neighbor of the current node
 628 |               2. immediate right neighbor of the current node
 629 |               3. the anchor of the current node and left neighbor
 630 |               4. the anchor of the current node and right neighbor
 631 |               5. the parent of the current node
 632 |
 633 |       All of these parameters are simple to calculate going along the
 634 |       recursive path to the leaf nodes and the point of key deletion.
 635 |       At that time, the algorithm determines which node manipulations
 636 |       are most efficient, that is, cause the least rearranging of data,
 637 |       and minimize the need for non-local key manipulation.
 638 |
 639 \***********************************************************************/
 640 void delete(Tree *B, keyT key)
 641 {
 642     Nptr newNode;
 643
 644 #ifdef DEBUG_BTREE
 645     sprintf(B->message, "DELETE:  key %s.\n", key.name);
 646     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
 647 #endif
 648
 649     setfunkey(B, key);                  /* set deletion key */
 650     setmergepath(B, NONODE);
 651     newNode = descendBalance(B, getroot(B), NONODE, NONODE, NONODE, NONODE, NONODE);
 652     if (isnode(newNode)) {
 653 #ifdef DEBUG_BTREE
 654         sprintf(B->message, "DELETE: collapsing node %d", getnodenumber(B, newNode));
 655         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
 656 #endif
 657         collapseRoot(B, getroot(B), newNode);   /* remove root when superfluous */
 658     }
 659 }
 660
 661
 662 /**********************   remove old root node   ***********************/
 663 static void
 664 collapseRoot(Tree *B, Nptr oldRoot, Nptr newRoot)
 665 {
 666
 667 #ifdef DEBUG_BTREE
 668     sprintf(B->message, "COLLAPSE:  old %d, new %d.\n", getnodenumber(B, oldRoot), getnodenumber(B, newRoot));
 669     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
 670     showNode(B, "collapseRoot oldRoot", oldRoot);
 671     showNode(B, "collapseRoot newRoot", newRoot);
 672 #endif
 673
 674     setroot(B, newRoot);
 675     setflag(newRoot, isROOT);
 676     clrflag(newRoot, FEWEST);
 677     putFreeNode(B, oldRoot);
 678     dectreeheight(B);                   /* the height of the tree decreases */
 679 }
 680
 681
 682 /****************   recurse down and balance back up   *****************/
 683 static Nptr
 684 descendBalance(Tree *B, Nptr curr, Nptr left, Nptr right, Nptr lAnc, Nptr rAnc, Nptr parent)
 685 {
 686     Nptr        newMe=NONODE, myLeft=NONODE, myRight=NONODE, lAnchor=NONODE, rAnchor=NONODE, newNode=NONODE;
 687     int slot = 0, notleft = 0, notright = 0, fewleft = 0, fewright = 0, test = 0;
 688
 689 #ifdef DEBUG_BTREE
 690     sprintf(B->message, "descendBalance curr %d, left %d, right %d, lAnc %d, rAnc %d, parent %d\n",
 691              curr ? getnodenumber(B, curr) : -1,
 692              left ? getnodenumber(B, left) : -1,
 693              right ? getnodenumber(B, right) : -1,
 694              lAnc ? getnodenumber(B, lAnc) : -1,
 695              rAnc ? getnodenumber(B, rAnc) : -1,
 696              parent ? getnodenumber(B, parent) : -1);
 697     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
 698 #endif
 699
 700     if (!isfew(curr))
 701         setmergepath(B,NONODE);
 702     else if (getmergepath(B) == NONODE)
 703         setmergepath(B, curr);          /* mark which nodes may need rebalancing */
 704
 705     slot = getSlot(B, curr);
 706     if (slot == BTERROR)
 707         return NONODE;
 708
 709     if (isleaf(curr)) {
 710         if (slot == BTLOWER)
 711             slot = 0;
 712         else if (slot == BTUPPER)
 713             slot = getfanout(B);
 714     }
 715
 716     if (isinternal(curr))       /* set up next recursion call's parameters */
 717     {
 718         if (slot == 0) {
 719             newNode = getfirstnode(curr);
 720             myLeft = !isnode(left) ? NONODE : getlastnode(left);
 721             lAnchor = lAnc;
 722         }
 723         else {
 724             newNode = getnode(curr, slot);
 725             if (slot == 1)
 726                 myLeft = getfirstnode(curr);
 727             else
 728                 myLeft = getnode(curr, slot - 1);
 729             lAnchor = curr;
 730         }
 731
 732         if (slot == numentries(curr)) {
 733             myRight = !isnode(right) ? NONODE : getfirstnode(right);
 734             rAnchor = rAnc;
 735         }
 736         else {
 737             myRight = getnode(curr, slot + 1);
 738             rAnchor = curr;
 739         }
 740         newMe = descendBalance(B, newNode, myLeft, myRight, lAnchor, rAnchor, curr);
 741     }
 742     else if ((slot > 0) && !comparekeys(B)(getfunkey(B), getkey(curr, slot), 0))
 743     {
 744         Nptr        next;
 745         int         exact = 0;
 746         int         count = 0;
 747
 748         newNode = getnode(curr, slot);
 749         next = getdatanext(newNode);
 750
 751         /*
 752          * We only delete exact matches.
 753          */
 754         if (!comparekeys(B)(getfunkey(B), getdatakey(newNode), EXACT_MATCH)) {
 755             /* exact match, free the first entry */
 756             setnode(curr, slot, next);
 757
 758             if (next == NONODE) {
 759                 /* delete this key as there are no more data values */
 760                 newMe = newNode;
 761             } else {
 762                 /* otherwise, there are more and we leave the key in place */
 763                 setnode(curr, slot, next);
 764                 putFreeNode(B, newNode);
 765
 766                 /* but do not delete the key */
 767                 newMe = NONODE;
 768                 setmergepath(B, NONODE);
 769             }
 770         } else if (next == NONODE) {
 771             /*
 772              * we didn't find an exact match and there are no more
 773              * choices.  so we leave it alone and remove nothing.
 774              */
 775             newMe = NONODE;
 776             setmergepath(B, NONODE);
 777         } else {
 778             /* The first data node doesn't match but there are other
 779              * options.  So we must determine if any of the next nodes
 780              * are the one we are looking for.
 781              */
 782             Nptr prev = newNode;
 783
 784             while ( next ) {
 785                 if (!comparekeys(B)(getfunkey(B), getdatakey(next), EXACT_MATCH)) {
 786                     /* we found the one to delete */
 787                     getdatanext(prev) = getdatanext(next);
 788                     putFreeNode(B, next);
 789                     break;
 790                 }
 791                 prev = next;
 792                 next = getdatanext(next);
 793             }
 794
 795             /* do not delete the key */
 796             newMe = NONODE;
 797             setmergepath(B, NONODE);
 798         }
 799     }
 800     else
 801     {
 802         newMe = NONODE;         /* no deletion possible, key not found */
 803         setmergepath(B, NONODE);
 804     }
 805
 806 /*****************   rebalancing tree after deletion   *****************\
 807 |
 808 |       The simplest B+tree rebalancing consists of the following rules.
 809 |
 810 |       If a node underflows:
 811 |       CASE 1 check if it is the root, and collapse it if it is,
 812 |       CASE 2 otherwise, check if both of its neighbors are minimum
 813 |           sized and merge the underflowing node with one of them,
 814 |       CASE 3 otherwise shift surplus entries to the underflowing node.
 815 |
 816 |       The choice of which neighbor to use is optional.  However, the
 817 |       rebalancing rules that follow also ensure whenever possible
 818 |       that the merges and shifts which do occur use a neighbor whose
 819 |       anchor is the parent of the underflowing node.
 820 |
 821 |       Cases 3, 4, 5 below are more an optimization than a requirement,
 822 |       and can be omitted, with a change of the action value in case 6,
 823 |       which actually corresponds to the third case described above.
 824 |
 825 \***********************************************************************/
 826
 827     /* begin deletion, working upwards from leaves */
 828
 829     if (newMe != NONODE) {      /* this node removal doesn't consider duplicates */
 830 #ifdef DEBUG_BTREE
 831         sprintf(B->message, "descendBalance DELETE:  slot %d, node %d.\n", slot, getnodenumber(B, curr));
 832         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
 833 #endif
 834
 835         removeEntry(B, curr, slot + (newMe != newNode));        /* removes one of two */
 836
 837 #ifdef DEBUG_BTREE
 838         showNode(B, "descendBalance curr", curr);
 839 #endif
 840     }
 841
 842     if (getmergepath(B) == NONODE)
 843         newNode = NONODE;
 844     else {              /* tree rebalancing rules for node merges and shifts */
 845         notleft = !isnode(left);
 846         notright = !isnode(right);
 847         if (!notleft)
 848             fewleft = isfew(left);              /* only used when defined */
 849         if (!notright)
 850             fewright = isfew(right);
 851
 852         /* CASE 1:  prepare root node (curr) for removal */
 853         if (notleft && notright) {
 854             test = isleaf(curr);                /* check if B+tree has become empty */
 855             newNode = test ? NONODE : getfirstnode(curr);
 856         }
 857         /* CASE 2:  the merging of two nodes is a must */
 858         else if ((notleft || fewleft) && (notright || fewright)) {
 859             test = (lAnc != parent);
 860             newNode = test ? merge(B, curr, right, rAnc) : merge(B, left, curr, lAnc);
 861         }
 862         /* CASE 3: choose the better of a merge or a shift */
 863         else if (!notleft && fewleft && !notright && !fewright) {
 864             test = (rAnc != parent) && (curr == getmergepath(B));
 865             newNode = test ? merge(B, left, curr, lAnc) : shift(B, curr, right, rAnc);
 866         }
 867         /* CASE 4: also choose between a merge or a shift */
 868         else if (!notleft && !fewleft && !notright && fewright) {
 869             test = !(lAnc == parent) && (curr == getmergepath(B));
 870             newNode = test ? merge(B, curr, right, rAnc) : shift(B, left, curr, lAnc);
 871         }
 872         /* CASE 5: choose the more effective of two shifts */
 873         else if (lAnc == rAnc) {                /* => both anchors are the parent */
 874             test = (numentries(left) <= numentries(right));
 875             newNode = test ? shift(B, curr, right, rAnc) : shift(B, left, curr, lAnc);
 876         }
 877         /* CASE 6: choose the shift with more local effect */
 878         else {                          /* if omitting cases 3,4,5 use below */
 879             test = (lAnc == parent);            /* test = (!notleft && !fewleft); */
 880             newNode = test ? shift(B, left, curr, lAnc) : shift(B, curr, right, rAnc);
 881         }
 882     }
 883
 884 #ifdef DEBUG_BTREE
 885     sprintf(B->message, "descendBalance returns %d\n", getnodenumber(B, newNode));
 886     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
 887 #endif
 888     return newNode;
 889 }
 890
 891
 892 /****************   remove key and pointer from node   *****************/
 893 static void
 894 removeEntry(Tree *B, Nptr curr, int slot)
 895 {
 896     int x;
 897
 898     putFreeNode(B, getnode(curr, slot));        /* return deleted node to free list */
 899     for (x = slot; x < numentries(curr); x++)
 900         pullentry(curr, x, 1);                  /* adjust node with removed key */
 901     decentries(curr);
 902     clrflag(curr, isFULL);                      /* keep flag information up to date */
 903     if (numentries(curr) > getminfanout(B, curr))
 904         clrflag(curr, FEWEST);
 905     else
 906         setflag(curr, FEWEST);
 907 }
 908
 909
 910 /*******   merge a node pair & set emptied node up for removal   *******/
 911 static Nptr
 912 merge(Tree *B, Nptr left, Nptr right, Nptr anchor)
 913 {
 914     int x, y, z;
 915
 916 #ifdef DEBUG_BTREE
 917     sprintf(B->message, "MERGE:  left %d, right %d.\n", getnodenumber(B, left), getnodenumber(B, right));
 918     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
 919     showNode(B, "pre-merge anchor", anchor);
 920     showNode(B, "pre-merge left", left);
 921     showNode(B, "pre-merge right", right);
 922 #endif
 923
 924     if (isinternal(left)) {
 925         incentries(left);                       /* copy key separating the nodes */
 926 #ifdef DEBUG_BTREE
 927         if (numentries(left) > getfanout(B))
 928             DebugBreak();
 929 #endif
 930         setfunkey(B, getkey(right, 1)); /* defined but maybe just deleted */
 931         z = getSlot(B, anchor);         /* needs the just calculated key */
 932         if (z <= BTERROR)
 933             return NONODE;
 934         setfunkey(B, getkey(anchor, z));        /* set slot to delete in anchor */
 935         setentry(left, numentries(left), getfunkey(B), getfirstnode(right));
 936     }
 937     else
 938         setnextnode(left, getnextnode(right));
 939
 940     for (x = numentries(left) + 1, y = 1; y <= numentries(right); x++, y++) {
 941         incentries(left);
 942 #ifdef DEBUG_BTREE
 943         if (numentries(left) > getfanout(B))
 944             DebugBreak();
 945 #endif
 946         xferentry(right, y, left, x);   /* transfer entries to left node */
 947     }
 948     clearentries(right);
 949
 950     if (numentries(left) > getminfanout(B, left))
 951         clrflag(left, FEWEST);
 952     if (numentries(left) == getfanout(B))
 953         setflag(left, isFULL);          /* never happens in even size nodes */
 954
 955     if (getmergepath(B) == left || getmergepath(B) == right)
 956         setmergepath(B, NONODE);                /* indicate rebalancing is complete */
 957
 958 #ifdef DEBUG_BTREE
 959     showNode(B, "post-merge anchor", anchor);
 960     showNode(B, "post-merge left", left);
 961     showNode(B, "post-merge right", right);
 962 #endif
 963     return right;
 964 }
 965
 966
 967 /******   shift entries in a node pair & adjust anchor key value   *****/
 968 static Nptr
 969 shift(Tree *B, Nptr left, Nptr right, Nptr anchor)
 970 {
 971     int i, x, y, z;
 972
 973 #ifdef DEBUG_BTREE
 974     sprintf(B->message, "SHIFT:  left %d, right %d, anchor %d.\n",
 975              getnodenumber(B, left),
 976              getnodenumber(B, right),
 977              getnodenumber(B, anchor));
 978     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
 979     showNode(B, "pre-shift anchor", anchor);
 980     showNode(B, "pre-shift left", left);
 981     showNode(B, "pre-shift right", right);
 982 #endif
 983
 984     i = isinternal(left);
 985
 986     if (numentries(left) < numentries(right)) { /* shift entries to left */
 987         y = (numentries(right) - numentries(left)) >> 1;
 988         x = numentries(left) + y;
 989         setfunkey(B, getkey(right, y + 1 - i)); /* set new anchor key value */
 990         z = getSlot(B, anchor);                 /* find slot in anchor node */
 991         if (z <= BTERROR)
 992             return NONODE;
 993 #ifdef DEBUG_BTREE
 994         if (z == 0 && !isroot(anchor))
 995             DebugBreak();
 996 #endif
 997         if (i) {                                        /* move out old anchor value */
 998             decentries(right);                  /* adjust for shifting anchor */
 999             incentries(left);
1000 #ifdef DEBUG_BTREE
1001             if (numentries(left) > getfanout(B))
1002                 DebugBreak();
1003 #endif
1004             setentry(left, numentries(left), getkey(anchor, z), getfirstnode(right));
1005             setfirstnode(right, getnode(right, y + 1 - i));
1006         }
1007         clrflag(right, isFULL);
1008         setkey(anchor, z, getfunkey(B));                /* set new anchor value */
1009         for (z = y, y -= i; y > 0; y--, x--) {
1010             decentries(right);                  /* adjust entry count */
1011             incentries(left);
1012 #ifdef DEBUG_BTREE
1013             if (numentries(left) > getfanout(B))
1014                 DebugBreak();
1015 #endif
1016             xferentry(right, y, left, x);               /* transfer entries over */
1017         }
1018
1019         for (x = 1; x <= numentries(right); x++)        /* adjust reduced node */
1020             pullentry(right, x, z);
1021     }
1022     else if (numentries(left) > numentries(right)) {                                    /* shift entries to right */
1023         y = (numentries(left) - numentries(right)) >> 1;
1024         x = numentries(left) - y + 1;
1025
1026         for (z = numentries(right); z > 0; z--) /* adjust increased node */
1027             pushentry(right, z, y);
1028
1029         setfunkey(B, getkey(left, x));                  /* set new anchor key value */
1030         z = getSlot(B, anchor);
1031         if (z <= BTERROR)
1032             return NONODE;
1033         z += 1;
1034
1035         if (i) {
1036             decentries(left);
1037             incentries(right);
1038 #ifdef DEBUG_BTREE
1039             if (numentries(right) > getfanout(B))
1040                 DebugBreak();
1041 #endif
1042             setentry(right, y, getkey(anchor, z), getfirstnode(right));
1043             setfirstnode(right, getnode(left, x));
1044         }
1045         clrflag(left, isFULL);
1046         setkey(anchor, z, getfunkey(B));
1047         for (x = numentries(left) + i, y -= i; y > 0; y--, x--) {
1048             decentries(left);
1049             incentries(right);
1050 #ifdef DEBUG_BTREE
1051             if (numentries(right) > getfanout(B))
1052                 DebugBreak();
1053 #endif
1054             xferentry(left, x, right, y);               /* transfer entries over */
1055             clrentry(left, x);
1056         }
1057     }
1058 #ifdef DEBUG_BTREE
1059     else {
1060         DebugBreak();
1061     }
1062 #endif /* DEBUG_BTREE */
1063
1064     if (numentries(left) > getminfanout(B, left))               /* adjust node flags */
1065         clrflag(left, FEWEST);                  /* never happens in 2-3+trees */
1066     else
1067         setflag(left, FEWEST);
1068     if (numentries(right) > getminfanout(B, right))
1069         clrflag(right, FEWEST);                 /* never happens in 2-3+trees */
1070     else
1071         setflag(right, FEWEST);
1072     setmergepath(B, NONODE);
1073
1074 #ifdef DEBUG_BTREE
1075     sprintf(B->message, "SHIFT:  left %d, right %d.\n", getnodenumber(B, left), getnodenumber(B, right));
1076     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1077     showNode(B, "post-shift anchor", anchor);
1078     showNode(B, "post-shift left", left);
1079     showNode(B, "post-shift right", right);
1080 #endif
1081
1082     return NONODE;
1083 }
1084
1085
1086 static void
1087 _clrentry(Nptr node, int entry)
1088 {
1089     if (getkey(node,entry).name != NULL) {
1090         free(getkey(node,entry).name);
1091         getkey(node,entry).name = NULL;
1092     }
1093     getnode(node,entry) = NONODE;
1094 }
1095
1096 static void
1097 _pushentry(Nptr node, int entry, int offset)
1098 {
1099     if (getkey(node,entry + offset).name != NULL)
1100         free(getkey(node,entry + offset).name);
1101 #ifdef DEBUG_BTREE
1102     if (entry == 0)
1103         DebugBreak();
1104 #endif
1105     getkey(node,entry + offset).name = strdup(getkey(node,entry).name);
1106 #ifdef DEBUG_BTREE
1107     if ( getnode(node, entry) == NONODE )
1108         DebugBreak();
1109 #endif
1110     getnode(node,entry + offset) = getnode(node,entry);
1111 }
1112
1113 static void
1114 _pullentry(Nptr node, int entry, int offset)
1115 {
1116     if (getkey(node,entry).name != NULL)
1117         free(getkey(node,entry).name);
1118     getkey(node,entry).name = strdup(getkey(node,entry + offset).name);
1119 #ifdef DEBUG_BTREE
1120     if ( getnode(node, entry + offset) == NONODE )
1121         DebugBreak();
1122 #endif
1123     getnode(node,entry) = getnode(node,entry + offset);
1124 }
1125
1126 static void
1127 _xferentry(Nptr srcNode, int srcEntry, Nptr destNode, int destEntry)
1128 {
1129     if (getkey(destNode,destEntry).name != NULL)
1130         free(getkey(destNode,destEntry).name);
1131     getkey(destNode,destEntry).name = strdup(getkey(srcNode,srcEntry).name);
1132 #ifdef DEBUG_BTREE
1133     if ( getnode(srcNode, srcEntry) == NONODE )
1134         DebugBreak();
1135 #endif
1136     getnode(destNode,destEntry) = getnode(srcNode,srcEntry);
1137 }
1138
1139 static void
1140 _setentry(Nptr node, int entry, keyT key, Nptr downNode)
1141 {
1142     if (getkey(node,entry).name != NULL)
1143         free(getkey(node,entry).name);
1144     getkey(node,entry).name = strdup(key.name);
1145 #ifdef DEBUG_BTREE
1146     if ( downNode == NONODE )
1147         DebugBreak();
1148 #endif
1149     getnode(node,entry) = downNode;
1150 }
1151
1152
1153 /***********************************************************************\
1154 |       Empty Node Utilities                                            |
1155 \***********************************************************************/
1156
1157 /*********************   Set up initial pool of free nodes   ***********/
1158 static void
1159 initFreeNodePool(Tree *B, int quantity)
1160 {
1161     int i;
1162     Nptr        n, p;
1163
1164     setfirstallnode(B, NONODE);
1165     setfirstfreenode(B, NONODE);
1166
1167     for (i = 0, p = NONODE; i < quantity; i++) {
1168         n = malloc(sizeof(*n));
1169         memset(n, 0, sizeof(*n));
1170         setnodenumber(B,n,i);
1171
1172         if (p) {
1173             setnextnode(p, n);          /* insert node into free node list */
1174             setallnode(p, n);
1175         } else {
1176             setfirstfreenode(B, n);
1177             setfirstallnode(B, n);
1178         }
1179         p = n;
1180     }
1181     setnextnode(p, NONODE);             /* indicates end of free node list */
1182     setallnode(p, NONODE);              /* indicates end of all node list */
1183
1184     setpoolsize(B, quantity);
1185 }
1186
1187
1188 /*******************   Cleanup Free Node Pool **************************/
1189
1190 static void
1191 cleanupNodePool(Tree *B)
1192 {
1193     int i, j;
1194     Nptr node, next;
1195
1196     for ( i=0, node = getfirstallnode(B); node != NONODE && i<getpoolsize(B); node = next, i++ ) {
1197         if (isdata(node)) {
1198             if ( getdatakey(node).name ) {
1199                 free(getdatakey(node).name);
1200                 getdatakey(node).name = NULL;
1201             }
1202             if ( getdatavalue(node).longname ) {
1203                 free(getdatavalue(node).longname);
1204                 getdatavalue(node).longname = NULL;
1205             }
1206         } else { /* data node */
1207             for ( j=1; j<=getfanout(B); j++ ) {
1208                 if (getkey(node, j).name)
1209                     free(getkey(node, j).name);
1210             }
1211         }
1212         next = getallnode(node);
1213         free(node);
1214     }
1215 }
1216
1217 /**************   take a free B+tree node from the pool   **************/
1218 static Nptr
1219 getFreeNode(Tree *B)
1220 {
1221     Nptr newNode = getfirstfreenode(B);
1222
1223     if (newNode != NONODE) {
1224         setfirstfreenode(B, getnextnode(newNode));      /* adjust free node list */
1225         setnextnode(newNode, NONODE);                   /* remove node from list */
1226     }
1227     else {
1228         newNode = malloc(sizeof(*newNode));
1229         memset(newNode, 0, sizeof(*newNode));
1230
1231         setallnode(newNode, getfirstallnode(B));
1232         setfirstallnode(B, newNode);
1233         setnodenumber(B, newNode, getpoolsize(B));
1234         setpoolsize(B, getpoolsize(B) + 1);
1235     }
1236
1237     clearflags(newNode);                        /* Sets MAGIC */
1238     return newNode;
1239 }
1240
1241
1242 /*************   return a deleted B+tree node to the pool   ************/
1243 static void
1244 putFreeNode(Tree *B, Nptr node)
1245 {
1246     int i;
1247
1248     if (isntnode(node))
1249         return;
1250
1251     if (isdata(node)) {
1252         if ( getdatakey(node).name )
1253             free(getdatakey(node).name);
1254     } else {    /* data node */
1255         for ( i=1; i<=getfanout(B); i++ ) {
1256             if (getkey(node, i).name)
1257                 free(getkey(node, i).name);
1258         }
1259     }
1260
1261     /* free nodes do not have MAGIC set */
1262     memset(&nAdr(node), 0, sizeof(nAdr(node)));
1263     setnextnode(node, getfirstfreenode(B));     /* add node to list */
1264     setfirstfreenode(B, node);                  /* set it to be list head */
1265 }
1266
1267
1268 /*******   fill a free data node with a key and associated data   ******/
1269 static Nptr
1270 getDataNode(Tree *B, keyT key, dataT data)
1271 {
1272     Nptr        newNode = getFreeNode(B);
1273
1274     setflag(newNode, isDATA);
1275     getdatakey(newNode).name = strdup(key.name);
1276     getdatavalue(newNode) = data;
1277     getdatanext(newNode) = NONODE;
1278
1279     return newNode;
1280 }
1281
1282
1283 #ifdef DEBUG_BTREE
1284 /***********************************************************************\
1285 |       B+tree Printing Utilities                                       |
1286 \***********************************************************************/
1287
1288 /***********************   B+tree node printer   ***********************/
1289 void showNode(Tree *B, const char * where, Nptr n)
1290 {
1291     int x;
1292
1293     sprintf(B->message, "-  --  --  --  --  --  --  --  --  --  --  --  -\n");
1294     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1295     sprintf(B->message, "| %-20s                        |\n", where);
1296     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1297     sprintf(B->message, "| node %6d                 ", getnodenumber(B, n));
1298     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1299     sprintf(B->message, "  magic    %4x  |\n", getmagic(n));
1300     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1301     sprintf(B->message, "-  --  --  --  --  --  --  --  --  --  --  --  -\n");
1302     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1303     sprintf(B->message, "| flags   %1d%1d%1d%1d ", isfew(n), isfull(n), isroot(n), isleaf(n));
1304     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1305     sprintf(B->message, "| keys = %5d ", numentries(n));
1306     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1307     sprintf(B->message, "| node = %6d  |\n", getnodenumber(B, getfirstnode(n)));
1308     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1309     for (x = 1; x <= numentries(n); x++) {
1310         sprintf(B->message, "| entry %6d ", x);
1311         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1312         sprintf(B->message, "| key = %6s ", getkey(n, x).name);
1313         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1314         sprintf(B->message, "| node = %6d  |\n", getnodenumber(B, getnode(n, x)));
1315         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1316     }
1317     sprintf(B->message, "-  --  --  --  --  --  --  --  --  --  --  --  -\n");
1318     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1319 }
1320
1321 /******************   B+tree class variable printer   ******************/
1322 void showBtree(Tree *B)
1323 {
1324     sprintf(B->message, "-  --  --  --  --  --  -\n");
1325     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1326     sprintf(B->message, "|  B+tree  %10p  |\n", (void *) B);
1327     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1328     sprintf(B->message, "-  --  --  --  --  --  -\n");
1329     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1330     sprintf(B->message, "|  root        %6d  |\n", getnodenumber(B, getroot(B)));
1331     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1332     sprintf(B->message, "|  leaf        %6d  |\n", getnodenumber(B, getleaf(B)));
1333     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1334     sprintf(B->message, "|  fanout         %3d  |\n", getfanout(B) + 1);
1335     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1336     sprintf(B->message, "|  minfanout      %3d  |\n", getminfanout(B, getroot(B)) + 1);
1337     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1338     sprintf(B->message, "|  height         %3d  |\n", gettreeheight(B));
1339     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1340     sprintf(B->message, "|  freenode    %6d  |\n", getnodenumber(B, getfirstfreenode(B)));
1341     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1342     sprintf(B->message, "|  theKey      %6s  |\n", getfunkey(B).name);
1343     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1344     sprintf(B->message, "|  theData     %d.%d.%d |\n", getfundata(B).volume,
1345              getfundata(B).vnode, getfundata(B).unique);
1346     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1347     sprintf(B->message, "-  --  --  --  --  --  -\n");
1348     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1349 }
1350
1351 void
1352 listBtreeNodes(Tree *B, const char * parent_desc, Nptr node)
1353 {
1354     int i;
1355     char thisnode[64];
1356     dataT data;
1357
1358     if (isntnode(node)) {
1359         sprintf(B->message, "%s - NoNode!!!\n");
1360         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1361         return;
1362     }
1363
1364     if (!isnode(node))
1365     {
1366         data = getdatavalue(node);
1367         sprintf(B->message, "%s - data node %d (%d.%d.%d)\n",
1368                  parent_desc, getnodenumber(B, node),
1369                  data.fid.volume, data.fid.vnode, data.fid.unique);
1370         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1371         return;
1372     } else
1373         showNode(B, parent_desc, node);
1374
1375     if ( isinternal(node) || isroot(node) ) {
1376         sprintf(thisnode, "parent %6d", getnodenumber(B , node));
1377
1378         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1379         for ( i= isinternal(node) ? 0 : 1; i <= numentries(node); i++ ) {
1380             listBtreeNodes(B, thisnode, i == 0 ? getfirstnode(node) : getnode(node, i));
1381         }
1382     }
1383 }
1384
1385 /***********************   B+tree data printer   ***********************/
1386 void
1387 listBtreeValues(Tree *B, Nptr n, int num)
1388 {
1389     int slot;
1390     keyT prev = {""};
1391     dataT data;
1392
1393     for (slot = 1; (n != NONODE) && num && numentries(n); num--) {
1394         if (comparekeys(B)(getkey(n, slot),prev, 0) < 0) {
1395             sprintf(B->message, "BOMB %8s\n", getkey(n, slot).name);
1396             osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1397             DebugBreak();
1398         }
1399         prev = getkey(n, slot);
1400         data = getdatavalue(getnode(n, slot));
1401         sprintf(B->message, "%8s (%d.%d.%d)\n",
1402                 prev.name, data.fid.volume, data.fid.vnode, data.fid.unique);
1403         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1404         if (++slot > numentries(n))
1405             n = getnextnode(n), slot = 1;
1406     }
1407     sprintf(B->message, "\n\n");
1408     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1409 }
1410
1411 /********************   entire B+tree data printer   *******************/
1412 void
1413 listAllBtreeValues(Tree *B)
1414 {
1415     listBtreeValues(B, getleaf(B), BTERROR);
1416 }
1417 #endif /* DEBUG_BTREE */
1418
1419 void
1420 findAllBtreeValues(Tree *B)
1421 {
1422     int num = -1;
1423     Nptr n = getleaf(B), l;
1424     int slot;
1425     keyT prev = {""};
1426
1427     for (slot = 1; (n != NONODE) && num && numentries(n); num--) {
1428         if (comparekeys(B)(getkey(n, slot),prev, 0) < 0) {
1429             sprintf(B->message,"BOMB %8s\n", getkey(n, slot).name);
1430             osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1431 #ifdef DEBUG_BTREE
1432             DebugBreak();
1433 #endif
1434         }
1435         prev = getkey(n, slot);
1436         l = bplus_Lookup(B, prev);
1437         if ( l != n ){
1438             if (l == NONODE)
1439                 sprintf(B->message,"BOMB %8s cannot be found\n", prev.name);
1440             else
1441                 sprintf(B->message,"BOMB lookup(%8s) finds wrong node\n", prev.name);
1442             osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1443 #ifdef DEBUG_BTREE
1444             DebugBreak();
1445 #endif
1446         }
1447
1448         if (++slot > numentries(n))
1449             n = getnextnode(n), slot = 1;
1450     }
1451 }
1452
1453 /*
1454  * the return must be -1, 0, or 1.  stricmp() in MSVC 8.0
1455  * does not return only those values.
1456  *
1457  * the sorting of the tree is by case insensitive sort order
1458  * therefore, unless the strings actually match via a case
1459  * insensitive search do we want to perform the case sensitive
1460  * match.  Otherwise, the search order might be considered
1461  * to be inconsistent when the EXACT_MATCH flag is set.
1462  */
1463 static int
1464 compareKeys(keyT key1, keyT key2, int flags)
1465 {
1466     int comp;
1467
1468     comp = stricmp(key1.name, key2.name);
1469     if (comp == 0 && (flags & EXACT_MATCH))
1470         comp = strcmp(key1.name, key2.name);
1471     return (comp < 0 ? -1 : (comp > 0 ? 1 : 0));
1472 }
1473
1474 /* Look up a file name in directory.
1475
1476    On entry:
1477        op->scp->dirlock is read locked
1478
1479    On exit:
1480        op->scp->dirlock is read locked
1481 */
1482 int
1483 cm_BPlusDirLookup(cm_dirOp_t * op, char *entry, cm_fid_t * cfid)
1484 {
1485     int rc = EINVAL;
1486     keyT key = {entry};
1487     Nptr leafNode = NONODE;
1488     LARGE_INTEGER start, end;
1489
1490     if (op->scp->dirBplus == NULL ||
1491         op->dataVersion != op->scp->dirDataVersion) {
1492         rc = EINVAL;
1493         goto done;
1494     }
1495
1496     lock_AssertAny(&op->scp->dirlock);
1497
1498     QueryPerformanceCounter(&start);
1499
1500     leafNode = bplus_Lookup(op->scp->dirBplus, key);
1501     if (leafNode != NONODE) {
1502         int         slot;
1503         Nptr        firstDataNode, dataNode, nextDataNode;
1504         int         exact = 0;
1505         int         count = 0;
1506
1507         /* Found a leaf that matches the key via a case-insensitive
1508          * match.  There may be one or more data nodes that match.
1509          * If we have an exact match, return that.
1510          * If we have an ambiguous match, return an error.
1511          * If we have only one inexact match, return that.
1512          */
1513         slot = getSlot(op->scp->dirBplus, leafNode);
1514         if (slot <= BTERROR) {
1515             op->scp->dirDataVersion = 0;
1516             rc = (slot == BTERROR ? EINVAL : ENOENT);
1517             goto done;
1518         }
1519         firstDataNode = getnode(leafNode, slot);
1520
1521         for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1522             count++;
1523             if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1524                 exact = 1;
1525                 break;
1526             }
1527             nextDataNode = getdatanext(dataNode);
1528         }
1529
1530         if (exact) {
1531             *cfid = getdatavalue(dataNode).fid;
1532             rc = 0;
1533             bplus_lookup_hits++;
1534         } else if (count == 1) {
1535             *cfid = getdatavalue(firstDataNode).fid;
1536             rc = CM_ERROR_INEXACT_MATCH;
1537             bplus_lookup_hits_inexact++;
1538         } else {
1539             rc = CM_ERROR_AMBIGUOUS_FILENAME;
1540             bplus_lookup_ambiguous++;
1541         }
1542     } else {
1543             rc = ENOENT;
1544         bplus_lookup_misses++;
1545     }
1546
1547     QueryPerformanceCounter(&end);
1548
1549     bplus_lookup_time += (end.QuadPart - start.QuadPart);
1550
1551   done:
1552     return rc;
1553 }
1554
1555
1556 /*
1557    On entry:
1558        op->scp->dirlock is write locked
1559
1560    On exit:
1561        op->scp->dirlock is write locked
1562 */
1563 long cm_BPlusDirCreateEntry(cm_dirOp_t * op, char *entry, cm_fid_t * cfid)
1564 {
1565     long rc = 0;
1566     keyT key = {entry};
1567     dataT  data;
1568     LARGE_INTEGER start, end;
1569     char shortName[13];
1570
1571     if (op->scp->dirBplus == NULL ||
1572         op->dataVersion != op->scp->dirDataVersion) {
1573         rc = EINVAL;
1574         goto done;
1575     }
1576
1577
1578     lock_AssertWrite(&op->scp->dirlock);
1579
1580     data.fid.cell = cfid->cell;
1581     data.fid.volume = cfid->volume;
1582     data.fid.vnode = cfid->vnode;
1583     data.fid.unique = cfid->unique;
1584     data.longname = NULL;
1585
1586     QueryPerformanceCounter(&start);
1587     bplus_create_entry++;
1588
1589     insert(op->scp->dirBplus, key, data);
1590     if (!cm_Is8Dot3(entry)) {
1591         cm_dirFid_t dfid;
1592         dfid.vnode = htonl(data.fid.vnode);
1593         dfid.unique = htonl(data.fid.unique);
1594
1595         cm_Gen8Dot3NameInt(entry, &dfid, shortName, NULL);
1596
1597         key.name = shortName;
1598         data.longname = strdup(entry);
1599         insert(op->scp->dirBplus, key, data);
1600     }
1601
1602     QueryPerformanceCounter(&end);
1603
1604     bplus_create_time += (end.QuadPart - start.QuadPart);
1605
1606   done:
1607
1608     return rc;
1609 }
1610
1611 /*
1612    On entry:
1613        op->scp->dirlock is write locked
1614
1615    On exit:
1616        op->scp->dirlock is write locked
1617 */
1618 int  cm_BPlusDirDeleteEntry(cm_dirOp_t * op, char *entry)
1619 {
1620     long rc = 0;
1621     keyT key = {entry};
1622     Nptr leafNode = NONODE;
1623     LARGE_INTEGER start, end;
1624
1625     if (op->scp->dirBplus == NULL ||
1626         op->dataVersion != op->scp->dirDataVersion) {
1627         rc = EINVAL;
1628         goto done;
1629     }
1630
1631     lock_AssertWrite(&op->scp->dirlock);
1632
1633     QueryPerformanceCounter(&start);
1634
1635     bplus_remove_entry++;
1636
1637     if (op->scp->dirBplus) {
1638         if (!cm_Is8Dot3(entry)) {
1639             cm_dirFid_t dfid;
1640             cm_fid_t fid;
1641             char shortName[13];
1642
1643             leafNode = bplus_Lookup(op->scp->dirBplus, key);
1644             if (leafNode != NONODE) {
1645                 int         slot;
1646                 Nptr        firstDataNode, dataNode, nextDataNode;
1647                 int         exact = 0;
1648                 int         count = 0;
1649
1650                 /* Found a leaf that matches the key via a case-insensitive
1651                  * match.  There may be one or more data nodes that match.
1652                  * If we have an exact match, return that.
1653                  * If we have an ambiguous match, return an error.
1654                  * If we have only one inexact match, return that.
1655                  */
1656                 slot = getSlot(op->scp->dirBplus, leafNode);
1657                 if (slot <= BTERROR) {
1658                     op->scp->dirDataVersion = 0;
1659                     rc = EINVAL;
1660                     goto done;
1661                 }
1662                 firstDataNode = getnode(leafNode, slot);
1663
1664                 for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1665                     count++;
1666                     if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1667                         exact = 1;
1668                         break;
1669                     }
1670                     nextDataNode = getdatanext(dataNode);
1671                 }
1672
1673                 if (exact) {
1674                     fid = getdatavalue(dataNode).fid;
1675                     rc = 0;
1676                 } else if (count == 1) {
1677                     fid = getdatavalue(firstDataNode).fid;
1678                     rc = CM_ERROR_INEXACT_MATCH;
1679                 } else {
1680                     rc = CM_ERROR_AMBIGUOUS_FILENAME;
1681                 }
1682             }
1683
1684
1685             if (rc != CM_ERROR_AMBIGUOUS_FILENAME) {
1686                 dfid.vnode = htonl(fid.vnode);
1687                 dfid.unique = htonl(fid.unique);
1688                 cm_Gen8Dot3NameInt(entry, &dfid, shortName, NULL);
1689
1690                 /* delete first the long name and then the short name */
1691                 delete(op->scp->dirBplus, key);
1692                 key.name = shortName;
1693                 delete(op->scp->dirBplus, key);
1694             }
1695         } else {
1696             char * longname = NULL;
1697             /* We need to lookup the 8dot3 name to determine what the
1698              * matching long name is
1699              */
1700             leafNode = bplus_Lookup(op->scp->dirBplus, key);
1701             if (leafNode != NONODE) {
1702                 int         slot;
1703                 Nptr        firstDataNode, dataNode, nextDataNode;
1704                 int         exact = 0;
1705                 int         count = 0;
1706
1707                 /* Found a leaf that matches the key via a case-insensitive
1708                  * match.  There may be one or more data nodes that match.
1709                  * If we have an exact match, return that.
1710                  * If we have an ambiguous match, return an error.
1711                  * If we have only one inexact match, return that.
1712                  */
1713                 slot = getSlot(op->scp->dirBplus, leafNode);
1714                 if (slot <= BTERROR) {
1715                     op->scp->dirDataVersion = 0;
1716                     rc = EINVAL;
1717                     goto done;
1718
1719                 }
1720                 firstDataNode = getnode(leafNode, slot);
1721
1722                 for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1723                     count++;
1724                     if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1725                         exact = 1;
1726                         break;
1727                     }
1728                     nextDataNode = getdatanext(dataNode);
1729                 }
1730
1731                 if (exact) {
1732                     longname = getdatavalue(dataNode).longname;
1733                     rc = 0;
1734                 } else if (count == 1) {
1735                     longname = getdatavalue(firstDataNode).longname;
1736                     rc = CM_ERROR_INEXACT_MATCH;
1737                 } else {
1738                     rc = CM_ERROR_AMBIGUOUS_FILENAME;
1739                 }
1740             }
1741
1742             if (rc != CM_ERROR_AMBIGUOUS_FILENAME) {
1743                 if (longname) {
1744                     key.name = longname;
1745                     delete(op->scp->dirBplus, key);
1746                     key.name = entry;
1747                 }
1748                 delete(op->scp->dirBplus, key);
1749             }
1750         }
1751     }
1752
1753     QueryPerformanceCounter(&end);
1754
1755     bplus_remove_time += (end.QuadPart - start.QuadPart);
1756
1757   done:
1758     return rc;
1759
1760 }
1761
1762 static
1763 int cm_BPlusDirFoo(struct cm_scache *scp, struct cm_dirEntry *dep,
1764                    void *dummy, osi_hyper_t *entryOffsetp)
1765 {
1766     keyT   key = {dep->name};
1767     dataT  data;
1768     char   shortName[13];
1769
1770     data.fid.cell = scp->fid.cell;
1771     data.fid.volume = scp->fid.volume;
1772     data.fid.vnode = ntohl(dep->fid.vnode);
1773     data.fid.unique = ntohl(dep->fid.unique);
1774     data.longname = NULL;
1775
1776     /* the Write lock is held in cm_BPlusDirBuildTree() */
1777     insert(scp->dirBplus, key, data);
1778     if (!cm_Is8Dot3(dep->name)) {
1779         cm_dirFid_t dfid;
1780         dfid.vnode = dep->fid.vnode;
1781         dfid.unique = dep->fid.unique;
1782
1783         cm_Gen8Dot3NameInt(dep->name, &dfid, shortName, NULL);
1784
1785         key.name = shortName;
1786         data.longname = strdup(dep->name);
1787         insert(scp->dirBplus, key, data);
1788     }
1789
1790 #ifdef BTREE_DEBUG
1791     findAllBtreeValues(scp->dirBplus);
1792 #endif
1793     return 0;
1794 }
1795
1796
1797 /*
1798  *   scp->dirlock must be writeLocked before call
1799  *
1800  *   scp->mutex must not be held
1801  */
1802 long cm_BPlusDirBuildTree(cm_scache_t *scp, cm_user_t *userp, cm_req_t* reqp)
1803 {
1804     long rc = 0;
1805     osi_hyper_t thyper;
1806     LARGE_INTEGER start, end;
1807
1808     osi_assertx(scp->dirBplus == NULL, "cm_BPlusDirBuildTree called on non-empty tree");
1809
1810     lock_AssertWrite(&scp->dirlock);
1811
1812     QueryPerformanceCounter(&start);
1813     bplus_build_tree++;
1814
1815     if (scp->dirBplus == NULL) {
1816         scp->dirBplus = initBtree(64, MAX_FANOUT, compareKeys);
1817     }
1818     if (scp->dirBplus == NULL) {
1819         rc = ENOMEM;
1820     } else {
1821         thyper.LowPart = 0;
1822         thyper.HighPart = 0;
1823         rc = cm_ApplyDir(scp, cm_BPlusDirFoo, NULL, &thyper, userp, reqp, NULL);
1824     }
1825
1826     QueryPerformanceCounter(&end);
1827
1828     bplus_build_time += (end.QuadPart - start.QuadPart);
1829
1830 #if 0
1831     cm_BPlusDirEnumTest(scp, 1);
1832 #endif
1833     return rc;
1834 }
1835
1836 int cm_MemDumpBPlusStats(FILE *outputFile, char *cookie, int lock)
1837 {
1838     int zilch;
1839     char output[128];
1840
1841     sprintf(output, "%s - B+ Lookup    Hits: %-8d\r\n", cookie, bplus_lookup_hits);
1842     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1843     sprintf(output, "%s -      Inexact Hits: %-8d\r\n", cookie, bplus_lookup_hits_inexact);
1844     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1845     sprintf(output, "%s -    Ambiguous Hits: %-8d\r\n", cookie, bplus_lookup_ambiguous);
1846     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1847     sprintf(output, "%s -            Misses: %-8d\r\n", cookie, bplus_lookup_misses);
1848     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1849     sprintf(output, "%s -            Create: %-8d\r\n", cookie, bplus_create_entry);
1850     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1851     sprintf(output, "%s -            Remove: %-8d\r\n", cookie, bplus_remove_entry);
1852     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1853     sprintf(output, "%s -        Build Tree: %-8d\r\n", cookie, bplus_build_tree);
1854     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1855     sprintf(output, "%s -         Free Tree: %-8d\r\n", cookie, bplus_free_tree);
1856     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1857     sprintf(output, "%s -          DV Error: %-8d\r\n", cookie, bplus_dv_error);
1858     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1859
1860     sprintf(output, "%s - B+ Time    Lookup: %-16I64d\r\n", cookie, bplus_lookup_time);
1861     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1862     sprintf(output, "%s -            Create: %-16I64d\r\n", cookie, bplus_create_time);
1863     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1864     sprintf(output, "%s -            Remove: %-16I64d\r\n", cookie, bplus_remove_time);
1865     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1866     sprintf(output, "%s -             Build: %-16I64d\r\n", cookie, bplus_build_time);
1867     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1868     sprintf(output, "%s -              Free: %-16I64d\r\n", cookie, bplus_free_time);
1869     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
1870
1871     return(0);
1872 }
1873
1874 void cm_BPlusDumpStats(void)
1875 {
1876     afsi_log("B+ Lookup    Hits: %-8d", bplus_lookup_hits);
1877     afsi_log("     Inexact Hits: %-8d", bplus_lookup_hits_inexact);
1878     afsi_log("   Ambiguous Hits: %-8d", bplus_lookup_ambiguous);
1879     afsi_log("           Misses: %-8d", bplus_lookup_misses);
1880     afsi_log("           Create: %-8d", bplus_create_entry);
1881     afsi_log("           Remove: %-8d", bplus_remove_entry);
1882     afsi_log("       Build Tree: %-8d", bplus_build_tree);
1883     afsi_log("        Free Tree: %-8d", bplus_free_tree);
1884     afsi_log("         DV Error: %-8d", bplus_dv_error);
1885
1886     afsi_log("B+ Time    Lookup: %-16I64d", bplus_lookup_time);
1887     afsi_log("           Create: %-16I64d", bplus_create_time);
1888     afsi_log("           Remove: %-16I64d", bplus_remove_time);
1889     afsi_log("            Build: %-16I64d", bplus_build_time);
1890     afsi_log("             Free: %-16I64d", bplus_free_time);
1891 }
1892
1893 static cm_direnum_t *
1894 cm_BPlusEnumAlloc(afs_uint32 entries)
1895 {
1896     cm_direnum_t * enump;
1897     size_t         size;
1898
1899     if (entries == 0)
1900         return NULL;
1901
1902     size = sizeof(cm_direnum_t)+(entries-1)*sizeof(cm_direnum_entry_t);
1903     enump = (cm_direnum_t *)malloc(size);
1904     memset(enump, 0, size);
1905     enump->count = entries;
1906     return enump;
1907 }
1908
1909 long
1910 cm_BPlusDirEnumerate(cm_scache_t *scp, afs_uint32 locked,
1911                      char * maskp, cm_direnum_t **enumpp)
1912 {
1913     afs_uint32 count = 0, slot, numentries;
1914     Nptr leafNode = NONODE, nextLeafNode;
1915     Nptr firstDataNode, dataNode, nextDataNode;
1916     cm_direnum_t * enump;
1917     long rc = 0;
1918     char buffer[512];
1919
1920     osi_Log0(afsd_logp, "cm_BPlusDirEnumerate start");
1921
1922     /* Read lock the bplus tree so the data can't change */
1923     if (!locked)
1924         lock_ObtainRead(&scp->dirlock);
1925
1926     if (scp->dirBplus == NULL) {
1927         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate No BPlus Tree");
1928         goto done;
1929     }
1930
1931     /* Compute the number of entries */
1932     for (count = 0, leafNode = getleaf(scp->dirBplus); leafNode; leafNode = nextLeafNode) {
1933
1934         for ( slot = 1, numentries = numentries(leafNode); slot <= numentries; slot++) {
1935             firstDataNode = getnode(leafNode, slot);
1936
1937             for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1938                 if (maskp == NULL) {
1939                     /* name is in getdatakey(dataNode) */
1940                     if (getdatavalue(dataNode).longname != NULL ||
1941                         cm_Is8Dot3(getdatakey(dataNode).name))
1942                         count++;
1943                 } else {
1944                     if (cm_Is8Dot3(getdatakey(dataNode).name) &&
1945                         smb_V3MatchMask(getdatakey(dataNode).name, maskp, CM_FLAG_CASEFOLD) ||
1946                         getdatavalue(dataNode).longname == NULL &&
1947                         smb_V3MatchMask(getdatavalue(dataNode).longname, maskp, CM_FLAG_CASEFOLD))
1948                         count++;
1949                 }
1950                 nextDataNode = getdatanext(dataNode);
1951             }
1952         }
1953
1954         nextLeafNode = getnextnode(leafNode);
1955     }
1956
1957     sprintf(buffer, "BPlusTreeEnumerate count = %d", count);
1958     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, buffer));
1959
1960     /* Allocate the enumeration object */
1961     enump = cm_BPlusEnumAlloc(count);
1962     if (enump == NULL) {
1963         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate Alloc failed");
1964         rc = ENOMEM;
1965         goto done;
1966     }
1967
1968     /* Copy the name and fid for each longname entry into the enumeration */
1969     for (count = 0, leafNode = getleaf(scp->dirBplus); leafNode; leafNode = nextLeafNode) {
1970
1971         for ( slot = 1, numentries = numentries(leafNode); slot <= numentries; slot++) {
1972             firstDataNode = getnode(leafNode, slot);
1973
1974             for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1975                 char * name;
1976                 int hasShortName;
1977                 int includeIt = 0;
1978
1979                 if (maskp == NULL) {
1980                     if (getdatavalue(dataNode).longname != NULL ||
1981                          cm_Is8Dot3(getdatakey(dataNode).name))
1982                     {
1983                         includeIt = 1;
1984                     }
1985                 } else {
1986                     if (cm_Is8Dot3(getdatakey(dataNode).name) &&
1987                         smb_V3MatchMask(getdatakey(dataNode).name, maskp, CM_FLAG_CASEFOLD) ||
1988                         getdatavalue(dataNode).longname == NULL &&
1989                          smb_V3MatchMask(getdatavalue(dataNode).longname, maskp, CM_FLAG_CASEFOLD))
1990                     {
1991                         includeIt = 1;
1992                     }
1993                 }
1994
1995                 if (includeIt) {
1996                     if (getdatavalue(dataNode).longname) {
1997                         name = strdup(getdatavalue(dataNode).longname);
1998                         hasShortName = 1;
1999                     } else {
2000                         name = strdup(getdatakey(dataNode).name);
2001                         hasShortName = 0;
2002                     }
2003
2004                     if (name == NULL) {
2005                         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate strdup failed");
2006                         rc = ENOMEM;
2007                         goto done;
2008                     }
2009                     enump->entry[count].name = name;
2010                     enump->entry[count].fid  = getdatavalue(dataNode).fid;
2011                     if (hasShortName)
2012                         strncpy(enump->entry[count].shortName, getdatakey(dataNode).name,
2013                                 sizeof(enump->entry[count].shortName));
2014                     else
2015                         enump->entry[count].shortName[0] = '\0';
2016                     count++;
2017                 }
2018                 nextDataNode = getdatanext(dataNode);
2019             }
2020         }
2021
2022         nextLeafNode = getnextnode(leafNode);
2023     }
2024
2025   done:
2026     if (!locked)
2027         lock_ReleaseRead(&scp->dirlock);
2028
2029     /* if we failed, cleanup any mess */
2030     if (rc != 0) {
2031         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate rc != 0");
2032         if (enump) {
2033             for ( count = 0; count < enump->count && enump->entry[count].name; count++ ) {
2034                 free(enump->entry[count].name);
2035             }
2036             free(enump);
2037             enump = NULL;
2038         }
2039     }
2040
2041     osi_Log0(afsd_logp, "cm_BPlusDirEnumerate end");
2042     *enumpp = enump;
2043     return rc;
2044 }
2045
2046 long
2047 cm_BPlusDirNextEnumEntry(cm_direnum_t *enump, cm_direnum_entry_t **entrypp)
2048 {
2049     if (enump == NULL || entrypp == NULL || enump->next > enump->count) {
2050         if (entrypp)
2051             *entrypp = NULL;
2052         osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry invalid input");
2053         return CM_ERROR_INVAL;                        \
2054     }
2055
2056     *entrypp = &enump->entry[enump->next++];
2057     if ( enump->next == enump->count ) {
2058         osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry STOPNOW");
2059         return CM_ERROR_STOPNOW;
2060     }
2061     else {
2062         osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry SUCCESS");
2063         return 0;
2064     }
2065 }
2066
2067 long
2068 cm_BPlusDirFreeEnumeration(cm_direnum_t *enump)
2069 {
2070     afs_uint32 count;
2071
2072     osi_Log0(afsd_logp, "cm_BPlusDirFreeEnumeration");
2073
2074     if (enump) {
2075         for ( count = 0; count < enump->count && enump->entry[count].name; count++ ) {
2076             free(enump->entry[count].name);
2077         }
2078         free(enump);
2079     }
2080     return 0;
2081 }
2082
2083 long
2084 cm_BPlusDirEnumTest(cm_scache_t * dscp, afs_uint32 locked)
2085 {
2086     cm_direnum_t *       enump = NULL;
2087     cm_direnum_entry_t * entryp;
2088     long                 code;
2089
2090     osi_Log0(afsd_logp, "cm_BPlusDirEnumTest start");
2091
2092     for (code = cm_BPlusDirEnumerate(dscp, locked, NULL, &enump); code == 0; ) {
2093         code = cm_BPlusDirNextEnumEntry(enump, &entryp);
2094         if (code == 0 || code == CM_ERROR_STOPNOW) {
2095             char buffer[1024];
2096             cm_scache_t *scp;
2097             char * type = "ScpNotFound";
2098             afs_int32 dv = -1;
2099
2100             scp = cm_FindSCache(&entryp->fid);
2101             if (scp) {
2102                 switch (scp->fileType) {
2103                 case CM_SCACHETYPE_FILE :
2104                     type = "File";
2105                     break;
2106                 case CM_SCACHETYPE_DIRECTORY    :
2107                     type = "Directory";
2108                     break;
2109                 case CM_SCACHETYPE_SYMLINK      :
2110                     type = "Symlink";
2111                     break;
2112                 case CM_SCACHETYPE_MOUNTPOINT:
2113                     type = "MountPoint";
2114                     break;
2115                 case CM_SCACHETYPE_DFSLINK   :
2116                     type = "Dfs";
2117                     break;
2118                 case CM_SCACHETYPE_INVALID   :
2119                     type = "Invalid";
2120                     break;
2121                 default:
2122                     type = "Unknown";
2123                     break;
2124                 }
2125
2126                 dv = scp->dataVersion;
2127             cm_ReleaseSCache(scp);
2128             }
2129
2130             sprintf(buffer, "'%s' Fid = (%d,%d,%d,%d) Short = '%s' Type %s DV %d",
2131                     entryp->name,
2132                     entryp->fid.cell, entryp->fid.volume, entryp->fid.vnode, entryp->fid.unique,
2133                     entryp->shortName,
2134                     type,
2135                     dv);
2136
2137             osi_Log0(afsd_logp, osi_LogSaveString(afsd_logp, buffer));
2138         }
2139     }
2140
2141     if (enump)
2142         cm_BPlusDirFreeEnumeration(enump);
2143
2144     osi_Log0(afsd_logp, "cm_BPlusDirEnumTest end");
2145
2146     return 0;
2147 }
2148 #endif /* USE_BPLUS */