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