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