]> 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-3248.60.10.tar.gz
[apple/xnu.git] / bsd / hfs / hfscommon / BTree / BTreeTreeOps.c
1 /*
2 * Copyright (c) 2000-2014 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("SearchTree: 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("Incorrect 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("Incorrect 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("Incorrect 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), " 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(" 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), " 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, " 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, " 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, " 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 (" 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 = NULL;
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, " InsertNode: rightNode == leftNode, huh?");
581
582 leftNodeNum = ((NodeDescPtr) rightNode->buffer)->bLink;
583
584
585 /////////////////////// Try Simple Insert ///////////////////////////////
586
587 /* sanity check our left and right nodes here. */
588 if (node == leftNodeNum) {
589 if (leftNode->buffer == NULL) {
590 err = fsBTInvalidNodeErr;
591 M_ExitOnError(err);
592 }
593 else{
594 targetNode = leftNode;
595 }
596 }
597 else {
598 // we can assume right node is initialized.
599 targetNode = rightNode;
600 }
601
602
603 recordFit = InsertKeyRecord (btreePtr, targetNode->buffer, index, key->keyPtr, key->keyLength, key->recPtr, key->recSize);
604
605 if ( recordFit )
606 {
607 *newNode = node;
608 *newIndex = index;
609
610 if ( (index == 0) && (((NodeDescPtr) targetNode->buffer)->height != btreePtr->treeDepth) )
611 *updateParent = true; // the first record changed so we need to update the parent
612 }
613
614
615 //////////////////////// Try Rotate Left ////////////////////////////////
616
617 if ( !recordFit && leftNodeNum > 0 )
618 {
619 PanicIf ( leftNode->buffer != nil, " InsertNode: leftNode already acquired!");
620
621 if ( leftNode->buffer == nil )
622 {
623 err = GetNode (btreePtr, leftNodeNum, 0, leftNode); // will be released by caller or a split below
624 M_ExitOnError (err);
625 // XXXdbg
626 ModifyBlockStart(btreePtr->fileRefNum, leftNode);
627 }
628
629 PanicIf ( ((NodeDescPtr) leftNode->buffer)->fLink != node, " InsertNode, RotateLeft: invalid sibling link!" );
630
631 if ( !key->skipRotate ) // are rotates allowed?
632 {
633 err = RotateLeft (btreePtr, leftNode->buffer, rightNode->buffer, index, key->keyPtr, key->recPtr,
634 key->recSize, newIndex, newNode, &recordFit, &recsRotated );
635 M_ExitOnError (err);
636
637 if ( recordFit )
638 {
639 if ( key->replacingKey || (recsRotated > 1) || (index > 0) )
640 *updateParent = true;
641 }
642 }
643 }
644
645
646 //////////////////////// Try Split Left /////////////////////////////////
647
648 if ( !recordFit )
649 {
650 // might not have left node...
651 err = SplitLeft (btreePtr, leftNode, rightNode, node, index, key->keyPtr,
652 key->recPtr, key->recSize, newIndex, newNode, &recsRotated);
653 M_ExitOnError (err);
654
655 // if we split root node - add new root
656
657 if ( ((NodeDescPtr) rightNode->buffer)->height == btreePtr->treeDepth )
658 {
659 err = AddNewRootNode (btreePtr, leftNode->buffer, rightNode->buffer); // Note: does not update TPT
660 M_ExitOnError (err);
661 *rootSplit = true;
662 }
663 else
664 {
665 *insertParent = true;
666
667 if ( key->replacingKey || (recsRotated > 1) || (index > 0) )
668 *updateParent = true;
669 }
670 }
671
672 return noErr;
673
674 ErrorExit:
675 (void) ReleaseNode (btreePtr, leftNode);
676 return err;
677
678 } // End of InsertNode
679
680
681 /*-------------------------------------------------------------------------------
682 Routine: DeleteTree - One_line_description.
683
684 Function: Brief_description_of_the_function_and_any_side_effects
685
686 ToDo:
687
688 Input: btreePtr - description
689 treePathTable - description
690 targetNode - description
691 index - description
692
693 Result: noErr - success
694 != noErr - failure
695 -------------------------------------------------------------------------------*/
696
697 OSStatus DeleteTree (BTreeControlBlockPtr btreePtr,
698 TreePathTable treePathTable,
699 BlockDescriptor *targetNode,
700 u_int16_t index,
701 u_int16_t level )
702 {
703 OSStatus err;
704 BlockDescriptor parentNode;
705 BTNodeDescriptor *targetNodePtr;
706 u_int32_t targetNodeNum;
707 Boolean deleteRequired;
708 Boolean updateRequired;
709
710 // XXXdbg - initialize these to null in case we get an
711 // error and try to exit before it's initialized
712 parentNode.buffer = nil;
713 parentNode.blockHeader = nil;
714
715 deleteRequired = false;
716 updateRequired = false;
717
718 targetNodeNum = treePathTable[level].node;
719 targetNodePtr = targetNode->buffer;
720 PanicIf (targetNodePtr == nil, "DeleteTree: targetNode has nil buffer!");
721
722 // XXXdbg
723 ModifyBlockStart(btreePtr->fileRefNum, targetNode);
724
725 DeleteRecord (btreePtr, targetNodePtr, index);
726
727 //\80\80 coalesce remaining records?
728
729 if ( targetNodePtr->numRecords == 0 ) // did we delete the last record?
730 {
731 BlockDescriptor siblingNode;
732 u_int32_t siblingNodeNum;
733
734 deleteRequired = true;
735
736 siblingNode.buffer = nil;
737 siblingNode.blockHeader = nil;
738
739 ////////////////// Get Siblings & Update Links //////////////////////////
740
741 siblingNodeNum = targetNodePtr->bLink; // Left Sibling Node
742 if ( siblingNodeNum != 0 )
743 {
744 err = GetNode (btreePtr, siblingNodeNum, 0, &siblingNode);
745 M_ExitOnError (err);
746
747 // XXXdbg
748 ModifyBlockStart(btreePtr->fileRefNum, &siblingNode);
749
750 ((NodeDescPtr)siblingNode.buffer)->fLink = targetNodePtr->fLink;
751 err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction);
752 M_ExitOnError (err);
753 }
754 else if ( targetNodePtr->kind == kBTLeafNode ) // update firstLeafNode
755 {
756 btreePtr->firstLeafNode = targetNodePtr->fLink;
757 }
758
759 siblingNodeNum = targetNodePtr->fLink; // Right Sibling Node
760 if ( siblingNodeNum != 0 )
761 {
762 err = GetNode (btreePtr, siblingNodeNum, 0, &siblingNode);
763 M_ExitOnError (err);
764
765 // XXXdbg
766 ModifyBlockStart(btreePtr->fileRefNum, &siblingNode);
767
768 ((NodeDescPtr)siblingNode.buffer)->bLink = targetNodePtr->bLink;
769 err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction);
770 M_ExitOnError (err);
771 }
772 else if ( targetNodePtr->kind == kBTLeafNode ) // update lastLeafNode
773 {
774 btreePtr->lastLeafNode = targetNodePtr->bLink;
775 }
776
777 //////////////////////// Free Empty Node ////////////////////////////////
778
779 ClearNode (btreePtr, targetNodePtr);
780
781 err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction);
782 M_ExitOnError (err);
783
784 err = FreeNode (btreePtr, targetNodeNum);
785 M_ExitOnError (err);
786 }
787 else if ( index == 0 ) // did we delete the first record?
788 {
789 updateRequired = true; // yes, so we need to update parent
790 }
791
792
793 if ( level == btreePtr->treeDepth ) // then targetNode->buffer is the root node
794 {
795 deleteRequired = false;
796 updateRequired = false;
797
798 if ( targetNode->buffer == nil ) // then root was freed and the btree is empty
799 {
800 btreePtr->rootNode = 0;
801 btreePtr->treeDepth = 0;
802 }
803 else if ( ((NodeDescPtr)targetNode->buffer)->numRecords == 1 )
804 {
805 err = CollapseTree (btreePtr, targetNode);
806 M_ExitOnError (err);
807 }
808 }
809
810
811 if ( updateRequired || deleteRequired )
812 {
813 ++level; // next level
814
815 //// Get Parent Node and index
816 index = treePathTable [level].index;
817 err = GetNode (btreePtr, treePathTable[level].node, 0, &parentNode);
818 M_ExitOnError (err);
819
820 if ( updateRequired )
821 {
822 KeyPtr keyPtr;
823 u_int8_t * recPtr;
824 u_int16_t recSize;
825 u_int32_t insertNode;
826
827 // XXXdbg
828 ModifyBlockStart(btreePtr->fileRefNum, &parentNode);
829
830 //\80\80 debug: check if ptr == targetNodeNum
831 GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
832 PanicIf( (*(u_int32_t *) recPtr) != targetNodeNum, " DeleteTree: parent ptr doesn't match targetNodeNum!!");
833
834 // need to delete and re-insert this parent key/ptr
835 DeleteRecord (btreePtr, parentNode.buffer, index);
836
837 keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
838 recPtr = (u_int8_t *) &targetNodeNum;
839 recSize = sizeof(targetNodeNum);
840
841 err = InsertTree (btreePtr, treePathTable, keyPtr, recPtr, recSize,
842 &parentNode, index, level, kReplaceRecord, &insertNode);
843 M_ExitOnError (err);
844 }
845 else // deleteRequired
846 {
847 err = DeleteTree (btreePtr, treePathTable, &parentNode, index, level);
848 M_ExitOnError (err);
849 }
850 }
851
852
853 err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction);
854 M_ExitOnError (err);
855
856 return noErr;
857
858 ErrorExit:
859
860 (void) ReleaseNode (btreePtr, targetNode);
861 (void) ReleaseNode (btreePtr, &parentNode);
862
863 return err;
864
865 } // end DeleteTree
866
867
868
869 ///////////////////////////////// CollapseTree //////////////////////////////////
870
871 static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr,
872 BlockDescriptor *blockPtr )
873 {
874 OSStatus err;
875 u_int32_t originalRoot;
876 u_int32_t nodeNum;
877
878 originalRoot = btreePtr->rootNode;
879
880 // XXXdbg
881 ModifyBlockStart(btreePtr->fileRefNum, blockPtr);
882
883 while (true)
884 {
885 if ( ((NodeDescPtr)blockPtr->buffer)->numRecords > 1)
886 break; // this will make a fine root node
887
888 if ( ((NodeDescPtr)blockPtr->buffer)->kind == kBTLeafNode)
889 break; // we've hit bottom
890
891 nodeNum = btreePtr->rootNode;
892 btreePtr->rootNode = GetChildNodeNum (btreePtr, blockPtr->buffer, 0);
893 --btreePtr->treeDepth;
894
895 //// Clear and Free Current Old Root Node ////
896 ClearNode (btreePtr, blockPtr->buffer);
897 err = UpdateNode (btreePtr, blockPtr, 0, kLockTransaction);
898 M_ExitOnError (err);
899 err = FreeNode (btreePtr, nodeNum);
900 M_ExitOnError (err);
901
902 //// Get New Root Node
903 err = GetNode (btreePtr, btreePtr->rootNode, 0, blockPtr);
904 M_ExitOnError (err);
905
906 // XXXdbg
907 ModifyBlockStart(btreePtr->fileRefNum, blockPtr);
908 }
909
910 if (btreePtr->rootNode != originalRoot)
911 M_BTreeHeaderDirty (btreePtr);
912
913 err = UpdateNode (btreePtr, blockPtr, 0, kLockTransaction); // always update!
914 M_ExitOnError (err);
915
916 return noErr;
917
918
919 /////////////////////////////////// ErrorExit ///////////////////////////////////
920
921 ErrorExit:
922 (void) ReleaseNode (btreePtr, blockPtr);
923 return err;
924 }
925
926
927
928 ////////////////////////////////// RotateLeft ///////////////////////////////////
929
930 /*-------------------------------------------------------------------------------
931
932 Routine: RotateLeft - One_line_description.
933
934 Function: Brief_description_of_the_function_and_any_side_effects
935
936 Algorithm: if rightIndex > insertIndex, subtract 1 for actual rightIndex
937
938 Input: btreePtr - description
939 leftNode - description
940 rightNode - description
941 rightInsertIndex - description
942 keyPtr - description
943 recPtr - description
944 recSize - description
945
946 Output: insertIndex
947 insertNodeNum - description
948 recordFit - description
949 recsRotated
950
951 Result: noErr - success
952 != noErr - failure
953 -------------------------------------------------------------------------------*/
954
955 static OSStatus RotateLeft (BTreeControlBlockPtr btreePtr,
956 NodeDescPtr leftNode,
957 NodeDescPtr rightNode,
958 u_int16_t rightInsertIndex,
959 KeyPtr keyPtr,
960 u_int8_t * recPtr,
961 u_int16_t recSize,
962 u_int16_t *insertIndex,
963 u_int32_t *insertNodeNum,
964 Boolean *recordFit,
965 u_int16_t *recsRotated )
966 {
967 OSStatus err;
968 int32_t insertSize;
969 int32_t nodeSize;
970 int32_t leftSize, rightSize;
971 int32_t moveSize = 0;
972 u_int16_t keyLength;
973 u_int16_t lengthFieldSize;
974 u_int16_t index, moveIndex;
975 Boolean didItFit;
976
977 ///////////////////// Determine If Record Will Fit //////////////////////////
978
979 keyLength = GetKeyLength(btreePtr, keyPtr, (rightNode->kind == kBTLeafNode));
980
981 // the key's length field is 8-bits in HFS and 16-bits in HFS+
982 if ( btreePtr->attributes & kBTBigKeysMask )
983 lengthFieldSize = sizeof(u_int16_t);
984 else
985 lengthFieldSize = sizeof(u_int8_t);
986
987 insertSize = keyLength + lengthFieldSize + recSize + sizeof(u_int16_t);
988
989 if ( M_IsOdd (insertSize) )
990 ++insertSize; // add pad byte;
991
992 nodeSize = btreePtr->nodeSize;
993
994 // add size of insert record to right node
995 rightSize = nodeSize - GetNodeFreeSize (btreePtr, rightNode) + insertSize;
996 leftSize = nodeSize - GetNodeFreeSize (btreePtr, leftNode);
997
998 moveIndex = 0;
999
1000 while ( leftSize < rightSize )
1001 {
1002 if ( moveIndex < rightInsertIndex )
1003 {
1004 moveSize = GetRecordSize (btreePtr, rightNode, moveIndex) + 2;
1005 }
1006 else if ( moveIndex == rightInsertIndex )
1007 {
1008 moveSize = insertSize;
1009 }
1010 else // ( moveIndex > rightInsertIndex )
1011 {
1012 moveSize = GetRecordSize (btreePtr, rightNode, moveIndex - 1) + 2;
1013 }
1014
1015 leftSize += moveSize;
1016 rightSize -= moveSize;
1017 ++moveIndex;
1018 }
1019
1020 if ( leftSize > nodeSize ) // undo last move
1021 {
1022 leftSize -= moveSize;
1023 rightSize += moveSize;
1024 --moveIndex;
1025 }
1026
1027 if ( rightSize > nodeSize ) // record won't fit - failure, but not error
1028 {
1029 *insertIndex = 0;
1030 *insertNodeNum = 0;
1031 *recordFit = false;
1032 *recsRotated = 0;
1033
1034 return noErr;
1035 }
1036
1037 // we've found balance point, moveIndex == number of records moved into leftNode
1038
1039
1040 //////////////////////////// Rotate Records /////////////////////////////////
1041
1042 *recsRotated = moveIndex;
1043 *recordFit = true;
1044 index = 0;
1045
1046 while ( index < moveIndex )
1047 {
1048 if ( index == rightInsertIndex ) // insert new record in left node
1049 {
1050 u_int16_t leftInsertIndex;
1051
1052 leftInsertIndex = leftNode->numRecords;
1053
1054 didItFit = InsertKeyRecord (btreePtr, leftNode, leftInsertIndex,
1055 keyPtr, keyLength, recPtr, recSize);
1056 if ( !didItFit )
1057 {
1058 Panic ("RotateLeft: InsertKeyRecord (left) returned false!");
1059 err = fsBTBadRotateErr;
1060 goto ErrorExit;
1061 }
1062
1063 *insertIndex = leftInsertIndex;
1064 *insertNodeNum = rightNode->bLink;
1065 }
1066 else
1067 {
1068 didItFit = RotateRecordLeft (btreePtr, leftNode, rightNode);
1069 if ( !didItFit )
1070 {
1071 Panic ("RotateLeft: RotateRecordLeft returned false!");
1072 err = fsBTBadRotateErr;
1073 goto ErrorExit;
1074 }
1075 }
1076
1077 ++index;
1078 }
1079
1080 if ( moveIndex <= rightInsertIndex ) // then insert new record in right node
1081 {
1082 rightInsertIndex -= index; // adjust for records already rotated
1083
1084 didItFit = InsertKeyRecord (btreePtr, rightNode, rightInsertIndex,
1085 keyPtr, keyLength, recPtr, recSize);
1086 if ( !didItFit )
1087 {
1088 Panic ("RotateLeft: InsertKeyRecord (right) returned false!");
1089 err = fsBTBadRotateErr;
1090 goto ErrorExit;
1091 }
1092
1093 *insertIndex = rightInsertIndex;
1094 *insertNodeNum = leftNode->fLink;
1095 }
1096
1097
1098 return noErr;
1099
1100
1101 ////////////////////////////// Error Exit ///////////////////////////////////
1102
1103 ErrorExit:
1104
1105 *insertIndex = 0;
1106 *insertNodeNum = 0;
1107 *recordFit = false;
1108 *recsRotated = 0;
1109
1110 return err;
1111 }
1112
1113
1114
1115 /////////////////////////////////// SplitLeft ///////////////////////////////////
1116
1117 static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr,
1118 BlockDescriptor *leftNode,
1119 BlockDescriptor *rightNode,
1120 u_int32_t rightNodeNum,
1121 u_int16_t index,
1122 KeyPtr keyPtr,
1123 u_int8_t * recPtr,
1124 u_int16_t recSize,
1125 u_int16_t *insertIndex,
1126 u_int32_t *insertNodeNum,
1127 u_int16_t *recsRotated )
1128 {
1129 OSStatus err;
1130 NodeDescPtr left, right;
1131 u_int32_t newNodeNum;
1132 Boolean recordFit;
1133
1134
1135 ///////////////////////////// Compare Nodes /////////////////////////////////
1136
1137 right = rightNode->buffer;
1138 left = leftNode->buffer;
1139
1140 PanicIf ( right->bLink != 0 && left == 0, " SplitLeft: left sibling missing!?" );
1141
1142 /* type should be kBTLeafNode or kBTIndexNode */
1143
1144 if ( (right->height == 1) && (right->kind != kBTLeafNode) )
1145 return fsBTInvalidNodeErr;
1146
1147 if ( left != nil )
1148 {
1149 if ( left->fLink != rightNodeNum )
1150 return fsBTInvalidNodeErr; //\80\80 E_BadSibling ?
1151
1152 if ( left->height != right->height )
1153 return fsBTInvalidNodeErr; //\80\80 E_BadNodeHeight ?
1154
1155 if ( left->kind != right->kind )
1156 return fsBTInvalidNodeErr; //\80\80 E_BadNodeType ?
1157 }
1158
1159
1160 ///////////////////////////// Allocate Node /////////////////////////////////
1161
1162 err = AllocateNode (btreePtr, &newNodeNum);
1163 M_ExitOnError (err);
1164
1165
1166 /////////////// Update Forward Link In Original Left Node ///////////////////
1167
1168 if ( left != nil )
1169 {
1170 // XXXdbg
1171 ModifyBlockStart(btreePtr->fileRefNum, leftNode);
1172
1173 left->fLink = newNodeNum;
1174 err = UpdateNode (btreePtr, leftNode, 0, kLockTransaction);
1175 M_ExitOnError (err);
1176 }
1177
1178
1179 /////////////////////// Initialize New Left Node ////////////////////////////
1180
1181 err = GetNewNode (btreePtr, newNodeNum, leftNode);
1182 M_ExitOnError (err);
1183
1184 // XXXdbg
1185 ModifyBlockStart(btreePtr->fileRefNum, leftNode);
1186
1187 left = leftNode->buffer;
1188 left->fLink = rightNodeNum;
1189
1190
1191 // Steal Info From Right Node
1192
1193 left->bLink = right->bLink;
1194 left->kind = right->kind;
1195 left->height = right->height;
1196
1197 right->bLink = newNodeNum; // update Right bLink
1198
1199 if ( (left->kind == kBTLeafNode) && (left->bLink == 0) )
1200 {
1201 // if we're adding a new first leaf node - update BTreeInfoRec
1202
1203 btreePtr->firstLeafNode = newNodeNum;
1204 M_BTreeHeaderDirty (btreePtr); //\80\80 AllocateNode should have set the bit already...
1205 }
1206
1207 ////////////////////////////// Rotate Left //////////////////////////////////
1208
1209 err = RotateLeft (btreePtr, left, right, index, keyPtr, recPtr, recSize,
1210 insertIndex, insertNodeNum, &recordFit, recsRotated);
1211
1212 M_ExitOnError (err);
1213
1214 return noErr;
1215
1216 ErrorExit:
1217
1218 (void) ReleaseNode (btreePtr, leftNode);
1219 (void) ReleaseNode (btreePtr, rightNode);
1220
1221 //\80\80 Free new node if allocated?
1222
1223 *insertIndex = 0;
1224 *insertNodeNum = 0;
1225 *recsRotated = 0;
1226
1227 return err;
1228 }
1229
1230
1231
1232 /////////////////////////////// RotateRecordLeft ////////////////////////////////
1233
1234 static Boolean RotateRecordLeft (BTreeControlBlockPtr btreePtr,
1235 NodeDescPtr leftNode,
1236 NodeDescPtr rightNode )
1237 {
1238 u_int16_t size;
1239 u_int8_t * recPtr;
1240 Boolean recordFit;
1241
1242 size = GetRecordSize (btreePtr, rightNode, 0);
1243 recPtr = GetRecordAddress (btreePtr, rightNode, 0);
1244
1245 recordFit = InsertRecord (btreePtr, leftNode, leftNode->numRecords, recPtr, size);
1246
1247 if ( !recordFit )
1248 return false;
1249
1250 DeleteRecord (btreePtr, rightNode, 0);
1251
1252 return true;
1253 }
1254
1255
1256 //////////////////////////////// AddNewRootNode /////////////////////////////////
1257
1258 static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr,
1259 NodeDescPtr leftNode,
1260 NodeDescPtr rightNode )
1261 {
1262 OSStatus err;
1263 BlockDescriptor rootNode;
1264 u_int32_t rootNum;
1265 KeyPtr keyPtr;
1266 Boolean didItFit;
1267 u_int16_t keyLength;
1268
1269 rootNode.buffer = nil;
1270 rootNode.blockHeader = nil;
1271
1272 PanicIf (leftNode == nil, "AddNewRootNode: leftNode == nil");
1273 PanicIf (rightNode == nil, "AddNewRootNode: rightNode == nil");
1274
1275
1276 /////////////////////// Initialize New Root Node ////////////////////////////
1277
1278 err = AllocateNode (btreePtr, &rootNum);
1279 M_ExitOnError (err);
1280
1281 err = GetNewNode (btreePtr, rootNum, &rootNode);
1282 M_ExitOnError (err);
1283
1284 // XXXdbg
1285 ModifyBlockStart(btreePtr->fileRefNum, &rootNode);
1286
1287 ((NodeDescPtr)rootNode.buffer)->kind = kBTIndexNode;
1288 ((NodeDescPtr)rootNode.buffer)->height = ++btreePtr->treeDepth;
1289
1290
1291 ///////////////////// Insert Left Node Index Record /////////////////////////
1292
1293 keyPtr = (KeyPtr) GetRecordAddress (btreePtr, leftNode, 0);
1294 keyLength = GetKeyLength(btreePtr, keyPtr, false);
1295
1296 didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 0, keyPtr, keyLength,
1297 (u_int8_t *) &rightNode->bLink, 4 );
1298
1299 PanicIf ( !didItFit, "AddNewRootNode:InsertKeyRecord failed for left index record");
1300
1301
1302 //////////////////// Insert Right Node Index Record /////////////////////////
1303
1304 keyPtr = (KeyPtr) GetRecordAddress (btreePtr, rightNode, 0);
1305 keyLength = GetKeyLength(btreePtr, keyPtr, false);
1306
1307 didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 1, keyPtr, keyLength,
1308 (u_int8_t *) &leftNode->fLink, 4 );
1309
1310 PanicIf ( !didItFit, "AddNewRootNode:InsertKeyRecord failed for right index record");
1311
1312
1313 /////////////////////////// Release Root Node ///////////////////////////////
1314
1315 err = UpdateNode (btreePtr, &rootNode, 0, kLockTransaction);
1316 M_ExitOnError (err);
1317
1318 // update BTreeInfoRec
1319
1320 btreePtr->rootNode = rootNum;
1321 M_BTreeHeaderDirty(btreePtr);
1322
1323 return noErr;
1324
1325
1326 ////////////////////////////// Error Exit ///////////////////////////////////
1327
1328 ErrorExit:
1329
1330 return err;
1331 }
1332
1333
1334 static u_int16_t GetKeyLength ( const BTreeControlBlock *btreePtr, const BTreeKey *key, Boolean forLeafNode )
1335 {
1336 u_int16_t length;
1337
1338 if ( forLeafNode || btreePtr->attributes & kBTVariableIndexKeysMask )
1339 length = KeyLength (btreePtr, key); // just use actual key length
1340 else
1341 length = btreePtr->maxKeyLength; // fixed sized index key (i.e. HFS) //\80\80 shouldn't we clear the pad bytes?
1342
1343 return length;
1344 }
1345
mirror of XNU