2
* Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
4
* @APPLE_LICENSE_HEADER_START@
6
* "Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7
* Reserved. This file contains Original Code and/or Modifications of
8
* Original Code as defined in and that are subject to the Apple Public
9
* Source License Version 1.0 (the 'License'). You may not use this file
10
* except in compliance with the License. Please obtain a copy of the
11
* License at http://www.apple.com/publicsource and read it before using
14
* The Original Code and all software distributed under the License are
15
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18
* FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19
* License for the specific language governing rights and limitations
22
* @APPLE_LICENSE_HEADER_END@
27
Contains: Miscellaneous operations for the BTree Module.
29
Version: xxx put the technology version here xxx
31
Written by: Gordon Sheridan and Bill Bruffey
33
Copyright: � 1992-1999 by Apple Computer, Inc., all rights reserved.
36
#include "BTreePrivate.h"
39
////////////////////////////// Routine Definitions //////////////////////////////
41
/*-------------------------------------------------------------------------------
42
Routine: CalcKeyRecordSize - Return size of combined key/record structure.
44
Function: Rounds keySize and recSize so they will end on word boundaries.
45
Does NOT add size of offset.
47
Input: keySize - length of key (including length field)
48
recSize - length of record data
52
Result: UInt16 - size of combined key/record that will be inserted in btree
53
-------------------------------------------------------------------------------*/
55
UInt16 CalcKeyRecordSize (UInt16 keySize,
58
if ( M_IsOdd (keySize) ) keySize += 1; // pad byte
60
if (M_IsOdd (recSize) ) recSize += 1; // pad byte
62
return (keySize + recSize);
67
/*-------------------------------------------------------------------------------
68
Routine: VerifyHeader - Validate fields of the BTree header record.
70
Function: Examines the fields of the BTree header record to determine if the
71
fork appears to contain a valid BTree.
73
Input: forkPtr - pointer to fork control block
74
header - pointer to BTree header
77
Result: noErr - success
79
-------------------------------------------------------------------------------*/
81
OSStatus VerifyHeader (SFCB *filePtr,
88
switch (header->nodeSize) // node size == 512*2^n
97
default: return fsBTInvalidHeaderErr; //�� E_BadNodeType
100
totalNodes = header->totalNodes;
102
forkSize = totalNodes * header->nodeSize;
104
if ( forkSize != filePtr->fcbLogicalSize )
105
return fsBTInvalidHeaderErr;
107
if ( header->freeNodes >= totalNodes )
108
return fsBTInvalidHeaderErr;
110
if ( header->rootNode >= totalNodes )
111
return fsBTInvalidHeaderErr;
113
if ( header->firstLeafNode >= totalNodes )
114
return fsBTInvalidHeaderErr;
116
if ( header->lastLeafNode >= totalNodes )
117
return fsBTInvalidHeaderErr;
119
if ( header->treeDepth > kMaxTreeDepth )
120
return fsBTInvalidHeaderErr;
123
/////////////////////////// Check BTree Type ////////////////////////////////
125
switch (header->btreeType)
127
case 0: // HFS Type - no Key Descriptor
128
case kUserBTreeType: // with Key Descriptors etc.
129
case kReservedBTreeType: // Desktop Mgr BTree ?
132
default: return fsBTUnknownVersionErr;
140
/*-------------------------------------------------------------------------------
141
Routine: UpdateHeader - Write BTreeInfoRec fields to Header node.
143
Function: Checks the kBTHeaderDirty flag in the BTreeInfoRec and updates the
144
header node if necessary.
146
Input: btreePtr - pointer to BTreeInfoRec
149
Result: noErr - success
151
-------------------------------------------------------------------------------*/
153
OSStatus UpdateHeader (BTreeControlBlockPtr btreePtr)
156
BlockDescriptor node;
160
if ((btreePtr->flags & kBTHeaderDirty) == 0) // btree info already flushed
164
err = GetNode (btreePtr, kHeaderNodeNum, &node );
168
header = (BTHeaderRec*) (node.buffer + sizeof(BTNodeDescriptor));
170
header->treeDepth = btreePtr->treeDepth;
171
header->rootNode = btreePtr->rootNode;
172
header->leafRecords = btreePtr->leafRecords;
173
header->firstLeafNode = btreePtr->firstLeafNode;
174
header->lastLeafNode = btreePtr->lastLeafNode;
175
header->nodeSize = btreePtr->nodeSize; //�� this shouldn't change
176
header->maxKeyLength = btreePtr->maxKeyLength; //�� neither should this
177
header->totalNodes = btreePtr->totalNodes;
178
header->freeNodes = btreePtr->freeNodes;
179
header->btreeType = btreePtr->btreeType;
181
// ignore header->clumpSize; //�� rename this field?
183
err = UpdateNode (btreePtr, &node);
185
btreePtr->flags &= (~kBTHeaderDirty);
192
/*-------------------------------------------------------------------------------
193
Routine: FindIteratorPosition - One_line_description.
195
Function: Brief_description_of_the_function_and_any_side_effects
197
Algorithm: see FSC.BT.BTIterateRecord.PICT
199
Note: //�� document side-effects of bad node hints
201
Input: btreePtr - description
202
iterator - description
205
Output: iterator - description
209
nodeNum - description
210
returnIndex - description
211
foundRecord - description
214
Result: noErr - success
216
-------------------------------------------------------------------------------*/
218
OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr,
219
BTreeIteratorPtr iterator,
220
BlockDescriptor *left,
221
BlockDescriptor *middle,
222
BlockDescriptor *right,
223
UInt32 *returnNodeNum,
225
Boolean *foundRecord )
230
UInt16 leftIndex, index, rightIndex;
233
// assume btreePtr valid
234
// assume left, middle, right point to BlockDescriptors
235
// assume nodeNum points to UInt32
236
// assume index points to UInt16
237
// assume foundRecord points to Boolean
240
middle->buffer = nil;
245
if (iterator == nil) // do we have an iterator?
247
err = fsBTInvalidIteratorErr;
251
#if SupportsKeyDescriptors
252
//�� verify iterator key (change CheckKey to take btreePtr instead of keyDescPtr?)
253
if (btreePtr->keyDescPtr != nil)
255
err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength );
260
err = IsItAHint (btreePtr, iterator, &validHint);
263
nodeNum = iterator->hint.nodeNum;
264
if (! validHint) // does the hint appear to be valid?
269
err = GetNode (btreePtr, nodeNum, middle);
270
if( err == fsBTInvalidNodeErr ) // returned if nodeNum is out of range
275
if ( ((NodeDescPtr) middle->buffer)->kind != kBTLeafNode ||
276
((NodeDescPtr) middle->buffer)->numRecords <= 0 )
281
++btreePtr->numValidHints;
283
foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index);
291
if (((NodeDescPtr) middle->buffer)->bLink == 0) // before 1st btree record
296
nodeNum = ((NodeDescPtr) middle->buffer)->bLink;
298
err = GetLeftSiblingNode (btreePtr, middle->buffer, left);
301
if ( ((NodeDescPtr) left->buffer)->kind != kBTLeafNode ||
302
((NodeDescPtr) left->buffer)->numRecords <= 0 )
307
foundIt = SearchNode (btreePtr, left->buffer, &iterator->key, &leftIndex);
318
if (leftIndex == 0) // we're lost!
322
else if (leftIndex >= ((NodeDescPtr) left->buffer)->numRecords)
324
nodeNum = ((NodeDescPtr) left->buffer)->fLink;
326
PanicIf (index != 0, "\pFindIteratorPosition: index != 0"); //�� just checking...
339
else if (index >= ((NodeDescPtr) middle->buffer)->numRecords)
341
if (((NodeDescPtr) middle->buffer)->fLink == 0) // beyond last record
346
nodeNum = ((NodeDescPtr) middle->buffer)->fLink;
348
err = GetRightSiblingNode (btreePtr, middle->buffer, right);
351
if ( ((NodeDescPtr) right->buffer)->kind != kBTLeafNode ||
352
((NodeDescPtr) right->buffer)->numRecords <= 0 )
357
foundIt = SearchNode (btreePtr, right->buffer, &iterator->key, &rightIndex);
358
if (rightIndex >= ((NodeDescPtr) right->buffer)->numRecords) // we're lost
362
else // we found it, or rightIndex==0, or rightIndex<numRecs
374
//////////////////////////// Search The Tree ////////////////////////////////
378
TreePathTable treePathTable; // so we only use stack space if we need to
380
err = ReleaseNode (btreePtr, left); M_ExitOnError (err);
381
err = ReleaseNode (btreePtr, middle); M_ExitOnError (err);
382
err = ReleaseNode (btreePtr, right); M_ExitOnError (err);
384
err = SearchTree ( btreePtr, &iterator->key, treePathTable, &nodeNum, middle, &index);
385
switch (err) //�� separate find condition from exceptions
387
case noErr: foundIt = true; break;
388
case fsBTRecordNotFoundErr: break;
389
default: goto ErrorExit;
393
/////////////////////////////// Success! ////////////////////////////////////
397
*returnNodeNum = nodeNum;
398
*returnIndex = index;
399
*foundRecord = foundIt;
404
////////////////////////////// Error Exit ///////////////////////////////////
408
(void) ReleaseNode (btreePtr, left);
409
(void) ReleaseNode (btreePtr, middle);
410
(void) ReleaseNode (btreePtr, right);
414
*foundRecord = false;
421
/////////////////////////////// CheckInsertParams ///////////////////////////////
423
OSStatus CheckInsertParams (SFCB *filePtr,
424
BTreeIterator *iterator,
425
FSBufferDescriptor *record,
428
BTreeControlBlockPtr btreePtr;
430
if (filePtr == nil) return paramErr;
432
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
433
if (btreePtr == nil) return fsBTInvalidFileErr;
434
if (iterator == nil) return paramErr;
435
if (record == nil) return paramErr;
437
#if SupportsKeyDescriptors
438
if (btreePtr->keyDescPtr != nil)
442
err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength);
448
// check total key/record size limit
449
if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1))
450
return fsBTRecordTooLargeErr;
457
/*-------------------------------------------------------------------------------
458
Routine: TrySimpleReplace - Attempts a simple insert, set, or replace.
460
Function: If a hint exitst for the iterator, attempt to find the key in the hint
461
node. If the key is found, an insert operation fails. If the is not
462
found, a replace operation fails. If the key was not found, and the
463
insert position is greater than 0 and less than numRecords, the record
464
is inserted, provided there is enough freeSpace. If the key was found,
465
and there is more freeSpace than the difference between the new record
466
and the old record, the old record is deleted and the new record is
469
Assumptions: iterator key has already been checked by CheckKey
472
Input: btreePtr - description
473
iterator - description
475
recordLen - description
476
operation - description
479
Output: recordInserted - description
482
Result: noErr - success
483
E_RecordExits - insert operation failure
484
!= noErr - GetNode, ReleaseNode, UpdateNode returned an error
485
-------------------------------------------------------------------------------*/
487
OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,
489
BTreeIterator *iterator,
490
FSBufferDescriptor *record,
492
Boolean *recordInserted )
502
*recordInserted = false; // we'll assume this won't work...
504
if ( nodePtr->kind != kBTLeafNode )
505
return noErr; // we're in the weeds!
507
foundIt = SearchNode (btreePtr, nodePtr, &iterator->key, &index);
509
if ( foundIt == false )
510
return noErr; // we might be lost...
512
keySize = CalcKeySize(btreePtr, &iterator->key); // includes length field
514
spaceNeeded = CalcKeyRecordSize (keySize, recordLen);
516
oldSpace = GetRecordSize (btreePtr, nodePtr, index);
518
if ( spaceNeeded == oldSpace )
522
dst = GetRecordAddress (btreePtr, nodePtr, index);
524
if ( M_IsOdd (keySize) )
525
++keySize; // add pad byte
527
dst += keySize; // skip over key to point at record
529
CopyMemory(record->bufferAddress, dst, recordLen); // blast away...
531
*recordInserted = true;
533
else if ( (GetNodeFreeSize(btreePtr, nodePtr) + oldSpace) >= spaceNeeded)
535
DeleteRecord (btreePtr, nodePtr, index);
537
didItFit = InsertKeyRecord (btreePtr, nodePtr, index,
538
&iterator->key, KeyLength(btreePtr, &iterator->key),
539
record->bufferAddress, recordLen);
540
PanicIf (didItFit == false, "\pTrySimpleInsert: InsertKeyRecord returned false!");
542
*recordInserted = true;
544
// else not enough space...
550
/*-------------------------------------------------------------------------------
551
Routine: IsItAHint - checks the hint within a BTreeInterator.
553
Function: checks the hint within a BTreeInterator. If it is non-zero, it may
556
Input: btreePtr - pointer to control block for BTree file
557
iterator - pointer to BTreeIterator
559
Output: answer - true if the hint looks reasonable
560
- false if the hint is 0
562
Result: noErr - success
563
-------------------------------------------------------------------------------*/
566
OSStatus IsItAHint (BTreeControlBlockPtr btreePtr, BTreeIterator *iterator, Boolean *answer)
568
++btreePtr->numHintChecks;
570
//�� shouldn't we do a range check?
571
if (iterator->hint.nodeNum == 0)
578
++btreePtr->numPossibleHints;
added
removed
.pc/91-remove-nils.patch/fsck_hfs.tproj/dfalib/BTreeMiscOps.c
