[apple/hfs.git] / livefiles_hfs_plugin / lf_hfs_btree_misc_ops.c

//
//  lf_hfs_btree_misc_ops.c
//  livefiles_hfs
//
//  Created by Yakov Ben Zaken on 22/03/2018.
//

#include "lf_hfs_btrees_private.h"
#include "lf_hfs_btrees_io.h"
#include "lf_hfs_utils.h"

////////////////////////////// Routine Definitions //////////////////////////////

/*-------------------------------------------------------------------------------
 Routine:    CalcKeyRecordSize    -    Return size of combined key/record structure.

 Function:    Rounds keySize and recSize so they will end on word boundaries.
 Does NOT add size of offset.

 Input:        keySize        - length of key (including length field)
 recSize        - length of record data

 Output:        none

 Result:        u_int16_t    - size of combined key/record that will be inserted in btree
 -------------------------------------------------------------------------------*/

u_int16_t        CalcKeyRecordSize        (u_int16_t                 keySize,
                                           u_int16_t                 recSize )
{
    if ( M_IsOdd (keySize) )    keySize += 1;    // pad byte

    if (M_IsOdd (recSize) )        recSize += 1;    // pad byte

    return    (keySize + recSize);
}


/*-------------------------------------------------------------------------------
 Routine:    VerifyHeader    -    Validate fields of the BTree header record.

 Function:    Examines the fields of the BTree header record to determine if the
 fork appears to contain a valid BTree.

 Input:        forkPtr        - pointer to fork control block
 header        - pointer to BTree header


 Result:        noErr        - success
 != noErr    - failure
 -------------------------------------------------------------------------------*/

OSStatus    VerifyHeader    (FCB                *filePtr,
                             BTHeaderRec             *header )
{
    u_int64_t        forkSize;
    u_int32_t        totalNodes;


    switch (header->nodeSize)                            // node size == 512*2^n
    {
        case   512:
        case  1024:
        case  2048:
        case  4096:
        case  8192:
        case 16384:
        case 32768:        break;
        default:        return    fsBTInvalidHeaderErr;            //E_BadNodeType
    }

    totalNodes = header->totalNodes;

    forkSize = (u_int64_t)totalNodes * (u_int64_t)header->nodeSize;

    if ( forkSize > (u_int64_t)filePtr->fcbEOF )
        return fsBTInvalidHeaderErr;

    if ( header->freeNodes >= totalNodes )
        return fsBTInvalidHeaderErr;

    if ( header->rootNode >= totalNodes )
        return fsBTInvalidHeaderErr;

    if ( header->firstLeafNode >= totalNodes )
        return fsBTInvalidHeaderErr;

    if ( header->lastLeafNode >= totalNodes )
        return fsBTInvalidHeaderErr;

    if ( header->treeDepth > kMaxTreeDepth )
        return fsBTInvalidHeaderErr;


    /////////////////////////// Check BTree Type ////////////////////////////////

    switch (header->btreeType)
    {
        case    0:                    // HFS Type - no Key Descriptor
        case    kUserBTreeType:        // with Key Descriptors etc.
        case    kReservedBTreeType:    // Desktop Mgr BTree ?
            break;

        default:                    return fsBTUnknownVersionErr;
    }

    return noErr;
}


OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr)
{
    return (btreePtr->flags & kBTHeaderDirty);
}


/*-------------------------------------------------------------------------------
 Routine:    UpdateHeader    -    Write BTreeInfoRec fields to Header node.

 Function:    Checks the kBTHeaderDirty flag in the BTreeInfoRec and updates the
 header node if necessary.

 Input:        btreePtr        - pointer to BTreeInfoRec


 Result:        noErr        - success
 != noErr    - failure
 -------------------------------------------------------------------------------*/

