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