bsd/hfs/hfscommon/headers/BTreeScanner.h

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