OSStatus UpdateHeader(BTreeControlBlockPtr btreePtr, Boolean forceWrite)
{
    OSStatus                err;
    BlockDescriptor            node;
    BTHeaderRec    *header;
    u_int32_t options;

    if ((btreePtr->flags & kBTHeaderDirty) == 0)            // btree info already flushed
        return    noErr;

    err = GetNode (btreePtr, kHeaderNodeNum, 0, &node );
    if (err != noErr) {
        return    err;
    }

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

    header = (BTHeaderRec*) ((char *)node.buffer + sizeof(BTNodeDescriptor));

    header->treeDepth        = btreePtr->treeDepth;
    header->rootNode        = btreePtr->rootNode;
    header->leafRecords        = btreePtr->leafRecords;
    header->firstLeafNode    = btreePtr->firstLeafNode;
    header->lastLeafNode    = btreePtr->lastLeafNode;
    header->nodeSize        = btreePtr->nodeSize;            // this shouldn't change
    header->maxKeyLength    = btreePtr->maxKeyLength;        // neither should this
    header->totalNodes        = btreePtr->totalNodes;
    header->freeNodes        = btreePtr->freeNodes;
    header->btreeType        = btreePtr->btreeType;

    // ignore    header->clumpSize;                            // rename this field?

    if (forceWrite)
        options = kForceWriteBlock;
    else
        options = kLockTransaction;

    err = UpdateNode (btreePtr, &node, 0, options);

    btreePtr->flags &= (~kBTHeaderDirty);

    return    err;
}


/*-------------------------------------------------------------------------------
 Routine:    FindIteratorPosition    -    One_line_description.

 Function:    Brief_description_of_the_function_and_any_side_effects

 Algorithm:    see FSC.BT.BTIterateRecord.PICT

 Note:        // document side-effects of bad node hints

 Input:        btreePtr        - description
 iterator        - description


 Output:        iterator        - description
 left            - description
 middle            - description
 right            - description
 nodeNum            - description
 returnIndex        - description
 foundRecord        - description


 Result:        noErr        - success
 != noErr    - failure
 -------------------------------------------------------------------------------*/

OSStatus    FindIteratorPosition    (BTreeControlBlockPtr     btreePtr,
                                     BTreeIteratorPtr         iterator,
                                     BlockDescriptor        *left,
                                     BlockDescriptor        *middle,
                                     BlockDescriptor        *right,
                                     u_int32_t                *returnNodeNum,
                                     u_int16_t                *returnIndex,
                                     Boolean                *foundRecord )
{
    OSStatus        err;
    Boolean            foundIt;
    u_int32_t        nodeNum;
    u_int16_t        leftIndex,    index,    rightIndex;
    Boolean            validHint;

    // assume btreePtr valid
    // assume left, middle, right point to BlockDescriptors
    // assume nodeNum points to u_int32_t
    // assume index points to u_int16_t
    // assume foundRecord points to Boolean

    left->buffer        = nil;
    left->blockHeader   = nil;
    middle->buffer        = nil;
    middle->blockHeader    = nil;
    right->buffer        = nil;
    right->blockHeader    = nil;

    foundIt                = false;

    if (iterator == nil)                        // do we have an iterator?
    {
        err = fsBTInvalidIteratorErr;
        goto ErrorExit;
    }

    err = IsItAHint (btreePtr, iterator, &validHint);
    M_ExitOnError (err);

    nodeNum = iterator->hint.nodeNum;
    if (! validHint)                            // does the hint appear to be valid?
    {
        goto SearchTheTree;
    }

    err = GetNode (btreePtr, nodeNum, kGetNodeHint, middle);
    if( err == fsBTInvalidNodeErr )    // returned if nodeNum is out of range
        goto SearchTheTree;

    M_ExitOnError (err);

    if ( ((NodeDescPtr) middle->buffer)->kind != kBTLeafNode ||
        ((NodeDescPtr) middle->buffer)->numRecords <= 0 )
    {
        goto SearchTheTree;
    }

    foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index);
    if (foundIt == true)
    {
        ++btreePtr->numValidHints;
        goto SuccessfulExit;
    }
    iterator->hint.nodeNum = 0;

    if (index == 0)
    {
        if (((NodeDescPtr) middle->buffer)->bLink == 0)        // before 1st btree record
        {
            goto SuccessfulExit;
        }

        nodeNum = ((NodeDescPtr) middle->buffer)->bLink;

        // BTree nodes are always grabbed in left to right order.
        // Therefore release the current node before looking up the
        // left node.
        err = ReleaseNode(btreePtr, middle);
        M_ExitOnError(err);

        // Look up the left node
        err = GetNode (btreePtr, nodeNum, 0, left);
        M_ExitOnError (err);

        // Look up the current node again
        err = GetRightSiblingNode (btreePtr, left->buffer, middle);
        M_ExitOnError (err);

        if ( ((NodeDescPtr) left->buffer)->kind != kBTLeafNode ||
            ((NodeDescPtr) left->buffer)->numRecords <= 0 )
        {
            goto SearchTheTree;
        }

        foundIt = SearchNode (btreePtr, left->buffer, &iterator->key, &leftIndex);
        if (foundIt == true)
        {
            *right            = *middle;
            *middle            = *left;
            left->buffer    = nil;
            index            = leftIndex;

            goto SuccessfulExit;
        }

        if (leftIndex == 0)                                    // we're lost!
        {
            goto SearchTheTree;
        }
        else if (leftIndex >= ((NodeDescPtr) left->buffer)->numRecords)
        {
            nodeNum = ((NodeDescPtr) left->buffer)->fLink;
            if (index != 0)
            {
                LFHFS_LOG(LEVEL_ERROR, "FindIteratorPosition: index != 0\n");
                hfs_assert(0);
            }
            goto SuccessfulExit;
        }
        else
        {
            *right            = *middle;
            *middle            = *left;
            left->buffer    = nil;
            index            = leftIndex;

            goto SuccessfulExit;
        }
    }
    else if (index >= ((NodeDescPtr) middle->buffer)->numRecords)
    {
        if (((NodeDescPtr) middle->buffer)->fLink == 0)    // beyond last record
        {
            goto SuccessfulExit;
        }

        nodeNum = ((NodeDescPtr) middle->buffer)->fLink;

        err = GetRightSiblingNode (btreePtr, middle->buffer, right);
        M_ExitOnError (err);

        if ( ((NodeDescPtr) right->buffer)->kind != kBTLeafNode ||
            ((NodeDescPtr) right->buffer)->numRecords <= 0 )
        {
            goto SearchTheTree;
        }

        foundIt = SearchNode (btreePtr, right->buffer, &iterator->key, &rightIndex);
        if (rightIndex >= ((NodeDescPtr) right->buffer)->numRecords)        // we're lost
        {
            goto SearchTheTree;
        }
        else    // we found it, or rightIndex==0, or rightIndex<numRecs
        {
            *left            = *middle;
            *middle            = *right;
            right->buffer    = nil;
            index            = rightIndex;

            goto SuccessfulExit;
        }
    }


    //////////////////////////// Search The Tree ////////////////////////////////

