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 htab_t in hashtab.h.
  25
  26
  27    INTRODUCTION TO TYPES
  28
  29    Users of the hash table generally need to be aware of three types.
  30
  31       1. The type being placed into the hash table.  This type is called
  32       the value type.
  33
  34       2. The type used to describe how to handle the value type within
  35       the hash table.  This descriptor type provides the hash table with
  36       several things.
  37
  38          - A typedef named 'value_type' to the value type (from above).
  39
  40          - A static member function named 'hash' that takes a value_type
  41          pointer and returns a hashval_t value.
  42
  43          - A typedef named 'compare_type' that is used to test when an value
  44          is found.  This type is the comparison type.  Usually, it will be the
  45          same as value_type.  If it is not the same type, you must generally
  46          explicitly compute hash values and pass them to the hash table.
  47
  48          - A static member function named 'equal' that takes a value_type
  49          pointer and a compare_type pointer, and returns a bool.
  50
  51          - A static function named 'remove' that takes an value_type pointer
  52          and frees the memory allocated by it.  This function is used when
  53          individual elements of the table need to be disposed of (e.g.,
  54          when deleting a hash table, removing elements from the table, etc).
  55
  56       3. The type of the hash table itself.  (More later.)
  57
  58    In very special circumstances, users may need to know about a fourth type.
  59
  60       4. The template type used to describe how hash table memory
  61       is allocated.  This type is called the allocator type.  It is
  62       parameterized on the value type.  It provides four functions.
  63
  64          - A static member function named 'control_alloc'.  This function
  65          allocates the control data blocks for the table.
  66
  67          - A static member function named 'control_free'.  This function
  68          frees the control data blocks for the table.
  69
  70          - A static member function named 'data_alloc'.  This function
  71          allocates the data elements in the table.
  72
  73          - A static member function named 'data_free'.  This function
  74          deallocates the data elements in the table.
  75
  76    Hash table are instantiated with two type arguments.
  77
  78       * The descriptor type, (2) above.
  79
  80       * The allocator type, (4) above.  In general, you will not need to
  81       provide your own allocator type.  By default, hash tables will use
  82       the class template xcallocator, which uses malloc/free for allocation.
  83
  84
  85    DEFINING A DESCRIPTOR TYPE
  86
  87    The first task in using the hash table is to describe the element type.
  88    We compose this into a few steps.
  89
  90       1. Decide on a removal policy for values stored in the table.
  91          This header provides class templates for the two most common
  92          policies.
  93
  94          * typed_free_remove implements the static 'remove' member function
  95          by calling free().
  96
  97          * typed_noop_remove implements the static 'remove' member function
  98          by doing nothing.
  99
 100          You can use these policies by simply deriving the descriptor type
 101          from one of those class template, with the appropriate argument.
 102
 103          Otherwise, you need to write the static 'remove' member function
 104          in the descriptor class.
 105
 106       2. Choose a hash function.  Write the static 'hash' member function.
 107
 108       3. Choose an equality testing function.  In most cases, its two
 109       arguments will be value_type pointers.  If not, the first argument must
 110       be a value_type pointer, and the second argument a compare_type pointer.
 111
 112
 113    AN EXAMPLE DESCRIPTOR TYPE
 114
 115    Suppose you want to put some_type into the hash table.  You could define
 116    the descriptor type as follows.
 117
 118       struct some_type_hasher : typed_noop_remove <some_type>
 119       // Deriving from typed_noop_remove means that we get a 'remove' that does
 120       // nothing.  This choice is good for raw values.
 121       {
 122         typedef some_type value_type;
 123         typedef some_type compare_type;
 124         static inline hashval_t hash (const value_type *);
 125         static inline bool equal (const value_type *, const compare_type *);
 126       };
 127
 128       inline hashval_t
 129       some_type_hasher::hash (const value_type *e)
 130       { ... compute and return a hash value for E ... }
 131
 132       inline bool
 133       some_type_hasher::equal (const value_type *p1, const compare_type *p2)
 134       { ... compare P1 vs P2.  Return true if they are the 'same' ... }
 135
 136
 137    AN EXAMPLE HASH_TABLE DECLARATION
 138
 139    To instantiate a hash table for some_type:
 140
 141       hash_table <some_type_hasher> some_type_hash_table;
 142
 143    There is no need to mention some_type directly, as the hash table will
 144    obtain it using some_type_hasher::value_type.
 145
 146    You can then used any of the functions in hash_table's public interface.
 147    See hash_table for details.  The interface is very similar to libiberty's
 148    htab_t.
 149
 150
 151    EASY DESCRIPTORS FOR POINTERS
 152
 153    The class template pointer_hash provides everything you need to hash
 154    pointers (as opposed to what they point to).  So, to instantiate a hash
 155    table over pointers to whatever_type,
 156
 157       hash_table <pointer_hash <whatever_type>> whatever_type_hash_table;
 158
 159 */
 160
 161
 162 #ifndef TYPED_HASHTAB_H
 163 #define TYPED_HASHTAB_H
 164
 165 #include "hashtab.h"
 166
 167
 168 /* The ordinary memory allocator.  */
 169 /* FIXME (crowl): This allocator may be extracted for wider sharing later.  */
 170
 171 template <typename Type>
 172 struct xcallocator
 173 {
 174   static Type *control_alloc (size_t count);
 175   static Type *data_alloc (size_t count);
 176   static void control_free (Type *memory);
 177   static void data_free (Type *memory);
 178 };
 179
 180
 181 /* Allocate memory for COUNT control blocks.  */
 182
 183 template <typename Type>
 184 inline Type *
 185 xcallocator <Type>::control_alloc (size_t count)
 186 {
 187   return static_cast <Type *> (xcalloc (count, sizeof (Type)));
 188 }
 189
 190
 191 /* Allocate memory for COUNT data blocks.  */
 192
 193 template <typename Type>
 194 inline Type *
 195 xcallocator <Type>::data_alloc (size_t count)
 196 {
 197   return static_cast <Type *> (xcalloc (count, sizeof (Type)));
 198 }
 199
 200
 201 /* Free memory for control blocks.  */
 202
 203 template <typename Type>
 204 inline void
 205 xcallocator <Type>::control_free (Type *memory)
 206 {
 207   return ::free (memory);
 208 }
 209
 210
 211 /* Free memory for data blocks.  */
 212
 213 template <typename Type>
 214 inline void
 215 xcallocator <Type>::data_free (Type *memory)
 216 {
 217   return ::free (memory);
 218 }
 219
 220
 221 /* Helpful type for removing with free.  */
 222
 223 template <typename Type>
 224 struct typed_free_remove
 225 {
 226   static inline void remove (Type *p);
 227 };
 228
 229
 230 /* Remove with free.  */
 231
 232 template <typename Type>
 233 inline void
 234 typed_free_remove <Type>::remove (Type *p)
 235 {
 236   free (p);
 237 }
 238
 239
 240 /* Helpful type for a no-op remove.  */
 241
 242 template <typename Type>
 243 struct typed_noop_remove
 244 {
 245   static inline void remove (Type *p);
 246 };
 247
 248
 249 /* Remove doing nothing.  */
 250
 251 template <typename Type>
 252 inline void
 253 typed_noop_remove <Type>::remove (Type *p ATTRIBUTE_UNUSED)
 254 {
 255 }
 256
 257
 258 /* Pointer hash with a no-op remove method.  */
 259
 260 template <typename Type>
 261 struct pointer_hash : typed_noop_remove <Type>
 262 {
 263   typedef Type value_type;
 264   typedef Type compare_type;
 265
 266   static inline hashval_t
 267   hash (const value_type *);
 268
 269   static inline int
 270   equal (const value_type *existing, const compare_type *candidate);
 271 };
 272
 273 template <typename Type>
 274 inline hashval_t
 275 pointer_hash <Type>::hash (const value_type *candidate)
 276 {
 277   /* This is a really poor hash function, but it is what the current code uses,
 278      so I am reusing it to avoid an additional axis in testing.  */
 279   return (hashval_t) ((intptr_t)candidate >> 3);
 280 }
 281
 282 template <typename Type>
 283 inline int
 284 pointer_hash <Type>::equal (const value_type *existing,
 285                            const compare_type *candidate)
 286 {
 287   return existing == candidate;
 288 }
 289
 290
 291 /* Table of primes and their inversion information.  */
 292
 293 struct prime_ent
 294 {
 295   hashval_t prime;
 296   hashval_t inv;
 297   hashval_t inv_m2;     /* inverse of prime-2 */
 298   hashval_t shift;
 299 };
 300
 301 extern struct prime_ent const prime_tab[];
 302
 303
 304 /* Functions for computing hash table indexes.  */
 305
 306 extern unsigned int hash_table_higher_prime_index (unsigned long n);
 307 extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index);
 308 extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index);
 309
 310
 311 /* Internal implementation type.  */
 312
 313 template <typename T>
 314 struct hash_table_control
 315 {
 316   /* Table itself.  */
 317   T **entries;
 318
 319   /* Current size (in entries) of the hash table.  */
 320   size_t size;
 321
 322   /* Current number of elements including also deleted elements.  */
 323   size_t n_elements;
 324
 325   /* Current number of deleted elements in the table.  */
 326   size_t n_deleted;
 327
 328   /* The following member is used for debugging. Its value is number
 329      of all calls of `htab_find_slot' for the hash table. */
 330   unsigned int searches;
 331
 332   /* The following member is used for debugging.  Its value is number
 333      of collisions fixed for time of work with the hash table. */
 334   unsigned int collisions;
 335
 336   /* Current size (in entries) of the hash table, as an index into the
 337      table of primes.  */
 338   unsigned int size_prime_index;
 339 };
 340
 341
 342 /* User-facing hash table type.
 343
 344    The table stores elements of type Descriptor::value_type.
 345
 346    It hashes values with the hash member function.
 347      The table currently works with relatively weak hash functions.
 348      Use typed_pointer_hash <Value> when hashing pointers instead of objects.
 349
 350    It compares elements with the equal member function.
 351      Two elements with the same hash may not be equal.
 352      Use typed_pointer_equal <Value> when hashing pointers instead of objects.
 353
 354    It removes elements with the remove member function.
 355      This feature is useful for freeing memory.
 356      Derive from typed_null_remove <Value> when not freeing objects.
 357      Derive from typed_free_remove <Value> when doing a simple object free.
 358
 359    Specify the template Allocator to allocate and free memory.
 360      The default is xcallocator.
 361
 362 */
 363
 364 template <typename Descriptor,
 365           template <typename Type> class Allocator = xcallocator>
 366 class hash_table
 367 {
 368 public:
 369   typedef typename Descriptor::value_type value_type;
 370   typedef typename Descriptor::compare_type compare_type;
 371
 372 private:
 373   hash_table_control <value_type> *htab;
 374
 375   value_type **find_empty_slot_for_expand (hashval_t hash);
 376   void expand ();
 377
 378 public:
 379   hash_table ();
 380   void create (size_t initial_slots);
 381   bool is_created ();
 382   void dispose ();
 383   value_type *find (const compare_type *comparable);
 384   value_type *find_with_hash (const compare_type *comparable, hashval_t hash);
 385   value_type **find_slot (const compare_type *comparable,
 386                           enum insert_option insert);
 387   value_type **find_slot_with_hash (const compare_type *comparable,
 388                                     hashval_t hash, enum insert_option insert);
 389   void empty ();
 390   void clear_slot (value_type **slot);
 391   void remove_elt (const compare_type *comparable);
 392   void remove_elt_with_hash (const compare_type *comparable, hashval_t hash);
 393   size_t size();
 394   size_t elements();
 395   double collisions();
 396
 397   template <typename Argument,
 398             int (*Callback) (value_type **slot, Argument argument)>
 399   void traverse_noresize (Argument argument);
 400
 401   template <typename Argument,
 402             int (*Callback) (value_type **slot, Argument argument)>
 403   void traverse (Argument argument);
 404 };
 405
 406
 407 /* Construct the hash table.  The only useful operation next is create.  */
 408
 409 template <typename Descriptor,
 410           template <typename Type> class Allocator>
 411 inline
 412 hash_table <Descriptor, Allocator>::hash_table ()
 413 : htab (NULL)
 414 {
 415 }
 416
 417
 418 /* See if the table has been created, as opposed to constructed.  */
 419
 420 template <typename Descriptor,
 421           template <typename Type> class Allocator>
 422 inline bool
 423 hash_table <Descriptor, Allocator>::is_created ()
 424 {
 425   return htab != NULL;
 426 }
 427
 428
 429 /* Like find_with_hash, but compute the hash value from the element.  */
 430
 431 template <typename Descriptor,
 432           template <typename Type> class Allocator>
 433 inline typename Descriptor::value_type *
 434 hash_table <Descriptor, Allocator>::find (const compare_type *comparable)
 435 {
 436   return find_with_hash (comparable, Descriptor::hash (comparable));
 437 }
 438
 439
 440 /* Like find_slot_with_hash, but compute the hash value from the element.  */
 441
 442 template <typename Descriptor,
 443           template <typename Type> class Allocator>
 444 inline typename Descriptor::value_type **
 445 hash_table <Descriptor, Allocator>
 446 ::find_slot (const compare_type *comparable, enum insert_option insert)
 447 {
 448   return find_slot_with_hash (comparable, Descriptor::hash (comparable), insert);
 449 }
 450
 451
 452 /* Like remove_elt_with_hash, but compute the hash value from the element.  */
 453
 454 template <typename Descriptor,
 455           template <typename Type> class Allocator>
 456 inline void
 457 hash_table <Descriptor, Allocator>::remove_elt (const compare_type *comparable)
 458 {
 459   remove_elt_with_hash (comparable, Descriptor::hash (comparable));
 460 }
 461
 462
 463 /* Return the current size of this hash table.  */
 464
 465 template <typename Descriptor,
 466           template <typename Type> class Allocator>
 467 inline size_t
 468 hash_table <Descriptor, Allocator>::size()
 469 {
 470   return htab->size;
 471 }
 472
 473
 474 /* Return the current number of elements in this hash table. */
 475
 476 template <typename Descriptor,
 477           template <typename Type> class Allocator>
 478 inline size_t
 479 hash_table <Descriptor, Allocator>::elements()
 480 {
 481   return htab->n_elements - htab->n_deleted;
 482 }
 483
 484
 485   /* Return the fraction of fixed collisions during all work with given
 486      hash table. */
 487
 488 template <typename Descriptor,
 489           template <typename Type> class Allocator>
 490 inline double
 491 hash_table <Descriptor, Allocator>::collisions()
 492 {
 493   if (htab->searches == 0)
 494     return 0.0;
 495
 496   return static_cast <double> (htab->collisions) / htab->searches;
 497 }
 498
 499
 500 /* Create a hash table with at least the given number of INITIAL_SLOTS.  */
 501
 502 template <typename Descriptor,
 503           template <typename Type> class Allocator>
 504 void
 505 hash_table <Descriptor, Allocator>::create (size_t size)
 506 {
 507   unsigned int size_prime_index;
 508
 509   size_prime_index = hash_table_higher_prime_index (size);
 510   size = prime_tab[size_prime_index].prime;
 511
 512   htab = Allocator <hash_table_control <value_type> > ::control_alloc (1);
 513   gcc_assert (htab != NULL);
 514   htab->entries = Allocator <value_type*> ::data_alloc (size);
 515   gcc_assert (htab->entries != NULL);
 516   htab->size = size;
 517   htab->size_prime_index = size_prime_index;
 518 }
 519
 520
 521 /* Dispose of a hash table.  Free all memory and return this hash table to
 522    the non-created state.  Naturally the hash table must already exist.  */
 523
 524 template <typename Descriptor,
 525           template <typename Type> class Allocator>
 526 void
 527 hash_table <Descriptor, Allocator>::dispose ()
 528 {
 529   size_t size = htab->size;
 530   value_type **entries = htab->entries;
 531
 532   for (int i = size - 1; i >= 0; i--)
 533     if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
 534       Descriptor::remove (entries[i]);
 535
 536   Allocator <value_type *> ::data_free (entries);
 537   Allocator <hash_table_control <value_type> > ::control_free (htab);
 538   htab = NULL;
 539 }
 540
 541
 542 /* Similar to find_slot, but without several unwanted side effects:
 543     - Does not call equal when it finds an existing entry.
 544     - Does not change the count of elements/searches/collisions in the
 545       hash table.
 546    This function also assumes there are no deleted entries in the table.
 547    HASH is the hash value for the element to be inserted.  */
 548
 549 template <typename Descriptor,
 550           template <typename Type> class Allocator>
 551 typename Descriptor::value_type **
 552 hash_table <Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash)
 553 {
 554   hashval_t index = hash_table_mod1 (hash, htab->size_prime_index);
 555   size_t size = htab->size;
 556   value_type **slot = htab->entries + index;
 557   hashval_t hash2;
 558
 559   if (*slot == HTAB_EMPTY_ENTRY)
 560     return slot;
 561   else if (*slot == HTAB_DELETED_ENTRY)
 562     abort ();
 563
 564   hash2 = hash_table_mod2 (hash, htab->size_prime_index);
 565   for (;;)
 566     {
 567       index += hash2;
 568       if (index >= size)
 569         index -= size;
 570
 571       slot = htab->entries + index;
 572       if (*slot == HTAB_EMPTY_ENTRY)
 573         return slot;
 574       else if (*slot == HTAB_DELETED_ENTRY)
 575         abort ();
 576     }
 577 }
 578
 579
 580 /* The following function changes size of memory allocated for the
 581    entries and repeatedly inserts the table elements.  The occupancy
 582    of the table after the call will be about 50%.  Naturally the hash
 583    table must already exist.  Remember also that the place of the
 584    table entries is changed.  If memory allocation fails, this function
 585    will abort.  */
 586
 587 template <typename Descriptor,
 588           template <typename Type> class Allocator>
 589 void
 590 hash_table <Descriptor, Allocator>::expand ()
 591 {
 592   value_type **oentries;
 593   value_type **olimit;
 594   value_type **p;
 595   value_type **nentries;
 596   size_t nsize, osize, elts;
 597   unsigned int oindex, nindex;
 598
 599   oentries = htab->entries;
 600   oindex = htab->size_prime_index;
 601   osize = htab->size;
 602   olimit = oentries + osize;
 603   elts = elements ();
 604
 605   /* Resize only when table after removal of unused elements is either
 606      too full or too empty.  */
 607   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
 608     {
 609       nindex = hash_table_higher_prime_index (elts * 2);
 610       nsize = prime_tab[nindex].prime;
 611     }
 612   else
 613     {
 614       nindex = oindex;
 615       nsize = osize;
 616     }
 617
 618   nentries = Allocator <value_type *> ::data_alloc (nsize);
 619   gcc_assert (nentries != NULL);
 620   htab->entries = nentries;
 621   htab->size = nsize;
 622   htab->size_prime_index = nindex;
 623   htab->n_elements -= htab->n_deleted;
 624   htab->n_deleted = 0;
 625
 626   p = oentries;
 627   do
 628     {
 629       value_type *x = *p;
 630
 631       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
 632         {
 633           value_type **q = find_empty_slot_for_expand (Descriptor::hash (x));
 634
 635           *q = x;
 636         }
 637
 638       p++;
 639     }
 640   while (p < olimit);
 641
 642   Allocator <value_type *> ::data_free (oentries);
 643 }
 644
 645
 646 /* This function searches for a hash table entry equal to the given
 647    COMPARABLE element starting with the given HASH value.  It cannot
 648    be used to insert or delete an element. */
 649
 650 template <typename Descriptor,
 651           template <typename Type> class Allocator>
 652 typename Descriptor::value_type *
 653 hash_table <Descriptor, Allocator>
 654 ::find_with_hash (const compare_type *comparable, hashval_t hash)
 655 {
 656   hashval_t index, hash2;
 657   size_t size;
 658   value_type *entry;
 659
 660   htab->searches++;
 661   size = htab->size;
 662   index = hash_table_mod1 (hash, htab->size_prime_index);
 663
 664   entry = htab->entries[index];
 665   if (entry == HTAB_EMPTY_ENTRY
 666       || (entry != HTAB_DELETED_ENTRY && Descriptor::equal (entry, comparable)))
 667     return entry;
 668
 669   hash2 = hash_table_mod2 (hash, htab->size_prime_index);
 670   for (;;)
 671     {
 672       htab->collisions++;
 673       index += hash2;
 674       if (index >= size)
 675         index -= size;
 676
 677       entry = htab->entries[index];
 678       if (entry == HTAB_EMPTY_ENTRY
 679           || (entry != HTAB_DELETED_ENTRY
 680               && Descriptor::equal (entry, comparable)))
 681         return entry;
 682     }
 683 }
 684
 685
 686 /* This function searches for a hash table slot containing an entry
 687    equal to the given COMPARABLE element and starting with the given
 688    HASH.  To delete an entry, call this with insert=NO_INSERT, then
 689    call clear_slot on the slot returned (possibly after doing some
 690    checks).  To insert an entry, call this with insert=INSERT, then
 691    write the value you want into the returned slot.  When inserting an
 692    entry, NULL may be returned if memory allocation fails. */
 693
 694 template <typename Descriptor,
 695           template <typename Type> class Allocator>
 696 typename Descriptor::value_type **
 697 hash_table <Descriptor, Allocator>
 698 ::find_slot_with_hash (const compare_type *comparable, hashval_t hash,
 699                        enum insert_option insert)
 700 {
 701   value_type **first_deleted_slot;
 702   hashval_t index, hash2;
 703   size_t size;
 704   value_type *entry;
 705
 706   size = htab->size;
 707   if (insert == INSERT && size * 3 <= htab->n_elements * 4)
 708     {
 709       expand ();
 710       size = htab->size;
 711     }
 712
 713   index = hash_table_mod1 (hash, htab->size_prime_index);
 714
 715   htab->searches++;
 716   first_deleted_slot = NULL;
 717
 718   entry = htab->entries[index];
 719   if (entry == HTAB_EMPTY_ENTRY)
 720     goto empty_entry;
 721   else if (entry == HTAB_DELETED_ENTRY)
 722     first_deleted_slot = &htab->entries[index];
 723   else if (Descriptor::equal (entry, comparable))
 724     return &htab->entries[index];
 725
 726   hash2 = hash_table_mod2 (hash, htab->size_prime_index);
 727   for (;;)
 728     {
 729       htab->collisions++;
 730       index += hash2;
 731       if (index >= size)
 732         index -= size;
 733
 734       entry = htab->entries[index];
 735       if (entry == HTAB_EMPTY_ENTRY)
 736         goto empty_entry;
 737       else if (entry == HTAB_DELETED_ENTRY)
 738         {
 739           if (!first_deleted_slot)
 740             first_deleted_slot = &htab->entries[index];
 741         }
 742       else if (Descriptor::equal (entry, comparable))
 743         return &htab->entries[index];
 744     }
 745
 746  empty_entry:
 747   if (insert == NO_INSERT)
 748     return NULL;
 749
 750   if (first_deleted_slot)
 751     {
 752       htab->n_deleted--;
 753       *first_deleted_slot = static_cast <value_type *> (HTAB_EMPTY_ENTRY);
 754       return first_deleted_slot;
 755     }
 756
 757   htab->n_elements++;
 758   return &htab->entries[index];
 759 }
 760
 761
 762 /* This function clears all entries in the given hash table.  */
 763
 764 template <typename Descriptor,
 765           template <typename Type> class Allocator>
 766 void
 767 hash_table <Descriptor, Allocator>::empty ()
 768 {
 769   size_t size = htab->size;
 770   value_type **entries = htab->entries;
 771   int i;
 772
 773   for (i = size - 1; i >= 0; i--)
 774     if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
 775       Descriptor::remove (entries[i]);
 776
 777   /* Instead of clearing megabyte, downsize the table.  */
 778   if (size > 1024*1024 / sizeof (PTR))
 779     {
 780       int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
 781       int nsize = prime_tab[nindex].prime;
 782
 783       Allocator <value_type *> ::data_free (htab->entries);
 784       htab->entries = Allocator <value_type *> ::data_alloc (nsize);
 785       htab->size = nsize;
 786       htab->size_prime_index = nindex;
 787     }
 788   else
 789     memset (entries, 0, size * sizeof (value_type *));
 790   htab->n_deleted = 0;
 791   htab->n_elements = 0;
 792 }
 793
 794
 795 /* This function clears a specified SLOT in a hash table.  It is
 796    useful when you've already done the lookup and don't want to do it
 797    again. */
 798
 799 template <typename Descriptor,
 800           template <typename Type> class Allocator>
 801 void
 802 hash_table <Descriptor, Allocator>::clear_slot (value_type **slot)
 803 {
 804   if (slot < htab->entries || slot >= htab->entries + htab->size
 805       || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
 806     abort ();
 807
 808   Descriptor::remove (*slot);
 809
 810   *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY);
 811   htab->n_deleted++;
 812 }
 813
 814
 815 /* This function deletes an element with the given COMPARABLE value
 816    from hash table starting with the given HASH.  If there is no
 817    matching element in the hash table, this function does nothing. */
 818
 819 template <typename Descriptor,
 820           template <typename Type> class Allocator>
 821 void
 822 hash_table <Descriptor, Allocator>
 823 ::remove_elt_with_hash (const compare_type *comparable, hashval_t hash)
 824 {
 825   value_type **slot;
 826
 827   slot = find_slot_with_hash (comparable, hash, NO_INSERT);
 828   if (*slot == HTAB_EMPTY_ENTRY)
 829     return;
 830
 831   Descriptor::remove (*slot);
 832
 833   *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY);
 834   htab->n_deleted++;
 835 }
 836
 837
 838 /* This function scans over the entire hash table calling CALLBACK for
 839    each live entry.  If CALLBACK returns false, the iteration stops.
 840    ARGUMENT is passed as CALLBACK's second argument. */
 841
 842 template <typename Descriptor,
 843           template <typename Type> class Allocator>
 844 template <typename Argument,
 845           int (*Callback) (typename Descriptor::value_type **slot, Argument argument)>
 846 void
 847 hash_table <Descriptor, Allocator>::traverse_noresize (Argument argument)
 848 {
 849   value_type **slot;
 850   value_type **limit;
 851
 852   slot = htab->entries;
 853   limit = slot + htab->size;
 854
 855   do
 856     {
 857       value_type *x = *slot;
 858
 859       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
 860         if (! Callback (slot, argument))
 861           break;
 862     }
 863   while (++slot < limit);
 864 }
 865
 866
 867 /* Like traverse_noresize, but does resize the table when it is too empty
 868    to improve effectivity of subsequent calls.  */
 869
 870 template <typename Descriptor,
 871           template <typename Type> class Allocator>
 872 template <typename Argument,
 873           int (*Callback) (typename Descriptor::value_type **slot,
 874                            Argument argument)>
 875 void
 876 hash_table <Descriptor, Allocator>::traverse (Argument argument)
 877 {
 878   size_t size = htab->size;
 879   if (elements () * 8 < size && size > 32)
 880     expand ();
 881
 882   traverse_noresize <Argument, Callback> (argument);
 883 }
 884
 885 #endif /* TYPED_HASHTAB_H */