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