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