src/gdbmdefs.h

   1 /* gdbmdefs.h - The include file for dbm.  Defines structure and constants. */
   2
   3 /* This file is part of GDBM, the GNU data base manager.
   4    Copyright (C) 1990, 1991, 1993, 2007, 2011 Free Software Foundation,
   5    Inc.
   6
   7    GDBM is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3, or (at your option)
  10    any later version.
  11
  12    GDBM is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GDBM. If not, see <http://www.gnu.org/licenses/>.   */
  19
  20 #include "systems.h"
  21 #include "gdbmconst.h"
  22 #include "gdbm.h"
  23 #define DEFAULT_TEXT_DOMAIN PACKAGE
  24 #include "gettext.h"
  25
  26 #define _(s) gettext (s)
  27 #define N_(s) s
  28
  29 /* The type definitions are next.  */
  30
  31 /* The available file space is stored in an "avail" table.  The one with
  32    most activity is contained in the file header. (See below.)  When that
  33    one filles up, it is split in half and half is pushed on an "avail
  34    stack."  When the active avail table is empty and the "avail stack" is
  35    not empty, the top of the stack is popped into the active avail table. */
  36
  37 /* The following structure is the element of the avaliable table.  */
  38 typedef struct {
  39         int   av_size;          /* The size of the available block. */
  40         off_t  av_adr;          /* The file address of the available block. */
  41       } avail_elem;
  42
  43 /* This is the actual table. The in-memory images of the avail blocks are
  44    allocated by malloc using a calculated size.  */
  45 typedef struct {
  46         int   size;             /* The number of avail elements in the table.*/
  47         int   count;            /* The number of entries in the table. */
  48         off_t next_block;       /* The file address of the next avail block. */
  49         avail_elem av_table[1]; /* The table.  Make it look like an array.  */
  50       } avail_block;
  51
  52 /* The dbm file header keeps track of the current location of the hash
  53    directory and the free space in the file.  */
  54
  55 typedef struct {
  56         int   header_magic;  /* Version of file. */
  57         int   block_size;    /* The optimal i/o blocksize from stat. */
  58         off_t dir;           /* File address of hash directory table. */
  59         int   dir_size;      /* Size in bytes of the table.  */
  60         int   dir_bits;      /* The number of address bits used in the table.*/
  61         int   bucket_size;   /* Size in bytes of a hash bucket struct. */
  62         int   bucket_elems;  /* Number of elements in a hash bucket. */
  63         off_t next_block;    /* The next unallocated block address. */
  64         avail_block avail;   /* This must be last because of the psuedo
  65                                 array in avail.  This avail grows to fill
  66                                 the entire block. */
  67       }  gdbm_file_header;
  68
  69
  70 /* The dbm hash bucket element contains the full 31 bit hash value, the
  71    "pointer" to the key and data (stored together) with their sizes.  It also
  72    has a small part of the actual key value.  It is used to verify the first
  73    part of the key has the correct value without having to read the actual
  74    key. */
  75
  76 typedef struct {
  77         int   hash_value;       /* The complete 31 bit value. */
  78         char  key_start[SMALL]; /* Up to the first SMALL bytes of the key.  */
  79         off_t data_pointer;     /* The file address of the key record. The
  80                                    data record directly follows the key.  */
  81         int   key_size;         /* Size of key data in the file. */
  82         int   data_size;        /* Size of associated data in the file. */
  83       } bucket_element;
  84
  85
  86 /* A bucket is a small hash table.  This one consists of a number of
  87    bucket elements plus some bookkeeping fields.  The number of elements
  88    depends on the optimum blocksize for the storage device and on a
  89    parameter given at file creation time.  This bucket takes one block.
  90    When one of these tables gets full, it is split into two hash buckets.
  91    The contents are split between them by the use of the first few bits
  92    of the 31 bit hash function.  The location in a bucket is the hash
  93    value modulo the size of the bucket.  The in-memory images of the
  94    buckets are allocated by malloc using a calculated size depending of
  95    the file system buffer size.  To speed up write, each bucket will have
  96    BUCKET_AVAIL avail elements with the bucket. */
  97
  98 typedef struct {
  99         int   av_count;            /* The number of bucket_avail entries. */
 100         avail_elem bucket_avail[BUCKET_AVAIL];  /* Distributed avail. */
 101         int   bucket_bits;         /* The number of bits used to get here. */
 102         int   count;               /* The number of element buckets full. */
 103         bucket_element h_table[1]; /* The table.  Make it look like an array.*/
 104       } hash_bucket;
 105
 106 /* We want to keep from reading buckets as much as possible.  The following is
 107    to implement a bucket cache.  When full, buckets will be dropped in a
 108    least recently read from disk order.  */
 109
 110 /* To speed up fetching and "sequential" access, we need to implement a
 111    data cache for key/data pairs read from the file.  To find a key, we
 112    must exactly match the key from the file.  To reduce overhead, the
 113    data will be read at the same time.  Both key and data will be stored
 114    in a data cache.  Each bucket cached will have a one element data
 115    cache.  */
 116
 117 typedef struct {
 118         int   hash_val;
 119         int   data_size;
 120         int   key_size;
 121         char *dptr;
 122         int   elem_loc;
 123       }  data_cache_elem;
 124
 125 typedef struct {
 126         hash_bucket *   ca_bucket;
 127         off_t           ca_adr;
 128         char            ca_changed;   /* Data in the bucket changed. */
 129         data_cache_elem ca_data;
 130       } cache_elem;
 131
 132 /* This final structure contains all main memory based information for
 133    a gdbm file.  This allows multiple gdbm files to be opened at the same
 134    time by one program. */
 135
 136 struct gdbm_file_info {
 137         /* Global variables and pointers to dynamic variables used by gdbm.  */
 138
 139         /* The file name. */
 140         char *name;
 141
 142         /* The reader/writer status. */
 143         unsigned read_write :2;
 144
 145         /* Fast_write is set to 1 if no fsyncs are to be done. */
 146         unsigned fast_write :1;
 147
 148         /* Central_free is set if all free blocks are kept in the header. */
 149         unsigned central_free :1;
 150
 151         /* Coalesce_blocks is set if we should try to merge free blocks. */
 152         unsigned coalesce_blocks :1;
 153
 154         /* Whether or not we should do file locking ourselves. */
 155         unsigned file_locking :1;
 156
 157         /* Whether or not we're allowing mmap() use. */
 158         unsigned memory_mapping :1;
 159
 160         /* Whether the database was open with GDBM_CLOEXEC flag */
 161         unsigned cloexec :1;
 162
 163         /* Type of file locking in use. */
 164         enum { LOCKING_NONE = 0, LOCKING_FLOCK, LOCKING_LOCKF,
 165                 LOCKING_FCNTL } lock_type;
 166
 167         /* The fatal error handling routine. */
 168         void (*fatal_err) (const char *);
 169
 170         /* The gdbm file descriptor which is set in gdbm_open.  */
 171         int desc;
 172
 173         /* The file header holds information about the database. */
 174         gdbm_file_header *header;
 175
 176         /* The hash table directory from extendible hashing.  See Fagin et al,
 177            ACM Trans on Database Systems, Vol 4, No 3. Sept 1979, 315-344 */
 178         off_t *dir;
 179
 180         /* The bucket cache. */
 181         cache_elem *bucket_cache;
 182         size_t cache_size;
 183         int last_read;
 184
 185         /* Points to the current hash bucket in the cache. */
 186         hash_bucket *bucket;
 187
 188         /* The directory entry used to get the current hash bucket. */
 189         int bucket_dir;
 190
 191         /* Pointer to the current bucket's cache entry. */
 192         cache_elem *cache_entry;
 193
 194         /* Bookkeeping of things that need to be written back at the
 195            end of an update. */
 196         unsigned header_changed :1;
 197         unsigned directory_changed :1;
 198         unsigned bucket_changed :1;
 199         unsigned second_changed :1;
 200
 201         /* Mmap info */
 202         size_t mapped_size_max;/* Max. allowed value for mapped_size */
 203         void  *mapped_region;  /* Mapped region */
 204         size_t mapped_size;    /* Size of the region */
 205         off_t  mapped_pos;     /* Current offset in the region */
 206         off_t  mapped_off;     /* Position in the file where the region
 207                                   begins */
 208       };
 209
 210 /* Execute CODE without clobbering errno */
 211 #define SAVE_ERRNO(code)                        \
 212   do                                            \
 213     {                                           \
 214       int __ec = errno;                         \
 215       code;                                     \
 216       errno = __ec;                             \
 217     }                                           \
 218   while (0)                                     \
 219
 220 /* Now define all the routines in use. */
 221 #include "proto.h"