gcc/hash-table.h

   1 /* A type-safe hash table template.
   2    Copyright (C) 2012
   3    Free Software Foundation, Inc.
   4    Contributed by Lawrence Crowl <crowl@google.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22
  23 /* This file implements a typed hash table.
  24    The implementation borrows from libiberty's hashtab.  */
  25
  26
  27 #ifndef TYPED_HASHTAB_H
  28 #define TYPED_HASHTAB_H
  29
  30 #include "hashtab.h"
  31
  32
  33 /* The ordinary memory allocator.  */
  34 /* FIXME (crowl): This allocator may be extracted for wider sharing later.  */
  35
  36 template <typename Type>
  37 struct xcallocator
  38 {
  39   static Type *control_alloc (size_t count);
  40   static Type *data_alloc (size_t count);
  41   static void control_free (Type *memory);
  42   static void data_free (Type *memory);
  43 };
  44
  45
  46 /* Allocate memory for COUNT control blocks.  */
  47
  48 template <typename Type>
  49 inline Type *
  50 xcallocator <Type>::control_alloc (size_t count)
  51 {
  52   return static_cast <Type *> (xcalloc (count, sizeof (Type)));
  53 }
  54
  55
  56 /* Allocate memory for COUNT data blocks.  */
  57
  58 template <typename Type>
  59 inline Type *
  60 xcallocator <Type>::data_alloc (size_t count)
  61 {
  62   return static_cast <Type *> (xcalloc (count, sizeof (Type)));
  63 }
  64
  65
  66 /* Free memory for control blocks.  */
  67
  68 template <typename Type>
  69 inline void
  70 xcallocator <Type>::control_free (Type *memory)
  71 {
  72   return ::free (memory);
  73 }
  74
  75
  76 /* Free memory for data blocks.  */
  77
  78 template <typename Type>
  79 inline void
  80 xcallocator <Type>::data_free (Type *memory)
  81 {
  82   return ::free (memory);
  83 }
  84
  85
  86 /* Remove method dispatching to free.  */
  87
  88 template <typename Element>
  89 struct typed_free_remove
  90 {
  91   static inline void remove (Element *p) { free (p); }
  92 };
  93
  94 /* No-op remove method.  */
  95
  96 template <typename Element>
  97 struct typed_noop_remove
  98 {
  99   static inline void remove (Element *) {}
 100 };
 101
 102
 103 /* Pointer hash with a no-op remove method.  */
 104
 105 template <typename Element>
 106 struct pointer_hash : typed_noop_remove <Element>
 107 {
 108   typedef Element T;
 109
 110   static inline hashval_t
 111   hash (const T *);
 112
 113   static inline int
 114   equal (const T *existing, const T * candidate);
 115 };
 116
 117 template <typename Element>
 118 inline hashval_t
 119 pointer_hash<Element>::hash (const T *candidate)
 120 {
 121   /* This is a really poor hash function, but it is what the current code uses,
 122      so I am reusing it to avoid an additional axis in testing.  */
 123   return (hashval_t) ((intptr_t)candidate >> 3);
 124 }
 125
 126 template <typename Element>
 127 inline int
 128 pointer_hash<Element>::equal (const T *existing,
 129                               const T *candidate)
 130 {
 131   return existing == candidate;
 132 }
 133
 134
 135 /* Table of primes and their inversion information.  */
 136
 137 struct prime_ent
 138 {
 139   hashval_t prime;
 140   hashval_t inv;
 141   hashval_t inv_m2;     /* inverse of prime-2 */
 142   hashval_t shift;
 143 };
 144
 145 extern struct prime_ent const prime_tab[];
 146
 147
 148 /* Functions for computing hash table indexes.  */
 149
 150 extern unsigned int hash_table_higher_prime_index (unsigned long n);
 151 extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index);
 152 extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index);
 153
 154
 155 /* Internal implementation type.  */
 156
 157 template <typename T>
 158 struct hash_table_control
 159 {
 160   /* Table itself.  */
 161   T **entries;
 162
 163   /* Current size (in entries) of the hash table.  */
 164   size_t size;
 165
 166   /* Current number of elements including also deleted elements.  */
 167   size_t n_elements;
 168
 169   /* Current number of deleted elements in the table.  */
 170   size_t n_deleted;
 171
 172   /* The following member is used for debugging. Its value is number
 173      of all calls of `htab_find_slot' for the hash table. */
 174   unsigned int searches;
 175
 176   /* The following member is used for debugging.  Its value is number
 177      of collisions fixed for time of work with the hash table. */
 178   unsigned int collisions;
 179
 180   /* Current size (in entries) of the hash table, as an index into the
 181      table of primes.  */
 182   unsigned int size_prime_index;
 183 };
 184
 185
 186 /* User-facing hash table type.
 187
 188    The table stores elements of type Element.
 189
 190    It hashes elements with the hash function.
 191      The table currently works with relatively weak hash functions.
 192      Use typed_pointer_hash <Element> when hashing pointers instead of objects.
 193
 194    It compares elements with the equal function.
 195      Two elements with the same hash may not be equal.
 196      Use typed_pointer_equal <Element> when hashing pointers instead of objects.
 197
 198    It removes elements with the remove function.
 199      This feature is useful for freeing memory.
 200      Use typed_null_remove <Element> when not freeing objects.
 201      Use typed_free_remove <Element> when doing a simple object free.
 202
 203    Use the Allocator template to allocate and free memory.
 204      The default is xcallocator.
 205
 206 */
 207
 208 template <typename Descr,
 209           template <typename Type> class Allocator = xcallocator>
 210 class hash_table
 211 {
 212 public:
 213   typedef typename Descr::T T;
 214
 215 private:
 216   hash_table_control <T> *htab;
 217
 218   T **find_empty_slot_for_expand (hashval_t hash);
 219   void expand ();
 220
 221 public:
 222   hash_table ();
 223   void create (size_t initial_slots);
 224   bool is_created ();
 225   void dispose ();
 226   T *find (const T *comparable);
 227   T *find_with_hash (const T *comparable, hashval_t hash);
 228   T **find_slot (const T *comparable, enum insert_option insert);
 229   T **find_slot_with_hash (const T *comparable, hashval_t hash,
 230                                    enum insert_option insert);
 231   void empty ();
 232   void clear_slot (T **slot);
 233   void remove_elt (const T *comparable);
 234   void remove_elt_with_hash (const T *comparable, hashval_t hash);
 235   size_t size();
 236   size_t elements();
 237   double collisions();
 238
 239   template <typename Argument,
 240             int (*Callback) (T **slot, Argument argument)>
 241   void traverse_noresize (Argument argument);
 242
 243   template <typename Argument,
 244             int (*Callback) (T **slot, Argument argument)>
 245   void traverse (Argument argument);
 246 };
 247
 248
 249 /* Construct the hash table.  The only useful operation next is create.  */
 250
 251 template <typename Descr,
 252           template <typename Type> class Allocator>
 253 inline
 254 hash_table <Descr, Allocator>::hash_table ()
 255 : htab (NULL)
 256 {
 257 }
 258
 259
 260 /* See if the table has been created, as opposed to constructed.  */
 261
 262 template <typename Descr,
 263           template <typename Type> class Allocator>
 264 inline bool
 265 hash_table <Descr, Allocator>::is_created ()
 266 {
 267   return htab != NULL;
 268 }
 269
 270
 271 /* Like find_with_hash, but compute the hash value from the element.  */
 272
 273 template <typename Descr,
 274           template <typename Type> class Allocator>
 275 inline typename Descr::T *
 276 hash_table <Descr, Allocator>::find (const T *comparable)
 277 {
 278   return find_with_hash (comparable, Descr::hash (comparable));
 279 }
 280
 281
 282 /* Like find_slot_with_hash, but compute the hash value from the element.  */
 283
 284 template <typename Descr,
 285           template <typename Type> class Allocator>
 286 inline typename Descr::T **
 287 hash_table <Descr, Allocator>
 288 ::find_slot (const T *comparable, enum insert_option insert)
 289 {
 290   return find_slot_with_hash (comparable, Descr::hash (comparable), insert);
 291 }
 292
 293
 294 /* Like remove_elt_with_hash, but compute the hash value from the element.  */
 295
 296 template <typename Descr,
 297           template <typename Type> class Allocator>
 298 inline void
 299 hash_table <Descr, Allocator>
 300 ::remove_elt (const T *comparable)
 301 {
 302   remove_elt_with_hash (comparable, Descr::hash (comparable));
 303 }
 304
 305
 306 /* Return the current size of this hash table.  */
 307
 308 template <typename Descr,
 309           template <typename Type> class Allocator>
 310 inline size_t
 311 hash_table <Descr, Allocator>::size()
 312 {
 313   return htab->size;
 314 }
 315
 316
 317 /* Return the current number of elements in this hash table. */
 318
 319 template <typename Descr,
 320           template <typename Type> class Allocator>
 321 inline size_t
 322 hash_table <Descr, Allocator>::elements()
 323 {
 324   return htab->n_elements - htab->n_deleted;
 325 }
 326
 327
 328   /* Return the fraction of fixed collisions during all work with given
 329      hash table. */
 330
 331 template <typename Descr,
 332           template <typename Type> class Allocator>
 333 inline double
 334 hash_table <Descr, Allocator>::collisions()
 335 {
 336   if (htab->searches == 0)
 337     return 0.0;
 338
 339   return static_cast <double> (htab->collisions) / htab->searches;
 340 }
 341
 342
 343 /* Create a hash table with at least the given number of INITIAL_SLOTS.  */
 344
 345 template <typename Descr,
 346           template <typename Type> class Allocator>
 347 void
 348 hash_table <Descr, Allocator>::create (size_t size)
 349 {
 350   unsigned int size_prime_index;
 351
 352   size_prime_index = hash_table_higher_prime_index (size);
 353   size = prime_tab[size_prime_index].prime;
 354
 355   htab = Allocator <hash_table_control <T> > ::control_alloc (1);
 356   gcc_assert (htab != NULL);
 357   htab->entries = Allocator <T*> ::data_alloc (size);
 358   gcc_assert (htab->entries != NULL);
 359   htab->size = size;
 360   htab->size_prime_index = size_prime_index;
 361 }
 362
 363
 364 /* Dispose of a hash table.  Free all memory and return this hash table to
 365    the non-created state.  Naturally the hash table must already exist.  */
 366
 367 template <typename Descr,
 368           template <typename Type> class Allocator>
 369 void
 370 hash_table <Descr, Allocator>::dispose ()
 371 {
 372   size_t size = htab->size;
 373   T **entries = htab->entries;
 374
 375   for (int i = size - 1; i >= 0; i--)
 376     if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
 377       Descr::remove (entries[i]);
 378
 379   Allocator <T *> ::data_free (entries);
 380   Allocator <hash_table_control <T> > ::control_free (htab);
 381   htab = NULL;
 382 }
 383
 384
 385 /* Similar to find_slot, but without several unwanted side effects:
 386     - Does not call equal when it finds an existing entry.
 387     - Does not change the count of elements/searches/collisions in the
 388       hash table.
 389    This function also assumes there are no deleted entries in the table.
 390    HASH is the hash value for the element to be inserted.  */
 391
 392 template <typename Descr,
 393           template <typename Type> class Allocator>
 394 typename Descr::T **
 395 hash_table <Descr, Allocator>
 396 ::find_empty_slot_for_expand (hashval_t hash)
 397 {
 398   hashval_t index = hash_table_mod1 (hash, htab->size_prime_index);
 399   size_t size = htab->size;
 400   T **slot = htab->entries + index;
 401   hashval_t hash2;
 402
 403   if (*slot == HTAB_EMPTY_ENTRY)
 404     return slot;
 405   else if (*slot == HTAB_DELETED_ENTRY)
 406     abort ();
 407
 408   hash2 = hash_table_mod2 (hash, htab->size_prime_index);
 409   for (;;)
 410     {
 411       index += hash2;
 412       if (index >= size)
 413         index -= size;
 414
 415       slot = htab->entries + index;
 416       if (*slot == HTAB_EMPTY_ENTRY)
 417         return slot;
 418       else if (*slot == HTAB_DELETED_ENTRY)
 419         abort ();
 420     }
 421 }
 422
 423
 424 /* The following function changes size of memory allocated for the
 425    entries and repeatedly inserts the table elements.  The occupancy
 426    of the table after the call will be about 50%.  Naturally the hash
 427    table must already exist.  Remember also that the place of the
 428    table entries is changed.  If memory allocation fails, this function
 429    will abort.  */
 430
 431 template <typename Descr,
 432           template <typename Type> class Allocator>
 433 void
 434 hash_table <Descr, Allocator>::expand ()
 435 {
 436   T **oentries;
 437   T **olimit;
 438   T **p;
 439   T **nentries;
 440   size_t nsize, osize, elts;
 441   unsigned int oindex, nindex;
 442
 443   oentries = htab->entries;
 444   oindex = htab->size_prime_index;
 445   osize = htab->size;
 446   olimit = oentries + osize;
 447   elts = elements ();
 448
 449   /* Resize only when table after removal of unused elements is either
 450      too full or too empty.  */
 451   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
 452     {
 453       nindex = hash_table_higher_prime_index (elts * 2);
 454       nsize = prime_tab[nindex].prime;
 455     }
 456   else
 457     {
 458       nindex = oindex;
 459       nsize = osize;
 460     }
 461
 462   nentries = Allocator <T *> ::data_alloc (nsize);
 463   gcc_assert (nentries != NULL);
 464   htab->entries = nentries;
 465   htab->size = nsize;
 466   htab->size_prime_index = nindex;
 467   htab->n_elements -= htab->n_deleted;
 468   htab->n_deleted = 0;
 469
 470   p = oentries;
 471   do
 472     {
 473       T *x = *p;
 474
 475       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
 476         {
 477           T **q = find_empty_slot_for_expand (Descr::hash (x));
 478
 479           *q = x;
 480         }
 481
 482       p++;
 483     }
 484   while (p < olimit);
 485
 486   Allocator <T *> ::data_free (oentries);
 487 }
 488
 489
 490 /* This function searches for a hash table entry equal to the given
 491    COMPARABLE element starting with the given HASH value.  It cannot
 492    be used to insert or delete an element. */
 493
 494 template <typename Descr,
 495           template <typename Type> class Allocator>
 496 typename Descr::T *
 497 hash_table <Descr, Allocator>
 498 ::find_with_hash (const T *comparable, hashval_t hash)
 499 {
 500   hashval_t index, hash2;
 501   size_t size;
 502   T *entry;
 503
 504   htab->searches++;
 505   size = htab->size;
 506   index = hash_table_mod1 (hash, htab->size_prime_index);
 507
 508   entry = htab->entries[index];
 509   if (entry == HTAB_EMPTY_ENTRY
 510       || (entry != HTAB_DELETED_ENTRY && Descr::equal (entry, comparable)))
 511     return entry;
 512
 513   hash2 = hash_table_mod2 (hash, htab->size_prime_index);
 514   for (;;)
 515     {
 516       htab->collisions++;
 517       index += hash2;
 518       if (index >= size)
 519         index -= size;
 520
 521       entry = htab->entries[index];
 522       if (entry == HTAB_EMPTY_ENTRY
 523           || (entry != HTAB_DELETED_ENTRY && Descr::equal (entry, comparable)))
 524         return entry;
 525     }
 526 }
 527
 528
 529 /* This function searches for a hash table slot containing an entry
 530    equal to the given COMPARABLE element and starting with the given
 531    HASH.  To delete an entry, call this with insert=NO_INSERT, then
 532    call clear_slot on the slot returned (possibly after doing some
 533    checks).  To insert an entry, call this with insert=INSERT, then
 534    write the value you want into the returned slot.  When inserting an
 535    entry, NULL may be returned if memory allocation fails. */
 536
 537 template <typename Descr,
 538           template <typename Type> class Allocator>
 539 typename Descr::T **
 540 hash_table <Descr, Allocator>
 541 ::find_slot_with_hash (const T *comparable, hashval_t hash,
 542                        enum insert_option insert)
 543 {
 544   T **first_deleted_slot;
 545   hashval_t index, hash2;
 546   size_t size;
 547   T *entry;
 548
 549   size = htab->size;
 550   if (insert == INSERT && size * 3 <= htab->n_elements * 4)
 551     {
 552       expand ();
 553       size = htab->size;
 554     }
 555
 556   index = hash_table_mod1 (hash, htab->size_prime_index);
 557
 558   htab->searches++;
 559   first_deleted_slot = NULL;
 560
 561   entry = htab->entries[index];
 562   if (entry == HTAB_EMPTY_ENTRY)
 563     goto empty_entry;
 564   else if (entry == HTAB_DELETED_ENTRY)
 565     first_deleted_slot = &htab->entries[index];
 566   else if (Descr::equal (entry, comparable))
 567     return &htab->entries[index];
 568
 569   hash2 = hash_table_mod2 (hash, htab->size_prime_index);
 570   for (;;)
 571     {
 572       htab->collisions++;
 573       index += hash2;
 574       if (index >= size)
 575         index -= size;
 576
 577       entry = htab->entries[index];
 578       if (entry == HTAB_EMPTY_ENTRY)
 579         goto empty_entry;
 580       else if (entry == HTAB_DELETED_ENTRY)
 581         {
 582           if (!first_deleted_slot)
 583             first_deleted_slot = &htab->entries[index];
 584         }
 585       else if (Descr::equal (entry, comparable))
 586         return &htab->entries[index];
 587     }
 588
 589  empty_entry:
 590   if (insert == NO_INSERT)
 591     return NULL;
 592
 593   if (first_deleted_slot)
 594     {
 595       htab->n_deleted--;
 596       *first_deleted_slot = static_cast <T *> (HTAB_EMPTY_ENTRY);
 597       return first_deleted_slot;
 598     }
 599
 600   htab->n_elements++;
 601   return &htab->entries[index];
 602 }
 603
 604
 605 /* This function clears all entries in the given hash table.  */
 606
 607 template <typename Descr,
 608           template <typename Type> class Allocator>
 609 void
 610 hash_table <Descr, Allocator>::empty ()
 611 {
 612   size_t size = htab->size;
 613   T **entries = htab->entries;
 614   int i;
 615
 616   for (i = size - 1; i >= 0; i--)
 617     if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
 618       Descr::remove (entries[i]);
 619
 620   /* Instead of clearing megabyte, downsize the table.  */
 621   if (size > 1024*1024 / sizeof (PTR))
 622     {
 623       int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
 624       int nsize = prime_tab[nindex].prime;
 625
 626       Allocator <T *> ::data_free (htab->entries);
 627       htab->entries = Allocator <T *> ::data_alloc (nsize);
 628       htab->size = nsize;
 629       htab->size_prime_index = nindex;
 630     }
 631   else
 632     memset (entries, 0, size * sizeof (T *));
 633   htab->n_deleted = 0;
 634   htab->n_elements = 0;
 635 }
 636
 637
 638 /* This function clears a specified SLOT in a hash table.  It is
 639    useful when you've already done the lookup and don't want to do it
 640    again. */
 641
 642 template <typename Descr,
 643           template <typename Type> class Allocator>
 644 void
 645 hash_table <Descr, Allocator>
 646 ::clear_slot (T **slot)
 647 {
 648   if (slot < htab->entries || slot >= htab->entries + htab->size
 649       || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
 650     abort ();
 651
 652   Descr::remove (*slot);
 653
 654   *slot = static_cast <T *> (HTAB_DELETED_ENTRY);
 655   htab->n_deleted++;
 656 }
 657
 658
 659 /* This function deletes an element with the given COMPARABLE value
 660    from hash table starting with the given HASH.  If there is no
 661    matching element in the hash table, this function does nothing. */
 662
 663 template <typename Descr,
 664           template <typename Type> class Allocator>
 665 void
 666 hash_table <Descr, Allocator>
 667 ::remove_elt_with_hash (const T *comparable, hashval_t hash)
 668 {
 669   T **slot;
 670
 671   slot = find_slot_with_hash (comparable, hash, NO_INSERT);
 672   if (*slot == HTAB_EMPTY_ENTRY)
 673     return;
 674
 675   Descr::remove (*slot);
 676
 677   *slot = static_cast <T *> (HTAB_DELETED_ENTRY);
 678   htab->n_deleted++;
 679 }
 680
 681
 682 /* This function scans over the entire hash table calling CALLBACK for
 683    each live entry.  If CALLBACK returns false, the iteration stops.
 684    ARGUMENT is passed as CALLBACK's second argument. */
 685
 686 template <typename Descr,
 687           template <typename Type> class Allocator>
 688 template <typename Argument,
 689           int (*Callback) (typename Descr::T **slot, Argument argument)>
 690 void
 691 hash_table <Descr, Allocator>
 692 ::traverse_noresize (Argument argument)
 693 {
 694   T **slot;
 695   T **limit;
 696
 697   slot = htab->entries;
 698   limit = slot + htab->size;
 699
 700   do
 701     {
 702       T *x = *slot;
 703
 704       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
 705         if (! Callback (slot, argument))
 706           break;
 707     }
 708   while (++slot < limit);
 709 }
 710
 711
 712 /* Like traverse_noresize, but does resize the table when it is too empty
 713    to improve effectivity of subsequent calls.  */
 714
 715 template <typename Descr,
 716           template <typename Type> class Allocator>
 717 template <typename Argument,
 718           int (*Callback) (typename Descr::T **slot, Argument argument)>
 719 void
 720 hash_table <Descr, Allocator>
 721 ::traverse (Argument argument)
 722 {
 723   size_t size = htab->size;
 724   if (elements () * 8 < size && size > 32)
 725     expand ();
 726
 727   traverse_noresize <Argument, Callback> (argument);
 728 }
 729
 730 #endif /* TYPED_HASHTAB_H */