gcc/hash-table.h

   1 /* A type-safe hash table template.
   2    Copyright (C) 2012-2014 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 'data_alloc'.  This function
  64          allocates the data elements in the table.
  65
  66          - A static member function named 'data_free'.  This function
  67          deallocates the data elements in the table.
  68
  69    Hash table are instantiated with two type arguments.
  70
  71       * The descriptor type, (2) above.
  72
  73       * The allocator type, (4) above.  In general, you will not need to
  74       provide your own allocator type.  By default, hash tables will use
  75       the class template xcallocator, which uses malloc/free for allocation.
  76
  77
  78    DEFINING A DESCRIPTOR TYPE
  79
  80    The first task in using the hash table is to describe the element type.
  81    We compose this into a few steps.
  82
  83       1. Decide on a removal policy for values stored in the table.
  84          This header provides class templates for the two most common
  85          policies.
  86
  87          * typed_free_remove implements the static 'remove' member function
  88          by calling free().
  89
  90          * typed_noop_remove implements the static 'remove' member function
  91          by doing nothing.
  92
  93          You can use these policies by simply deriving the descriptor type
  94          from one of those class template, with the appropriate argument.
  95
  96          Otherwise, you need to write the static 'remove' member function
  97          in the descriptor class.
  98
  99       2. Choose a hash function.  Write the static 'hash' member function.
 100
 101       3. Choose an equality testing function.  In most cases, its two
 102       arguments will be value_type pointers.  If not, the first argument must
 103       be a value_type pointer, and the second argument a compare_type pointer.
 104
 105
 106    AN EXAMPLE DESCRIPTOR TYPE
 107
 108    Suppose you want to put some_type into the hash table.  You could define
 109    the descriptor type as follows.
 110
 111       struct some_type_hasher : typed_noop_remove <some_type>
 112       // Deriving from typed_noop_remove means that we get a 'remove' that does
 113       // nothing.  This choice is good for raw values.
 114       {
 115         typedef some_type value_type;
 116         typedef some_type compare_type;
 117         static inline hashval_t hash (const value_type *);
 118         static inline bool equal (const value_type *, const compare_type *);
 119       };
 120
 121       inline hashval_t
 122       some_type_hasher::hash (const value_type *e)
 123       { ... compute and return a hash value for E ... }
 124
 125       inline bool
 126       some_type_hasher::equal (const value_type *p1, const compare_type *p2)
 127       { ... compare P1 vs P2.  Return true if they are the 'same' ... }
 128
 129
 130    AN EXAMPLE HASH_TABLE DECLARATION
 131
 132    To instantiate a hash table for some_type:
 133
 134       hash_table <some_type_hasher> some_type_hash_table;
 135
 136    There is no need to mention some_type directly, as the hash table will
 137    obtain it using some_type_hasher::value_type.
 138
 139    You can then used any of the functions in hash_table's public interface.
 140    See hash_table for details.  The interface is very similar to libiberty's
 141    htab_t.
 142
 143
 144    EASY DESCRIPTORS FOR POINTERS
 145
 146    The class template pointer_hash provides everything you need to hash
 147    pointers (as opposed to what they point to).  So, to instantiate a hash
 148    table over pointers to whatever_type,
 149
 150       hash_table <pointer_hash <whatever_type>> whatever_type_hash_table;
 151
 152
 153    HASH TABLE ITERATORS
 154
 155    The hash table provides standard C++ iterators.  For example, consider a
 156    hash table of some_info.  We wish to consume each element of the table:
 157
 158       extern void consume (some_info *);
 159
 160    We define a convenience typedef and the hash table:
 161
 162       typedef hash_table <some_info_hasher> info_table_type;
 163       info_table_type info_table;
 164
 165    Then we write the loop in typical C++ style:
 166
 167       for (info_table_type::iterator iter = info_table.begin ();
 168            iter != info_table.end ();
 169            ++iter)
 170         if ((*iter).status == INFO_READY)
 171           consume (&*iter);
 172
 173    Or with common sub-expression elimination:
 174
 175       for (info_table_type::iterator iter = info_table.begin ();
 176            iter != info_table.end ();
 177            ++iter)
 178         {
 179           some_info &elem = *iter;
 180           if (elem.status == INFO_READY)
 181             consume (&elem);
 182         }
 183
 184    One can also use a more typical GCC style:
 185
 186       typedef some_info *some_info_p;
 187       some_info *elem_ptr;
 188       info_table_type::iterator iter;
 189       FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
 190         if (elem_ptr->status == INFO_READY)
 191           consume (elem_ptr);
 192
 193 */
 194
 195
 196 #ifndef TYPED_HASHTAB_H
 197 #define TYPED_HASHTAB_H
 198
 199 #include "ggc.h"
 200 #include "hashtab.h"
 201 #include <new>
 202
 203 template<typename, typename, typename> class hash_map;
 204 template<typename, typename> class hash_set;
 205
 206 /* The ordinary memory allocator.  */
 207 /* FIXME (crowl): This allocator may be extracted for wider sharing later.  */
 208
 209 template <typename Type>
 210 struct xcallocator
 211 {
 212   static Type *data_alloc (size_t count);
 213   static void data_free (Type *memory);
 214 };
 215
 216
 217 /* Allocate memory for COUNT data blocks.  */
 218
 219 template <typename Type>
 220 inline Type *
 221 xcallocator <Type>::data_alloc (size_t count)
 222 {
 223   return static_cast <Type *> (xcalloc (count, sizeof (Type)));
 224 }
 225
 226
 227 /* Free memory for data blocks.  */
 228
 229 template <typename Type>
 230 inline void
 231 xcallocator <Type>::data_free (Type *memory)
 232 {
 233   return ::free (memory);
 234 }
 235
 236
 237 /* Helpful type for removing with free.  */
 238
 239 template <typename Type>
 240 struct typed_free_remove
 241 {
 242   static inline void remove (Type *p);
 243 };
 244
 245
 246 /* Remove with free.  */
 247
 248 template <typename Type>
 249 inline void
 250 typed_free_remove <Type>::remove (Type *p)
 251 {
 252   free (p);
 253 }
 254
 255
 256 /* Helpful type for a no-op remove.  */
 257
 258 template <typename Type>
 259 struct typed_noop_remove
 260 {
 261   static inline void remove (Type *p);
 262 };
 263
 264
 265 /* Remove doing nothing.  */
 266
 267 template <typename Type>
 268 inline void
 269 typed_noop_remove <Type>::remove (Type *p ATTRIBUTE_UNUSED)
 270 {
 271 }
 272
 273
 274 /* Pointer hash with a no-op remove method.  */
 275
 276 template <typename Type>
 277 struct pointer_hash : typed_noop_remove <Type>
 278 {
 279   typedef Type *value_type;
 280   typedef Type *compare_type;
 281   typedef int store_values_directly;
 282
 283   static inline hashval_t hash (const value_type &);
 284
 285   static inline bool equal (const value_type &existing, const compare_type &candidate);
 286 };
 287
 288 template <typename Type>
 289 inline hashval_t
 290 pointer_hash <Type>::hash (const value_type &candidate)
 291 {
 292   /* This is a really poor hash function, but it is what the current code uses,
 293      so I am reusing it to avoid an additional axis in testing.  */
 294   return (hashval_t) ((intptr_t)candidate >> 3);
 295 }
 296
 297 template <typename Type>
 298 inline bool
 299 pointer_hash <Type>::equal (const value_type &existing,
 300                            const compare_type &candidate)
 301 {
 302   return existing == candidate;
 303 }
 304
 305 /* Hasher for entry in gc memory.  */
 306
 307 template<typename T>
 308 struct ggc_hasher
 309 {
 310   typedef T value_type;
 311   typedef T compare_type;
 312   typedef int store_values_directly;
 313
 314   static void remove (T) {}
 315
 316   static void
 317   ggc_mx (T p)
 318   {
 319     extern void gt_ggc_mx (T &);
 320     gt_ggc_mx (p);
 321   }
 322
 323   static void
 324   pch_nx (T &p)
 325   {
 326   extern void gt_pch_nx (T &);
 327   gt_pch_nx (p);
 328   }
 329
 330   static void
 331   pch_nx (T &p, gt_pointer_operator op, void *cookie)
 332   {
 333     op (&p, cookie);
 334   }
 335 };
 336
 337
 338 /* Table of primes and their inversion information.  */
 339
 340 struct prime_ent
 341 {
 342   hashval_t prime;
 343   hashval_t inv;
 344   hashval_t inv_m2;     /* inverse of prime-2 */
 345   hashval_t shift;
 346 };
 347
 348 extern struct prime_ent const prime_tab[];
 349
 350
 351 /* Functions for computing hash table indexes.  */
 352
 353 extern unsigned int hash_table_higher_prime_index (unsigned long n);
 354 extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index);
 355 extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index);
 356
 357 /* The below is some template meta programming to decide if we should use the
 358    hash table partial specialization that directly stores value_type instead of
 359    pointers to value_type.  If the Descriptor type defines the type
 360    Descriptor::store_values_directly then values are stored directly otherwise
 361    pointers to them are stored.  */
 362 template<typename T> struct notype { typedef void type; };
 363
 364 template<typename T, typename = void>
 365 struct storage_tester
 366 {
 367   static const bool value = false;
 368 };
 369
 370 template<typename T>
 371 struct storage_tester<T, typename notype<typename
 372                                          T::store_values_directly>::type>
 373 {
 374   static const bool value = true;
 375 };
 376
 377  template<typename Traits>
 378  struct has_is_deleted
 379 {
 380   template<typename U, bool (*)(U &)> struct helper {};
 381   template<typename U> static char test (helper<U, U::is_deleted> *);
 382   template<typename U> static int test (...);
 383   static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
 384 };
 385
 386 template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value>
 387 struct is_deleted_helper
 388 {
 389   static inline bool
 390   call (Type &v)
 391   {
 392     return Traits::is_deleted (v);
 393   }
 394 };
 395
 396 template<typename Type, typename Traits>
 397 struct is_deleted_helper<Type *, Traits, false>
 398 {
 399   static inline bool
 400   call (Type *v)
 401   {
 402     return v == HTAB_DELETED_ENTRY;
 403   }
 404 };
 405
 406  template<typename Traits>
 407  struct has_is_empty
 408 {
 409   template<typename U, bool (*)(U &)> struct helper {};
 410   template<typename U> static char test (helper<U, U::is_empty> *);
 411   template<typename U> static int test (...);
 412   static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
 413 };
 414
 415 template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value>
 416 struct is_empty_helper
 417 {
 418   static inline bool
 419   call (Type &v)
 420   {
 421     return Traits::is_empty (v);
 422   }
 423 };
 424
 425 template<typename Type, typename Traits>
 426 struct is_empty_helper<Type *, Traits, false>
 427 {
 428   static inline bool
 429   call (Type *v)
 430   {
 431     return v == HTAB_EMPTY_ENTRY;
 432   }
 433 };
 434
 435  template<typename Traits>
 436  struct has_mark_deleted
 437 {
 438   template<typename U, void (*)(U &)> struct helper {};
 439   template<typename U> static char test (helper<U, U::mark_deleted> *);
 440   template<typename U> static int test (...);
 441   static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
 442 };
 443
 444 template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value>
 445 struct mark_deleted_helper
 446 {
 447   static inline void
 448   call (Type &v)
 449   {
 450     Traits::mark_deleted (v);
 451   }
 452 };
 453
 454 template<typename Type, typename Traits>
 455 struct mark_deleted_helper<Type *, Traits, false>
 456 {
 457   static inline void
 458   call (Type *&v)
 459   {
 460     v = static_cast<Type *> (HTAB_DELETED_ENTRY);
 461   }
 462 };
 463
 464  template<typename Traits>
 465  struct has_mark_empty
 466 {
 467   template<typename U, void (*)(U &)> struct helper {};
 468   template<typename U> static char test (helper<U, U::mark_empty> *);
 469   template<typename U> static int test (...);
 470   static const bool value = sizeof (test<Traits> (0)) == sizeof (char);
 471 };
 472
 473 template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value>
 474 struct mark_empty_helper
 475 {
 476   static inline void
 477   call (Type &v)
 478   {
 479     Traits::mark_empty (v);
 480   }
 481 };
 482
 483 template<typename Type, typename Traits>
 484 struct mark_empty_helper<Type *, Traits, false>
 485 {
 486   static inline void
 487   call (Type *&v)
 488   {
 489     v = static_cast<Type *> (HTAB_EMPTY_ENTRY);
 490   }
 491 };
 492
 493 /* User-facing hash table type.
 494
 495    The table stores elements of type Descriptor::value_type, or pointers to
 496    objects of type value_type if the descriptor does not define the type
 497    store_values_directly.
 498
 499    It hashes values with the hash member function.
 500      The table currently works with relatively weak hash functions.
 501      Use typed_pointer_hash <Value> when hashing pointers instead of objects.
 502
 503    It compares elements with the equal member function.
 504      Two elements with the same hash may not be equal.
 505      Use typed_pointer_equal <Value> when hashing pointers instead of objects.
 506
 507    It removes elements with the remove member function.
 508      This feature is useful for freeing memory.
 509      Derive from typed_null_remove <Value> when not freeing objects.
 510      Derive from typed_free_remove <Value> when doing a simple object free.
 511
 512    Specify the template Allocator to allocate and free memory.
 513      The default is xcallocator.
 514
 515      Storage is an implementation detail and should not be used outside the
 516      hash table code.
 517
 518 */
 519 template <typename Descriptor,
 520          template<typename Type> class Allocator= xcallocator,
 521          bool Storage = storage_tester<Descriptor>::value>
 522 class hash_table
 523 {
 524 };
 525
 526 template <typename Descriptor,
 527          template<typename Type> class Allocator>
 528 class hash_table<Descriptor, Allocator, false>
 529 {
 530   typedef typename Descriptor::value_type value_type;
 531   typedef typename Descriptor::compare_type compare_type;
 532
 533 public:
 534   hash_table (size_t);
 535   ~hash_table ();
 536
 537   /* Current size (in entries) of the hash table.  */
 538   size_t size () const { return m_size; }
 539
 540   /* Return the current number of elements in this hash table. */
 541   size_t elements () const { return m_n_elements - m_n_deleted; }
 542
 543   /* Return the current number of elements in this hash table. */
 544   size_t elements_with_deleted () const { return m_n_elements; }
 545
 546   /* This function clears all entries in the given hash table.  */
 547   void empty ();
 548
 549   /* This function clears a specified SLOT in a hash table.  It is
 550      useful when you've already done the lookup and don't want to do it
 551      again. */
 552
 553   void clear_slot (value_type **);
 554
 555   /* This function searches for a hash table entry equal to the given
 556      COMPARABLE element starting with the given HASH value.  It cannot
 557      be used to insert or delete an element. */
 558   value_type *find_with_hash (const compare_type *, hashval_t);
 559
 560 /* Like find_slot_with_hash, but compute the hash value from the element.  */
 561   value_type *find (const value_type *value)
 562     {
 563       return find_with_hash (value, Descriptor::hash (value));
 564     }
 565
 566   value_type **find_slot (const value_type *value, insert_option insert)
 567     {
 568       return find_slot_with_hash (value, Descriptor::hash (value), insert);
 569     }
 570
 571   /* This function searches for a hash table slot containing an entry
 572      equal to the given COMPARABLE element and starting with the given
 573      HASH.  To delete an entry, call this with insert=NO_INSERT, then
 574      call clear_slot on the slot returned (possibly after doing some
 575      checks).  To insert an entry, call this with insert=INSERT, then
 576      write the value you want into the returned slot.  When inserting an
 577      entry, NULL may be returned if memory allocation fails. */
 578   value_type **find_slot_with_hash (const compare_type *comparable,
 579                                     hashval_t hash, enum insert_option insert);
 580
 581   /* This function deletes an element with the given COMPARABLE value
 582      from hash table starting with the given HASH.  If there is no
 583      matching element in the hash table, this function does nothing. */
 584   void remove_elt_with_hash (const compare_type *, hashval_t);
 585
 586 /* Like remove_elt_with_hash, but compute the hash value from the element.  */
 587   void remove_elt (const value_type *value)
 588     {
 589       remove_elt_with_hash (value, Descriptor::hash (value));
 590     }
 591
 592   /* This function scans over the entire hash table calling CALLBACK for
 593      each live entry.  If CALLBACK returns false, the iteration stops.
 594      ARGUMENT is passed as CALLBACK's second argument. */
 595   template <typename Argument,
 596             int (*Callback) (value_type **slot, Argument argument)>
 597   void traverse_noresize (Argument argument);
 598
 599   /* Like traverse_noresize, but does resize the table when it is too empty
 600      to improve effectivity of subsequent calls.  */
 601   template <typename Argument,
 602             int (*Callback) (value_type **slot, Argument argument)>
 603   void traverse (Argument argument);
 604
 605   class iterator
 606   {
 607   public:
 608     iterator () : m_slot (NULL), m_limit (NULL) {}
 609
 610     iterator (value_type **slot, value_type **limit) :
 611       m_slot (slot), m_limit (limit) {}
 612
 613     inline value_type *operator * () { return *m_slot; }
 614     void slide ();
 615     inline iterator &operator ++ ();
 616     bool operator != (const iterator &other) const
 617       {
 618         return m_slot != other.m_slot || m_limit != other.m_limit;
 619       }
 620
 621   private:
 622     value_type **m_slot;
 623     value_type **m_limit;
 624   };
 625
 626   iterator begin () const
 627     {
 628       iterator iter (m_entries, m_entries + m_size);
 629       iter.slide ();
 630       return iter;
 631     }
 632
 633   iterator end () const { return iterator (); }
 634
 635   double collisions () const
 636     {
 637       return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
 638     }
 639
 640 private:
 641
 642   value_type **find_empty_slot_for_expand (hashval_t);
 643   void expand ();
 644
 645   /* Table itself.  */
 646   typename Descriptor::value_type **m_entries;
 647
 648   size_t m_size;
 649
 650   /* Current number of elements including also deleted elements.  */
 651   size_t m_n_elements;
 652
 653   /* Current number of deleted elements in the table.  */
 654   size_t m_n_deleted;
 655
 656   /* The following member is used for debugging. Its value is number
 657      of all calls of `htab_find_slot' for the hash table. */
 658   unsigned int m_searches;
 659
 660   /* The following member is used for debugging.  Its value is number
 661      of collisions fixed for time of work with the hash table. */
 662   unsigned int m_collisions;
 663
 664   /* Current size (in entries) of the hash table, as an index into the
 665      table of primes.  */
 666   unsigned int m_size_prime_index;
 667 };
 668
 669 template<typename Descriptor, template<typename Type> class Allocator>
 670 hash_table<Descriptor, Allocator, false>::hash_table (size_t size) :
 671   m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0)
 672 {
 673   unsigned int size_prime_index;
 674
 675   size_prime_index = hash_table_higher_prime_index (size);
 676   size = prime_tab[size_prime_index].prime;
 677
 678   m_entries = Allocator <value_type*> ::data_alloc (size);
 679   gcc_assert (m_entries != NULL);
 680   m_size = size;
 681   m_size_prime_index = size_prime_index;
 682 }
 683
 684 template<typename Descriptor, template<typename Type> class Allocator>
 685 hash_table<Descriptor, Allocator, false>::~hash_table ()
 686 {
 687   for (size_t i = m_size - 1; i < m_size; i--)
 688     if (m_entries[i] != HTAB_EMPTY_ENTRY && m_entries[i] != HTAB_DELETED_ENTRY)
 689       Descriptor::remove (m_entries[i]);
 690
 691   Allocator <value_type *> ::data_free (m_entries);
 692 }
 693
 694 /* Similar to find_slot, but without several unwanted side effects:
 695     - Does not call equal when it finds an existing entry.
 696     - Does not change the count of elements/searches/collisions in the
 697       hash table.
 698    This function also assumes there are no deleted entries in the table.
 699    HASH is the hash value for the element to be inserted.  */
 700
 701 template<typename Descriptor, template<typename Type> class Allocator>
 702 typename hash_table<Descriptor, Allocator, false>::value_type **
 703 hash_table<Descriptor, Allocator, false>
 704 ::find_empty_slot_for_expand (hashval_t hash)
 705 {
 706   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
 707   size_t size = m_size;
 708   value_type **slot = m_entries + index;
 709   hashval_t hash2;
 710
 711   if (*slot == HTAB_EMPTY_ENTRY)
 712     return slot;
 713   else if (*slot == HTAB_DELETED_ENTRY)
 714     abort ();
 715
 716   hash2 = hash_table_mod2 (hash, m_size_prime_index);
 717   for (;;)
 718     {
 719       index += hash2;
 720       if (index >= size)
 721         index -= size;
 722
 723       slot = m_entries + index;
 724       if (*slot == HTAB_EMPTY_ENTRY)
 725         return slot;
 726       else if (*slot == HTAB_DELETED_ENTRY)
 727         abort ();
 728     }
 729 }
 730
 731 /* The following function changes size of memory allocated for the
 732    entries and repeatedly inserts the table elements.  The occupancy
 733    of the table after the call will be about 50%.  Naturally the hash
 734    table must already exist.  Remember also that the place of the
 735    table entries is changed.  If memory allocation fails, this function
 736    will abort.  */
 737
 738           template<typename Descriptor, template<typename Type> class Allocator>
 739 void
 740 hash_table<Descriptor, Allocator, false>::expand ()
 741 {
 742   value_type **oentries = m_entries;
 743   unsigned int oindex = m_size_prime_index;
 744   size_t osize = size ();
 745   value_type **olimit = oentries + osize;
 746   size_t elts = elements ();
 747
 748   /* Resize only when table after removal of unused elements is either
 749      too full or too empty.  */
 750   unsigned int nindex;
 751   size_t nsize;
 752   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
 753     {
 754       nindex = hash_table_higher_prime_index (elts * 2);
 755       nsize = prime_tab[nindex].prime;
 756     }
 757   else
 758     {
 759       nindex = oindex;
 760       nsize = osize;
 761     }
 762
 763   value_type **nentries = Allocator <value_type *> ::data_alloc (nsize);
 764   gcc_assert (nentries != NULL);
 765   m_entries = nentries;
 766   m_size = nsize;
 767   m_size_prime_index = nindex;
 768   m_n_elements -= m_n_deleted;
 769   m_n_deleted = 0;
 770
 771   value_type **p = oentries;
 772   do
 773     {
 774       value_type *x = *p;
 775
 776       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
 777         {
 778           value_type **q = find_empty_slot_for_expand (Descriptor::hash (x));
 779
 780           *q = x;
 781         }
 782
 783       p++;
 784     }
 785   while (p < olimit);
 786
 787   Allocator <value_type *> ::data_free (oentries);
 788 }
 789
 790 template<typename Descriptor, template<typename Type> class Allocator>
 791 void
 792 hash_table<Descriptor, Allocator, false>::empty ()
 793 {
 794   size_t size = m_size;
 795   value_type **entries = m_entries;
 796   int i;
 797
 798   for (i = size - 1; i >= 0; i--)
 799     if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
 800       Descriptor::remove (entries[i]);
 801
 802   /* Instead of clearing megabyte, downsize the table.  */
 803   if (size > 1024*1024 / sizeof (PTR))
 804     {
 805       int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
 806       int nsize = prime_tab[nindex].prime;
 807
 808       Allocator <value_type *> ::data_free (m_entries);
 809       m_entries = Allocator <value_type *> ::data_alloc (nsize);
 810       m_size = nsize;
 811       m_size_prime_index = nindex;
 812     }
 813   else
 814     memset (entries, 0, size * sizeof (value_type *));
 815   m_n_deleted = 0;
 816   m_n_elements = 0;
 817 }
 818
 819 /* This function clears a specified SLOT in a hash table.  It is
 820    useful when you've already done the lookup and don't want to do it
 821    again. */
 822
 823 template<typename Descriptor, template<typename Type> class Allocator>
 824 void
 825 hash_table<Descriptor, Allocator, false>::clear_slot (value_type **slot)
 826 {
 827   if (slot < m_entries || slot >= m_entries + size ()
 828       || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
 829     abort ();
 830
 831   Descriptor::remove (*slot);
 832
 833   *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY);
 834   m_n_deleted++;
 835 }
 836
 837 /* This function searches for a hash table entry equal to the given
 838    COMPARABLE element starting with the given HASH value.  It cannot
 839    be used to insert or delete an element. */
 840
 841 template<typename Descriptor, template<typename Type> class Allocator>
 842 typename hash_table<Descriptor, Allocator, false>::value_type *
 843 hash_table<Descriptor, Allocator, false>
 844 ::find_with_hash (const compare_type *comparable, hashval_t hash)
 845 {
 846   m_searches++;
 847   size_t size = m_size;
 848   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
 849
 850   value_type *entry = m_entries[index];
 851   if (entry == HTAB_EMPTY_ENTRY
 852       || (entry != HTAB_DELETED_ENTRY && Descriptor::equal (entry, comparable)))
 853     return entry;
 854
 855   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
 856   for (;;)
 857     {
 858       m_collisions++;
 859       index += hash2;
 860       if (index >= size)
 861         index -= size;
 862
 863       entry = m_entries[index];
 864       if (entry == HTAB_EMPTY_ENTRY
 865           || (entry != HTAB_DELETED_ENTRY
 866               && Descriptor::equal (entry, comparable)))
 867         return entry;
 868     }
 869 }
 870
 871 /* This function searches for a hash table slot containing an entry
 872    equal to the given COMPARABLE element and starting with the given
 873    HASH.  To delete an entry, call this with insert=NO_INSERT, then
 874    call clear_slot on the slot returned (possibly after doing some
 875    checks).  To insert an entry, call this with insert=INSERT, then
 876    write the value you want into the returned slot.  When inserting an
 877    entry, NULL may be returned if memory allocation fails. */
 878
 879 template<typename Descriptor, template<typename Type> class Allocator>
 880 typename hash_table<Descriptor, Allocator, false>::value_type **
 881 hash_table<Descriptor, Allocator, false>
 882 ::find_slot_with_hash (const compare_type *comparable, hashval_t hash,
 883                        enum insert_option insert)
 884 {
 885   if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
 886     expand ();
 887
 888   m_searches++;
 889
 890   value_type **first_deleted_slot = NULL;
 891   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
 892   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
 893   value_type *entry = m_entries[index];
 894   size_t size = m_size;
 895   if (entry == HTAB_EMPTY_ENTRY)
 896     goto empty_entry;
 897   else if (entry == HTAB_DELETED_ENTRY)
 898     first_deleted_slot = &m_entries[index];
 899   else if (Descriptor::equal (entry, comparable))
 900     return &m_entries[index];
 901
 902   for (;;)
 903     {
 904       m_collisions++;
 905       index += hash2;
 906       if (index >= size)
 907         index -= size;
 908
 909       entry = m_entries[index];
 910       if (entry == HTAB_EMPTY_ENTRY)
 911         goto empty_entry;
 912       else if (entry == HTAB_DELETED_ENTRY)
 913         {
 914           if (!first_deleted_slot)
 915             first_deleted_slot = &m_entries[index];
 916         }
 917       else if (Descriptor::equal (entry, comparable))
 918         return &m_entries[index];
 919     }
 920
 921  empty_entry:
 922   if (insert == NO_INSERT)
 923     return NULL;
 924
 925   if (first_deleted_slot)
 926     {
 927       m_n_deleted--;
 928       *first_deleted_slot = static_cast <value_type *> (HTAB_EMPTY_ENTRY);
 929       return first_deleted_slot;
 930     }
 931
 932   m_n_elements++;
 933   return &m_entries[index];
 934 }
 935
 936 /* This function deletes an element with the given COMPARABLE value
 937    from hash table starting with the given HASH.  If there is no
 938    matching element in the hash table, this function does nothing. */
 939
 940 template<typename Descriptor, template<typename Type> class Allocator>
 941 void
 942 hash_table<Descriptor, Allocator, false>
 943 ::remove_elt_with_hash (const compare_type *comparable, hashval_t hash)
 944 {
 945   value_type **slot = find_slot_with_hash (comparable, hash, NO_INSERT);
 946   if (*slot == HTAB_EMPTY_ENTRY)
 947     return;
 948
 949   Descriptor::remove (*slot);
 950
 951   *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY);
 952   m_n_deleted++;
 953 }
 954
 955 /* This function scans over the entire hash table calling CALLBACK for
 956    each live entry.  If CALLBACK returns false, the iteration stops.
 957    ARGUMENT is passed as CALLBACK's second argument. */
 958
 959 template<typename Descriptor, template<typename Type> class Allocator>
 960 template<typename Argument,
 961           int (*Callback) (typename hash_table<Descriptor, Allocator,
 962                                                false>::value_type **slot,
 963                            Argument argument)>
 964 void
 965 hash_table<Descriptor, Allocator, false>::traverse_noresize (Argument argument)
 966 {
 967   value_type **slot = m_entries;
 968   value_type **limit = slot + size ();
 969
 970   do
 971     {
 972       value_type *x = *slot;
 973
 974       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
 975         if (! Callback (slot, argument))
 976           break;
 977     }
 978   while (++slot < limit);
 979 }
 980
 981 /* Like traverse_noresize, but does resize the table when it is too empty
 982    to improve effectivity of subsequent calls.  */
 983
 984 template <typename Descriptor,
 985           template <typename Type> class Allocator>
 986 template <typename Argument,
 987           int (*Callback) (typename hash_table<Descriptor, Allocator,
 988                                                false>::value_type **slot,
 989                            Argument argument)>
 990 void
 991 hash_table<Descriptor, Allocator, false>::traverse (Argument argument)
 992 {
 993   size_t size = m_size;
 994   if (elements () * 8 < size && size > 32)
 995     expand ();
 996
 997   traverse_noresize <Argument, Callback> (argument);
 998 }
 999
