bsd/hfs/hfscommon/headers/BTreesInternal.h

   1 /*
   2  * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_OSREFERENCE_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.  The rights granted to you under the
  10  * License may not be used to create, or enable the creation or
  11  * redistribution of, unlawful or unlicensed copies of an Apple operating
  12  * system, or to circumvent, violate, or enable the circumvention or
  13  * violation of, any terms of an Apple operating system software license
  14  * agreement.
  15  *
  16  * Please obtain a copy of the License at
  17  * http://www.opensource.apple.com/apsl/ and read it before using this
  18  * file.
  19  *
  20  * The Original Code and all software distributed under the License are
  21  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  22  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  23  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  24  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  25  * Please see the License for the specific language governing rights and
  26  * limitations under the License.
  27  *
  28  * @APPLE_LICENSE_OSREFERENCE_HEADER_END@
  29  */
  30 /*
  31         File:           BTreesInternal.h
  32
  33         Contains:       IPI to File Manager B-tree
  34
  35         Version:        HFS Plus 1.0
  36
  37         Copyright:      © 1996-1998 by Apple Computer, Inc., all rights reserved.
  38
  39         File Ownership:
  40
  41                 DRI:                            Don Brady
  42
  43                 Other Contact:          Mark Day
  44
  45                 Technology:                     File Systems
  46
  47         Writers:
  48
  49                 (msd)   Mark Day
  50                 (DSH)   Deric Horn
  51                 (djb)   Don Brady
  52
  53         Change History (most recent first):
  54
  55           <RHAP>         9/22/99        ser             Added prototypes for BTGetLastSync and BTSetLastSync
  56           <RHAP>         6/22/98        djb             Add ERR_BASE to btree error codes to make them negative (for MacOS X only).
  57
  58            <CS7>         7/28/97        msd             Add enum for fsBTTimeOutErr.
  59            <CS6>         7/25/97        DSH             Added heuristicHint as parameter to BTSearchRecord.
  60            <CS5>         7/24/97        djb             Add blockReadFromDisk flag to BlockDescriptor. Callbacks now use
  61                                                                         a file refNum instead of an FCB.
  62            <CS4>         7/16/97        DSH             FilesInternal.i renamed FileMgrInternal.i to avoid name
  63                                                                         collision
  64            <CS3>          6/2/97        DSH             Added SetEndOfForkProc() prototype, so Attributes.c can call it
  65                                                                         directly.
  66            <CS2>         5/19/97        djb             kMaxKeyLength is now 520.
  67            <CS1>         4/28/97        djb             first checked in
  68
  69           <HFS6>         3/17/97        DSH             Remove Key Comparison prototype, already in FilesInternal.h.
  70           <HFS5>         2/19/97        djb             Add SetBlockSizeProcPtr. Add blockSize field to BlockDescriptor.
  71                                                                         Remove E_ type error enums.
  72           <HFS4>         1/27/97        djb             Include Types.h and FilesInternal.h.
  73           <HFS3>         1/13/97        djb             Added kBTreeCurrentRecord for BTIterateRecord.
  74           <HFS2>          1/3/97        djb             Added support for large keys.
  75           <HFS1>        12/19/96        djb             first checked in
  76
  77 */
  78
  79 #ifndef __BTREESINTERNAL__
  80 #define __BTREESINTERNAL__
  81
  82 #include <sys/appleapiopts.h>
  83
  84 #ifdef KERNEL
  85 #ifdef __APPLE_API_PRIVATE
  86
  87 #ifndef __FILEMGRINTERNAL__
  88 #include "FileMgrInternal.h"
  89 #endif
  90
  91 enum {
  92         fsBTInvalidHeaderErr                    = btBadHdr,
  93         fsBTBadRotateErr                                = dsBadRotate,
  94         fsBTInvalidNodeErr                              = btBadNode,
  95         fsBTRecordTooLargeErr                   = btNoFit,
  96         fsBTRecordNotFoundErr                   = btNotFound,
  97         fsBTDuplicateRecordErr                  = btExists,
  98         fsBTFullErr                                             = btNoSpaceAvail,
  99
 100         fsBTInvalidFileErr                              = ERR_BASE + 0x0302,    /* no BTreeCB has been allocated for fork*/
 101         fsBTrFileAlreadyOpenErr                 = ERR_BASE + 0x0303,
 102         fsBTInvalidIteratorErr                  = ERR_BASE + 0x0308,
 103         fsBTEmptyErr                                    = ERR_BASE + 0x030A,
 104         fsBTNoMoreMapNodesErr                   = ERR_BASE + 0x030B,
 105         fsBTBadNodeSize                                 = ERR_BASE + 0x030C,
 106         fsBTBadNodeType                                 = ERR_BASE + 0x030D,
 107         fsBTInvalidKeyLengthErr                 = ERR_BASE + 0x030E,
 108         fsBTStartOfIterationErr                 = ERR_BASE + 0x0353,
 109         fsBTEndOfIterationErr                   = ERR_BASE + 0x0354,
 110         fsBTUnknownVersionErr                   = ERR_BASE + 0x0355,
 111         fsBTTreeTooDeepErr                              = ERR_BASE + 0x0357,
 112         fsIteratorExitedScopeErr                = ERR_BASE + 0x0A02,    /* iterator exited the scope*/
 113         fsIteratorScopeExceptionErr             = ERR_BASE + 0x0A03,    /* iterator is undefined due to error or movement of scope locality*/
 114         fsUnknownIteratorMovementErr    = ERR_BASE + 0x0A04,    /* iterator movement is not defined*/
 115         fsInvalidIterationMovmentErr    = ERR_BASE + 0x0A05,    /* iterator movement is invalid in current context*/
 116         fsClientIDMismatchErr                   = ERR_BASE + 0x0A06,    /* wrong client process ID*/
 117         fsEndOfIterationErr                             = ERR_BASE + 0x0A07,    /* there were no objects left to return on iteration*/
 118         fsBTTimeOutErr                                  = ERR_BASE + 0x0A08             /* BTree scan interrupted -- no time left for physical I/O */
 119 };
 120
 121 struct BlockDescriptor{
 122         void            *buffer;
 123         void            *blockHeader;
 124         daddr64_t        blockNum;      /* logical block number (used by hfs_swap_BTNode) */
 125         ByteCount        blockSize;
 126         Boolean          blockReadFromDisk;
 127         Byte         isModified;             // XXXdbg - for journaling
 128         Byte             reserved[2];
 129 };
 130 typedef struct BlockDescriptor BlockDescriptor;
 131 typedef BlockDescriptor *BlockDescPtr;
 132
 133
 134 struct FSBufferDescriptor {
 135         void *          bufferAddress;
 136         ByteCount       itemSize;
 137         ItemCount       itemCount;
 138 };
 139 typedef struct FSBufferDescriptor FSBufferDescriptor;
 140
 141 typedef FSBufferDescriptor *FSBufferDescriptorPtr;
 142
 143
 144 /*
 145         Fork Level Access Method Block get options
 146 */
 147 enum {
 148                 kGetBlock                       = 0x00000000,
 149                 kForceReadBlock         = 0x00000002,   //\80\80 how does this relate to Read/Verify? Do we need this?
 150                 kGetEmptyBlock          = 0x00000008
 151 };
 152 typedef OptionBits      GetBlockOptions;
 153
 154 /*
 155         Fork Level Access Method Block release options
 156 */
 157 enum {
 158                 kReleaseBlock           = 0x00000000,
 159                 kForceWriteBlock        = 0x00000001,
 160                 kMarkBlockDirty         = 0x00000002,
 161                 kTrashBlock                     = 0x00000004,
 162                 kLockTransaction    = 0x00000100
 163 };
 164 typedef OptionBits      ReleaseBlockOptions;
 165
 166 typedef UInt64  FSSize;
 167 typedef UInt32  ForkBlockNumber;
 168
 169 /*============================================================================
 170         Fork Level Buffered I/O Access Method
 171 ============================================================================*/
 172
 173 typedef OSStatus        (* GetBlockProcPtr)             (FileReference                           fileRefNum,
 174                                                                                          UInt32                                          blockNum,
 175                                                                                          GetBlockOptions                         options,
 176                                                                                          BlockDescriptor                        *block );
 177
 178
 179 typedef OSStatus        (* ReleaseBlockProcPtr) (FileReference                           fileRefNum,
 180                                                                                          BlockDescPtr                            blockPtr,
 181                                                                                          ReleaseBlockOptions             options );
 182
 183 typedef OSStatus        (* SetEndOfForkProcPtr) (FileReference                           fileRefNum,
 184                                                                                          FSSize                                          minEOF,
 185                                                                                          FSSize                                          maxEOF );
 186
 187 typedef OSStatus        (* SetBlockSizeProcPtr) (FileReference                           fileRefNum,
 188                                                                                          ByteCount                                       blockSize,
 189                                                                                          ItemCount                                       minBlockCount );
 190
 191 OSStatus                SetEndOfForkProc ( FileReference fileRefNum, FSSize minEOF, FSSize maxEOF );
 192
 193
 194 /*
 195         B*Tree Information Version
 196 */
 197
 198 enum BTreeInformationVersion{
 199         kBTreeInfoVersion       = 0
 200 };
 201
 202 /*
 203         B*Tree Iteration Operation Constants
 204 */
 205
 206 enum BTreeIterationOperations{
 207         kBTreeFirstRecord,
 208         kBTreeNextRecord,
 209         kBTreePrevRecord,
 210         kBTreeLastRecord,
 211         kBTreeCurrentRecord
 212 };
 213 typedef UInt16 BTreeIterationOperation;
 214
 215
 216 /*
 217         Btree types: 0 is HFS CAT/EXT file, 1~127 are AppleShare B*Tree files, 128~254 unused
 218         hfsBtreeType    EQU             0                       ; control file
 219         validBTType             EQU             $80                     ; user btree type starts from 128
 220         userBT1Type             EQU             $FF                     ; 255 is our Btree type. Used by BTInit and BTPatch
 221 */
 222
 223 enum BTreeTypes{
 224         kHFSBTreeType                   =   0,          // control file
 225         kUserBTreeType                  = 128,          // user btree type starts from 128
 226         kReservedBTreeType              = 255           //
 227 };
 228
 229 #define kBTreeHeaderUserBytes   128
 230
 231
 232 typedef BTreeKey *BTreeKeyPtr;
 233
 234
 235 /*
 236         BTreeInfoRec Structure - for BTGetInformation
 237 */
 238 struct BTreeInfoRec{
 239         UInt16                          version;
 240         UInt16                          nodeSize;
 241         UInt16                          maxKeyLength;
 242         UInt16                          treeDepth;
 243         UInt32                          lastfsync;              /* Last time that this was fsynced  */
 244         ItemCount                       numRecords;
 245         ItemCount                       numNodes;
 246         ItemCount                       numFreeNodes;
 247         UInt8                           keyCompareType;
 248         UInt8                           reserved[3];
 249 };
 250 typedef struct BTreeInfoRec BTreeInfoRec;
 251 typedef BTreeInfoRec *BTreeInfoPtr;
 252
 253 /*
 254         BTreeHint can never be exported to the outside. Use UInt32 BTreeHint[4],
 255         UInt8 BTreeHint[16], etc.
 256  */
 257 struct BTreeHint{
 258         ItemCount                               writeCount;
 259         UInt32                                  nodeNum;                        // node the key was last seen in
 260         UInt16                                  index;                          // index then key was last seen at
 261         UInt16                                  reserved1;
 262         UInt32                                  reserved2;
 263 };
 264 typedef struct BTreeHint BTreeHint;
 265 typedef BTreeHint *BTreeHintPtr;
 266
 267 /*
 268         BTree Iterator
 269 */
 270 struct BTreeIterator{
 271         BTreeHint                               hint;
 272         UInt16                                  version;
 273         UInt16                                  reserved;
 274         UInt32                                  hitCount;                       // Total number of leaf records hit
 275         UInt32                                  maxLeafRecs;            // Max leaf records over iteration
 276         BTreeKey                                key;
 277 };
 278 typedef struct BTreeIterator BTreeIterator;
 279 typedef BTreeIterator *BTreeIteratorPtr;
 280
 281
 282 /*============================================================================
 283         B*Tree SPI
 284 ============================================================================*/
 285
 286 /*
 287         Key Comparison Function ProcPtr Type - for BTOpenPath
 288 */
 289 //typedef SInt32                                (* KeyCompareProcPtr)(BTreeKeyPtr a, BTreeKeyPtr b);
 290
 291
 292 typedef SInt32 (* IterateCallBackProcPtr)(BTreeKeyPtr key, void * record, void * state);
 293
 294
 295 extern OSStatus BTOpenPath(FCB *filePtr, KeyCompareProcPtr keyCompareProc);
 296
 297 extern OSStatus BTClosePath                     (FCB                                            *filePtr );
 298
 299
 300 extern OSStatus BTSearchRecord          (FCB                                            *filePtr,
 301                                                                          BTreeIterator                          *searchIterator,
 302                                                                          FSBufferDescriptor                     *btRecord,
 303                                                                          UInt16                                         *recordLen,
 304                                                                          BTreeIterator                          *resultIterator );
 305
 306 extern OSStatus BTIterateRecord         (FCB                                            *filePtr,
 307                                                                          BTreeIterationOperation         operation,
 308                                                                          BTreeIterator                          *iterator,
 309                                                                          FSBufferDescriptor                     *btRecord,
 310                                                                          UInt16                                         *recordLen );
 311
 312
 313 extern OSStatus BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator *iterator,
 314                  IterateCallBackProcPtr  callBackProc, void * callBackState);
 315
 316 extern OSStatus BTInsertRecord          (FCB                                            *filePtr,
 317                                                                          BTreeIterator                          *iterator,
 318                                                                          FSBufferDescriptor                     *btrecord,
 319                                                                          UInt16                                          recordLen );
 320
 321 extern OSStatus BTReplaceRecord         (FCB                                            *filePtr,
 322                                                                          BTreeIterator                          *iterator,
 323                                                                          FSBufferDescriptor                     *btRecord,
 324                                                                          UInt16                                          recordLen );
 325
 326 extern OSStatus BTUpdateRecord          (FCB                                            *filePtr,
 327                                                                          BTreeIterator                          *iterator,
 328                                                                          IterateCallBackProcPtr          callBackProc,
 329                                                                          void                                           *callBackState );
 330
 331 extern OSStatus BTDeleteRecord          (FCB                                            *filePtr,
 332                                                                          BTreeIterator                          *iterator );
 333
 334 extern OSStatus BTGetInformation        (FCB                                            *filePtr,
 335                                                                          UInt16                                          vers,
 336                                                                          BTreeInfoRec                           *info );
 337
 338 extern OSStatus BTFlushPath                     (FCB                                            *filePtr );
 339
 340 extern OSStatus BTReloadData            (FCB *filePtr);
 341
 342 extern OSStatus BTInvalidateHint        (BTreeIterator                          *iterator );
 343
 344 extern OSStatus BTGetLastSync           (FCB                                            *filePtr,
 345                                                                          UInt32                                         *lastfsync );
 346
 347 extern OSStatus BTSetLastSync           (FCB                                            *filePtr,
 348                                                                          UInt32                                         lastfsync );
 349
 350 extern OSStatus BTHasContiguousNodes(FCB                                                *filePtr);
 351
 352 extern OSStatus BTGetUserData(FCB *filePtr, void * dataPtr, int dataSize);
 353
 354 extern OSStatus BTSetUserData(FCB *filePtr, void * dataPtr, int dataSize);
 355
 356 /* B-tree node reserve routines. */
 357 extern void BTReserveSetup(void);
 358
 359 extern int  BTReserveSpace(FCB *file, int operations, void * data);
 360
 361 extern int  BTReleaseReserve(FCB *file, void * data);
 362
 363
 364 #endif /* __APPLE_API_PRIVATE */
 365 #endif /* KERNEL */
 366 #endif // __BTREESINTERNAL__