]> git.saurik.com Git - apple/hfs.git/blob - core/BTreeTreeOps.c
projects / apple / hfs.git / blob
? search:


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