SearchTheTree:
    {
        TreePathTable    treePathTable;        // so we only use stack space if we need to

        err = ReleaseNode (btreePtr, left);            M_ExitOnError (err);
        err = ReleaseNode (btreePtr, middle);        M_ExitOnError (err);
        err = ReleaseNode (btreePtr, right);        M_ExitOnError (err);

        err = SearchTree ( btreePtr, &iterator->key, treePathTable, &nodeNum, middle, &index);
        switch (err)                // separate find condition from exceptions
        {
            case noErr:            foundIt = true;                break;
            case fsBTRecordNotFoundErr:                        break;
            default:                goto ErrorExit;
        }
    }

    /////////////////////////////// Success! ////////////////////////////////////

SuccessfulExit:

    *returnNodeNum    = nodeNum;
    *returnIndex     = index;
    *foundRecord    = foundIt;

    return    noErr;


    ////////////////////////////// Error Exit ///////////////////////////////////

ErrorExit:

    (void)    ReleaseNode (btreePtr, left);
    (void)    ReleaseNode (btreePtr, middle);
    (void)    ReleaseNode (btreePtr, right);

    *returnNodeNum    = 0;
    *returnIndex     = 0;
    *foundRecord    = false;

    return    err;
}


/////////////////////////////// CheckInsertParams ///////////////////////////////

OSStatus    CheckInsertParams        (FCB                        *filePtr,
                                      BTreeIterator                *iterator,
                                      FSBufferDescriptor            *record,
                                      u_int16_t                     recordLen )
{
    BTreeControlBlockPtr    btreePtr;

    if (filePtr == nil)                                    return    paramErr;

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

    //    check total key/record size limit
    if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1))
        return    fsBTRecordTooLargeErr;

    return    noErr;
}


