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


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