xnu-792.17.14.tar.gz

[apple/xnu.git] / bsd / hfs / hfscommon / BTree / BTree.c

diff --git a/bsd/hfs/hfscommon/BTree/BTree.c b/bsd/hfs/hfscommon/BTree/BTree.c
index 1cd262eef8dc7aef2909393454d96165ff826e7b..a1334a712818455e56f41ac8f634dacb7b7db34d 100644 (file)
--- a/bsd/hfs/hfscommon/BTree/BTree.c
+++ b/bsd/hfs/hfscommon/BTree/BTree.c
@@ -1,23 +1,29 @@
 /*
 /*

- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved.

  *
  *

- * @APPLE_LICENSE_HEADER_START@
+ * @APPLE_OSREFERENCE_LICENSE_HEADER_START@

  * 
  * 

- * The contents of this file constitute Original Code as defined in and
- * are subject to the Apple Public Source License Version 1.1 (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.
+ * 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 2.0 (the 'License'). You may not use this file except in
+ * compliance with the License. The rights granted to you under the License
+ * may not be used to create, or enable the creation or redistribution of,
+ * unlawful or unlicensed copies of an Apple operating system, or to
+ * circumvent, violate, or enable the circumvention or violation of, any
+ * terms of an Apple operating system software license agreement.

  * 
  * 

- * This Original Code and all software distributed under the License are
- * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * Please obtain a copy of the License at
+ * http://www.opensource.apple.com/apsl/ 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,
  * 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.
+ * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
+ * Please see the License for the specific language governing rights and
+ * limitations under the License.

  * 
  * 

- * @APPLE_LICENSE_HEADER_END@
+ * @APPLE_OSREFERENCE_LICENSE_HEADER_END@

  */
 /*
        File:           BTree.c
  */
 /*
        File:           BTree.c


@@ -146,14 +152,18 @@
 
 #include "../headers/BTreesPrivate.h"
 
 
 #include "../headers/BTreesPrivate.h"
 

-#include "../headers/HFSInstrumentation.h"
-

 /* 
  * The amount that the BTree header leaf count can be wrong before we assume
  * it is in an infinite loop.
  */
 #define        kNumLeafRecSlack 10             
 
 /* 
  * The amount that the BTree header leaf count can be wrong before we assume
  * it is in an infinite loop.
  */
 #define        kNumLeafRecSlack 10             
 

+/* BTree accessor routines */
+extern OSStatus GetBTreeBlock(FileReference vp, UInt32 blockNum, GetBlockOptions options, BlockDescriptor *block);
+extern OSStatus SetBTreeBlockSize(FileReference vp, ByteCount blockSize, ItemCount minBlockCount);
+extern OSStatus ExtendBTreeFile(FileReference vp, FSSize minEOF, FSSize maxEOF);
+extern OSStatus ReleaseBTreeBlock(FileReference vp, BlockDescPtr blockPtr, ReleaseBlockOptions options);
+

 //////////////////////////////////// Globals ////////////////////////////////////
 
 
 //////////////////////////////////// Globals ////////////////////////////////////
 
 


@@ -170,9 +180,6 @@ Function:   Create BTree control block for a file, if necessary. Validates the
 
 Input:         filePtr                         - pointer to file to open as a B-tree
                        keyCompareProc          - pointer to client's KeyCompare function
 
 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
 
 Result:                noErr                           - success
                        paramErr                        - required ptr was nil


@@ -181,37 +188,31 @@ Result:           noErr                           - success
                        != noErr                        - failure
 -------------------------------------------------------------------------------*/
 
                        != noErr                        - failure
 -------------------------------------------------------------------------------*/
 

