Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

keydef.h

Go to the documentation of this file.
00001 #if !defined(KEYDEF_H)
00002 #define KEYDEF_H
00003 
00004 /*                                                               */
00005 /* Copyright 1984,1985,1986,1988,1989,1990,2003,2004,2005,       */
00006 /*   2006, 2007 by Howard Turtle                                 */
00007 /*                                                               */
00008 
00009 #include <math.h>
00010 #include "integer_types.h"
00011 
00012 /*#ifdef WIN32
00013 typedef unsigned short     UINT16;
00014 typedef unsigned int       UINT32;
00015 typedef unsigned __int64   UINT64;
00016 #define UINT64_format "%llu"
00017 #define UINT64_C(c)   c ## ULL
00018 #define PATH_SEPARATOR '\\'
00019 typedef struct F_HANDLE F_HANDLE;
00020 #else
00021 #include <inttypes.h>
00022 typedef uint16_t           UINT16;
00023 typedef uint32_t           UINT32;
00024 typedef uint64_t           UINT64;
00025 #define UINT64_format "%" PRIu64
00026 #define PATH_SEPARATOR '/'
00027 #define F_HANDLE FILE
00028 #endif
00029 */
00030 
00031 #define bits(i) ( (int) (log((double)i-1)/log(2.0)) + 1 )
00032 #define compressed_bits_per_byte 7
00033 #define compressed_lc(bits) ( (bits-1) / compressed_bits_per_byte + 1 )
00034 
00035 #define eqn_pntr(p1,p2) ((p1.block==p2.block) && (p1.segment==p2.segment))
00036 #define lt_pntr(p1,p2) ((p1.segment<p2.segment) || ((p1.segment==p2.segment) && (p1.block<p2.block)))
00037 #define null_pntr(p1) ((p1.segment==max_segment) && (p1.block==0))
00038 #define mvc(t1,sc1,t2,sc2,lc) memmove((unsigned char *)t2+sc2,(unsigned char *)t1+sc1,(size_t)lc)
00039 
00040 #define keyf                   32472 /* marker for fcb */
00041 #define current_version            7 /* version of keyed file software */
00042 #define current_sub_version        0
00043 #define maxkey_lc                512 /* maximum key length */
00044 #define max_prefix_lc            127 /* max index block prefix */
00045 #define level_zero                 0 /* level of index leaves */
00046 #define level_one                  1 /* level immediately above leaves */
00047 #define min_data_in_index_lc       6 /* records <= this go in index block */
00048 #define max_data_in_index_lc     128 /* longest record that can go in index block */
00049 #define seq_threshold             20
00050 #define min_buffer_cnt             8 /* default number of buffers allocated */
00051 /*#define max_buffer_cnt         32768*/ /* max buffers allowed */
00052 #define buf_hash_load_factor       3 /* hash table is>=this times buffers alloc,*/
00053 #define max_level                 32 /* number of index block levels */
00054 #define file_lc_bits              31 /* <64, max_file_lc = 2**file_lc_bits - 1 */
00055 #define max_segment              127 /* max number of file segments */
00056 #define max_files                 10 /* max number of open files */
00057 #define max_filename_lc          128 /* max length of a file name */
00058 #define max_extension_lc          40 /* max length of file name extension */
00059 /*#define v6_block_lc             4096*/
00060 #define block_lc                4096
00061 #define rec_allocation_unit        8 /* data recs allocated as multiple of this */
00062 #define block_allocation_unit     16 /* # index (or freespace) blocks to allocate */
00063 #define max_allocation_depth       4
00064 #define user_ix                    0
00065 #define free_rec_ix                1
00066 #define free_lc_ix                 2
00067 #define max_index                  3
00068 #define cmp_less                   0
00069 #define cmp_equal                  1
00070 #define cmp_greater                2
00071 
00072 #define UINT32_lc      (unsigned)sizeof(UINT32)
00073 #define freespace_lc_key_lc 14       /* length of a freespace lc key */
00074 #define freespace_rec_key_lc 10      /* length of a freespace rec key */
00075 
00076 enum comparison {less,equal,greater};
00077 
00078 struct key {
00079   unsigned char
00080     text[maxkey_lc];
00081   UINT16
00082     lc;
00083 };
00084 
00085 /* leveln_pntrs point to index blocks and are the pointers stored  */
00086 /*   in index blocks above level0.  They are always compressed     */
00087 /*   when stored in index blocks; segment is usually small (less   */
00088 /*   that max_segment), block is a block number (not a file       */
00089 /*   offset).  leveln_lc is the size of the pointer on disk.       */
00090 
00091 struct leveln_pntr{
00092   UINT16
00093     segment;                    /* in range 0..max_segment  */
00094   UINT64
00095     block;
00096 };
00097 #define leveln_lc (sizeof(UINT16)+sizeof(UINT64))
00098 #define compressed_block_lc ( compressed_lc( file_lc_bits - bits(block_lc) ) )
00099 #define compressed_leveln_lc ( compressed_lc(bits(max_segment)) + compressed_block_lc )
00100 
00101 /* level0_pntrs point to (or contain) data records and are only   */
00102 /*   found in level0 blocks.  Segment is the file segment in      */
00103 /*   which the record lies (short).  sc is the byte offset in the */
00104 /*   file at which the record starts, lc is the length of the     */
00105 /*   record.  If the record will fit in sizeof(UINT64) then it is */
00106 /*   stored in sc rather than on disk.                            */
00107 
00108 /* Starting with version 7, level0 pntrs are stored differently.  */
00109 /*   lc is compressed first.  If lc<=f->data_in_index_lc then lc  */
00110 /*   is followed by the actual data associated with the key       */
00111 /*   (uncompressed).  If lc>f->data_in_index_lc then lc is        */
00112 /*   followed by segment and sc that define the disk offset to    */
00113 /*   the data stored on disk.                                     */
00114 
00115 struct disk_offset {
00116   UINT16
00117     segment;
00118   UINT64
00119     sc;
00120 };
00121 
00122 typedef union data_or_disk_offset_t {
00123   struct disk_offset    offset;
00124   unsigned char        data[max_data_in_index_lc];
00125 } data_or_disk_offset;
00126 
00127 struct internal_level0_pntr {
00128   UINT16
00129     segment;
00130   UINT32
00131     lc;
00132   UINT64
00133     sc;
00134   unsigned char
00135     data_rec[max_data_in_index_lc];
00136 };
00137 typedef struct internal_level0_pntr level0_pntr;
00138 
00139 struct external_level0_pntr {
00140   UINT16
00141     segment;
00142   UINT32
00143     lc;
00144   UINT64
00145     sc;
00146 };
00147 typedef struct internal_level0_pntr keyfile_pointer; /* external name for Chiliad use */
00148 
00149 
00150 #define ix_block_header_lc (2*sizeof(UINT16)+ 4 +2*leveln_lc)
00151 #define key_ptrs_per_block ((block_lc - ix_block_header_lc) / sizeof(UINT16))
00152 #define keyspace_lc (sizeof(UINT16)*key_ptrs_per_block)
00153 
00154 struct ix_block {                  /* block is the disk resident image of */
00155   UINT16                         /*   an index block */
00156     keys_in_block,
00157     chars_in_use;               /* chars in key/pointer pool, does not */
00158                                 /*   include length of key_ptr_t entries */
00159   unsigned char
00160     index_type,                 /* user, free_lc, or free_rec */
00161     prefix_lc,                  /* lc of prefix removed from all keys in block */
00162     unused,
00163     level;                      /* level of block */
00164   struct leveln_pntr
00165     next,prev;
00166   UINT16                        /* key_ptrs are inserted from 0, keys and */
00167     keys[key_ptrs_per_block];   /*  file pointers overlay the top end */
00168 };
00169 typedef struct ix_block block_type_t;
00170 #define ix_block_lc sizeof(block_type_t)
00171 
00172 
00173 /* Free space management.  Available space is recorded in two separate */
00174 /*   indexes.  The first (free_rec_ix) records each space in address   */
00175 /*   order using a binary key of segment/sc and lc as the record,  The */
00176 /*   second (free_lc_ix) records each space in length order using a    */
00177 /*   key of lc/segment/sc.  To allocate a record the lc list is        */
00178 /*   searched with a key of lc/0/0 then next_rec is used to find a     */
00179 /*   space of lc or longer (if it exists).  To deallocate, the rec     */
00180 /*   list searched and any contiguous entries are combined.            */
00181 
00182 typedef union level0orn_pntr {
00183   level0_pntr            p0;
00184   struct leveln_pntr     pn;
00185 } levelx_pntr;
00186 
00187 /* Buffer handling.  Buffers contain the disk image of an index or    */
00188 /*   freespace block */
00189 /*   together with additional information.  A hashing technique is    */
00190 /*   used to find a buffer that holds a given block.  A hash table is */
00191 /*   allocated as the last buffers in the fcb of roughly three times  */
00192 /*   the number of buffers allocated.  buf_hash_table[k] contains the */
00193 /*   index of the first buffer containing a block whose hash value is */
00194 /*   k.  If there are multiple buffers containing blocks with hash    */
00195 /*   value k then they are linked using hash_next.                    */
00196 
00197 struct buffer_struct {            /* buffer is the memory resident image of */
00198                                 /* a disk block */
00199   unsigned char
00200     lock_cnt,
00201     modified,
00202     notused;
00203   int
00204     older,                      /* index to prev element in LRU list */
00205     younger,                    /* index to next element in LRU list */
00206     hash_next,
00207     search_cnt;
00208   struct leveln_pntr
00209     contents;                   /* block in buffer, nulln_ptr if empty */
00210   block_type_t
00211     b;
00212 };
00213 typedef struct buffer_struct buffer_t;
00214 #define buffer_lc sizeof(buffer_t)
00215 #define hash_entries_per_buf (buffer_lc / sizeof(int))
00216 
00217 struct buffer_pool_struct {
00218   int
00219     buffers_allocated,          /* number of buffers allocated */
00220     buffers_in_use,             /* buffers actually used */
00221     *buf_hash_table,            /* pointer to base of buffer hash table */
00222     buf_hash_entries;           /* size of buf_hash_table              */
00223   buffer_t
00224     buffer[min_buffer_cnt];    /* should be at end of fcb so we can extend */
00225 };
00226 typedef struct buffer_pool_struct buffer_pool_t;
00227 #define min_buffer_pool_lc (sizeof(buffer_pool_t) + min_buffer_cnt*sizeof(buffer_t))
00228 
00229 
00230 /* File information block.  The following information is stored at the */
00231 /*   start of segment 0 for all keyed files.  The sizes are            */
00232 /*   fixed for all keyed files but the information is kept in the fcb  */
00233 /*   in whatever form fits the architecture at hand.  Note that this   */
00234 /*   struct is never actually used -- it's here to document the        */
00235 /*   structure of the fib.  fib_lc_on_disk is the length of the fib on disk -- */
00236 /*   it doesn't include alignment padding inserted by a compiler.      */
00237 
00238 struct file_information_block {
00239   UINT32
00240     error_code,
00241     version,                    /* version of keyed file manager */
00242     sub_version,
00243     segment_cnt,                /* number of segments in use     */
00244     primary_level[max_index],              /* level of primary index block */
00245     marker,
00246     file_ok;
00247   struct leveln_pntr
00248     first_free_block[max_level][max_index],/* points to start of empty block chain */
00249     first_at_level[max_level][max_index],  /* block containing lowest key at level */
00250     last_pntr[max_level][max_index];       /* last pointer at each level */
00251   UINT64
00252     max_file_lc,
00253     segment_length[max_segment];/* length in bytes of each segment     */
00254   UINT32
00255     data_in_index_lc;
00256 
00257 };
00258 #define fib_lc_on_disk ((7+max_index)*sizeof(UINT32)+(3*max_level*max_index)*leveln_lc+(max_segment+1)*sizeof(UINT64))
00259 
00260 
00261 /* Segment handling.  A keyed file consist of one or more component files */
00262 /*    called segments.  Segment 0 contains the file information block and */
00263 /*    is alway present.  Additional segments are created as needed with   */
00264 /*    a suffix of "$n" appended to the base file name where n is the      */
00265 /*    segment number.  The file information block contains a segment_cnt  */
00266 /*    and a list of each segment_length.  After open the fcb contains a   */
00267 /*    list of the file number on which each segment is open (max_files    */
00268 /*    implies not open) in segment_ix                                     */
00269 
00270 /* File handling.  Up to max_files files may be open at one time.         */
00271 /*   open_file_cnt is the number of files actually open, open_file[] is   */
00272 /*   a list of file_indexes in use, file_age[] is the age of each open    */
00273 /*   file, open_segment[] is the segment to which the file is open        */
00274 
00275 struct fcb {
00276 
00277   UINT32
00278     error_code,
00279     version,                    /* version of keyed file manager */
00280     sub_version,
00281     segment_cnt,                /* number of segments in use     */
00282     primary_level[max_index],              /* level of primary index block */
00283     marker,
00284     file_ok;
00285   struct leveln_pntr
00286     first_free_block[max_level][max_index],/* points to start of empty block chain */
00287     first_at_level[max_level][max_index],  /* block containing lowest key at level */
00288     last_pntr[max_level][max_index];       /* last pointer at each level */
00289   UINT64
00290     max_file_lc,                 /* max file lc for file system (2**file_lc_bits - 1)*/
00291     segment_length[max_segment];/* length in bytes of each segment     */
00292   UINT32
00293     data_in_index_lc;            /* data recs <= this go in index */
00294 
00295     /* end of fib information, temporary information follows */
00296 
00297   char
00298     file_name[max_filename_lc],
00299     file_extension[max_extension_lc],
00300     *search_block_caller;       /* pointer to name of caller for debug */
00301   unsigned char
00302     byte_swapping_required,     /* true means swap bytes on I/O */
00303     trace,                      /* true means trace execution */
00304     trace_freespace,            /* true means trace space management */
00305     read_only;                  /* true means file is read only */
00306   int
00307     open_file_cnt,              /* number of files actually open */
00308     open_segment[max_files],    /* segment to which each file is open */
00309     file_age[max_files],        /* age of each open file  */
00310     oldest_buffer,              /* first buffer in LRU buffer list */
00311     youngest_buffer,            /* last buffer in LRU buffer list */
00312     block_shift;                /* log2(block_lc) */
00313   F_HANDLE
00314     *log_file,
00315     *open_file[max_files];      /* pointers to open files */
00316 
00317   int
00318     segment_ix[max_segment],   /* index into open_file[] if segment open */
00319     position_ix[max_index],                /* posn. in level0 blk of last retrieval */
00320     seq_cnt[max_index],
00321     current_age;                /* age of file pool (0..maxint)*/
00322   struct leveln_pntr
00323     mru_at_level[max_level][max_index],    /* most recently used block at each level*/
00324     position[max_index];                   /* level0 block of last retrieval */
00325 
00326   buffer_pool_t
00327     buffer_pool;     /* should be at end of fcb so we can extend */
00328   /*  buffer_t
00329       buffer[min_buffer_cnt];*/
00330 };
00331 #define min_fcb_lc sizeof(struct fcb)
00332 
00333 #endif

Generated on Tue Jun 15 11:02:54 2010 for Lemur by doxygen 1.3.4