1 /* Fixed size hash table with internal linking. 2 Copyright (C) 2000, 2001, 2002, 2004 Red Hat, Inc. 3 Written by Ulrich Drepper <drepper (at) redhat.com>, 2000. 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation, version 2. 8 9 This program is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 GNU General Public License for more details. 13 14 You should have received a copy of the GNU General Public License 15 along with this program; if not, write to the Free Software Foundation, 16 Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ 17 18 #include <errno.h> 19 #include <stdlib.h> 20 #include <string.h> 21 #include <sys/cdefs.h> 22 #include <sys/param.h> 23 24 #include <system.h> 25 26 #define CONCAT(t1,t2) __CONCAT (t1,t2) 27 28 /* Before including this file the following macros must be defined: 29 30 TYPE data type of the hash table entries 31 HASHFCT name of the hashing function to use 32 HASHTYPE type used for the hashing value 33 COMPARE comparison function taking two pointers to TYPE objects 34 CLASS can be defined to `static' to avoid exporting the functions 35 PREFIX prefix to be used for function and data type names 36 STORE_POINTER if defined the table stores a pointer and not an element 37 of type TYPE 38 INSERT_HASH if defined alternate insert function which takes a hash 39 value is defined 40 NO_FINI_FCT if defined the fini function is not defined 41 */ 42 43 44 /* Defined separately. */ 45 extern size_t next_prime (size_t seed); 46 47 48 /* Set default values. */ 49 #ifndef HASHTYPE 50 # define HASHTYPE size_t 51 #endif 52 53 #ifndef CLASS 54 # define CLASS 55 #endif 56 57 #ifndef PREFIX 58 # define PREFIX 59 #endif 60 61 62 /* The data structure. */ 63 struct CONCAT(PREFIX,fshash) 64 { 65 size_t nslots; 66 struct CONCAT(PREFIX,fshashent) 67 { 68 HASHTYPE hval; 69 #ifdef STORE_POINTER 70 # define ENTRYP(el) (el).entry 71 TYPE *entry; 72 #else 73 # define ENTRYP(el) &(el).entry 74 TYPE entry; 75 #endif 76 } table[0]; 77 }; 78 79 80 /* Constructor for the hashing table. */ 81 CLASS struct CONCAT(PREFIX,fshash) * 82 CONCAT(PREFIX,fshash_init) (size_t nelems) 83 { 84 struct CONCAT(PREFIX,fshash) *result; 85 /* We choose a size for the hashing table 150% over the number of 86 entries. This will guarantee short medium search lengths. */ 87 const size_t max_size_t = ~((size_t) 0); 88 89 if (nelems >= (max_size_t / 3) * 2) 90 { 91 errno = EINVAL; 92 return NULL; 93 } 94 95 /* Adjust the size to be used for the hashing table. */ 96 nelems = next_prime (MAX ((nelems * 3) / 2, 10)); 97 98 /* Allocate the data structure for the result. */ 99 result = (struct CONCAT(PREFIX,fshash) *) 100 xcalloc (sizeof (struct CONCAT(PREFIX,fshash)) 101 + (nelems + 1) * sizeof (struct CONCAT(PREFIX,fshashent)), 1); 102 if (result == NULL) 103 return NULL; 104 105 result->nslots = nelems; 106 107 return result; 108 } 109 110 111 #ifndef NO_FINI_FCT 112 CLASS void 113 CONCAT(PREFIX,fshash_fini) (struct CONCAT(PREFIX,fshash) *htab) 114 { 115 free (htab); 116 } 117 #endif 118 119 120 static struct CONCAT(PREFIX,fshashent) * 121 CONCAT(PREFIX,fshash_lookup) (struct CONCAT(PREFIX,fshash) *htab, 122 HASHTYPE hval, TYPE *data) 123 { 124 size_t idx = 1 + hval % htab->nslots; 125 126 if (htab->table[idx].hval != 0) 127 { 128 HASHTYPE hash; 129 130 /* See whether this is the same entry. */ 131 if (htab->table[idx].hval == hval 132 && COMPARE (data, ENTRYP (htab->table[idx])) == 0) 133 return &htab->table[idx]; 134 135 /* Second hash function as suggested in [Knuth]. */ 136 hash = 1 + hval % (htab->nslots - 2); 137 138 do 139 { 140 if (idx <= hash) 141 idx = htab->nslots + idx - hash; 142 else 143 idx -= hash; 144 145 if (htab->table[idx].hval == hval 146 && COMPARE (data, ENTRYP(htab->table[idx])) == 0) 147 return &htab->table[idx]; 148 } 149 while (htab->table[idx].hval != 0); 150 } 151 152 return &htab->table[idx]; 153 } 154 155 156 CLASS int 157 __attribute__ ((unused)) 158 CONCAT(PREFIX,fshash_insert) (struct CONCAT(PREFIX,fshash) *htab, 159 const char *str, size_t len, TYPE *data) 160 { 161 HASHTYPE hval = HASHFCT (str, len ?: strlen (str)); 162 struct CONCAT(PREFIX,fshashent) *slot; 163 164 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data); 165 if (slot->hval != 0) 166 /* We don't want to overwrite the old value. */ 167 return -1; 168 169 slot->hval = hval; 170 #ifdef STORE_POINTER 171 slot->entry = data; 172 #else 173 slot->entry = *data; 174 #endif 175 176 return 0; 177 } 178 179 180 #ifdef INSERT_HASH 181 CLASS int 182 __attribute__ ((unused)) 183 CONCAT(PREFIX,fshash_insert_hash) (struct CONCAT(PREFIX,fshash) *htab, 184 HASHTYPE hval, TYPE *data) 185 { 186 struct CONCAT(PREFIX,fshashent) *slot; 187 188 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data); 189 if (slot->hval != 0) 190 /* We don't want to overwrite the old value. */ 191 return -1; 192 193 slot->hval = hval; 194 #ifdef STORE_POINTER 195 slot->entry = data; 196 #else 197 slot->entry = *data; 198 #endif 199 200 return 0; 201 } 202 #endif 203 204 205 CLASS int 206 __attribute__ ((unused)) 207 CONCAT(PREFIX,fshash_overwrite) (struct CONCAT(PREFIX,fshash) *htab, 208 const char *str, size_t len, TYPE *data) 209 { 210 HASHTYPE hval = HASHFCT (str, len ?: strlen (str)); 211 struct CONCAT(PREFIX,fshashent) *slot; 212 213 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data); 214 slot->hval = hval; 215 #ifdef STORE_POINTER 216 slot->entry = data; 217 #else 218 slot->entry = *data; 219 #endif 220 221 return 0; 222 } 223 224 225 const CLASS TYPE * 226 CONCAT(PREFIX,fshash_find) (const struct CONCAT(PREFIX,fshash) *htab, 227 const char *str, size_t len, TYPE *data) 228 { 229 HASHTYPE hval = HASHFCT (str, len ?: strlen (str)); 230 struct CONCAT(PREFIX,fshashent) *slot; 231 232 slot = CONCAT(PREFIX,fshash_lookup) ((struct CONCAT(PREFIX,fshash) *) htab, 233 hval, data); 234 if (slot->hval == 0) 235 /* Not found. */ 236 return NULL; 237 238 return ENTRYP(*slot); 239 } 240 241 242 /* Unset the macros we expect. */ 243 #undef TYPE 244 #undef HASHFCT 245 #undef HASHTYPE 246 #undef COMPARE 247 #undef CLASS 248 #undef PREFIX 249 #undef INSERT_HASH 250 #undef STORE_POINTER 251 #undef NO_FINI_FCT 252
