Return to BTreesPrivate.h CVS log

Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / headers

Annotation of kernel/bsd/hfs/hfscommon/headers/BTreesPrivate.h, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.