#ifndef __BTREEPRIVATE__
#define __BTREEPRIVATE__
#include "BTree.h"
#define SupportsKeyDescriptors 0
#define kBTreeVersion 1
#define kMaxTreeDepth 16
#define kHeaderNodeNum 0
#define kKeyDescRecord 1
enum {
kHeaderRecOffset = 0x000E,
kKeyDescRecOffset = 0x0078,
kHeaderMapRecOffset = 0x00F8
};
#define kMinNodeSize 512
#define kMinRecordSize 6
enum {
kOffsetSize = 2
};
typedef enum {
kInsertRecord = 0,
kReplaceRecord = 1
} InsertType;
#define kBadStrAttribMask 0xCF
#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 ) do { ; } while (0)
#define PanicIf( condition, message ) do { ; } while (0)
#endif
struct BTreeExtensionRec;
typedef struct BTreeControlBlock {
UInt8 keyCompareType;
UInt8 btreeType;
SInt16 obsolete_fileRefNum; KeyCompareProcPtr keyCompareProc;
UInt8 reserved2[16]; UInt16 treeDepth;
UInt32 rootNode;
UInt32 leafRecords;
UInt32 firstLeafNode;
UInt32 lastLeafNode;
UInt16 nodeSize;
UInt16 maxKeyLength;
UInt32 totalNodes;
UInt32 freeNodes;
UInt32 reserved3[16];
SInt16 version;
UInt32 flags; UInt32 attributes; KeyDescriptorPtr keyDescPtr;
UInt32 writeCount;
GetBlockProcPtr getBlockProc;
ReleaseBlockProcPtr releaseBlockProc;
SetEndOfForkProcPtr setEndOfForkProc;
BTreeIterator lastIterator;
UInt32 numGetNodes;
UInt32 numGetNewNodes;
UInt32 numReleaseNodes;
UInt32 numUpdateNodes;
UInt32 numMapNodesRead; UInt32 numHintChecks;
UInt32 numPossibleHints; UInt32 numValidHints;
struct BTreeExtensionsRec *refCon; SFCB *fcbPtr;
} 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;
typedef struct {
UInt32 node; UInt16 index;
UInt16 reserved; } TreePathRecord, *TreePathRecordPtr;
typedef TreePathRecord TreePathTable [kMaxTreeDepth];
struct InsertKey {
BTreeKeyPtr keyPtr;
UInt8 * recPtr;
UInt16 keyLength;
UInt16 recSize;
Boolean replacingKey;
Boolean skipRotate;
};
typedef struct InsertKey InsertKey;
typedef BTNodeDescriptor* NodeDescPtr;
typedef UInt8 *RecordPtr;
typedef BTreeKeyPtr KeyPtr;
#define M_ExitOnError( result ) if ( ( result ) != noErr ) goto ErrorExit; else ;
#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 ) do { ; } while (0)
#define PanicIf( condition, message ) do { ; } while (0)
#endif
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 );
OSStatus AllocateNode (BTreeControlBlockPtr btreePtr,
UInt32 *nodeNum);
OSStatus FreeNode (BTreeControlBlockPtr btreePtr,
UInt32 nodeNum);
OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr,
UInt32 nodes );
UInt32 CalcMapBits (BTreeControlBlockPtr btreePtr);
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 );
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 );
void ClearNode (BTreeControlBlockPtr btreePtr,
NodeDescPtr node );
UInt16 GetNodeDataSize (BTreeControlBlockPtr btreePtr,
NodeDescPtr node );
UInt16 GetNodeFreeSize (BTreeControlBlockPtr btreePtr,
NodeDescPtr node );
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))
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__