libgomp/hashtab.h

   1 /* An expandable hash tables datatype.
   2    Copyright (C) 1999-2021 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 static inline htab_t
 228 htab_clear (htab_t htab)
 229 {
 230   htab->n_elements = 0;
 231   htab->n_deleted = 0;
 232   memset (htab->entries, 0, htab->size * sizeof (hash_entry_type));
 233   return htab;
 234 }
 235
 236 /* Create hash table of size SIZE.  */
 237
 238 static htab_t
 239 htab_create (size_t size)
 240 {
 241   htab_t result;
 242   unsigned int size_prime_index;
 243
 244   size_prime_index = higher_prime_index (size);
 245   size = prime_tab[size_prime_index].prime;
 246
 247   result = (htab_t) htab_alloc (sizeof (struct htab)
 248                                 + size * sizeof (hash_entry_type));
 249   result->size = size;
 250   result->size_prime_index = size_prime_index;
 251   return htab_clear (result);
 252 }
 253
 254 /* Similar to htab_find_slot, but without several unwanted side effects:
 255     - Does not call htab_eq when it finds an existing entry.
 256     - Does not change the count of elements in the hash table.
 257    This function also assumes there are no deleted entries in the table.
 258    HASH is the hash value for the element to be inserted.  */
 259
 260 static hash_entry_type *
 261 find_empty_slot_for_expand (htab_t htab, hashval_t hash)
 262 {
 263   hashval_t index = htab_mod (hash, htab);
 264   size_t size = htab_size (htab);
 265   hash_entry_type *slot = htab->entries + index;
 266   hashval_t hash2;
 267
 268   if (*slot == HTAB_EMPTY_ENTRY)
 269     return slot;
 270   else if (*slot == HTAB_DELETED_ENTRY)
 271     abort ();
 272
 273   hash2 = htab_mod_m2 (hash, htab);
 274   for (;;)
 275     {
 276       index += hash2;
 277       if (index >= size)
 278         index -= size;
 279
 280       slot = htab->entries + index;
 281       if (*slot == HTAB_EMPTY_ENTRY)
 282         return slot;
 283       else if (*slot == HTAB_DELETED_ENTRY)
 284         abort ();
 285     }
 286 }
 287
 288 /* The following function changes size of memory allocated for the
 289    entries and repeatedly inserts the table elements.  The occupancy
 290    of the table after the call will be about 50%.  Naturally the hash
 291    table must already exist.  Remember also that the place of the
 292    table entries is changed.  */
 293
 294 static htab_t
 295 htab_expand (htab_t htab)
 296 {
 297   htab_t nhtab;
 298   hash_entry_type *olimit;
 299   hash_entry_type *p;
 300   size_t osize, elts;
 301
 302   osize = htab->size;
 303   olimit = htab->entries + osize;
 304   elts = htab_elements (htab);
 305
 306   /* Resize only when table after removal of unused elements is either
 307      too full or too empty.  */
 308   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
 309     nhtab = htab_create (elts * 2);
 310   else
 311     nhtab = htab_create (osize - 1);
 312   nhtab->n_elements = htab->n_elements - htab->n_deleted;
 313
 314   p = htab->entries;
 315   do
 316     {
 317       hash_entry_type x = *p;
 318
 319       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
 320         *find_empty_slot_for_expand (nhtab, htab_hash (x)) = x;
 321
 322       p++;
 323     }
 324   while (p < olimit);
 325
 326   htab_free (htab);
 327   return nhtab;
 328 }
 329
 330 /* This function searches for a hash table entry equal to the given
 331    element.  It cannot be used to insert or delete an element.  */
 332
 333 static hash_entry_type
 334 htab_find (htab_t htab, const hash_entry_type element)
 335 {
 336   hashval_t index, hash2, hash = htab_hash (element);
 337   size_t size;
 338   hash_entry_type entry;
 339
 340   size = htab_size (htab);
 341   index = htab_mod (hash, htab);
 342
 343   entry = htab->entries[index];
 344   if (entry == HTAB_EMPTY_ENTRY
 345       || (entry != HTAB_DELETED_ENTRY && htab_eq (entry, element)))
 346     return entry;
 347
 348   hash2 = htab_mod_m2 (hash, htab);
 349   for (;;)
 350     {
 351       index += hash2;
 352       if (index >= size)
 353         index -= size;
 354
 355       entry = htab->entries[index];
 356       if (entry == HTAB_EMPTY_ENTRY
 357           || (entry != HTAB_DELETED_ENTRY && htab_eq (entry, element)))
 358         return entry;
 359     }
 360 }
 361
 362 /* This function searches for a hash table slot containing an entry
 363    equal to the given element.  To delete an entry, call this with
 364    insert=NO_INSERT, then call htab_clear_slot on the slot returned
 365    (possibly after doing some checks).  To insert an entry, call this
 366    with insert=INSERT, then write the value you want into the returned
 367    slot.  */
 368
 369 static hash_entry_type *
 370 htab_find_slot (htab_t *htabp, const hash_entry_type element,
 371                 enum insert_option insert)
 372 {
 373   hash_entry_type *first_deleted_slot;
 374   hashval_t index, hash2, hash = htab_hash (element);
 375   size_t size;
 376   hash_entry_type entry;
 377   htab_t htab = *htabp;
 378
 379   size = htab_size (htab);
 380   if (insert == INSERT && size * 3 <= htab->n_elements * 4)
 381     {
 382       htab = *htabp = htab_expand (htab);
 383       size = htab_size (htab);
 384     }
 385
 386   index = htab_mod (hash, htab);
 387
 388   first_deleted_slot = NULL;
 389
 390   entry = htab->entries[index];
 391   if (entry == HTAB_EMPTY_ENTRY)
 392     goto empty_entry;
 393   else if (entry == HTAB_DELETED_ENTRY)
 394     first_deleted_slot = &htab->entries[index];
 395   else if (htab_eq (entry, element))
 396     return &htab->entries[index];
 397
 398   hash2 = htab_mod_m2 (hash, htab);
 399   for (;;)
 400     {
 401       index += hash2;
 402       if (index >= size)
 403         index -= size;
 404
 405       entry = htab->entries[index];
 406       if (entry == HTAB_EMPTY_ENTRY)
 407         goto empty_entry;
 408       else if (entry == HTAB_DELETED_ENTRY)
 409         {
 410           if (!first_deleted_slot)
 411             first_deleted_slot = &htab->entries[index];
 412         }
 413       else if (htab_eq (entry, element))
 414         return &htab->entries[index];
 415     }
 416
 417  empty_entry:
 418   if (insert == NO_INSERT)
 419     return NULL;
 420
 421   if (first_deleted_slot)
 422     {
 423       htab->n_deleted--;
 424       *first_deleted_slot = HTAB_EMPTY_ENTRY;
 425       return first_deleted_slot;
 426     }
 427
 428   htab->n_elements++;
 429   return &htab->entries[index];
 430 }
 431
 432 /* This function clears a specified slot in a hash table.  It is
 433    useful when you've already done the lookup and don't want to do it
 434    again.  */
 435
 436 static inline void
 437 htab_clear_slot (htab_t htab, hash_entry_type *slot)
 438 {
 439   if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
 440       || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
 441     abort ();
 442
 443   *slot = HTAB_DELETED_ENTRY;
 444   htab->n_deleted++;
 445 }
 446
 447 /* Returns a hash code for pointer P. Simplified version of evahash */
 448
 449 static inline hashval_t
 450 hash_pointer (const void *p)
 451 {
 452   uintptr_t v = (uintptr_t) p;
 453   if (sizeof (v) > sizeof (hashval_t))
 454     v ^= v >> (sizeof (uintptr_t) / 2 * __CHAR_BIT__);
 455   return v;
 456 }