]> git.saurik.com Git - apple/xnu.git/blobdiff - bsd/hfs/hfscommon/BTree/BTreeNodeOps.c
xnu-1699.22.73.tar.gz
[apple/xnu.git] / bsd / hfs / hfscommon / BTree / BTreeNodeOps.c
index 916c660b38337221e8c3858626a7180c831f7acc..89f4eaf1323c02617f93cbdcae4f416dc207a83f 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000, 2002, 2005-2008 Apple Inc. All rights reserved.
  *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
  * 
 
 ////////////////////// Routines Internal To BTreeNodeOps.c //////////////////////
 
-UInt16         GetRecordOffset         (BTreeControlBlockPtr    btree,
+u_int16_t      GetRecordOffset         (BTreeControlBlockPtr    btree,
                                                                 NodeDescPtr                     node,
-                                                                UInt16                                  index );
+                                                                u_int16_t                               index );
 
-UInt16    *GetOffsetAddress    (BTreeControlBlockPtr   btreePtr,
+u_int16_t      *GetOffsetAddress       (BTreeControlBlockPtr   btreePtr,
                                                                 NodeDescPtr                     node,
-                                                                UInt16                                 index );
+                                                                u_int16_t                              index );
                                                                 
 void           InsertOffset            (BTreeControlBlockPtr    btreePtr,
                                                                 NodeDescPtr                     node,
-                                                                UInt16                                  index,
-                                                                UInt16                                  delta );
+                                                                u_int16_t                               index,
+                                                                u_int16_t                               delta );
 
 void           DeleteOffset            (BTreeControlBlockPtr    btreePtr,
                                                                 NodeDescPtr                     node,
-                                                                UInt16                                  index );
+                                                                u_int16_t                               index );
 
 
 /////////////////////////////////////////////////////////////////////////////////
 
-#define GetRecordOffset(btreePtr,node,index)           (*(short *) ((UInt8 *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize))
+#define GetRecordOffset(btreePtr,node,index)           (*(short *) ((u_int8_t *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize))
 
 #if HFS_DIAGNOSTIC
                #include <sys/systm.h>
            #define PRINTIT kprintf
+static void PrintNode(const NodeDescPtr node, u_int16_t nodeSize, u_int32_t nodeNumber);
 #endif /* HFS_DIAGNOSTIC */
 
-static void PrintNode(const NodeDescPtr node, UInt16 nodeSize, UInt32 nodeNumber);
 
 
 
