![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to BTreeMiscOps.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / BTree|
Return to BTreeMiscOps.c CVS log | Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / BTree |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.1 (the "License"). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License.
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24:
25: /*
26: File: BTreeMiscOps.c
27:
28: Contains: Miscellaneous operations for the BTree Module.
29:
30: Version: xxx put the technology version here xxx
31:
32: Written by: Gordon Sheridan and Bill Bruffey
33:
34: Copyright: � 1992-1997 by Apple Computer, Inc., all rights reserved.
35:
36: File Ownership:
37:
38: DRI: Don Brady
39:
40: Other Contact: Mark Day
41:
42: Technology: File Systems
43:
44: Writers:
45:
46: (DSH) Deric Horn
47: (msd) Mark Day
48: (djb) Don Brady
49:
50: Change History (most recent first):
51:
52: <CS2> 9/4/97 djb Optimize TrySimpleReplace for the case where record size is not
53: changing.
54: <CS1> 4/23/97 djb first checked in
55:
56: <HFS7> 3/31/97 djb Move ClearMemory to Utilities.c.
57: <HFS6> 3/17/97 DSH Casting for DFA
58: <HFS5> 2/27/97 msd Remove temporary fix from last revision. BTree EOF's should be
59: correct now, so check for strict equality.
60: <HFS4> 2/26/97 msd Fix a casting problem in ClearMemory. TEMPORARY FIX: Made
61: VerifyHeader more lenient, allowing the EOF to be greater than
62: the amount actually used by nodes; this should really be fixed
63: in the formatting code (which needs to compute the real BTree
64: sizes before writing the volume header).
65: <HFS3> 2/19/97 djb Added ClearMemory. Changed CalcKeyLength to KeyLength.
66: <HFS2> 1/3/97 djb Added support for large keys.
67: <HFS1> 12/19/96 djb first checked in
68:
69: History applicable to original Scarecrow Design:
70:
71: <9> 10/25/96 ser Changing for new VFPI
72: <8> 10/18/96 ser Converting over VFPI changes
73: <7> 9/17/96 dkh More BTree statistics. Change IsItAHint to not always check to
74: see if the hint node is allocated.
75: <6> 9/16/96 dkh Revised BTree statistics.
76: <5> 6/20/96 dkh Radar #1358740. Change from using Pools to debug MemAllocators.
77: <4> 1/22/96 dkh Change Pools.i inclusion to PoolsPriv.i
78: <3> 1/10/96 msd Change 64-bit math to use real function names from Math64.i.
79: <2> 12/7/95 dkh D10E2 build. Changed usage of Ref data type to LogicalAddress.
80: <1> 10/18/95 rst Moved from Scarecrow project.
81:
82: <19> 4/26/95 prp In UpdateHeader, clear the dirty flag after the BTree is updated.
83: <18> 1/12/95 wjk Adopt Model FileSystem changes in D5.
84: <17> 11/16/94 prp Add IsItAHint routine and use it whenever hint's node number was
85: used for testing.
86: <16> 10/5/94 bk add pools.h include file
87: <15> 9/30/94 prp Get in sync with D2 interface changes.
88: <14> 7/22/94 wjk Convert to the new set of header files.
89: <13> 12/2/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
90: NRCmds environments.
91: <12> 11/30/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
92: NRCmds environments.
93: <11> 11/23/93 wjk Changes required to compile on the RS6000.
94: <10> 8/31/93 prp Use U64SetU instead of S64Set.
95: <9> 6/2/93 gs Update for changes to FSErrors.h and add some comments.
96: <8> 5/21/93 gs Modify UpdateHeader to write out attributes. Remove
97: Get/UpdateNode from TrySimpleReplace.
98: <7> 5/10/93 gs Add TrySimpleReplace routine.
99: <6> 3/23/93 gs Change MoveData to take void * instead of Ptr. Add UpdateHeader
100: and ClearBytes routines.
101: <5> 2/8/93 gs Add FindIteratorPosition.
102: <4> 12/10/92 gs Implement CheckKeyDescriptor and the KeyDescriptor interpreter.
103: <3> 12/8/92 gs Add GetKeyDescriptor, VerifyHeader, and Alloc/Dealloc memory
104: routines.
105: <2> 12/2/92 gs Add CompareKeys routine.
106: <1> 11/15/92 gs first checked in
107:
108: */
109:
110: #include "../headers/BTreesPrivate.h"
111:
112:
113: ////////////////////////////// Routine Definitions //////////////////////////////
114:
115: /*-------------------------------------------------------------------------------
116: Routine: CalcKeyRecordSize - Return size of combined key/record structure.
117:
118: Function: Rounds keySize and recSize so they will end on word boundaries.
119: Does NOT add size of offset.
120:
121: Input: keySize - length of key (including length field)
122: recSize - length of record data
123:
124: Output: none
125:
126: Result: UInt16 - size of combined key/record that will be inserted in btree
127: -------------------------------------------------------------------------------*/
128:
129: UInt16 CalcKeyRecordSize (UInt16 keySize,
130: UInt16 recSize )
131: {
132: if ( M_IsOdd (keySize) ) keySize += 1; // pad byte
133:
134: if (M_IsOdd (recSize) ) recSize += 1; // pad byte
135:
136: return (keySize + recSize);
137: }
138:
139:
140:
141: /*-------------------------------------------------------------------------------
142: Routine: VerifyHeader - Validate fields of the BTree header record.
143:
144: Function: Examines the fields of the BTree header record to determine if the
145: fork appears to contain a valid BTree.
146:
147: Input: forkPtr - pointer to fork control block
148: header - pointer to BTree header
149:
150:
151: Result: noErr - success
152: != noErr - failure
153: -------------------------------------------------------------------------------*/
154:
155: OSStatus VerifyHeader (FCB *filePtr,
156: HeaderPtr header )
157: {
158: UInt32 forkSize;
159: UInt32 totalNodes;
160:
161:
162: switch (header->nodeSize) // node size == 512*2^n
163: {
164: case 512:
165: case 1024:
166: case 2048:
167: case 4096:
168: case 8192:
169: case 16384:
170: case 32768: break;
171: default: return fsBTInvalidHeaderErr; //�� E_BadNodeType
172: }
173:
174: totalNodes = header->totalNodes;
175:
176: forkSize = totalNodes * header->nodeSize;
177:
178: if ( forkSize != filePtr->fcbEOF )
179: return fsBTInvalidHeaderErr;
180:
181: if ( header->freeNodes >= totalNodes )
182: return fsBTInvalidHeaderErr;
183:
184: if ( header->rootNode >= totalNodes )
185: return fsBTInvalidHeaderErr;
186:
187: if ( header->firstLeafNode >= totalNodes )
188: return fsBTInvalidHeaderErr;
189:
190: if ( header->lastLeafNode >= totalNodes )
191: return fsBTInvalidHeaderErr;
192:
193: if ( header->treeDepth > kMaxTreeDepth )
194: return fsBTInvalidHeaderErr;
195:
196:
197: /////////////////////////// Check BTree Type ////////////////////////////////
198:
199: switch (header->btreeType)
200: {
201: case 0: // HFS Type - no Key Descriptor
202: case kUserBTreeType: // with Key Descriptors etc.
203: case kReservedBTreeType: // Desktop Mgr BTree ?
204: break;
205:
206: default: return fsBTUnknownVersionErr;
207: }
208:
209: return noErr;
210: }
211:
212:
213:
214: /*-------------------------------------------------------------------------------
215: Routine: UpdateHeader - Write BTreeInfoRec fields to Header node.
216:
217: Function: Checks the kBTHeaderDirty flag in the BTreeInfoRec and updates the
218: header node if necessary.
219:
220: Input: btreePtr - pointer to BTreeInfoRec
221:
222:
223: Result: noErr - success
224: != noErr - failure
225: -------------------------------------------------------------------------------*/
226:
227: OSStatus UpdateHeader (BTreeControlBlockPtr btreePtr)
228: {
229: OSStatus err;
230: BlockDescriptor node;
231: HeaderPtr header;
232:
233:
234: if ((btreePtr->flags & kBTHeaderDirty) == 0) // btree info already flushed
235: return noErr;
236:
237:
238: err = GetNode (btreePtr, kHeaderNodeNum, &node );
239: if (err != noErr)
240: return err;
241:
242: header = node.buffer;
243:
244: header->treeDepth = btreePtr->treeDepth;
245: header->rootNode = btreePtr->rootNode;
246: header->leafRecords = btreePtr->leafRecords;
247: header->firstLeafNode = btreePtr->firstLeafNode;
248: header->lastLeafNode = btreePtr->lastLeafNode;
249: header->nodeSize = btreePtr->nodeSize; //�� this shouldn't change
250: header->maxKeyLength = btreePtr->maxKeyLength; //�� neither should this
251: header->totalNodes = btreePtr->totalNodes;
252: header->freeNodes = btreePtr->freeNodes;
253: header->btreeType = btreePtr->btreeType;
254:
255: // ignore header->clumpSize; //�� rename this field?
256:
257: err = UpdateNode (btreePtr, &node);
258:
259: btreePtr->flags &= (~kBTHeaderDirty);
260:
261: return err;
262: }
263:
264:
265:
266: /*-------------------------------------------------------------------------------
267: Routine: FindIteratorPosition - One_line_description.
268:
269: Function: Brief_description_of_the_function_and_any_side_effects
270:
271: Algorithm: see FSC.BT.BTIterateRecord.PICT
272:
273: Note: //�� document side-effects of bad node hints
274:
275: Input: btreePtr - description
276: iterator - description
277:
278:
279: Output: iterator - description
280: left - description
281: middle - description
282: right - description
283: nodeNum - description
284: returnIndex - description
285: foundRecord - description
286:
287:
288: Result: noErr - success
289: != noErr - failure
290: -------------------------------------------------------------------------------*/
291:
292: OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr,
293: BTreeIteratorPtr iterator,
294: BlockDescriptor *left,
295: BlockDescriptor *middle,
296: BlockDescriptor *right,
297: UInt32 *returnNodeNum,
298: UInt16 *returnIndex,
299: Boolean *foundRecord )
300: {
301: OSStatus err;
302: Boolean foundIt;
303: UInt32 nodeNum;
304: UInt16 leftIndex, index, rightIndex;
305: Boolean validHint;
306:
307: // assume btreePtr valid
308: // assume left, middle, right point to BlockDescriptors
309: // assume nodeNum points to UInt32
310: // assume index points to UInt16
311: // assume foundRecord points to Boolean
312:
313: left->buffer = nil;
314: middle->buffer = nil;
315: right->buffer = nil;
316:
317: foundIt = false;
318:
319: if (iterator == nil) // do we have an iterator?
320: {
321: err = fsBTInvalidIteratorErr;
322: goto ErrorExit;
323: }
324:
325: #if SupportsKeyDescriptors
326: //�� verify iterator key (change CheckKey to take btreePtr instead of keyDescPtr?)
327: if (btreePtr->keyDescPtr != nil)
328: {
329: err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength );
330: M_ExitOnError (err);
331: }
332: #endif
333:
334: err = IsItAHint (btreePtr, iterator, &validHint);
335: M_ExitOnError (err);
336:
337: nodeNum = iterator->hint.nodeNum;
338: if (! validHint) // does the hint appear to be valid?
339: {
340: goto SearchTheTree;
341: }
342:
343: err = GetNode (btreePtr, nodeNum, middle);
344: if( err == fsBTInvalidNodeErr ) // returned if nodeNum is out of range
345: goto SearchTheTree;
346:
347: M_ExitOnError (err);
348:
349: if ( ((NodeDescPtr) middle->buffer)->type != kLeafNode ||
350: ((NodeDescPtr) middle->buffer)->numRecords <= 0 )
351: {
352: goto SearchTheTree;
353: }
354:
355: ++btreePtr->numValidHints;
356:
357: foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index);
358: if (foundIt == true)
359: {
360: goto SuccessfulExit;
361: }
362:
363: if (index == 0)
364: {
365: if (((NodeDescPtr) middle->buffer)->bLink == 0) // before 1st btree record
366: {
367: goto SuccessfulExit;
368: }
369:
370: nodeNum = ((NodeDescPtr) middle->buffer)->bLink;
371:
372: err = GetLeftSiblingNode (btreePtr, middle->buffer, left);
373: M_ExitOnError (err);
374:
375: if ( ((NodeDescPtr) left->buffer)->type != kLeafNode ||
376: ((NodeDescPtr) left->buffer)->numRecords <= 0 )
377: {
378: goto SearchTheTree;
379: }
380:
381: foundIt = SearchNode (btreePtr, left->buffer, &iterator->key, &leftIndex);
382: if (foundIt == true)
383: {
384: *right = *middle;
385: *middle = *left;
386: left->buffer = nil;
387: index = leftIndex;
388:
389: goto SuccessfulExit;
390: }
391:
392: if (leftIndex == 0) // we're lost!
393: {
394: goto SearchTheTree;
395: }
396: else if (leftIndex >= ((NodeDescPtr) left->buffer)->numRecords)
397: {
398: nodeNum = ((NodeDescPtr) left->buffer)->fLink;
399:
400: PanicIf (index != 0, "\pFindIteratorPosition: index != 0"); //�� just checking...
401: goto SuccessfulExit;
402: }
403: else
404: {
405: *right = *middle;
406: *middle = *left;
407: left->buffer = nil;
408: index = leftIndex;
409:
410: goto SuccessfulExit;
411: }
412: }
413: else if (index >= ((NodeDescPtr) middle->buffer)->numRecords)
414: {
415: if (((NodeDescPtr) middle->buffer)->fLink == 0) // beyond last record
416: {
417: goto SuccessfulExit;
418: }
419:
420: nodeNum = ((NodeDescPtr) middle->buffer)->fLink;
421:
422: err = GetRightSiblingNode (btreePtr, middle->buffer, right);
423: M_ExitOnError (err);
424:
425: if ( ((NodeDescPtr) right->buffer)->type != kLeafNode ||
426: ((NodeDescPtr) right->buffer)->numRecords <= 0 )
427: {
428: goto SearchTheTree;
429: }
430:
431: foundIt = SearchNode (btreePtr, right->buffer, &iterator->key, &rightIndex);
432: if (rightIndex >= ((NodeDescPtr) right->buffer)->numRecords) // we're lost
433: {
434: goto SearchTheTree;
435: }
436: else // we found it, or rightIndex==0, or rightIndex<numRecs
437: {
438: *left = *middle;
439: *middle = *right;
440: right->buffer = nil;
441: index = rightIndex;
442:
443: goto SuccessfulExit;
444: }
445: }
446:
447:
448: //////////////////////////// Search The Tree ////////////////////////////////
449:
450: SearchTheTree:
451: {
452: TreePathTable treePathTable; // so we only use stack space if we need to
453:
454: err = ReleaseNode (btreePtr, left); M_ExitOnError (err);
455: err = ReleaseNode (btreePtr, middle); M_ExitOnError (err);
456: err = ReleaseNode (btreePtr, right); M_ExitOnError (err);
457:
458: err = SearchTree ( btreePtr, &iterator->key, treePathTable, &nodeNum, middle, &index);
459: switch (err) //�� separate find condition from exceptions
460: {
461: case noErr: foundIt = true; break;
462: case fsBTRecordNotFoundErr: break;
463: default: goto ErrorExit;
464: }
465: }
466:
467: /////////////////////////////// Success! ////////////////////////////////////
468:
469: SuccessfulExit:
470:
471: *returnNodeNum = nodeNum;
472: *returnIndex = index;
473: *foundRecord = foundIt;
474:
475: return noErr;
476:
477:
478: ////////////////////////////// Error Exit ///////////////////////////////////
479:
480: ErrorExit:
481:
482: (void) ReleaseNode (btreePtr, left);
483: (void) ReleaseNode (btreePtr, middle);
484: (void) ReleaseNode (btreePtr, right);
485:
486: *returnNodeNum = 0;
487: *returnIndex = 0;
488: *foundRecord = false;
489:
490: return err;
491: }
492:
493:
494:
495: /////////////////////////////// CheckInsertParams ///////////////////////////////
496:
497: OSStatus CheckInsertParams (FCB *filePtr,
498: BTreeIterator *iterator,
499: FSBufferDescriptor *record,
500: UInt16 recordLen )
501: {
502: BTreeControlBlockPtr btreePtr;
503:
504: if (filePtr == nil) return paramErr;
505:
506: btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
507: if (btreePtr == nil) return fsBTInvalidFileErr;
508: if (iterator == nil) return paramErr;
509: if (record == nil) return paramErr;
510:
511: #if SupportsKeyDescriptors
512: if (btreePtr->keyDescPtr != nil)
513: {
514: OSStatus err;
515:
516: err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength);
517: if (err != noErr)
518: return err;
519: }
520: #endif
521:
522: // check total key/record size limit
523: if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1))
524: return fsBTRecordTooLargeErr;
525:
526: return noErr;
527: }
528:
529:
530:
531: /*-------------------------------------------------------------------------------
532: Routine: TrySimpleReplace - Attempts a simple insert, set, or replace.
533:
534: Function: If a hint exitst for the iterator, attempt to find the key in the hint
535: node. If the key is found, an insert operation fails. If the is not
536: found, a replace operation fails. If the key was not found, and the
537: insert position is greater than 0 and less than numRecords, the record
538: is inserted, provided there is enough freeSpace. If the key was found,
539: and there is more freeSpace than the difference between the new record
540: and the old record, the old record is deleted and the new record is
541: inserted.
542:
543: Assumptions: iterator key has already been checked by CheckKey
544:
545:
546: Input: btreePtr - description
547: iterator - description
548: record - description
549: recordLen - description
550: operation - description
551:
552:
553: Output: recordInserted - description
554:
555:
556: Result: noErr - success
557: E_RecordExits - insert operation failure
558: != noErr - GetNode, ReleaseNode, UpdateNode returned an error
559: -------------------------------------------------------------------------------*/
560:
561: OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,
562: NodeDescPtr nodePtr,
563: BTreeIterator *iterator,
564: FSBufferDescriptor *record,
565: UInt16 recordLen,
566: Boolean *recordInserted )
567: {
568: UInt32 oldSpace;
569: UInt32 spaceNeeded;
570: UInt16 index;
571: UInt16 keySize;
572: Boolean foundIt;
573: Boolean didItFit;
574:
575:
576: *recordInserted = false; // we'll assume this won't work...
577:
578: if ( nodePtr->type != kLeafNode )
579: return noErr; // we're in the weeds!
580:
581: foundIt = SearchNode (btreePtr, nodePtr, &iterator->key, &index);
582:
583: if ( foundIt == false )
584: return noErr; // we might be lost...
585:
586: keySize = CalcKeySize(btreePtr, &iterator->key); // includes length field
587:
588: spaceNeeded = CalcKeyRecordSize (keySize, recordLen);
589:
590: oldSpace = GetRecordSize (btreePtr, nodePtr, index);
591:
592: if ( spaceNeeded == oldSpace )
593: {
594: UInt8 * dst;
595:
596: dst = GetRecordAddress (btreePtr, nodePtr, index);
597:
598: if ( M_IsOdd (keySize) )
599: ++keySize; // add pad byte
600:
601: dst += keySize; // skip over key to point at record
602:
603: BlockMoveData(record->bufferAddress, dst, recordLen); // blast away...
604:
605: *recordInserted = true;
606: }
607: else if ( (GetNodeFreeSize(btreePtr, nodePtr) + oldSpace) >= spaceNeeded)
608: {
609: DeleteRecord (btreePtr, nodePtr, index);
610:
611: didItFit = InsertKeyRecord (btreePtr, nodePtr, index,
612: &iterator->key, KeyLength(btreePtr, &iterator->key),
613: record->bufferAddress, recordLen);
614: PanicIf (didItFit == false, "\pTrySimpleInsert: InsertKeyRecord returned false!");
615:
616: *recordInserted = true;
617: }
618: // else not enough space...
619:
620: return noErr;
621: }
622:
623:
624: /*-------------------------------------------------------------------------------
625: Routine: IsItAHint - checks the hint within a BTreeInterator.
626:
627: Function: checks the hint within a BTreeInterator. If it is non-zero, it may
628: possibly be valid.
629:
630: Input: btreePtr - pointer to control block for BTree file
631: iterator - pointer to BTreeIterator
632:
633: Output: answer - true if the hint looks reasonable
634: - false if the hint is 0
635:
636: Result: noErr - success
637: -------------------------------------------------------------------------------*/
638:
639:
640: OSStatus IsItAHint (BTreeControlBlockPtr btreePtr, BTreeIterator *iterator, Boolean *answer)
641: {
642: ++btreePtr->numHintChecks;
643:
644: //�� shouldn't we do a range check?
645: if (iterator->hint.nodeNum == 0)
646: {
647: *answer = false;
648: }
649: else
650: {
651: *answer = true;
652: ++btreePtr->numPossibleHints;
653: }
654:
655: return noErr;
656: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.