1b262c76fc0c5584f232385149c1150e88941b0f
[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,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             if ( getdatavalue(node).origname ) {
1297                 free(getdatavalue(node).origname);
1298                 getdatavalue(node).origname = NULL;
1299             }
1300         } else { /* data node */
1301             for ( j=1; j<=getfanout(B); j++ ) {
1302                 if (getkey(node, j).name)
1303                     free(getkey(node, j).name);
1304             }
1305         }
1306         next = getallnode(node);
1307         free(node);
1308     }
1309 }
1310
1311 /**************   take a free B+tree node from the pool   **************/
1312 static Nptr 
1313 getFreeNode(Tree *B)
1314 {
1315     Nptr newNode = getfirstfreenode(B);
1316
1317     if (newNode != NONODE) {
1318         setfirstfreenode(B, getnextnode(newNode));      /* adjust free node list */
1319         setnextnode(newNode, NONODE);                   /* remove node from list */
1320     }
1321     else {
1322         newNode = malloc(sizeof(*newNode));
1323         memset(newNode, 0, sizeof(*newNode));
1324
1325         setallnode(newNode, getfirstallnode(B));
1326         setfirstallnode(B, newNode);
1327         setnodenumber(B, newNode, getpoolsize(B));
1328         setpoolsize(B, getpoolsize(B) + 1);
1329     }
1330
1331     clearflags(newNode);                        /* Sets MAGIC */
1332     return newNode;
1333 }
1334
1335
1336 /*************   return a deleted B+tree node to the pool   ************/
1337 static void 
1338 putFreeNode(Tree *B, Nptr node)
1339 {
1340     int i;
1341
1342     if (isntnode(node))
1343         return;
1344
1345     if (isdata(node)) {
1346         if ( getdatakey(node).name )
1347             free(getdatakey(node).name);
1348     } else {    /* data node */
1349         for ( i=1; i<=getfanout(B); i++ ) {
1350             if (getkey(node, i).name)
1351                 free(getkey(node, i).name);
1352         }
1353     }
1354
1355     /* free nodes do not have MAGIC set */
1356     memset(&nAdr(node), 0, sizeof(nAdr(node)));
1357     setnextnode(node, getfirstfreenode(B));     /* add node to list */
1358     setfirstfreenode(B, node);                  /* set it to be list head */
1359 }
1360
1361
1362 /*******   fill a free data node with a key and associated data   ******/
1363 static Nptr 
1364 getDataNode(Tree *B, keyT key, dataT data)
1365 {
1366     Nptr        newNode = getFreeNode(B);
1367
1368     setflag(newNode, isDATA);
1369     getdatakey(newNode).name = strdup(key.name);
1370     getdatavalue(newNode) = data;
1371     getdatanext(newNode) = NONODE;
1372
1373     return newNode;
1374 }
1375
1376
1377 #ifdef DEBUG_BTREE
1378 /***********************************************************************\
1379 |       B+tree Printing Utilities                                       |
1380 \***********************************************************************/
1381
1382 /***********************   B+tree node printer   ***********************/
1383 void showNode(Tree *B, const char * where, Nptr n)
1384 {
1385     int x;
1386
1387     sprintf(B->message, "-  --  --  --  --  --  --  --  --  --  --  --  -\n");
1388     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1389     sprintf(B->message, "| %-20s                        |\n", where);
1390     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1391     sprintf(B->message, "| node %6d                 ", getnodenumber(B, n));
1392     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1393     sprintf(B->message, "  magic    %4x  |\n", getmagic(n));
1394     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1395     sprintf(B->message, "-  --  --  --  --  --  --  --  --  --  --  --  -\n");
1396     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1397     sprintf(B->message, "| flags   %1d%1d%1d%1d ", isfew(n), isfull(n), isroot(n), isleaf(n));
1398     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1399     sprintf(B->message, "| keys = %5d ", numentries(n));
1400     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1401     sprintf(B->message, "| node = %6d  |\n", getnodenumber(B, getfirstnode(n)));
1402     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1403     for (x = 1; x <= numentries(n); x++) {
1404         sprintf(B->message, "| entry %6d ", x);
1405         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1406         sprintf(B->message, "| key = %6s ", getkey(n, x).name);
1407         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1408         sprintf(B->message, "| node = %6d  |\n", getnodenumber(B, getnode(n, x)));
1409         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1410     }
1411     sprintf(B->message, "-  --  --  --  --  --  --  --  --  --  --  --  -\n");
1412     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1413 }
1414
1415 /******************   B+tree class variable printer   ******************/
1416 void showBtree(Tree *B)
1417 {
1418     sprintf(B->message, "-  --  --  --  --  --  -\n");
1419     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1420     sprintf(B->message, "|  B+tree  %10p  |\n", (void *) B);
1421     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1422     sprintf(B->message, "-  --  --  --  --  --  -\n");
1423     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1424     sprintf(B->message, "|  root        %6d  |\n", getnodenumber(B, getroot(B)));
1425     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1426     sprintf(B->message, "|  leaf        %6d  |\n", getnodenumber(B, getleaf(B)));
1427     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1428     sprintf(B->message, "|  fanout         %3d  |\n", getfanout(B) + 1);
1429     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1430     sprintf(B->message, "|  minfanout      %3d  |\n", getminfanout(B, getroot(B)) + 1);
1431     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1432     sprintf(B->message, "|  height         %3d  |\n", gettreeheight(B));
1433     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1434     sprintf(B->message, "|  freenode    %6d  |\n", getnodenumber(B, getfirstfreenode(B)));
1435     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1436     sprintf(B->message, "|  theKey      %6s  |\n", getfunkey(B).name);
1437     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1438     sprintf(B->message, "|  theData     %d.%d.%d |\n", getfundata(B).volume,
1439              getfundata(B).vnode, getfundata(B).unique);
1440     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1441     sprintf(B->message, "-  --  --  --  --  --  -\n");
1442     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1443 }
1444
1445 void 
1446 listBtreeNodes(Tree *B, const char * parent_desc, Nptr node)
1447 {
1448     int i;
1449     char thisnode[64];
1450     dataT data;
1451
1452     if (isntnode(node)) {
1453         sprintf(B->message, "%s - NoNode!!!\n");
1454         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1455         return;
1456     } 
1457     
1458     if (!isnode(node))
1459     {
1460         data = getdatavalue(node);
1461         sprintf(B->message, "%s - data node %d (%d.%d.%d)\n", 
1462                  parent_desc, getnodenumber(B, node),
1463                  data.fid.volume, data.fid.vnode, data.fid.unique);
1464         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1465         return;
1466     } else 
1467         showNode(B, parent_desc, node);
1468
1469     if ( isinternal(node) || isroot(node) ) {
1470         sprintf(thisnode, "parent %6d", getnodenumber(B , node));
1471
1472         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1473         for ( i= isinternal(node) ? 0 : 1; i <= numentries(node); i++ ) {
1474             listBtreeNodes(B, thisnode, i == 0 ? getfirstnode(node) : getnode(node, i));
1475         }
1476     }
1477 }
1478
1479 /***********************   B+tree data printer   ***********************/
1480 void 
1481 listBtreeValues(Tree *B, Nptr n, int num)
1482 {
1483     int slot;
1484     keyT prev = {""};
1485     dataT data;
1486
1487     for (slot = 1; (n != NONODE) && num && numentries(n); num--) {
1488         if (comparekeys(B)(getkey(n, slot),prev, 0) < 0) {
1489             sprintf(B->message, "BOMB %8s\n", getkey(n, slot).name);
1490             osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1491             DebugBreak();
1492         }
1493         prev = getkey(n, slot);
1494         data = getdatavalue(getnode(n, slot));
1495         sprintf(B->message, "%8s (%d.%d.%d)\n", 
1496                 prev.name, data.fid.volume, data.fid.vnode, data.fid.unique);
1497         osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1498         if (++slot > numentries(n))
1499             n = getnextnode(n), slot = 1;
1500     }   
1501     sprintf(B->message, "\n\n");
1502     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1503 }
1504
1505 /********************   entire B+tree data printer   *******************/
1506 void 
1507 listAllBtreeValues(Tree *B)
1508 {
1509     listBtreeValues(B, getleaf(B), BTERROR);
1510 }
1511 #endif /* DEBUG_BTREE */
1512
1513 void 
1514 findAllBtreeValues(Tree *B)
1515 {
1516     int num = -1;
1517     Nptr n = getleaf(B), l;
1518     int slot;
1519     keyT prev = {""};
1520
1521     for (slot = 1; (n != NONODE) && num && numentries(n); num--) {
1522         if (comparekeys(B)(getkey(n, slot),prev, 0) < 0) {
1523             sprintf(B->message,"BOMB %8s\n", getkey(n, slot).name);
1524             osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1525 #ifdef DEBUG_BTREE
1526             DebugBreak();
1527 #endif
1528         }
1529         prev = getkey(n, slot);
1530         l = bplus_Lookup(B, prev);
1531         if ( l != n ){
1532             if (l == NONODE)
1533                 sprintf(B->message,"BOMB %8s cannot be found\n", prev.name);
1534             else 
1535                 sprintf(B->message,"BOMB lookup(%8s) finds wrong node\n", prev.name);
1536             osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1537 #ifdef DEBUG_BTREE
1538             DebugBreak();
1539 #endif
1540         }
1541
1542         if (++slot > numentries(n))
1543             n = getnextnode(n), slot = 1;
1544     }   
1545 }
1546
1547 /* 
1548  * the return must be -1, 0, or 1.  stricmp() in MSVC 8.0
1549  * does not return only those values.
1550  *
1551  * the sorting of the tree is by case insensitive sort order
1552  * therefore, unless the strings actually match via a case
1553  * insensitive search do we want to perform the case sensitive
1554  * match.  Otherwise, the search order might be considered 
1555  * to be inconsistent when the EXACT_MATCH flag is set.
1556  */
1557 static int
1558 compareKeys(keyT key1, keyT key2, int flags)
1559 {
1560     int comp;
1561
1562     comp = cm_stricmp_utf8(key1.name, key2.name);
1563     if (comp == 0 && (flags & EXACT_MATCH))
1564         comp = strcmp(key1.name, key2.name);
1565     return (comp < 0 ? -1 : (comp > 0 ? 1 : 0));
1566 }
1567
1568 int
1569 cm_BPlusDirLookupOriginalName(cm_dirOp_t * op, char * entry,
1570                               char ** originalNameRetp)
1571 {
1572     int rc = EINVAL;
1573     keyT key = {entry};
1574     Nptr leafNode = NONODE;
1575     LARGE_INTEGER start, end;
1576     char * originalName = NULL;
1577
1578     if (op->scp->dirBplus == NULL || 
1579         op->dataVersion != op->scp->dirDataVersion) {
1580         rc = EINVAL;
1581         goto done;
1582     }
1583
1584     lock_AssertAny(&op->scp->dirlock);
1585
1586     QueryPerformanceCounter(&start);
1587
1588     leafNode = bplus_Lookup(op->scp->dirBplus, key);
1589     if (leafNode != NONODE) {
1590         int         slot;
1591         Nptr        firstDataNode, dataNode, nextDataNode;
1592         int         exact = 0;
1593         int         count = 0;
1594
1595         /* Found a leaf that matches the key via a case-insensitive
1596          * match.  There may be one or more data nodes that match.
1597          * If we have an exact match, return that.
1598          * If we have an ambiguous match, return an error.
1599          * If we have only one inexact match, return that.
1600          */
1601         slot = getSlot(op->scp->dirBplus, leafNode);
1602         if (slot <= BTERROR) {
1603             op->scp->dirDataVersion = 0;
1604             rc = (slot == BTERROR ? EINVAL : ENOENT);
1605             goto done;
1606         }
1607         firstDataNode = getnode(leafNode, slot);
1608
1609         for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1610             count++;
1611             if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1612                 exact = 1;
1613                 break;
1614             }
1615             nextDataNode = getdatanext(dataNode);
1616         }
1617
1618         if (exact) {
1619             originalName = getdatavalue(dataNode).origname;
1620             rc = 0;
1621             bplus_lookup_hits++;
1622         } else if (count == 1) {
1623             originalName = getdatavalue(firstDataNode).origname;
1624             rc = CM_ERROR_INEXACT_MATCH;
1625             bplus_lookup_hits_inexact++;
1626         } else {
1627             rc = CM_ERROR_AMBIGUOUS_FILENAME;
1628             bplus_lookup_ambiguous++;
1629         } 
1630     } else {
1631         rc = ENOENT;
1632         bplus_lookup_misses++;
1633     }
1634
1635     if (originalName)
1636         *originalNameRetp = strdup(originalName);
1637
1638     QueryPerformanceCounter(&end);
1639
1640     bplus_lookup_time += (end.QuadPart - start.QuadPart);
1641
1642   done:
1643     return rc;
1644
1645 }
1646
1647 /* Look up a file name in directory.
1648
1649    On entry:
1650        op->scp->dirlock is read locked
1651
1652    On exit:
1653        op->scp->dirlock is read locked
1654 */
1655 int
1656 cm_BPlusDirLookup(cm_dirOp_t * op, char *entry, cm_fid_t * cfid)
1657 {
1658     int rc = EINVAL;
1659     keyT key = {entry};
1660     Nptr leafNode = NONODE;
1661     LARGE_INTEGER start, end;
1662
1663     if (op->scp->dirBplus == NULL || 
1664         op->dataVersion != op->scp->dirDataVersion) {
1665         rc = EINVAL;
1666         goto done;
1667     }
1668
1669     lock_AssertAny(&op->scp->dirlock);
1670
1671     QueryPerformanceCounter(&start);
1672
1673     leafNode = bplus_Lookup(op->scp->dirBplus, key);
1674     if (leafNode != NONODE) {
1675         int         slot;
1676         Nptr        firstDataNode, dataNode, nextDataNode;
1677         int         exact = 0;
1678         int         count = 0;
1679
1680         /* Found a leaf that matches the key via a case-insensitive
1681          * match.  There may be one or more data nodes that match.
1682          * If we have an exact match, return that.
1683          * If we have an ambiguous match, return an error.
1684          * If we have only one inexact match, return that.
1685          */
1686         slot = getSlot(op->scp->dirBplus, leafNode);
1687         if (slot <= BTERROR) {
1688             op->scp->dirDataVersion = 0;
1689             rc = (slot == BTERROR ? EINVAL : ENOENT);
1690             goto done;
1691         }
1692         firstDataNode = getnode(leafNode, slot);
1693
1694         for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1695             count++;
1696             if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1697                 exact = 1;
1698                 break;
1699             }
1700             nextDataNode = getdatanext(dataNode);
1701         }
1702
1703         if (exact) {
1704             *cfid = getdatavalue(dataNode).fid;
1705             rc = 0;
1706             bplus_lookup_hits++;
1707         } else if (count == 1) {
1708             *cfid = getdatavalue(firstDataNode).fid;
1709             rc = CM_ERROR_INEXACT_MATCH;
1710             bplus_lookup_hits_inexact++;
1711         } else {
1712             rc = CM_ERROR_AMBIGUOUS_FILENAME;
1713             bplus_lookup_ambiguous++;
1714         } 
1715     } else {
1716             rc = ENOENT;
1717         bplus_lookup_misses++;
1718     }
1719
1720     QueryPerformanceCounter(&end);
1721
1722     bplus_lookup_time += (end.QuadPart - start.QuadPart);
1723
1724   done:
1725     return rc;
1726 }
1727
1728
1729 /* 
1730    On entry:
1731        op->scp->dirlock is write locked
1732
1733    On exit:
1734        op->scp->dirlock is write locked
1735 */
1736 long cm_BPlusDirCreateEntry(cm_dirOp_t * op, char *entry, cm_fid_t * cfid)
1737 {
1738     long rc = 0;
1739     keyT key = {entry};
1740     dataT  data;
1741     LARGE_INTEGER start, end;
1742     char shortName[13];
1743
1744     if (op->scp->dirBplus == NULL || 
1745         op->dataVersion != op->scp->dirDataVersion) {
1746         rc = EINVAL;
1747         goto done;
1748     }
1749
1750
1751     lock_AssertWrite(&op->scp->dirlock);
1752
1753     cm_SetFid(&data.fid, cfid->cell, cfid->volume, cfid->vnode, cfid->unique);
1754     data.longname = NULL;
1755     data.origname = NULL;
1756
1757     QueryPerformanceCounter(&start);
1758     bplus_create_entry++;
1759
1760     insert(op->scp->dirBplus, key, data);
1761     if (!cm_Is8Dot3(entry)) {
1762         cm_dirFid_t dfid;
1763         dfid.vnode = htonl(data.fid.vnode);
1764         dfid.unique = htonl(data.fid.unique);
1765
1766         cm_Gen8Dot3NameInt(entry, &dfid, shortName, NULL);
1767
1768         key.name = shortName;
1769         data.longname = strdup(entry);
1770         insert(op->scp->dirBplus, key, data);
1771     }
1772
1773     QueryPerformanceCounter(&end);
1774
1775     bplus_create_time += (end.QuadPart - start.QuadPart);
1776
1777   done:
1778
1779     return rc;
1780 }
1781
1782 /* 
1783    On entry:
1784        op->scp->dirlock is write locked
1785
1786    On exit:
1787        op->scp->dirlock is write locked
1788 */
1789 int  cm_BPlusDirDeleteEntry(cm_dirOp_t * op, char *entry)
1790 {
1791     long rc = 0;
1792     keyT key = {entry};
1793     Nptr leafNode = NONODE;
1794     LARGE_INTEGER start, end;
1795
1796     if (op->scp->dirBplus == NULL || 
1797         op->dataVersion != op->scp->dirDataVersion) {
1798         rc = EINVAL;
1799         goto done;
1800     }
1801
1802     lock_AssertWrite(&op->scp->dirlock);
1803
1804     QueryPerformanceCounter(&start);
1805
1806     bplus_remove_entry++;
1807
1808     if (op->scp->dirBplus) {
1809         if (!cm_Is8Dot3(entry)) {
1810             cm_dirFid_t dfid;
1811             cm_fid_t fid;
1812             char shortName[13];
1813
1814             leafNode = bplus_Lookup(op->scp->dirBplus, key);
1815             if (leafNode != NONODE) {
1816                 int         slot;
1817                 Nptr        firstDataNode, dataNode, nextDataNode;
1818                 int         exact = 0;
1819                 int         count = 0;
1820
1821                 /* Found a leaf that matches the key via a case-insensitive
1822                  * match.  There may be one or more data nodes that match.
1823                  * If we have an exact match, return that.
1824                  * If we have an ambiguous match, return an error.
1825                  * If we have only one inexact match, return that.
1826                  */
1827                 slot = getSlot(op->scp->dirBplus, leafNode);
1828                 if (slot <= BTERROR) {
1829                     op->scp->dirDataVersion = 0;
1830                     rc = EINVAL;
1831                     goto done;
1832                 }
1833                 firstDataNode = getnode(leafNode, slot);
1834
1835                 for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1836                     count++;
1837                     if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1838                         exact = 1;
1839                         break;
1840                     }
1841                     nextDataNode = getdatanext(dataNode);
1842                 }
1843
1844                 if (exact) {
1845                     fid = getdatavalue(dataNode).fid;
1846                     rc = 0;
1847                 } else if (count == 1) {
1848                     fid = getdatavalue(firstDataNode).fid;
1849                     rc = CM_ERROR_INEXACT_MATCH;
1850                 } else {
1851                     rc = CM_ERROR_AMBIGUOUS_FILENAME;
1852                 } 
1853             }
1854
1855
1856             if (rc != CM_ERROR_AMBIGUOUS_FILENAME) {
1857                 dfid.vnode = htonl(fid.vnode);
1858                 dfid.unique = htonl(fid.unique);
1859                 cm_Gen8Dot3NameInt(entry, &dfid, shortName, NULL);
1860
1861                 /* delete first the long name and then the short name */
1862                 delete(op->scp->dirBplus, key);
1863                 key.name = shortName;
1864                 delete(op->scp->dirBplus, key);
1865             }
1866         } else {
1867             char * longname = NULL;
1868             /* We need to lookup the 8dot3 name to determine what the 
1869              * matching long name is
1870              */
1871             leafNode = bplus_Lookup(op->scp->dirBplus, key);
1872             if (leafNode != NONODE) {
1873                 int         slot;
1874                 Nptr        firstDataNode, dataNode, nextDataNode;
1875                 int         exact = 0;
1876                 int         count = 0;
1877
1878                 /* Found a leaf that matches the key via a case-insensitive
1879                  * match.  There may be one or more data nodes that match.
1880                  * If we have an exact match, return that.
1881                  * If we have an ambiguous match, return an error.
1882                  * If we have only one inexact match, return that.
1883                  */
1884                 slot = getSlot(op->scp->dirBplus, leafNode);
1885                 if (slot <= BTERROR) {
1886                     op->scp->dirDataVersion = 0;
1887                     rc = EINVAL;
1888                     goto done;
1889
1890                 }
1891                 firstDataNode = getnode(leafNode, slot);
1892
1893                 for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1894                     count++;
1895                     if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1896                         exact = 1;
1897                         break;
1898                     }
1899                     nextDataNode = getdatanext(dataNode);
1900                 }
1901
1902                 if (exact) {
1903                     longname = getdatavalue(dataNode).longname;
1904                     rc = 0;
1905                 } else if (count == 1) {
1906                     longname = getdatavalue(firstDataNode).longname;
1907                     rc = CM_ERROR_INEXACT_MATCH;
1908                 } else {
1909                     rc = CM_ERROR_AMBIGUOUS_FILENAME;
1910                 } 
1911             }
1912
1913             if (rc != CM_ERROR_AMBIGUOUS_FILENAME) {
1914                 if (longname) {
1915                     key.name = longname;
1916                     delete(op->scp->dirBplus, key);
1917                     key.name = entry;
1918                 }
1919                 delete(op->scp->dirBplus, key);
1920             }
1921         }
1922     }
1923     
1924     QueryPerformanceCounter(&end);
1925
1926     bplus_remove_time += (end.QuadPart - start.QuadPart);
1927
1928   done:
1929     return rc;
1930       
1931 }
1932
1933 static 
1934 int cm_BPlusDirFoo(struct cm_scache *scp, struct cm_dirEntry *dep,
1935                    void *dummy, osi_hyper_t *entryOffsetp)
1936 {
1937     keyT   key = {dep->name};
1938     dataT  data;
1939     char   shortName[13];
1940     long   normalized_len;
1941     char  *normalized_name=NULL;
1942     cm_SetFid(&data.fid, scp->fid.cell, scp->fid.volume, ntohl(dep->fid.vnode), ntohl(dep->fid.unique));
1943     data.longname = NULL;
1944     data.origname = NULL;
1945
1946     normalized_len = cm_NormalizeUtf8String(dep->name, -1, NULL, 0);
1947     if (normalized_len)
1948         normalized_name = malloc(normalized_len);
1949     if (normalized_name) {
1950         cm_NormalizeUtf8String(dep->name, -1, normalized_name, normalized_len);
1951         key.name = normalized_name;
1952         if (strcmp(normalized_name, dep->name))
1953             data.origname = strdup(dep->name);
1954     } else {
1955         key.name = dep->name;
1956     }
1957
1958     /* the Write lock is held in cm_BPlusDirBuildTree() */
1959     insert(scp->dirBplus, key, data);
1960     if (!cm_Is8Dot3(dep->name)) {
1961         cm_dirFid_t dfid;
1962         dfid.vnode = dep->fid.vnode;
1963         dfid.unique = dep->fid.unique;
1964
1965         cm_Gen8Dot3NameInt(dep->name, &dfid, shortName, NULL);
1966
1967         data.longname = strdup(key.name);
1968         data.origname = NULL;
1969         key.name = shortName;
1970         insert(scp->dirBplus, key, data);
1971     }
1972
1973     if (normalized_name)
1974         free(normalized_name);
1975
1976 #ifdef BTREE_DEBUG
1977     findAllBtreeValues(scp->dirBplus);
1978 #endif
1979     return 0;
1980 }
1981
1982
1983 /*
1984  *   scp->dirlock must be writeLocked before call
1985  *
1986  *   scp->mutex must not be held
1987  */
1988 long cm_BPlusDirBuildTree(cm_scache_t *scp, cm_user_t *userp, cm_req_t* reqp)
1989 {
1990     long rc = 0;
1991     osi_hyper_t thyper;
1992     LARGE_INTEGER start, end;
1993
1994     osi_assertx(scp->dirBplus == NULL, "cm_BPlusDirBuildTree called on non-empty tree");
1995
1996     lock_AssertWrite(&scp->dirlock);
1997
1998     QueryPerformanceCounter(&start);
1999     bplus_build_tree++;
2000
2001     if (scp->dirBplus == NULL) {
2002         scp->dirBplus = initBtree(64, MAX_FANOUT, compareKeys);
2003     }
2004     if (scp->dirBplus == NULL) {
2005         rc = ENOMEM;
2006     } else {
2007         thyper.LowPart = 0;
2008         thyper.HighPart = 0;
2009         rc = cm_ApplyDir(scp, cm_BPlusDirFoo, NULL, &thyper, userp, reqp, NULL);
2010     }
2011
2012     QueryPerformanceCounter(&end);
2013
2014     bplus_build_time += (end.QuadPart - start.QuadPart);
2015
2016 #if 0
2017     cm_BPlusDirEnumTest(scp, 1);
2018 #endif
2019     return rc;
2020 }
2021
2022 int cm_MemDumpBPlusStats(FILE *outputFile, char *cookie, int lock)
2023 {
2024     int zilch;
2025     char output[128];
2026
2027     sprintf(output, "%s - B+ Lookup    Hits: %-8d\r\n", cookie, bplus_lookup_hits);
2028     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2029     sprintf(output, "%s -      Inexact Hits: %-8d\r\n", cookie, bplus_lookup_hits_inexact);
2030     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2031     sprintf(output, "%s -    Ambiguous Hits: %-8d\r\n", cookie, bplus_lookup_ambiguous);
2032     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2033     sprintf(output, "%s -            Misses: %-8d\r\n", cookie, bplus_lookup_misses);
2034     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2035     sprintf(output, "%s -            Create: %-8d\r\n", cookie, bplus_create_entry);
2036     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2037     sprintf(output, "%s -            Remove: %-8d\r\n", cookie, bplus_remove_entry);
2038     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2039     sprintf(output, "%s -        Build Tree: %-8d\r\n", cookie, bplus_build_tree);
2040     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2041     sprintf(output, "%s -         Free Tree: %-8d\r\n", cookie, bplus_free_tree);
2042     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2043     sprintf(output, "%s -          DV Error: %-8d\r\n", cookie, bplus_dv_error);
2044     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2045
2046     sprintf(output, "%s - B+ Time    Lookup: %-16I64d\r\n", cookie, bplus_lookup_time);
2047     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2048     sprintf(output, "%s -            Create: %-16I64d\r\n", cookie, bplus_create_time);
2049     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2050     sprintf(output, "%s -            Remove: %-16I64d\r\n", cookie, bplus_remove_time);
2051     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2052     sprintf(output, "%s -             Build: %-16I64d\r\n", cookie, bplus_build_time);
2053     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2054     sprintf(output, "%s -              Free: %-16I64d\r\n", cookie, bplus_free_time);
2055     WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2056
2057     return(0);
2058 }
2059
2060 void cm_BPlusDumpStats(void)
2061 {
2062     afsi_log("B+ Lookup    Hits: %-8d", bplus_lookup_hits);
2063     afsi_log("     Inexact Hits: %-8d", bplus_lookup_hits_inexact);
2064     afsi_log("   Ambiguous Hits: %-8d", bplus_lookup_ambiguous);
2065     afsi_log("           Misses: %-8d", bplus_lookup_misses);
2066     afsi_log("           Create: %-8d", bplus_create_entry);
2067     afsi_log("           Remove: %-8d", bplus_remove_entry);
2068     afsi_log("       Build Tree: %-8d", bplus_build_tree);
2069     afsi_log("        Free Tree: %-8d", bplus_free_tree);
2070     afsi_log("         DV Error: %-8d", bplus_dv_error);
2071
2072     afsi_log("B+ Time    Lookup: %-16I64d", bplus_lookup_time);
2073     afsi_log("           Create: %-16I64d", bplus_create_time);
2074     afsi_log("           Remove: %-16I64d", bplus_remove_time);
2075     afsi_log("            Build: %-16I64d", bplus_build_time);
2076     afsi_log("             Free: %-16I64d", bplus_free_time);
2077 }
2078
2079 static cm_direnum_t * 
2080 cm_BPlusEnumAlloc(afs_uint32 entries)
2081 {
2082     cm_direnum_t * enump;
2083     size_t         size;
2084
2085     if (entries == 0)
2086         return NULL;
2087
2088     size = sizeof(cm_direnum_t)+(entries-1)*sizeof(cm_direnum_entry_t);
2089     enump = (cm_direnum_t *)malloc(size);
2090     memset(enump, 0, size);
2091     enump->count = entries;
2092     return enump;
2093 }
2094
2095 long 
2096 cm_BPlusDirEnumerate(cm_scache_t *scp, afs_uint32 locked, 
2097                      char * maskp, cm_direnum_t **enumpp)
2098 {
2099     afs_uint32 count = 0, slot, numentries;
2100     Nptr leafNode = NONODE, nextLeafNode;
2101     Nptr firstDataNode, dataNode, nextDataNode;
2102     cm_direnum_t * enump;
2103     long rc = 0;
2104     char buffer[512];
2105
2106     osi_Log0(afsd_logp, "cm_BPlusDirEnumerate start");
2107
2108     /* Read lock the bplus tree so the data can't change */
2109     if (!locked)
2110         lock_ObtainRead(&scp->dirlock);
2111
2112     if (scp->dirBplus == NULL) {
2113         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate No BPlus Tree");
2114         goto done;
2115     }
2116
2117     /* Compute the number of entries */
2118     for (count = 0, leafNode = getleaf(scp->dirBplus); leafNode; leafNode = nextLeafNode) {
2119
2120         for ( slot = 1, numentries = numentries(leafNode); slot <= numentries; slot++) {
2121             firstDataNode = getnode(leafNode, slot);
2122
2123             for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
2124                 if (maskp == NULL) {
2125                     /* name is in getdatakey(dataNode) */
2126                     if (getdatavalue(dataNode).longname != NULL ||
2127                         cm_Is8Dot3(getdatakey(dataNode).name))
2128                         count++;
2129                 } else {
2130                     if (cm_Is8Dot3(getdatakey(dataNode).name) && 
2131                         smb_V3MatchMask(getdatakey(dataNode).name, maskp, CM_FLAG_CASEFOLD) ||
2132                         getdatavalue(dataNode).longname == NULL &&
2133                         smb_V3MatchMask(getdatavalue(dataNode).longname, maskp, CM_FLAG_CASEFOLD))
2134                         count++;
2135                 }
2136                 nextDataNode = getdatanext(dataNode);
2137             }
2138         }
2139
2140         nextLeafNode = getnextnode(leafNode);
2141     }   
2142
2143     sprintf(buffer, "BPlusTreeEnumerate count = %d", count);
2144     osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, buffer));
2145
2146     /* Allocate the enumeration object */
2147     enump = cm_BPlusEnumAlloc(count);
2148     if (enump == NULL) {
2149         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate Alloc failed");
2150         rc = ENOMEM;
2151         goto done;
2152     }
2153         
2154     /* Copy the name and fid for each longname entry into the enumeration */
2155     for (count = 0, leafNode = getleaf(scp->dirBplus); leafNode; leafNode = nextLeafNode) {
2156
2157         for ( slot = 1, numentries = numentries(leafNode); slot <= numentries; slot++) {
2158             firstDataNode = getnode(leafNode, slot);
2159
2160             for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
2161                 char * name;
2162                 int hasShortName;
2163                 int includeIt = 0;
2164
2165                 if (maskp == NULL) {
2166                     if (getdatavalue(dataNode).longname != NULL ||
2167                          cm_Is8Dot3(getdatakey(dataNode).name)) 
2168                     {
2169                         includeIt = 1;
2170                     }
2171                 } else {
2172                     if (cm_Is8Dot3(getdatakey(dataNode).name) && 
2173                         smb_V3MatchMask(getdatakey(dataNode).name, maskp, CM_FLAG_CASEFOLD) ||
2174                         getdatavalue(dataNode).longname == NULL &&
2175                          smb_V3MatchMask(getdatavalue(dataNode).longname, maskp, CM_FLAG_CASEFOLD)) 
2176                     {
2177                         includeIt = 1;
2178                     }
2179                 }
2180
2181                 if (includeIt) {
2182                     if (getdatavalue(dataNode).longname) {
2183                         name = strdup(getdatavalue(dataNode).longname);
2184                         hasShortName = 1;
2185                     } else {
2186                         name = strdup(getdatakey(dataNode).name);
2187                         hasShortName = 0;
2188                     }
2189
2190                     if (name == NULL) {
2191                         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate strdup failed");
2192                         rc = ENOMEM;
2193                         goto done;
2194                     }
2195                     enump->entry[count].name = name;
2196                     enump->entry[count].fid  = getdatavalue(dataNode).fid;
2197                     if (hasShortName)
2198                         strncpy(enump->entry[count].shortName, getdatakey(dataNode).name, 
2199                                 sizeof(enump->entry[count].shortName));
2200                     else
2201                         enump->entry[count].shortName[0] = '\0';
2202                     count++;
2203                 }
2204                 nextDataNode = getdatanext(dataNode);
2205             }
2206         }
2207
2208         nextLeafNode = getnextnode(leafNode);
2209     }   
2210
2211   done:
2212     if (!locked)
2213         lock_ReleaseRead(&scp->dirlock);
2214
2215     /* if we failed, cleanup any mess */
2216     if (rc != 0) {
2217         osi_Log0(afsd_logp, "cm_BPlusDirEnumerate rc != 0");
2218         if (enump) {
2219             for ( count = 0; count < enump->count && enump->entry[count].name; count++ ) {
2220                 free(enump->entry[count].name);
2221             }
2222             free(enump);
2223             enump = NULL;
2224         }
2225     }
2226
2227     osi_Log0(afsd_logp, "cm_BPlusDirEnumerate end");
2228     *enumpp = enump;
2229     return rc;
2230 }
2231
2232 long 
2233 cm_BPlusDirNextEnumEntry(cm_direnum_t *enump, cm_direnum_entry_t **entrypp)
2234 {       
2235     if (enump == NULL || entrypp == NULL || enump->next > enump->count) {
2236         if (entrypp)
2237             *entrypp = NULL;
2238         osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry invalid input");
2239         return CM_ERROR_INVAL;                        \
2240     }
2241
2242     *entrypp = &enump->entry[enump->next++];
2243     if ( enump->next == enump->count ) {
2244         osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry STOPNOW");
2245         return CM_ERROR_STOPNOW;
2246     }
2247     else {
2248         osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry SUCCESS");
2249         return 0;
2250     }
2251 }
2252
2253 long 
2254 cm_BPlusDirFreeEnumeration(cm_direnum_t *enump)
2255 {
2256     afs_uint32 count;
2257
2258     osi_Log0(afsd_logp, "cm_BPlusDirFreeEnumeration");
2259
2260     if (enump) {
2261         for ( count = 0; count < enump->count && enump->entry[count].name; count++ ) {
2262             free(enump->entry[count].name);
2263         }
2264         free(enump);
2265     }
2266     return 0;
2267 }
2268
2269 long
2270 cm_BPlusDirEnumTest(cm_scache_t * dscp, afs_uint32 locked)
2271 {
2272     cm_direnum_t *       enump = NULL;
2273     cm_direnum_entry_t * entryp;
2274     long                 code;
2275
2276     osi_Log0(afsd_logp, "cm_BPlusDirEnumTest start");
2277
2278     for (code = cm_BPlusDirEnumerate(dscp, locked, NULL, &enump); code == 0; ) {
2279         code = cm_BPlusDirNextEnumEntry(enump, &entryp);
2280         if (code == 0 || code == CM_ERROR_STOPNOW) {
2281             char buffer[1024];
2282             cm_scache_t *scp;
2283             char * type = "ScpNotFound";
2284             afs_uint64 dv = -1;
2285
2286             scp = cm_FindSCache(&entryp->fid);
2287             if (scp) {
2288                 switch (scp->fileType) {
2289                 case CM_SCACHETYPE_FILE :
2290                     type = "File";
2291                     break;
2292                 case CM_SCACHETYPE_DIRECTORY    :
2293                     type = "Directory";
2294                     break;
2295                 case CM_SCACHETYPE_SYMLINK      :
2296                     type = "Symlink";
2297                     break;
2298                 case CM_SCACHETYPE_MOUNTPOINT:
2299                     type = "MountPoint";
2300                     break;
2301                 case CM_SCACHETYPE_DFSLINK   :
2302                     type = "Dfs";
2303                     break;
2304                 case CM_SCACHETYPE_INVALID   :
2305                     type = "Invalid";
2306                     break;
2307                 default:
2308                     type = "Unknown";
2309                     break;
2310                 }
2311
2312                 dv = scp->dataVersion;
2313                 cm_ReleaseSCache(scp);
2314             }
2315
2316             sprintf(buffer, "'%s' Fid = (%d,%d,%d,%d) Short = '%s' Type %s DV %I64d",
2317                     entryp->name,
2318                     entryp->fid.cell, entryp->fid.volume, entryp->fid.vnode, entryp->fid.unique,
2319                     entryp->shortName,
2320                     type, 
2321                     dv);
2322
2323             osi_Log0(afsd_logp, osi_LogSaveString(afsd_logp, buffer));
2324         }
2325     }
2326
2327     if (enump)
2328         cm_BPlusDirFreeEnumeration(enump);
2329
2330     osi_Log0(afsd_logp, "cm_BPlusDirEnumTest end");
2331
2332     return 0;
2333 }
2334 #endif /* USE_BPLUS */