1/*
2 * Copyright (c) 1999, 2005-2006 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:		BTreeNodeOps.c
25
26	Contains:	Single-node operations for the BTree Module.
27
28	Version:	xxx put the technology version here xxx
29
30	Written by:	Gordon Sheridan and Bill Bruffey
31
32	Copyright:	� 1992-1999 by Apple Computer, Inc., all rights reserved.
33*/
34
35#include "BTreePrivate.h"
36#include "hfs_endian.h"
37#include "../fsck_hfs.h"
38
39
40///////////////////////// BTree Module Node Operations //////////////////////////
41//
42//	GetNode 			- Call FS Agent to get node
43//	GetNewNode			- Call FS Agent to get a new node
44//	ReleaseNode			- Call FS Agent to release node obtained by GetNode.
45//	UpdateNode			- Mark a node as dirty and call FS Agent to release it.
46//
47//	ClearNode			- Clear a node to all zeroes.
48//
49//	InsertRecord		- Inserts a record into a BTree node.
50//	InsertKeyRecord		- Inserts a key and record pair into a BTree node.
51//	DeleteRecord		- Deletes a record from a BTree node.
52//
53//	SearchNode			- Return index for record that matches key.
54//	LocateRecord		- Return pointer to key and data, and size of data.
55//
56//	GetNodeDataSize		- Return the amount of space used for data in the node.
57//	GetNodeFreeSize		- Return the amount of free space in the node.
58//
59//	GetRecordOffset		- Return the offset for record "index".
60//	GetRecordAddress	- Return address of record "index".
61//	GetOffsetAddress	- Return address of offset for record "index".
62//
63//	InsertOffset		- Inserts a new offset into a node.
64//	DeleteOffset		- Deletes an offset from a node.
65//
66//	MoveRecordsLeft		- Move records left within a node.
67//	MoveRecordsRight	- Move records right within a node.
68//
69/////////////////////////////////////////////////////////////////////////////////
70
71
72
73////////////////////// Routines Internal To BTreeNodeOps.c //////////////////////
74
75UInt16		GetRecordOffset		(BTreeControlBlockPtr	 btree,
76								 NodeDescPtr			 node,
77								 UInt16					 index );
78
79UInt16	   *GetOffsetAddress	(BTreeControlBlockPtr	btreePtr,
80								 NodeDescPtr			 node,
81								 UInt16					index );
82
83void		InsertOffset		(BTreeControlBlockPtr	 btreePtr,
84								 NodeDescPtr			 node,
85								 UInt16					 index,
86								 UInt16					 delta );
87
88void		DeleteOffset		(BTreeControlBlockPtr	 btreePtr,
89								 NodeDescPtr			 node,
90								 UInt16					 index );
91
92
93/////////////////////////////////////////////////////////////////////////////////
94
95#define GetRecordOffset(btreePtr,node,index)		(*(short *) ((UInt8 *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize))
96
97
98/*-------------------------------------------------------------------------------
99
100Routine:	GetNode	-	Call FS Agent to get node
101
102Function:	Gets an existing BTree node from FS Agent and verifies it.
103
104Input:		btreePtr	- pointer to BTree control block
105			nodeNum		- number of node to request
106
107Output:		nodePtr		- pointer to beginning of node (nil if error)
108
109Result:
110			noErr		- success
111			!= noErr	- failure
112-------------------------------------------------------------------------------*/
113
114OSStatus	GetNode		(BTreeControlBlockPtr	 btreePtr,
115						 UInt32					 nodeNum,
116						 NodeRec				*nodePtr )
117{
118	OSStatus			err;
119	GetBlockProcPtr		getNodeProc;
120
121
122//	LogStartTime(kTraceGetNode);
123
124	//�� is nodeNum within proper range?
125	if( nodeNum >= btreePtr->totalNodes )
126	{
127		Panic("\pGetNode:nodeNum >= totalNodes");
128		if (debug) fprintf(stderr, "%s(%d):  nodeNum %u > totalNodes %u\n", __FUNCTION__, __LINE__, nodeNum, btreePtr->totalNodes);
129		err = fsBTInvalidNodeErr;
130		goto ErrorExit;
131	}
132
133	getNodeProc = btreePtr->getBlockProc;
134	err = getNodeProc (btreePtr->fcbPtr,
135					   nodeNum,
136					   kGetBlock,
137					   nodePtr );
138
139	if (err != noErr)
140	{
141		Panic ("\pGetNode: getNodeProc returned error.");
142		nodePtr->buffer = nil;
143		goto ErrorExit;
144	}
145	++btreePtr->numGetNodes;
146
147	err = hfs_swap_BTNode(nodePtr, btreePtr->fcbPtr, kSwapBTNodeBigToHost);
148	if (err != noErr)
149	{
150		(void) TrashNode (btreePtr, nodePtr);			// ignore error
151		goto ErrorExit;
152	}
153
154//	LogEndTime(kTraceGetNode, noErr);
155
156	return noErr;
157
158ErrorExit:
159	nodePtr->buffer			= nil;
160	nodePtr->blockHeader	= nil;
161
162//	LogEndTime(kTraceGetNode, err);
163
164	return	err;
165}
166
167
168
169/*-------------------------------------------------------------------------------
170
171Routine:	GetNewNode	-	Call FS Agent to get a new node
172
173Function:	Gets a new BTree node from FS Agent and initializes it to an empty
174			state.
175
176Input:		btreePtr		- pointer to BTree control block
177			nodeNum			- number of node to request
178
179Output:		returnNodePtr	- pointer to beginning of node (nil if error)
180
181Result:		noErr		- success
182			!= noErr	- failure
183-------------------------------------------------------------------------------*/
184
185OSStatus	GetNewNode	(BTreeControlBlockPtr	 btreePtr,
186						 UInt32					 nodeNum,
187						 NodeRec				*returnNodePtr )
188{
189	OSStatus			 err;
190	NodeDescPtr			 node;
191	void				*pos;
192	GetBlockProcPtr		 getNodeProc;
193
194
195	//////////////////////// get buffer for new node ////////////////////////////
196
197	getNodeProc = btreePtr->getBlockProc;
198	err = getNodeProc (btreePtr->fcbPtr,
199					   nodeNum,
200					   kGetBlock+kGetEmptyBlock,
201					   returnNodePtr );
202
203	if (err != noErr)
204	{
205		Panic ("\pGetNewNode: getNodeProc returned error.");
206		returnNodePtr->buffer = nil;
207		return err;
208	}
209	++btreePtr->numGetNewNodes;
210
211
212	////////////////////////// initialize the node //////////////////////////////
213
214	node = returnNodePtr->buffer;
215
216	ClearNode (btreePtr, node);						// clear the node
217
218	pos = (char *)node + btreePtr->nodeSize - 2;	// find address of last offset
219	*(UInt16 *)pos = sizeof (BTNodeDescriptor);		// set offset to beginning of free space
220
221
222	return noErr;
223}
224
225
226
227/*-------------------------------------------------------------------------------
228
229Routine:	ReleaseNode	-	Call FS Agent to release node obtained by GetNode.
230
231Function:	Informs the FS Agent that a BTree node may be released.
232
233Input:		btreePtr		- pointer to BTree control block
234			nodeNum			- number of node to release
235
236Result:		noErr		- success
237			!= noErr	- failure
238-------------------------------------------------------------------------------*/
239
240OSStatus	ReleaseNode	(BTreeControlBlockPtr	 btreePtr,
241						 NodePtr				 nodePtr )
242{
243	OSStatus			 err;
244	ReleaseBlockProcPtr	 releaseNodeProc;
245	ReleaseBlockOptions	 options = kReleaseBlock;
246
247//	LogStartTime(kTraceReleaseNode);
248
249	err = noErr;
250
251	if (nodePtr->buffer != nil)
252	{
253		/*
254		 * The nodes must remain in the cache as big endian!
255		 */
256		err = hfs_swap_BTNode(nodePtr, btreePtr->fcbPtr, kSwapBTNodeHostToBig);
257		if (err)
258		{
259			options |= kTrashBlock;
260		}
261
262		releaseNodeProc = btreePtr->releaseBlockProc;
263		err = releaseNodeProc (btreePtr->fcbPtr,
264							   nodePtr,
265							   options );
266		PanicIf (err, "\pReleaseNode: releaseNodeProc returned error.");
267		++btreePtr->numReleaseNodes;
268	}
269
270	nodePtr->buffer = nil;
271	nodePtr->blockHeader = nil;
272
273//	LogEndTime(kTraceReleaseNode, err);
274
275	return err;
276}
277
278
279/*-------------------------------------------------------------------------------
280
281Routine:	TrashNode	-	Call FS Agent to release node obtained by GetNode, and
282							not store it...mark it as bad.
283
284Function:	Informs the FS Agent that a BTree node may be released and thrown away.
285
286Input:		btreePtr		- pointer to BTree control block
287			nodeNum			- number of node to release
288
289Result:		noErr		- success
290			!= noErr	- failure
291-------------------------------------------------------------------------------*/
292
293OSStatus	TrashNode	(BTreeControlBlockPtr	 btreePtr,
294						 NodePtr				 nodePtr )
295{
296	OSStatus			 err;
297	ReleaseBlockProcPtr	 releaseNodeProc;
298
299
300	err = noErr;
301
302	if (nodePtr->buffer != nil)
303	{
304		releaseNodeProc = btreePtr->releaseBlockProc;
305		err = releaseNodeProc (btreePtr->fcbPtr,
306							   nodePtr,
307							   kReleaseBlock | kTrashBlock );
308		PanicIf (err, "\pTrashNode: releaseNodeProc returned error.");
309		++btreePtr->numReleaseNodes;
310	}
311
312	nodePtr->buffer			= nil;
313	nodePtr->blockHeader	= nil;
314
315	return err;
316}
317
318
319/*-------------------------------------------------------------------------------
320
321Routine:	UpdateNode	-	Mark a node as dirty and call FS Agent to release it.
322
323Function:	Marks a BTree node dirty and informs the FS Agent that it may be released.
324
325Input:		btreePtr		- pointer to BTree control block
326			nodeNum			- number of node to release
327
328Result:		noErr		- success
329			!= noErr	- failure
330-------------------------------------------------------------------------------*/
331
332OSStatus	UpdateNode	(BTreeControlBlockPtr	 btreePtr,
333						 NodePtr				 nodePtr )
334{
335	OSStatus			 err;
336	ReleaseBlockProcPtr	 releaseNodeProc;
337	ReleaseBlockOptions	 options = kMarkBlockDirty;
338
339	err = noErr;
340
341	if (nodePtr->buffer != nil)			//�� why call UpdateNode if nil ?!?
342	{
343	//	LogStartTime(kTraceReleaseNode);
344
345		err = hfs_swap_BTNode(nodePtr, btreePtr->fcbPtr, kSwapBTNodeHostToBig);
346		if (err != noErr)
347		{
348			options = kReleaseBlock | kTrashBlock;
349		}
350
351		releaseNodeProc = btreePtr->releaseBlockProc;
352		err = releaseNodeProc (btreePtr->fcbPtr,
353							   nodePtr,
354							   options );
355
356	//	LogEndTime(kTraceReleaseNode, err);
357
358		M_ExitOnError (err);
359		++btreePtr->numUpdateNodes;
360	}
361
362	nodePtr->buffer			= nil;
363	nodePtr->blockHeader	= nil;
364
365	return	noErr;
366
367ErrorExit:
368
369	return	err;
370}
371
372
373
374/*-------------------------------------------------------------------------------
375
376Routine:	ClearNode	-	Clear a node to all zeroes.
377
378Function:	Writes zeroes from beginning of node for nodeSize bytes.
379
380Input:		btreePtr		- pointer to BTree control block
381			node			- pointer to node to clear
382
383Result:		none
384-------------------------------------------------------------------------------*/
385
386void	ClearNode	(BTreeControlBlockPtr	btreePtr, NodeDescPtr	 node )
387{
388	ClearMemory( node, btreePtr->nodeSize );
389}
390
391/*-------------------------------------------------------------------------------
392
393Routine:	InsertRecord	-	Inserts a record into a BTree node.
394
395Function:
396
397Note:		Record size must be even!
398
399Input:		btreePtr		- pointer to BTree control block
400			node			- pointer to node to insert the record
401			index			- position record is to be inserted
402			recPtr			- pointer to record to insert
403
404Result:		noErr		- success
405			fsBTFullErr	- record larger than remaining free space.
406-------------------------------------------------------------------------------*/
407
408Boolean		InsertRecord	(BTreeControlBlockPtr	btreePtr,
409							 NodeDescPtr 			node,
410							 UInt16	 				index,
411							 RecordPtr				recPtr,
412							 UInt16					recSize )
413{
414	UInt16		freeSpace;
415	UInt16		indexOffset;
416	UInt16		freeOffset;
417	UInt16		bytesToMove;
418	void	   *src;
419	void	   *dst;
420
421	//// will new record fit in node?
422
423	freeSpace = GetNodeFreeSize (btreePtr, node);
424											//�� we could get freeOffset & calc freeSpace
425	if ( freeSpace < recSize + 2)
426	{
427		return false;
428	}
429
430
431	//// make hole for new record
432
433	indexOffset = GetRecordOffset (btreePtr, node, index);
434	freeOffset	= GetRecordOffset (btreePtr, node, node->numRecords);
435
436	src = ((Ptr) node) + indexOffset;
437	dst = ((Ptr) src)  + recSize;
438	bytesToMove = freeOffset - indexOffset;
439	MoveRecordsRight (src, dst, bytesToMove);
440
441
442	//// adjust offsets for moved records
443
444	InsertOffset (btreePtr, node, index, recSize);
445
446
447	//// move in the new record
448
449	dst = ((Ptr) node) + indexOffset;
450	MoveRecordsLeft (recPtr, dst, recSize);
451
452	return true;
453}
454
455
456
457/*-------------------------------------------------------------------------------
458
459Routine:	InsertKeyRecord	-	Inserts a record into a BTree node.
460
461Function:
462
463Note:		Record size must be even!
464
465Input:		btreePtr		- pointer to BTree control block
466			node			- pointer to node to insert the record
467			index			- position record is to be inserted
468			keyPtr			- pointer to key for record to insert
469			keyLength		- length of key (or maxKeyLength)
470			recPtr			- pointer to record to insert
471			recSize			- number of bytes to copy for record
472
473Result:		noErr		- success
474			fsBTFullErr	- record larger than remaining free space.
475-------------------------------------------------------------------------------*/
476
477Boolean		InsertKeyRecord		(BTreeControlBlockPtr	 btreePtr,
478								 NodeDescPtr 			 node,
479								 UInt16	 				 index,
480								 KeyPtr					 keyPtr,
481								 UInt16					 keyLength,
482								 RecordPtr				 recPtr,
483								 UInt16					 recSize )
484{
485	UInt16		freeSpace;
486	UInt16		indexOffset;
487	UInt16		freeOffset;
488	UInt16		bytesToMove;
489	UInt8 *		src;
490	UInt8 *		dst;
491	UInt16		keySize;
492	UInt16		rawKeyLength;
493	UInt16		sizeOfLength;
494
495	//// calculate actual key size
496
497	if ( btreePtr->attributes & kBTBigKeysMask )
498		keySize = keyLength + sizeof(UInt16);
499	else
500		keySize = keyLength + sizeof(UInt8);
501
502	if ( M_IsOdd (keySize) )
503		++keySize;			// add pad byte
504
505
506	//// will new record fit in node?
507
508	freeSpace = GetNodeFreeSize (btreePtr, node);
509											//�� we could get freeOffset & calc freeSpace
510	if ( freeSpace < keySize + recSize + 2)
511	{
512		return false;
513	}
514
515
516	//// make hole for new record
517
518	indexOffset = GetRecordOffset (btreePtr, node, index);
519	freeOffset	= GetRecordOffset (btreePtr, node, node->numRecords);
520
521	src = ((UInt8 *) node) + indexOffset;
522	dst = ((UInt8 *) src) + keySize + recSize;
523	bytesToMove = freeOffset - indexOffset;
524	MoveRecordsRight (src, dst, bytesToMove);
525
526
527	//// adjust offsets for moved records
528
529	InsertOffset (btreePtr, node, index, keySize + recSize);
530
531
532	//// copy record key
533
534	dst = ((UInt8 *) node) + indexOffset;
535
536	if ( btreePtr->attributes & kBTBigKeysMask )
537	{
538		*((UInt16 *)dst) = keyLength;					// use keyLength rather than key.length
539		rawKeyLength = keyPtr->length16;
540		sizeOfLength = 2;
541	}
542	else
543	{
544		*dst = keyLength;					// use keyLength rather than key.length
545		rawKeyLength = keyPtr->length8;
546		sizeOfLength = 1;
547	}
548	dst += sizeOfLength;
549
550	MoveRecordsLeft ( ((UInt8 *) keyPtr) + sizeOfLength, dst, rawKeyLength);	// copy key
551
552	// any pad bytes?
553	bytesToMove = keySize - rawKeyLength;
554	if (bytesToMove)
555		ClearMemory (dst + rawKeyLength, bytesToMove);	// clear pad bytes in index key
556
557
558	//// copy record data
559
560	dst = ((UInt8 *) node) + indexOffset + keySize;
561	MoveRecordsLeft (recPtr, dst, recSize);
562
563	return true;
564}
565
566
567
568/*-------------------------------------------------------------------------------
569
570Routine:	DeleteRecord	-	Deletes a record from a BTree node.
571
572Function:
573
574Input:		btreePtr		- pointer to BTree control block
575			node			- pointer to node to insert the record
576			index			- position record is to be inserted
577
578Result:		none
579-------------------------------------------------------------------------------*/
580
581void		DeleteRecord	(BTreeControlBlockPtr	btreePtr,
582							 NodeDescPtr 			node,
583							 UInt16	 				index )
584{
585	SInt16		indexOffset;
586	SInt16		nextOffset;
587	SInt16		freeOffset;
588	SInt16		bytesToMove;
589	void	   *src;
590	void	   *dst;
591
592	//// compress records
593	indexOffset = GetRecordOffset (btreePtr, node, index);
594	nextOffset	= GetRecordOffset (btreePtr, node, index + 1);
595	freeOffset	= GetRecordOffset (btreePtr, node, node->numRecords);
596
597	src = ((Ptr) node) + nextOffset;
598	dst = ((Ptr) node) + indexOffset;
599	bytesToMove = freeOffset - nextOffset;
600	MoveRecordsLeft (src, dst, bytesToMove);
601
602	//// Adjust the offsets
603	DeleteOffset (btreePtr, node, index);
604}
605
606
607
608/*-------------------------------------------------------------------------------
609
610Routine:	SearchNode	-	Return index for record that matches key.
611
612Function:	Returns the record index for the record that matches the search key.
613			If no record was found that matches the search key, the "insert index"
614			of where the record should go is returned instead.
615
616Algorithm:	A binary search algorithm is used to find the specified key.
617
618Input:		btreePtr	- pointer to BTree control block
619			node		- pointer to node that contains the record
620			searchKey	- pointer to the key to match
621
622Output:		index		- pointer to beginning of key for record
623
624Result:		true	- success (index = record index)
625			false	- key did not match anything in node (index = insert index)
626-------------------------------------------------------------------------------*/
627
628Boolean		SearchNode		(BTreeControlBlockPtr	 btreePtr,
629							 NodeDescPtr			 node,
630							 KeyPtr					 searchKey,
631							 UInt16					*returnIndex )
632{
633	SInt32		lowerBound;
634	SInt32		upperBound;
635	SInt32		index;
636	SInt32		result;
637	KeyPtr		trialKey;
638#if !SupportsKeyDescriptors
639	KeyCompareProcPtr	compareProc = btreePtr->keyCompareProc;
640#endif
641
642	lowerBound = 0;
643	upperBound = node->numRecords - 1;
644
645	while (lowerBound <= upperBound)
646	{
647		index = (lowerBound + upperBound) >> 1;		// divide by 2
648
649		trialKey = (KeyPtr) GetRecordAddress (btreePtr, node, index );
650
651	#if SupportsKeyDescriptors
652		result = CompareKeys (btreePtr, searchKey, trialKey);
653	#else
654		result = compareProc(searchKey, trialKey);
655	#endif
656
657		if		(result <  0)		upperBound = index - 1;		// search < trial
658		else if (result >  0)		lowerBound = index + 1;		// search > trial
659		else													// search = trial
660		{
661			*returnIndex = index;
662			return true;
663		}
664	}
665
666	*returnIndex = lowerBound;				// lowerBound is insert index
667	return false;
668}
669
670
671/*-------------------------------------------------------------------------------
672
673Routine:	GetRecordByIndex	-	Return pointer to key and data, and size of data.
674
675Function:	Returns a pointer to beginning of key for record, a pointer to the
676			beginning of the data for the record, and the size of the record data
677			(does not include the size of the key).
678
679Input:		btreePtr	- pointer to BTree control block
680			node		- pointer to node that contains the record
681			index		- index of record to get
682
683Output:		keyPtr		- pointer to beginning of key for record
684			dataPtr		- pointer to beginning of data for record
685			dataSize	- size of the data portion of the record
686
687Result:		none
688-------------------------------------------------------------------------------*/
689
690OSStatus	GetRecordByIndex	(BTreeControlBlockPtr	 btreePtr,
691								 NodeDescPtr			 node,
692								 UInt16					 index,
693								 KeyPtr					*keyPtr,
694								 UInt8 *				*dataPtr,
695								 UInt16					*dataSize )
696{
697	UInt16		offset;
698	UInt16		nextOffset;
699	UInt16		keySize;
700
701	//
702	//	Make sure index is valid (in range 0..numRecords-1)
703	//
704	if (index >= node->numRecords)
705		return fsBTRecordNotFoundErr;
706
707	//// find keyPtr
708	offset		= GetRecordOffset (btreePtr, node, index);
709	*keyPtr		= (KeyPtr) ((Ptr)node + offset);
710
711	//// find dataPtr
712	keySize	= CalcKeySize(btreePtr, *keyPtr);
713	if ( M_IsOdd (keySize) )
714		++keySize;	// add pad byte
715
716	offset += keySize;			// add the key length to find data offset
717	*dataPtr = (UInt8 *) node + offset;
718
719	//// find dataSize
720	nextOffset	= GetRecordOffset (btreePtr, node, index + 1);
721	*dataSize	= nextOffset - offset;
722
723	return noErr;
724}
725
726
727
728/*-------------------------------------------------------------------------------
729
730Routine:	GetNodeDataSize	-	Return the amount of space used for data in the node.
731
732Function:	Gets the size of the data currently contained in a node, excluding
733			the node header. (record data + offset overhead)
734
735Input:		btreePtr		- pointer to BTree control block
736			node			- pointer to node that contains the record
737
738Result:		- number of bytes used for data and offsets in the node.
739-------------------------------------------------------------------------------*/
740
741UInt16		GetNodeDataSize	(BTreeControlBlockPtr	btreePtr, NodeDescPtr	 node )
742{
743	UInt16 freeOffset;
744
745	freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
746
747	return	freeOffset + (node->numRecords << 1) - sizeof (BTNodeDescriptor);
748}
749
750
751
752/*-------------------------------------------------------------------------------
753
754Routine:	GetNodeFreeSize	-	Return the amount of free space in the node.
755
756Function:
757
758Input:		btreePtr		- pointer to BTree control block
759			node			- pointer to node that contains the record
760
761Result:		- number of bytes of free space in the node.
762-------------------------------------------------------------------------------*/
763
764UInt16		GetNodeFreeSize	(BTreeControlBlockPtr	btreePtr, NodeDescPtr	 node )
765{
766	UInt16	freeOffset;
767
768	freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);	//�� inline?
769
770	return btreePtr->nodeSize - freeOffset - (node->numRecords << 1) - kOffsetSize;
771}
772
773
774
775/*-------------------------------------------------------------------------------
776
777Routine:	GetRecordOffset	-	Return the offset for record "index".
778
779Function:
780
781Input:		btreePtr		- pointer to BTree control block
782			node			- pointer to node that contains the record
783			index			- record to obtain offset for
784
785Result:		- offset (in bytes) from beginning of node of record specified by index
786-------------------------------------------------------------------------------*/
787// make this a macro (for inlining)
788#if 0
789UInt16		GetRecordOffset	(BTreeControlBlockPtr	btreePtr,
790							 NodeDescPtr			node,
791							 UInt16					index )
792{
793	void	*pos;
794
795
796	pos = (UInt8 *)node + btreePtr->nodeSize - (index << 1) - kOffsetSize;
797
798	return *(short *)pos;
799}
800#endif
801
802
803
804/*-------------------------------------------------------------------------------
805
806Routine:	GetRecordAddress	-	Return address of record "index".
807
808Function:
809
810Input:		btreePtr		- pointer to BTree control block
811			node			- pointer to node that contains the record
812			index			- record to obtain offset address for
813
814Result:		- pointer to record "index".
815-------------------------------------------------------------------------------*/
816// make this a macro (for inlining)
817#if 0
818UInt8 *		GetRecordAddress	(BTreeControlBlockPtr	btreePtr,
819								 NodeDescPtr			node,
820								 UInt16					index )
821{
822	UInt8 *		pos;
823
824	pos = (UInt8 *)node + GetRecordOffset (btreePtr, node, index);
825
826	return pos;
827}
828#endif
829
830
831
832/*-------------------------------------------------------------------------------
833
834Routine:	GetRecordSize	-	Return size of record "index".
835
836Function:
837
838Note:		This does not work on the FreeSpace index!
839
840Input:		btreePtr		- pointer to BTree control block
841			node			- pointer to node that contains the record
842			index			- record to obtain record size for
843
844Result:		- size of record "index".
845-------------------------------------------------------------------------------*/
846
847UInt16		GetRecordSize		(BTreeControlBlockPtr	btreePtr,
848								 NodeDescPtr			node,
849								 UInt16					index )
850{
851	UInt16	*pos;
852
853	pos = (UInt16 *) ((Ptr)node + btreePtr->nodeSize - (index << 1) - kOffsetSize);
854
855	return  *(pos-1) - *pos;
856}
857
858
859
860/*-------------------------------------------------------------------------------
861Routine:	GetOffsetAddress	-	Return address of offset for record "index".
862
863Function:
864
865Input:		btreePtr		- pointer to BTree control block
866			node			- pointer to node that contains the record
867			index			- record to obtain offset address for
868
869Result:		- pointer to offset for record "index".
870-------------------------------------------------------------------------------*/
871
872UInt16	   *GetOffsetAddress	(BTreeControlBlockPtr	btreePtr,
873								 NodeDescPtr			node,
874								 UInt16					index )
875{
876	void	*pos;
877
878	pos = (Ptr)node + btreePtr->nodeSize - (index << 1) -2;
879
880	return (UInt16 *)pos;
881}
882
883
884
885/*-------------------------------------------------------------------------------
886Routine:	GetChildNodeNum	-	Return child node number from index record "index".
887
888Function:	Returns the first UInt32 stored after the key for record "index".
889
890Assumes:	The node is an Index Node.
891			The key.length stored at record "index" is ODD. //�� change for variable length index keys
892
893Input:		btreePtr		- pointer to BTree control block
894			node			- pointer to node that contains the record
895			index			- record to obtain child node number from
896
897Result:		- child node number from record "index".
898-------------------------------------------------------------------------------*/
899
900UInt32		GetChildNodeNum			(BTreeControlBlockPtr	 btreePtr,
901									 NodeDescPtr			 nodePtr,
902									 UInt16					 index )
903{
904	UInt8 *		pos;
905
906	pos = GetRecordAddress (btreePtr, nodePtr, index);
907	pos += CalcKeySize(btreePtr, (BTreeKey *) pos);		// key.length + size of length field
908
909	return	*(UInt32 *)pos;
910}
911
912
913
914/*-------------------------------------------------------------------------------
915Routine:	InsertOffset	-	Add an offset and adjust existing offsets by delta.
916
917Function:	Add an offset at 'index' by shifting 'index+1' through the last offset
918			and adjusting them by 'delta', the size of the record to be inserted.
919			The number of records contained in the node is also incremented.
920
921Input:		btreePtr	- pointer to BTree control block
922			node		- pointer to node
923			index		- index at which to insert record
924			delta		- size of record to be inserted
925
926Result:		none
927-------------------------------------------------------------------------------*/
928
929void		InsertOffset		(BTreeControlBlockPtr	 btreePtr,
930								 NodeDescPtr			 node,
931								 UInt16					 index,
932								 UInt16					 delta )
933{
934	UInt16		*src, *dst;
935	UInt16		 numOffsets;
936
937	src = GetOffsetAddress (btreePtr, node, node->numRecords);	// point to free offset
938	dst = src - 1; 												// point to new offset
939	numOffsets = node->numRecords++ - index;			// subtract index  & postincrement
940
941	do {
942		*dst++ = *src++ + delta;								// to tricky?
943	} while (numOffsets--);
944}
945
946
947
948/*-------------------------------------------------------------------------------
949
950Routine:	DeleteOffset	-	Delete an offset.
951
952Function:	Delete the offset at 'index' by shifting 'index+1' through the last offset
953			and adjusting them by the size of the record 'index'.
954			The number of records contained in the node is also decremented.
955
956Input:		btreePtr	- pointer to BTree control block
957			node		- pointer to node
958			index		- index at which to delete record
959
960Result:		none
961-------------------------------------------------------------------------------*/
962
963void		DeleteOffset		(BTreeControlBlockPtr	 btreePtr,
964								 NodeDescPtr			 node,
965								 UInt16					 index )
966{
967	UInt16		*src, *dst;
968	UInt16		 numOffsets;
969	UInt16		 delta;
970
971	dst			= GetOffsetAddress (btreePtr, node, index);
972	src			= dst - 1;
973	delta		= *src - *dst;
974	numOffsets	= --node->numRecords - index;	// predecrement numRecords & subtract index
975
976	while (numOffsets--)
977	{
978		*--dst = *--src - delta;				// work our way left
979	}
980}
981
982
983
984/*-------------------------------------------------------------------------------
985
986Routine:	MoveRecordsLeft	-	Move records left within a node.
987
988Function:	Moves a number of bytes from src to dst. Safely handles overlapping
989			ranges if the bytes are being moved to the "left". No bytes are moved
990			if bytesToMove is zero.
991
992Input:		src				- pointer to source
993			dst				- pointer to destination
994			bytesToMove		- number of bytes to move records
995
996Result:		none
997-------------------------------------------------------------------------------*/
998#if 0
999void		MoveRecordsLeft		(UInt8 *				 src,
1000								 UInt8 *				 dst,
1001								 UInt16					 bytesToMove )
1002{
1003	while (bytesToMove--)
1004		*dst++ = *src++;
1005}
1006#endif
1007
1008
1009/*-------------------------------------------------------------------------------
1010
1011Routine:	MoveRecordsRight	-	Move records right within a node.
1012
1013Function:	Moves a number of bytes from src to dst. Safely handles overlapping
1014			ranges if the bytes are being moved to the "right". No bytes are moved
1015			if bytesToMove is zero.
1016
1017Input:		src				- pointer to source
1018			dst				- pointer to destination
1019			bytesToMove		- number of bytes to move records
1020
1021Result:		none
1022-------------------------------------------------------------------------------*/
1023#if 0
1024void		MoveRecordsRight	(UInt8 *				 src,
1025								 UInt8 *				 dst,
1026								 UInt16					 bytesToMove )
1027{
1028	src += bytesToMove;
1029	dst += bytesToMove;
1030
1031	while (bytesToMove--)
1032		*--dst = *--src;
1033}
1034#endif
1035