]> git.saurik.com Git - apple/hfs.git/blob - core/BTreesInternal.h
hfs-522.100.5.tar.gz
[apple/hfs.git] / core / BTreesInternal.h
1 /*
2 * Copyright (c) 2000-2014 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: (c) 1996-1998 by Apple 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
89 enum {
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
119 struct 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 };
128 typedef struct BlockDescriptor BlockDescriptor;
129 typedef BlockDescriptor *BlockDescPtr;
130
131
132 struct FSBufferDescriptor {
133 void * bufferAddress;
134 ByteCount itemSize;
135 ItemCount itemCount;
136 };
137 typedef struct FSBufferDescriptor FSBufferDescriptor;
138
139 typedef FSBufferDescriptor *FSBufferDescriptorPtr;
140
141
142 /*
143 Fork Level Access Method Block get options
144 */
145 enum {
146 kGetBlock = 0x00000000,
147 kGetBlockHint = 0x00000001, // if set, the block is being looked up using hint
148 kForceReadBlock = 0x00000002, //\80\80 how does this relate to Read/Verify? Do we need this?
149 kGetEmptyBlock = 0x00000008
150 };
151 typedef u_int32_t GetBlockOptions;
152
153 /*
154 Fork Level Access Method Block release options
155 */
156 enum {
157 kReleaseBlock = 0x00000000,
158 kForceWriteBlock = 0x00000001,
159 kMarkBlockDirty = 0x00000002,
160 kTrashBlock = 0x00000004,
161 kLockTransaction = 0x00000100
162 };
163 typedef u_int32_t ReleaseBlockOptions;
164
165 typedef u_int64_t FSSize;
166 typedef u_int32_t ForkBlockNumber;
167
168 /*============================================================================
169 Fork Level Buffered I/O Access Method
170 ============================================================================*/
171
172 typedef OSStatus (* GetBlockProcPtr) (FileReference fileRefNum,
173 u_int32_t blockNum,
174 GetBlockOptions options,
175 BlockDescriptor *block );
176
177
178 typedef OSStatus (* ReleaseBlockProcPtr) (FileReference fileRefNum,
179 BlockDescPtr blockPtr,
180 ReleaseBlockOptions options );
181
182 typedef OSStatus (* SetEndOfForkProcPtr) (FileReference fileRefNum,
183 FSSize minEOF,
184 FSSize maxEOF );
185
186 typedef OSStatus (* SetBlockSizeProcPtr) (FileReference fileRefNum,
187 ByteCount blockSize,
188 ItemCount minBlockCount );
189
190 OSStatus SetEndOfForkProc ( FileReference fileRefNum, FSSize minEOF, FSSize maxEOF );
191
192
193 /*
194 B*Tree Information Version
195 */
196
197 enum BTreeInformationVersion{
198 kBTreeInfoVersion = 0
199 };
200
201 /*
202 B*Tree Iteration Operation Constants
203 */
204
205 enum BTreeIterationOperations{
206 kBTreeFirstRecord,
207 kBTreeNextRecord,
208 kBTreePrevRecord,
209 kBTreeLastRecord,
210 kBTreeCurrentRecord
211 };
212 typedef 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
222 enum 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
231 typedef BTreeKey *BTreeKeyPtr;
232
233
234 /*
235 BTreeInfoRec Structure - for BTGetInformation
236 */
237 struct 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 };
249 typedef struct BTreeInfoRec BTreeInfoRec;
250 typedef 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 */
256 struct 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 };
263 typedef struct BTreeHint BTreeHint;
264 typedef BTreeHint *BTreeHintPtr;
265
266 /*
267 BTree Iterator
268 */
269 struct 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 };
277 typedef struct BTreeIterator BTreeIterator;
278 typedef 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
291 typedef int32_t (* IterateCallBackProcPtr)(BTreeKeyPtr key, void * record, void * state);
292
293
294 extern OSStatus BTOpenPath(FCB *filePtr, KeyCompareProcPtr keyCompareProc);
295
296 extern OSStatus BTClosePath (FCB *filePtr );
297
298
299 extern OSStatus BTSearchRecord (FCB *filePtr,
300 BTreeIterator *searchIterator,
301 FSBufferDescriptor *btRecord,
302 u_int16_t *recordLen,
303 BTreeIterator *resultIterator );
304
305 extern OSStatus BTIterateRecord (FCB *filePtr,
306 BTreeIterationOperation operation,
307 BTreeIterator *iterator,
308 FSBufferDescriptor *btRecord,
309 u_int16_t *recordLen );
310
311
312 extern OSStatus BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator *iterator,
313 IterateCallBackProcPtr callBackProc, void * callBackState);
314
315 extern OSStatus BTInsertRecord (FCB *filePtr,
316 BTreeIterator *iterator,
317 FSBufferDescriptor *btrecord,
318 u_int16_t recordLen );
319
320 extern OSStatus BTReplaceRecord (FCB *filePtr,
321 BTreeIterator *iterator,
322 FSBufferDescriptor *btRecord,
323 u_int16_t recordLen );
324
325 extern OSStatus BTUpdateRecord (FCB *filePtr,
326 BTreeIterator *iterator,
327 IterateCallBackProcPtr callBackProc,
328 void *callBackState );
329
330 extern OSStatus BTDeleteRecord (FCB *filePtr,
331 BTreeIterator *iterator );
332
333 extern OSStatus BTGetInformation (FCB *filePtr,
334 u_int16_t vers,
335 BTreeInfoRec *info );
336
337 extern OSStatus BTIsDirty(FCB *filePtr);
338
339 extern OSStatus BTFlushPath (FCB *filePtr );
340
341 extern OSStatus BTReloadData (FCB *filePtr);
342
343 extern OSStatus BTInvalidateHint (BTreeIterator *iterator );
344
345 extern OSStatus BTGetLastSync (FCB *filePtr,
346 u_int32_t *lastfsync );
347
348 extern OSStatus BTSetLastSync (FCB *filePtr,
349 u_int32_t lastfsync );
350
351 extern OSStatus BTHasContiguousNodes(FCB *filePtr);
352
353 extern OSStatus BTGetUserData(FCB *filePtr, void * dataPtr, int dataSize);
354
355 extern OSStatus BTSetUserData(FCB *filePtr, void * dataPtr, int dataSize);
356
357 /* B-tree node reserve routines. */
358 extern void BTReserveSetup(void);
359
360 extern int BTReserveSpace(FCB *file, int operations, void * data);
361
362 extern int BTReleaseReserve(FCB *file, void * data);
363
364 extern int BTZeroUnusedNodes(FCB *file);
365
366 #endif /* __APPLE_API_PRIVATE */
367 #endif /* KERNEL */
368 #endif // __BTREESINTERNAL__