1/*
2 * Copyright (c) 1999 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:		BTreesInternal.h
25
26	Contains:	IPI to File Manager B-tree
27
28	Version:	HFS Plus 1.0
29
30	Copyright:	� 1996-1998 by Apple Computer, Inc., all rights reserved.
31*/
32
33#ifndef	__BTREESINTERNAL__
34#define __BTREESINTERNAL__
35
36#include "SRuntime.h"
37
38//
39// internal error codes
40//
41enum {
42	// FXM errors
43
44	fxRangeErr				= 16,		// file position beyond mapped range
45	fxOvFlErr				= 17,		// extents file overflow
46
47	// Unicode errors
48
49	uniTooLongErr			= 24,		// Unicode string too long to convert to Str31
50	uniBufferTooSmallErr	= 25,		// Unicode output buffer too small
51	uniNotMappableErr		= 26,		// Unicode string can't be mapped to given script
52
53	// BTree Manager errors
54
55	btNotFound		 		= 32,		// record not found
56	btExists  		 		= 33,		// record already exists
57	btNoSpaceAvail			= 34,		// no available space
58	btNoFit   		 		= 35,		// record doesn't fit in node
59	btBadNode 		 		= 36,		// bad node detected
60	btBadHdr  		 		= 37,		// bad BTree header record detected
61	dsBadRotate   	 		= 64,		// bad BTree rotate
62
63	// Catalog Manager errors
64
65	cmNotFound		 		= 48,		// CNode not found
66	cmExists  		 		= 49,		// CNode already exists
67	cmNotEmpty		 		= 50,		// directory CNode not empty (valence = 0)
68	cmRootCN  		 		= 51,		// invalid reference to root CNode
69	cmBadNews 		 		= 52,		// detected bad catalog structure
70	cmFThdDirErr  	 		= 53,		// thread belongs to a directory not a file
71	cmFThdGone		 		= 54,		// file thread doesn't exist
72	cmParentNotFound		= 55,		// CNode for parent ID does not exist
73	cmNotAFolder			= 56,		// Destination of move is a file, not a folder
74	cmUnknownNodeType		= 57,		// Node type isn't recognized
75
76	// Volume Check errors
77
78	vcInvalidExtentErr		= 60		// Extent record is out of bounds
79};
80
81enum {
82	fsBTInvalidHeaderErr			= btBadHdr,
83	fsBTBadRotateErr				= dsBadRotate,
84	fsBTInvalidNodeErr				= btBadNode,
85	fsBTRecordTooLargeErr			= btNoFit,
86	fsBTRecordNotFoundErr			= btNotFound,
87	fsBTDuplicateRecordErr			= btExists,
88	fsBTFullErr						= btNoSpaceAvail,
89
90	fsBTInvalidFileErr				= 0x0302,					/* no BTreeCB has been allocated for fork*/
91	fsBTrFileAlreadyOpenErr			= 0x0303,
92	fsBTInvalidIteratorErr			= 0x0308,
93	fsBTEmptyErr					= 0x030A,
94	fsBTNoMoreMapNodesErr			= 0x030B,
95	fsBTBadNodeSize					= 0x030C,
96	fsBTBadNodeType					= 0x030D,
97	fsBTInvalidKeyLengthErr			= 0x030E,
98	fsBTInvalidKeyDescriptor		= 0x030F,
99	fsBTStartOfIterationErr			= 0x0353,
100	fsBTEndOfIterationErr			= 0x0354,
101	fsBTUnknownVersionErr			= 0x0355,
102	fsBTTreeTooDeepErr				= 0x0357,
103	fsBTInvalidKeyDescriptorErr		= 0x0358,
104	fsBTInvalidKeyFieldErr			= 0x035E,
105	fsBTInvalidKeyAttributeErr		= 0x035F,
106	fsIteratorExitedScopeErr		= 0x0A02,			/* iterator exited the scope*/
107	fsIteratorScopeExceptionErr		= 0x0A03,			/* iterator is undefined due to error or movement of scope locality*/
108	fsUnknownIteratorMovementErr	= 0x0A04,			/* iterator movement is not defined*/
109	fsInvalidIterationMovmentErr	= 0x0A05,			/* iterator movement is invalid in current context*/
110	fsClientIDMismatchErr			= 0x0A06,			/* wrong client process ID*/
111	fsEndOfIterationErr				= 0x0A07,			/* there were no objects left to return on iteration*/
112	fsBTTimeOutErr					= 0x0A08			/* BTree scan interrupted -- no time left for physical I/O */
113};
114
115
116struct FSBufferDescriptor {
117	LogicalAddress 					bufferAddress;
118	ByteCount 						itemSize;
119	ItemCount 						itemCount;
120};
121typedef struct FSBufferDescriptor FSBufferDescriptor;
122
123typedef FSBufferDescriptor *FSBufferDescriptorPtr;
124
125
126
127typedef	UInt64	FSSize;
128typedef	UInt32	ForkBlockNumber;
129
130
131/*
132	BTreeObjID is used to indicate an access path using the
133	BTree access method to a specific fork of a file. This value
134	is session relative and not persistent between invocations of
135	an application. It is in fact an object ID to which requests
136	for the given path should be sent.
137 */
138typedef UInt32 BTreeObjID;
139
140/*
141	B*Tree Information Version
142*/
143
144enum BTreeInformationVersion{
145	kBTreeInfoVersion	= 0
146};
147
148/*
149	B*Tree Iteration Operation Constants
150*/
151
152enum BTreeIterationOperations{
153	kBTreeFirstRecord,
154	kBTreeNextRecord,
155	kBTreePrevRecord,
156	kBTreeLastRecord,
157	kBTreeCurrentRecord
158};
159typedef UInt16 BTreeIterationOperation;
160
161/*
162	B*Tree Key Descriptor Limits
163*/
164
165enum {
166	kMaxKeyDescriptorLength		= 23,
167};
168
169/*
170	B*Tree Key Descriptor Field Types
171*/
172
173enum {
174	kBTreeSkip				=  0,
175	kBTreeByte				=  1,
176	kBTreeSignedByte		=  2,
177	kBTreeWord				=  4,
178	kBTreeSignedWord		=  5,
179	kBTreeLong				=  6,
180	kBTreeSignedLong		=  7,
181	kBTreeString			=  3,		// Pascal string
182	kBTreeFixLenString		=  8,		// Pascal string w/ fixed length buffer
183	kBTreeReserved			=  9,		// reserved for Desktop Manager (?)
184	kBTreeUseKeyCmpProc		= 10,
185	//�� not implemented yet...
186	kBTreeCString			= 11,
187	kBTreeFixLenCString		= 12,
188	kBTreeUniCodeString		= 13,
189	kBTreeFixUniCodeString	= 14
190};
191typedef UInt8		BTreeKeyType;
192
193
194/*
195	B*Tree Key Descriptor String Field Attributes
196*/
197
198enum {
199	kBTreeCaseSens			= 0x10,		// case sensitive
200	kBTreeNotDiacSens		= 0x20		// not diacritical sensitive
201};
202typedef UInt8		BTreeStringAttributes;
203
204/*
205	Btree types: 0 is HFS CAT/EXT file, 1~127 are AppleShare B*Tree files, 128~254 unused
206	hfsBtreeType	EQU		0			; control file
207	validBTType		EQU		$80			; user btree type starts from 128
208	userBT1Type		EQU		$FF			; 255 is our Btree type. Used by BTInit and BTPatch
209*/
210
211enum BTreeTypes{
212	kHFSBTreeType			=   0,		// control file
213	kUserBTreeType			= 128,		// user btree type starts from 128
214	kReservedBTreeType		= 255		//
215};
216
217enum {
218	kInvalidMRUCacheKey		= -1L	/* flag to denote current MRU cache key is invalid*/
219
220};
221
222/*============================================================================
223	B*Tree Key Structures
224============================================================================*/
225
226/*
227	BTreeKeyDescriptor is used to indicate how keys for a particular B*Tree
228	are to be compared.
229 */
230typedef char BTreeKeyDescriptor[26];
231typedef char *BTreeKeyDescriptorPtr;
232
233/*
234	BTreeInformation is used to describe the public information about a BTree
235 */
236struct BTreeInformation{
237	UInt16						NodeSize;
238	UInt16						MaxKeyLength;
239	UInt16						Depth;
240	UInt16						Reserved;
241	ItemCount					NumRecords;
242	ItemCount					NumNodes;
243	ItemCount					NumFreeNodes;
244	ByteCount					ClumpSize;
245	BTreeKeyDescriptor			KeyDescriptor;
246	};
247typedef struct BTreeInformation BTreeInformation;
248typedef BTreeInformation *BTreeInformationPtr;
249
250typedef BTreeKey *BTreeKeyPtr;
251
252
253struct KeyDescriptor{
254	UInt8			length;
255	UInt8			fieldDesc [kMaxKeyDescriptorLength];
256};
257typedef struct KeyDescriptor KeyDescriptor;
258typedef KeyDescriptor *KeyDescriptorPtr;
259
260struct NumberFieldDescriptor{
261	UInt8			fieldType;
262	UInt8			occurrence;					// number of consecutive fields of this type
263};
264typedef struct NumberFieldDescriptor NumberFieldDescriptor;
265
266struct StringFieldDescriptor{
267	UInt8			fieldType;					// kBTString
268	UInt8			occurrence;					// number of consecutive fields of this type
269	UInt8			stringAttribute;
270	UInt8			filler;
271};
272typedef struct StringFieldDescriptor StringFieldDescriptor;
273
274struct FixedLengthStringFieldDescriptor{
275	UInt8			fieldType;					// kBTFixLenString
276	UInt8			stringLength;
277	UInt8			occurrence;
278	UInt8			stringAttribute;
279};
280typedef struct FixedLengthStringFieldDescriptor FixedLengthStringFieldDescriptor;
281
282/*
283	BTreeInfoRec Structure - for BTGetInformation
284*/
285struct BTreeInfoRec{
286	UInt16				version;
287	UInt16				nodeSize;
288	UInt16				maxKeyLength;
289	UInt16				treeDepth;
290	ItemCount			numRecords;
291	ItemCount			numNodes;
292	ItemCount			numFreeNodes;
293	KeyDescriptorPtr	keyDescriptor;
294	ByteCount			keyDescLength;
295	UInt32				reserved;
296};
297typedef struct BTreeInfoRec BTreeInfoRec;
298typedef BTreeInfoRec *BTreeInfoPtr;
299
300/*
301	BTreeHint can never be exported to the outside. Use UInt32 BTreeHint[4],
302	UInt8 BTreeHint[16], etc.
303 */
304struct BTreeHint{
305	ItemCount				writeCount;
306	UInt32					nodeNum;			// node the key was last seen in
307	UInt16					index;				// index then key was last seen at
308	UInt16					reserved1;
309	UInt32					reserved2;
310};
311typedef struct BTreeHint BTreeHint;
312typedef BTreeHint *BTreeHintPtr;
313
314/*
315	BTree Iterator
316*/
317struct BTreeIterator{
318	BTreeHint				hint;
319	UInt16					version;
320	UInt16					reserved;
321	BTreeKey				key;
322};
323typedef struct BTreeIterator BTreeIterator;
324typedef BTreeIterator *BTreeIteratorPtr;
325
326
327/*============================================================================
328	B*Tree SPI
329============================================================================*/
330
331typedef SInt32		(* KeyCompareProcPtr)	(BTreeKeyPtr a, BTreeKeyPtr b);
332
333typedef	OSStatus	(* GetBlockProcPtr)		(SFCB	*filePtr,
334											 UInt32						 blockNum,
335											 GetBlockOptions			 options,
336											 BlockDescriptor			*block );
337
338
339typedef	OSStatus	(* ReleaseBlockProcPtr)	(SFCB		*filePtr,
340											 BlockDescPtr				 blockPtr,
341											 ReleaseBlockOptions		 options );
342
343typedef	OSStatus	(* SetEndOfForkProcPtr)	(SFCB		 				*filePtr,
344											 FSSize						 minEOF,
345											 FSSize						 maxEOF );
346
347typedef	OSStatus	(* SetBlockSizeProcPtr)	(SFCB		 				*filePtr,
348											 ByteCount					 blockSize );
349
350OSStatus		SetEndOfForkProc ( SFCB		 				*filePtr, FSSize minEOF, FSSize maxEOF );
351
352
353
354extern OSStatus	InitBTreeModule		(void);
355
356
357extern OSStatus	BTInitialize		(SFCB						*filePtrPtr,
358									 UInt16						 maxKeyLength,
359									 UInt16						 nodeSize,
360									 UInt8						 btreeType,
361									 KeyDescriptorPtr			 keyDescPtr );
362
363extern OSStatus	BTOpenPath			(SFCB		 				*filePtr,
364									 KeyCompareProcPtr			 keyCompareProc,
365									 GetBlockProcPtr			 getBlockProc,
366									 ReleaseBlockProcPtr		 releaseBlockProc,
367									 SetEndOfForkProcPtr		 setEndOfForkProc,
368									 SetBlockSizeProcPtr		 setBlockSizeProc );
369
370extern OSStatus	BTClosePath			(SFCB		 				*filePtr );
371
372
373extern OSStatus	BTSearchRecord		(SFCB		 				*filePtr,
374									 BTreeIterator				*searchIterator,
375									 UInt32						heuristicHint,
376									 FSBufferDescriptor			*btRecord,
377									 UInt16						*recordLen,
378									 BTreeIterator				*resultIterator );
379
380extern OSStatus	BTIterateRecord		(SFCB		 				*filePtr,
381									 BTreeIterationOperation	 operation,
382									 BTreeIterator				*iterator,
383									 FSBufferDescriptor			*btRecord,
384									 UInt16						*recordLen );
385
386extern OSStatus	BTInsertRecord		(SFCB		 				*filePtr,
387									 BTreeIterator				*iterator,
388									 FSBufferDescriptor			*btrecord,
389									 UInt16						 recordLen );
390
391extern OSStatus	BTReplaceRecord		(SFCB		 				*filePtr,
392									 BTreeIterator				*iterator,
393									 FSBufferDescriptor			*btRecord,
394									 UInt16						 recordLen );
395
396extern OSStatus	BTSetRecord			(SFCB		 				*filePtr,
397									 BTreeIterator				*iterator,
398									 FSBufferDescriptor			*btRecord,
399									 UInt16						 recordLen );
400
401extern OSStatus	BTDeleteRecord		(SFCB		 				*filePtr,
402									 BTreeIterator				*iterator );
403
404extern OSStatus	BTGetInformation	(SFCB		 				*filePtr,
405									 UInt16						 version,
406									 BTreeInfoRec				*info );
407
408extern OSStatus	BTFlushPath			(SFCB		 				*filePtr );
409
410extern OSStatus	BTInvalidateHint	(BTreeIterator				*iterator );
411
412#endif // __BTREESINTERNAL__
413