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