-OSStatus       BTOpenPath                      (FCB                                    *filePtr,
-                                                                KeyCompareProcPtr               keyCompareProc,
-                                                                GetBlockProcPtr                 getBlockProc,
-                                                                ReleaseBlockProcPtr     releaseBlockProc,
-                                                                SetEndOfForkProcPtr     setEndOfForkProc,
-                                                                SetBlockSizeProcPtr     setBlockSizeProc )
+OSStatus BTOpenPath(FCB *filePtr, KeyCompareProcPtr keyCompareProc)

 {
        OSStatus                                err;
        BTreeControlBlockPtr    btreePtr;
        BTHeaderRec                             *header;
        NodeRec                                 nodeRec;
 
 {
        OSStatus                                err;
        BTreeControlBlockPtr    btreePtr;
        BTHeaderRec                             *header;
        NodeRec                                 nodeRec;
 

-       LogStartTime(kTraceOpenBTree);
-

        ////////////////////// Preliminary Error Checking ///////////////////////////
 
        ////////////////////// Preliminary Error Checking ///////////////////////////
 

-       if ( filePtr == nil                             ||
-                getBlockProc == nil            ||
-                releaseBlockProc == nil        ||
-                setEndOfForkProc == nil        ||
-                setBlockSizeProc == nil )
+       if ( filePtr == nil )

        {
                return  paramErr;
        }
 
        {
                return  paramErr;
        }
 

-       if ( filePtr->fcbBTCBPtr != nil )                       // already has a BTreeCB
+       /*
+        * Subsequent opens allow key compare proc to be changed.
+        */
+       if ( filePtr->fcbBTCBPtr != nil && keyCompareProc != nil) {
+               btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+               btreePtr->keyCompareProc = keyCompareProc;

                return noErr;
                return noErr;

+       }

 
 

-                                                                                               // is file large enough to contain header node?

        if ( filePtr->fcbEOF < kMinNodeSize )
        if ( filePtr->fcbEOF < kMinNodeSize )

-               return fsBTInvalidFileErr;                                                      //\80\80 or E_BadHeader?
+               return fsBTInvalidFileErr;

 
 
        //////////////////////// Allocate Control Block /////////////////////////////
 
 
        //////////////////////// Allocate Control Block /////////////////////////////


@@ -223,9 +224,9 @@ OSStatus    BTOpenPath                      (FCB                                    *filePtr,
                return  memFullErr;
        }
 
                return  memFullErr;
        }
 

-       btreePtr->getBlockProc          = getBlockProc;
-       btreePtr->releaseBlockProc      = releaseBlockProc;
-       btreePtr->setEndOfForkProc      = setEndOfForkProc;
+       btreePtr->getBlockProc          = GetBTreeBlock;
+       btreePtr->releaseBlockProc      = ReleaseBTreeBlock;
+       btreePtr->setEndOfForkProc      = ExtendBTreeFile;

        btreePtr->keyCompareProc        = keyCompareProc;
 
        /////////////////////////// Read Header Node ////////////////////////////////
        btreePtr->keyCompareProc        = keyCompareProc;
 
        /////////////////////////// Read Header Node ////////////////////////////////


@@ -237,15 +238,20 @@ OSStatus  BTOpenPath                      (FCB                                    *filePtr,
        /* The minimum node size is the physical block size */
        nodeRec.blockSize = VTOHFS(btreePtr->fileRefNum)->hfs_phys_block_size;
 
        /* The minimum node size is the physical block size */
        nodeRec.blockSize = VTOHFS(btreePtr->fileRefNum)->hfs_phys_block_size;
 

+       /* Start with the allocation block size for regular files. */
+       if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID)
+       {
+               nodeRec.blockSize = FCBTOVCB(filePtr)->blockSize;
+       }

        REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
 
        // it is now safe to call M_ExitOnError (err)
 
        REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
 
        // it is now safe to call M_ExitOnError (err)
 

-       err = setBlockSizeProc (btreePtr->fileRefNum, nodeRec.blockSize, 1);
+       err = SetBTreeBlockSize (btreePtr->fileRefNum, nodeRec.blockSize, 1);

        M_ExitOnError (err);
 
 
        M_ExitOnError (err);
 
 

-       err = getBlockProc (btreePtr->fileRefNum,
+       err = GetBTreeBlock(btreePtr->fileRefNum,

                                                kHeaderNodeNum,
                                                kGetBlock,
                                                &nodeRec );
                                                kHeaderNodeNum,
                                                kGetBlock,
                                                &nodeRec );


@@ -256,7 +262,7 @@ OSStatus    BTOpenPath                      (FCB                                    *filePtr,
                Panic("\pBTOpen: getNodeProc returned error getting header node.");
                goto ErrorExit;
        }
                Panic("\pBTOpen: getNodeProc returned error getting header node.");
                goto ErrorExit;
        }

-
+       ++btreePtr->numGetNodes;

        header = (BTHeaderRec*) ((u_long)nodeRec.buffer + sizeof(BTNodeDescriptor));
 
 
        header = (BTHeaderRec*) ((u_long)nodeRec.buffer + sizeof(BTNodeDescriptor));
 
 


@@ -279,9 +285,12 @@ OSStatus   BTOpenPath                      (FCB                                    *filePtr,
        btreePtr->maxKeyLength          = header->maxKeyLength;
        btreePtr->totalNodes            = header->totalNodes;
        btreePtr->freeNodes                     = header->freeNodes;
        btreePtr->maxKeyLength          = header->maxKeyLength;
        btreePtr->totalNodes            = header->totalNodes;
        btreePtr->freeNodes                     = header->freeNodes;

-       // ignore                                         header->clumpSize;    //\80\80 rename this field?
+       if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID)
+               filePtr->ff_clumpsize = header->clumpSize;

        btreePtr->btreeType                     = header->btreeType;
 
        btreePtr->btreeType                     = header->btreeType;
 

+       btreePtr->keyCompareType = header->keyCompareType;
+

        btreePtr->attributes            = header->attributes;
 
        if ( btreePtr->maxKeyLength > 40 )
        btreePtr->attributes            = header->attributes;
 
        if ( btreePtr->maxKeyLength > 40 )


