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


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