![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to BTree.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 BTree.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: BTree.c
24:
25: Contains: Implementation of public interface routines for B-tree manager.
26:
27: Version: HFS Plus 1.0
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: (msd) Mark Day
44: (DSH) Deric Horn
45: (djb) Don Brady
46:
47: Change History (most recent first):
48: <MOSXS> 9/22/99 ser Added routines BTGetLastSync and BTSetLastSync
49: <MOSXS> 6/1/99 djb Sync up with Mac OS 8.6.
50: <MOSXS> 6/30/98 djb In BTOpenPath make sure nodes are contiguous on disk (radar #2249539).
51: <MOSXS> 4/15/98 djb In BTOpenPath need to clear nodeRec.buffer if GetBlockProc fails.
52: <MOSXS> 4/11/98 djb Add RequireFileLock checking to all external entry points.
53:
54: <MOSXS> 03/23/98 djb In BTOpenPath use kTrashBlock option when releasing the header so
55: that we get a full node when we call GetNode.
56:
57: <CS9> 12/12/97 djb Radar #2202682, BTIterateRecord with kBTreeCurrentRecord was not
58: checking if we had a record and could call BlockMove with an
59: uninitialize source pointer (causing a bus error).
60: <CS8> 10/24/97 msd In BTIterateRecord, when moving to the previous or next record
61: and we have to move to another node, see if we need to release
62: the node about to be "shifted out" (opposite sibling of the
63: direction we need to move).
64: <CS7> 7/25/97 DSH BTSearchRecord now takes a heuristicHint, nodeNum, and tries it
65: before calling SearchBTree
66: <CS6> 7/24/97 djb GetBlockProc now take a file refnum instead of an FCB ptr.
67: <CS5> 7/22/97 djb Move trace points from BTreeWrapper.c to here.
68: <CS4> 7/21/97 djb LogEndTime now takes an error code.
69: <CS3> 7/16/97 DSH FilesInternal.i renamed FileMgrInternal.i to avoid name
70: collision
71: <CS2> 5/19/97 djb Add summary traces to BTIterateRecord.
72: <CS1> 4/23/97 djb first checked in
73:
74: <HFS7> 2/19/97 djb Enable variable sized index keys for HFS+ volumes. Added node
75: cache to support nodes larger than 512 bytes.
76: <HFS6> 1/27/97 djb Calls to InsertTree and DeleteTree are now recursive (to support
77: variable sized index keys).
78: <HFS5> 1/13/97 djb Added support for getting current record to BTIterateRecord.
79: <HFS4> 1/6/97 djb Initialize "BigKeys" attribute in BTOpen.
80: <HFS3> 1/3/97 djb Added support for large keys.
81: <HFS2> 12/23/96 djb On exit map fsBTEmptyErr and fsBTEndOfIterationErr to
82: fsBTRecordNotFoundErr.
83: <HFS1> 12/19/96 djb first checked in
84:
85: History applicable to original Scarecrow Design:
86:
87: <13> 10/25/96 ser Changing for new VFPI
88: <12> 10/18/96 ser Converting over VFPI changes
89: <11> 9/17/96 dkh More BTree statistics. Modified hint checks to not bail out when
90: an error is returned from GetNode.
91: <10> 9/16/96 dkh Revised BTree statistics.
92: <9> 8/23/96 dkh Remove checks for multiple paths to BTree file. Need to add
93: equivalent mechanism later.
94: <8> 6/20/96 dkh Radar #1358740. Switch from using Pools to debug MemAllocators.
95: <7> 3/14/96 jev Fix BTreeSetRecord, recordFound was not set for the case of a
96: simple replace causing the leafRecords count to get bumped even
97: though we didn't have to add a record.
98: <6> 3/1/96 prp Fix lint problems. Bug in BTSetRecord that does not initialize
99: recordFound.
100: <5> 1/22/96 dkh Add #include Memory.h
101: <4> 1/10/96 msd Use the real function names from Math64.i.
102: <3> 1/4/96 jev Fix BTItererateRecord for the condition when the iterator
103: position routine does not find the record and we are looking for
104: the next record. In such a case, if the node's forrward link is
105: non-zero, we have to keep iterating next and not return
106: fsBTEndOfIterationErr error.
107: <2> 12/7/95 dkh D10E2 build. Changed usage of Ref data type to LogicalAddress.
108: <1> 10/18/95 rst Moved from Scarecrow project.
109:
110: <24> 7/18/95 mbb Change MoveData & ClearBytes to BlockMoveData & BlockZero.
111: <23> 1/31/95 prp GetBlockProc interface uses a 64 bit node number.
112: <22> 1/12/95 wjk Adopt Model FileSystem changes in D5.
113: <21> 11/16/94 prp Add IsItAHint routine and use it whenever hint's node number was
114: used for testing.
115: <20> 11/10/94 prp BTGetInfo name collides with the same name in FileManagerPriv.i.
116: Change it to BTGetInformation.
117: <19> 9/30/94 prp Get in sync with D2 interface changes.
118: <18> 7/22/94 wjk Convert to the new set of header files.
119: <17> 12/9/93 wjk Cleanup usage of char, Byte, int8, UInt8, etc.
120: <16> 12/2/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
121: NRCmds environments.
122: <15> 11/30/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
123: NRCmds environments.
124: <14> 9/30/93 gs Rename E_NoGetNodeProc and E_NoReleaseNodeProc to
125: E_NoXxxxBlockProc.
126: <13> 8/31/93 prp Use Set64U instead of Set64.
127: <12> 8/16/93 prp In BTSearchRecord, if the input hint found the node and record,
128: set the local nodeNum variable correctly so that the resultant
129: iterator gets set correctly.
130: <11> 7/1/93 gs Fix bug in BTIterateRecord related to kBTreePrevRecord
131: operation.
132: <10> 6/2/93 gs Update for changes to FSErrors.h and add some comments.
133: <9> 5/24/93 gs Fix bug in BTInsert/Set/ReplaceRecord which didn't set node hint
134: properly in some cases.
135: <8> 5/24/93 gs Do NOT map fsBTEmptyErr to fsBTRecordNotFoundErr in BTSearchRecord.
136: <7> 5/24/93 gs Rename BTFlush to BTFlushPath.
137: <6> 5/21/93 gs Add hint optimization to Set/Replace routines.
138: <5> 5/10/93 gs Remove Panic from BTInitialize for small logicalEOF. Implement
139: Insert, Set, Replace, and Delete.
140: <4> 3/23/93 gs Finish BTInitialize.
141: <3> 2/8/93 gs Implement BTSearchRecord and BTIterateRecord.
142: <2> 12/8/92 gs Implement Open and Close routines.
143: <1> 11/15/92 gs first checked in
144:
145: */
146:
147: #include "../headers/BTreesPrivate.h"
148:
149: #include "../headers/HFSInstrumentation.h"
150:
151:
152: //////////////////////////////////// Globals ////////////////////////////////////
153:
154:
155: /////////////////////////// BTree Module Entry Points ///////////////////////////
156:
157:
158:
159: /*-------------------------------------------------------------------------------
160: Routine: BTOpenPath - Open a file for access as a B*Tree.
161:
162: Function: Create BTree control block for a file, if necessary. Validates the
163: file to be sure it looks like a BTree file.
164:
165:
166: Input: filePtr - pointer to file to open as a B-tree
167: keyCompareProc - pointer to client's KeyCompare function
168: getBlockProc - pointer to client's GetBlock function
169: releaseBlockProc - pointer to client's ReleaseBlock function
170: setEndOfForkProc - pointer to client's SetEOF function
171:
172: Result: noErr - success
173: paramErr - required ptr was nil
174: fsBTInvalidFileErr -
175: memFullErr -
176: != noErr - failure
177: -------------------------------------------------------------------------------*/
178:
179: OSStatus BTOpenPath (FCB *filePtr,
180: KeyCompareProcPtr keyCompareProc,
181: GetBlockProcPtr getBlockProc,
182: ReleaseBlockProcPtr releaseBlockProc,
183: SetEndOfForkProcPtr setEndOfForkProc,
184: SetBlockSizeProcPtr setBlockSizeProc )
185: {
186: OSStatus err;
187: BTreeControlBlockPtr btreePtr;
188: BTHeaderRec *header;
189: NodeRec nodeRec;
190:
191: LogStartTime(kTraceOpenBTree);
192:
193: ////////////////////// Preliminary Error Checking ///////////////////////////
194:
195: if ( filePtr == nil ||
196: getBlockProc == nil ||
197: releaseBlockProc == nil ||
198: setEndOfForkProc == nil ||
199: setBlockSizeProc == nil )
200: {
201: return paramErr;
202: }
203:
204: if ( filePtr->fcbBTCBPtr != nil ) // already has a BTreeCB
205: return noErr;
206:
207: // is file large enough to contain header node?
208: if ( filePtr->fcbEOF < kMinNodeSize )
209: return fsBTInvalidFileErr; //�� or E_BadHeader?
210:
211:
212: //////////////////////// Allocate Control Block /////////////////////////////
213:
214: btreePtr = (BTreeControlBlock*) NewPtrSysClear( sizeof( BTreeControlBlock ) );
215: if (btreePtr == nil)
216: {
217: Panic ("\pBTOpen: no memory for btreePtr.");
218: return memFullErr;
219: }
220:
221: btreePtr->getBlockProc = getBlockProc;
222: btreePtr->releaseBlockProc = releaseBlockProc;
223: btreePtr->setEndOfForkProc = setEndOfForkProc;
224: btreePtr->keyCompareProc = keyCompareProc;
225:
226: /////////////////////////// Read Header Node ////////////////////////////////
227:
228: nodeRec.buffer = nil; // so we can call ReleaseNode
229: nodeRec.blockSize = kMinNodeSize;
230: btreePtr->fileRefNum = GetFileRefNumFromFCB(filePtr);
231: filePtr->fcbBTCBPtr = (Ptr) btreePtr; // attach btree cb to file
232:
233: RequireFileLock(btreePtr->fileRefNum, false);
234:
235: // it is now safe to call M_ExitOnError (err)
236:
237: err = setBlockSizeProc (btreePtr->fileRefNum, kMinNodeSize, 1);
238: M_ExitOnError (err);
239:
240:
241: err = getBlockProc (btreePtr->fileRefNum,
242: kHeaderNodeNum,
243: kGetBlock,
244: &nodeRec );
245: if (err != noErr)
246: {
247: nodeRec.buffer = nil;
248: nodeRec.blockHeader = nil;
249: Panic("\pBTOpen: getNodeProc returned error getting header node.");
250: goto ErrorExit;
251: }
252:
253: header = (BTHeaderRec*) ((u_long)nodeRec.buffer + sizeof(BTNodeDescriptor));
254:
255:
256: ///////////////////////////// verify header /////////////////////////////////
257:
258: err = VerifyHeader (filePtr, header);
259: M_ExitOnError (err);
260:
261:
262: ///////////////////// Initalize fields from header //////////////////////////
263:
264: PanicIf ( (FCBTOVCB(filePtr)->vcbSigWord != 0x4244) && (header->nodeSize == 512), "\p BTOpenPath: wrong node size for HFS+ volume!"); // 0x4244 = 'BD'
265:
266: btreePtr->treeDepth = header->treeDepth;
267: btreePtr->rootNode = header->rootNode;
268: btreePtr->leafRecords = header->leafRecords;
269: btreePtr->firstLeafNode = header->firstLeafNode;
270: btreePtr->lastLeafNode = header->lastLeafNode;
271: btreePtr->nodeSize = header->nodeSize;
272: btreePtr->maxKeyLength = header->maxKeyLength;
273: btreePtr->totalNodes = header->totalNodes;
274: btreePtr->freeNodes = header->freeNodes;
275: // ignore header->clumpSize; //�� rename this field?
276: btreePtr->btreeType = header->btreeType;
277:
278: btreePtr->attributes = header->attributes;
279:
280: if ( btreePtr->maxKeyLength > 40 )
281: btreePtr->attributes |= (kBTBigKeysMask + kBTVariableIndexKeysMask); //�� we need a way to save these attributes
282:
283: /////////////////////// Initialize dynamic fields ///////////////////////////
284:
285: btreePtr->version = kBTreeVersion;
286: btreePtr->flags = 0;
287: btreePtr->writeCount = 1;
288:
289: btreePtr->numGetNodes = 1; // for earlier call to getNodeProc
290:
291: /////////////////////////// Check Header Node ///////////////////////////////
292:
293: //�� set kBadClose attribute bit, and UpdateNode
294:
295: // if nodeSize is 512 then we don't need to release, just CheckNode
296:
297: if ( btreePtr->nodeSize == kMinNodeSize )
298: {
299: err = CheckNode (btreePtr, nodeRec.buffer);
300: if (err)
301: VTOVCB(btreePtr->fileRefNum)->vcbFlags |= kHFS_DamagedVolume;
302: M_ExitOnError (err);
303: }
304: else
305: {
306: err = setBlockSizeProc (btreePtr->fileRefNum, btreePtr->nodeSize, 32); //���we should try and get this down to 8
307: M_ExitOnError (err);
308:
309: /*
310: * Need to use kTrashBlock option to force the
311: * buffer cache to read the entire node
312: */
313: err = releaseBlockProc(btreePtr->fileRefNum, &nodeRec, kTrashBlock);
314: M_ExitOnError (err);
315:
316: err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec ); // calls CheckNode...
317: M_ExitOnError (err);
318: }
319:
320: //�� total nodes * node size <= LEOF?
321:
322:
323: err = ReleaseNode (btreePtr, &nodeRec);
324: M_ExitOnError (err);
325:
326: /*
327: * Under Mac OS, b-tree nodes can be non-contiguous on disk when the
328: * allocation block size is smaller than the b-tree node size.
329: */
330: if ( !NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize) )
331: return fsBTInvalidNodeErr;
332:
333: //////////////////////////////// Success ////////////////////////////////////
334:
335: //�� align LEOF to multiple of node size? - just on close
336:
337: LogEndTime(kTraceOpenBTree, noErr);
338:
339: return noErr;
340:
341:
342: /////////////////////// Error - Clean up and Exit ///////////////////////////
343:
344: ErrorExit:
345:
346: filePtr->fcbBTCBPtr = nil;
347: (void) ReleaseNode (btreePtr, &nodeRec);
348: DisposePtr( (Ptr) btreePtr );
349:
350: LogEndTime(kTraceOpenBTree, err);
351:
352: return err;
353: }
354:
355:
356:
357: /*-------------------------------------------------------------------------------
358: Routine: BTClosePath - Flush BTree Header and Deallocate Memory for BTree.
359:
360: Function: Flush the BTreeControlBlock fields to header node, and delete BTree control
361: block and key descriptor associated with the file if filePtr is last
362: path of type kBTreeType ('btre').
363:
364:
365: Input: filePtr - pointer to file to delete BTree control block for.
366:
367: Result: noErr - success
368: fsBTInvalidFileErr -
369: != noErr - failure
370: -------------------------------------------------------------------------------*/
371:
372: OSStatus BTClosePath (FCB *filePtr)
373: {
374: OSStatus err;
375: BTreeControlBlockPtr btreePtr;
376:
377: LogStartTime(kTraceCloseBTree);
378:
379: btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
380:
381: if (btreePtr == nil)
382: return fsBTInvalidFileErr;
383:
384: RequireFileLock(btreePtr->fileRefNum, false);
385:
386: ////////////////////// Check for other BTree Paths //////////////////////////
387:
388: btreePtr->attributes &= ~kBTBadCloseMask; // clear "bad close" attribute bit
389: err = UpdateHeader (btreePtr);
390: M_ExitOnError (err);
391:
392: DisposePtr( (Ptr) btreePtr );
393: filePtr->fcbBTCBPtr = nil;
394:
395: LogEndTime(kTraceCloseBTree, noErr);
396:
397: return noErr;
398:
399: /////////////////////// Error - Clean Up and Exit ///////////////////////////
400:
401: ErrorExit:
402:
403: LogEndTime(kTraceCloseBTree, err);
404:
405: return err;
406: }
407:
408:
409:
410: /*-------------------------------------------------------------------------------
411: Routine: BTSearchRecord - Search BTree for a record with a matching key.
412:
413: Function: Search for position in B*Tree indicated by searchKey. If a valid node hint
414: is provided, it will be searched first, then SearchTree will be called.
415: If a BTreeIterator is provided, it will be set to the position found as
416: a result of the search. If a record exists at that position, and a BufferDescriptor
417: is supplied, the record will be copied to the buffer (as much as will fit),
418: and recordLen will be set to the length of the record.
419:
420: If an error other than fsBTRecordNotFoundErr occurs, the BTreeIterator, if any,
421: is invalidated, and recordLen is set to 0.
422:
423:
424: Input: pathPtr - pointer to path for BTree file.
425: searchKey - pointer to search key to match.
426: hintPtr - pointer to hint (may be nil)
427:
428: Output: record - pointer to BufferDescriptor containing record
429: recordLen - length of data at recordPtr
430: iterator - pointer to BTreeIterator indicating position result of search
431:
432: Result: noErr - success, record contains copy of record found
433: fsBTRecordNotFoundErr - record was not found, no data copied
434: fsBTInvalidFileErr - no BTreeControlBlock is allocated for the fork
435: fsBTInvalidKeyLengthErr -
436: != noErr - failure
437: -------------------------------------------------------------------------------*/
438:
439: OSStatus BTSearchRecord (FCB *filePtr,
440: BTreeIterator *searchIterator,
441: UInt32 heuristicHint,
442: FSBufferDescriptor *record,
443: UInt16 *recordLen,
444: BTreeIterator *resultIterator )
445: {
446: OSStatus err;
447: BTreeControlBlockPtr btreePtr;
448: TreePathTable treePathTable;
449: UInt32 nodeNum;
450: BlockDescriptor node;
451: UInt16 index;
452: BTreeKeyPtr keyPtr;
453: RecordPtr recordPtr;
454: UInt16 len;
455: Boolean foundRecord;
456: Boolean validHint;
457:
458:
459: LogStartTime(kTraceSearchBTree);
460:
461: if (filePtr == nil) return paramErr;
462: if (searchIterator == nil) return paramErr;
463:
464: btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
465: if (btreePtr == nil) return fsBTInvalidFileErr;
466:
467: RequireFileLock(btreePtr->fileRefNum, true);
468:
469: foundRecord = false;
470:
471: ////////////////////////////// Take A Hint //////////////////////////////////
472:
473: err = IsItAHint (btreePtr, searchIterator, &validHint);
474: M_ExitOnError (err);
475:
476: if (validHint)
477: {
478: nodeNum = searchIterator->hint.nodeNum;
479:
480: err = GetNode (btreePtr, nodeNum, &node);
481: if( err == noErr )
482: {
483: if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode &&
484: ((BTNodeDescriptor*) node.buffer)->numRecords > 0 )
485: {
486: foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index);
487:
488: //�� if !foundRecord, we could still skip tree search if ( 0 < index < numRecords )
489: }
490:
491: if (foundRecord == false)
492: {
493: err = ReleaseNode (btreePtr, &node);
494: M_ExitOnError (err);
495: }
496: else
497: {
498: ++btreePtr->numValidHints;
499: }
500: }
501:
502: if( foundRecord == false )
503: (void) BTInvalidateHint( searchIterator );
504: }
505:
506: ////////////////////////////// Try the heuristicHint //////////////////////////////////
507:
508: if ( (foundRecord == false) && (heuristicHint != kInvalidMRUCacheKey) && (nodeNum != heuristicHint) )
509: {
510: LogStartTime(kHeuristicHint);
511: nodeNum = heuristicHint;
512:
513: err = GetNode (btreePtr, nodeNum, &node);
514: if( err == noErr )
515: {
516: if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode &&
517: ((BTNodeDescriptor*) node.buffer)->numRecords > 0 )
518: {
519: foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index);
520: }
521:
522: if (foundRecord == false)
523: {
524: err = ReleaseNode (btreePtr, &node);
525: M_ExitOnError (err);
526: }
527: }
528: LogEndTime(kHeuristicHint, (foundRecord == false));
529: }
530:
531: //////////////////////////// Search The Tree ////////////////////////////////
532:
533: if (foundRecord == false)
534: {
535: err = SearchTree ( btreePtr, &searchIterator->key, treePathTable, &nodeNum, &node, &index);
536: switch (err)
537: {
538: case noErr: foundRecord = true; break;
539: case fsBTRecordNotFoundErr: break;
540: default: goto ErrorExit;
541: }
542: }
543:
544:
545: //////////////////////////// Get the Record /////////////////////////////////
546:
547: if (foundRecord == true)
548: {
549: //XXX Should check for errors! Or BlockMove could choke on recordPtr!!!
550: GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
551:
552: if (recordLen != nil) *recordLen = len;
553:
554: if (record != nil)
555: {
556: ByteCount recordSize;
557:
558: recordSize = record->itemCount * record->itemSize;
559:
560: if (len > recordSize) len = recordSize;
561:
562: BlockMoveData (recordPtr, record->bufferAddress, len);
563: }
564: }
565:
566:
567: /////////////////////// Success - Update Iterator ///////////////////////////
568:
569: if (resultIterator != nil)
570: {
571: resultIterator->hint.writeCount = btreePtr->writeCount;
572: resultIterator->hint.nodeNum = nodeNum;
573: resultIterator->hint.index = index;
574: #if DEBUG_BUILD
575: resultIterator->hint.reserved1 = 0;
576: resultIterator->hint.reserved2 = 0;
577: resultIterator->version = 0;
578: resultIterator->reserved = 0;
579: #endif
580: // copy the key in the BTree when found rather than searchIterator->key to get proper case/diacriticals
581: if (foundRecord == true)
582: BlockMoveData ((Ptr)keyPtr, (Ptr)&resultIterator->key, CalcKeySize(btreePtr, keyPtr));
583: else
584: BlockMoveData ((Ptr)&searchIterator->key, (Ptr)&resultIterator->key, CalcKeySize(btreePtr, &searchIterator->key));
585: }
586:
587: err = ReleaseNode (btreePtr, &node);
588: M_ExitOnError (err);
589:
590: LogEndTime(kTraceSearchBTree, (foundRecord == false));
591:
592: if (foundRecord == false) return fsBTRecordNotFoundErr;
593: else return noErr;
594:
595:
596: /////////////////////// Error - Clean Up and Exit ///////////////////////////
597:
598: ErrorExit:
599:
600: if (recordLen != nil)
601: *recordLen = 0;
602:
603: if (resultIterator != nil)
604: {
605: resultIterator->hint.writeCount = 0;
606: resultIterator->hint.nodeNum = 0;
607: resultIterator->hint.index = 0;
608: resultIterator->hint.reserved1 = 0;
609: resultIterator->hint.reserved2 = 0;
610:
611: resultIterator->version = 0;
612: resultIterator->reserved = 0;
613: resultIterator->key.length16 = 0; // zero out two bytes to cover both types of keys
614: }
615:
616: if ( err == fsBTEmptyErr )
617: err = fsBTRecordNotFoundErr;
618:
619: LogEndTime(kTraceSearchBTree, err);
620:
621: return err;
622: }
623:
624:
625:
626: /*-------------------------------------------------------------------------------
627: Routine: BTIterateRecord - Find the first, next, previous, or last record.
628:
629: Function: Find the first, next, previous, or last record in the BTree
630:
631: Input: pathPtr - pointer to path iterate records for.
632: operation - iteration operation (first,next,prev,last)
633: iterator - pointer to iterator indicating start position
634:
635: Output: iterator - iterator is updated to indicate new position
636: newKeyPtr - pointer to buffer to copy key found by iteration
637: record - pointer to buffer to copy record found by iteration
638: recordLen - length of record
639:
640: Result: noErr - success
641: != noErr - failure
642: -------------------------------------------------------------------------------*/
643:
644: OSStatus BTIterateRecord (FCB *filePtr,
645: BTreeIterationOperation operation,
646: BTreeIterator *iterator,
647: FSBufferDescriptor *record,
648: UInt16 *recordLen )
649: {
650: OSStatus err;
651: BTreeControlBlockPtr btreePtr;
652: BTreeKeyPtr keyPtr;
653: RecordPtr recordPtr;
654: UInt16 len;
655:
656: Boolean foundRecord;
657: UInt32 nodeNum;
658:
659: BlockDescriptor left, node, right;
660: UInt16 index;
661:
662:
663: LogStartTime(kTraceGetBTreeRecord);
664:
665: ////////////////////////// Priliminary Checks ///////////////////////////////
666:
667: left.buffer = nil;
668: right.buffer = nil;
669: node.buffer = nil;
670:
671:
672: if (filePtr == nil)
673: {
674: return paramErr;
675: }
676:
677: btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
678: if (btreePtr == nil)
679: {
680: return fsBTInvalidFileErr; //�� handle properly
681: }
682:
683: RequireFileLock(btreePtr->fileRefNum, true);
684:
685: if ((operation != kBTreeFirstRecord) &&
686: (operation != kBTreeNextRecord) &&
687: (operation != kBTreeCurrentRecord) &&
688: (operation != kBTreePrevRecord) &&
689: (operation != kBTreeLastRecord))
690: {
691: err = fsInvalidIterationMovmentErr;
692: goto ErrorExit;
693: }
694:
695: /////////////////////// Find First or Last Record ///////////////////////////
696:
697: if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord))
698: {
699: if (operation == kBTreeFirstRecord) nodeNum = btreePtr->firstLeafNode;
700: else nodeNum = btreePtr->lastLeafNode;
701:
702: if (nodeNum == 0)
703: {
704: err = fsBTEmptyErr;
705: goto ErrorExit;
706: }
707:
708: err = GetNode (btreePtr, nodeNum, &node);
709: M_ExitOnError (err);
710:
711: if ( ((NodeDescPtr) node.buffer)->kind != kBTLeafNode ||
712: ((NodeDescPtr) node.buffer)->numRecords <= 0 )
713: {
714: err = ReleaseNode (btreePtr, &node);
715: M_ExitOnError (err);
716:
717: err = fsBTInvalidNodeErr;
718: goto ErrorExit;
719: }
720:
721: if (operation == kBTreeFirstRecord) index = 0;
722: else index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1;
723:
724: goto CopyData; //�� is there a cleaner way?
725: }
726:
727:
728: //////////////////////// Find Iterator Position /////////////////////////////
729:
730: err = FindIteratorPosition (btreePtr, iterator,
731: &left, &node, &right, &nodeNum, &index, &foundRecord);
732: M_ExitOnError (err);
733:
734:
735: ///////////////////// Find Next Or Previous Record //////////////////////////
736:
737: if (operation == kBTreePrevRecord)
738: {
739: if (index > 0)
740: {
741: --index;
742: }
743: else
744: {
745: if (left.buffer == nil)
746: {
747: nodeNum = ((NodeDescPtr) node.buffer)->bLink;
748: if ( nodeNum > 0)
749: {
750: err = GetNode (btreePtr, nodeNum, &left);
751: M_ExitOnError (err);
752: } else {
753: err = fsBTStartOfIterationErr;
754: goto ErrorExit;
755: }
756: }
757: // Before we stomp on "right", we'd better release it if needed
758: if (right.buffer != nil) {
759: err = ReleaseNode(btreePtr, &right);
760: M_ExitOnError(err);
761: }
762: right = node;
763: node = left;
764: left.buffer = nil;
765: index = ((NodeDescPtr) node.buffer)->numRecords -1;
766: }
767: }
768: else if (operation == kBTreeNextRecord)
769: {
770: if ((foundRecord != true) &&
771: (((NodeDescPtr) node.buffer)->fLink == 0) &&
772: (index == ((NodeDescPtr) node.buffer)->numRecords))
773: {
774: err = fsBTEndOfIterationErr;
775: goto ErrorExit;
776: }
777:
778: // we did not find the record but the index is already positioned correctly
779: if ((foundRecord == false) && (index != ((NodeDescPtr) node.buffer)->numRecords))
780: goto CopyData;
781:
782: // we found the record OR we have to look in the next node
783: if (index < ((NodeDescPtr) node.buffer)->numRecords -1)
784: {
785: ++index;
786: }
787: else
788: {
789: if (right.buffer == nil)
790: {
791: nodeNum = ((NodeDescPtr) node.buffer)->fLink;
792: if ( nodeNum > 0)
793: {
794: err = GetNode (btreePtr, nodeNum, &right);
795: M_ExitOnError (err);
796: } else {
797: err = fsBTEndOfIterationErr;
798: goto ErrorExit;
799: }
800: }
801: // Before we stomp on "left", we'd better release it if needed
802: if (left.buffer != nil) {
803: err = ReleaseNode(btreePtr, &left);
804: M_ExitOnError(err);
805: }
806: left = node;
807: node = right;
808: right.buffer = nil;
809: index = 0;
810: }
811: }
812: else // operation == kBTreeCurrentRecord
813: {
814: // make sure we have something... <CS9>
815: if ((foundRecord != true) &&
816: (index >= ((NodeDescPtr) node.buffer)->numRecords))
817: {
818: err = fsBTEndOfIterationErr;
819: goto ErrorExit;
820: }
821: }
822:
823: //////////////////// Copy Record And Update Iterator ////////////////////////
824:
825: CopyData:
826:
827: // added check for errors <CS9>
828: err = GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
829: M_ExitOnError (err);
830:
831: if (recordLen != nil)
832: *recordLen = len;
833:
834: if (record != nil)
835: {
836: ByteCount recordSize;
837:
838: recordSize = record->itemCount * record->itemSize;
839:
840: if (len > recordSize) len = recordSize;
841:
842: BlockMoveData (recordPtr, record->bufferAddress, len);
843: }
844:
845: if (iterator != nil) // first & last do not require iterator
846: {
847: iterator->hint.writeCount = btreePtr->writeCount;
848: iterator->hint.nodeNum = nodeNum;
849: iterator->hint.index = index;
850: iterator->hint.reserved1 = 0;
851: iterator->hint.reserved2 = 0;
852:
853: iterator->version = 0;
854: iterator->reserved = 0;
855:
856: BlockMoveData ((Ptr)keyPtr, (Ptr)&iterator->key, CalcKeySize(btreePtr, keyPtr));
857: }
858:
859:
860: ///////////////////////////// Release Nodes /////////////////////////////////
861:
862: err = ReleaseNode (btreePtr, &node);
863: M_ExitOnError (err);
864:
865: if (left.buffer != nil)
866: {
867: err = ReleaseNode (btreePtr, &left);
868: M_ExitOnError (err);
869: }
870:
871: if (right.buffer != nil)
872: {
873: err = ReleaseNode (btreePtr, &right);
874: M_ExitOnError (err);
875: }
876:
877: LogEndTime(kTraceGetBTreeRecord, noErr);
878:
879: return noErr;
880:
881: /////////////////////// Error - Clean Up and Exit ///////////////////////////
882:
883: ErrorExit:
884:
885: (void) ReleaseNode (btreePtr, &left);
886: (void) ReleaseNode (btreePtr, &node);
887: (void) ReleaseNode (btreePtr, &right);
888:
889: if (recordLen != nil)
890: *recordLen = 0;
891:
892: if (iterator != nil)
893: {
894: iterator->hint.writeCount = 0;
895: iterator->hint.nodeNum = 0;
896: iterator->hint.index = 0;
897: iterator->hint.reserved1 = 0;
898: iterator->hint.reserved2 = 0;
899:
900: iterator->version = 0;
901: iterator->reserved = 0;
902: iterator->key.length16 = 0;
903: }
904:
905: if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
906: err = fsBTRecordNotFoundErr;
907:
908: LogEndTime(kTraceGetBTreeRecord, err);
909:
910: return err;
911: }
912:
913:
914: /*-------------------------------------------------------------------------------
915: Routine: BTIterateRecords
916:
917: Function: Find a series of records
918:
919: Input: filePtr - b-tree file
920: operation - iteration operation (first,next,prev,last)
921: iterator - pointer to iterator indicating start position
922: callBackProc - pointer to routince to process a record
923: callBackState - pointer to state data (used by callBackProc)
924:
925: Output: iterator - iterator is updated to indicate new position
926:
927: Result: noErr - success
928: != noErr - failure
929: -------------------------------------------------------------------------------*/
930:
931: OSStatus
932: BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator *iterator,
933: IterateCallBackProcPtr callBackProc, void * callBackState)
934: {
935: OSStatus err;
936: BTreeControlBlockPtr btreePtr;
937: BTreeKeyPtr keyPtr;
938: RecordPtr recordPtr;
939: UInt16 len;
940: Boolean foundRecord;
941: UInt32 nodeNum;
942: BlockDescriptor left, node, right;
943: UInt16 index;
944:
945:
946: ////////////////////////// Priliminary Checks ///////////////////////////////
947:
948: left.buffer = nil;
949: right.buffer = nil;
950: node.buffer = nil;
951:
952: btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
953:
954: RequireFileLock(btreePtr->fileRefNum, true);
955:
956: if ((operation != kBTreeFirstRecord) &&
957: (operation != kBTreeNextRecord) &&
958: (operation != kBTreeCurrentRecord) &&
959: (operation != kBTreePrevRecord) &&
960: (operation != kBTreeLastRecord))
961: {
962: err = fsInvalidIterationMovmentErr;
963: goto ErrorExit;
964: }
965:
966: /////////////////////// Find First or Last Record ///////////////////////////
967:
968: if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord))
969: {
970: if (operation == kBTreeFirstRecord)
971: nodeNum = btreePtr->firstLeafNode;
972: else
973: nodeNum = btreePtr->lastLeafNode;
974:
975: if (nodeNum == 0)
976: {
977: err = fsBTEmptyErr;
978: goto ErrorExit;
979: }
980:
981: err = GetNode(btreePtr, nodeNum, &node);
982: M_ExitOnError(err);
983:
984: if ( ((NodeDescPtr)node.buffer)->kind != kBTLeafNode ||
985: ((NodeDescPtr)node.buffer)->numRecords <= 0 )
986: {
987: err = ReleaseNode(btreePtr, &node);
988: M_ExitOnError(err);
989:
990: err = fsBTInvalidNodeErr;
991: goto ErrorExit;
992: }
993:
994: if (operation == kBTreeFirstRecord)
995: index = 0;
996: else
997: index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1;
998:
999: goto ProcessData;
1000: }
1001:
1002: //////////////////////// Find Iterator Position /////////////////////////////
1003:
1004: err = FindIteratorPosition(btreePtr, iterator, &left, &node, &right,
1005: &nodeNum, &index, &foundRecord);
1006: M_ExitOnError(err);
1007:
1008:
1009: ///////////////////// Find Next Or Previous Record //////////////////////////
1010:
1011: if (operation == kBTreePrevRecord)
1012: {
1013: if (index > 0)
1014: {
1015: --index;
1016: }
1017: else
1018: {
1019: if (left.buffer == nil)
1020: {
1021: nodeNum = ((NodeDescPtr) node.buffer)->bLink;
1022: if ( nodeNum > 0)
1023: {
1024: err = GetNode(btreePtr, nodeNum, &left);
1025: M_ExitOnError(err);
1026: } else {
1027: err = fsBTStartOfIterationErr;
1028: goto ErrorExit;
1029: }
1030: }
1031: // Before we stomp on "right", we'd better release it if needed
1032: if (right.buffer != nil) {
1033: err = ReleaseNode(btreePtr, &right);
1034: M_ExitOnError(err);
1035: }
1036: right = node;
1037: node = left;
1038: left.buffer = nil;
1039: index = ((NodeDescPtr) node.buffer)->numRecords -1;
1040: }
1041: }
1042: else if (operation == kBTreeNextRecord)
1043: {
1044: if ((foundRecord != true) &&
1045: (((NodeDescPtr)node.buffer)->fLink == 0) &&
1046: (index == ((NodeDescPtr)node.buffer)->numRecords))
1047: {
1048: err = fsBTEndOfIterationErr;
1049: goto ErrorExit;
1050: }
1051:
1052: // we did not find the record but the index is already positioned correctly
1053: if ((foundRecord == false) && (index != ((NodeDescPtr)node.buffer)->numRecords))
1054: goto ProcessData;
1055:
1056: // we found the record OR we have to look in the next node
1057: if (index < ((NodeDescPtr)node.buffer)->numRecords -1)
1058: {
1059: ++index;
1060: }
1061: else
1062: {
1063: if (right.buffer == nil)
1064: {
1065: nodeNum = ((NodeDescPtr)node.buffer)->fLink;
1066: if ( nodeNum > 0)
1067: {
1068: err = GetNode(btreePtr, nodeNum, &right);
1069: M_ExitOnError(err);
1070: } else {
1071: err = fsBTEndOfIterationErr;
1072: goto ErrorExit;
1073: }
1074: }
1075: // Before we stomp on "left", we'd better release it if needed
1076: if (left.buffer != nil) {
1077: err = ReleaseNode(btreePtr, &left);
1078: M_ExitOnError(err);
1079: }
1080: left = node;
1081: node = right;
1082: right.buffer = nil;
1083: index = 0;
1084: }
1085: }
1086: else // operation == kBTreeCurrentRecord
1087: {
1088: // make sure we have something... <CS9>
1089: if ((foundRecord != true) &&
1090: (index >= ((NodeDescPtr)node.buffer)->numRecords))
1091: {
1092: err = fsBTEndOfIterationErr;
1093: goto ErrorExit;
1094: }
1095: }
1096:
1097: //////////////////// Process Records Using Callback ////////////////////////
1098:
1099: ProcessData:
1100: err = GetRecordByIndex(btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
1101:
1102: while (err == 0) {
1103: if (callBackProc(keyPtr, recordPtr, len, callBackState) == 0)
1104: break;
1105:
1106: if ((index+1) < ((NodeDescPtr)node.buffer)->numRecords) {
1107: ++index;
1108: } else {
1109: if (right.buffer == nil)
1110: {
1111: nodeNum = ((NodeDescPtr)node.buffer)->fLink;
1112: if ( nodeNum > 0)
1113: {
1114: err = GetNode(btreePtr, nodeNum, &right);
1115: M_ExitOnError(err);
1116: } else {
1117: err = fsBTEndOfIterationErr;
1118: break;
1119: }
1120: }
1121: // Before we stomp on "left", we'd better release it if needed
1122: if (left.buffer != nil) {
1123: err = ReleaseNode(btreePtr, &left);
1124: M_ExitOnError(err);
1125: }
1126: left = node;
1127: node = right;
1128: right.buffer = nil;
1129: index = 0;
1130: }
1131: err = GetRecordByIndex(btreePtr, node.buffer, index,
1132: &keyPtr, &recordPtr, &len);
1133: }
1134:
1135:
1136: ///////////////// Update Iterator to Last Item Processed /////////////////////
1137:
1138:
1139: if (iterator != nil) // first & last have optional iterator
1140: {
1141: iterator->hint.writeCount = btreePtr->writeCount;
1142: iterator->hint.nodeNum = nodeNum;
1143: iterator->hint.index = index;
1144: iterator->version = 0;
1145:
1146: BlockMoveData((Ptr)keyPtr, (Ptr)&iterator->key, CalcKeySize(btreePtr, keyPtr));
1147: }
1148: M_ExitOnError(err);
1149:
1150:
1151: ///////////////////////////// Release Nodes /////////////////////////////////
1152:
1153: err = ReleaseNode(btreePtr, &node);
1154: M_ExitOnError(err);
1155:
1156: if (left.buffer != nil)
1157: {
1158: err = ReleaseNode(btreePtr, &left);
1159: M_ExitOnError(err);
1160: }
1161:
1162: if (right.buffer != nil)
1163: {
1164: err = ReleaseNode(btreePtr, &right);
1165: M_ExitOnError(err);
1166: }
1167:
1168: return noErr;
1169:
1170: /////////////////////// Error - Clean Up and Exit ///////////////////////////
1171:
1172: ErrorExit:
1173:
1174: (void) ReleaseNode(btreePtr, &left);
1175: (void) ReleaseNode(btreePtr, &node);
1176: (void) ReleaseNode(btreePtr, &right);
1177:
1178: if (iterator != nil)
1179: {
1180: iterator->hint.writeCount = 0;
1181: iterator->hint.nodeNum = 0;
1182: iterator->hint.index = 0;
1183: iterator->version = 0;
1184: iterator->key.length16 = 0;
1185: }
1186:
1187: if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
1188: err = fsBTRecordNotFoundErr;
1189:
1190: return err;
1191: }
1192:
1193:
1194: //////////////////////////////// BTInsertRecord /////////////////////////////////
1195:
1196: OSStatus BTInsertRecord (FCB *filePtr,
1197: BTreeIterator *iterator,
1198: FSBufferDescriptor *record,
1199: UInt16 recordLen )
1200: {
1201: OSStatus err;
1202: BTreeControlBlockPtr btreePtr;
1203: TreePathTable treePathTable;
1204: SInt32 nodesNeeded;
1205: BlockDescriptor nodeRec;
1206: UInt32 insertNodeNum;
1207: UInt16 index;
1208: Boolean recordFit;
1209:
1210:
1211: ////////////////////////// Priliminary Checks ///////////////////////////////
1212:
1213: nodeRec.buffer = nil; // so we can call ReleaseNode
1214:
1215: err = CheckInsertParams (filePtr, iterator, record, recordLen);
1216: if (err != noErr)
1217: return err;
1218:
1219: LogStartTime(kTraceInsertBTreeRecord);
1220:
1221: btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1222:
1223: RequireFileLock(btreePtr->fileRefNum, false);
1224:
1225:
1226: ///////////////////////// Find Insert Position //////////////////////////////
1227:
1228: // always call SearchTree for Insert
1229: err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1230:
1231: switch (err) // set/replace/insert decision point
1232: {
1233: case noErr: err = fsBTDuplicateRecordErr;
1234: goto ErrorExit;
1235:
1236: case fsBTRecordNotFoundErr: break;
1237:
1238: case fsBTEmptyErr: // if tree empty add 1st leaf node
1239:
1240: if (btreePtr->freeNodes == 0)
1241: {
1242: err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
1243: M_ExitOnError (err);
1244: }
1245:
1246: err = AllocateNode (btreePtr, &insertNodeNum);
1247: M_ExitOnError (err);
1248:
1249: err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
1250: M_ExitOnError (err);
1251:
1252: ((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
1253: ((NodeDescPtr)nodeRec.buffer)->height = 1;
1254:
1255: recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0,
1256: &iterator->key, KeyLength(btreePtr, &iterator->key),
1257: record->bufferAddress, recordLen );
1258: if (recordFit != true)
1259: {
1260: err = fsBTRecordTooLargeErr;
1261: goto ErrorExit;
1262: }
1263:
1264: err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
1265: M_ExitOnError (err);
1266:
1267: // update BTreeControlBlock
1268: btreePtr->treeDepth = 1;
1269: btreePtr->rootNode = insertNodeNum;
1270: btreePtr->firstLeafNode = insertNodeNum;
1271: btreePtr->lastLeafNode = insertNodeNum;
1272: M_BTreeHeaderDirty (btreePtr);
1273:
1274: goto Success;
1275:
1276: default: goto ErrorExit;
1277: }
1278:
1279: if (index > 0)
1280: {
1281: recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
1282: &iterator->key, KeyLength(btreePtr, &iterator->key),
1283: record->bufferAddress, recordLen);
1284: if (recordFit == true)
1285: {
1286: err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
1287: M_ExitOnError (err);
1288:
1289: goto Success;
1290: }
1291: }
1292:
1293: /////////////////////// Extend File If Necessary ////////////////////////////
1294:
1295: nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //�� math limit
1296: if (nodesNeeded > 0)
1297: {
1298: nodesNeeded += btreePtr->totalNodes;
1299: if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
1300: ++nodesNeeded;
1301:
1302: err = ExtendBTree (btreePtr, nodesNeeded);
1303: M_ExitOnError (err);
1304: }
1305:
1306: // no need to delete existing record
1307:
1308: err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1309: recordLen, &nodeRec, index, 1, kInsertRecord, &insertNodeNum);
1310: M_ExitOnError (err);
1311:
1312:
1313: //////////////////////////////// Success ////////////////////////////////////
1314:
1315: Success:
1316: ++btreePtr->writeCount;
1317: ++btreePtr->leafRecords;
1318: M_BTreeHeaderDirty (btreePtr);
1319:
1320: // create hint
1321: iterator->hint.writeCount = btreePtr->writeCount;
1322: iterator->hint.nodeNum = insertNodeNum;
1323: iterator->hint.index = 0; // unused
1324: iterator->hint.reserved1 = 0;
1325: iterator->hint.reserved2 = 0;
1326:
1327: LogEndTime(kTraceInsertBTreeRecord, noErr);
1328:
1329: return noErr;
1330:
1331:
1332: ////////////////////////////// Error Exit ///////////////////////////////////
1333:
1334: ErrorExit:
1335:
1336: (void) ReleaseNode (btreePtr, &nodeRec);
1337:
1338: iterator->hint.writeCount = 0;
1339: iterator->hint.nodeNum = 0;
1340: iterator->hint.index = 0;
1341: iterator->hint.reserved1 = 0;
1342: iterator->hint.reserved2 = 0;
1343:
1344: if (err == fsBTEmptyErr)
1345: err = fsBTRecordNotFoundErr;
1346:
1347: LogEndTime(kTraceInsertBTreeRecord, err);
1348:
1349: return err;
1350: }
1351:
1352:
1353: //////////////////////////////// BTReplaceRecord ////////////////////////////////
1354:
1355: OSStatus BTReplaceRecord (FCB *filePtr,
1356: BTreeIterator *iterator,
1357: FSBufferDescriptor *record,
1358: UInt16 recordLen )
1359: {
1360: OSStatus err;
1361: BTreeControlBlockPtr btreePtr;
1362: TreePathTable treePathTable;
1363: SInt32 nodesNeeded;
1364: BlockDescriptor nodeRec;
1365: UInt32 insertNodeNum;
1366: UInt16 index;
1367: Boolean recordFit;
1368: Boolean validHint;
1369:
1370:
1371: ////////////////////////// Priliminary Checks ///////////////////////////////
1372:
1373: nodeRec.buffer = nil; // so we can call ReleaseNode
1374:
1375: err = CheckInsertParams (filePtr, iterator, record, recordLen);
1376: if (err != noErr)
1377: return err;
1378:
1379: LogStartTime(kTraceReplaceBTreeRecord);
1380:
1381: btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1382:
1383: RequireFileLock(btreePtr->fileRefNum, false);
1384:
1385: ////////////////////////////// Take A Hint //////////////////////////////////
1386:
1387: err = IsItAHint (btreePtr, iterator, &validHint);
1388: M_ExitOnError (err);
1389:
1390: if (validHint)
1391: {
1392: insertNodeNum = iterator->hint.nodeNum;
1393:
1394: err = GetNode (btreePtr, insertNodeNum, &nodeRec);
1395: if( err == noErr )
1396: {
1397: err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1398: M_ExitOnError (err);
1399:
1400: if (recordFit)
1401: {
1402: err = UpdateNode (btreePtr, &nodeRec, 0, 0);
1403: M_ExitOnError (err);
1404:
1405: ++btreePtr->numValidHints;
1406:
1407: goto Success;
1408: }
1409: else
1410: {
1411: (void) BTInvalidateHint( iterator );
1412: }
1413:
1414: err = ReleaseNode (btreePtr, &nodeRec);
1415: M_ExitOnError (err);
1416: }
1417: else
1418: {
1419: (void) BTInvalidateHint( iterator );
1420: }
1421: }
1422:
1423:
1424: ////////////////////////////// Get A Clue ///////////////////////////////////
1425:
1426: err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1427: M_ExitOnError (err); // record must exit for Replace
1428:
1429: // optimization - if simple replace will work then don't extend btree
1430: // �� if we tried this before, and failed because it wouldn't fit then we shouldn't try this again...
1431:
1432: err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1433: M_ExitOnError (err);
1434:
1435: if (recordFit)
1436: {
1437: err = UpdateNode (btreePtr, &nodeRec, 0, 0);
1438: M_ExitOnError (err);
1439:
1440: goto Success;
1441: }
1442:
1443:
1444: //////////////////////////// Make Some Room /////////////////////////////////
1445:
1446: nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //�� math limit
1447: if (nodesNeeded > 0)
1448: {
1449: nodesNeeded += btreePtr->totalNodes;
1450: if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
1451: ++nodesNeeded;
1452:
1453: err = ExtendBTree (btreePtr, nodesNeeded);
1454: M_ExitOnError (err);
1455: }
1456:
1457:
1458: DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record
1459:
1460: err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1461: recordLen, &nodeRec, index, 1, kReplaceRecord, &insertNodeNum);
1462: M_ExitOnError (err);
1463:
1464: ++btreePtr->writeCount; /* writeCount changes only if the tree structure changed */
1465:
1466: Success:
1467: // create hint
1468: iterator->hint.writeCount = btreePtr->writeCount;
1469: iterator->hint.nodeNum = insertNodeNum;
1470: iterator->hint.index = 0; // unused
1471: iterator->hint.reserved1 = 0;
1472: iterator->hint.reserved2 = 0;
1473:
1474: LogEndTime(kTraceReplaceBTreeRecord, noErr);
1475:
1476: return noErr;
1477:
1478:
1479: ////////////////////////////// Error Exit ///////////////////////////////////
1480:
1481: ErrorExit:
1482:
1483: (void) ReleaseNode (btreePtr, &nodeRec);
1484:
1485: iterator->hint.writeCount = 0;
1486: iterator->hint.nodeNum = 0;
1487: iterator->hint.index = 0;
1488: iterator->hint.reserved1 = 0;
1489: iterator->hint.reserved2 = 0;
1490:
1491:
1492: LogEndTime(kTraceReplaceBTreeRecord, err);
1493:
1494: return err;
1495: }
1496:
1497:
1498:
1499: //////////////////////////////// BTDeleteRecord /////////////////////////////////
1500:
1501: OSStatus BTDeleteRecord (FCB *filePtr,
1502: BTreeIterator *iterator )
1503: {
1504: OSStatus err;
1505: BTreeControlBlockPtr btreePtr;
1506: TreePathTable treePathTable;
1507: BlockDescriptor nodeRec;
1508: UInt32 nodeNum;
1509: UInt16 index;
1510:
1511: LogStartTime(kTraceDeleteBTreeRecord);
1512:
1513: ////////////////////////// Priliminary Checks ///////////////////////////////
1514:
1515: nodeRec.buffer = nil; // so we can call ReleaseNode
1516:
1517: M_ReturnErrorIf (filePtr == nil, paramErr);
1518: M_ReturnErrorIf (iterator == nil, paramErr);
1519:
1520: btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1521: if (btreePtr == nil)
1522: {
1523: err = fsBTInvalidFileErr;
1524: goto ErrorExit;
1525: }
1526:
1527: RequireFileLock(btreePtr->fileRefNum, false);
1528:
1529:
1530: /////////////////////////////// Find Key ////////////////////////////////////
1531:
1532: //�� check hint for simple delete case (index > 0, numRecords > 2)
1533:
1534: err = SearchTree (btreePtr, &iterator->key, treePathTable, &nodeNum, &nodeRec, &index);
1535: M_ExitOnError (err); // record must exit for Delete
1536:
1537:
1538: ///////////////////////////// Delete Record /////////////////////////////////
1539:
1540: err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1);
1541: M_ExitOnError (err);
1542:
1543: ++btreePtr->writeCount;
1544: --btreePtr->leafRecords;
1545: M_BTreeHeaderDirty (btreePtr);
1546:
1547: iterator->hint.nodeNum = 0;
1548:
1549: LogEndTime(kTraceDeleteBTreeRecord, noErr);
1550:
1551: return noErr;
1552:
1553: ////////////////////////////// Error Exit ///////////////////////////////////
1554:
1555: ErrorExit:
1556: (void) ReleaseNode (btreePtr, &nodeRec);
1557:
1558: LogEndTime(kTraceDeleteBTreeRecord, err);
1559:
1560: return err;
1561: }
1562:
1563:
1564:
1565: OSStatus BTGetInformation (FCB *filePtr,
1566: UInt16 version,
1567: BTreeInfoRec *info )
1568: {
1569: #pragma unused (version)
1570:
1571: BTreeControlBlockPtr btreePtr;
1572:
1573:
1574: M_ReturnErrorIf (filePtr == nil, paramErr);
1575:
1576: btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1577:
1578: RequireFileLock(btreePtr->fileRefNum, true);
1579:
1580: M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1581: M_ReturnErrorIf (info == nil, paramErr);
1582:
1583: //�� check version?
1584:
1585: info->nodeSize = btreePtr->nodeSize;
1586: info->maxKeyLength = btreePtr->maxKeyLength;
1587: info->treeDepth = btreePtr->treeDepth;
1588: info->numRecords = btreePtr->leafRecords;
1589: info->numNodes = btreePtr->totalNodes;
1590: info->numFreeNodes = btreePtr->freeNodes;
1591: info->lastfsync = btreePtr->lastfsync;
1592: info->reserved = 0;
1593:
1594: return noErr;
1595: }
1596:
1597:
1598:
1599: /*-------------------------------------------------------------------------------
1600: Routine: BTFlushPath - Flush BTreeControlBlock to Header Node.
1601:
1602: Function: Brief_description_of_the_function_and_any_side_effects
1603:
1604:
1605: Input: pathPtr - pointer to path control block for B*Tree file to flush
1606:
1607: Output: none
1608:
1609: Result: noErr - success
1610: != noErr - failure
1611: -------------------------------------------------------------------------------*/
1612:
1613: OSStatus BTFlushPath (FCB *filePtr)
1614: {
1615: OSStatus err;
1616: BTreeControlBlockPtr btreePtr;
1617:
1618:
1619: LogStartTime(kTraceFlushBTree);
1620:
1621: M_ReturnErrorIf (filePtr == nil, paramErr);
1622:
1623: btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1624:
1625: M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1626:
1627: RequireFileLock(btreePtr->fileRefNum, false);
1628:
1629: err = UpdateHeader (btreePtr);
1630:
1631: LogEndTime(kTraceFlushBTree, err);
1632:
1633: return err;
1634: }
1635:
1636:
1637:
1638: /*-------------------------------------------------------------------------------
1639: Routine: BTInvalidateHint - Invalidates the hint within a BTreeInterator.
1640:
1641: Function: Invalidates the hint within a BTreeInterator.
1642:
1643:
1644: Input: iterator - pointer to BTreeIterator
1645:
1646: Output: iterator - iterator with the hint.nodeNum cleared
1647:
1648: Result: noErr - success
1649: paramErr - iterator == nil
1650: -------------------------------------------------------------------------------*/
1651:
1652:
1653: OSStatus BTInvalidateHint (BTreeIterator *iterator )
1654: {
1655: if (iterator == nil)
1656: return paramErr;
1657:
1658: iterator->hint.nodeNum = 0;
1659:
1660: return noErr;
1661: }
1662:
1663:
1664:
1665:
1666: /*-------------------------------------------------------------------------------
1667: Routine: BTGetLastSync
1668:
1669: Function: Returns the last time that this btree was flushed, does not include header.
1670:
1671: Input: filePtr - pointer file control block
1672:
1673: Output: lastfsync - time in seconds of last update
1674:
1675: Result: noErr - success
1676: paramErr - iterator == nil
1677: -------------------------------------------------------------------------------*/
1678:
1679:
1680: OSStatus BTGetLastSync (FCB *filePtr,
1681: UInt32 *lastsync)
1682: {
1683: BTreeControlBlockPtr btreePtr;
1684:
1685:
1686: M_ReturnErrorIf (filePtr == nil, paramErr);
1687:
1688: btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1689:
1690: /* Maybe instead of requiring a lock..an atomic set might be more appropriate */
1691: RequireFileLock(btreePtr->fileRefNum, true);
1692:
1693: M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1694: M_ReturnErrorIf (lastsync == nil, paramErr);
1695:
1696: *lastsync = btreePtr->lastfsync;
1697:
1698: return noErr;
1699: }
1700:
1701:
1702:
1703:
1704: /*-------------------------------------------------------------------------------
1705: Routine: BTSetLastSync
1706:
1707: Function: Sets the last time that this btree was flushed, does not include header.
1708:
1709:
1710: Input: fcb - pointer file control block
1711:
1712: Output: lastfsync - time in seconds of last update
1713:
1714: Result: noErr - success
1715: paramErr - iterator == nil
1716: -------------------------------------------------------------------------------*/
1717:
1718:
1719: OSStatus BTSetLastSync (FCB *filePtr,
1720: UInt32 lastsync)
1721: {
1722: BTreeControlBlockPtr btreePtr;
1723:
1724:
1725: M_ReturnErrorIf (filePtr == nil, paramErr);
1726:
1727: btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1728:
1729: /* Maybe instead of requiring a lock..an atomic set might be more appropriate */
1730: RequireFileLock(btreePtr->fileRefNum, true);
1731:
1732: M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1733: M_ReturnErrorIf (lastsync == nil, paramErr);
1734:
1735: btreePtr->lastfsync = lastsync;
1736:
1737: return noErr;
1738: }
1739:
1740:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.