gcc/hash-table.h

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