File: BTree.h

package info (click to toggle)
hfsprogs 332.25-11
  • links: PTS
  • area: main
  • in suites: bullseye, buster, jessie, jessie-kfreebsd, sid, stretch
  • size: 6,440 kB
  • ctags: 7,805
  • sloc: ansic: 58,120; makefile: 25
file content (413 lines) | stat: -rw-r--r-- 12,043 bytes parent folder | download | duplicates (4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
/*
 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * "Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
 * Reserved.  This file contains Original Code and/or Modifications of
 * Original Code as defined in and that are subject to the Apple Public
 * Source License Version 1.0 (the 'License').  You may not use this file
 * except in compliance with the License.  Please obtain a copy of the
 * License at http://www.apple.com/publicsource and read it before using
 * this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License."
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*
	File:		BTreesInternal.h

	Contains:	IPI to File Manager B-tree

	Version:	HFS Plus 1.0

	Copyright:	� 1996-1998 by Apple Computer, Inc., all rights reserved.
*/

#ifndef	__BTREESINTERNAL__
#define __BTREESINTERNAL__

#include "SRuntime.h"

//
// internal error codes
//
enum {
	// FXM errors

	fxRangeErr				= 16,		// file position beyond mapped range
	fxOvFlErr				= 17,		// extents file overflow

	// Unicode errors
	
	uniTooLongErr			= 24,		// Unicode string too long to convert to Str31
	uniBufferTooSmallErr	= 25,		// Unicode output buffer too small
	uniNotMappableErr		= 26,		// Unicode string can't be mapped to given script

	// BTree Manager errors

	btNotFound		 		= 32,		// record not found
	btExists  		 		= 33,		// record already exists
	btNoSpaceAvail			= 34,		// no available space
	btNoFit   		 		= 35,		// record doesn't fit in node 
	btBadNode 		 		= 36,		// bad node detected
	btBadHdr  		 		= 37,		// bad BTree header record detected
	dsBadRotate   	 		= 64,		// bad BTree rotate

	// Catalog Manager errors

	cmNotFound		 		= 48,		// CNode not found
	cmExists  		 		= 49,		// CNode already exists
	cmNotEmpty		 		= 50,		// directory CNode not empty (valence = 0)
	cmRootCN  		 		= 51,		// invalid reference to root CNode
	cmBadNews 		 		= 52,		// detected bad catalog structure
	cmFThdDirErr  	 		= 53,		// thread belongs to a directory not a file
	cmFThdGone		 		= 54,		// file thread doesn't exist
	cmParentNotFound		= 55,		// CNode for parent ID does not exist
	cmNotAFolder			= 56,		// Destination of move is a file, not a folder
	cmUnknownNodeType		= 57,		// Node type isn't recognized

	// Volume Check errors
	
	vcInvalidExtentErr		= 60		// Extent record is out of bounds
};

enum {
	fsBTInvalidHeaderErr			= btBadHdr,
	fsBTBadRotateErr				= dsBadRotate,
	fsBTInvalidNodeErr				= btBadNode,
	fsBTRecordTooLargeErr			= btNoFit,
	fsBTRecordNotFoundErr			= btNotFound,
	fsBTDuplicateRecordErr			= btExists,
	fsBTFullErr						= btNoSpaceAvail,

	fsBTInvalidFileErr				= 0x0302,					/* no BTreeCB has been allocated for fork*/
	fsBTrFileAlreadyOpenErr			= 0x0303,
	fsBTInvalidIteratorErr			= 0x0308,
	fsBTEmptyErr					= 0x030A,
	fsBTNoMoreMapNodesErr			= 0x030B,
	fsBTBadNodeSize					= 0x030C,
	fsBTBadNodeType					= 0x030D,
	fsBTInvalidKeyLengthErr			= 0x030E,
	fsBTInvalidKeyDescriptor		= 0x030F,
	fsBTStartOfIterationErr			= 0x0353,
	fsBTEndOfIterationErr			= 0x0354,
	fsBTUnknownVersionErr			= 0x0355,
	fsBTTreeTooDeepErr				= 0x0357,
	fsBTInvalidKeyDescriptorErr		= 0x0358,
	fsBTInvalidKeyFieldErr			= 0x035E,
	fsBTInvalidKeyAttributeErr		= 0x035F,
	fsIteratorExitedScopeErr		= 0x0A02,			/* iterator exited the scope*/
	fsIteratorScopeExceptionErr		= 0x0A03,			/* iterator is undefined due to error or movement of scope locality*/
	fsUnknownIteratorMovementErr	= 0x0A04,			/* iterator movement is not defined*/
	fsInvalidIterationMovmentErr	= 0x0A05,			/* iterator movement is invalid in current context*/
	fsClientIDMismatchErr			= 0x0A06,			/* wrong client process ID*/
	fsEndOfIterationErr				= 0x0A07,			/* there were no objects left to return on iteration*/
	fsBTTimeOutErr					= 0x0A08			/* BTree scan interrupted -- no time left for physical I/O */
};


struct FSBufferDescriptor {
	LogicalAddress 					bufferAddress;
	ByteCount 						itemSize;
	ItemCount 						itemCount;
};
typedef struct FSBufferDescriptor FSBufferDescriptor;

typedef FSBufferDescriptor *FSBufferDescriptorPtr;



typedef	UInt64	FSSize;
typedef	UInt32	ForkBlockNumber;


/*
	BTreeObjID is used to indicate an access path using the
	BTree access method to a specific fork of a file. This value
	is session relative and not persistent between invocations of
	an application. It is in fact an object ID to which requests
	for the given path should be sent.
 */
typedef UInt32 BTreeObjID;

/*
	B*Tree Information Version
*/

enum BTreeInformationVersion{
	kBTreeInfoVersion	= 0
};

/*
	B*Tree Iteration Operation Constants
*/

enum BTreeIterationOperations{
	kBTreeFirstRecord,
	kBTreeNextRecord,
	kBTreePrevRecord,
	kBTreeLastRecord,
	kBTreeCurrentRecord
};
typedef UInt16 BTreeIterationOperation;

/*
	B*Tree Key Descriptor Limits
*/

enum {
	kMaxKeyDescriptorLength		= 23,
};

/*
	B*Tree Key Descriptor Field Types
*/

enum {
	kBTreeSkip				=  0,
	kBTreeByte				=  1,
	kBTreeSignedByte		=  2,
	kBTreeWord				=  4,
	kBTreeSignedWord		=  5,
	kBTreeLong				=  6,
	kBTreeSignedLong		=  7,
	kBTreeString			=  3,		// Pascal string
	kBTreeFixLenString		=  8,		// Pascal string w/ fixed length buffer
	kBTreeReserved			=  9,		// reserved for Desktop Manager (?)
	kBTreeUseKeyCmpProc		= 10,
	//�� not implemented yet...
	kBTreeCString			= 11,
	kBTreeFixLenCString		= 12,
	kBTreeUniCodeString		= 13,
	kBTreeFixUniCodeString	= 14
};
typedef UInt8		BTreeKeyType;


/*
	B*Tree Key Descriptor String Field Attributes
*/

enum {
	kBTreeCaseSens			= 0x10,		// case sensitive
	kBTreeNotDiacSens		= 0x20		// not diacritical sensitive
};
typedef UInt8		BTreeStringAttributes;

/*
	Btree types: 0 is HFS CAT/EXT file, 1~127 are AppleShare B*Tree files, 128~254 unused
	hfsBtreeType	EQU		0			; control file
	validBTType		EQU		$80			; user btree type starts from 128
	userBT1Type		EQU		$FF			; 255 is our Btree type. Used by BTInit and BTPatch
*/

enum BTreeTypes{
	kHFSBTreeType			=   0,		// control file
	kUserBTreeType			= 128,		// user btree type starts from 128
	kReservedBTreeType		= 255		//
};

enum {
	kInvalidMRUCacheKey		= -1L	/* flag to denote current MRU cache key is invalid*/

};

/*============================================================================
	B*Tree Key Structures
============================================================================*/

/*
	BTreeKeyDescriptor is used to indicate how keys for a particular B*Tree
	are to be compared.
 */
typedef char BTreeKeyDescriptor[26];
typedef char *BTreeKeyDescriptorPtr;

/*
	BTreeInformation is used to describe the public information about a BTree
 */
struct BTreeInformation{
	UInt16						NodeSize;
	UInt16						MaxKeyLength;
	UInt16						Depth;
	UInt16						Reserved;
	ItemCount					NumRecords;
	ItemCount					NumNodes;
	ItemCount					NumFreeNodes;
	ByteCount					ClumpSize;
	BTreeKeyDescriptor			KeyDescriptor;
	};
typedef struct BTreeInformation BTreeInformation;
typedef BTreeInformation *BTreeInformationPtr;

typedef BTreeKey *BTreeKeyPtr;


struct KeyDescriptor{
	UInt8			length;
	UInt8			fieldDesc [kMaxKeyDescriptorLength];
};
typedef struct KeyDescriptor KeyDescriptor;
typedef KeyDescriptor *KeyDescriptorPtr;

struct NumberFieldDescriptor{
	UInt8			fieldType;
	UInt8			occurrence;					// number of consecutive fields of this type
};
typedef struct NumberFieldDescriptor NumberFieldDescriptor;

struct StringFieldDescriptor{
	UInt8			fieldType;					// kBTString
	UInt8			occurrence;					// number of consecutive fields of this type
	UInt8			stringAttribute;
	UInt8			filler;
};
typedef struct StringFieldDescriptor StringFieldDescriptor;

struct FixedLengthStringFieldDescriptor{
	UInt8			fieldType;					// kBTFixLenString
	UInt8			stringLength;
	UInt8			occurrence;
	UInt8			stringAttribute;
};
typedef struct FixedLengthStringFieldDescriptor FixedLengthStringFieldDescriptor;

/*
	BTreeInfoRec Structure - for BTGetInformation
*/
struct BTreeInfoRec{
	UInt16				version;
	UInt16				nodeSize;
	UInt16				maxKeyLength;
	UInt16				treeDepth;
	ItemCount			numRecords;
	ItemCount			numNodes;
	ItemCount			numFreeNodes;
	KeyDescriptorPtr	keyDescriptor;
	ByteCount			keyDescLength;
	UInt32				reserved;
};
typedef struct BTreeInfoRec BTreeInfoRec;
typedef BTreeInfoRec *BTreeInfoPtr;

/*
	BTreeHint can never be exported to the outside. Use UInt32 BTreeHint[4],
	UInt8 BTreeHint[16], etc.
 */
struct BTreeHint{
	ItemCount				writeCount;
	UInt32					nodeNum;			// node the key was last seen in
	UInt16					index;				// index then key was last seen at
	UInt16					reserved1;
	UInt32					reserved2;
};
typedef struct BTreeHint BTreeHint;
typedef BTreeHint *BTreeHintPtr;

/*
	BTree Iterator
*/
struct BTreeIterator{
	BTreeHint				hint;
	UInt16					version;
	UInt16					reserved;
	BTreeKey				key;
};
typedef struct BTreeIterator BTreeIterator;
typedef BTreeIterator *BTreeIteratorPtr;


/*============================================================================
	B*Tree SPI
============================================================================*/

typedef SInt32		(* KeyCompareProcPtr)	(BTreeKeyPtr a, BTreeKeyPtr b);

typedef	OSStatus	(* GetBlockProcPtr)		(SFCB	*filePtr,
											 UInt32						 blockNum,
											 GetBlockOptions			 options,
											 BlockDescriptor			*block );
							 

typedef	OSStatus	(* ReleaseBlockProcPtr)	(SFCB		*filePtr,
											 BlockDescPtr				 blockPtr,
											 ReleaseBlockOptions		 options );

typedef	OSStatus	(* SetEndOfForkProcPtr)	(SFCB		 				*filePtr,
											 FSSize						 minEOF,
											 FSSize						 maxEOF );
								 
typedef	OSStatus	(* SetBlockSizeProcPtr)	(SFCB		 				*filePtr,
											 ByteCount					 blockSize );

OSStatus		SetEndOfForkProc ( SFCB		 				*filePtr, FSSize minEOF, FSSize maxEOF );



extern OSStatus	InitBTreeModule		(void);


extern OSStatus	BTInitialize		(SFCB						*filePtrPtr,
									 UInt16						 maxKeyLength,
									 UInt16						 nodeSize,
									 UInt8						 btreeType,
									 KeyDescriptorPtr			 keyDescPtr );

extern OSStatus	BTOpenPath			(SFCB		 				*filePtr,
									 KeyCompareProcPtr			 keyCompareProc,
									 GetBlockProcPtr			 getBlockProc,
									 ReleaseBlockProcPtr		 releaseBlockProc,
									 SetEndOfForkProcPtr		 setEndOfForkProc,
									 SetBlockSizeProcPtr		 setBlockSizeProc );

extern OSStatus	BTClosePath			(SFCB		 				*filePtr );


extern OSStatus	BTSearchRecord		(SFCB		 				*filePtr,
									 BTreeIterator				*searchIterator,
									 UInt32						heuristicHint,
									 FSBufferDescriptor			*btRecord,
									 UInt16						*recordLen,
									 BTreeIterator				*resultIterator );

extern OSStatus	BTIterateRecord		(SFCB		 				*filePtr,
									 BTreeIterationOperation	 operation,
									 BTreeIterator				*iterator,
									 FSBufferDescriptor			*btRecord,
									 UInt16						*recordLen );

extern OSStatus	BTInsertRecord		(SFCB		 				*filePtr,
									 BTreeIterator				*iterator,
									 FSBufferDescriptor			*btrecord,
									 UInt16						 recordLen );

extern OSStatus	BTReplaceRecord		(SFCB		 				*filePtr,
									 BTreeIterator				*iterator,
									 FSBufferDescriptor			*btRecord,
									 UInt16						 recordLen );

extern OSStatus	BTSetRecord			(SFCB		 				*filePtr,
									 BTreeIterator				*iterator,
									 FSBufferDescriptor			*btRecord,
									 UInt16						 recordLen );

extern OSStatus	BTDeleteRecord		(SFCB		 				*filePtr,
									 BTreeIterator				*iterator );

extern OSStatus	BTGetInformation	(SFCB		 				*filePtr,
									 UInt16						 version,
									 BTreeInfoRec				*info );

extern OSStatus	BTFlushPath			(SFCB		 				*filePtr );

extern OSStatus	BTInvalidateHint	(BTreeIterator				*iterator );

#endif // __BTREESINTERNAL__