fsck_hfs/dfalib/BTree.h

   1 /*
   2  * Copyright (c) 1999 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:           BTreesInternal.h
  25
  26         Contains:       IPI to File Manager B-tree
  27
  28         Version:        HFS Plus 1.0
  29
  30         Copyright:      © 1996-1998 by Apple Computer, Inc., all rights reserved.
  31 */
  32
  33 #ifndef __BTREESINTERNAL__
  34 #define __BTREESINTERNAL__
  35
  36 #include "SRuntime.h"
  37
  38 //
  39 // internal error codes
  40 //
  41 enum {
  42         // FXM errors
  43
  44         fxRangeErr                              = 16,           // file position beyond mapped range
  45         fxOvFlErr                               = 17,           // extents file overflow
  46
  47         // Unicode errors
  48
  49         uniTooLongErr                   = 24,           // Unicode string too long to convert to Str31
  50         uniBufferTooSmallErr    = 25,           // Unicode output buffer too small
  51         uniNotMappableErr               = 26,           // Unicode string can't be mapped to given script
  52
  53         // BTree Manager errors
  54
  55         btNotFound                              = 32,           // record not found
  56         btExists                                = 33,           // record already exists
  57         btNoSpaceAvail                  = 34,           // no available space
  58         btNoFit                                 = 35,           // record doesn't fit in node
  59         btBadNode                               = 36,           // bad node detected
  60         btBadHdr                                = 37,           // bad BTree header record detected
  61         dsBadRotate                     = 64,           // bad BTree rotate
  62
  63         // Catalog Manager errors
  64
  65         cmNotFound                              = 48,           // CNode not found
  66         cmExists                                = 49,           // CNode already exists
  67         cmNotEmpty                              = 50,           // directory CNode not empty (valence = 0)
  68         cmRootCN                                = 51,           // invalid reference to root CNode
  69         cmBadNews                               = 52,           // detected bad catalog structure
  70         cmFThdDirErr                    = 53,           // thread belongs to a directory not a file
  71         cmFThdGone                              = 54,           // file thread doesn't exist
  72         cmParentNotFound                = 55,           // CNode for parent ID does not exist
  73         cmNotAFolder                    = 56,           // Destination of move is a file, not a folder
  74         cmUnknownNodeType               = 57,           // Node type isn't recognized
  75
  76         // Volume Check errors
  77
  78         vcInvalidExtentErr              = 60            // Extent record is out of bounds
  79 };
  80
  81 enum {
  82         fsBTInvalidHeaderErr                    = btBadHdr,
  83         fsBTBadRotateErr                                = dsBadRotate,
  84         fsBTInvalidNodeErr                              = btBadNode,
  85         fsBTRecordTooLargeErr                   = btNoFit,
  86         fsBTRecordNotFoundErr                   = btNotFound,
  87         fsBTDuplicateRecordErr                  = btExists,
  88         fsBTFullErr                                             = btNoSpaceAvail,
  89
  90         fsBTInvalidFileErr                              = 0x0302,                                       /* no BTreeCB has been allocated for fork*/
  91         fsBTrFileAlreadyOpenErr                 = 0x0303,
  92         fsBTInvalidIteratorErr                  = 0x0308,
  93         fsBTEmptyErr                                    = 0x030A,
  94         fsBTNoMoreMapNodesErr                   = 0x030B,
  95         fsBTBadNodeSize                                 = 0x030C,
  96         fsBTBadNodeType                                 = 0x030D,
  97         fsBTInvalidKeyLengthErr                 = 0x030E,
  98         fsBTInvalidKeyDescriptor                = 0x030F,
  99         fsBTStartOfIterationErr                 = 0x0353,
 100         fsBTEndOfIterationErr                   = 0x0354,
 101         fsBTUnknownVersionErr                   = 0x0355,
 102         fsBTTreeTooDeepErr                              = 0x0357,
 103         fsBTInvalidKeyDescriptorErr             = 0x0358,
 104         fsBTInvalidKeyFieldErr                  = 0x035E,
 105         fsBTInvalidKeyAttributeErr              = 0x035F,
 106         fsIteratorExitedScopeErr                = 0x0A02,                       /* iterator exited the scope*/
 107         fsIteratorScopeExceptionErr             = 0x0A03,                       /* iterator is undefined due to error or movement of scope locality*/
 108         fsUnknownIteratorMovementErr    = 0x0A04,                       /* iterator movement is not defined*/
 109         fsInvalidIterationMovmentErr    = 0x0A05,                       /* iterator movement is invalid in current context*/
 110         fsClientIDMismatchErr                   = 0x0A06,                       /* wrong client process ID*/
 111         fsEndOfIterationErr                             = 0x0A07,                       /* there were no objects left to return on iteration*/
 112         fsBTTimeOutErr                                  = 0x0A08                        /* BTree scan interrupted -- no time left for physical I/O */
 113 };
 114
 115
 116 struct FSBufferDescriptor {
 117         LogicalAddress                                  bufferAddress;
 118         ByteCount                                               itemSize;
 119         ItemCount                                               itemCount;
 120 };
 121 typedef struct FSBufferDescriptor FSBufferDescriptor;
 122
 123 typedef FSBufferDescriptor *FSBufferDescriptorPtr;
 124
 125
 126
 127 typedef UInt64  FSSize;
 128 typedef UInt32  ForkBlockNumber;
 129
 130
 131 /*
 132         BTreeObjID is used to indicate an access path using the
 133         BTree access method to a specific fork of a file. This value
 134         is session relative and not persistent between invocations of
 135         an application. It is in fact an object ID to which requests
 136         for the given path should be sent.
 137  */
 138 typedef UInt32 BTreeObjID;
 139
 140 /*
 141         B*Tree Information Version
 142 */
 143
 144 enum BTreeInformationVersion{
 145         kBTreeInfoVersion       = 0
 146 };
 147
 148 /*
 149         B*Tree Iteration Operation Constants
 150 */
 151
 152 enum BTreeIterationOperations{
 153         kBTreeFirstRecord,
 154         kBTreeNextRecord,
 155         kBTreePrevRecord,
 156         kBTreeLastRecord,
 157         kBTreeCurrentRecord
 158 };
 159 typedef UInt16 BTreeIterationOperation;
 160
 161 /*
 162         B*Tree Key Descriptor Limits
 163 */
 164
 165 enum {
 166         kMaxKeyDescriptorLength         = 23,
 167 };
 168
 169 /*
 170         B*Tree Key Descriptor Field Types
 171 */
 172
 173 enum {
 174         kBTreeSkip                              =  0,
 175         kBTreeByte                              =  1,
 176         kBTreeSignedByte                =  2,
 177         kBTreeWord                              =  4,
 178         kBTreeSignedWord                =  5,
 179         kBTreeLong                              =  6,
 180         kBTreeSignedLong                =  7,
 181         kBTreeString                    =  3,           // Pascal string
 182         kBTreeFixLenString              =  8,           // Pascal string w/ fixed length buffer
 183         kBTreeReserved                  =  9,           // reserved for Desktop Manager (?)
 184         kBTreeUseKeyCmpProc             = 10,
 185         //¥¥ not implemented yet...
 186         kBTreeCString                   = 11,
 187         kBTreeFixLenCString             = 12,
 188         kBTreeUniCodeString             = 13,
 189         kBTreeFixUniCodeString  = 14
 190 };
 191 typedef UInt8           BTreeKeyType;
 192
 193
 194 /*
 195         B*Tree Key Descriptor String Field Attributes
 196 */
 197
 198 enum {
 199         kBTreeCaseSens                  = 0x10,         // case sensitive
 200         kBTreeNotDiacSens               = 0x20          // not diacritical sensitive
 201 };
 202 typedef UInt8           BTreeStringAttributes;
 203
 204 /*
 205         Btree types: 0 is HFS CAT/EXT file, 1~127 are AppleShare B*Tree files, 128~254 unused
 206         hfsBtreeType    EQU             0                       ; control file
 207         validBTType             EQU             $80                     ; user btree type starts from 128
 208         userBT1Type             EQU             $FF                     ; 255 is our Btree type. Used by BTInit and BTPatch
 209 */
 210
 211 enum BTreeTypes{
 212         kHFSBTreeType                   =   0,          // control file
 213         kUserBTreeType                  = 128,          // user btree type starts from 128
 214         kReservedBTreeType              = 255           //
 215 };
 216
 217 enum {
 218         kInvalidMRUCacheKey             = -1L   /* flag to denote current MRU cache key is invalid*/
 219
 220 };
 221
 222 /*============================================================================
 223         B*Tree Key Structures
 224 ============================================================================*/
 225
 226 /*
 227         BTreeKeyDescriptor is used to indicate how keys for a particular B*Tree
 228         are to be compared.
 229  */
 230 typedef char BTreeKeyDescriptor[26];
 231 typedef char *BTreeKeyDescriptorPtr;
 232
 233 /*
 234         BTreeInformation is used to describe the public information about a BTree
 235  */
 236 struct BTreeInformation{
 237         UInt16                                          NodeSize;
 238         UInt16                                          MaxKeyLength;
 239         UInt16                                          Depth;
 240         UInt16                                          Reserved;
 241         ItemCount                                       NumRecords;
 242         ItemCount                                       NumNodes;
 243         ItemCount                                       NumFreeNodes;
 244         ByteCount                                       ClumpSize;
 245         BTreeKeyDescriptor                      KeyDescriptor;
 246         };
 247 typedef struct BTreeInformation BTreeInformation;
 248 typedef BTreeInformation *BTreeInformationPtr;
 249
 250 typedef BTreeKey *BTreeKeyPtr;
 251
 252
 253 struct KeyDescriptor{
 254         UInt8                   length;
 255         UInt8                   fieldDesc [kMaxKeyDescriptorLength];
 256 };
 257 typedef struct KeyDescriptor KeyDescriptor;
 258 typedef KeyDescriptor *KeyDescriptorPtr;
 259
 260 struct NumberFieldDescriptor{
 261         UInt8                   fieldType;
 262         UInt8                   occurrence;                                     // number of consecutive fields of this type
 263 };
 264 typedef struct NumberFieldDescriptor NumberFieldDescriptor;
 265
 266 struct StringFieldDescriptor{
 267         UInt8                   fieldType;                                      // kBTString
 268         UInt8                   occurrence;                                     // number of consecutive fields of this type
 269         UInt8                   stringAttribute;
 270         UInt8                   filler;
 271 };
 272 typedef struct StringFieldDescriptor StringFieldDescriptor;
 273
 274 struct FixedLengthStringFieldDescriptor{
 275         UInt8                   fieldType;                                      // kBTFixLenString
 276         UInt8                   stringLength;
 277         UInt8                   occurrence;
 278         UInt8                   stringAttribute;
 279 };
 280 typedef struct FixedLengthStringFieldDescriptor FixedLengthStringFieldDescriptor;
 281
 282 /*
 283         BTreeInfoRec Structure - for BTGetInformation
 284 */
 285 struct BTreeInfoRec{
 286         UInt16                          version;
 287         UInt16                          nodeSize;
 288         UInt16                          maxKeyLength;
 289         UInt16                          treeDepth;
 290         ItemCount                       numRecords;
 291         ItemCount                       numNodes;
 292         ItemCount                       numFreeNodes;
 293         KeyDescriptorPtr        keyDescriptor;
 294         ByteCount                       keyDescLength;
 295         UInt32                          reserved;
 296 };
 297 typedef struct BTreeInfoRec BTreeInfoRec;
 298 typedef BTreeInfoRec *BTreeInfoPtr;
 299
 300 /*
 301         BTreeHint can never be exported to the outside. Use UInt32 BTreeHint[4],
 302         UInt8 BTreeHint[16], etc.
 303  */
 304 struct BTreeHint{
 305         ItemCount                               writeCount;
 306         UInt32                                  nodeNum;                        // node the key was last seen in
 307         UInt16                                  index;                          // index then key was last seen at
 308         UInt16                                  reserved1;
 309         UInt32                                  reserved2;
 310 };
 311 typedef struct BTreeHint BTreeHint;
 312 typedef BTreeHint *BTreeHintPtr;
 313
 314 /*
 315         BTree Iterator
 316 */
 317 struct BTreeIterator{
 318         BTreeHint                               hint;
 319         UInt16                                  version;
 320         UInt16                                  reserved;
 321         BTreeKey                                key;
 322 };
 323 typedef struct BTreeIterator BTreeIterator;
 324 typedef BTreeIterator *BTreeIteratorPtr;
 325
 326
 327 /*============================================================================
 328         B*Tree SPI
 329 ============================================================================*/
 330
 331 typedef SInt32          (* KeyCompareProcPtr)   (BTreeKeyPtr a, BTreeKeyPtr b);
 332
 333 typedef OSStatus        (* GetBlockProcPtr)             (SFCB   *filePtr,
 334                                                                                          UInt32                                          blockNum,
 335                                                                                          GetBlockOptions                         options,
 336                                                                                          BlockDescriptor                        *block );
 337
 338
 339 typedef OSStatus        (* ReleaseBlockProcPtr) (SFCB           *filePtr,
 340                                                                                          BlockDescPtr                            blockPtr,
 341                                                                                          ReleaseBlockOptions             options );
 342
 343 typedef OSStatus        (* SetEndOfForkProcPtr) (SFCB                                           *filePtr,
 344                                                                                          FSSize                                          minEOF,
 345                                                                                          FSSize                                          maxEOF );
 346
 347 typedef OSStatus        (* SetBlockSizeProcPtr) (SFCB                                           *filePtr,
 348                                                                                          ByteCount                                       blockSize );
 349
 350 OSStatus                SetEndOfForkProc ( SFCB                                         *filePtr, FSSize minEOF, FSSize maxEOF );
 351
 352
 353
 354 extern OSStatus InitBTreeModule         (void);
 355
 356
 357 extern OSStatus BTInitialize            (SFCB                                           *filePtrPtr,
 358                                                                          UInt16                                          maxKeyLength,
 359                                                                          UInt16                                          nodeSize,
 360                                                                          UInt8                                           btreeType,
 361                                                                          KeyDescriptorPtr                        keyDescPtr );
 362
 363 extern OSStatus BTOpenPath                      (SFCB                                           *filePtr,
 364                                                                          KeyCompareProcPtr                       keyCompareProc,
 365                                                                          GetBlockProcPtr                         getBlockProc,
 366                                                                          ReleaseBlockProcPtr             releaseBlockProc,
 367                                                                          SetEndOfForkProcPtr             setEndOfForkProc,
 368                                                                          SetBlockSizeProcPtr             setBlockSizeProc );
 369
 370 extern OSStatus BTClosePath                     (SFCB                                           *filePtr );
 371
 372
 373 extern OSStatus BTSearchRecord          (SFCB                                           *filePtr,
 374                                                                          BTreeIterator                          *searchIterator,
 375                                                                          UInt32                                         heuristicHint,
 376                                                                          FSBufferDescriptor                     *btRecord,
 377                                                                          UInt16                                         *recordLen,
 378                                                                          BTreeIterator                          *resultIterator );
 379
 380 extern OSStatus BTIterateRecord         (SFCB                                           *filePtr,
 381                                                                          BTreeIterationOperation         operation,
 382                                                                          BTreeIterator                          *iterator,
 383                                                                          FSBufferDescriptor                     *btRecord,
 384                                                                          UInt16                                         *recordLen );
 385
 386 extern OSStatus BTInsertRecord          (SFCB                                           *filePtr,
 387                                                                          BTreeIterator                          *iterator,
 388                                                                          FSBufferDescriptor                     *btrecord,
 389                                                                          UInt16                                          recordLen );
 390
 391 extern OSStatus BTReplaceRecord         (SFCB                                           *filePtr,
 392                                                                          BTreeIterator                          *iterator,
 393                                                                          FSBufferDescriptor                     *btRecord,
 394                                                                          UInt16                                          recordLen );
 395
 396 extern OSStatus BTSetRecord                     (SFCB                                           *filePtr,
 397                                                                          BTreeIterator                          *iterator,
 398                                                                          FSBufferDescriptor                     *btRecord,
 399                                                                          UInt16                                          recordLen );
 400
 401 extern OSStatus BTDeleteRecord          (SFCB                                           *filePtr,
 402                                                                          BTreeIterator                          *iterator );
 403
 404 extern OSStatus BTGetInformation        (SFCB                                           *filePtr,
 405                                                                          UInt16                                          version,
 406                                                                          BTreeInfoRec                           *info );
 407
 408 extern OSStatus BTFlushPath                     (SFCB                                           *filePtr );
 409
 410 extern OSStatus BTInvalidateHint        (BTreeIterator                          *iterator );
 411
 412 #endif // __BTREESINTERNAL__