![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to BTreesInternal.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / headers|
Return to BTreesInternal.h CVS log | Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / headers |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.1 (the "License"). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License.
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24:
25: /*
26: File: BTreesInternal.h
27:
28: Contains: IPI to File Manager B-tree
29:
30: Version: HFS Plus 1.0
31:
32: Copyright: � 1996-1998 by Apple Computer, Inc., all rights reserved.
33:
34: File Ownership:
35:
36: DRI: Don Brady
37:
38: Other Contact: Mark Day
39:
40: Technology: File Systems
41:
42: Writers:
43:
44: (msd) Mark Day
45: (DSH) Deric Horn
46: (djb) Don Brady
47:
48: Change History (most recent first):
49:
50: <RHAP> 6/22/98 djb Add ERR_BASE to btree error codes to make them negative (for Rhapsody only).
51:
52: <CS7> 7/28/97 msd Add enum for fsBTTimeOutErr.
53: <CS6> 7/25/97 DSH Added heuristicHint as parameter to BTSearchRecord.
54: <CS5> 7/24/97 djb Add blockReadFromDisk flag to BlockDescriptor. Callbacks now use
55: a file refNum instead of an FCB.
56: <CS4> 7/16/97 DSH FilesInternal.i renamed FileMgrInternal.i to avoid name
57: collision
58: <CS3> 6/2/97 DSH Added SetEndOfForkProc() prototype, so Attributes.c can call it
59: directly.
60: <CS2> 5/19/97 djb kMaxKeyLength is now 520.
61: <CS1> 4/28/97 djb first checked in
62:
63: <HFS6> 3/17/97 DSH Remove Key Comparison prototype, already in FilesInternal.h.
64: <HFS5> 2/19/97 djb Add SetBlockSizeProcPtr. Add blockSize field to BlockDescriptor.
65: Remove E_ type error enums.
66: <HFS4> 1/27/97 djb Include Types.h and FilesInternal.h.
67: <HFS3> 1/13/97 djb Added kBTreeCurrentRecord for BTIterateRecord.
68: <HFS2> 1/3/97 djb Added support for large keys.
69: <HFS1> 12/19/96 djb first checked in
70:
71: */
72:
73: #ifndef __BTREESINTERNAL__
74: #define __BTREESINTERNAL__
75:
76: #if TARGET_OS_MAC
77: #include <Types.h>
78: #else
79: #include "system/MacOSTypes.h"
80: #endif /* TARGET_OS_MAC */
81:
82: #include "FileMgrInternal.h"
83:
84: enum {
85: fsBTInvalidHeaderErr = btBadHdr,
86: fsBTBadRotateErr = dsBadRotate,
87: fsBTInvalidNodeErr = btBadNode,
88: fsBTRecordTooLargeErr = btNoFit,
89: fsBTRecordNotFoundErr = btNotFound,
90: fsBTDuplicateRecordErr = btExists,
91: fsBTFullErr = btNoSpaceAvail,
92:
93: fsBTInvalidFileErr = ERR_BASE + 0x0302, /* no BTreeCB has been allocated for fork*/
94: fsBTrFileAlreadyOpenErr = ERR_BASE + 0x0303,
95: fsBTInvalidIteratorErr = ERR_BASE + 0x0308,
96: fsBTEmptyErr = ERR_BASE + 0x030A,
97: fsBTNoMoreMapNodesErr = ERR_BASE + 0x030B,
98: fsBTBadNodeSize = ERR_BASE + 0x030C,
99: fsBTBadNodeType = ERR_BASE + 0x030D,
100: fsBTInvalidKeyLengthErr = ERR_BASE + 0x030E,
101: fsBTInvalidKeyDescriptor = ERR_BASE + 0x030F,
102: fsBTStartOfIterationErr = ERR_BASE + 0x0353,
103: fsBTEndOfIterationErr = ERR_BASE + 0x0354,
104: fsBTUnknownVersionErr = ERR_BASE + 0x0355,
105: fsBTTreeTooDeepErr = ERR_BASE + 0x0357,
106: fsBTInvalidKeyDescriptorErr = ERR_BASE + 0x0358,
107: fsBTInvalidKeyFieldErr = ERR_BASE + 0x035E,
108: fsBTInvalidKeyAttributeErr = ERR_BASE + 0x035F,
109: fsIteratorExitedScopeErr = ERR_BASE + 0x0A02, /* iterator exited the scope*/
110: fsIteratorScopeExceptionErr = ERR_BASE + 0x0A03, /* iterator is undefined due to error or movement of scope locality*/
111: fsUnknownIteratorMovementErr = ERR_BASE + 0x0A04, /* iterator movement is not defined*/
112: fsInvalidIterationMovmentErr = ERR_BASE + 0x0A05, /* iterator movement is invalid in current context*/
113: fsClientIDMismatchErr = ERR_BASE + 0x0A06, /* wrong client process ID*/
114: fsEndOfIterationErr = ERR_BASE + 0x0A07, /* there were no objects left to return on iteration*/
115: fsBTTimeOutErr = ERR_BASE + 0x0A08 /* BTree scan interrupted -- no time left for physical I/O */
116: };
117:
118: struct BlockDescriptor{
119: void *buffer;
120: void *blockHeader;
121: ByteCount blockSize;
122: Boolean blockReadFromDisk;
123: Byte reserved[3];
124: };
125: typedef struct BlockDescriptor BlockDescriptor;
126: typedef BlockDescriptor *BlockDescPtr;
127:
128:
129: struct FSBufferDescriptor {
130: LogicalAddress bufferAddress;
131: ByteCount itemSize;
132: ItemCount itemCount;
133: };
134: typedef struct FSBufferDescriptor FSBufferDescriptor;
135:
136: typedef FSBufferDescriptor *FSBufferDescriptorPtr;
137:
138:
139: /*
140: Fork Level Access Method Block get options
141: */
142: enum {
143: kGetBlock = 0x00000000,
144: kForceReadBlock = 0x00000002, //�� how does this relate to Read/Verify? Do we need this?
145: kGetEmptyBlock = 0x00000008
146: };
147: typedef OptionBits GetBlockOptions;
148:
149: /*
150: Fork Level Access Method Block release options
151: */
152: enum {
153: kReleaseBlock = 0x00000000,
154: kForceWriteBlock = 0x00000001,
155: kMarkBlockDirty = 0x00000002,
156: kTrashBlock = 0x00000004
157: };
158: typedef OptionBits ReleaseBlockOptions;
159:
160: typedef UInt32 FSSize;
161: typedef UInt32 ForkBlockNumber;
162:
163: /*============================================================================
164: Fork Level Buffered I/O Access Method
165: ============================================================================*/
166:
167: typedef OSStatus (* GetBlockProcPtr) (FileReference fileRefNum,
168: UInt32 blockNum,
169: GetBlockOptions options,
170: BlockDescriptor *block );
171:
172:
173: typedef OSStatus (* ReleaseBlockProcPtr) (FileReference fileRefNum,
174: BlockDescPtr blockPtr,
175: ReleaseBlockOptions options );
176:
177: typedef OSStatus (* SetEndOfForkProcPtr) (FileReference fileRefNum,
178: FSSize minEOF,
179: FSSize maxEOF );
180:
181: typedef OSStatus (* SetBlockSizeProcPtr) (FileReference fileRefNum,
182: ByteCount blockSize,
183: ItemCount minBlockCount );
184:
185: OSStatus SetEndOfForkProc ( FileReference fileRefNum, FSSize minEOF, FSSize maxEOF );
186:
187: /*
188: BTreeObjID is used to indicate an access path using the
189: BTree access method to a specific fork of a file. This value
190: is session relative and not persistent between invocations of
191: an application. It is in fact an object ID to which requests
192: for the given path should be sent.
193: */
194: typedef UInt32 BTreeObjID;
195:
196: /*
197: B*Tree Information Version
198: */
199:
200: enum BTreeInformationVersion{
201: kBTreeInfoVersion = 0
202: };
203:
204: /*
205: B*Tree Iteration Operation Constants
206: */
207:
208: enum BTreeIterationOperations{
209: kBTreeFirstRecord,
210: kBTreeNextRecord,
211: kBTreePrevRecord,
212: kBTreeLastRecord,
213: kBTreeCurrentRecord
214: };
215: typedef UInt16 BTreeIterationOperation;
216:
217: /*
218: B*Tree Key Descriptor Limits
219: */
220:
221: enum BTreeKeyLimits{
222: kMaxKeyDescriptorLength = 23,
223: kMaxKeyLength = 520
224: };
225:
226: /*
227: B*Tree Key Descriptor Field Types
228: */
229:
230: enum {
231: kBTreeSkip = 0,
232: kBTreeByte = 1,
233: kBTreeSignedByte = 2,
234: kBTreeWord = 4,
235: kBTreeSignedWord = 5,
236: kBTreeLong = 6,
237: kBTreeSignedLong = 7,
238: kBTreeString = 3, // Pascal string
239: kBTreeFixLenString = 8, // Pascal string w/ fixed length buffer
240: kBTreeReserved = 9, // reserved for Desktop Manager (?)
241: kBTreeUseKeyCmpProc = 10,
242: //�� not implemented yet...
243: kBTreeCString = 11,
244: kBTreeFixLenCString = 12,
245: kBTreeUniCodeString = 13,
246: kBTreeFixUniCodeString = 14
247: };
248: typedef UInt8 BTreeKeyType;
249:
250:
251: /*
252: B*Tree Key Descriptor String Field Attributes
253: */
254:
255: enum {
256: kBTreeCaseSens = 0x10, // case sensitive
257: kBTreeNotDiacSens = 0x20 // not diacritical sensitive
258: };
259: typedef UInt8 BTreeStringAttributes;
260:
261: /*
262: Btree types: 0 is HFS CAT/EXT file, 1~127 are AppleShare B*Tree files, 128~254 unused
263: hfsBtreeType EQU 0 ; control file
264: validBTType EQU $80 ; user btree type starts from 128
265: userBT1Type EQU $FF ; 255 is our Btree type. Used by BTInit and BTPatch
266: */
267:
268: enum BTreeTypes{
269: kHFSBTreeType = 0, // control file
270: kUserBTreeType = 128, // user btree type starts from 128
271: kReservedBTreeType = 255 //
272: };
273:
274: /*============================================================================
275: B*Tree Key Structures
276: ============================================================================*/
277:
278: #if PRAGMA_STRUCT_ALIGN
279: #pragma options align=mac68k
280: #elif PRAGMA_STRUCT_PACKPUSH
281: #pragma pack(push, 2)
282: #elif PRAGMA_STRUCT_PACK
283: #pragma pack(2)
284: #endif
285:
286: /*
287: BTreeKeyDescriptor is used to indicate how keys for a particular B*Tree
288: are to be compared.
289: */
290: typedef char BTreeKeyDescriptor[26];
291: typedef char *BTreeKeyDescriptorPtr;
292:
293: /*
294: BTreeInformation is used to describe the public information about a BTree
295: */
296: struct BTreeInformation{
297: UInt16 NodeSize;
298: UInt16 MaxKeyLength;
299: UInt16 Depth;
300: UInt16 Reserved;
301: ItemCount NumRecords;
302: ItemCount NumNodes;
303: ItemCount NumFreeNodes;
304: ByteCount ClumpSize;
305: BTreeKeyDescriptor KeyDescriptor;
306: };
307: typedef struct BTreeInformation BTreeInformation;
308: typedef BTreeInformation *BTreeInformationPtr;
309:
310: union BTreeKey{
311: UInt8 length8;
312: UInt16 length16;
313: UInt8 rawData [kMaxKeyLength+2];
314: };
315:
316: typedef union BTreeKey BTreeKey;
317: typedef BTreeKey *BTreeKeyPtr;
318:
319:
320: struct KeyDescriptor{
321: UInt8 length;
322: UInt8 fieldDesc [kMaxKeyDescriptorLength];
323: };
324: typedef struct KeyDescriptor KeyDescriptor;
325: typedef KeyDescriptor *KeyDescriptorPtr;
326:
327: struct NumberFieldDescriptor{
328: UInt8 fieldType;
329: UInt8 occurrence; // number of consecutive fields of this type
330: };
331: typedef struct NumberFieldDescriptor NumberFieldDescriptor;
332:
333: struct StringFieldDescriptor{
334: UInt8 fieldType; // kBTString
335: UInt8 occurrence; // number of consecutive fields of this type
336: UInt8 stringAttribute;
337: UInt8 filler;
338: };
339: typedef struct StringFieldDescriptor StringFieldDescriptor;
340:
341: struct FixedLengthStringFieldDescriptor{
342: UInt8 fieldType; // kBTFixLenString
343: UInt8 stringLength;
344: UInt8 occurrence;
345: UInt8 stringAttribute;
346: };
347: typedef struct FixedLengthStringFieldDescriptor FixedLengthStringFieldDescriptor;
348:
349: #if PRAGMA_STRUCT_ALIGN
350: #pragma options align=reset
351: #elif PRAGMA_STRUCT_PACKPUSH
352: #pragma pack(pop)
353: #elif PRAGMA_STRUCT_PACK
354: #pragma pack()
355: #endif
356:
357: /*
358: BTreeInfoRec Structure - for BTGetInformation
359: */
360: struct BTreeInfoRec{
361: UInt16 version;
362: UInt16 nodeSize;
363: UInt16 maxKeyLength;
364: UInt16 treeDepth;
365: ItemCount numRecords;
366: ItemCount numNodes;
367: ItemCount numFreeNodes;
368: KeyDescriptorPtr keyDescriptor;
369: ByteCount keyDescLength;
370: UInt32 reserved;
371: };
372: typedef struct BTreeInfoRec BTreeInfoRec;
373: typedef BTreeInfoRec *BTreeInfoPtr;
374:
375: /*
376: BTreeHint can never be exported to the outside. Use UInt32 BTreeHint[4],
377: UInt8 BTreeHint[16], etc.
378: */
379: struct BTreeHint{
380: ItemCount writeCount;
381: UInt32 nodeNum; // node the key was last seen in
382: UInt16 index; // index then key was last seen at
383: UInt16 reserved1;
384: UInt32 reserved2;
385: };
386: typedef struct BTreeHint BTreeHint;
387: typedef BTreeHint *BTreeHintPtr;
388:
389: /*
390: BTree Iterator
391: */
392: struct BTreeIterator{
393: BTreeHint hint;
394: UInt16 version;
395: UInt16 reserved;
396: BTreeKey key;
397: };
398: typedef struct BTreeIterator BTreeIterator;
399: typedef BTreeIterator *BTreeIteratorPtr;
400:
401:
402: /*============================================================================
403: B*Tree SPI
404: ============================================================================*/
405:
406: extern OSStatus InitBTreeModule (void);
407:
408:
409: extern OSStatus BTInitialize (FCB *filePtrPtr,
410: UInt16 maxKeyLength,
411: UInt16 nodeSize,
412: UInt8 btreeType,
413: KeyDescriptorPtr keyDescPtr );
414:
415: /*
416: Key Comparison Function ProcPtr Type - for BTOpenPath
417: */
418: //typedef SInt32 (* KeyCompareProcPtr)(BTreeKeyPtr a, BTreeKeyPtr b);
419:
420: extern OSStatus BTOpenPath (FCB *filePtr,
421: KeyCompareProcPtr keyCompareProc,
422: GetBlockProcPtr getBlockProc,
423: ReleaseBlockProcPtr releaseBlockProc,
424: SetEndOfForkProcPtr setEndOfForkProc,
425: SetBlockSizeProcPtr setBlockSizeProc );
426:
427: extern OSStatus BTClosePath (FCB *filePtr );
428:
429:
430: extern OSStatus BTSearchRecord (FCB *filePtr,
431: BTreeIterator *searchIterator,
432: UInt32 heuristicHint,
433: FSBufferDescriptor *btRecord,
434: UInt16 *recordLen,
435: BTreeIterator *resultIterator );
436:
437: extern OSStatus BTIterateRecord (FCB *filePtr,
438: BTreeIterationOperation operation,
439: BTreeIterator *iterator,
440: FSBufferDescriptor *btRecord,
441: UInt16 *recordLen );
442:
443: extern OSStatus BTInsertRecord (FCB *filePtr,
444: BTreeIterator *iterator,
445: FSBufferDescriptor *btrecord,
446: UInt16 recordLen );
447:
448: extern OSStatus BTReplaceRecord (FCB *filePtr,
449: BTreeIterator *iterator,
450: FSBufferDescriptor *btRecord,
451: UInt16 recordLen );
452:
453: extern OSStatus BTSetRecord (FCB *filePtr,
454: BTreeIterator *iterator,
455: FSBufferDescriptor *btRecord,
456: UInt16 recordLen );
457:
458: extern OSStatus BTDeleteRecord (FCB *filePtr,
459: BTreeIterator *iterator );
460:
461: extern OSStatus BTGetInformation (FCB *filePtr,
462: UInt16 version,
463: BTreeInfoRec *info );
464:
465: extern OSStatus BTFlushPath (FCB *filePtr );
466:
467: extern OSStatus BTInvalidateHint (BTreeIterator *iterator );
468:
469: #endif // __BTREESINTERNAL__
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.