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