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