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