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