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