]> 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-201.42.3.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;
198 UInt32 curNodeNum;
199 NodeRec nodeRec;
200 UInt16 index;
201 Boolean keyFound;
202 KeyPtr keyPtr;
203 UInt8 * dataPtr;
204 UInt16 dataSize;
205
206
207 if (btreePtr->treeDepth == 0) // is the tree empty?
208 {
209 err = fsBTEmptyErr;
210 goto ErrorExit;
211 }
212
213 curNodeNum = btreePtr->rootNode;
214
215 //\80\80 for debugging...
216 treePathTable [0].node = 0;
217 treePathTable [0].index = 0;
218
219 while (true)
220 {
221 PanicIf(curNodeNum == 0, "\pSearchTree: curNodeNum is zero!");
222
223 err = GetNode (btreePtr, curNodeNum, &nodeRec);
224 if (err != noErr)
225 {
226 goto ErrorExit;
227 }
228
229 keyFound = SearchNode (btreePtr, nodeRec.buffer, searchKey, &index);
230
231 level = ((BTNodeDescriptor*)nodeRec.buffer)->height; //\80\80 or --level;
232
233
234 treePathTable [level].node = curNodeNum;
235
236 if ( ((BTNodeDescriptor*)nodeRec.buffer)->kind == kBTLeafNode)
237 {
238 treePathTable [level].index = index;
239 break; // were done...
240 }
241
242 if ( (keyFound != true) && (index != 0))
243 --index;
244
245 treePathTable [level].index = index;
246
247 GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize);
248 curNodeNum = *(UInt32 *)dataPtr;
249 err = ReleaseNode (btreePtr, &nodeRec);
250 if (err != noErr)
251 {
252 goto ErrorExit;
253 }
254 }
255
256 *nodeNum = curNodeNum;
257 *nodePtr = nodeRec;
258 *returnIndex = index;
259
260 if (keyFound)
261 return noErr; // searchKey found, index identifies record in node
262 else
263 return fsBTRecordNotFoundErr; // searchKey not found, index identifies insert point
264
265 ErrorExit:
266
267 *nodeNum = 0;
268 nodePtr->buffer = nil;
269 nodePtr->blockHeader = nil;
270 *returnIndex = 0;
271
272 return err;
273 }
274
275
276
277
278 ////////////////////////////////// InsertTree ///////////////////////////////////
279
280 OSStatus InsertTree ( BTreeControlBlockPtr btreePtr,
281 TreePathTable treePathTable,
282 KeyPtr keyPtr,
283 UInt8 * recPtr,
284 UInt16 recSize,
285 BlockDescriptor *targetNode,
286 UInt16 index,
287 UInt16 level,
288 Boolean replacingKey,
289 UInt32 *insertNode )
290 {
291 InsertKey primaryKey;
292 OSStatus err;
293
294 primaryKey.keyPtr = keyPtr;
295 primaryKey.keyLength = GetKeyLength(btreePtr, primaryKey.keyPtr, (level == 1));
296 primaryKey.recPtr = recPtr;
297 primaryKey.recSize = recSize;
298 primaryKey.replacingKey = replacingKey;
299 primaryKey.skipRotate = false;
300
301 err = InsertLevel (btreePtr, treePathTable, &primaryKey, nil,
302 targetNode, index, level, insertNode );
303
304 return err;
305
306 } // End of InsertTree
307
308
309 ////////////////////////////////// InsertLevel //////////////////////////////////
310
311 OSStatus InsertLevel (BTreeControlBlockPtr btreePtr,
312 TreePathTable treePathTable,
313 InsertKey *primaryKey,
314 InsertKey *secondaryKey,
315 BlockDescriptor *targetNode,
316 UInt16 index,
317 UInt16 level,
318 UInt32 *insertNode )
319 {
320 OSStatus err;
321 BlockDescriptor leftNode;
322 UInt32 targetNodeNum;
323 UInt32 newNodeNum;
324 UInt16 newIndex;
325 Boolean insertParent;
326 Boolean updateParent;
327 Boolean newRoot;
328
329 #if defined(applec) && !defined(__SC__)
330 PanicIf ((level == 1) && (((NodeDescPtr)targetNode->buffer)->kind != kBTLeafNode), "\P InsertLevel: non-leaf at level 1! ");
331 #endif
332 leftNode.buffer = nil;
333 targetNodeNum = treePathTable [level].node;
334
335 insertParent = false;
336 updateParent = false;
337
338 ////// process first insert //////
339
340 err = InsertNode (btreePtr, primaryKey, targetNode, targetNodeNum, index,
341 &newNodeNum, &newIndex, &leftNode, &updateParent, &insertParent, &newRoot );
342 M_ExitOnError (err);
343
344 if ( newRoot )
345 {
346 // Extend the treePathTable by adding an entry for the new
347 // root node that references the current targetNode.
348 //
349 // If inserting the secondaryKey changes the first key of
350 // the target node, then we'll have to update the second
351 // key in the new root node.
352
353 treePathTable [level + 1].node = btreePtr->rootNode;
354 treePathTable [level + 1].index = 1; // 1 since we always split/rotate left
355 }
356
357 if ( level == 1 )
358 *insertNode = newNodeNum;
359
360 ////// process second insert (if any) //////
361
362 if ( secondaryKey != nil )
363 {
364 Boolean temp;
365
366 err = InsertNode (btreePtr, secondaryKey, targetNode, newNodeNum, newIndex,
367 &newNodeNum, &newIndex, &leftNode, &updateParent, &insertParent, &temp);
368 M_ExitOnError (err);
369
370 if ( DEBUG_BUILD && updateParent && newRoot )
371 DebugStr("\p InsertLevel: New root from primary key, update from secondary key...");
372 }
373
374 //////////////////////// Update Parent(s) ///////////////////////////////
375
376 if ( insertParent || updateParent )
377 {
378 BlockDescriptor parentNode;
379 UInt32 parentNodeNum;
380 KeyPtr keyPtr;
381 UInt8 * recPtr;
382 UInt16 recSize;
383
384 secondaryKey = nil;
385
386 PanicIf ( (level == btreePtr->treeDepth), "\p InsertLevel: unfinished insert!?");
387
388 ++level;
389
390 // Get Parent Node data...
391 index = treePathTable [level].index;
392 parentNodeNum = treePathTable [level].node;
393
394 PanicIf ( parentNodeNum == 0, "\p InsertLevel: parent node is zero!?");
395
396 err = GetNode (btreePtr, parentNodeNum, &parentNode); // released as target node in next level up
397 M_ExitOnError (err);
398 #if defined(applec) && !defined(__SC__)
399 if (DEBUG_BUILD && level > 1)
400 PanicIf ( ((NodeDescPtr)parentNode.buffer)->kind != kBTIndexNode, "\P InsertLevel: parent node not an index node! ");
401 #endif
402 ////////////////////////// Update Parent Index //////////////////////////////
403
404 if ( updateParent )
405 {
406 //\80\80 debug: check if ptr == targetNodeNum
407 GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
408 PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p InsertLevel: parent ptr doesn't match target node!");
409
410 // need to delete and re-insert this parent key/ptr
411 // we delete it here and it gets re-inserted in the
412 // InsertLevel call below.
413 DeleteRecord (btreePtr, parentNode.buffer, index);
414
415 primaryKey->keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
416 primaryKey->keyLength = GetKeyLength(btreePtr, primaryKey->keyPtr, false);
417 primaryKey->recPtr = (UInt8 *) &targetNodeNum;
418 primaryKey->recSize = sizeof(targetNodeNum);
419 primaryKey->replacingKey = kReplaceRecord;
420 primaryKey->skipRotate = insertParent; // don't rotate left if we have two inserts occuring
421 }
422
423 ////////////////////////// Add New Parent Index /////////////////////////////
424
425 if ( insertParent )
426 {
427 InsertKey *insertKeyPtr;
428 InsertKey insertKey;
429
430 if ( updateParent )
431 {
432 insertKeyPtr = &insertKey;
433 secondaryKey = &insertKey;
434 }
435 else
436 {
437 insertKeyPtr = primaryKey;
438 }
439
440 insertKeyPtr->keyPtr = (KeyPtr) GetRecordAddress (btreePtr, leftNode.buffer, 0);
441 insertKeyPtr->keyLength = GetKeyLength(btreePtr, insertKeyPtr->keyPtr, false);
442 insertKeyPtr->recPtr = (UInt8 *) &((NodeDescPtr)targetNode->buffer)->bLink;
443 insertKeyPtr->recSize = sizeof(UInt32);
444 insertKeyPtr->replacingKey = kInsertRecord;
445 insertKeyPtr->skipRotate = false; // a rotate is OK during second insert
446 }
447
448 err = InsertLevel (btreePtr, treePathTable, primaryKey, secondaryKey,
449 &parentNode, index, level, insertNode );
450 M_ExitOnError (err);
451 }
452
453 err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction); // all done with target
454 M_ExitOnError (err);
455
456 err = UpdateNode (btreePtr, &leftNode, 0, kLockTransaction); // all done with left sibling
457 M_ExitOnError (err);
458
459 return noErr;
460
461 ErrorExit:
462
463 (void) ReleaseNode (btreePtr, targetNode);
464 (void) ReleaseNode (btreePtr, &leftNode);
465
466 Panic ("\p InsertLevel: an error occured!");
467
468 return err;
469
470 } // End of InsertLevel
471
472
473
474 ////////////////////////////////// InsertNode ///////////////////////////////////
475
476 static OSErr InsertNode (BTreeControlBlockPtr btreePtr,
477 InsertKey *key,
478
479 BlockDescriptor *rightNode,
480 UInt32 node,
481 UInt16 index,
482
483 UInt32 *newNode,
484 UInt16 *newIndex,
485
486 BlockDescriptor *leftNode,
487 Boolean *updateParent,
488 Boolean *insertParent,
489 Boolean *rootSplit )
490 {
491 BlockDescriptor *targetNode;
492 UInt32 leftNodeNum;
493 UInt16 recsRotated;
494 OSErr err;
495 Boolean recordFit;
496
497 *rootSplit = false;
498
499 PanicIf ( rightNode->buffer == leftNode->buffer, "\p InsertNode: rightNode == leftNode, huh?");
500
501 leftNodeNum = ((NodeDescPtr) rightNode->buffer)->bLink;
502
503
504 /////////////////////// Try Simple Insert ///////////////////////////////
505
506 if ( node == leftNodeNum )
507 targetNode = leftNode;
508 else
509 targetNode = rightNode;
510
511 recordFit = InsertKeyRecord (btreePtr, targetNode->buffer, index, key->keyPtr, key->keyLength, key->recPtr, key->recSize);
512
513 if ( recordFit )
514 {
515 *newNode = node;
516 *newIndex = index;
517
518 if ( (index == 0) && (((NodeDescPtr) targetNode->buffer)->height != btreePtr->treeDepth) )
519 *updateParent = true; // the first record changed so we need to update the parent
520 }
521
522
523 //////////////////////// Try Rotate Left ////////////////////////////////
524
525 if ( !recordFit && leftNodeNum > 0 )
526 {
527 PanicIf ( leftNode->buffer != nil, "\p InsertNode: leftNode already aquired!");
528
529 if ( leftNode->buffer == nil )
530 {
531 err = GetNode (btreePtr, leftNodeNum, leftNode); // will be released by caller or a split below
532 M_ExitOnError (err);
533 }
534
535 PanicIf ( ((NodeDescPtr) leftNode->buffer)->fLink != node, "\p InsertNode, RotateLeft: invalid sibling link!" );
536
537 if ( !key->skipRotate ) // are rotates allowed?
538 {
539 err = RotateLeft (btreePtr, leftNode->buffer, rightNode->buffer, index, key->keyPtr, key->recPtr,
540 key->recSize, newIndex, newNode, &recordFit, &recsRotated );
541 M_ExitOnError (err);
542
543 if ( recordFit )
544 {
545 if ( key->replacingKey || (recsRotated > 1) || (index > 0) )
546 *updateParent = true;
547 }
548 }
549 }
550
551
552 //////////////////////// Try Split Left /////////////////////////////////
553
554 if ( !recordFit )
555 {
556 // might not have left node...
557 err = SplitLeft (btreePtr, leftNode, rightNode, node, index, key->keyPtr,
558 key->recPtr, key->recSize, newIndex, newNode, &recsRotated);
559 M_ExitOnError (err);
560
561 // if we split root node - add new root
562
563 if ( ((NodeDescPtr) rightNode->buffer)->height == btreePtr->treeDepth )
564 {
565 err = AddNewRootNode (btreePtr, leftNode->buffer, rightNode->buffer); // Note: does not update TPT
566 M_ExitOnError (err);
567 *rootSplit = true;
568 }
569 else
570 {
571 *insertParent = true;
572
573 if ( key->replacingKey || (recsRotated > 1) || (index > 0) )
574 *updateParent = true;
575 }
576 }
577
578 return noErr;
579
580 ErrorExit:
581
582 (void) ReleaseNode (btreePtr, leftNode);
583 return err;
584
585 } // End of InsertNode
586
587
588 /*-------------------------------------------------------------------------------
589 Routine: DeleteTree - One_line_description.
590
591 Function: Brief_description_of_the_function_and_any_side_effects
592
593 ToDo:
594
595 Input: btreePtr - description
596 treePathTable - description
597 targetNode - description
598 index - description
599
600 Result: noErr - success
601 != noErr - failure
602 -------------------------------------------------------------------------------*/
603
604 OSStatus DeleteTree (BTreeControlBlockPtr btreePtr,
605 TreePathTable treePathTable,
606 BlockDescriptor *targetNode,
607 UInt16 index,
608 UInt16 level )
609 {
610 OSStatus err;
611 BlockDescriptor parentNode;
612 BTNodeDescriptor *targetNodePtr;
613 UInt32 targetNodeNum;
614 Boolean deleteRequired;
615 Boolean updateRequired;
616
617
618 deleteRequired = false;
619 updateRequired = false;
620
621 targetNodeNum = treePathTable[level].node;
622 targetNodePtr = targetNode->buffer;
623 PanicIf (targetNodePtr == nil, "\pDeleteTree: targetNode has nil buffer!");
624
625 DeleteRecord (btreePtr, targetNodePtr, index);
626
627 //\80\80 coalesce remaining records?
628
629 if ( targetNodePtr->numRecords == 0 ) // did we delete the last record?
630 {
631 BlockDescriptor siblingNode;
632 UInt32 siblingNodeNum;
633
634 deleteRequired = true;
635
636 ////////////////// Get Siblings & Update Links //////////////////////////
637
638 siblingNodeNum = targetNodePtr->bLink; // Left Sibling Node
639 if ( siblingNodeNum != 0 )
640 {
641 err = GetNode (btreePtr, siblingNodeNum, &siblingNode);
642 M_ExitOnError (err);
643 ((NodeDescPtr)siblingNode.buffer)->fLink = targetNodePtr->fLink;
644 err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction);
645 M_ExitOnError (err);
646 }
647 else if ( targetNodePtr->kind == kBTLeafNode ) // update firstLeafNode
648 {
649 btreePtr->firstLeafNode = targetNodePtr->fLink;
650 }
651
652 siblingNodeNum = targetNodePtr->fLink; // Right Sibling Node
653 if ( siblingNodeNum != 0 )
654 {
655 err = GetNode (btreePtr, siblingNodeNum, &siblingNode);
656 M_ExitOnError (err);
657 ((NodeDescPtr)siblingNode.buffer)->bLink = targetNodePtr->bLink;
658 err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction);
659 M_ExitOnError (err);
660 }
661 else if ( targetNodePtr->kind == kBTLeafNode ) // update lastLeafNode
662 {
663 btreePtr->lastLeafNode = targetNodePtr->bLink;
664 }
665
666 //////////////////////// Free Empty Node ////////////////////////////////
667
668 ClearNode (btreePtr, targetNodePtr);
669
670 err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction);
671 M_ExitOnError (err);
672 err = FreeNode (btreePtr, targetNodeNum);
673 M_ExitOnError (err);
674 }
675 else if ( index == 0 ) // did we delete the first record?
676 {
677 updateRequired = true; // yes, so we need to update parent
678 }
679
680
681 if ( level == btreePtr->treeDepth ) // then targetNode->buffer is the root node
682 {
683 deleteRequired = false;
684 updateRequired = false;
685
686 if ( targetNode->buffer == nil ) // then root was freed and the btree is empty
687 {
688 btreePtr->rootNode = 0;
689 btreePtr->treeDepth = 0;
690 }
691 else if ( ((NodeDescPtr)targetNode->buffer)->numRecords == 1 )
692 {
693 err = CollapseTree (btreePtr, targetNode);
694 M_ExitOnError (err);
695 }
696 }
697
698
699 if ( updateRequired || deleteRequired )
700 {
701 ++level; // next level
702
703 //// Get Parent Node and index
704 index = treePathTable [level].index;
705 err = GetNode (btreePtr, treePathTable[level].node, &parentNode);
706 M_ExitOnError (err);
707
708 if ( updateRequired )
709 {
710 KeyPtr keyPtr;
711 UInt8 * recPtr;
712 UInt16 recSize;
713 UInt32 insertNode;
714
715 //\80\80 debug: check if ptr == targetNodeNum
716 GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
717 PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p DeleteTree: parent ptr doesn't match targetNodeNum!!");
718
719 // need to delete and re-insert this parent key/ptr
720 DeleteRecord (btreePtr, parentNode.buffer, index);
721
722 keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
723 recPtr = (UInt8 *) &targetNodeNum;
724 recSize = sizeof(targetNodeNum);
725
726 err = InsertTree (btreePtr, treePathTable, keyPtr, recPtr, recSize,
727 &parentNode, index, level, kReplaceRecord, &insertNode);
728 M_ExitOnError (err);
729 }
730 else // deleteRequired
731 {
732 err = DeleteTree (btreePtr, treePathTable, &parentNode, index, level);
733 M_ExitOnError (err);
734 }
735 }
736
737
738 err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction);
739 M_ExitOnError (err);
740
741 return noErr;
742
743 ErrorExit:
744
745 (void) ReleaseNode (btreePtr, targetNode);
746 (void) ReleaseNode (btreePtr, &parentNode);
747
748 return err;
749
750 } // end DeleteTree
751
752
753
754 ///////////////////////////////// CollapseTree //////////////////////////////////
755
756 static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr,
757 BlockDescriptor *blockPtr )
758 {
759 OSStatus err;
760 UInt32 originalRoot;
761 UInt32 nodeNum;
762
763 originalRoot = btreePtr->rootNode;
764
765 while (true)
766 {
767 if ( ((NodeDescPtr)blockPtr->buffer)->numRecords > 1)
768 break; // this will make a fine root node
769
770 if ( ((NodeDescPtr)blockPtr->buffer)->kind == kBTLeafNode)
771 break; // we've hit bottom
772
773 nodeNum = btreePtr->rootNode;
774 btreePtr->rootNode = GetChildNodeNum (btreePtr, blockPtr->buffer, 0);
775 --btreePtr->treeDepth;
776
777 //// Clear and Free Current Old Root Node ////
778 ClearNode (btreePtr, blockPtr->buffer);
779 err = UpdateNode (btreePtr, blockPtr, 0, kLockTransaction);
780 M_ExitOnError (err);
781 err = FreeNode (btreePtr, nodeNum);
782 M_ExitOnError (err);
783
784 //// Get New Root Node
785 err = GetNode (btreePtr, btreePtr->rootNode, blockPtr);
786 M_ExitOnError (err);
787 }
788
789 if (btreePtr->rootNode != originalRoot)
790 M_BTreeHeaderDirty (btreePtr);
791
792 err = UpdateNode (btreePtr, blockPtr, 0, kLockTransaction); // always update!
793 M_ExitOnError (err);
794
795 return noErr;
796
797
798 /////////////////////////////////// ErrorExit ///////////////////////////////////
799
800 ErrorExit:
801 (void) ReleaseNode (btreePtr, blockPtr);
802 return err;
803 }
804
805
806
807 ////////////////////////////////// RotateLeft ///////////////////////////////////
808
809 /*-------------------------------------------------------------------------------
810
811 Routine: RotateLeft - One_line_description.
812
813 Function: Brief_description_of_the_function_and_any_side_effects
814
815 Algorithm: if rightIndex > insertIndex, subtract 1 for actual rightIndex
816
817 Input: btreePtr - description
818 leftNode - description
819 rightNode - description
820 rightInsertIndex - description
821 keyPtr - description
822 recPtr - description
823 recSize - description
824
825 Output: insertIndex
826 insertNodeNum - description
827 recordFit - description
828 recsRotated
829
830 Result: noErr - success
831 != noErr - failure
832 -------------------------------------------------------------------------------*/
833
834 static OSStatus RotateLeft (BTreeControlBlockPtr btreePtr,
835 NodeDescPtr leftNode,
836 NodeDescPtr rightNode,
837 UInt16 rightInsertIndex,
838 KeyPtr keyPtr,
839 UInt8 * recPtr,
840 UInt16 recSize,
841 UInt16 *insertIndex,
842 UInt32 *insertNodeNum,
843 Boolean *recordFit,
844 UInt16 *recsRotated )
845 {
846 OSStatus err;
847 SInt32 insertSize;
848 SInt32 nodeSize;
849 SInt32 leftSize, rightSize;
850 SInt32 moveSize = 0;
851 UInt16 keyLength;
852 UInt16 lengthFieldSize;
853 UInt16 index, moveIndex;
854 Boolean didItFit;
855
856 ///////////////////// Determine If Record Will Fit //////////////////////////
857
858 keyLength = GetKeyLength(btreePtr, keyPtr, (rightNode->kind == kBTLeafNode));
859
860 // the key's length field is 8-bits in HFS and 16-bits in HFS+
861 if ( btreePtr->attributes & kBTBigKeysMask )
862 lengthFieldSize = sizeof(UInt16);
863 else
864 lengthFieldSize = sizeof(UInt8);
865
866 insertSize = keyLength + lengthFieldSize + recSize + sizeof(UInt16);
867
868 if ( M_IsOdd (insertSize) )
869 ++insertSize; // add pad byte;
870
871 nodeSize = btreePtr->nodeSize;
872
873 // add size of insert record to right node
874 rightSize = nodeSize - GetNodeFreeSize (btreePtr, rightNode) + insertSize;
875 leftSize = nodeSize - GetNodeFreeSize (btreePtr, leftNode);
876
877 moveIndex = 0;
878
879 while ( leftSize < rightSize )
880 {
881 if ( moveIndex < rightInsertIndex )
882 {
883 moveSize = GetRecordSize (btreePtr, rightNode, moveIndex) + 2;
884 }
885 else if ( moveIndex == rightInsertIndex )
886 {
887 moveSize = insertSize;
888 }
889 else // ( moveIndex > rightInsertIndex )
890 {
891 moveSize = GetRecordSize (btreePtr, rightNode, moveIndex - 1) + 2;
892 }
893
894 leftSize += moveSize;
895 rightSize -= moveSize;
896 ++moveIndex;
897 }
898
899 if ( leftSize > nodeSize ) // undo last move
900 {
901 leftSize -= moveSize;
902 rightSize += moveSize;
903 --moveIndex;
904 }
905
906 if ( rightSize > nodeSize ) // record won't fit - failure, but not error
907 {
908 *insertIndex = 0;
909 *insertNodeNum = 0;
910 *recordFit = false;
911 *recsRotated = 0;
912
913 return noErr;
914 }
915
916 // we've found balance point, moveIndex == number of records moved into leftNode
917
918
919 //////////////////////////// Rotate Records /////////////////////////////////
920
921 *recsRotated = moveIndex;
922 *recordFit = true;
923 index = 0;
924
925 while ( index < moveIndex )
926 {
927 if ( index == rightInsertIndex ) // insert new record in left node
928 {
929 UInt16 leftInsertIndex;
930
931 leftInsertIndex = leftNode->numRecords;
932
933 didItFit = InsertKeyRecord (btreePtr, leftNode, leftInsertIndex,
934 keyPtr, keyLength, recPtr, recSize);
935 if ( !didItFit )
936 {
937 Panic ("\pRotateLeft: InsertKeyRecord (left) returned false!");
938 err = fsBTBadRotateErr;
939 goto ErrorExit;
940 }
941
942 *insertIndex = leftInsertIndex;
943 *insertNodeNum = rightNode->bLink;
944 }
945 else
946 {
947 didItFit = RotateRecordLeft (btreePtr, leftNode, rightNode);
948 if ( !didItFit )
949 {
950 Panic ("\pRotateLeft: RotateRecordLeft returned false!");
951 err = fsBTBadRotateErr;
952 goto ErrorExit;
953 }
954 }
955
956 ++index;
957 }
958
959 if ( moveIndex <= rightInsertIndex ) // then insert new record in right node
960 {
961 rightInsertIndex -= index; // adjust for records already rotated
962
963 didItFit = InsertKeyRecord (btreePtr, rightNode, rightInsertIndex,
964 keyPtr, keyLength, recPtr, recSize);
965 if ( !didItFit )
966 {
967 Panic ("\pRotateLeft: InsertKeyRecord (right) returned false!");
968 err = fsBTBadRotateErr;
969 goto ErrorExit;
970 }
971
972 *insertIndex = rightInsertIndex;
973 *insertNodeNum = leftNode->fLink;
974 }
975
976
977 return noErr;
978
979
980 ////////////////////////////// Error Exit ///////////////////////////////////
981
982 ErrorExit:
983
984 *insertIndex = 0;
985 *insertNodeNum = 0;
986 *recordFit = false;
987 *recsRotated = 0;
988
989 return err;
990 }
991
992
993
994 /////////////////////////////////// SplitLeft ///////////////////////////////////
995
996 static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr,
997 BlockDescriptor *leftNode,
998 BlockDescriptor *rightNode,
999 UInt32 rightNodeNum,
1000 UInt16 index,
1001 KeyPtr keyPtr,
1002 UInt8 * recPtr,
1003 UInt16 recSize,
1004 UInt16 *insertIndex,
1005 UInt32 *insertNodeNum,
1006 UInt16 *recsRotated )
1007 {
1008 OSStatus err;
1009 NodeDescPtr left, right;
1010 UInt32 newNodeNum;
1011 Boolean recordFit;
1012
1013
1014 ///////////////////////////// Compare Nodes /////////////////////////////////
1015
1016 right = rightNode->buffer;
1017 left = leftNode->buffer;
1018
1019 PanicIf ( right->bLink != 0 && left == 0, "\p SplitLeft: left sibling missing!?" );
1020
1021 /* type should be kBTLeafNode or kBTIndexNode */
1022
1023 if ( (right->height == 1) && (right->kind != kBTLeafNode) )
1024 return fsBTInvalidNodeErr;
1025
1026 if ( left != nil )
1027 {
1028 if ( left->fLink != rightNodeNum )
1029 return fsBTInvalidNodeErr; //\80\80 E_BadSibling ?
1030
1031 if ( left->height != right->height )
1032 return fsBTInvalidNodeErr; //\80\80 E_BadNodeHeight ?
1033
1034 if ( left->kind != right->kind )
1035 return fsBTInvalidNodeErr; //\80\80 E_BadNodeType ?
1036 }
1037
1038
1039 ///////////////////////////// Allocate Node /////////////////////////////////
1040
1041 err = AllocateNode (btreePtr, &newNodeNum);
1042 M_ExitOnError (err);
1043
1044
1045 /////////////// Update Forward Link In Original Left Node ///////////////////
1046
1047 if ( left != nil )
1048 {
1049 left->fLink = newNodeNum;
1050 err = UpdateNode (btreePtr, leftNode, 0, kLockTransaction);
1051 M_ExitOnError (err);
1052 }
1053
1054
1055 /////////////////////// Initialize New Left Node ////////////////////////////
1056
1057 err = GetNewNode (btreePtr, newNodeNum, leftNode);
1058 M_ExitOnError (err);
1059
1060 left = leftNode->buffer;
1061 left->fLink = rightNodeNum;
1062
1063
1064 // Steal Info From Right Node
1065
1066 left->bLink = right->bLink;
1067 left->kind = right->kind;
1068 left->height = right->height;
1069
1070 right->bLink = newNodeNum; // update Right bLink
1071
1072 if ( (left->kind == kBTLeafNode) && (left->bLink == 0) )
1073 {
1074 // if we're adding a new first leaf node - update BTreeInfoRec
1075
1076 btreePtr->firstLeafNode = newNodeNum;
1077 M_BTreeHeaderDirty (btreePtr); //\80\80 AllocateNode should have set the bit already...
1078 }
1079
1080 ////////////////////////////// Rotate Left //////////////////////////////////
1081
1082 err = RotateLeft (btreePtr, left, right, index, keyPtr, recPtr, recSize,
1083 insertIndex, insertNodeNum, &recordFit, recsRotated);
1084 M_ExitOnError (err);
1085
1086 return noErr;
1087
1088 ErrorExit:
1089
1090 (void) ReleaseNode (btreePtr, leftNode);
1091 (void) ReleaseNode (btreePtr, rightNode);
1092
1093 //\80\80 Free new node if allocated?
1094
1095 *insertIndex = 0;
1096 *insertNodeNum = 0;
1097 *recsRotated = 0;
1098
1099 return err;
1100 }
1101
1102
1103
1104 /////////////////////////////// RotateRecordLeft ////////////////////////////////
1105
1106 static Boolean RotateRecordLeft (BTreeControlBlockPtr btreePtr,
1107 NodeDescPtr leftNode,
1108 NodeDescPtr rightNode )
1109 {
1110 UInt16 size;
1111 UInt8 * recPtr;
1112 Boolean recordFit;
1113
1114 size = GetRecordSize (btreePtr, rightNode, 0);
1115 recPtr = GetRecordAddress (btreePtr, rightNode, 0);
1116
1117 recordFit = InsertRecord (btreePtr, leftNode, leftNode->numRecords, recPtr, size);
1118
1119 if ( !recordFit )
1120 return false;
1121
1122 DeleteRecord (btreePtr, rightNode, 0);
1123
1124 return true;
1125 }
1126
1127
1128 //////////////////////////////// AddNewRootNode /////////////////////////////////
1129
1130 static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr,
1131 NodeDescPtr leftNode,
1132 NodeDescPtr rightNode )
1133 {
1134 OSStatus err;
1135 BlockDescriptor rootNode;
1136 UInt32 rootNum;
1137 KeyPtr keyPtr;
1138 Boolean didItFit;
1139 UInt16 keyLength;
1140
1141 PanicIf (leftNode == nil, "\pAddNewRootNode: leftNode == nil");
1142 PanicIf (rightNode == nil, "\pAddNewRootNode: rightNode == nil");
1143
1144
1145 /////////////////////// Initialize New Root Node ////////////////////////////
1146
1147 err = AllocateNode (btreePtr, &rootNum);
1148 M_ExitOnError (err);
1149
1150 err = GetNewNode (btreePtr, rootNum, &rootNode);
1151 M_ExitOnError (err);
1152
1153 ((NodeDescPtr)rootNode.buffer)->kind = kBTIndexNode;
1154 ((NodeDescPtr)rootNode.buffer)->height = ++btreePtr->treeDepth;
1155
1156
1157 ///////////////////// Insert Left Node Index Record /////////////////////////
1158
1159 keyPtr = (KeyPtr) GetRecordAddress (btreePtr, leftNode, 0);
1160 keyLength = GetKeyLength(btreePtr, keyPtr, false);
1161
1162 didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 0, keyPtr, keyLength,
1163 (UInt8 *) &rightNode->bLink, 4 );
1164
1165 PanicIf ( !didItFit, "\pAddNewRootNode:InsertKeyRecord failed for left index record");
1166
1167
1168 //////////////////// Insert Right Node Index Record /////////////////////////
1169
1170 keyPtr = (KeyPtr) GetRecordAddress (btreePtr, rightNode, 0);
1171 keyLength = GetKeyLength(btreePtr, keyPtr, false);
1172
1173 didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 1, keyPtr, keyLength,
1174 (UInt8 *) &leftNode->fLink, 4 );
1175
1176 PanicIf ( !didItFit, "\pAddNewRootNode:InsertKeyRecord failed for right index record");
1177
1178
1179 /////////////////////////// Release Root Node ///////////////////////////////
1180
1181 err = UpdateNode (btreePtr, &rootNode, 0, kLockTransaction);
1182 M_ExitOnError (err);
1183
1184 // update BTreeInfoRec
1185
1186 btreePtr->rootNode = rootNum;
1187 btreePtr->flags |= kBTHeaderDirty;
1188
1189 return noErr;
1190
1191
1192 ////////////////////////////// Error Exit ///////////////////////////////////
1193
1194 ErrorExit:
1195
1196 return err;
1197 }
1198
1199
1200 static UInt16 GetKeyLength ( const BTreeControlBlock *btreePtr, const BTreeKey *key, Boolean forLeafNode )
1201 {
1202 UInt16 length;
1203
1204 if ( forLeafNode || btreePtr->attributes & kBTVariableIndexKeysMask )
1205 length = KeyLength (btreePtr, key); // just use actual key length
1206 else
1207 length = btreePtr->maxKeyLength; // fixed sized index key (i.e. HFS) //\80\80 shouldn't we clear the pad bytes?
1208
1209 return length;
1210 }
1211
mirror of XNU