@@ -293,40 +302,44 @@ OSStatus  BTOpenPath                      (FCB                                    *filePtr,
        btreePtr->flags                         = 0;
        btreePtr->writeCount            = 1;
 
        btreePtr->flags                         = 0;
        btreePtr->writeCount            = 1;
 

-       btreePtr->numGetNodes           = 1;            // for earlier call to getNodeProc
-

        /////////////////////////// Check Header Node ///////////////////////////////
 
        /////////////////////////// Check Header Node ///////////////////////////////
 

-       //\80\80 set kBadClose attribute bit, and UpdateNode
-
-       // if nodeSize matches then we don't need to release, just CheckNode
+       // set kBadClose attribute bit, and UpdateNode

 
        /* b-tree node size must be at least as big as the physical block size */
 
        /* b-tree node size must be at least as big as the physical block size */

-       if (btreePtr->nodeSize < nodeRec.blockSize) {
-               err = fsBTBadNodeSize;
-               goto ErrorExit;
-       }
-
-       if ( btreePtr->nodeSize == nodeRec.blockSize )
+       if (btreePtr->nodeSize < nodeRec.blockSize)

        {
        {

-               err = CheckNode (btreePtr, nodeRec.buffer);
-               if (err)
-                       VTOVCB(btreePtr->fileRefNum)->vcbFlags |= kHFS_DamagedVolume;
-               M_ExitOnError (err);
+               /*
+                * If this tree has any records or the media is writeable then
+                * we cannot mount using the current physical block size.
+                */
+               if (btreePtr->leafRecords > 0 ||
+                   VTOHFS(btreePtr->fileRefNum)->hfs_flags & HFS_WRITEABLE_MEDIA)              
+               {
+                       err = fsBTBadNodeSize;
+                       goto ErrorExit;
+               }

        }
        }

-       else
+
+       /*
+        * If the actual node size is different than the amount we read,
+        * then release and trash this block, and re-read with the correct
+        * node size.
+        */
+       if ( btreePtr->nodeSize != nodeRec.blockSize )

        {
        {

-               err = setBlockSizeProc (btreePtr->fileRefNum, btreePtr->nodeSize, 32);  //\80\80 we should try and get this down to 8
+               err = SetBTreeBlockSize (btreePtr->fileRefNum, btreePtr->nodeSize, 32);

                M_ExitOnError (err);
 
                /*
                 * Need to use kTrashBlock option to force the
                 * buffer cache to read the entire node
                 */
                M_ExitOnError (err);
 
                /*
                 * Need to use kTrashBlock option to force the
                 * buffer cache to read the entire node
                 */

-               err = releaseBlockProc(btreePtr->fileRefNum, &nodeRec, kTrashBlock);
+               err = ReleaseBTreeBlock(btreePtr->fileRefNum, &nodeRec, kTrashBlock);
+               ++btreePtr->numReleaseNodes;

                M_ExitOnError (err);
 
                M_ExitOnError (err);
 

-               err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec );            // calls CheckNode...
+               err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec );

                M_ExitOnError (err);
        }
 
                M_ExitOnError (err);
        }
 


@@ -339,16 +352,21 @@ OSStatus  BTOpenPath                      (FCB                                    *filePtr,
        /*
         * 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.
        /*
         * 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 journaling is turned on for this volume we can't deal with this
+        * situation and so we bail out.  If journaling isn't on it's ok as
+        * hfs_strategy_fragmented() deals with it.  Journaling can't support
+        * this because it assumes that if you give it a block that it's
+        * contiguous on disk.

         */
         */

-       if ( !NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize) )
+       if ( FCBTOHFS(filePtr)->jnl && !NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize) ) {

                return fsBTInvalidNodeErr;
                return fsBTInvalidNodeErr;

+       }

 
        //////////////////////////////// Success ////////////////////////////////////
 
        //\80\80 align LEOF to multiple of node size?       - just on close
 
 
        //////////////////////////////// Success ////////////////////////////////////
 
        //\80\80 align LEOF to multiple of node size?       - just on close
 

-       LogEndTime(kTraceOpenBTree, noErr);
-

        return noErr;
 
 
        return noErr;
 
 


@@ -360,8 +378,6 @@ ErrorExit:
        (void) ReleaseNode (btreePtr, &nodeRec);
        DisposePtr( (Ptr) btreePtr );
 
        (void) ReleaseNode (btreePtr, &nodeRec);
        DisposePtr( (Ptr) btreePtr );
 

-       LogEndTime(kTraceOpenBTree, err);
-

        return err;
 }
 
        return err;
 }
 


@@ -387,8 +403,6 @@ OSStatus    BTClosePath                     (FCB                                    *filePtr)
        OSStatus                                err;
        BTreeControlBlockPtr    btreePtr;
 
        OSStatus                                err;
        BTreeControlBlockPtr    btreePtr;
 

-       LogStartTime(kTraceCloseBTree);
-

        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
        if (btreePtr == nil)
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
        if (btreePtr == nil)


@@ -405,16 +419,12 @@ OSStatus  BTClosePath                     (FCB                                    *filePtr)
        DisposePtr( (Ptr) btreePtr );
        filePtr->fcbBTCBPtr = nil;
 
        DisposePtr( (Ptr) btreePtr );
        filePtr->fcbBTCBPtr = nil;
 

-       LogEndTime(kTraceCloseBTree, noErr);
-

        return  noErr;
 
        /////////////////////// Error - Clean Up and Exit ///////////////////////////
 
 ErrorExit:
 
        return  noErr;
 
        /////////////////////// Error - Clean Up and Exit ///////////////////////////
 
 ErrorExit:
 

-       LogEndTime(kTraceCloseBTree, err);
-

        return  err;
 }
 
        return  err;
 }
 


