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