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