home *** CD-ROM | disk | FTP | other *** search
/ H4CK3R 4 / hacker04 / 04_HACK04.ISO / darwin / darwinx86.iso / usr / include / hfs / hfscommon / headers / BTreesInternal.h next >
Encoding:
C/C++ Source or Header  |  2001-09-30  |  10.1 KB  |  334 lines
  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:        BTreesInternal.h
  24.  
  25.     Contains:    IPI to File Manager B-tree
  26.  
  27.     Version:    HFS Plus 1.0
  28.  
  29.     Copyright:    ⌐ 1996-1998 by Apple Computer, Inc., all rights reserved.
  30.  
  31.     File Ownership:
  32.  
  33.         DRI:                Don Brady
  34.  
  35.         Other Contact:        Mark Day
  36.  
  37.         Technology:            File Systems
  38.  
  39.     Writers:
  40.  
  41.         (msd)    Mark Day
  42.         (DSH)    Deric Horn
  43.         (djb)    Don Brady
  44.  
  45.     Change History (most recent first):
  46.     
  47.       <RHAP>     9/22/99    ser        Added prototypes for BTGetLastSync and BTSetLastSync
  48.       <RHAP>     6/22/98    djb        Add ERR_BASE to btree error codes to make them negative (for MacOS X only).
  49.  
  50.        <CS7>     7/28/97    msd        Add enum for fsBTTimeOutErr.
  51.        <CS6>     7/25/97    DSH        Added heuristicHint as parameter to BTSearchRecord.
  52.        <CS5>     7/24/97    djb        Add blockReadFromDisk flag to BlockDescriptor. Callbacks now use
  53.                                     a file refNum instead of an FCB.
  54.        <CS4>     7/16/97    DSH        FilesInternal.i renamed FileMgrInternal.i to avoid name
  55.                                     collision
  56.        <CS3>      6/2/97    DSH        Added SetEndOfForkProc() prototype, so Attributes.c can call it
  57.                                     directly.
  58.        <CS2>     5/19/97    djb        kMaxKeyLength is now 520.
  59.        <CS1>     4/28/97    djb        first checked in
  60.  
  61.       <HFS6>     3/17/97    DSH        Remove Key Comparison prototype, already in FilesInternal.h.
  62.       <HFS5>     2/19/97    djb        Add SetBlockSizeProcPtr. Add blockSize field to BlockDescriptor.
  63.                                     Remove E_ type error enums.
  64.       <HFS4>     1/27/97    djb        Include Types.h and FilesInternal.h.
  65.       <HFS3>     1/13/97    djb        Added kBTreeCurrentRecord for BTIterateRecord.
  66.       <HFS2>      1/3/97    djb        Added support for large keys.
  67.       <HFS1>    12/19/96    djb        first checked in
  68.  
  69. */
  70.  
  71. #ifndef    __BTREESINTERNAL__
  72. #define __BTREESINTERNAL__
  73.  
  74. #ifndef __FILEMGRINTERNAL__
  75. #include "FileMgrInternal.h"
  76. #endif
  77.  
  78. enum {
  79.     fsBTInvalidHeaderErr            = btBadHdr,
  80.     fsBTBadRotateErr                = dsBadRotate,
  81.     fsBTInvalidNodeErr                = btBadNode,
  82.     fsBTRecordTooLargeErr            = btNoFit,
  83.     fsBTRecordNotFoundErr            = btNotFound,
  84.     fsBTDuplicateRecordErr            = btExists,
  85.     fsBTFullErr                        = btNoSpaceAvail,
  86.  
  87.     fsBTInvalidFileErr                = ERR_BASE + 0x0302,    /* no BTreeCB has been allocated for fork*/
  88.     fsBTrFileAlreadyOpenErr            = ERR_BASE + 0x0303,
  89.     fsBTInvalidIteratorErr            = ERR_BASE + 0x0308,
  90.     fsBTEmptyErr                    = ERR_BASE + 0x030A,
  91.     fsBTNoMoreMapNodesErr            = ERR_BASE + 0x030B,
  92.     fsBTBadNodeSize                    = ERR_BASE + 0x030C,
  93.     fsBTBadNodeType                    = ERR_BASE + 0x030D,
  94.     fsBTInvalidKeyLengthErr            = ERR_BASE + 0x030E,
  95.     fsBTStartOfIterationErr            = ERR_BASE + 0x0353,
  96.     fsBTEndOfIterationErr            = ERR_BASE + 0x0354,
  97.     fsBTUnknownVersionErr            = ERR_BASE + 0x0355,
  98.     fsBTTreeTooDeepErr                = ERR_BASE + 0x0357,
  99.     fsIteratorExitedScopeErr        = ERR_BASE + 0x0A02,    /* iterator exited the scope*/
  100.     fsIteratorScopeExceptionErr        = ERR_BASE + 0x0A03,    /* iterator is undefined due to error or movement of scope locality*/
  101.     fsUnknownIteratorMovementErr    = ERR_BASE + 0x0A04,    /* iterator movement is not defined*/
  102.     fsInvalidIterationMovmentErr    = ERR_BASE + 0x0A05,    /* iterator movement is invalid in current context*/
  103.     fsClientIDMismatchErr            = ERR_BASE + 0x0A06,    /* wrong client process ID*/
  104.     fsEndOfIterationErr                = ERR_BASE + 0x0A07,    /* there were no objects left to return on iteration*/
  105.     fsBTTimeOutErr                    = ERR_BASE + 0x0A08        /* BTree scan interrupted -- no time left for physical I/O */
  106. };
  107.  
  108. struct BlockDescriptor{
  109.     void        *buffer;
  110.     void        *blockHeader;
  111.     ByteCount     blockSize;
  112.     Boolean         blockReadFromDisk;
  113.     Byte         reserved[3];
  114. };
  115. typedef struct BlockDescriptor BlockDescriptor;
  116. typedef BlockDescriptor *BlockDescPtr;
  117.  
  118.  
  119. struct FSBufferDescriptor {
  120.     LogicalAddress                     bufferAddress;
  121.     ByteCount                         itemSize;
  122.     ItemCount                         itemCount;
  123. };
  124. typedef struct FSBufferDescriptor FSBufferDescriptor;
  125.  
  126. typedef FSBufferDescriptor *FSBufferDescriptorPtr;
  127.  
  128.  
  129. /*
  130.     Fork Level Access Method Block get options
  131. */
  132. enum {
  133.         kGetBlock            = 0x00000000,
  134.         kForceReadBlock        = 0x00000002,    //ÇÇ how does this relate to Read/Verify? Do we need this?
  135.         kGetEmptyBlock        = 0x00000008
  136. };
  137. typedef OptionBits    GetBlockOptions;
  138.  
  139. /*
  140.     Fork Level Access Method Block release options
  141. */
  142. enum {
  143.         kReleaseBlock        = 0x00000000,
  144.         kForceWriteBlock    = 0x00000001,
  145.         kMarkBlockDirty        = 0x00000002,
  146.         kTrashBlock            = 0x00000004,
  147.         kLockTransaction    = 0x00000100
  148. };
  149. typedef OptionBits    ReleaseBlockOptions;
  150.  
  151. typedef    UInt32    FSSize;
  152. typedef    UInt32    ForkBlockNumber;
  153.  
  154. /*============================================================================
  155.     Fork Level Buffered I/O Access Method
  156. ============================================================================*/
  157.  
  158. typedef    OSStatus    (* GetBlockProcPtr)        (FileReference                 fileRefNum,
  159.                                              UInt32                         blockNum,
  160.                                              GetBlockOptions             options,
  161.                                              BlockDescriptor            *block );
  162.                              
  163.  
  164. typedef    OSStatus    (* ReleaseBlockProcPtr)    (FileReference                 fileRefNum,
  165.                                              BlockDescPtr                 blockPtr,
  166.                                              ReleaseBlockOptions         options );
  167.  
  168. typedef    OSStatus    (* SetEndOfForkProcPtr)    (FileReference                 fileRefNum,
  169.                                              FSSize                         minEOF,
  170.                                              FSSize                         maxEOF );
  171.                                  
  172. typedef    OSStatus    (* SetBlockSizeProcPtr)    (FileReference                 fileRefNum,
  173.                                              ByteCount                     blockSize,
  174.                                              ItemCount                     minBlockCount );
  175.  
  176. OSStatus        SetEndOfForkProc ( FileReference fileRefNum, FSSize minEOF, FSSize maxEOF );
  177.  
  178.  
  179. /*
  180.     B*Tree Information Version
  181. */
  182.  
  183. enum BTreeInformationVersion{
  184.     kBTreeInfoVersion    = 0
  185. };
  186.  
  187. /*
  188.     B*Tree Iteration Operation Constants
  189. */
  190.  
  191. enum BTreeIterationOperations{
  192.     kBTreeFirstRecord,
  193.     kBTreeNextRecord,
  194.     kBTreePrevRecord,
  195.     kBTreeLastRecord,
  196.     kBTreeCurrentRecord
  197. };
  198. typedef UInt16 BTreeIterationOperation;
  199.  
  200.  
  201. /*
  202.     Btree types: 0 is HFS CAT/EXT file, 1~127 are AppleShare B*Tree files, 128~254 unused
  203.     hfsBtreeType    EQU        0            ; control file
  204.     validBTType        EQU        $80            ; user btree type starts from 128
  205.     userBT1Type        EQU        $FF            ; 255 is our Btree type. Used by BTInit and BTPatch
  206. */
  207.  
  208. enum BTreeTypes{
  209.     kHFSBTreeType            =   0,        // control file
  210.     kUserBTreeType            = 128,        // user btree type starts from 128
  211.     kReservedBTreeType        = 255        //
  212. };
  213.  
  214.  
  215. typedef BTreeKey *BTreeKeyPtr;
  216.  
  217.  
  218. /*
  219.     BTreeInfoRec Structure - for BTGetInformation
  220. */
  221. struct BTreeInfoRec{
  222.     UInt16                version;
  223.     UInt16                nodeSize;
  224.     UInt16                maxKeyLength;
  225.     UInt16                treeDepth;
  226.     UInt32                lastfsync;        /* Last time that this was fsynced  */
  227.     ItemCount            numRecords;
  228.     ItemCount            numNodes;
  229.     ItemCount            numFreeNodes;
  230.     UInt32                reserved;
  231. };
  232. typedef struct BTreeInfoRec BTreeInfoRec;
  233. typedef BTreeInfoRec *BTreeInfoPtr;
  234.  
  235. /*
  236.     BTreeHint can never be exported to the outside. Use UInt32 BTreeHint[4],
  237.     UInt8 BTreeHint[16], etc.
  238.  */
  239. struct BTreeHint{
  240.     ItemCount                writeCount;
  241.     UInt32                    nodeNum;            // node the key was last seen in
  242.     UInt16                    index;                // index then key was last seen at
  243.     UInt16                    reserved1;
  244.     UInt32                    reserved2;
  245. };
  246. typedef struct BTreeHint BTreeHint;
  247. typedef BTreeHint *BTreeHintPtr;
  248.  
  249. /*
  250.     BTree Iterator
  251. */
  252. struct BTreeIterator{
  253.     BTreeHint                hint;
  254.     UInt16                    version;
  255.     UInt16                    reserved;
  256.     UInt32                    hitCount;            // Total number of leaf records hit
  257.     UInt32                    maxLeafRecs;        // Max leaf records over iteration
  258.     BTreeKey                key;
  259. };
  260. typedef struct BTreeIterator BTreeIterator;
  261. typedef BTreeIterator *BTreeIteratorPtr;
  262.  
  263.  
  264. /*============================================================================
  265.     B*Tree SPI
  266. ============================================================================*/
  267.  
  268. /*
  269.     Key Comparison Function ProcPtr Type - for BTOpenPath
  270. */
  271. //typedef SInt32                 (* KeyCompareProcPtr)(BTreeKeyPtr a, BTreeKeyPtr b);
  272.  
  273.  
  274. typedef SInt32 (* IterateCallBackProcPtr)(BTreeKeyPtr key, void * record, UInt16 recordLen, void * state);
  275.  
  276. extern OSStatus    BTOpenPath            (FCB                         *filePtr,
  277.                                      KeyCompareProcPtr             keyCompareProc,
  278.                                      GetBlockProcPtr             getBlockProc,
  279.                                      ReleaseBlockProcPtr         releaseBlockProc,
  280.                                      SetEndOfForkProcPtr         setEndOfForkProc,
  281.                                      SetBlockSizeProcPtr         setBlockSizeProc );
  282.  
  283. extern OSStatus    BTClosePath            (FCB                         *filePtr );
  284.  
  285.  
  286. extern OSStatus    BTSearchRecord        (FCB                         *filePtr,
  287.                                      BTreeIterator                *searchIterator,
  288.                                      UInt32                        heuristicHint,
  289.                                      FSBufferDescriptor            *btRecord,
  290.                                      UInt16                        *recordLen,
  291.                                      BTreeIterator                *resultIterator );
  292.  
  293. extern OSStatus    BTIterateRecord        (FCB                         *filePtr,
  294.                                      BTreeIterationOperation     operation,
  295.                                      BTreeIterator                *iterator,
  296.                                      FSBufferDescriptor            *btRecord,
  297.                                      UInt16                        *recordLen );
  298.  
  299.  
  300. extern OSStatus BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator *iterator,
  301.          IterateCallBackProcPtr     callBackProc, void * callBackState);
  302.  
  303. extern OSStatus    BTInsertRecord        (FCB                         *filePtr,
  304.                                      BTreeIterator                *iterator,
  305.                                      FSBufferDescriptor            *btrecord,
  306.                                      UInt16                         recordLen );
  307.  
  308. extern OSStatus    BTReplaceRecord        (FCB                         *filePtr,
  309.                                      BTreeIterator                *iterator,
  310.                                      FSBufferDescriptor            *btRecord,
  311.                                      UInt16                         recordLen );
  312.  
  313.  
  314. extern OSStatus    BTDeleteRecord        (FCB                         *filePtr,
  315.                                      BTreeIterator                *iterator );
  316.  
  317. extern OSStatus    BTGetInformation    (FCB                         *filePtr,
  318.                                      UInt16                         version,
  319.                                      BTreeInfoRec                *info );
  320.  
  321. extern OSStatus    BTFlushPath            (FCB                         *filePtr );
  322.  
  323. extern OSStatus BTReloadData        (FCB *filePtr);
  324.  
  325. extern OSStatus    BTInvalidateHint    (BTreeIterator                *iterator );
  326.  
  327. extern OSStatus    BTGetLastSync        (FCB                         *filePtr,
  328.                                      UInt32                        *lastfsync );
  329.  
  330. extern OSStatus    BTSetLastSync        (FCB                         *filePtr,
  331.                                      UInt32                        lastfsync );
  332.  
  333. #endif // __BTREESINTERNAL__
  334.