]> git.saurik.com Git - apple/xnu.git/blob - bsd/hfs/hfscommon/headers/BTreesInternal.h
projects / apple / xnu.git / blob
? search:


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