1/*
2 * Copyright (c) 2000-2008 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28/*
29	File:		BTreesPrivate.h
30
31	Contains:	Private interface file for the BTree Module.
32
33	Version:	xxx put the technology version here xxx
34
35	Written by:	Gordon Sheridan and Bill Bruffey
36
37	Copyright:	� 1992-1999 by Apple Computer, Inc., all rights reserved.
38
39	File Ownership:
40
41		DRI:				Don Brady
42
43		Other Contact:		Mark Day
44
45		Technology:			File Systems
46
47	Writers:
48
49		(msd)	Mark Day
50		(DSH)	Deric Horn
51		(djb)	Don Brady
52		(ser)	Scott Roberts
53		(dkh)	Dave Heller
54
55	Change History (most recent first):
56	   <MacOSX>	 3/19/99	djb		Disable MoveRecordsLeft/Right macros since bcopy is broken.
57
58	   <MacOSX>	 8/10/98	djb		Removed unused BTreeIterator from BTreeControlBlock, fixed alignment.
59
60	   <CS5>	  9/4/97	djb		Convert MoveRecordsLeft and GetLeftSiblingNode to macros.
61	   <CS4>	 7/24/97	djb		Add macro for GetRecordAddress (was a function before).
62	   <CS3>	 7/21/97	msd		GetRecordByIndex now returns an OSStatus.
63	   <CS2>	 7/16/97	DSH		FilesInternal.i renamed FileMgrInternal.i to avoid name
64									collision
65	   <CS1>	 4/23/97	djb		first checked in
66
67	  <HFS6>	 3/17/97	DSH		Added a refCon field to BTreeControlBlock, for DFA use, to point
68									to additional data.  Fixed Panic macros for use with SC.
69	  <HFS5>	 2/19/97	djb		Add InsertKey struct. Moved on-disk definitions to
70									HFSBTreesPriv.h
71	  <HFS4>	 1/27/97	djb		InsertTree and DeleteTree are now recursive and support variable
72									sized index keys.
73	  <HFS3>	 1/15/97	djb		Move GetFileRefNumFromFCB macro to FilesInternal.h. Added
74									kBTVariableIndexKeysMask.
75	  <HFS2>	  1/3/97	djb		Added support for large keys.
76	  <HFS1>	12/19/96	djb		first checked in
77
78	History applicable to original Scarecrow Design:
79
80		 <7>	10/25/96	ser		Changing for new VFPI
81		 <6>	10/18/96	ser		Converting over VFPI changes
82		 <5>	 9/17/96	dkh		More BTree statistics
83		 <4>	 9/16/96	dkh		Revised BTree statistics
84		 <3>	 6/20/96	dkh		Radar #1358740. Switch from using Pools to debug MemAllocators.
85		 <2>	 12/7/95	dkh		D10E2 build. Changed usage of Ref data type to LogicalAddress.
86		 <1>	10/18/95	rst		Moved from Scarecrow project.
87
88		<19>	11/22/94	djb		Add prototype for GetMapNode
89		<18>	11/16/94	prp		Add IsItAHint routine prototype.
90		<17>	 9/30/94	prp		Get in sync with D2 interface changes.
91		<16>	 7/25/94	wjk		Eliminate usage of BytePtr in favor of UInt8 *.
92		<15>	 7/22/94	wjk		Convert to the new set of header files.
93		<14>	 5/31/94	srs		Moved Btree types to public interface
94		<13>	 12/9/93	wjk		Add 68k alignment pragma's around persistent structures.
95		<12>	11/30/93	wjk		Move from Makefiles to BuildFiles. Fit into the ModernOS and
96									NRCmds environments.
97		<11>	11/23/93	wjk		Changes required to compile on the RS6000.
98		<10>	 8/30/93	CH		Removed the M_ExitOnError and M_ReturnErrorIf macros which were
99									already defined in FileSystemPriv.h (included here).
100		 <9>	 8/30/93	CH		Added parens around the M_ReturnErrorIf macro.
101		 <8>	 5/21/93	gs		Add kBadClose flag. Add some prototypes for internal routines.
102		 <7>	 5/10/93	gs		Change Ptr to BytePtr. Move BTreeTypes to BTree.h. Add
103									DeleteTree prototype.
104		 <6>	 3/23/93	gs		Remove mysterious "flags" field from HeaderRec structure. Move
105									prototypes of private functions to top of respective source
106									files.
107		 <5>	  2/8/93	gs		Update to use FSAgent.h Get/Release/SetEOF/SetBlockSize
108									procPtrs. Add UpdateNode routine.
109		 <4>	12/10/92	gs		Add Key Descriptor function declarations.
110		 <3>	 12/8/92	gs		Add HeaderRec structure and incorporate review feedback.
111		 <2>	 12/2/92	gs		Add GetNode and ReleaseNode callback procptrs to BTree CB, and
112									add internal function declarations.
113		 <1>	11/15/92	gs		first checked in
114
115*/
116
117#ifndef	__BTREESPRIVATE__
118#define __BTREESPRIVATE__
119
120#include <sys/appleapiopts.h>
121
122#ifdef KERNEL
123#ifdef __APPLE_API_PRIVATE
124
125#include "../../hfs_macos_defs.h"
126
127#ifndef __FILEMGRINTERNAL__
128#include "FileMgrInternal.h"
129#endif
130
131#ifndef __BTREESINTERNAL__
132#include "BTreesInternal.h"
133#endif
134
135
136/////////////////////////////////// Constants ///////////////////////////////////
137
138#define		kBTreeVersion		  1
139#define		kMaxTreeDepth		 16
140
141
142#define		kHeaderNodeNum		  0
143#define		kKeyDescRecord		  1
144
145
146// Header Node Record Offsets
147enum {
148	kHeaderRecOffset	=	0x000E,
149	kKeyDescRecOffset	=	0x0078,
150	kHeaderMapRecOffset	=	0x00F8
151};
152
153#define		kMinNodeSize		512
154
155#define		kMinRecordSize		  6
156										// where is minimum record size enforced?
157
158// miscellaneous BTree constants
159enum {
160			kOffsetSize				= 2
161};
162
163// Insert Operations
164typedef enum {
165			kInsertRecord			= 0,
166			kReplaceRecord			= 1
167} InsertType;
168
169// illegal string attribute bits set in mask
170#define		kBadStrAttribMask		0xCF
171
172
173
174//////////////////////////////////// Macros /////////////////////////////////////
175
176#define		M_NodesInMap(mapSize)				((mapSize) << 3)
177
178#define		M_ClearBitNum(integer,bitNumber) 	((integer) &= (~(1<<(bitNumber))))
179#define		M_SetBitNum(integer,bitNumber) 		((integer) |= (1<<(bitNumber)))
180#define		M_IsOdd(integer) 					(((integer) & 1) != 0)
181#define		M_IsEven(integer) 					(((integer) & 1) == 0)
182#define		M_BTreeHeaderDirty(btreePtr)		btreePtr->flags |= kBTHeaderDirty
183
184#define		M_MapRecordSize(nodeSize)			(nodeSize - sizeof (BTNodeDescriptor) - 6)
185#define		M_HeaderMapRecordSize(nodeSize)		(nodeSize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) - 128 - 8)
186
187#define		M_SWAP_BE16_ClearBitNum(integer,bitNumber)  ((integer) &= SWAP_BE16(~(1<<(bitNumber))))
188#define		M_SWAP_BE16_SetBitNum(integer,bitNumber)    ((integer) |= SWAP_BE16(1<<(bitNumber)))
189
190///////////////////////////////////// Types /////////////////////////////////////
191
192typedef struct BTreeControlBlock {					// fields specific to BTree CBs
193
194	u_int8_t		keyCompareType;   /* Key string Comparison Type */
195	u_int8_t					 btreeType;
196	u_int16_t					 treeDepth;
197	FileReference				 fileRefNum;		// refNum of btree file
198	KeyCompareProcPtr			 keyCompareProc;
199	u_int32_t					 rootNode;
200	u_int32_t					 leafRecords;
201	u_int32_t					 firstLeafNode;
202	u_int32_t					 lastLeafNode;
203	u_int16_t					 nodeSize;
204	u_int16_t					 maxKeyLength;
205	u_int32_t					 totalNodes;
206	u_int32_t					 freeNodes;
207
208	u_int16_t					 reserved3;			// 4-byte alignment
209
210	// new fields
211	int16_t						 version;
212	u_int32_t					 flags;				// dynamic flags
213	u_int32_t					 attributes;		// persistent flags
214	u_int32_t					 writeCount;
215	u_int32_t					 lastfsync;		/* Last time that this was fsynced  */
216
217	GetBlockProcPtr			 	 getBlockProc;
218	ReleaseBlockProcPtr			 releaseBlockProc;
219	SetEndOfForkProcPtr			 setEndOfForkProc;
220
221	// statistical information
222	u_int32_t					 numGetNodes;
223	u_int32_t					 numGetNewNodes;
224	u_int32_t					 numReleaseNodes;
225	u_int32_t					 numUpdateNodes;
226	u_int32_t					 numMapNodesRead;	// map nodes beyond header node
227	u_int32_t					 numHintChecks;
228	u_int32_t					 numPossibleHints;	// Looks like a formated hint
229	u_int32_t					 numValidHints;		// Hint used to find correct record.
230	u_int32_t					reservedNodes;
231	BTreeIterator   iterator; // useable when holding exclusive b-tree lock
232} BTreeControlBlock, *BTreeControlBlockPtr;
233
234
235u_int32_t CalcKeySize(const BTreeControlBlock *btcb, const BTreeKey *key);
236#define CalcKeySize(btcb, key)			( ((btcb)->attributes & kBTBigKeysMask) ? ((key)->length16 + 2) : ((key)->length8 + 1) )
237
238u_int32_t KeyLength(const BTreeControlBlock *btcb, const BTreeKey *key);
239#define KeyLength(btcb, key)			( ((btcb)->attributes & kBTBigKeysMask) ? (key)->length16 : (key)->length8 )
240
241
242
243typedef enum {
244					kBTHeaderDirty	= 0x00000001
245}	BTreeFlags;
246
247
248typedef	int8_t				*NodeBuffer;
249typedef BlockDescriptor		 NodeRec, *NodePtr;		//�� remove this someday...
250
251
252
253
254//// Tree Path Table - constructed by SearchTree, used by InsertTree and DeleteTree
255
256typedef struct {
257	u_int32_t				node;				// node number
258	u_int16_t				index;
259	u_int16_t				reserved;			// align size to a power of 2
260} TreePathRecord, *TreePathRecordPtr;
261
262typedef TreePathRecord		TreePathTable [kMaxTreeDepth];
263
264
265//// InsertKey - used by InsertTree, InsertLevel and InsertNode
266
267struct InsertKey {
268	BTreeKeyPtr		keyPtr;
269	u_int8_t *		recPtr;
270	u_int16_t		keyLength;
271	u_int16_t		recSize;
272	Boolean			replacingKey;
273	Boolean			skipRotate;
274};
275
276typedef struct InsertKey InsertKey;
277
278
279//// For Notational Convenience
280
281typedef	BTNodeDescriptor*	 NodeDescPtr;
282typedef u_int8_t			*RecordPtr;
283typedef BTreeKeyPtr			 KeyPtr;
284
285
286//////////////////////////////////// Globals ////////////////////////////////////
287
288
289//////////////////////////////////// Macros /////////////////////////////////////
290
291#if DEBUG_BUILD
292	#define Panic( message )					DebugStr( message )
293	#define PanicIf( condition, message )		do { if ( condition != 0 )	DebugStr( message ); } while(0)
294#else
295	#define Panic( message )				do { } while(0)
296	#define PanicIf( condition, message )	do { } while(0)
297#endif
298
299//	Exit function on error
300#define M_ExitOnError( result )	do { if ( ( result ) != noErr )	goto ErrorExit; } while(0)
301
302//	Test for passed condition and return if true
303#define	M_ReturnErrorIf( condition, error )	do { if ( condition )	return( error ); } while(0)
304
305//////////////////////////////// Key Operations /////////////////////////////////
306
307int32_t		CompareKeys				(BTreeControlBlockPtr	 btreePtr,
308									 KeyPtr					 searchKey,
309									 KeyPtr					 trialKey );
310
311//////////////////////////////// Map Operations /////////////////////////////////
312
313OSStatus	AllocateNode			(BTreeControlBlockPtr	 btreePtr,
314									 u_int32_t				*nodeNum);
315
316OSStatus	FreeNode				(BTreeControlBlockPtr	 btreePtr,
317									 u_int32_t				 nodeNum);
318
319OSStatus	ExtendBTree				(BTreeControlBlockPtr	 btreePtr,
320									 u_int32_t				 nodes );
321
322u_int32_t	CalcMapBits				(BTreeControlBlockPtr	 btreePtr);
323
324
325void 		BTUpdateReserve				(BTreeControlBlockPtr btreePtr,
326                                                         int nodes);
327
328//////////////////////////////// Misc Operations ////////////////////////////////
329
330u_int16_t	CalcKeyRecordSize		(u_int16_t				 keySize,
331									 u_int16_t				 recSize );
332
333OSStatus	VerifyHeader			(FCB					*filePtr,
334									 BTHeaderRec				*header );
335
336OSStatus	UpdateHeader			(BTreeControlBlockPtr	 btreePtr,
337						 Boolean forceWrite );
338
339OSStatus	FindIteratorPosition	(BTreeControlBlockPtr	 btreePtr,
340									 BTreeIteratorPtr		 iterator,
341									 BlockDescriptor		*left,
342									 BlockDescriptor		*middle,
343									 BlockDescriptor		*right,
344									 u_int32_t				*nodeNum,
345									 u_int16_t				*index,
346									 Boolean				*foundRecord );
347
348OSStatus	CheckInsertParams		(FCB					*filePtr,
349									 BTreeIterator			*iterator,
350									 FSBufferDescriptor		*record,
351									 u_int16_t				 recordLen );
352
353OSStatus	TrySimpleReplace		(BTreeControlBlockPtr	 btreePtr,
354									 NodeDescPtr			 nodePtr,
355									 BTreeIterator			*iterator,
356									 FSBufferDescriptor		*record,
357									 u_int16_t				 recordLen,
358									 Boolean				*recordInserted );
359
360OSStatus	IsItAHint				(BTreeControlBlockPtr 	 btreePtr,
361									 BTreeIterator 			*iterator,
362									 Boolean 				*answer );
363
364extern OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr);
365
366//////////////////////////////// Node Operations ////////////////////////////////
367
368//// Node Operations
369
370OSStatus	GetNode					(BTreeControlBlockPtr	 btreePtr,
371									 u_int32_t				 nodeNum,
372									 u_int32_t 				 flags,
373									 NodeRec				*returnNodePtr );
374
375/* Flags for GetNode() */
376#define		kGetNodeHint	0x1		/* If set, the node is being looked up using a hint */
377
378OSStatus	GetLeftSiblingNode		(BTreeControlBlockPtr	 btreePtr,
379									 NodeDescPtr			 node,
380									 NodeRec				*left );
381
382#define		GetLeftSiblingNode(btree,node,left)			GetNode ((btree), ((NodeDescPtr)(node))->bLink, 0, (left))
383
384OSStatus	GetRightSiblingNode		(BTreeControlBlockPtr	 btreePtr,
385									 NodeDescPtr			 node,
386									 NodeRec				*right );
387
388#define		GetRightSiblingNode(btree,node,right)		GetNode ((btree), ((NodeDescPtr)(node))->fLink, 0, (right))
389
390
391OSStatus	GetNewNode				(BTreeControlBlockPtr	 btreePtr,
392									 u_int32_t				 nodeNum,
393									 NodeRec				*returnNodePtr );
394
395OSStatus	ReleaseNode				(BTreeControlBlockPtr	 btreePtr,
396									 NodePtr				 nodePtr );
397
398OSStatus	TrashNode				(BTreeControlBlockPtr	 btreePtr,
399									 NodePtr				 nodePtr );
400
401OSStatus	UpdateNode				(BTreeControlBlockPtr	 btreePtr,
402									 NodePtr				 nodePtr,
403									 u_int32_t				 transactionID,
404									 u_int32_t				 flags );
405
406//// Node Buffer Operations
407
408void		ClearNode				(BTreeControlBlockPtr	 btreePtr,
409									 NodeDescPtr			 node );
410
411u_int16_t	GetNodeDataSize			(BTreeControlBlockPtr	 btreePtr,
412									 NodeDescPtr			 node );
413
414u_int16_t	GetNodeFreeSize			(BTreeControlBlockPtr	 btreePtr,
415									 NodeDescPtr			 node );
416
417
418//// Record Operations
419
420Boolean		InsertRecord			(BTreeControlBlockPtr	 btreePtr,
421									 NodeDescPtr	 		 node,
422									 u_int16_t	 			 index,
423									 RecordPtr				 recPtr,
424									 u_int16_t				 recSize );
425
426Boolean		InsertKeyRecord			(BTreeControlBlockPtr	 btreePtr,
427									 NodeDescPtr 			 node,
428									 u_int16_t	 			 index,
429									 KeyPtr					 keyPtr,
430									 u_int16_t				 keyLength,
431									 RecordPtr				 recPtr,
432									 u_int16_t				 recSize );
433
434void		DeleteRecord			(BTreeControlBlockPtr	btree,
435									 NodeDescPtr	 		node,
436									 u_int16_t	 			index );
437
438
439Boolean		SearchNode				(BTreeControlBlockPtr	 btree,
440									 NodeDescPtr			 node,
441									 KeyPtr					 searchKey,
442									 u_int16_t				*index );
443
444OSStatus	GetRecordByIndex		(BTreeControlBlockPtr	 btree,
445									 NodeDescPtr			 node,
446									 u_int16_t				 index,
447									 KeyPtr					*keyPtr,
448									 u_int8_t *				*dataPtr,
449									 u_int16_t				*dataSize );
450
451u_int8_t *	GetRecordAddress		(BTreeControlBlockPtr	 btree,
452									 NodeDescPtr			 node,
453									 u_int16_t				 index );
454
455#define GetRecordAddress(btreePtr,node,index)		((u_int8_t *)(node) + (*(short *) ((u_int8_t *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize)))
456
457
458u_int16_t	GetRecordSize			(BTreeControlBlockPtr	 btree,
459									 NodeDescPtr			 node,
460									 u_int16_t				 index );
461
462u_int32_t	GetChildNodeNum			(BTreeControlBlockPtr	 btreePtr,
463									 NodeDescPtr			 nodePtr,
464									 u_int16_t				 index );
465
466void		MoveRecordsLeft			(u_int8_t *				 src,
467									 u_int8_t *				 dst,
468									 u_int16_t				 bytesToMove );
469
470#define		MoveRecordsLeft(src,dst,bytes)			bcopy((src),(dst),(bytes))
471
472void		MoveRecordsRight		(u_int8_t *				 src,
473									 u_int8_t *				 dst,
474									 u_int16_t				 bytesToMove );
475
476#define		MoveRecordsRight(src,dst,bytes)			bcopy((src),(dst),(bytes))
477
478
479//////////////////////////////// Tree Operations ////////////////////////////////
480
481OSStatus	SearchTree				(BTreeControlBlockPtr	 btreePtr,
482									 BTreeKeyPtr			 keyPtr,
483									 TreePathTable			 treePathTable,
484									 u_int32_t				*nodeNum,
485									 BlockDescriptor		*nodePtr,
486									 u_int16_t				*index );
487
488OSStatus	InsertTree				(BTreeControlBlockPtr	 btreePtr,
489									 TreePathTable			 treePathTable,
490									 KeyPtr					 keyPtr,
491									 u_int8_t *				 recPtr,
492									 u_int16_t				 recSize,
493									 BlockDescriptor		*targetNode,
494									 u_int16_t				 index,
495									 u_int16_t				 level,
496									 Boolean				 replacingKey,
497									 u_int32_t				*insertNode );
498
499OSStatus	DeleteTree				(BTreeControlBlockPtr	 btreePtr,
500									 TreePathTable			 treePathTable,
501									 BlockDescriptor		*targetNode,
502									 u_int16_t				 index,
503									 u_int16_t				 level );
504
505#endif /* __APPLE_API_PRIVATE */
506#endif /* KERNEL */
507#endif //__BTREESPRIVATE__
508