/* * Copyright (c) 1999 Apple Computer, Inc. All rights reserved. * * @APPLE_LICENSE_HEADER_START@ * * "Portions Copyright (c) 1999 Apple Computer, Inc. All Rights * Reserved. This file contains Original Code and/or Modifications of * Original Code as defined in and that are subject to the Apple Public * Source License Version 1.0 (the 'License'). You may not use this file * except in compliance with the License. Please obtain a copy of the * License at http://www.apple.com/publicsource and read it before using * this file. * * The Original Code and all software distributed under the License are * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the * License for the specific language governing rights and limitations * under the License." * * @APPLE_LICENSE_HEADER_END@ */ /* File: BTree.c Contains: Implementation of public interface routines for B-tree manager. Version: HFS Plus 1.0 Written by: Gordon Sheridan and Bill Bruffey Copyright: й 1992-1999 by Apple Computer, Inc., all rights reserved. */ #include "BTree.h" #include "BTreePrivate.h" //#include "HFSInstrumentation.h" extern Boolean NodesAreContiguous(SFCB *fcb, UInt32 nodeSize); //////////////////////////////////// Globals //////////////////////////////////// /////////////////////////// BTree Module Entry Points /////////////////////////// /*------------------------------------------------------------------------------- Routine: InitBTreeModule - Initialize BTree Module Global(s). Function: Initialize BTree code, if necessary Input: none Output: none Result: noErr - success != noErr - can't happen -------------------------------------------------------------------------------*/ OSStatus InitBTreeModule(void) { return noErr; } /*------------------------------------------------------------------------------- Routine: BTInitialize - Initialize a fork for access as a B*Tree. Function: Write Header node and create any map nodes necessary to map the fork as a B*Tree. If the fork is not large enough for the header node, the FS Agent is called to extend the LEOF. Additional map nodes will be allocated if necessary to represent the size of the fork. This allows the FS Agent to specify the initial size of B*Tree files. Input: pathPtr - pointer to path control block maxKeyLength - maximum length that will be used for any key in this B*Tree nodeSize - node size for B*Tree (must be 2^n, 9 >= n >= 15) btreeType - type of B*Tree keyDescPtr - pointer to key descriptor (optional if key compare proc is used) Output: none Result: noErr - success paramErr - mandatory parameter was missing E_NoGetBlockProc - FS Agent CB has no GetNodeProcPtr E_NoReleaseBlockProc - FS Agent CB has no ReleaseNodeProcPtr E_NoSetEndOfForkProc - FS Agent CB has no SetEndOfForkProcPtr E_NoSetBlockSizeProc - FS Agent CB has no SetBlockSizeProcPtr fsBTrFileAlreadyOpenErr - fork is already open as a B*Tree fsBTInvalidKeyLengthErr - maximum key length is out of range E_BadNodeType - node size is an illegal value fsBTUnknownVersionErr - the B*Tree type is unknown by this module memFullErr - not enough memory to initialize B*Tree != noErr - failure -------------------------------------------------------------------------------*/ #if 0 OSStatus BTInitialize (FCB *filePtr, UInt16 maxKeyLength, UInt16 nodeSize, UInt8 btreeType, KeyDescriptorPtr keyDescPtr ) { OSStatus err; FSForkControlBlockPtr forkPtr; BTreeControlBlockPtr btreePtr; BlockDescriptor headerNode; HeaderPtr header; Ptr pos; FSSize minEOF, maxEOF; SetEndOfForkProcPtr setEndOfForkProc; SetBlockSizeProcPtr setBlockSizeProc; ////////////////////// Preliminary Error Checking /////////////////////////// headerNode.buffer = nil; if (pathPtr == nil) return paramErr; setEndOfForkProc = pathPtr->agentPtr->agent.setEndOfForkProc; setBlockSizeProc = pathPtr->agentPtr->agent.setBlockSizeProc; if (pathPtr->agentPtr->agent.getBlockProc == nil) return E_NoGetBlockProc; if (pathPtr->agentPtr->agent.releaseBlockProc == nil) return E_NoReleaseBlockProc; if (setEndOfForkProc == nil) return E_NoSetEndOfForkProc; if (setBlockSizeProc == nil) return E_NoSetBlockSizeProc; forkPtr = pathPtr->path.forkPtr; if (forkPtr->fork.btreePtr != nil) return fsBTrFileAlreadyOpenErr; if ((maxKeyLength == 0) || (maxKeyLength > kMaxKeyLength)) return fsBTInvalidKeyLengthErr; if ( M_IsEven (maxKeyLength)) ++maxKeyLength; // len byte + even bytes + pad byte switch (nodeSize) // node size == 512*2^n { case 512: case 1024: case 2048: case 4096: case 8192: case 16384: case 32768: break; default: return E_BadNodeType; } switch (btreeType) { case kHFSBTreeType: case kUserBTreeType: case kReservedBTreeType: break; default: return fsBTUnknownVersionErr; //ее right? } //////////////////////// Allocate Control Block ///////////////////////////// M_RESIDENT_ALLOCATE_FIXED_CLEAR( &btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType ); if (btreePtr == nil) { err = memFullErr; goto ErrorExit; } btreePtr->version = kBTreeVersion; //ее what is the version? btreePtr->reserved1 = 0; btreePtr->flags = 0; btreePtr->attributes = 0; btreePtr->forkPtr = forkPtr; btreePtr->keyCompareProc = nil; btreePtr->keyDescPtr = keyDescPtr; btreePtr->btreeType = btreeType; btreePtr->treeDepth = 0; btreePtr->rootNode = 0; btreePtr->leafRecords = 0; btreePtr->firstLeafNode = 0; btreePtr->lastLeafNode = 0; btreePtr->nodeSize = nodeSize; btreePtr->maxKeyLength = maxKeyLength; btreePtr->totalNodes = 1; // so ExtendBTree adds maps nodes properly btreePtr->freeNodes = 0; btreePtr->writeCount = 1; // , for BTree scanner // set block size = nodeSize err = setBlockSizeProc (forkPtr, nodeSize); M_ExitOnError (err); ////////////////////////////// Check LEOF /////////////////////////////////// minEOF = nodeSize; if ( forkPtr->fork.logicalEOF < minEOF ) { // allocate more space if necessary maxEOF 0xFFFFFFFFL; err = setEndOfForkProc (forkPtr, minEOF, maxEOF); M_ExitOnError (err); }; //////////////////////// Initialize Header Node ///////////////////////////// err = GetNewNode (btreePtr, kHeaderNodeNum, &headerNode); M_ExitOnError (err); header = headerNode.buffer; header->node.type = kHeaderNode; header->node.numRecords = 3; // header rec, key desc, map rec header->nodeSize = nodeSize; header->maxKeyLength = maxKeyLength; header->btreeType = btreeType; header->totalNodes = btreePtr->totalNodes; header->freeNodes = btreePtr->totalNodes - 1; // ignore header->clumpSize; //ее rename this field? // mark header node allocated in map record pos = ((Ptr)headerNode.buffer) + kHeaderMapRecOffset; *pos = 0x80; // set node offsets ( nodeSize-8, F8, 78, 0E) pos = ((Ptr)headerNode.buffer) + nodeSize; pos -= 2; *((UInt16 *)pos) = kHeaderRecOffset; pos -= 2; *((UInt16 *)pos) = kKeyDescRecOffset; pos -= 2; *((UInt16 *)pos) = kHeaderMapRecOffset; pos -= 2; *((UInt16 *)pos) = nodeSize - 8; ///////////////////// Copy Key Descriptor To Header ///////////////////////// #if SupportsKeyDescriptors if (keyDescPtr != nil) { err = CheckKeyDescriptor (keyDescPtr, maxKeyLength); M_ExitOnError (err); // copy to header node pos = ((Ptr)headerNode.buffer) + kKeyDescRecOffset; CopyMemory (keyDescPtr, pos, keyDescPtr->length + 1); } #endif // write header node err = UpdateNode (btreePtr, &headerNode); M_ExitOnError (err); ////////////////////////// Allocate Map Nodes /////////////////////////////// err = ExtendBTree (btreePtr, forkPtr->fork.logicalEOF.lo / nodeSize); // sets totalNodes M_ExitOnError (err); ////////////////////////////// Close BTree ////////////////////////////////// err = UpdateHeader (btreePtr); M_ExitOnError (err); pathPtr->path.forkPtr->fork.btreePtr = nil; M_RESIDENT_DEALLOCATE_FIXED( btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType ); return noErr; /////////////////////// Error - Clean up and Exit /////////////////////////// ErrorExit: (void) ReleaseNode (btreePtr, &headerNode); if (btreePtr != nil) M_RESIDENT_DEALLOCATE_FIXED( btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType ); return err; } #endif /*------------------------------------------------------------------------------- Routine: BTOpenPath - Open a file for access as a B*Tree. Function: Create BTree control block for a file, if necessary. Validates the file to be sure it looks like a BTree file. Input: filePtr - pointer to file to open as a B-tree keyCompareProc - pointer to client's KeyCompare function getBlockProc - pointer to client's GetBlock function releaseBlockProc - pointer to client's ReleaseBlock function setEndOfForkProc - pointer to client's SetEOF function Result: noErr - success paramErr - required ptr was nil fsBTInvalidFileErr - memFullErr - != noErr - failure -------------------------------------------------------------------------------*/ OSStatus BTOpenPath (SFCB *filePtr, KeyCompareProcPtr keyCompareProc, GetBlockProcPtr getBlockProc, ReleaseBlockProcPtr releaseBlockProc, SetEndOfForkProcPtr setEndOfForkProc, SetBlockSizeProcPtr setBlockSizeProc ) { OSStatus err; BTreeControlBlockPtr btreePtr; BTHeaderRec *header; NodeRec nodeRec; // LogStartTime(kTraceOpenBTree); ////////////////////// Preliminary Error Checking /////////////////////////// if ( filePtr == nil || getBlockProc == nil || releaseBlockProc == nil || setEndOfForkProc == nil || setBlockSizeProc == nil ) { return paramErr; } if ( filePtr->fcbBtree != nil ) // already has a BTreeCB return noErr; // is file large enough to contain header node? if ( filePtr->fcbLogicalSize < kMinNodeSize ) return fsBTInvalidFileErr; //ее or E_BadHeader? //////////////////////// Allocate Control Block ///////////////////////////// btreePtr = (BTreeControlBlock*) AllocateClearMemory( sizeof( BTreeControlBlock ) ); if (btreePtr == nil) { Panic ("\pBTOpen: no memory for btreePtr."); return memFullErr; } btreePtr->getBlockProc = getBlockProc; btreePtr->releaseBlockProc = releaseBlockProc; btreePtr->setEndOfForkProc = setEndOfForkProc; btreePtr->keyCompareProc = keyCompareProc; /////////////////////////// Read Header Node //////////////////////////////// nodeRec.buffer = nil; // so we can call ReleaseNode btreePtr->fcbPtr = filePtr; filePtr->fcbBtree = (void *) btreePtr; // attach btree cb to file // it is now safe to call M_ExitOnError (err) err = setBlockSizeProc (btreePtr->fcbPtr, kMinNodeSize); M_ExitOnError (err); err = getBlockProc (btreePtr->fcbPtr, kHeaderNodeNum, kGetBlock, &nodeRec ); PanicIf (err != noErr, "\pBTOpen: getNodeProc returned error getting header node."); M_ExitOnError (err); header = (BTHeaderRec*) (nodeRec.buffer + sizeof(BTNodeDescriptor)); ///////////////////////////// verify header ///////////////////////////////// err = VerifyHeader (filePtr, header); M_ExitOnError (err); ///////////////////// Initalize fields from header ////////////////////////// PanicIf ( (filePtr->fcbVolume->vcbSigWord != 'BD') && (btreePtr->nodeSize == 512), "\p BTOpenPath: wrong node size for HFS+ volume!"); btreePtr->treeDepth = header->treeDepth; btreePtr->rootNode = header->rootNode; btreePtr->leafRecords = header->leafRecords; btreePtr->firstLeafNode = header->firstLeafNode; btreePtr->lastLeafNode = header->lastLeafNode; btreePtr->nodeSize = header->nodeSize; btreePtr->maxKeyLength = header->maxKeyLength; btreePtr->totalNodes = header->totalNodes; btreePtr->freeNodes = header->freeNodes; // ignore header->clumpSize; //ее rename this field? btreePtr->btreeType = header->btreeType; btreePtr->attributes = header->attributes; if ( btreePtr->maxKeyLength > 40 ) btreePtr->attributes |= (kBTBigKeysMask + kBTVariableIndexKeysMask); //ее we need a way to save these attributes /////////////////////// Initialize dynamic fields /////////////////////////// btreePtr->version = kBTreeVersion; btreePtr->flags = 0; btreePtr->writeCount = 1; // , for BTree scanner btreePtr->numGetNodes = 1; // for earlier call to getNodeProc /////////////////////////// Check Header Node /////////////////////////////// //ее set kBadClose attribute bit, and UpdateNode // if nodeSize is 512 then we don't need to release, just CheckNode if ( btreePtr->nodeSize == kMinNodeSize ) { err = CheckNode (btreePtr, nodeRec.buffer); M_ExitOnError (err); } else { err = setBlockSizeProc (btreePtr->fcbPtr, btreePtr->nodeSize); M_ExitOnError (err); #if BSD /* * Need to use kTrashBlock option to force the * buffer cache to re-read the entire node */ err = releaseBlockProc(btreePtr->fcbPtr, &nodeRec, kTrashBlock); #else err = ReleaseNode (btreePtr, &nodeRec); #endif err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec ); // calls CheckNode... M_ExitOnError (err); } //ее total nodes * node size <= LEOF? ////////////////////////// Get Key Descriptor /////////////////////////////// #if SupportsKeyDescriptors if ( keyCompareProc == nil ) // if no key compare proc then get key descriptor { err = GetKeyDescriptor (btreePtr, nodeRec.buffer); //ее it should check amount of memory allocated... M_ExitOnError (err); err = CheckKeyDescriptor (btreePtr->keyDescPtr, btreePtr->maxKeyLength); M_ExitOnError (err); } else #endif { btreePtr->keyDescPtr = nil; // clear it so we don't dispose garbage later } err = ReleaseNode (btreePtr, &nodeRec); M_ExitOnError (err); #if BSD /* * Under Mac OS, b-tree nodes can be non-contiguous on disk when the * allocation block size is smaller than the b-tree node size. */ if ( !NodesAreContiguous(filePtr, btreePtr->nodeSize) ) return fsBTInvalidNodeErr; #endif //////////////////////////////// Success //////////////////////////////////// //ее align LEOF to multiple of node size? - just on close // LogEndTime(kTraceOpenBTree, noErr); return noErr; /////////////////////// Error - Clean up and Exit /////////////////////////// ErrorExit: filePtr->fcbBtree = nil; (void) ReleaseNode (btreePtr, &nodeRec); DisposeMemory( btreePtr ); // LogEndTime(kTraceOpenBTree, err); return err; } /*------------------------------------------------------------------------------- Routine: BTClosePath - Flush BTree Header and Deallocate Memory for BTree. Function: Flush the BTreeControlBlock fields to header node, and delete BTree control block and key descriptor associated with the file if filePtr is last path of type kBTreeType ('btre'). Input: filePtr - pointer to file to delete BTree control block for. Result: noErr - success fsBTInvalidFileErr - != noErr - failure -------------------------------------------------------------------------------*/ OSStatus BTClosePath (SFCB *filePtr) { OSStatus err; BTreeControlBlockPtr btreePtr; #if 0 FSPathControlBlockPtr tempPath; Boolean otherBTreePathsOpen; #endif // LogStartTime(kTraceCloseBTree); btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; if (btreePtr == nil) return fsBTInvalidFileErr; ////////////////////// Check for other BTree Paths ////////////////////////// #if 0 //ее Need replacement field for pathType otherBTreePathsOpen = false; tempPath = forkPtr->fork.pathList.head; while ( (tempPath != (FSPathControlBlockPtr) &forkPtr->fork.pathList) && (otherBTreePathsOpen == false) ) { if ((tempPath != pathPtr) && (tempPath->path.pathType == kBTreeType)) { otherBTreePathsOpen = true; break; // done with loop check } tempPath = tempPath->next; } ////////////////////////// Update Header Node /////////////////////////////// if (otherBTreePathsOpen == true) { err = UpdateHeader (btreePtr); // update header even if we aren't closing return err; // we only clean up after the last user... } #endif btreePtr->attributes &= ~kBTBadCloseMask; // clear "bad close" attribute bit err = UpdateHeader (btreePtr); M_ExitOnError (err); #if SupportsKeyDescriptors if (btreePtr->keyDescPtr != nil) // deallocate keyDescriptor, if any { DisposeMemory( btreePtr->keyDescPtr ); } #endif DisposeMemory( btreePtr ); filePtr->fcbBtree = nil; // LogEndTime(kTraceCloseBTree, noErr); return noErr; /////////////////////// Error - Clean Up and Exit /////////////////////////// ErrorExit: // LogEndTime(kTraceCloseBTree, err); return err; } /*------------------------------------------------------------------------------- Routine: BTSearchRecord - Search BTree for a record with a matching key. Function: Search for position in B*Tree indicated by searchKey. If a valid node hint is provided, it will be searched first, then SearchTree will be called. If a BTreeIterator is provided, it will be set to the position found as a result of the search. If a record exists at that position, and a BufferDescriptor is supplied, the record will be copied to the buffer (as much as will fit), and recordLen will be set to the length of the record. If an error other than fsBTRecordNotFoundErr occurs, the BTreeIterator, if any, is invalidated, and recordLen is set to 0. Input: pathPtr - pointer to path for BTree file. searchKey - pointer to search key to match. hintPtr - pointer to hint (may be nil) Output: record - pointer to BufferDescriptor containing record recordLen - length of data at recordPtr iterator - pointer to BTreeIterator indicating position result of search Result: noErr - success, record contains copy of record found fsBTRecordNotFoundErr - record was not found, no data copied fsBTInvalidFileErr - no BTreeControlBlock is allocated for the fork fsBTInvalidKeyLengthErr - != noErr - failure -------------------------------------------------------------------------------*/ OSStatus BTSearchRecord (SFCB *filePtr, BTreeIterator *searchIterator, UInt32 heuristicHint, FSBufferDescriptor *record, UInt16 *recordLen, BTreeIterator *resultIterator ) { OSStatus err; BTreeControlBlockPtr btreePtr; TreePathTable treePathTable; UInt32 nodeNum; BlockDescriptor node; UInt16 index; BTreeKeyPtr keyPtr; RecordPtr recordPtr; UInt16 len; Boolean foundRecord; Boolean validHint; // LogStartTime(kTraceSearchBTree); if (filePtr == nil) return paramErr; if (searchIterator == nil) return paramErr; btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; if (btreePtr == nil) return fsBTInvalidFileErr; #if SupportsKeyDescriptors if (btreePtr->keyCompareProc == nil) // CheckKey if we using Key Descriptor { err = CheckKey (&searchIterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength); M_ExitOnError (err); } #endif foundRecord = false; ////////////////////////////// Take A Hint ////////////////////////////////// err = IsItAHint (btreePtr, searchIterator, &validHint); M_ExitOnError (err); if (validHint) { nodeNum = searchIterator->hint.nodeNum; err = GetNode (btreePtr, nodeNum, &node); if( err == noErr ) { if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode && ((BTNodeDescriptor*) node.buffer)->numRecords > 0 ) { foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index); //ее if !foundRecord, we could still skip tree search if ( 0 < index < numRecords ) } if (foundRecord == false) { err = ReleaseNode (btreePtr, &node); M_ExitOnError (err); } else { ++btreePtr->numValidHints; } } if( foundRecord == false ) (void) BTInvalidateHint( searchIterator ); } ////////////////////////////// Try the heuristicHint ////////////////////////////////// if ( (foundRecord == false) && (heuristicHint != kInvalidMRUCacheKey) && (nodeNum != heuristicHint) ) { // LogStartTime(kHeuristicHint); nodeNum = heuristicHint; err = GetNode (btreePtr, nodeNum, &node); if( err == noErr ) { if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode && ((BTNodeDescriptor*) node.buffer)->numRecords > 0 ) { foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index); } if (foundRecord == false) { err = ReleaseNode (btreePtr, &node); M_ExitOnError (err); } } // LogEndTime(kHeuristicHint, (foundRecord == false)); } //////////////////////////// Search The Tree //////////////////////////////// if (foundRecord == false) { err = SearchTree ( btreePtr, &searchIterator->key, treePathTable, &nodeNum, &node, &index); switch (err) { case noErr: foundRecord = true; break; case fsBTRecordNotFoundErr: break; default: goto ErrorExit; } } //////////////////////////// Get the Record ///////////////////////////////// if (foundRecord == true) { //ее Should check for errors! Or BlockMove could choke on recordPtr!!! GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len); if (recordLen != nil) *recordLen = len; if (record != nil) { ByteCount recordSize; recordSize = record->itemCount * record->itemSize; PanicIf(len > recordSize, "\pBTSearchRecord: truncating record!"); if (len > recordSize) len = recordSize; CopyMemory (recordPtr, record->bufferAddress, len); } } /////////////////////// Success - Update Iterator /////////////////////////// if (resultIterator != nil) { resultIterator->hint.writeCount = btreePtr->writeCount; resultIterator->hint.nodeNum = nodeNum; resultIterator->hint.index = index; resultIterator->hint.reserved1 = 0; resultIterator->hint.reserved2 = 0; resultIterator->version = 0; resultIterator->reserved = 0; // copy the key in the BTree when found rather than searchIterator->key to get proper case/diacriticals if (foundRecord == true) CopyMemory ((Ptr)keyPtr, (Ptr)&resultIterator->key, CalcKeySize(btreePtr, keyPtr)); else CopyMemory ((Ptr)&searchIterator->key, (Ptr)&resultIterator->key, CalcKeySize(btreePtr, &searchIterator->key)); } err = ReleaseNode (btreePtr, &node); M_ExitOnError (err); // LogEndTime(kTraceSearchBTree, (foundRecord == false)); if (foundRecord == false) return fsBTRecordNotFoundErr; else return noErr; /////////////////////// Error - Clean Up and Exit /////////////////////////// ErrorExit: if (recordLen != nil) *recordLen = 0; if (resultIterator != nil) { resultIterator->hint.writeCount = 0; resultIterator->hint.nodeNum = 0; resultIterator->hint.index = 0; resultIterator->hint.reserved1 = 0; resultIterator->hint.reserved2 = 0; resultIterator->version = 0; resultIterator->reserved = 0; resultIterator->key.length16 = 0; // zero out two bytes to cover both types of keys } if ( err == fsBTEmptyErr ) err = fsBTRecordNotFoundErr; // LogEndTime(kTraceSearchBTree, err); return err; } /*------------------------------------------------------------------------------- Routine: BTIterateRecord - Find the first, next, previous, or last record. Function: Find the first, next, previous, or last record in the BTree Input: pathPtr - pointer to path iterate records for. operation - iteration operation (first,next,prev,last) iterator - pointer to iterator indicating start position Output: iterator - iterator is updated to indicate new position newKeyPtr - pointer to buffer to copy key found by iteration record - pointer to buffer to copy record found by iteration recordLen - length of record Result: noErr - success != noErr - failure -------------------------------------------------------------------------------*/ OSStatus BTIterateRecord (SFCB *filePtr, BTreeIterationOperation operation, BTreeIterator *iterator, FSBufferDescriptor *record, UInt16 *recordLen ) { OSStatus err; BTreeControlBlockPtr btreePtr; BTreeKeyPtr keyPtr; RecordPtr recordPtr; UInt16 len; Boolean foundRecord; UInt32 nodeNum; BlockDescriptor left, node, right; UInt16 index; // LogStartTime(kTraceGetBTreeRecord); ////////////////////////// Priliminary Checks /////////////////////////////// left.buffer = nil; right.buffer = nil; node.buffer = nil; if (filePtr == nil) { return paramErr; } btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; if (btreePtr == nil) { return fsBTInvalidFileErr; //ее handle properly } if ((operation != kBTreeFirstRecord) && (operation != kBTreeNextRecord) && (operation != kBTreeCurrentRecord) && (operation != kBTreePrevRecord) && (operation != kBTreeLastRecord)) { err = fsInvalidIterationMovmentErr; goto ErrorExit; } /////////////////////// Find First or Last Record /////////////////////////// if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord)) { if (operation == kBTreeFirstRecord) nodeNum = btreePtr->firstLeafNode; else nodeNum = btreePtr->lastLeafNode; if (nodeNum == 0) { err = fsBTEmptyErr; goto ErrorExit; } err = GetNode (btreePtr, nodeNum, &node); M_ExitOnError (err); if ( ((NodeDescPtr) node.buffer)->kind != kBTLeafNode || ((NodeDescPtr) node.buffer)->numRecords <= 0 ) { err = ReleaseNode (btreePtr, &node); M_ExitOnError (err); err = fsBTInvalidNodeErr; goto ErrorExit; } if (operation == kBTreeFirstRecord) index = 0; else index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1; goto CopyData; //ее is there a cleaner way? } //////////////////////// Find Iterator Position ///////////////////////////// err = FindIteratorPosition (btreePtr, iterator, &left, &node, &right, &nodeNum, &index, &foundRecord); M_ExitOnError (err); ///////////////////// Find Next Or Previous Record ////////////////////////// if (operation == kBTreePrevRecord) { if (index > 0) { --index; } else { if (left.buffer == nil) { nodeNum = ((NodeDescPtr) node.buffer)->bLink; if ( nodeNum > 0) { err = GetNode (btreePtr, nodeNum, &left); M_ExitOnError (err); } else { err = fsBTStartOfIterationErr; goto ErrorExit; } } // Before we stomp on "right", we'd better release it if needed if (right.buffer != nil) { err = ReleaseNode(btreePtr, &right); M_ExitOnError(err); } right = node; node = left; left.buffer = nil; index = ((NodeDescPtr) node.buffer)->numRecords -1; } } else if (operation == kBTreeNextRecord) { if ((foundRecord != true) && (((NodeDescPtr) node.buffer)->fLink == 0) && (index == ((NodeDescPtr) node.buffer)->numRecords)) { err = fsBTEndOfIterationErr; goto ErrorExit; } // we did not find the record but the index is already positioned correctly if ((foundRecord == false) && (index != ((NodeDescPtr) node.buffer)->numRecords)) goto CopyData; // we found the record OR we have to look in the next node if (index < ((NodeDescPtr) node.buffer)->numRecords -1) { ++index; } else { if (right.buffer == nil) { nodeNum = ((NodeDescPtr) node.buffer)->fLink; if ( nodeNum > 0) { err = GetNode (btreePtr, nodeNum, &right); M_ExitOnError (err); } else { err = fsBTEndOfIterationErr; goto ErrorExit; } } // Before we stomp on "left", we'd better release it if needed if (left.buffer != nil) { err = ReleaseNode(btreePtr, &left); M_ExitOnError(err); } left = node; node = right; right.buffer = nil; index = 0; } } else // operation == kBTreeCurrentRecord { // make sure we have something... if ((foundRecord != true) && (index >= ((NodeDescPtr) node.buffer)->numRecords)) { err = fsBTEndOfIterationErr; goto ErrorExit; } } //////////////////// Copy Record And Update Iterator //////////////////////// CopyData: // added check for errors err = GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len); M_ExitOnError (err); if (recordLen != nil) *recordLen = len; if (record != nil) { ByteCount recordSize; recordSize = record->itemCount * record->itemSize; PanicIf(len > recordSize, "\pBTIterateRecord: truncating record!"); if (len > recordSize) len = recordSize; CopyMemory (recordPtr, record->bufferAddress, len); } if (iterator != nil) // first & last do not require iterator { iterator->hint.writeCount = btreePtr->writeCount; iterator->hint.nodeNum = nodeNum; iterator->hint.index = index; iterator->hint.reserved1 = 0; iterator->hint.reserved2 = 0; iterator->version = 0; iterator->reserved = 0; CopyMemory ((Ptr)keyPtr, (Ptr)&iterator->key, CalcKeySize(btreePtr, keyPtr)); } ///////////////////////////// Release Nodes ///////////////////////////////// err = ReleaseNode (btreePtr, &node); M_ExitOnError (err); if (left.buffer != nil) { err = ReleaseNode (btreePtr, &left); M_ExitOnError (err); } if (right.buffer != nil) { err = ReleaseNode (btreePtr, &right); M_ExitOnError (err); } // LogEndTime(kTraceGetBTreeRecord, noErr); return noErr; /////////////////////// Error - Clean Up and Exit /////////////////////////// ErrorExit: (void) ReleaseNode (btreePtr, &left); (void) ReleaseNode (btreePtr, &node); (void) ReleaseNode (btreePtr, &right); if (recordLen != nil) *recordLen = 0; if (iterator != nil) { iterator->hint.writeCount = 0; iterator->hint.nodeNum = 0; iterator->hint.index = 0; iterator->hint.reserved1 = 0; iterator->hint.reserved2 = 0; iterator->version = 0; iterator->reserved = 0; iterator->key.length16 = 0; } if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr ) err = fsBTRecordNotFoundErr; // LogEndTime(kTraceGetBTreeRecord, err); return err; } //////////////////////////////// BTInsertRecord ///////////////////////////////// OSStatus BTInsertRecord (SFCB *filePtr, BTreeIterator *iterator, FSBufferDescriptor *record, UInt16 recordLen ) { OSStatus err; BTreeControlBlockPtr btreePtr; TreePathTable treePathTable; SInt32 nodesNeeded; BlockDescriptor nodeRec; UInt32 insertNodeNum; UInt16 index; Boolean recordFit; ////////////////////////// Priliminary Checks /////////////////////////////// nodeRec.buffer = nil; // so we can call ReleaseNode err = CheckInsertParams (filePtr, iterator, record, recordLen); if (err != noErr) return err; // LogStartTime(kTraceInsertBTreeRecord); btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; ///////////////////////// Find Insert Position ////////////////////////////// // always call SearchTree for Insert err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index); switch (err) // set/replace/insert decision point { case noErr: err = fsBTDuplicateRecordErr; goto ErrorExit; case fsBTRecordNotFoundErr: break; case fsBTEmptyErr: // if tree empty add 1st leaf node if (btreePtr->freeNodes == 0) { err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1); M_ExitOnError (err); } err = AllocateNode (btreePtr, &insertNodeNum); M_ExitOnError (err); err = GetNewNode (btreePtr, insertNodeNum, &nodeRec); M_ExitOnError (err); ((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode; ((NodeDescPtr)nodeRec.buffer)->height = 1; recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0, &iterator->key, KeyLength(btreePtr, &iterator->key), record->bufferAddress, recordLen ); if (recordFit != true) { err = fsBTRecordTooLargeErr; goto ErrorExit; } err = UpdateNode (btreePtr, &nodeRec); M_ExitOnError (err); // update BTreeControlBlock btreePtr->treeDepth = 1; btreePtr->rootNode = insertNodeNum; btreePtr->firstLeafNode = insertNodeNum; btreePtr->lastLeafNode = insertNodeNum; M_BTreeHeaderDirty (btreePtr); goto Success; default: goto ErrorExit; } if (index > 0) { recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index, &iterator->key, KeyLength(btreePtr, &iterator->key), record->bufferAddress, recordLen); if (recordFit == true) { err = UpdateNode (btreePtr, &nodeRec); M_ExitOnError (err); goto Success; } } /////////////////////// Extend File If Necessary //////////////////////////// nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //ее math limit if (nodesNeeded > 0) { nodesNeeded += btreePtr->totalNodes; if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too! ++nodesNeeded; err = ExtendBTree (btreePtr, nodesNeeded); M_ExitOnError (err); } // no need to delete existing record err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress, recordLen, &nodeRec, index, 1, kInsertRecord, &insertNodeNum); M_ExitOnError (err); //////////////////////////////// Success //////////////////////////////////// Success: ++btreePtr->writeCount; // ++btreePtr->leafRecords; M_BTreeHeaderDirty (btreePtr); // create hint iterator->hint.writeCount = btreePtr->writeCount; // unused until iterator->hint.nodeNum = insertNodeNum; iterator->hint.index = 0; // unused iterator->hint.reserved1 = 0; iterator->hint.reserved2 = 0; // LogEndTime(kTraceInsertBTreeRecord, noErr); return noErr; ////////////////////////////// Error Exit /////////////////////////////////// ErrorExit: (void) ReleaseNode (btreePtr, &nodeRec); iterator->hint.writeCount = 0; iterator->hint.nodeNum = 0; iterator->hint.index = 0; iterator->hint.reserved1 = 0; iterator->hint.reserved2 = 0; if (err == fsBTEmptyErr) err = fsBTRecordNotFoundErr; // LogEndTime(kTraceInsertBTreeRecord, err); return err; } ////////////////////////////////// BTSetRecord ////////////////////////////////// #if 0 OSStatus BTSetRecord (SFCB *filePtr, BTreeIterator *iterator, FSBufferDescriptor *record, UInt16 recordLen ) { OSStatus err; BTreeControlBlockPtr btreePtr; TreePathTable treePathTable; SInt32 nodesNeeded; BlockDescriptor nodeRec; UInt32 insertNodeNum; UInt16 index; Boolean recordFound = false; Boolean recordFit; Boolean operation; Boolean validHint; ////////////////////////// Priliminary Checks /////////////////////////////// nodeRec.buffer = nil; // so we can call ReleaseNode err = CheckInsertParams (filePtr, iterator, record, recordLen); if (err != noErr) return err; btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; ///////////////////////// Find Insert Position ////////////////////////////// err = IsItAHint (btreePtr, iterator, &validHint); M_ExitOnError (err); if (validHint) { insertNodeNum = iterator->hint.nodeNum; err = GetNode (btreePtr, insertNodeNum, &nodeRec); if( err == noErr ) { err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit); M_ExitOnError (err); if (recordFit) { err = UpdateNode (btreePtr, &nodeRec); M_ExitOnError (err); recordFound = true; ++btreePtr->numValidHints; goto Success; } // else else { (void) BTInvalidateHint( iterator ); } err = ReleaseNode (btreePtr, &nodeRec); M_ExitOnError (err); } } err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index); switch (err) // set/replace/insert decision point { case noErr: recordFound = true; break; case fsBTRecordNotFoundErr: break; case fsBTEmptyErr: // if tree empty add 1st leaf node if (btreePtr->freeNodes == 0) { err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1); M_ExitOnError (err); } err = AllocateNode (btreePtr, &insertNodeNum); M_ExitOnError (err); err = GetNewNode (btreePtr, insertNodeNum, &nodeRec); M_ExitOnError (err); ((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode; ((NodeDescPtr)nodeRec.buffer)->height = 1; recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0, &iterator->key, KeyLength(btreePtr, &iterator->key), record->bufferAddress, recordLen ); if (recordFit != true) { err = fsBTRecordTooLargeErr; goto ErrorExit; } err = UpdateNode (btreePtr, &nodeRec); M_ExitOnError (err); // update BTreeControlBlock btreePtr->rootNode = insertNodeNum; btreePtr->treeDepth = 1; btreePtr->flags |= kBTHeaderDirty; goto Success; default: goto ErrorExit; } if (recordFound == true) // Simple Replace - optimization avoids unecessary ExtendBTree { err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit); M_ExitOnError (err); if (recordFit) { err = UpdateNode (btreePtr, &nodeRec); M_ExitOnError (err); goto Success; } } /////////////////////// Extend File If Necessary //////////////////////////// nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //ее math limit if (nodesNeeded > 0) { nodesNeeded += btreePtr->totalNodes; if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too! ++nodesNeeded; err = ExtendBTree (btreePtr, nodesNeeded); M_ExitOnError (err); } if (recordFound == true) // Delete existing record { DeleteRecord (btreePtr, nodeRec.buffer, index); operation = kReplaceRecord; } else { operation = kInsertRecord; } err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress, recordLen, &nodeRec, index, 1, operation, &insertNodeNum); M_ExitOnError (err); ++btreePtr->writeCount; // writeCount changes only if the tree structure changed Success: if (recordFound == false) { ++btreePtr->leafRecords; M_BTreeHeaderDirty (btreePtr); } // create hint iterator->hint.writeCount = btreePtr->writeCount; // unused until iterator->hint.nodeNum = insertNodeNum; iterator->hint.index = 0; // unused iterator->hint.reserved1 = 0; iterator->hint.reserved2 = 0; return noErr; ////////////////////////////// Error Exit /////////////////////////////////// ErrorExit: (void) ReleaseNode (btreePtr, &nodeRec); iterator->hint.writeCount = 0; iterator->hint.nodeNum = 0; iterator->hint.index = 0; iterator->hint.reserved1 = 0; iterator->hint.reserved2 = 0; return err; } #endif //////////////////////////////// BTReplaceRecord //////////////////////////////// OSStatus BTReplaceRecord (SFCB *filePtr, BTreeIterator *iterator, FSBufferDescriptor *record, UInt16 recordLen ) { OSStatus err; BTreeControlBlockPtr btreePtr; TreePathTable treePathTable; SInt32 nodesNeeded; BlockDescriptor nodeRec; UInt32 insertNodeNum; UInt16 index; Boolean recordFit; Boolean validHint; ////////////////////////// Priliminary Checks /////////////////////////////// nodeRec.buffer = nil; // so we can call ReleaseNode err = CheckInsertParams (filePtr, iterator, record, recordLen); if (err != noErr) return err; // LogStartTime(kTraceReplaceBTreeRecord); btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; ////////////////////////////// Take A Hint ////////////////////////////////// err = IsItAHint (btreePtr, iterator, &validHint); M_ExitOnError (err); if (validHint) { insertNodeNum = iterator->hint.nodeNum; err = GetNode (btreePtr, insertNodeNum, &nodeRec); if( err == noErr ) { err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit); M_ExitOnError (err); if (recordFit) { err = UpdateNode (btreePtr, &nodeRec); M_ExitOnError (err); ++btreePtr->numValidHints; goto Success; } else { (void) BTInvalidateHint( iterator ); } err = ReleaseNode (btreePtr, &nodeRec); M_ExitOnError (err); } else { (void) BTInvalidateHint( iterator ); } } ////////////////////////////// Get A Clue /////////////////////////////////// err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index); M_ExitOnError (err); // record must exit for Replace // optimization - if simple replace will work then don't extend btree // ее if we tried this before, and failed because it wouldn't fit then we shouldn't try this again... err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit); M_ExitOnError (err); if (recordFit) { err = UpdateNode (btreePtr, &nodeRec); M_ExitOnError (err); goto Success; } //////////////////////////// Make Some Room ///////////////////////////////// nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //ее math limit if (nodesNeeded > 0) { nodesNeeded += btreePtr->totalNodes; if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too! ++nodesNeeded; err = ExtendBTree (btreePtr, nodesNeeded); M_ExitOnError (err); } DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress, recordLen, &nodeRec, index, 1, kReplaceRecord, &insertNodeNum); M_ExitOnError (err); ++btreePtr->writeCount; // writeCount changes only if the tree structure changed Success: // create hint iterator->hint.writeCount = btreePtr->writeCount; // unused until iterator->hint.nodeNum = insertNodeNum; iterator->hint.index = 0; // unused iterator->hint.reserved1 = 0; iterator->hint.reserved2 = 0; // LogEndTime(kTraceReplaceBTreeRecord, noErr); return noErr; ////////////////////////////// Error Exit /////////////////////////////////// ErrorExit: (void) ReleaseNode (btreePtr, &nodeRec); iterator->hint.writeCount = 0; iterator->hint.nodeNum = 0; iterator->hint.index = 0; iterator->hint.reserved1 = 0; iterator->hint.reserved2 = 0; // LogEndTime(kTraceReplaceBTreeRecord, err); return err; } //////////////////////////////// BTDeleteRecord ///////////////////////////////// OSStatus BTDeleteRecord (SFCB *filePtr, BTreeIterator *iterator ) { OSStatus err; BTreeControlBlockPtr btreePtr; TreePathTable treePathTable; BlockDescriptor nodeRec; UInt32 nodeNum; UInt16 index; // LogStartTime(kTraceDeleteBTreeRecord); ////////////////////////// Priliminary Checks /////////////////////////////// nodeRec.buffer = nil; // so we can call ReleaseNode M_ReturnErrorIf (filePtr == nil, paramErr); M_ReturnErrorIf (iterator == nil, paramErr); btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; if (btreePtr == nil) { err = fsBTInvalidFileErr; goto ErrorExit; } #if SupportsKeyDescriptors if (btreePtr->keyDescPtr != nil) { err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength); M_ExitOnError (err); } #endif /////////////////////////////// Find Key //////////////////////////////////// //ее check hint for simple delete case (index > 0, numRecords > 2) err = SearchTree (btreePtr, &iterator->key, treePathTable, &nodeNum, &nodeRec, &index); M_ExitOnError (err); // record must exit for Delete ///////////////////////////// Delete Record ///////////////////////////////// err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1); M_ExitOnError (err); //Success: ++btreePtr->writeCount; // --btreePtr->leafRecords; M_BTreeHeaderDirty (btreePtr); iterator->hint.nodeNum = 0; // LogEndTime(kTraceDeleteBTreeRecord, noErr); return noErr; ////////////////////////////// Error Exit /////////////////////////////////// ErrorExit: (void) ReleaseNode (btreePtr, &nodeRec); // LogEndTime(kTraceDeleteBTreeRecord, err); return err; } OSStatus BTGetInformation (SFCB *filePtr, UInt16 version, BTreeInfoRec *info ) { #pragma unused (version) BTreeControlBlockPtr btreePtr; M_ReturnErrorIf (filePtr == nil, paramErr); btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr); M_ReturnErrorIf (info == nil, paramErr); //ее check version? info->nodeSize = btreePtr->nodeSize; info->maxKeyLength = btreePtr->maxKeyLength; info->treeDepth = btreePtr->treeDepth; info->numRecords = btreePtr->leafRecords; info->numNodes = btreePtr->totalNodes; info->numFreeNodes = btreePtr->freeNodes; info->keyDescriptor = btreePtr->keyDescPtr; //ее this won't do at all... info->reserved = 0; if (btreePtr->keyDescPtr == nil) info->keyDescLength = 0; else info->keyDescLength = (UInt32) btreePtr->keyDescPtr->length; return noErr; } /*------------------------------------------------------------------------------- Routine: BTFlushPath - Flush BTreeControlBlock to Header Node. Function: Brief_description_of_the_function_and_any_side_effects Input: pathPtr - pointer to path control block for B*Tree file to flush Output: none Result: noErr - success != noErr - failure -------------------------------------------------------------------------------*/ OSStatus BTFlushPath (SFCB *filePtr) { OSStatus err; BTreeControlBlockPtr btreePtr; // LogStartTime(kTraceFlushBTree); M_ReturnErrorIf (filePtr == nil, paramErr); btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree; M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr); err = UpdateHeader (btreePtr); // LogEndTime(kTraceFlushBTree, err); return err; } /*------------------------------------------------------------------------------- Routine: BTInvalidateHint - Invalidates the hint within a BTreeInterator. Function: Invalidates the hint within a BTreeInterator. Input: iterator - pointer to BTreeIterator Output: iterator - iterator with the hint.nodeNum cleared Result: noErr - success paramErr - iterator == nil -------------------------------------------------------------------------------*/ OSStatus BTInvalidateHint (BTreeIterator *iterator ) { if (iterator == nil) return paramErr; iterator->hint.nodeNum = 0; return noErr; }