1/* 2 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_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. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23/* 24 File: BTreesInternal.h 25 26 Contains: IPI to File Manager B-tree 27 28 Version: HFS Plus 1.0 29 30 Copyright: � 1996-1998 by Apple Computer, Inc., all rights reserved. 31*/ 32 33#ifndef __BTREESINTERNAL__ 34#define __BTREESINTERNAL__ 35 36#include "SRuntime.h" 37 38// 39// internal error codes 40// 41enum { 42 // FXM errors 43 44 fxRangeErr = 16, // file position beyond mapped range 45 fxOvFlErr = 17, // extents file overflow 46 47 // Unicode errors 48 49 uniTooLongErr = 24, // Unicode string too long to convert to Str31 50 uniBufferTooSmallErr = 25, // Unicode output buffer too small 51 uniNotMappableErr = 26, // Unicode string can't be mapped to given script 52 53 // BTree Manager errors 54 55 btNotFound = 32, // record not found 56 btExists = 33, // record already exists 57 btNoSpaceAvail = 34, // no available space 58 btNoFit = 35, // record doesn't fit in node 59 btBadNode = 36, // bad node detected 60 btBadHdr = 37, // bad BTree header record detected 61 dsBadRotate = 64, // bad BTree rotate 62 63 // Catalog Manager errors 64 65 cmNotFound = 48, // CNode not found 66 cmExists = 49, // CNode already exists 67 cmNotEmpty = 50, // directory CNode not empty (valence = 0) 68 cmRootCN = 51, // invalid reference to root CNode 69 cmBadNews = 52, // detected bad catalog structure 70 cmFThdDirErr = 53, // thread belongs to a directory not a file 71 cmFThdGone = 54, // file thread doesn't exist 72 cmParentNotFound = 55, // CNode for parent ID does not exist 73 cmNotAFolder = 56, // Destination of move is a file, not a folder 74 cmUnknownNodeType = 57, // Node type isn't recognized 75 76 // Volume Check errors 77 78 vcInvalidExtentErr = 60 // Extent record is out of bounds 79}; 80 81enum { 82 fsBTInvalidHeaderErr = btBadHdr, 83 fsBTBadRotateErr = dsBadRotate, 84 fsBTInvalidNodeErr = btBadNode, 85 fsBTRecordTooLargeErr = btNoFit, 86 fsBTRecordNotFoundErr = btNotFound, 87 fsBTDuplicateRecordErr = btExists, 88 fsBTFullErr = btNoSpaceAvail, 89 90 fsBTInvalidFileErr = 0x0302, /* no BTreeCB has been allocated for fork*/ 91 fsBTrFileAlreadyOpenErr = 0x0303, 92 fsBTInvalidIteratorErr = 0x0308, 93 fsBTEmptyErr = 0x030A, 94 fsBTNoMoreMapNodesErr = 0x030B, 95 fsBTBadNodeSize = 0x030C, 96 fsBTBadNodeType = 0x030D, 97 fsBTInvalidKeyLengthErr = 0x030E, 98 fsBTInvalidKeyDescriptor = 0x030F, 99 fsBTStartOfIterationErr = 0x0353, 100 fsBTEndOfIterationErr = 0x0354, 101 fsBTUnknownVersionErr = 0x0355, 102 fsBTTreeTooDeepErr = 0x0357, 103 fsBTInvalidKeyDescriptorErr = 0x0358, 104 fsBTInvalidKeyFieldErr = 0x035E, 105 fsBTInvalidKeyAttributeErr = 0x035F, 106 fsIteratorExitedScopeErr = 0x0A02, /* iterator exited the scope*/ 107 fsIteratorScopeExceptionErr = 0x0A03, /* iterator is undefined due to error or movement of scope locality*/ 108 fsUnknownIteratorMovementErr = 0x0A04, /* iterator movement is not defined*/ 109 fsInvalidIterationMovmentErr = 0x0A05, /* iterator movement is invalid in current context*/ 110 fsClientIDMismatchErr = 0x0A06, /* wrong client process ID*/ 111 fsEndOfIterationErr = 0x0A07, /* there were no objects left to return on iteration*/ 112 fsBTTimeOutErr = 0x0A08 /* BTree scan interrupted -- no time left for physical I/O */ 113}; 114 115 116struct FSBufferDescriptor { 117 LogicalAddress bufferAddress; 118 ByteCount itemSize; 119 ItemCount itemCount; 120}; 121typedef struct FSBufferDescriptor FSBufferDescriptor; 122 123typedef FSBufferDescriptor *FSBufferDescriptorPtr; 124 125 126 127typedef UInt64 FSSize; 128typedef UInt32 ForkBlockNumber; 129 130 131/* 132 BTreeObjID is used to indicate an access path using the 133 BTree access method to a specific fork of a file. This value 134 is session relative and not persistent between invocations of 135 an application. It is in fact an object ID to which requests 136 for the given path should be sent. 137 */ 138typedef UInt32 BTreeObjID; 139 140/* 141 B*Tree Information Version 142*/ 143 144enum BTreeInformationVersion{ 145 kBTreeInfoVersion = 0 146}; 147 148/* 149 B*Tree Iteration Operation Constants 150*/ 151 152enum BTreeIterationOperations{ 153 kBTreeFirstRecord, 154 kBTreeNextRecord, 155 kBTreePrevRecord, 156 kBTreeLastRecord, 157 kBTreeCurrentRecord 158}; 159typedef UInt16 BTreeIterationOperation; 160 161/* 162 B*Tree Key Descriptor Limits 163*/ 164 165enum { 166 kMaxKeyDescriptorLength = 23, 167}; 168 169/* 170 B*Tree Key Descriptor Field Types 171*/ 172 173enum { 174 kBTreeSkip = 0, 175 kBTreeByte = 1, 176 kBTreeSignedByte = 2, 177 kBTreeWord = 4, 178 kBTreeSignedWord = 5, 179 kBTreeLong = 6, 180 kBTreeSignedLong = 7, 181 kBTreeString = 3, // Pascal string 182 kBTreeFixLenString = 8, // Pascal string w/ fixed length buffer 183 kBTreeReserved = 9, // reserved for Desktop Manager (?) 184 kBTreeUseKeyCmpProc = 10, 185 //�� not implemented yet... 186 kBTreeCString = 11, 187 kBTreeFixLenCString = 12, 188 kBTreeUniCodeString = 13, 189 kBTreeFixUniCodeString = 14 190}; 191typedef UInt8 BTreeKeyType; 192 193 194/* 195 B*Tree Key Descriptor String Field Attributes 196*/ 197 198enum { 199 kBTreeCaseSens = 0x10, // case sensitive 200 kBTreeNotDiacSens = 0x20 // not diacritical sensitive 201}; 202typedef UInt8 BTreeStringAttributes; 203 204/* 205 Btree types: 0 is HFS CAT/EXT file, 1~127 are AppleShare B*Tree files, 128~254 unused 206 hfsBtreeType EQU 0 ; control file 207 validBTType EQU $80 ; user btree type starts from 128 208 userBT1Type EQU $FF ; 255 is our Btree type. Used by BTInit and BTPatch 209*/ 210 211enum BTreeTypes{ 212 kHFSBTreeType = 0, // control file 213 kUserBTreeType = 128, // user btree type starts from 128 214 kReservedBTreeType = 255 // 215}; 216 217enum { 218 kInvalidMRUCacheKey = -1L /* flag to denote current MRU cache key is invalid*/ 219 220}; 221 222/*============================================================================ 223 B*Tree Key Structures 224============================================================================*/ 225 226/* 227 BTreeKeyDescriptor is used to indicate how keys for a particular B*Tree 228 are to be compared. 229 */ 230typedef char BTreeKeyDescriptor[26]; 231typedef char *BTreeKeyDescriptorPtr; 232 233/* 234 BTreeInformation is used to describe the public information about a BTree 235 */ 236struct BTreeInformation{ 237 UInt16 NodeSize; 238 UInt16 MaxKeyLength; 239 UInt16 Depth; 240 UInt16 Reserved; 241 ItemCount NumRecords; 242 ItemCount NumNodes; 243 ItemCount NumFreeNodes; 244 ByteCount ClumpSize; 245 BTreeKeyDescriptor KeyDescriptor; 246 }; 247typedef struct BTreeInformation BTreeInformation; 248typedef BTreeInformation *BTreeInformationPtr; 249 250typedef BTreeKey *BTreeKeyPtr; 251 252 253struct KeyDescriptor{ 254 UInt8 length; 255 UInt8 fieldDesc [kMaxKeyDescriptorLength]; 256}; 257typedef struct KeyDescriptor KeyDescriptor; 258typedef KeyDescriptor *KeyDescriptorPtr; 259 260struct NumberFieldDescriptor{ 261 UInt8 fieldType; 262 UInt8 occurrence; // number of consecutive fields of this type 263}; 264typedef struct NumberFieldDescriptor NumberFieldDescriptor; 265 266struct StringFieldDescriptor{ 267 UInt8 fieldType; // kBTString 268 UInt8 occurrence; // number of consecutive fields of this type 269 UInt8 stringAttribute; 270 UInt8 filler; 271}; 272typedef struct StringFieldDescriptor StringFieldDescriptor; 273 274struct FixedLengthStringFieldDescriptor{ 275 UInt8 fieldType; // kBTFixLenString 276 UInt8 stringLength; 277 UInt8 occurrence; 278 UInt8 stringAttribute; 279}; 280typedef struct FixedLengthStringFieldDescriptor FixedLengthStringFieldDescriptor; 281 282/* 283 BTreeInfoRec Structure - for BTGetInformation 284*/ 285struct BTreeInfoRec{ 286 UInt16 version; 287 UInt16 nodeSize; 288 UInt16 maxKeyLength; 289 UInt16 treeDepth; 290 ItemCount numRecords; 291 ItemCount numNodes; 292 ItemCount numFreeNodes; 293 KeyDescriptorPtr keyDescriptor; 294 ByteCount keyDescLength; 295 UInt32 reserved; 296}; 297typedef struct BTreeInfoRec BTreeInfoRec; 298typedef BTreeInfoRec *BTreeInfoPtr; 299 300/* 301 BTreeHint can never be exported to the outside. Use UInt32 BTreeHint[4], 302 UInt8 BTreeHint[16], etc. 303 */ 304struct BTreeHint{ 305 ItemCount writeCount; 306 UInt32 nodeNum; // node the key was last seen in 307 UInt16 index; // index then key was last seen at 308 UInt16 reserved1; 309 UInt32 reserved2; 310}; 311typedef struct BTreeHint BTreeHint; 312typedef BTreeHint *BTreeHintPtr; 313 314/* 315 BTree Iterator 316*/ 317struct BTreeIterator{ 318 BTreeHint hint; 319 UInt16 version; 320 UInt16 reserved; 321 BTreeKey key; 322}; 323typedef struct BTreeIterator BTreeIterator; 324typedef BTreeIterator *BTreeIteratorPtr; 325 326 327/*============================================================================ 328 B*Tree SPI 329============================================================================*/ 330 331typedef SInt32 (* KeyCompareProcPtr) (BTreeKeyPtr a, BTreeKeyPtr b); 332 333typedef OSStatus (* GetBlockProcPtr) (SFCB *filePtr, 334 UInt32 blockNum, 335 GetBlockOptions options, 336 BlockDescriptor *block ); 337 338 339typedef OSStatus (* ReleaseBlockProcPtr) (SFCB *filePtr, 340 BlockDescPtr blockPtr, 341 ReleaseBlockOptions options ); 342 343typedef OSStatus (* SetEndOfForkProcPtr) (SFCB *filePtr, 344 FSSize minEOF, 345 FSSize maxEOF ); 346 347typedef OSStatus (* SetBlockSizeProcPtr) (SFCB *filePtr, 348 ByteCount blockSize ); 349 350OSStatus SetEndOfForkProc ( SFCB *filePtr, FSSize minEOF, FSSize maxEOF ); 351 352 353 354extern OSStatus InitBTreeModule (void); 355 356 357extern OSStatus BTInitialize (SFCB *filePtrPtr, 358 UInt16 maxKeyLength, 359 UInt16 nodeSize, 360 UInt8 btreeType, 361 KeyDescriptorPtr keyDescPtr ); 362 363extern OSStatus BTOpenPath (SFCB *filePtr, 364 KeyCompareProcPtr keyCompareProc, 365 GetBlockProcPtr getBlockProc, 366 ReleaseBlockProcPtr releaseBlockProc, 367 SetEndOfForkProcPtr setEndOfForkProc, 368 SetBlockSizeProcPtr setBlockSizeProc ); 369 370extern OSStatus BTClosePath (SFCB *filePtr ); 371 372 373extern OSStatus BTSearchRecord (SFCB *filePtr, 374 BTreeIterator *searchIterator, 375 UInt32 heuristicHint, 376 FSBufferDescriptor *btRecord, 377 UInt16 *recordLen, 378 BTreeIterator *resultIterator ); 379 380extern OSStatus BTIterateRecord (SFCB *filePtr, 381 BTreeIterationOperation operation, 382 BTreeIterator *iterator, 383 FSBufferDescriptor *btRecord, 384 UInt16 *recordLen ); 385 386extern OSStatus BTInsertRecord (SFCB *filePtr, 387 BTreeIterator *iterator, 388 FSBufferDescriptor *btrecord, 389 UInt16 recordLen ); 390 391extern OSStatus BTReplaceRecord (SFCB *filePtr, 392 BTreeIterator *iterator, 393 FSBufferDescriptor *btRecord, 394 UInt16 recordLen ); 395 396extern OSStatus BTSetRecord (SFCB *filePtr, 397 BTreeIterator *iterator, 398 FSBufferDescriptor *btRecord, 399 UInt16 recordLen ); 400 401extern OSStatus BTDeleteRecord (SFCB *filePtr, 402 BTreeIterator *iterator ); 403 404extern OSStatus BTGetInformation (SFCB *filePtr, 405 UInt16 version, 406 BTreeInfoRec *info ); 407 408extern OSStatus BTFlushPath (SFCB *filePtr ); 409 410extern OSStatus BTInvalidateHint (BTreeIterator *iterator ); 411 412#endif // __BTREESINTERNAL__ 413