]> git.saurik.com Git - apple/xnu.git/blob - bsd/hfs/hfscommon/BTree/BTree.c
projects / apple / xnu.git / blob
? search:


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