![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to BTreeTreeOps.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / BTree|
Return to BTreeTreeOps.c CVS log | Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / BTree |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.1 (the "License"). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License.
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24:
25: /*
26: File: BTreeTreeOps.c
27:
28: Contains: Multi-node tree operations for the BTree Module.
29:
30: Version: xxx put the technology version here xxx
31:
32: Written by: Gordon Sheridan and Bill Bruffey
33:
34: Copyright: � 1992-1998 by Apple Computer, Inc., all rights reserved.
35:
36: File Ownership:
37:
38: DRI: Don Brady
39:
40: Other Contact: Mark Day
41:
42: Technology: File Systems
43:
44: Writers:
45:
46: (msd) Mark Day
47: (DSH) Deric Horn
48: (djb) Don Brady
49:
50: Change History (most recent first):
51:
52: <CS5> 12/8/97 djb Radar #2200632, CollapseTree wasn't marking root node dirty.
53: <CS4> 11/24/97 djb Radar #2005325, InsertLevel incorrectly handled root splits!
54: <CS3> 10/17/97 msd Conditionalize DebugStrs.
55: <CS2> 5/16/97 msd InsertNode() needs a return statement in ErrorExit.
56: <CS1> 4/23/97 djb first checked in
57:
58: <HFS8> 3/17/97 DSH Conditionalize out Panic assertion for SC.
59: <HFS7> 3/3/97 djb Removed DebugStr in InsertLevel.
60: <HFS6> 2/19/97 djb Major re-write of insert code; added InsertLevel and InsertNode.
61: <HFS5> 1/27/97 djb InsertTree and DeleteTree are now recursive and support variable
62: sized index keys.
63: <HFS4> 1/16/97 djb Removed DebugStr in SearchTree. Added initial support for
64: variable sized index keys.
65: <HFS3> 1/3/97 djb Changed len8 to length8.
66: <HFS2> 1/3/97 djb Added support for large keys.
67: <HFS1> 12/19/96 djb first checked in
68:
69: History applicable to original Scarecrow Design:
70:
71: <3> 10/25/96 ser Changing for new VFPI
72: <2> 1/22/96 dkh Add #include Memory.h
73: <1> 10/18/95 rst Moved from Scarecrow project.
74:
75: <12> 7/18/95 mbb Change MoveData & ClearBytes to BlockMoveData & BlockZero.
76: <11> 9/30/94 prp Get in sync with D2 interface changes.
77: <10> 7/25/94 wjk Eliminate usage of BytePtr in favor of UInt8 *.
78: <9> 7/22/94 wjk Convert to the new set of header files.
79: <8> 12/2/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
80: NRCmds environments.
81: <7> 11/30/93 wjk Change some Ptr's to BytePtr's in function definitions so they
82: agree with their prototypes.
83: <6> 5/21/93 gs Debug DeleteTree. Modify InsertTree for BTReplaceRecord.
84: <5> 5/10/93 gs Modify RotateLeft, and add DeleteTree, CollapseTree routines.
85: <4> 3/23/93 gs revise RotateLeft to use InsertKeyRecord instead of
86: InsertRecord.
87: <3> 3/23/93 gs Implement SplitLeft, InsertTree routine.
88: <2> 2/8/93 gs Implement SearchTree, and RotateLeft.
89: <1> 11/15/92 gs first checked in
90:
91: */
92:
93: #include "../headers/BTreesPrivate.h"
94:
95: //
96: /////////////////////// Routines Internal To BTree Module ///////////////////////
97: //
98: // SearchTree
99: // InsertTree
100: //
101: ////////////////////// Routines Internal To BTreeTreeOps.c //////////////////////
102:
103: static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr,
104: NodeDescPtr leftNode,
105: NodeDescPtr rightNode );
106:
107: static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr,
108: BlockDescriptor *blockPtr );
109:
110: static OSStatus RotateLeft (BTreeControlBlockPtr btreePtr,
111: NodeDescPtr leftNode,
112: NodeDescPtr rightNode,
113: UInt16 rightInsertIndex,
114: KeyPtr keyPtr,
115: UInt8 * recPtr,
116: UInt16 recSize,
117: UInt16 *insertIndex,
118: UInt32 *insertNodeNum,
119: Boolean *recordFit,
120: UInt16 *recsRotated );
121:
122: static Boolean RotateRecordLeft (BTreeControlBlockPtr btreePtr,
123: NodeDescPtr leftNode,
124: NodeDescPtr rightNode );
125:
126: static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr,
127: BlockDescriptor *leftNode,
128: BlockDescriptor *rightNode,
129: UInt32 rightNodeNum,
130: UInt16 index,
131: KeyPtr keyPtr,
132: UInt8 * recPtr,
133: UInt16 recSize,
134: UInt16 *insertIndex,
135: UInt32 *insertNodeNum,
136: UInt16 *recsRotated );
137:
138:
139:
140: static OSStatus InsertLevel (BTreeControlBlockPtr btreePtr,
141: TreePathTable treePathTable,
142: InsertKey *primaryKey,
143: InsertKey *secondaryKey,
144: BlockDescriptor *targetNode,
145: UInt16 index,
146: UInt16 level,
147: UInt32 *insertNode );
148:
149: static OSErr InsertNode (BTreeControlBlockPtr btreePtr,
150: InsertKey *key,
151: BlockDescriptor *rightNode,
152: UInt32 node,
153: UInt16 index,
154: UInt32 *newNode,
155: UInt16 *newIndex,
156: BlockDescriptor *leftNode,
157: Boolean *updateParent,
158: Boolean *insertParent,
159: Boolean *rootSplit );
160:
161: static UInt16 GetKeyLength (const BTreeControlBlock *btreePtr,
162: const BTreeKey *key,
163: Boolean forLeafNode );
164:
165:
166:
167: //////////////////////// BTree Multi-node Tree Operations ///////////////////////
168:
169:
170: /*-------------------------------------------------------------------------------
171:
172: Routine: SearchTree - Search BTree for key and set up Tree Path Table.
173:
174: Function: Searches BTree for specified key, setting up the Tree Path Table to
175: reflect the search path.
176:
177:
178: Input: btreePtr - pointer to control block of BTree to search
179: keyPtr - pointer to the key to search for
180: treePathTable - pointer to the tree path table to construct
181:
182: Output: nodeNum - number of the node containing the key position
183: iterator - BTreeIterator specifying record or insert position
184:
185: Result: noErr - key found, index is record index
186: fsBTRecordNotFoundErr - key not found, index is insert index
187: fsBTEmptyErr - key not found, return params are nil
188: otherwise - catastrophic failure (GetNode/ReleaseNode failed)
189: -------------------------------------------------------------------------------*/
190:
191: OSStatus SearchTree (BTreeControlBlockPtr btreePtr,
192: BTreeKeyPtr searchKey,
193: TreePathTable treePathTable,
194: UInt32 *nodeNum,
195: BlockDescriptor *nodePtr,
196: UInt16 *returnIndex )
197: {
198: OSStatus err;
199: SInt16 level;
200: UInt32 curNodeNum;
201: NodeRec nodeRec;
202: UInt16 index;
203: Boolean keyFound;
204: KeyPtr keyPtr;
205: UInt8 * dataPtr;
206: UInt16 dataSize;
207:
208:
209: if (btreePtr->treeDepth == 0) // is the tree empty?
210: {
211: err = fsBTEmptyErr;
212: goto ErrorExit;
213: }
214:
215: curNodeNum = btreePtr->rootNode;
216:
217: //�� for debugging...
218: treePathTable [0].node = 0;
219: treePathTable [0].index = 0;
220:
221: while (true)
222: {
223: PanicIf(curNodeNum == 0, "\pSearchTree: curNodeNum is zero!");
224:
225: err = GetNode (btreePtr, curNodeNum, &nodeRec);
226: if (err != noErr)
227: {
228: goto ErrorExit;
229: }
230:
231: keyFound = SearchNode (btreePtr, nodeRec.buffer, searchKey, &index);
232:
233: level = ((BTNodeDescriptor*)nodeRec.buffer)->height; //�� or --level;
234:
235:
236: treePathTable [level].node = curNodeNum;
237:
238: if ( ((BTNodeDescriptor*)nodeRec.buffer)->type == kLeafNode)
239: {
240: treePathTable [level].index = index;
241: break; // were done...
242: }
243:
244: if ( (keyFound != true) && (index != 0))
245: --index;
246:
247: treePathTable [level].index = index;
248:
249: GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize);
250: curNodeNum = *(UInt32 *)dataPtr;
251: err = ReleaseNode (btreePtr, &nodeRec);
252: if (err != noErr)
253: {
254: goto ErrorExit;
255: }
256: }
257:
258: *nodeNum = curNodeNum;
259: *nodePtr = nodeRec;
260: *returnIndex = index;
261:
262: if (keyFound)
263: return noErr; // searchKey found, index identifies record in node
264: else
265: return fsBTRecordNotFoundErr; // searchKey not found, index identifies insert point
266:
267: ErrorExit:
268:
269: *nodeNum = 0;
270: nodePtr->buffer = nil;
271: nodePtr->blockHeader = nil;
272: *returnIndex = 0;
273:
274: return err;
275: }
276:
277:
278:
279:
280: ////////////////////////////////// InsertTree ///////////////////////////////////
281:
282: OSStatus InsertTree ( BTreeControlBlockPtr btreePtr,
283: TreePathTable treePathTable,
284: KeyPtr keyPtr,
285: UInt8 * recPtr,
286: UInt16 recSize,
287: BlockDescriptor *targetNode,
288: UInt16 index,
289: UInt16 level,
290: Boolean replacingKey,
291: UInt32 *insertNode )
292: {
293: InsertKey primaryKey;
294: OSStatus err;
295:
296: primaryKey.keyPtr = keyPtr;
297: primaryKey.keyLength = GetKeyLength(btreePtr, primaryKey.keyPtr, (level == 1));
298: primaryKey.recPtr = recPtr;
299: primaryKey.recSize = recSize;
300: primaryKey.replacingKey = replacingKey;
301: primaryKey.skipRotate = false;
302:
303: err = InsertLevel (btreePtr, treePathTable, &primaryKey, nil,
304: targetNode, index, level, insertNode );
305:
306: return err;
307:
308: } // End of InsertTree
309:
310:
311: ////////////////////////////////// InsertLevel //////////////////////////////////
312:
313: OSStatus InsertLevel (BTreeControlBlockPtr btreePtr,
314: TreePathTable treePathTable,
315: InsertKey *primaryKey,
316: InsertKey *secondaryKey,
317: BlockDescriptor *targetNode,
318: UInt16 index,
319: UInt16 level,
320: UInt32 *insertNode )
321: {
322: OSStatus err;
323: BlockDescriptor leftNode;
324: UInt32 targetNodeNum;
325: UInt32 newNodeNum;
326: UInt16 newIndex;
327: Boolean insertParent;
328: Boolean updateParent;
329: Boolean newRoot;
330:
331: #if defined(applec) && !defined(__SC__)
332: PanicIf ((level == 1) && (((NodeDescPtr)targetNode->buffer)->type != kLeafNode), "\P InsertLevel: non-leaf at level 1! ");
333: #endif
334: leftNode.buffer = nil;
335: targetNodeNum = treePathTable [level].node;
336:
337: insertParent = false;
338: updateParent = false;
339:
340: ////// process first insert //////
341:
342: err = InsertNode (btreePtr, primaryKey, targetNode, targetNodeNum, index,
343: &newNodeNum, &newIndex, &leftNode, &updateParent, &insertParent, &newRoot );
344: M_ExitOnError (err);
345:
346: if ( newRoot )
347: {
348: // Extend the treePathTable by adding an entry for the new
349: // root node that references the current targetNode.
350: //
351: // If inserting the secondaryKey changes the first key of
352: // the target node, then we'll have to update the second
353: // key in the new root node.
354:
355: treePathTable [level + 1].node = btreePtr->rootNode;
356: treePathTable [level + 1].index = 1; // 1 since we always split/rotate left
357: }
358:
359: if ( level == 1 )
360: *insertNode = newNodeNum;
361:
362: ////// process second insert (if any) //////
363:
364: if ( secondaryKey != nil )
365: {
366: Boolean temp;
367:
368: err = InsertNode (btreePtr, secondaryKey, targetNode, newNodeNum, newIndex,
369: &newNodeNum, &newIndex, &leftNode, &updateParent, &insertParent, &temp);
370: M_ExitOnError (err);
371:
372: if ( DEBUG_BUILD && updateParent && newRoot )
373: DebugStr("\p InsertLevel: New root from primary key, update from secondary key...");
374: }
375:
376: //////////////////////// Update Parent(s) ///////////////////////////////
377:
378: if ( insertParent || updateParent )
379: {
380: BlockDescriptor parentNode;
381: UInt32 parentNodeNum;
382: KeyPtr keyPtr;
383: UInt8 * recPtr;
384: UInt16 recSize;
385:
386: secondaryKey = nil;
387:
388: PanicIf ( (level == btreePtr->treeDepth), "\p InsertLevel: unfinished insert!?");
389:
390: ++level;
391:
392: // Get Parent Node data...
393: index = treePathTable [level].index;
394: parentNodeNum = treePathTable [level].node;
395:
396: PanicIf ( parentNodeNum == 0, "\p InsertLevel: parent node is zero!?");
397:
398: err = GetNode (btreePtr, parentNodeNum, &parentNode); // released as target node in next level up
399: M_ExitOnError (err);
400: #if defined(applec) && !defined(__SC__)
401: if (DEBUG_BUILD && level > 1)
402: PanicIf ( ((NodeDescPtr)parentNode.buffer)->type != kIndexNode, "\P InsertLevel: parent node not an index node! ");
403: #endif
404: ////////////////////////// Update Parent Index //////////////////////////////
405:
406: if ( updateParent )
407: {
408: //���debug: check if ptr == targetNodeNum
409: GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
410: PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p InsertLevel: parent ptr doesn't match target node!");
411:
412: // need to delete and re-insert this parent key/ptr
413: // we delete it here and it gets re-inserted in the
414: // InsertLevel call below.
415: DeleteRecord (btreePtr, parentNode.buffer, index);
416:
417: primaryKey->keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
418: primaryKey->keyLength = GetKeyLength(btreePtr, primaryKey->keyPtr, false);
419: primaryKey->recPtr = (UInt8 *) &targetNodeNum;
420: primaryKey->recSize = sizeof(targetNodeNum);
421: primaryKey->replacingKey = kReplaceRecord;
422: primaryKey->skipRotate = insertParent; // don't rotate left if we have two inserts occuring
423: }
424:
425: ////////////////////////// Add New Parent Index /////////////////////////////
426:
427: if ( insertParent )
428: {
429: InsertKey *insertKeyPtr;
430: InsertKey insertKey;
431:
432: if ( updateParent )
433: {
434: insertKeyPtr = &insertKey;
435: secondaryKey = &insertKey;
436: }
437: else
438: {
439: insertKeyPtr = primaryKey;
440: }
441:
442: insertKeyPtr->keyPtr = (KeyPtr) GetRecordAddress (btreePtr, leftNode.buffer, 0);
443: insertKeyPtr->keyLength = GetKeyLength(btreePtr, insertKeyPtr->keyPtr, false);
444: insertKeyPtr->recPtr = (UInt8 *) &((NodeDescPtr)targetNode->buffer)->bLink;
445: insertKeyPtr->recSize = sizeof(UInt32);
446: insertKeyPtr->replacingKey = kInsertRecord;
447: insertKeyPtr->skipRotate = false; // a rotate is OK during second insert
448: }
449:
450: err = InsertLevel (btreePtr, treePathTable, primaryKey, secondaryKey,
451: &parentNode, index, level, insertNode );
452: M_ExitOnError (err);
453: }
454:
455: err = UpdateNode (btreePtr, targetNode); // all done with target
456: M_ExitOnError (err);
457:
458: err = UpdateNode (btreePtr, &leftNode); // all done with left sibling
459: M_ExitOnError (err);
460:
461: return noErr;
462:
463: ErrorExit:
464:
465: (void) ReleaseNode (btreePtr, targetNode);
466: (void) ReleaseNode (btreePtr, &leftNode);
467:
468: Panic ("\p InsertLevel: an error occured!");
469:
470: return err;
471:
472: } // End of InsertLevel
473:
474:
475:
476: ////////////////////////////////// InsertNode ///////////////////////////////////
477:
478: static OSErr InsertNode (BTreeControlBlockPtr btreePtr,
479: InsertKey *key,
480:
481: BlockDescriptor *rightNode,
482: UInt32 node,
483: UInt16 index,
484:
485: UInt32 *newNode,
486: UInt16 *newIndex,
487:
488: BlockDescriptor *leftNode,
489: Boolean *updateParent,
490: Boolean *insertParent,
491: Boolean *rootSplit )
492: {
493: BlockDescriptor *targetNode;
494: UInt32 leftNodeNum;
495: UInt16 recsRotated;
496: OSErr err;
497: Boolean recordFit;
498:
499: *rootSplit = false;
500:
501: PanicIf ( rightNode->buffer == leftNode->buffer, "\p InsertNode: rightNode == leftNode, huh?");
502:
503: leftNodeNum = ((NodeDescPtr) rightNode->buffer)->bLink;
504:
505:
506: /////////////////////// Try Simple Insert ///////////////////////////////
507:
508: if ( node == leftNodeNum )
509: targetNode = leftNode;
510: else
511: targetNode = rightNode;
512:
513: recordFit = InsertKeyRecord (btreePtr, targetNode->buffer, index, key->keyPtr, key->keyLength, key->recPtr, key->recSize);
514:
515: if ( recordFit )
516: {
517: *newNode = node;
518: *newIndex = index;
519:
520: if ( (index == 0) && (((NodeDescPtr) targetNode->buffer)->height != btreePtr->treeDepth) )
521: *updateParent = true; // the first record changed so we need to update the parent
522: }
523:
524:
525: //////////////////////// Try Rotate Left ////////////////////////////////
526:
527: if ( !recordFit && leftNodeNum > 0 )
528: {
529: PanicIf ( leftNode->buffer != nil, "\p InsertNode: leftNode already aquired!");
530:
531: if ( leftNode->buffer == nil )
532: {
533: err = GetNode (btreePtr, leftNodeNum, leftNode); // will be released by caller or a split below
534: M_ExitOnError (err);
535: }
536:
537: PanicIf ( ((NodeDescPtr) leftNode->buffer)->fLink != node, "\p InsertNode, RotateLeft: invalid sibling link!" );
538:
539: if ( !key->skipRotate ) // are rotates allowed?
540: {
541: err = RotateLeft (btreePtr, leftNode->buffer, rightNode->buffer, index, key->keyPtr, key->recPtr,
542: key->recSize, newIndex, newNode, &recordFit, &recsRotated );
543: M_ExitOnError (err);
544:
545: if ( recordFit )
546: {
547: if ( key->replacingKey || (recsRotated > 1) || (index > 0) )
548: *updateParent = true;
549: }
550: }
551: }
552:
553:
554: //////////////////////// Try Split Left /////////////////////////////////
555:
556: if ( !recordFit )
557: {
558: // might not have left node...
559: err = SplitLeft (btreePtr, leftNode, rightNode, node, index, key->keyPtr,
560: key->recPtr, key->recSize, newIndex, newNode, &recsRotated);
561: M_ExitOnError (err);
562:
563: // if we split root node - add new root
564:
565: if ( ((NodeDescPtr) rightNode->buffer)->height == btreePtr->treeDepth )
566: {
567: err = AddNewRootNode (btreePtr, leftNode->buffer, rightNode->buffer); // Note: does not update TPT
568: M_ExitOnError (err);
569: *rootSplit = true;
570: }
571: else
572: {
573: *insertParent = true;
574:
575: if ( key->replacingKey || (recsRotated > 1) || (index > 0) )
576: *updateParent = true;
577: }
578: }
579:
580: return noErr;
581:
582: ErrorExit:
583:
584: (void) ReleaseNode (btreePtr, leftNode);
585: return err;
586:
587: } // End of InsertNode
588:
589:
590: /*-------------------------------------------------------------------------------
591: Routine: DeleteTree - One_line_description.
592:
593: Function: Brief_description_of_the_function_and_any_side_effects
594:
595: ToDo:
596:
597: Input: btreePtr - description
598: treePathTable - description
599: targetNode - description
600: index - description
601:
602: Result: noErr - success
603: != noErr - failure
604: -------------------------------------------------------------------------------*/
605:
606: OSStatus DeleteTree (BTreeControlBlockPtr btreePtr,
607: TreePathTable treePathTable,
608: BlockDescriptor *targetNode,
609: UInt16 index,
610: UInt16 level )
611: {
612: OSStatus err;
613: BlockDescriptor parentNode;
614: BTNodeDescriptor *targetNodePtr;
615: UInt32 targetNodeNum;
616: Boolean deleteRequired;
617: Boolean updateRequired;
618:
619:
620: deleteRequired = false;
621: updateRequired = false;
622:
623: targetNodeNum = treePathTable[level].node;
624: targetNodePtr = targetNode->buffer;
625: PanicIf (targetNodePtr == nil, "\pDeleteTree: targetNode has nil buffer!");
626:
627: DeleteRecord (btreePtr, targetNodePtr, index);
628:
629: //�� coalesce remaining records?
630:
631: if ( targetNodePtr->numRecords == 0 ) // did we delete the last record?
632: {
633: BlockDescriptor siblingNode;
634: UInt32 siblingNodeNum;
635:
636: deleteRequired = true;
637:
638: ////////////////// Get Siblings & Update Links //////////////////////////
639:
640: siblingNodeNum = targetNodePtr->bLink; // Left Sibling Node
641: if ( siblingNodeNum != 0 )
642: {
643: err = GetNode (btreePtr, siblingNodeNum, &siblingNode);
644: M_ExitOnError (err);
645: ((NodeDescPtr)siblingNode.buffer)->fLink = targetNodePtr->fLink;
646: err = UpdateNode (btreePtr, &siblingNode);
647: M_ExitOnError (err);
648: }
649: else if ( targetNodePtr->type == kLeafNode ) // update firstLeafNode
650: {
651: btreePtr->firstLeafNode = targetNodePtr->fLink;
652: }
653:
654: siblingNodeNum = targetNodePtr->fLink; // Right Sibling Node
655: if ( siblingNodeNum != 0 )
656: {
657: err = GetNode (btreePtr, siblingNodeNum, &siblingNode);
658: M_ExitOnError (err);
659: ((NodeDescPtr)siblingNode.buffer)->bLink = targetNodePtr->bLink;
660: err = UpdateNode (btreePtr, &siblingNode);
661: M_ExitOnError (err);
662: }
663: else if ( targetNodePtr->type == kLeafNode ) // update lastLeafNode
664: {
665: btreePtr->lastLeafNode = targetNodePtr->bLink;
666: }
667:
668: //////////////////////// Free Empty Node ////////////////////////////////
669:
670: ClearNode (btreePtr, targetNodePtr);
671:
672: err = UpdateNode (btreePtr, targetNode);
673: M_ExitOnError (err);
674: err = FreeNode (btreePtr, targetNodeNum);
675: M_ExitOnError (err);
676: }
677: else if ( index == 0 ) // did we delete the first record?
678: {
679: updateRequired = true; // yes, so we need to update parent
680: }
681:
682:
683: if ( level == btreePtr->treeDepth ) // then targetNode->buffer is the root node
684: {
685: deleteRequired = false;
686: updateRequired = false;
687:
688: if ( targetNode->buffer == nil ) // then root was freed and the btree is empty
689: {
690: btreePtr->rootNode = 0;
691: btreePtr->treeDepth = 0;
692: }
693: else if ( ((NodeDescPtr)targetNode->buffer)->numRecords == 1 )
694: {
695: err = CollapseTree (btreePtr, targetNode);
696: M_ExitOnError (err);
697: }
698: }
699:
700:
701: if ( updateRequired || deleteRequired )
702: {
703: ++level; // next level
704:
705: //// Get Parent Node and index
706: index = treePathTable [level].index;
707: err = GetNode (btreePtr, treePathTable[level].node, &parentNode);
708: M_ExitOnError (err);
709:
710: if ( updateRequired )
711: {
712: KeyPtr keyPtr;
713: UInt8 * recPtr;
714: UInt16 recSize;
715: UInt32 insertNode;
716:
717: //���debug: check if ptr == targetNodeNum
718: GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
719: PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p DeleteTree: parent ptr doesn't match targetNodeNum!!");
720:
721: // need to delete and re-insert this parent key/ptr
722: DeleteRecord (btreePtr, parentNode.buffer, index);
723:
724: keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
725: recPtr = (UInt8 *) &targetNodeNum;
726: recSize = sizeof(targetNodeNum);
727:
728: err = InsertTree (btreePtr, treePathTable, keyPtr, recPtr, recSize,
729: &parentNode, index, level, kReplaceRecord, &insertNode);
730: M_ExitOnError (err);
731: }
732: else // deleteRequired
733: {
734: err = DeleteTree (btreePtr, treePathTable, &parentNode, index, level);
735: M_ExitOnError (err);
736: }
737: }
738:
739:
740: err = UpdateNode (btreePtr, targetNode);
741: M_ExitOnError (err);
742:
743: return noErr;
744:
745: ErrorExit:
746:
747: (void) ReleaseNode (btreePtr, targetNode);
748: (void) ReleaseNode (btreePtr, &parentNode);
749:
750: return err;
751:
752: } // end DeleteTree
753:
754:
755:
756: ///////////////////////////////// CollapseTree //////////////////////////////////
757:
758: static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr,
759: BlockDescriptor *blockPtr )
760: {
761: OSStatus err;
762: UInt32 originalRoot;
763: UInt32 nodeNum;
764:
765: originalRoot = btreePtr->rootNode;
766:
767: while (true)
768: {
769: if ( ((NodeDescPtr)blockPtr->buffer)->numRecords > 1)
770: break; // this will make a fine root node
771:
772: if ( ((NodeDescPtr)blockPtr->buffer)->type == kLeafNode)
773: break; // we've hit bottom
774:
775: nodeNum = btreePtr->rootNode;
776: btreePtr->rootNode = GetChildNodeNum (btreePtr, blockPtr->buffer, 0);
777: --btreePtr->treeDepth;
778:
779: //// Clear and Free Current Old Root Node ////
780: ClearNode (btreePtr, blockPtr->buffer);
781: err = UpdateNode (btreePtr, blockPtr);
782: M_ExitOnError (err);
783: err = FreeNode (btreePtr, nodeNum);
784: M_ExitOnError (err);
785:
786: //// Get New Root Node
787: err = GetNode (btreePtr, btreePtr->rootNode, blockPtr);
788: M_ExitOnError (err);
789: }
790:
791: if (btreePtr->rootNode != originalRoot)
792: M_BTreeHeaderDirty (btreePtr);
793:
794: err = UpdateNode (btreePtr, blockPtr); // always update!
795: M_ExitOnError (err);
796:
797: return noErr;
798:
799:
800: /////////////////////////////////// ErrorExit ///////////////////////////////////
801:
802: ErrorExit:
803: (void) ReleaseNode (btreePtr, blockPtr);
804: return err;
805: }
806:
807:
808:
809: ////////////////////////////////// RotateLeft ///////////////////////////////////
810:
811: /*-------------------------------------------------------------------------------
812:
813: Routine: RotateLeft - One_line_description.
814:
815: Function: Brief_description_of_the_function_and_any_side_effects
816:
817: Algorithm: if rightIndex > insertIndex, subtract 1 for actual rightIndex
818:
819: Input: btreePtr - description
820: leftNode - description
821: rightNode - description
822: rightInsertIndex - description
823: keyPtr - description
824: recPtr - description
825: recSize - description
826:
827: Output: insertIndex
828: insertNodeNum - description
829: recordFit - description
830: recsRotated
831:
832: Result: noErr - success
833: != noErr - failure
834: -------------------------------------------------------------------------------*/
835:
836: static OSStatus RotateLeft (BTreeControlBlockPtr btreePtr,
837: NodeDescPtr leftNode,
838: NodeDescPtr rightNode,
839: UInt16 rightInsertIndex,
840: KeyPtr keyPtr,
841: UInt8 * recPtr,
842: UInt16 recSize,
843: UInt16 *insertIndex,
844: UInt32 *insertNodeNum,
845: Boolean *recordFit,
846: UInt16 *recsRotated )
847: {
848: OSStatus err;
849: SInt32 insertSize;
850: SInt32 nodeSize;
851: SInt32 leftSize, rightSize;
852: SInt32 moveSize = 0;
853: UInt16 keyLength;
854: UInt16 lengthFieldSize;
855: UInt16 index, moveIndex;
856: Boolean didItFit;
857:
858: ///////////////////// Determine If Record Will Fit //////////////////////////
859:
860: keyLength = GetKeyLength(btreePtr, keyPtr, (rightNode->type == kLeafNode));
861:
862: // the key's length field is 8-bits in HFS and 16-bits in HFS+
863: if ( btreePtr->attributes & kBTBigKeysMask )
864: lengthFieldSize = sizeof(UInt16);
865: else
866: lengthFieldSize = sizeof(UInt8);
867:
868: insertSize = keyLength + lengthFieldSize + recSize + sizeof(UInt16);
869:
870: if ( M_IsOdd (insertSize) )
871: ++insertSize; // add pad byte;
872:
873: nodeSize = btreePtr->nodeSize;
874:
875: // add size of insert record to right node
876: rightSize = nodeSize - GetNodeFreeSize (btreePtr, rightNode) + insertSize;
877: leftSize = nodeSize - GetNodeFreeSize (btreePtr, leftNode);
878:
879: moveIndex = 0;
880:
881: while ( leftSize < rightSize )
882: {
883: if ( moveIndex < rightInsertIndex )
884: {
885: moveSize = GetRecordSize (btreePtr, rightNode, moveIndex) + 2;
886: }
887: else if ( moveIndex == rightInsertIndex )
888: {
889: moveSize = insertSize;
890: }
891: else // ( moveIndex > rightInsertIndex )
892: {
893: moveSize = GetRecordSize (btreePtr, rightNode, moveIndex - 1) + 2;
894: }
895:
896: leftSize += moveSize;
897: rightSize -= moveSize;
898: ++moveIndex;
899: }
900:
901: if ( leftSize > nodeSize ) // undo last move
902: {
903: leftSize -= moveSize;
904: rightSize += moveSize;
905: --moveIndex;
906: }
907:
908: if ( rightSize > nodeSize ) // record won't fit - failure, but not error
909: {
910: *insertIndex = 0;
911: *insertNodeNum = 0;
912: *recordFit = false;
913: *recsRotated = 0;
914:
915: return noErr;
916: }
917:
918: // we've found balance point, moveIndex == number of records moved into leftNode
919:
920:
921: //////////////////////////// Rotate Records /////////////////////////////////
922:
923: *recsRotated = moveIndex;
924: *recordFit = true;
925: index = 0;
926:
927: while ( index < moveIndex )
928: {
929: if ( index == rightInsertIndex ) // insert new record in left node
930: {
931: UInt16 leftInsertIndex;
932:
933: leftInsertIndex = leftNode->numRecords;
934:
935: didItFit = InsertKeyRecord (btreePtr, leftNode, leftInsertIndex,
936: keyPtr, keyLength, recPtr, recSize);
937: if ( !didItFit )
938: {
939: Panic ("\pRotateLeft: InsertKeyRecord (left) returned false!");
940: err = fsBTBadRotateErr;
941: goto ErrorExit;
942: }
943:
944: *insertIndex = leftInsertIndex;
945: *insertNodeNum = rightNode->bLink;
946: }
947: else
948: {
949: didItFit = RotateRecordLeft (btreePtr, leftNode, rightNode);
950: if ( !didItFit )
951: {
952: Panic ("\pRotateLeft: RotateRecordLeft returned false!");
953: err = fsBTBadRotateErr;
954: goto ErrorExit;
955: }
956: }
957:
958: ++index;
959: }
960:
961: if ( moveIndex <= rightInsertIndex ) // then insert new record in right node
962: {
963: rightInsertIndex -= index; // adjust for records already rotated
964:
965: didItFit = InsertKeyRecord (btreePtr, rightNode, rightInsertIndex,
966: keyPtr, keyLength, recPtr, recSize);
967: if ( !didItFit )
968: {
969: Panic ("\pRotateLeft: InsertKeyRecord (right) returned false!");
970: err = fsBTBadRotateErr;
971: goto ErrorExit;
972: }
973:
974: *insertIndex = rightInsertIndex;
975: *insertNodeNum = leftNode->fLink;
976: }
977:
978:
979: return noErr;
980:
981:
982: ////////////////////////////// Error Exit ///////////////////////////////////
983:
984: ErrorExit:
985:
986: *insertIndex = 0;
987: *insertNodeNum = 0;
988: *recordFit = false;
989: *recsRotated = 0;
990:
991: return err;
992: }
993:
994:
995:
996: /////////////////////////////////// SplitLeft ///////////////////////////////////
997:
998: static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr,
999: BlockDescriptor *leftNode,
1000: BlockDescriptor *rightNode,
1001: UInt32 rightNodeNum,
1002: UInt16 index,
1003: KeyPtr keyPtr,
1004: UInt8 * recPtr,
1005: UInt16 recSize,
1006: UInt16 *insertIndex,
1007: UInt32 *insertNodeNum,
1008: UInt16 *recsRotated )
1009: {
1010: OSStatus err;
1011: NodeDescPtr left, right;
1012: UInt32 newNodeNum;
1013: Boolean recordFit;
1014:
1015:
1016: ///////////////////////////// Compare Nodes /////////////////////////////////
1017:
1018: right = rightNode->buffer;
1019: left = leftNode->buffer;
1020:
1021: PanicIf ( right->bLink != 0 && left == 0, "\p SplitLeft: left sibling missing!?" );
1022:
1023: //�� type should be kLeafNode or kIndexNode
1024:
1025: if ( (right->height == 1) && (right->type != kLeafNode) )
1026: return fsBTInvalidNodeErr;
1027:
1028: if ( left != nil )
1029: {
1030: if ( left->fLink != rightNodeNum )
1031: return fsBTInvalidNodeErr; //�� E_BadSibling ?
1032:
1033: if ( left->height != right->height )
1034: return fsBTInvalidNodeErr; //�� E_BadNodeHeight ?
1035:
1036: if ( left->type != right->type )
1037: return fsBTInvalidNodeErr; //�� E_BadNodeType ?
1038: }
1039:
1040:
1041: ///////////////////////////// Allocate Node /////////////////////////////////
1042:
1043: err = AllocateNode (btreePtr, &newNodeNum);
1044: M_ExitOnError (err);
1045:
1046:
1047: /////////////// Update Forward Link In Original Left Node ///////////////////
1048:
1049: if ( left != nil )
1050: {
1051: left->fLink = newNodeNum;
1052: err = UpdateNode (btreePtr, leftNode);
1053: M_ExitOnError (err);
1054: }
1055:
1056:
1057: /////////////////////// Initialize New Left Node ////////////////////////////
1058:
1059: err = GetNewNode (btreePtr, newNodeNum, leftNode);
1060: M_ExitOnError (err);
1061:
1062: left = leftNode->buffer;
1063: left->fLink = rightNodeNum;
1064:
1065:
1066: // Steal Info From Right Node
1067:
1068: left->bLink = right->bLink;
1069: left->type = right->type;
1070: left->height = right->height;
1071:
1072: right->bLink = newNodeNum; // update Right bLink
1073:
1074: if ( (left->type == kLeafNode) && (left->bLink == 0) )
1075: {
1076: // if we're adding a new first leaf node - update BTreeInfoRec
1077:
1078: btreePtr->firstLeafNode = newNodeNum;
1079: M_BTreeHeaderDirty (btreePtr); //�� AllocateNode should have set the bit already...
1080: }
1081:
1082: ////////////////////////////// Rotate Left //////////////////////////////////
1083:
1084: err = RotateLeft (btreePtr, left, right, index, keyPtr, recPtr, recSize,
1085: insertIndex, insertNodeNum, &recordFit, recsRotated);
1086: M_ExitOnError (err);
1087:
1088: return noErr;
1089:
1090: ErrorExit:
1091:
1092: (void) ReleaseNode (btreePtr, leftNode);
1093: (void) ReleaseNode (btreePtr, rightNode);
1094:
1095: //�� Free new node if allocated?
1096:
1097: *insertIndex = 0;
1098: *insertNodeNum = 0;
1099: *recsRotated = 0;
1100:
1101: return err;
1102: }
1103:
1104:
1105:
1106: /////////////////////////////// RotateRecordLeft ////////////////////////////////
1107:
1108: static Boolean RotateRecordLeft (BTreeControlBlockPtr btreePtr,
1109: NodeDescPtr leftNode,
1110: NodeDescPtr rightNode )
1111: {
1112: UInt16 size;
1113: UInt8 * recPtr;
1114: Boolean recordFit;
1115:
1116: size = GetRecordSize (btreePtr, rightNode, 0);
1117: recPtr = GetRecordAddress (btreePtr, rightNode, 0);
1118:
1119: recordFit = InsertRecord (btreePtr, leftNode, leftNode->numRecords, recPtr, size);
1120:
1121: if ( !recordFit )
1122: return false;
1123:
1124: DeleteRecord (btreePtr, rightNode, 0);
1125:
1126: return true;
1127: }
1128:
1129:
1130: //////////////////////////////// AddNewRootNode /////////////////////////////////
1131:
1132: static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr,
1133: NodeDescPtr leftNode,
1134: NodeDescPtr rightNode )
1135: {
1136: OSStatus err;
1137: BlockDescriptor rootNode;
1138: UInt32 rootNum;
1139: KeyPtr keyPtr;
1140: Boolean didItFit;
1141: UInt16 keyLength;
1142:
1143: PanicIf (leftNode == nil, "\pAddNewRootNode: leftNode == nil");
1144: PanicIf (rightNode == nil, "\pAddNewRootNode: rightNode == nil");
1145:
1146:
1147: /////////////////////// Initialize New Root Node ////////////////////////////
1148:
1149: err = AllocateNode (btreePtr, &rootNum);
1150: M_ExitOnError (err);
1151:
1152: err = GetNewNode (btreePtr, rootNum, &rootNode);
1153: M_ExitOnError (err);
1154:
1155: ((NodeDescPtr)rootNode.buffer)->type = kIndexNode;
1156: ((NodeDescPtr)rootNode.buffer)->height = ++btreePtr->treeDepth;
1157:
1158:
1159: ///////////////////// Insert Left Node Index Record /////////////////////////
1160:
1161: keyPtr = (KeyPtr) GetRecordAddress (btreePtr, leftNode, 0);
1162: keyLength = GetKeyLength(btreePtr, keyPtr, false);
1163:
1164: didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 0, keyPtr, keyLength,
1165: (UInt8 *) &rightNode->bLink, 4 );
1166:
1167: PanicIf ( !didItFit, "\pAddNewRootNode:InsertKeyRecord failed for left index record");
1168:
1169:
1170: //////////////////// Insert Right Node Index Record /////////////////////////
1171:
1172: keyPtr = (KeyPtr) GetRecordAddress (btreePtr, rightNode, 0);
1173: keyLength = GetKeyLength(btreePtr, keyPtr, false);
1174:
1175: didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 1, keyPtr, keyLength,
1176: (UInt8 *) &leftNode->fLink, 4 );
1177:
1178: PanicIf ( !didItFit, "\pAddNewRootNode:InsertKeyRecord failed for right index record");
1179:
1180:
1181: /////////////////////////// Release Root Node ///////////////////////////////
1182:
1183: err = UpdateNode (btreePtr, &rootNode);
1184: M_ExitOnError (err);
1185:
1186: // update BTreeInfoRec
1187:
1188: btreePtr->rootNode = rootNum;
1189: btreePtr->flags |= kBTHeaderDirty;
1190:
1191: return noErr;
1192:
1193:
1194: ////////////////////////////// Error Exit ///////////////////////////////////
1195:
1196: ErrorExit:
1197:
1198: return err;
1199: }
1200:
1201:
1202: static UInt16 GetKeyLength ( const BTreeControlBlock *btreePtr, const BTreeKey *key, Boolean forLeafNode )
1203: {
1204: UInt16 length;
1205:
1206: if ( forLeafNode || btreePtr->attributes & kBTVariableIndexKeysMask )
1207: length = KeyLength (btreePtr, key); // just use actual key length
1208: else
1209: length = btreePtr->maxKeyLength; // fixed sized index key (i.e. HFS) //�� shouldn't we clear the pad bytes?
1210:
1211: return length;
1212: }
1213:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.