libgomp/hashtab.h

   1 /* An expandable hash tables datatype.
   2    Copyright (C) 1999-2014 Free Software Foundation, Inc.
   3    Contributed by Vladimir Makarov <vmakarov@cygnus.com>.
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation; either version 2 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, 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.  */
  41 typedef unsigned int hashval_t;
  42
  43 static inline hashval_t htab_hash (hash_entry_type);
  44 static 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
  61 struct 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
  79 typedef struct htab *htab_t;
  80
  81 /* An enum saying whether we insert into the hash table or not.  */
  82 enum 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
  93 struct 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
 101 static 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
 138 static unsigned int
 139 higher_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
 162 static inline size_t
 163 htab_size (htab_t htab)
 164 {
 165   return htab->size;
 166 }
 167
 168 /* Return the current number of elements in given hash table. */
 169
 170 static inline size_t
 171 htab_elements (htab_t htab)
 172 {
 173   return htab->n_elements - htab->n_deleted;
 174 }
 175
 176 /* Return X % Y.  */
 177
 178 static inline hashval_t
 179 htab_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
 203 static inline hashval_t
 204 htab_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
 212 static inline hashval_t
 213 htab_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
 221 static htab_t
 222 htab_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
 246 static hash_entry_type *
 247 find_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
 280 static htab_t
 281 htab_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
 319 static hash_entry_type
 320 htab_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
 355 static hash_entry_type *
 356 htab_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
 422 static inline void
 423 htab_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
 435 static inline hashval_t
 436 hash_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 }