@@ -190,33 +190,40 @@ Result:
 -------------------------------------------------------------------------------*/
 
 OSStatus       GetNode         (BTreeControlBlockPtr    btreePtr,
-                                                UInt32                                  nodeNum,
+                                                u_int32_t                               nodeNum,
+                                                u_int32_t                               flags, 
                                                 NodeRec                                *nodePtr )
 {
        OSStatus                        err;
        GetBlockProcPtr         getNodeProc;
+       u_int32_t                       options;
        
 
-       //\80\80 is nodeNum within proper range?
+       // is nodeNum within proper range?
        if( nodeNum >= btreePtr->totalNodes )
        {
-               Panic("\pGetNode:nodeNum >= totalNodes");
+               Panic("GetNode:nodeNum >= totalNodes");
                err = fsBTInvalidNodeErr;
                goto ErrorExit;
        }
        
        nodePtr->blockSize = btreePtr->nodeSize;        // indicate the size of a node
+
+       options = kGetBlock;
+       if ( flags & kGetNodeHint ) 
+       {
+               options |= kGetBlockHint;
+       }
        
        getNodeProc = btreePtr->getBlockProc;
        err = getNodeProc (btreePtr->fileRefNum,
                                           nodeNum,
-                                          kGetBlock,
+                                          options,
                                           nodePtr );
 
        if (err != noErr)
        {
-               Panic ("\pGetNode: getNodeProc returned error.");
-       //      nodePtr->buffer = nil;
+               Panic ("GetNode: getNodeProc returned error.");
                goto ErrorExit;
        }
        ++btreePtr->numGetNodes;
@@ -249,7 +256,7 @@ Result:             noErr           - success
 -------------------------------------------------------------------------------*/
 
 OSStatus       GetNewNode      (BTreeControlBlockPtr    btreePtr,
-                                                UInt32                                  nodeNum,
+                                                u_int32_t                               nodeNum,
                                                 NodeRec                                *returnNodePtr )
 {
        OSStatus                         err;
@@ -270,7 +277,7 @@ OSStatus    GetNewNode      (BTreeControlBlockPtr    btreePtr,
                                           
        if (err != noErr)
        {
-               Panic ("\pGetNewNode: getNodeProc returned error.");
+               Panic ("GetNewNode: getNodeProc returned error.");
        //      returnNodePtr->buffer = nil;
                return err;
        }
@@ -284,7 +291,7 @@ OSStatus    GetNewNode      (BTreeControlBlockPtr    btreePtr,
        ClearNode (btreePtr, node);                                             // clear the node
 
        pos = (char *)node + btreePtr->nodeSize - 2;    // find address of last offset
-       *(UInt16 *)pos = sizeof (BTNodeDescriptor);             // set offset to beginning of free space
+       *(u_int16_t *)pos = sizeof (BTNodeDescriptor);  // set offset to beginning of free space
 
 
        return noErr;
@@ -320,7 +327,7 @@ OSStatus    ReleaseNode     (BTreeControlBlockPtr    btreePtr,
                err = releaseNodeProc (btreePtr->fileRefNum,
                                                           nodePtr,
                                                           kReleaseBlock );
-               PanicIf (err, "\pReleaseNode: releaseNodeProc returned error.");
+               PanicIf (err, "ReleaseNode: releaseNodeProc returned error.");
                ++btreePtr->numReleaseNodes;
        }
 
@@ -362,7 +369,7 @@ OSStatus    TrashNode       (BTreeControlBlockPtr    btreePtr,
                err = releaseNodeProc (btreePtr->fileRefNum,
                                                           nodePtr,
                                                           kReleaseBlock | kTrashBlock );
-               PanicIf (err, "\TrashNode: releaseNodeProc returned error.");
+               PanicIf (err, "TrashNode: releaseNodeProc returned error.");
                ++btreePtr->numReleaseNodes;
        }
 
@@ -391,9 +398,11 @@ Result:            noErr           - success
 
 OSStatus       UpdateNode      (BTreeControlBlockPtr    btreePtr,
                                                 NodePtr                                 nodePtr,
-                                                UInt32                                  transactionID,
-                                                UInt32                                  flags )
+                                                u_int32_t                               transactionID,
+                                                u_int32_t                               flags )
 {
+#pragma unused(transactionID)
+
        OSStatus                         err;
        ReleaseBlockProcPtr      releaseNodeProc;
        
@@ -423,19 +432,19 @@ ErrorExit:
 
 
 #if HFS_DIAGNOSTIC
-static void PrintNode(const NodeDescPtr node, UInt16 nodeSize, UInt32 nodeNumber)
+static void PrintNode(const NodeDescPtr node, u_int16_t nodeSize, u_int32_t nodeNumber)
 {
        struct row {
-               UInt16  word[8];
+               u_int16_t       word[8];
        };
        struct row      *offset;
-       UInt16  rows;
-       UInt32  *lp;
+       u_int16_t       rows;
+       u_int32_t       *lp;
 
        PRINTIT("Dump of B-tree node #%ld ($%08lX)\n", nodeNumber, nodeNumber);
 
        rows = nodeSize/16;
-       lp = (UInt32*) node;
+       lp = (u_int32_t*) node;
        offset = 0;
        
        while (rows-- > 0)
@@ -480,14 +489,14 @@ Result:           noErr           - success
 
 Boolean                InsertRecord    (BTreeControlBlockPtr   btreePtr,
                                                         NodeDescPtr                    node,
-                                                        UInt16                                 index,
+                                                        u_int16_t                              index,
                                                         RecordPtr                              recPtr,
-                                                        UInt16                                 recSize )
+                                                        u_int16_t                              recSize )
 {
-       UInt16          freeSpace;
-       UInt16          indexOffset;
-       UInt16          freeOffset;
-       UInt16          bytesToMove;
+       u_int16_t       freeSpace;
+       u_int16_t       indexOffset;
+       u_int16_t       freeOffset;
+       u_int16_t       bytesToMove;
        void       *src;
        void       *dst;
        
@@ -550,28 +559,28 @@ Result:           noErr           - success
 
 Boolean                InsertKeyRecord         (BTreeControlBlockPtr    btreePtr,
                                                                 NodeDescPtr                     node,
-                                                                UInt16                                  index,
+                                                                u_int16_t                               index,
                                                                 KeyPtr                                  keyPtr,
-                                                                UInt16                                  keyLength,
+                                                                u_int16_t                               keyLength,
                                                                 RecordPtr                               recPtr,
-                                                                UInt16                                  recSize )
+                                                                u_int16_t                               recSize )
 {
-       UInt16          freeSpace;
-       UInt16          indexOffset;
-       UInt16          freeOffset;
-       UInt16          bytesToMove;
-       UInt8 *         src;
-       UInt8 *         dst;
-       UInt16          keySize;
-       UInt16          rawKeyLength;
-       UInt16          sizeOfLength;
+       u_int16_t               freeSpace;
+       u_int16_t               indexOffset;
+       u_int16_t               freeOffset;
+       u_int16_t               bytesToMove;
+       u_int8_t *              src;
+       u_int8_t *              dst;
+       u_int16_t               keySize;
+       u_int16_t               rawKeyLength;
+       u_int16_t               sizeOfLength;
        
        //// calculate actual key size
 
        if ( btreePtr->attributes & kBTBigKeysMask )
-               keySize = keyLength + sizeof(UInt16);
+               keySize = keyLength + sizeof(u_int16_t);
        else
-               keySize = keyLength + sizeof(UInt8);
+               keySize = keyLength + sizeof(u_int8_t);
        
        if ( M_IsOdd (keySize) )
                ++keySize;                      // add pad byte
@@ -592,8 +601,8 @@ Boolean             InsertKeyRecord         (BTreeControlBlockPtr    btreePtr,
        indexOffset = GetRecordOffset (btreePtr, node, index);
        freeOffset      = GetRecordOffset (btreePtr, node, node->numRecords);
 
-       src = ((UInt8 *) node) + indexOffset;
-       dst = ((UInt8 *) src) + keySize + recSize;
+       src = ((u_int8_t *) node) + indexOffset;
+       dst = ((u_int8_t *) src) + keySize + recSize;
        bytesToMove = freeOffset - indexOffset;
        if (bytesToMove)
                MoveRecordsRight (src, dst, bytesToMove);
@@ -606,11 +615,12 @@ Boolean           InsertKeyRecord         (BTreeControlBlockPtr    btreePtr,
 
        //// copy record key
 
-       dst = ((UInt8 *) node) + indexOffset;
+       dst = ((u_int8_t *) node) + indexOffset;
 
        if ( btreePtr->attributes & kBTBigKeysMask )
        {
-               *((UInt16*) dst)++ = keyLength;         // use keyLength rather than key.length
+               *((u_int16_t *)dst) = keyLength;                        // use keyLength rather than key.length
+               dst = (u_int8_t *) (((u_int16_t *)dst) + 1);
                rawKeyLength = keyPtr->length16;
                sizeOfLength = 2;
        }
@@ -621,7 +631,7 @@ Boolean             InsertKeyRecord         (BTreeControlBlockPtr    btreePtr,
                sizeOfLength = 1;
        }
        
-       MoveRecordsLeft ( ((UInt8 *) keyPtr) + sizeOfLength, dst, rawKeyLength);        // copy key
+       MoveRecordsLeft ( ((u_int8_t *) keyPtr) + sizeOfLength, dst, rawKeyLength);     // copy key
 
        // any pad bytes?
        bytesToMove = keySize - rawKeyLength;
@@ -631,7 +641,7 @@ Boolean             InsertKeyRecord         (BTreeControlBlockPtr    btreePtr,
 
        //// copy record data
 
-       dst = ((UInt8 *) node) + indexOffset + keySize;
+       dst = ((u_int8_t *) node) + indexOffset + keySize;
        MoveRecordsLeft (recPtr, dst, recSize);
 
        return true;
@@ -654,12 +664,12 @@ Result:           none
 
 void           DeleteRecord    (BTreeControlBlockPtr   btreePtr,
                                                         NodeDescPtr                    node,
-                                                        UInt16                                 index )
+                                                        u_int16_t                              index )
 {
-       SInt16          indexOffset;
-       SInt16          nextOffset;
-       SInt16          freeOffset;
-       SInt16          bytesToMove;
+       int16_t         indexOffset;
+       int16_t         nextOffset;
+       int16_t         freeOffset;
+       int16_t         bytesToMove;
        void       *src;
        void       *dst;
        
@@ -708,24 +718,24 @@ Boolean
 SearchNode( BTreeControlBlockPtr btreePtr,
            NodeDescPtr node,
            KeyPtr searchKey,
-           UInt16 *returnIndex )
+           u_int16_t *returnIndex )
 {
-       SInt32          lowerBound;
-       SInt32          upperBound;
-       SInt32          index;
-       SInt32          result;
+       int32_t         lowerBound;
+       int32_t         upperBound;
+       int32_t         index;
+       int32_t         result;
        KeyPtr          trialKey;
-       UInt16          *offset;
+       u_int16_t       *offset;
        KeyCompareProcPtr compareProc = btreePtr->keyCompareProc;
 
        lowerBound = 0;
        upperBound = node->numRecords - 1;
-       offset = (UInt16 *) ((UInt8 *)(node) + (btreePtr)->nodeSize - kOffsetSize);
+       offset = (u_int16_t *) ((u_int8_t *)(node) + (btreePtr)->nodeSize - kOffsetSize);
        
        while (lowerBound <= upperBound) {
                index = (lowerBound + upperBound) >> 1;
 
-               trialKey = (KeyPtr) ((UInt8 *)node + *(offset - index));
+               trialKey = (KeyPtr) ((u_int8_t *)node + *(offset - index));
                
                result = compareProc(searchKey, trialKey);
 
@@ -765,14 +775,14 @@ Result:           none
 
 OSStatus       GetRecordByIndex        (BTreeControlBlockPtr    btreePtr,
                                                                 NodeDescPtr                     node,
-                                                                UInt16                                  index,
+                                                                u_int16_t                               index,
                                                                 KeyPtr                                 *keyPtr,
-                                                                UInt8 *                                *dataPtr,
-                                                                UInt16                                 *dataSize )
+                                                                u_int8_t *                             *dataPtr,
+                                                                u_int16_t                              *dataSize )
 {
-       UInt16          offset;
-       UInt16          nextOffset;
-       UInt16          keySize;
+       u_int16_t               offset;
+       u_int16_t               nextOffset;
+       u_int16_t               keySize;
        
        //
        //      Make sure index is valid (in range 0..numRecords-1)
@@ -790,7 +800,7 @@ OSStatus    GetRecordByIndex        (BTreeControlBlockPtr    btreePtr,
                ++keySize;      // add pad byte
 
        offset += keySize;                      // add the key length to find data offset
-       *dataPtr = (UInt8 *) node + offset;
+       *dataPtr = (u_int8_t *) node + offset;
        
        //// find dataSize
        nextOffset      = GetRecordOffset (btreePtr, node, index + 1);
@@ -814,9 +824,9 @@ Input:              btreePtr                - pointer to BTree control block
 Result:                - number of bytes used for data and offsets in the node.
 -------------------------------------------------------------------------------*/
 
-UInt16         GetNodeDataSize (BTreeControlBlockPtr   btreePtr, NodeDescPtr    node )
+u_int16_t      GetNodeDataSize (BTreeControlBlockPtr   btreePtr, NodeDescPtr    node )
 {
-       UInt16 freeOffset;
+       u_int16_t freeOffset;
        
        freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
        
@@ -837,9 +847,9 @@ Input:              btreePtr                - pointer to BTree control block
 Result:                - number of bytes of free space in the node.
 -------------------------------------------------------------------------------*/
 
-UInt16         GetNodeFreeSize (BTreeControlBlockPtr   btreePtr, NodeDescPtr    node )
+u_int16_t              GetNodeFreeSize (BTreeControlBlockPtr   btreePtr, NodeDescPtr    node )
 {
-       UInt16  freeOffset;
+       u_int16_t       freeOffset;
        
        freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);        //\80\80 inline?
        
@@ -862,14 +872,14 @@ Result:           - offset (in bytes) from beginning of node of record specified by index
 -------------------------------------------------------------------------------*/
 // make this a macro (for inlining)
 #if 0
-UInt16         GetRecordOffset (BTreeControlBlockPtr   btreePtr,
+u_int16_t      GetRecordOffset (BTreeControlBlockPtr   btreePtr,
                                                         NodeDescPtr                    node,
-                                                        UInt16                                 index )
+                                                        u_int16_t                              index )
 {
        void    *pos;
        
                
-       pos = (UInt8 *)node + btreePtr->nodeSize - (index << 1) - kOffsetSize;
+       pos = (u_int8_t *)node + btreePtr->nodeSize - (index << 1) - kOffsetSize;
        
        return *(short *)pos;
 }
@@ -891,13 +901,13 @@ Result:           - pointer to record "index".
 -------------------------------------------------------------------------------*/
 // make this a macro (for inlining)
 #if 0
-UInt8 *                GetRecordAddress        (BTreeControlBlockPtr   btreePtr,
+u_int8_t *     GetRecordAddress        (BTreeControlBlockPtr   btreePtr,
                                                                 NodeDescPtr                    node,
-                                                                UInt16                                 index )
+                                                                u_int16_t                              index )
 {
-       UInt8 *         pos;
+       u_int8_t *      pos;
        
-       pos = (UInt8 *)node + GetRecordOffset (btreePtr, node, index);
+       pos = (u_int8_t *)node + GetRecordOffset (btreePtr, node, index);
        
        return pos;
 }
@@ -920,13 +930,13 @@ Input:            btreePtr                - pointer to BTree control block
 Result:                - size of record "index".
 -------------------------------------------------------------------------------*/
 
-UInt16         GetRecordSize           (BTreeControlBlockPtr   btreePtr,
+u_int16_t      GetRecordSize           (BTreeControlBlockPtr   btreePtr,
                                                                 NodeDescPtr                    node,
-                                                                UInt16                                 index )
+                                                                u_int16_t                              index )
 {
-       UInt16  *pos;
+       u_int16_t       *pos;
                
-       pos = (UInt16 *) ((Ptr)node + btreePtr->nodeSize - (index << 1) - kOffsetSize);
+       pos = (u_int16_t *) ((Ptr)node + btreePtr->nodeSize - (index << 1) - kOffsetSize);
        
        return  *(pos-1) - *pos;
 }
@@ -945,15 +955,15 @@ Input:            btreePtr                - pointer to BTree control block
 Result:                - pointer to offset for record "index".
 -------------------------------------------------------------------------------*/
 
-UInt16    *GetOffsetAddress    (BTreeControlBlockPtr   btreePtr,
+u_int16_t       *GetOffsetAddress      (BTreeControlBlockPtr   btreePtr,
                                                                 NodeDescPtr                    node,
-                                                                UInt16                                 index )
+                                                                u_int16_t                              index )
 {
        void    *pos;
        
        pos = (Ptr)node + btreePtr->nodeSize - (index << 1) -2;
        
-       return (UInt16 *)pos;
+       return (u_int16_t *)pos;
 }
 
 
@@ -961,7 +971,7 @@ UInt16         *GetOffsetAddress    (BTreeControlBlockPtr   btreePtr,
 /*-------------------------------------------------------------------------------
 Routine:       GetChildNodeNum -       Return child node number from index record "index".
 
-Function:      Returns the first UInt32 stored after the key for record "index".
+Function:      Returns the first u_int32_t stored after the key for record "index".
 
 Assumes:       The node is an Index Node.
                        The key.length stored at record "index" is ODD. //\80\80 change for variable length index keys
@@ -973,16 +983,16 @@ Input:            btreePtr                - pointer to BTree control block
 Result:                - child node number from record "index".
 -------------------------------------------------------------------------------*/
 
-UInt32         GetChildNodeNum                 (BTreeControlBlockPtr    btreePtr,
+u_int32_t      GetChildNodeNum                 (BTreeControlBlockPtr    btreePtr,
                                                                         NodeDescPtr                     nodePtr,
-                                                                        UInt16                                  index )
+                                                                        u_int16_t                               index )
 {
-       UInt8 *         pos;
+       u_int8_t *              pos;
        
        pos = GetRecordAddress (btreePtr, nodePtr, index);
        pos += CalcKeySize(btreePtr, (BTreeKey *) pos);         // key.length + size of length field
        
-       return  *(UInt32 *)pos;
+       return  *(u_int32_t *)pos;
 }
 
 
@@ -1004,11 +1014,11 @@ Result:         none
 
 void           InsertOffset            (BTreeControlBlockPtr    btreePtr,
                                                                 NodeDescPtr                     node,
-                                                                UInt16                                  index,
-                                                                UInt16                                  delta )
+                                                                u_int16_t                               index,
+                                                                u_int16_t                               delta )
 {
-       UInt16          *src, *dst;
-       UInt16           numOffsets;
+       u_int16_t       *src, *dst;
+       u_int16_t        numOffsets;
        
        src = GetOffsetAddress (btreePtr, node, node->numRecords);      // point to free offset
        dst = src - 1;                                                                                          // point to new offset
@@ -1038,11 +1048,11 @@ Result:         none
 
 void           DeleteOffset            (BTreeControlBlockPtr    btreePtr,
                                                                 NodeDescPtr                     node,
-                                                                UInt16                                  index )
+                                                                u_int16_t                               index )
 {
-       UInt16          *src, *dst;
-       UInt16           numOffsets;
-       UInt16           delta;
+       u_int16_t               *src, *dst;
+       u_int16_t                numOffsets;
+       u_int16_t                delta;
        
        dst                     = GetOffsetAddress (btreePtr, node, index);
        src                     = dst - 1;