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