/*-------------------------------------------------------------------------------
 Routine:    TrySimpleReplace    -    Attempts a simple insert, set, or replace.

 Function:    If a hint exitst for the iterator, attempt to find the key in the hint
 node. If the key is found, an insert operation fails. If the is not
 found, a replace operation fails. If the key was not found, and the
 insert position is greater than 0 and less than numRecords, the record
 is inserted, provided there is enough freeSpace.  If the key was found,
 and there is more freeSpace than the difference between the new record
 and the old record, the old record is deleted and the new record is
 inserted.

 Assumptions:    iterator key has already been checked by CheckKey


 Input:        btreePtr        - description
 iterator        - description
 record            - description
 recordLen        - description
 operation        - description


 Output:        recordInserted        - description


 Result:        noErr            - success
 E_RecordExits        - insert operation failure
 != noErr        - GetNode, ReleaseNode, UpdateNode returned an error
 -------------------------------------------------------------------------------*/

OSStatus    TrySimpleReplace        (BTreeControlBlockPtr     btreePtr,
                                     NodeDescPtr             nodePtr,
                                     BTreeIterator            *iterator,
                                     FSBufferDescriptor        *record,
                                     u_int16_t                 recordLen,
                                     Boolean                *recordInserted )
{
    u_int32_t            oldSpace;
    u_int32_t            spaceNeeded;
    u_int16_t            index;
    u_int16_t            keySize;
    Boolean                foundIt;
    Boolean                didItFit;


    *recordInserted    = false;                                // we'll assume this won't work...

    if ( nodePtr->kind != kBTLeafNode )
        return    noErr;    // we're in the weeds!

    foundIt    = SearchNode (btreePtr, nodePtr, &iterator->key, &index);

    if ( foundIt == false )
        return    noErr;    // we might be lost...

    keySize = CalcKeySize(btreePtr, &iterator->key);    // includes length field

    spaceNeeded    = CalcKeyRecordSize (keySize, recordLen);

    oldSpace = GetRecordSize (btreePtr, nodePtr, index);

    if ( spaceNeeded == oldSpace )
    {
        u_int8_t *        dst;

        dst = GetRecordAddress (btreePtr, nodePtr, index);

        if ( M_IsOdd (keySize) )
            ++keySize;            // add pad byte

        dst += keySize;        // skip over key to point at record

        BlockMoveData(record->bufferAddress, dst, recordLen);    // blast away...

        *recordInserted = true;
    }
    else if ( (GetNodeFreeSize(btreePtr, nodePtr) + oldSpace) >= spaceNeeded)
    {
        DeleteRecord (btreePtr, nodePtr, index);

        didItFit = InsertKeyRecord (btreePtr, nodePtr, index,
                                    &iterator->key, KeyLength(btreePtr, &iterator->key),
                                    record->bufferAddress, recordLen);
        if (didItFit == false)
        {
            LFHFS_LOG(LEVEL_ERROR, "TrySimpleInsert: InsertKeyRecord returned false!");
            hfs_assert(0);
        }
        *recordInserted = true;
    }
    // else not enough space...

    return    noErr;
}


/*-------------------------------------------------------------------------------
 Routine:    IsItAHint    -    checks the hint within a BTreeInterator.

 Function:    checks the hint within a BTreeInterator.  If it is non-zero, it may
 possibly be valid.

 Input:        btreePtr    - pointer to control block for BTree file
 iterator    - pointer to BTreeIterator

 Output:        answer        - true if the hint looks reasonable
 - false if the hint is 0

 Result:        noErr            - success
 -------------------------------------------------------------------------------*/


