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