1/* 2 * Copyright (c) 1999-2008 Apple Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23/* 24 File: BTreePrivate.h 25 26 Contains: Private interface file for the BTree Module. 27 28 Version: xxx put the technology version here xxx 29 30 Written by: Gordon Sheridan and Bill Bruffey 31 32 Copyright: � 1992-1998 by Apple Computer, Inc., all rights reserved. 33*/ 34 35#ifndef __BTREEPRIVATE__ 36#define __BTREEPRIVATE__ 37 38#include "BTree.h" 39 40/////////////////////////////////// Constants /////////////////////////////////// 41 42#define SupportsKeyDescriptors 0 43 44#define kBTreeVersion 1 45#define kMaxTreeDepth 16 46 47 48#define kHeaderNodeNum 0 49#define kKeyDescRecord 1 50 51 52// Header Node Record Offsets 53enum { 54 kHeaderRecOffset = 0x000E, 55 kKeyDescRecOffset = 0x0078, 56 kHeaderMapRecOffset = 0x00F8 57}; 58 59#define kMinNodeSize 512 60 61#define kMinRecordSize 6 62 //�� where is minimum record size enforced? 63 64// miscellaneous BTree constants 65enum { 66 kOffsetSize = 2 67}; 68 69// Insert Operations 70typedef enum { 71 kInsertRecord = 0, 72 kReplaceRecord = 1 73} InsertType; 74 75// illegal string attribute bits set in mask 76#define kBadStrAttribMask 0xCF 77 78 79 80//////////////////////////////////// Macros ///////////////////////////////////// 81 82#define M_NodesInMap(mapSize) ((mapSize) << 3) 83 84#define M_ClearBitNum(integer,bitNumber) ((integer) &= (~(1<<(bitNumber)))) 85#define M_SetBitNum(integer,bitNumber) ((integer) |= (1<<(bitNumber))) 86#define M_IsOdd(integer) (((integer) & 1) != 0) 87#define M_IsEven(integer) (((integer) & 1) == 0) 88#define M_BTreeHeaderDirty(btreePtr) btreePtr->flags |= kBTHeaderDirty 89 90#define M_MapRecordSize(nodeSize) (nodeSize - sizeof (BTNodeDescriptor) - 6) 91#define M_HeaderMapRecordSize(nodeSize) (nodeSize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) - 128 - 8) 92 93#define M_SWAP_BE16_ClearBitNum(integer,bitNumber) ((integer) &= SWAP_BE16(~(1<<(bitNumber)))) 94#define M_SWAP_BE16_SetBitNum(integer,bitNumber) ((integer) |= SWAP_BE16(1<<(bitNumber))) 95 96#if DEBUG_BUILD 97 #define Panic( message ) DebugStr( (ConstStr255Param) message ) 98 #define PanicIf( condition, message ) if ( (condition) != 0 ) DebugStr( message ) 99#else 100 #define Panic( message ) do { ; } while (0) 101 #define PanicIf( condition, message ) do { ; } while (0) 102#endif 103 104///////////////////////////////////// Types ///////////////////////////////////// 105struct BTreeExtensionRec; 106 107typedef struct BTreeControlBlock { // fields specific to BTree CBs 108 109 UInt8 keyCompareType; /* Key string Comparison Type */ 110 UInt8 btreeType; 111 SInt16 obsolete_fileRefNum; // refNum of btree file 112 KeyCompareProcPtr keyCompareProc; 113 UInt8 reserved2[16]; // keep for alignment with old style fields 114 UInt16 treeDepth; 115 UInt32 rootNode; 116 UInt32 leafRecords; 117 UInt32 firstLeafNode; 118 UInt32 lastLeafNode; 119 UInt16 nodeSize; 120 UInt16 maxKeyLength; 121 UInt32 totalNodes; 122 UInt32 freeNodes; 123 UInt32 reserved3[16]; /* reserved*/ 124 125 // new fields 126 SInt16 version; 127 UInt32 flags; // dynamic flags 128 UInt32 attributes; // persistent flags 129 KeyDescriptorPtr keyDescPtr; 130 UInt32 writeCount; 131 132 GetBlockProcPtr getBlockProc; 133 ReleaseBlockProcPtr releaseBlockProc; 134 SetEndOfForkProcPtr setEndOfForkProc; 135 BTreeIterator lastIterator; // needed for System 7 iteration context 136 137 // statistical information 138 UInt32 numGetNodes; 139 UInt32 numGetNewNodes; 140 UInt32 numReleaseNodes; 141 UInt32 numUpdateNodes; 142 UInt32 numMapNodesRead; // map nodes beyond header node 143 UInt32 numHintChecks; 144 UInt32 numPossibleHints; // Looks like a formated hint 145 UInt32 numValidHints; // Hint used to find correct record. 146 147 struct BTreeExtensionsRec *refCon; // Used by DFA to point to private data. 148 SFCB *fcbPtr; // fcb of btree file 149 150} BTreeControlBlock, *BTreeControlBlockPtr; 151 152 153UInt32 CalcKeySize(const BTreeControlBlock *btcb, const BTreeKey *key); 154#define CalcKeySize(btcb, key) ( ((btcb)->attributes & kBTBigKeysMask) ? ((key)->length16 + 2) : ((key)->length8 + 1) ) 155 156UInt32 MaxKeySize(const BTreeControlBlock *btcb); 157#define MaxKeySize(btcb) ( (btcb)->maxKeyLength + ((btcb)->attributes & kBTBigKeysMask ? 2 : 1)) 158 159UInt32 KeyLength(const BTreeControlBlock *btcb, const BTreeKey *key); 160#define KeyLength(btcb, key) ( ((btcb)->attributes & kBTBigKeysMask) ? (key)->length16 : (key)->length8 ) 161 162 163typedef enum { 164 kBTHeaderDirty = 0x00000001 165} BTreeFlags; 166 167 168typedef SInt8 *NodeBuffer; 169typedef BlockDescriptor NodeRec, *NodePtr; //�� remove this someday... 170 171 172 173 174//// Tree Path Table - constructed by SearchTree, used by InsertTree and DeleteTree 175 176typedef struct { 177 UInt32 node; // node number 178 UInt16 index; 179 UInt16 reserved; // align size to a power of 2 180} TreePathRecord, *TreePathRecordPtr; 181 182typedef TreePathRecord TreePathTable [kMaxTreeDepth]; 183 184 185//// InsertKey - used by InsertTree, InsertLevel and InsertNode 186 187struct InsertKey { 188 BTreeKeyPtr keyPtr; 189 UInt8 * recPtr; 190 UInt16 keyLength; 191 UInt16 recSize; 192 Boolean replacingKey; 193 Boolean skipRotate; 194}; 195 196typedef struct InsertKey InsertKey; 197 198 199//// For Notational Convenience 200 201typedef BTNodeDescriptor* NodeDescPtr; 202typedef UInt8 *RecordPtr; 203typedef BTreeKeyPtr KeyPtr; 204 205 206//////////////////////////////////// Globals //////////////////////////////////// 207 208 209//////////////////////////////////// Macros ///////////////////////////////////// 210 211// Exit function on error 212#define M_ExitOnError( result ) if ( ( result ) != noErr ) goto ErrorExit; else ; 213 214// Test for passed condition and return if true 215#define M_ReturnErrorIf( condition, error ) if ( condition ) return( error ) 216 217#if DEBUG_BUILD 218 #define Panic( message ) DebugStr( (ConstStr255Param) message ) 219 #define PanicIf( condition, message ) if ( (condition) != 0 ) DebugStr( message ) 220#else 221 #define Panic( message ) do { ; } while (0) 222 #define PanicIf( condition, message ) do { ; } while (0) 223#endif 224 225//////////////////////////////// Key Operations ///////////////////////////////// 226 227SInt32 CompareKeys (BTreeControlBlockPtr btreePtr, 228 KeyPtr searchKey, 229 KeyPtr trialKey ); 230 231OSStatus GetKeyDescriptor (BTreeControlBlockPtr btreePtr, 232 NodeDescPtr headerNode ); 233 234OSStatus CheckKeyDescriptor (KeyDescriptorPtr keyDescPtr, 235 UInt16 maxKeyLength ); 236 237OSStatus CheckKey (KeyPtr keyPtr, 238 KeyDescriptorPtr keyDescPtr, 239 UInt16 maxKeyLength ); 240 241 242 243//////////////////////////////// Map Operations ///////////////////////////////// 244 245OSStatus AllocateNode (BTreeControlBlockPtr btreePtr, 246 UInt32 *nodeNum); 247 248OSStatus FreeNode (BTreeControlBlockPtr btreePtr, 249 UInt32 nodeNum); 250 251OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr, 252 UInt32 nodes ); 253 254UInt32 CalcMapBits (BTreeControlBlockPtr btreePtr); 255 256 257//////////////////////////////// Misc Operations //////////////////////////////// 258 259UInt16 CalcKeyRecordSize (UInt16 keySize, 260 UInt16 recSize ); 261 262OSStatus VerifyHeader (SFCB *filePtr, 263 BTHeaderRec *header ); 264 265OSStatus UpdateHeader (BTreeControlBlockPtr btreePtr ); 266 267OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr, 268 BTreeIteratorPtr iterator, 269 BlockDescriptor *left, 270 BlockDescriptor *middle, 271 BlockDescriptor *right, 272 UInt32 *nodeNum, 273 UInt16 *index, 274 Boolean *foundRecord ); 275 276OSStatus CheckInsertParams (SFCB *filePtr, 277 BTreeIterator *iterator, 278 FSBufferDescriptor *record, 279 UInt16 recordLen ); 280 281OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr, 282 NodeDescPtr nodePtr, 283 BTreeIterator *iterator, 284 FSBufferDescriptor *record, 285 UInt16 recordLen, 286 Boolean *recordInserted ); 287 288OSStatus IsItAHint (BTreeControlBlockPtr btreePtr, 289 BTreeIterator *iterator, 290 Boolean *answer ); 291 292//////////////////////////////// Node Operations //////////////////////////////// 293 294//// Node Operations 295 296OSStatus GetNode (BTreeControlBlockPtr btreePtr, 297 UInt32 nodeNum, 298 NodeRec *returnNodePtr ); 299 300OSStatus GetLeftSiblingNode (BTreeControlBlockPtr btreePtr, 301 NodeDescPtr node, 302 NodeRec *left ); 303 304#define GetLeftSiblingNode(btree,node,left) GetNode ((btree), ((NodeDescPtr)(node))->bLink, (left)) 305 306OSStatus GetRightSiblingNode (BTreeControlBlockPtr btreePtr, 307 NodeDescPtr node, 308 NodeRec *right ); 309 310#define GetRightSiblingNode(btree,node,right) GetNode ((btree), ((NodeDescPtr)(node))->fLink, (right)) 311 312 313OSStatus GetNewNode (BTreeControlBlockPtr btreePtr, 314 UInt32 nodeNum, 315 NodeRec *returnNodePtr ); 316 317OSStatus ReleaseNode (BTreeControlBlockPtr btreePtr, 318 NodePtr nodePtr ); 319OSStatus TrashNode (BTreeControlBlockPtr btreePtr, 320 NodePtr nodePtr ); 321 322OSStatus UpdateNode (BTreeControlBlockPtr btreePtr, 323 NodePtr nodePtr ); 324 325OSStatus GetMapNode (BTreeControlBlockPtr btreePtr, 326 BlockDescriptor *nodePtr, 327 UInt16 **mapPtr, 328 UInt16 *mapSize ); 329 330//// Node Buffer Operations 331 332void ClearNode (BTreeControlBlockPtr btreePtr, 333 NodeDescPtr node ); 334 335UInt16 GetNodeDataSize (BTreeControlBlockPtr btreePtr, 336 NodeDescPtr node ); 337 338UInt16 GetNodeFreeSize (BTreeControlBlockPtr btreePtr, 339 NodeDescPtr node ); 340 341 342//// Record Operations 343 344Boolean InsertRecord (BTreeControlBlockPtr btreePtr, 345 NodeDescPtr node, 346 UInt16 index, 347 RecordPtr recPtr, 348 UInt16 recSize ); 349 350Boolean InsertKeyRecord (BTreeControlBlockPtr btreePtr, 351 NodeDescPtr node, 352 UInt16 index, 353 KeyPtr keyPtr, 354 UInt16 keyLength, 355 RecordPtr recPtr, 356 UInt16 recSize ); 357 358void DeleteRecord (BTreeControlBlockPtr btree, 359 NodeDescPtr node, 360 UInt16 index ); 361 362 363Boolean SearchNode (BTreeControlBlockPtr btree, 364 NodeDescPtr node, 365 KeyPtr searchKey, 366 UInt16 *index ); 367 368OSStatus GetRecordByIndex (BTreeControlBlockPtr btree, 369 NodeDescPtr node, 370 UInt16 index, 371 KeyPtr *keyPtr, 372 UInt8 * *dataPtr, 373 UInt16 *dataSize ); 374 375UInt8 * GetRecordAddress (BTreeControlBlockPtr btree, 376 NodeDescPtr node, 377 UInt16 index ); 378 379#define GetRecordAddress(btreePtr,node,index) ((UInt8 *)(node) + (*(short *) ((UInt8 *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize))) 380 381 382UInt16 GetRecordSize (BTreeControlBlockPtr btree, 383 NodeDescPtr node, 384 UInt16 index ); 385 386UInt32 GetChildNodeNum (BTreeControlBlockPtr btreePtr, 387 NodeDescPtr nodePtr, 388 UInt16 index ); 389 390void MoveRecordsLeft (UInt8 * src, 391 UInt8 * dst, 392 UInt16 bytesToMove ); 393 394#define MoveRecordsLeft(src,dst,bytes) CopyMemory((src),(dst),(bytes)) 395 396void MoveRecordsRight (UInt8 * src, 397 UInt8 * dst, 398 UInt16 bytesToMove ); 399 400#define MoveRecordsRight(src,dst,bytes) CopyMemory((src),(dst),(bytes)) 401 402 403 404//////////////////////////////// Tree Operations //////////////////////////////// 405 406OSStatus SearchTree (BTreeControlBlockPtr btreePtr, 407 BTreeKeyPtr keyPtr, 408 TreePathTable treePathTable, 409 UInt32 *nodeNum, 410 BlockDescriptor *nodePtr, 411 UInt16 *index ); 412 413OSStatus InsertTree (BTreeControlBlockPtr btreePtr, 414 TreePathTable treePathTable, 415 KeyPtr keyPtr, 416 UInt8 * recPtr, 417 UInt16 recSize, 418 BlockDescriptor *targetNode, 419 UInt16 index, 420 UInt16 level, 421 Boolean replacingKey, 422 UInt32 *insertNode ); 423 424OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, 425 TreePathTable treePathTable, 426 BlockDescriptor *targetNode, 427 UInt16 index, 428 UInt16 level ); 429 430#endif //__BTREEPRIVATE__ 431