OSStatus    IsItAHint    (BTreeControlBlockPtr btreePtr, BTreeIterator *iterator, Boolean *answer)
{
    ++btreePtr->numHintChecks;
    if (iterator->hint.nodeNum == 0)
    {
        *answer = false;
    }
    else
    {
        *answer = true;
        ++btreePtr->numPossibleHints;
    }

    return noErr;
}
Commit	Line	Data
de8ee011 A	1	//
	2	// lf_hfs_btree_misc_ops.c
	3	// livefiles_hfs
	4	//
	5	// Created by Yakov Ben Zaken on 22/03/2018.
	6	//
	7
	8	#include "lf_hfs_btrees_private.h"
	9	#include "lf_hfs_btrees_io.h"
	10	#include "lf_hfs_utils.h"
	11
	12	////////////////////////////// Routine Definitions //////////////////////////////
	13
	14	/*-------------------------------------------------------------------------------
	15	Routine: CalcKeyRecordSize - Return size of combined key/record structure.
	16
	17	Function: Rounds keySize and recSize so they will end on word boundaries.
	18	Does NOT add size of offset.
	19
	20	Input: keySize - length of key (including length field)
	21	recSize - length of record data
	22
	23	Output: none
	24
	25	Result: u_int16_t - size of combined key/record that will be inserted in btree
	26	-------------------------------------------------------------------------------*/
	27
	28	u_int16_t CalcKeyRecordSize (u_int16_t keySize,
	29	u_int16_t recSize )
	30	{
	31	if ( M_IsOdd (keySize) ) keySize += 1; // pad byte
	32
	33	if (M_IsOdd (recSize) ) recSize += 1; // pad byte
	34
	35	return (keySize + recSize);
	36	}
	37
	38
	39
	40	/*-------------------------------------------------------------------------------
	41	Routine: VerifyHeader - Validate fields of the BTree header record.
	42
	43	Function: Examines the fields of the BTree header record to determine if the
	44	fork appears to contain a valid BTree.
	45
	46	Input: forkPtr - pointer to fork control block
	47	header - pointer to BTree header
	48
	49
	50	Result: noErr - success
	51	!= noErr - failure
	52	-------------------------------------------------------------------------------*/
	53
	54	OSStatus VerifyHeader (FCB *filePtr,
	55	BTHeaderRec *header )
	56	{
	57	u_int64_t forkSize;
	58	u_int32_t totalNodes;
	59
	60
	61	switch (header->nodeSize) // node size == 512*2^n
	62	{
	63	case 512:
	64	case 1024:
65	case 2048:
66	case 4096:
67	case 8192:
68	case 16384:
69	case 32768: break;
70	default: return fsBTInvalidHeaderErr; //E_BadNodeType
71	}
72
73	totalNodes = header->totalNodes;
74
75	forkSize = (u_int64_t)totalNodes * (u_int64_t)header->nodeSize;
76
77	if ( forkSize > (u_int64_t)filePtr->fcbEOF )
78	return fsBTInvalidHeaderErr;
79
80	if ( header->freeNodes >= totalNodes )
81	return fsBTInvalidHeaderErr;
82
83	if ( header->rootNode >= totalNodes )
84	return fsBTInvalidHeaderErr;
85
86	if ( header->firstLeafNode >= totalNodes )
87	return fsBTInvalidHeaderErr;
88
89	if ( header->lastLeafNode >= totalNodes )
90	return fsBTInvalidHeaderErr;
91
92	if ( header->treeDepth > kMaxTreeDepth )
93	return fsBTInvalidHeaderErr;
94
95
96	/////////////////////////// Check BTree Type ////////////////////////////////
97
98	switch (header->btreeType)
99	{
100	case 0: // HFS Type - no Key Descriptor
101	case kUserBTreeType: // with Key Descriptors etc.
102	case kReservedBTreeType: // Desktop Mgr BTree ?
103	break;
104
105	default: return fsBTUnknownVersionErr;
106	}
107
108	return noErr;
109	}
110
111
112
113	OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr)
114	{
115	return (btreePtr->flags & kBTHeaderDirty);
116	}
117
118
119
120	/*-------------------------------------------------------------------------------
121	Routine: UpdateHeader - Write BTreeInfoRec fields to Header node.
122
123	Function: Checks the kBTHeaderDirty flag in the BTreeInfoRec and updates the
124	header node if necessary.
125
126	Input: btreePtr - pointer to BTreeInfoRec
127
128
129	Result: noErr - success
130	!= noErr - failure
131	-------------------------------------------------------------------------------*/
132
133	OSStatus UpdateHeader(BTreeControlBlockPtr btreePtr, Boolean forceWrite)
134	{
135	OSStatus err;
136	BlockDescriptor node;
137	BTHeaderRec *header;
138	u_int32_t options;
139
140	if ((btreePtr->flags & kBTHeaderDirty) == 0) // btree info already flushed
141	return noErr;
142
143	err = GetNode (btreePtr, kHeaderNodeNum, 0, &node );
144	if (err != noErr) {
145	return err;
146	}
147
148	// XXXdbg
149	ModifyBlockStart(btreePtr->fileRefNum, &node);
150
151	header = (BTHeaderRec) ((char )node.buffer + sizeof(BTNodeDescriptor));
152
153	header->treeDepth = btreePtr->treeDepth;
154	header->rootNode = btreePtr->rootNode;
155	header->leafRecords = btreePtr->leafRecords;
156	header->firstLeafNode = btreePtr->firstLeafNode;
157	header->lastLeafNode = btreePtr->lastLeafNode;
158	header->nodeSize = btreePtr->nodeSize; // this shouldn't change
159	header->maxKeyLength = btreePtr->maxKeyLength; // neither should this
160	header->totalNodes = btreePtr->totalNodes;
161	header->freeNodes = btreePtr->freeNodes;
162	header->btreeType = btreePtr->btreeType;
163
164	// ignore header->clumpSize; // rename this field?
165
166	if (forceWrite)
167	options = kForceWriteBlock;
168	else
169	options = kLockTransaction;
170
171	err = UpdateNode (btreePtr, &node, 0, options);
172
173	btreePtr->flags &= (~kBTHeaderDirty);
174
175	return err;
176	}
177
178
179
180	/*-------------------------------------------------------------------------------
181	Routine: FindIteratorPosition - One_line_description.
182
183	Function: Brief_description_of_the_function_and_any_side_effects
184
185	Algorithm: see FSC.BT.BTIterateRecord.PICT
186
187	Note: // document side-effects of bad node hints
188
189	Input: btreePtr - description
190	iterator - description
191
192
193	Output: iterator - description
194	left - description
195	middle - description
196	right - description
197	nodeNum - description
198	returnIndex - description
199	foundRecord - description
200
201
202	Result: noErr - success
203	!= noErr - failure
204	-------------------------------------------------------------------------------*/
205
206	OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr,
207	BTreeIteratorPtr iterator,
208	BlockDescriptor *left,
209	BlockDescriptor *middle,
210	BlockDescriptor *right,
211	u_int32_t *returnNodeNum,
212	u_int16_t *returnIndex,
213	Boolean *foundRecord )
214	{
215	OSStatus err;
216	Boolean foundIt;
217	u_int32_t nodeNum;
218	u_int16_t leftIndex, index, rightIndex;
219	Boolean validHint;
220
221	// assume btreePtr valid
222	// assume left, middle, right point to BlockDescriptors
223	// assume nodeNum points to u_int32_t
224	// assume index points to u_int16_t
225	// assume foundRecord points to Boolean
226
227	left->buffer = nil;
228	left->blockHeader = nil;
229	middle->buffer = nil;
230	middle->blockHeader = nil;
231	right->buffer = nil;
232	right->blockHeader = nil;
233
234	foundIt = false;
235
236	if (iterator == nil) // do we have an iterator?
237	{
238	err = fsBTInvalidIteratorErr;
239	goto ErrorExit;
240	}
241
242	err = IsItAHint (btreePtr, iterator, &validHint);
243	M_ExitOnError (err);
244
245	nodeNum = iterator->hint.nodeNum;
246	if (! validHint) // does the hint appear to be valid?
247	{
248	goto SearchTheTree;
249	}
250
251	err = GetNode (btreePtr, nodeNum, kGetNodeHint, middle);
252	if( err == fsBTInvalidNodeErr ) // returned if nodeNum is out of range
253	goto SearchTheTree;
254
255	M_ExitOnError (err);
256
257	if ( ((NodeDescPtr) middle->buffer)->kind != kBTLeafNode \|\|
258	((NodeDescPtr) middle->buffer)->numRecords <= 0 )
259	{
260	goto SearchTheTree;
261	}
262
263	foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index);
264	if (foundIt == true)
265	{
266	++btreePtr->numValidHints;
267	goto SuccessfulExit;
268	}
269	iterator->hint.nodeNum = 0;
270
271	if (index == 0)
272	{
273	if (((NodeDescPtr) middle->buffer)->bLink == 0) // before 1st btree record
274	{
275	goto SuccessfulExit;
276	}
277
278	nodeNum = ((NodeDescPtr) middle->buffer)->bLink;
279
280	// BTree nodes are always grabbed in left to right order.
281	// Therefore release the current node before looking up the
282	// left node.
283	err = ReleaseNode(btreePtr, middle);
284	M_ExitOnError(err);
285
286	// Look up the left node
287	err = GetNode (btreePtr, nodeNum, 0, left);
288	M_ExitOnError (err);
289
290	// Look up the current node again
291	err = GetRightSiblingNode (btreePtr, left->buffer, middle);
292	M_ExitOnError (err);
293
294	if ( ((NodeDescPtr) left->buffer)->kind != kBTLeafNode \|\|
295	((NodeDescPtr) left->buffer)->numRecords <= 0 )
296	{
297	goto SearchTheTree;
298	}
299
300	foundIt = SearchNode (btreePtr, left->buffer, &iterator->key, &leftIndex);
301	if (foundIt == true)
302	{
303	right = middle;
304	middle = left;
305	left->buffer = nil;
306	index = leftIndex;
307
308	goto SuccessfulExit;
309	}
310
311	if (leftIndex == 0) // we're lost!
312	{
313	goto SearchTheTree;
314	}
315	else if (leftIndex >= ((NodeDescPtr) left->buffer)->numRecords)
316	{
317	nodeNum = ((NodeDescPtr) left->buffer)->fLink;
318	if (index != 0)
319	{
320	LFHFS_LOG(LEVEL_ERROR, "FindIteratorPosition: index != 0\n");
321	hfs_assert(0);
322	}
323	goto SuccessfulExit;
324	}
325	else
326	{
327	right = middle;
328	middle = left;
329	left->buffer = nil;
330	index = leftIndex;
331
332	goto SuccessfulExit;
333	}
334	}
335	else if (index >= ((NodeDescPtr) middle->buffer)->numRecords)
336	{
337	if (((NodeDescPtr) middle->buffer)->fLink == 0) // beyond last record
338	{
339	goto SuccessfulExit;
340	}
341
342	nodeNum = ((NodeDescPtr) middle->buffer)->fLink;
343
344	err = GetRightSiblingNode (btreePtr, middle->buffer, right);
345	M_ExitOnError (err);
346
347	if ( ((NodeDescPtr) right->buffer)->kind != kBTLeafNode \|\|
348	((NodeDescPtr) right->buffer)->numRecords <= 0 )
349	{
350	goto SearchTheTree;
351	}
352
353	foundIt = SearchNode (btreePtr, right->buffer, &iterator->key, &rightIndex);
354	if (rightIndex >= ((NodeDescPtr) right->buffer)->numRecords) // we're lost
355	{
356	goto SearchTheTree;
357	}
358	else // we found it, or rightIndex==0, or rightIndex<numRecs
359	{
360	left = middle;
361	middle = right;
362	right->buffer = nil;
363	index = rightIndex;
364
365	goto SuccessfulExit;
366	}
367	}
368
369
370	//////////////////////////// Search The Tree ////////////////////////////////
371
372	SearchTheTree:
373	{
374	TreePathTable treePathTable; // so we only use stack space if we need to
375
376	err = ReleaseNode (btreePtr, left); M_ExitOnError (err);
377	err = ReleaseNode (btreePtr, middle); M_ExitOnError (err);
378	err = ReleaseNode (btreePtr, right); M_ExitOnError (err);
379
380	err = SearchTree ( btreePtr, &iterator->key, treePathTable, &nodeNum, middle, &index);
381	switch (err) // separate find condition from exceptions
382	{
383	case noErr: foundIt = true; break;
384	case fsBTRecordNotFoundErr: break;
385	default: goto ErrorExit;
386	}
387	}
388
389	/////////////////////////////// Success! ////////////////////////////////////
390
391	SuccessfulExit:
392
393	*returnNodeNum = nodeNum;
394	*returnIndex = index;
395	*foundRecord = foundIt;
396
397	return noErr;
398
399
400	////////////////////////////// Error Exit ///////////////////////////////////
401
402	ErrorExit:
403
404	(void) ReleaseNode (btreePtr, left);
405	(void) ReleaseNode (btreePtr, middle);
406	(void) ReleaseNode (btreePtr, right);
407
408	*returnNodeNum = 0;
409	*returnIndex = 0;
410	*foundRecord = false;
411
412	return err;
413	}
414
415
416
417	/////////////////////////////// CheckInsertParams ///////////////////////////////
418
419	OSStatus CheckInsertParams (FCB *filePtr,
420	BTreeIterator *iterator,
421	FSBufferDescriptor *record,
422	u_int16_t recordLen )
423	{
424	BTreeControlBlockPtr btreePtr;
425
426	if (filePtr == nil) return paramErr;
427
428	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
429	if (btreePtr == nil) return fsBTInvalidFileErr;
430	if (iterator == nil) return paramErr;
431	if (record == nil) return paramErr;
432
433	// check total key/record size limit
434	if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1))
435	return fsBTRecordTooLargeErr;
436
437	return noErr;
438	}
439
440
441
442	/*-------------------------------------------------------------------------------
443	Routine: TrySimpleReplace - Attempts a simple insert, set, or replace.
444
445	Function: If a hint exitst for the iterator, attempt to find the key in the hint
446	node. If the key is found, an insert operation fails. If the is not
447	found, a replace operation fails. If the key was not found, and the
448	insert position is greater than 0 and less than numRecords, the record
449	is inserted, provided there is enough freeSpace. If the key was found,
450	and there is more freeSpace than the difference between the new record
451	and the old record, the old record is deleted and the new record is
452	inserted.
453
454	Assumptions: iterator key has already been checked by CheckKey
455
456
457	Input: btreePtr - description
458	iterator - description
459	record - description
460	recordLen - description
461	operation - description
462
463
464	Output: recordInserted - description
465
466
467	Result: noErr - success
468	E_RecordExits - insert operation failure
469	!= noErr - GetNode, ReleaseNode, UpdateNode returned an error
470	-------------------------------------------------------------------------------*/
471
472	OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,
473	NodeDescPtr nodePtr,
474	BTreeIterator *iterator,
475	FSBufferDescriptor *record,
476	u_int16_t recordLen,
477	Boolean *recordInserted )
478	{
479	u_int32_t oldSpace;
480	u_int32_t spaceNeeded;
481	u_int16_t index;
482	u_int16_t keySize;
483	Boolean foundIt;
484	Boolean didItFit;
485
486
487	*recordInserted = false; // we'll assume this won't work...
488
489	if ( nodePtr->kind != kBTLeafNode )
490	return noErr; // we're in the weeds!
491
492	foundIt = SearchNode (btreePtr, nodePtr, &iterator->key, &index);
493
494	if ( foundIt == false )
495	return noErr; // we might be lost...
496
497	keySize = CalcKeySize(btreePtr, &iterator->key); // includes length field
498
499	spaceNeeded = CalcKeyRecordSize (keySize, recordLen);
500
501	oldSpace = GetRecordSize (btreePtr, nodePtr, index);
502
503	if ( spaceNeeded == oldSpace )
504	{
505	u_int8_t * dst;
506
507	dst = GetRecordAddress (btreePtr, nodePtr, index);
508
509	if ( M_IsOdd (keySize) )
510	++keySize; // add pad byte
511
512	dst += keySize; // skip over key to point at record
513
514	BlockMoveData(record->bufferAddress, dst, recordLen); // blast away...
515
516	*recordInserted = true;
517	}
518	else if ( (GetNodeFreeSize(btreePtr, nodePtr) + oldSpace) >= spaceNeeded)
519	{
520	DeleteRecord (btreePtr, nodePtr, index);
521
522	didItFit = InsertKeyRecord (btreePtr, nodePtr, index,
523	&iterator->key, KeyLength(btreePtr, &iterator->key),
524	record->bufferAddress, recordLen);
525	if (didItFit == false)
526	{
527	LFHFS_LOG(LEVEL_ERROR, "TrySimpleInsert: InsertKeyRecord returned false!");
528	hfs_assert(0);
529	}
530	*recordInserted = true;
531	}
532	// else not enough space...
533
534	return noErr;
535	}
536
537
538	/*-------------------------------------------------------------------------------
539	Routine: IsItAHint - checks the hint within a BTreeInterator.
540
541	Function: checks the hint within a BTreeInterator. If it is non-zero, it may
542	possibly be valid.
543
544	Input: btreePtr - pointer to control block for BTree file
545	iterator - pointer to BTreeIterator
546
547	Output: answer - true if the hint looks reasonable
548	- false if the hint is 0
549
550	Result: noErr - success
551	-------------------------------------------------------------------------------*/
552
553
554	OSStatus IsItAHint (BTreeControlBlockPtr btreePtr, BTreeIterator iterator, Boolean answer)
555	{
556	++btreePtr->numHintChecks;
557	if (iterator->hint.nodeNum == 0)
558	{
559	*answer = false;
560	}
561	else
562	{
563	*answer = true;
564	++btreePtr->numPossibleHints;
565	}
566
567	return noErr;
568	}