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     %s (%d.%d.%d) |\n", getfundata(B).fsname, getfundata(B).fid.volume,
1448              getfundata(B).fid.vnode, getfundata(B).fid.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_shortNames && !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                     /* delete first the long name and then the short name */
1912                     delete(op->scp->dirBplus, key);
1913
1914                     if (cm_shortNames) {
1915                         dfid.vnode = htonl(fid.vnode);
1916                         dfid.unique = htonl(fid.unique);
1917                         cm_Gen8Dot3NameIntW(centry, &dfid, shortName, NULL);
1918
1919                         key.name = shortName;
1920                         delete(op->scp->dirBplus, key);
1921                     }
1922                 }
1923             } /* !NONODE */
1924         } else {
1925             clientchar_t * cname = NULL;
1926
1927             /* We need to lookup the 8dot3 name to determine what the
1928              * matching long name is
1929              */
1930             leafNode = bplus_Lookup(op->scp->dirBplus, key);
1931             if (leafNode != NONODE) {
1932                 int         slot;
1933                 Nptr        firstDataNode, dataNode, nextDataNode;
1934                 int         exact = 0;
1935                 int         count = 0;
1936
1937                 /* Found a leaf that matches the key via a case-insensitive
1938                  * match.  There may be one or more data nodes that match.
1939                  * If we have an exact match, return that.
1940                  * If we have an ambiguous match, return an error.
1941                  * If we have only one inexact match, return that.
1942                  */
1943                 slot = getSlot(op->scp->dirBplus, leafNode);
1944                 if (slot <= BTERROR) {
1945                     op->scp->dirDataVersion = 0;
1946                     rc = EINVAL;
1947                     goto done;
1948
1949                 }
1950                 firstDataNode = getnode(leafNode, slot);
1951
1952                 for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1953                     count++;
1954                     if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1955                         exact = 1;
1956                         break;
1957                     }
1958                     nextDataNode = getdatanext(dataNode);
1959                 }
1960
1961                 if (exact) {
1962                     cname = getdatavalue(dataNode).cname;
1963                     rc = 0;
1964                 } else if (count == 1) {
1965                     cname = getdatavalue(firstDataNode).cname;
1966                     rc = CM_ERROR_INEXACT_MATCH;
1967                 } else {
1968                     rc = CM_ERROR_AMBIGUOUS_FILENAME;
1969                 }
1970             }
1971
1972             if (rc != CM_ERROR_AMBIGUOUS_FILENAME) {
1973                 if (cname) {
1974                     normchar_t * longNName = cm_NormalizeStringAlloc(cname, -1, NULL);
1975
1976                     key.name = longNName;
1977                     delete(op->scp->dirBplus, key);
1978                     key.name = normalizedEntry;
1979
1980                     free(longNName);
1981                 }
1982
1983                 delete(op->scp->dirBplus, key);
1984             }
1985         }
1986     }
1987
1988     QueryPerformanceCounter(&end);
1989
1990     bplus_remove_time += (end.QuadPart - start.QuadPart);
1991
1992   done:
1993     if (normalizedEntry)
1994         free(normalizedEntry);
1995
1996     return rc;
1997
1998 }
1999
2000
2001 int cm_BPlusDirFoo(struct cm_scache *scp, struct cm_dirEntry *dep,
2002                    void *dummy, osi_hyper_t *entryOffsetp)
2003 {
2004     keyT   key = {NULL};
2005     dataT  data;
2006     normchar_t *normalized_name=NULL;
2007
2008     cm_SetFid(&data.fid, scp->fid.cell, scp->fid.volume,
2009               ntohl(dep->fid.vnode), ntohl(dep->fid.unique));
2010     data.cname = NULL;
2011     data.fsname = NULL;
2012
2013     normalized_name = cm_FsStringToNormStringAlloc(dep->name, -1, NULL);
2014
2015     if (normalized_name) {
2016         key.name = normalized_name;
2017     } else {
2018 #ifdef DEBUG
2019         DebugBreak();
2020 #endif
2021         return 0;
2022     }
2023
2024     data.cname = cm_FsStringToClientStringAlloc(dep->name, -1, NULL);
2025     if (data.cname == NULL) {
2026 #ifdef DEBUG
2027         DebugBreak();
2028 #endif
2029         return 0;
2030     }
2031     data.fsname = cm_FsStrDup(dep->name);
2032     data.shortform = FALSE;
2033
2034     /* the Write lock is held in cm_BPlusDirBuildTree() */
2035     insert(scp->dirBplus, key, data);
2036
2037     if (cm_shortNames && !cm_Is8Dot3(data.cname)) {
2038         cm_dirFid_t dfid;
2039         wchar_t wshortName[13];
2040
2041         dfid.vnode = dep->fid.vnode;
2042         dfid.unique = dep->fid.unique;
2043
2044         cm_Gen8Dot3NameIntW(data.cname, &dfid, wshortName, NULL);
2045
2046         key.name = wshortName;
2047         data.cname = cm_FsStringToClientStringAlloc(dep->name, -1, NULL);
2048         if (data.cname) {
2049             data.fsname = cm_FsStrDup(dep->name);
2050             data.shortform = TRUE;
2051
2052             insert(scp->dirBplus, key, data);
2053         }
2054     }
2055
2056     if (normalized_name)
2057         free(normalized_name);
2058
2059 #ifdef BTREE_DEBUG
2060     findAllBtreeValues(scp->dirBplus);
2061 #endif
2062     return 0;
2063 }
2064
2065
2066 /*
2067  *   scp->dirlock must be writeLocked before call
2068  *
2069  *   scp->mutex must not be held
2070  */
2071 long cm_BPlusDirBuildTree(cm_scache_t *scp, cm_user_t *userp, cm_req_t* reqp)
2072 {
2073     long rc = 0;
2074     osi_hyper_t thyper;
2075     LARGE_INTEGER start, end;
2076
2077     osi_assertx(scp->dirBplus == NULL, "cm_BPlusDirBuildTree called on non-empty tree");
2078
2079     lock_AssertWrite(&scp->dirlock);
2080
2081     QueryPerformanceCounter(&start);
2082     bplus_build_tree++;
2083
2084     if (scp->dirBplus == NULL) {
2085         scp->dirBplus = initBtree(64, MAX_FANOUT, cm_BPlusCompareNormalizedKeys);
2086     }
2087     if (scp->dirBplus == NULL) {
2088         rc = ENOMEM;
2089     } else {
2090         thyper.LowPart = 0;
2091         thyper.HighPart = 0;
2092         rc = cm_ApplyDir(scp, cm_BPlusDirFoo, NULL, &thyper, userp, reqp, NULL);
2093     }
2094
2095     QueryPerformanceCounter(&end);
2096
2097     bplus_build_time += (end.QuadPart - start.QuadPart);
2098
2099 #if 0
2100     cm_BPlusDirEnumTest(scp, 1);
2101 #endif
2102     return rc;
2103 }
2104
2105 int cm_MemDumpBPlusStats(FILE *outputFile, char *cookie, int lock)
2106 {
2107     int zilch;
2108     char output[128];
2109
2110     StringCbPrintfA(output, sizeof(output), "%s - B+ Lookup    Hits: %-8d\r\n", cookie, bplus_lookup_hits);
2111     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2112     StringCbPrintfA(output, sizeof(output), "%s -      Inexact Hits: %-8d\r\n", cookie, bplus_lookup_hits_inexact);
2113     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2114     StringCbPrintfA(output, sizeof(output), "%s -    Ambiguous Hits: %-8d\r\n", cookie, bplus_lookup_ambiguous);
2115     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2116     StringCbPrintfA(output, sizeof(output), "%s -            Misses: %-8d\r\n", cookie, bplus_lookup_misses);
2117     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2118     StringCbPrintfA(output, sizeof(output), "%s -            Create: %-8d\r\n", cookie, bplus_create_entry);
2119     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2120     StringCbPrintfA(output, sizeof(output), "%s -            Remove: %-8d\r\n", cookie, bplus_remove_entry);
2121     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2122     StringCbPrintfA(output, sizeof(output), "%s -        Build Tree: %-8d\r\n", cookie, bplus_build_tree);
2123     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2124     StringCbPrintfA(output, sizeof(output), "%s -         Free Tree: %-8d\r\n", cookie, bplus_free_tree);
2125     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2126     StringCbPrintfA(output, sizeof(output), "%s -          DV Error: %-8d\r\n", cookie, bplus_dv_error);
2127     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2128
2129     StringCbPrintfA(output, sizeof(output), "%s - B+ Time    Lookup: %-16I64d\r\n", cookie, bplus_lookup_time);
2130     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2131     StringCbPrintfA(output, sizeof(output), "%s -            Create: %-16I64d\r\n", cookie, bplus_create_time);
2132     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2133     StringCbPrintfA(output, sizeof(output), "%s -            Remove: %-16I64d\r\n", cookie, bplus_remove_time);
2134     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2135     StringCbPrintfA(output, sizeof(output), "%s -             Build: %-16I64d\r\n", cookie, bplus_build_time);
2136     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2137     StringCbPrintfA(output, sizeof(output), "%s -              Free: %-16I64d\r\n", cookie, bplus_free_time);
2138     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2139
2140     return(0);
2141 }
2142
2143 void cm_BPlusDumpStats(void)
2144 {
2145     afsi_log("B+ Lookup    Hits: %-8d", bplus_lookup_hits);
2146     afsi_log("     Inexact Hits: %-8d", bplus_lookup_hits_inexact);
2147     afsi_log("   Ambiguous Hits: %-8d", bplus_lookup_ambiguous);
2148     afsi_log("           Misses: %-8d", bplus_lookup_misses);
2149     afsi_log("           Create: %-8d", bplus_create_entry);
2150     afsi_log("           Remove: %-8d", bplus_remove_entry);
2151     afsi_log("       Build Tree: %-8d", bplus_build_tree);
2152     afsi_log("        Free Tree: %-8d", bplus_free_tree);
2153     afsi_log("         DV Error: %-8d", bplus_dv_error);
2154
2155     afsi_log("B+ Time    Lookup: %-16I64d", bplus_lookup_time);
2156     afsi_log("           Create: %-16I64d", bplus_create_time);
2157     afsi_log("           Remove: %-16I64d", bplus_remove_time);
2158     afsi_log("            Build: %-16I64d", bplus_build_time);
2159     afsi_log("             Free: %-16I64d", bplus_free_time);
2160 }
2161
2162 static cm_direnum_t *
2163 cm_BPlusEnumAlloc(afs_uint32 entries)
2164 {
2165     cm_direnum_t * enump;
2166     size_t         size;
2167
2168     if (entries == 0)
2169         size = sizeof(cm_direnum_t);
2170     else
2171         size = sizeof(cm_direnum_t)+(entries-1)*sizeof(cm_direnum_entry_t);
2172     enump = (cm_direnum_t *)malloc(size);
2173     if (enump) {
2174         memset(enump, 0, size);
2175         enump->count = entries;
2176     }
2177     return enump;
2178 }
2179
2180 long
2181 cm_BPlusDirEnumerate(cm_scache_t *dscp, cm_user_t *userp, cm_req_t *reqp,
2182                      afs_uint32 locked, clientchar_t * maskp,
2183                      afs_uint32 fetchStatus, cm_direnum_t **enumpp)
2184 {
2185     afs_uint32 count = 0, slot, numentries;
2186     Nptr leafNode = NONODE, nextLeafNode;
2187     Nptr firstDataNode, dataNode, nextDataNode;
2188     cm_direnum_t * enump = NULL;
2189     long rc = 0;
2190     char buffer[512];
2191
2192     osi_Log0(afsd_logp, "cm_BPlusDirEnumerate start");
2193
2194     /* Read lock the bplus tree so the data can't change */
2195     if (!locked)
2196         lock_ObtainRead(&dscp->dirlock);
2197
2198     /*
2199      * Hold a reference to the directory so that it won't be
2200      * recycled while the enumeration is active.
2201      */
2202     cm_HoldSCache(dscp);
2203     cm_HoldUser(userp);
2204
2205     if (dscp->dirBplus == NULL) {
2206         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate No BPlus Tree");
2207         rc = CM_ERROR_WOULDBLOCK;
2208         goto done;
2209     }
2210
2211     /* Compute the number of entries */
2212     for (count = 0, leafNode = getleaf(dscp->dirBplus); leafNode; leafNode = nextLeafNode) {
2213
2214         for ( slot = 1, numentries = numentries(leafNode); slot <= numentries; slot++) {
2215             firstDataNode = getnode(leafNode, slot);
2216
2217             for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
2218
2219                 /* There can be two data nodes for one file.  One for
2220                    the long name and one for the short name.  We only
2221                    include one of these for the enumeration */
2222
2223                 if (maskp == NULL) {
2224                     if (!getdatavalue(dataNode).shortform)
2225                         count++;
2226                 } else {
2227                     if (!getdatavalue(dataNode).shortform &&
2228                         cm_MatchMask(getdatavalue(dataNode).cname, maskp, CM_FLAG_CASEFOLD))
2229                         count++;
2230                 }
2231                 nextDataNode = getdatanext(dataNode);
2232             }
2233         }
2234
2235         nextLeafNode = getnextnode(leafNode);
2236     }
2237
2238     StringCbPrintfA(buffer, sizeof(buffer), "BPlusTreeEnumerate count = %d", count);
2239     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, buffer));
2240
2241     /* Allocate the enumeration object */
2242     enump = cm_BPlusEnumAlloc(count);
2243     if (enump == NULL) {
2244         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate Alloc failed");
2245         rc = ENOMEM;
2246         goto done;
2247     }
2248
2249     /* Copy the name and fid for each cname entry into the enumeration */
2250     for (count = 0, leafNode = getleaf(dscp->dirBplus); leafNode; leafNode = nextLeafNode) {
2251
2252         for ( slot = 1, numentries = numentries(leafNode); slot <= numentries; slot++) {
2253             firstDataNode = getnode(leafNode, slot);
2254
2255             for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
2256                 clientchar_t * name;
2257                 int includeIt = 0;
2258
2259                 if (maskp == NULL) {
2260                     if (!getdatavalue(dataNode).shortform) {
2261                         includeIt = 1;
2262                     }
2263                 } else {
2264                     if (!getdatavalue(dataNode).shortform &&
2265                         cm_MatchMask(getdatavalue(dataNode).cname, maskp, CM_FLAG_CASEFOLD)) {
2266                         includeIt = 1;
2267                     }
2268                 }
2269
2270                 if (includeIt) {
2271                     name = cm_ClientStrDup(getdatavalue(dataNode).cname);
2272
2273                     if (name == NULL) {
2274                         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate strdup failed");
2275                         rc = ENOMEM;
2276                         goto done;
2277                     }
2278
2279                     enump->entry[count].name = name;
2280                     enump->entry[count].fid  = getdatavalue(dataNode).fid;
2281
2282                     if (cm_shortNames) {
2283                         if (!cm_Is8Dot3(name)) {
2284                             cm_dirFid_t dfid;
2285
2286                             dfid.vnode = htonl(getdatavalue(dataNode).fid.vnode);
2287                             dfid.unique = htonl(getdatavalue(dataNode).fid.unique);
2288
2289                             cm_Gen8Dot3NameIntW(name, &dfid, enump->entry[count].shortName, NULL);
2290                         } else {
2291                             StringCbCopyW(enump->entry[count].shortName,
2292                                           sizeof(enump->entry[count].shortName),
2293                                           name);
2294                         }
2295                     }
2296
2297                     count++;
2298                 }
2299                 nextDataNode = getdatanext(dataNode);
2300             }
2301         }
2302
2303         nextLeafNode = getnextnode(leafNode);
2304     }
2305
2306     enump->dscp = dscp;
2307     enump->userp = userp;
2308     enump->reqFlags = reqp->flags;
2309     enump->fetchStatus = fetchStatus;
2310     enump->dataVersion = dscp->dirDataVersion;
2311
2312   done:
2313     if (!locked)
2314         lock_ReleaseRead(&dscp->dirlock);
2315
2316     /* if we failed, cleanup any mess */
2317     if (rc != 0) {
2318         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate rc != 0");
2319
2320         /*
2321          * release the directory because we failed to generate an enumeration object.
2322          * adjust the directory position in the queue to ensure it doesn't get pushed
2323          * out by the allocation of a large number of cm_scache objects.
2324          */
2325         lock_ObtainWrite(&cm_scacheLock);
2326         cm_AdjustScacheLRU(dscp);
2327         cm_ReleaseSCacheNoLock(dscp);
2328         lock_ReleaseWrite(&cm_scacheLock);
2329         cm_ReleaseUser(userp);
2330         if (enump) {
2331             for ( count = 0; count < enump->count && enump->entry[count].name; count++ ) {
2332                 free(enump->entry[count].name);
2333             }
2334             free(enump);
2335             enump = NULL;
2336         }
2337     }
2338
2339     osi_Log0(afsd_logp, "cm_BPlusDirEnumerate end");
2340     *enumpp = enump;
2341     return rc;
2342 }
2343
2344 long
2345 cm_BPlusDirEnumBulkStat(cm_direnum_t *enump)
2346 {
2347     cm_scache_t *dscp = enump->dscp;
2348     cm_user_t   *userp = enump->userp;
2349     cm_bulkStat_t *bsp = NULL;
2350     afs_uint32 ** bs_errorCodep = NULL;
2351     afs_uint32 ** bs_flagsp = NULL;
2352     afs_uint32    dscp_errorCode = 0;
2353     afs_uint32    dscp_flags = 0;
2354     afs_uint32 count;
2355     afs_uint32 code = 0;
2356     cm_req_t req;
2357     int i;
2358     cm_scache_t   *tscp;
2359     afs_int32 nobulkstat = 0;
2360
2361     cm_InitReq(&req);
2362     req.flags = enump->reqFlags;
2363
2364     if ( dscp->fid.cell == AFS_FAKE_ROOT_CELL_ID )
2365         return 0;
2366
2367     bsp = malloc(sizeof(cm_bulkStat_t));
2368     if (!bsp) {
2369         code = ENOMEM;
2370         goto done;
2371     }
2372     memset(bsp, 0, sizeof(cm_bulkStat_t));
2373     bsp->userp = userp;
2374
2375     bs_errorCodep = malloc(sizeof(afs_uint32 *) * AFSCBMAX);
2376     if (!bs_errorCodep) {
2377         code = ENOMEM;
2378         goto done;
2379     }
2380
2381     bs_flagsp = malloc(sizeof(afs_uint32 *) * AFSCBMAX);
2382     if (!bs_flagsp) {
2383         code = ENOMEM;
2384         goto done;
2385     }
2386
2387     /*
2388      * In order to prevent the directory callback from expiring
2389      * on really large directories with many symlinks to mount
2390      * points such as /afs/andrew.cmu.edu/usr/, always include
2391      * the directory fid in the search.
2392      */
2393     bsp->fids[0].Volume = dscp->fid.volume;
2394     bsp->fids[0].Vnode = dscp->fid.vnode;
2395     bsp->fids[0].Unique = dscp->fid.unique;
2396     bs_errorCodep[0] = &dscp_errorCode;
2397     bs_flagsp[0] = &dscp_flags;
2398     bsp->counter++;
2399
2400   restart_stat:
2401     for ( count = 0; count < enump->count; count++ ) {
2402         if ( !wcscmp(L".", enump->entry[count].name) || !wcscmp(L"..", enump->entry[count].name) ) {
2403             continue;
2404         }
2405
2406         tscp = cm_FindSCache(&enump->entry[count].fid);
2407         if (tscp) {
2408             if (lock_TryWrite(&tscp->rw)) {
2409                 /* we have an entry that we can look at */
2410                 if (!cm_EAccesFindEntry(userp, &tscp->fid) && cm_HaveCallback(tscp)) {
2411                     /* we have a callback on it.  Don't bother
2412                      * fetching this stat entry, since we're happy
2413                      * with the info we have.
2414                      */
2415                     lock_ReleaseWrite(&tscp->rw);
2416                     cm_ReleaseSCache(tscp);
2417                     enump->entry[count].flags |= CM_DIRENUM_FLAG_GOT_STATUS;
2418                     enump->entry[count].errorCode = 0;
2419                     continue;
2420                 }
2421
2422                 if (nobulkstat) {
2423                     code = cm_SyncOp(tscp, NULL, userp, &req, 0,
2424                                       CM_SCACHESYNC_NEEDCALLBACK | CM_SCACHESYNC_GETSTATUS);
2425                     lock_ReleaseWrite(&tscp->rw);
2426                     cm_ReleaseSCache(tscp);
2427                     enump->entry[count].flags |= CM_DIRENUM_FLAG_GOT_STATUS;
2428                     enump->entry[count].errorCode = code;
2429                     continue;
2430                 }
2431
2432                 lock_ReleaseWrite(&tscp->rw);
2433             }   /* got lock */
2434             cm_ReleaseSCache(tscp);
2435         }       /* found entry */
2436
2437         i = bsp->counter++;
2438         bsp->fids[i].Volume = enump->entry[count].fid.volume;
2439         bsp->fids[i].Vnode = enump->entry[count].fid.vnode;
2440         bsp->fids[i].Unique = enump->entry[count].fid.unique;
2441         bs_errorCodep[i] = &enump->entry[count].errorCode;
2442         bs_flagsp[bsp->counter] = &enump->entry[i].flags;
2443         enump->entry[count].flags |= CM_DIRENUM_FLAG_GOT_STATUS;
2444
2445         if (bsp->counter == AFSCBMAX) {
2446             code = cm_TryBulkStatRPC(dscp, bsp, userp, &req);
2447             if (code == CM_ERROR_BULKSTAT_FAILURE) {
2448                 /*
2449                  * If bulk stat cannot be used for this directory
2450                  * we must perform individual fetch status calls.
2451                  * Restart from the beginning of the enumeration.
2452                  */
2453                 nobulkstat = 1;
2454
2455                 for (i=0; i<bsp->counter; i++) {
2456                     *(bs_flagsp[i]) &= ~CM_DIRENUM_FLAG_GOT_STATUS;
2457                 }
2458                 goto restart_stat;
2459             }
2460
2461             if (code) {
2462                 /* on any other error, exit */
2463                 goto done;
2464             }
2465             for ( i=0; i<bsp->counter; i++) {
2466                 *(bs_errorCodep[i]) = cm_MapRPCError(bsp->stats[i].errorCode, &req);
2467             }
2468
2469             if (dscp_errorCode) {
2470                 code = dscp_errorCode;
2471                 goto done;
2472             }
2473             memset(bsp, 0, sizeof(cm_bulkStat_t));
2474             bsp->userp = userp;
2475
2476             /*
2477              * In order to prevent the directory callback from expiring
2478              * on really large directories with many symlinks to mount
2479              * points such as /afs/andrew.cmu.edu/usr/, always include
2480              * the directory fid in the search.
2481              */
2482             bsp->fids[0].Volume = dscp->fid.volume;
2483             bsp->fids[0].Vnode = dscp->fid.vnode;
2484             bsp->fids[0].Unique = dscp->fid.unique;
2485             bs_errorCodep[0] = &dscp_errorCode;
2486             bsp->counter++;
2487         }
2488     }
2489
2490     if (bsp->counter > 0) {
2491         code = cm_TryBulkStatRPC(dscp, bsp, userp, &req);
2492         if (code == CM_ERROR_BULKSTAT_FAILURE) {
2493             /*
2494              * If bulk stat cannot be used for this directory
2495              * we must perform individual fetch status calls.
2496              * Restart from the beginning of the enumeration.
2497              */
2498             nobulkstat = 1;
2499
2500             for (i=0; i<bsp->counter; i++) {
2501                 *(bs_flagsp[i]) &= ~CM_DIRENUM_FLAG_GOT_STATUS;
2502             }
2503             goto restart_stat;
2504         }
2505
2506         if (code)
2507             goto done;
2508
2509         for ( i=0; i<bsp->counter; i++) {
2510             *(bs_errorCodep[i]) = cm_MapRPCError(bsp->stats[i].errorCode, &req);
2511         }
2512
2513         if (dscp_errorCode) {
2514             code = dscp_errorCode;
2515             goto done;
2516         }
2517     }
2518
2519   done:
2520     if (bsp)
2521         free(bsp);
2522     if (bs_errorCodep)
2523         free(bs_errorCodep);
2524     if (bs_flagsp)
2525         free(bs_flagsp);
2526
2527     return code;
2528 }
2529
2530 /*
2531  * Similar to cm_BPlusDirEnumBulkStat() except that only
2532  * one RPC is issued containing the provided scp FID and up to
2533  * AFSCBMAX - 2 other FIDs for which the status info has yet
2534  * to be obtained.
2535  */
2536 long
2537 cm_BPlusDirEnumBulkStatOne(cm_direnum_t *enump, cm_scache_t *scp)
2538 {
2539     cm_scache_t *dscp = enump->dscp;
2540     cm_user_t   *userp = enump->userp;
2541     cm_bulkStat_t *bsp = NULL;
2542     afs_uint32 ** bs_errorCodep = NULL;
2543     afs_uint32 ** bs_flagsp = NULL;
2544     afs_uint32    dscp_errorCode = 0;
2545     afs_uint32    dscp_flags = 0;
2546     afs_uint32    scp_errorCode = 0;
2547     afs_uint32    scp_flags = 0;
2548     afs_uint32 code = 0;
2549     afs_uint32 i;
2550     cm_req_t req;
2551     cm_scache_t   *tscp;
2552
2553     if ( dscp->fid.cell == AFS_FAKE_ROOT_CELL_ID )
2554         return 0;
2555
2556     cm_InitReq(&req);
2557     req.flags = enump->reqFlags;
2558
2559     bsp = malloc(sizeof(cm_bulkStat_t));
2560     if (!bsp) {
2561         code = ENOMEM;
2562         goto done;
2563     }
2564     memset(bsp, 0, sizeof(cm_bulkStat_t));
2565     bsp->userp = userp;
2566
2567     bs_errorCodep = malloc(sizeof(afs_uint32 *) * AFSCBMAX);
2568     if (!bs_errorCodep) {
2569         code = ENOMEM;
2570         goto done;
2571     }
2572
2573     bs_flagsp = malloc(sizeof(afs_uint32 *) * AFSCBMAX);
2574     if (!bs_flagsp) {
2575         code = ENOMEM;
2576         goto done;
2577     }
2578
2579     /*
2580      * In order to prevent the directory callback from expiring
2581      * on really large directories with many symlinks to mount
2582      * points such as /afs/andrew.cmu.edu/usr/, always include
2583      * the directory fid in the search.
2584      */
2585     bsp->fids[0].Volume = dscp->fid.volume;
2586     bsp->fids[0].Vnode = dscp->fid.vnode;
2587     bsp->fids[0].Unique = dscp->fid.unique;
2588     bs_errorCodep[0] = &dscp_errorCode;
2589     bs_flagsp[0] = &dscp_flags;
2590     bsp->counter++;
2591
2592     /*
2593      * There is an assumption that this FID is located
2594      * within the directory enumeration but it could be
2595      * the case that the enumeration is out of date and
2596      * the FID is not listed.  So we explicitly add it
2597      * after the directory FID and then skip it later
2598      * if we find it.
2599      */
2600     bsp->fids[1].Volume = scp->fid.volume;
2601     bsp->fids[1].Vnode = scp->fid.vnode;
2602     bsp->fids[1].Unique = scp->fid.unique;
2603     bs_errorCodep[1] = &scp_errorCode;
2604     bs_flagsp[1] = &scp_flags;
2605     bsp->counter++;
2606
2607     if (enump->count <= AFSCBMAX - 1) {
2608         i = 0;
2609     } else {
2610         /*
2611          * Find the requested FID in the enumeration and start from there.
2612          */
2613         for (i=0; i < enump->count && cm_FidCmp(&scp->fid, &enump->entry[i].fid); i++);
2614     }
2615
2616     for ( ; bsp->counter < AFSCBMAX && i < enump->count; i++) {
2617         if ( !wcscmp(L".", enump->entry[i].name) || !wcscmp(L"..", enump->entry[i].name) ) {
2618             continue;
2619         }
2620
2621         tscp = cm_FindSCache(&enump->entry[i].fid);
2622         if (tscp) {
2623             if (tscp == scp) {
2624                 cm_ReleaseSCache(tscp);
2625                 continue;
2626             }
2627
2628             if (lock_TryWrite(&tscp->rw)) {
2629                 /* we have an entry that we can look at */
2630                 if (!cm_EAccesFindEntry(userp, &tscp->fid) && cm_HaveCallback(tscp)) {
2631                     /* we have a callback on it.  Don't bother
2632                      * fetching this stat entry, since we're happy
2633                      * with the info we have.
2634                      */
2635                     lock_ReleaseWrite(&tscp->rw);
2636                     cm_ReleaseSCache(tscp);
2637                     enump->entry[i].flags |= CM_DIRENUM_FLAG_GOT_STATUS;
2638                     enump->entry[i].errorCode = 0;
2639                     continue;
2640                 }
2641                 lock_ReleaseWrite(&tscp->rw);
2642             }   /* got lock */
2643             cm_ReleaseSCache(tscp);
2644         } /* found entry */
2645
2646         bsp->fids[bsp->counter].Volume = enump->entry[i].fid.volume;
2647         bsp->fids[bsp->counter].Vnode = enump->entry[i].fid.vnode;
2648         bsp->fids[bsp->counter].Unique = enump->entry[i].fid.unique;
2649         bs_errorCodep[bsp->counter] = &enump->entry[i].errorCode;
2650         bs_flagsp[bsp->counter] = &enump->entry[i].flags;
2651         enump->entry[i].flags |= CM_DIRENUM_FLAG_GOT_STATUS;
2652         bsp->counter++;
2653     }
2654
2655     if (bsp->counter > 0) {
2656         code = cm_TryBulkStatRPC(dscp, bsp, userp, &req);
2657         /* Now process any errors that might have occurred */
2658         if (code == CM_ERROR_BULKSTAT_FAILURE) {
2659             for (i=2; i<bsp->counter; i++) {
2660                 *(bs_flagsp[i]) &= ~CM_DIRENUM_FLAG_GOT_STATUS;
2661             }
2662
2663             lock_ObtainWrite(&scp->rw);
2664             code = cm_SyncOp(scp, NULL, userp, &req, 0,
2665                               CM_SCACHESYNC_NEEDCALLBACK | CM_SCACHESYNC_GETSTATUS);
2666             lock_ReleaseWrite(&scp->rw);
2667             goto done;
2668         }
2669
2670         if (code)
2671             goto done;
2672
2673         for ( i=0; i<bsp->counter; i++) {
2674             *(bs_errorCodep[i]) = cm_MapRPCError(bsp->stats[i].errorCode, &req);
2675         }
2676
2677         /* Check if there was an error on the requested FID, if so return it */
2678         if ( scp_errorCode ) {
2679             code = scp_errorCode;
2680             goto done;
2681         }
2682     }
2683
2684   done:
2685     if (bsp)
2686         free(bsp);
2687     if (bs_errorCodep)
2688         free(bs_errorCodep);
2689     if (bs_flagsp)
2690         free(bs_flagsp);
2691
2692     return code;
2693 }
2694
2695 static long
2696 cm_BPlusDirEnumBulkStatNext(cm_direnum_t *enump)
2697 {
2698     cm_scache_t *dscp = enump->dscp;
2699     cm_user_t   *userp = enump->userp;
2700     cm_bulkStat_t *bsp = NULL;
2701     afs_uint32 ** bs_errorCodep = NULL;
2702     afs_uint32 ** bs_flagsp = NULL;
2703     afs_uint32    dscp_errorCode = 0;
2704     afs_uint32    dscp_flags = 0;
2705     afs_uint32 count;
2706     afs_uint32 code = 0;
2707     cm_req_t req;
2708     cm_scache_t   *tscp;
2709     afs_int32     next = -1;
2710     int i;
2711
2712     if ( dscp->fid.cell == AFS_FAKE_ROOT_CELL_ID )
2713         return 0;
2714
2715     cm_InitReq(&req);
2716     req.flags = enump->reqFlags;
2717
2718     bsp = malloc(sizeof(cm_bulkStat_t));
2719     if (!bsp) {
2720         code = ENOMEM;
2721         goto done;
2722     }
2723     memset(bsp, 0, sizeof(cm_bulkStat_t));
2724     bsp->userp = userp;
2725
2726     bs_errorCodep = malloc(sizeof(afs_uint32 *) * AFSCBMAX);
2727     if (!bs_errorCodep) {
2728         code = ENOMEM;
2729         goto done;
2730     }
2731
2732     bs_flagsp = malloc(sizeof(afs_uint32 *) * AFSCBMAX);
2733     if (!bs_flagsp) {
2734         code = ENOMEM;
2735         goto done;
2736     }
2737
2738     /*
2739      * In order to prevent the directory callback from expiring
2740      * on really large directories with many symlinks to mount
2741      * points such as /afs/andrew.cmu.edu/usr/, always include
2742      * the directory fid in the search.
2743      */
2744     bsp->fids[0].Volume = dscp->fid.volume;
2745     bsp->fids[0].Vnode = dscp->fid.vnode;
2746     bsp->fids[0].Unique = dscp->fid.unique;
2747     bs_errorCodep[0] = &dscp_errorCode;
2748     bs_flagsp[0] = &dscp_flags;
2749     bsp->counter++;
2750
2751     for ( count = enump->next; count < enump->count && bsp->counter < AFSCBMAX; count++ ) {
2752         if ( !wcscmp(L".", enump->entry[count].name) || !wcscmp(L"..", enump->entry[count].name) ) {
2753             continue;
2754         }
2755
2756         if (next == -1)
2757             next = count;
2758         tscp = cm_FindSCache(&enump->entry[count].fid);
2759         if (tscp) {
2760             if (lock_TryWrite(&tscp->rw)) {
2761                 /* we have an entry that we can look at */
2762                 if (!cm_EAccesFindEntry(userp, &tscp->fid) && cm_HaveCallback(tscp)) {
2763                     /* we have a callback on it.  Don't bother
2764                      * fetching this stat entry, since we're happy
2765                      * with the info we have.
2766                      */
2767                     lock_ReleaseWrite(&tscp->rw);
2768                     cm_ReleaseSCache(tscp);
2769                     enump->entry[count].flags |= CM_DIRENUM_FLAG_GOT_STATUS;
2770                     enump->entry[count].errorCode = 0;
2771                     continue;
2772                 }
2773                 lock_ReleaseWrite(&tscp->rw);
2774             }   /* got lock */
2775             cm_ReleaseSCache(tscp);
2776         }       /* found entry */
2777
2778         bsp->fids[bsp->counter].Volume = enump->entry[count].fid.volume;
2779         bsp->fids[bsp->counter].Vnode = enump->entry[count].fid.vnode;
2780         bsp->fids[bsp->counter].Unique = enump->entry[count].fid.unique;
2781         bs_errorCodep[bsp->counter] = &enump->entry[count].errorCode;
2782         bs_flagsp[bsp->counter] = &enump->entry[count].flags;
2783         enump->entry[count].flags |= CM_DIRENUM_FLAG_GOT_STATUS;
2784         bsp->counter++;
2785     }
2786
2787     if (bsp->counter > 0) {
2788         code = cm_TryBulkStatRPC(dscp, bsp, userp, &req);
2789         /* Now process any errors that might have occurred */
2790         if (code == CM_ERROR_BULKSTAT_FAILURE) {
2791             for (i=0; i<bsp->counter; i++) {
2792                 *(bs_flagsp[i]) &= ~CM_DIRENUM_FLAG_GOT_STATUS;
2793             }
2794
2795             code = cm_GetSCache(&enump->entry[next].fid, NULL, &tscp, userp, &req);
2796             if (code == 0) {
2797                 if (lock_TryWrite(&tscp->rw)) {
2798                     code = cm_SyncOp(tscp, NULL, userp, &req, 0,
2799                                      CM_SCACHESYNC_NEEDCALLBACK | CM_SCACHESYNC_GETSTATUS);
2800                     lock_ReleaseWrite(&tscp->rw);
2801                     *(bs_errorCodep[1]) = code;
2802                     *(bs_flagsp[1]) |= CM_DIRENUM_FLAG_GOT_STATUS;
2803                 }
2804                 cm_ReleaseSCache(tscp);
2805             } else {
2806                 *(bs_errorCodep[1]) = code;
2807                 *(bs_flagsp[1]) |= CM_DIRENUM_FLAG_GOT_STATUS;
2808             }
2809             goto done;
2810         }
2811
2812         if (code)
2813             goto done;
2814
2815         for ( i=0; i<bsp->counter; i++) {
2816             *(bs_errorCodep[i]) = cm_MapRPCError(bsp->stats[i].errorCode, &req);
2817         }
2818
2819         if (dscp_errorCode) {
2820             code = dscp_errorCode;
2821             goto done;
2822         }
2823     }
2824
2825   done:
2826     if (bsp)
2827         free(bsp);
2828     if (bs_errorCodep)
2829         free(bs_errorCodep);
2830     if (bs_flagsp)
2831         free(bs_flagsp);
2832
2833     return code;
2834 }
2835
2836 long
2837 cm_BPlusDirNextEnumEntry(cm_direnum_t *enump, cm_direnum_entry_t **entrypp)
2838 {
2839     long code = 0;
2840
2841     if (enump == NULL || entrypp == NULL || enump->next >= enump->count) {
2842         if (entrypp)
2843             *entrypp = NULL;
2844         osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry invalid input");
2845         return CM_ERROR_INVAL;
2846     }
2847
2848     if (enump->fetchStatus &&
2849                 !(enump->entry[enump->next].flags & CM_DIRENUM_FLAG_GOT_STATUS)) {
2850         code = cm_BPlusDirEnumBulkStatNext(enump);
2851     }
2852
2853     *entrypp = &enump->entry[enump->next++];
2854     if ( enump->next == enump->count ) {
2855         osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry STOPNOW");
2856         return CM_ERROR_STOPNOW;
2857     }
2858     else {
2859         if (code) {
2860             (*entrypp)->errorCode = code;
2861             osi_Log1(afsd_logp, "cm_BPlusDirNextEnumEntry ERROR 0x%x", code);
2862         } else {
2863             osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry SUCCESS");
2864         }
2865         return 0;
2866     }
2867 }
2868
2869 long
2870 cm_BPlusDirPeekNextEnumEntry(cm_direnum_t *enump, cm_direnum_entry_t **entrypp)
2871 {
2872     long code;
2873
2874     if (enump == NULL || entrypp == NULL || enump->next >= enump->count) {
2875         if (entrypp)
2876             *entrypp = NULL;
2877         osi_Log0(afsd_logp, "cm_BPlusDirPeekNextEnumEntry invalid input");
2878         return CM_ERROR_INVAL;
2879     }
2880
2881     if (enump->fetchStatus &&
2882         !(enump->entry[enump->next].flags & CM_DIRENUM_FLAG_GOT_STATUS)) {
2883         code = cm_BPlusDirEnumBulkStatNext(enump);
2884         if (code)
2885             return code;
2886     }
2887
2888     *entrypp = &enump->entry[enump->next];
2889     if ( enump->next == enump->count ) {
2890         osi_Log0(afsd_logp, "cm_BPlusDirPeekNextEnumEntry STOPNOW");
2891         return CM_ERROR_STOPNOW;
2892     }
2893     else {
2894         osi_Log0(afsd_logp, "cm_BPlusDirPeekNextEnumEntry SUCCESS");
2895         return 0;
2896     }
2897 }
2898
2899 long
2900 cm_BPlusDirFreeEnumeration(cm_direnum_t *enump)
2901 {
2902     afs_uint32 count;
2903
2904     osi_Log0(afsd_logp, "cm_BPlusDirFreeEnumeration");
2905
2906     if (enump) {
2907         /*
2908          * Release the directory object but first adjust its position
2909          * in the LRU queue to ensure that it does not get stuck at the
2910          * end due to the allocation of a large number of cm_scache
2911          * entries in the directory.
2912          */
2913         lock_ObtainWrite(&cm_scacheLock);
2914         cm_AdjustScacheLRU(enump->dscp);
2915         cm_ReleaseSCacheNoLock(enump->dscp);
2916         lock_ReleaseWrite(&cm_scacheLock);
2917         cm_ReleaseUser(enump->userp);
2918
2919         for ( count = 0; count < enump->count && enump->entry[count].name; count++ ) {
2920             free(enump->entry[count].name);
2921         }
2922         free(enump);
2923     }
2924     return 0;
2925 }
2926
2927 long
2928 cm_BPlusDirEnumTest(cm_scache_t * dscp, cm_user_t *userp, cm_req_t *reqp, afs_uint32 locked)
2929 {
2930     cm_direnum_t *       enump = NULL;
2931     cm_direnum_entry_t * entryp;
2932     long                 code;
2933
2934
2935     osi_Log0(afsd_logp, "cm_BPlusDirEnumTest start");
2936
2937     for (code = cm_BPlusDirEnumerate(dscp, userp, reqp, locked, NULL, 1, &enump); code == 0; ) {
2938         code = cm_BPlusDirNextEnumEntry(enump, &entryp);
2939         if (code == 0 || code == CM_ERROR_STOPNOW) {
2940             char buffer[1024];
2941             cm_scache_t *scp;
2942             char * type = "ScpNotFound";
2943             afs_uint64 dv = -1;
2944
2945             scp = cm_FindSCache(&entryp->fid);
2946             if (scp) {
2947                 switch (scp->fileType) {
2948                 case CM_SCACHETYPE_FILE :
2949                     type = "File";
2950                     break;
2951                 case CM_SCACHETYPE_DIRECTORY    :
2952                     type = "Directory";
2953                     break;
2954                 case CM_SCACHETYPE_SYMLINK      :
2955                     type = "Symlink";
2956                     break;
2957                 case CM_SCACHETYPE_MOUNTPOINT:
2958                     type = "MountPoint";
2959                     break;
2960                 case CM_SCACHETYPE_DFSLINK   :
2961                     type = "Dfs";
2962                     break;
2963                 case CM_SCACHETYPE_INVALID   :
2964                     type = "Invalid";
2965                     break;
2966                 default:
2967                     type = "Unknown";
2968                     break;
2969                 }
2970
2971                 dv = scp->dataVersion;
2972                 cm_ReleaseSCache(scp);
2973             }
2974
2975             StringCbPrintfA(buffer, sizeof(buffer), "'%S' Fid = (%d,%d,%d,%d) Short = '%S' Type %s DV %I64d",
2976                     entryp->name,
2977                     entryp->fid.cell, entryp->fid.volume, entryp->fid.vnode, entryp->fid.unique,
2978                     entryp->shortName,
2979                     type,
2980                     dv);
2981
2982             osi_Log0(afsd_logp, osi_LogSaveString(afsd_logp, buffer));
2983         }
2984     }
2985
2986     if (enump)
2987         cm_BPlusDirFreeEnumeration(enump);
2988
2989     osi_Log0(afsd_logp, "cm_BPlusDirEnumTest end");
2990
2991     return 0;
2992 }
2993 #endif /* USE_BPLUS */