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