src/WINNT/afsd/cm_btree.c

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