1/*
2 * Copyright (c) 1999, 2005 Apple Computer, 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:		BTree.c
25
26	Contains:	Implementation of public interface routines for B-tree manager.
27
28	Version:	HFS Plus 1.0
29
30	Written by:	Gordon Sheridan and Bill Bruffey
31
32	Copyright:	� 1992-1999 by Apple Computer, Inc., all rights reserved.
33*/
34
35extern char debug;
36
37#include "BTree.h"
38#include "BTreePrivate.h"
39//#include "HFSInstrumentation.h"
40
41
42extern Boolean NodesAreContiguous(SFCB *fcb, UInt32 nodeSize);
43extern void fplog(FILE *stream, const char *fmt, ...);
44
45/*-------------------------------------------------------------------------------
46Routine:	CopyKey
47
48Function:	Copy a BTree key.  Sanity check the key length; if it is too large,
49			then set the copy's length to the BTree's maximum key length.
50
51Inputs:		btcb		BTree whose key is being copied
52			srcKey		Source key being copied
53
54Output:		destKey		Destination where copy will be stored
55
56Result:		none (void)
57-------------------------------------------------------------------------------*/
58static void CopyKey(BTreeControlBlockPtr btcb, const BTreeKey *srcKey, BTreeKey *destKey)
59{
60	unsigned	keySize = CalcKeySize(btcb, srcKey);
61	unsigned	maxKeySize = MaxKeySize(btcb);
62	int			fixLength = 0;
63
64	/*
65	 *	If the key length is too long (corrupted), then constrain the number
66	 *	of bytes to copy.  Remember that we did this so we can also update
67	 *	the copy's length field later.
68	 */
69	if (keySize > maxKeySize)
70	{
71		keySize = maxKeySize;
72		fixLength = 1;
73	}
74
75	CopyMemory(srcKey, destKey, keySize);
76
77	/*
78	 *	If we had to constrain the key size above, then also update the
79	 *	key length in the copy.  This will prevent the caller from dereferencing
80	 *	part of the key which we never actually copied.
81	 */
82	if (fixLength)
83	{
84		if (btcb->attributes & kBTBigKeysMask)
85			destKey->length16 = btcb->maxKeyLength;
86		else
87			destKey->length8 = btcb->maxKeyLength;
88	}
89}
90
91
92//////////////////////////////////// Globals ////////////////////////////////////
93
94
95/////////////////////////// BTree Module Entry Points ///////////////////////////
96
97
98/*-------------------------------------------------------------------------------
99Routine:	InitBTreeModule	-	Initialize BTree Module Global(s).
100
101Function:	Initialize BTree code, if necessary
102
103Input:		none
104
105Output:		none
106
107Result:		noErr		- success
108			!= noErr	- can't happen
109-------------------------------------------------------------------------------*/
110
111OSStatus	InitBTreeModule(void)
112{
113	return noErr;
114}
115
116
117/*-------------------------------------------------------------------------------
118Routine:	BTInitialize	-	Initialize a fork for access as a B*Tree.
119
120Function:	Write Header node and create any map nodes necessary to map the fork
121			as a B*Tree. If the fork is not large enough for the header node, the
122			FS Agent is called to extend the LEOF. Additional map nodes will be
123			allocated if necessary to represent the size of the fork. This allows
124			the FS Agent to specify the initial size of B*Tree files.
125
126
127Input:		pathPtr			- pointer to path control block
128			maxKeyLength	- maximum length that will be used for any key in this B*Tree
129			nodeSize		- node size for B*Tree (must be 2^n, 9 >= n >= 15)
130			btreeType		- type of B*Tree
131			keyDescPtr		- pointer to key descriptor (optional if key compare proc is used)
132
133Output:		none
134
135Result:		noErr		- success
136			paramErr		- mandatory parameter was missing
137			E_NoGetBlockProc		- FS Agent CB has no GetNodeProcPtr
138			E_NoReleaseBlockProc	- FS Agent CB has no ReleaseNodeProcPtr
139			E_NoSetEndOfForkProc	- FS Agent CB has no SetEndOfForkProcPtr
140			E_NoSetBlockSizeProc	- FS Agent CB has no SetBlockSizeProcPtr
141			fsBTrFileAlreadyOpenErr	- fork is already open as a B*Tree
142			fsBTInvalidKeyLengthErr		- maximum key length is out of range
143			E_BadNodeType			- node size is an illegal value
144			fsBTUnknownVersionErr	- the B*Tree type is unknown by this module
145			memFullErr			- not enough memory to initialize B*Tree
146			!= noErr	- failure
147-------------------------------------------------------------------------------*/
148#if 0
149OSStatus	BTInitialize		(FCB					*filePtr,
150								 UInt16					 maxKeyLength,
151								 UInt16					 nodeSize,
152								 UInt8					 btreeType,
153								 KeyDescriptorPtr		 keyDescPtr )
154{
155	OSStatus				err;
156	FSForkControlBlockPtr	 	forkPtr;
157	BTreeControlBlockPtr	btreePtr;
158	BlockDescriptor			headerNode;
159	HeaderPtr				header;
160	Ptr						pos;
161	FSSize					minEOF, maxEOF;
162	SetEndOfForkProcPtr		setEndOfForkProc;
163	SetBlockSizeProcPtr		setBlockSizeProc;
164
165	////////////////////// Preliminary Error Checking ///////////////////////////
166
167	headerNode.buffer	= nil;
168
169	if (pathPtr										== nil)	return  paramErr;
170
171	setEndOfForkProc	= pathPtr->agentPtr->agent.setEndOfForkProc;
172	setBlockSizeProc	= pathPtr->agentPtr->agent.setBlockSizeProc;
173
174	if (pathPtr->agentPtr->agent.getBlockProc		== nil)	return  E_NoGetBlockProc;
175	if (pathPtr->agentPtr->agent.releaseBlockProc	== nil)	return  E_NoReleaseBlockProc;
176	if (setEndOfForkProc							== nil)	return  E_NoSetEndOfForkProc;
177	if (setBlockSizeProc							== nil)	return  E_NoSetBlockSizeProc;
178
179	forkPtr = pathPtr->path.forkPtr;
180
181	if (forkPtr->fork.btreePtr != nil)						return	fsBTrFileAlreadyOpenErr;
182
183	if ((maxKeyLength == 0) ||
184		(maxKeyLength >  kMaxKeyLength))					return	fsBTInvalidKeyLengthErr;
185
186	if ( M_IsEven (maxKeyLength))	++maxKeyLength;			// len byte + even bytes + pad byte
187
188	switch (nodeSize)										// node size == 512*2^n
189	{
190		case   512:
191		case  1024:
192		case  2048:
193		case  4096:
194		case  8192:
195		case 16384:
196		case 32768:		break;
197		default:		return	E_BadNodeType;
198	}
199
200	switch (btreeType)
201	{
202		case kHFSBTreeType:
203		case kUserBTreeType:
204		case kReservedBTreeType:	break;
205
206		default:					return	fsBTUnknownVersionErr;		//�� right?
207	}
208
209
210	//////////////////////// Allocate Control Block /////////////////////////////
211
212	M_RESIDENT_ALLOCATE_FIXED_CLEAR( &btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType );
213	if (btreePtr == nil)
214	{
215		err = memFullErr;
216		goto ErrorExit;
217	}
218
219	btreePtr->version			= kBTreeVersion;			//�� what is the version?
220	btreePtr->reserved1			= 0;
221	btreePtr->flags				= 0;
222	btreePtr->attributes		= 0;
223	btreePtr->forkPtr			= forkPtr;
224	btreePtr->keyCompareProc	= nil;
225	btreePtr->keyDescPtr		= keyDescPtr;
226	btreePtr->btreeType			= btreeType;
227	btreePtr->treeDepth			= 0;
228	btreePtr->rootNode			= 0;
229	btreePtr->leafRecords		= 0;
230	btreePtr->firstLeafNode		= 0;
231	btreePtr->lastLeafNode		= 0;
232	btreePtr->nodeSize			= nodeSize;
233	btreePtr->maxKeyLength		= maxKeyLength;
234	btreePtr->totalNodes		= 1;			// so ExtendBTree adds maps nodes properly
235	btreePtr->freeNodes			= 0;
236	btreePtr->writeCount		= 1;			//	<CS10>, for BTree scanner
237
238	// set block size = nodeSize
239	err = setBlockSizeProc (forkPtr, nodeSize);
240	M_ExitOnError (err);
241
242	////////////////////////////// Check LEOF ///////////////////////////////////
243
244	minEOF = nodeSize;
245	if ( forkPtr->fork.logicalEOF < minEOF )
246	{
247		// allocate more space if necessary
248		maxEOF 0xFFFFFFFFL;
249
250		err = setEndOfForkProc (forkPtr, minEOF, maxEOF);
251		M_ExitOnError (err);
252	};
253
254
255	//////////////////////// Initialize Header Node /////////////////////////////
256
257	err = GetNewNode (btreePtr, kHeaderNodeNum, &headerNode);
258	M_ExitOnError (err);
259
260	header = headerNode.buffer;
261
262	header->node.type			= kHeaderNode;
263	header->node.numRecords		= 3;			// header rec, key desc, map rec
264
265	header->nodeSize			= nodeSize;
266	header->maxKeyLength		= maxKeyLength;
267	header->btreeType			= btreeType;
268	header->totalNodes			= btreePtr->totalNodes;
269	header->freeNodes			= btreePtr->totalNodes - 1;
270	// ignore					  header->clumpSize;	//�� rename this field?
271
272	// mark header node allocated in map record
273	pos		= ((Ptr)headerNode.buffer) + kHeaderMapRecOffset;
274	*pos	= 0x80;
275
276	// set node offsets ( nodeSize-8, F8, 78, 0E)
277	pos	 = ((Ptr)headerNode.buffer) + nodeSize;
278	pos	-= 2;		*((UInt16 *)pos) = kHeaderRecOffset;
279	pos	-= 2;		*((UInt16 *)pos) = kKeyDescRecOffset;
280	pos -= 2;		*((UInt16 *)pos) = kHeaderMapRecOffset;
281	pos -= 2;		*((UInt16 *)pos) = nodeSize - 8;
282
283
284	///////////////////// Copy Key Descriptor To Header /////////////////////////
285#if SupportsKeyDescriptors
286	if (keyDescPtr != nil)
287	{
288		err = CheckKeyDescriptor (keyDescPtr, maxKeyLength);
289		M_ExitOnError (err);
290
291		// copy to header node
292		pos = ((Ptr)headerNode.buffer) + kKeyDescRecOffset;
293		CopyMemory (keyDescPtr, pos, keyDescPtr->length + 1);
294	}
295#endif
296
297	// write header node
298	err = UpdateNode (btreePtr, &headerNode);
299	M_ExitOnError (err);
300
301
302	////////////////////////// Allocate Map Nodes ///////////////////////////////
303
304	err = ExtendBTree (btreePtr, forkPtr->fork.logicalEOF.lo / nodeSize);	// sets totalNodes
305	M_ExitOnError (err);
306
307
308	////////////////////////////// Close BTree //////////////////////////////////
309
310	err = UpdateHeader (btreePtr);
311	M_ExitOnError (err);
312
313	pathPtr->path.forkPtr->fork.btreePtr = nil;
314	M_RESIDENT_DEALLOCATE_FIXED( btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType );
315
316	return	noErr;
317
318
319	/////////////////////// Error - Clean up and Exit ///////////////////////////
320
321ErrorExit:
322
323	(void) ReleaseNode (btreePtr, &headerNode);
324	if (btreePtr != nil)
325		M_RESIDENT_DEALLOCATE_FIXED( btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType );
326
327	return	err;
328}
329#endif
330
331
332/*-------------------------------------------------------------------------------
333Routine:	BTOpenPath	-	Open a file for access as a B*Tree.
334
335Function:	Create BTree control block for a file, if necessary. Validates the
336			file to be sure it looks like a BTree file.
337
338
339Input:		filePtr				- pointer to file to open as a B-tree
340			keyCompareProc		- pointer to client's KeyCompare function
341			getBlockProc		- pointer to client's GetBlock function
342			releaseBlockProc	- pointer to client's ReleaseBlock function
343			setEndOfForkProc	- pointer to client's SetEOF function
344
345Result:		noErr				- success
346			paramErr			- required ptr was nil
347			fsBTInvalidFileErr				-
348			memFullErr			-
349			!= noErr			- failure
350-------------------------------------------------------------------------------*/
351
352OSStatus	BTOpenPath			(SFCB					*filePtr,
353								 KeyCompareProcPtr		 keyCompareProc,
354								 GetBlockProcPtr		 getBlockProc,
355								 ReleaseBlockProcPtr	 releaseBlockProc,
356								 SetEndOfForkProcPtr	 setEndOfForkProc,
357								 SetBlockSizeProcPtr	 setBlockSizeProc )
358{
359	OSStatus				err;
360	BTreeControlBlockPtr	btreePtr;
361	BTHeaderRec				*header;
362	NodeRec					nodeRec;
363
364//	LogStartTime(kTraceOpenBTree);
365
366	////////////////////// Preliminary Error Checking ///////////////////////////
367
368	if ( filePtr == nil				||
369		 getBlockProc == nil		||
370		 releaseBlockProc == nil	||
371		 setEndOfForkProc == nil	||
372		 setBlockSizeProc == nil )
373	{
374		return  paramErr;
375	}
376
377	if ( filePtr->fcbBtree != nil )			// already has a BTreeCB
378		return noErr;
379
380												// is file large enough to contain header node?
381	if ( filePtr->fcbLogicalSize < kMinNodeSize )
382		return fsBTInvalidFileErr;							//�� or E_BadHeader?
383
384
385	//////////////////////// Allocate Control Block /////////////////////////////
386
387	btreePtr = (BTreeControlBlock*) AllocateClearMemory( sizeof( BTreeControlBlock ) );
388	if (btreePtr == nil)
389	{
390		Panic ("\pBTOpen: no memory for btreePtr.");
391		return	memFullErr;
392	}
393
394	btreePtr->getBlockProc		= getBlockProc;
395	btreePtr->releaseBlockProc	= releaseBlockProc;
396	btreePtr->setEndOfForkProc	= setEndOfForkProc;
397	btreePtr->keyCompareProc	= keyCompareProc;
398
399	/////////////////////////// Read Header Node ////////////////////////////////
400
401	nodeRec.buffer				= nil;				// so we can call ReleaseNode
402
403	btreePtr->fcbPtr			= filePtr;
404	filePtr->fcbBtree			= (void *) btreePtr;	// attach btree cb to file
405
406	// it is now safe to call M_ExitOnError (err)
407
408	err = setBlockSizeProc (btreePtr->fcbPtr, kMinNodeSize);
409	M_ExitOnError (err);
410
411
412	err = getBlockProc (btreePtr->fcbPtr,
413						kHeaderNodeNum,
414						kGetBlock,
415						&nodeRec );
416
417	PanicIf (err != noErr, "\pBTOpen: getNodeProc returned error getting header node.");
418	M_ExitOnError (err);
419
420	header = (BTHeaderRec*) (nodeRec.buffer + sizeof(BTNodeDescriptor));
421
422
423	///////////////////////////// verify header /////////////////////////////////
424
425	err = VerifyHeader (filePtr, header);
426	M_ExitOnError (err);
427
428
429	///////////////////// Initalize fields from header //////////////////////////
430
431	PanicIf ( (filePtr->fcbVolume->vcbSignature != 0x4244) && (btreePtr->nodeSize == 512), "\p BTOpenPath: wrong node size for HFS+ volume!");
432
433	btreePtr->treeDepth			= header->treeDepth;
434	btreePtr->rootNode			= header->rootNode;
435	btreePtr->leafRecords		= header->leafRecords;
436	btreePtr->firstLeafNode		= header->firstLeafNode;
437	btreePtr->lastLeafNode		= header->lastLeafNode;
438	btreePtr->nodeSize			= header->nodeSize;
439	btreePtr->maxKeyLength		= header->maxKeyLength;
440	btreePtr->totalNodes		= header->totalNodes;
441	btreePtr->freeNodes			= header->freeNodes;
442	// ignore					  header->clumpSize;	//�� rename this field?
443	btreePtr->btreeType			= header->btreeType;
444
445	btreePtr->attributes		= header->attributes;
446
447	if ( btreePtr->maxKeyLength > 40 )
448		btreePtr->attributes |= (kBTBigKeysMask + kBTVariableIndexKeysMask);	//�� we need a way to save these attributes
449
450	/////////////////////// Initialize dynamic fields ///////////////////////////
451
452	btreePtr->version			= kBTreeVersion;
453	btreePtr->flags				= 0;
454	btreePtr->writeCount		= 1;		//	<CS10>, for BTree scanner
455
456	btreePtr->numGetNodes		= 1;		// for earlier call to getNodeProc
457
458	/////////////////////////// Check Header Node ///////////////////////////////
459
460	//�� set kBadClose attribute bit, and UpdateNode
461
462	/*
463	 * If the actual node size is different than the amount we read,
464	 * then release and trash this block, and re-read with the correct
465	 * node size.
466	 */
467	if ( btreePtr->nodeSize != kMinNodeSize )
468	{
469		err = setBlockSizeProc (btreePtr->fcbPtr, btreePtr->nodeSize);
470		M_ExitOnError (err);
471
472#if BSD
473		/*
474		 * Need to use kTrashBlock option to force the
475		 * buffer cache to re-read the entire node
476		 */
477		err = releaseBlockProc(btreePtr->fcbPtr, &nodeRec, kTrashBlock);
478#else
479		err = ReleaseNode (btreePtr, &nodeRec);
480#endif
481
482		err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec );		// calls CheckNode...
483		M_ExitOnError (err);
484	}
485
486	//�� total nodes * node size <= LEOF?
487
488
489	////////////////////////// Get Key Descriptor ///////////////////////////////
490#if SupportsKeyDescriptors
491	if ( keyCompareProc == nil )		// 	if no key compare proc then get key descriptor
492	{
493		err = GetKeyDescriptor (btreePtr, nodeRec.buffer);	//�� it should check amount of memory allocated...
494		M_ExitOnError (err);
495
496		err = CheckKeyDescriptor (btreePtr->keyDescPtr, btreePtr->maxKeyLength);
497		M_ExitOnError (err);
498
499	}
500	else
501#endif
502	{
503		btreePtr->keyDescPtr = nil;			// clear it so we don't dispose garbage later
504	}
505
506	err = ReleaseNode (btreePtr, &nodeRec);
507	M_ExitOnError (err);
508
509
510#if BSD
511	/*
512	 * Under Mac OS, b-tree nodes can be non-contiguous on disk when the
513	 * allocation block size is smaller than the b-tree node size.
514	 */
515	if ( !NodesAreContiguous(filePtr, btreePtr->nodeSize) ) {
516		if (debug) fplog(stderr, "Nodes are not contiguous -- this is fatal\n");
517		return fsBTInvalidNodeErr;
518	}
519#endif
520
521	//////////////////////////////// Success ////////////////////////////////////
522
523	//�� align LEOF to multiple of node size?	- just on close
524
525//	LogEndTime(kTraceOpenBTree, noErr);
526
527	return noErr;
528
529
530	/////////////////////// Error - Clean up and Exit ///////////////////////////
531
532ErrorExit:
533
534	filePtr->fcbBtree = nil;
535	(void) ReleaseNode (btreePtr, &nodeRec);
536	DisposeMemory( btreePtr );
537
538//	LogEndTime(kTraceOpenBTree, err);
539
540	return err;
541}
542
543
544
545/*-------------------------------------------------------------------------------
546Routine:	BTClosePath	-	Flush BTree Header and Deallocate Memory for BTree.
547
548Function:	Flush the BTreeControlBlock fields to header node, and delete BTree control
549			block and key descriptor associated with the file if filePtr is last
550			path of type kBTreeType ('btre').
551
552
553Input:		filePtr		- pointer to file to delete BTree control block for.
554
555Result:		noErr			- success
556			fsBTInvalidFileErr	-
557			!= noErr		- failure
558-------------------------------------------------------------------------------*/
559
560OSStatus	BTClosePath			(SFCB					*filePtr)
561{
562	OSStatus				err;
563	BTreeControlBlockPtr	btreePtr;
564#if 0
565	FSPathControlBlockPtr	tempPath;
566	Boolean					otherBTreePathsOpen;
567#endif
568
569//	LogStartTime(kTraceCloseBTree);
570
571	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
572
573	if (btreePtr == nil)
574		return fsBTInvalidFileErr;
575
576	////////////////////// Check for other BTree Paths //////////////////////////
577
578#if 0
579//�� Need replacement field for pathType
580	otherBTreePathsOpen = false;
581	tempPath = forkPtr->fork.pathList.head;
582	while ( (tempPath != (FSPathControlBlockPtr) &forkPtr->fork.pathList) &&
583			(otherBTreePathsOpen == false) )
584	{
585		if ((tempPath != pathPtr) && (tempPath->path.pathType == kBTreeType))
586		{
587			otherBTreePathsOpen = true;
588			break;							// done with loop check
589		}
590
591		tempPath = tempPath->next;
592	}
593
594	////////////////////////// Update Header Node ///////////////////////////////
595
596
597	if (otherBTreePathsOpen == true)
598	{
599		err = UpdateHeader (btreePtr);			// update header even if we aren't closing
600		return err;								// we only clean up after the last user...
601	}
602#endif
603
604	btreePtr->attributes &= ~kBTBadCloseMask;		// clear "bad close" attribute bit
605	err = UpdateHeader (btreePtr);
606	M_ExitOnError (err);
607
608#if SupportsKeyDescriptors
609	if (btreePtr->keyDescPtr != nil)			// deallocate keyDescriptor, if any
610	{
611		DisposeMemory( btreePtr->keyDescPtr );
612	}
613#endif
614
615	DisposeMemory( btreePtr );
616	filePtr->fcbBtree = nil;
617
618//	LogEndTime(kTraceCloseBTree, noErr);
619
620	return	noErr;
621
622	/////////////////////// Error - Clean Up and Exit ///////////////////////////
623
624ErrorExit:
625
626//	LogEndTime(kTraceCloseBTree, err);
627
628	return	err;
629}
630
631
632
633/*-------------------------------------------------------------------------------
634Routine:	BTSearchRecord	-	Search BTree for a record with a matching key.
635
636Function:	Search for position in B*Tree indicated by searchKey. If a valid node hint
637			is provided, it will be searched first, then SearchTree will be called.
638			If a BTreeIterator is provided, it will be set to the position found as
639			a result of the search. If a record exists at that position, and a BufferDescriptor
640			is supplied, the record will be copied to the buffer (as much as will fit),
641			and recordLen will be set to the length of the record.
642
643			If an error other than fsBTRecordNotFoundErr occurs, the BTreeIterator, if any,
644			is invalidated, and recordLen is set to 0.
645
646
647Input:		pathPtr			- pointer to path for BTree file.
648			searchKey		- pointer to search key to match.
649			hintPtr			- pointer to hint (may be nil)
650
651Output:		record			- pointer to BufferDescriptor containing record
652			recordLen		- length of data at recordPtr
653			iterator		- pointer to BTreeIterator indicating position result of search
654
655Result:		noErr			- success, record contains copy of record found
656			fsBTRecordNotFoundErr	- record was not found, no data copied
657			fsBTInvalidFileErr	- no BTreeControlBlock is allocated for the fork
658			fsBTInvalidKeyLengthErr		-
659			!= noErr		- failure
660-------------------------------------------------------------------------------*/
661
662OSStatus	BTSearchRecord		(SFCB						*filePtr,
663								 BTreeIterator				*searchIterator,
664								 UInt32						heuristicHint,
665								 FSBufferDescriptor			*record,
666								 UInt16						*recordLen,
667								 BTreeIterator				*resultIterator )
668{
669	OSStatus				err;
670	BTreeControlBlockPtr	btreePtr;
671	TreePathTable			treePathTable;
672	UInt32					nodeNum = 0;
673	BlockDescriptor			node;
674	UInt16					index;
675	BTreeKeyPtr				keyPtr;
676	RecordPtr				recordPtr;
677	UInt16					len;
678	Boolean					foundRecord;
679	Boolean					validHint;
680
681
682//	LogStartTime(kTraceSearchBTree);
683
684	if (filePtr == nil)									return	paramErr;
685	if (searchIterator == nil)							return	paramErr;
686
687	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
688	if (btreePtr == nil)								return	fsBTInvalidFileErr;
689
690#if SupportsKeyDescriptors
691	if (btreePtr->keyCompareProc == nil)		// CheckKey if we using Key Descriptor
692	{
693		err = CheckKey (&searchIterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength);
694		M_ExitOnError (err);
695	}
696#endif
697
698	foundRecord = false;
699
700	////////////////////////////// Take A Hint //////////////////////////////////
701
702	err = IsItAHint (btreePtr, searchIterator, &validHint);
703	M_ExitOnError (err);
704
705	if (validHint)
706	{
707		nodeNum = searchIterator->hint.nodeNum;
708
709		err = GetNode (btreePtr, nodeNum, &node);
710		if( err == noErr )
711		{
712			if ( ((BTNodeDescriptor*) node.buffer)->kind		== kBTLeafNode &&
713				 ((BTNodeDescriptor*) node.buffer)->numRecords	>  0 )
714			{
715				foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index);
716
717				//�� if !foundRecord, we could still skip tree search if ( 0 < index < numRecords )
718			}
719
720			if (foundRecord == false)
721			{
722				err = ReleaseNode (btreePtr, &node);
723				M_ExitOnError (err);
724			}
725			else
726			{
727				++btreePtr->numValidHints;
728			}
729		}
730
731		if( foundRecord == false )
732			(void) BTInvalidateHint( searchIterator );
733	}
734
735	////////////////////////////// Try the heuristicHint //////////////////////////////////
736
737	if ( (foundRecord == false) && (heuristicHint != kInvalidMRUCacheKey) && (nodeNum != heuristicHint) )
738	{
739	//	LogStartTime(kHeuristicHint);
740		nodeNum = heuristicHint;
741
742		err = GetNode (btreePtr, nodeNum, &node);
743		if( err == noErr )
744		{
745			if ( ((BTNodeDescriptor*) node.buffer)->kind		== kBTLeafNode &&
746				 ((BTNodeDescriptor*) node.buffer)->numRecords	>  0 )
747			{
748				foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index);
749			}
750
751			if (foundRecord == false)
752			{
753				err = ReleaseNode (btreePtr, &node);
754				M_ExitOnError (err);
755			}
756		}
757	//	LogEndTime(kHeuristicHint, (foundRecord == false));
758	}
759
760	//////////////////////////// Search The Tree ////////////////////////////////
761
762	if (foundRecord == false)
763	{
764		err = SearchTree ( btreePtr, &searchIterator->key, treePathTable, &nodeNum, &node, &index);
765		switch (err)
766		{
767			case noErr:			foundRecord = true;				break;
768			case fsBTRecordNotFoundErr:									break;
769			default:				goto ErrorExit;
770		}
771	}
772
773
774	//////////////////////////// Get the Record /////////////////////////////////
775
776	if (foundRecord == true)
777	{
778		//�� Should check for errors! Or BlockMove could choke on recordPtr!!!
779		GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
780
781		if (recordLen != nil)			*recordLen = len;
782
783		if (record != nil)
784		{
785			ByteCount recordSize;
786
787			recordSize = record->itemCount * record->itemSize;
788
789			PanicIf(len > recordSize, "\pBTSearchRecord: truncating record!");
790
791			if (len > recordSize)	len = recordSize;
792
793			CopyMemory (recordPtr, record->bufferAddress, len);
794		}
795	}
796
797
798	/////////////////////// Success - Update Iterator ///////////////////////////
799
800	if (resultIterator != nil)
801	{
802		resultIterator->hint.writeCount	= btreePtr->writeCount;
803		resultIterator->hint.nodeNum	= nodeNum;
804		resultIterator->hint.index		= index;
805		resultIterator->hint.reserved1	= 0;
806		resultIterator->hint.reserved2	= 0;
807
808		resultIterator->version			= 0;
809		resultIterator->reserved		= 0;
810
811		// copy the key in the BTree when found rather than searchIterator->key to get proper case/diacriticals
812		if (foundRecord == true)
813			CopyKey(btreePtr, keyPtr, &resultIterator->key);
814		else
815			CopyKey(btreePtr, &searchIterator->key, &resultIterator->key);
816	}
817
818	err = ReleaseNode (btreePtr, &node);
819	M_ExitOnError (err);
820
821//	LogEndTime(kTraceSearchBTree, (foundRecord == false));
822
823	if (foundRecord == false)	return	fsBTRecordNotFoundErr;
824	else						return	noErr;
825
826
827	/////////////////////// Error - Clean Up and Exit ///////////////////////////
828
829ErrorExit:
830
831	if (recordLen != nil)
832		*recordLen = 0;
833
834	if (resultIterator != nil)
835	{
836		resultIterator->hint.writeCount	= 0;
837		resultIterator->hint.nodeNum	= 0;
838		resultIterator->hint.index		= 0;
839		resultIterator->hint.reserved1	= 0;
840		resultIterator->hint.reserved2	= 0;
841
842		resultIterator->version			= 0;
843		resultIterator->reserved		= 0;
844		resultIterator->key.length16	= 0;	// zero out two bytes to cover both types of keys
845	}
846
847	if ( err == fsBTEmptyErr )
848		err = fsBTRecordNotFoundErr;
849
850//	LogEndTime(kTraceSearchBTree, err);
851
852	return err;
853}
854
855
856
857/*-------------------------------------------------------------------------------
858Routine:	BTIterateRecord	-	Find the first, next, previous, or last record.
859
860Function:	Find the first, next, previous, or last record in the BTree
861
862Input:		pathPtr			- pointer to path iterate records for.
863			operation		- iteration operation (first,next,prev,last)
864			iterator		- pointer to iterator indicating start position
865
866Output:		iterator		- iterator is updated to indicate new position
867			newKeyPtr		- pointer to buffer to copy key found by iteration
868			record			- pointer to buffer to copy record found by iteration
869			recordLen		- length of record
870
871Result:		noErr			- success
872			!= noErr		- failure
873-------------------------------------------------------------------------------*/
874
875OSStatus	BTIterateRecord		(SFCB						*filePtr,
876								 BTreeIterationOperation	 operation,
877								 BTreeIterator				*iterator,
878								 FSBufferDescriptor			*record,
879								 UInt16						*recordLen )
880{
881	OSStatus					err;
882	BTreeControlBlockPtr		btreePtr;
883	BTreeKeyPtr					keyPtr;
884	RecordPtr					recordPtr;
885	UInt16						len;
886
887	Boolean						foundRecord;
888	UInt32						nodeNum;
889
890	BlockDescriptor				left,		node,		right;
891	UInt16						index;
892
893
894//	LogStartTime(kTraceGetBTreeRecord);
895
896	////////////////////////// Priliminary Checks ///////////////////////////////
897
898	left.buffer		= nil;
899	right.buffer	= nil;
900	node.buffer		= nil;
901
902
903	if (filePtr == nil)
904	{
905		return	paramErr;
906	}
907
908	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
909	if (btreePtr == nil)
910	{
911		return	fsBTInvalidFileErr;			//�� handle properly
912	}
913
914	if ((operation != kBTreeFirstRecord)	&&
915		(operation != kBTreeNextRecord)		&&
916		(operation != kBTreeCurrentRecord)	&&
917		(operation != kBTreePrevRecord)		&&
918		(operation != kBTreeLastRecord))
919	{
920		err = fsInvalidIterationMovmentErr;
921		goto ErrorExit;
922	}
923
924	/////////////////////// Find First or Last Record ///////////////////////////
925
926	if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord))
927	{
928		if (operation == kBTreeFirstRecord)		nodeNum = btreePtr->firstLeafNode;
929		else									nodeNum = btreePtr->lastLeafNode;
930
931		if (nodeNum == 0)
932		{
933			err = fsBTEmptyErr;
934			goto ErrorExit;
935		}
936
937		err = GetNode (btreePtr, nodeNum, &node);
938		M_ExitOnError (err);
939
940		if ( ((NodeDescPtr) node.buffer)->kind			!= kBTLeafNode ||
941			 ((NodeDescPtr) node.buffer)->numRecords	<=  0 )
942		{
943			err = ReleaseNode (btreePtr, &node);
944			M_ExitOnError (err);
945
946			if (debug) fprintf(stderr, "%s(%d): returning fsBTInvalidNodeErr\n", __FUNCTION__, __LINE__);
947			err = fsBTInvalidNodeErr;
948			goto ErrorExit;
949		}
950
951		if (operation == kBTreeFirstRecord)		index = 0;
952		else									index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1;
953
954		goto CopyData;						//�� is there a cleaner way?
955	}
956
957
958	//////////////////////// Find Iterator Position /////////////////////////////
959
960	err = FindIteratorPosition (btreePtr, iterator,
961								&left, &node, &right, &nodeNum, &index, &foundRecord);
962	M_ExitOnError (err);
963
964
965	///////////////////// Find Next Or Previous Record //////////////////////////
966
967	if (operation == kBTreePrevRecord)
968	{
969		if (index > 0)
970		{
971			--index;
972		}
973		else
974		{
975			if (left.buffer == nil)
976			{
977				nodeNum = ((NodeDescPtr) node.buffer)->bLink;
978				if ( nodeNum > 0)
979				{
980					err = GetNode (btreePtr, nodeNum, &left);
981					M_ExitOnError (err);
982				} else {
983					err = fsBTStartOfIterationErr;
984					goto ErrorExit;
985				}
986			}
987			//	Before we stomp on "right", we'd better release it if needed
988			if (right.buffer != nil) {
989				err = ReleaseNode(btreePtr, &right);
990				M_ExitOnError(err);
991			}
992			right		= node;
993			node		= left;
994			left.buffer	= nil;
995			index 		= ((NodeDescPtr) node.buffer)->numRecords -1;
996		}
997	}
998	else if (operation == kBTreeNextRecord)
999	{
1000		if ((foundRecord != true) &&
1001			(((NodeDescPtr) node.buffer)->fLink == 0) &&
1002			(index == ((NodeDescPtr) node.buffer)->numRecords))
1003		{
1004			err = fsBTEndOfIterationErr;
1005			goto ErrorExit;
1006		}
1007
1008		// we did not find the record but the index is already positioned correctly
1009		if ((foundRecord == false) && (index != ((NodeDescPtr) node.buffer)->numRecords))
1010			goto CopyData;
1011
1012		// we found the record OR we have to look in the next node
1013		if (index < ((NodeDescPtr) node.buffer)->numRecords -1)
1014		{
1015			++index;
1016		}
1017		else
1018		{
1019			if (right.buffer == nil)
1020			{
1021				nodeNum = ((NodeDescPtr) node.buffer)->fLink;
1022				if ( nodeNum > 0)
1023				{
1024					err = GetNode (btreePtr, nodeNum, &right);
1025					M_ExitOnError (err);
1026				} else {
1027					err = fsBTEndOfIterationErr;
1028					goto ErrorExit;
1029				}
1030			}
1031			//	Before we stomp on "left", we'd better release it if needed
1032			if (left.buffer != nil) {
1033				err = ReleaseNode(btreePtr, &left);
1034				M_ExitOnError(err);
1035			}
1036			left		 = node;
1037			node		 = right;
1038			right.buffer = nil;
1039			index		 = 0;
1040		}
1041	}
1042	else // operation == kBTreeCurrentRecord
1043	{
1044		// make sure we have something... <CS9>
1045		if ((foundRecord != true) &&
1046			(index >= ((NodeDescPtr) node.buffer)->numRecords))
1047		{
1048			err = fsBTEndOfIterationErr;
1049			goto ErrorExit;
1050		}
1051	}
1052
1053	//////////////////// Copy Record And Update Iterator ////////////////////////
1054
1055CopyData:
1056
1057	// added check for errors <CS9>
1058	err = GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
1059	M_ExitOnError (err);
1060
1061	if (recordLen != nil)			*recordLen = len;
1062
1063	if (record != nil)
1064	{
1065		ByteCount recordSize;
1066
1067		recordSize = record->itemCount * record->itemSize;
1068
1069		PanicIf(len > recordSize, "\pBTIterateRecord: truncating record!");
1070
1071		if (len > recordSize)	len = recordSize;
1072
1073		CopyMemory (recordPtr, record->bufferAddress, len);
1074	}
1075
1076	if (iterator != nil)						// first & last do not require iterator
1077	{
1078		iterator->hint.writeCount	= btreePtr->writeCount;
1079		iterator->hint.nodeNum		= nodeNum;
1080		iterator->hint.index		= index;
1081		iterator->hint.reserved1	= 0;
1082		iterator->hint.reserved2	= 0;
1083
1084		iterator->version			= 0;
1085		iterator->reserved			= 0;
1086
1087		CopyKey(btreePtr, keyPtr, &iterator->key);
1088	}
1089
1090
1091	///////////////////////////// Release Nodes /////////////////////////////////
1092
1093	err = ReleaseNode (btreePtr, &node);
1094	M_ExitOnError (err);
1095
1096	if (left.buffer != nil)
1097	{
1098		err = ReleaseNode (btreePtr, &left);
1099		M_ExitOnError (err);
1100	}
1101
1102	if (right.buffer != nil)
1103	{
1104		err = ReleaseNode (btreePtr, &right);
1105		M_ExitOnError (err);
1106	}
1107
1108//	LogEndTime(kTraceGetBTreeRecord, noErr);
1109
1110	return noErr;
1111
1112	/////////////////////// Error - Clean Up and Exit ///////////////////////////
1113
1114ErrorExit:
1115
1116	(void)	ReleaseNode (btreePtr, &left);
1117	(void)	ReleaseNode (btreePtr, &node);
1118	(void)	ReleaseNode (btreePtr, &right);
1119
1120	if (recordLen != nil)
1121		*recordLen = 0;
1122
1123	if (iterator != nil)
1124	{
1125		iterator->hint.writeCount	= 0;
1126		iterator->hint.nodeNum		= 0;
1127		iterator->hint.index		= 0;
1128		iterator->hint.reserved1	= 0;
1129		iterator->hint.reserved2	= 0;
1130
1131		iterator->version			= 0;
1132		iterator->reserved			= 0;
1133		iterator->key.length16		= 0;
1134	}
1135
1136	if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
1137		err = fsBTRecordNotFoundErr;
1138
1139//	LogEndTime(kTraceGetBTreeRecord, err);
1140
1141	return err;
1142}
1143
1144
1145//////////////////////////////// BTInsertRecord /////////////////////////////////
1146
1147OSStatus	BTInsertRecord		(SFCB						*filePtr,
1148								 BTreeIterator				*iterator,
1149								 FSBufferDescriptor			*record,
1150								 UInt16						 recordLen )
1151{
1152	OSStatus				err;
1153	BTreeControlBlockPtr	btreePtr;
1154	TreePathTable			treePathTable;
1155	SInt32					nodesNeeded;
1156	BlockDescriptor			nodeRec;
1157	UInt32					insertNodeNum;
1158	UInt16					index;
1159	Boolean					recordFit;
1160
1161
1162	////////////////////////// Priliminary Checks ///////////////////////////////
1163
1164	nodeRec.buffer = nil;					// so we can call ReleaseNode
1165
1166	err = CheckInsertParams (filePtr, iterator, record, recordLen);
1167	if (err != noErr)
1168		return	err;
1169
1170//	LogStartTime(kTraceInsertBTreeRecord);
1171
1172	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1173
1174	///////////////////////// Find Insert Position //////////////////////////////
1175
1176	// always call SearchTree for Insert
1177	err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1178
1179	switch (err)				// set/replace/insert decision point
1180	{
1181		case noErr:			err = fsBTDuplicateRecordErr;
1182							goto ErrorExit;
1183
1184		case fsBTRecordNotFoundErr:	break;
1185
1186		case fsBTEmptyErr:	// if tree empty add 1st leaf node
1187
1188			if (btreePtr->freeNodes == 0)
1189			{
1190				err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
1191				M_ExitOnError (err);
1192			}
1193
1194			err = AllocateNode (btreePtr, &insertNodeNum);
1195			M_ExitOnError (err);
1196
1197			err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
1198			M_ExitOnError (err);
1199
1200			((NodeDescPtr)nodeRec.buffer)->kind		= kBTLeafNode;
1201			((NodeDescPtr)nodeRec.buffer)->height	= 1;
1202
1203			recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0,
1204										 &iterator->key, KeyLength(btreePtr, &iterator->key),
1205										 record->bufferAddress, recordLen );
1206			if (recordFit != true)
1207			{
1208				err = fsBTRecordTooLargeErr;
1209				goto ErrorExit;
1210			}
1211
1212			err = UpdateNode (btreePtr, &nodeRec);
1213			M_ExitOnError (err);
1214
1215			// update BTreeControlBlock
1216			btreePtr->treeDepth	 		= 1;
1217			btreePtr->rootNode	 		= insertNodeNum;
1218			btreePtr->firstLeafNode		= insertNodeNum;
1219			btreePtr->lastLeafNode		= insertNodeNum;
1220			M_BTreeHeaderDirty (btreePtr);
1221
1222			goto Success;
1223
1224		default:
1225			goto ErrorExit;
1226	}
1227
1228	if (index > 0)
1229	{
1230		recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
1231										&iterator->key, KeyLength(btreePtr, &iterator->key),
1232										record->bufferAddress, recordLen);
1233		if (recordFit == true)
1234		{
1235			err = UpdateNode (btreePtr, &nodeRec);
1236			M_ExitOnError (err);
1237
1238			goto Success;
1239		}
1240	}
1241
1242	/////////////////////// Extend File If Necessary ////////////////////////////
1243
1244	nodesNeeded =  btreePtr->treeDepth + 1 - btreePtr->freeNodes;	//�� math limit
1245	if (nodesNeeded > 0)
1246	{
1247		nodesNeeded += btreePtr->totalNodes;
1248		if (nodesNeeded > CalcMapBits (btreePtr))	// we'll need to add a map node too!
1249			++nodesNeeded;
1250
1251		err = ExtendBTree (btreePtr, nodesNeeded);
1252		M_ExitOnError (err);
1253	}
1254
1255	// no need to delete existing record
1256
1257	err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1258					  recordLen, &nodeRec, index, 1, kInsertRecord, &insertNodeNum);
1259	M_ExitOnError (err);
1260
1261
1262	//////////////////////////////// Success ////////////////////////////////////
1263
1264Success:
1265	++btreePtr->writeCount;				//	<CS10>
1266	++btreePtr->leafRecords;
1267	M_BTreeHeaderDirty (btreePtr);
1268
1269	// create hint
1270	iterator->hint.writeCount 	= btreePtr->writeCount;		//	unused until <CS10>
1271	iterator->hint.nodeNum		= insertNodeNum;
1272	iterator->hint.index		= 0;						// unused
1273	iterator->hint.reserved1	= 0;
1274	iterator->hint.reserved2	= 0;
1275
1276//	LogEndTime(kTraceInsertBTreeRecord, noErr);
1277
1278	return noErr;
1279
1280
1281	////////////////////////////// Error Exit ///////////////////////////////////
1282
1283ErrorExit:
1284	(void) ReleaseNode (btreePtr, &nodeRec);
1285
1286	iterator->hint.writeCount 	= 0;
1287	iterator->hint.nodeNum		= 0;
1288	iterator->hint.index		= 0;
1289	iterator->hint.reserved1	= 0;
1290	iterator->hint.reserved2	= 0;
1291
1292	if (err == fsBTEmptyErr)
1293		err = fsBTRecordNotFoundErr;
1294
1295//	LogEndTime(kTraceInsertBTreeRecord, err);
1296
1297	return err;
1298}
1299
1300
1301
1302////////////////////////////////// BTSetRecord //////////////////////////////////
1303#if 0
1304OSStatus	BTSetRecord			(SFCB						*filePtr,
1305								 BTreeIterator				*iterator,
1306								 FSBufferDescriptor			*record,
1307								 UInt16						 recordLen )
1308{
1309	OSStatus				err;
1310	BTreeControlBlockPtr	btreePtr;
1311	TreePathTable			treePathTable;
1312	SInt32					nodesNeeded;
1313	BlockDescriptor			nodeRec;
1314	UInt32					insertNodeNum;
1315	UInt16					index;
1316	Boolean					recordFound = false;
1317	Boolean					recordFit;
1318	Boolean					operation;
1319	Boolean					validHint;
1320
1321
1322	////////////////////////// Priliminary Checks ///////////////////////////////
1323
1324	nodeRec.buffer = nil;					// so we can call ReleaseNode
1325
1326	err = CheckInsertParams (filePtr, iterator, record, recordLen);
1327	if (err != noErr)
1328		return	err;
1329
1330	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1331
1332
1333	///////////////////////// Find Insert Position //////////////////////////////
1334
1335	err = IsItAHint (btreePtr, iterator, &validHint);
1336	M_ExitOnError (err);
1337
1338	if (validHint)
1339	{
1340		insertNodeNum = iterator->hint.nodeNum;
1341
1342		err = GetNode (btreePtr, insertNodeNum, &nodeRec);
1343		if( err == noErr )
1344		{
1345			err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1346			M_ExitOnError (err);
1347
1348			if (recordFit)
1349			{
1350				err = UpdateNode (btreePtr, &nodeRec);
1351				M_ExitOnError (err);
1352
1353				recordFound = true;
1354				++btreePtr->numValidHints;
1355				goto Success;
1356			} 											// else
1357			else
1358			{
1359				(void) BTInvalidateHint( iterator );
1360			}
1361
1362			err = ReleaseNode (btreePtr, &nodeRec);
1363			M_ExitOnError (err);
1364		}
1365	}
1366
1367	err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1368
1369	switch (err)				// set/replace/insert decision point
1370	{
1371		case noErr:			recordFound = true;
1372								break;
1373
1374		case fsBTRecordNotFoundErr:	break;
1375
1376		case fsBTEmptyErr:	// if tree empty add 1st leaf node
1377
1378								if (btreePtr->freeNodes == 0)
1379								{
1380									err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
1381									M_ExitOnError (err);
1382								}
1383
1384								err = AllocateNode (btreePtr, &insertNodeNum);
1385								M_ExitOnError (err);
1386
1387								err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
1388								M_ExitOnError (err);
1389
1390								((NodeDescPtr)nodeRec.buffer)->kind		= kBTLeafNode;
1391								((NodeDescPtr)nodeRec.buffer)->height	= 1;
1392
1393								recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0,
1394															 &iterator->key, KeyLength(btreePtr, &iterator->key),
1395															 record->bufferAddress, recordLen );
1396								if (recordFit != true)
1397								{
1398									err = fsBTRecordTooLargeErr;
1399									goto ErrorExit;
1400								}
1401
1402								err = UpdateNode (btreePtr, &nodeRec);
1403								M_ExitOnError (err);
1404
1405								// update BTreeControlBlock
1406								btreePtr->rootNode	 = insertNodeNum;
1407								btreePtr->treeDepth	 = 1;
1408								btreePtr->flags		|= kBTHeaderDirty;
1409
1410								goto Success;
1411
1412		default:				goto ErrorExit;
1413	}
1414
1415
1416	if (recordFound == true)		// Simple Replace - optimization avoids unecessary ExtendBTree
1417	{
1418		err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1419		M_ExitOnError (err);
1420
1421		if (recordFit)
1422		{
1423			err = UpdateNode (btreePtr, &nodeRec);
1424			M_ExitOnError (err);
1425
1426			goto Success;
1427		}
1428	}
1429
1430
1431	/////////////////////// Extend File If Necessary ////////////////////////////
1432
1433	nodesNeeded =  btreePtr->treeDepth + 1 - btreePtr->freeNodes;	//�� math limit
1434	if (nodesNeeded > 0)
1435	{
1436		nodesNeeded += btreePtr->totalNodes;
1437		if (nodesNeeded > CalcMapBits (btreePtr))	// we'll need to add a map node too!
1438			++nodesNeeded;
1439
1440		err = ExtendBTree (btreePtr, nodesNeeded);
1441		M_ExitOnError (err);
1442	}
1443
1444
1445	if (recordFound == true)							// Delete existing record
1446	{
1447		DeleteRecord (btreePtr, nodeRec.buffer, index);
1448		operation = kReplaceRecord;
1449	} else {
1450		operation = kInsertRecord;
1451	}
1452
1453	err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1454					  recordLen, &nodeRec, index, 1, operation, &insertNodeNum);
1455	M_ExitOnError (err);
1456
1457	++btreePtr->writeCount;				//	<CS10> writeCount changes only if the tree structure changed
1458
1459Success:
1460	if (recordFound == false)
1461	{
1462		++btreePtr->leafRecords;
1463		M_BTreeHeaderDirty (btreePtr);
1464	}
1465
1466	// create hint
1467	iterator->hint.writeCount 	= btreePtr->writeCount;		//	unused until <CS10>
1468	iterator->hint.nodeNum		= insertNodeNum;
1469	iterator->hint.index		= 0;						// unused
1470	iterator->hint.reserved1	= 0;
1471	iterator->hint.reserved2	= 0;
1472
1473	return noErr;
1474
1475
1476	////////////////////////////// Error Exit ///////////////////////////////////
1477
1478ErrorExit:
1479
1480	(void) ReleaseNode (btreePtr, &nodeRec);
1481
1482	iterator->hint.writeCount 	= 0;
1483	iterator->hint.nodeNum		= 0;
1484	iterator->hint.index		= 0;
1485	iterator->hint.reserved1	= 0;
1486	iterator->hint.reserved2	= 0;
1487
1488	return err;
1489}
1490#endif
1491
1492
1493//////////////////////////////// BTReplaceRecord ////////////////////////////////
1494
1495OSStatus	BTReplaceRecord		(SFCB						*filePtr,
1496								 BTreeIterator				*iterator,
1497								 FSBufferDescriptor			*record,
1498								 UInt16						 recordLen )
1499{
1500	OSStatus				err;
1501	BTreeControlBlockPtr	btreePtr;
1502	TreePathTable			treePathTable;
1503	SInt32					nodesNeeded;
1504	BlockDescriptor			nodeRec;
1505	UInt32					insertNodeNum;
1506	UInt16					index;
1507	Boolean					recordFit;
1508	Boolean					validHint;
1509
1510
1511	////////////////////////// Priliminary Checks ///////////////////////////////
1512
1513	nodeRec.buffer = nil;					// so we can call ReleaseNode
1514
1515	err = CheckInsertParams (filePtr, iterator, record, recordLen);
1516	if (err != noErr)
1517		return err;
1518
1519//	LogStartTime(kTraceReplaceBTreeRecord);
1520
1521	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1522
1523	////////////////////////////// Take A Hint //////////////////////////////////
1524
1525	err = IsItAHint (btreePtr, iterator, &validHint);
1526	M_ExitOnError (err);
1527
1528	if (validHint)
1529	{
1530		insertNodeNum = iterator->hint.nodeNum;
1531
1532		err = GetNode (btreePtr, insertNodeNum, &nodeRec);
1533		if( err == noErr )
1534		{
1535			err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1536			M_ExitOnError (err);
1537
1538			if (recordFit)
1539			{
1540				err = UpdateNode (btreePtr, &nodeRec);
1541				M_ExitOnError (err);
1542
1543				++btreePtr->numValidHints;
1544
1545				goto Success;
1546			}
1547			else
1548			{
1549				(void) BTInvalidateHint( iterator );
1550			}
1551
1552			err = ReleaseNode (btreePtr, &nodeRec);
1553			M_ExitOnError (err);
1554		}
1555		else
1556		{
1557			(void) BTInvalidateHint( iterator );
1558		}
1559	}
1560
1561
1562	////////////////////////////// Get A Clue ///////////////////////////////////
1563
1564	err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1565	M_ExitOnError (err);					// record must exit for Replace
1566
1567	// optimization - if simple replace will work then don't extend btree
1568	// �� if we tried this before, and failed because it wouldn't fit then we shouldn't try this again...
1569
1570	err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1571	M_ExitOnError (err);
1572
1573	if (recordFit)
1574	{
1575		err = UpdateNode (btreePtr, &nodeRec);
1576		M_ExitOnError (err);
1577
1578		goto Success;
1579	}
1580
1581
1582	//////////////////////////// Make Some Room /////////////////////////////////
1583
1584	nodesNeeded =  btreePtr->treeDepth + 1 - btreePtr->freeNodes;	//�� math limit
1585	if (nodesNeeded > 0)
1586	{
1587		nodesNeeded += btreePtr->totalNodes;
1588		if (nodesNeeded > CalcMapBits (btreePtr))	// we'll need to add a map node too!
1589			++nodesNeeded;
1590
1591		err = ExtendBTree (btreePtr, nodesNeeded);
1592		M_ExitOnError (err);
1593	}
1594
1595
1596	DeleteRecord (btreePtr, nodeRec.buffer, index);	// delete existing key/record
1597
1598	err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1599					  recordLen, &nodeRec, index, 1, kReplaceRecord, &insertNodeNum);
1600	M_ExitOnError (err);
1601
1602	++btreePtr->writeCount;				//	<CS10> writeCount changes only if the tree structure changed
1603
1604Success:
1605	// create hint
1606	iterator->hint.writeCount 	= btreePtr->writeCount;		//	unused until <CS10>
1607	iterator->hint.nodeNum		= insertNodeNum;
1608	iterator->hint.index		= 0;						// unused
1609	iterator->hint.reserved1	= 0;
1610	iterator->hint.reserved2	= 0;
1611
1612//	LogEndTime(kTraceReplaceBTreeRecord, noErr);
1613
1614	return noErr;
1615
1616
1617	////////////////////////////// Error Exit ///////////////////////////////////
1618
1619ErrorExit:
1620
1621	(void) ReleaseNode (btreePtr, &nodeRec);
1622
1623	iterator->hint.writeCount 	= 0;
1624	iterator->hint.nodeNum		= 0;
1625	iterator->hint.index		= 0;
1626	iterator->hint.reserved1	= 0;
1627	iterator->hint.reserved2	= 0;
1628
1629//	LogEndTime(kTraceReplaceBTreeRecord, err);
1630
1631	return err;
1632}
1633
1634
1635
1636//////////////////////////////// BTDeleteRecord /////////////////////////////////
1637
1638OSStatus	BTDeleteRecord		(SFCB						*filePtr,
1639								 BTreeIterator				*iterator )
1640{
1641	OSStatus				err;
1642	BTreeControlBlockPtr	btreePtr;
1643	TreePathTable			treePathTable;
1644	BlockDescriptor			nodeRec;
1645	UInt32					nodeNum;
1646	UInt16					index;
1647
1648//	LogStartTime(kTraceDeleteBTreeRecord);
1649
1650	////////////////////////// Priliminary Checks ///////////////////////////////
1651
1652	nodeRec.buffer = nil;					// so we can call ReleaseNode
1653
1654	M_ReturnErrorIf (filePtr == nil, 	paramErr);
1655	M_ReturnErrorIf (iterator == nil,	paramErr);
1656
1657	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1658	if (btreePtr == nil)
1659	{
1660		err = fsBTInvalidFileErr;
1661		goto ErrorExit;
1662	}
1663
1664#if SupportsKeyDescriptors
1665	if (btreePtr->keyDescPtr != nil)
1666	{
1667		err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength);
1668		M_ExitOnError (err);
1669	}
1670#endif
1671
1672	/////////////////////////////// Find Key ////////////////////////////////////
1673
1674	//�� check hint for simple delete case (index > 0, numRecords > 2)
1675
1676	err = SearchTree (btreePtr, &iterator->key, treePathTable, &nodeNum, &nodeRec, &index);
1677	M_ExitOnError (err);					// record must exit for Delete
1678
1679
1680	///////////////////////////// Delete Record /////////////////////////////////
1681
1682	err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1);
1683	M_ExitOnError (err);
1684
1685//Success:
1686	++btreePtr->writeCount;				//	<CS10>
1687	--btreePtr->leafRecords;
1688	M_BTreeHeaderDirty (btreePtr);
1689
1690	iterator->hint.nodeNum	= 0;
1691
1692//	LogEndTime(kTraceDeleteBTreeRecord, noErr);
1693
1694	return noErr;
1695
1696	////////////////////////////// Error Exit ///////////////////////////////////
1697
1698ErrorExit:
1699	(void) ReleaseNode (btreePtr, &nodeRec);
1700
1701//	LogEndTime(kTraceDeleteBTreeRecord, err);
1702
1703	return	err;
1704}
1705
1706
1707
1708OSStatus	BTGetInformation	(SFCB					*filePtr,
1709								 UInt16					 version,
1710								 BTreeInfoRec			*info )
1711{
1712#pragma unused (version)
1713
1714	BTreeControlBlockPtr	btreePtr;
1715
1716
1717	M_ReturnErrorIf (filePtr == nil, 	paramErr);
1718
1719	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1720
1721	M_ReturnErrorIf (btreePtr == nil,	fsBTInvalidFileErr);
1722	M_ReturnErrorIf (info == nil,		paramErr);
1723
1724	//�� check version?
1725
1726	info->nodeSize		= btreePtr->nodeSize;
1727	info->maxKeyLength	= btreePtr->maxKeyLength;
1728	info->treeDepth		= btreePtr->treeDepth;
1729	info->numRecords	= btreePtr->leafRecords;
1730	info->numNodes		= btreePtr->totalNodes;
1731	info->numFreeNodes	= btreePtr->freeNodes;
1732	info->keyDescriptor	= btreePtr->keyDescPtr;	//�� this won't do at all...
1733	info->reserved		= 0;
1734
1735	if (btreePtr->keyDescPtr == nil)
1736		info->keyDescLength	= 0;
1737	else
1738		info->keyDescLength	= (UInt32) btreePtr->keyDescPtr->length;
1739
1740	return noErr;
1741}
1742
1743
1744
1745/*-------------------------------------------------------------------------------
1746Routine:	BTFlushPath	-	Flush BTreeControlBlock to Header Node.
1747
1748Function:	Brief_description_of_the_function_and_any_side_effects
1749
1750
1751Input:		pathPtr		- pointer to path control block for B*Tree file to flush
1752
1753Output:		none
1754
1755Result:		noErr		- success
1756			!= noErr	- failure
1757-------------------------------------------------------------------------------*/
1758
1759OSStatus	BTFlushPath				(SFCB					*filePtr)
1760{
1761	OSStatus				err;
1762	BTreeControlBlockPtr	btreePtr;
1763
1764
1765//	LogStartTime(kTraceFlushBTree);
1766
1767	M_ReturnErrorIf (filePtr == nil, 	paramErr);
1768
1769	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1770
1771	M_ReturnErrorIf (btreePtr == nil,	fsBTInvalidFileErr);
1772
1773	err = UpdateHeader (btreePtr);
1774
1775//	LogEndTime(kTraceFlushBTree, err);
1776
1777	return	err;
1778}
1779
1780
1781
1782/*-------------------------------------------------------------------------------
1783Routine:	BTInvalidateHint	-	Invalidates the hint within a BTreeInterator.
1784
1785Function:	Invalidates the hint within a BTreeInterator.
1786
1787
1788Input:		iterator	- pointer to BTreeIterator
1789
1790Output:		iterator	- iterator with the hint.nodeNum cleared
1791
1792Result:		noErr			- success
1793			paramErr	- iterator == nil
1794-------------------------------------------------------------------------------*/
1795
1796
1797OSStatus	BTInvalidateHint	(BTreeIterator				*iterator )
1798{
1799	if (iterator == nil)
1800		return	paramErr;
1801
1802	iterator->hint.nodeNum = 0;
1803
1804	return	noErr;
1805}
1806
1807