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


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