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 = 0;
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         return NULL;
2164
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, afs_uint32 locked,
2174                      clientchar_t * maskp, cm_direnum_t **enumpp)
2175 {
2176     afs_uint32 count = 0, slot, numentries;
2177     Nptr leafNode = NONODE, nextLeafNode;
2178     Nptr firstDataNode, dataNode, nextDataNode;
2179     cm_direnum_t * enump = NULL;
2180     long rc = 0;
2181     char buffer[512];
2182
2183     osi_Log0(afsd_logp, "cm_BPlusDirEnumerate start");
2184
2185     /* Read lock the bplus tree so the data can't change */
2186     if (!locked)
2187         lock_ObtainRead(&scp->dirlock);
2188
2189     if (scp->dirBplus == NULL) {
2190         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate No BPlus Tree");
2191         rc = CM_ERROR_WOULDBLOCK;
2192         goto done;
2193     }
2194
2195     /* Compute the number of entries */
2196     for (count = 0, leafNode = getleaf(scp->dirBplus); leafNode; leafNode = nextLeafNode) {
2197
2198         for ( slot = 1, numentries = numentries(leafNode); slot <= numentries; slot++) {
2199             firstDataNode = getnode(leafNode, slot);
2200
2201             for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
2202
2203                 /* There can be two data nodes for one file.  One for
2204                    the long name and one for the short name.  We only
2205                    include one of these for the enumeration */
2206
2207                 if (maskp == NULL) {
2208                     if (!getdatavalue(dataNode).shortform)
2209                         count++;
2210                 } else {
2211                     if (!getdatavalue(dataNode).shortform &&
2212                         cm_MatchMask(getdatavalue(dataNode).cname, maskp, CM_FLAG_CASEFOLD))
2213                         count++;
2214                 }
2215                 nextDataNode = getdatanext(dataNode);
2216             }
2217         }
2218
2219         nextLeafNode = getnextnode(leafNode);
2220     }
2221
2222     StringCbPrintfA(buffer, sizeof(buffer), "BPlusTreeEnumerate count = %d", count);
2223     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, buffer));
2224
2225     /* Allocate the enumeration object */
2226     enump = cm_BPlusEnumAlloc(count);
2227     if (enump == NULL) {
2228         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate Alloc failed");
2229         rc = ENOMEM;
2230         goto done;
2231     }
2232
2233     /* Copy the name and fid for each cname entry into the enumeration */
2234     for (count = 0, leafNode = getleaf(scp->dirBplus); leafNode; leafNode = nextLeafNode) {
2235
2236         for ( slot = 1, numentries = numentries(leafNode); slot <= numentries; slot++) {
2237             firstDataNode = getnode(leafNode, slot);
2238
2239             for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
2240                 clientchar_t * name;
2241                 int includeIt = 0;
2242
2243                 if (maskp == NULL) {
2244                     if (!getdatavalue(dataNode).shortform) {
2245                         includeIt = 1;
2246                     }
2247                 } else {
2248                     if (!getdatavalue(dataNode).shortform &&
2249                         cm_MatchMask(getdatavalue(dataNode).cname, maskp, CM_FLAG_CASEFOLD)) {
2250                         includeIt = 1;
2251                     }
2252                 }
2253
2254                 if (includeIt) {
2255                     name = cm_ClientStrDup(getdatavalue(dataNode).cname);
2256
2257                     if (name == NULL) {
2258                         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate strdup failed");
2259                         rc = ENOMEM;
2260                         goto done;
2261                     }
2262
2263                     enump->entry[count].name = name;
2264                     enump->entry[count].fid  = getdatavalue(dataNode).fid;
2265
2266                     if (!cm_Is8Dot3(name)) {
2267                         cm_dirFid_t dfid;
2268
2269                         dfid.vnode = htonl(getdatavalue(dataNode).fid.vnode);
2270                         dfid.unique = htonl(getdatavalue(dataNode).fid.unique);
2271
2272                         cm_Gen8Dot3NameIntW(name, &dfid, enump->entry[count].shortName, NULL);
2273                     } else {
2274                         StringCbCopyW(enump->entry[count].shortName,
2275                                       sizeof(enump->entry[count].shortName),
2276                                       name);
2277                     }
2278
2279                     count++;
2280                 }
2281                 nextDataNode = getdatanext(dataNode);
2282             }
2283         }
2284
2285         nextLeafNode = getnextnode(leafNode);
2286     }
2287
2288   done:
2289     if (!locked)
2290         lock_ReleaseRead(&scp->dirlock);
2291
2292     /* if we failed, cleanup any mess */
2293     if (rc != 0) {
2294         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate rc != 0");
2295         if (enump) {
2296             for ( count = 0; count < enump->count && enump->entry[count].name; count++ ) {
2297                 free(enump->entry[count].name);
2298             }
2299             free(enump);
2300             enump = NULL;
2301         }
2302     }
2303
2304     osi_Log0(afsd_logp, "cm_BPlusDirEnumerate end");
2305     *enumpp = enump;
2306     return rc;
2307 }
2308
2309 long
2310 cm_BPlusDirEnumBulkStat(cm_scache_t *dscp, cm_direnum_t *enump, cm_user_t *userp, cm_req_t *reqp)
2311 {
2312     cm_bulkStat_t *bsp;
2313     afs_uint32 count;
2314     afs_uint32 code;
2315
2316     if ( dscp->fid.cell == AFS_FAKE_ROOT_CELL_ID )
2317         return 0;
2318
2319     bsp = malloc(sizeof(cm_bulkStat_t));
2320     memset(bsp, 0, sizeof(cm_bulkStat_t));
2321
2322     for ( count = 0; count < enump->count; count++ ) {
2323         cm_scache_t   *tscp = cm_FindSCache(&enump->entry[count].fid);
2324         int i;
2325
2326         if (tscp) {
2327             if (lock_TryWrite(&tscp->rw)) {
2328                 /* we have an entry that we can look at */
2329                 if (!(tscp->flags & CM_SCACHEFLAG_EACCESS) && cm_HaveCallback(tscp)) {
2330                     /* we have a callback on it.  Don't bother
2331                      * fetching this stat entry, since we're happy
2332                      * with the info we have.
2333                      */
2334                     lock_ReleaseWrite(&tscp->rw);
2335                     cm_ReleaseSCache(tscp);
2336                     continue;
2337                 }
2338                 lock_ReleaseWrite(&tscp->rw);
2339             }   /* got lock */
2340             cm_ReleaseSCache(tscp);
2341         }       /* found entry */
2342
2343         i = bsp->counter++;
2344         bsp->fids[i].Volume = enump->entry[count].fid.volume;
2345         bsp->fids[i].Vnode = enump->entry[count].fid.vnode;
2346         bsp->fids[i].Unique = enump->entry[count].fid.unique;
2347
2348         if (bsp->counter == AFSCBMAX) {
2349             code = cm_TryBulkStatRPC(dscp, bsp, userp, reqp);
2350             memset(bsp, 0, sizeof(cm_bulkStat_t));
2351         }
2352     }
2353
2354     if (bsp->counter > 0)
2355         code = cm_TryBulkStatRPC(dscp, bsp, userp, reqp);
2356
2357     free(bsp);
2358     return 0;
2359 }
2360
2361 long
2362 cm_BPlusDirNextEnumEntry(cm_direnum_t *enump, cm_direnum_entry_t **entrypp)
2363 {
2364     if (enump == NULL || entrypp == NULL || enump->next >= enump->count) {
2365         if (entrypp)
2366             *entrypp = NULL;
2367         osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry invalid input");
2368         return CM_ERROR_INVAL;
2369     }
2370
2371     *entrypp = &enump->entry[enump->next++];
2372     if ( enump->next == enump->count ) {
2373         osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry STOPNOW");
2374         return CM_ERROR_STOPNOW;
2375     }
2376     else {
2377         osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry SUCCESS");
2378         return 0;
2379     }
2380 }
2381
2382 long
2383 cm_BPlusDirFreeEnumeration(cm_direnum_t *enump)
2384 {
2385     afs_uint32 count;
2386
2387     osi_Log0(afsd_logp, "cm_BPlusDirFreeEnumeration");
2388
2389     if (enump) {
2390         for ( count = 0; count < enump->count && enump->entry[count].name; count++ ) {
2391             free(enump->entry[count].name);
2392         }
2393         free(enump);
2394     }
2395     return 0;
2396 }
2397
2398 long
2399 cm_BPlusDirEnumTest(cm_scache_t * dscp, afs_uint32 locked)
2400 {
2401     cm_direnum_t *       enump = NULL;
2402     cm_direnum_entry_t * entryp;
2403     long                 code;
2404
2405     osi_Log0(afsd_logp, "cm_BPlusDirEnumTest start");
2406
2407     for (code = cm_BPlusDirEnumerate(dscp, locked, NULL, &enump); code == 0; ) {
2408         code = cm_BPlusDirNextEnumEntry(enump, &entryp);
2409         if (code == 0 || code == CM_ERROR_STOPNOW) {
2410             char buffer[1024];
2411             cm_scache_t *scp;
2412             char * type = "ScpNotFound";
2413             afs_uint64 dv = -1;
2414
2415             scp = cm_FindSCache(&entryp->fid);
2416             if (scp) {
2417                 switch (scp->fileType) {
2418                 case CM_SCACHETYPE_FILE :
2419                     type = "File";
2420                     break;
2421                 case CM_SCACHETYPE_DIRECTORY    :
2422                     type = "Directory";
2423                     break;
2424                 case CM_SCACHETYPE_SYMLINK      :
2425                     type = "Symlink";
2426                     break;
2427                 case CM_SCACHETYPE_MOUNTPOINT:
2428                     type = "MountPoint";
2429                     break;
2430                 case CM_SCACHETYPE_DFSLINK   :
2431                     type = "Dfs";
2432                     break;
2433                 case CM_SCACHETYPE_INVALID   :
2434                     type = "Invalid";
2435                     break;
2436                 default:
2437                     type = "Unknown";
2438                     break;
2439                 }
2440
2441                 dv = scp->dataVersion;
2442                 cm_ReleaseSCache(scp);
2443             }
2444
2445             StringCbPrintfA(buffer, sizeof(buffer), "'%S' Fid = (%d,%d,%d,%d) Short = '%S' Type %s DV %I64d",
2446                     entryp->name,
2447                     entryp->fid.cell, entryp->fid.volume, entryp->fid.vnode, entryp->fid.unique,
2448                     entryp->shortName,
2449                     type,
2450                     dv);
2451
2452             osi_Log0(afsd_logp, osi_LogSaveString(afsd_logp, buffer));
2453         }
2454     }
2455
2456     if (enump)
2457         cm_BPlusDirFreeEnumeration(enump);
2458
2459     osi_Log0(afsd_logp, "cm_BPlusDirEnumTest end");
2460
2461     return 0;
2462 }
2463 #endif /* USE_BPLUS */