libgomp/hashtab.h

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