]> git.saurik.com Git - apple/hfs.git/blob - fsck_hfs/dfalib/BTree.c
projects / apple / hfs.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
hfs-366.30.3.tar.gz
[apple/hfs.git] / fsck_hfs / dfalib / BTree.c
1 /*
2 * Copyright (c) 1999, 2005 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23 /*
24 File: BTree.c
25
26 Contains: Implementation of public interface routines for B-tree manager.
27
28 Version: HFS Plus 1.0
29
30 Written by: Gordon Sheridan and Bill Bruffey
31
32 Copyright: © 1992-1999 by Apple Computer, Inc., all rights reserved.
33 */
34
35 extern char debug;
36
37 #include "BTree.h"
38 #include "BTreePrivate.h"
39 //#include "HFSInstrumentation.h"
40
41
42 extern Boolean NodesAreContiguous(SFCB *fcb, UInt32 nodeSize);
43 extern void fplog(FILE *stream, const char *fmt, ...);
44
45 /*-------------------------------------------------------------------------------
46 Routine: CopyKey
47
48 Function: Copy a BTree key. Sanity check the key length; if it is too large,
49 then set the copy's length to the BTree's maximum key length.
50
51 Inputs: btcb BTree whose key is being copied
52 srcKey Source key being copied
53
54 Output: destKey Destination where copy will be stored
55
56 Result: none (void)
57 -------------------------------------------------------------------------------*/
58 static void CopyKey(BTreeControlBlockPtr btcb, const BTreeKey *srcKey, BTreeKey *destKey)
59 {
60 unsigned keySize = CalcKeySize(btcb, srcKey);
61 unsigned maxKeySize = MaxKeySize(btcb);
62 int fixLength = 0;
63
64 /*
65 * If the key length is too long (corrupted), then constrain the number
66 * of bytes to copy. Remember that we did this so we can also update
67 * the copy's length field later.
68 */
69 if (keySize > maxKeySize)
70 {
71 keySize = maxKeySize;
72 fixLength = 1;
73 }
74
75 CopyMemory(srcKey, destKey, keySize);
76
77 /*
78 * If we had to constrain the key size above, then also update the
79 * key length in the copy. This will prevent the caller from dereferencing
80 * part of the key which we never actually copied.
81 */
82 if (fixLength)
83 {
84 if (btcb->attributes & kBTBigKeysMask)
85 destKey->length16 = btcb->maxKeyLength;
86 else
87 destKey->length8 = btcb->maxKeyLength;
88 }
89 }
90
91
92 //////////////////////////////////// Globals ////////////////////////////////////
93
94
95 /////////////////////////// BTree Module Entry Points ///////////////////////////
96
97
98 /*-------------------------------------------------------------------------------
99 Routine: InitBTreeModule - Initialize BTree Module Global(s).
100
101 Function: Initialize BTree code, if necessary
102
103 Input: none
104
105 Output: none
106
107 Result: noErr - success
108 != noErr - can't happen
109 -------------------------------------------------------------------------------*/
110
111 OSStatus InitBTreeModule(void)
112 {
113 return noErr;
114 }
115
116
117 /*-------------------------------------------------------------------------------
118 Routine: BTInitialize - Initialize a fork for access as a B*Tree.
119
120 Function: Write Header node and create any map nodes necessary to map the fork
121 as a B*Tree. If the fork is not large enough for the header node, the
122 FS Agent is called to extend the LEOF. Additional map nodes will be
123 allocated if necessary to represent the size of the fork. This allows
124 the FS Agent to specify the initial size of B*Tree files.
125
126
127 Input: pathPtr - pointer to path control block
128 maxKeyLength - maximum length that will be used for any key in this B*Tree
129 nodeSize - node size for B*Tree (must be 2^n, 9 >= n >= 15)
130 btreeType - type of B*Tree
131 keyDescPtr - pointer to key descriptor (optional if key compare proc is used)
132
133 Output: none
134
135 Result: noErr - success
136 paramErr - mandatory parameter was missing
137 E_NoGetBlockProc - FS Agent CB has no GetNodeProcPtr
138 E_NoReleaseBlockProc - FS Agent CB has no ReleaseNodeProcPtr
139 E_NoSetEndOfForkProc - FS Agent CB has no SetEndOfForkProcPtr
140 E_NoSetBlockSizeProc - FS Agent CB has no SetBlockSizeProcPtr
141 fsBTrFileAlreadyOpenErr - fork is already open as a B*Tree
142 fsBTInvalidKeyLengthErr - maximum key length is out of range
143 E_BadNodeType - node size is an illegal value
144 fsBTUnknownVersionErr - the B*Tree type is unknown by this module
145 memFullErr - not enough memory to initialize B*Tree
146 != noErr - failure
147 -------------------------------------------------------------------------------*/
148 #if 0
149 OSStatus BTInitialize (FCB *filePtr,
150 UInt16 maxKeyLength,
151 UInt16 nodeSize,
152 UInt8 btreeType,
153 KeyDescriptorPtr keyDescPtr )
154 {
155 OSStatus err;
156 FSForkControlBlockPtr forkPtr;
157 BTreeControlBlockPtr btreePtr;
158 BlockDescriptor headerNode;
159 HeaderPtr header;
160 Ptr pos;
161 FSSize minEOF, maxEOF;
162 SetEndOfForkProcPtr setEndOfForkProc;
163 SetBlockSizeProcPtr setBlockSizeProc;
164
165 ////////////////////// Preliminary Error Checking ///////////////////////////
166
167 headerNode.buffer = nil;
168
169 if (pathPtr == nil) return paramErr;
170
171 setEndOfForkProc = pathPtr->agentPtr->agent.setEndOfForkProc;
172 setBlockSizeProc = pathPtr->agentPtr->agent.setBlockSizeProc;
173
174 if (pathPtr->agentPtr->agent.getBlockProc == nil) return E_NoGetBlockProc;
175 if (pathPtr->agentPtr->agent.releaseBlockProc == nil) return E_NoReleaseBlockProc;
176 if (setEndOfForkProc == nil) return E_NoSetEndOfForkProc;
177 if (setBlockSizeProc == nil) return E_NoSetBlockSizeProc;
178
179 forkPtr = pathPtr->path.forkPtr;
180
181 if (forkPtr->fork.btreePtr != nil) return fsBTrFileAlreadyOpenErr;
182
183 if ((maxKeyLength == 0) ||
184 (maxKeyLength > kMaxKeyLength)) return fsBTInvalidKeyLengthErr;
185
186 if ( M_IsEven (maxKeyLength)) ++maxKeyLength; // len byte + even bytes + pad byte
187
188 switch (nodeSize) // node size == 512*2^n
189 {
190 case 512:
191 case 1024:
192 case 2048:
193 case 4096:
194 case 8192:
195 case 16384:
196 case 32768: break;
197 default: return E_BadNodeType;
198 }
199
200 switch (btreeType)
201 {
202 case kHFSBTreeType:
203 case kUserBTreeType:
204 case kReservedBTreeType: break;
205
206 default: return fsBTUnknownVersionErr; //¥¥ right?
207 }
208
209
210 //////////////////////// Allocate Control Block /////////////////////////////
211
212 M_RESIDENT_ALLOCATE_FIXED_CLEAR( &btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType );
213 if (btreePtr == nil)
214 {
215 err = memFullErr;
216 goto ErrorExit;
217 }
218
219 btreePtr->version = kBTreeVersion; //¥¥ what is the version?
220 btreePtr->reserved1 = 0;
221 btreePtr->flags = 0;
222 btreePtr->attributes = 0;
223 btreePtr->forkPtr = forkPtr;
224 btreePtr->keyCompareProc = nil;
225 btreePtr->keyDescPtr = keyDescPtr;
226 btreePtr->btreeType = btreeType;
227 btreePtr->treeDepth = 0;
228 btreePtr->rootNode = 0;
229 btreePtr->leafRecords = 0;
230 btreePtr->firstLeafNode = 0;
231 btreePtr->lastLeafNode = 0;
232 btreePtr->nodeSize = nodeSize;
233 btreePtr->maxKeyLength = maxKeyLength;
234 btreePtr->totalNodes = 1; // so ExtendBTree adds maps nodes properly
235 btreePtr->freeNodes = 0;
236 btreePtr->writeCount = 1; // <CS10>, for BTree scanner
237
238 // set block size = nodeSize
239 err = setBlockSizeProc (forkPtr, nodeSize);
240 M_ExitOnError (err);
241
242 ////////////////////////////// Check LEOF ///////////////////////////////////
243
244 minEOF = nodeSize;
245 if ( forkPtr->fork.logicalEOF < minEOF )
246 {
247 // allocate more space if necessary
248 maxEOF 0xFFFFFFFFL;
249
250 err = setEndOfForkProc (forkPtr, minEOF, maxEOF);
251 M_ExitOnError (err);
252 };
253
254
255 //////////////////////// Initialize Header Node /////////////////////////////
256
257 err = GetNewNode (btreePtr, kHeaderNodeNum, &headerNode);
258 M_ExitOnError (err);
259
260 header = headerNode.buffer;
261
262 header->node.type = kHeaderNode;
263 header->node.numRecords = 3; // header rec, key desc, map rec
264
265 header->nodeSize = nodeSize;
266 header->maxKeyLength = maxKeyLength;
267 header->btreeType = btreeType;
268 header->totalNodes = btreePtr->totalNodes;
269 header->freeNodes = btreePtr->totalNodes - 1;
270 // ignore header->clumpSize; //¥¥ rename this field?
271
272 // mark header node allocated in map record
273 pos = ((Ptr)headerNode.buffer) + kHeaderMapRecOffset;
274 *pos = 0x80;
275
276 // set node offsets ( nodeSize-8, F8, 78, 0E)
277 pos = ((Ptr)headerNode.buffer) + nodeSize;
278 pos -= 2; *((UInt16 *)pos) = kHeaderRecOffset;
279 pos -= 2; *((UInt16 *)pos) = kKeyDescRecOffset;
280 pos -= 2; *((UInt16 *)pos) = kHeaderMapRecOffset;
281 pos -= 2; *((UInt16 *)pos) = nodeSize - 8;
282
283
284 ///////////////////// Copy Key Descriptor To Header /////////////////////////
285 #if SupportsKeyDescriptors
286 if (keyDescPtr != nil)
287 {
288 err = CheckKeyDescriptor (keyDescPtr, maxKeyLength);
289 M_ExitOnError (err);
290
291 // copy to header node
292 pos = ((Ptr)headerNode.buffer) + kKeyDescRecOffset;
293 CopyMemory (keyDescPtr, pos, keyDescPtr->length + 1);
294 }
295 #endif
296
297 // write header node
298 err = UpdateNode (btreePtr, &headerNode);
299 M_ExitOnError (err);
300
301
302 ////////////////////////// Allocate Map Nodes ///////////////////////////////
303
304 err = ExtendBTree (btreePtr, forkPtr->fork.logicalEOF.lo / nodeSize); // sets totalNodes
305 M_ExitOnError (err);
306
307
308 ////////////////////////////// Close BTree //////////////////////////////////
309
310 err = UpdateHeader (btreePtr);
311 M_ExitOnError (err);
312
313 pathPtr->path.forkPtr->fork.btreePtr = nil;
314 M_RESIDENT_DEALLOCATE_FIXED( btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType );
315
316 return noErr;
317
318
319 /////////////////////// Error - Clean up and Exit ///////////////////////////
320
321 ErrorExit:
322
323 (void) ReleaseNode (btreePtr, &headerNode);
324 if (btreePtr != nil)
325 M_RESIDENT_DEALLOCATE_FIXED( btreePtr, sizeof( BTreeControlBlock ), kFSBTreeControlBlockType );
326
327 return err;
328 }
329 #endif
330
331
332 /*-------------------------------------------------------------------------------
333 Routine: BTOpenPath - Open a file for access as a B*Tree.
334
335 Function: Create BTree control block for a file, if necessary. Validates the
336 file to be sure it looks like a BTree file.
337
338
339 Input: filePtr - pointer to file to open as a B-tree
340 keyCompareProc - pointer to client's KeyCompare function
341 getBlockProc - pointer to client's GetBlock function
342 releaseBlockProc - pointer to client's ReleaseBlock function
343 setEndOfForkProc - pointer to client's SetEOF function
344
345 Result: noErr - success
346 paramErr - required ptr was nil
347 fsBTInvalidFileErr -
348 memFullErr -
349 != noErr - failure
350 -------------------------------------------------------------------------------*/
351
352 OSStatus BTOpenPath (SFCB *filePtr,
353 KeyCompareProcPtr keyCompareProc,
354 GetBlockProcPtr getBlockProc,
355 ReleaseBlockProcPtr releaseBlockProc,
356 SetEndOfForkProcPtr setEndOfForkProc,
357 SetBlockSizeProcPtr setBlockSizeProc )
358 {
359 OSStatus err;
360 BTreeControlBlockPtr btreePtr;
361 BTHeaderRec *header;
362 NodeRec nodeRec;
363
364 // LogStartTime(kTraceOpenBTree);
365
366 ////////////////////// Preliminary Error Checking ///////////////////////////
367
368 if ( filePtr == nil ||
369 getBlockProc == nil ||
370 releaseBlockProc == nil ||
371 setEndOfForkProc == nil ||
372 setBlockSizeProc == nil )
373 {
374 return paramErr;
375 }
376
377 if ( filePtr->fcbBtree != nil ) // already has a BTreeCB
378 return noErr;
379
380 // is file large enough to contain header node?
381 if ( filePtr->fcbLogicalSize < kMinNodeSize )
382 return fsBTInvalidFileErr; //¥¥ or E_BadHeader?
383
384
385 //////////////////////// Allocate Control Block /////////////////////////////
386
387 btreePtr = (BTreeControlBlock*) AllocateClearMemory( sizeof( BTreeControlBlock ) );
388 if (btreePtr == nil)
389 {
390 Panic ("\pBTOpen: no memory for btreePtr.");
391 return memFullErr;
392 }
393
394 btreePtr->getBlockProc = getBlockProc;
395 btreePtr->releaseBlockProc = releaseBlockProc;
396 btreePtr->setEndOfForkProc = setEndOfForkProc;
397 btreePtr->keyCompareProc = keyCompareProc;
398
399 /////////////////////////// Read Header Node ////////////////////////////////
400
401 nodeRec.buffer = nil; // so we can call ReleaseNode
402
403 btreePtr->fcbPtr = filePtr;
404 filePtr->fcbBtree = (void *) btreePtr; // attach btree cb to file
405
406 // it is now safe to call M_ExitOnError (err)
407
408 err = setBlockSizeProc (btreePtr->fcbPtr, kMinNodeSize);
409 M_ExitOnError (err);
410
411
412 err = getBlockProc (btreePtr->fcbPtr,
413 kHeaderNodeNum,
414 kGetBlock,
415 &nodeRec );
416
417 PanicIf (err != noErr, "\pBTOpen: getNodeProc returned error getting header node.");
418 M_ExitOnError (err);
419
420 header = (BTHeaderRec*) (nodeRec.buffer + sizeof(BTNodeDescriptor));
421
422
423 ///////////////////////////// verify header /////////////////////////////////
424
425 err = VerifyHeader (filePtr, header);
426 M_ExitOnError (err);
427
428
429 ///////////////////// Initalize fields from header //////////////////////////
430
431 PanicIf ( (filePtr->fcbVolume->vcbSignature != 0x4244) && (btreePtr->nodeSize == 512), "\p BTOpenPath: wrong node size for HFS+ volume!");
432
433 btreePtr->treeDepth = header->treeDepth;
434 btreePtr->rootNode = header->rootNode;
435 btreePtr->leafRecords = header->leafRecords;
436 btreePtr->firstLeafNode = header->firstLeafNode;
437 btreePtr->lastLeafNode = header->lastLeafNode;
438 btreePtr->nodeSize = header->nodeSize;
439 btreePtr->maxKeyLength = header->maxKeyLength;
440 btreePtr->totalNodes = header->totalNodes;
441 btreePtr->freeNodes = header->freeNodes;
442 // ignore header->clumpSize; //¥¥ rename this field?
443 btreePtr->btreeType = header->btreeType;
444
445 btreePtr->attributes = header->attributes;
446
447 if ( btreePtr->maxKeyLength > 40 )
448 btreePtr->attributes |= (kBTBigKeysMask + kBTVariableIndexKeysMask); //¥¥ we need a way to save these attributes
449
450 /////////////////////// Initialize dynamic fields ///////////////////////////
451
452 btreePtr->version = kBTreeVersion;
453 btreePtr->flags = 0;
454 btreePtr->writeCount = 1; // <CS10>, for BTree scanner
455
456 btreePtr->numGetNodes = 1; // for earlier call to getNodeProc
457
458 /////////////////////////// Check Header Node ///////////////////////////////
459
460 //¥¥ set kBadClose attribute bit, and UpdateNode
461
462 /*
463 * If the actual node size is different than the amount we read,
464 * then release and trash this block, and re-read with the correct
465 * node size.
466 */
467 if ( btreePtr->nodeSize != kMinNodeSize )
468 {
469 err = setBlockSizeProc (btreePtr->fcbPtr, btreePtr->nodeSize);
470 M_ExitOnError (err);
471
472 #if BSD
473 /*
474 * Need to use kTrashBlock option to force the
475 * buffer cache to re-read the entire node
476 */
477 err = releaseBlockProc(btreePtr->fcbPtr, &nodeRec, kTrashBlock);
478 #else
479 err = ReleaseNode (btreePtr, &nodeRec);
480 #endif
481
482 err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec ); // calls CheckNode...
483 M_ExitOnError (err);
484 }
485
486 //¥¥ total nodes * node size <= LEOF?
487
488
489 ////////////////////////// Get Key Descriptor ///////////////////////////////
490 #if SupportsKeyDescriptors
491 if ( keyCompareProc == nil ) // if no key compare proc then get key descriptor
492 {
493 err = GetKeyDescriptor (btreePtr, nodeRec.buffer); //¥¥ it should check amount of memory allocated...
494 M_ExitOnError (err);
495
496 err = CheckKeyDescriptor (btreePtr->keyDescPtr, btreePtr->maxKeyLength);
497 M_ExitOnError (err);
498
499 }
500 else
501 #endif
502 {
503 btreePtr->keyDescPtr = nil; // clear it so we don't dispose garbage later
504 }
505
506 err = ReleaseNode (btreePtr, &nodeRec);
507 M_ExitOnError (err);
508
509
510 #if BSD
511 /*
512 * Under Mac OS, b-tree nodes can be non-contiguous on disk when the
513 * allocation block size is smaller than the b-tree node size.
514 */
515 if ( !NodesAreContiguous(filePtr, btreePtr->nodeSize) ) {
516 if (debug) fplog(stderr, "Nodes are not contiguous -- this is fatal\n");
517 return fsBTInvalidNodeErr;
518 }
519 #endif
520
521 //////////////////////////////// Success ////////////////////////////////////
522
523 //¥¥ align LEOF to multiple of node size? - just on close
524
525 // LogEndTime(kTraceOpenBTree, noErr);
526
527 return noErr;
528
529
530 /////////////////////// Error - Clean up and Exit ///////////////////////////
531
532 ErrorExit:
533
534 filePtr->fcbBtree = nil;
535 (void) ReleaseNode (btreePtr, &nodeRec);
536 DisposeMemory( btreePtr );
537
538 // LogEndTime(kTraceOpenBTree, err);
539
540 return err;
541 }
542
543
544
545 /*-------------------------------------------------------------------------------
546 Routine: BTClosePath - Flush BTree Header and Deallocate Memory for BTree.
547
548 Function: Flush the BTreeControlBlock fields to header node, and delete BTree control
549 block and key descriptor associated with the file if filePtr is last
550 path of type kBTreeType ('btre').
551
552
553 Input: filePtr - pointer to file to delete BTree control block for.
554
555 Result: noErr - success
556 fsBTInvalidFileErr -
557 != noErr - failure
558 -------------------------------------------------------------------------------*/
559
560 OSStatus BTClosePath (SFCB *filePtr)
561 {
562 OSStatus err;
563 BTreeControlBlockPtr btreePtr;
564 #if 0
565 FSPathControlBlockPtr tempPath;
566 Boolean otherBTreePathsOpen;
567 #endif
568
569 // LogStartTime(kTraceCloseBTree);
570
571 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
572
573 if (btreePtr == nil)
574 return fsBTInvalidFileErr;
575
576 ////////////////////// Check for other BTree Paths //////////////////////////
577
578 #if 0
579 //¥¥ Need replacement field for pathType
580 otherBTreePathsOpen = false;
581 tempPath = forkPtr->fork.pathList.head;
582 while ( (tempPath != (FSPathControlBlockPtr) &forkPtr->fork.pathList) &&
583 (otherBTreePathsOpen == false) )
584 {
585 if ((tempPath != pathPtr) && (tempPath->path.pathType == kBTreeType))
586 {
587 otherBTreePathsOpen = true;
588 break; // done with loop check
589 }
590
591 tempPath = tempPath->next;
592 }
593
594 ////////////////////////// Update Header Node ///////////////////////////////
595
596
597 if (otherBTreePathsOpen == true)
598 {
599 err = UpdateHeader (btreePtr); // update header even if we aren't closing
600 return err; // we only clean up after the last user...
601 }
602 #endif
603
604 btreePtr->attributes &= ~kBTBadCloseMask; // clear "bad close" attribute bit
605 err = UpdateHeader (btreePtr);
606 M_ExitOnError (err);
607
608 #if SupportsKeyDescriptors
609 if (btreePtr->keyDescPtr != nil) // deallocate keyDescriptor, if any
610 {
611 DisposeMemory( btreePtr->keyDescPtr );
612 }
613 #endif
614
615 DisposeMemory( btreePtr );
616 filePtr->fcbBtree = nil;
617
618 // LogEndTime(kTraceCloseBTree, noErr);
619
620 return noErr;
621
622 /////////////////////// Error - Clean Up and Exit ///////////////////////////
623
624 ErrorExit:
625
626 // LogEndTime(kTraceCloseBTree, err);
627
628 return err;
629 }
630
631
632
633 /*-------------------------------------------------------------------------------
634 Routine: BTSearchRecord - Search BTree for a record with a matching key.
635
636 Function: Search for position in B*Tree indicated by searchKey. If a valid node hint
637 is provided, it will be searched first, then SearchTree will be called.
638 If a BTreeIterator is provided, it will be set to the position found as
639 a result of the search. If a record exists at that position, and a BufferDescriptor
640 is supplied, the record will be copied to the buffer (as much as will fit),
641 and recordLen will be set to the length of the record.
642
643 If an error other than fsBTRecordNotFoundErr occurs, the BTreeIterator, if any,
644 is invalidated, and recordLen is set to 0.
645
646
647 Input: pathPtr - pointer to path for BTree file.
648 searchKey - pointer to search key to match.
649 hintPtr - pointer to hint (may be nil)
650
651 Output: record - pointer to BufferDescriptor containing record
652 recordLen - length of data at recordPtr
653 iterator - pointer to BTreeIterator indicating position result of search
654
655 Result: noErr - success, record contains copy of record found
656 fsBTRecordNotFoundErr - record was not found, no data copied
657 fsBTInvalidFileErr - no BTreeControlBlock is allocated for the fork
658 fsBTInvalidKeyLengthErr -
659 != noErr - failure
660 -------------------------------------------------------------------------------*/
661
662 OSStatus BTSearchRecord (SFCB *filePtr,
663 BTreeIterator *searchIterator,
664 UInt32 heuristicHint,
665 FSBufferDescriptor *record,
666 UInt16 *recordLen,
667 BTreeIterator *resultIterator )
668 {
669 OSStatus err;
670 BTreeControlBlockPtr btreePtr;
671 TreePathTable treePathTable;
672 UInt32 nodeNum = 0;
673 BlockDescriptor node;
674 UInt16 index;
675 BTreeKeyPtr keyPtr;
676 RecordPtr recordPtr;
677 UInt16 len;
678 Boolean foundRecord;
679 Boolean validHint;
680
681
682 // LogStartTime(kTraceSearchBTree);
683
684 if (filePtr == nil) return paramErr;
685 if (searchIterator == nil) return paramErr;
686
687 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
688 if (btreePtr == nil) return fsBTInvalidFileErr;
689
690 #if SupportsKeyDescriptors
691 if (btreePtr->keyCompareProc == nil) // CheckKey if we using Key Descriptor
692 {
693 err = CheckKey (&searchIterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength);
694 M_ExitOnError (err);
695 }
696 #endif
697
698 foundRecord = false;
699
700 ////////////////////////////// Take A Hint //////////////////////////////////
701
702 err = IsItAHint (btreePtr, searchIterator, &validHint);
703 M_ExitOnError (err);
704
705 if (validHint)
706 {
707 nodeNum = searchIterator->hint.nodeNum;
708
709 err = GetNode (btreePtr, nodeNum, &node);
710 if( err == noErr )
711 {
712 if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode &&
713 ((BTNodeDescriptor*) node.buffer)->numRecords > 0 )
714 {
715 foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index);
716
717 //¥¥ if !foundRecord, we could still skip tree search if ( 0 < index < numRecords )
718 }
719
720 if (foundRecord == false)
721 {
722 err = ReleaseNode (btreePtr, &node);
723 M_ExitOnError (err);
724 }
725 else
726 {
727 ++btreePtr->numValidHints;
728 }
729 }
730
731 if( foundRecord == false )
732 (void) BTInvalidateHint( searchIterator );
733 }
734
735 ////////////////////////////// Try the heuristicHint //////////////////////////////////
736
737 if ( (foundRecord == false) && (heuristicHint != kInvalidMRUCacheKey) && (nodeNum != heuristicHint) )
738 {
739 // LogStartTime(kHeuristicHint);
740 nodeNum = heuristicHint;
741
742 err = GetNode (btreePtr, nodeNum, &node);
743 if( err == noErr )
744 {
745 if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode &&
746 ((BTNodeDescriptor*) node.buffer)->numRecords > 0 )
747 {
748 foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index);
749 }
750
751 if (foundRecord == false)
752 {
753 err = ReleaseNode (btreePtr, &node);
754 M_ExitOnError (err);
755 }
756 }
757 // LogEndTime(kHeuristicHint, (foundRecord == false));
758 }
759
760 //////////////////////////// Search The Tree ////////////////////////////////
761
762 if (foundRecord == false)
763 {
764 err = SearchTree ( btreePtr, &searchIterator->key, treePathTable, &nodeNum, &node, &index);
765 switch (err)
766 {
767 case noErr: foundRecord = true; break;
768 case fsBTRecordNotFoundErr: break;
769 default: goto ErrorExit;
770 }
771 }
772
773
774 //////////////////////////// Get the Record /////////////////////////////////
775
776 if (foundRecord == true)
777 {
778 //¥¥ Should check for errors! Or BlockMove could choke on recordPtr!!!
779 GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
780
781 if (recordLen != nil) *recordLen = len;
782
783 if (record != nil)
784 {
785 ByteCount recordSize;
786
787 recordSize = record->itemCount * record->itemSize;
788
789 PanicIf(len > recordSize, "\pBTSearchRecord: truncating record!");
790
791 if (len > recordSize) len = recordSize;
792
793 CopyMemory (recordPtr, record->bufferAddress, len);
794 }
795 }
796
797
798 /////////////////////// Success - Update Iterator ///////////////////////////
799
800 if (resultIterator != nil)
801 {
802 resultIterator->hint.writeCount = btreePtr->writeCount;
803 resultIterator->hint.nodeNum = nodeNum;
804 resultIterator->hint.index = index;
805 resultIterator->hint.reserved1 = 0;
806 resultIterator->hint.reserved2 = 0;
807
808 resultIterator->version = 0;
809 resultIterator->reserved = 0;
810
811 // copy the key in the BTree when found rather than searchIterator->key to get proper case/diacriticals
812 if (foundRecord == true)
813 CopyKey(btreePtr, keyPtr, &resultIterator->key);
814 else
815 CopyKey(btreePtr, &searchIterator->key, &resultIterator->key);
816 }
817
818 err = ReleaseNode (btreePtr, &node);
819 M_ExitOnError (err);
820
821 // LogEndTime(kTraceSearchBTree, (foundRecord == false));
822
823 if (foundRecord == false) return fsBTRecordNotFoundErr;
824 else return noErr;
825
826
827 /////////////////////// Error - Clean Up and Exit ///////////////////////////
828
829 ErrorExit:
830
831 if (recordLen != nil)
832 *recordLen = 0;
833
834 if (resultIterator != nil)
835 {
836 resultIterator->hint.writeCount = 0;
837 resultIterator->hint.nodeNum = 0;
838 resultIterator->hint.index = 0;
839 resultIterator->hint.reserved1 = 0;
840 resultIterator->hint.reserved2 = 0;
841
842 resultIterator->version = 0;
843 resultIterator->reserved = 0;
844 resultIterator->key.length16 = 0; // zero out two bytes to cover both types of keys
845 }
846
847 if ( err == fsBTEmptyErr )
848 err = fsBTRecordNotFoundErr;
849
850 // LogEndTime(kTraceSearchBTree, err);
851
852 return err;
853 }
854
855
856
857 /*-------------------------------------------------------------------------------
858 Routine: BTIterateRecord - Find the first, next, previous, or last record.
859
860 Function: Find the first, next, previous, or last record in the BTree
861
862 Input: pathPtr - pointer to path iterate records for.
863 operation - iteration operation (first,next,prev,last)
864 iterator - pointer to iterator indicating start position
865
866 Output: iterator - iterator is updated to indicate new position
867 newKeyPtr - pointer to buffer to copy key found by iteration
868 record - pointer to buffer to copy record found by iteration
869 recordLen - length of record
870
871 Result: noErr - success
872 != noErr - failure
873 -------------------------------------------------------------------------------*/
874
875 OSStatus BTIterateRecord (SFCB *filePtr,
876 BTreeIterationOperation operation,
877 BTreeIterator *iterator,
878 FSBufferDescriptor *record,
879 UInt16 *recordLen )
880 {
881 OSStatus err;
882 BTreeControlBlockPtr btreePtr;
883 BTreeKeyPtr keyPtr;
884 RecordPtr recordPtr;
885 UInt16 len;
886
887 Boolean foundRecord;
888 UInt32 nodeNum;
889
890 BlockDescriptor left, node, right;
891 UInt16 index;
892
893
894 // LogStartTime(kTraceGetBTreeRecord);
895
896 ////////////////////////// Priliminary Checks ///////////////////////////////
897
898 left.buffer = nil;
899 right.buffer = nil;
900 node.buffer = nil;
901
902
903 if (filePtr == nil)
904 {
905 return paramErr;
906 }
907
908 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
909 if (btreePtr == nil)
910 {
911 return fsBTInvalidFileErr; //¥¥ handle properly
912 }
913
914 if ((operation != kBTreeFirstRecord) &&
915 (operation != kBTreeNextRecord) &&
916 (operation != kBTreeCurrentRecord) &&
917 (operation != kBTreePrevRecord) &&
918 (operation != kBTreeLastRecord))
919 {
920 err = fsInvalidIterationMovmentErr;
921 goto ErrorExit;
922 }
923
924 /////////////////////// Find First or Last Record ///////////////////////////
925
926 if ((operation == kBTreeFirstRecord) || (operation == kBTreeLastRecord))
927 {
928 if (operation == kBTreeFirstRecord) nodeNum = btreePtr->firstLeafNode;
929 else nodeNum = btreePtr->lastLeafNode;
930
931 if (nodeNum == 0)
932 {
933 err = fsBTEmptyErr;
934 goto ErrorExit;
935 }
936
937 err = GetNode (btreePtr, nodeNum, &node);
938 M_ExitOnError (err);
939
940 if ( ((NodeDescPtr) node.buffer)->kind != kBTLeafNode ||
941 ((NodeDescPtr) node.buffer)->numRecords <= 0 )
942 {
943 err = ReleaseNode (btreePtr, &node);
944 M_ExitOnError (err);
945
946 if (debug) fprintf(stderr, "%s(%d): returning fsBTInvalidNodeErr\n", __FUNCTION__, __LINE__);
947 err = fsBTInvalidNodeErr;
948 goto ErrorExit;
949 }
950
951 if (operation == kBTreeFirstRecord) index = 0;
952 else index = ((BTNodeDescriptor*) node.buffer)->numRecords - 1;
953
954 goto CopyData; //¥¥ is there a cleaner way?
955 }
956
957
958 //////////////////////// Find Iterator Position /////////////////////////////
959
960 err = FindIteratorPosition (btreePtr, iterator,
961 &left, &node, &right, &nodeNum, &index, &foundRecord);
962 M_ExitOnError (err);
963
964
965 ///////////////////// Find Next Or Previous Record //////////////////////////
966
967 if (operation == kBTreePrevRecord)
968 {
969 if (index > 0)
970 {
971 --index;
972 }
973 else
974 {
975 if (left.buffer == nil)
976 {
977 nodeNum = ((NodeDescPtr) node.buffer)->bLink;
978 if ( nodeNum > 0)
979 {
980 err = GetNode (btreePtr, nodeNum, &left);
981 M_ExitOnError (err);
982 } else {
983 err = fsBTStartOfIterationErr;
984 goto ErrorExit;
985 }
986 }
987 // Before we stomp on "right", we'd better release it if needed
988 if (right.buffer != nil) {
989 err = ReleaseNode(btreePtr, &right);
990 M_ExitOnError(err);
991 }
992 right = node;
993 node = left;
994 left.buffer = nil;
995 index = ((NodeDescPtr) node.buffer)->numRecords -1;
996 }
997 }
998 else if (operation == kBTreeNextRecord)
999 {
1000 if ((foundRecord != true) &&
1001 (((NodeDescPtr) node.buffer)->fLink == 0) &&
1002 (index == ((NodeDescPtr) node.buffer)->numRecords))
1003 {
1004 err = fsBTEndOfIterationErr;
1005 goto ErrorExit;
1006 }
1007
1008 // we did not find the record but the index is already positioned correctly
1009 if ((foundRecord == false) && (index != ((NodeDescPtr) node.buffer)->numRecords))
1010 goto CopyData;
1011
1012 // we found the record OR we have to look in the next node
1013 if (index < ((NodeDescPtr) node.buffer)->numRecords -1)
1014 {
1015 ++index;
1016 }
1017 else
1018 {
1019 if (right.buffer == nil)
1020 {
1021 nodeNum = ((NodeDescPtr) node.buffer)->fLink;
1022 if ( nodeNum > 0)
1023 {
1024 err = GetNode (btreePtr, nodeNum, &right);
1025 M_ExitOnError (err);
1026 } else {
1027 err = fsBTEndOfIterationErr;
1028 goto ErrorExit;
1029 }
1030 }
1031 // Before we stomp on "left", we'd better release it if needed
1032 if (left.buffer != nil) {
1033 err = ReleaseNode(btreePtr, &left);
1034 M_ExitOnError(err);
1035 }
1036 left = node;
1037 node = right;
1038 right.buffer = nil;
1039 index = 0;
1040 }
1041 }
1042 else // operation == kBTreeCurrentRecord
1043 {
1044 // make sure we have something... <CS9>
1045 if ((foundRecord != true) &&
1046 (index >= ((NodeDescPtr) node.buffer)->numRecords))
1047 {
1048 err = fsBTEndOfIterationErr;
1049 goto ErrorExit;
1050 }
1051 }
1052
1053 //////////////////// Copy Record And Update Iterator ////////////////////////
1054
1055 CopyData:
1056
1057 // added check for errors <CS9>
1058 err = GetRecordByIndex (btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
1059 M_ExitOnError (err);
1060
1061 if (recordLen != nil) *recordLen = len;
1062
1063 if (record != nil)
1064 {
1065 ByteCount recordSize;
1066
1067 recordSize = record->itemCount * record->itemSize;
1068
1069 PanicIf(len > recordSize, "\pBTIterateRecord: truncating record!");
1070
1071 if (len > recordSize) len = recordSize;
1072
1073 CopyMemory (recordPtr, record->bufferAddress, len);
1074 }
1075
1076 if (iterator != nil) // first & last do not require iterator
1077 {
1078 iterator->hint.writeCount = btreePtr->writeCount;
1079 iterator->hint.nodeNum = nodeNum;
1080 iterator->hint.index = index;
1081 iterator->hint.reserved1 = 0;
1082 iterator->hint.reserved2 = 0;
1083
1084 iterator->version = 0;
1085 iterator->reserved = 0;
1086
1087 CopyKey(btreePtr, keyPtr, &iterator->key);
1088 }
1089
1090
1091 ///////////////////////////// Release Nodes /////////////////////////////////
1092
1093 err = ReleaseNode (btreePtr, &node);
1094 M_ExitOnError (err);
1095
1096 if (left.buffer != nil)
1097 {
1098 err = ReleaseNode (btreePtr, &left);
1099 M_ExitOnError (err);
1100 }
1101
1102 if (right.buffer != nil)
1103 {
1104 err = ReleaseNode (btreePtr, &right);
1105 M_ExitOnError (err);
1106 }
1107
1108 // LogEndTime(kTraceGetBTreeRecord, noErr);
1109
1110 return noErr;
1111
1112 /////////////////////// Error - Clean Up and Exit ///////////////////////////
1113
1114 ErrorExit:
1115
1116 (void) ReleaseNode (btreePtr, &left);
1117 (void) ReleaseNode (btreePtr, &node);
1118 (void) ReleaseNode (btreePtr, &right);
1119
1120 if (recordLen != nil)
1121 *recordLen = 0;
1122
1123 if (iterator != nil)
1124 {
1125 iterator->hint.writeCount = 0;
1126 iterator->hint.nodeNum = 0;
1127 iterator->hint.index = 0;
1128 iterator->hint.reserved1 = 0;
1129 iterator->hint.reserved2 = 0;
1130
1131 iterator->version = 0;
1132 iterator->reserved = 0;
1133 iterator->key.length16 = 0;
1134 }
1135
1136 if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
1137 err = fsBTRecordNotFoundErr;
1138
1139 // LogEndTime(kTraceGetBTreeRecord, err);
1140
1141 return err;
1142 }
1143
1144
1145 //////////////////////////////// BTInsertRecord /////////////////////////////////
1146
1147 OSStatus BTInsertRecord (SFCB *filePtr,
1148 BTreeIterator *iterator,
1149 FSBufferDescriptor *record,
1150 UInt16 recordLen )
1151 {
1152 OSStatus err;
1153 BTreeControlBlockPtr btreePtr;
1154 TreePathTable treePathTable;
1155 SInt32 nodesNeeded;
1156 BlockDescriptor nodeRec;
1157 UInt32 insertNodeNum;
1158 UInt16 index;
1159 Boolean recordFit;
1160
1161
1162 ////////////////////////// Priliminary Checks ///////////////////////////////
1163
1164 nodeRec.buffer = nil; // so we can call ReleaseNode
1165
1166 err = CheckInsertParams (filePtr, iterator, record, recordLen);
1167 if (err != noErr)
1168 return err;
1169
1170 // LogStartTime(kTraceInsertBTreeRecord);
1171
1172 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1173
1174 ///////////////////////// Find Insert Position //////////////////////////////
1175
1176 // always call SearchTree for Insert
1177 err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1178
1179 switch (err) // set/replace/insert decision point
1180 {
1181 case noErr: err = fsBTDuplicateRecordErr;
1182 goto ErrorExit;
1183
1184 case fsBTRecordNotFoundErr: break;
1185
1186 case fsBTEmptyErr: // if tree empty add 1st leaf node
1187
1188 if (btreePtr->freeNodes == 0)
1189 {
1190 err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
1191 M_ExitOnError (err);
1192 }
1193
1194 err = AllocateNode (btreePtr, &insertNodeNum);
1195 M_ExitOnError (err);
1196
1197 err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
1198 M_ExitOnError (err);
1199
1200 ((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
1201 ((NodeDescPtr)nodeRec.buffer)->height = 1;
1202
1203 recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0,
1204 &iterator->key, KeyLength(btreePtr, &iterator->key),
1205 record->bufferAddress, recordLen );
1206 if (recordFit != true)
1207 {
1208 err = fsBTRecordTooLargeErr;
1209 goto ErrorExit;
1210 }
1211
1212 err = UpdateNode (btreePtr, &nodeRec);
1213 M_ExitOnError (err);
1214
1215 // update BTreeControlBlock
1216 btreePtr->treeDepth = 1;
1217 btreePtr->rootNode = insertNodeNum;
1218 btreePtr->firstLeafNode = insertNodeNum;
1219 btreePtr->lastLeafNode = insertNodeNum;
1220 M_BTreeHeaderDirty (btreePtr);
1221
1222 goto Success;
1223
1224 default:
1225 goto ErrorExit;
1226 }
1227
1228 if (index > 0)
1229 {
1230 recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
1231 &iterator->key, KeyLength(btreePtr, &iterator->key),
1232 record->bufferAddress, recordLen);
1233 if (recordFit == true)
1234 {
1235 err = UpdateNode (btreePtr, &nodeRec);
1236 M_ExitOnError (err);
1237
1238 goto Success;
1239 }
1240 }
1241
1242 /////////////////////// Extend File If Necessary ////////////////////////////
1243
1244 nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //¥¥ math limit
1245 if (nodesNeeded > 0)
1246 {
1247 nodesNeeded += btreePtr->totalNodes;
1248 if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
1249 ++nodesNeeded;
1250
1251 err = ExtendBTree (btreePtr, nodesNeeded);
1252 M_ExitOnError (err);
1253 }
1254
1255 // no need to delete existing record
1256
1257 err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1258 recordLen, &nodeRec, index, 1, kInsertRecord, &insertNodeNum);
1259 M_ExitOnError (err);
1260
1261
1262 //////////////////////////////// Success ////////////////////////////////////
1263
1264 Success:
1265 ++btreePtr->writeCount; // <CS10>
1266 ++btreePtr->leafRecords;
1267 M_BTreeHeaderDirty (btreePtr);
1268
1269 // create hint
1270 iterator->hint.writeCount = btreePtr->writeCount; // unused until <CS10>
1271 iterator->hint.nodeNum = insertNodeNum;
1272 iterator->hint.index = 0; // unused
1273 iterator->hint.reserved1 = 0;
1274 iterator->hint.reserved2 = 0;
1275
1276 // LogEndTime(kTraceInsertBTreeRecord, noErr);
1277
1278 return noErr;
1279
1280
1281 ////////////////////////////// Error Exit ///////////////////////////////////
1282
1283 ErrorExit:
1284 (void) ReleaseNode (btreePtr, &nodeRec);
1285
1286 iterator->hint.writeCount = 0;
1287 iterator->hint.nodeNum = 0;
1288 iterator->hint.index = 0;
1289 iterator->hint.reserved1 = 0;
1290 iterator->hint.reserved2 = 0;
1291
1292 if (err == fsBTEmptyErr)
1293 err = fsBTRecordNotFoundErr;
1294
1295 // LogEndTime(kTraceInsertBTreeRecord, err);
1296
1297 return err;
1298 }
1299
1300
1301
1302 ////////////////////////////////// BTSetRecord //////////////////////////////////
1303 #if 0
1304 OSStatus BTSetRecord (SFCB *filePtr,
1305 BTreeIterator *iterator,
1306 FSBufferDescriptor *record,
1307 UInt16 recordLen )
1308 {
1309 OSStatus err;
1310 BTreeControlBlockPtr btreePtr;
1311 TreePathTable treePathTable;
1312 SInt32 nodesNeeded;
1313 BlockDescriptor nodeRec;
1314 UInt32 insertNodeNum;
1315 UInt16 index;
1316 Boolean recordFound = false;
1317 Boolean recordFit;
1318 Boolean operation;
1319 Boolean validHint;
1320
1321
1322 ////////////////////////// Priliminary Checks ///////////////////////////////
1323
1324 nodeRec.buffer = nil; // so we can call ReleaseNode
1325
1326 err = CheckInsertParams (filePtr, iterator, record, recordLen);
1327 if (err != noErr)
1328 return err;
1329
1330 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1331
1332
1333 ///////////////////////// Find Insert Position //////////////////////////////
1334
1335 err = IsItAHint (btreePtr, iterator, &validHint);
1336 M_ExitOnError (err);
1337
1338 if (validHint)
1339 {
1340 insertNodeNum = iterator->hint.nodeNum;
1341
1342 err = GetNode (btreePtr, insertNodeNum, &nodeRec);
1343 if( err == noErr )
1344 {
1345 err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1346 M_ExitOnError (err);
1347
1348 if (recordFit)
1349 {
1350 err = UpdateNode (btreePtr, &nodeRec);
1351 M_ExitOnError (err);
1352
1353 recordFound = true;
1354 ++btreePtr->numValidHints;
1355 goto Success;
1356 } // else
1357 else
1358 {
1359 (void) BTInvalidateHint( iterator );
1360 }
1361
1362 err = ReleaseNode (btreePtr, &nodeRec);
1363 M_ExitOnError (err);
1364 }
1365 }
1366
1367 err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1368
1369 switch (err) // set/replace/insert decision point
1370 {
1371 case noErr: recordFound = true;
1372 break;
1373
1374 case fsBTRecordNotFoundErr: break;
1375
1376 case fsBTEmptyErr: // if tree empty add 1st leaf node
1377
1378 if (btreePtr->freeNodes == 0)
1379 {
1380 err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
1381 M_ExitOnError (err);
1382 }
1383
1384 err = AllocateNode (btreePtr, &insertNodeNum);
1385 M_ExitOnError (err);
1386
1387 err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
1388 M_ExitOnError (err);
1389
1390 ((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
1391 ((NodeDescPtr)nodeRec.buffer)->height = 1;
1392
1393 recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, 0,
1394 &iterator->key, KeyLength(btreePtr, &iterator->key),
1395 record->bufferAddress, recordLen );
1396 if (recordFit != true)
1397 {
1398 err = fsBTRecordTooLargeErr;
1399 goto ErrorExit;
1400 }
1401
1402 err = UpdateNode (btreePtr, &nodeRec);
1403 M_ExitOnError (err);
1404
1405 // update BTreeControlBlock
1406 btreePtr->rootNode = insertNodeNum;
1407 btreePtr->treeDepth = 1;
1408 btreePtr->flags |= kBTHeaderDirty;
1409
1410 goto Success;
1411
1412 default: goto ErrorExit;
1413 }
1414
1415
1416 if (recordFound == true) // Simple Replace - optimization avoids unecessary ExtendBTree
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);
1424 M_ExitOnError (err);
1425
1426 goto Success;
1427 }
1428 }
1429
1430
1431 /////////////////////// Extend File If Necessary ////////////////////////////
1432
1433 nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //¥¥ math limit
1434 if (nodesNeeded > 0)
1435 {
1436 nodesNeeded += btreePtr->totalNodes;
1437 if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
1438 ++nodesNeeded;
1439
1440 err = ExtendBTree (btreePtr, nodesNeeded);
1441 M_ExitOnError (err);
1442 }
1443
1444
1445 if (recordFound == true) // Delete existing record
1446 {
1447 DeleteRecord (btreePtr, nodeRec.buffer, index);
1448 operation = kReplaceRecord;
1449 } else {
1450 operation = kInsertRecord;
1451 }
1452
1453 err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1454 recordLen, &nodeRec, index, 1, operation, &insertNodeNum);
1455 M_ExitOnError (err);
1456
1457 ++btreePtr->writeCount; // <CS10> writeCount changes only if the tree structure changed
1458
1459 Success:
1460 if (recordFound == false)
1461 {
1462 ++btreePtr->leafRecords;
1463 M_BTreeHeaderDirty (btreePtr);
1464 }
1465
1466 // create hint
1467 iterator->hint.writeCount = btreePtr->writeCount; // unused until <CS10>
1468 iterator->hint.nodeNum = insertNodeNum;
1469 iterator->hint.index = 0; // unused
1470 iterator->hint.reserved1 = 0;
1471 iterator->hint.reserved2 = 0;
1472
1473 return noErr;
1474
1475
1476 ////////////////////////////// Error Exit ///////////////////////////////////
1477
1478 ErrorExit:
1479
1480 (void) ReleaseNode (btreePtr, &nodeRec);
1481
1482 iterator->hint.writeCount = 0;
1483 iterator->hint.nodeNum = 0;
1484 iterator->hint.index = 0;
1485 iterator->hint.reserved1 = 0;
1486 iterator->hint.reserved2 = 0;
1487
1488 return err;
1489 }
1490 #endif
1491
1492
1493 //////////////////////////////// BTReplaceRecord ////////////////////////////////
1494
1495 OSStatus BTReplaceRecord (SFCB *filePtr,
1496 BTreeIterator *iterator,
1497 FSBufferDescriptor *record,
1498 UInt16 recordLen )
1499 {
1500 OSStatus err;
1501 BTreeControlBlockPtr btreePtr;
1502 TreePathTable treePathTable;
1503 SInt32 nodesNeeded;
1504 BlockDescriptor nodeRec;
1505 UInt32 insertNodeNum;
1506 UInt16 index;
1507 Boolean recordFit;
1508 Boolean validHint;
1509
1510
1511 ////////////////////////// Priliminary Checks ///////////////////////////////
1512
1513 nodeRec.buffer = nil; // so we can call ReleaseNode
1514
1515 err = CheckInsertParams (filePtr, iterator, record, recordLen);
1516 if (err != noErr)
1517 return err;
1518
1519 // LogStartTime(kTraceReplaceBTreeRecord);
1520
1521 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1522
1523 ////////////////////////////// Take A Hint //////////////////////////////////
1524
1525 err = IsItAHint (btreePtr, iterator, &validHint);
1526 M_ExitOnError (err);
1527
1528 if (validHint)
1529 {
1530 insertNodeNum = iterator->hint.nodeNum;
1531
1532 err = GetNode (btreePtr, insertNodeNum, &nodeRec);
1533 if( err == noErr )
1534 {
1535 err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1536 M_ExitOnError (err);
1537
1538 if (recordFit)
1539 {
1540 err = UpdateNode (btreePtr, &nodeRec);
1541 M_ExitOnError (err);
1542
1543 ++btreePtr->numValidHints;
1544
1545 goto Success;
1546 }
1547 else
1548 {
1549 (void) BTInvalidateHint( iterator );
1550 }
1551
1552 err = ReleaseNode (btreePtr, &nodeRec);
1553 M_ExitOnError (err);
1554 }
1555 else
1556 {
1557 (void) BTInvalidateHint( iterator );
1558 }
1559 }
1560
1561
1562 ////////////////////////////// Get A Clue ///////////////////////////////////
1563
1564 err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1565 M_ExitOnError (err); // record must exit for Replace
1566
1567 // optimization - if simple replace will work then don't extend btree
1568 // ¥¥ if we tried this before, and failed because it wouldn't fit then we shouldn't try this again...
1569
1570 err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1571 M_ExitOnError (err);
1572
1573 if (recordFit)
1574 {
1575 err = UpdateNode (btreePtr, &nodeRec);
1576 M_ExitOnError (err);
1577
1578 goto Success;
1579 }
1580
1581
1582 //////////////////////////// Make Some Room /////////////////////////////////
1583
1584 nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //¥¥ math limit
1585 if (nodesNeeded > 0)
1586 {
1587 nodesNeeded += btreePtr->totalNodes;
1588 if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
1589 ++nodesNeeded;
1590
1591 err = ExtendBTree (btreePtr, nodesNeeded);
1592 M_ExitOnError (err);
1593 }
1594
1595
1596 DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record
1597
1598 err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1599 recordLen, &nodeRec, index, 1, kReplaceRecord, &insertNodeNum);
1600 M_ExitOnError (err);
1601
1602 ++btreePtr->writeCount; // <CS10> writeCount changes only if the tree structure changed
1603
1604 Success:
1605 // create hint
1606 iterator->hint.writeCount = btreePtr->writeCount; // unused until <CS10>
1607 iterator->hint.nodeNum = insertNodeNum;
1608 iterator->hint.index = 0; // unused
1609 iterator->hint.reserved1 = 0;
1610 iterator->hint.reserved2 = 0;
1611
1612 // LogEndTime(kTraceReplaceBTreeRecord, noErr);
1613
1614 return noErr;
1615
1616
1617 ////////////////////////////// Error Exit ///////////////////////////////////
1618
1619 ErrorExit:
1620
1621 (void) ReleaseNode (btreePtr, &nodeRec);
1622
1623 iterator->hint.writeCount = 0;
1624 iterator->hint.nodeNum = 0;
1625 iterator->hint.index = 0;
1626 iterator->hint.reserved1 = 0;
1627 iterator->hint.reserved2 = 0;
1628
1629 // LogEndTime(kTraceReplaceBTreeRecord, err);
1630
1631 return err;
1632 }
1633
1634
1635
1636 //////////////////////////////// BTDeleteRecord /////////////////////////////////
1637
1638 OSStatus BTDeleteRecord (SFCB *filePtr,
1639 BTreeIterator *iterator )
1640 {
1641 OSStatus err;
1642 BTreeControlBlockPtr btreePtr;
1643 TreePathTable treePathTable;
1644 BlockDescriptor nodeRec;
1645 UInt32 nodeNum;
1646 UInt16 index;
1647
1648 // LogStartTime(kTraceDeleteBTreeRecord);
1649
1650 ////////////////////////// Priliminary Checks ///////////////////////////////
1651
1652 nodeRec.buffer = nil; // so we can call ReleaseNode
1653
1654 M_ReturnErrorIf (filePtr == nil, paramErr);
1655 M_ReturnErrorIf (iterator == nil, paramErr);
1656
1657 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1658 if (btreePtr == nil)
1659 {
1660 err = fsBTInvalidFileErr;
1661 goto ErrorExit;
1662 }
1663
1664 #if SupportsKeyDescriptors
1665 if (btreePtr->keyDescPtr != nil)
1666 {
1667 err = CheckKey (&iterator->key, btreePtr->keyDescPtr, btreePtr->maxKeyLength);
1668 M_ExitOnError (err);
1669 }
1670 #endif
1671
1672 /////////////////////////////// Find Key ////////////////////////////////////
1673
1674 //¥¥ check hint for simple delete case (index > 0, numRecords > 2)
1675
1676 err = SearchTree (btreePtr, &iterator->key, treePathTable, &nodeNum, &nodeRec, &index);
1677 M_ExitOnError (err); // record must exit for Delete
1678
1679
1680 ///////////////////////////// Delete Record /////////////////////////////////
1681
1682 err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1);
1683 M_ExitOnError (err);
1684
1685 //Success:
1686 ++btreePtr->writeCount; // <CS10>
1687 --btreePtr->leafRecords;
1688 M_BTreeHeaderDirty (btreePtr);
1689
1690 iterator->hint.nodeNum = 0;
1691
1692 // LogEndTime(kTraceDeleteBTreeRecord, noErr);
1693
1694 return noErr;
1695
1696 ////////////////////////////// Error Exit ///////////////////////////////////
1697
1698 ErrorExit:
1699 (void) ReleaseNode (btreePtr, &nodeRec);
1700
1701 // LogEndTime(kTraceDeleteBTreeRecord, err);
1702
1703 return err;
1704 }
1705
1706
1707
1708 OSStatus BTGetInformation (SFCB *filePtr,
1709 UInt16 version,
1710 BTreeInfoRec *info )
1711 {
1712 #pragma unused (version)
1713
1714 BTreeControlBlockPtr btreePtr;
1715
1716
1717 M_ReturnErrorIf (filePtr == nil, paramErr);
1718
1719 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1720
1721 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1722 M_ReturnErrorIf (info == nil, paramErr);
1723
1724 //¥¥ check version?
1725
1726 info->nodeSize = btreePtr->nodeSize;
1727 info->maxKeyLength = btreePtr->maxKeyLength;
1728 info->treeDepth = btreePtr->treeDepth;
1729 info->numRecords = btreePtr->leafRecords;
1730 info->numNodes = btreePtr->totalNodes;
1731 info->numFreeNodes = btreePtr->freeNodes;
1732 info->keyDescriptor = btreePtr->keyDescPtr; //¥¥ this won't do at all...
1733 info->reserved = 0;
1734
1735 if (btreePtr->keyDescPtr == nil)
1736 info->keyDescLength = 0;
1737 else
1738 info->keyDescLength = (UInt32) btreePtr->keyDescPtr->length;
1739
1740 return noErr;
1741 }
1742
1743
1744
1745 /*-------------------------------------------------------------------------------
1746 Routine: BTFlushPath - Flush BTreeControlBlock to Header Node.
1747
1748 Function: Brief_description_of_the_function_and_any_side_effects
1749
1750
1751 Input: pathPtr - pointer to path control block for B*Tree file to flush
1752
1753 Output: none
1754
1755 Result: noErr - success
1756 != noErr - failure
1757 -------------------------------------------------------------------------------*/
1758
1759 OSStatus BTFlushPath (SFCB *filePtr)
1760 {
1761 OSStatus err;
1762 BTreeControlBlockPtr btreePtr;
1763
1764
1765 // LogStartTime(kTraceFlushBTree);
1766
1767 M_ReturnErrorIf (filePtr == nil, paramErr);
1768
1769 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBtree;
1770
1771 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1772
1773 err = UpdateHeader (btreePtr);
1774
1775 // LogEndTime(kTraceFlushBTree, err);
1776
1777 return err;
1778 }
1779
1780
1781
1782 /*-------------------------------------------------------------------------------
1783 Routine: BTInvalidateHint - Invalidates the hint within a BTreeInterator.
1784
1785 Function: Invalidates the hint within a BTreeInterator.
1786
1787
1788 Input: iterator - pointer to BTreeIterator
1789
1790 Output: iterator - iterator with the hint.nodeNum cleared
1791
1792 Result: noErr - success
1793 paramErr - iterator == nil
1794 -------------------------------------------------------------------------------*/
1795
1796
1797 OSStatus BTInvalidateHint (BTreeIterator *iterator )
1798 {
1799 if (iterator == nil)
1800 return paramErr;
1801
1802 iterator->hint.nodeNum = 0;
1803
1804 return noErr;
1805 }
1806
mirror of hfs