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