1000 /* Slide down the iterator slots until an active entry is found.  */
1001
1002 template<typename Descriptor, template<typename Type> class Allocator>
1003 void
1004 hash_table<Descriptor, Allocator, false>::iterator::slide ()
1005 {
1006   for ( ; m_slot < m_limit; ++m_slot )
1007     {
1008       value_type *x = *m_slot;
1009       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
1010         return;
1011     }
1012   m_slot = NULL;
1013   m_limit = NULL;
1014 }
1015
1016 /* Bump the iterator.  */
1017
1018 template<typename Descriptor, template<typename Type> class Allocator>
1019 inline typename hash_table<Descriptor, Allocator, false>::iterator &
1020 hash_table<Descriptor, Allocator, false>::iterator::operator ++ ()
1021 {
1022   ++m_slot;
1023   slide ();
1024   return *this;
1025 }
1026
1027 /* A partial specialization used when values should be stored directly.  */
1028
1029 template <typename Descriptor,
1030          template<typename Type> class Allocator>
1031 class hash_table<Descriptor, Allocator, true>
1032 {
1033   typedef typename Descriptor::value_type value_type;
1034   typedef typename Descriptor::compare_type compare_type;
1035
1036 public:
1037   explicit hash_table (size_t, bool ggc = false);
1038   ~hash_table ();
1039
1040   /* Create a hash_table in gc memory.  */
1041
1042   static hash_table *
1043   create_ggc (size_t n)
1044   {
1045     hash_table *table = ggc_alloc<hash_table> ();
1046     new (table) hash_table (n, true);
1047     return table;
1048   }
1049
1050   /* Current size (in entries) of the hash table.  */
1051   size_t size () const { return m_size; }
1052
1053   /* Return the current number of elements in this hash table. */
1054   size_t elements () const { return m_n_elements - m_n_deleted; }
1055
1056   /* Return the current number of elements in this hash table. */
1057   size_t elements_with_deleted () const { return m_n_elements; }
1058
1059   /* This function clears all entries in the given hash table.  */
1060   void empty ();
1061
1062   /* This function clears a specified SLOT in a hash table.  It is
1063      useful when you've already done the lookup and don't want to do it
1064      again. */
1065
1066   void clear_slot (value_type *);
1067
1068   /* This function searches for a hash table entry equal to the given
1069      COMPARABLE element starting with the given HASH value.  It cannot
1070      be used to insert or delete an element. */
1071   value_type &find_with_hash (const compare_type &, hashval_t);
1072
1073 /* Like find_slot_with_hash, but compute the hash value from the element.  */
1074   value_type &find (const value_type &value)
1075     {
1076       return find_with_hash (value, Descriptor::hash (value));
1077     }
1078
1079   value_type *find_slot (const value_type &value, insert_option insert)
1080     {
1081       return find_slot_with_hash (value, Descriptor::hash (value), insert);
1082     }
1083
1084   /* This function searches for a hash table slot containing an entry
1085      equal to the given COMPARABLE element and starting with the given
1086      HASH.  To delete an entry, call this with insert=NO_INSERT, then
1087      call clear_slot on the slot returned (possibly after doing some
1088      checks).  To insert an entry, call this with insert=INSERT, then
1089      write the value you want into the returned slot.  When inserting an
1090      entry, NULL may be returned if memory allocation fails. */
1091   value_type *find_slot_with_hash (const compare_type &comparable,
1092                                     hashval_t hash, enum insert_option insert);
1093
1094   /* This function deletes an element with the given COMPARABLE value
1095      from hash table starting with the given HASH.  If there is no
1096      matching element in the hash table, this function does nothing. */
1097   void remove_elt_with_hash (const compare_type &, hashval_t);
1098
1099 /* Like remove_elt_with_hash, but compute the hash value from the element.  */
1100   void remove_elt (const value_type &value)
1101     {
1102       remove_elt_with_hash (value, Descriptor::hash (value));
1103     }
1104
1105   /* This function scans over the entire hash table calling CALLBACK for
1106      each live entry.  If CALLBACK returns false, the iteration stops.
1107      ARGUMENT is passed as CALLBACK's second argument. */
1108   template <typename Argument,
1109             int (*Callback) (value_type *slot, Argument argument)>
1110   void traverse_noresize (Argument argument);
1111
1112   /* Like traverse_noresize, but does resize the table when it is too empty
1113      to improve effectivity of subsequent calls.  */
1114   template <typename Argument,
1115             int (*Callback) (value_type *slot, Argument argument)>
1116   void traverse (Argument argument);
1117
1118   class iterator
1119   {
1120   public:
1121     iterator () : m_slot (NULL), m_limit (NULL) {}
1122
1123     iterator (value_type *slot, value_type *limit) :
1124       m_slot (slot), m_limit (limit) {}
1125
1126     inline value_type &operator * () { return *m_slot; }
1127     void slide ();
1128     inline iterator &operator ++ ();
1129     bool operator != (const iterator &other) const
1130       {
1131         return m_slot != other.m_slot || m_limit != other.m_limit;
1132       }
1133
1134   private:
1135     value_type *m_slot;
1136     value_type *m_limit;
1137   };
1138
1139   iterator begin () const
1140     {
1141       iterator iter (m_entries, m_entries + m_size);
1142       iter.slide ();
1143       return iter;
1144     }
1145
1146   iterator end () const { return iterator (); }
1147
1148   double collisions () const
1149     {
1150       return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
1151     }
1152
1153 private:
1154   template<typename T> friend void gt_ggc_mx (hash_table<T> *);
1155   template<typename T> friend void gt_pch_nx (hash_table<T> *);
1156   template<typename T> friend void
1157     hashtab_entry_note_pointers (void *, void *, gt_pointer_operator, void *);
1158   template<typename T, typename U, typename V> friend void
1159   gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
1160   template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *,
1161                                                           gt_pointer_operator,
1162                                                           void *);
1163   template<typename T> friend void gt_pch_nx (hash_table<T> *,
1164                                               gt_pointer_operator, void *);
1165
1166   value_type *find_empty_slot_for_expand (hashval_t);
1167   void expand ();
1168   static bool is_deleted (value_type &v)
1169     {
1170       return is_deleted_helper<value_type, Descriptor>::call (v);
1171     }
1172   static bool is_empty (value_type &v)
1173     {
1174       return is_empty_helper<value_type, Descriptor>::call (v);
1175     }
1176
1177   static void mark_deleted (value_type &v)
1178     {
1179       return mark_deleted_helper<value_type, Descriptor>::call (v);
1180     }
1181
1182   static void mark_empty (value_type &v)
1183     {
1184       return mark_empty_helper<value_type, Descriptor>::call (v);
1185     }
1186
1187   /* Table itself.  */
1188   typename Descriptor::value_type *m_entries;
1189
1190   size_t m_size;
1191
1192   /* Current number of elements including also deleted elements.  */
1193   size_t m_n_elements;
1194
1195   /* Current number of deleted elements in the table.  */
1196   size_t m_n_deleted;
1197
1198   /* The following member is used for debugging. Its value is number
1199      of all calls of `htab_find_slot' for the hash table. */
1200   unsigned int m_searches;
1201
1202   /* The following member is used for debugging.  Its value is number
1203      of collisions fixed for time of work with the hash table. */
1204   unsigned int m_collisions;
1205
1206   /* Current size (in entries) of the hash table, as an index into the
1207      table of primes.  */
1208   unsigned int m_size_prime_index;
1209
1210   /* if m_entries is stored in ggc memory.  */
1211   bool m_ggc;
1212 };
1213
1214 template<typename Descriptor, template<typename Type> class Allocator>
1215 hash_table<Descriptor, Allocator, true>::hash_table (size_t size, bool ggc) :
1216   m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
1217   m_ggc (ggc)
1218 {
1219   unsigned int size_prime_index;
1220
1221   size_prime_index = hash_table_higher_prime_index (size);
1222   size = prime_tab[size_prime_index].prime;
1223
1224   if (!m_ggc)
1225     m_entries = Allocator <value_type> ::data_alloc (size);
1226   else
1227     m_entries = ggc_cleared_vec_alloc<value_type> (size);
1228
1229   gcc_assert (m_entries != NULL);
1230   m_size = size;
1231   m_size_prime_index = size_prime_index;
1232 }
1233
1234 template<typename Descriptor, template<typename Type> class Allocator>
1235 hash_table<Descriptor, Allocator, true>::~hash_table ()
1236 {
1237   for (size_t i = m_size - 1; i < m_size; i--)
1238     if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
1239       Descriptor::remove (m_entries[i]);
1240
1241   if (!m_ggc)
1242     Allocator <value_type> ::data_free (m_entries);
1243   else
1244     ggc_free (m_entries);
1245 }
1246
1247 /* Similar to find_slot, but without several unwanted side effects:
1248     - Does not call equal when it finds an existing entry.
1249     - Does not change the count of elements/searches/collisions in the
1250       hash table.
1251    This function also assumes there are no deleted entries in the table.
1252    HASH is the hash value for the element to be inserted.  */
1253
1254 template<typename Descriptor, template<typename Type> class Allocator>
1255 typename hash_table<Descriptor, Allocator, true>::value_type *
1256 hash_table<Descriptor, Allocator, true>
1257 ::find_empty_slot_for_expand (hashval_t hash)
1258 {
1259   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
1260   size_t size = m_size;
1261   value_type *slot = m_entries + index;
1262   hashval_t hash2;
1263
1264   if (is_empty (*slot))
1265     return slot;
1266   else if (is_deleted (*slot))
1267     abort ();
1268
1269   hash2 = hash_table_mod2 (hash, m_size_prime_index);
1270   for (;;)
1271     {
1272       index += hash2;
1273       if (index >= size)
1274         index -= size;
1275
1276       slot = m_entries + index;
1277       if (is_empty (*slot))
1278         return slot;
1279       else if (is_deleted (*slot))
1280         abort ();
1281     }
1282 }
1283
1284 /* The following function changes size of memory allocated for the
1285    entries and repeatedly inserts the table elements.  The occupancy
1286    of the table after the call will be about 50%.  Naturally the hash
1287    table must already exist.  Remember also that the place of the
1288    table entries is changed.  If memory allocation fails, this function
1289    will abort.  */
1290
1291           template<typename Descriptor, template<typename Type> class Allocator>
1292 void
1293 hash_table<Descriptor, Allocator, true>::expand ()
1294 {
1295   value_type *oentries = m_entries;
1296   unsigned int oindex = m_size_prime_index;
1297   size_t osize = size ();
1298   value_type *olimit = oentries + osize;
1299   size_t elts = elements ();
1300
1301   /* Resize only when table after removal of unused elements is either
1302      too full or too empty.  */
1303   unsigned int nindex;
1304   size_t nsize;
1305   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
1306     {
1307       nindex = hash_table_higher_prime_index (elts * 2);
1308       nsize = prime_tab[nindex].prime;
1309     }
1310   else
1311     {
1312       nindex = oindex;
1313       nsize = osize;
1314     }
1315
1316   value_type *nentries;
1317   if (!m_ggc)
1318     nentries = Allocator <value_type> ::data_alloc (nsize);
1319   else
1320     nentries = ggc_cleared_vec_alloc<value_type> (nsize);
1321
1322   gcc_assert (nentries != NULL);
1323   m_entries = nentries;
1324   m_size = nsize;
1325   m_size_prime_index = nindex;
1326   m_n_elements -= m_n_deleted;
1327   m_n_deleted = 0;
1328
1329   value_type *p = oentries;
1330   do
1331     {
1332       value_type &x = *p;
1333
1334       if (!is_empty (x) && !is_deleted (x))
1335         {
1336           value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
1337
1338           *q = x;
1339         }
1340
1341       p++;
1342     }
1343   while (p < olimit);
1344
1345   if (!m_ggc)
1346     Allocator <value_type> ::data_free (oentries);
1347   else
1348     ggc_free (oentries);
1349 }
1350
1351 template<typename Descriptor, template<typename Type> class Allocator>
1352 void
1353 hash_table<Descriptor, Allocator, true>::empty ()
1354 {
1355   size_t size = m_size;
1356   value_type *entries = m_entries;
1357   int i;
1358
1359   for (i = size - 1; i >= 0; i--)
1360     if (!is_empty (entries[i]) && !is_deleted (entries[i]))
1361       Descriptor::remove (entries[i]);
1362
1363   /* Instead of clearing megabyte, downsize the table.  */
1364   if (size > 1024*1024 / sizeof (PTR))
1365     {
1366       int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
1367       int nsize = prime_tab[nindex].prime;
1368
1369       if (!m_ggc)
1370         {
1371           Allocator <value_type> ::data_free (m_entries);
1372           m_entries = Allocator <value_type> ::data_alloc (nsize);
1373         }
1374       else
1375         {
1376           ggc_free (m_entries);
1377           m_entries = ggc_cleared_vec_alloc<value_type> (nsize);
1378         }
1379
1380       m_size = nsize;
1381       m_size_prime_index = nindex;
1382     }
1383   else
1384     memset (entries, 0, size * sizeof (value_type));
1385   m_n_deleted = 0;
1386   m_n_elements = 0;
1387 }
1388
1389 /* This function clears a specified SLOT in a hash table.  It is
1390    useful when you've already done the lookup and don't want to do it
1391    again. */
1392
1393 template<typename Descriptor, template<typename Type> class Allocator>
1394 void
1395 hash_table<Descriptor, Allocator, true>::clear_slot (value_type *slot)
1396 {
1397   if (slot < m_entries || slot >= m_entries + size ()
1398       || is_empty (*slot) || is_deleted (*slot))
1399     abort ();
1400
1401   Descriptor::remove (*slot);
1402
1403   mark_deleted (*slot);
1404   m_n_deleted++;
1405 }
1406
1407 /* This function searches for a hash table entry equal to the given
1408    COMPARABLE element starting with the given HASH value.  It cannot
1409    be used to insert or delete an element. */
1410
1411 template<typename Descriptor, template<typename Type> class Allocator>
1412 typename hash_table<Descriptor, Allocator, true>::value_type &
1413 hash_table<Descriptor, Allocator, true>
1414 ::find_with_hash (const compare_type &comparable, hashval_t hash)
1415 {
1416   m_searches++;
1417   size_t size = m_size;
1418   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
1419
1420   value_type *entry = &m_entries[index];
1421   if (is_empty (*entry)
1422       || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
1423     return *entry;
1424
1425   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
1426   for (;;)
1427     {
1428       m_collisions++;
1429       index += hash2;
1430       if (index >= size)
1431         index -= size;
1432
1433       entry = &m_entries[index];
1434       if (is_empty (*entry)
1435           || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
1436         return *entry;
1437     }
1438 }
1439
1440 /* This function searches for a hash table slot containing an entry
1441    equal to the given COMPARABLE element and starting with the given
1442    HASH.  To delete an entry, call this with insert=NO_INSERT, then
1443    call clear_slot on the slot returned (possibly after doing some
1444    checks).  To insert an entry, call this with insert=INSERT, then
1445    write the value you want into the returned slot.  When inserting an
1446    entry, NULL may be returned if memory allocation fails. */
1447
1448 template<typename Descriptor, template<typename Type> class Allocator>
1449 typename hash_table<Descriptor, Allocator, true>::value_type *
1450 hash_table<Descriptor, Allocator, true>
1451 ::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
1452                        enum insert_option insert)
1453 {
1454   if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
1455     expand ();
1456
1457   m_searches++;
1458
1459   value_type *first_deleted_slot = NULL;
1460   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
1461   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
1462   value_type *entry = &m_entries[index];
1463   size_t size = m_size;
1464   if (is_empty (*entry))
1465     goto empty_entry;
1466   else if (is_deleted (*entry))
1467     first_deleted_slot = &m_entries[index];
1468   else if (Descriptor::equal (*entry, comparable))
1469     return &m_entries[index];
1470
1471   for (;;)
1472     {
1473       m_collisions++;
1474       index += hash2;
1475       if (index >= size)
1476         index -= size;
1477
1478       entry = &m_entries[index];
1479       if (is_empty (*entry))
1480         goto empty_entry;
1481       else if (is_deleted (*entry))
1482         {
1483           if (!first_deleted_slot)
1484             first_deleted_slot = &m_entries[index];
1485         }
1486       else if (Descriptor::equal (*entry, comparable))
1487         return &m_entries[index];
1488     }
1489
1490  empty_entry:
1491   if (insert == NO_INSERT)
1492     return NULL;
1493
1494   if (first_deleted_slot)
1495     {
1496       m_n_deleted--;
1497       mark_empty (*first_deleted_slot);
1498       return first_deleted_slot;
1499     }
1500
1501   m_n_elements++;
1502   return &m_entries[index];
1503 }
1504
1505 /* This function deletes an element with the given COMPARABLE value
1506    from hash table starting with the given HASH.  If there is no
1507    matching element in the hash table, this function does nothing. */
1508
1509 template<typename Descriptor, template<typename Type> class Allocator>
1510 void
1511 hash_table<Descriptor, Allocator, true>
1512 ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
1513 {
1514   value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
1515   if (is_empty (*slot))
1516     return;
1517
1518   Descriptor::remove (*slot);
1519
1520   mark_deleted (*slot);
1521   m_n_deleted++;
1522 }
1523
1524 /* This function scans over the entire hash table calling CALLBACK for
1525    each live entry.  If CALLBACK returns false, the iteration stops.
1526    ARGUMENT is passed as CALLBACK's second argument. */
1527
1528 template<typename Descriptor,
1529           template<typename Type> class Allocator>
1530 template<typename Argument,
1531           int (*Callback) (typename hash_table<Descriptor, Allocator,
1532                                                true>::value_type *slot,
1533                            Argument argument)>
1534 void
1535 hash_table<Descriptor, Allocator, true>::traverse_noresize (Argument argument)
1536 {
1537   value_type *slot = m_entries;
1538   value_type *limit = slot + size ();
1539
1540   do
1541     {
1542       value_type &x = *slot;
1543
1544       if (!is_empty (x) && !is_deleted (x))
1545         if (! Callback (slot, argument))
1546           break;
1547     }
1548   while (++slot < limit);
1549 }
1550
1551 /* Like traverse_noresize, but does resize the table when it is too empty
1552    to improve effectivity of subsequent calls.  */
1553
1554 template <typename Descriptor,
1555           template <typename Type> class Allocator>
1556 template <typename Argument,
1557           int (*Callback) (typename hash_table<Descriptor, Allocator,
1558                                                true>::value_type *slot,
1559                            Argument argument)>
1560 void
1561 hash_table<Descriptor, Allocator, true>::traverse (Argument argument)
1562 {
1563   size_t size = m_size;
1564   if (elements () * 8 < size && size > 32)
1565     expand ();
1566
1567   traverse_noresize <Argument, Callback> (argument);
1568 }
1569
1570 /* Slide down the iterator slots until an active entry is found.  */
1571
1572 template<typename Descriptor, template<typename Type> class Allocator>
1573 void
1574 hash_table<Descriptor, Allocator, true>::iterator::slide ()
1575 {
1576   for ( ; m_slot < m_limit; ++m_slot )
1577     {
1578       value_type &x = *m_slot;
1579       if (!is_empty (x) && !is_deleted (x))
1580         return;
1581     }
1582   m_slot = NULL;
1583   m_limit = NULL;
1584 }
1585
1586 /* Bump the iterator.  */
1587
1588 template<typename Descriptor, template<typename Type> class Allocator>
1589 inline typename hash_table<Descriptor, Allocator, true>::iterator &
1590 hash_table<Descriptor, Allocator, true>::iterator::operator ++ ()
1591 {
1592   ++m_slot;
1593   slide ();
1594   return *this;
1595 }
1596
1597
1598 /* Iterate through the elements of hash_table HTAB,
1599    using hash_table <....>::iterator ITER,
1600    storing each element in RESULT, which is of type TYPE.  */
1601
1602 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1603   for ((ITER) = (HTAB).begin (); \
1604        (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1605        ++(ITER))
1606
1607 /* ggc walking routines.  */
1608
1609 template<typename E>
1610 static inline void
1611 gt_ggc_mx (hash_table<E> *h)
1612 {
1613   typedef hash_table<E> table;
1614
1615   if (!ggc_test_and_set_mark (h->m_entries))
1616     return;
1617
1618   for (size_t i = 0; i < h->m_size; i++)
1619     {
1620       if (table::is_empty (h->m_entries[i])
1621           || table::is_deleted (h->m_entries[i]))
1622         continue;
1623
1624       E::ggc_mx (h->m_entries[i]);
1625     }
1626 }
1627
1628 template<typename D>
1629 static inline void
1630 hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
1631                              void *cookie)
1632 {
1633   hash_table<D> *map = static_cast<hash_table<D> *> (h);
1634   gcc_checking_assert (map->m_entries == obj);
1635   for (size_t i = 0; i < map->m_size; i++)
1636     {
1637       typedef hash_table<D> table;
1638       if (table::is_empty (map->m_entries[i])
1639           || table::is_deleted (map->m_entries[i]))
1640         continue;
1641
1642       D::pch_nx (map->m_entries[i], op, cookie);
1643     }
1644 }
1645
1646 template<typename D>
1647 static void
1648 gt_pch_nx (hash_table<D> *h)
1649 {
1650   bool success
1651     = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
1652   gcc_checking_assert (success);
1653   for (size_t i = 0; i < h->m_size; i++)
1654     {
1655       if (hash_table<D>::is_empty (h->m_entries[i])
1656           || hash_table<D>::is_deleted (h->m_entries[i]))
1657         continue;
1658
1659       D::pch_nx (h->m_entries[i]);
1660     }
1661 }
1662
1663 template<typename D>
1664 static inline void
1665 gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
1666 {
1667   op (&h->m_entries, cookie);
1668 }
1669
1670 #endif /* TYPED_HASHTAB_H */