Logo Search packages:      
Sourcecode: hfsprogs version File versions  Download package

BTreePrivate.h

/*
 * Copyright (c) 1999, 2005 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * "Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
 * Reserved.  This file contains Original Code and/or Modifications of
 * Original Code as defined in and that are subject to the Apple Public
 * Source License Version 1.0 (the 'License').  You may not use this file
 * except in compliance with the License.  Please obtain a copy of the
 * License at http://www.apple.com/publicsource and read it before using
 * this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License."
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*
      File:       BTreePrivate.h

      Contains:   Private interface file for the BTree Module.

      Version:    xxx put the technology version here xxx

      Written by: Gordon Sheridan and Bill Bruffey

      Copyright:   1992-1998 by Apple Computer, Inc., all rights reserved.
*/

#ifndef     __BTREEPRIVATE__
#define __BTREEPRIVATE__

#include "BTree.h"

/////////////////////////////////// Constants ///////////////////////////////////

#define           SupportsKeyDescriptors  0

#define           kBTreeVersion             1
#define           kMaxTreeDepth            16


#define           kHeaderNodeNum            0
#define           kKeyDescRecord            1


// Header Node Record Offsets
enum {
      kHeaderRecOffset  =     0x000E,
      kKeyDescRecOffset =     0x0078,
      kHeaderMapRecOffset     =     0x00F8
};

#define           kMinNodeSize            512

#define           kMinRecordSize            6
                                                            // where is minimum record size enforced?

// miscellaneous BTree constants
enum {
                  kOffsetSize                   = 2
};

// Insert Operations
typedef enum {
                  kInsertRecord                 = 0,
                  kReplaceRecord                = 1
} InsertType;

// illegal string attribute bits set in mask
#define           kBadStrAttribMask       0xCF



//////////////////////////////////// Macros /////////////////////////////////////

#define           M_NodesInMap(mapSize)                     ((mapSize) << 3)

#define           M_ClearBitNum(integer,bitNumber)    ((integer) &= (~(1<<(bitNumber))))
#define           M_SetBitNum(integer,bitNumber)            ((integer) |= (1<<(bitNumber)))
#define           M_IsOdd(integer)                          (((integer) & 1) != 0)
#define           M_IsEven(integer)                               (((integer) & 1) == 0)
#define           M_BTreeHeaderDirty(btreePtr)        btreePtr->flags |= kBTHeaderDirty

#define           M_MapRecordSize(nodeSize)                 (nodeSize - sizeof (BTNodeDescriptor) - 6)
#define           M_HeaderMapRecordSize(nodeSize)           (nodeSize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) - 128 - 8)

#define           M_SWAP_BE16_ClearBitNum(integer,bitNumber)  ((integer) &= SWAP_BE16(~(1<<(bitNumber))))
#define           M_SWAP_BE16_SetBitNum(integer,bitNumber)    ((integer) |= SWAP_BE16(1<<(bitNumber)))

#if DEBUG_BUILD
      #define Panic( message )                              DebugStr( (ConstStr255Param) message )
      #define PanicIf( condition, message )           if ( condition != 0 )   DebugStr( message )
#else
      #define Panic( message )
      #define PanicIf( condition, message )
#endif

///////////////////////////////////// Types /////////////////////////////////////

