lh | 9ed821d | 2023-04-07 01:36:19 -0700 | [diff] [blame^] | 1 | /* Implement simple hashing table with string based keys. |
| 2 | Copyright (C) 1994-2015 Free Software Foundation, Inc. |
| 3 | This file is part of the GNU C Library. |
| 4 | Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994. |
| 5 | |
| 6 | This program is free software; you can redistribute it and/or modify |
| 7 | it under the terms of the GNU General Public License as published |
| 8 | by the Free Software Foundation; version 2 of the License, or |
| 9 | (at your option) any later version. |
| 10 | |
| 11 | This program 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 this program; if not, see <http://www.gnu.org/licenses/>. */ |
| 18 | |
| 19 | #ifdef HAVE_CONFIG_H |
| 20 | # include <config.h> |
| 21 | #endif |
| 22 | |
| 23 | #include <inttypes.h> |
| 24 | #include <stdio.h> |
| 25 | #include <stdlib.h> |
| 26 | #include <string.h> |
| 27 | #include <stdint.h> |
| 28 | #include <sys/types.h> |
| 29 | |
| 30 | #include <obstack.h> |
| 31 | |
| 32 | #ifdef HAVE_VALUES_H |
| 33 | # include <values.h> |
| 34 | #endif |
| 35 | |
| 36 | #include "simple-hash.h" |
| 37 | |
| 38 | #define obstack_chunk_alloc malloc |
| 39 | #define obstack_chunk_free free |
| 40 | |
| 41 | #ifndef BITSPERBYTE |
| 42 | # define BITSPERBYTE 8 |
| 43 | #endif |
| 44 | |
| 45 | #define hashval_t uint32_t |
| 46 | #include "hashval.h" |
| 47 | |
| 48 | #include <programs/xmalloc.h> |
| 49 | |
| 50 | typedef struct hash_entry |
| 51 | { |
| 52 | unsigned long used; |
| 53 | const void *key; |
| 54 | size_t keylen; |
| 55 | void *data; |
| 56 | struct hash_entry *next; |
| 57 | } |
| 58 | hash_entry; |
| 59 | |
| 60 | /* Prototypes for local functions. */ |
| 61 | static void insert_entry_2 (hash_table *htab, const void *key, size_t keylen, |
| 62 | unsigned long hval, size_t idx, void *data); |
| 63 | static size_t lookup (const hash_table *htab, const void *key, size_t keylen, |
| 64 | unsigned long int hval); |
| 65 | static int is_prime (unsigned long int candidate); |
| 66 | |
| 67 | |
| 68 | int |
| 69 | init_hash (htab, init_size) |
| 70 | hash_table *htab; |
| 71 | unsigned long int init_size; |
| 72 | { |
| 73 | /* We need the size to be a prime. */ |
| 74 | init_size = next_prime (init_size); |
| 75 | |
| 76 | /* Initialize the data structure. */ |
| 77 | htab->size = init_size; |
| 78 | htab->filled = 0; |
| 79 | htab->first = NULL; |
| 80 | htab->table = (void *) xcalloc (init_size + 1, sizeof (hash_entry)); |
| 81 | if (htab->table == NULL) |
| 82 | return -1; |
| 83 | |
| 84 | obstack_init (&htab->mem_pool); |
| 85 | |
| 86 | return 0; |
| 87 | } |
| 88 | |
| 89 | |
| 90 | int |
| 91 | delete_hash (htab) |
| 92 | hash_table *htab; |
| 93 | { |
| 94 | free (htab->table); |
| 95 | obstack_free (&htab->mem_pool, NULL); |
| 96 | return 0; |
| 97 | } |
| 98 | |
| 99 | |
| 100 | int |
| 101 | insert_entry (htab, key, keylen, data) |
| 102 | hash_table *htab; |
| 103 | const void *key; |
| 104 | size_t keylen; |
| 105 | void *data; |
| 106 | { |
| 107 | unsigned long int hval = compute_hashval (key, keylen); |
| 108 | hash_entry *table = (hash_entry *) htab->table; |
| 109 | size_t idx = lookup (htab, key, keylen, hval); |
| 110 | |
| 111 | if (table[idx].used) |
| 112 | /* We don't want to overwrite the old value. */ |
| 113 | return -1; |
| 114 | else |
| 115 | { |
| 116 | /* An empty bucket has been found. */ |
| 117 | insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen), |
| 118 | keylen, hval, idx, data); |
| 119 | return 0; |
| 120 | } |
| 121 | } |
| 122 | |
| 123 | static void |
| 124 | insert_entry_2 (htab, key, keylen, hval, idx, data) |
| 125 | hash_table *htab; |
| 126 | const void *key; |
| 127 | size_t keylen; |
| 128 | unsigned long int hval; |
| 129 | size_t idx; |
| 130 | void *data; |
| 131 | { |
| 132 | hash_entry *table = (hash_entry *) htab->table; |
| 133 | |
| 134 | table[idx].used = hval; |
| 135 | table[idx].key = key; |
| 136 | table[idx].keylen = keylen; |
| 137 | table[idx].data = data; |
| 138 | |
| 139 | /* List the new value in the list. */ |
| 140 | if ((hash_entry *) htab->first == NULL) |
| 141 | { |
| 142 | table[idx].next = &table[idx]; |
| 143 | htab->first = &table[idx]; |
| 144 | } |
| 145 | else |
| 146 | { |
| 147 | table[idx].next = ((hash_entry *) htab->first)->next; |
| 148 | ((hash_entry *) htab->first)->next = &table[idx]; |
| 149 | htab->first = &table[idx]; |
| 150 | } |
| 151 | |
| 152 | ++htab->filled; |
| 153 | if (100 * htab->filled > 75 * htab->size) |
| 154 | { |
| 155 | /* Table is filled more than 75%. Resize the table. |
| 156 | Experiments have shown that for best performance, this threshold |
| 157 | must lie between 40% and 85%. */ |
| 158 | unsigned long int old_size = htab->size; |
| 159 | |
| 160 | htab->size = next_prime (htab->size * 2); |
| 161 | htab->filled = 0; |
| 162 | htab->first = NULL; |
| 163 | htab->table = (void *) xcalloc (1 + htab->size, sizeof (hash_entry)); |
| 164 | |
| 165 | for (idx = 1; idx <= old_size; ++idx) |
| 166 | if (table[idx].used) |
| 167 | insert_entry_2 (htab, table[idx].key, table[idx].keylen, |
| 168 | table[idx].used, |
| 169 | lookup (htab, table[idx].key, table[idx].keylen, |
| 170 | table[idx].used), |
| 171 | table[idx].data); |
| 172 | |
| 173 | free (table); |
| 174 | } |
| 175 | } |
| 176 | |
| 177 | |
| 178 | int |
| 179 | find_entry (htab, key, keylen, result) |
| 180 | const hash_table *htab; |
| 181 | const void *key; |
| 182 | size_t keylen; |
| 183 | void **result; |
| 184 | { |
| 185 | hash_entry *table = (hash_entry *) htab->table; |
| 186 | size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen)); |
| 187 | |
| 188 | if (table[idx].used == 0) |
| 189 | return -1; |
| 190 | |
| 191 | *result = table[idx].data; |
| 192 | return 0; |
| 193 | } |
| 194 | |
| 195 | |
| 196 | int |
| 197 | set_entry (htab, key, keylen, newval) |
| 198 | hash_table *htab; |
| 199 | const void *key; |
| 200 | size_t keylen; |
| 201 | void *newval; |
| 202 | { |
| 203 | hash_entry *table = (hash_entry *) htab->table; |
| 204 | size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen)); |
| 205 | |
| 206 | if (table[idx].used == 0) |
| 207 | return -1; |
| 208 | |
| 209 | table[idx].data = newval; |
| 210 | return 0; |
| 211 | } |
| 212 | |
| 213 | |
| 214 | int |
| 215 | iterate_table (htab, ptr, key, keylen, data) |
| 216 | const hash_table *htab; |
| 217 | void **ptr; |
| 218 | const void **key; |
| 219 | size_t *keylen; |
| 220 | void **data; |
| 221 | { |
| 222 | if (*ptr == NULL) |
| 223 | { |
| 224 | if (htab->first == NULL) |
| 225 | return -1; |
| 226 | *ptr = (void *) ((hash_entry *) htab->first)->next; |
| 227 | } |
| 228 | else |
| 229 | { |
| 230 | if (*ptr == htab->first) |
| 231 | return -1; |
| 232 | *ptr = (void *) (((hash_entry *) *ptr)->next); |
| 233 | } |
| 234 | |
| 235 | *key = ((hash_entry *) *ptr)->key; |
| 236 | *keylen = ((hash_entry *) *ptr)->keylen; |
| 237 | *data = ((hash_entry *) *ptr)->data; |
| 238 | return 0; |
| 239 | } |
| 240 | |
| 241 | |
| 242 | /* References: |
| 243 | [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986 |
| 244 | [Knuth] The Art of Computer Programming, part3 (6.4) */ |
| 245 | |
| 246 | static size_t |
| 247 | lookup (htab, key, keylen, hval) |
| 248 | const hash_table *htab; |
| 249 | const void *key; |
| 250 | size_t keylen; |
| 251 | unsigned long int hval; |
| 252 | { |
| 253 | unsigned long int hash; |
| 254 | size_t idx; |
| 255 | hash_entry *table = (hash_entry *) htab->table; |
| 256 | |
| 257 | /* First hash function: simply take the modul but prevent zero. */ |
| 258 | hash = 1 + hval % htab->size; |
| 259 | |
| 260 | idx = hash; |
| 261 | |
| 262 | if (table[idx].used) |
| 263 | { |
| 264 | if (table[idx].used == hval && table[idx].keylen == keylen |
| 265 | && memcmp (table[idx].key, key, keylen) == 0) |
| 266 | return idx; |
| 267 | |
| 268 | /* Second hash function as suggested in [Knuth]. */ |
| 269 | hash = 1 + hval % (htab->size - 2); |
| 270 | |
| 271 | do |
| 272 | { |
| 273 | if (idx <= hash) |
| 274 | idx = htab->size + idx - hash; |
| 275 | else |
| 276 | idx -= hash; |
| 277 | |
| 278 | /* If entry is found use it. */ |
| 279 | if (table[idx].used == hval && table[idx].keylen == keylen |
| 280 | && memcmp (table[idx].key, key, keylen) == 0) |
| 281 | return idx; |
| 282 | } |
| 283 | while (table[idx].used); |
| 284 | } |
| 285 | return idx; |
| 286 | } |
| 287 | |
| 288 | |
| 289 | unsigned long int |
| 290 | next_prime (seed) |
| 291 | unsigned long int seed; |
| 292 | { |
| 293 | /* Make it definitely odd. */ |
| 294 | seed |= 1; |
| 295 | |
| 296 | while (!is_prime (seed)) |
| 297 | seed += 2; |
| 298 | |
| 299 | return seed; |
| 300 | } |
| 301 | |
| 302 | |
| 303 | static int |
| 304 | is_prime (candidate) |
| 305 | unsigned long int candidate; |
| 306 | { |
| 307 | /* No even number and none less than 10 will be passed here. */ |
| 308 | unsigned long int divn = 3; |
| 309 | unsigned long int sq = divn * divn; |
| 310 | |
| 311 | while (sq < candidate && candidate % divn != 0) |
| 312 | { |
| 313 | ++divn; |
| 314 | sq += 4 * divn; |
| 315 | ++divn; |
| 316 | } |
| 317 | |
| 318 | return candidate % divn != 0; |
| 319 | } |