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


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