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