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"
37extern char debug;
38extern 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
49static OSStatus   AddNewRootNode	(BTreeControlBlockPtr		 btreePtr,
50									 NodeDescPtr				 leftNode,
51									 NodeDescPtr				 rightNode );
52
53static OSStatus   CollapseTree		(BTreeControlBlockPtr		 btreePtr,
54									 BlockDescriptor			*blockPtr );
55
56static 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
68static Boolean	   RotateRecordLeft	(BTreeControlBlockPtr		 btreePtr,
69									 NodeDescPtr				 leftNode,
70									 NodeDescPtr				 rightNode );
71
72#if 0
73static 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
87static	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
96static 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
108static UInt16		GetKeyLength	(const BTreeControlBlock *btreePtr,
109									 const BTreeKey *key,
110									 Boolean forLeafNode );
111
112static Boolean 		RotateRecordRight( 	BTreeControlBlockPtr		btreePtr,
113								 		NodeDescPtr				leftNode,
114							 	 		NodeDescPtr				rightNode );
115
116static 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
128static 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
141static int DoKeyCheck( NodeDescPtr nodeP, BTreeControlBlock *btcb );
142static int	DoKeyCheckAcrossNodes( 	NodeDescPtr theLeftNodePtr,
143									NodeDescPtr theRightNodePtr,
144									BTreeControlBlock *theTreePtr,
145									Boolean printKeys );
146static void PrintNodeDescriptor( NodeDescPtr  thePtr );
147static 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 */
152enum
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
167Routine:	SearchTree	-	Search BTree for key and set up Tree Path Table.
168
169Function:	Searches BTree for specified key, setting up the Tree Path Table to
170			reflect the search path.
171
172
173Input:		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
177Output:		nodeNum			- number of the node containing the key position
178			iterator		- BTreeIterator specifying record or insert position
179
180Result:		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
186OSStatus	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
331ReleaseAndExit:
332    (void) ReleaseNode(btreePtr, &nodeRec);
333    //	fall into ErrorExit
334
335ErrorExit:
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
350OSStatus	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
381OSStatus	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
544ErrorExit:
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
559static 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
673ExitThisRoutine:
674
675	return noErr;
676
677ErrorExit:
678
679	(void) ReleaseNode (btreePtr, siblingNode);
680	return err;
681
682} // End of InsertNode
683
684
685/*-------------------------------------------------------------------------------
686Routine:	DeleteTree	-	One_line_description.
687
688Function:	Brief_description_of_the_function_and_any_side_effects
689
690ToDo:
691
692Input:		btreePtr		- description
693			treePathTable	- description
694			targetNode		- description
695			index			- description
696
697Result:		noErr		- success
698			!= noErr	- failure
699-------------------------------------------------------------------------------*/
700
701OSStatus	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
840ErrorExit:
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
853static 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
897ErrorExit:
898	(void)	ReleaseNode (btreePtr, blockPtr);
899	return	err;
900}
901
902
903
904////////////////////////////////// RotateLeft ///////////////////////////////////
905
906/*-------------------------------------------------------------------------------
907
908Routine:	RotateLeft	-	One_line_description.
909
910Function:	Brief_description_of_the_function_and_any_side_effects
911
912Algorithm:	if rightIndex > insertIndex, subtract 1 for actual rightIndex
913
914Input:		btreePtr			- description
915			leftNode			- description
916			rightNode			- description
917			rightInsertIndex	- description
918			keyPtr				- description
919			recPtr				- description
920			recSize				- description
921
922Output:		insertIndex
923			insertNodeNum		- description
924			recordFit			- description
925			recsRotated
926
927Result:		noErr		- success
928			!= noErr	- failure
929-------------------------------------------------------------------------------*/
930
931static 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
1097ErrorExit:
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
1111static 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
1203ErrorExit:
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
1222static 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
1246static 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
1321ErrorExit:
1322
1323	return	err;
1324}
1325
1326
1327static 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
1343static 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
1439ErrorExit:
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
1460Routine:	RotateRight	-	rotate half of .
1461
1462Function:	Brief_description_of_the_function_and_any_side_effects
1463
1464Algorithm:	if rightIndex > insertIndex, subtract 1 for actual rightIndex
1465
1466Input:		btreePtr			- description
1467			leftNode			- description
1468			rightNode			- description
1469			leftInsertIndex		- description
1470			keyPtr				- description
1471			recPtr				- description
1472			recSize				- description
1473
1474Output:		insertIndex
1475			insertNodeNum		- description
1476			recordFit			- description
1477			recsRotated
1478
1479Result:		noErr		- success
1480			!= noErr	- failure
1481-------------------------------------------------------------------------------*/
1482
1483static 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
1691ErrorExit:
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
1706static 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
1730static 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
1776static 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
1825static 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
1832static 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
1845