core/BTreesInternal.h

   1 /*
   2  * Copyright (c) 2000-2014 Apple 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:      (c) 1996-1998 by Apple 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                 kGetBlockHint           = 0x00000001,   // if set, the block is being looked up using hint
 148                 kForceReadBlock         = 0x00000002,   //\80\80 how does this relate to Read/Verify? Do we need this?
 149                 kGetEmptyBlock          = 0x00000008
 150 };
 151 typedef u_int32_t       GetBlockOptions;
 152
 153 /*
 154         Fork Level Access Method Block release options
 155 */
 156 enum {
 157                 kReleaseBlock           = 0x00000000,
 158                 kForceWriteBlock        = 0x00000001,
 159                 kMarkBlockDirty         = 0x00000002,
 160                 kTrashBlock                     = 0x00000004,
 161                 kLockTransaction    = 0x00000100
 162 };
 163 typedef u_int32_t       ReleaseBlockOptions;
 164
 165 typedef u_int64_t       FSSize;
 166 typedef u_int32_t       ForkBlockNumber;
 167
 168 /*============================================================================
 169         Fork Level Buffered I/O Access Method
 170 ============================================================================*/
 171
 172 typedef OSStatus        (* GetBlockProcPtr)             (FileReference                           fileRefNum,
 173                                                                                          u_int32_t                                       blockNum,
 174                                                                                          GetBlockOptions                         options,
 175                                                                                          BlockDescriptor                        *block );
 176
 177
 178 typedef OSStatus        (* ReleaseBlockProcPtr) (FileReference                           fileRefNum,
 179                                                                                          BlockDescPtr                            blockPtr,
 180                                                                                          ReleaseBlockOptions             options );
 181
 182 typedef OSStatus        (* SetEndOfForkProcPtr) (FileReference                           fileRefNum,
 183                                                                                          FSSize                                          minEOF,
 184                                                                                          FSSize                                          maxEOF );
 185
 186 typedef OSStatus        (* SetBlockSizeProcPtr) (FileReference                           fileRefNum,
 187                                                                                          ByteCount                                       blockSize,
 188                                                                                          ItemCount                                       minBlockCount );
 189
 190 OSStatus                SetEndOfForkProc ( FileReference fileRefNum, FSSize minEOF, FSSize maxEOF );
 191
 192
 193 /*
 194         B*Tree Information Version
 195 */
 196
 197 enum BTreeInformationVersion{
 198         kBTreeInfoVersion       = 0
 199 };
 200
 201 /*
 202         B*Tree Iteration Operation Constants
 203 */
 204
 205 enum BTreeIterationOperations{
 206         kBTreeFirstRecord,
 207         kBTreeNextRecord,
 208         kBTreePrevRecord,
 209         kBTreeLastRecord,
 210         kBTreeCurrentRecord
 211 };
 212 typedef u_int16_t BTreeIterationOperation;
 213
 214
 215 /*
 216         Btree types: 0 is HFS CAT/EXT file, 1~127 are AppleShare B*Tree files, 128~254 unused
 217         hfsBtreeType    EQU             0                       ; control file
 218         validBTType             EQU             $80                     ; user btree type starts from 128
 219         userBT1Type             EQU             $FF                     ; 255 is our Btree type. Used by BTInit and BTPatch
 220 */
 221
 222 enum BTreeTypes{
 223         kHFSBTreeType                   =   0,          // control file
 224         kUserBTreeType                  = 128,          // user btree type starts from 128
 225         kReservedBTreeType              = 255           //
 226 };
 227
 228 #define kBTreeHeaderUserBytes   128
 229
 230
 231 typedef BTreeKey *BTreeKeyPtr;
 232
 233
 234 /*
 235         BTreeInfoRec Structure - for BTGetInformation
 236 */
 237 struct BTreeInfoRec{
 238         u_int16_t                       version;
 239         u_int16_t                       nodeSize;
 240         u_int16_t                       maxKeyLength;
 241         u_int16_t                       treeDepth;
 242         u_int32_t                       lastfsync;              /* Last time that this was fsynced  */
 243         ItemCount                       numRecords;
 244         ItemCount                       numNodes;
 245         ItemCount                       numFreeNodes;
 246         u_int8_t                        keyCompareType;
 247         u_int8_t                        reserved[3];
 248 };
 249 typedef struct BTreeInfoRec BTreeInfoRec;
 250 typedef BTreeInfoRec *BTreeInfoPtr;
 251
 252 /*
 253         BTreeHint can never be exported to the outside. Use u_int32_t BTreeHint[4],
 254         u_int8_t BTreeHint[16], etc.
 255  */
 256 struct BTreeHint{
 257         ItemCount                               writeCount;
 258         u_int32_t                               nodeNum;                        // node the key was last seen in
 259         u_int16_t                               index;                          // index then key was last seen at
 260         u_int16_t                               reserved1;
 261         u_int32_t                               reserved2;
 262 };
 263 typedef struct BTreeHint BTreeHint;
 264 typedef BTreeHint *BTreeHintPtr;
 265
 266 /*
 267         BTree Iterator
 268 */
 269 struct BTreeIterator{
 270         BTreeHint                               hint;
 271         u_int16_t                               version;
 272         u_int16_t                               reserved;
 273         u_int32_t                               hitCount;                       // Total number of leaf records hit
 274         u_int32_t                               maxLeafRecs;            // Max leaf records over iteration
 275         BTreeKey                                key;
 276 };
 277 typedef struct BTreeIterator BTreeIterator;
 278 typedef BTreeIterator *BTreeIteratorPtr;
 279
 280
 281 /*============================================================================
 282         B*Tree SPI
 283 ============================================================================*/
 284
 285 /*
 286         Key Comparison Function ProcPtr Type - for BTOpenPath
 287 */
 288 //typedef int32_t                               (* KeyCompareProcPtr)(BTreeKeyPtr a, BTreeKeyPtr b);
 289
 290
 291 typedef int32_t (* IterateCallBackProcPtr)(BTreeKeyPtr key, void * record, void * state);
 292
 293
 294 extern OSStatus BTOpenPath(FCB *filePtr, KeyCompareProcPtr keyCompareProc);
 295
 296 extern OSStatus BTClosePath                     (FCB                                            *filePtr );
 297
 298
 299 extern OSStatus BTSearchRecord          (FCB                                            *filePtr,
 300                                                                          BTreeIterator                          *searchIterator,
 301                                                                          FSBufferDescriptor                     *btRecord,
 302                                                                          u_int16_t                                      *recordLen,
 303                                                                          BTreeIterator                          *resultIterator );
 304
 305 extern OSStatus BTIterateRecord         (FCB                                            *filePtr,
 306                                                                          BTreeIterationOperation         operation,
 307                                                                          BTreeIterator                          *iterator,
 308                                                                          FSBufferDescriptor                     *btRecord,
 309                                                                          u_int16_t                                      *recordLen );
 310
 311
 312 extern OSStatus BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator *iterator,
 313                  IterateCallBackProcPtr  callBackProc, void * callBackState);
 314
 315 extern OSStatus BTInsertRecord          (FCB                                            *filePtr,
 316                                                                          BTreeIterator                          *iterator,
 317                                                                          FSBufferDescriptor                     *btrecord,
 318                                                                          u_int16_t                                       recordLen );
 319
 320 extern OSStatus BTReplaceRecord         (FCB                                            *filePtr,
 321                                                                          BTreeIterator                          *iterator,
 322                                                                          FSBufferDescriptor                     *btRecord,
 323                                                                          u_int16_t                                       recordLen );
 324
 325 extern OSStatus BTUpdateRecord          (FCB                                            *filePtr,
 326                                                                          BTreeIterator                          *iterator,
 327                                                                          IterateCallBackProcPtr          callBackProc,
 328                                                                          void                                           *callBackState );
 329
 330 extern OSStatus BTDeleteRecord          (FCB                                            *filePtr,
 331                                                                          BTreeIterator                          *iterator );
 332
 333 extern OSStatus BTGetInformation        (FCB                                            *filePtr,
 334                                                                          u_int16_t                                       vers,
 335                                                                          BTreeInfoRec                           *info );
 336
 337 extern OSStatus BTIsDirty(FCB *filePtr);
 338
 339 extern OSStatus BTFlushPath                     (FCB                                            *filePtr );
 340
 341 extern OSStatus BTReloadData            (FCB *filePtr);
 342
 343 extern OSStatus BTInvalidateHint        (BTreeIterator                          *iterator );
 344
 345 extern OSStatus BTGetLastSync           (FCB                                            *filePtr,
 346                                                                          u_int32_t                                      *lastfsync );
 347
 348 extern OSStatus BTSetLastSync           (FCB                                            *filePtr,
 349                                                                          u_int32_t                                      lastfsync );
 350
 351 extern OSStatus BTHasContiguousNodes(FCB                                                *filePtr);
 352
 353 extern OSStatus BTGetUserData(FCB *filePtr, void * dataPtr, int dataSize);
 354
 355 extern OSStatus BTSetUserData(FCB *filePtr, void * dataPtr, int dataSize);
 356
 357 /* B-tree node reserve routines. */
 358 extern void BTReserveSetup(void);
 359
 360 extern int  BTReserveSpace(FCB *file, int operations, void * data);
 361
 362 extern int  BTReleaseReserve(FCB *file, void * data);
 363
 364 extern int  BTZeroUnusedNodes(FCB *file);
 365
 366 #endif /* __APPLE_API_PRIVATE */
 367 #endif /* KERNEL */
 368 #endif // __BTREESINTERNAL__