2 * Copyright 2007-2008 Secure Endpoints Inc.
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
10 * Thanks to Jan Jannink for B+ tree algorithms.
23 /******************* statistics globals *********************************/
24 afs_uint32 bplus_lookup_hits = 0;
25 afs_uint32 bplus_lookup_hits_inexact = 0;
26 afs_uint32 bplus_lookup_misses = 0;
27 afs_uint32 bplus_lookup_ambiguous = 0;
28 afs_uint32 bplus_create_entry = 0;
29 afs_uint32 bplus_remove_entry = 0;
30 afs_uint32 bplus_build_tree = 0;
31 afs_uint32 bplus_free_tree = 0;
32 afs_uint32 bplus_dv_error = 0;
34 afs_uint64 bplus_lookup_time = 0;
35 afs_uint64 bplus_create_time = 0;
36 afs_uint64 bplus_remove_time = 0;
37 afs_uint64 bplus_build_time = 0;
38 afs_uint64 bplus_free_time = 0;
40 /*********************** private functions *************************/
41 static void initFreeNodePool(Tree *B, int quantity);
42 static Nptr getFreeNode(Tree *B);
43 static void putFreeNode(Tree *B, Nptr self);
44 static void cleanupNodePool(Tree *B);
46 static Nptr descendToLeaf(Tree *B, Nptr curr);
47 int getSlot(Tree *B, Nptr curr);
48 static int findKey(Tree *B, Nptr curr, int lo, int hi);
49 static int bestMatch(Tree *B, Nptr curr, int slot);
51 static Nptr getDataNode(Tree *B, keyT key, dataT data);
52 static Nptr descendSplit(Tree *B, Nptr curr);
53 static void insertEntry(Tree *B, Nptr node, int slot, Nptr sibling, Nptr downPtr);
54 static void placeEntry(Tree *B, Nptr node, int slot, Nptr downPtr);
55 static Nptr split(Tree *B, Nptr node);
56 static void makeNewRoot(Tree *B, Nptr oldRoot, Nptr newNode);
58 static Nptr descendBalance(Tree *B, Nptr curr, Nptr left, Nptr right, Nptr lAnc, Nptr rAnc, Nptr parent);
59 static void collapseRoot(Tree *B, Nptr oldRoot, Nptr newRoot);
60 static void removeEntry(Tree *B, Nptr curr, int slot);
61 static Nptr merge(Tree *B, Nptr left, Nptr right, Nptr anchor);
62 static Nptr shift(Tree *B, Nptr left, Nptr right, Nptr anchor);
64 static void _clrentry(Nptr node, int entry);
65 static void _pushentry(Nptr node, int entry, int offset);
66 static void _pullentry(Nptr node, int entry, int offset);
67 static void _xferentry(Nptr srcNode, int srcEntry, Nptr destNode, int destEntry);
68 static void _setentry(Nptr node, int entry, keyT key, Nptr downNode);
70 /* access key and data values for B+tree methods */
71 /* pass values to getSlot(), descend...() */
72 static keyT getfunkey(Tree *B);
73 static dataT getfundata(Tree *B);
74 static void setfunkey(Tree *B, keyT v);
75 static void setfundata(Tree *B, dataT v);
79 static int _isRoot(Tree *B, Nptr n)
81 int flagset = ((n->flags & isROOT) == isROOT);
86 if (flagset && n != getroot(B))
92 static int _isFew(Tree *B, Nptr n)
94 int flagset = ((n->flags & FEWEST) == FEWEST);
95 int fanout = getminfanout(B, n);
96 int entries = numentries(n);
97 int mincnt = entries <= fanout;
102 if (flagset && !mincnt || !flagset && mincnt)
108 static int _isFull(Tree *B, Nptr n)
110 int flagset = ((n->flags & isFULL) == isFULL);
111 int maxcnt = numentries(n) == getfanout(B);
116 if (flagset && !maxcnt || !flagset && maxcnt)
121 #endif /* DEBUG_BTREE */
123 /***********************************************************************\
124 | B+tree Initialization and Cleanup Routines |
125 \***********************************************************************/
126 static DWORD TlsKeyIndex;
127 static DWORD TlsDataIndex;
129 long cm_InitBPlusDir(void)
131 if ((TlsKeyIndex = TlsAlloc()) == TLS_OUT_OF_INDEXES)
134 if ((TlsDataIndex = TlsAlloc()) == TLS_OUT_OF_INDEXES)
140 /******************** Set up B+tree structure **********************/
141 Tree *initBtree(unsigned int poolsz, unsigned int fanout, KeyCmp keyCmp)
145 dataT data = {0,0,0,0,0,0,0};
147 if (fanout > MAX_FANOUT)
150 setbplustree(B, malloc(sizeof(Tree)));
151 memset(B, 0, sizeof(Tree));
152 setfanout(B, fanout);
153 setminfanout(B, (fanout + 1) >> 1);
154 initFreeNodePool(B, poolsz);
156 setleaf(B, getFreeNode(B)); /* set up the first leaf node */
157 setroot(B, getleaf(B)); /* the root is initially the leaf */
158 setflag(getroot(B), isLEAF);
159 setflag(getroot(B), isROOT);
160 setflag(getroot(B), FEWEST);
165 setcomparekeys(B, keyCmp);
168 StringCbPrintfA(B->message, sizeof(B->message), "INIT: B+tree of fanout %d at %10p.\n", fanout, (void *)B);
169 OutputDebugString(B->message);
175 /******************** Clean up B+tree structure ********************/
177 * dirlock must be write locked
179 void freeBtree(Tree *B)
182 StringCbPrintfA(B->message, sizeof(B->message), "FREE: B+tree at %10p.\n", (void *) B);
183 OutputDebugString(B->message);
188 memset(B, 0, sizeof(*B));
193 /* access key and data values for B+tree methods */
194 /* pass values to getSlot(), descend...() */
195 static keyT getfunkey(Tree *B) {
198 // Retrieve a data pointer for the current thread.
199 tlsKey = (keyT *) TlsGetValue(TlsKeyIndex);
200 if (tlsKey == NULL) {
201 if (GetLastError() != ERROR_SUCCESS)
202 osi_panic("TlsGetValue failed", __FILE__, __LINE__);
204 osi_panic("get before set", __FILE__, __LINE__);
210 static dataT getfundata(Tree *B) {
213 // Retrieve a data pointer for the current thread.
214 tlsData = (dataT *) TlsGetValue(TlsDataIndex);
215 if (tlsData == NULL) {
216 if (GetLastError() != ERROR_SUCCESS)
217 osi_panic("TlsGetValue failed", __FILE__, __LINE__);
219 osi_panic("get before set", __FILE__, __LINE__);
225 static void setfunkey(Tree *B, keyT theKey) {
228 tlsKey = (keyT *) TlsGetValue(TlsKeyIndex);
229 if (tlsKey == NULL) {
230 if (GetLastError() != ERROR_SUCCESS)
231 osi_panic("TlsGetValue failed", __FILE__, __LINE__);
233 tlsKey = malloc(sizeof(keyT));
235 if (!TlsSetValue(TlsKeyIndex, tlsKey))
236 osi_panic("TlsSetValue failed", __FILE__, __LINE__);
242 static void setfundata(Tree *B, dataT theData) {
245 tlsData = (dataT *) TlsGetValue(TlsDataIndex);
246 if (tlsData == NULL) {
247 if (GetLastError() != ERROR_SUCCESS)
248 osi_panic("TlsGetValue failed", __FILE__, __LINE__);
250 tlsData = malloc(sizeof(dataT));
252 if (!TlsSetValue(TlsDataIndex, tlsData))
253 osi_panic("TlsSetValue failed", __FILE__, __LINE__);
260 /***********************************************************************\
261 | Find leaf node in which data nodes can be found |
262 \***********************************************************************/
264 /********************** top level lookup **********************/
265 Nptr bplus_Lookup(Tree *B, keyT key)
270 StringCbPrintfA(B->message, sizeof(B->message), "LOOKUP: key %s.\n", key.name);
271 OutputDebugString(B->message);
274 setfunkey(B, key); /* set search key */
275 leafNode = descendToLeaf(B, getroot(B)); /* start search from root node */
283 slot = getSlot(B, leafNode);
287 dataNode = getnode(leafNode, slot);
288 data = getdatavalue(dataNode);
290 StringCbPrintfA(B->message, sizeof(B->message), "LOOKUP: %s found on page %d value (%d.%d.%d).\n",
292 getnodenumber(B, leafNode),
297 StringCbPrintfA(B->message, sizeof(B->message), "LOOKUP: not found!\n");
298 OutputDebugString(B->message);
304 /********************** `recurse' down B+tree **********************/
305 static Nptr descendToLeaf(Tree *B, Nptr curr)
312 memset(prev, 0, sizeof(prev));
314 for (depth = 0, slot = getSlot(B, curr); (slot >= 0) && isinternal(curr); depth++, slot = getSlot(B, curr)) {
317 curr = getfirstnode(curr);
319 curr = getnode(curr, slot);
320 else /* BTERROR, BTLOWER, BTUPPER */ {
329 if ((slot > 0) && !comparekeys(B)(getfunkey(B), getkey(curr, slot), 0))
330 findNode = curr; /* correct key value found */
332 findNode = NONODE; /* key value not in tree */
337 /******************** find slot for search key *********************/
338 int getSlot(Tree *B, Nptr curr)
342 entries = numentries(curr); /* need this if root is ever empty */
343 slot = !entries ? 0 : findKey(B, curr, 1, entries);
349 /******************** recursive binary search **********************/
350 static int findKey(Tree *B, Nptr curr, int lo, int hi)
352 int mid, findslot = BTERROR;
355 findslot = bestMatch(B, curr, lo); /* recursion base case */
358 if (findslot == BTERROR) {
359 StringCbPrintfA(B->message, sizeof(B->message), "FINDKEY: (lo %d hi %d) Bad key ordering on node %d (0x%p)\n",
360 lo, hi, getnodenumber(B, curr), curr);
361 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
365 mid = (lo + hi) >> 1;
366 switch (findslot = bestMatch(B, curr, mid)) {
367 case BTLOWER: /* check lower half of range */
369 findslot = findKey(B, curr, lo, mid - 1); /* never in 2-3+trees */
371 case BTUPPER: /* check upper half of range */
372 if (mid < getfanout(B))
373 findslot = findKey(B, curr, mid + 1, hi);
376 StringCbPrintfA(B->message, sizeof(B->message), "FINDKEY: (lo %d hi %d) Bad key ordering on node %d (0x%p)\n",
377 lo, hi, getnodenumber(B, curr), curr);
378 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
382 if (isleaf(curr) && findslot == 0)
384 StringCbPrintfA(B->message, sizeof(B->message), "FINDKEY: (lo %d hi %d) findslot %d is invalid for leaf nodes, bad key ordering on node %d (0x%p)\n",
385 lo, hi, findslot, getnodenumber(B, curr), curr);
386 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
392 /************ comparison of key with a target key slot *************/
393 static int bestMatch(Tree *B, Nptr curr, int slot)
395 int diff, comp=2, findslot;
397 diff = comparekeys(B)(getfunkey(B), getkey(curr, slot), 0);
400 } else if (diff < 0) { /* also check previous slot */
403 findslot = BTLOWER; /* not found in the tree */
407 else if ((comp = comparekeys(B)(getfunkey(B), getkey(curr, slot - 1), 0)) >= 0) {
409 } else if (comp < diff) {
410 findslot = BTERROR; /* inconsistent ordering of keys */
415 findslot = BTLOWER; /* key must be below in node ordering */
417 } else { /* or check following slot */
418 if (slot == numentries(curr)) {
419 if (isleaf(curr) && numentries(curr) == getfanout(B))
423 } else if ((comp = comparekeys(B)(getfunkey(B), getkey(curr, slot + 1), 0)) < 0) {
425 } else if (comp == 0) {
427 } else if (comp > diff) {
428 findslot = BTERROR; /* inconsistent ordering of keys */
433 findslot = BTUPPER; /* key must be above in node ordering */
437 if (findslot == BTERROR || isleaf(curr) && findslot == 0)
439 StringCbPrintfA(B->message, sizeof(B->message), "BESTMATCH: node %d (0x%p) slot %d diff %d comp %d findslot %d\n",
440 getnodenumber(B, curr), curr, slot, diff, comp, findslot);
441 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
447 /***********************************************************************\
448 | Insert new data into tree |
449 \***********************************************************************/
452 /********************** top level insert call **********************/
453 void insert(Tree *B, keyT key, dataT data)
458 StringCbPrintfA(B->message, sizeof(B->message), "INSERT: key %s.\n", key.name);
459 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
462 setfunkey(B, key); /* set insertion key */
463 setfundata(B, data); /* a node containing data */
464 setsplitpath(B, NONODE);
465 newNode = descendSplit(B, getroot(B)); /* insertion point search from root */
466 if (newNode != getsplitpath(B)) /* indicates the root node has split */
467 makeNewRoot(B, getroot(B), newNode);
471 /***************** recurse down and split back up ******************/
473 descendSplit(Tree *B, Nptr curr)
475 Nptr downNode = NONODE, sibling = NONODE;
483 setsplitpath(B, NONODE);
484 else if (getsplitpath(B) == NONODE)
485 setsplitpath(B, curr); /* indicates where nodes must split */
487 slot = getSlot(B, curr); /* is null only if the root is empty */
494 else if (slot == BTUPPER)
498 if (isinternal(curr)) { /* continue recursion to leaves */
500 downNode = descendSplit(B, getfirstnode(curr));
502 downNode = descendSplit(B, getnode(curr, slot));
503 } else if ((slot > 0) && !comparekeys(B)(getfunkey(B), getkey(curr, slot), 0)) {
504 if (!(gettreeflags(B) & TREE_FLAG_UNIQUE_KEYS)) {
505 downNode = getDataNode(B, getfunkey(B), getfundata(B));
506 getdatanext(downNode) = getnode(curr,slot);
507 setnode(curr, slot, downNode);
510 setsplitpath(B, NONODE);
513 downNode = getDataNode(B, getfunkey(B), getfundata(B)); /* an insertion takes place */
515 if (downNode != NONODE) { /* insert only where necessary */
516 if (getsplitpath(B) != NONODE)
517 sibling = split(B, curr); /* a sibling node is prepared */
518 insertEntry(B, curr, slot, sibling, downNode);
524 /*************** determine location of inserted key ****************/
526 insertEntry(Tree *B, Nptr currNode, int slot, Nptr sibling, Nptr downPtr)
528 int split, i, j, k, x, y;
532 StringCbPrintfA(B->message, sizeof(B->message), "INSERT: slot %d, down node %d.\n", slot, getnodenumber(B, downPtr));
533 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
536 if (sibling == NONODE) { /* no split occurred */
537 placeEntry(B, currNode, slot + 1, downPtr);
539 else { /* split entries between the two */
540 if isinternal(currNode) {
542 split = getfanout(B) - getminfanout(B, currNode);
543 } else if (isroot(currNode)) {
544 /* split the root node and turn it into just a leaf */
546 split = getminfanout(B, currNode);
549 split = getminfanout(B, currNode);
551 j = (slot != split ? 1 : 0);
552 k = (slot >= split ? 1 : 0);
555 * Move entries from the top half of the current node to
556 * to the sibling node.
557 * The number of entries to move is dependent upon where
558 * the new entry is going to be added in relationship to
559 * the split slot. (slots are 1-based). If order to produce
560 * a balanced tree, if the insertion slot is greater than
561 * the split we move one less entry as the new entry will
562 * be inserted into the sibling.
564 * If the node that is being split is an internal node (i != 0)
565 * then we move one less entry due to the extra down pointer
566 * when the split slot is not equal to the insertion slot
568 for (x = split + k + j * i, y = 1; x <= getfanout(B); x++, y++) {
569 xferentry(currNode, x, sibling, y); /* copy entries to sibling */
570 clrentry(currNode, x);
571 decentries(currNode);
575 if (getkey(sibling, numentries(sibling)).name == NULL)
579 clrflag(currNode, isFULL);
580 if (numentries(currNode) == getminfanout(B, currNode))
581 setflag(currNode, FEWEST); /* never happens in even size nodes */
584 if (numentries(sibling) > getfanout(B))
587 if (numentries(sibling) == getfanout(B))
588 setflag(sibling, isFULL); /* only ever happens in 2-3+trees */
590 if (numentries(sibling) > getminfanout(B, sibling))
591 clrflag(sibling, FEWEST);
593 if (i) { /* set first pointer of internal node */
595 setfirstnode(sibling, getnode(currNode, split + k));
596 decentries(currNode);
597 if (numentries(currNode) == getminfanout(B, currNode))
598 setflag(currNode, FEWEST);
600 clrflag(currNode, FEWEST);
603 setfirstnode(sibling, downPtr);
606 if (j) { /* insert new entry into correct spot */
608 placeEntry(B, sibling, slot - split + 1 - i, downPtr);
610 placeEntry(B, currNode, slot + 1, downPtr);
612 /* set key separating nodes */
614 key = getkey(sibling, 1);
616 Nptr leaf = getfirstnode(sibling);
617 while ( isinternal(leaf) )
618 leaf = getfirstnode(leaf);
619 key = getkey(leaf, 1);
624 placeEntry(B, sibling, 1, downPtr);
628 /************ place key into appropriate node & slot ***************/
630 placeEntry(Tree *B, Nptr node, int slot, Nptr downPtr)
640 if (numentries(node) != 0 && getkey(node, numentries(node)).name == NULL)
643 for (x = numentries(node); x >= slot && x != 0; x--) /* make room for new entry */
644 pushentry(node, x, 1);
645 setentry(node, slot, getfunkey(B), downPtr);/* place it in correct slot */
647 incentries(node); /* adjust entry counter */
649 if (getkey(node, numentries(node)).name == NULL)
653 if (numentries(node) == getfanout(B))
654 setflag(node, isFULL);
655 if (numentries(node) > getminfanout(B, node))
656 clrflag(node, FEWEST);
658 setflag(node, FEWEST);
662 /***************** split full node and set flags *******************/
664 split(Tree *B, Nptr node)
668 sibling = getFreeNode(B);
670 setflag(sibling, FEWEST); /* set up node flags */
673 setflag(sibling, isLEAF);
674 setnextnode(sibling, getnextnode(node));/* adjust leaf pointers */
675 setnextnode(node, sibling);
677 if (getsplitpath(B) == node)
678 setsplitpath(B, NONODE); /* no more splitting needed */
681 clrflag(node, isROOT);
687 /********************** build new root node ************************/
689 makeNewRoot(Tree *B, Nptr oldRoot, Nptr newNode)
691 setroot(B, getFreeNode(B));
693 setfirstnode(getroot(B), oldRoot); /* old root becomes new root's child */
694 setentry(getroot(B), 1, getfunkey(B), newNode); /* old root's sibling also */
695 incentries(getroot(B));
697 if (numentries(getroot(B)) > getfanout(B))
701 /* the oldRoot's isROOT flag was cleared in split() */
702 setflag(getroot(B), isROOT);
703 setflag(getroot(B), FEWEST);
704 clrflag(getroot(B), isLEAF);
709 /***********************************************************************\
710 | Delete data from tree |
711 \***********************************************************************/
713 /********************** top level delete call **********************\
715 | The recursive call for deletion carries 5 additional parameters
716 | which may be needed to rebalance the B+tree when removing the key.
717 | These parameters are:
718 | 1. immediate left neighbor of the current node
719 | 2. immediate right neighbor of the current node
720 | 3. the anchor of the current node and left neighbor
721 | 4. the anchor of the current node and right neighbor
722 | 5. the parent of the current node
724 | All of these parameters are simple to calculate going along the
725 | recursive path to the leaf nodes and the point of key deletion.
726 | At that time, the algorithm determines which node manipulations
727 | are most efficient, that is, cause the least rearranging of data,
728 | and minimize the need for non-local key manipulation.
730 \***********************************************************************/
731 void delete(Tree *B, keyT key)
736 StringCbPrintfA(B->message, sizeof(B->message), "DELETE: key %s.\n", key.name);
737 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
740 setfunkey(B, key); /* set deletion key */
741 setmergepath(B, NONODE);
742 newNode = descendBalance(B, getroot(B), NONODE, NONODE, NONODE, NONODE, NONODE);
743 if (isnode(newNode)) {
745 StringCbPrintfA(B->message, sizeof(B->message), "DELETE: collapsing node %d", getnodenumber(B, newNode));
746 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
748 collapseRoot(B, getroot(B), newNode); /* remove root when superfluous */
753 /********************** remove old root node ***********************/
755 collapseRoot(Tree *B, Nptr oldRoot, Nptr newRoot)
759 StringCbPrintfA(B->message, sizeof(B->message), "COLLAPSE: old %d, new %d.\n", getnodenumber(B, oldRoot), getnodenumber(B, newRoot));
760 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
761 showNode(B, "collapseRoot oldRoot", oldRoot);
762 showNode(B, "collapseRoot newRoot", newRoot);
766 setflag(newRoot, isROOT);
767 clrflag(newRoot, FEWEST);
768 putFreeNode(B, oldRoot);
769 dectreeheight(B); /* the height of the tree decreases */
773 /**************** recurse down and balance back up *****************/
775 descendBalance(Tree *B, Nptr curr, Nptr left, Nptr right, Nptr lAnc, Nptr rAnc, Nptr parent)
777 Nptr newMe=NONODE, myLeft=NONODE, myRight=NONODE, lAnchor=NONODE, rAnchor=NONODE, newNode=NONODE;
778 int slot = 0, notleft = 0, notright = 0, fewleft = 0, fewright = 0, test = 0;
781 StringCbPrintfA(B->message, sizeof(B->message), "descendBalance curr %d, left %d, right %d, lAnc %d, rAnc %d, parent %d\n",
782 curr ? getnodenumber(B, curr) : -1,
783 left ? getnodenumber(B, left) : -1,
784 right ? getnodenumber(B, right) : -1,
785 lAnc ? getnodenumber(B, lAnc) : -1,
786 rAnc ? getnodenumber(B, rAnc) : -1,
787 parent ? getnodenumber(B, parent) : -1);
788 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
792 setmergepath(B,NONODE);
793 else if (getmergepath(B) == NONODE)
794 setmergepath(B, curr); /* mark which nodes may need rebalancing */
796 slot = getSlot(B, curr);
803 else if (slot == BTUPPER)
807 if (isinternal(curr)) /* set up next recursion call's parameters */
810 newNode = getfirstnode(curr);
811 myLeft = !isnode(left) ? NONODE : getlastnode(left);
815 newNode = getnode(curr, slot);
817 myLeft = getfirstnode(curr);
819 myLeft = getnode(curr, slot - 1);
823 if (slot == numentries(curr)) {
824 myRight = !isnode(right) ? NONODE : getfirstnode(right);
828 myRight = getnode(curr, slot + 1);
831 newMe = descendBalance(B, newNode, myLeft, myRight, lAnchor, rAnchor, curr);
833 else if ((slot > 0) && !comparekeys(B)(getfunkey(B), getkey(curr, slot), 0))
839 newNode = getnode(curr, slot);
840 next = getdatanext(newNode);
843 * We only delete exact matches.
845 if (!comparekeys(B)(getfunkey(B), getdatakey(newNode), EXACT_MATCH)) {
846 /* exact match, free the first entry */
847 setnode(curr, slot, next);
849 if (next == NONODE) {
850 /* delete this key as there are no more data values */
853 /* otherwise, there are more and we leave the key in place */
854 setnode(curr, slot, next);
855 putFreeNode(B, newNode);
857 /* but do not delete the key */
859 setmergepath(B, NONODE);
861 } else if (next == NONODE) {
863 * we didn't find an exact match and there are no more
864 * choices. so we leave it alone and remove nothing.
867 setmergepath(B, NONODE);
869 /* The first data node doesn't match but there are other
870 * options. So we must determine if any of the next nodes
871 * are the one we are looking for.
876 if (!comparekeys(B)(getfunkey(B), getdatakey(next), EXACT_MATCH)) {
877 /* we found the one to delete */
878 getdatanext(prev) = getdatanext(next);
879 putFreeNode(B, next);
883 next = getdatanext(next);
886 /* do not delete the key */
888 setmergepath(B, NONODE);
893 newMe = NONODE; /* no deletion possible, key not found */
894 setmergepath(B, NONODE);
897 /***************** rebalancing tree after deletion *****************\
899 | The simplest B+tree rebalancing consists of the following rules.
901 | If a node underflows:
902 | CASE 1 check if it is the root, and collapse it if it is,
903 | CASE 2 otherwise, check if both of its neighbors are minimum
904 | sized and merge the underflowing node with one of them,
905 | CASE 3 otherwise shift surplus entries to the underflowing node.
907 | The choice of which neighbor to use is optional. However, the
908 | rebalancing rules that follow also ensure whenever possible
909 | that the merges and shifts which do occur use a neighbor whose
910 | anchor is the parent of the underflowing node.
912 | Cases 3, 4, 5 below are more an optimization than a requirement,
913 | and can be omitted, with a change of the action value in case 6,
914 | which actually corresponds to the third case described above.
916 \***********************************************************************/
918 /* begin deletion, working upwards from leaves */
920 if (newMe != NONODE) { /* this node removal doesn't consider duplicates */
922 StringCbPrintfA(B->message, sizeof(B->message), "descendBalance DELETE: slot %d, node %d.\n", slot, getnodenumber(B, curr));
923 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
926 removeEntry(B, curr, slot + (newMe != newNode)); /* removes one of two */
929 showNode(B, "descendBalance curr", curr);
933 if (getmergepath(B) == NONODE)
935 else { /* tree rebalancing rules for node merges and shifts */
936 notleft = !isnode(left);
937 notright = !isnode(right);
939 fewleft = isfew(left); /* only used when defined */
941 fewright = isfew(right);
943 /* CASE 1: prepare root node (curr) for removal */
944 if (notleft && notright) {
945 test = isleaf(curr); /* check if B+tree has become empty */
946 newNode = test ? NONODE : getfirstnode(curr);
948 /* CASE 2: the merging of two nodes is a must */
949 else if ((notleft || fewleft) && (notright || fewright)) {
950 test = (lAnc != parent);
951 newNode = test ? merge(B, curr, right, rAnc) : merge(B, left, curr, lAnc);
953 /* CASE 3: choose the better of a merge or a shift */
954 else if (!notleft && fewleft && !notright && !fewright) {
955 test = (rAnc != parent) && (curr == getmergepath(B));
956 newNode = test ? merge(B, left, curr, lAnc) : shift(B, curr, right, rAnc);
958 /* CASE 4: also choose between a merge or a shift */
959 else if (!notleft && !fewleft && !notright && fewright) {
960 test = !(lAnc == parent) && (curr == getmergepath(B));
961 newNode = test ? merge(B, curr, right, rAnc) : shift(B, left, curr, lAnc);
963 /* CASE 5: choose the more effective of two shifts */
964 else if (lAnc == rAnc) { /* => both anchors are the parent */
965 test = (numentries(left) <= numentries(right));
966 newNode = test ? shift(B, curr, right, rAnc) : shift(B, left, curr, lAnc);
968 /* CASE 6: choose the shift with more local effect */
969 else { /* if omitting cases 3,4,5 use below */
970 test = (lAnc == parent); /* test = (!notleft && !fewleft); */
971 newNode = test ? shift(B, left, curr, lAnc) : shift(B, curr, right, rAnc);
976 StringCbPrintfA(B->message, sizeof(B->message), "descendBalance returns %d\n", getnodenumber(B, newNode));
977 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
983 /**************** remove key and pointer from node *****************/
985 removeEntry(Tree *B, Nptr curr, int slot)
989 putFreeNode(B, getnode(curr, slot)); /* return deleted node to free list */
990 for (x = slot; x < numentries(curr); x++)
991 pullentry(curr, x, 1); /* adjust node with removed key */
993 clrflag(curr, isFULL); /* keep flag information up to date */
994 if (numentries(curr) > getminfanout(B, curr))
995 clrflag(curr, FEWEST);
997 setflag(curr, FEWEST);
1001 /******* merge a node pair & set emptied node up for removal *******/
1003 merge(Tree *B, Nptr left, Nptr right, Nptr anchor)
1008 StringCbPrintfA(B->message, sizeof(B->message), "MERGE: left %d, right %d.\n", getnodenumber(B, left), getnodenumber(B, right));
1009 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1010 showNode(B, "pre-merge anchor", anchor);
1011 showNode(B, "pre-merge left", left);
1012 showNode(B, "pre-merge right", right);
1015 if (isinternal(left)) {
1016 incentries(left); /* copy key separating the nodes */
1018 if (numentries(left) > getfanout(B))
1021 setfunkey(B, getkey(right, 1)); /* defined but maybe just deleted */
1022 z = getSlot(B, anchor); /* needs the just calculated key */
1025 setfunkey(B, getkey(anchor, z)); /* set slot to delete in anchor */
1026 setentry(left, numentries(left), getfunkey(B), getfirstnode(right));
1029 setnextnode(left, getnextnode(right));
1031 for (x = numentries(left) + 1, y = 1; y <= numentries(right); x++, y++) {
1034 if (numentries(left) > getfanout(B))
1037 xferentry(right, y, left, x); /* transfer entries to left node */
1039 clearentries(right);
1041 if (numentries(left) > getminfanout(B, left))
1042 clrflag(left, FEWEST);
1043 if (numentries(left) == getfanout(B))
1044 setflag(left, isFULL); /* never happens in even size nodes */
1046 if (getmergepath(B) == left || getmergepath(B) == right)
1047 setmergepath(B, NONODE); /* indicate rebalancing is complete */
1050 showNode(B, "post-merge anchor", anchor);
1051 showNode(B, "post-merge left", left);
1052 showNode(B, "post-merge right", right);
1058 /****** shift entries in a node pair & adjust anchor key value *****/
1060 shift(Tree *B, Nptr left, Nptr right, Nptr anchor)
1065 StringCbPrintfA(B->message, sizeof(B->message), "SHIFT: left %d, right %d, anchor %d.\n",
1066 getnodenumber(B, left),
1067 getnodenumber(B, right),
1068 getnodenumber(B, anchor));
1069 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1070 showNode(B, "pre-shift anchor", anchor);
1071 showNode(B, "pre-shift left", left);
1072 showNode(B, "pre-shift right", right);
1075 i = isinternal(left);
1077 if (numentries(left) < numentries(right)) { /* shift entries to left */
1078 y = (numentries(right) - numentries(left)) >> 1;
1079 x = numentries(left) + y;
1080 setfunkey(B, getkey(right, y + 1 - i)); /* set new anchor key value */
1081 z = getSlot(B, anchor); /* find slot in anchor node */
1085 if (z == 0 && !isroot(anchor))
1088 if (i) { /* move out old anchor value */
1089 decentries(right); /* adjust for shifting anchor */
1092 if (numentries(left) > getfanout(B))
1095 setentry(left, numentries(left), getkey(anchor, z), getfirstnode(right));
1096 setfirstnode(right, getnode(right, y + 1 - i));
1098 clrflag(right, isFULL);
1099 setkey(anchor, z, getfunkey(B)); /* set new anchor value */
1100 for (z = y, y -= i; y > 0; y--, x--) {
1101 decentries(right); /* adjust entry count */
1104 if (numentries(left) > getfanout(B))
1107 xferentry(right, y, left, x); /* transfer entries over */
1110 for (x = 1; x <= numentries(right); x++) /* adjust reduced node */
1111 pullentry(right, x, z);
1113 else if (numentries(left) > numentries(right)) { /* shift entries to right */
1114 y = (numentries(left) - numentries(right)) >> 1;
1115 x = numentries(left) - y + 1;
1117 for (z = numentries(right); z > 0; z--) /* adjust increased node */
1118 pushentry(right, z, y);
1120 setfunkey(B, getkey(left, x)); /* set new anchor key value */
1121 z = getSlot(B, anchor);
1130 if (numentries(right) > getfanout(B))
1133 setentry(right, y, getkey(anchor, z), getfirstnode(right));
1134 setfirstnode(right, getnode(left, x));
1136 clrflag(left, isFULL);
1137 setkey(anchor, z, getfunkey(B));
1138 for (x = numentries(left) + i, y -= i; y > 0; y--, x--) {
1142 if (numentries(right) > getfanout(B))
1145 xferentry(left, x, right, y); /* transfer entries over */
1153 #endif /* DEBUG_BTREE */
1155 if (numentries(left) > getminfanout(B, left)) /* adjust node flags */
1156 clrflag(left, FEWEST); /* never happens in 2-3+trees */
1158 setflag(left, FEWEST);
1159 if (numentries(right) > getminfanout(B, right))
1160 clrflag(right, FEWEST); /* never happens in 2-3+trees */
1162 setflag(right, FEWEST);
1163 setmergepath(B, NONODE);
1166 StringCbPrintfA(B->message, sizeof(B->message), "SHIFT: left %d, right %d.\n", getnodenumber(B, left), getnodenumber(B, right));
1167 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1168 showNode(B, "post-shift anchor", anchor);
1169 showNode(B, "post-shift left", left);
1170 showNode(B, "post-shift right", right);
1178 _clrentry(Nptr node, int entry)
1180 if (getkey(node,entry).name != NULL) {
1181 free(getkey(node,entry).name);
1182 getkey(node,entry).name = NULL;
1184 getnode(node,entry) = NONODE;
1188 _pushentry(Nptr node, int entry, int offset)
1190 if (getkey(node,entry + offset).name != NULL)
1191 free(getkey(node,entry + offset).name);
1196 getkey(node,entry + offset).name = cm_NormStrDup(getkey(node,entry).name);
1198 if ( getnode(node, entry) == NONODE )
1201 getnode(node,entry + offset) = getnode(node,entry);
1205 _pullentry(Nptr node, int entry, int offset)
1207 if (getkey(node,entry).name != NULL)
1208 free(getkey(node,entry).name);
1209 getkey(node,entry).name = cm_NormStrDup(getkey(node,entry + offset).name);
1211 if ( getnode(node, entry + offset) == NONODE )
1214 getnode(node,entry) = getnode(node,entry + offset);
1218 _xferentry(Nptr srcNode, int srcEntry, Nptr destNode, int destEntry)
1220 if (getkey(destNode,destEntry).name != NULL)
1221 free(getkey(destNode,destEntry).name);
1222 getkey(destNode,destEntry).name = cm_NormStrDup(getkey(srcNode,srcEntry).name);
1224 if ( getnode(srcNode, srcEntry) == NONODE )
1227 getnode(destNode,destEntry) = getnode(srcNode,srcEntry);
1231 _setentry(Nptr node, int entry, keyT key, Nptr downNode)
1233 if (getkey(node,entry).name != NULL)
1234 free(getkey(node,entry).name);
1235 getkey(node,entry).name = cm_NormStrDup(key.name);
1237 if ( downNode == NONODE )
1240 getnode(node,entry) = downNode;
1244 /***********************************************************************\
1245 | Empty Node Utilities |
1246 \***********************************************************************/
1248 /********************* Set up initial pool of free nodes ***********/
1250 initFreeNodePool(Tree *B, int quantity)
1255 setfirstallnode(B, NONODE);
1256 setfirstfreenode(B, NONODE);
1258 for (i = 0, p = NONODE; i < quantity; i++) {
1259 n = malloc(sizeof(*n));
1260 memset(n, 0, sizeof(*n));
1261 setnodenumber(B,n,i);
1264 setnextnode(p, n); /* insert node into free node list */
1267 setfirstfreenode(B, n);
1268 setfirstallnode(B, n);
1272 setnextnode(p, NONODE); /* indicates end of free node list */
1273 setallnode(p, NONODE); /* indicates end of all node list */
1275 setpoolsize(B, quantity);
1279 /******************* Cleanup Free Node Pool **************************/
1282 cleanupNodePool(Tree *B)
1287 for ( i=0, node = getfirstallnode(B); node != NONODE && i<getpoolsize(B); node = next, i++ ) {
1289 if ( getdatakey(node).name ) {
1290 free(getdatakey(node).name);
1291 getdatakey(node).name = NULL;
1293 if ( getdatavalue(node).cname ) {
1294 free(getdatavalue(node).cname);
1295 getdatavalue(node).cname = NULL;
1297 if ( getdatavalue(node).fsname ) {
1298 free(getdatavalue(node).fsname);
1299 getdatavalue(node).fsname = NULL;
1301 } else { /* data node */
1302 for ( j=1; j<=getfanout(B); j++ ) {
1303 if (getkey(node, j).name)
1304 free(getkey(node, j).name);
1307 next = getallnode(node);
1312 /************** take a free B+tree node from the pool **************/
1314 getFreeNode(Tree *B)
1316 Nptr newNode = getfirstfreenode(B);
1318 if (newNode != NONODE) {
1319 setfirstfreenode(B, getnextnode(newNode)); /* adjust free node list */
1320 setnextnode(newNode, NONODE); /* remove node from list */
1323 newNode = malloc(sizeof(*newNode));
1324 memset(newNode, 0, sizeof(*newNode));
1326 setallnode(newNode, getfirstallnode(B));
1327 setfirstallnode(B, newNode);
1328 setnodenumber(B, newNode, getpoolsize(B));
1329 setpoolsize(B, getpoolsize(B) + 1);
1332 clearflags(newNode); /* Sets MAGIC */
1337 /************* return a deleted B+tree node to the pool ************/
1339 putFreeNode(Tree *B, Nptr node)
1347 if ( getdatakey(node).name )
1348 free(getdatakey(node).name);
1349 if ( getdatavalue(node).cname )
1350 free(getdatavalue(node).cname);
1351 if ( getdatavalue(node).fsname )
1352 free(getdatavalue(node).fsname);
1353 } else { /* data node */
1354 for ( i=1; i<=getfanout(B); i++ ) {
1355 if (getkey(node, i).name)
1356 free(getkey(node, i).name);
1360 /* free nodes do not have MAGIC set */
1361 memset(&nAdr(node), 0, sizeof(nAdr(node)));
1362 setnextnode(node, getfirstfreenode(B)); /* add node to list */
1363 setfirstfreenode(B, node); /* set it to be list head */
1367 /******* fill a free data node with a key and associated data ******/
1369 getDataNode(Tree *B, keyT key, dataT data)
1371 Nptr newNode = getFreeNode(B);
1373 setflag(newNode, isDATA);
1374 getdatakey(newNode).name = cm_NormStrDup(key.name);
1375 getdatavalue(newNode) = data;
1376 getdatanext(newNode) = NONODE;
1383 /***********************************************************************\
1384 | B+tree Printing Utilities |
1385 \***********************************************************************/
1387 /*********************** B+tree node printer ***********************/
1388 void showNode(Tree *B, const char * where, Nptr n)
1392 StringCbPrintfA(B->message, sizeof(B->message), "- -- -- -- -- -- -- -- -- -- -- -- -\n");
1393 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1394 StringCbPrintfA(B->message, sizeof(B->message), "| %-20s |\n", where);
1395 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1396 StringCbPrintfA(B->message, sizeof(B->message), "| node %6d ", getnodenumber(B, n));
1397 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1398 StringCbPrintfA(B->message, sizeof(B->message), " magic %4x |\n", getmagic(n));
1399 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1400 StringCbPrintfA(B->message, sizeof(B->message), "- -- -- -- -- -- -- -- -- -- -- -- -\n");
1401 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1402 StringCbPrintfA(B->message, sizeof(B->message), "| flags %1d%1d%1d%1d ", isfew(n), isfull(n), isroot(n), isleaf(n));
1403 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1404 StringCbPrintfA(B->message, sizeof(B->message), "| keys = %5d ", numentries(n));
1405 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1406 StringCbPrintfA(B->message, sizeof(B->message), "| node = %6d |\n", getnodenumber(B, getfirstnode(n)));
1407 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1408 for (x = 1; x <= numentries(n); x++) {
1409 StringCbPrintfA(B->message, sizeof(B->message), "| entry %6d ", x);
1410 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1411 StringCbPrintfA(B->message, sizeof(B->message), "| key = %6s ", getkey(n, x).name);
1412 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1413 StringCbPrintfA(B->message, sizeof(B->message), "| node = %6d |\n", getnodenumber(B, getnode(n, x)));
1414 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1416 StringCbPrintfA(B->message, sizeof(B->message), "- -- -- -- -- -- -- -- -- -- -- -- -\n");
1417 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1420 /****************** B+tree class variable printer ******************/
1421 void showBtree(Tree *B)
1423 StringCbPrintfA(B->message, sizeof(B->message), "- -- -- -- -- -- -\n");
1424 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1425 StringCbPrintfA(B->message, sizeof(B->message), "| B+tree %10p |\n", (void *) B);
1426 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1427 StringCbPrintfA(B->message, sizeof(B->message), "- -- -- -- -- -- -\n");
1428 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1429 StringCbPrintfA(B->message, sizeof(B->message), "| root %6d |\n", getnodenumber(B, getroot(B)));
1430 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1431 StringCbPrintfA(B->message, sizeof(B->message), "| leaf %6d |\n", getnodenumber(B, getleaf(B)));
1432 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1433 StringCbPrintfA(B->message, sizeof(B->message), "| fanout %3d |\n", getfanout(B) + 1);
1434 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1435 StringCbPrintfA(B->message, sizeof(B->message), "| minfanout %3d |\n", getminfanout(B, getroot(B)) + 1);
1436 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1437 StringCbPrintfA(B->message, sizeof(B->message), "| height %3d |\n", gettreeheight(B));
1438 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1439 StringCbPrintfA(B->message, sizeof(B->message), "| freenode %6d |\n", getnodenumber(B, getfirstfreenode(B)));
1440 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1441 StringCbPrintfA(B->message, sizeof(B->message), "| theKey %6s |\n", getfunkey(B).name);
1442 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1443 StringCbPrintfA(B->message, sizeof(B->message), "| theData %d.%d.%d |\n", getfundata(B).volume,
1444 getfundata(B).vnode, getfundata(B).unique);
1445 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1446 StringCbPrintfA(B->message, sizeof(B->message), "- -- -- -- -- -- -\n");
1447 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1451 listBtreeNodes(Tree *B, const char * parent_desc, Nptr node)
1457 if (isntnode(node)) {
1458 StringCbPrintfA(B->message, sizeof(B->message), "%s - NoNode!!!\n");
1459 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1465 data = getdatavalue(node);
1466 StringCbPrintfA(B->message, sizeof(B->message), "%s - data node %d (%d.%d.%d)\n",
1467 parent_desc, getnodenumber(B, node),
1468 data.fid.volume, data.fid.vnode, data.fid.unique);
1469 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1472 showNode(B, parent_desc, node);
1474 if ( isinternal(node) || isroot(node) ) {
1475 StringCbPrintfA(thisnode, sizeof(thisnode), "parent %6d", getnodenumber(B , node));
1477 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1478 for ( i= isinternal(node) ? 0 : 1; i <= numentries(node); i++ ) {
1479 listBtreeNodes(B, thisnode, i == 0 ? getfirstnode(node) : getnode(node, i));
1484 /*********************** B+tree data printer ***********************/
1486 listBtreeValues(Tree *B, Nptr n, int num)
1492 for (slot = 1; (n != NONODE) && num && numentries(n); num--) {
1493 if (comparekeys(B)(getkey(n, slot),prev, 0) < 0) {
1494 StringCbPrintfA(B->message, sizeof(B->message), "BOMB %8s\n", getkey(n, slot).name);
1495 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1498 prev = getkey(n, slot);
1499 data = getdatavalue(getnode(n, slot));
1500 StringCbPrintfA(B->message, sizeof(B->message), "%8S (%d.%d.%d)\n",
1501 prev.name, data.fid.volume, data.fid.vnode, data.fid.unique);
1502 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1503 if (++slot > numentries(n))
1504 n = getnextnode(n), slot = 1;
1506 StringCbPrintfA(B->message, sizeof(B->message), "\n\n");
1507 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1510 /******************** entire B+tree data printer *******************/
1512 listAllBtreeValues(Tree *B)
1514 listBtreeValues(B, getleaf(B), BTERROR);
1516 #endif /* DEBUG_BTREE */
1519 findAllBtreeValues(Tree *B)
1522 Nptr n = getleaf(B), l;
1526 for (slot = 1; (n != NONODE) && num && numentries(n); num--) {
1527 if (comparekeys(B)(getkey(n, slot),prev, 0) < 0) {
1528 StringCbPrintfA(B->message, sizeof(B->message),"BOMB %8s\n", getkey(n, slot).name);
1529 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1534 prev = getkey(n, slot);
1535 l = bplus_Lookup(B, prev);
1538 StringCbPrintfA(B->message, sizeof(B->message),"BOMB %8S cannot be found\n", prev.name);
1540 StringCbPrintfA(B->message, sizeof(B->message),"BOMB lookup(%8S) finds wrong node\n", prev.name);
1541 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, B->message));
1547 if (++slot > numentries(n))
1548 n = getnextnode(n), slot = 1;
1553 * the return must be -1, 0, or 1. stricmp() in MSVC 8.0
1554 * does not return only those values.
1556 * the sorting of the tree is by case insensitive sort order
1557 * therefore, unless the strings actually match via a case
1558 * insensitive search do we want to perform the case sensitive
1559 * match. Otherwise, the search order might be considered
1560 * to be inconsistent when the EXACT_MATCH flag is set.
1563 cm_BPlusCompareNormalizedKeys(keyT key1, keyT key2, int flags)
1567 comp = cm_NormStrCmpI(key1.name, key2.name);
1568 if (comp == 0 && (flags & EXACT_MATCH))
1569 comp = cm_NormStrCmp(key1.name, key2.name);
1570 return (comp < 0 ? -1 : (comp > 0 ? 1 : 0));
1574 cm_BPlusDirLookupOriginalName(cm_dirOp_t * op, clientchar_t *centry,
1575 fschar_t **fsnameRetp)
1579 Nptr leafNode = NONODE;
1580 LARGE_INTEGER start, end;
1581 fschar_t * fsname = NULL;
1582 normchar_t * entry = NULL;
1584 if (op->scp->dirBplus == NULL ||
1585 op->dataVersion != op->scp->dirDataVersion) {
1590 entry = cm_ClientStringToNormStringAlloc(centry, -1, NULL);
1593 lock_AssertAny(&op->scp->dirlock);
1595 QueryPerformanceCounter(&start);
1597 leafNode = bplus_Lookup(op->scp->dirBplus, key);
1598 if (leafNode != NONODE) {
1600 Nptr firstDataNode, dataNode, nextDataNode;
1604 /* Found a leaf that matches the key via a case-insensitive
1605 * match. There may be one or more data nodes that match.
1606 * If we have an exact match, return that.
1607 * If we have an ambiguous match, return an error.
1608 * If we have only one inexact match, return that.
1610 slot = getSlot(op->scp->dirBplus, leafNode);
1611 if (slot <= BTERROR) {
1612 op->scp->dirDataVersion = 0;
1613 rc = (slot == BTERROR ? EINVAL : ENOENT);
1616 firstDataNode = getnode(leafNode, slot);
1618 for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1620 if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1624 nextDataNode = getdatanext(dataNode);
1628 fsname = getdatavalue(dataNode).fsname;
1630 bplus_lookup_hits++;
1631 } else if (count == 1) {
1632 fsname = getdatavalue(firstDataNode).fsname;
1633 rc = CM_ERROR_INEXACT_MATCH;
1634 bplus_lookup_hits_inexact++;
1636 rc = CM_ERROR_AMBIGUOUS_FILENAME;
1637 bplus_lookup_ambiguous++;
1641 bplus_lookup_misses++;
1645 *fsnameRetp = cm_FsStrDup(fsname);
1647 QueryPerformanceCounter(&end);
1649 bplus_lookup_time += (end.QuadPart - start.QuadPart);
1659 /* Look up a file name in directory.
1662 op->scp->dirlock is read locked
1665 op->scp->dirlock is read locked
1668 cm_BPlusDirLookup(cm_dirOp_t * op, clientchar_t * centry, cm_fid_t * cfid)
1671 normchar_t * entry = NULL;
1673 Nptr leafNode = NONODE;
1674 LARGE_INTEGER start, end;
1676 if (op->scp->dirBplus == NULL ||
1677 op->dataVersion != op->scp->dirDataVersion) {
1682 entry = cm_ClientStringToNormStringAlloc(centry, -1, NULL);
1685 lock_AssertAny(&op->scp->dirlock);
1687 QueryPerformanceCounter(&start);
1689 leafNode = bplus_Lookup(op->scp->dirBplus, key);
1690 if (leafNode != NONODE) {
1692 Nptr firstDataNode, dataNode, nextDataNode;
1696 /* Found a leaf that matches the key via a case-insensitive
1697 * match. There may be one or more data nodes that match.
1698 * If we have an exact match, return that.
1699 * If we have an ambiguous match, return an error.
1700 * If we have only one inexact match, return that.
1702 slot = getSlot(op->scp->dirBplus, leafNode);
1703 if (slot <= BTERROR) {
1704 op->scp->dirDataVersion = 0;
1705 rc = (slot == BTERROR ? EINVAL : ENOENT);
1708 firstDataNode = getnode(leafNode, slot);
1710 for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1712 if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1716 nextDataNode = getdatanext(dataNode);
1720 *cfid = getdatavalue(dataNode).fid;
1722 bplus_lookup_hits++;
1723 } else if (count == 1) {
1724 *cfid = getdatavalue(firstDataNode).fid;
1725 rc = CM_ERROR_INEXACT_MATCH;
1726 bplus_lookup_hits_inexact++;
1728 rc = CM_ERROR_AMBIGUOUS_FILENAME;
1729 bplus_lookup_ambiguous++;
1733 bplus_lookup_misses++;
1736 QueryPerformanceCounter(&end);
1738 bplus_lookup_time += (end.QuadPart - start.QuadPart);
1750 op->scp->dirlock is write locked
1753 op->scp->dirlock is write locked
1755 long cm_BPlusDirCreateEntry(cm_dirOp_t * op, clientchar_t * entry, cm_fid_t * cfid)
1760 LARGE_INTEGER start, end;
1761 normchar_t * normalizedName = NULL;
1763 if (op->scp->dirBplus == NULL ||
1764 op->dataVersion != op->scp->dirDataVersion) {
1769 normalizedName = cm_ClientStringToNormStringAlloc(entry, -1, NULL);
1770 key.name = normalizedName;
1772 lock_AssertWrite(&op->scp->dirlock);
1774 cm_SetFid(&data.fid, cfid->cell, cfid->volume, cfid->vnode, cfid->unique);
1775 data.cname = cm_ClientStrDup(entry);
1776 data.fsname = cm_ClientStringToFsStringAlloc(entry, -1, NULL);
1777 data.shortform = FALSE;
1779 QueryPerformanceCounter(&start);
1780 bplus_create_entry++;
1782 insert(op->scp->dirBplus, key, data);
1784 if (!cm_Is8Dot3(entry)) {
1786 clientchar_t wshortName[13];
1788 dfid.vnode = htonl(data.fid.vnode);
1789 dfid.unique = htonl(data.fid.unique);
1791 cm_Gen8Dot3NameIntW(entry, &dfid, wshortName, NULL);
1793 key.name = wshortName;
1795 data.cname = cm_ClientStrDup(entry);
1796 data.fsname = cm_ClientStringToFsStringAlloc(entry, -1, NULL);
1797 data.shortform = TRUE;
1799 insert(op->scp->dirBplus, key, data);
1802 QueryPerformanceCounter(&end);
1804 bplus_create_time += (end.QuadPart - start.QuadPart);
1808 if (normalizedName != NULL)
1809 free(normalizedName);
1816 op->scp->dirlock is write locked
1819 op->scp->dirlock is write locked
1821 int cm_BPlusDirDeleteEntry(cm_dirOp_t * op, clientchar_t *centry)
1825 Nptr leafNode = NONODE;
1826 LARGE_INTEGER start, end;
1827 normchar_t * normalizedEntry = NULL;
1829 if (op->scp->dirBplus == NULL ||
1830 op->dataVersion != op->scp->dirDataVersion) {
1835 normalizedEntry = cm_ClientStringToNormStringAlloc(centry, -1, NULL);
1836 key.name = normalizedEntry;
1838 lock_AssertWrite(&op->scp->dirlock);
1840 QueryPerformanceCounter(&start);
1842 bplus_remove_entry++;
1844 if (op->scp->dirBplus) {
1845 if (!cm_Is8Dot3(centry)) {
1848 clientchar_t shortName[13];
1850 leafNode = bplus_Lookup(op->scp->dirBplus, key);
1851 if (leafNode != NONODE) {
1853 Nptr firstDataNode, dataNode, nextDataNode;
1857 /* Found a leaf that matches the key via a case-insensitive
1858 * match. There may be one or more data nodes that match.
1859 * If we have an exact match, return that.
1860 * If we have an ambiguous match, return an error.
1861 * If we have only one inexact match, return that.
1863 slot = getSlot(op->scp->dirBplus, leafNode);
1864 if (slot <= BTERROR) {
1865 op->scp->dirDataVersion = 0;
1869 firstDataNode = getnode(leafNode, slot);
1871 for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1873 if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1877 nextDataNode = getdatanext(dataNode);
1881 fid = getdatavalue(dataNode).fid;
1883 } else if (count == 1) {
1884 fid = getdatavalue(firstDataNode).fid;
1885 rc = CM_ERROR_INEXACT_MATCH;
1887 rc = CM_ERROR_AMBIGUOUS_FILENAME;
1892 if (rc != CM_ERROR_AMBIGUOUS_FILENAME) {
1893 dfid.vnode = htonl(fid.vnode);
1894 dfid.unique = htonl(fid.unique);
1895 cm_Gen8Dot3NameIntW(centry, &dfid, shortName, NULL);
1897 /* delete first the long name and then the short name */
1898 delete(op->scp->dirBplus, key);
1899 key.name = shortName;
1900 delete(op->scp->dirBplus, key);
1903 clientchar_t * cname = NULL;
1905 /* We need to lookup the 8dot3 name to determine what the
1906 * matching long name is
1908 leafNode = bplus_Lookup(op->scp->dirBplus, key);
1909 if (leafNode != NONODE) {
1911 Nptr firstDataNode, dataNode, nextDataNode;
1915 /* Found a leaf that matches the key via a case-insensitive
1916 * match. There may be one or more data nodes that match.
1917 * If we have an exact match, return that.
1918 * If we have an ambiguous match, return an error.
1919 * If we have only one inexact match, return that.
1921 slot = getSlot(op->scp->dirBplus, leafNode);
1922 if (slot <= BTERROR) {
1923 op->scp->dirDataVersion = 0;
1928 firstDataNode = getnode(leafNode, slot);
1930 for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
1932 if (!comparekeys(op->scp->dirBplus)(key, getdatakey(dataNode), EXACT_MATCH) ) {
1936 nextDataNode = getdatanext(dataNode);
1940 cname = getdatavalue(dataNode).cname;
1942 } else if (count == 1) {
1943 cname = getdatavalue(firstDataNode).cname;
1944 rc = CM_ERROR_INEXACT_MATCH;
1946 rc = CM_ERROR_AMBIGUOUS_FILENAME;
1950 if (rc != CM_ERROR_AMBIGUOUS_FILENAME) {
1952 normchar_t * longNName = cm_NormalizeStringAlloc(cname, -1, NULL);
1954 key.name = longNName;
1955 delete(op->scp->dirBplus, key);
1956 key.name = normalizedEntry;
1961 delete(op->scp->dirBplus, key);
1966 QueryPerformanceCounter(&end);
1968 bplus_remove_time += (end.QuadPart - start.QuadPart);
1971 if (normalizedEntry)
1972 free(normalizedEntry);
1979 int cm_BPlusDirFoo(struct cm_scache *scp, struct cm_dirEntry *dep,
1980 void *dummy, osi_hyper_t *entryOffsetp)
1984 normchar_t *normalized_name=NULL;
1986 cm_SetFid(&data.fid, scp->fid.cell, scp->fid.volume,
1987 ntohl(dep->fid.vnode), ntohl(dep->fid.unique));
1991 normalized_name = cm_FsStringToNormStringAlloc(dep->name, -1, NULL);
1993 if (normalized_name) {
1994 key.name = normalized_name;
2002 data.cname = cm_FsStringToClientStringAlloc(dep->name, -1, NULL);
2003 data.fsname = cm_FsStrDup(dep->name);
2004 data.shortform = FALSE;
2006 /* the Write lock is held in cm_BPlusDirBuildTree() */
2007 insert(scp->dirBplus, key, data);
2009 if (!cm_Is8Dot3(data.cname)) {
2011 wchar_t wshortName[13];
2013 dfid.vnode = dep->fid.vnode;
2014 dfid.unique = dep->fid.unique;
2016 cm_Gen8Dot3NameIntW(data.cname, &dfid, wshortName, NULL);
2018 key.name = wshortName;
2019 data.cname = cm_FsStringToClientStringAlloc(dep->name, -1, NULL);
2020 data.fsname = cm_FsStrDup(dep->name);
2021 data.shortform = TRUE;
2023 insert(scp->dirBplus, key, data);
2026 if (normalized_name)
2027 free(normalized_name);
2030 findAllBtreeValues(scp->dirBplus);
2037 * scp->dirlock must be writeLocked before call
2039 * scp->mutex must not be held
2041 long cm_BPlusDirBuildTree(cm_scache_t *scp, cm_user_t *userp, cm_req_t* reqp)
2045 LARGE_INTEGER start, end;
2047 osi_assertx(scp->dirBplus == NULL, "cm_BPlusDirBuildTree called on non-empty tree");
2049 lock_AssertWrite(&scp->dirlock);
2051 QueryPerformanceCounter(&start);
2054 if (scp->dirBplus == NULL) {
2055 scp->dirBplus = initBtree(64, MAX_FANOUT, cm_BPlusCompareNormalizedKeys);
2057 if (scp->dirBplus == NULL) {
2061 thyper.HighPart = 0;
2062 rc = cm_ApplyDir(scp, cm_BPlusDirFoo, NULL, &thyper, userp, reqp, NULL);
2065 QueryPerformanceCounter(&end);
2067 bplus_build_time += (end.QuadPart - start.QuadPart);
2070 cm_BPlusDirEnumTest(scp, 1);
2075 int cm_MemDumpBPlusStats(FILE *outputFile, char *cookie, int lock)
2080 StringCbPrintfA(output, sizeof(output), "%s - B+ Lookup Hits: %-8d\r\n", cookie, bplus_lookup_hits);
2081 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2082 StringCbPrintfA(output, sizeof(output), "%s - Inexact Hits: %-8d\r\n", cookie, bplus_lookup_hits_inexact);
2083 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2084 StringCbPrintfA(output, sizeof(output), "%s - Ambiguous Hits: %-8d\r\n", cookie, bplus_lookup_ambiguous);
2085 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2086 StringCbPrintfA(output, sizeof(output), "%s - Misses: %-8d\r\n", cookie, bplus_lookup_misses);
2087 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2088 StringCbPrintfA(output, sizeof(output), "%s - Create: %-8d\r\n", cookie, bplus_create_entry);
2089 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2090 StringCbPrintfA(output, sizeof(output), "%s - Remove: %-8d\r\n", cookie, bplus_remove_entry);
2091 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2092 StringCbPrintfA(output, sizeof(output), "%s - Build Tree: %-8d\r\n", cookie, bplus_build_tree);
2093 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2094 StringCbPrintfA(output, sizeof(output), "%s - Free Tree: %-8d\r\n", cookie, bplus_free_tree);
2095 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2096 StringCbPrintfA(output, sizeof(output), "%s - DV Error: %-8d\r\n", cookie, bplus_dv_error);
2097 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2099 StringCbPrintfA(output, sizeof(output), "%s - B+ Time Lookup: %-16I64d\r\n", cookie, bplus_lookup_time);
2100 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2101 StringCbPrintfA(output, sizeof(output), "%s - Create: %-16I64d\r\n", cookie, bplus_create_time);
2102 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2103 StringCbPrintfA(output, sizeof(output), "%s - Remove: %-16I64d\r\n", cookie, bplus_remove_time);
2104 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2105 StringCbPrintfA(output, sizeof(output), "%s - Build: %-16I64d\r\n", cookie, bplus_build_time);
2106 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2107 StringCbPrintfA(output, sizeof(output), "%s - Free: %-16I64d\r\n", cookie, bplus_free_time);
2108 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
2113 void cm_BPlusDumpStats(void)
2115 afsi_log("B+ Lookup Hits: %-8d", bplus_lookup_hits);
2116 afsi_log(" Inexact Hits: %-8d", bplus_lookup_hits_inexact);
2117 afsi_log(" Ambiguous Hits: %-8d", bplus_lookup_ambiguous);
2118 afsi_log(" Misses: %-8d", bplus_lookup_misses);
2119 afsi_log(" Create: %-8d", bplus_create_entry);
2120 afsi_log(" Remove: %-8d", bplus_remove_entry);
2121 afsi_log(" Build Tree: %-8d", bplus_build_tree);
2122 afsi_log(" Free Tree: %-8d", bplus_free_tree);
2123 afsi_log(" DV Error: %-8d", bplus_dv_error);
2125 afsi_log("B+ Time Lookup: %-16I64d", bplus_lookup_time);
2126 afsi_log(" Create: %-16I64d", bplus_create_time);
2127 afsi_log(" Remove: %-16I64d", bplus_remove_time);
2128 afsi_log(" Build: %-16I64d", bplus_build_time);
2129 afsi_log(" Free: %-16I64d", bplus_free_time);
2132 static cm_direnum_t *
2133 cm_BPlusEnumAlloc(afs_uint32 entries)
2135 cm_direnum_t * enump;
2141 size = sizeof(cm_direnum_t)+(entries-1)*sizeof(cm_direnum_entry_t);
2142 enump = (cm_direnum_t *)malloc(size);
2143 memset(enump, 0, size);
2144 enump->count = entries;
2149 cm_BPlusDirEnumerate(cm_scache_t *scp, afs_uint32 locked,
2150 clientchar_t * maskp, cm_direnum_t **enumpp)
2152 afs_uint32 count = 0, slot, numentries;
2153 Nptr leafNode = NONODE, nextLeafNode;
2154 Nptr firstDataNode, dataNode, nextDataNode;
2155 cm_direnum_t * enump;
2159 osi_Log0(afsd_logp, "cm_BPlusDirEnumerate start");
2161 /* Read lock the bplus tree so the data can't change */
2163 lock_ObtainRead(&scp->dirlock);
2165 if (scp->dirBplus == NULL) {
2166 osi_Log0(afsd_logp, "cm_BPlusDirEnumerate No BPlus Tree");
2170 /* Compute the number of entries */
2171 for (count = 0, leafNode = getleaf(scp->dirBplus); leafNode; leafNode = nextLeafNode) {
2173 for ( slot = 1, numentries = numentries(leafNode); slot <= numentries; slot++) {
2174 firstDataNode = getnode(leafNode, slot);
2176 for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
2178 /* There can be two data nodes for one file. One for
2179 the long name and one for the short name. We only
2180 include one of these for the enumeration */
2182 if (maskp == NULL) {
2183 if (!getdatavalue(dataNode).shortform)
2186 if (!getdatavalue(dataNode).shortform &&
2187 cm_MatchMask(getdatavalue(dataNode).cname, maskp, CM_FLAG_CASEFOLD))
2190 nextDataNode = getdatanext(dataNode);
2194 nextLeafNode = getnextnode(leafNode);
2197 StringCbPrintfA(buffer, sizeof(buffer), "BPlusTreeEnumerate count = %d", count);
2198 osi_Log1(afsd_logp, "BPlus: %s", osi_LogSaveString(afsd_logp, buffer));
2200 /* Allocate the enumeration object */
2201 enump = cm_BPlusEnumAlloc(count);
2202 if (enump == NULL) {
2203 osi_Log0(afsd_logp, "cm_BPlusDirEnumerate Alloc failed");
2208 /* Copy the name and fid for each cname entry into the enumeration */
2209 for (count = 0, leafNode = getleaf(scp->dirBplus); leafNode; leafNode = nextLeafNode) {
2211 for ( slot = 1, numentries = numentries(leafNode); slot <= numentries; slot++) {
2212 firstDataNode = getnode(leafNode, slot);
2214 for ( dataNode = firstDataNode; dataNode; dataNode = nextDataNode) {
2215 clientchar_t * name;
2218 if (maskp == NULL) {
2219 if (!getdatavalue(dataNode).shortform) {
2223 if (!getdatavalue(dataNode).shortform &&
2224 cm_MatchMask(getdatavalue(dataNode).cname, maskp, CM_FLAG_CASEFOLD)) {
2230 name = cm_ClientStrDup(getdatavalue(dataNode).cname);
2233 osi_Log0(afsd_logp, "cm_BPlusDirEnumerate strdup failed");
2238 enump->entry[count].name = name;
2239 enump->entry[count].fid = getdatavalue(dataNode).fid;
2241 if (!cm_Is8Dot3(name)) {
2244 dfid.vnode = htonl(getdatavalue(dataNode).fid.vnode);
2245 dfid.unique = htonl(getdatavalue(dataNode).fid.unique);
2247 cm_Gen8Dot3NameIntW(name, &dfid, enump->entry[count].shortName, NULL);
2249 StringCbCopyW(enump->entry[count].shortName,
2250 sizeof(enump->entry[count].shortName),
2256 nextDataNode = getdatanext(dataNode);
2260 nextLeafNode = getnextnode(leafNode);
2265 lock_ReleaseRead(&scp->dirlock);
2267 /* if we failed, cleanup any mess */
2269 osi_Log0(afsd_logp, "cm_BPlusDirEnumerate rc != 0");
2271 for ( count = 0; count < enump->count && enump->entry[count].name; count++ ) {
2272 free(enump->entry[count].name);
2279 osi_Log0(afsd_logp, "cm_BPlusDirEnumerate end");
2285 cm_BPlusDirNextEnumEntry(cm_direnum_t *enump, cm_direnum_entry_t **entrypp)
2287 if (enump == NULL || entrypp == NULL || enump->next > enump->count) {
2290 osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry invalid input");
2291 return CM_ERROR_INVAL; \
2294 *entrypp = &enump->entry[enump->next++];
2295 if ( enump->next == enump->count ) {
2296 osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry STOPNOW");
2297 return CM_ERROR_STOPNOW;
2300 osi_Log0(afsd_logp, "cm_BPlusDirNextEnumEntry SUCCESS");
2306 cm_BPlusDirFreeEnumeration(cm_direnum_t *enump)
2310 osi_Log0(afsd_logp, "cm_BPlusDirFreeEnumeration");
2313 for ( count = 0; count < enump->count && enump->entry[count].name; count++ ) {
2314 free(enump->entry[count].name);
2322 cm_BPlusDirEnumTest(cm_scache_t * dscp, afs_uint32 locked)
2324 cm_direnum_t * enump = NULL;
2325 cm_direnum_entry_t * entryp;
2328 osi_Log0(afsd_logp, "cm_BPlusDirEnumTest start");
2330 for (code = cm_BPlusDirEnumerate(dscp, locked, NULL, &enump); code == 0; ) {
2331 code = cm_BPlusDirNextEnumEntry(enump, &entryp);
2332 if (code == 0 || code == CM_ERROR_STOPNOW) {
2335 char * type = "ScpNotFound";
2338 scp = cm_FindSCache(&entryp->fid);
2340 switch (scp->fileType) {
2341 case CM_SCACHETYPE_FILE :
2344 case CM_SCACHETYPE_DIRECTORY :
2347 case CM_SCACHETYPE_SYMLINK :
2350 case CM_SCACHETYPE_MOUNTPOINT:
2351 type = "MountPoint";
2353 case CM_SCACHETYPE_DFSLINK :
2356 case CM_SCACHETYPE_INVALID :
2364 dv = scp->dataVersion;
2365 cm_ReleaseSCache(scp);
2368 StringCbPrintfA(buffer, sizeof(buffer), "'%S' Fid = (%d,%d,%d,%d) Short = '%S' Type %s DV %I64d",
2370 entryp->fid.cell, entryp->fid.volume, entryp->fid.vnode, entryp->fid.unique,
2375 osi_Log0(afsd_logp, osi_LogSaveString(afsd_logp, buffer));
2380 cm_BPlusDirFreeEnumeration(enump);
2382 osi_Log0(afsd_logp, "cm_BPlusDirEnumTest end");
2386 #endif /* USE_BPLUS */