typedef struct BTreeControlBlock {                          // fields specific to BTree CBs

      UInt8       keyCompareType;   /* Key string Comparison Type */
      UInt8                                btreeType;
      SInt16                                     obsolete_fileRefNum;         // refNum of btree file
      KeyCompareProcPtr              keyCompareProc;
      UInt8                                reserved2[16];         // keep for alignment with old style fields
      UInt16                                     treeDepth;
      UInt32                                     rootNode;
      UInt32                                     leafRecords;
      UInt32                                     firstLeafNode;
      UInt32                                     lastLeafNode;
      UInt16                                     nodeSize;
      UInt16                                     maxKeyLength;
      UInt32                                     totalNodes;
      UInt32                                     freeNodes;
      UInt32                                    reserved3[16];                      /*    reserved*/

      // new fields
      SInt16                                     version;
      UInt32                                     flags;                       // dynamic flags
      UInt32                                     attributes;            // persistent flags
      KeyDescriptorPtr               keyDescPtr;
      UInt32                                     writeCount;

      GetBlockProcPtr                      getBlockProc;
      ReleaseBlockProcPtr                  releaseBlockProc;
      SetEndOfForkProcPtr                  setEndOfForkProc;
      BTreeIterator                        lastIterator;          // needed for System 7 iteration context

      // statistical information
      UInt32                                     numGetNodes;
      UInt32                                     numGetNewNodes;
      UInt32                                     numReleaseNodes;
      UInt32                                     numUpdateNodes;
      UInt32                                     numMapNodesRead; // map nodes beyond header node
      UInt32                                     numHintChecks;
      UInt32                                     numPossibleHints;      // Looks like a formated hint
      UInt32                                     numValidHints;         // Hint used to find correct record.
      
      UInt32                                     refCon;                //    Used by DFA to point to private data.
      SFCB                                *fcbPtr;          // fcb of btree file
      
} BTreeControlBlock, *BTreeControlBlockPtr;


UInt32 CalcKeySize(const BTreeControlBlock *btcb, const BTreeKey *key);
#define CalcKeySize(btcb, key)                  ( ((btcb)->attributes & kBTBigKeysMask) ? ((key)->length16 + 2) : ((key)->length8 + 1) )

UInt32 MaxKeySize(const BTreeControlBlock *btcb);
#define MaxKeySize(btcb)                        ( (btcb)->maxKeyLength + ((btcb)->attributes & kBTBigKeysMask ? 2 : 1))

UInt32 KeyLength(const BTreeControlBlock *btcb, const BTreeKey *key);
#define KeyLength(btcb, key)              ( ((btcb)->attributes & kBTBigKeysMask) ? (key)->length16 : (key)->length8 )


typedef enum {
                              kBTHeaderDirty    = 0x00000001
}     BTreeFlags;


typedef     SInt8                   *NodeBuffer;
typedef BlockDescriptor        NodeRec, *NodePtr;           // remove this someday...




//// Tree Path Table - constructed by SearchTree, used by InsertTree and DeleteTree

typedef struct {
      UInt32                        node;                   // node number
      UInt16                        index;
      UInt16                        reserved;               // align size to a power of 2
} TreePathRecord, *TreePathRecordPtr;

typedef TreePathRecord        TreePathTable [kMaxTreeDepth];


//// InsertKey - used by InsertTree, InsertLevel and InsertNode

struct InsertKey {
      BTreeKeyPtr       keyPtr;
      UInt8 *                 recPtr;
      UInt16                  keyLength;
      UInt16                  recSize;
      Boolean                 replacingKey;
      Boolean                 skipRotate;
};

typedef struct InsertKey InsertKey;


//// For Notational Convenience

typedef     BTNodeDescriptor*  NodeDescPtr;
typedef UInt8                       *RecordPtr;
typedef BTreeKeyPtr                  KeyPtr;


//////////////////////////////////// Globals ////////////////////////////////////


//////////////////////////////////// Macros /////////////////////////////////////

//    Exit function on error
#define M_ExitOnError( result )     if ( ( result ) != noErr )    goto ErrorExit; else ;

//    Test for passed condition and return if true
#define     M_ReturnErrorIf( condition, error ) if ( condition )  return( error )

#if DEBUG_BUILD
      #define Panic( message )                              DebugStr( (ConstStr255Param) message )
      #define PanicIf( condition, message )           if ( condition != 0 )   DebugStr( message )
#else
      #define Panic( message )
      #define PanicIf( condition, message )
#endif

//////////////////////////////// Key Operations /////////////////////////////////

SInt32            CompareKeys                   (BTreeControlBlockPtr    btreePtr,
                                                       KeyPtr                              searchKey,
                                                       KeyPtr                              trialKey );

OSStatus    GetKeyDescriptor        (BTreeControlBlockPtr    btreePtr,
                                                       NodeDescPtr                   headerNode );

