1/* 2 * Copyright (c) 2000-2008 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: � 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 89enum { 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 119struct 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}; 128typedef struct BlockDescriptor BlockDescriptor; 129typedef BlockDescriptor *BlockDescPtr; 130 131 132struct FSBufferDescriptor { 133 void * bufferAddress; 134 ByteCount itemSize; 135 ItemCount itemCount; 136}; 137typedef struct FSBufferDescriptor FSBufferDescriptor; 138 139typedef FSBufferDescriptor *FSBufferDescriptorPtr; 140 141 142/* 143 Fork Level Access Method Block get options 144*/ 145enum { 146 kGetBlock = 0x00000000, 147 kGetBlockHint = 0x00000001, // if set, the block is being looked up using hint 148 kForceReadBlock = 0x00000002, //�� how does this relate to Read/Verify? Do we need this? 149 kGetEmptyBlock = 0x00000008 150}; 151typedef OptionBits GetBlockOptions; 152 153/* 154 Fork Level Access Method Block release options 155*/ 156enum { 157 kReleaseBlock = 0x00000000, 158 kForceWriteBlock = 0x00000001, 159 kMarkBlockDirty = 0x00000002, 160 kTrashBlock = 0x00000004, 161 kLockTransaction = 0x00000100 162}; 163typedef OptionBits ReleaseBlockOptions; 164 165typedef u_int64_t FSSize; 166typedef u_int32_t ForkBlockNumber; 167 168/*============================================================================ 169 Fork Level Buffered I/O Access Method 170============================================================================*/ 171 172typedef OSStatus (* GetBlockProcPtr) (FileReference fileRefNum, 173 u_int32_t blockNum, 174 GetBlockOptions options, 175 BlockDescriptor *block ); 176 177 178typedef OSStatus (* ReleaseBlockProcPtr) (FileReference fileRefNum, 179 BlockDescPtr blockPtr, 180 ReleaseBlockOptions options ); 181 182typedef OSStatus (* SetEndOfForkProcPtr) (FileReference fileRefNum, 183 FSSize minEOF, 184 FSSize maxEOF ); 185 186typedef OSStatus (* SetBlockSizeProcPtr) (FileReference fileRefNum, 187 ByteCount blockSize, 188 ItemCount minBlockCount ); 189 190OSStatus SetEndOfForkProc ( FileReference fileRefNum, FSSize minEOF, FSSize maxEOF ); 191 192 193/* 194 B*Tree Information Version 195*/ 196 197enum BTreeInformationVersion{ 198 kBTreeInfoVersion = 0 199}; 200 201/* 202 B*Tree Iteration Operation Constants 203*/ 204 205enum BTreeIterationOperations{ 206 kBTreeFirstRecord, 207 kBTreeNextRecord, 208 kBTreePrevRecord, 209 kBTreeLastRecord, 210 kBTreeCurrentRecord 211}; 212typedef 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 222enum 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 231typedef BTreeKey *BTreeKeyPtr; 232 233 234/* 235 BTreeInfoRec Structure - for BTGetInformation 236*/ 237struct 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}; 249typedef struct BTreeInfoRec BTreeInfoRec; 250typedef 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 */ 256struct 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}; 263typedef struct BTreeHint BTreeHint; 264typedef BTreeHint *BTreeHintPtr; 265 266/* 267 BTree Iterator 268*/ 269struct 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}; 277typedef struct BTreeIterator BTreeIterator; 278typedef 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 291typedef int32_t (* IterateCallBackProcPtr)(BTreeKeyPtr key, void * record, void * state); 292 293 294extern OSStatus BTOpenPath(FCB *filePtr, KeyCompareProcPtr keyCompareProc); 295 296extern OSStatus BTClosePath (FCB *filePtr ); 297 298 299extern OSStatus BTSearchRecord (FCB *filePtr, 300 BTreeIterator *searchIterator, 301 FSBufferDescriptor *btRecord, 302 u_int16_t *recordLen, 303 BTreeIterator *resultIterator ); 304 305extern OSStatus BTIterateRecord (FCB *filePtr, 306 BTreeIterationOperation operation, 307 BTreeIterator *iterator, 308 FSBufferDescriptor *btRecord, 309 u_int16_t *recordLen ); 310 311 312extern OSStatus BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator *iterator, 313 IterateCallBackProcPtr callBackProc, void * callBackState); 314 315extern OSStatus BTInsertRecord (FCB *filePtr, 316 BTreeIterator *iterator, 317 FSBufferDescriptor *btrecord, 318 u_int16_t recordLen ); 319 320extern OSStatus BTReplaceRecord (FCB *filePtr, 321 BTreeIterator *iterator, 322 FSBufferDescriptor *btRecord, 323 u_int16_t recordLen ); 324 325extern OSStatus BTUpdateRecord (FCB *filePtr, 326 BTreeIterator *iterator, 327 IterateCallBackProcPtr callBackProc, 328 void *callBackState ); 329 330extern OSStatus BTDeleteRecord (FCB *filePtr, 331 BTreeIterator *iterator ); 332 333extern OSStatus BTGetInformation (FCB *filePtr, 334 u_int16_t vers, 335 BTreeInfoRec *info ); 336 337extern OSStatus BTIsDirty(FCB *filePtr); 338 339extern OSStatus BTFlushPath (FCB *filePtr ); 340 341extern OSStatus BTReloadData (FCB *filePtr); 342 343extern OSStatus BTInvalidateHint (BTreeIterator *iterator ); 344 345extern OSStatus BTGetLastSync (FCB *filePtr, 346 u_int32_t *lastfsync ); 347 348extern OSStatus BTSetLastSync (FCB *filePtr, 349 u_int32_t lastfsync ); 350 351extern OSStatus BTHasContiguousNodes(FCB *filePtr); 352 353extern OSStatus BTGetUserData(FCB *filePtr, void * dataPtr, int dataSize); 354 355extern OSStatus BTSetUserData(FCB *filePtr, void * dataPtr, int dataSize); 356 357/* B-tree node reserve routines. */ 358extern void BTReserveSetup(void); 359 360extern int BTReserveSpace(FCB *file, int operations, void * data); 361 362extern int BTReleaseReserve(FCB *file, void * data); 363 364 365#endif /* __APPLE_API_PRIVATE */ 366#endif /* KERNEL */ 367#endif // __BTREESINTERNAL__ 368