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


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