home *** CD-ROM | disk | FTP | other *** search
/ H4CK3R 4 / hacker04 / 04_HACK04.ISO / darwin / darwinx86.iso / usr / include / hfs / hfscommon / headers / BTreesPrivate.h < prev    next >
Encoding:
C/C++ Source or Header  |  2001-09-30  |  15.5 KB  |  493 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:        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. #include "../../hfs_macos_defs.h"
  115.  
  116. #ifndef __FILEMGRINTERNAL__
  117. #include "FileMgrInternal.h"
  118. #endif
  119.  
  120. #ifndef __BTREESINTERNAL__
  121. #include "BTreesInternal.h"
  122. #endif
  123.  
  124.  
  125. /////////////////////////////////// Constants ///////////////////////////////////
  126.  
  127. #define        kBTreeVersion          1
  128. #define        kMaxTreeDepth         16
  129.  
  130.  
  131. #define        kHeaderNodeNum          0
  132. #define        kKeyDescRecord          1
  133.  
  134.  
  135. // Header Node Record Offsets
  136. enum {
  137.     kHeaderRecOffset    =    0x000E,
  138.     kKeyDescRecOffset    =    0x0078,
  139.     kHeaderMapRecOffset    =    0x00F8
  140. };
  141.  
  142. #define        kMinNodeSize        512
  143.  
  144. #define        kMinRecordSize          6
  145.                                         // where is minimum record size enforced?
  146.  
  147. // miscellaneous BTree constants
  148. enum {
  149.             kOffsetSize                = 2
  150. };
  151.  
  152. // Insert Operations
  153. typedef enum {
  154.             kInsertRecord            = 0,
  155.             kReplaceRecord            = 1
  156. } InsertType;
  157.  
  158. // illegal string attribute bits set in mask
  159. #define        kBadStrAttribMask        0xCF
  160.  
  161.  
  162.  
  163. //////////////////////////////////// Macros /////////////////////////////////////
  164.  
  165. #define        M_NodesInMap(mapSize)                ((mapSize) << 3)
  166.  
  167. #define        M_ClearBitNum(integer,bitNumber)     ((integer) &= (~(1<<(bitNumber))))
  168. #define        M_SetBitNum(integer,bitNumber)         ((integer) |= (1<<(bitNumber)))
  169. #define        M_IsOdd(integer)                     (((integer) & 1) != 0)
  170. #define        M_IsEven(integer)                     (((integer) & 1) == 0)
  171. #define        M_BTreeHeaderDirty(btreePtr)        btreePtr->flags |= kBTHeaderDirty
  172.  
  173. #define        M_MapRecordSize(nodeSize)            (nodeSize - sizeof (BTNodeDescriptor) - 6)
  174. #define        M_HeaderMapRecordSize(nodeSize)        (nodeSize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) - 128 - 8)
  175.  
  176. #define        M_SWAP_BE16_ClearBitNum(integer,bitNumber)  ((integer) &= SWAP_BE16(~(1<<(bitNumber))))
  177. #define        M_SWAP_BE16_SetBitNum(integer,bitNumber)    ((integer) |= SWAP_BE16(1<<(bitNumber)))
  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.                          Boolean forceWrite );
  323.  
  324. OSStatus    FindIteratorPosition    (BTreeControlBlockPtr     btreePtr,
  325.                                      BTreeIteratorPtr         iterator,
  326.                                      BlockDescriptor        *left,
  327.                                      BlockDescriptor        *middle,
  328.                                      BlockDescriptor        *right,
  329.                                      UInt32                    *nodeNum,
  330.                                      UInt16                    *index,
  331.                                      Boolean                *foundRecord );
  332.  
  333. OSStatus    CheckInsertParams        (FCB                    *filePtr,
  334.                                      BTreeIterator            *iterator,
  335.                                      FSBufferDescriptor        *record,
  336.                                      UInt16                     recordLen );
  337.  
  338. OSStatus    TrySimpleReplace        (BTreeControlBlockPtr     btreePtr,
  339.                                      NodeDescPtr             nodePtr,
  340.                                      BTreeIterator            *iterator,
  341.                                      FSBufferDescriptor        *record,
  342.                                      UInt16                     recordLen,
  343.                                      Boolean                *recordInserted );
  344.  
  345. OSStatus    IsItAHint                (BTreeControlBlockPtr      btreePtr, 
  346.                                      BTreeIterator             *iterator, 
  347.                                      Boolean                 *answer );
  348.  
  349. //////////////////////////////// Node Operations ////////////////////////////////
  350.  
  351. //// Node Operations
  352.  
  353. OSStatus    GetNode                    (BTreeControlBlockPtr     btreePtr,
  354.                                      UInt32                     nodeNum,
  355.                                      NodeRec                *returnNodePtr );
  356.  
  357. OSStatus    GetLeftSiblingNode        (BTreeControlBlockPtr     btreePtr,
  358.                                      NodeDescPtr             node,
  359.                                      NodeRec                *left );
  360.  
  361. #define        GetLeftSiblingNode(btree,node,left)            GetNode ((btree), ((NodeDescPtr)(node))->bLink, (left))
  362.  
  363. OSStatus    GetRightSiblingNode        (BTreeControlBlockPtr     btreePtr,
  364.                                      NodeDescPtr             node,
  365.                                      NodeRec                *right );
  366.  
  367. #define        GetRightSiblingNode(btree,node,right)        GetNode ((btree), ((NodeDescPtr)(node))->fLink, (right))
  368.  
  369.  
  370. OSStatus    GetNewNode                (BTreeControlBlockPtr     btreePtr,
  371.                                      UInt32                     nodeNum,
  372.                                      NodeRec                *returnNodePtr );
  373.  
  374. OSStatus    ReleaseNode                (BTreeControlBlockPtr     btreePtr,
  375.                                      NodePtr                 nodePtr );
  376.  
  377. OSStatus    TrashNode                (BTreeControlBlockPtr     btreePtr,
  378.                                      NodePtr                 nodePtr );
  379.  
  380. OSStatus    UpdateNode                (BTreeControlBlockPtr     btreePtr,
  381.                                      NodePtr                 nodePtr,
  382.                                      UInt32                     transactionID,
  383.                                      UInt32                     flags );
  384.  
  385. OSStatus    GetMapNode                (BTreeControlBlockPtr     btreePtr,
  386.                                      BlockDescriptor         *nodePtr,
  387.                                      UInt16                     **mapPtr,
  388.                                      UInt16                     *mapSize );
  389.  
  390. //// Node Buffer Operations
  391.  
  392. OSStatus    CheckNode                (BTreeControlBlockPtr     btreePtr,
  393.                                      NodeDescPtr             node );
  394.  
  395. void        ClearNode                (BTreeControlBlockPtr     btreePtr,
  396.                                      NodeDescPtr             node );
  397.  
  398. UInt16        GetNodeDataSize            (BTreeControlBlockPtr     btreePtr,
  399.                                      NodeDescPtr             node );
  400.  
  401. UInt16        GetNodeFreeSize            (BTreeControlBlockPtr     btreePtr,
  402.                                      NodeDescPtr             node );
  403.  
  404.  
  405. //// Record Operations
  406.  
  407. Boolean        InsertRecord            (BTreeControlBlockPtr     btreePtr,
  408.                                      NodeDescPtr              node,
  409.                                      UInt16                      index,
  410.                                      RecordPtr                 recPtr,
  411.                                      UInt16                     recSize );
  412.  
  413. Boolean        InsertKeyRecord            (BTreeControlBlockPtr     btreePtr,
  414.                                      NodeDescPtr              node,
  415.                                      UInt16                      index,
  416.                                      KeyPtr                     keyPtr,
  417.                                      UInt16                     keyLength,
  418.                                      RecordPtr                 recPtr,
  419.                                      UInt16                     recSize );
  420.  
  421. void        DeleteRecord            (BTreeControlBlockPtr    btree,
  422.                                      NodeDescPtr             node,
  423.                                      UInt16                     index );
  424.  
  425.  
  426. Boolean        SearchNode                (BTreeControlBlockPtr     btree,
  427.                                      NodeDescPtr             node,
  428.                                      KeyPtr                     searchKey,
  429.                                      UInt16                    *index );
  430.  
  431. OSStatus    GetRecordByIndex        (BTreeControlBlockPtr     btree,
  432.                                      NodeDescPtr             node,
  433.                                      UInt16                     index,
  434.                                      KeyPtr                    *keyPtr,
  435.                                      UInt8 *                *dataPtr,
  436.                                      UInt16                    *dataSize );
  437.  
  438. UInt8 *        GetRecordAddress        (BTreeControlBlockPtr     btree,
  439.                                      NodeDescPtr             node,
  440.                                      UInt16                     index );
  441.  
  442. #define GetRecordAddress(btreePtr,node,index)        ((UInt8 *)(node) + (*(short *) ((UInt8 *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize)))
  443.  
  444.  
  445. UInt16        GetRecordSize            (BTreeControlBlockPtr     btree,
  446.                                      NodeDescPtr             node,
  447.                                      UInt16                     index );
  448.  
  449. UInt32        GetChildNodeNum            (BTreeControlBlockPtr     btreePtr,
  450.                                      NodeDescPtr             nodePtr,
  451.                                      UInt16                     index );
  452.  
  453. void        MoveRecordsLeft            (UInt8 *                 src,
  454.                                      UInt8 *                 dst,
  455.                                      UInt16                     bytesToMove );
  456.  
  457. #define        MoveRecordsLeft(src,dst,bytes)            bcopy((src),(dst),(bytes))
  458.  
  459. void        MoveRecordsRight        (UInt8 *                 src,
  460.                                      UInt8 *                 dst,
  461.                                      UInt16                     bytesToMove );
  462.  
  463. #define        MoveRecordsRight(src,dst,bytes)            bcopy((src),(dst),(bytes))
  464.  
  465.  
  466. //////////////////////////////// Tree Operations ////////////////////////////////
  467.  
  468. OSStatus    SearchTree                (BTreeControlBlockPtr     btreePtr,
  469.                                      BTreeKeyPtr             keyPtr,
  470.                                      TreePathTable             treePathTable,
  471.                                      UInt32                    *nodeNum,
  472.                                      BlockDescriptor        *nodePtr,
  473.                                      UInt16                    *index );
  474.  
  475. OSStatus    InsertTree                (BTreeControlBlockPtr     btreePtr,
  476.                                      TreePathTable             treePathTable,
  477.                                      KeyPtr                     keyPtr,
  478.                                      UInt8 *                 recPtr,
  479.                                      UInt16                     recSize,
  480.                                      BlockDescriptor        *targetNode,
  481.                                      UInt16                     index,
  482.                                      UInt16                     level,
  483.                                      Boolean                 replacingKey,
  484.                                      UInt32                    *insertNode );
  485.  
  486. OSStatus    DeleteTree                (BTreeControlBlockPtr     btreePtr,
  487.                                      TreePathTable             treePathTable,
  488.                                      BlockDescriptor        *targetNode,
  489.                                      UInt16                     index,
  490.                                      UInt16                     level );
  491.  
  492. #endif //__BTREESPRIVATE__
  493.