← Back to branch summary

~ubuntu-branches/ubuntu/maverick/hfsprogs/maverick

« back to all changes in this revision

Viewing changes to .pc/10-linux_specific_code.patch/fsck_hfs.tproj/dfalib/BTree.c

  • Committer: Bazaar Package Importer
  • Author(s): Rogério Brito
  • Date: 2010-01-31 07:01:54 UTC
  • mfrom: (5.1.5 sid)
  • Revision ID: james.westby@ubuntu.com-20100131070154-tn5dfg5fjiejd6hn
Tags: 332.25-8
http://bugs.debian.org/566916
* Use a FTBFS bug revealed by the kfreebsd-* ports.
  This was reported by Cyril Brulebois, and patched by: Petr Salinger.
  Closes: #566916
* Remove b-dep on kfreebsd-kernel-headers, as it is build-essential.

Show diffs side-by-side

added added

removed removed

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