]> git.saurik.com Git - apple/hfs.git/blob - fsck_hfs/dfalib/BTreeTreeOps.c
projects / apple / hfs.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
hfs-556.41.1.tar.gz
[apple/hfs.git] / fsck_hfs / dfalib / BTreeTreeOps.c
1 /*
2 * Copyright (c) 1999-2000, 2002, 2007-2008 Apple Inc. All rights reserved.
3 *
4 * @APPLE_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. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23 /*
24 File: BTreeTreeOps.c
25
26 Contains: Multi-node tree operations for the BTree Module.
27
28 Version: xxx put the technology version here xxx
29
30 Written by: Gordon Sheridan and Bill Bruffey
31
32 Copyright: © 1992-1997, 1999 by Apple Computer, Inc., all rights reserved.
33 */
34
35 #include "BTreePrivate.h"
36 #include "../fsck_debug.h"
37 extern char debug;
38 extern void plog(const char *fmt, ...);
39
40 #define DEBUG_TREEOPS 0
41
42 /////////////////////// Routines Internal To BTree Module ///////////////////////
43 //
44 // SearchTree
45 // InsertTree
46 //
47 ////////////////////// Routines Internal To BTreeTreeOps.c //////////////////////
48
49 static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr,
50 NodeDescPtr leftNode,
51 NodeDescPtr rightNode );
52
53 static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr,
54 BlockDescriptor *blockPtr );
55
56 static OSStatus RotateLeft (BTreeControlBlockPtr btreePtr,
57 NodeDescPtr leftNode,
58 NodeDescPtr rightNode,
59 UInt16 rightInsertIndex,
60 KeyPtr keyPtr,
61 UInt8 * recPtr,
62 UInt16 recSize,
63 UInt16 *insertIndex,
64 UInt32 *insertNodeNum,
65 Boolean *recordFit,
66 UInt16 *recsRotated );
67
68 static Boolean RotateRecordLeft (BTreeControlBlockPtr btreePtr,
69 NodeDescPtr leftNode,
70 NodeDescPtr rightNode );
71
72 #if 0
73 static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr,
74 BlockDescriptor *leftNode,
75 BlockDescriptor *rightNode,
76 UInt32 rightNodeNum,
77 UInt16 index,
78 KeyPtr keyPtr,
79 UInt8 * recPtr,
80 UInt16 recSize,
81 UInt16 *insertIndex,
82 UInt32 *insertNodeNum,
83 UInt16 *recsRotated );
84 #endif
85
86
87 static OSStatus InsertLevel (BTreeControlBlockPtr btreePtr,
88 TreePathTable treePathTable,
89 InsertKey *primaryKey,
90 InsertKey *secondaryKey,
91 BlockDescriptor *targetNode,
92 UInt16 index,
93 UInt16 level,
94 UInt32 *insertNode );
95
96 static OSErr InsertNode (BTreeControlBlockPtr btreePtr,
97 InsertKey *key,
98 BlockDescriptor *targetNode,
99 UInt32 node,
100 UInt16 index,
101 UInt32 *newNode,
102 UInt16 *newIndex,
103 BlockDescriptor *leftNode,
104 Boolean *updateParent,
105 Boolean *insertParent,
106 Boolean *rootSplit );
107
108 static UInt16 GetKeyLength (const BTreeControlBlock *btreePtr,
109 const BTreeKey *key,
110 Boolean forLeafNode );
111
112 static Boolean RotateRecordRight( BTreeControlBlockPtr btreePtr,
113 NodeDescPtr leftNode,
114 NodeDescPtr rightNode );
115
116 static OSStatus RotateRight( BTreeControlBlockPtr btreePtr,
117 NodeDescPtr leftNode,
118 NodeDescPtr rightNode,
119 UInt16 leftInsertIndex,
120 KeyPtr keyPtr,
121 UInt8 * recPtr,
122 UInt16 recSize,
123 UInt16 *insertIndex,
124 UInt32 *insertNodeNum,
125 Boolean *recordFit,
126 UInt16 *recsRotated );
127
128 static OSStatus SplitRight( BTreeControlBlockPtr btreePtr,
129 BlockDescriptor *nodePtr,
130 BlockDescriptor *rightNodePtr,
131 UInt32 nodeNum,
132 UInt16 index,
133 KeyPtr keyPtr,
134 UInt8 *recPtr,
135 UInt16 recSize,
136 UInt16 *insertIndexPtr,
137 UInt32 *newNodeNumPtr,
138 UInt16 *recsRotatedPtr );
139
140 #if DEBUG_TREEOPS
141 static int DoKeyCheck( NodeDescPtr nodeP, BTreeControlBlock *btcb );
142 static int DoKeyCheckAcrossNodes( NodeDescPtr theLeftNodePtr,
143 NodeDescPtr theRightNodePtr,
144 BTreeControlBlock *theTreePtr,
145 Boolean printKeys );
146 static void PrintNodeDescriptor( NodeDescPtr thePtr );
147 static void PrintKey( UInt8 * myPtr, int mySize );
148 #endif // DEBUG_TREEOPS
149
150
151 /* used by InsertLevel (and called routines) to communicate the state of an insert operation */
152 enum
153 {
154 kInsertParent = 0x0001,
155 kUpdateParent = 0x0002,
156 kNewRoot = 0x0004,
157 kInsertedInRight = 0x0008,
158 kRecordFits = 0x0010
159 };
160
161
162 //////////////////////// BTree Multi-node Tree Operations ///////////////////////
163
164
165 /*-------------------------------------------------------------------------------
166
167 Routine: SearchTree - Search BTree for key and set up Tree Path Table.
168
169 Function: Searches BTree for specified key, setting up the Tree Path Table to
170 reflect the search path.
171
172
173 Input: btreePtr - pointer to control block of BTree to search
174 keyPtr - pointer to the key to search for
175 treePathTable - pointer to the tree path table to construct
176
177 Output: nodeNum - number of the node containing the key position
178 iterator - BTreeIterator specifying record or insert position
179
180 Result: noErr - key found, index is record index
181 fsBTRecordNotFoundErr - key not found, index is insert index
182 fsBTEmptyErr - key not found, return params are nil
183 otherwise - catastrophic failure (GetNode/ReleaseNode failed)
184 -------------------------------------------------------------------------------*/
185
186 OSStatus SearchTree (BTreeControlBlockPtr btreePtr,
187 BTreeKeyPtr searchKey,
188 TreePathTable treePathTable,
189 UInt32 *nodeNum,
190 BlockDescriptor *nodePtr,
191 UInt16 *returnIndex )
192 {
193 OSStatus err;
194 SInt16 level;
195 UInt32 curNodeNum;
196 NodeRec nodeRec;
197 UInt16 index;
198 Boolean keyFound;
199 SInt8 nodeKind; // Kind of current node (index/leaf)
200 KeyPtr keyPtr;
201 UInt8 * dataPtr;
202 UInt16 dataSize;
203
204
205 curNodeNum = btreePtr->rootNode;
206 level = btreePtr->treeDepth;
207
208 if (level == 0) // is the tree empty?
209 {
210 err = fsBTEmptyErr;
211 goto ErrorExit;
212 }
213
214 //¥¥ for debugging...
215 treePathTable [0].node = 0;
216 treePathTable [0].index = 0;
217
218 while (true)
219 {
220 //
221 // [2550929] Node number 0 is the header node. It is never a valid
222 // index or leaf node. If we're ever asked to search through node 0,
223 // something has gone wrong (typically a bad child node number, or
224 // we found a node full of zeroes that we thought was an index node).
225 //
226 if (curNodeNum == 0)
227 {
228 // Panic("\pSearchTree: curNodeNum is zero!");
229 if (debug) fprintf(stderr, "%s(%d): curNodeNum is 0\n", __FUNCTION__, __LINE__);
230 err = fsBTInvalidNodeErr;
231 goto ErrorExit;
232 }
233
234 err = GetNode (btreePtr, curNodeNum, &nodeRec);
235 if (err != noErr)
236 {
237 goto ErrorExit;
238 }
239
240 //
241 // [2550929] Sanity check the node height and node type. We expect
242 // particular values at each iteration in the search. This checking
243 // quickly finds bad pointers, loops, and other damage to the
244 // hierarchy of the B-tree.
245 //
246 if (((BTNodeDescriptor*)nodeRec.buffer)->height != level)
247 {
248 if (debug)
249 {
250 fprintf(stderr, "%s(line %d): height %d != level %d\n", __FUNCTION__, __LINE__, ((BTNodeDescriptor*)nodeRec.buffer)->height, level);
251 fprintf(stderr, " curNodeNum = %u\n", curNodeNum);
252 if (cur_debug_level & d_dump_node)
253 {
254 HexDump(nodeRec.buffer, nodeRec.blockSize, true);
255 }
256 }
257 err = fsBTInvalidNodeErr;
258 goto ReleaseAndExit;
259 }
260 nodeKind = ((BTNodeDescriptor*)nodeRec.buffer)->kind;
261 if (level == 1)
262 {
263 // Nodes at level 1 must be leaves, by definition
264 if (nodeKind != kBTLeafNode)
265 {
266 if (debug) fprintf(stderr, "%s(%d): wrong kind of node\n", __FUNCTION__, __LINE__);
267 err = fsBTInvalidNodeErr;
268 goto ReleaseAndExit;
269 }
270 }
271 else
272 {
273 // A node at any other depth must be an index node
274 if (nodeKind != kBTIndexNode)
275 {
276 if (debug) fprintf(stderr, "%s(%d): other wrong kind of node\n", __FUNCTION__, __LINE__);
277 err = fsBTInvalidNodeErr;
278 goto ReleaseAndExit;
279 }
280 }
281
282 keyFound = SearchNode (btreePtr, nodeRec.buffer, searchKey, &index);
283
284 treePathTable [level].node = curNodeNum;
285
286 if (nodeKind == kBTLeafNode)
287 {
288 treePathTable [level].index = index;
289 break; // were done...
290 }
291
292 if ( (keyFound != true) && (index != 0))
293 --index;
294
295 treePathTable [level].index = index;
296
297 err = GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize);
298 if (err != noErr)
299 {
300 // [2550929] If we got an error, it is probably because the index was bad
301 // (typically a corrupt node that confused SearchNode). Invalidate the node
302 // so we won't accidentally use the corrupted contents. NOTE: the Mac OS 9
303 // sources call this InvalidateNode.
304
305 (void) TrashNode(btreePtr, &nodeRec);
306 goto ErrorExit;
307 }
308
309 // Get the child pointer out of this index node. We're now done with the current
310 // node and can continue the search with the child node.
311 curNodeNum = *(UInt32 *)dataPtr;
312 err = ReleaseNode (btreePtr, &nodeRec);
313 if (err != noErr)
314 {
315 goto ErrorExit;
316 }
317
318 // The child node should be at a level one less than the parent.
319 --level;
320 }
321
322 *nodeNum = curNodeNum;
323 *nodePtr = nodeRec;
324 *returnIndex = index;
325
326 if (keyFound)
327 return noErr; // searchKey found, index identifies record in node
328 else
329 return fsBTRecordNotFoundErr; // searchKey not found, index identifies insert point
330
331 ReleaseAndExit:
332 (void) ReleaseNode(btreePtr, &nodeRec);
333 // fall into ErrorExit
334
335 ErrorExit:
336
337 *nodeNum = 0;
338 nodePtr->buffer = nil;
339 nodePtr->blockHeader = nil;
340 *returnIndex = 0;
341
342 return err;
343 }
344
345
346
347
348 ////////////////////////////////// InsertTree ///////////////////////////////////
349
350 OSStatus InsertTree ( BTreeControlBlockPtr btreePtr,
351 TreePathTable treePathTable,
352 KeyPtr keyPtr,
353 UInt8 * recPtr,
354 UInt16 recSize,
355 BlockDescriptor *targetNode,
356 UInt16 index,
357 UInt16 level,
358 Boolean replacingKey,
359 UInt32 *insertNode )
360 {
361 InsertKey primaryKey;
362 OSStatus err;
363
364 primaryKey.keyPtr = keyPtr;
365 primaryKey.keyLength = GetKeyLength(btreePtr, primaryKey.keyPtr, (level == 1));
366 primaryKey.recPtr = recPtr;
367 primaryKey.recSize = recSize;
368 primaryKey.replacingKey = replacingKey;
369 primaryKey.skipRotate = false;
370
371 err = InsertLevel (btreePtr, treePathTable, &primaryKey, nil,
372 targetNode, index, level, insertNode );
373
374 return err;
375
376 } // End of InsertTree
377
378
379 ////////////////////////////////// InsertLevel //////////////////////////////////
380
381 OSStatus InsertLevel (BTreeControlBlockPtr btreePtr,
382 TreePathTable treePathTable,
383 InsertKey *primaryKey,
384 InsertKey *secondaryKey,
385 BlockDescriptor *targetNode,
386 UInt16 index,
387 UInt16 level,
388 UInt32 *insertNode )
389 {
390 OSStatus err;
391 BlockDescriptor siblingNode;
392 UInt32 targetNodeNum;
393 UInt32 newNodeNum;
394 UInt16 newIndex;
395 Boolean insertParent;
396 Boolean updateParent;
397 Boolean newRoot;
398
399 #if defined(applec) && !defined(__SC__)
400 PanicIf ((level == 1) && (((NodeDescPtr)targetNode->buffer)->kind != kBTLeafNode), "\P InsertLevel: non-leaf at level 1! ");
401 #endif
402 siblingNode.buffer = nil;
403 targetNodeNum = treePathTable [level].node;
404
405 insertParent = false;
406 updateParent = false;
407
408 ////// process first insert //////
409
410 err = InsertNode (btreePtr, primaryKey, targetNode, targetNodeNum, index,
411 &newNodeNum, &newIndex, &siblingNode, &updateParent, &insertParent, &newRoot );
412 M_ExitOnError (err);
413
414 if ( newRoot )
415 {
416 // Extend the treePathTable by adding an entry for the new
417 // root node that references the current targetNode.
418 //
419 // When we split right the index in the new root is 0 if the new
420 // node is the same as the target node or 1 otherwise. When the
421 // new node number and the target node number are the same then
422 // we inserted the new record into the left node (the orignial target)
423 // after the split.
424
425 treePathTable [level + 1].node = btreePtr->rootNode;
426 if ( targetNodeNum == newNodeNum )
427 treePathTable [level + 1].index = 0; //
428 else
429 treePathTable [level + 1].index = 1;
430 }
431
432 if ( level == 1 )
433 *insertNode = newNodeNum;
434
435 ////// process second insert (if any) //////
436
437 if ( secondaryKey != nil )
438 {
439 Boolean temp;
440
441 // NOTE - we only get here if we have split a child node to the right and
442 // we are currently updating the child's parent. newIndex + 1 refers to
443 // the location in the parent node where we insert the new index record that
444 // represents the new child node (the new right node).
445 err = InsertNode (btreePtr, secondaryKey, targetNode, newNodeNum, newIndex + 1,
446 &newNodeNum, &newIndex, &siblingNode, &updateParent, &insertParent, &temp);
447 M_ExitOnError (err);
448
449 if ( DEBUG_BUILD && updateParent && newRoot )
450 DebugStr("\p InsertLevel: New root from primary key, update from secondary key...");
451 }
452
453 //////////////////////// Update Parent(s) ///////////////////////////////
454
455 if ( insertParent || updateParent )
456 {
457 BlockDescriptor parentNode;
458 UInt32 parentNodeNum;
459 KeyPtr keyPtr;
460 UInt8 * recPtr;
461 UInt16 recSize;
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, &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 //¥¥Êdebug: check if ptr == targetNodeNum
486 GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
487 PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p InsertLevel: parent ptr doesn't match target node!");
488
489 // need to delete and re-insert this parent key/ptr
490 // we delete it here and it gets re-inserted in the
491 // InsertLevel call below.
492 DeleteRecord (btreePtr, parentNode.buffer, index);
493
494 primaryKey->keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
495 primaryKey->keyLength = GetKeyLength(btreePtr, primaryKey->keyPtr, false);
496 primaryKey->recPtr = (UInt8 *) &targetNodeNum;
497 primaryKey->recSize = sizeof(targetNodeNum);
498 primaryKey->replacingKey = kReplaceRecord;
499 primaryKey->skipRotate = insertParent; // don't rotate left if we have two inserts occuring
500 }
501
502 ////////////////////////// Add New Parent Index /////////////////////////////
503
504 if ( insertParent )
505 {
506 InsertKey *insertKeyPtr;
507 InsertKey insertKey;
508
509 if ( updateParent )
510 {
511 insertKeyPtr = &insertKey;
512 secondaryKey = &insertKey;
513 }
514 else
515 {
516 insertKeyPtr = primaryKey;
517 // split right but not updating parent for our left node then
518 // we want to insert the key for the new right node just after
519 // the key for our left node.
520 index++;
521 }
522
523 insertKeyPtr->keyPtr = (KeyPtr) GetRecordAddress (btreePtr, siblingNode.buffer, 0);
524 insertKeyPtr->keyLength = GetKeyLength(btreePtr, insertKeyPtr->keyPtr, false);
525 insertKeyPtr->recPtr = (UInt8 *) &((NodeDescPtr)targetNode->buffer)->fLink;
526 insertKeyPtr->recSize = sizeof(UInt32);
527 insertKeyPtr->replacingKey = kInsertRecord;
528 insertKeyPtr->skipRotate = false; // a rotate is OK during second insert
529 }
530
531 err = InsertLevel (btreePtr, treePathTable, primaryKey, secondaryKey,
532 &parentNode, index, level, insertNode );
533 M_ExitOnError (err);
534 }
535
536 err = UpdateNode (btreePtr, targetNode); // all done with target
537 M_ExitOnError (err);
538
539 err = UpdateNode (btreePtr, &siblingNode); // all done with left sibling
540 M_ExitOnError (err);
541
542 return noErr;
543
544 ErrorExit:
545
546 (void) ReleaseNode (btreePtr, targetNode);
547 (void) ReleaseNode (btreePtr, &siblingNode);
548
549 Panic ("\p InsertLevel: an error occured!");
550
551 return err;
552
553 } // End of InsertLevel
554
555
556
557 ////////////////////////////////// InsertNode ///////////////////////////////////
558
559 static OSErr InsertNode (BTreeControlBlockPtr btreePtr,
560 InsertKey *key,
561
562 BlockDescriptor *targetNode,
563 UInt32 nodeNum,
564 UInt16 index,
565
566 UInt32 *newNodeNumPtr,
567 UInt16 *newIndex,
568
569 BlockDescriptor *siblingNode,
570 Boolean *updateParent,
571 Boolean *insertParent,
572 Boolean *rootSplit )
573 {
574 BlockDescriptor *tempNode;
575 UInt32 leftNodeNum;
576 UInt32 rightNodeNum;
577 UInt16 recsRotated;
578 OSErr err;
579 Boolean recordFit;
580
581 *rootSplit = false;
582
583 PanicIf ( targetNode->buffer == siblingNode->buffer, "\p InsertNode: targetNode == siblingNode, huh?");
584
585 leftNodeNum = ((NodeDescPtr) targetNode->buffer)->bLink;
586 rightNodeNum = ((NodeDescPtr) targetNode->buffer)->fLink;
587
588
589 /////////////////////// Try Simple Insert ///////////////////////////////
590
591 if ( nodeNum == leftNodeNum )
592 tempNode = siblingNode;
593 else
594 tempNode = targetNode;
595
596 recordFit = InsertKeyRecord (btreePtr, tempNode->buffer, index, key->keyPtr, key->keyLength, key->recPtr, key->recSize);
597
598 if ( recordFit )
599 {
600 *newNodeNumPtr = nodeNum;
601 *newIndex = index;
602
603 #if DEBUG_TREEOPS
604 if ( DoKeyCheck( tempNode->buffer, btreePtr ) != noErr )
605 {
606 plog( "\n%s - bad key order in node num %d: \n", __FUNCTION__ , nodeNum );
607 PrintNodeDescriptor( tempNode->buffer );
608 err = fsBTBadRotateErr;
609 goto ErrorExit;
610 }
611 #endif // DEBUG_TREEOPS
612
613 if ( (index == 0) && (((NodeDescPtr) tempNode->buffer)->height != btreePtr->treeDepth) )
614 *updateParent = true; // the first record changed so we need to update the parent
615 goto ExitThisRoutine;
616 }
617
618
619 //////////////////////// Try Rotate Left ////////////////////////////////
620
621 if ( leftNodeNum > 0 )
622 {
623 PanicIf ( siblingNode->buffer != nil, "\p InsertNode: siblingNode already aquired!");
624
625 if ( siblingNode->buffer == nil )
626 {
627 err = GetNode (btreePtr, leftNodeNum, siblingNode); // will be released by caller or a split below
628 M_ExitOnError (err);
629 }
630
631 PanicIf ( ((NodeDescPtr) siblingNode->buffer)->fLink != nodeNum, "\p InsertNode, RotateLeft: invalid sibling link!" );
632
633 if ( !key->skipRotate ) // are rotates allowed?
634 {
635 err = RotateLeft (btreePtr, siblingNode->buffer, targetNode->buffer, index, key->keyPtr, key->recPtr,
636 key->recSize, newIndex, newNodeNumPtr, &recordFit, &recsRotated );
637 M_ExitOnError (err);
638
639 if ( recordFit )
640 {
641 if ( key->replacingKey || (recsRotated > 1) || (index > 0) )
642 *updateParent = true;
643 goto ExitThisRoutine;
644 }
645 }
646 }
647
648
649 //////////////////////// Try Split Right /////////////////////////////////
650
651 (void) ReleaseNode( btreePtr, siblingNode );
652 err = SplitRight( btreePtr, targetNode, siblingNode, nodeNum, index, key->keyPtr,
653 key->recPtr, key->recSize, newIndex, newNodeNumPtr, &recsRotated );
654 M_ExitOnError (err);
655
656 // if we split root node - add new root
657 if ( ((NodeDescPtr) targetNode->buffer)->height == btreePtr->treeDepth )
658 {
659 err = AddNewRootNode( btreePtr, targetNode->buffer, siblingNode->buffer ); // Note: does not update TPT
660 M_ExitOnError (err);
661 *rootSplit = true;
662 }
663 else
664 {
665 *insertParent = true;
666
667 // update parent index node when replacingKey is true or when
668 // we inserted a new record at the beginning of our target node.
669 if ( key->replacingKey || ( index == 0 && *newIndex == 0 ) )
670 *updateParent = true;
671 }
672
673 ExitThisRoutine:
674
675 return noErr;
676
677 ErrorExit:
678
679 (void) ReleaseNode (btreePtr, siblingNode);
680 return err;
681
682 } // End of InsertNode
683
684
685 /*-------------------------------------------------------------------------------
686 Routine: DeleteTree - One_line_description.
687
688 Function: Brief_description_of_the_function_and_any_side_effects
689
690 ToDo:
691
692 Input: btreePtr - description
693 treePathTable - description
694 targetNode - description
695 index - description
696
697 Result: noErr - success
698 != noErr - failure
699 -------------------------------------------------------------------------------*/
700
701 OSStatus DeleteTree (BTreeControlBlockPtr btreePtr,
702 TreePathTable treePathTable,
703 BlockDescriptor *targetNode,
704 UInt16 index,
705 UInt16 level )
706 {
707 OSStatus err;
708 BlockDescriptor parentNode;
709 BTNodeDescriptor *targetNodePtr;
710 UInt32 targetNodeNum;
711 Boolean deleteRequired;
712 Boolean updateRequired;
713
714
715 deleteRequired = false;
716 updateRequired = false;
717
718 targetNodeNum = treePathTable[level].node;
719 targetNodePtr = targetNode->buffer;
720 PanicIf (targetNodePtr == nil, "\pDeleteTree: targetNode has nil buffer!");
721
722 DeleteRecord (btreePtr, targetNodePtr, index);
723
724 //¥¥ coalesce remaining records?
725
726 if ( targetNodePtr->numRecords == 0 ) // did we delete the last record?
727 {
728 BlockDescriptor siblingNode;
729 UInt32 siblingNodeNum;
730
731 deleteRequired = true;
732
733 ////////////////// Get Siblings & Update Links //////////////////////////
734
735 siblingNodeNum = targetNodePtr->bLink; // Left Sibling Node
736 if ( siblingNodeNum != 0 )
737 {
738 err = GetNode (btreePtr, siblingNodeNum, &siblingNode);
739 M_ExitOnError (err);
740 ((NodeDescPtr)siblingNode.buffer)->fLink = targetNodePtr->fLink;
741 err = UpdateNode (btreePtr, &siblingNode);
742 M_ExitOnError (err);
743 }
744 else if ( targetNodePtr->kind == kBTLeafNode ) // update firstLeafNode
745 {
746 btreePtr->firstLeafNode = targetNodePtr->fLink;
747 }
748
749 siblingNodeNum = targetNodePtr->fLink; // Right Sibling Node
750 if ( siblingNodeNum != 0 )
751 {
752 err = GetNode (btreePtr, siblingNodeNum, &siblingNode);
753 M_ExitOnError (err);
754 ((NodeDescPtr)siblingNode.buffer)->bLink = targetNodePtr->bLink;
755 err = UpdateNode (btreePtr, &siblingNode);
756 M_ExitOnError (err);
757 }
758 else if ( targetNodePtr->kind == kBTLeafNode ) // update lastLeafNode
759 {
760 btreePtr->lastLeafNode = targetNodePtr->bLink;
761 }
762
763 //////////////////////// Free Empty Node ////////////////////////////////
764
765 ClearNode (btreePtr, targetNodePtr);
766
767 err = UpdateNode (btreePtr, targetNode);
768 M_ExitOnError (err);
769 err = FreeNode (btreePtr, targetNodeNum);
770 M_ExitOnError (err);
771 }
772 else if ( index == 0 ) // did we delete the first record?
773 {
774 updateRequired = true; // yes, so we need to update parent
775 }
776
777
778 if ( level == btreePtr->treeDepth ) // then targetNode->buffer is the root node
779 {
780 deleteRequired = false;
781 updateRequired = false;
782
783 if ( targetNode->buffer == nil ) // then root was freed and the btree is empty
784 {
785 btreePtr->rootNode = 0;
786 btreePtr->treeDepth = 0;
787 }
788 else if ( ((NodeDescPtr)targetNode->buffer)->numRecords == 1 )
789 {
790 err = CollapseTree (btreePtr, targetNode);
791 M_ExitOnError (err);
792 }
793 }
794
795
796 if ( updateRequired || deleteRequired )
797 {
798 ++level; // next level
799
800 //// Get Parent Node and index
801 index = treePathTable [level].index;
802 err = GetNode (btreePtr, treePathTable[level].node, &parentNode);
803 M_ExitOnError (err);
804
805 if ( updateRequired )
806 {
807 KeyPtr keyPtr;
808 UInt8 * recPtr;
809 UInt16 recSize;
810 UInt32 insertNode;
811
812 //¥¥Êdebug: check if ptr == targetNodeNum
813 GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
814 PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p DeleteTree: parent ptr doesn't match targetNodeNum!!");
815
816 // need to delete and re-insert this parent key/ptr
817 DeleteRecord (btreePtr, parentNode.buffer, index);
818
819 keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
820 recPtr = (UInt8 *) &targetNodeNum;
821 recSize = sizeof(targetNodeNum);
822
823 err = InsertTree (btreePtr, treePathTable, keyPtr, recPtr, recSize,
824 &parentNode, index, level, kReplaceRecord, &insertNode);
825 M_ExitOnError (err);
826 }
827 else // deleteRequired
828 {
829 err = DeleteTree (btreePtr, treePathTable, &parentNode, index, level);
830 M_ExitOnError (err);
831 }
832 }
833
834
835 err = UpdateNode (btreePtr, targetNode);
836 M_ExitOnError (err);
837
838 return noErr;
839
840 ErrorExit:
841
842 (void) ReleaseNode (btreePtr, targetNode);
843 (void) ReleaseNode (btreePtr, &parentNode);
844
845 return err;
846
847 } // end DeleteTree
848
849
850
851 ///////////////////////////////// CollapseTree //////////////////////////////////
852
853 static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr,
854 BlockDescriptor *blockPtr )
855 {
856 OSStatus err;
857 UInt32 originalRoot;
858 UInt32 nodeNum;
859
860 originalRoot = btreePtr->rootNode;
861
862 while (true)
863 {
864 if ( ((NodeDescPtr)blockPtr->buffer)->numRecords > 1)
865 break; // this will make a fine root node
866
867 if ( ((NodeDescPtr)blockPtr->buffer)->kind == kBTLeafNode)
868 break; // we've hit bottom
869
870 nodeNum = btreePtr->rootNode;
871 btreePtr->rootNode = GetChildNodeNum (btreePtr, blockPtr->buffer, 0);
872 --btreePtr->treeDepth;
873
874 //// Clear and Free Current Old Root Node ////
875 ClearNode (btreePtr, blockPtr->buffer);
876 err = UpdateNode (btreePtr, blockPtr);
877 M_ExitOnError (err);
878 err = FreeNode (btreePtr, nodeNum);
879 M_ExitOnError (err);
880
881 //// Get New Root Node
882 err = GetNode (btreePtr, btreePtr->rootNode, blockPtr);
883 M_ExitOnError (err);
884 }
885
886 if (btreePtr->rootNode != originalRoot)
887 M_BTreeHeaderDirty (btreePtr);
888
889 err = UpdateNode (btreePtr, blockPtr); // always update!
890 M_ExitOnError (err);
891
892 return noErr;
893
894
895 /////////////////////////////////// ErrorExit ///////////////////////////////////
896
897 ErrorExit:
898 (void) ReleaseNode (btreePtr, blockPtr);
899 return err;
900 }
901
902
903
904 ////////////////////////////////// RotateLeft ///////////////////////////////////
905
906 /*-------------------------------------------------------------------------------
907
908 Routine: RotateLeft - One_line_description.
909
910 Function: Brief_description_of_the_function_and_any_side_effects
911
912 Algorithm: if rightIndex > insertIndex, subtract 1 for actual rightIndex
913
914 Input: btreePtr - description
915 leftNode - description
916 rightNode - description
917 rightInsertIndex - description
918 keyPtr - description
919 recPtr - description
920 recSize - description
921
922 Output: insertIndex
923 insertNodeNum - description
924 recordFit - description
925 recsRotated
926
927 Result: noErr - success
928 != noErr - failure
929 -------------------------------------------------------------------------------*/
930
931 static OSStatus RotateLeft (BTreeControlBlockPtr btreePtr,
932 NodeDescPtr leftNode,
933 NodeDescPtr rightNode,
934 UInt16 rightInsertIndex,
935 KeyPtr keyPtr,
936 UInt8 * recPtr,
937 UInt16 recSize,
938 UInt16 *insertIndex,
939 UInt32 *insertNodeNum,
940 Boolean *recordFit,
941 UInt16 *recsRotated )
942 {
943 OSStatus err;
944 SInt32 insertSize;
945 SInt32 nodeSize;
946 SInt32 leftSize, rightSize;
947 SInt32 moveSize;
948 UInt16 keyLength;
949 UInt16 lengthFieldSize;
950 UInt16 index, moveIndex;
951 Boolean didItFit;
952
953 ///////////////////// Determine If Record Will Fit //////////////////////////
954
955 keyLength = GetKeyLength(btreePtr, keyPtr, (rightNode->kind == kBTLeafNode));
956
957 // the key's length field is 8-bits in HFS and 16-bits in HFS+
958 if ( btreePtr->attributes & kBTBigKeysMask )
959 lengthFieldSize = sizeof(UInt16);
960 else
961 lengthFieldSize = sizeof(UInt8);
962
963 insertSize = keyLength + lengthFieldSize + recSize + sizeof(UInt16);
964
965 if ( M_IsOdd (insertSize) )
966 ++insertSize; // add pad byte;
967
968 nodeSize = btreePtr->nodeSize;
969
970 // add size of insert record to right node
971 rightSize = nodeSize - GetNodeFreeSize (btreePtr, rightNode) + insertSize;
972 leftSize = nodeSize - GetNodeFreeSize (btreePtr, leftNode);
973
974 moveIndex = 0;
975 moveSize = 0;
976
977 while ( leftSize < rightSize )
978 {
979 if ( moveIndex < rightInsertIndex )
980 {
981 moveSize = GetRecordSize (btreePtr, rightNode, moveIndex) + 2;
982 }
983 else if ( moveIndex == rightInsertIndex )
984 {
985 moveSize = insertSize;
986 }
987 else // ( moveIndex > rightInsertIndex )
988 {
989 moveSize = GetRecordSize (btreePtr, rightNode, moveIndex - 1) + 2;
990 }
991
992 leftSize += moveSize;
993 rightSize -= moveSize;
994 ++moveIndex;
995 }
996
997 if ( leftSize > nodeSize ) // undo last move
998 {
999 leftSize -= moveSize;
1000 rightSize += moveSize;
1001 --moveIndex;
1002 }
1003
1004 if ( rightSize > nodeSize ) // record won't fit - failure, but not error
1005 {
1006 *insertIndex = 0;
1007 *insertNodeNum = 0;
1008 *recordFit = false;
1009 *recsRotated = 0;
1010
1011 return noErr;
1012 }
1013
1014 // we've found balance point, moveIndex == number of records moved into leftNode
1015
1016
1017 //////////////////////////// Rotate Records /////////////////////////////////
1018
1019 *recsRotated = moveIndex;
1020 *recordFit = true;
1021 index = 0;
1022
1023 while ( index < moveIndex )
1024 {
1025 if ( index == rightInsertIndex ) // insert new record in left node
1026 {
1027 UInt16 leftInsertIndex;
1028
1029 leftInsertIndex = leftNode->numRecords;
1030
1031 didItFit = InsertKeyRecord (btreePtr, leftNode, leftInsertIndex,
1032 keyPtr, keyLength, recPtr, recSize);
1033 if ( !didItFit )
1034 {
1035 Panic ("\pRotateLeft: InsertKeyRecord (left) returned false!");
1036 err = fsBTBadRotateErr;
1037 goto ErrorExit;
1038 }
1039
1040 *insertIndex = leftInsertIndex;
1041 *insertNodeNum = rightNode->bLink;
1042 }
1043 else
1044 {
1045 didItFit = RotateRecordLeft (btreePtr, leftNode, rightNode);
1046 if ( !didItFit )
1047 {
1048 Panic ("\pRotateLeft: RotateRecordLeft returned false!");
1049 err = fsBTBadRotateErr;
1050 goto ErrorExit;
1051 }
1052 }
1053
1054 ++index;
1055 }
1056
1057 if ( moveIndex <= rightInsertIndex ) // then insert new record in right node
1058 {
1059 rightInsertIndex -= index; // adjust for records already rotated
1060
1061 didItFit = InsertKeyRecord (btreePtr, rightNode, rightInsertIndex,
1062 keyPtr, keyLength, recPtr, recSize);
1063 if ( !didItFit )
1064 {
1065 Panic ("\pRotateLeft: InsertKeyRecord (right) returned false!");
1066 err = fsBTBadRotateErr;
1067 goto ErrorExit;
1068 }
1069
1070 *insertIndex = rightInsertIndex;
1071 *insertNodeNum = leftNode->fLink;
1072 }
1073
1074 #if DEBUG_TREEOPS
1075 if ( DoKeyCheck( leftNode, btreePtr ) != noErr )
1076 {
1077 plog( "\n%s - bad key order in left node num %d: \n", __FUNCTION__ , rightNode->bLink );
1078 PrintNodeDescriptor( leftNode );
1079 err = fsBTBadRotateErr;
1080 goto ErrorExit;
1081 }
1082 if ( DoKeyCheck( rightNode, btreePtr ) != noErr )
1083 {
1084 plog( "\n%s - bad key order in left node num %d: \n", __FUNCTION__ , leftNode->fLink );
1085 PrintNodeDescriptor( rightNode );
1086 err = fsBTBadRotateErr;
1087 goto ErrorExit;
1088 }
1089 #endif // DEBUG_TREEOPS
1090
1091
1092 return noErr;
1093
1094
1095 ////////////////////////////// Error Exit ///////////////////////////////////
1096
1097 ErrorExit:
1098
1099 *insertIndex = 0;
1100 *insertNodeNum = 0;
1101 *recordFit = false;
1102 *recsRotated = 0;
1103
1104 return err;
1105 }
1106
1107
1108 #if 0
1109 /////////////////////////////////// SplitLeft ///////////////////////////////////
1110
1111 static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr,
1112 BlockDescriptor *leftNode,
1113 BlockDescriptor *rightNode,
1114 UInt32 rightNodeNum,
1115 UInt16 index,
1116 KeyPtr keyPtr,
1117 UInt8 * recPtr,
1118 UInt16 recSize,
1119 UInt16 *insertIndex,
1120 UInt32 *insertNodeNum,
1121 UInt16 *recsRotated )
1122 {
1123 OSStatus err;
1124 NodeDescPtr left, right;
1125 UInt32 newNodeNum;
1126 Boolean recordFit;
1127
1128
1129 ///////////////////////////// Compare Nodes /////////////////////////////////
1130
1131 right = rightNode->buffer;
1132 left = leftNode->buffer;
1133
1134 PanicIf ( right->bLink != 0 && left == 0, "\p SplitLeft: left sibling missing!?" );
1135
1136 //¥¥ type should be kLeafNode or kIndexNode
1137
1138 if ( (right->height == 1) && (right->kind != kBTLeafNode) )
1139 return fsBTInvalidNodeErr;
1140
1141 if ( left != nil )
1142 {
1143 if ( left->fLink != rightNodeNum )
1144 return fsBTInvalidNodeErr; //¥¥ E_BadSibling ?
1145
1146 if ( left->height != right->height )
1147 return fsBTInvalidNodeErr; //¥¥ E_BadNodeHeight ?
1148
1149 if ( left->kind != right->kind )
1150 return fsBTInvalidNodeErr; //¥¥ E_BadNodeType ?
1151 }
1152
1153
1154 ///////////////////////////// Allocate Node /////////////////////////////////
1155
1156 err = AllocateNode (btreePtr, &newNodeNum);
1157 M_ExitOnError (err);
1158
1159
1160 /////////////// Update Forward Link In Original Left Node ///////////////////
1161
1162 if ( left != nil )
1163 {
1164 left->fLink = newNodeNum;
1165 err = UpdateNode (btreePtr, leftNode);
1166 M_ExitOnError (err);
1167 }
1168
1169
1170 /////////////////////// Initialize New Left Node ////////////////////////////
1171
1172 err = GetNewNode (btreePtr, newNodeNum, leftNode);
1173 M_ExitOnError (err);
1174
1175 left = leftNode->buffer;
1176 left->fLink = rightNodeNum;
1177
1178
1179 // Steal Info From Right Node
1180
1181 left->bLink = right->bLink;
1182 left->kind = right->kind;
1183 left->height = right->height;
1184
1185 right->bLink = newNodeNum; // update Right bLink
1186
1187 if ( (left->kind == kBTLeafNode) && (left->bLink == 0) )
1188 {
1189 // if we're adding a new first leaf node - update BTreeInfoRec
1190
1191 btreePtr->firstLeafNode = newNodeNum;
1192 M_BTreeHeaderDirty (btreePtr); //¥¥ AllocateNode should have set the bit already...
1193 }
1194
1195 ////////////////////////////// Rotate Left //////////////////////////////////
1196
1197 err = RotateLeft (btreePtr, left, right, index, keyPtr, recPtr, recSize,
1198 insertIndex, insertNodeNum, &recordFit, recsRotated);
1199 M_ExitOnError (err);
1200
1201 return noErr;
1202
1203 ErrorExit:
1204
1205 (void) ReleaseNode (btreePtr, leftNode);
1206 (void) ReleaseNode (btreePtr, rightNode);
1207
1208 //¥¥ Free new node if allocated?
1209
1210 *insertIndex = 0;
1211 *insertNodeNum = 0;
1212 *recsRotated = 0;
1213
1214 return err;
1215 }
1216 #endif
1217
1218
1219
1220 /////////////////////////////// RotateRecordLeft ////////////////////////////////
1221
1222 static Boolean RotateRecordLeft (BTreeControlBlockPtr btreePtr,
1223 NodeDescPtr leftNode,
1224 NodeDescPtr rightNode )
1225 {
1226 UInt16 size;
1227 UInt8 * recPtr;
1228 Boolean recordFit;
1229
1230 size = GetRecordSize (btreePtr, rightNode, 0);
1231 recPtr = GetRecordAddress (btreePtr, rightNode, 0);
1232
1233 recordFit = InsertRecord (btreePtr, leftNode, leftNode->numRecords, recPtr, size);
1234
1235 if ( !recordFit )
1236 return false;
1237
1238 DeleteRecord (btreePtr, rightNode, 0);
1239
1240 return true;
1241 }
1242
1243
1244 //////////////////////////////// AddNewRootNode /////////////////////////////////
1245
1246 static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr,
1247 NodeDescPtr leftNode,
1248 NodeDescPtr rightNode )
1249 {
1250 OSStatus err;
1251 BlockDescriptor rootNode;
1252 UInt32 rootNum;
1253 KeyPtr keyPtr;
1254 Boolean didItFit;
1255 UInt16 keyLength;
1256
1257 PanicIf (leftNode == nil, "\pAddNewRootNode: leftNode == nil");
1258 PanicIf (rightNode == nil, "\pAddNewRootNode: rightNode == nil");
1259
1260
1261 /////////////////////// Initialize New Root Node ////////////////////////////
1262
1263 err = AllocateNode (btreePtr, &rootNum);
1264 M_ExitOnError (err);
1265
1266 err = GetNewNode (btreePtr, rootNum, &rootNode);
1267 M_ExitOnError (err);
1268
1269 ((NodeDescPtr)rootNode.buffer)->kind = kBTIndexNode;
1270 ((NodeDescPtr)rootNode.buffer)->height = ++btreePtr->treeDepth;
1271
1272
1273 ///////////////////// Insert Left Node Index Record /////////////////////////
1274
1275 keyPtr = (KeyPtr) GetRecordAddress (btreePtr, leftNode, 0);
1276 keyLength = GetKeyLength(btreePtr, keyPtr, false);
1277
1278 didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 0, keyPtr, keyLength,
1279 (UInt8 *) &rightNode->bLink, 4 );
1280
1281 PanicIf ( !didItFit, "\pAddNewRootNode:InsertKeyRecord failed for left index record");
1282
1283
1284 //////////////////// Insert Right Node Index Record /////////////////////////
1285
1286 keyPtr = (KeyPtr) GetRecordAddress (btreePtr, rightNode, 0);
1287 keyLength = GetKeyLength(btreePtr, keyPtr, false);
1288
1289 didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 1, keyPtr, keyLength,
1290 (UInt8 *) &leftNode->fLink, 4 );
1291
1292 PanicIf ( !didItFit, "\pAddNewRootNode:InsertKeyRecord failed for right index record");
1293
1294
1295 #if DEBUG_TREEOPS
1296 if ( DoKeyCheck( rootNode.buffer, btreePtr ) != noErr )
1297 {
1298 plog( "\n%s - bad key order in root node num %d: \n", __FUNCTION__ , rootNum );
1299 PrintNodeDescriptor( rootNode.buffer );
1300 err = fsBTBadRotateErr;
1301 goto ErrorExit;
1302 }
1303 #endif // DEBUG_TREEOPS
1304
1305
1306 /////////////////////////// Release Root Node ///////////////////////////////
1307
1308 err = UpdateNode (btreePtr, &rootNode);
1309 M_ExitOnError (err);
1310
1311 // update BTreeInfoRec
1312
1313 btreePtr->rootNode = rootNum;
1314 btreePtr->flags |= kBTHeaderDirty;
1315
1316 return noErr;
1317
1318
1319 ////////////////////////////// Error Exit ///////////////////////////////////
1320
1321 ErrorExit:
1322
1323 return err;
1324 }
1325
1326
1327 static UInt16 GetKeyLength ( const BTreeControlBlock *btreePtr, const BTreeKey *key, Boolean forLeafNode )
1328 {
1329 UInt16 length;
1330
1331 if ( forLeafNode || btreePtr->attributes & kBTVariableIndexKeysMask )
1332 length = KeyLength (btreePtr, key); // just use actual key length
1333 else
1334 length = btreePtr->maxKeyLength; // fixed sized index key (i.e. HFS) //¥¥ shouldn't we clear the pad bytes?
1335
1336 return length;
1337 }
1338
1339
1340
1341 /////////////////////////////////// SplitRight ///////////////////////////////////
1342
1343 static OSStatus SplitRight (BTreeControlBlockPtr btreePtr,
1344 BlockDescriptor *nodePtr,
1345 BlockDescriptor *rightNodePtr,
1346 UInt32 nodeNum,
1347 UInt16 index,
1348 KeyPtr keyPtr,
1349 UInt8 *recPtr,
1350 UInt16 recSize,
1351 UInt16 *insertIndexPtr,
1352 UInt32 *newNodeNumPtr,
1353 UInt16 *recsRotatedPtr )
1354 {
1355 OSStatus err;
1356 NodeDescPtr leftPtr, rightPtr;
1357 UInt32 newNodeNum;
1358 Boolean recordFit;
1359
1360
1361 ///////////////////////////// Compare Nodes /////////////////////////////////
1362
1363 leftPtr = nodePtr->buffer;
1364
1365 if ( leftPtr->fLink != 0 )
1366 {
1367 err = GetNode( btreePtr, leftPtr->fLink, rightNodePtr );
1368 M_ExitOnError( err );
1369 }
1370 rightPtr = rightNodePtr->buffer;
1371
1372 PanicIf ( leftPtr->fLink != 0 && rightPtr == 0, "\p SplitRight: right sibling missing!?" );
1373
1374 //¥¥ type should be kLeafNode or kIndexNode
1375
1376 if ( (leftPtr->height == 1) && (leftPtr->kind != kBTLeafNode) )
1377 return fsBTInvalidNodeErr;
1378
1379 if ( rightPtr != nil )
1380 {
1381 if ( rightPtr->bLink != nodeNum )
1382 return fsBTInvalidNodeErr; //¥¥ E_BadSibling ?
1383
1384 if ( rightPtr->height != leftPtr->height )
1385 return fsBTInvalidNodeErr; //¥¥ E_BadNodeHeight ?
1386
1387 if ( rightPtr->kind != leftPtr->kind )
1388 return fsBTInvalidNodeErr; //¥¥ E_BadNodeType ?
1389 }
1390
1391
1392 ///////////////////////////// Allocate Node /////////////////////////////////
1393
1394 err = AllocateNode (btreePtr, &newNodeNum);
1395 M_ExitOnError (err);
1396
1397 /////////////// Update backward Link In Original Right Node ///////////////////
1398
1399 if ( rightPtr != nil )
1400 {
1401 rightPtr->bLink = newNodeNum;
1402 err = UpdateNode (btreePtr, rightNodePtr);
1403 M_ExitOnError (err);
1404 }
1405
1406 /////////////////////// Initialize New Right Node ////////////////////////////
1407
1408 err = GetNewNode (btreePtr, newNodeNum, rightNodePtr );
1409 M_ExitOnError (err);
1410
1411 rightPtr = rightNodePtr->buffer;
1412 rightPtr->bLink = nodeNum;
1413
1414
1415 // Steal Info From Left Node
1416
1417 rightPtr->fLink = leftPtr->fLink;
1418 rightPtr->kind = leftPtr->kind;
1419 rightPtr->height = leftPtr->height;
1420
1421 leftPtr->fLink = newNodeNum; // update Left fLink
1422
1423 if ( (rightPtr->kind == kBTLeafNode) && (rightPtr->fLink == 0) )
1424 {
1425 // if we're adding a new last leaf node - update BTreeInfoRec
1426
1427 btreePtr->lastLeafNode = newNodeNum;
1428 M_BTreeHeaderDirty (btreePtr); //¥¥ AllocateNode should have set the bit already...
1429 }
1430
1431 ////////////////////////////// Rotate Right //////////////////////////////////
1432
1433 err = RotateRight (btreePtr, leftPtr, rightPtr, index, keyPtr, recPtr, recSize,
1434 insertIndexPtr, newNodeNumPtr, &recordFit, recsRotatedPtr);
1435 M_ExitOnError (err);
1436
1437 return noErr;
1438
1439 ErrorExit:
1440
1441 (void) ReleaseNode (btreePtr, nodePtr);
1442 (void) ReleaseNode (btreePtr, rightNodePtr);
1443
1444 //¥¥ Free new node if allocated?
1445
1446 *insertIndexPtr = 0;
1447 *newNodeNumPtr = 0;
1448 *recsRotatedPtr = 0;
1449
1450 return err;
1451
1452 } /* SplitRight */
1453
1454
1455
1456 ////////////////////////////////// RotateRight ///////////////////////////////////
1457
1458 /*-------------------------------------------------------------------------------
1459
1460 Routine: RotateRight - rotate half of .
1461
1462 Function: Brief_description_of_the_function_and_any_side_effects
1463
1464 Algorithm: if rightIndex > insertIndex, subtract 1 for actual rightIndex
1465
1466 Input: btreePtr - description
1467 leftNode - description
1468 rightNode - description
1469 leftInsertIndex - description
1470 keyPtr - description
1471 recPtr - description
1472 recSize - description
1473
1474 Output: insertIndex
1475 insertNodeNum - description
1476 recordFit - description
1477 recsRotated
1478
1479 Result: noErr - success
1480 != noErr - failure
1481 -------------------------------------------------------------------------------*/
1482
1483 static OSStatus RotateRight (BTreeControlBlockPtr btreePtr,
1484 NodeDescPtr leftNodePtr,
1485 NodeDescPtr rightNodePtr,
1486 UInt16 leftInsertIndex,
1487 KeyPtr keyPtr,
1488 UInt8 *recPtr,
1489 UInt16 recSize,
1490 UInt16 *insertIndexPtr,
1491 UInt32 *newNodeNumPtr,
1492 Boolean *didRecordFitPtr,
1493 UInt16 *recsRotatedPtr )
1494 {
1495 OSStatus err;
1496 SInt32 insertSize;
1497 SInt32 nodeSize;
1498 SInt32 leftSize, rightSize;
1499 SInt32 moveSize;
1500 UInt16 keyLength;
1501 UInt16 lengthFieldSize;
1502 SInt16 index, moveIndex, myInsertIndex;
1503 Boolean didItFit;
1504 Boolean doIncrement = false;
1505
1506 ///////////////////// Determine If Record Will Fit //////////////////////////
1507
1508 keyLength = GetKeyLength( btreePtr, keyPtr, (leftNodePtr->kind == kBTLeafNode) );
1509
1510 // the key's length field is 8-bits in HFS and 16-bits in HFS+
1511 if ( btreePtr->attributes & kBTBigKeysMask )
1512 lengthFieldSize = sizeof(UInt16);
1513 else
1514 lengthFieldSize = sizeof(UInt8);
1515
1516 /*
1517 * A record size in a node is the size of the key, the size of the key length field,
1518 * the size of the record, and the size of the record offset index.
1519 */
1520 insertSize = keyLength + lengthFieldSize + recSize + sizeof(UInt16);
1521 if ( M_IsOdd (insertSize) )
1522 ++insertSize; // add pad byte;
1523 nodeSize = btreePtr->nodeSize;
1524
1525 // add size of insert record to left node
1526 rightSize = nodeSize - GetNodeFreeSize( btreePtr, rightNodePtr );
1527 leftSize = nodeSize - GetNodeFreeSize( btreePtr, leftNodePtr ) + insertSize;
1528
1529 moveIndex = leftNodePtr->numRecords; // start at last record in the node
1530 moveSize = 0;
1531
1532 /*
1533 * The goal here is to attempt to make the nodes as balanced as
1534 * possible. We do this by "moving" records from the left node to
1535 * the right node, until the right node is larger than the left
1536 * node.
1537 *
1538 * We also need to factor in the new record for this; what we are
1539 * trying to do, as a result, is consider a virtual node that has
1540 * all of the old records in it, plus the new record inserted at
1541 * the proper place. (This is the reason for the if cases in the
1542 * loop.)
1543 */
1544 while ( rightSize < leftSize )
1545 {
1546 /*
1547 * We set moveSize to the size of the record being moved in this
1548 * pass. We need to add sizeof(UInt16) because we need to account
1549 * for the record offset index, which is two bytes. This was already
1550 * added to insertSize above.
1551 */
1552 if (moveIndex > leftInsertIndex)
1553 moveSize = GetRecordSize( btreePtr, leftNodePtr, moveIndex - 1) + sizeof(UInt16);
1554 else if (moveIndex == leftInsertIndex)
1555 moveSize = insertSize;
1556 else // (moveIndex < leftInsertIndex)
1557 moveSize = GetRecordSize( btreePtr, leftNodePtr, moveIndex) + sizeof(UInt16);
1558
1559 leftSize -= moveSize;
1560 rightSize += moveSize;
1561 --moveIndex;
1562 }
1563
1564 if ( rightSize > nodeSize ) // undo last move
1565 {
1566 leftSize += moveSize;
1567 rightSize -= moveSize;
1568 ++moveIndex;
1569 }
1570
1571 if ( leftSize > nodeSize ) // record won't fit - failure, but not error
1572 {
1573 *insertIndexPtr = 0;
1574 *newNodeNumPtr = 0;
1575 *didRecordFitPtr = false;
1576 *recsRotatedPtr = 0;
1577
1578 return noErr;
1579 }
1580
1581 // we've found balance point, we rotate up to moveIndex into right node
1582
1583 //////////////////////////// Rotate Records /////////////////////////////////
1584
1585 *didRecordFitPtr = true;
1586 index = leftNodePtr->numRecords;
1587 *recsRotatedPtr = index - moveIndex;
1588 myInsertIndex = 0;
1589
1590 // handle case where the new record is inserting after the last
1591 // record in our left node.
1592 if ( leftNodePtr->numRecords == leftInsertIndex )
1593 {
1594 didItFit = InsertKeyRecord (btreePtr, rightNodePtr, 0,
1595 keyPtr, keyLength, recPtr, recSize);
1596 if ( !didItFit )
1597 {
1598 if (debug) plog ("RotateRight: InsertKeyRecord (left) returned false!\n");
1599 err = fsBTBadRotateErr;
1600 goto ErrorExit;
1601 }
1602
1603 // NOTE - our insert location will slide as we insert more records
1604 doIncrement = true;
1605 *newNodeNumPtr = leftNodePtr->fLink;
1606 index--;
1607 }
1608
1609 while ( index > moveIndex )
1610 {
1611 if ( index == leftInsertIndex ) // insert new record in right node
1612 {
1613 didItFit = InsertKeyRecord (btreePtr, rightNodePtr, 0,
1614 keyPtr, keyLength, recPtr, recSize);
1615 if ( !didItFit )
1616 {
1617 if (debug) plog ("RotateRight: InsertKeyRecord (right) returned false!\n");
1618 err = fsBTBadRotateErr;
1619 goto ErrorExit;
1620 }
1621
1622 // NOTE - our insert index will slide as we insert more records
1623 doIncrement = true;
1624 myInsertIndex = -1;
1625 *newNodeNumPtr = leftNodePtr->fLink;
1626 }
1627 else
1628 {
1629 didItFit = RotateRecordRight( btreePtr, leftNodePtr, rightNodePtr );
1630 if ( !didItFit )
1631 {
1632 if (debug) plog ("RotateRight: RotateRecordRight returned false!\n");
1633 err = fsBTBadRotateErr;
1634 goto ErrorExit;
1635 }
1636 }
1637
1638 if ( doIncrement )
1639 myInsertIndex++;
1640 --index;
1641 }
1642
1643 *insertIndexPtr = myInsertIndex;
1644
1645 if ( moveIndex >= leftInsertIndex ) // then insert new record in left node
1646 {
1647 didItFit = InsertKeyRecord (btreePtr, leftNodePtr, leftInsertIndex,
1648 keyPtr, keyLength, recPtr, recSize);
1649 if ( !didItFit )
1650 {
1651 if (debug) plog ("RotateRight: InsertKeyRecord (left) returned false!\n");
1652 err = fsBTBadRotateErr;
1653 goto ErrorExit;
1654 }
1655
1656 *insertIndexPtr = leftInsertIndex;
1657 *newNodeNumPtr = rightNodePtr->bLink;
1658 }
1659
1660 #if DEBUG_TREEOPS
1661 if ( DoKeyCheck( rightNodePtr, btreePtr ) != noErr )
1662 {
1663 plog( "\n%s - bad key order in right node num %d: \n", __FUNCTION__ , leftNodePtr->fLink);
1664 PrintNodeDescriptor( rightNodePtr );
1665 err = fsBTBadRotateErr;
1666 goto ErrorExit;
1667 }
1668 if ( DoKeyCheck( leftNodePtr, btreePtr ) != noErr )
1669 {
1670 plog( "\n%s - bad key order in left node num %d: \n", __FUNCTION__ , rightNodePtr->bLink);
1671 PrintNodeDescriptor( leftNodePtr );
1672 err = fsBTBadRotateErr;
1673 goto ErrorExit;
1674 }
1675 if ( DoKeyCheckAcrossNodes( leftNodePtr, rightNodePtr, btreePtr, false ) != noErr )
1676 {
1677 plog( "\n%s - bad key order across nodes left %d right %d: \n",
1678 __FUNCTION__ , rightNodePtr->bLink, leftNodePtr->fLink );
1679 PrintNodeDescriptor( leftNodePtr );
1680 PrintNodeDescriptor( rightNodePtr );
1681 err = fsBTBadRotateErr;
1682 goto ErrorExit;
1683 }
1684 #endif // DEBUG_TREEOPS
1685
1686 return noErr;
1687
1688
1689 ////////////////////////////// Error Exit ///////////////////////////////////
1690
1691 ErrorExit:
1692
1693 *insertIndexPtr = 0;
1694 *newNodeNumPtr = 0;
1695 *didRecordFitPtr = false;
1696 *recsRotatedPtr = 0;
1697
1698 return err;
1699
1700 } /* RotateRight */
1701
1702
1703
1704 /////////////////////////////// RotateRecordRight ////////////////////////////////
1705
1706 static Boolean RotateRecordRight (BTreeControlBlockPtr btreePtr,
1707 NodeDescPtr leftNodePtr,
1708 NodeDescPtr rightNodePtr )
1709 {
1710 UInt16 size;
1711 UInt8 * recPtr;
1712 Boolean didRecordFit;
1713
1714 size = GetRecordSize( btreePtr, leftNodePtr, leftNodePtr->numRecords - 1 ) ;
1715 recPtr = GetRecordAddress( btreePtr, leftNodePtr, leftNodePtr->numRecords - 1 ) ;
1716
1717 didRecordFit = InsertRecord( btreePtr, rightNodePtr, 0, recPtr, size );
1718 if ( !didRecordFit )
1719 return false;
1720
1721 DeleteRecord( btreePtr, leftNodePtr, leftNodePtr->numRecords - 1 );
1722
1723 return true;
1724
1725 } /* RotateRecordRight */
1726
1727
1728
1729 #if DEBUG_TREEOPS
1730 static int DoKeyCheckAcrossNodes( NodeDescPtr theLeftNodePtr,
1731 NodeDescPtr theRightNodePtr,
1732 BTreeControlBlock *theTreePtr,
1733 Boolean printKeys )
1734 {
1735 UInt16 myLeftDataSize;
1736 UInt16 myRightDataSize;
1737 UInt16 myRightKeyLen;
1738 UInt16 myLeftKeyLen;
1739 KeyPtr myLeftKeyPtr;
1740 KeyPtr myRightKeyPtr;
1741 UInt8 * myLeftDataPtr;
1742 UInt8 * myRightDataPtr;
1743
1744
1745 GetRecordByIndex( theTreePtr, theLeftNodePtr, (theLeftNodePtr->numRecords - 1),
1746 &myLeftKeyPtr, &myLeftDataPtr, &myLeftDataSize );
1747 GetRecordByIndex( theTreePtr, theRightNodePtr, 0,
1748 &myRightKeyPtr, &myRightDataPtr, &myRightDataSize );
1749
1750 if ( theTreePtr->attributes & kBTBigKeysMask )
1751 {
1752 myRightKeyLen = myRightKeyPtr->length16;
1753 myLeftKeyLen = myLeftKeyPtr->length16;
1754 }
1755 else
1756 {
1757 myRightKeyLen = myRightKeyPtr->length8;
1758 myLeftKeyLen = myLeftKeyPtr->length8;
1759 }
1760
1761 if ( printKeys )
1762 {
1763 plog( "%s - left and right keys:\n", __FUNCTION__ );
1764 PrintKey( (UInt8 *) myLeftKeyPtr, myLeftKeyLen );
1765 PrintKey( (UInt8 *) myRightKeyPtr, myRightKeyLen );
1766 }
1767
1768 if ( CompareKeys( theTreePtr, myLeftKeyPtr, myRightKeyPtr ) >= 0 )
1769 return( -1 );
1770
1771 return( noErr );
1772
1773 } /* DoKeyCheckAcrossNodes */
1774
1775
1776 static int DoKeyCheck( NodeDescPtr nodeP, BTreeControlBlock *btcb )
1777 {
1778 SInt16 index;
1779 UInt16 dataSize;
1780 UInt16 keyLength;
1781 KeyPtr keyPtr;
1782 UInt8 *dataPtr;
1783 KeyPtr prevkeyP = nil;
1784
1785
1786 if ( nodeP->numRecords == 0 )
1787 {
1788 if ( (nodeP->fLink == 0) && (nodeP->bLink == 0) )
1789 return( -1 );
1790 }
1791 else
1792 {
1793 /*
1794 * Loop on number of records in node
1795 */
1796 for ( index = 0; index < nodeP->numRecords; index++)
1797 {
1798 GetRecordByIndex( (BTreeControlBlock *)btcb, nodeP, (UInt16) index, &keyPtr, &dataPtr, &dataSize );
1799
1800 if (btcb->attributes & kBTBigKeysMask)
1801 keyLength = keyPtr->length16;
1802 else
1803 keyLength = keyPtr->length8;
1804
1805 if ( keyLength > btcb->maxKeyLength )
1806 {
1807 return( -1 );
1808 }
1809
1810 if ( prevkeyP != nil )
1811 {
1812 if ( CompareKeys( (BTreeControlBlockPtr)btcb, prevkeyP, keyPtr ) >= 0 )
1813 {
1814 return( -1 );
1815 }
1816 }
1817 prevkeyP = keyPtr;
1818 }
1819 }
1820
1821 return( noErr );
1822
1823 } /* DoKeyCheck */
1824
1825 static void PrintNodeDescriptor( NodeDescPtr thePtr )
1826 {
1827 plog( " fLink %d bLink %d kind %d height %d numRecords %d \n",
1828 thePtr->fLink, thePtr->bLink, thePtr->kind, thePtr->height, thePtr->numRecords );
1829 }
1830
1831
1832 static void PrintKey( UInt8 * myPtr, int mySize )
1833 {
1834 int i;
1835
1836 for ( i = 0; i < mySize+2; i++ )
1837 {
1838 plog("%02X", *(myPtr + i) );
1839 }
1840 plog("\n" );
1841 } /* PrintKey */
1842
1843
1844 #endif // DEBUG_TREEOPS
mirror of hfs