Return to BTreesInternal.h CVS log

Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / headers

Annotation of kernel/bsd/hfs/hfscommon/headers/BTreesInternal.h, revision 1.1

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.