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