1/* An expandable hash tables datatype. 2 Copyright (C) 1999-2015 Free Software Foundation, Inc. 3 Contributed by Vladimir Makarov <vmakarov@cygnus.com>. 4 5This program is free software; you can redistribute it and/or modify 6it under the terms of the GNU General Public License as published by 7the Free Software Foundation; either version 2 of the License, or 8(at your option) any later version. 9 10This program is distributed in the hope that it will be useful, 11but WITHOUT ANY WARRANTY; without even the implied warranty of 12MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13GNU General Public License for more details. 14 15You should have received a copy of the GNU General Public License 16along with this program; if not, write to the Free Software 17Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA. */ 18 19/* The hash table code copied from include/hashtab.[hc] and adjusted, 20 so that the hash table entries are in the flexible array at the end 21 of the control structure, no callbacks are used and the elements in the 22 table are of the hash_entry_type type. 23 Before including this file, define hash_entry_type type and 24 htab_alloc and htab_free functions. After including it, define 25 htab_hash and htab_eq inline functions. */ 26 27/* This package implements basic hash table functionality. It is possible 28 to search for an entry, create an entry and destroy an entry. 29 30 Elements in the table are generic pointers. 31 32 The size of the table is not fixed; if the occupancy of the table 33 grows too high the hash table will be expanded. 34 35 The abstract data implementation is based on generalized Algorithm D 36 from Knuth's book "The art of computer programming". Hash table is 37 expanded by creation of new hash table and transferring elements from 38 the old table to the new table. */ 39 40/* The type for a hash code. */ 41typedef unsigned int hashval_t; 42 43static inline hashval_t htab_hash (hash_entry_type); 44static inline bool htab_eq (hash_entry_type, hash_entry_type); 45 46/* This macro defines reserved value for empty table entry. */ 47 48#define HTAB_EMPTY_ENTRY ((hash_entry_type) 0) 49 50/* This macro defines reserved value for table entry which contained 51 a deleted element. */ 52 53#define HTAB_DELETED_ENTRY ((hash_entry_type) 1) 54 55/* Hash tables are of the following type. The structure 56 (implementation) of this type is not needed for using the hash 57 tables. All work with hash table should be executed only through 58 functions mentioned below. The size of this structure is subject to 59 change. */ 60 61struct htab { 62 /* Current size (in entries) of the hash table. */ 63 size_t size; 64 65 /* Current number of elements including also deleted elements. */ 66 size_t n_elements; 67 68 /* Current number of deleted elements in the table. */ 69 size_t n_deleted; 70 71 /* Current size (in entries) of the hash table, as an index into the 72 table of primes. */ 73 unsigned int size_prime_index; 74 75 /* Table itself. */ 76 hash_entry_type entries[]; 77}; 78 79typedef struct htab *htab_t; 80 81/* An enum saying whether we insert into the hash table or not. */ 82enum insert_option {NO_INSERT, INSERT}; 83 84/* Table of primes and multiplicative inverses. 85 86 Note that these are not minimally reduced inverses. Unlike when generating 87 code to divide by a constant, we want to be able to use the same algorithm 88 all the time. All of these inverses (are implied to) have bit 32 set. 89 90 For the record, the function that computed the table is in 91 libiberty/hashtab.c. */ 92 93struct prime_ent 94{ 95 hashval_t prime; 96 hashval_t inv; 97 hashval_t inv_m2; /* inverse of prime-2 */ 98 hashval_t shift; 99}; 100 101static struct prime_ent const prime_tab[] = { 102 { 7, 0x24924925, 0x9999999b, 2 }, 103 { 13, 0x3b13b13c, 0x745d1747, 3 }, 104 { 31, 0x08421085, 0x1a7b9612, 4 }, 105 { 61, 0x0c9714fc, 0x15b1e5f8, 5 }, 106 { 127, 0x02040811, 0x0624dd30, 6 }, 107 { 251, 0x05197f7e, 0x073260a5, 7 }, 108 { 509, 0x01824366, 0x02864fc8, 8 }, 109 { 1021, 0x00c0906d, 0x014191f7, 9 }, 110 { 2039, 0x0121456f, 0x0161e69e, 10 }, 111 { 4093, 0x00300902, 0x00501908, 11 }, 112 { 8191, 0x00080041, 0x00180241, 12 }, 113 { 16381, 0x000c0091, 0x00140191, 13 }, 114 { 32749, 0x002605a5, 0x002a06e6, 14 }, 115 { 65521, 0x000f00e2, 0x00110122, 15 }, 116 { 131071, 0x00008001, 0x00018003, 16 }, 117 { 262139, 0x00014002, 0x0001c004, 17 }, 118 { 524287, 0x00002001, 0x00006001, 18 }, 119 { 1048573, 0x00003001, 0x00005001, 19 }, 120 { 2097143, 0x00004801, 0x00005801, 20 }, 121 { 4194301, 0x00000c01, 0x00001401, 21 }, 122 { 8388593, 0x00001e01, 0x00002201, 22 }, 123 { 16777213, 0x00000301, 0x00000501, 23 }, 124 { 33554393, 0x00001381, 0x00001481, 24 }, 125 { 67108859, 0x00000141, 0x000001c1, 25 }, 126 { 134217689, 0x000004e1, 0x00000521, 26 }, 127 { 268435399, 0x00000391, 0x000003b1, 27 }, 128 { 536870909, 0x00000019, 0x00000029, 28 }, 129 { 1073741789, 0x0000008d, 0x00000095, 29 }, 130 { 2147483647, 0x00000003, 0x00000007, 30 }, 131 /* Avoid "decimal constant so large it is unsigned" for 4294967291. */ 132 { 0xfffffffb, 0x00000006, 0x00000008, 31 } 133}; 134 135/* The following function returns an index into the above table of the 136 nearest prime number which is greater than N, and near a power of two. */ 137 138static unsigned int 139higher_prime_index (unsigned long n) 140{ 141 unsigned int low = 0; 142 unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]); 143 144 while (low != high) 145 { 146 unsigned int mid = low + (high - low) / 2; 147 if (n > prime_tab[mid].prime) 148 low = mid + 1; 149 else 150 high = mid; 151 } 152 153 /* If we've run out of primes, abort. */ 154 if (n > prime_tab[low].prime) 155 abort (); 156 157 return low; 158} 159 160/* Return the current size of given hash table. */ 161 162static inline size_t 163htab_size (htab_t htab) 164{ 165 return htab->size; 166} 167 168/* Return the current number of elements in given hash table. */ 169 170static inline size_t 171htab_elements (htab_t htab) 172{ 173 return htab->n_elements - htab->n_deleted; 174} 175 176/* Return X % Y. */ 177 178static inline hashval_t 179htab_mod_1 (hashval_t x, hashval_t y, hashval_t inv, int shift) 180{ 181 /* The multiplicative inverses computed above are for 32-bit types, and 182 requires that we be able to compute a highpart multiply. */ 183 if (sizeof (hashval_t) * __CHAR_BIT__ <= 32) 184 { 185 hashval_t t1, t2, t3, t4, q, r; 186 187 t1 = ((unsigned long long)x * inv) >> 32; 188 t2 = x - t1; 189 t3 = t2 >> 1; 190 t4 = t1 + t3; 191 q = t4 >> shift; 192 r = x - (q * y); 193 194 return r; 195 } 196 197 /* Otherwise just use the native division routines. */ 198 return x % y; 199} 200 201/* Compute the primary hash for HASH given HTAB's current size. */ 202 203static inline hashval_t 204htab_mod (hashval_t hash, htab_t htab) 205{ 206 const struct prime_ent *p = &prime_tab[htab->size_prime_index]; 207 return htab_mod_1 (hash, p->prime, p->inv, p->shift); 208} 209 210/* Compute the secondary hash for HASH given HTAB's current size. */ 211 212static inline hashval_t 213htab_mod_m2 (hashval_t hash, htab_t htab) 214{ 215 const struct prime_ent *p = &prime_tab[htab->size_prime_index]; 216 return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift); 217} 218 219/* Create hash table of size SIZE. */ 220 221static htab_t 222htab_create (size_t size) 223{ 224 htab_t result; 225 unsigned int size_prime_index; 226 227 size_prime_index = higher_prime_index (size); 228 size = prime_tab[size_prime_index].prime; 229 230 result = (htab_t) htab_alloc (sizeof (struct htab) 231 + size * sizeof (hash_entry_type)); 232 result->size = size; 233 result->n_elements = 0; 234 result->n_deleted = 0; 235 result->size_prime_index = size_prime_index; 236 memset (result->entries, 0, size * sizeof (hash_entry_type)); 237 return result; 238} 239 240/* Similar to htab_find_slot, but without several unwanted side effects: 241 - Does not call htab_eq when it finds an existing entry. 242 - Does not change the count of elements in the hash table. 243 This function also assumes there are no deleted entries in the table. 244 HASH is the hash value for the element to be inserted. */ 245 246static hash_entry_type * 247find_empty_slot_for_expand (htab_t htab, hashval_t hash) 248{ 249 hashval_t index = htab_mod (hash, htab); 250 size_t size = htab_size (htab); 251 hash_entry_type *slot = htab->entries + index; 252 hashval_t hash2; 253 254 if (*slot == HTAB_EMPTY_ENTRY) 255 return slot; 256 else if (*slot == HTAB_DELETED_ENTRY) 257 abort (); 258 259 hash2 = htab_mod_m2 (hash, htab); 260 for (;;) 261 { 262 index += hash2; 263 if (index >= size) 264 index -= size; 265 266 slot = htab->entries + index; 267 if (*slot == HTAB_EMPTY_ENTRY) 268 return slot; 269 else if (*slot == HTAB_DELETED_ENTRY) 270 abort (); 271 } 272} 273 274/* The following function changes size of memory allocated for the 275 entries and repeatedly inserts the table elements. The occupancy 276 of the table after the call will be about 50%. Naturally the hash 277 table must already exist. Remember also that the place of the 278 table entries is changed. */ 279 280static htab_t 281htab_expand (htab_t htab) 282{ 283 htab_t nhtab; 284 hash_entry_type *olimit; 285 hash_entry_type *p; 286 size_t osize, elts; 287 288 osize = htab->size; 289 olimit = htab->entries + osize; 290 elts = htab_elements (htab); 291 292 /* Resize only when table after removal of unused elements is either 293 too full or too empty. */ 294 if (elts * 2 > osize || (elts * 8 < osize && osize > 32)) 295 nhtab = htab_create (elts * 2); 296 else 297 nhtab = htab_create (osize - 1); 298 nhtab->n_elements = htab->n_elements - htab->n_deleted; 299 300 p = htab->entries; 301 do 302 { 303 hash_entry_type x = *p; 304 305 if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) 306 *find_empty_slot_for_expand (nhtab, htab_hash (x)) = x; 307 308 p++; 309 } 310 while (p < olimit); 311 312 htab_free (htab); 313 return nhtab; 314} 315 316/* This function searches for a hash table entry equal to the given 317 element. It cannot be used to insert or delete an element. */ 318 319static hash_entry_type 320htab_find (htab_t htab, const hash_entry_type element) 321{ 322 hashval_t index, hash2, hash = htab_hash (element); 323 size_t size; 324 hash_entry_type entry; 325 326 size = htab_size (htab); 327 index = htab_mod (hash, htab); 328 329 entry = htab->entries[index]; 330 if (entry == HTAB_EMPTY_ENTRY 331 || (entry != HTAB_DELETED_ENTRY && htab_eq (entry, element))) 332 return entry; 333 334 hash2 = htab_mod_m2 (hash, htab); 335 for (;;) 336 { 337 index += hash2; 338 if (index >= size) 339 index -= size; 340 341 entry = htab->entries[index]; 342 if (entry == HTAB_EMPTY_ENTRY 343 || (entry != HTAB_DELETED_ENTRY && htab_eq (entry, element))) 344 return entry; 345 } 346} 347 348/* This function searches for a hash table slot containing an entry 349 equal to the given element. To delete an entry, call this with 350 insert=NO_INSERT, then call htab_clear_slot on the slot returned 351 (possibly after doing some checks). To insert an entry, call this 352 with insert=INSERT, then write the value you want into the returned 353 slot. */ 354 355static hash_entry_type * 356htab_find_slot (htab_t *htabp, const hash_entry_type element, 357 enum insert_option insert) 358{ 359 hash_entry_type *first_deleted_slot; 360 hashval_t index, hash2, hash = htab_hash (element); 361 size_t size; 362 hash_entry_type entry; 363 htab_t htab = *htabp; 364 365 size = htab_size (htab); 366 if (insert == INSERT && size * 3 <= htab->n_elements * 4) 367 { 368 htab = *htabp = htab_expand (htab); 369 size = htab_size (htab); 370 } 371 372 index = htab_mod (hash, htab); 373 374 first_deleted_slot = NULL; 375 376 entry = htab->entries[index]; 377 if (entry == HTAB_EMPTY_ENTRY) 378 goto empty_entry; 379 else if (entry == HTAB_DELETED_ENTRY) 380 first_deleted_slot = &htab->entries[index]; 381 else if (htab_eq (entry, element)) 382 return &htab->entries[index]; 383 384 hash2 = htab_mod_m2 (hash, htab); 385 for (;;) 386 { 387 index += hash2; 388 if (index >= size) 389 index -= size; 390 391 entry = htab->entries[index]; 392 if (entry == HTAB_EMPTY_ENTRY) 393 goto empty_entry; 394 else if (entry == HTAB_DELETED_ENTRY) 395 { 396 if (!first_deleted_slot) 397 first_deleted_slot = &htab->entries[index]; 398 } 399 else if (htab_eq (entry, element)) 400 return &htab->entries[index]; 401 } 402 403 empty_entry: 404 if (insert == NO_INSERT) 405 return NULL; 406 407 if (first_deleted_slot) 408 { 409 htab->n_deleted--; 410 *first_deleted_slot = HTAB_EMPTY_ENTRY; 411 return first_deleted_slot; 412 } 413 414 htab->n_elements++; 415 return &htab->entries[index]; 416} 417 418/* This function clears a specified slot in a hash table. It is 419 useful when you've already done the lookup and don't want to do it 420 again. */ 421 422static inline void 423htab_clear_slot (htab_t htab, hash_entry_type *slot) 424{ 425 if (slot < htab->entries || slot >= htab->entries + htab_size (htab) 426 || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY) 427 abort (); 428 429 *slot = HTAB_DELETED_ENTRY; 430 htab->n_deleted++; 431} 432 433/* Returns a hash code for pointer P. Simplified version of evahash */ 434 435static inline hashval_t 436hash_pointer (const void *p) 437{ 438 uintptr_t v = (uintptr_t) p; 439 if (sizeof (v) > sizeof (hashval_t)) 440 v ^= v >> (sizeof (uintptr_t) / 2 * __CHAR_BIT__); 441 return v; 442} 443