OSStatus    CheckKeyDescriptor            (KeyDescriptorPtr        keyDescPtr,
                                                       UInt16                              maxKeyLength );

OSStatus    CheckKey                      (KeyPtr                              keyPtr,
                                                       KeyDescriptorPtr        keyDescPtr,
                                                       UInt16                              maxKeyLength );



//////////////////////////////// Map Operations /////////////////////////////////

OSStatus    AllocateNode                  (BTreeControlBlockPtr    btreePtr,
                                                       UInt32                             *nodeNum);

OSStatus    FreeNode                      (BTreeControlBlockPtr    btreePtr,
                                                       UInt32                              nodeNum);

OSStatus    ExtendBTree                   (BTreeControlBlockPtr    btreePtr,
                                                       UInt32                              nodes );

UInt32            CalcMapBits                   (BTreeControlBlockPtr    btreePtr);


//////////////////////////////// Misc Operations ////////////////////////////////

UInt16            CalcKeyRecordSize       (UInt16                              keySize,
                                                       UInt16                              recSize );

OSStatus    VerifyHeader                  (SFCB             *filePtr,
                                                       BTHeaderRec                  *header );

OSStatus    UpdateHeader                  (BTreeControlBlockPtr    btreePtr );

OSStatus    FindIteratorPosition    (BTreeControlBlockPtr    btreePtr,
                                                       BTreeIteratorPtr        iterator,
                                                       BlockDescriptor        *left,
                                                       BlockDescriptor        *middle,
                                                       BlockDescriptor        *right,
                                                       UInt32                             *nodeNum,
                                                       UInt16                             *index,
                                                       Boolean                      *foundRecord );

OSStatus    CheckInsertParams       (SFCB             *filePtr,
                                                       BTreeIterator                *iterator,
                                                       FSBufferDescriptor           *record,
                                                       UInt16                              recordLen );

OSStatus    TrySimpleReplace        (BTreeControlBlockPtr    btreePtr,
                                                       NodeDescPtr                   nodePtr,
                                                       BTreeIterator                *iterator,
                                                       FSBufferDescriptor           *record,
                                                       UInt16                              recordLen,
                                                       Boolean                      *recordInserted );

OSStatus    IsItAHint                     (BTreeControlBlockPtr    btreePtr, 
                                                       BTreeIterator                *iterator, 
                                                       Boolean                      *answer );

//////////////////////////////// Node Operations ////////////////////////////////

//// Node Operations

OSStatus    GetNode                             (BTreeControlBlockPtr    btreePtr,
                                                       UInt32                              nodeNum,
                                                       NodeRec                      *returnNodePtr );

OSStatus    GetLeftSiblingNode            (BTreeControlBlockPtr    btreePtr,
                                                       NodeDescPtr                   node,
                                                       NodeRec                      *left );

#define           GetLeftSiblingNode(btree,node,left)             GetNode ((btree), ((NodeDescPtr)(node))->bLink, (left))

OSStatus    GetRightSiblingNode           (BTreeControlBlockPtr    btreePtr,
                                                       NodeDescPtr                   node,
                                                       NodeRec                      *right );

#define           GetRightSiblingNode(btree,node,right)           GetNode ((btree), ((NodeDescPtr)(node))->fLink, (right))


OSStatus    GetNewNode                    (BTreeControlBlockPtr    btreePtr,
                                                       UInt32                              nodeNum,
                                                       NodeRec                      *returnNodePtr );

OSStatus    ReleaseNode                   (BTreeControlBlockPtr    btreePtr,
                                                       NodePtr                       nodePtr );
OSStatus    TrashNode                     (BTreeControlBlockPtr    btreePtr,
                                                      NodePtr                        nodePtr );

OSStatus    UpdateNode                    (BTreeControlBlockPtr    btreePtr,
                                                       NodePtr                       nodePtr );

OSStatus    GetMapNode                    (BTreeControlBlockPtr    btreePtr,
                                                       BlockDescriptor         *nodePtr,
                                                       UInt16                              **mapPtr,
                                                       UInt16                              *mapSize );

