1/*
2 * Copyright (c) 1999-2008 Apple Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23/*
24	File:		BTreePrivate.h
25
26	Contains:	Private interface file 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-1998 by Apple Computer, Inc., all rights reserved.
33*/
34
35#ifndef	__BTREEPRIVATE__
36#define __BTREEPRIVATE__
37
38#include "BTree.h"
39
40/////////////////////////////////// Constants ///////////////////////////////////
41
42#define		SupportsKeyDescriptors	0
43
44#define		kBTreeVersion		  1
45#define		kMaxTreeDepth		 16
46
47
48#define		kHeaderNodeNum		  0
49#define		kKeyDescRecord		  1
50
51
52// Header Node Record Offsets
53enum {
54	kHeaderRecOffset	=	0x000E,
55	kKeyDescRecOffset	=	0x0078,
56	kHeaderMapRecOffset	=	0x00F8
57};
58
59#define		kMinNodeSize		512
60
61#define		kMinRecordSize		  6
62										//�� where is minimum record size enforced?
63
64// miscellaneous BTree constants
65enum {
66			kOffsetSize				= 2
67};
68
69// Insert Operations
70typedef enum {
71			kInsertRecord			= 0,
72			kReplaceRecord			= 1
73} InsertType;
74
75// illegal string attribute bits set in mask
76#define		kBadStrAttribMask		0xCF
77
78
79
80//////////////////////////////////// Macros /////////////////////////////////////
81
82#define		M_NodesInMap(mapSize)				((mapSize) << 3)
83
84#define		M_ClearBitNum(integer,bitNumber) 	((integer) &= (~(1<<(bitNumber))))
85#define		M_SetBitNum(integer,bitNumber) 		((integer) |= (1<<(bitNumber)))
86#define		M_IsOdd(integer) 					(((integer) & 1) != 0)
87#define		M_IsEven(integer) 					(((integer) & 1) == 0)
88#define		M_BTreeHeaderDirty(btreePtr)		btreePtr->flags |= kBTHeaderDirty
89
90#define		M_MapRecordSize(nodeSize)			(nodeSize - sizeof (BTNodeDescriptor) - 6)
91#define		M_HeaderMapRecordSize(nodeSize)		(nodeSize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) - 128 - 8)
92
93#define		M_SWAP_BE16_ClearBitNum(integer,bitNumber)  ((integer) &= SWAP_BE16(~(1<<(bitNumber))))
94#define		M_SWAP_BE16_SetBitNum(integer,bitNumber)    ((integer) |= SWAP_BE16(1<<(bitNumber)))
95
96#if DEBUG_BUILD
97	#define Panic( message )					DebugStr( (ConstStr255Param) message )
98	#define PanicIf( condition, message )		if ( (condition) != 0 )	DebugStr( message )
99#else
100	#define Panic( message )	do { ; } while (0)
101	#define PanicIf( condition, message )	do { ; } while (0)
102#endif
103
104///////////////////////////////////// Types /////////////////////////////////////
105struct BTreeExtensionRec;
106
107typedef struct BTreeControlBlock {					// fields specific to BTree CBs
108
109	UInt8		keyCompareType;   /* Key string Comparison Type */
110	UInt8						 btreeType;
111	SInt16						 obsolete_fileRefNum;		// refNum of btree file
112	KeyCompareProcPtr			 keyCompareProc;
113	UInt8						 reserved2[16];		// keep for alignment with old style fields
114	UInt16						 treeDepth;
115	UInt32						 rootNode;
116	UInt32						 leafRecords;
117	UInt32						 firstLeafNode;
118	UInt32						 lastLeafNode;
119	UInt16						 nodeSize;
120	UInt16						 maxKeyLength;
121	UInt32						 totalNodes;
122	UInt32						 freeNodes;
123	UInt32 						reserved3[16];				/*	reserved*/
124
125	// new fields
126	SInt16						 version;
127	UInt32						 flags;				// dynamic flags
128	UInt32						 attributes;		// persistent flags
129	KeyDescriptorPtr			 keyDescPtr;
130	UInt32						 writeCount;
131
132	GetBlockProcPtr			 	 getBlockProc;
133	ReleaseBlockProcPtr			 releaseBlockProc;
134	SetEndOfForkProcPtr			 setEndOfForkProc;
135	BTreeIterator				 lastIterator;		// needed for System 7 iteration context
136
137	// statistical information
138	UInt32						 numGetNodes;
139	UInt32						 numGetNewNodes;
140	UInt32						 numReleaseNodes;
141	UInt32						 numUpdateNodes;
142	UInt32						 numMapNodesRead;	// map nodes beyond header node
143	UInt32						 numHintChecks;
144	UInt32						 numPossibleHints;	// Looks like a formated hint
145	UInt32						 numValidHints;		// Hint used to find correct record.
146
147	struct BTreeExtensionsRec	*refCon;			//	Used by DFA to point to private data.
148	SFCB						*fcbPtr;		// fcb of btree file
149
150} BTreeControlBlock, *BTreeControlBlockPtr;
151
152
153UInt32 CalcKeySize(const BTreeControlBlock *btcb, const BTreeKey *key);
154#define CalcKeySize(btcb, key)			( ((btcb)->attributes & kBTBigKeysMask) ? ((key)->length16 + 2) : ((key)->length8 + 1) )
155
156UInt32 MaxKeySize(const BTreeControlBlock *btcb);
157#define MaxKeySize(btcb)				( (btcb)->maxKeyLength + ((btcb)->attributes & kBTBigKeysMask ? 2 : 1))
158
159UInt32 KeyLength(const BTreeControlBlock *btcb, const BTreeKey *key);
160#define KeyLength(btcb, key)			( ((btcb)->attributes & kBTBigKeysMask) ? (key)->length16 : (key)->length8 )
161
162
163typedef enum {
164					kBTHeaderDirty	= 0x00000001
165}	BTreeFlags;
166
167
168typedef	SInt8				*NodeBuffer;
169typedef BlockDescriptor		 NodeRec, *NodePtr;		//�� remove this someday...
170
171
172
173
174//// Tree Path Table - constructed by SearchTree, used by InsertTree and DeleteTree
175
176typedef struct {
177	UInt32				node;				// node number
178	UInt16				index;
179	UInt16				reserved;			// align size to a power of 2
180} TreePathRecord, *TreePathRecordPtr;
181
182typedef TreePathRecord		TreePathTable [kMaxTreeDepth];
183
184
185//// InsertKey - used by InsertTree, InsertLevel and InsertNode
186
187struct InsertKey {
188	BTreeKeyPtr		keyPtr;
189	UInt8 *			recPtr;
190	UInt16			keyLength;
191	UInt16			recSize;
192	Boolean			replacingKey;
193	Boolean			skipRotate;
194};
195
196typedef struct InsertKey InsertKey;
197
198
199//// For Notational Convenience
200
201typedef	BTNodeDescriptor*	 NodeDescPtr;
202typedef UInt8				*RecordPtr;
203typedef BTreeKeyPtr			 KeyPtr;
204
205
206//////////////////////////////////// Globals ////////////////////////////////////
207
208
209//////////////////////////////////// Macros /////////////////////////////////////
210
211//	Exit function on error
212#define M_ExitOnError( result )	if ( ( result ) != noErr )	goto ErrorExit; else ;
213
214//	Test for passed condition and return if true
215#define	M_ReturnErrorIf( condition, error )	if ( condition )	return( error )
216
217#if DEBUG_BUILD
218	#define Panic( message )					DebugStr( (ConstStr255Param) message )
219	#define PanicIf( condition, message )		if ( (condition) != 0 )	DebugStr( message )
220#else
221	#define Panic( message )	do { ; } while (0)
222	#define PanicIf( condition, message )	do { ; } while (0)
223#endif
224
225//////////////////////////////// Key Operations /////////////////////////////////
226
227SInt32		CompareKeys				(BTreeControlBlockPtr	 btreePtr,
228									 KeyPtr					 searchKey,
229									 KeyPtr					 trialKey );
230
231OSStatus	GetKeyDescriptor		(BTreeControlBlockPtr	 btreePtr,
232									 NodeDescPtr			 headerNode );
233
234OSStatus	CheckKeyDescriptor		(KeyDescriptorPtr		 keyDescPtr,
235									 UInt16					 maxKeyLength );
236
237OSStatus	CheckKey				(KeyPtr					 keyPtr,
238									 KeyDescriptorPtr		 keyDescPtr,
239									 UInt16					 maxKeyLength );
240
241
242
243//////////////////////////////// Map Operations /////////////////////////////////
244
245OSStatus	AllocateNode			(BTreeControlBlockPtr	 btreePtr,
246									 UInt32					*nodeNum);
247
248OSStatus	FreeNode				(BTreeControlBlockPtr	 btreePtr,
249									 UInt32					 nodeNum);
250
251OSStatus	ExtendBTree				(BTreeControlBlockPtr	 btreePtr,
252									 UInt32					 nodes );
253
254UInt32		CalcMapBits				(BTreeControlBlockPtr	 btreePtr);
255
256
257//////////////////////////////// Misc Operations ////////////////////////////////
258
259UInt16		CalcKeyRecordSize		(UInt16					 keySize,
260									 UInt16					 recSize );
261
262OSStatus	VerifyHeader			(SFCB			*filePtr,
263									 BTHeaderRec			*header );
264
265OSStatus	UpdateHeader			(BTreeControlBlockPtr	 btreePtr );
266
267OSStatus	FindIteratorPosition	(BTreeControlBlockPtr	 btreePtr,
268									 BTreeIteratorPtr		 iterator,
269									 BlockDescriptor		*left,
270									 BlockDescriptor		*middle,
271									 BlockDescriptor		*right,
272									 UInt32					*nodeNum,
273									 UInt16					*index,
274									 Boolean				*foundRecord );
275
276OSStatus	CheckInsertParams		(SFCB			*filePtr,
277									 BTreeIterator			*iterator,
278									 FSBufferDescriptor		*record,
279									 UInt16					 recordLen );
280
281OSStatus	TrySimpleReplace		(BTreeControlBlockPtr	 btreePtr,
282									 NodeDescPtr			 nodePtr,
283									 BTreeIterator			*iterator,
284									 FSBufferDescriptor		*record,
285									 UInt16					 recordLen,
286									 Boolean				*recordInserted );
287
288OSStatus	IsItAHint				(BTreeControlBlockPtr 	 btreePtr,
289									 BTreeIterator 			*iterator,
290									 Boolean 				*answer );
291
292//////////////////////////////// Node Operations ////////////////////////////////
293
294//// Node Operations
295
296OSStatus	GetNode					(BTreeControlBlockPtr	 btreePtr,
297									 UInt32					 nodeNum,
298									 NodeRec				*returnNodePtr );
299
300OSStatus	GetLeftSiblingNode		(BTreeControlBlockPtr	 btreePtr,
301									 NodeDescPtr			 node,
302									 NodeRec				*left );
303
304#define		GetLeftSiblingNode(btree,node,left)			GetNode ((btree), ((NodeDescPtr)(node))->bLink, (left))
305
306OSStatus	GetRightSiblingNode		(BTreeControlBlockPtr	 btreePtr,
307									 NodeDescPtr			 node,
308									 NodeRec				*right );
309
310#define		GetRightSiblingNode(btree,node,right)		GetNode ((btree), ((NodeDescPtr)(node))->fLink, (right))
311
312
313OSStatus	GetNewNode				(BTreeControlBlockPtr	 btreePtr,
314									 UInt32					 nodeNum,
315									 NodeRec				*returnNodePtr );
316
317OSStatus	ReleaseNode				(BTreeControlBlockPtr	 btreePtr,
318									 NodePtr				 nodePtr );
319OSStatus	TrashNode				(BTreeControlBlockPtr	 btreePtr,
320									NodePtr				 nodePtr );
321
322OSStatus	UpdateNode				(BTreeControlBlockPtr	 btreePtr,
323									 NodePtr				 nodePtr );
324
325OSStatus	GetMapNode				(BTreeControlBlockPtr	 btreePtr,
326									 BlockDescriptor		 *nodePtr,
327									 UInt16					 **mapPtr,
328									 UInt16					 *mapSize );
329
330//// Node Buffer Operations
331
332void		ClearNode				(BTreeControlBlockPtr	 btreePtr,
333									 NodeDescPtr			 node );
334
335UInt16		GetNodeDataSize			(BTreeControlBlockPtr	 btreePtr,
336									 NodeDescPtr			 node );
337
338UInt16		GetNodeFreeSize			(BTreeControlBlockPtr	 btreePtr,
339									 NodeDescPtr			 node );
340
341
342//// Record Operations
343
344Boolean		InsertRecord			(BTreeControlBlockPtr	 btreePtr,
345									 NodeDescPtr	 		 node,
346									 UInt16	 				 index,
347									 RecordPtr				 recPtr,
348									 UInt16					 recSize );
349
350Boolean		InsertKeyRecord			(BTreeControlBlockPtr	 btreePtr,
351									 NodeDescPtr 			 node,
352									 UInt16	 				 index,
353									 KeyPtr					 keyPtr,
354									 UInt16					 keyLength,
355									 RecordPtr				 recPtr,
356									 UInt16					 recSize );
357
358void		DeleteRecord			(BTreeControlBlockPtr	btree,
359									 NodeDescPtr	 		node,
360									 UInt16	 				index );
361
362
363Boolean		SearchNode				(BTreeControlBlockPtr	 btree,
364									 NodeDescPtr			 node,
365									 KeyPtr					 searchKey,
366									 UInt16					*index );
367
368OSStatus	GetRecordByIndex		(BTreeControlBlockPtr	 btree,
369									 NodeDescPtr			 node,
370									 UInt16					 index,
371									 KeyPtr					*keyPtr,
372									 UInt8 *				*dataPtr,
373									 UInt16					*dataSize );
374
375UInt8 *		GetRecordAddress		(BTreeControlBlockPtr	 btree,
376									 NodeDescPtr			 node,
377									 UInt16					 index );
378
379#define GetRecordAddress(btreePtr,node,index)		((UInt8 *)(node) + (*(short *) ((UInt8 *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize)))
380
381
382UInt16		GetRecordSize			(BTreeControlBlockPtr	 btree,
383									 NodeDescPtr			 node,
384									 UInt16					 index );
385
386UInt32		GetChildNodeNum			(BTreeControlBlockPtr	 btreePtr,
387									 NodeDescPtr			 nodePtr,
388									 UInt16					 index );
389
390void		MoveRecordsLeft			(UInt8 *				 src,
391									 UInt8 *				 dst,
392									 UInt16					 bytesToMove );
393
394#define		MoveRecordsLeft(src,dst,bytes)			CopyMemory((src),(dst),(bytes))
395
396void		MoveRecordsRight		(UInt8 *				 src,
397									 UInt8 *				 dst,
398									 UInt16					 bytesToMove );
399
400#define		MoveRecordsRight(src,dst,bytes)			CopyMemory((src),(dst),(bytes))
401
402
403
404//////////////////////////////// Tree Operations ////////////////////////////////
405
406OSStatus	SearchTree				(BTreeControlBlockPtr	 btreePtr,
407									 BTreeKeyPtr			 keyPtr,
408									 TreePathTable			 treePathTable,
409									 UInt32					*nodeNum,
410									 BlockDescriptor		*nodePtr,
411									 UInt16					*index );
412
413OSStatus	InsertTree				(BTreeControlBlockPtr	 btreePtr,
414									 TreePathTable			 treePathTable,
415									 KeyPtr					 keyPtr,
416									 UInt8 *				 recPtr,
417									 UInt16					 recSize,
418									 BlockDescriptor		*targetNode,
419									 UInt16					 index,
420									 UInt16					 level,
421									 Boolean				 replacingKey,
422									 UInt32					*insertNode );
423
424OSStatus	DeleteTree				(BTreeControlBlockPtr	 btreePtr,
425									 TreePathTable			 treePathTable,
426									 BlockDescriptor		*targetNode,
427									 UInt16					 index,
428									 UInt16					 level );
429
430#endif //__BTREEPRIVATE__
431