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