src/WINNT/afsd/cm_btree.c

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