bsd/hfs/hfscommon/headers/BTreesInternal.h

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