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