//// Node Buffer Operations

void        ClearNode                     (BTreeControlBlockPtr    btreePtr,
                                                       NodeDescPtr                   node );

UInt16            GetNodeDataSize               (BTreeControlBlockPtr    btreePtr,
                                                       NodeDescPtr                   node );

UInt16            GetNodeFreeSize               (BTreeControlBlockPtr    btreePtr,
                                                       NodeDescPtr                   node );


//// Record Operations

Boolean           InsertRecord                  (BTreeControlBlockPtr    btreePtr,
                                                       NodeDescPtr                   node,
                                                       UInt16                              index,
                                                       RecordPtr                     recPtr,
                                                       UInt16                              recSize );

Boolean           InsertKeyRecord               (BTreeControlBlockPtr    btreePtr,
                                                       NodeDescPtr                   node,
                                                       UInt16                              index,
                                                       KeyPtr                              keyPtr,
                                                       UInt16                              keyLength,
                                                       RecordPtr                     recPtr,
                                                       UInt16                              recSize );

void        DeleteRecord                  (BTreeControlBlockPtr   btree,
                                                       NodeDescPtr                  node,
                                                       UInt16                             index );


Boolean           SearchNode                    (BTreeControlBlockPtr    btree,
                                                       NodeDescPtr                   node,
                                                       KeyPtr                              searchKey,
                                                       UInt16                             *index );

OSStatus    GetRecordByIndex        (BTreeControlBlockPtr    btree,
                                                       NodeDescPtr                   node,
                                                       UInt16                              index,
                                                       KeyPtr                             *keyPtr,
                                                       UInt8 *                      *dataPtr,
                                                       UInt16                             *dataSize );

UInt8 *           GetRecordAddress        (BTreeControlBlockPtr    btree,
                                                       NodeDescPtr                   node,
                                                       UInt16                              index );

#define GetRecordAddress(btreePtr,node,index)         ((UInt8 *)(node) + (*(short *) ((UInt8 *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize)))


UInt16            GetRecordSize                 (BTreeControlBlockPtr    btree,
                                                       NodeDescPtr                   node,
                                                       UInt16                              index );

UInt32            GetChildNodeNum               (BTreeControlBlockPtr    btreePtr,
                                                       NodeDescPtr                   nodePtr,
                                                       UInt16                              index );

void        MoveRecordsLeft               (UInt8 *                       src,
                                                       UInt8 *                       dst,
                                                       UInt16                              bytesToMove );

#define           MoveRecordsLeft(src,dst,bytes)                  CopyMemory((src),(dst),(bytes))

void        MoveRecordsRight        (UInt8 *                       src,
                                                       UInt8 *                       dst,
                                                       UInt16                              bytesToMove );

#define           MoveRecordsRight(src,dst,bytes)                 CopyMemory((src),(dst),(bytes))



//////////////////////////////// Tree Operations ////////////////////////////////

OSStatus    SearchTree                    (BTreeControlBlockPtr    btreePtr,
                                                       BTreeKeyPtr                   keyPtr,
                                                       TreePathTable                 treePathTable,
                                                       UInt32                             *nodeNum,
                                                       BlockDescriptor        *nodePtr,
                                                       UInt16                             *index );

OSStatus    InsertTree                    (BTreeControlBlockPtr    btreePtr,
                                                       TreePathTable                 treePathTable,
                                                       KeyPtr                              keyPtr,
                                                       UInt8 *                       recPtr,
                                                       UInt16                              recSize,
                                                       BlockDescriptor        *targetNode,
                                                       UInt16                              index,
                                                       UInt16                              level,
                                                       Boolean                       replacingKey,
                                                       UInt32                             *insertNode );

OSStatus    DeleteTree                    (BTreeControlBlockPtr    btreePtr,
                                                       TreePathTable                 treePathTable,
                                                       BlockDescriptor        *targetNode,
                                                       UInt16                              index,
                                                       UInt16                              level );

#endif //__BTREEPRIVATE__

Generated by  Doxygen 1.6.0   Back to index