]> git.saurik.com Git - apple/xnu.git/blob - bsd/hfs/hfscommon/BTree/BTreeTreeOps.c
projects / apple / xnu.git / blob
? search:


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