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 Red Hat elfutils. 4 Written by Ulrich Drepper <drepper (at) redhat.com>, 2000. 5 6 Red Hat elfutils is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by the 8 Free Software Foundation; version 2 of the License. 9 10 Red Hat elfutils is distributed in the hope that it will be useful, but 11 WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 General Public License for more details. 14 15 You should have received a copy of the GNU General Public License along 16 with Red Hat elfutils; if not, write to the Free Software Foundation, 17 Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA. 18 19 In addition, as a special exception, Red Hat, Inc. gives You the 20 additional right to link the code of Red Hat elfutils with code licensed 21 under any Open Source Initiative certified open source license 22 (http://www.opensource.org/licenses/index.php) which requires the 23 distribution of source code with any binary distribution and to 24 distribute linked combinations of the two. Non-GPL Code permitted under 25 this exception must only link to the code of Red Hat elfutils through 26 those well defined interfaces identified in the file named EXCEPTION 27 found in the source code files (the "Approved Interfaces"). The files 28 of Non-GPL Code may instantiate templates or use macros or inline 29 functions from the Approved Interfaces without causing the resulting 30 work to be covered by the GNU General Public License. Only Red Hat, 31 Inc. may make changes or additions to the list of Approved Interfaces. 32 Red Hat's grant of this exception is conditioned upon your not adding 33 any new exceptions. If you wish to add a new Approved Interface or 34 exception, please contact Red Hat. You must obey the GNU General Public 35 License in all respects for all of the Red Hat elfutils code and other 36 code used in conjunction with Red Hat elfutils except the Non-GPL Code 37 covered by this exception. If you modify this file, you may extend this 38 exception to your version of the file, but you are not obligated to do 39 so. If you do not wish to provide this exception without modification, 40 you must delete this exception statement from your version and license 41 this file solely under the GPL without exception. 42 43 Red Hat elfutils is an included package of the Open Invention Network. 44 An included package of the Open Invention Network is a package for which 45 Open Invention Network licensees cross-license their patents. No patent 46 license is granted, either expressly or impliedly, by designation as an 47 included package. Should you wish to participate in the Open Invention 48 Network licensing program, please visit www.openinventionnetwork.com 49 <http://www.openinventionnetwork.com>. */ 50 51 #include <errno.h> 52 #include <stdlib.h> 53 #include <string.h> 54 #include <sys/cdefs.h> 55 #include <sys/param.h> 56 57 #include <system.h> 58 59 #define CONCAT(t1,t2) __CONCAT (t1,t2) 60 61 /* Before including this file the following macros must be defined: 62 63 TYPE data type of the hash table entries 64 HASHFCT name of the hashing function to use 65 HASHTYPE type used for the hashing value 66 COMPARE comparison function taking two pointers to TYPE objects 67 CLASS can be defined to `static' to avoid exporting the functions 68 PREFIX prefix to be used for function and data type names 69 STORE_POINTER if defined the table stores a pointer and not an element 70 of type TYPE 71 INSERT_HASH if defined alternate insert function which takes a hash 72 value is defined 73 NO_FINI_FCT if defined the fini function is not defined 74 */ 75 76 77 /* Defined separately. */ 78 extern size_t next_prime (size_t seed); 79 80 81 /* Set default values. */ 82 #ifndef HASHTYPE 83 # define HASHTYPE size_t 84 #endif 85 86 #ifndef CLASS 87 # define CLASS 88 #endif 89 90 #ifndef PREFIX 91 # define PREFIX 92 #endif 93 94 95 /* The data structure. */ 96 struct CONCAT(PREFIX,fshash) 97 { 98 size_t nslots; 99 struct CONCAT(PREFIX,fshashent) 100 { 101 HASHTYPE hval; 102 #ifdef STORE_POINTER 103 # define ENTRYP(el) (el).entry 104 TYPE *entry; 105 #else 106 # define ENTRYP(el) &(el).entry 107 TYPE entry; 108 #endif 109 } table[0]; 110 }; 111 112 113 /* Constructor for the hashing table. */ 114 CLASS struct CONCAT(PREFIX,fshash) * 115 CONCAT(PREFIX,fshash_init) (size_t nelems) 116 { 117 struct CONCAT(PREFIX,fshash) *result; 118 /* We choose a size for the hashing table 150% over the number of 119 entries. This will guarantee short medium search lengths. */ 120 const size_t max_size_t = ~((size_t) 0); 121 122 if (nelems >= (max_size_t / 3) * 2) 123 { 124 errno = EINVAL; 125 return NULL; 126 } 127 128 /* Adjust the size to be used for the hashing table. */ 129 nelems = next_prime (MAX ((nelems * 3) / 2, 10)); 130 131 /* Allocate the data structure for the result. */ 132 result = (struct CONCAT(PREFIX,fshash) *) 133 xcalloc (sizeof (struct CONCAT(PREFIX,fshash)) 134 + (nelems + 1) * sizeof (struct CONCAT(PREFIX,fshashent)), 1); 135 if (result == NULL) 136 return NULL; 137 138 result->nslots = nelems; 139 140 return result; 141 } 142 143 144 #ifndef NO_FINI_FCT 145 CLASS void 146 CONCAT(PREFIX,fshash_fini) (struct CONCAT(PREFIX,fshash) *htab) 147 { 148 free (htab); 149 } 150 #endif 151 152 153 static struct CONCAT(PREFIX,fshashent) * 154 CONCAT(PREFIX,fshash_lookup) (struct CONCAT(PREFIX,fshash) *htab, 155 HASHTYPE hval, TYPE *data) 156 { 157 size_t idx = 1 + hval % htab->nslots; 158 159 if (htab->table[idx].hval != 0) 160 { 161 HASHTYPE hash; 162 163 /* See whether this is the same entry. */ 164 if (htab->table[idx].hval == hval 165 && COMPARE (data, ENTRYP (htab->table[idx])) == 0) 166 return &htab->table[idx]; 167 168 /* Second hash function as suggested in [Knuth]. */ 169 hash = 1 + hval % (htab->nslots - 2); 170 171 do 172 { 173 if (idx <= hash) 174 idx = htab->nslots + idx - hash; 175 else 176 idx -= hash; 177 178 if (htab->table[idx].hval == hval 179 && COMPARE (data, ENTRYP(htab->table[idx])) == 0) 180 return &htab->table[idx]; 181 } 182 while (htab->table[idx].hval != 0); 183 } 184 185 return &htab->table[idx]; 186 } 187 188 189 CLASS int 190 __attribute__ ((unused)) 191 CONCAT(PREFIX,fshash_insert) (struct CONCAT(PREFIX,fshash) *htab, 192 const char *str, 193 size_t len __attribute__ ((unused)), TYPE *data) 194 { 195 HASHTYPE hval = HASHFCT (str, len ?: strlen (str)); 196 struct CONCAT(PREFIX,fshashent) *slot; 197 198 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data); 199 if (slot->hval != 0) 200 /* We don't want to overwrite the old value. */ 201 return -1; 202 203 slot->hval = hval; 204 #ifdef STORE_POINTER 205 slot->entry = data; 206 #else 207 slot->entry = *data; 208 #endif 209 210 return 0; 211 } 212 213 214 #ifdef INSERT_HASH 215 CLASS int 216 __attribute__ ((unused)) 217 CONCAT(PREFIX,fshash_insert_hash) (struct CONCAT(PREFIX,fshash) *htab, 218 HASHTYPE hval, TYPE *data) 219 { 220 struct CONCAT(PREFIX,fshashent) *slot; 221 222 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data); 223 if (slot->hval != 0) 224 /* We don't want to overwrite the old value. */ 225 return -1; 226 227 slot->hval = hval; 228 #ifdef STORE_POINTER 229 slot->entry = data; 230 #else 231 slot->entry = *data; 232 #endif 233 234 return 0; 235 } 236 #endif 237 238 239 CLASS int 240 __attribute__ ((unused)) 241 CONCAT(PREFIX,fshash_overwrite) (struct CONCAT(PREFIX,fshash) *htab, 242 const char *str, 243 size_t len __attribute__ ((unused)), 244 TYPE *data) 245 { 246 HASHTYPE hval = HASHFCT (str, len ?: strlen (str)); 247 struct CONCAT(PREFIX,fshashent) *slot; 248 249 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data); 250 slot->hval = hval; 251 #ifdef STORE_POINTER 252 slot->entry = data; 253 #else 254 slot->entry = *data; 255 #endif 256 257 return 0; 258 } 259 260 261 CLASS const TYPE * 262 CONCAT(PREFIX,fshash_find) (const struct CONCAT(PREFIX,fshash) *htab, 263 const char *str, 264 size_t len __attribute__ ((unused)), TYPE *data) 265 { 266 HASHTYPE hval = HASHFCT (str, len ?: strlen (str)); 267 struct CONCAT(PREFIX,fshashent) *slot; 268 269 slot = CONCAT(PREFIX,fshash_lookup) ((struct CONCAT(PREFIX,fshash) *) htab, 270 hval, data); 271 if (slot->hval == 0) 272 /* Not found. */ 273 return NULL; 274 275 return ENTRYP(*slot); 276 } 277 278 279 /* Unset the macros we expect. */ 280 #undef TYPE 281 #undef HASHFCT 282 #undef HASHTYPE 283 #undef COMPARE 284 #undef CLASS 285 #undef PREFIX 286 #undef INSERT_HASH 287 #undef STORE_POINTER 288 #undef NO_FINI_FCT 289
