bsd/hfs/hfscommon/headers/BTreesInternal.h

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