bsd/hfs/hfscommon/headers/BTreesPrivate.h

   1 /*
   2  * Copyright (c) 2000-2003 Apple Computer, 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:           BTreesPrivate.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-1999 by Apple Computer, Inc., all rights reserved.
  33
  34         File Ownership:
  35
  36                 DRI:                            Don Brady
  37
  38                 Other Contact:          Mark Day
  39
  40                 Technology:                     File Systems
  41
  42         Writers:
  43
  44                 (msd)   Mark Day
  45                 (DSH)   Deric Horn
  46                 (djb)   Don Brady
  47                 (ser)   Scott Roberts
  48                 (dkh)   Dave Heller
  49
  50         Change History (most recent first):
  51            <MacOSX>      3/19/99        djb             Disable MoveRecordsLeft/Right macros since bcopy is broken.
  52
  53            <MacOSX>      8/10/98        djb             Removed unused BTreeIterator from BTreeControlBlock, fixed alignment.
  54
  55            <CS5>          9/4/97        djb             Convert MoveRecordsLeft and GetLeftSiblingNode to macros.
  56            <CS4>         7/24/97        djb             Add macro for GetRecordAddress (was a function before).
  57            <CS3>         7/21/97        msd             GetRecordByIndex now returns an OSStatus.
  58            <CS2>         7/16/97        DSH             FilesInternal.i renamed FileMgrInternal.i to avoid name
  59                                                                         collision
  60            <CS1>         4/23/97        djb             first checked in
  61
  62           <HFS6>         3/17/97        DSH             Added a refCon field to BTreeControlBlock, for DFA use, to point
  63                                                                         to additional data.  Fixed Panic macros for use with SC.
  64           <HFS5>         2/19/97        djb             Add InsertKey struct. Moved on-disk definitions to
  65                                                                         HFSBTreesPriv.h
  66           <HFS4>         1/27/97        djb             InsertTree and DeleteTree are now recursive and support variable
  67                                                                         sized index keys.
  68           <HFS3>         1/15/97        djb             Move GetFileRefNumFromFCB macro to FilesInternal.h. Added
  69                                                                         kBTVariableIndexKeysMask.
  70           <HFS2>          1/3/97        djb             Added support for large keys.
  71           <HFS1>        12/19/96        djb             first checked in
  72
  73         History applicable to original Scarecrow Design:
  74
  75                  <7>    10/25/96        ser             Changing for new VFPI
  76                  <6>    10/18/96        ser             Converting over VFPI changes
  77                  <5>     9/17/96        dkh             More BTree statistics
  78                  <4>     9/16/96        dkh             Revised BTree statistics
  79                  <3>     6/20/96        dkh             Radar #1358740. Switch from using Pools to debug MemAllocators.
  80                  <2>     12/7/95        dkh             D10E2 build. Changed usage of Ref data type to LogicalAddress.
  81                  <1>    10/18/95        rst             Moved from Scarecrow project.
  82
  83                 <19>    11/22/94        djb             Add prototype for GetMapNode
  84                 <18>    11/16/94        prp             Add IsItAHint routine prototype.
  85                 <17>     9/30/94        prp             Get in sync with D2 interface changes.
  86                 <16>     7/25/94        wjk             Eliminate usage of BytePtr in favor of UInt8 *.
  87                 <15>     7/22/94        wjk             Convert to the new set of header files.
  88                 <14>     5/31/94        srs             Moved Btree types to public interface
  89                 <13>     12/9/93        wjk             Add 68k alignment pragma's around persistent structures.
  90                 <12>    11/30/93        wjk             Move from Makefiles to BuildFiles. Fit into the ModernOS and
  91                                                                         NRCmds environments.
  92                 <11>    11/23/93        wjk             Changes required to compile on the RS6000.
  93                 <10>     8/30/93        CH              Removed the M_ExitOnError and M_ReturnErrorIf macros which were
  94                                                                         already defined in FileSystemPriv.h (included here).
  95                  <9>     8/30/93        CH              Added parens around the M_ReturnErrorIf macro.
  96                  <8>     5/21/93        gs              Add kBadClose flag. Add some prototypes for internal routines.
  97                  <7>     5/10/93        gs              Change Ptr to BytePtr. Move BTreeTypes to BTree.h. Add
  98                                                                         DeleteTree prototype.
  99                  <6>     3/23/93        gs              Remove mysterious "flags" field from HeaderRec structure. Move
 100                                                                         prototypes of private functions to top of respective source
 101                                                                         files.
 102                  <5>      2/8/93        gs              Update to use FSAgent.h Get/Release/SetEOF/SetBlockSize
 103                                                                         procPtrs. Add UpdateNode routine.
 104                  <4>    12/10/92        gs              Add Key Descriptor function declarations.
 105                  <3>     12/8/92        gs              Add HeaderRec structure and incorporate review feedback.
 106                  <2>     12/2/92        gs              Add GetNode and ReleaseNode callback procptrs to BTree CB, and
 107                                                                         add internal function declarations.
 108                  <1>    11/15/92        gs              first checked in
 109
 110 */
 111
 112 #ifndef __BTREESPRIVATE__
 113 #define __BTREESPRIVATE__
 114
 115 #include <sys/appleapiopts.h>
 116
 117 #ifdef KERNEL
 118 #ifdef __APPLE_API_PRIVATE
 119
 120 #include "../../hfs_macos_defs.h"
 121
 122 #ifndef __FILEMGRINTERNAL__
 123 #include "FileMgrInternal.h"
 124 #endif
 125
 126 #ifndef __BTREESINTERNAL__
 127 #include "BTreesInternal.h"
 128 #endif
 129
 130
 131 /////////////////////////////////// Constants ///////////////////////////////////
 132
 133 #define         kBTreeVersion             1
 134 #define         kMaxTreeDepth            16
 135
 136
 137 #define         kHeaderNodeNum            0
 138 #define         kKeyDescRecord            1
 139
 140
 141 // Header Node Record Offsets
 142 enum {
 143         kHeaderRecOffset        =       0x000E,
 144         kKeyDescRecOffset       =       0x0078,
 145         kHeaderMapRecOffset     =       0x00F8
 146 };
 147
 148 #define         kMinNodeSize            512
 149
 150 #define         kMinRecordSize            6
 151                                                                                 // where is minimum record size enforced?
 152
 153 // miscellaneous BTree constants
 154 enum {
 155                         kOffsetSize                             = 2
 156 };
 157
 158 // Insert Operations
 159 typedef enum {
 160                         kInsertRecord                   = 0,
 161                         kReplaceRecord                  = 1
 162 } InsertType;
 163
 164 // illegal string attribute bits set in mask
 165 #define         kBadStrAttribMask               0xCF
 166
 167
 168
 169 //////////////////////////////////// Macros /////////////////////////////////////
 170
 171 #define         M_NodesInMap(mapSize)                           ((mapSize) << 3)
 172
 173 #define         M_ClearBitNum(integer,bitNumber)        ((integer) &= (~(1<<(bitNumber))))
 174 #define         M_SetBitNum(integer,bitNumber)          ((integer) |= (1<<(bitNumber)))
 175 #define         M_IsOdd(integer)                                        (((integer) & 1) != 0)
 176 #define         M_IsEven(integer)                                       (((integer) & 1) == 0)
 177 #define         M_BTreeHeaderDirty(btreePtr)            btreePtr->flags |= kBTHeaderDirty
 178
 179 #define         M_MapRecordSize(nodeSize)                       (nodeSize - sizeof (BTNodeDescriptor) - 6)
 180 #define         M_HeaderMapRecordSize(nodeSize)         (nodeSize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) - 128 - 8)
 181
 182 #define         M_SWAP_BE16_ClearBitNum(integer,bitNumber)  ((integer) &= SWAP_BE16(~(1<<(bitNumber))))
 183 #define         M_SWAP_BE16_SetBitNum(integer,bitNumber)    ((integer) |= SWAP_BE16(1<<(bitNumber)))
 184
 185 ///////////////////////////////////// Types /////////////////////////////////////
 186
 187 typedef struct BTreeControlBlock {                                      // fields specific to BTree CBs
 188
 189         UInt8           keyCompareType;   /* Key string Comparison Type */
 190         UInt8                                            btreeType;
 191         UInt16                                           treeDepth;
 192         FileReference                            fileRefNum;            // refNum of btree file
 193         KeyCompareProcPtr                        keyCompareProc;
 194         UInt32                                           rootNode;
 195         UInt32                                           leafRecords;
 196         UInt32                                           firstLeafNode;
 197         UInt32                                           lastLeafNode;
 198         UInt16                                           nodeSize;
 199         UInt16                                           maxKeyLength;
 200         UInt32                                           totalNodes;
 201         UInt32                                           freeNodes;
 202
 203         UInt16                                           reserved3;                     // 4-byte alignment
 204
 205         // new fields
 206         SInt16                                           version;
 207         UInt32                                           flags;                         // dynamic flags
 208         UInt32                                           attributes;            // persistent flags
 209         UInt32                                           writeCount;
 210         UInt32                                           lastfsync;             /* Last time that this was fsynced  */
 211
 212         GetBlockProcPtr                          getBlockProc;
 213         ReleaseBlockProcPtr                      releaseBlockProc;
 214         SetEndOfForkProcPtr                      setEndOfForkProc;
 215
 216         // statistical information
 217         UInt32                                           numGetNodes;
 218         UInt32                                           numGetNewNodes;
 219         UInt32                                           numReleaseNodes;
 220         UInt32                                           numUpdateNodes;
 221         UInt32                                           numMapNodesRead;       // map nodes beyond header node
 222         UInt32                                           numHintChecks;
 223         UInt32                                           numPossibleHints;      // Looks like a formated hint
 224         UInt32                                           numValidHints;         // Hint used to find correct record.
 225         UInt32                                  reservedNodes;
 226 } BTreeControlBlock, *BTreeControlBlockPtr;
 227
 228
 229 UInt32 CalcKeySize(const BTreeControlBlock *btcb, const BTreeKey *key);
 230 #define CalcKeySize(btcb, key)                  ( ((btcb)->attributes & kBTBigKeysMask) ? ((key)->length16 + 2) : ((key)->length8 + 1) )
 231
 232 UInt32 KeyLength(const BTreeControlBlock *btcb, const BTreeKey *key);
 233 #define KeyLength(btcb, key)                    ( ((btcb)->attributes & kBTBigKeysMask) ? (key)->length16 : (key)->length8 )
 234
 235
 236
 237 typedef enum {
 238                                         kBTHeaderDirty  = 0x00000001
 239 }       BTreeFlags;
 240
 241
 242 typedef SInt8                           *NodeBuffer;
 243 typedef BlockDescriptor          NodeRec, *NodePtr;             //\80\80 remove this someday...
 244
 245
 246
 247
 248 //// Tree Path Table - constructed by SearchTree, used by InsertTree and DeleteTree
 249
 250 typedef struct {
 251         UInt32                          node;                           // node number
 252         UInt16                          index;
 253         UInt16                          reserved;                       // align size to a power of 2
 254 } TreePathRecord, *TreePathRecordPtr;
 255
 256 typedef TreePathRecord          TreePathTable [kMaxTreeDepth];
 257
 258
 259 //// InsertKey - used by InsertTree, InsertLevel and InsertNode
 260
 261 struct InsertKey {
 262         BTreeKeyPtr             keyPtr;
 263         UInt8 *                 recPtr;
 264         UInt16                  keyLength;
 265         UInt16                  recSize;
 266         Boolean                 replacingKey;
 267         Boolean                 skipRotate;
 268 };
 269
 270 typedef struct InsertKey InsertKey;
 271
 272
 273 //// For Notational Convenience
 274
 275 typedef BTNodeDescriptor*        NodeDescPtr;
 276 typedef UInt8                           *RecordPtr;
 277 typedef BTreeKeyPtr                      KeyPtr;
 278
 279
 280 //////////////////////////////////// Globals ////////////////////////////////////
 281
 282
 283 //////////////////////////////////// Macros /////////////////////////////////////
 284
 285 #if DEBUG_BUILD
 286         #define Panic( message )                                        DebugStr( (ConstStr255Param) message )
 287         #define PanicIf( condition, message )           if ( condition != 0 )   DebugStr( message )
 288 #else
 289         #define Panic( message )
 290         #define PanicIf( condition, message )
 291 #endif
 292
 293 //      Exit function on error
 294 #define M_ExitOnError( result ) if ( ( result ) != noErr )      goto ErrorExit; else ;
 295
 296 //      Test for passed condition and return if true
 297 #define M_ReturnErrorIf( condition, error )     if ( condition )        return( error )
 298
 299 //////////////////////////////// Key Operations /////////////////////////////////
 300
 301 SInt32          CompareKeys                             (BTreeControlBlockPtr    btreePtr,
 302                                                                          KeyPtr                                  searchKey,
 303                                                                          KeyPtr                                  trialKey );
 304
 305 //////////////////////////////// Map Operations /////////////////////////////////
 306
 307 OSStatus        AllocateNode                    (BTreeControlBlockPtr    btreePtr,
 308                                                                          UInt32                                 *nodeNum);
 309
 310 OSStatus        FreeNode                                (BTreeControlBlockPtr    btreePtr,
 311                                                                          UInt32                                  nodeNum);
 312
 313 OSStatus        ExtendBTree                             (BTreeControlBlockPtr    btreePtr,
 314                                                                          UInt32                                  nodes );
 315
 316 UInt32          CalcMapBits                             (BTreeControlBlockPtr    btreePtr);
 317
 318 SInt32          BTAvailableNodes                        (BTreeControlBlock *btree);
 319
 320 void            BTUpdateReserve                         (BTreeControlBlockPtr btreePtr,
 321                                                          int nodes);
 322
 323 //////////////////////////////// Misc Operations ////////////////////////////////
 324
 325 UInt16          CalcKeyRecordSize               (UInt16                                  keySize,
 326                                                                          UInt16                                  recSize );
 327
 328 OSStatus        VerifyHeader                    (FCB                                    *filePtr,
 329                                                                          BTHeaderRec                            *header );
 330
 331 OSStatus        UpdateHeader                    (BTreeControlBlockPtr    btreePtr,
 332                                                  Boolean forceWrite );
 333
 334 OSStatus        FindIteratorPosition    (BTreeControlBlockPtr    btreePtr,
 335                                                                          BTreeIteratorPtr                iterator,
 336                                                                          BlockDescriptor                *left,
 337                                                                          BlockDescriptor                *middle,
 338                                                                          BlockDescriptor                *right,
 339                                                                          UInt32                                 *nodeNum,
 340                                                                          UInt16                                 *index,
 341                                                                          Boolean                                *foundRecord );
 342
 343 OSStatus        CheckInsertParams               (FCB                                    *filePtr,
 344                                                                          BTreeIterator                  *iterator,
 345                                                                          FSBufferDescriptor             *record,
 346                                                                          UInt16                                  recordLen );
 347
 348 OSStatus        TrySimpleReplace                (BTreeControlBlockPtr    btreePtr,
 349                                                                          NodeDescPtr                     nodePtr,
 350                                                                          BTreeIterator                  *iterator,
 351                                                                          FSBufferDescriptor             *record,
 352                                                                          UInt16                                  recordLen,
 353                                                                          Boolean                                *recordInserted );
 354
 355 OSStatus        IsItAHint                               (BTreeControlBlockPtr    btreePtr,
 356                                                                          BTreeIterator                  *iterator,
 357                                                                          Boolean                                *answer );
 358
 359 //////////////////////////////// Node Operations ////////////////////////////////
 360
 361 //// Node Operations
 362
 363 OSStatus        GetNode                                 (BTreeControlBlockPtr    btreePtr,
 364                                                                          UInt32                                  nodeNum,
 365                                                                          NodeRec                                *returnNodePtr );
 366
 367 OSStatus        GetLeftSiblingNode              (BTreeControlBlockPtr    btreePtr,
 368                                                                          NodeDescPtr                     node,
 369                                                                          NodeRec                                *left );
 370
 371 #define         GetLeftSiblingNode(btree,node,left)                     GetNode ((btree), ((NodeDescPtr)(node))->bLink, (left))
 372
 373 OSStatus        GetRightSiblingNode             (BTreeControlBlockPtr    btreePtr,
 374                                                                          NodeDescPtr                     node,
 375                                                                          NodeRec                                *right );
 376
 377 #define         GetRightSiblingNode(btree,node,right)           GetNode ((btree), ((NodeDescPtr)(node))->fLink, (right))
 378
 379
 380 OSStatus        GetNewNode                              (BTreeControlBlockPtr    btreePtr,
 381                                                                          UInt32                                  nodeNum,
 382                                                                          NodeRec                                *returnNodePtr );
 383
 384 OSStatus        ReleaseNode                             (BTreeControlBlockPtr    btreePtr,
 385                                                                          NodePtr                                 nodePtr );
 386
 387 OSStatus        TrashNode                               (BTreeControlBlockPtr    btreePtr,
 388                                                                          NodePtr                                 nodePtr );
 389
 390 // XXXdbg
 391 void ModifyBlockStart(FileReference vp, BlockDescPtr blockPtr);
 392 // XXXdbg
 393
 394 OSStatus        UpdateNode                              (BTreeControlBlockPtr    btreePtr,
 395                                                                          NodePtr                                 nodePtr,
 396                                                                          UInt32                                  transactionID,
 397                                                                          UInt32                                  flags );
 398
 399 OSStatus        GetMapNode                              (BTreeControlBlockPtr    btreePtr,
 400                                                                          BlockDescriptor                 *nodePtr,
 401                                                                          UInt16                                  **mapPtr,
 402                                                                          UInt16                                  *mapSize );
 403
 404 //// Node Buffer Operations
 405
 406 void            ClearNode                               (BTreeControlBlockPtr    btreePtr,
 407                                                                          NodeDescPtr                     node );
 408
 409 UInt16          GetNodeDataSize                 (BTreeControlBlockPtr    btreePtr,
 410                                                                          NodeDescPtr                     node );
 411
 412 UInt16          GetNodeFreeSize                 (BTreeControlBlockPtr    btreePtr,
 413                                                                          NodeDescPtr                     node );
 414
 415
 416 //// Record Operations
 417
 418 Boolean         InsertRecord                    (BTreeControlBlockPtr    btreePtr,
 419                                                                          NodeDescPtr                     node,
 420                                                                          UInt16                                  index,
 421                                                                          RecordPtr                               recPtr,
 422                                                                          UInt16                                  recSize );
 423
 424 Boolean         InsertKeyRecord                 (BTreeControlBlockPtr    btreePtr,
 425                                                                          NodeDescPtr                     node,
 426                                                                          UInt16                                  index,
 427                                                                          KeyPtr                                  keyPtr,
 428                                                                          UInt16                                  keyLength,
 429                                                                          RecordPtr                               recPtr,
 430                                                                          UInt16                                  recSize );
 431
 432 void            DeleteRecord                    (BTreeControlBlockPtr   btree,
 433                                                                          NodeDescPtr                    node,
 434                                                                          UInt16                                 index );
 435
 436
 437 Boolean         SearchNode                              (BTreeControlBlockPtr    btree,
 438                                                                          NodeDescPtr                     node,
 439                                                                          KeyPtr                                  searchKey,
 440                                                                          UInt16                                 *index );
 441
 442 OSStatus        GetRecordByIndex                (BTreeControlBlockPtr    btree,
 443                                                                          NodeDescPtr                     node,
 444                                                                          UInt16                                  index,
 445                                                                          KeyPtr                                 *keyPtr,
 446                                                                          UInt8 *                                *dataPtr,
 447                                                                          UInt16                                 *dataSize );
 448
 449 UInt8 *         GetRecordAddress                (BTreeControlBlockPtr    btree,
 450                                                                          NodeDescPtr                     node,
 451                                                                          UInt16                                  index );
 452
 453 #define GetRecordAddress(btreePtr,node,index)           ((UInt8 *)(node) + (*(short *) ((UInt8 *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize)))
 454
 455
 456 UInt16          GetRecordSize                   (BTreeControlBlockPtr    btree,
 457                                                                          NodeDescPtr                     node,
 458                                                                          UInt16                                  index );
 459
 460 UInt32          GetChildNodeNum                 (BTreeControlBlockPtr    btreePtr,
 461                                                                          NodeDescPtr                     nodePtr,
 462                                                                          UInt16                                  index );
 463
 464 void            MoveRecordsLeft                 (UInt8 *                                 src,
 465                                                                          UInt8 *                                 dst,
 466                                                                          UInt16                                  bytesToMove );
 467
 468 #define         MoveRecordsLeft(src,dst,bytes)                  bcopy((src),(dst),(bytes))
 469
 470 void            MoveRecordsRight                (UInt8 *                                 src,
 471                                                                          UInt8 *                                 dst,
 472                                                                          UInt16                                  bytesToMove );
 473
 474 #define         MoveRecordsRight(src,dst,bytes)                 bcopy((src),(dst),(bytes))
 475
 476
 477 //////////////////////////////// Tree Operations ////////////////////////////////
 478
 479 OSStatus        SearchTree                              (BTreeControlBlockPtr    btreePtr,
 480                                                                          BTreeKeyPtr                     keyPtr,
 481                                                                          TreePathTable                   treePathTable,
 482                                                                          UInt32                                 *nodeNum,
 483                                                                          BlockDescriptor                *nodePtr,
 484                                                                          UInt16                                 *index );
 485
 486 OSStatus        InsertTree                              (BTreeControlBlockPtr    btreePtr,
 487                                                                          TreePathTable                   treePathTable,
 488                                                                          KeyPtr                                  keyPtr,
 489                                                                          UInt8 *                                 recPtr,
 490                                                                          UInt16                                  recSize,
 491                                                                          BlockDescriptor                *targetNode,
 492                                                                          UInt16                                  index,
 493                                                                          UInt16                                  level,
 494                                                                          Boolean                                 replacingKey,
 495                                                                          UInt32                                 *insertNode );
 496
 497 OSStatus        DeleteTree                              (BTreeControlBlockPtr    btreePtr,
 498                                                                          TreePathTable                   treePathTable,
 499                                                                          BlockDescriptor                *targetNode,
 500                                                                          UInt16                                  index,
 501                                                                          UInt16                                  level );
 502
 503 #endif /* __APPLE_API_PRIVATE */
 504 #endif /* KERNEL */
 505 #endif //__BTREESPRIVATE__