@@ -451,7 +461,6 @@ Result:             noErr                   - success, record contains copy of record found
 
 OSStatus       BTSearchRecord          (FCB                                            *filePtr,
                                                                 BTreeIterator                          *searchIterator,
 
 OSStatus       BTSearchRecord          (FCB                                            *filePtr,
                                                                 BTreeIterator                          *searchIterator,

-                                                                UInt32                                         heuristicHint,

                                                                 FSBufferDescriptor                     *record,
                                                                 UInt16                                         *recordLen,
                                                                 BTreeIterator                          *resultIterator )
                                                                 FSBufferDescriptor                     *record,
                                                                 UInt16                                         *recordLen,
                                                                 BTreeIterator                          *resultIterator )


@@ -468,12 +477,12 @@ OSStatus  BTSearchRecord          (FCB                                            *filePtr,
        Boolean                                 foundRecord;
        Boolean                                 validHint;
 
        Boolean                                 foundRecord;
        Boolean                                 validHint;
 

-
-       LogStartTime(kTraceSearchBTree);
-

        if (filePtr == nil)                                                                     return  paramErr;
        if (searchIterator == nil)                                                      return  paramErr;
 
        if (filePtr == nil)                                                                     return  paramErr;
        if (searchIterator == nil)                                                      return  paramErr;
 

+       node.buffer = nil;
+       node.blockHeader = nil;
+

        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        if (btreePtr == nil)                                                            return  fsBTInvalidFileErr;
 
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        if (btreePtr == nil)                                                            return  fsBTInvalidFileErr;
 


@@ -516,30 +525,6 @@ OSStatus   BTSearchRecord          (FCB                                            *filePtr,
                        (void) BTInvalidateHint( searchIterator );
        }
 
                        (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 ////////////////////////////////
 
 
        //////////////////////////// Search The Tree ////////////////////////////////
 


@@ -600,8 +585,6 @@ OSStatus    BTSearchRecord          (FCB                                            *filePtr,
        err = ReleaseNode (btreePtr, &node);
        M_ExitOnError (err);
 
        err = ReleaseNode (btreePtr, &node);
        M_ExitOnError (err);
 

-       LogEndTime(kTraceSearchBTree, (foundRecord == false));
-

        if (foundRecord == false)       return  fsBTRecordNotFoundErr;
        else                                            return  noErr;
 
        if (foundRecord == false)       return  fsBTRecordNotFoundErr;
        else                                            return  noErr;
 


@@ -629,8 +612,6 @@ ErrorExit:
        if ( err == fsBTEmptyErr )
                err = fsBTRecordNotFoundErr;
 
        if ( err == fsBTEmptyErr )
                err = fsBTRecordNotFoundErr;
 

-       LogEndTime(kTraceSearchBTree, err);
-

        return err;
 }
 
        return err;
 }
 


@@ -673,13 +654,14 @@ OSStatus  BTIterateRecord         (FCB                                            *filePtr,
        UInt16                                          index;
 
 
        UInt16                                          index;
 
 

-       LogStartTime(kTraceGetBTreeRecord);
-

        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        ////////////////////////// Priliminary Checks ///////////////////////////////
 

-       left.buffer             = nil;
-       right.buffer    = nil;
-       node.buffer             = nil;
+       left.buffer               = nil;
+       left.blockHeader  = nil;
+       right.buffer      = nil;
+       right.blockHeader = nil;
+       node.buffer               = nil;
+       node.blockHeader  = nil;

 
 
        if (filePtr == nil)
 
 
        if (filePtr == nil)


@@ -909,8 +891,6 @@ CopyData:
                M_ExitOnError (err);
        }
 
                M_ExitOnError (err);
        }
 

-       LogEndTime(kTraceGetBTreeRecord, noErr);
-

        return noErr;
 
        /////////////////////// Error - Clean Up and Exit ///////////////////////////
        return noErr;
 
        /////////////////////// Error - Clean Up and Exit ///////////////////////////


@@ -940,8 +920,6 @@ ErrorExit:
        if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
                err = fsBTRecordNotFoundErr;
 
        if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
                err = fsBTRecordNotFoundErr;
 

-       LogEndTime(kTraceGetBTreeRecord, err);
-

        return err;
 }
 
        return err;
 }
 


@@ -980,9 +958,12 @@ BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator
 
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
 
        ////////////////////////// Priliminary Checks ///////////////////////////////
 

-       left.buffer  = nil;
-       right.buffer = nil;
-       node.buffer  = nil;
+       left.buffer       = nil;
+       left.blockHeader  = nil;
+       right.buffer      = nil;
+       right.blockHeader = nil;
+       node.buffer       = nil;
+       node.blockHeader  = nil;

 
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
 
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 


@@ -1039,6 +1020,8 @@ BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator
 
        err = FindIteratorPosition(btreePtr, iterator, &left, &node, &right,
                                   &nodeNum, &index, &foundRecord);
 
        err = FindIteratorPosition(btreePtr, iterator, &left, &node, &right,
                                   &nodeNum, &index, &foundRecord);

+       if (err == fsBTRecordNotFoundErr)
+               err = 0;

        M_ExitOnError(err);
 
 
        M_ExitOnError(err);
 
 


