![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to BTreesPrivate.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / XNU / bsd / hfs / hfscommon / headers|
Return to BTreesPrivate.h CVS log | Up to [Apple XNU] / XNU / bsd / hfs / hfscommon / headers |
1.1 root 1: /*
2: * Copyright (c) 2000 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: BTreesPrivate.h
24:
25: Contains: Private interface file for the BTree Module.
26:
27: Version: xxx put the technology version here xxx
28:
29: Written by: Gordon Sheridan and Bill Bruffey
30:
31: Copyright: � 1992-1999 by Apple Computer, Inc., all rights reserved.
32:
33: File Ownership:
34:
35: DRI: Don Brady
36:
37: Other Contact: Mark Day
38:
39: Technology: File Systems
40:
41: Writers:
42:
43: (msd) Mark Day
44: (DSH) Deric Horn
45: (djb) Don Brady
46: (ser) Scott Roberts
47: (dkh) Dave Heller
48:
49: Change History (most recent first):
50: <MacOSX> 3/19/99 djb Disable MoveRecordsLeft/Right macros since bcopy is broken.
51:
52: <MacOSX> 8/10/98 djb Removed unused BTreeIterator from BTreeControlBlock, fixed alignment.
53:
54: <CS5> 9/4/97 djb Convert MoveRecordsLeft and GetLeftSiblingNode to macros.
55: <CS4> 7/24/97 djb Add macro for GetRecordAddress (was a function before).
56: <CS3> 7/21/97 msd GetRecordByIndex now returns an OSStatus.
57: <CS2> 7/16/97 DSH FilesInternal.i renamed FileMgrInternal.i to avoid name
58: collision
59: <CS1> 4/23/97 djb first checked in
60:
61: <HFS6> 3/17/97 DSH Added a refCon field to BTreeControlBlock, for DFA use, to point
62: to additional data. Fixed Panic macros for use with SC.
63: <HFS5> 2/19/97 djb Add InsertKey struct. Moved on-disk definitions to
64: HFSBTreesPriv.h
65: <HFS4> 1/27/97 djb InsertTree and DeleteTree are now recursive and support variable
66: sized index keys.
67: <HFS3> 1/15/97 djb Move GetFileRefNumFromFCB macro to FilesInternal.h. Added
68: kBTVariableIndexKeysMask.
69: <HFS2> 1/3/97 djb Added support for large keys.
70: <HFS1> 12/19/96 djb first checked in
71:
72: History applicable to original Scarecrow Design:
73:
74: <7> 10/25/96 ser Changing for new VFPI
75: <6> 10/18/96 ser Converting over VFPI changes
76: <5> 9/17/96 dkh More BTree statistics
77: <4> 9/16/96 dkh Revised BTree statistics
78: <3> 6/20/96 dkh Radar #1358740. Switch from using Pools to debug MemAllocators.
79: <2> 12/7/95 dkh D10E2 build. Changed usage of Ref data type to LogicalAddress.
80: <1> 10/18/95 rst Moved from Scarecrow project.
81:
82: <19> 11/22/94 djb Add prototype for GetMapNode
83: <18> 11/16/94 prp Add IsItAHint routine prototype.
84: <17> 9/30/94 prp Get in sync with D2 interface changes.
85: <16> 7/25/94 wjk Eliminate usage of BytePtr in favor of UInt8 *.
86: <15> 7/22/94 wjk Convert to the new set of header files.
87: <14> 5/31/94 srs Moved Btree types to public interface
88: <13> 12/9/93 wjk Add 68k alignment pragma's around persistent structures.
89: <12> 11/30/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
90: NRCmds environments.
91: <11> 11/23/93 wjk Changes required to compile on the RS6000.
92: <10> 8/30/93 CH Removed the M_ExitOnError and M_ReturnErrorIf macros which were
93: already defined in FileSystemPriv.h (included here).
94: <9> 8/30/93 CH Added parens around the M_ReturnErrorIf macro.
95: <8> 5/21/93 gs Add kBadClose flag. Add some prototypes for internal routines.
96: <7> 5/10/93 gs Change Ptr to BytePtr. Move BTreeTypes to BTree.h. Add
97: DeleteTree prototype.
98: <6> 3/23/93 gs Remove mysterious "flags" field from HeaderRec structure. Move
99: prototypes of private functions to top of respective source
100: files.
101: <5> 2/8/93 gs Update to use FSAgent.h Get/Release/SetEOF/SetBlockSize
102: procPtrs. Add UpdateNode routine.
103: <4> 12/10/92 gs Add Key Descriptor function declarations.
104: <3> 12/8/92 gs Add HeaderRec structure and incorporate review feedback.
105: <2> 12/2/92 gs Add GetNode and ReleaseNode callback procptrs to BTree CB, and
106: add internal function declarations.
107: <1> 11/15/92 gs first checked in
108:
109: */
110:
111: #ifndef __BTREESPRIVATE__
112: #define __BTREESPRIVATE__
113:
114: /* keep this defined until bcopy correctly handles overlaps */
115: #define BCOPY_BROKEN 1
116:
117: #include "../../hfs_macos_defs.h"
118:
119: #ifndef __FILEMGRINTERNAL__
120: #include "FileMgrInternal.h"
121: #endif
122:
123: #ifndef __BTREESINTERNAL__
124: #include "BTreesInternal.h"
125: #endif
126:
127:
128: /////////////////////////////////// Constants ///////////////////////////////////
129:
130: #define kBTreeVersion 1
131: #define kMaxTreeDepth 16
132:
133:
134: #define kHeaderNodeNum 0
135: #define kKeyDescRecord 1
136:
137:
138: // Header Node Record Offsets
139: enum {
140: kHeaderRecOffset = 0x000E,
141: kKeyDescRecOffset = 0x0078,
142: kHeaderMapRecOffset = 0x00F8
143: };
144:
145: #define kMinNodeSize 512
146:
147: #define kMinRecordSize 6
148: //�� where is minimum record size enforced?
149:
150: // miscellaneous BTree constants
151: enum {
152: kOffsetSize = 2
153: };
154:
155: // Insert Operations
156: typedef enum {
157: kInsertRecord = 0,
158: kReplaceRecord = 1
159: } InsertType;
160:
161: // illegal string attribute bits set in mask
162: #define kBadStrAttribMask 0xCF
163:
164:
165:
166: //////////////////////////////////// Macros /////////////////////////////////////
167:
168: #define M_NodesInMap(mapSize) ((mapSize) << 3)
169:
170: #define M_ClearBitNum(integer,bitNumber) ((integer) &= (~(1<<(bitNumber))))
171: #define M_SetBitNum(integer,bitNumber) ((integer) |= (1<<(bitNumber)))
172: #define M_IsOdd(integer) (((integer) & 1) != 0)
173: #define M_IsEven(integer) (((integer) & 1) == 0)
174: #define M_BTreeHeaderDirty(btreePtr) btreePtr->flags |= kBTHeaderDirty
175:
176: #define M_MapRecordSize(nodeSize) (nodeSize - sizeof (BTNodeDescriptor) - 6)
177: #define M_HeaderMapRecordSize(nodeSize) (nodeSize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) - 128 - 8)
178:
179: ///////////////////////////////////// Types /////////////////////////////////////
180:
181: typedef struct BTreeControlBlock { // fields specific to BTree CBs
182:
183: UInt8 reserved1; // keep for alignment with old style fields
184: UInt8 btreeType;
185: UInt16 treeDepth;
186: FileReference fileRefNum; // refNum of btree file
187: KeyCompareProcPtr keyCompareProc;
188: UInt32 rootNode;
189: UInt32 leafRecords;
190: UInt32 firstLeafNode;
191: UInt32 lastLeafNode;
192: UInt16 nodeSize;
193: UInt16 maxKeyLength;
194: UInt32 totalNodes;
195: UInt32 freeNodes;
196:
197: UInt16 reserved3; // 4-byte alignment
198:
199: // new fields
200: SInt16 version;
201: UInt32 flags; // dynamic flags
202: UInt32 attributes; // persistent flags
203: UInt32 writeCount;
204: UInt32 lastfsync; /* Last time that this was fsynced */
205:
206: GetBlockProcPtr getBlockProc;
207: ReleaseBlockProcPtr releaseBlockProc;
208: SetEndOfForkProcPtr setEndOfForkProc;
209:
210: // statistical information
211: UInt32 numGetNodes;
212: UInt32 numGetNewNodes;
213: UInt32 numReleaseNodes;
214: UInt32 numUpdateNodes;
215: UInt32 numMapNodesRead; // map nodes beyond header node
216: UInt32 numHintChecks;
217: UInt32 numPossibleHints; // Looks like a formated hint
218: UInt32 numValidHints; // Hint used to find correct record.
219:
220: } BTreeControlBlock, *BTreeControlBlockPtr;
221:
222:
223: UInt32 CalcKeySize(const BTreeControlBlock *btcb, const BTreeKey *key);
224: #define CalcKeySize(btcb, key) ( ((btcb)->attributes & kBTBigKeysMask) ? ((key)->length16 + 2) : ((key)->length8 + 1) )
225:
226: UInt32 KeyLength(const BTreeControlBlock *btcb, const BTreeKey *key);
227: #define KeyLength(btcb, key) ( ((btcb)->attributes & kBTBigKeysMask) ? (key)->length16 : (key)->length8 )
228:
229:
230:
231: typedef enum {
232: kBTHeaderDirty = 0x00000001
233: } BTreeFlags;
234:
235:
236: typedef SInt8 *NodeBuffer;
237: typedef BlockDescriptor NodeRec, *NodePtr; //�� remove this someday...
238:
239:
240:
241:
242: //// Tree Path Table - constructed by SearchTree, used by InsertTree and DeleteTree
243:
244: typedef struct {
245: UInt32 node; // node number
246: UInt16 index;
247: UInt16 reserved; // align size to a power of 2
248: } TreePathRecord, *TreePathRecordPtr;
249:
250: typedef TreePathRecord TreePathTable [kMaxTreeDepth];
251:
252:
253: //// InsertKey - used by InsertTree, InsertLevel and InsertNode
254:
255: struct InsertKey {
256: BTreeKeyPtr keyPtr;
257: UInt8 * recPtr;
258: UInt16 keyLength;
259: UInt16 recSize;
260: Boolean replacingKey;
261: Boolean skipRotate;
262: };
263:
264: typedef struct InsertKey InsertKey;
265:
266:
267: //// For Notational Convenience
268:
269: typedef BTNodeDescriptor* NodeDescPtr;
270: typedef UInt8 *RecordPtr;
271: typedef BTreeKeyPtr KeyPtr;
272:
273:
274: //////////////////////////////////// Globals ////////////////////////////////////
275:
276:
277: //////////////////////////////////// Macros /////////////////////////////////////
278:
279: #if DEBUG_BUILD
280: #define Panic( message ) DebugStr( (ConstStr255Param) message )
281: #define PanicIf( condition, message ) if ( condition != 0 ) DebugStr( message )
282: #else
283: #define Panic( message )
284: #define PanicIf( condition, message )
285: #endif
286:
287: // Exit function on error
288: #define M_ExitOnError( result ) if ( ( result ) != noErr ) goto ErrorExit; else ;
289:
290: // Test for passed condition and return if true
291: #define M_ReturnErrorIf( condition, error ) if ( condition ) return( error )
292:
293: //////////////////////////////// Key Operations /////////////////////////////////
294:
295: SInt32 CompareKeys (BTreeControlBlockPtr btreePtr,
296: KeyPtr searchKey,
297: KeyPtr trialKey );
298:
299: //////////////////////////////// Map Operations /////////////////////////////////
300:
301: OSStatus AllocateNode (BTreeControlBlockPtr btreePtr,
302: UInt32 *nodeNum);
303:
304: OSStatus FreeNode (BTreeControlBlockPtr btreePtr,
305: UInt32 nodeNum);
306:
307: OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr,
308: UInt32 nodes );
309:
310: UInt32 CalcMapBits (BTreeControlBlockPtr btreePtr);
311:
312:
313: //////////////////////////////// Misc Operations ////////////////////////////////
314:
315: UInt16 CalcKeyRecordSize (UInt16 keySize,
316: UInt16 recSize );
317:
318: OSStatus VerifyHeader (FCB *filePtr,
319: BTHeaderRec *header );
320:
321: OSStatus UpdateHeader (BTreeControlBlockPtr btreePtr );
322:
323: OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr,
324: BTreeIteratorPtr iterator,
325: BlockDescriptor *left,
326: BlockDescriptor *middle,
327: BlockDescriptor *right,
328: UInt32 *nodeNum,
329: UInt16 *index,
330: Boolean *foundRecord );
331:
332: OSStatus CheckInsertParams (FCB *filePtr,
333: BTreeIterator *iterator,
334: FSBufferDescriptor *record,
335: UInt16 recordLen );
336:
337: OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,
338: NodeDescPtr nodePtr,
339: BTreeIterator *iterator,
340: FSBufferDescriptor *record,
341: UInt16 recordLen,
342: Boolean *recordInserted );
343:
344: OSStatus IsItAHint (BTreeControlBlockPtr btreePtr,
345: BTreeIterator *iterator,
346: Boolean *answer );
347:
348: //////////////////////////////// Node Operations ////////////////////////////////
349:
350: //// Node Operations
351:
352: OSStatus GetNode (BTreeControlBlockPtr btreePtr,
353: UInt32 nodeNum,
354: NodeRec *returnNodePtr );
355:
356: OSStatus GetLeftSiblingNode (BTreeControlBlockPtr btreePtr,
357: NodeDescPtr node,
358: NodeRec *left );
359:
360: #define GetLeftSiblingNode(btree,node,left) GetNode ((btree), ((NodeDescPtr)(node))->bLink, (left))
361:
362: OSStatus GetRightSiblingNode (BTreeControlBlockPtr btreePtr,
363: NodeDescPtr node,
364: NodeRec *right );
365:
366: #define GetRightSiblingNode(btree,node,right) GetNode ((btree), ((NodeDescPtr)(node))->fLink, (right))
367:
368:
369: OSStatus GetNewNode (BTreeControlBlockPtr btreePtr,
370: UInt32 nodeNum,
371: NodeRec *returnNodePtr );
372:
373: OSStatus ReleaseNode (BTreeControlBlockPtr btreePtr,
374: NodePtr nodePtr );
375:
376: OSStatus UpdateNode (BTreeControlBlockPtr btreePtr,
377: NodePtr nodePtr,
378: UInt32 transactionID,
379: UInt32 flags );
380:
381: OSStatus GetMapNode (BTreeControlBlockPtr btreePtr,
382: BlockDescriptor *nodePtr,
383: UInt16 **mapPtr,
384: UInt16 *mapSize );
385:
386: //// Node Buffer Operations
387:
388: OSStatus CheckNode (BTreeControlBlockPtr btreePtr,
389: NodeDescPtr node );
390:
391: void ClearNode (BTreeControlBlockPtr btreePtr,
392: NodeDescPtr node );
393:
394: UInt16 GetNodeDataSize (BTreeControlBlockPtr btreePtr,
395: NodeDescPtr node );
396:
397: UInt16 GetNodeFreeSize (BTreeControlBlockPtr btreePtr,
398: NodeDescPtr node );
399:
400:
401: //// Record Operations
402:
403: Boolean InsertRecord (BTreeControlBlockPtr btreePtr,
404: NodeDescPtr node,
405: UInt16 index,
406: RecordPtr recPtr,
407: UInt16 recSize );
408:
409: Boolean InsertKeyRecord (BTreeControlBlockPtr btreePtr,
410: NodeDescPtr node,
411: UInt16 index,
412: KeyPtr keyPtr,
413: UInt16 keyLength,
414: RecordPtr recPtr,
415: UInt16 recSize );
416:
417: void DeleteRecord (BTreeControlBlockPtr btree,
418: NodeDescPtr node,
419: UInt16 index );
420:
421:
422: Boolean SearchNode (BTreeControlBlockPtr btree,
423: NodeDescPtr node,
424: KeyPtr searchKey,
425: UInt16 *index );
426:
427: OSStatus GetRecordByIndex (BTreeControlBlockPtr btree,
428: NodeDescPtr node,
429: UInt16 index,
430: KeyPtr *keyPtr,
431: UInt8 * *dataPtr,
432: UInt16 *dataSize );
433:
434: UInt8 * GetRecordAddress (BTreeControlBlockPtr btree,
435: NodeDescPtr node,
436: UInt16 index );
437:
438: #define GetRecordAddress(btreePtr,node,index) ((UInt8 *)(node) + (*(short *) ((UInt8 *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize)))
439:
440:
441: UInt16 GetRecordSize (BTreeControlBlockPtr btree,
442: NodeDescPtr node,
443: UInt16 index );
444:
445: UInt32 GetChildNodeNum (BTreeControlBlockPtr btreePtr,
446: NodeDescPtr nodePtr,
447: UInt16 index );
448:
449: void MoveRecordsLeft (UInt8 * src,
450: UInt8 * dst,
451: UInt16 bytesToMove );
452:
453: #if !BCOPY_BROKEN
454: #define MoveRecordsLeft(src,dst,bytes) BlockMoveData((src),(dst),(bytes))
455: #endif
456: void MoveRecordsRight (UInt8 * src,
457: UInt8 * dst,
458: UInt16 bytesToMove );
459:
460: #if !BCOPY_BROKEN
461: #define MoveRecordsRight(src,dst,bytes) BlockMoveData((src),(dst),(bytes))
462: #endif
463:
464:
465: //////////////////////////////// Tree Operations ////////////////////////////////
466:
467: OSStatus SearchTree (BTreeControlBlockPtr btreePtr,
468: BTreeKeyPtr keyPtr,
469: TreePathTable treePathTable,
470: UInt32 *nodeNum,
471: BlockDescriptor *nodePtr,
472: UInt16 *index );
473:
474: OSStatus InsertTree (BTreeControlBlockPtr btreePtr,
475: TreePathTable treePathTable,
476: KeyPtr keyPtr,
477: UInt8 * recPtr,
478: UInt16 recSize,
479: BlockDescriptor *targetNode,
480: UInt16 index,
481: UInt16 level,
482: Boolean replacingKey,
483: UInt32 *insertNode );
484:
485: OSStatus DeleteTree (BTreeControlBlockPtr btreePtr,
486: TreePathTable treePathTable,
487: BlockDescriptor *targetNode,
488: UInt16 index,
489: UInt16 level );
490:
491: #endif //__BTREESPRIVATE__
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.