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