@@ -1134,9 +1117,13 @@ BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator
 
 ProcessData:
        err = GetRecordByIndex(btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
 
 ProcessData:
        err = GetRecordByIndex(btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);

+       if (err) {
+               err = btBadNode;
+               goto ErrorExit;
+       }

        
        while (err == 0) {
        
        while (err == 0) {

-               if (callBackProc(keyPtr, recordPtr, len, callBackState) == 0)
+               if (callBackProc(keyPtr, recordPtr, callBackState) == 0)

                        break;
                
                if ((index+1) < ((NodeDescPtr)node.buffer)->numRecords) {
                        break;
                
                if ((index+1) < ((NodeDescPtr)node.buffer)->numRecords) {


@@ -1166,6 +1153,10 @@ ProcessData:
                }
                err = GetRecordByIndex(btreePtr, node.buffer, index,
                                                &keyPtr, &recordPtr, &len);
                }
                err = GetRecordByIndex(btreePtr, node.buffer, index,
                                                &keyPtr, &recordPtr, &len);

+               if (err) {
+                       err = btBadNode;
+                       goto ErrorExit;
+               }

        }
 
 
        }
 
 


@@ -1243,17 +1234,15 @@ OSStatus        BTInsertRecord          (FCB                                            *filePtr,
        UInt16                                  index;
        Boolean                                 recordFit;
 
        UInt16                                  index;
        Boolean                                 recordFit;
 

-

        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        nodeRec.buffer = nil;                                   // so we can call ReleaseNode
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        nodeRec.buffer = nil;                                   // so we can call ReleaseNode

+       nodeRec.blockHeader = nil;

 
        err = CheckInsertParams (filePtr, iterator, record, recordLen);
        if (err != noErr)
                return  err;
 
 
        err = CheckInsertParams (filePtr, iterator, record, recordLen);
        if (err != noErr)
                return  err;
 

-       LogStartTime(kTraceInsertBTreeRecord);
-

        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
        REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
        REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);


@@ -1273,7 +1262,7 @@ OSStatus  BTInsertRecord          (FCB                                            *filePtr,
 
                case fsBTEmptyErr:      // if tree empty add 1st leaf node
 
 
                case fsBTEmptyErr:      // if tree empty add 1st leaf node
 

-                                                               if (btreePtr->freeNodes == 0)
+                                                               if (BTAvailableNodes(btreePtr) == 0)

                                                                {
                                                                        err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
                                                                        M_ExitOnError (err);
                                                                {
                                                                        err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
                                                                        M_ExitOnError (err);


@@ -1285,6 +1274,9 @@ OSStatus  BTInsertRecord          (FCB                                            *filePtr,
                                                                err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
                                                                M_ExitOnError (err);
 
                                                                err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
                                                                M_ExitOnError (err);
 

+                                                               // XXXdbg
+                                                               ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+                                                               

                                                                ((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
                                                                ((NodeDescPtr)nodeRec.buffer)->height   = 1;
 
                                                                ((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
                                                                ((NodeDescPtr)nodeRec.buffer)->height   = 1;
 


@@ -1297,14 +1289,19 @@ OSStatus        BTInsertRecord          (FCB                                            *filePtr,
                                                                        goto ErrorExit;
                                                                }
 
                                                                        goto ErrorExit;
                                                                }
 

-                                                               err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
-                                                               M_ExitOnError (err);
-
-                                                               // update BTreeControlBlock
+                                                               /*
+                                                                * Update the B-tree control block.  Do this before
+                                                                * calling UpdateNode since it will compare the node's
+                                                                * height with treeDepth.
+                                                                */

                                                                btreePtr->treeDepth                     = 1;
                                                                btreePtr->rootNode                      = insertNodeNum;
                                                                btreePtr->firstLeafNode         = insertNodeNum;
                                                                btreePtr->lastLeafNode          = insertNodeNum;
                                                                btreePtr->treeDepth                     = 1;
                                                                btreePtr->rootNode                      = insertNodeNum;
                                                                btreePtr->firstLeafNode         = insertNodeNum;
                                                                btreePtr->lastLeafNode          = insertNodeNum;

+
+                                                               err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
+                                                               M_ExitOnError (err);
+

                                                                M_BTreeHeaderDirty (btreePtr);
 
                                                                goto Success;
                                                                M_BTreeHeaderDirty (btreePtr);
 
                                                                goto Success;


@@ -1314,6 +1311,9 @@ OSStatus  BTInsertRecord          (FCB                                            *filePtr,
 
        if (index > 0)
        {
 
        if (index > 0)
        {

+               // XXXdbg
+               ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+                                                               

                recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
                                                                                &iterator->key, KeyLength(btreePtr, &iterator->key),
                                                                                record->bufferAddress, recordLen);
                recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
                                                                                &iterator->key, KeyLength(btreePtr, &iterator->key),
                                                                                record->bufferAddress, recordLen);


@@ -1328,10 +1328,10 @@ OSStatus        BTInsertRecord          (FCB                                            *filePtr,
 
        /////////////////////// Extend File If Necessary ////////////////////////////
 
 
        /////////////////////// Extend File If Necessary ////////////////////////////
 

-       nodesNeeded =  btreePtr->treeDepth + 1 - btreePtr->freeNodes;   //\80\80 math limit
+       nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);

        if (nodesNeeded > 0)
        {
        if (nodesNeeded > 0)
        {

-               nodesNeeded += btreePtr->totalNodes;
+               nodesNeeded += (SInt32)btreePtr->totalNodes;

                if (nodesNeeded > CalcMapBits (btreePtr))       // we'll need to add a map node too!
                        ++nodesNeeded;
 
                if (nodesNeeded > CalcMapBits (btreePtr))       // we'll need to add a map node too!
                        ++nodesNeeded;
 


@@ -1352,7 +1352,7 @@ Success:
        ++btreePtr->writeCount;
        ++btreePtr->leafRecords;
        M_BTreeHeaderDirty (btreePtr);
        ++btreePtr->writeCount;
        ++btreePtr->leafRecords;
        M_BTreeHeaderDirty (btreePtr);

-
+               

        // create hint
        iterator->hint.writeCount       = btreePtr->writeCount;
        iterator->hint.nodeNum          = insertNodeNum;
        // create hint
        iterator->hint.writeCount       = btreePtr->writeCount;
        iterator->hint.nodeNum          = insertNodeNum;


@@ -1360,8 +1360,6 @@ Success:
        iterator->hint.reserved1        = 0;
        iterator->hint.reserved2        = 0;
 
        iterator->hint.reserved1        = 0;
        iterator->hint.reserved2        = 0;
 

-       LogEndTime(kTraceInsertBTreeRecord, noErr);
-

        return noErr;
 
 
        return noErr;
 
 


@@ -1380,8 +1378,6 @@ ErrorExit:
        if (err == fsBTEmptyErr)
                err = fsBTRecordNotFoundErr;
 
        if (err == fsBTEmptyErr)
                err = fsBTRecordNotFoundErr;
 

-       LogEndTime(kTraceInsertBTreeRecord, err);
-

        return err;
 }
 
        return err;
 }
 


@@ -1407,13 +1403,12 @@ OSStatus        BTReplaceRecord         (FCB                                            *filePtr,
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        nodeRec.buffer = nil;                                   // so we can call ReleaseNode
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        nodeRec.buffer = nil;                                   // so we can call ReleaseNode

+       nodeRec.blockHeader = nil;

 
        err = CheckInsertParams (filePtr, iterator, record, recordLen);
        if (err != noErr)
                return err;
 
 
        err = CheckInsertParams (filePtr, iterator, record, recordLen);
        if (err != noErr)
                return err;
 

-       LogStartTime(kTraceReplaceBTreeRecord);
-

        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
        REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
        REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);


@@ -1430,6 +1425,9 @@ OSStatus  BTReplaceRecord         (FCB                                            *filePtr,
                err = GetNode (btreePtr, insertNodeNum, &nodeRec);
                if( err == noErr )
                {
                err = GetNode (btreePtr, insertNodeNum, &nodeRec);
                if( err == noErr )
                {

+                       // XXXdbg
+                       ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+                                                               

                        err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
                        M_ExitOnError (err);
 
                        err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
                        M_ExitOnError (err);
 


@@ -1465,6 +1463,9 @@ OSStatus  BTReplaceRecord         (FCB                                            *filePtr,
        // optimization - if simple replace will work then don't extend btree
        // \80\80 if we tried this before, and failed because it wouldn't fit then we shouldn't try this again...
 
        // optimization - if simple replace will work then don't extend btree
        // \80\80 if we tried this before, and failed because it wouldn't fit then we shouldn't try this again...
 

+       // XXXdbg
+       ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+

        err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
        M_ExitOnError (err);
 
        err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
        M_ExitOnError (err);
 


@@ -1479,10 +1480,10 @@ OSStatus        BTReplaceRecord         (FCB                                            *filePtr,
 
        //////////////////////////// Make Some Room /////////////////////////////////
 
 
        //////////////////////////// Make Some Room /////////////////////////////////
 

-       nodesNeeded =  btreePtr->treeDepth + 1 - btreePtr->freeNodes;   //\80\80 math limit
+       nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);

        if (nodesNeeded > 0)
        {
        if (nodesNeeded > 0)
        {

-               nodesNeeded += btreePtr->totalNodes;
+               nodesNeeded += (SInt32)btreePtr->totalNodes;

                if (nodesNeeded > CalcMapBits (btreePtr))       // we'll need to add a map node too!
                        ++nodesNeeded;
 
                if (nodesNeeded > CalcMapBits (btreePtr))       // we'll need to add a map node too!
                        ++nodesNeeded;
 


@@ -1490,7 +1491,9 @@ OSStatus  BTReplaceRecord         (FCB                                            *filePtr,
                M_ExitOnError (err);
        }
 
                M_ExitOnError (err);
        }
 

-
+       // XXXdbg
+       ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+                                                               

        DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record
 
        err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
        DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record
 
        err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,


@@ -1507,8 +1510,6 @@ Success:
        iterator->hint.reserved1        = 0;
        iterator->hint.reserved2        = 0;
 
        iterator->hint.reserved1        = 0;
        iterator->hint.reserved2        = 0;
 

-       LogEndTime(kTraceReplaceBTreeRecord, noErr);
-

        return noErr;
 
 
        return noErr;
 
 


@@ -1524,9 +1525,120 @@ ErrorExit:
        iterator->hint.reserved1        = 0;
        iterator->hint.reserved2        = 0;
 
        iterator->hint.reserved1        = 0;
        iterator->hint.reserved2        = 0;
 

+       return err;
+}
+
+
+
+//////////////////////////////// BTUpdateRecord ////////////////////////////////
+
+OSStatus
+BTUpdateRecord(FCB *filePtr, BTreeIterator *iterator,
+               IterateCallBackProcPtr callBackProc, void * callBackState)
+{
+       OSStatus                                err;
+       BTreeControlBlockPtr    btreePtr;
+       TreePathTable                   treePathTable;
+       BlockDescriptor                 nodeRec;
+       RecordPtr                               recordPtr;
+       BTreeKeyPtr                             keyPtr;
+       UInt32                                  insertNodeNum;
+       UInt16                                  recordLen;
+       UInt16                                  index;
+       Boolean                                 validHint;
+
+
+       ////////////////////////// Priliminary Checks ///////////////////////////////
+
+       nodeRec.buffer = nil;                                   // so we can call ReleaseNode
+       nodeRec.blockHeader = nil;
+
+       btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+
+       REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
+
+       ////////////////////////////// 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)
+               {
+                       if (((NodeDescPtr)nodeRec.buffer)->kind == kBTLeafNode &&
+                           SearchNode (btreePtr, nodeRec.buffer, &iterator->key, &index))
+                       {
+                               err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
+                               M_ExitOnError (err);
+
+                               // XXXdbg
+                               ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+                                                               
+                               err = callBackProc(keyPtr, recordPtr, callBackState);
+                               M_ExitOnError (err);
+
+                               err = UpdateNode (btreePtr, &nodeRec, 0, 0);
+                               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);
+
+       err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
+       M_ExitOnError (err);
+
+       // XXXdbg
+       ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+                                                               
+       err = callBackProc(keyPtr, recordPtr, callBackState);
+       M_ExitOnError (err);
+
+       err = UpdateNode (btreePtr, &nodeRec, 0, 0);
+       M_ExitOnError (err);
+
+Success:
+       // create hint
+       iterator->hint.writeCount       = btreePtr->writeCount;
+       iterator->hint.nodeNum          = insertNodeNum;
+       iterator->hint.index            = 0;
+       iterator->hint.reserved1        = 0;
+       iterator->hint.reserved2        = 0;
+       return noErr;
+
+       ////////////////////////////// Error Exit ///////////////////////////////////

 
 

-       LogEndTime(kTraceReplaceBTreeRecord, err);
+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;
 }
 
        return err;
 }
 


@@ -1541,14 +1653,15 @@ OSStatus        BTDeleteRecord          (FCB                                            *filePtr,
        BTreeControlBlockPtr    btreePtr;
        TreePathTable                   treePathTable;
        BlockDescriptor                 nodeRec;
        BTreeControlBlockPtr    btreePtr;
        TreePathTable                   treePathTable;
        BlockDescriptor                 nodeRec;

+       SInt32 nodesNeeded;

        UInt32                                  nodeNum;
        UInt16                                  index;
 
        UInt32                                  nodeNum;
        UInt16                                  index;
 

-       LogStartTime(kTraceDeleteBTreeRecord);

 
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        nodeRec.buffer = nil;                                   // so we can call ReleaseNode
 
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        nodeRec.buffer = nil;                                   // so we can call ReleaseNode

+       nodeRec.blockHeader = nil;

 
        M_ReturnErrorIf (filePtr == nil,        paramErr);
        M_ReturnErrorIf (iterator == nil,       paramErr);
 
        M_ReturnErrorIf (filePtr == nil,        paramErr);
        M_ReturnErrorIf (iterator == nil,       paramErr);


@@ -1571,6 +1684,19 @@ OSStatus BTDeleteRecord          (FCB                                            *filePtr,
        M_ExitOnError (err);                                    // record must exit for Delete
 
 
        M_ExitOnError (err);                                    // record must exit for Delete
 
 

+       /////////////////////// Extend File If Necessary ////////////////////////////
+
+       nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
+       if ((btreePtr->attributes & kBTVariableIndexKeysMask) && (nodesNeeded > 0))
+       {
+               nodesNeeded += (SInt32)btreePtr->totalNodes;
+               if (nodesNeeded > CalcMapBits (btreePtr))
+                       ++nodesNeeded;
+
+               err = ExtendBTree (btreePtr, nodesNeeded);
+               M_ExitOnError (err);
+       }
+

        ///////////////////////////// Delete Record /////////////////////////////////
 
        err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1);
        ///////////////////////////// Delete Record /////////////////////////////////
 
        err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1);


@@ -1579,11 +1705,9 @@ OSStatus BTDeleteRecord          (FCB                                            *filePtr,
        ++btreePtr->writeCount;
        --btreePtr->leafRecords;
        M_BTreeHeaderDirty (btreePtr);
        ++btreePtr->writeCount;
        --btreePtr->leafRecords;
        M_BTreeHeaderDirty (btreePtr);

-
+               

        iterator->hint.nodeNum  = 0;
 
        iterator->hint.nodeNum  = 0;
 

-       LogEndTime(kTraceDeleteBTreeRecord, noErr);
-

        return noErr;
 
        ////////////////////////////// Error Exit ///////////////////////////////////
        return noErr;
 
        ////////////////////////////// Error Exit ///////////////////////////////////


@@ -1591,8 +1715,6 @@ OSStatus  BTDeleteRecord          (FCB                                            *filePtr,
 ErrorExit:
        (void) ReleaseNode (btreePtr, &nodeRec);
 
 ErrorExit:
        (void) ReleaseNode (btreePtr, &nodeRec);
 

-       LogEndTime(kTraceDeleteBTreeRecord, err);
-

        return  err;
 }
 
        return  err;
 }
 


@@ -1630,12 +1752,20 @@ OSStatus        BTGetInformation        (FCB                                    *filePtr,
        info->numNodes          = btreePtr->totalNodes;
        info->numFreeNodes      = btreePtr->freeNodes;
        info->lastfsync         = btreePtr->lastfsync;
        info->numNodes          = btreePtr->totalNodes;
        info->numFreeNodes      = btreePtr->freeNodes;
        info->lastfsync         = btreePtr->lastfsync;

-       info->reserved          = 0;
-
+       info->keyCompareType    = btreePtr->keyCompareType;

        return noErr;
 }
 
        return noErr;
 }
 

+// XXXdbg
+__private_extern__
+OSStatus
+BTIsDirty(FCB *filePtr)
+{
+       BTreeControlBlockPtr    btreePtr;

 
 

+       btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+       return TreeIsDirty(btreePtr);
+}

 
 /*-------------------------------------------------------------------------------
 Routine:       BTFlushPath     -       Flush BTreeControlBlock to Header Node.
 
 /*-------------------------------------------------------------------------------
 Routine:       BTFlushPath     -       Flush BTreeControlBlock to Header Node.


@@ -1657,20 +1787,16 @@ OSStatus        BTFlushPath                             (FCB                                    *filePtr)
        BTreeControlBlockPtr    btreePtr;
 
 
        BTreeControlBlockPtr    btreePtr;
 
 

-       LogStartTime(kTraceFlushBTree);
-

        M_ReturnErrorIf (filePtr == nil,        paramErr);
 
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
        M_ReturnErrorIf (btreePtr == nil,       fsBTInvalidFileErr);
 
        M_ReturnErrorIf (filePtr == nil,        paramErr);
 
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
        M_ReturnErrorIf (btreePtr == nil,       fsBTInvalidFileErr);
 

-       REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
+       REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);

 
        err = UpdateHeader (btreePtr, false);
 
 
        err = UpdateHeader (btreePtr, false);
 

-       LogEndTime(kTraceFlushBTree, err);
-

        return  err;
 }
 
        return  err;
 }
 


@@ -1700,6 +1826,9 @@ BTReloadData(FCB *filePtr)
        BTHeaderRec *header;    
 
 
        BTHeaderRec *header;    
 
 

+       node.buffer = nil;
+       node.blockHeader = nil;
+

        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        if (btreePtr == nil)
                return (fsBTInvalidFileErr);
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        if (btreePtr == nil)
                return (fsBTInvalidFileErr);


@@ -1834,3 +1963,99 @@ OSStatus BTSetLastSync           (FCB                                    *filePtr,
 }
 
 
 }
 
 

+__private_extern__
+OSStatus       BTHasContiguousNodes    (FCB                                    *filePtr)
+{
+       BTreeControlBlockPtr    btreePtr;
+
+
+       M_ReturnErrorIf (filePtr == nil,        paramErr);
+
+       btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+       
+       REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
+
+       M_ReturnErrorIf (btreePtr == nil,       fsBTInvalidFileErr);
+
+       return NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize);
+}
+
+
+/*-------------------------------------------------------------------------------
+Routine:       BTGetUserData
+
+Function:      Read the user data area of the b-tree header node.
+
+-------------------------------------------------------------------------------*/
+__private_extern__
+OSStatus
+BTGetUserData(FCB *filePtr, void * dataPtr, int dataSize)
+{
+       BTreeControlBlockPtr btreePtr;
+       BlockDescriptor node;
+       char * offset;
+       OSStatus err;
+
+       if (dataSize > kBTreeHeaderUserBytes)
+               return (EINVAL);
+       node.buffer = nil;
+       node.blockHeader = nil;
+
+       btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+       if (btreePtr == nil)
+               return (fsBTInvalidFileErr);
+
+       REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
+
+       err = GetNode(btreePtr, kHeaderNodeNum, &node);
+       if (err)
+               return (err);
+       
+       offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec);
+       bcopy(offset, dataPtr, dataSize);
+
+       (void) ReleaseNode(btreePtr, &node);
+
+       return  (0);
+}
+
+
+/*-------------------------------------------------------------------------------
+Routine:       BTSetUserData
+
+Function:      Write the user data area of the b-tree header node.
+-------------------------------------------------------------------------------*/
+__private_extern__
+OSStatus
+BTSetUserData(FCB *filePtr, void * dataPtr, int dataSize)
+{
+       BTreeControlBlockPtr btreePtr;
+       BlockDescriptor node;
+       char * offset;
+       OSStatus err;
+
+       if (dataSize > kBTreeHeaderUserBytes)
+               return (EINVAL);
+       node.buffer = nil;
+       node.blockHeader = nil;
+
+       btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+       if (btreePtr == nil)
+               return (fsBTInvalidFileErr);
+
+       REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
+
+       err = GetNode(btreePtr, kHeaderNodeNum, &node);
+       if (err)
+               return (err);
+       
+       ModifyBlockStart(btreePtr->fileRefNum, &node);
+
+       offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec);
+       bcopy(dataPtr, offset, dataSize);
+
+       err = UpdateNode (btreePtr, &node, 0, 0);
+
+       return  (err);
+}
+