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: BTreesPrivate.h 30 31 Contains: Private interface file for the BTree Module. 32 33 Version: xxx put the technology version here xxx 34 35 Written by: Gordon Sheridan and Bill Bruffey 36 37 Copyright: � 1992-1999 by Apple Computer, Inc., all rights reserved. 38 39 File Ownership: 40 41 DRI: Don Brady 42 43 Other Contact: Mark Day 44 45 Technology: File Systems 46 47 Writers: 48 49 (msd) Mark Day 50 (DSH) Deric Horn 51 (djb) Don Brady 52 (ser) Scott Roberts 53 (dkh) Dave Heller 54 55 Change History (most recent first): 56 <MacOSX> 3/19/99 djb Disable MoveRecordsLeft/Right macros since bcopy is broken. 57 58 <MacOSX> 8/10/98 djb Removed unused BTreeIterator from BTreeControlBlock, fixed alignment. 59 60 <CS5> 9/4/97 djb Convert MoveRecordsLeft and GetLeftSiblingNode to macros. 61 <CS4> 7/24/97 djb Add macro for GetRecordAddress (was a function before). 62 <CS3> 7/21/97 msd GetRecordByIndex now returns an OSStatus. 63 <CS2> 7/16/97 DSH FilesInternal.i renamed FileMgrInternal.i to avoid name 64 collision 65 <CS1> 4/23/97 djb first checked in 66 67 <HFS6> 3/17/97 DSH Added a refCon field to BTreeControlBlock, for DFA use, to point 68 to additional data. Fixed Panic macros for use with SC. 69 <HFS5> 2/19/97 djb Add InsertKey struct. Moved on-disk definitions to 70 HFSBTreesPriv.h 71 <HFS4> 1/27/97 djb InsertTree and DeleteTree are now recursive and support variable 72 sized index keys. 73 <HFS3> 1/15/97 djb Move GetFileRefNumFromFCB macro to FilesInternal.h. Added 74 kBTVariableIndexKeysMask. 75 <HFS2> 1/3/97 djb Added support for large keys. 76 <HFS1> 12/19/96 djb first checked in 77 78 History applicable to original Scarecrow Design: 79 80 <7> 10/25/96 ser Changing for new VFPI 81 <6> 10/18/96 ser Converting over VFPI changes 82 <5> 9/17/96 dkh More BTree statistics 83 <4> 9/16/96 dkh Revised BTree statistics 84 <3> 6/20/96 dkh Radar #1358740. Switch from using Pools to debug MemAllocators. 85 <2> 12/7/95 dkh D10E2 build. Changed usage of Ref data type to LogicalAddress. 86 <1> 10/18/95 rst Moved from Scarecrow project. 87 88 <19> 11/22/94 djb Add prototype for GetMapNode 89 <18> 11/16/94 prp Add IsItAHint routine prototype. 90 <17> 9/30/94 prp Get in sync with D2 interface changes. 91 <16> 7/25/94 wjk Eliminate usage of BytePtr in favor of UInt8 *. 92 <15> 7/22/94 wjk Convert to the new set of header files. 93 <14> 5/31/94 srs Moved Btree types to public interface 94 <13> 12/9/93 wjk Add 68k alignment pragma's around persistent structures. 95 <12> 11/30/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and 96 NRCmds environments. 97 <11> 11/23/93 wjk Changes required to compile on the RS6000. 98 <10> 8/30/93 CH Removed the M_ExitOnError and M_ReturnErrorIf macros which were 99 already defined in FileSystemPriv.h (included here). 100 <9> 8/30/93 CH Added parens around the M_ReturnErrorIf macro. 101 <8> 5/21/93 gs Add kBadClose flag. Add some prototypes for internal routines. 102 <7> 5/10/93 gs Change Ptr to BytePtr. Move BTreeTypes to BTree.h. Add 103 DeleteTree prototype. 104 <6> 3/23/93 gs Remove mysterious "flags" field from HeaderRec structure. Move 105 prototypes of private functions to top of respective source 106 files. 107 <5> 2/8/93 gs Update to use FSAgent.h Get/Release/SetEOF/SetBlockSize 108 procPtrs. Add UpdateNode routine. 109 <4> 12/10/92 gs Add Key Descriptor function declarations. 110 <3> 12/8/92 gs Add HeaderRec structure and incorporate review feedback. 111 <2> 12/2/92 gs Add GetNode and ReleaseNode callback procptrs to BTree CB, and 112 add internal function declarations. 113 <1> 11/15/92 gs first checked in 114 115*/ 116 117#ifndef __BTREESPRIVATE__ 118#define __BTREESPRIVATE__ 119 120#include <sys/appleapiopts.h> 121 122#ifdef KERNEL 123#ifdef __APPLE_API_PRIVATE 124 125#include "../../hfs_macos_defs.h" 126 127#ifndef __FILEMGRINTERNAL__ 128#include "FileMgrInternal.h" 129#endif 130 131#ifndef __BTREESINTERNAL__ 132#include "BTreesInternal.h" 133#endif 134 135 136/////////////////////////////////// Constants /////////////////////////////////// 137 138#define kBTreeVersion 1 139#define kMaxTreeDepth 16 140 141 142#define kHeaderNodeNum 0 143#define kKeyDescRecord 1 144 145 146// Header Node Record Offsets 147enum { 148 kHeaderRecOffset = 0x000E, 149 kKeyDescRecOffset = 0x0078, 150 kHeaderMapRecOffset = 0x00F8 151}; 152 153#define kMinNodeSize 512 154 155#define kMinRecordSize 6 156 // where is minimum record size enforced? 157 158// miscellaneous BTree constants 159enum { 160 kOffsetSize = 2 161}; 162 163// Insert Operations 164typedef enum { 165 kInsertRecord = 0, 166 kReplaceRecord = 1 167} InsertType; 168 169// illegal string attribute bits set in mask 170#define kBadStrAttribMask 0xCF 171 172 173 174//////////////////////////////////// Macros ///////////////////////////////////// 175 176#define M_NodesInMap(mapSize) ((mapSize) << 3) 177 178#define M_ClearBitNum(integer,bitNumber) ((integer) &= (~(1<<(bitNumber)))) 179#define M_SetBitNum(integer,bitNumber) ((integer) |= (1<<(bitNumber))) 180#define M_IsOdd(integer) (((integer) & 1) != 0) 181#define M_IsEven(integer) (((integer) & 1) == 0) 182#define M_BTreeHeaderDirty(btreePtr) btreePtr->flags |= kBTHeaderDirty 183 184#define M_MapRecordSize(nodeSize) (nodeSize - sizeof (BTNodeDescriptor) - 6) 185#define M_HeaderMapRecordSize(nodeSize) (nodeSize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) - 128 - 8) 186 187#define M_SWAP_BE16_ClearBitNum(integer,bitNumber) ((integer) &= SWAP_BE16(~(1<<(bitNumber)))) 188#define M_SWAP_BE16_SetBitNum(integer,bitNumber) ((integer) |= SWAP_BE16(1<<(bitNumber))) 189 190///////////////////////////////////// Types ///////////////////////////////////// 191 192typedef struct BTreeControlBlock { // fields specific to BTree CBs 193 194 u_int8_t keyCompareType; /* Key string Comparison Type */ 195 u_int8_t btreeType; 196 u_int16_t treeDepth; 197 FileReference fileRefNum; // refNum of btree file 198 KeyCompareProcPtr keyCompareProc; 199 u_int32_t rootNode; 200 u_int32_t leafRecords; 201 u_int32_t firstLeafNode; 202 u_int32_t lastLeafNode; 203 u_int16_t nodeSize; 204 u_int16_t maxKeyLength; 205 u_int32_t totalNodes; 206 u_int32_t freeNodes; 207 208 u_int16_t reserved3; // 4-byte alignment 209 210 // new fields 211 int16_t version; 212 u_int32_t flags; // dynamic flags 213 u_int32_t attributes; // persistent flags 214 u_int32_t writeCount; 215 u_int32_t lastfsync; /* Last time that this was fsynced */ 216 217 GetBlockProcPtr getBlockProc; 218 ReleaseBlockProcPtr releaseBlockProc; 219 SetEndOfForkProcPtr setEndOfForkProc; 220 221 // statistical information 222 u_int32_t numGetNodes; 223 u_int32_t numGetNewNodes; 224 u_int32_t numReleaseNodes; 225 u_int32_t numUpdateNodes; 226 u_int32_t numMapNodesRead; // map nodes beyond header node 227 u_int32_t numHintChecks; 228 u_int32_t numPossibleHints; // Looks like a formated hint 229 u_int32_t numValidHints; // Hint used to find correct record. 230 u_int32_t reservedNodes; 231 BTreeIterator iterator; // useable when holding exclusive b-tree lock 232} BTreeControlBlock, *BTreeControlBlockPtr; 233 234 235u_int32_t CalcKeySize(const BTreeControlBlock *btcb, const BTreeKey *key); 236#define CalcKeySize(btcb, key) ( ((btcb)->attributes & kBTBigKeysMask) ? ((key)->length16 + 2) : ((key)->length8 + 1) ) 237 238u_int32_t KeyLength(const BTreeControlBlock *btcb, const BTreeKey *key); 239#define KeyLength(btcb, key) ( ((btcb)->attributes & kBTBigKeysMask) ? (key)->length16 : (key)->length8 ) 240 241 242 243typedef enum { 244 kBTHeaderDirty = 0x00000001 245} BTreeFlags; 246 247 248typedef int8_t *NodeBuffer; 249typedef BlockDescriptor NodeRec, *NodePtr; //�� remove this someday... 250 251 252 253 254//// Tree Path Table - constructed by SearchTree, used by InsertTree and DeleteTree 255 256typedef struct { 257 u_int32_t node; // node number 258 u_int16_t index; 259 u_int16_t reserved; // align size to a power of 2 260} TreePathRecord, *TreePathRecordPtr; 261 262typedef TreePathRecord TreePathTable [kMaxTreeDepth]; 263 264 265//// InsertKey - used by InsertTree, InsertLevel and InsertNode 266 267struct InsertKey { 268 BTreeKeyPtr keyPtr; 269 u_int8_t * recPtr; 270 u_int16_t keyLength; 271 u_int16_t recSize; 272 Boolean replacingKey; 273 Boolean skipRotate; 274}; 275 276typedef struct InsertKey InsertKey; 277 278 279//// For Notational Convenience 280 281typedef BTNodeDescriptor* NodeDescPtr; 282typedef u_int8_t *RecordPtr; 283typedef BTreeKeyPtr KeyPtr; 284 285 286//////////////////////////////////// Globals //////////////////////////////////// 287 288 289//////////////////////////////////// Macros ///////////////////////////////////// 290 291#if DEBUG_BUILD 292 #define Panic( message ) DebugStr( message ) 293 #define PanicIf( condition, message ) do { if ( condition != 0 ) DebugStr( message ); } while(0) 294#else 295 #define Panic( message ) do { } while(0) 296 #define PanicIf( condition, message ) do { } while(0) 297#endif 298 299// Exit function on error 300#define M_ExitOnError( result ) do { if ( ( result ) != noErr ) goto ErrorExit; } while(0) 301 302// Test for passed condition and return if true 303#define M_ReturnErrorIf( condition, error ) do { if ( condition ) return( error ); } while(0) 304 305//////////////////////////////// Key Operations ///////////////////////////////// 306 307int32_t CompareKeys (BTreeControlBlockPtr btreePtr, 308 KeyPtr searchKey, 309 KeyPtr trialKey ); 310 311//////////////////////////////// Map Operations ///////////////////////////////// 312 313OSStatus AllocateNode (BTreeControlBlockPtr btreePtr, 314 u_int32_t *nodeNum); 315 316OSStatus FreeNode (BTreeControlBlockPtr btreePtr, 317 u_int32_t nodeNum); 318 319OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr, 320 u_int32_t nodes ); 321 322u_int32_t CalcMapBits (BTreeControlBlockPtr btreePtr); 323 324 325void BTUpdateReserve (BTreeControlBlockPtr btreePtr, 326 int nodes); 327 328//////////////////////////////// Misc Operations //////////////////////////////// 329 330u_int16_t CalcKeyRecordSize (u_int16_t keySize, 331 u_int16_t recSize ); 332 333OSStatus VerifyHeader (FCB *filePtr, 334 BTHeaderRec *header ); 335 336OSStatus UpdateHeader (BTreeControlBlockPtr btreePtr, 337 Boolean forceWrite ); 338 339OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr, 340 BTreeIteratorPtr iterator, 341 BlockDescriptor *left, 342 BlockDescriptor *middle, 343 BlockDescriptor *right, 344 u_int32_t *nodeNum, 345 u_int16_t *index, 346 Boolean *foundRecord ); 347 348OSStatus CheckInsertParams (FCB *filePtr, 349 BTreeIterator *iterator, 350 FSBufferDescriptor *record, 351 u_int16_t recordLen ); 352 353OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr, 354 NodeDescPtr nodePtr, 355 BTreeIterator *iterator, 356 FSBufferDescriptor *record, 357 u_int16_t recordLen, 358 Boolean *recordInserted ); 359 360OSStatus IsItAHint (BTreeControlBlockPtr btreePtr, 361 BTreeIterator *iterator, 362 Boolean *answer ); 363 364extern OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr); 365 366//////////////////////////////// Node Operations //////////////////////////////// 367 368//// Node Operations 369 370OSStatus GetNode (BTreeControlBlockPtr btreePtr, 371 u_int32_t nodeNum, 372 u_int32_t flags, 373 NodeRec *returnNodePtr ); 374 375/* Flags for GetNode() */ 376#define kGetNodeHint 0x1 /* If set, the node is being looked up using a hint */ 377 378OSStatus GetLeftSiblingNode (BTreeControlBlockPtr btreePtr, 379 NodeDescPtr node, 380 NodeRec *left ); 381 382#define GetLeftSiblingNode(btree,node,left) GetNode ((btree), ((NodeDescPtr)(node))->bLink, 0, (left)) 383 384OSStatus GetRightSiblingNode (BTreeControlBlockPtr btreePtr, 385 NodeDescPtr node, 386 NodeRec *right ); 387 388#define GetRightSiblingNode(btree,node,right) GetNode ((btree), ((NodeDescPtr)(node))->fLink, 0, (right)) 389 390 391OSStatus GetNewNode (BTreeControlBlockPtr btreePtr, 392 u_int32_t nodeNum, 393 NodeRec *returnNodePtr ); 394 395OSStatus ReleaseNode (BTreeControlBlockPtr btreePtr, 396 NodePtr nodePtr ); 397 398OSStatus TrashNode (BTreeControlBlockPtr btreePtr, 399 NodePtr nodePtr ); 400 401OSStatus UpdateNode (BTreeControlBlockPtr btreePtr, 402 NodePtr nodePtr, 403 u_int32_t transactionID, 404 u_int32_t flags ); 405 406//// Node Buffer Operations 407 408void ClearNode (BTreeControlBlockPtr btreePtr, 409 NodeDescPtr node ); 410 411u_int16_t GetNodeDataSize (BTreeControlBlockPtr btreePtr, 412 NodeDescPtr node ); 413 414u_int16_t GetNodeFreeSize (BTreeControlBlockPtr btreePtr, 415 NodeDescPtr node ); 416 417 418//// Record Operations 419 420Boolean InsertRecord (BTreeControlBlockPtr btreePtr, 421 NodeDescPtr node, 422 u_int16_t index, 423 RecordPtr recPtr, 424 u_int16_t recSize ); 425 426Boolean InsertKeyRecord (BTreeControlBlockPtr btreePtr, 427 NodeDescPtr node, 428 u_int16_t index, 429 KeyPtr keyPtr, 430 u_int16_t keyLength, 431 RecordPtr recPtr, 432 u_int16_t recSize ); 433 434void DeleteRecord (BTreeControlBlockPtr btree, 435 NodeDescPtr node, 436 u_int16_t index ); 437 438 439Boolean SearchNode (BTreeControlBlockPtr btree, 440 NodeDescPtr node, 441 KeyPtr searchKey, 442 u_int16_t *index ); 443 444OSStatus GetRecordByIndex (BTreeControlBlockPtr btree, 445 NodeDescPtr node, 446 u_int16_t index, 447 KeyPtr *keyPtr, 448 u_int8_t * *dataPtr, 449 u_int16_t *dataSize ); 450 451u_int8_t * GetRecordAddress (BTreeControlBlockPtr btree, 452 NodeDescPtr node, 453 u_int16_t index ); 454 455#define GetRecordAddress(btreePtr,node,index) ((u_int8_t *)(node) + (*(short *) ((u_int8_t *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize))) 456 457 458u_int16_t GetRecordSize (BTreeControlBlockPtr btree, 459 NodeDescPtr node, 460 u_int16_t index ); 461 462u_int32_t GetChildNodeNum (BTreeControlBlockPtr btreePtr, 463 NodeDescPtr nodePtr, 464 u_int16_t index ); 465 466void MoveRecordsLeft (u_int8_t * src, 467 u_int8_t * dst, 468 u_int16_t bytesToMove ); 469 470#define MoveRecordsLeft(src,dst,bytes) bcopy((src),(dst),(bytes)) 471 472void MoveRecordsRight (u_int8_t * src, 473 u_int8_t * dst, 474 u_int16_t bytesToMove ); 475 476#define MoveRecordsRight(src,dst,bytes) bcopy((src),(dst),(bytes)) 477 478 479//////////////////////////////// Tree Operations //////////////////////////////// 480 481OSStatus SearchTree (BTreeControlBlockPtr btreePtr, 482 BTreeKeyPtr keyPtr, 483 TreePathTable treePathTable, 484 u_int32_t *nodeNum, 485 BlockDescriptor *nodePtr, 486 u_int16_t *index ); 487 488OSStatus InsertTree (BTreeControlBlockPtr btreePtr, 489 TreePathTable treePathTable, 490 KeyPtr keyPtr, 491 u_int8_t * recPtr, 492 u_int16_t recSize, 493 BlockDescriptor *targetNode, 494 u_int16_t index, 495 u_int16_t level, 496 Boolean replacingKey, 497 u_int32_t *insertNode ); 498 499OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, 500 TreePathTable treePathTable, 501 BlockDescriptor *targetNode, 502 u_int16_t index, 503 u_int16_t level ); 504 505#endif /* __APPLE_API_PRIVATE */ 506#endif /* KERNEL */ 507#endif //__BTREESPRIVATE__ 508