1/*
2 * Copyright (c) 2000-2009 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:		BTreesInternal.h
30
31	Contains:	IPI to File Manager B-tree
32
33	Version:	HFS Plus 1.0
34
35	Copyright:	� 1996-1998 by Apple Computer, Inc., all rights reserved.
36
37	File Ownership:
38
39		DRI:				Don Brady
40
41		Other Contact:		Mark Day
42
43		Technology:			File Systems
44
45	Writers:
46
47		(msd)	Mark Day
48		(DSH)	Deric Horn
49		(djb)	Don Brady
50
51	Change History (most recent first):
52
53	  <RHAP>	 9/22/99	ser		Added prototypes for BTGetLastSync and BTSetLastSync
54	  <RHAP>	 6/22/98	djb		Add ERR_BASE to btree error codes to make them negative (for MacOS X only).
55
56	   <CS7>	 7/28/97	msd		Add enum for fsBTTimeOutErr.
57	   <CS6>	 7/25/97	DSH		Added heuristicHint as parameter to BTSearchRecord.
58	   <CS5>	 7/24/97	djb		Add blockReadFromDisk flag to BlockDescriptor. Callbacks now use
59									a file refNum instead of an FCB.
60	   <CS4>	 7/16/97	DSH		FilesInternal.i renamed FileMgrInternal.i to avoid name
61									collision
62	   <CS3>	  6/2/97	DSH		Added SetEndOfForkProc() prototype, so Attributes.c can call it
63									directly.
64	   <CS2>	 5/19/97	djb		kMaxKeyLength is now 520.
65	   <CS1>	 4/28/97	djb		first checked in
66
67	  <HFS6>	 3/17/97	DSH		Remove Key Comparison prototype, already in FilesInternal.h.
68	  <HFS5>	 2/19/97	djb		Add SetBlockSizeProcPtr. Add blockSize field to BlockDescriptor.
69									Remove E_ type error enums.
70	  <HFS4>	 1/27/97	djb		Include Types.h and FilesInternal.h.
71	  <HFS3>	 1/13/97	djb		Added kBTreeCurrentRecord for BTIterateRecord.
72	  <HFS2>	  1/3/97	djb		Added support for large keys.
73	  <HFS1>	12/19/96	djb		first checked in
74
75*/
76
77#ifndef	__BTREESINTERNAL__
78#define __BTREESINTERNAL__
79
80#include <sys/appleapiopts.h>
81
82#ifdef KERNEL
83#ifdef __APPLE_API_PRIVATE
84
85#ifndef __FILEMGRINTERNAL__
86#include "FileMgrInternal.h"
87#endif
88
89enum {
90	fsBTInvalidHeaderErr			= btBadHdr,
91	fsBTBadRotateErr				= dsBadRotate,
92	fsBTInvalidNodeErr				= btBadNode,
93	fsBTRecordTooLargeErr			= btNoFit,
94	fsBTRecordNotFoundErr			= btNotFound,
95	fsBTDuplicateRecordErr			= btExists,
96	fsBTFullErr						= btNoSpaceAvail,
97
98	fsBTInvalidFileErr				= ERR_BASE + 0x0302,	/* no BTreeCB has been allocated for fork*/
99	fsBTrFileAlreadyOpenErr			= ERR_BASE + 0x0303,
100	fsBTInvalidIteratorErr			= ERR_BASE + 0x0308,
101	fsBTEmptyErr					= ERR_BASE + 0x030A,
102	fsBTNoMoreMapNodesErr			= ERR_BASE + 0x030B,
103	fsBTBadNodeSize					= ERR_BASE + 0x030C,
104	fsBTBadNodeType					= ERR_BASE + 0x030D,
105	fsBTInvalidKeyLengthErr			= ERR_BASE + 0x030E,
106	fsBTStartOfIterationErr			= ERR_BASE + 0x0353,
107	fsBTEndOfIterationErr			= ERR_BASE + 0x0354,
108	fsBTUnknownVersionErr			= ERR_BASE + 0x0355,
109	fsBTTreeTooDeepErr				= ERR_BASE + 0x0357,
110	fsIteratorExitedScopeErr		= ERR_BASE + 0x0A02,	/* iterator exited the scope*/
111	fsIteratorScopeExceptionErr		= ERR_BASE + 0x0A03,	/* iterator is undefined due to error or movement of scope locality*/
112	fsUnknownIteratorMovementErr	= ERR_BASE + 0x0A04,	/* iterator movement is not defined*/
113	fsInvalidIterationMovmentErr	= ERR_BASE + 0x0A05,	/* iterator movement is invalid in current context*/
114	fsClientIDMismatchErr			= ERR_BASE + 0x0A06,	/* wrong client process ID*/
115	fsEndOfIterationErr				= ERR_BASE + 0x0A07,	/* there were no objects left to return on iteration*/
116	fsBTTimeOutErr					= ERR_BASE + 0x0A08		/* BTree scan interrupted -- no time left for physical I/O */
117};
118
119struct BlockDescriptor{
120	void		*buffer;
121	void		*blockHeader;
122	daddr64_t	 blockNum;	/* logical block number (used by hfs_swap_BTNode) */
123	ByteCount	 blockSize;
124	Boolean		 blockReadFromDisk;
125	Byte         isModified;             // XXXdbg - for journaling
126	Byte		 reserved[2];
127};
128typedef struct BlockDescriptor BlockDescriptor;
129typedef BlockDescriptor *BlockDescPtr;
130
131
132struct FSBufferDescriptor {
133	void *		bufferAddress;
134	ByteCount	itemSize;
135	ItemCount	itemCount;
136};
137typedef struct FSBufferDescriptor FSBufferDescriptor;
138
139typedef FSBufferDescriptor *FSBufferDescriptorPtr;
140
141
142/*
143	Fork Level Access Method Block get options
144*/
145enum {
146		kGetBlock			= 0x00000000,
147		kGetBlockHint		= 0x00000001,	// if set, the block is being looked up using hint
148		kForceReadBlock		= 0x00000002,	//�� how does this relate to Read/Verify? Do we need this?
149		kGetEmptyBlock		= 0x00000008
150};
151typedef u_int32_t	GetBlockOptions;
152
153/*
154	Fork Level Access Method Block release options
155*/
156enum {
157		kReleaseBlock		= 0x00000000,
158		kForceWriteBlock	= 0x00000001,
159		kMarkBlockDirty		= 0x00000002,
160		kTrashBlock			= 0x00000004,
161		kLockTransaction    = 0x00000100
162};
163typedef u_int32_t	ReleaseBlockOptions;
164
165typedef	u_int64_t	FSSize;
166typedef	u_int32_t	ForkBlockNumber;
167
168/*============================================================================
169	Fork Level Buffered I/O Access Method
170============================================================================*/
171
172typedef	OSStatus	(* GetBlockProcPtr)		(FileReference				 fileRefNum,
173											 u_int32_t					 blockNum,
174											 GetBlockOptions			 options,
175											 BlockDescriptor			*block );
176
177
178typedef	OSStatus	(* ReleaseBlockProcPtr)	(FileReference				 fileRefNum,
179											 BlockDescPtr				 blockPtr,
180											 ReleaseBlockOptions		 options );
181
182typedef	OSStatus	(* SetEndOfForkProcPtr)	(FileReference				 fileRefNum,
183											 FSSize						 minEOF,
184											 FSSize						 maxEOF );
185
186typedef	OSStatus	(* SetBlockSizeProcPtr)	(FileReference				 fileRefNum,
187											 ByteCount					 blockSize,
188											 ItemCount					 minBlockCount );
189
190OSStatus		SetEndOfForkProc ( FileReference fileRefNum, FSSize minEOF, FSSize maxEOF );
191
192
193/*
194	B*Tree Information Version
195*/
196
197enum BTreeInformationVersion{
198	kBTreeInfoVersion	= 0
199};
200
201/*
202	B*Tree Iteration Operation Constants
203*/
204
205enum BTreeIterationOperations{
206	kBTreeFirstRecord,
207	kBTreeNextRecord,
208	kBTreePrevRecord,
209	kBTreeLastRecord,
210	kBTreeCurrentRecord
211};
212typedef u_int16_t BTreeIterationOperation;
213
214
215/*
216	Btree types: 0 is HFS CAT/EXT file, 1~127 are AppleShare B*Tree files, 128~254 unused
217	hfsBtreeType	EQU		0			; control file
218	validBTType		EQU		$80			; user btree type starts from 128
219	userBT1Type		EQU		$FF			; 255 is our Btree type. Used by BTInit and BTPatch
220*/
221
222enum BTreeTypes{
223	kHFSBTreeType			=   0,		// control file
224	kUserBTreeType			= 128,		// user btree type starts from 128
225	kReservedBTreeType		= 255		//
226};
227
228#define	kBTreeHeaderUserBytes	128
229
230
231typedef BTreeKey *BTreeKeyPtr;
232
233
234/*
235	BTreeInfoRec Structure - for BTGetInformation
236*/
237struct BTreeInfoRec{
238	u_int16_t			version;
239	u_int16_t			nodeSize;
240	u_int16_t			maxKeyLength;
241	u_int16_t			treeDepth;
242	u_int32_t			lastfsync;		/* Last time that this was fsynced  */
243	ItemCount			numRecords;
244	ItemCount			numNodes;
245	ItemCount			numFreeNodes;
246	u_int8_t			keyCompareType;
247	u_int8_t			reserved[3];
248};
249typedef struct BTreeInfoRec BTreeInfoRec;
250typedef BTreeInfoRec *BTreeInfoPtr;
251
252/*
253	BTreeHint can never be exported to the outside. Use u_int32_t BTreeHint[4],
254	u_int8_t BTreeHint[16], etc.
255 */
256struct BTreeHint{
257	ItemCount				writeCount;
258	u_int32_t				nodeNum;			// node the key was last seen in
259	u_int16_t				index;				// index then key was last seen at
260	u_int16_t				reserved1;
261	u_int32_t				reserved2;
262};
263typedef struct BTreeHint BTreeHint;
264typedef BTreeHint *BTreeHintPtr;
265
266/*
267	BTree Iterator
268*/
269struct BTreeIterator{
270	BTreeHint				hint;
271	u_int16_t				version;
272	u_int16_t				reserved;
273	u_int32_t				hitCount;			// Total number of leaf records hit
274	u_int32_t				maxLeafRecs;		// Max leaf records over iteration
275	BTreeKey				key;
276};
277typedef struct BTreeIterator BTreeIterator;
278typedef BTreeIterator *BTreeIteratorPtr;
279
280
281/*============================================================================
282	B*Tree SPI
283============================================================================*/
284
285/*
286	Key Comparison Function ProcPtr Type - for BTOpenPath
287*/
288//typedef int32_t 				(* KeyCompareProcPtr)(BTreeKeyPtr a, BTreeKeyPtr b);
289
290
291typedef int32_t (* IterateCallBackProcPtr)(BTreeKeyPtr key, void * record, void * state);
292
293
294extern OSStatus	BTOpenPath(FCB *filePtr, KeyCompareProcPtr keyCompareProc);
295
296extern OSStatus	BTClosePath			(FCB		 				*filePtr );
297
298
299extern OSStatus	BTSearchRecord		(FCB		 				*filePtr,
300									 BTreeIterator				*searchIterator,
301									 FSBufferDescriptor			*btRecord,
302									 u_int16_t					*recordLen,
303									 BTreeIterator				*resultIterator );
304
305extern OSStatus	BTIterateRecord		(FCB		 				*filePtr,
306									 BTreeIterationOperation	 operation,
307									 BTreeIterator				*iterator,
308									 FSBufferDescriptor			*btRecord,
309									 u_int16_t					*recordLen );
310
311
312extern OSStatus BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator *iterator,
313		 IterateCallBackProcPtr	 callBackProc, void * callBackState);
314
315extern OSStatus	BTInsertRecord		(FCB		 				*filePtr,
316									 BTreeIterator				*iterator,
317									 FSBufferDescriptor			*btrecord,
318									 u_int16_t					 recordLen );
319
320extern OSStatus	BTReplaceRecord		(FCB		 				*filePtr,
321									 BTreeIterator				*iterator,
322									 FSBufferDescriptor			*btRecord,
323									 u_int16_t					 recordLen );
324
325extern OSStatus	BTUpdateRecord		(FCB		 				*filePtr,
326									 BTreeIterator				*iterator,
327									 IterateCallBackProcPtr		 callBackProc,
328									 void						*callBackState );
329
330extern OSStatus	BTDeleteRecord		(FCB		 				*filePtr,
331									 BTreeIterator				*iterator );
332
333extern OSStatus	BTGetInformation	(FCB		 				*filePtr,
334									 u_int16_t					 vers,
335									 BTreeInfoRec				*info );
336
337extern OSStatus BTIsDirty(FCB *filePtr);
338
339extern OSStatus	BTFlushPath			(FCB		 				*filePtr );
340
341extern OSStatus BTReloadData		(FCB *filePtr);
342
343extern OSStatus	BTInvalidateHint	(BTreeIterator				*iterator );
344
345extern OSStatus	BTGetLastSync		(FCB		 				*filePtr,
346									 u_int32_t					*lastfsync );
347
348extern OSStatus	BTSetLastSync		(FCB		 				*filePtr,
349									 u_int32_t					lastfsync );
350
351extern OSStatus	BTHasContiguousNodes(FCB		 				*filePtr);
352
353extern OSStatus BTGetUserData(FCB *filePtr, void * dataPtr, int dataSize);
354
355extern OSStatus BTSetUserData(FCB *filePtr, void * dataPtr, int dataSize);
356
357/* B-tree node reserve routines. */
358extern void BTReserveSetup(void);
359
360extern int  BTReserveSpace(FCB *file, int operations, void * data);
361
362extern int  BTReleaseReserve(FCB *file, void * data);
363
364extern int  BTZeroUnusedNodes(FCB *file);
365
366#endif /* __APPLE_API_PRIVATE */
367#endif /* KERNEL */
368#endif // __BTREESINTERNAL__
369