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


d61c73936cb373c2c87ab40b9b943159074a493d
[apple/xnu.git] / bsd / hfs / hfscommon / BTree / BTree.c
1 /*
2 * Copyright (c) 2000-2003 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
7 *
8 * This file contains Original Code and/or Modifications of Original Code
9 * as defined in and that are subject to the Apple Public Source License
10 * Version 2.0 (the 'License'). You may not use this file except in
11 * compliance with the License. Please obtain a copy of the License at
12 * http://www.opensource.apple.com/apsl/ and read it before using this
13 * file.
14 *
15 * The Original Code and all software distributed under the License are
16 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
17 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
18 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
20 * Please see the License for the specific language governing rights and
21 * limitations under the License.
22 *
23 * @APPLE_LICENSE_HEADER_END@
24 */
25 /*
26 File: BTree.c
27
28 Contains: Implementation of public interface routines for B-tree manager.
29
30 Version: HFS Plus 1.0
31
32 Written by: Gordon Sheridan and Bill Bruffey
33
34 Copyright: © 1992-1999 by Apple Computer, Inc., all rights reserved.
35
36 File Ownership:
37
38 DRI: Don Brady
39
40 Other Contact: Mark Day
41
42 Technology: File Systems
43
44 Writers:
45
46 (msd) Mark Day
47 (DSH) Deric Horn
48 (djb) Don Brady
49
50 Change History (most recent first):
51 <MOSXS> 9/22/99 ser Added routines BTGetLastSync and BTSetLastSync
52 <MOSXS> 6/1/99 djb Sync up with Mac OS 8.6.
53 <MOSXS> 6/30/98 djb In BTOpenPath make sure nodes are contiguous on disk (radar #2249539).
54 <MOSXS> 4/15/98 djb In BTOpenPath need to clear nodeRec.buffer if GetBlockProc fails.
55 <MOSXS> 4/11/98 djb Add RequireFileLock checking to all external entry points.
56
57 <MOSXS> 03/23/98 djb In BTOpenPath use kTrashBlock option when releasing the header so
58 that we get a full node when we call GetNode.
59
60 <CS9> 12/12/97 djb Radar #2202682, BTIterateRecord with kBTreeCurrentRecord was not
61 checking if we had a record and could call BlockMove with an
62 uninitialize source pointer (causing a bus error).
63 <CS8> 10/24/97 msd In BTIterateRecord, when moving to the previous or next record
64 and we have to move to another node, see if we need to release
65 the node about to be "shifted out" (opposite sibling of the
66 direction we need to move).
67 <CS7> 7/25/97 DSH BTSearchRecord now takes a heuristicHint, nodeNum, and tries it
68 before calling SearchBTree
69 <CS6> 7/24/97 djb GetBlockProc now take a file refnum instead of an FCB ptr.
70 <CS5> 7/22/97 djb Move trace points from BTreeWrapper.c to here.
71 <CS4> 7/21/97 djb LogEndTime now takes an error code.
72 <CS3> 7/16/97 DSH FilesInternal.i renamed FileMgrInternal.i to avoid name
73 collision
74 <CS2> 5/19/97 djb Add summary traces to BTIterateRecord.
75 <CS1> 4/23/97 djb first checked in
76
77 <HFS7> 2/19/97 djb Enable variable sized index keys for HFS+ volumes. Added node
78 cache to support nodes larger than 512 bytes.
79 <HFS6> 1/27/97 djb Calls to InsertTree and DeleteTree are now recursive (to support
80 variable sized index keys).
81 <HFS5> 1/13/97 djb Added support for getting current record to BTIterateRecord.
82 <HFS4> 1/6/97 djb Initialize "BigKeys" attribute in BTOpen.
83 <HFS3> 1/3/97 djb Added support for large keys.
84 <HFS2> 12/23/96 djb On exit map fsBTEmptyErr and fsBTEndOfIterationErr to
85 fsBTRecordNotFoundErr.
86 <HFS1> 12/19/96 djb first checked in
87
88 History applicable to original Scarecrow Design:
89
90 <13> 10/25/96 ser Changing for new VFPI
91 <12> 10/18/96 ser Converting over VFPI changes
92 <11> 9/17/96 dkh More BTree statistics. Modified hint checks to not bail out when
93 an error is returned from GetNode.
94 <10> 9/16/96 dkh Revised BTree statistics.
95 <9> 8/23/96 dkh Remove checks for multiple paths to BTree file. Need to add
96 equivalent mechanism later.
97 <8> 6/20/96 dkh Radar #1358740. Switch from using Pools to debug MemAllocators.
98 <7> 3/14/96 jev Fix BTreeSetRecord, recordFound was not set for the case of a
99 simple replace causing the leafRecords count to get bumped even
100 though we didn't have to add a record.
101 <6> 3/1/96 prp Fix lint problems. Bug in BTSetRecord that does not initialize
102 recordFound.
103 <5> 1/22/96 dkh Add #include Memory.h
104 <4> 1/10/96 msd Use the real function names from Math64.i.
105 <3> 1/4/96 jev Fix BTItererateRecord for the condition when the iterator
106 position routine does not find the record and we are looking for
107 the next record. In such a case, if the node's forrward link is
108 non-zero, we have to keep iterating next and not return
109 fsBTEndOfIterationErr error.
110 <2> 12/7/95 dkh D10E2 build. Changed usage of Ref data type to LogicalAddress.
111 <1> 10/18/95 rst Moved from Scarecrow project.
112
113 <24> 7/18/95 mbb Change MoveData & ClearBytes to BlockMoveData & BlockZero.
114 <23> 1/31/95 prp GetBlockProc interface uses a 64 bit node number.
115 <22> 1/12/95 wjk Adopt Model FileSystem changes in D5.
116 <21> 11/16/94 prp Add IsItAHint routine and use it whenever hint's node number was
117 used for testing.
118 <20> 11/10/94 prp BTGetInfo name collides with the same name in FileManagerPriv.i.
119 Change it to BTGetInformation.
120 <19> 9/30/94 prp Get in sync with D2 interface changes.
121 <18> 7/22/94 wjk Convert to the new set of header files.
122 <17> 12/9/93 wjk Cleanup usage of char, Byte, int8, UInt8, etc.
123 <16> 12/2/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
124 NRCmds environments.
125 <15> 11/30/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
126 NRCmds environments.
127 <14> 9/30/93 gs Rename E_NoGetNodeProc and E_NoReleaseNodeProc to
128 E_NoXxxxBlockProc.
129 <13> 8/31/93 prp Use Set64U instead of Set64.
130 <12> 8/16/93 prp In BTSearchRecord, if the input hint found the node and record,
131 set the local nodeNum variable correctly so that the resultant
132 iterator gets set correctly.
133 <11> 7/1/93 gs Fix bug in BTIterateRecord related to kBTreePrevRecord
134 operation.
135 <10> 6/2/93 gs Update for changes to FSErrors.h and add some comments.
136 <9> 5/24/93 gs Fix bug in BTInsert/Set/ReplaceRecord which didn't set node hint
137 properly in some cases.
138 <8> 5/24/93 gs Do NOT map fsBTEmptyErr to fsBTRecordNotFoundErr in BTSearchRecord.
139 <7> 5/24/93 gs Rename BTFlush to BTFlushPath.
140 <6> 5/21/93 gs Add hint optimization to Set/Replace routines.
141 <5> 5/10/93 gs Remove Panic from BTInitialize for small logicalEOF. Implement
142 Insert, Set, Replace, and Delete.
143 <4> 3/23/93 gs Finish BTInitialize.
144 <3> 2/8/93 gs Implement BTSearchRecord and BTIterateRecord.
145 <2> 12/8/92 gs Implement Open and Close routines.
146 <1> 11/15/92 gs first checked in
147
148 */
149
150 #include "../headers/BTreesPrivate.h"
151
152 /*
153 * The amount that the BTree header leaf count can be wrong before we assume
154 * it is in an infinite loop.
155 */
156 #define kNumLeafRecSlack 10
157
158 /* BTree accessor routines */
159 extern OSStatus GetBTreeBlock(FileReference vp, UInt32 blockNum, GetBlockOptions options, BlockDescriptor *block);
160 extern OSStatus SetBTreeBlockSize(FileReference vp, ByteCount blockSize, ItemCount minBlockCount);
161 extern OSStatus ExtendBTreeFile(FileReference vp, FSSize minEOF, FSSize maxEOF);
162 extern OSStatus ReleaseBTreeBlock(FileReference vp, BlockDescPtr blockPtr, ReleaseBlockOptions options);
163
164 //////////////////////////////////// Globals ////////////////////////////////////
165
166
167 /////////////////////////// BTree Module Entry Points ///////////////////////////
168
169
170
171 /*-------------------------------------------------------------------------------
172 Routine: BTOpenPath - Open a file for access as a B*Tree.
173
174 Function: Create BTree control block for a file, if necessary. Validates the
175 file to be sure it looks like a BTree file.
176
177
178 Input: filePtr - pointer to file to open as a B-tree
179 keyCompareProc - pointer to client's KeyCompare function
180
181 Result: noErr - success
182 paramErr - required ptr was nil
183 fsBTInvalidFileErr -
184 memFullErr -
185 != noErr - failure
186 -------------------------------------------------------------------------------*/
187
188 OSStatus BTOpenPath(FCB *filePtr, KeyCompareProcPtr keyCompareProc)
189 {
190 OSStatus err;
191 BTreeControlBlockPtr btreePtr;
192 BTHeaderRec *header;
193 NodeRec nodeRec;
194
195 ////////////////////// Preliminary Error Checking ///////////////////////////
196
197 if ( filePtr == nil )
198 {
199 return paramErr;
200 }
201
202 /*
203 * Subsequent opens allow key compare proc to be changed.
204 */
205 if ( filePtr->fcbBTCBPtr != nil && keyCompareProc != nil) {
206 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
207 btreePtr->keyCompareProc = keyCompareProc;
208 return noErr;
209 }
210
211 if ( filePtr->fcbEOF < kMinNodeSize )
212 return fsBTInvalidFileErr;
213
214
215 //////////////////////// Allocate Control Block /////////////////////////////
216
217 btreePtr = (BTreeControlBlock*) NewPtrSysClear( sizeof( BTreeControlBlock ) );
218 if (btreePtr == nil)
219 {
220 Panic ("\pBTOpen: no memory for btreePtr.");
221 return memFullErr;
222 }
223
224 btreePtr->getBlockProc = GetBTreeBlock;
225 btreePtr->releaseBlockProc = ReleaseBTreeBlock;
226 btreePtr->setEndOfForkProc = ExtendBTreeFile;
227 btreePtr->keyCompareProc = keyCompareProc;
228
229 /////////////////////////// Read Header Node ////////////////////////////////
230
231 nodeRec.buffer = nil; // so we can call ReleaseNode
232 btreePtr->fileRefNum = GetFileRefNumFromFCB(filePtr);
233 filePtr->fcbBTCBPtr = (Ptr) btreePtr; // attach btree cb to file
234
235 /* The minimum node size is the physical block size */
236 nodeRec.blockSize = VTOHFS(btreePtr->fileRefNum)->hfs_phys_block_size;
237
238 /* Start with the allocation block size for regular files. */
239 if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID)
240 {
241 nodeRec.blockSize = FCBTOVCB(filePtr)->blockSize;
242 }
243 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
244
245 // it is now safe to call M_ExitOnError (err)
246
247 err = SetBTreeBlockSize (btreePtr->fileRefNum, nodeRec.blockSize, 1);
248 M_ExitOnError (err);
249
250
251 err = GetBTreeBlock(btreePtr->fileRefNum,
252 kHeaderNodeNum,
253 kGetBlock,
254 &nodeRec );
255 if (err != noErr)
256 {
257 nodeRec.buffer = nil;
258 nodeRec.blockHeader = nil;
259 Panic("\pBTOpen: getNodeProc returned error getting header node.");
260 goto ErrorExit;
261 }
262 ++btreePtr->numGetNodes;
263 header = (BTHeaderRec*) ((u_long)nodeRec.buffer + sizeof(BTNodeDescriptor));
264
265
266 ///////////////////////////// verify header /////////////////////////////////
267
268 err = VerifyHeader (filePtr, header);
269 M_ExitOnError (err);
270
271
272 ///////////////////// Initalize fields from header //////////////////////////
273
274 PanicIf ( (FCBTOVCB(filePtr)->vcbSigWord != 0x4244) && (header->nodeSize == 512), "\p BTOpenPath: wrong node size for HFS+ volume!"); // 0x4244 = 'BD'
275
276 btreePtr->treeDepth = header->treeDepth;
277 btreePtr->rootNode = header->rootNode;
278 btreePtr->leafRecords = header->leafRecords;
279 btreePtr->firstLeafNode = header->firstLeafNode;
280 btreePtr->lastLeafNode = header->lastLeafNode;
281 btreePtr->nodeSize = header->nodeSize;
282 btreePtr->maxKeyLength = header->maxKeyLength;
283 btreePtr->totalNodes = header->totalNodes;
284 btreePtr->freeNodes = header->freeNodes;
285 if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID)
286 filePtr->ff_clumpsize = header->clumpSize;
287 btreePtr->btreeType = header->btreeType;
288
289 btreePtr->keyCompareType = header->keyCompareType;
290
291 btreePtr->attributes = header->attributes;
292
293 if ( btreePtr->maxKeyLength > 40 )
294 btreePtr->attributes |= (kBTBigKeysMask + kBTVariableIndexKeysMask); //\80\80 we need a way to save these attributes
295
296 /////////////////////// Initialize dynamic fields ///////////////////////////
297
298 btreePtr->version = kBTreeVersion;
299 btreePtr->flags = 0;
300 btreePtr->writeCount = 1;
301
302 /////////////////////////// Check Header Node ///////////////////////////////
303
304 // set kBadClose attribute bit, and UpdateNode
305
306 /* b-tree node size must be at least as big as the physical block size */
307 if (btreePtr->nodeSize < nodeRec.blockSize)
308 {
309 /*
310 * If this tree has any records or the media is writeable then
311 * we cannot mount using the current physical block size.
312 */
313 if (btreePtr->leafRecords > 0 ||
314 VTOHFS(btreePtr->fileRefNum)->hfs_flags & HFS_WRITEABLE_MEDIA)
315 {
316 err = fsBTBadNodeSize;
317 goto ErrorExit;
318 }
319 }
320
321 // if nodeSize Matches then we don't need to release, just CheckNode
322 if ( btreePtr->nodeSize == nodeRec.blockSize )
323 {
324 err = CheckNode (btreePtr, nodeRec.buffer);
325 if (err)
326 VTOVCB(btreePtr->fileRefNum)->vcbFlags |= kHFS_DamagedVolume;
327 M_ExitOnError (err);
328 }
329 else
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 ); // calls CheckNode...
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, len, 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 err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
1293 M_ExitOnError (err);
1294
1295 // update BTreeControlBlock
1296 btreePtr->treeDepth = 1;
1297 btreePtr->rootNode = insertNodeNum;
1298 btreePtr->firstLeafNode = insertNodeNum;
1299 btreePtr->lastLeafNode = insertNodeNum;
1300
1301 M_BTreeHeaderDirty (btreePtr);
1302
1303 goto Success;
1304
1305 default: goto ErrorExit;
1306 }
1307
1308 if (index > 0)
1309 {
1310 // XXXdbg
1311 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
1312
1313 recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
1314 &iterator->key, KeyLength(btreePtr, &iterator->key),
1315 record->bufferAddress, recordLen);
1316 if (recordFit == true)
1317 {
1318 err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
1319 M_ExitOnError (err);
1320
1321 goto Success;
1322 }
1323 }
1324
1325 /////////////////////// Extend File If Necessary ////////////////////////////
1326
1327 nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
1328 if (nodesNeeded > 0)
1329 {
1330 nodesNeeded += (SInt32)btreePtr->totalNodes;
1331 if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
1332 ++nodesNeeded;
1333
1334 err = ExtendBTree (btreePtr, nodesNeeded);
1335 M_ExitOnError (err);
1336 }
1337
1338 // no need to delete existing record
1339
1340 err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1341 recordLen, &nodeRec, index, 1, kInsertRecord, &insertNodeNum);
1342 M_ExitOnError (err);
1343
1344
1345 //////////////////////////////// Success ////////////////////////////////////
1346
1347 Success:
1348 ++btreePtr->writeCount;
1349 ++btreePtr->leafRecords;
1350 M_BTreeHeaderDirty (btreePtr);
1351
1352 // create hint
1353 iterator->hint.writeCount = btreePtr->writeCount;
1354 iterator->hint.nodeNum = insertNodeNum;
1355 iterator->hint.index = 0; // unused
1356 iterator->hint.reserved1 = 0;
1357 iterator->hint.reserved2 = 0;
1358
1359 return noErr;
1360
1361
1362 ////////////////////////////// Error Exit ///////////////////////////////////
1363
1364 ErrorExit:
1365
1366 (void) ReleaseNode (btreePtr, &nodeRec);
1367
1368 iterator->hint.writeCount = 0;
1369 iterator->hint.nodeNum = 0;
1370 iterator->hint.index = 0;
1371 iterator->hint.reserved1 = 0;
1372 iterator->hint.reserved2 = 0;
1373
1374 if (err == fsBTEmptyErr)
1375 err = fsBTRecordNotFoundErr;
1376
1377 return err;
1378 }
1379
1380
1381 //////////////////////////////// BTReplaceRecord ////////////////////////////////
1382
1383 OSStatus BTReplaceRecord (FCB *filePtr,
1384 BTreeIterator *iterator,
1385 FSBufferDescriptor *record,
1386 UInt16 recordLen )
1387 {
1388 OSStatus err;
1389 BTreeControlBlockPtr btreePtr;
1390 TreePathTable treePathTable;
1391 SInt32 nodesNeeded;
1392 BlockDescriptor nodeRec;
1393 UInt32 insertNodeNum;
1394 UInt16 index;
1395 Boolean recordFit;
1396 Boolean validHint;
1397
1398
1399 ////////////////////////// Priliminary Checks ///////////////////////////////
1400
1401 nodeRec.buffer = nil; // so we can call ReleaseNode
1402 nodeRec.blockHeader = nil;
1403
1404 err = CheckInsertParams (filePtr, iterator, record, recordLen);
1405 if (err != noErr)
1406 return err;
1407
1408 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1409
1410 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
1411
1412 ////////////////////////////// Take A Hint //////////////////////////////////
1413
1414 err = IsItAHint (btreePtr, iterator, &validHint);
1415 M_ExitOnError (err);
1416
1417 if (validHint)
1418 {
1419 insertNodeNum = iterator->hint.nodeNum;
1420
1421 err = GetNode (btreePtr, insertNodeNum, &nodeRec);
1422 if( err == noErr )
1423 {
1424 // XXXdbg
1425 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
1426
1427 err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1428 M_ExitOnError (err);
1429
1430 if (recordFit)
1431 {
1432 err = UpdateNode (btreePtr, &nodeRec, 0, 0);
1433 M_ExitOnError (err);
1434
1435 ++btreePtr->numValidHints;
1436
1437 goto Success;
1438 }
1439 else
1440 {
1441 (void) BTInvalidateHint( iterator );
1442 }
1443
1444 err = ReleaseNode (btreePtr, &nodeRec);
1445 M_ExitOnError (err);
1446 }
1447 else
1448 {
1449 (void) BTInvalidateHint( iterator );
1450 }
1451 }
1452
1453
1454 ////////////////////////////// Get A Clue ///////////////////////////////////
1455
1456 err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1457 M_ExitOnError (err); // record must exit for Replace
1458
1459 // optimization - if simple replace will work then don't extend btree
1460 // \80\80 if we tried this before, and failed because it wouldn't fit then we shouldn't try this again...
1461
1462 // XXXdbg
1463 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
1464
1465 err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
1466 M_ExitOnError (err);
1467
1468 if (recordFit)
1469 {
1470 err = UpdateNode (btreePtr, &nodeRec, 0, 0);
1471 M_ExitOnError (err);
1472
1473 goto Success;
1474 }
1475
1476
1477 //////////////////////////// Make Some Room /////////////////////////////////
1478
1479 nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
1480 if (nodesNeeded > 0)
1481 {
1482 nodesNeeded += (SInt32)btreePtr->totalNodes;
1483 if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
1484 ++nodesNeeded;
1485
1486 err = ExtendBTree (btreePtr, nodesNeeded);
1487 M_ExitOnError (err);
1488 }
1489
1490 // XXXdbg
1491 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
1492
1493 DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record
1494
1495 err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
1496 recordLen, &nodeRec, index, 1, kReplaceRecord, &insertNodeNum);
1497 M_ExitOnError (err);
1498
1499 ++btreePtr->writeCount; /* writeCount changes only if the tree structure changed */
1500
1501 Success:
1502 // create hint
1503 iterator->hint.writeCount = btreePtr->writeCount;
1504 iterator->hint.nodeNum = insertNodeNum;
1505 iterator->hint.index = 0; // unused
1506 iterator->hint.reserved1 = 0;
1507 iterator->hint.reserved2 = 0;
1508
1509 return noErr;
1510
1511
1512 ////////////////////////////// Error Exit ///////////////////////////////////
1513
1514 ErrorExit:
1515
1516 (void) ReleaseNode (btreePtr, &nodeRec);
1517
1518 iterator->hint.writeCount = 0;
1519 iterator->hint.nodeNum = 0;
1520 iterator->hint.index = 0;
1521 iterator->hint.reserved1 = 0;
1522 iterator->hint.reserved2 = 0;
1523
1524 return err;
1525 }
1526
1527
1528
1529 //////////////////////////////// BTUpdateRecord ////////////////////////////////
1530
1531 OSStatus
1532 BTUpdateRecord(FCB *filePtr, BTreeIterator *iterator,
1533 IterateCallBackProcPtr callBackProc, void * callBackState)
1534 {
1535 OSStatus err;
1536 BTreeControlBlockPtr btreePtr;
1537 TreePathTable treePathTable;
1538 BlockDescriptor nodeRec;
1539 RecordPtr recordPtr;
1540 BTreeKeyPtr keyPtr;
1541 UInt32 insertNodeNum;
1542 UInt16 recordLen;
1543 UInt16 index;
1544 Boolean validHint;
1545
1546
1547 ////////////////////////// Priliminary Checks ///////////////////////////////
1548
1549 nodeRec.buffer = nil; // so we can call ReleaseNode
1550 nodeRec.blockHeader = nil;
1551
1552 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1553
1554 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
1555
1556 ////////////////////////////// Take A Hint //////////////////////////////////
1557
1558 err = IsItAHint (btreePtr, iterator, &validHint);
1559 M_ExitOnError (err);
1560
1561 if (validHint)
1562 {
1563 insertNodeNum = iterator->hint.nodeNum;
1564
1565 err = GetNode (btreePtr, insertNodeNum, &nodeRec);
1566 if (err == noErr)
1567 {
1568 if (((NodeDescPtr)nodeRec.buffer)->kind == kBTLeafNode &&
1569 SearchNode (btreePtr, nodeRec.buffer, &iterator->key, &index))
1570 {
1571 err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
1572 M_ExitOnError (err);
1573
1574 // XXXdbg
1575 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
1576
1577 err = callBackProc(keyPtr, recordPtr, recordLen, callBackState);
1578 M_ExitOnError (err);
1579
1580 err = UpdateNode (btreePtr, &nodeRec, 0, 0);
1581 M_ExitOnError (err);
1582
1583 ++btreePtr->numValidHints;
1584
1585 goto Success;
1586 }
1587 else
1588 {
1589 (void) BTInvalidateHint( iterator );
1590 }
1591
1592 err = ReleaseNode (btreePtr, &nodeRec);
1593 M_ExitOnError (err);
1594 }
1595 else
1596 {
1597 (void) BTInvalidateHint( iterator );
1598 }
1599 }
1600
1601 ////////////////////////////// Get A Clue ///////////////////////////////////
1602
1603 err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
1604 M_ExitOnError (err);
1605
1606 err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
1607 M_ExitOnError (err);
1608
1609 // XXXdbg
1610 ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
1611
1612 err = callBackProc(keyPtr, recordPtr, recordLen, callBackState);
1613 M_ExitOnError (err);
1614
1615 err = UpdateNode (btreePtr, &nodeRec, 0, 0);
1616 M_ExitOnError (err);
1617
1618 Success:
1619 // create hint
1620 iterator->hint.writeCount = btreePtr->writeCount;
1621 iterator->hint.nodeNum = insertNodeNum;
1622 iterator->hint.index = 0;
1623 iterator->hint.reserved1 = 0;
1624 iterator->hint.reserved2 = 0;
1625 return noErr;
1626
1627 ////////////////////////////// Error Exit ///////////////////////////////////
1628
1629 ErrorExit:
1630
1631 (void) ReleaseNode (btreePtr, &nodeRec);
1632
1633 iterator->hint.writeCount = 0;
1634 iterator->hint.nodeNum = 0;
1635 iterator->hint.index = 0;
1636 iterator->hint.reserved1 = 0;
1637 iterator->hint.reserved2 = 0;
1638 return err;
1639 }
1640
1641
1642
1643 //////////////////////////////// BTDeleteRecord /////////////////////////////////
1644
1645 OSStatus BTDeleteRecord (FCB *filePtr,
1646 BTreeIterator *iterator )
1647 {
1648 OSStatus err;
1649 BTreeControlBlockPtr btreePtr;
1650 TreePathTable treePathTable;
1651 BlockDescriptor nodeRec;
1652 SInt32 nodesNeeded;
1653 UInt32 nodeNum;
1654 UInt16 index;
1655
1656
1657 ////////////////////////// Priliminary Checks ///////////////////////////////
1658
1659 nodeRec.buffer = nil; // so we can call ReleaseNode
1660 nodeRec.blockHeader = nil;
1661
1662 M_ReturnErrorIf (filePtr == nil, paramErr);
1663 M_ReturnErrorIf (iterator == nil, paramErr);
1664
1665 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1666 if (btreePtr == nil)
1667 {
1668 err = fsBTInvalidFileErr;
1669 goto ErrorExit;
1670 }
1671
1672 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
1673
1674
1675 /////////////////////////////// Find Key ////////////////////////////////////
1676
1677 //\80\80 check hint for simple delete case (index > 0, numRecords > 2)
1678
1679 err = SearchTree (btreePtr, &iterator->key, treePathTable, &nodeNum, &nodeRec, &index);
1680 M_ExitOnError (err); // record must exit for Delete
1681
1682
1683 /////////////////////// Extend File If Necessary ////////////////////////////
1684
1685 nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
1686 if ((btreePtr->attributes & kBTVariableIndexKeysMask) && (nodesNeeded > 0))
1687 {
1688 nodesNeeded += (SInt32)btreePtr->totalNodes;
1689 if (nodesNeeded > CalcMapBits (btreePtr))
1690 ++nodesNeeded;
1691
1692 err = ExtendBTree (btreePtr, nodesNeeded);
1693 M_ExitOnError (err);
1694 }
1695
1696 ///////////////////////////// Delete Record /////////////////////////////////
1697
1698 err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1);
1699 M_ExitOnError (err);
1700
1701 ++btreePtr->writeCount;
1702 --btreePtr->leafRecords;
1703 M_BTreeHeaderDirty (btreePtr);
1704
1705 iterator->hint.nodeNum = 0;
1706
1707 return noErr;
1708
1709 ////////////////////////////// Error Exit ///////////////////////////////////
1710
1711 ErrorExit:
1712 (void) ReleaseNode (btreePtr, &nodeRec);
1713
1714 return err;
1715 }
1716
1717
1718
1719 OSStatus BTGetInformation (FCB *filePtr,
1720 UInt16 version,
1721 BTreeInfoRec *info )
1722 {
1723 #pragma unused (version)
1724
1725 BTreeControlBlockPtr btreePtr;
1726
1727
1728 M_ReturnErrorIf (filePtr == nil, paramErr);
1729
1730 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1731
1732 /*
1733 * XXX SER
1734 * This should not require the whole tree to be locked, just maybe the BTreeControlBlockPtr
1735 *
1736 * REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
1737 */
1738
1739 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1740 M_ReturnErrorIf (info == nil, paramErr);
1741
1742 //\80\80 check version?
1743
1744 info->nodeSize = btreePtr->nodeSize;
1745 info->maxKeyLength = btreePtr->maxKeyLength;
1746 info->treeDepth = btreePtr->treeDepth;
1747 info->numRecords = btreePtr->leafRecords;
1748 info->numNodes = btreePtr->totalNodes;
1749 info->numFreeNodes = btreePtr->freeNodes;
1750 info->lastfsync = btreePtr->lastfsync;
1751 info->keyCompareType = btreePtr->keyCompareType;
1752 return noErr;
1753 }
1754
1755 // XXXdbg
1756 __private_extern__
1757 OSStatus
1758 BTIsDirty(FCB *filePtr)
1759 {
1760 BTreeControlBlockPtr btreePtr;
1761
1762 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1763 return TreeIsDirty(btreePtr);
1764 }
1765
1766 /*-------------------------------------------------------------------------------
1767 Routine: BTFlushPath - Flush BTreeControlBlock to Header Node.
1768
1769 Function: Brief_description_of_the_function_and_any_side_effects
1770
1771
1772 Input: pathPtr - pointer to path control block for B*Tree file to flush
1773
1774 Output: none
1775
1776 Result: noErr - success
1777 != noErr - failure
1778 -------------------------------------------------------------------------------*/
1779
1780 OSStatus BTFlushPath (FCB *filePtr)
1781 {
1782 OSStatus err;
1783 BTreeControlBlockPtr btreePtr;
1784
1785
1786 M_ReturnErrorIf (filePtr == nil, paramErr);
1787
1788 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1789
1790 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1791
1792 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
1793
1794 err = UpdateHeader (btreePtr, false);
1795
1796 return err;
1797 }
1798
1799
1800 /*-------------------------------------------------------------------------------
1801 Routine: BTReload - Reload B-tree Header Data.
1802
1803 Function: Reload B-tree header data from disk. This is called after fsck
1804 has made repairs to the root filesystem. The filesystem is
1805 mounted read-only when BTReload is caled.
1806
1807
1808 Input: filePtr - the B*Tree file that needs its header updated
1809
1810 Output: none
1811
1812 Result: noErr - success
1813 != noErr - failure
1814 -------------------------------------------------------------------------------*/
1815
1816 OSStatus
1817 BTReloadData(FCB *filePtr)
1818 {
1819 OSStatus err;
1820 BTreeControlBlockPtr btreePtr;
1821 BlockDescriptor node;
1822 BTHeaderRec *header;
1823
1824
1825 node.buffer = nil;
1826 node.blockHeader = nil;
1827
1828 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1829 if (btreePtr == nil)
1830 return (fsBTInvalidFileErr);
1831
1832 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
1833
1834 err = GetNode(btreePtr, kHeaderNodeNum, &node);
1835 if (err != noErr)
1836 return (err);
1837
1838 header = (BTHeaderRec*)((char *)node.buffer + sizeof(BTNodeDescriptor));
1839 if ((err = VerifyHeader (filePtr, header)) == 0) {
1840 btreePtr->treeDepth = header->treeDepth;
1841 btreePtr->rootNode = header->rootNode;
1842 btreePtr->leafRecords = header->leafRecords;
1843 btreePtr->firstLeafNode = header->firstLeafNode;
1844 btreePtr->lastLeafNode = header->lastLeafNode;
1845 btreePtr->maxKeyLength = header->maxKeyLength;
1846 btreePtr->totalNodes = header->totalNodes;
1847 btreePtr->freeNodes = header->freeNodes;
1848 btreePtr->btreeType = header->btreeType;
1849
1850 btreePtr->flags &= (~kBTHeaderDirty);
1851 }
1852
1853 (void) ReleaseNode(btreePtr, &node);
1854
1855 return err;
1856 }
1857
1858
1859 /*-------------------------------------------------------------------------------
1860 Routine: BTInvalidateHint - Invalidates the hint within a BTreeInterator.
1861
1862 Function: Invalidates the hint within a BTreeInterator.
1863
1864
1865 Input: iterator - pointer to BTreeIterator
1866
1867 Output: iterator - iterator with the hint.nodeNum cleared
1868
1869 Result: noErr - success
1870 paramErr - iterator == nil
1871 -------------------------------------------------------------------------------*/
1872
1873
1874 OSStatus BTInvalidateHint (BTreeIterator *iterator )
1875 {
1876 if (iterator == nil)
1877 return paramErr;
1878
1879 iterator->hint.nodeNum = 0;
1880
1881 return noErr;
1882 }
1883
1884
1885
1886
1887 /*-------------------------------------------------------------------------------
1888 Routine: BTGetLastSync
1889
1890 Function: Returns the last time that this btree was flushed, does not include header.
1891
1892 Input: filePtr - pointer file control block
1893
1894 Output: lastfsync - time in seconds of last update
1895
1896 Result: noErr - success
1897 paramErr - iterator == nil
1898 -------------------------------------------------------------------------------*/
1899
1900
1901 OSStatus BTGetLastSync (FCB *filePtr,
1902 UInt32 *lastsync)
1903 {
1904 BTreeControlBlockPtr btreePtr;
1905
1906
1907 M_ReturnErrorIf (filePtr == nil, paramErr);
1908
1909 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1910
1911 /* Maybe instead of requiring a lock..an atomic set might be more appropriate */
1912 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
1913
1914 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1915 M_ReturnErrorIf (lastsync == nil, paramErr);
1916
1917 *lastsync = btreePtr->lastfsync;
1918
1919 return noErr;
1920 }
1921
1922
1923
1924
1925 /*-------------------------------------------------------------------------------
1926 Routine: BTSetLastSync
1927
1928 Function: Sets the last time that this btree was flushed, does not include header.
1929
1930
1931 Input: fcb - pointer file control block
1932
1933 Output: lastfsync - time in seconds of last update
1934
1935 Result: noErr - success
1936 paramErr - iterator == nil
1937 -------------------------------------------------------------------------------*/
1938
1939
1940 OSStatus BTSetLastSync (FCB *filePtr,
1941 UInt32 lastsync)
1942 {
1943 BTreeControlBlockPtr btreePtr;
1944
1945
1946 M_ReturnErrorIf (filePtr == nil, paramErr);
1947
1948 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1949
1950 /* Maybe instead of requiring a lock..an atomic set might be more appropriate */
1951 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
1952
1953 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1954 M_ReturnErrorIf (lastsync == nil, paramErr);
1955
1956 btreePtr->lastfsync = lastsync;
1957
1958 return noErr;
1959 }
1960
1961
1962 __private_extern__
1963 OSStatus BTHasContiguousNodes (FCB *filePtr)
1964 {
1965 BTreeControlBlockPtr btreePtr;
1966
1967
1968 M_ReturnErrorIf (filePtr == nil, paramErr);
1969
1970 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
1971
1972 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
1973
1974 M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
1975
1976 return NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize);
1977 }
1978
1979
1980 /*-------------------------------------------------------------------------------
1981 Routine: BTGetUserData
1982
1983 Function: Read the user data area of the b-tree header node.
1984
1985 -------------------------------------------------------------------------------*/
1986 __private_extern__
1987 OSStatus
1988 BTGetUserData(FCB *filePtr, void * dataPtr, int dataSize)
1989 {
1990 BTreeControlBlockPtr btreePtr;
1991 BlockDescriptor node;
1992 char * offset;
1993 OSStatus err;
1994
1995 if (dataSize > kBTreeHeaderUserBytes)
1996 return (EINVAL);
1997 node.buffer = nil;
1998 node.blockHeader = nil;
1999
2000 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
2001 if (btreePtr == nil)
2002 return (fsBTInvalidFileErr);
2003
2004 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
2005
2006 err = GetNode(btreePtr, kHeaderNodeNum, &node);
2007 if (err)
2008 return (err);
2009
2010 offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec);
2011 bcopy(offset, dataPtr, dataSize);
2012
2013 (void) ReleaseNode(btreePtr, &node);
2014
2015 return (0);
2016 }
2017
2018
2019 /*-------------------------------------------------------------------------------
2020 Routine: BTSetUserData
2021
2022 Function: Write the user data area of the b-tree header node.
2023 -------------------------------------------------------------------------------*/
2024 __private_extern__
2025 OSStatus
2026 BTSetUserData(FCB *filePtr, void * dataPtr, int dataSize)
2027 {
2028 BTreeControlBlockPtr btreePtr;
2029 BlockDescriptor node;
2030 char * offset;
2031 OSStatus err;
2032
2033 if (dataSize > kBTreeHeaderUserBytes)
2034 return (EINVAL);
2035 node.buffer = nil;
2036 node.blockHeader = nil;
2037
2038 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
2039 if (btreePtr == nil)
2040 return (fsBTInvalidFileErr);
2041
2042 REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
2043
2044 err = GetNode(btreePtr, kHeaderNodeNum, &node);
2045 if (err)
2046 return (err);
2047
2048 ModifyBlockStart(btreePtr->fileRefNum, &node);
2049
2050 offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec);
2051 bcopy(dataPtr, offset, dataSize);
2052
2053 err = UpdateNode (btreePtr, &node, 0, 0);
2054
2055 return (err);
2056 }
2057
mirror of XNU