livefiles_hfs_plugin/lf_hfs_btree.h

   1 //
   2 //  lf_hfs_btree.h
   3 //  livefiles_hfs
   4 //
   5 //  Created by Yakov Ben Zaken on 20/03/2018.
   6 //
   7
   8 #ifndef lf_hfs_btree_h
   9 #define lf_hfs_btree_h
  10
  11
  12 #include "lf_hfs_file_mgr_internal.h"
  13 #include "lf_hfs_btrees_internal.h"
  14
  15
  16 /////////////////////////////////// Constants ///////////////////////////////////
  17
  18 #define        kBTreeVersion          1
  19 #define        kMaxTreeDepth         16
  20
  21
  22 #define        kHeaderNodeNum          0
  23 #define        kKeyDescRecord          1
  24
  25
  26 // Header Node Record Offsets
  27 enum {
  28     kHeaderRecOffset    =    0x000E,
  29     kKeyDescRecOffset    =    0x0078,
  30     kHeaderMapRecOffset    =    0x00F8
  31 };
  32
  33 #define        kMinNodeSize        512
  34
  35 #define        kMinRecordSize          6
  36 // where is minimum record size enforced?
  37
  38 // miscellaneous BTree constants
  39 enum {
  40     kOffsetSize                = 2
  41 };
  42
  43 // Insert Operations
  44 typedef enum {
  45     kInsertRecord            = 0,
  46     kReplaceRecord            = 1
  47 } InsertType;
  48
  49 // illegal string attribute bits set in mask
  50 #define        kBadStrAttribMask        0xCF
  51
  52
  53
  54 //////////////////////////////////// Macros /////////////////////////////////////
  55
  56 #define        M_NodesInMap(mapSize)                ((mapSize) << 3)
  57
  58 #define        M_ClearBitNum(integer,bitNumber)     ((integer) &= (~(1<<(bitNumber))))
  59 #define        M_SetBitNum(integer,bitNumber)         ((integer) |= (1<<(bitNumber)))
  60 #define        M_IsOdd(integer)                     (((integer) & 1) != 0)
  61 #define        M_IsEven(integer)                     (((integer) & 1) == 0)
  62
  63 #define        M_MapRecordSize(nodeSize)            (nodeSize - sizeof (BTNodeDescriptor) - 6)
  64 #define        M_HeaderMapRecordSize(nodeSize)        (nodeSize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) - 128 - 8)
  65
  66 #define        M_SWAP_BE16_ClearBitNum(integer,bitNumber)  ((integer) &= SWAP_BE16(~(1<<(bitNumber))))
  67 #define        M_SWAP_BE16_SetBitNum(integer,bitNumber)    ((integer) |= SWAP_BE16(1<<(bitNumber)))
  68
  69 ///////////////////////////////////// Types /////////////////////////////////////
  70
  71 typedef struct BTreeControlBlock {                    // fields specific to BTree CBs
  72
  73     u_int8_t        keyCompareType;   /* Key string Comparison Type */
  74     u_int8_t                     btreeType;
  75     u_int16_t                     treeDepth;
  76     FileReference                 fileRefNum;        // refNum of btree file
  77     KeyCompareProcPtr             keyCompareProc;
  78     u_int32_t                     rootNode;
  79     u_int32_t                     leafRecords;
  80     u_int32_t                     firstLeafNode;
  81     u_int32_t                     lastLeafNode;
  82     u_int16_t                     nodeSize;
  83     u_int16_t                     maxKeyLength;
  84     u_int32_t                     totalNodes;
  85     u_int32_t                     freeNodes;
  86
  87     u_int16_t                     reserved3;            // 4-byte alignment
  88
  89     // new fields
  90     int16_t                         version;
  91     u_int32_t                     flags;                // dynamic flags
  92     u_int32_t                     attributes;        // persistent flags
  93     u_int32_t                     writeCount;
  94     u_int32_t                     lastfsync;        /* Last time that this was fsynced  */
  95
  96     GetBlockProcPtr                  getBlockProc;
  97     ReleaseBlockProcPtr             releaseBlockProc;
  98     SetEndOfForkProcPtr             setEndOfForkProc;
  99
 100     // statistical information
 101     u_int32_t                     numGetNodes;
 102     u_int32_t                     numGetNewNodes;
 103     u_int32_t                     numReleaseNodes;
 104     u_int32_t                     numUpdateNodes;
 105     u_int32_t                     numMapNodesRead;    // map nodes beyond header node
 106     u_int32_t                     numHintChecks;
 107     u_int32_t                     numPossibleHints;    // Looks like a formated hint
 108     u_int32_t                     numValidHints;        // Hint used to find correct record.
 109     u_int32_t                    reservedNodes;
 110     BTreeIterator   iterator; // useable when holding exclusive b-tree lock
 111
 112 #if DEBUG
 113     void                        *madeDirtyBy[2];
 114 #endif
 115 } BTreeControlBlock, *BTreeControlBlockPtr;
 116
 117 u_int32_t CalcKeySize(const BTreeControlBlock *btcb, const BTreeKey *key);
 118 #define CalcKeySize(btcb, key)            ( ((btcb)->attributes & kBTBigKeysMask) ? ((key)->length16 + 2) : ((key)->length8 + 1) )
 119
 120 u_int32_t KeyLength(const BTreeControlBlock *btcb, const BTreeKey *key);
 121 #define KeyLength(btcb, key)            ( ((btcb)->attributes & kBTBigKeysMask) ? (key)->length16 : (key)->length8 )
 122
 123
 124
 125 typedef enum {
 126     kBTHeaderDirty    = 0x00000001
 127 }    BTreeFlags;
 128
 129 static inline void M_BTreeHeaderDirty(BTreeControlBlock *bt) {
 130 #if DEBUG
 131     bt->madeDirtyBy[0] = __builtin_return_address(0);
 132     bt->madeDirtyBy[1] = __builtin_return_address(1);
 133 #endif
 134     bt->flags |= kBTHeaderDirty;
 135 }
 136
 137 typedef    int8_t                *NodeBuffer;
 138 typedef BlockDescriptor         NodeRec, *NodePtr;        //remove this someday...
 139
 140
 141
 142
 143 //// Tree Path Table - constructed by SearchTree, used by InsertTree and DeleteTree
 144
 145 typedef struct {
 146     u_int32_t                node;                // node number
 147     u_int16_t                index;
 148     u_int16_t                reserved;            // align size to a power of 2
 149 } TreePathRecord, *TreePathRecordPtr;
 150
 151 typedef TreePathRecord        TreePathTable [kMaxTreeDepth];
 152
 153
 154 //// InsertKey - used by InsertTree, InsertLevel and InsertNode
 155
 156 struct InsertKey {
 157     BTreeKeyPtr        keyPtr;
 158     u_int8_t *        recPtr;
 159     u_int16_t        keyLength;
 160     u_int16_t        recSize;
 161     Boolean            replacingKey;
 162     Boolean            skipRotate;
 163 };
 164
 165 typedef struct InsertKey InsertKey;
 166
 167
 168 //// For Notational Convenience
 169
 170 typedef    BTNodeDescriptor*     NodeDescPtr;
 171 typedef u_int8_t            *RecordPtr;
 172 typedef BTreeKeyPtr             KeyPtr;
 173
 174
 175 //////////////////////////////////// Globals ////////////////////////////////////
 176
 177
 178 //////////////////////////////////// Macros /////////////////////////////////////
 179 //    Exit function on error
 180 #define M_ExitOnError( result )    do { if ( ( result ) != noErr )    goto ErrorExit; } while(0)
 181
 182 //    Test for passed condition and return if true
 183 #define    M_ReturnErrorIf( condition, error )    do { if ( condition )    return( error ); } while(0)
 184
 185 //////////////////////////////// Key Operations /////////////////////////////////
 186
 187 int32_t        CompareKeys                (BTreeControlBlockPtr     btreePtr,
 188                                            KeyPtr                     searchKey,
 189                                            KeyPtr                     trialKey );
 190
 191 //////////////////////////////// Map Operations /////////////////////////////////
 192
 193 OSStatus    AllocateNode            (BTreeControlBlockPtr     btreePtr,
 194                                      u_int32_t                *nodeNum);
 195
 196 OSStatus    FreeNode                (BTreeControlBlockPtr     btreePtr,
 197                                      u_int32_t                 nodeNum);
 198
 199 OSStatus    ExtendBTree                (BTreeControlBlockPtr     btreePtr,
 200                                         u_int32_t                 nodes );
 201
 202 u_int32_t    CalcMapBits                (BTreeControlBlockPtr     btreePtr);
 203
 204
 205 void         BTUpdateReserve                (BTreeControlBlockPtr btreePtr,
 206                                              int nodes);
 207
 208 //////////////////////////////// Misc Operations ////////////////////////////////
 209
 210 u_int16_t    CalcKeyRecordSize        (u_int16_t                 keySize,
 211                                        u_int16_t                 recSize );
 212
 213 OSStatus    VerifyHeader            (FCB                    *filePtr,
 214                                      BTHeaderRec                *header );
 215
 216 OSStatus    UpdateHeader            (BTreeControlBlockPtr     btreePtr,
 217                                      Boolean forceWrite );
 218
 219 OSStatus    FindIteratorPosition    (BTreeControlBlockPtr     btreePtr,
 220                                      BTreeIteratorPtr         iterator,
 221                                      BlockDescriptor        *left,
 222                                      BlockDescriptor        *middle,
 223                                      BlockDescriptor        *right,
 224                                      u_int32_t                *nodeNum,
 225                                      u_int16_t                *index,
 226                                      Boolean                *foundRecord );
 227
 228 OSStatus    CheckInsertParams        (FCB                    *filePtr,
 229                                       BTreeIterator            *iterator,
 230                                       FSBufferDescriptor        *record,
 231                                       u_int16_t                 recordLen );
 232
 233 OSStatus    TrySimpleReplace        (BTreeControlBlockPtr     btreePtr,
 234                                      NodeDescPtr             nodePtr,
 235                                      BTreeIterator            *iterator,
 236                                      FSBufferDescriptor        *record,
 237                                      u_int16_t                 recordLen,
 238                                      Boolean                *recordInserted );
 239
 240 OSStatus    IsItAHint                (BTreeControlBlockPtr      btreePtr,
 241                                       BTreeIterator             *iterator,
 242                                       Boolean                 *answer );
 243
 244 extern OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr);
 245
 246 //////////////////////////////// Node Operations ////////////////////////////////
 247
 248 //// Node Operations
 249
 250 OSStatus    GetNode                    (BTreeControlBlockPtr     btreePtr,
 251                                         u_int32_t                 nodeNum,
 252                                         u_int32_t                  flags,
 253                                         NodeRec                *returnNodePtr );
 254
 255 /* Flags for GetNode() */
 256 #define        kGetNodeHint    0x1        /* If set, the node is being looked up using a hint */
 257
 258 OSStatus    GetLeftSiblingNode        (BTreeControlBlockPtr     btreePtr,
 259                                        NodeDescPtr             node,
 260                                        NodeRec                *left );
 261
 262 #define        GetLeftSiblingNode(btree,node,left)            GetNode ((btree), ((NodeDescPtr)(node))->bLink, 0, (left))
 263
 264 OSStatus    GetRightSiblingNode        (BTreeControlBlockPtr     btreePtr,
 265                                         NodeDescPtr             node,
 266                                         NodeRec                *right );
 267
 268 #define        GetRightSiblingNode(btree,node,right)        GetNode ((btree), ((NodeDescPtr)(node))->fLink, 0, (right))
 269
 270
 271 OSStatus    GetNewNode                (BTreeControlBlockPtr     btreePtr,
 272                                        u_int32_t                 nodeNum,
 273                                        NodeRec                *returnNodePtr );
 274
 275 OSStatus    ReleaseNode                (BTreeControlBlockPtr     btreePtr,
 276                                         NodePtr                 nodePtr );
 277
 278 OSStatus    TrashNode                (BTreeControlBlockPtr     btreePtr,
 279                                       NodePtr                 nodePtr );
 280
 281 OSStatus    UpdateNode                (BTreeControlBlockPtr     btreePtr,
 282                                        NodePtr                 nodePtr,
 283                                        u_int32_t                 transactionID,
 284                                        u_int32_t                 flags );
 285
 286 //// Node Buffer Operations
 287
 288 void        ClearNode                (BTreeControlBlockPtr     btreePtr,
 289                                       NodeDescPtr             node );
 290
 291 u_int16_t    GetNodeDataSize            (BTreeControlBlockPtr     btreePtr,
 292                                          NodeDescPtr             node );
 293
 294 u_int16_t    GetNodeFreeSize            (BTreeControlBlockPtr     btreePtr,
 295                                          NodeDescPtr             node );
 296
 297
 298 //// Record Operations
 299
 300 Boolean        InsertRecord            (BTreeControlBlockPtr     btreePtr,
 301                                         NodeDescPtr              node,
 302                                         u_int16_t                  index,
 303                                         RecordPtr                 recPtr,
 304                                         u_int16_t                 recSize );
 305
 306 Boolean        InsertKeyRecord            (BTreeControlBlockPtr     btreePtr,
 307                                            NodeDescPtr              node,
 308                                            u_int16_t                  index,
 309                                            KeyPtr                     keyPtr,
 310                                            u_int16_t                 keyLength,
 311                                            RecordPtr                 recPtr,
 312                                            u_int16_t                 recSize );
 313
 314 void        DeleteRecord            (BTreeControlBlockPtr    btree,
 315                                      NodeDescPtr             node,
 316                                      u_int16_t                 index );
 317
 318
 319 Boolean        SearchNode                (BTreeControlBlockPtr     btree,
 320                                           NodeDescPtr             node,
 321                                           KeyPtr                     searchKey,
 322                                           u_int16_t                *index );
 323
 324 OSStatus    GetRecordByIndex        (BTreeControlBlockPtr     btree,
 325                                      NodeDescPtr             node,
 326                                      u_int16_t                 index,
 327                                      KeyPtr                    *keyPtr,
 328                                      u_int8_t *                *dataPtr,
 329                                      u_int16_t                *dataSize );
 330
 331 u_int8_t *    GetRecordAddress        (BTreeControlBlockPtr     btree,
 332                                        NodeDescPtr             node,
 333                                        u_int16_t                 index );
 334
 335 #define GetRecordAddress(btreePtr,node,index)        ((u_int8_t *)(node) + (*(short *) ((u_int8_t *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize)))
 336
 337
 338 u_int16_t    GetRecordSize            (BTreeControlBlockPtr     btree,
 339                                        NodeDescPtr             node,
 340                                        u_int16_t                 index );
 341
 342 u_int32_t    GetChildNodeNum            (BTreeControlBlockPtr     btreePtr,
 343                                          NodeDescPtr             nodePtr,
 344                                          u_int16_t                 index );
 345
 346 void        MoveRecordsLeft            (u_int8_t *                 src,
 347                                         u_int8_t *                 dst,
 348                                         u_int16_t                 bytesToMove );
 349
 350 #define        MoveRecordsLeft(src,dst,bytes)            bcopy((src),(dst),(bytes))
 351
 352 void        MoveRecordsRight        (u_int8_t *                 src,
 353                                      u_int8_t *                 dst,
 354                                      u_int16_t                 bytesToMove );
 355
 356 #define        MoveRecordsRight(src,dst,bytes)            bcopy((src),(dst),(bytes))
 357
 358
 359 //////////////////////////////// Tree Operations ////////////////////////////////
 360
 361 OSStatus    SearchTree                (BTreeControlBlockPtr     btreePtr,
 362                                        BTreeKeyPtr             keyPtr,
 363                                        TreePathTable             treePathTable,
 364                                        u_int32_t                *nodeNum,
 365                                        BlockDescriptor        *nodePtr,
 366                                        u_int16_t                *index );
 367
 368 OSStatus    InsertTree                (BTreeControlBlockPtr     btreePtr,
 369                                        TreePathTable             treePathTable,
 370                                        KeyPtr                     keyPtr,
 371                                        u_int8_t *                 recPtr,
 372                                        u_int16_t                 recSize,
 373                                        BlockDescriptor        *targetNode,
 374                                        u_int16_t                 index,
 375                                        u_int16_t                 level,
 376                                        Boolean                 replacingKey,
 377                                        u_int32_t                *insertNode );
 378
 379 OSStatus    DeleteTree                (BTreeControlBlockPtr     btreePtr,
 380                                        TreePathTable             treePathTable,
 381                                        BlockDescriptor        *targetNode,
 382                                        u_int16_t                 index,
 383                                        u_int16_t                 level );
 384
 385 OSStatus    BTFlushPath               (FCB                    *filePtr);
 386
 387 OSStatus    BTSetLastSync             (FCB                    *filePtr,
 388                                        u_int32_t                lastsync);
 389 #endif /* lf_hfs_btree_h */