bsd/hfs/hfscommon/headers/BTreesInternal.h

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