bsd/hfs/hfscommon/headers/BTreeScanner.h

   1 /*
   2  * Copyright (c) 1996-2004 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_OSREFERENCE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License.  The rights granted to you under the
  10  * License may not be used to create, or enable the creation or
  11  * redistribution of, unlawful or unlicensed copies of an Apple operating
  12  * system, or to circumvent, violate, or enable the circumvention or
  13  * violation of, any terms of an Apple operating system software license
  14  * agreement.
  15  *
  16  * Please obtain a copy of the License at
  17  * http://www.opensource.apple.com/apsl/ and read it before using this
  18  * file.
  19  *
  20  * The Original Code and all software distributed under the License are
  21  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  22  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  23  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  24  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  25  * Please see the License for the specific language governing rights and
  26  * limitations under the License.
  27  *
  28  * @APPLE_LICENSE_OSREFERENCE_HEADER_END@
  29  *
  30  *      @(#)BTreeScanner.h
  31  */
  32
  33 #ifndef _BTREESCANNER_H_
  34 #define _BTREESCANNER_H_
  35
  36 #include <sys/appleapiopts.h>
  37
  38 #ifdef KERNEL
  39 #ifdef __APPLE_API_PRIVATE
  40 #include <sys/time.h>
  41
  42 #include "FileMgrInternal.h"
  43 #include "BTreesPrivate.h"
  44
  45 // amount of time we are allowed to process a catalog search (in µ secs)
  46 // NOTE - code assumes kMaxMicroSecsInKernel is less than 1,000,000
  47 enum { kMaxMicroSecsInKernel = (1000 * 100) };  // 1 tenth of a second
  48
  49 // btree node scanner buffer size.  at 32K we get 8 nodes.  this is the size used
  50 // in Mac OS 9
  51 enum { kCatSearchBufferSize = (32 * 1024) };
  52
  53
  54 /*
  55  * ============ W A R N I N G ! ============
  56  * DO NOT INCREASE THE SIZE OF THIS STRUCT!
  57  * It must be less than or equal to the size of
  58  * the opaque searchstate struct (in sys/attr.h).
  59  */
  60 /* Private description used in hfs_search */
  61 struct CatPosition
  62 {
  63   u_int32_t             writeCount;     /* The BTree's write count (to see if the catalog writeCount */
  64                                 /* changed since the last search).  If 0, the rest */
  65                                 /* of the record is invalid, start from beginning. */
  66   u_int32_t     nextNode;       /* node number to resume search */
  67   u_int32_t     nextRecord;     /* record number to resume search */
  68   u_int32_t     recordsFound;   /* number of leaf records seen so far */
  69 };
  70 typedef struct CatPosition              CatPosition;
  71
  72
  73 /*
  74         BTScanState - This structure is used to keep track of the current state
  75         of a BTree scan.  It contains both the dynamic state information (like
  76         the current node number and record number) and information that is static
  77         for the duration of a scan (such as buffer pointers).
  78
  79         NOTE: recordNum may equal or exceed the number of records in the node
  80         number nodeNum.  If so, then the next attempt to get a record will move
  81         to a new node number.
  82 */
  83 struct BTScanState
  84 {
  85         //      The following fields are set up once at initialization time.
  86         //      They are not changed during a scan.
  87         u_int32_t                       bufferSize;
  88         struct buf *            bufferPtr;
  89         BTreeControlBlock *     btcb;
  90
  91         //      The following fields are the dynamic state of the current scan.
  92         u_int32_t                       nodeNum;                        // zero is first node
  93         u_int32_t                       recordNum;                      // zero is first record
  94         BTNodeDescriptor *      currentNodePtr;         // points to current node within buffer
  95         u_int32_t                       nodesLeftInBuffer;      // number of valid nodes still in the buffer
  96         u_int32_t                       recordsFound;           // number of leaf records seen so far
  97         struct timeval          startTime;                      // time we started catalog search
  98 };
  99 typedef struct BTScanState BTScanState;
 100
 101
 102 /* *********************** PROTOTYPES *********************** */
 103
 104 int     BTScanInitialize(       const FCB *             btreeFile,
 105                                                 u_int32_t               startingNode,
 106                                                 u_int32_t               startingRecord,
 107                                                 u_int32_t               recordsFound,
 108                                                 u_int32_t               bufferSize,
 109                                                 BTScanState     *       scanState     );
 110
 111 int BTScanNextRecord(   BTScanState *   scanState,
 112                                                 Boolean                 avoidIO,
 113                                                 void * *                key,
 114                                                 void * *                data,
 115                                                 u_int32_t *             dataSize  );
 116
 117 int     BTScanTerminate(        BTScanState *   scanState,
 118                                                 u_int32_t *             startingNode,
 119                                                 u_int32_t *             startingRecord,
 120                                                 u_int32_t *             recordsFound    );
 121
 122 #endif /* __APPLE_API_PRIVATE */
 123 #endif /* KERNEL */
 124 #endif /* !_BTREESCANNER_H_ */