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


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