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