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