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