fsck_hfs/dfalib/BTreePrivate.h

   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
  53 enum {
  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
  65 enum {
  66                         kOffsetSize                             = 2
  67 };
  68
  69 // Insert Operations
  70 typedef 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 /////////////////////////////////////
 105 struct BTreeExtensionRec;
 106
 107 typedef 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
 153 UInt32 CalcKeySize(const BTreeControlBlock *btcb, const BTreeKey *key);
 154 #define CalcKeySize(btcb, key)                  ( ((btcb)->attributes & kBTBigKeysMask) ? ((key)->length16 + 2) : ((key)->length8 + 1) )
 155
 156 UInt32 MaxKeySize(const BTreeControlBlock *btcb);
 157 #define MaxKeySize(btcb)                                ( (btcb)->maxKeyLength + ((btcb)->attributes & kBTBigKeysMask ? 2 : 1))
 158
 159 UInt32 KeyLength(const BTreeControlBlock *btcb, const BTreeKey *key);
 160 #define KeyLength(btcb, key)                    ( ((btcb)->attributes & kBTBigKeysMask) ? (key)->length16 : (key)->length8 )
 161
 162
 163 typedef enum {
 164                                         kBTHeaderDirty  = 0x00000001
 165 }       BTreeFlags;
 166
 167
 168 typedef SInt8                           *NodeBuffer;
 169 typedef BlockDescriptor          NodeRec, *NodePtr;             //¥¥ remove this someday...
 170
 171
 172
 173
 174 //// Tree Path Table - constructed by SearchTree, used by InsertTree and DeleteTree
 175
 176 typedef struct {
 177         UInt32                          node;                           // node number
 178         UInt16                          index;
 179         UInt16                          reserved;                       // align size to a power of 2
 180 } TreePathRecord, *TreePathRecordPtr;
 181
 182 typedef TreePathRecord          TreePathTable [kMaxTreeDepth];
 183
 184
 185 //// InsertKey - used by InsertTree, InsertLevel and InsertNode
 186
 187 struct InsertKey {
 188         BTreeKeyPtr             keyPtr;
 189         UInt8 *                 recPtr;
 190         UInt16                  keyLength;
 191         UInt16                  recSize;
 192         Boolean                 replacingKey;
 193         Boolean                 skipRotate;
 194 };
 195
 196 typedef struct InsertKey InsertKey;
 197
 198
 199 //// For Notational Convenience
 200
 201 typedef BTNodeDescriptor*        NodeDescPtr;
 202 typedef UInt8                           *RecordPtr;
 203 typedef 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
 227 SInt32          CompareKeys                             (BTreeControlBlockPtr    btreePtr,
 228                                                                          KeyPtr                                  searchKey,
 229                                                                          KeyPtr                                  trialKey );
 230
 231 OSStatus        GetKeyDescriptor                (BTreeControlBlockPtr    btreePtr,
 232                                                                          NodeDescPtr                     headerNode );
 233
 234 OSStatus        CheckKeyDescriptor              (KeyDescriptorPtr                keyDescPtr,
 235                                                                          UInt16                                  maxKeyLength );
 236
 237 OSStatus        CheckKey                                (KeyPtr                                  keyPtr,
 238                                                                          KeyDescriptorPtr                keyDescPtr,
 239                                                                          UInt16                                  maxKeyLength );
 240
 241
 242
 243 //////////////////////////////// Map Operations /////////////////////////////////
 244
 245 OSStatus        AllocateNode                    (BTreeControlBlockPtr    btreePtr,
 246                                                                          UInt32                                 *nodeNum);
 247
 248 OSStatus        FreeNode                                (BTreeControlBlockPtr    btreePtr,
 249                                                                          UInt32                                  nodeNum);
 250
 251 OSStatus        ExtendBTree                             (BTreeControlBlockPtr    btreePtr,
 252                                                                          UInt32                                  nodes );
 253
 254 UInt32          CalcMapBits                             (BTreeControlBlockPtr    btreePtr);
 255
 256
 257 //////////////////////////////// Misc Operations ////////////////////////////////
 258
 259 UInt16          CalcKeyRecordSize               (UInt16                                  keySize,
 260                                                                          UInt16                                  recSize );
 261
 262 OSStatus        VerifyHeader                    (SFCB                   *filePtr,
 263                                                                          BTHeaderRec                    *header );
 264
 265 OSStatus        UpdateHeader                    (BTreeControlBlockPtr    btreePtr );
 266
 267 OSStatus        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
 276 OSStatus        CheckInsertParams               (SFCB                   *filePtr,
 277                                                                          BTreeIterator                  *iterator,
 278                                                                          FSBufferDescriptor             *record,
 279                                                                          UInt16                                  recordLen );
 280
 281 OSStatus        TrySimpleReplace                (BTreeControlBlockPtr    btreePtr,
 282                                                                          NodeDescPtr                     nodePtr,
 283                                                                          BTreeIterator                  *iterator,
 284                                                                          FSBufferDescriptor             *record,
 285                                                                          UInt16                                  recordLen,
 286                                                                          Boolean                                *recordInserted );
 287
 288 OSStatus        IsItAHint                               (BTreeControlBlockPtr    btreePtr,
 289                                                                          BTreeIterator                  *iterator,
 290                                                                          Boolean                                *answer );
 291
 292 //////////////////////////////// Node Operations ////////////////////////////////
 293
 294 //// Node Operations
 295
 296 OSStatus        GetNode                                 (BTreeControlBlockPtr    btreePtr,
 297                                                                          UInt32                                  nodeNum,
 298                                                                          NodeRec                                *returnNodePtr );
 299
 300 OSStatus        GetLeftSiblingNode              (BTreeControlBlockPtr    btreePtr,
 301                                                                          NodeDescPtr                     node,
 302                                                                          NodeRec                                *left );
 303
 304 #define         GetLeftSiblingNode(btree,node,left)                     GetNode ((btree), ((NodeDescPtr)(node))->bLink, (left))
 305
 306 OSStatus        GetRightSiblingNode             (BTreeControlBlockPtr    btreePtr,
 307                                                                          NodeDescPtr                     node,
 308                                                                          NodeRec                                *right );
 309
 310 #define         GetRightSiblingNode(btree,node,right)           GetNode ((btree), ((NodeDescPtr)(node))->fLink, (right))
 311
 312
 313 OSStatus        GetNewNode                              (BTreeControlBlockPtr    btreePtr,
 314                                                                          UInt32                                  nodeNum,
 315                                                                          NodeRec                                *returnNodePtr );
 316
 317 OSStatus        ReleaseNode                             (BTreeControlBlockPtr    btreePtr,
 318                                                                          NodePtr                                 nodePtr );
 319 OSStatus        TrashNode                               (BTreeControlBlockPtr    btreePtr,
 320                                                                         NodePtr                          nodePtr );
 321
 322 OSStatus        UpdateNode                              (BTreeControlBlockPtr    btreePtr,
 323                                                                          NodePtr                                 nodePtr );
 324
 325 OSStatus        GetMapNode                              (BTreeControlBlockPtr    btreePtr,
 326                                                                          BlockDescriptor                 *nodePtr,
 327                                                                          UInt16                                  **mapPtr,
 328                                                                          UInt16                                  *mapSize );
 329
 330 //// Node Buffer Operations
 331
 332 void            ClearNode                               (BTreeControlBlockPtr    btreePtr,
 333                                                                          NodeDescPtr                     node );
 334
 335 UInt16          GetNodeDataSize                 (BTreeControlBlockPtr    btreePtr,
 336                                                                          NodeDescPtr                     node );
 337
 338 UInt16          GetNodeFreeSize                 (BTreeControlBlockPtr    btreePtr,
 339                                                                          NodeDescPtr                     node );
 340
 341
 342 //// Record Operations
 343
 344 Boolean         InsertRecord                    (BTreeControlBlockPtr    btreePtr,
 345                                                                          NodeDescPtr                     node,
 346                                                                          UInt16                                  index,
 347                                                                          RecordPtr                               recPtr,
 348                                                                          UInt16                                  recSize );
 349
 350 Boolean         InsertKeyRecord                 (BTreeControlBlockPtr    btreePtr,
 351                                                                          NodeDescPtr                     node,
 352                                                                          UInt16                                  index,
 353                                                                          KeyPtr                                  keyPtr,
 354                                                                          UInt16                                  keyLength,
 355                                                                          RecordPtr                               recPtr,
 356                                                                          UInt16                                  recSize );
 357
 358 void            DeleteRecord                    (BTreeControlBlockPtr   btree,
 359                                                                          NodeDescPtr                    node,
 360                                                                          UInt16                                 index );
 361
 362
 363 Boolean         SearchNode                              (BTreeControlBlockPtr    btree,
 364                                                                          NodeDescPtr                     node,
 365                                                                          KeyPtr                                  searchKey,
 366                                                                          UInt16                                 *index );
 367
 368 OSStatus        GetRecordByIndex                (BTreeControlBlockPtr    btree,
 369                                                                          NodeDescPtr                     node,
 370                                                                          UInt16                                  index,
 371                                                                          KeyPtr                                 *keyPtr,
 372                                                                          UInt8 *                                *dataPtr,
 373                                                                          UInt16                                 *dataSize );
 374
 375 UInt8 *         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
 382 UInt16          GetRecordSize                   (BTreeControlBlockPtr    btree,
 383                                                                          NodeDescPtr                     node,
 384                                                                          UInt16                                  index );
 385
 386 UInt32          GetChildNodeNum                 (BTreeControlBlockPtr    btreePtr,
 387                                                                          NodeDescPtr                     nodePtr,
 388                                                                          UInt16                                  index );
 389
 390 void            MoveRecordsLeft                 (UInt8 *                                 src,
 391                                                                          UInt8 *                                 dst,
 392                                                                          UInt16                                  bytesToMove );
 393
 394 #define         MoveRecordsLeft(src,dst,bytes)                  CopyMemory((src),(dst),(bytes))
 395
 396 void            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
 406 OSStatus        SearchTree                              (BTreeControlBlockPtr    btreePtr,
 407                                                                          BTreeKeyPtr                     keyPtr,
 408                                                                          TreePathTable                   treePathTable,
 409                                                                          UInt32                                 *nodeNum,
 410                                                                          BlockDescriptor                *nodePtr,
 411                                                                          UInt16                                 *index );
 412
 413 OSStatus        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
 424 OSStatus        DeleteTree                              (BTreeControlBlockPtr    btreePtr,
 425                                                                          TreePathTable                   treePathTable,
 426                                                                          BlockDescriptor                *targetNode,
 427                                                                          UInt16                                  index,
 428                                                                          UInt16                                  level );
 429
 430 #endif //__BTREEPRIVATE__