Mercurial > hg > CbC > CbC_gcc
annotate libiberty/hashtab.c @ 55:77e2b8dfacca gcc-4.4.5
update it from 4.4.3 to 4.5.0
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 12 Feb 2010 23:39:51 +0900 |
| parents | a06113de4d67 |
| children | f6334be47118 |
| rev | line source |
|---|---|
| 0 | 1 /* An expandable hash tables datatype. |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2009 |
| 0 | 3 Free Software Foundation, Inc. |
| 4 Contributed by Vladimir Makarov (vmakarov@cygnus.com). | |
| 5 | |
| 6 This file is part of the libiberty library. | |
| 7 Libiberty is free software; you can redistribute it and/or | |
| 8 modify it under the terms of the GNU Library General Public | |
| 9 License as published by the Free Software Foundation; either | |
| 10 version 2 of the License, or (at your option) any later version. | |
| 11 | |
| 12 Libiberty is distributed in the hope that it will be useful, | |
| 13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| 15 Library General Public License for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU Library General Public | |
| 18 License along with libiberty; see the file COPYING.LIB. If | |
| 19 not, write to the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor, | |
| 20 Boston, MA 02110-1301, USA. */ | |
| 21 | |
| 22 /* This package implements basic hash table functionality. It is possible | |
| 23 to search for an entry, create an entry and destroy an entry. | |
| 24 | |
| 25 Elements in the table are generic pointers. | |
| 26 | |
| 27 The size of the table is not fixed; if the occupancy of the table | |
| 28 grows too high the hash table will be expanded. | |
| 29 | |
| 30 The abstract data implementation is based on generalized Algorithm D | |
| 31 from Knuth's book "The art of computer programming". Hash table is | |
| 32 expanded by creation of new hash table and transferring elements from | |
| 33 the old table to the new table. */ | |
| 34 | |
| 35 #ifdef HAVE_CONFIG_H | |
| 36 #include "config.h" | |
| 37 #endif | |
| 38 | |
| 39 #include <sys/types.h> | |
| 40 | |
| 41 #ifdef HAVE_STDLIB_H | |
| 42 #include <stdlib.h> | |
| 43 #endif | |
| 44 #ifdef HAVE_STRING_H | |
| 45 #include <string.h> | |
| 46 #endif | |
| 47 #ifdef HAVE_MALLOC_H | |
| 48 #include <malloc.h> | |
| 49 #endif | |
| 50 #ifdef HAVE_LIMITS_H | |
| 51 #include <limits.h> | |
| 52 #endif | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
53 #ifdef HAVE_INTTYPES_H |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
54 #include <inttypes.h> |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
55 #endif |
| 0 | 56 #ifdef HAVE_STDINT_H |
| 57 #include <stdint.h> | |
| 58 #endif | |
| 59 | |
| 60 #include <stdio.h> | |
| 61 | |
| 62 #include "libiberty.h" | |
| 63 #include "ansidecl.h" | |
| 64 #include "hashtab.h" | |
| 65 | |
| 66 #ifndef CHAR_BIT | |
| 67 #define CHAR_BIT 8 | |
| 68 #endif | |
| 69 | |
| 70 static unsigned int higher_prime_index (unsigned long); | |
| 71 static hashval_t htab_mod_1 (hashval_t, hashval_t, hashval_t, int); | |
| 72 static hashval_t htab_mod (hashval_t, htab_t); | |
| 73 static hashval_t htab_mod_m2 (hashval_t, htab_t); | |
| 74 static hashval_t hash_pointer (const void *); | |
| 75 static int eq_pointer (const void *, const void *); | |
| 76 static int htab_expand (htab_t); | |
| 77 static PTR *find_empty_slot_for_expand (htab_t, hashval_t); | |
| 78 | |
| 79 /* At some point, we could make these be NULL, and modify the | |
| 80 hash-table routines to handle NULL specially; that would avoid | |
| 81 function-call overhead for the common case of hashing pointers. */ | |
| 82 htab_hash htab_hash_pointer = hash_pointer; | |
| 83 htab_eq htab_eq_pointer = eq_pointer; | |
| 84 | |
| 85 /* Table of primes and multiplicative inverses. | |
| 86 | |
| 87 Note that these are not minimally reduced inverses. Unlike when generating | |
| 88 code to divide by a constant, we want to be able to use the same algorithm | |
| 89 all the time. All of these inverses (are implied to) have bit 32 set. | |
| 90 | |
| 91 For the record, here's the function that computed the table; it's a | |
| 92 vastly simplified version of the function of the same name from gcc. */ | |
| 93 | |
| 94 #if 0 | |
| 95 unsigned int | |
| 96 ceil_log2 (unsigned int x) | |
| 97 { | |
| 98 int i; | |
| 99 for (i = 31; i >= 0 ; --i) | |
| 100 if (x > (1u << i)) | |
| 101 return i+1; | |
| 102 abort (); | |
| 103 } | |
| 104 | |
| 105 unsigned int | |
| 106 choose_multiplier (unsigned int d, unsigned int *mlp, unsigned char *shiftp) | |
| 107 { | |
| 108 unsigned long long mhigh; | |
| 109 double nx; | |
| 110 int lgup, post_shift; | |
| 111 int pow, pow2; | |
| 112 int n = 32, precision = 32; | |
| 113 | |
| 114 lgup = ceil_log2 (d); | |
| 115 pow = n + lgup; | |
| 116 pow2 = n + lgup - precision; | |
| 117 | |
| 118 nx = ldexp (1.0, pow) + ldexp (1.0, pow2); | |
| 119 mhigh = nx / d; | |
| 120 | |
| 121 *shiftp = lgup - 1; | |
| 122 *mlp = mhigh; | |
| 123 return mhigh >> 32; | |
| 124 } | |
| 125 #endif | |
| 126 | |
| 127 struct prime_ent | |
| 128 { | |
| 129 hashval_t prime; | |
| 130 hashval_t inv; | |
| 131 hashval_t inv_m2; /* inverse of prime-2 */ | |
| 132 hashval_t shift; | |
| 133 }; | |
| 134 | |
| 135 static struct prime_ent const prime_tab[] = { | |
| 136 { 7, 0x24924925, 0x9999999b, 2 }, | |
| 137 { 13, 0x3b13b13c, 0x745d1747, 3 }, | |
| 138 { 31, 0x08421085, 0x1a7b9612, 4 }, | |
| 139 { 61, 0x0c9714fc, 0x15b1e5f8, 5 }, | |
| 140 { 127, 0x02040811, 0x0624dd30, 6 }, | |
| 141 { 251, 0x05197f7e, 0x073260a5, 7 }, | |
| 142 { 509, 0x01824366, 0x02864fc8, 8 }, | |
| 143 { 1021, 0x00c0906d, 0x014191f7, 9 }, | |
| 144 { 2039, 0x0121456f, 0x0161e69e, 10 }, | |
| 145 { 4093, 0x00300902, 0x00501908, 11 }, | |
| 146 { 8191, 0x00080041, 0x00180241, 12 }, | |
| 147 { 16381, 0x000c0091, 0x00140191, 13 }, | |
| 148 { 32749, 0x002605a5, 0x002a06e6, 14 }, | |
| 149 { 65521, 0x000f00e2, 0x00110122, 15 }, | |
| 150 { 131071, 0x00008001, 0x00018003, 16 }, | |
| 151 { 262139, 0x00014002, 0x0001c004, 17 }, | |
| 152 { 524287, 0x00002001, 0x00006001, 18 }, | |
| 153 { 1048573, 0x00003001, 0x00005001, 19 }, | |
| 154 { 2097143, 0x00004801, 0x00005801, 20 }, | |
| 155 { 4194301, 0x00000c01, 0x00001401, 21 }, | |
| 156 { 8388593, 0x00001e01, 0x00002201, 22 }, | |
| 157 { 16777213, 0x00000301, 0x00000501, 23 }, | |
| 158 { 33554393, 0x00001381, 0x00001481, 24 }, | |
| 159 { 67108859, 0x00000141, 0x000001c1, 25 }, | |
| 160 { 134217689, 0x000004e1, 0x00000521, 26 }, | |
| 161 { 268435399, 0x00000391, 0x000003b1, 27 }, | |
| 162 { 536870909, 0x00000019, 0x00000029, 28 }, | |
| 163 { 1073741789, 0x0000008d, 0x00000095, 29 }, | |
| 164 { 2147483647, 0x00000003, 0x00000007, 30 }, | |
| 165 /* Avoid "decimal constant so large it is unsigned" for 4294967291. */ | |
| 166 { 0xfffffffb, 0x00000006, 0x00000008, 31 } | |
| 167 }; | |
| 168 | |
| 169 /* The following function returns an index into the above table of the | |
| 170 nearest prime number which is greater than N, and near a power of two. */ | |
| 171 | |
| 172 static unsigned int | |
| 173 higher_prime_index (unsigned long n) | |
| 174 { | |
| 175 unsigned int low = 0; | |
| 176 unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]); | |
| 177 | |
| 178 while (low != high) | |
| 179 { | |
| 180 unsigned int mid = low + (high - low) / 2; | |
| 181 if (n > prime_tab[mid].prime) | |
| 182 low = mid + 1; | |
| 183 else | |
| 184 high = mid; | |
| 185 } | |
| 186 | |
| 187 /* If we've run out of primes, abort. */ | |
| 188 if (n > prime_tab[low].prime) | |
| 189 { | |
| 190 fprintf (stderr, "Cannot find prime bigger than %lu\n", n); | |
| 191 abort (); | |
| 192 } | |
| 193 | |
| 194 return low; | |
| 195 } | |
| 196 | |
| 197 /* Returns a hash code for P. */ | |
| 198 | |
| 199 static hashval_t | |
| 200 hash_pointer (const PTR p) | |
| 201 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
202 return (hashval_t) ((intptr_t)p >> 3); |
| 0 | 203 } |
| 204 | |
| 205 /* Returns non-zero if P1 and P2 are equal. */ | |
| 206 | |
| 207 static int | |
| 208 eq_pointer (const PTR p1, const PTR p2) | |
| 209 { | |
| 210 return p1 == p2; | |
| 211 } | |
| 212 | |
| 213 | |
| 214 /* The parens around the function names in the next two definitions | |
| 215 are essential in order to prevent macro expansions of the name. | |
| 216 The bodies, however, are expanded as expected, so they are not | |
| 217 recursive definitions. */ | |
| 218 | |
| 219 /* Return the current size of given hash table. */ | |
| 220 | |
| 221 #define htab_size(htab) ((htab)->size) | |
| 222 | |
| 223 size_t | |
| 224 (htab_size) (htab_t htab) | |
| 225 { | |
| 226 return htab_size (htab); | |
| 227 } | |
| 228 | |
| 229 /* Return the current number of elements in given hash table. */ | |
| 230 | |
| 231 #define htab_elements(htab) ((htab)->n_elements - (htab)->n_deleted) | |
| 232 | |
| 233 size_t | |
| 234 (htab_elements) (htab_t htab) | |
| 235 { | |
| 236 return htab_elements (htab); | |
| 237 } | |
| 238 | |
| 239 /* Return X % Y. */ | |
| 240 | |
| 241 static inline hashval_t | |
| 242 htab_mod_1 (hashval_t x, hashval_t y, hashval_t inv, int shift) | |
| 243 { | |
| 244 /* The multiplicative inverses computed above are for 32-bit types, and | |
| 245 requires that we be able to compute a highpart multiply. */ | |
| 246 #ifdef UNSIGNED_64BIT_TYPE | |
| 247 __extension__ typedef UNSIGNED_64BIT_TYPE ull; | |
| 248 if (sizeof (hashval_t) * CHAR_BIT <= 32) | |
| 249 { | |
| 250 hashval_t t1, t2, t3, t4, q, r; | |
| 251 | |
| 252 t1 = ((ull)x * inv) >> 32; | |
| 253 t2 = x - t1; | |
| 254 t3 = t2 >> 1; | |
| 255 t4 = t1 + t3; | |
| 256 q = t4 >> shift; | |
| 257 r = x - (q * y); | |
| 258 | |
| 259 return r; | |
| 260 } | |
| 261 #endif | |
| 262 | |
| 263 /* Otherwise just use the native division routines. */ | |
| 264 return x % y; | |
| 265 } | |
| 266 | |
| 267 /* Compute the primary hash for HASH given HTAB's current size. */ | |
| 268 | |
| 269 static inline hashval_t | |
| 270 htab_mod (hashval_t hash, htab_t htab) | |
| 271 { | |
| 272 const struct prime_ent *p = &prime_tab[htab->size_prime_index]; | |
| 273 return htab_mod_1 (hash, p->prime, p->inv, p->shift); | |
| 274 } | |
| 275 | |
| 276 /* Compute the secondary hash for HASH given HTAB's current size. */ | |
| 277 | |
| 278 static inline hashval_t | |
| 279 htab_mod_m2 (hashval_t hash, htab_t htab) | |
| 280 { | |
| 281 const struct prime_ent *p = &prime_tab[htab->size_prime_index]; | |
| 282 return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift); | |
| 283 } | |
| 284 | |
| 285 /* This function creates table with length slightly longer than given | |
| 286 source length. Created hash table is initiated as empty (all the | |
| 287 hash table entries are HTAB_EMPTY_ENTRY). The function returns the | |
| 288 created hash table, or NULL if memory allocation fails. */ | |
| 289 | |
| 290 htab_t | |
| 291 htab_create_alloc (size_t size, htab_hash hash_f, htab_eq eq_f, | |
| 292 htab_del del_f, htab_alloc alloc_f, htab_free free_f) | |
| 293 { | |
| 294 htab_t result; | |
| 295 unsigned int size_prime_index; | |
| 296 | |
| 297 size_prime_index = higher_prime_index (size); | |
| 298 size = prime_tab[size_prime_index].prime; | |
| 299 | |
| 300 result = (htab_t) (*alloc_f) (1, sizeof (struct htab)); | |
| 301 if (result == NULL) | |
| 302 return NULL; | |
| 303 result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR)); | |
| 304 if (result->entries == NULL) | |
| 305 { | |
| 306 if (free_f != NULL) | |
| 307 (*free_f) (result); | |
| 308 return NULL; | |
| 309 } | |
| 310 result->size = size; | |
| 311 result->size_prime_index = size_prime_index; | |
| 312 result->hash_f = hash_f; | |
| 313 result->eq_f = eq_f; | |
| 314 result->del_f = del_f; | |
| 315 result->alloc_f = alloc_f; | |
| 316 result->free_f = free_f; | |
| 317 return result; | |
| 318 } | |
| 319 | |
| 320 /* As above, but use the variants of alloc_f and free_f which accept | |
| 321 an extra argument. */ | |
| 322 | |
| 323 htab_t | |
| 324 htab_create_alloc_ex (size_t size, htab_hash hash_f, htab_eq eq_f, | |
| 325 htab_del del_f, void *alloc_arg, | |
| 326 htab_alloc_with_arg alloc_f, | |
| 327 htab_free_with_arg free_f) | |
| 328 { | |
| 329 htab_t result; | |
| 330 unsigned int size_prime_index; | |
| 331 | |
| 332 size_prime_index = higher_prime_index (size); | |
| 333 size = prime_tab[size_prime_index].prime; | |
| 334 | |
| 335 result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab)); | |
| 336 if (result == NULL) | |
| 337 return NULL; | |
| 338 result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR)); | |
| 339 if (result->entries == NULL) | |
| 340 { | |
| 341 if (free_f != NULL) | |
| 342 (*free_f) (alloc_arg, result); | |
| 343 return NULL; | |
| 344 } | |
| 345 result->size = size; | |
| 346 result->size_prime_index = size_prime_index; | |
| 347 result->hash_f = hash_f; | |
| 348 result->eq_f = eq_f; | |
| 349 result->del_f = del_f; | |
| 350 result->alloc_arg = alloc_arg; | |
| 351 result->alloc_with_arg_f = alloc_f; | |
| 352 result->free_with_arg_f = free_f; | |
| 353 return result; | |
| 354 } | |
| 355 | |
| 356 /* Update the function pointers and allocation parameter in the htab_t. */ | |
| 357 | |
| 358 void | |
| 359 htab_set_functions_ex (htab_t htab, htab_hash hash_f, htab_eq eq_f, | |
| 360 htab_del del_f, PTR alloc_arg, | |
| 361 htab_alloc_with_arg alloc_f, htab_free_with_arg free_f) | |
| 362 { | |
| 363 htab->hash_f = hash_f; | |
| 364 htab->eq_f = eq_f; | |
| 365 htab->del_f = del_f; | |
| 366 htab->alloc_arg = alloc_arg; | |
| 367 htab->alloc_with_arg_f = alloc_f; | |
| 368 htab->free_with_arg_f = free_f; | |
| 369 } | |
| 370 | |
| 371 /* These functions exist solely for backward compatibility. */ | |
| 372 | |
| 373 #undef htab_create | |
| 374 htab_t | |
| 375 htab_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f) | |
| 376 { | |
| 377 return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free); | |
| 378 } | |
| 379 | |
| 380 htab_t | |
| 381 htab_try_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f) | |
| 382 { | |
| 383 return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free); | |
| 384 } | |
| 385 | |
| 386 /* This function frees all memory allocated for given hash table. | |
| 387 Naturally the hash table must already exist. */ | |
| 388 | |
| 389 void | |
| 390 htab_delete (htab_t htab) | |
| 391 { | |
| 392 size_t size = htab_size (htab); | |
| 393 PTR *entries = htab->entries; | |
| 394 int i; | |
| 395 | |
| 396 if (htab->del_f) | |
| 397 for (i = size - 1; i >= 0; i--) | |
| 398 if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY) | |
| 399 (*htab->del_f) (entries[i]); | |
| 400 | |
| 401 if (htab->free_f != NULL) | |
| 402 { | |
| 403 (*htab->free_f) (entries); | |
| 404 (*htab->free_f) (htab); | |
| 405 } | |
| 406 else if (htab->free_with_arg_f != NULL) | |
| 407 { | |
| 408 (*htab->free_with_arg_f) (htab->alloc_arg, entries); | |
| 409 (*htab->free_with_arg_f) (htab->alloc_arg, htab); | |
| 410 } | |
| 411 } | |
| 412 | |
| 413 /* This function clears all entries in the given hash table. */ | |
| 414 | |
| 415 void | |
| 416 htab_empty (htab_t htab) | |
| 417 { | |
| 418 size_t size = htab_size (htab); | |
| 419 PTR *entries = htab->entries; | |
| 420 int i; | |
| 421 | |
| 422 if (htab->del_f) | |
| 423 for (i = size - 1; i >= 0; i--) | |
| 424 if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY) | |
| 425 (*htab->del_f) (entries[i]); | |
| 426 | |
| 427 /* Instead of clearing megabyte, downsize the table. */ | |
| 428 if (size > 1024*1024 / sizeof (PTR)) | |
| 429 { | |
| 430 int nindex = higher_prime_index (1024 / sizeof (PTR)); | |
| 431 int nsize = prime_tab[nindex].prime; | |
| 432 | |
| 433 if (htab->free_f != NULL) | |
| 434 (*htab->free_f) (htab->entries); | |
| 435 else if (htab->free_with_arg_f != NULL) | |
| 436 (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries); | |
| 437 if (htab->alloc_with_arg_f != NULL) | |
| 438 htab->entries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize, | |
| 439 sizeof (PTR *)); | |
| 440 else | |
| 441 htab->entries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *)); | |
| 442 htab->size = nsize; | |
| 443 htab->size_prime_index = nindex; | |
| 444 } | |
| 445 else | |
| 446 memset (entries, 0, size * sizeof (PTR)); | |
| 447 htab->n_deleted = 0; | |
| 448 htab->n_elements = 0; | |
| 449 } | |
| 450 | |
| 451 /* Similar to htab_find_slot, but without several unwanted side effects: | |
| 452 - Does not call htab->eq_f when it finds an existing entry. | |
| 453 - Does not change the count of elements/searches/collisions in the | |
| 454 hash table. | |
| 455 This function also assumes there are no deleted entries in the table. | |
| 456 HASH is the hash value for the element to be inserted. */ | |
| 457 | |
| 458 static PTR * | |
| 459 find_empty_slot_for_expand (htab_t htab, hashval_t hash) | |
| 460 { | |
| 461 hashval_t index = htab_mod (hash, htab); | |
| 462 size_t size = htab_size (htab); | |
| 463 PTR *slot = htab->entries + index; | |
| 464 hashval_t hash2; | |
| 465 | |
| 466 if (*slot == HTAB_EMPTY_ENTRY) | |
| 467 return slot; | |
| 468 else if (*slot == HTAB_DELETED_ENTRY) | |
| 469 abort (); | |
| 470 | |
| 471 hash2 = htab_mod_m2 (hash, htab); | |
| 472 for (;;) | |
| 473 { | |
| 474 index += hash2; | |
| 475 if (index >= size) | |
| 476 index -= size; | |
| 477 | |
| 478 slot = htab->entries + index; | |
| 479 if (*slot == HTAB_EMPTY_ENTRY) | |
| 480 return slot; | |
| 481 else if (*slot == HTAB_DELETED_ENTRY) | |
| 482 abort (); | |
| 483 } | |
| 484 } | |
| 485 | |
| 486 /* The following function changes size of memory allocated for the | |
| 487 entries and repeatedly inserts the table elements. The occupancy | |
| 488 of the table after the call will be about 50%. Naturally the hash | |
| 489 table must already exist. Remember also that the place of the | |
| 490 table entries is changed. If memory allocation failures are allowed, | |
| 491 this function will return zero, indicating that the table could not be | |
| 492 expanded. If all goes well, it will return a non-zero value. */ | |
| 493 | |
| 494 static int | |
| 495 htab_expand (htab_t htab) | |
| 496 { | |
| 497 PTR *oentries; | |
| 498 PTR *olimit; | |
| 499 PTR *p; | |
| 500 PTR *nentries; | |
| 501 size_t nsize, osize, elts; | |
| 502 unsigned int oindex, nindex; | |
| 503 | |
| 504 oentries = htab->entries; | |
| 505 oindex = htab->size_prime_index; | |
| 506 osize = htab->size; | |
| 507 olimit = oentries + osize; | |
| 508 elts = htab_elements (htab); | |
| 509 | |
| 510 /* Resize only when table after removal of unused elements is either | |
| 511 too full or too empty. */ | |
| 512 if (elts * 2 > osize || (elts * 8 < osize && osize > 32)) | |
| 513 { | |
| 514 nindex = higher_prime_index (elts * 2); | |
| 515 nsize = prime_tab[nindex].prime; | |
| 516 } | |
| 517 else | |
| 518 { | |
| 519 nindex = oindex; | |
| 520 nsize = osize; | |
| 521 } | |
| 522 | |
| 523 if (htab->alloc_with_arg_f != NULL) | |
| 524 nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize, | |
| 525 sizeof (PTR *)); | |
| 526 else | |
| 527 nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *)); | |
| 528 if (nentries == NULL) | |
| 529 return 0; | |
| 530 htab->entries = nentries; | |
| 531 htab->size = nsize; | |
| 532 htab->size_prime_index = nindex; | |
| 533 htab->n_elements -= htab->n_deleted; | |
| 534 htab->n_deleted = 0; | |
| 535 | |
| 536 p = oentries; | |
| 537 do | |
| 538 { | |
| 539 PTR x = *p; | |
| 540 | |
| 541 if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) | |
| 542 { | |
| 543 PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x)); | |
| 544 | |
| 545 *q = x; | |
| 546 } | |
| 547 | |
| 548 p++; | |
| 549 } | |
| 550 while (p < olimit); | |
| 551 | |
| 552 if (htab->free_f != NULL) | |
| 553 (*htab->free_f) (oentries); | |
| 554 else if (htab->free_with_arg_f != NULL) | |
| 555 (*htab->free_with_arg_f) (htab->alloc_arg, oentries); | |
| 556 return 1; | |
| 557 } | |
| 558 | |
| 559 /* This function searches for a hash table entry equal to the given | |
| 560 element. It cannot be used to insert or delete an element. */ | |
| 561 | |
| 562 PTR | |
| 563 htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash) | |
| 564 { | |
| 565 hashval_t index, hash2; | |
| 566 size_t size; | |
| 567 PTR entry; | |
| 568 | |
| 569 htab->searches++; | |
| 570 size = htab_size (htab); | |
| 571 index = htab_mod (hash, htab); | |
| 572 | |
| 573 entry = htab->entries[index]; | |
| 574 if (entry == HTAB_EMPTY_ENTRY | |
| 575 || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element))) | |
| 576 return entry; | |
| 577 | |
| 578 hash2 = htab_mod_m2 (hash, htab); | |
| 579 for (;;) | |
| 580 { | |
| 581 htab->collisions++; | |
| 582 index += hash2; | |
| 583 if (index >= size) | |
| 584 index -= size; | |
| 585 | |
| 586 entry = htab->entries[index]; | |
| 587 if (entry == HTAB_EMPTY_ENTRY | |
| 588 || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element))) | |
| 589 return entry; | |
| 590 } | |
| 591 } | |
| 592 | |
| 593 /* Like htab_find_slot_with_hash, but compute the hash value from the | |
| 594 element. */ | |
| 595 | |
| 596 PTR | |
| 597 htab_find (htab_t htab, const PTR element) | |
| 598 { | |
| 599 return htab_find_with_hash (htab, element, (*htab->hash_f) (element)); | |
| 600 } | |
| 601 | |
| 602 /* This function searches for a hash table slot containing an entry | |
| 603 equal to the given element. To delete an entry, call this with | |
| 604 insert=NO_INSERT, then call htab_clear_slot on the slot returned | |
| 605 (possibly after doing some checks). To insert an entry, call this | |
| 606 with insert=INSERT, then write the value you want into the returned | |
| 607 slot. When inserting an entry, NULL may be returned if memory | |
| 608 allocation fails. */ | |
| 609 | |
| 610 PTR * | |
| 611 htab_find_slot_with_hash (htab_t htab, const PTR element, | |
| 612 hashval_t hash, enum insert_option insert) | |
| 613 { | |
| 614 PTR *first_deleted_slot; | |
| 615 hashval_t index, hash2; | |
| 616 size_t size; | |
| 617 PTR entry; | |
| 618 | |
| 619 size = htab_size (htab); | |
| 620 if (insert == INSERT && size * 3 <= htab->n_elements * 4) | |
| 621 { | |
| 622 if (htab_expand (htab) == 0) | |
| 623 return NULL; | |
| 624 size = htab_size (htab); | |
| 625 } | |
| 626 | |
| 627 index = htab_mod (hash, htab); | |
| 628 | |
| 629 htab->searches++; | |
| 630 first_deleted_slot = NULL; | |
| 631 | |
| 632 entry = htab->entries[index]; | |
| 633 if (entry == HTAB_EMPTY_ENTRY) | |
| 634 goto empty_entry; | |
| 635 else if (entry == HTAB_DELETED_ENTRY) | |
| 636 first_deleted_slot = &htab->entries[index]; | |
| 637 else if ((*htab->eq_f) (entry, element)) | |
| 638 return &htab->entries[index]; | |
| 639 | |
| 640 hash2 = htab_mod_m2 (hash, htab); | |
| 641 for (;;) | |
| 642 { | |
| 643 htab->collisions++; | |
| 644 index += hash2; | |
| 645 if (index >= size) | |
| 646 index -= size; | |
| 647 | |
| 648 entry = htab->entries[index]; | |
| 649 if (entry == HTAB_EMPTY_ENTRY) | |
| 650 goto empty_entry; | |
| 651 else if (entry == HTAB_DELETED_ENTRY) | |
| 652 { | |
| 653 if (!first_deleted_slot) | |
| 654 first_deleted_slot = &htab->entries[index]; | |
| 655 } | |
| 656 else if ((*htab->eq_f) (entry, element)) | |
| 657 return &htab->entries[index]; | |
| 658 } | |
| 659 | |
| 660 empty_entry: | |
| 661 if (insert == NO_INSERT) | |
| 662 return NULL; | |
| 663 | |
| 664 if (first_deleted_slot) | |
| 665 { | |
| 666 htab->n_deleted--; | |
| 667 *first_deleted_slot = HTAB_EMPTY_ENTRY; | |
| 668 return first_deleted_slot; | |
| 669 } | |
| 670 | |
| 671 htab->n_elements++; | |
| 672 return &htab->entries[index]; | |
| 673 } | |
| 674 | |
| 675 /* Like htab_find_slot_with_hash, but compute the hash value from the | |
| 676 element. */ | |
| 677 | |
| 678 PTR * | |
| 679 htab_find_slot (htab_t htab, const PTR element, enum insert_option insert) | |
| 680 { | |
| 681 return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element), | |
| 682 insert); | |
| 683 } | |
| 684 | |
| 685 /* This function deletes an element with the given value from hash | |
| 686 table (the hash is computed from the element). If there is no matching | |
| 687 element in the hash table, this function does nothing. */ | |
| 688 | |
| 689 void | |
| 690 htab_remove_elt (htab_t htab, PTR element) | |
| 691 { | |
| 692 htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element)); | |
| 693 } | |
| 694 | |
| 695 | |
| 696 /* This function deletes an element with the given value from hash | |
| 697 table. If there is no matching element in the hash table, this | |
| 698 function does nothing. */ | |
| 699 | |
| 700 void | |
| 701 htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash) | |
| 702 { | |
| 703 PTR *slot; | |
| 704 | |
| 705 slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT); | |
| 706 if (*slot == HTAB_EMPTY_ENTRY) | |
| 707 return; | |
| 708 | |
| 709 if (htab->del_f) | |
| 710 (*htab->del_f) (*slot); | |
| 711 | |
| 712 *slot = HTAB_DELETED_ENTRY; | |
| 713 htab->n_deleted++; | |
| 714 } | |
| 715 | |
| 716 /* This function clears a specified slot in a hash table. It is | |
| 717 useful when you've already done the lookup and don't want to do it | |
| 718 again. */ | |
| 719 | |
| 720 void | |
| 721 htab_clear_slot (htab_t htab, PTR *slot) | |
| 722 { | |
| 723 if (slot < htab->entries || slot >= htab->entries + htab_size (htab) | |
| 724 || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY) | |
| 725 abort (); | |
| 726 | |
| 727 if (htab->del_f) | |
| 728 (*htab->del_f) (*slot); | |
| 729 | |
| 730 *slot = HTAB_DELETED_ENTRY; | |
| 731 htab->n_deleted++; | |
| 732 } | |
| 733 | |
| 734 /* This function scans over the entire hash table calling | |
| 735 CALLBACK for each live entry. If CALLBACK returns false, | |
| 736 the iteration stops. INFO is passed as CALLBACK's second | |
| 737 argument. */ | |
| 738 | |
| 739 void | |
| 740 htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info) | |
| 741 { | |
| 742 PTR *slot; | |
| 743 PTR *limit; | |
| 744 | |
| 745 slot = htab->entries; | |
| 746 limit = slot + htab_size (htab); | |
| 747 | |
| 748 do | |
| 749 { | |
| 750 PTR x = *slot; | |
| 751 | |
| 752 if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) | |
| 753 if (!(*callback) (slot, info)) | |
| 754 break; | |
| 755 } | |
| 756 while (++slot < limit); | |
| 757 } | |
| 758 | |
| 759 /* Like htab_traverse_noresize, but does resize the table when it is | |
| 760 too empty to improve effectivity of subsequent calls. */ | |
| 761 | |
| 762 void | |
| 763 htab_traverse (htab_t htab, htab_trav callback, PTR info) | |
| 764 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
765 size_t size = htab_size (htab); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
766 if (htab_elements (htab) * 8 < size && size > 32) |
| 0 | 767 htab_expand (htab); |
| 768 | |
| 769 htab_traverse_noresize (htab, callback, info); | |
| 770 } | |
| 771 | |
| 772 /* Return the fraction of fixed collisions during all work with given | |
| 773 hash table. */ | |
| 774 | |
| 775 double | |
| 776 htab_collisions (htab_t htab) | |
| 777 { | |
| 778 if (htab->searches == 0) | |
| 779 return 0.0; | |
| 780 | |
| 781 return (double) htab->collisions / (double) htab->searches; | |
| 782 } | |
| 783 | |
| 784 /* Hash P as a null-terminated string. | |
| 785 | |
| 786 Copied from gcc/hashtable.c. Zack had the following to say with respect | |
| 787 to applicability, though note that unlike hashtable.c, this hash table | |
| 788 implementation re-hashes rather than chain buckets. | |
| 789 | |
| 790 http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html | |
| 791 From: Zack Weinberg <zackw@panix.com> | |
| 792 Date: Fri, 17 Aug 2001 02:15:56 -0400 | |
| 793 | |
| 794 I got it by extracting all the identifiers from all the source code | |
| 795 I had lying around in mid-1999, and testing many recurrences of | |
| 796 the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either | |
| 797 prime numbers or the appropriate identity. This was the best one. | |
| 798 I don't remember exactly what constituted "best", except I was | |
| 799 looking at bucket-length distributions mostly. | |
| 800 | |
| 801 So it should be very good at hashing identifiers, but might not be | |
| 802 as good at arbitrary strings. | |
| 803 | |
| 804 I'll add that it thoroughly trounces the hash functions recommended | |
| 805 for this use at http://burtleburtle.net/bob/hash/index.html, both | |
| 806 on speed and bucket distribution. I haven't tried it against the | |
| 807 function they just started using for Perl's hashes. */ | |
| 808 | |
| 809 hashval_t | |
| 810 htab_hash_string (const PTR p) | |
| 811 { | |
| 812 const unsigned char *str = (const unsigned char *) p; | |
| 813 hashval_t r = 0; | |
| 814 unsigned char c; | |
| 815 | |
| 816 while ((c = *str++) != 0) | |
| 817 r = r * 67 + c - 113; | |
| 818 | |
| 819 return r; | |
| 820 } | |
| 821 | |
| 822 /* DERIVED FROM: | |
| 823 -------------------------------------------------------------------- | |
| 824 lookup2.c, by Bob Jenkins, December 1996, Public Domain. | |
| 825 hash(), hash2(), hash3, and mix() are externally useful functions. | |
| 826 Routines to test the hash are included if SELF_TEST is defined. | |
| 827 You can use this free for any purpose. It has no warranty. | |
| 828 -------------------------------------------------------------------- | |
| 829 */ | |
| 830 | |
| 831 /* | |
| 832 -------------------------------------------------------------------- | |
| 833 mix -- mix 3 32-bit values reversibly. | |
| 834 For every delta with one or two bit set, and the deltas of all three | |
| 835 high bits or all three low bits, whether the original value of a,b,c | |
| 836 is almost all zero or is uniformly distributed, | |
| 837 * If mix() is run forward or backward, at least 32 bits in a,b,c | |
| 838 have at least 1/4 probability of changing. | |
| 839 * If mix() is run forward, every bit of c will change between 1/3 and | |
| 840 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.) | |
| 841 mix() was built out of 36 single-cycle latency instructions in a | |
| 842 structure that could supported 2x parallelism, like so: | |
| 843 a -= b; | |
| 844 a -= c; x = (c>>13); | |
| 845 b -= c; a ^= x; | |
| 846 b -= a; x = (a<<8); | |
| 847 c -= a; b ^= x; | |
| 848 c -= b; x = (b>>13); | |
| 849 ... | |
| 850 Unfortunately, superscalar Pentiums and Sparcs can't take advantage | |
| 851 of that parallelism. They've also turned some of those single-cycle | |
| 852 latency instructions into multi-cycle latency instructions. Still, | |
| 853 this is the fastest good hash I could find. There were about 2^^68 | |
| 854 to choose from. I only looked at a billion or so. | |
| 855 -------------------------------------------------------------------- | |
| 856 */ | |
| 857 /* same, but slower, works on systems that might have 8 byte hashval_t's */ | |
| 858 #define mix(a,b,c) \ | |
| 859 { \ | |
| 860 a -= b; a -= c; a ^= (c>>13); \ | |
| 861 b -= c; b -= a; b ^= (a<< 8); \ | |
| 862 c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \ | |
| 863 a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \ | |
| 864 b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \ | |
| 865 c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \ | |
| 866 a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \ | |
| 867 b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \ | |
| 868 c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \ | |
| 869 } | |
| 870 | |
| 871 /* | |
| 872 -------------------------------------------------------------------- | |
| 873 hash() -- hash a variable-length key into a 32-bit value | |
| 874 k : the key (the unaligned variable-length array of bytes) | |
| 875 len : the length of the key, counting by bytes | |
| 876 level : can be any 4-byte value | |
| 877 Returns a 32-bit value. Every bit of the key affects every bit of | |
| 878 the return value. Every 1-bit and 2-bit delta achieves avalanche. | |
| 879 About 36+6len instructions. | |
| 880 | |
| 881 The best hash table sizes are powers of 2. There is no need to do | |
| 882 mod a prime (mod is sooo slow!). If you need less than 32 bits, | |
| 883 use a bitmask. For example, if you need only 10 bits, do | |
| 884 h = (h & hashmask(10)); | |
| 885 In which case, the hash table should have hashsize(10) elements. | |
| 886 | |
| 887 If you are hashing n strings (ub1 **)k, do it like this: | |
| 888 for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h); | |
| 889 | |
| 890 By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this | |
| 891 code any way you wish, private, educational, or commercial. It's free. | |
| 892 | |
| 893 See http://burtleburtle.net/bob/hash/evahash.html | |
| 894 Use for hash table lookup, or anything where one collision in 2^32 is | |
| 895 acceptable. Do NOT use for cryptographic purposes. | |
| 896 -------------------------------------------------------------------- | |
| 897 */ | |
| 898 | |
| 899 hashval_t | |
| 900 iterative_hash (const PTR k_in /* the key */, | |
| 901 register size_t length /* the length of the key */, | |
| 902 register hashval_t initval /* the previous hash, or | |
| 903 an arbitrary value */) | |
| 904 { | |
| 905 register const unsigned char *k = (const unsigned char *)k_in; | |
| 906 register hashval_t a,b,c,len; | |
| 907 | |
| 908 /* Set up the internal state */ | |
| 909 len = length; | |
| 910 a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */ | |
| 911 c = initval; /* the previous hash value */ | |
| 912 | |
| 913 /*---------------------------------------- handle most of the key */ | |
| 914 #ifndef WORDS_BIGENDIAN | |
| 915 /* On a little-endian machine, if the data is 4-byte aligned we can hash | |
| 916 by word for better speed. This gives nondeterministic results on | |
| 917 big-endian machines. */ | |
| 918 if (sizeof (hashval_t) == 4 && (((size_t)k)&3) == 0) | |
| 919 while (len >= 12) /* aligned */ | |
| 920 { | |
| 921 a += *(hashval_t *)(k+0); | |
| 922 b += *(hashval_t *)(k+4); | |
| 923 c += *(hashval_t *)(k+8); | |
| 924 mix(a,b,c); | |
| 925 k += 12; len -= 12; | |
| 926 } | |
| 927 else /* unaligned */ | |
| 928 #endif | |
| 929 while (len >= 12) | |
| 930 { | |
| 931 a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24)); | |
| 932 b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24)); | |
| 933 c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24)); | |
| 934 mix(a,b,c); | |
| 935 k += 12; len -= 12; | |
| 936 } | |
| 937 | |
| 938 /*------------------------------------- handle the last 11 bytes */ | |
| 939 c += length; | |
| 940 switch(len) /* all the case statements fall through */ | |
| 941 { | |
| 942 case 11: c+=((hashval_t)k[10]<<24); | |
| 943 case 10: c+=((hashval_t)k[9]<<16); | |
| 944 case 9 : c+=((hashval_t)k[8]<<8); | |
| 945 /* the first byte of c is reserved for the length */ | |
| 946 case 8 : b+=((hashval_t)k[7]<<24); | |
| 947 case 7 : b+=((hashval_t)k[6]<<16); | |
| 948 case 6 : b+=((hashval_t)k[5]<<8); | |
| 949 case 5 : b+=k[4]; | |
| 950 case 4 : a+=((hashval_t)k[3]<<24); | |
| 951 case 3 : a+=((hashval_t)k[2]<<16); | |
| 952 case 2 : a+=((hashval_t)k[1]<<8); | |
| 953 case 1 : a+=k[0]; | |
| 954 /* case 0: nothing left to add */ | |
| 955 } | |
| 956 mix(a,b,c); | |
| 957 /*-------------------------------------------- report the result */ | |
| 958 return c; | |
| 959 } |