gcc/hash-table.h

   1 /* A type-safe hash table template.
   2    Copyright (C) 2012-2016 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          (or 'const value_type &') and returns a hashval_t value.
  41
  42          - A typedef named 'compare_type' that is used to test when a 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          and a compare_type, and returns a bool.  Both arguments can be
  49          const references.
  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          - An optional static function named 'keep_cache_entry'.  This
  57          function is provided only for garbage-collected elements that
  58          are not marked by the normal gc mark pass.  It describes what
  59          what should happen to the element at the end of the gc mark phase.
  60          The return value should be:
  61            - 0 if the element should be deleted
  62            - 1 if the element should be kept and needs to be marked
  63            - -1 if the element should be kept and is already marked.
  64          Returning -1 rather than 1 is purely an optimization.
  65
  66       3. The type of the hash table itself.  (More later.)
  67
  68    In very special circumstances, users may need to know about a fourth type.
  69
  70       4. The template type used to describe how hash table memory
  71       is allocated.  This type is called the allocator type.  It is
  72       parameterized on the value type.  It provides two functions:
  73
  74          - A static member function named 'data_alloc'.  This function
  75          allocates the data elements in the table.
  76
  77          - A static member function named 'data_free'.  This function
  78          deallocates the data elements in the table.
  79
  80    Hash table are instantiated with two type arguments.
  81
  82       * The descriptor type, (2) above.
  83
  84       * The allocator type, (4) above.  In general, you will not need to
  85       provide your own allocator type.  By default, hash tables will use
  86       the class template xcallocator, which uses malloc/free for allocation.
  87
  88
  89    DEFINING A DESCRIPTOR TYPE
  90
  91    The first task in using the hash table is to describe the element type.
  92    We compose this into a few steps.
  93
  94       1. Decide on a removal policy for values stored in the table.
  95          hash-traits.h provides class templates for the four most common
  96          policies:
  97
  98          * typed_free_remove implements the static 'remove' member function
  99          by calling free().
 100
 101          * typed_noop_remove implements the static 'remove' member function
 102          by doing nothing.
 103
 104          * ggc_remove implements the static 'remove' member by doing nothing,
 105          but instead provides routines for gc marking and for PCH streaming.
 106          Use this for garbage-collected data that needs to be preserved across
 107          collections.
 108
 109          * ggc_cache_remove is like ggc_remove, except that it does not
 110          mark the entries during the normal gc mark phase.  Instead it
 111          uses 'keep_cache_entry' (described above) to keep elements that
 112          were not collected and delete those that were.  Use this for
 113          garbage-collected caches that should not in themselves stop
 114          the data from being collected.
 115
 116          You can use these policies by simply deriving the descriptor type
 117          from one of those class template, with the appropriate argument.
 118
 119          Otherwise, you need to write the static 'remove' member function
 120          in the descriptor class.
 121
 122       2. Choose a hash function.  Write the static 'hash' member function.
 123
 124       3. Decide whether the lookup function should take as input an object
 125          of type value_type or something more restricted.  Define compare_type
 126          accordingly.
 127
 128       4. Choose an equality testing function 'equal' that compares a value_type
 129          and a compare_type.
 130
 131    If your elements are pointers, it is usually easiest to start with one
 132    of the generic pointer descriptors described below and override the bits
 133    you need to change.
 134
 135    AN EXAMPLE DESCRIPTOR TYPE
 136
 137    Suppose you want to put some_type into the hash table.  You could define
 138    the descriptor type as follows.
 139
 140       struct some_type_hasher : nofree_ptr_hash <some_type>
 141       // Deriving from nofree_ptr_hash means that we get a 'remove' that does
 142       // nothing.  This choice is good for raw values.
 143       {
 144         static inline hashval_t hash (const value_type *);
 145         static inline bool equal (const value_type *, const compare_type *);
 146       };
 147
 148       inline hashval_t
 149       some_type_hasher::hash (const value_type *e)
 150       { ... compute and return a hash value for E ... }
 151
 152       inline bool
 153       some_type_hasher::equal (const value_type *p1, const compare_type *p2)
 154       { ... compare P1 vs P2.  Return true if they are the 'same' ... }
 155
 156
 157    AN EXAMPLE HASH_TABLE DECLARATION
 158
 159    To instantiate a hash table for some_type:
 160
 161       hash_table <some_type_hasher> some_type_hash_table;
 162
 163    There is no need to mention some_type directly, as the hash table will
 164    obtain it using some_type_hasher::value_type.
 165
 166    You can then use any of the functions in hash_table's public interface.
 167    See hash_table for details.  The interface is very similar to libiberty's
 168    htab_t.
 169
 170
 171    EASY DESCRIPTORS FOR POINTERS
 172
 173    There are four descriptors for pointer elements, one for each of
 174    the removal policies above:
 175
 176    * nofree_ptr_hash (based on typed_noop_remove)
 177    * free_ptr_hash (based on typed_free_remove)
 178    * ggc_ptr_hash (based on ggc_remove)
 179    * ggc_cache_ptr_hash (based on ggc_cache_remove)
 180
 181    These descriptors hash and compare elements by their pointer value,
 182    rather than what they point to.  So, to instantiate a hash table over
 183    pointers to whatever_type, without freeing the whatever_types, use:
 184
 185       hash_table <nofree_ptr_hash <whatever_type> > whatever_type_hash_table;
 186
 187
 188    HASH TABLE ITERATORS
 189
 190    The hash table provides standard C++ iterators.  For example, consider a
 191    hash table of some_info.  We wish to consume each element of the table:
 192
 193       extern void consume (some_info *);
 194
 195    We define a convenience typedef and the hash table:
 196
 197       typedef hash_table <some_info_hasher> info_table_type;
 198       info_table_type info_table;
 199
 200    Then we write the loop in typical C++ style:
 201
 202       for (info_table_type::iterator iter = info_table.begin ();
 203            iter != info_table.end ();
 204            ++iter)
 205         if ((*iter).status == INFO_READY)
 206           consume (&*iter);
 207
 208    Or with common sub-expression elimination:
 209
 210       for (info_table_type::iterator iter = info_table.begin ();
 211            iter != info_table.end ();
 212            ++iter)
 213         {
 214           some_info &elem = *iter;
 215           if (elem.status == INFO_READY)
 216             consume (&elem);
 217         }
 218
 219    One can also use a more typical GCC style:
 220
 221       typedef some_info *some_info_p;
 222       some_info *elem_ptr;
 223       info_table_type::iterator iter;
 224       FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
 225         if (elem_ptr->status == INFO_READY)
 226           consume (elem_ptr);
 227
 228 */
 229
 230
 231 #ifndef TYPED_HASHTAB_H
 232 #define TYPED_HASHTAB_H
 233
 234 #include "statistics.h"
 235 #include "ggc.h"
 236 #include "vec.h"
 237 #include "hashtab.h"
 238 #include "inchash.h"
 239 #include "mem-stats-traits.h"
 240 #include "hash-traits.h"
 241 #include "hash-map-traits.h"
 242
 243 template<typename, typename, typename> class hash_map;
 244 template<typename, typename> class hash_set;
 245
 246 /* The ordinary memory allocator.  */
 247 /* FIXME (crowl): This allocator may be extracted for wider sharing later.  */
 248
 249 template <typename Type>
 250 struct xcallocator
 251 {
 252   static Type *data_alloc (size_t count);
 253   static void data_free (Type *memory);
 254 };
 255
 256
 257 /* Allocate memory for COUNT data blocks.  */
 258
 259 template <typename Type>
 260 inline Type *
 261 xcallocator <Type>::data_alloc (size_t count)
 262 {
 263   return static_cast <Type *> (xcalloc (count, sizeof (Type)));
 264 }
 265
 266
 267 /* Free memory for data blocks.  */
 268
 269 template <typename Type>
 270 inline void
 271 xcallocator <Type>::data_free (Type *memory)
 272 {
 273   return ::free (memory);
 274 }
 275
 276
 277 /* Table of primes and their inversion information.  */
 278
 279 struct prime_ent
 280 {
 281   hashval_t prime;
 282   hashval_t inv;
 283   hashval_t inv_m2;     /* inverse of prime-2 */
 284   hashval_t shift;
 285 };
 286
 287 extern struct prime_ent const prime_tab[];
 288
 289
 290 /* Functions for computing hash table indexes.  */
 291
 292 extern unsigned int hash_table_higher_prime_index (unsigned long n)
 293    ATTRIBUTE_PURE;
 294
 295 /* Return X % Y using multiplicative inverse values INV and SHIFT.
 296
 297    The multiplicative inverses computed above are for 32-bit types,
 298    and requires that we be able to compute a highpart multiply.
 299
 300    FIX: I am not at all convinced that
 301      3 loads, 2 multiplications, 3 shifts, and 3 additions
 302    will be faster than
 303      1 load and 1 modulus
 304    on modern systems running a compiler.  */
 305
 306 inline hashval_t
 307 mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
 308 {
 309    hashval_t t1, t2, t3, t4, q, r;
 310
 311    t1 = ((uint64_t)x * inv) >> 32;
 312    t2 = x - t1;
 313    t3 = t2 >> 1;
 314    t4 = t1 + t3;
 315    q  = t4 >> shift;
 316    r  = x - (q * y);
 317
 318    return r;
 319 }
 320
 321 /* Compute the primary table index for HASH given current prime index.  */
 322
 323 inline hashval_t
 324 hash_table_mod1 (hashval_t hash, unsigned int index)
 325 {
 326   const struct prime_ent *p = &prime_tab[index];
 327   gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
 328     return mul_mod (hash, p->prime, p->inv, p->shift);
 329 }
 330
 331 /* Compute the secondary table index for HASH given current prime index.  */
 332
 333 inline hashval_t
 334 hash_table_mod2 (hashval_t hash, unsigned int index)
 335 {
 336   const struct prime_ent *p = &prime_tab[index];
 337   gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
 338   return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift);
 339 }
 340
 341 class mem_usage;
 342
 343 /* User-facing hash table type.
 344
 345    The table stores elements of type Descriptor::value_type and uses
 346    the static descriptor functions described at the top of the file
 347    to hash, compare and remove elements.
 348
 349    Specify the template Allocator to allocate and free memory.
 350      The default is xcallocator.
 351
 352      Storage is an implementation detail and should not be used outside the
 353      hash table code.
 354
 355 */
 356 template <typename Descriptor,
 357          template<typename Type> class Allocator = xcallocator>
 358 class hash_table
 359 {
 360   typedef typename Descriptor::value_type value_type;
 361   typedef typename Descriptor::compare_type compare_type;
 362
 363 public:
 364   explicit hash_table (size_t, bool ggc = false,
 365                        bool gather_mem_stats = GATHER_STATISTICS,
 366                        mem_alloc_origin origin = HASH_TABLE_ORIGIN
 367                        CXX_MEM_STAT_INFO);
 368   explicit hash_table (const hash_table &, bool ggc = false,
 369                        bool gather_mem_stats = GATHER_STATISTICS,
 370                        mem_alloc_origin origin = HASH_TABLE_ORIGIN
 371                        CXX_MEM_STAT_INFO);
 372   ~hash_table ();
 373
 374   /* Create a hash_table in gc memory.  */
 375   static hash_table *
 376   create_ggc (size_t n CXX_MEM_STAT_INFO)
 377   {
 378     hash_table *table = ggc_alloc<hash_table> ();
 379     new (table) hash_table (n, true, GATHER_STATISTICS,
 380                             HASH_TABLE_ORIGIN PASS_MEM_STAT);
 381     return table;
 382   }
 383
 384   /* Current size (in entries) of the hash table.  */
 385   size_t size () const { return m_size; }
 386
 387   /* Return the current number of elements in this hash table. */
 388   size_t elements () const { return m_n_elements - m_n_deleted; }
 389
 390   /* Return the current number of elements in this hash table. */
 391   size_t elements_with_deleted () const { return m_n_elements; }
 392
 393   /* This function clears all entries in this hash table.  */
 394   void empty () { if (elements ()) empty_slow (); }
 395
 396   /* This function clears a specified SLOT in a hash table.  It is
 397      useful when you've already done the lookup and don't want to do it
 398      again. */
 399   void clear_slot (value_type *);
 400
 401   /* This function searches for a hash table entry equal to the given
 402      COMPARABLE element starting with the given HASH value.  It cannot
 403      be used to insert or delete an element. */
 404   value_type &find_with_hash (const compare_type &, hashval_t);
 405
 406   /* Like find_slot_with_hash, but compute the hash value from the element.  */
 407   value_type &find (const value_type &value)
 408     {
 409       return find_with_hash (value, Descriptor::hash (value));
 410     }
 411
 412   value_type *find_slot (const value_type &value, insert_option insert)
 413     {
 414       return find_slot_with_hash (value, Descriptor::hash (value), insert);
 415     }
 416
 417   /* This function searches for a hash table slot containing an entry
 418      equal to the given COMPARABLE element and starting with the given
 419      HASH.  To delete an entry, call this with insert=NO_INSERT, then
 420      call clear_slot on the slot returned (possibly after doing some
 421      checks).  To insert an entry, call this with insert=INSERT, then
 422      write the value you want into the returned slot.  When inserting an
 423      entry, NULL may be returned if memory allocation fails. */
 424   value_type *find_slot_with_hash (const compare_type &comparable,
 425                                     hashval_t hash, enum insert_option insert);
 426
 427   /* This function deletes an element with the given COMPARABLE value
 428      from hash table starting with the given HASH.  If there is no
 429      matching element in the hash table, this function does nothing. */
 430   void remove_elt_with_hash (const compare_type &, hashval_t);
 431
 432   /* Like remove_elt_with_hash, but compute the hash value from the
 433      element.  */
 434   void remove_elt (const value_type &value)
 435     {
 436       remove_elt_with_hash (value, Descriptor::hash (value));
 437     }
 438
 439   /* This function scans over the entire hash table calling CALLBACK for
 440      each live entry.  If CALLBACK returns false, the iteration stops.
 441      ARGUMENT is passed as CALLBACK's second argument. */
 442   template <typename Argument,
 443             int (*Callback) (value_type *slot, Argument argument)>
 444   void traverse_noresize (Argument argument);
 445
 446   /* Like traverse_noresize, but does resize the table when it is too empty
 447      to improve effectivity of subsequent calls.  */
 448   template <typename Argument,
 449             int (*Callback) (value_type *slot, Argument argument)>
 450   void traverse (Argument argument);
 451
 452   class iterator
 453   {
 454   public:
 455     iterator () : m_slot (NULL), m_limit (NULL) {}
 456
 457     iterator (value_type *slot, value_type *limit) :
 458       m_slot (slot), m_limit (limit) {}
 459
 460     inline value_type &operator * () { return *m_slot; }
 461     void slide ();
 462     inline iterator &operator ++ ();
 463     bool operator != (const iterator &other) const
 464       {
 465         return m_slot != other.m_slot || m_limit != other.m_limit;
 466       }
 467
 468   private:
 469     value_type *m_slot;
 470     value_type *m_limit;
 471   };
 472
 473   iterator begin () const
 474     {
 475       iterator iter (m_entries, m_entries + m_size);
 476       iter.slide ();
 477       return iter;
 478     }
 479
 480   iterator end () const { return iterator (); }
 481
 482   double collisions () const
 483     {
 484       return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
 485     }
 486
 487 private:
 488   template<typename T> friend void gt_ggc_mx (hash_table<T> *);
 489   template<typename T> friend void gt_pch_nx (hash_table<T> *);
 490   template<typename T> friend void
 491     hashtab_entry_note_pointers (void *, void *, gt_pointer_operator, void *);
 492   template<typename T, typename U, typename V> friend void
 493   gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
 494   template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *,
 495                                                           gt_pointer_operator,
 496                                                           void *);
 497   template<typename T> friend void gt_pch_nx (hash_table<T> *,
 498                                               gt_pointer_operator, void *);
 499
 500   template<typename T> friend void gt_cleare_cache (hash_table<T> *);
 501
 502   void empty_slow ();
 503
 504   value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
 505   value_type *find_empty_slot_for_expand (hashval_t);
 506   void expand ();
 507   static bool is_deleted (value_type &v)
 508   {
 509     return Descriptor::is_deleted (v);
 510   }
 511
 512   static bool is_empty (value_type &v)
 513   {
 514     return Descriptor::is_empty (v);
 515   }
 516
 517   static void mark_deleted (value_type &v)
 518   {
 519     Descriptor::mark_deleted (v);
 520   }
 521
 522   static void mark_empty (value_type &v)
 523   {
 524     Descriptor::mark_empty (v);
 525   }
 526
 527   /* Table itself.  */
 528   typename Descriptor::value_type *m_entries;
 529
 530   size_t m_size;
 531
 532   /* Current number of elements including also deleted elements.  */
 533   size_t m_n_elements;
 534
 535   /* Current number of deleted elements in the table.  */
 536   size_t m_n_deleted;
 537
 538   /* The following member is used for debugging. Its value is number
 539      of all calls of `htab_find_slot' for the hash table. */
 540   unsigned int m_searches;
 541
 542   /* The following member is used for debugging.  Its value is number
 543      of collisions fixed for time of work with the hash table. */
 544   unsigned int m_collisions;
 545
 546   /* Current size (in entries) of the hash table, as an index into the
 547      table of primes.  */
 548   unsigned int m_size_prime_index;
 549
 550   /* if m_entries is stored in ggc memory.  */
 551   bool m_ggc;
 552
 553   /* If we should gather memory statistics for the table.  */
 554   bool m_gather_mem_stats;
 555 };
 556
 557 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
 558    mem-stats.h after hash_table declaration.  */
 559
 560 #include "mem-stats.h"
 561 #include "hash-map.h"
 562
 563 extern mem_alloc_description<mem_usage> hash_table_usage;
 564
 565 /* Support function for statistics.  */
 566 extern void dump_hash_table_loc_statistics (void);
 567
 568 template<typename Descriptor, template<typename Type> class Allocator>
 569 hash_table<Descriptor, Allocator>::hash_table (size_t size, bool ggc, bool
 570                                                gather_mem_stats,
 571                                                mem_alloc_origin origin
 572                                                MEM_STAT_DECL) :
 573   m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
 574   m_ggc (ggc), m_gather_mem_stats (gather_mem_stats)
 575 {
 576   unsigned int size_prime_index;
 577
 578   size_prime_index = hash_table_higher_prime_index (size);
 579   size = prime_tab[size_prime_index].prime;
 580
 581   if (m_gather_mem_stats)
 582     hash_table_usage.register_descriptor (this, origin, ggc
 583                                           FINAL_PASS_MEM_STAT);
 584
 585   m_entries = alloc_entries (size PASS_MEM_STAT);
 586   m_size = size;
 587   m_size_prime_index = size_prime_index;
 588 }
 589
 590 template<typename Descriptor, template<typename Type> class Allocator>
 591 hash_table<Descriptor, Allocator>::hash_table (const hash_table &h, bool ggc,
 592                                                bool gather_mem_stats,
 593                                                mem_alloc_origin origin
 594                                                MEM_STAT_DECL) :
 595   m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
 596   m_searches (0), m_collisions (0), m_ggc (ggc),
 597   m_gather_mem_stats (gather_mem_stats)
 598 {
 599   size_t size = h.m_size;
 600
 601   if (m_gather_mem_stats)
 602     hash_table_usage.register_descriptor (this, origin, ggc
 603                                           FINAL_PASS_MEM_STAT);
 604
 605   value_type *nentries = alloc_entries (size PASS_MEM_STAT);
 606   for (size_t i = 0; i < size; ++i)
 607     {
 608       value_type &entry = h.m_entries[i];
 609       if (is_deleted (entry))
 610         mark_deleted (nentries[i]);
 611       else if (!is_empty (entry))
 612         nentries[i] = entry;
 613     }
 614   m_entries = nentries;
 615   m_size = size;
 616   m_size_prime_index = h.m_size_prime_index;
 617 }
 618
 619 template<typename Descriptor, template<typename Type> class Allocator>
 620 hash_table<Descriptor, Allocator>::~hash_table ()
 621 {
 622   for (size_t i = m_size - 1; i < m_size; i--)
 623     if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
 624       Descriptor::remove (m_entries[i]);
 625
 626   if (!m_ggc)
 627     Allocator <value_type> ::data_free (m_entries);
 628   else
 629     ggc_free (m_entries);
 630
 631   if (m_gather_mem_stats)
 632     hash_table_usage.release_instance_overhead (this,
 633                                                 sizeof (value_type) * m_size,
 634                                                 true);
 635 }
 636
 637 /* This function returns an array of empty hash table elements.  */
 638
 639 template<typename Descriptor, template<typename Type> class Allocator>
 640 inline typename hash_table<Descriptor, Allocator>::value_type *
 641 hash_table<Descriptor, Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const
 642 {
 643   value_type *nentries;
 644
 645   if (m_gather_mem_stats)
 646     hash_table_usage.register_instance_overhead (sizeof (value_type) * n, this);
 647
 648   if (!m_ggc)
 649     nentries = Allocator <value_type> ::data_alloc (n);
 650   else
 651     nentries = ::ggc_cleared_vec_alloc<value_type> (n PASS_MEM_STAT);
 652
 653   gcc_assert (nentries != NULL);
 654   for (size_t i = 0; i < n; i++)
 655     mark_empty (nentries[i]);
 656
 657   return nentries;
 658 }
 659
 660 /* Similar to find_slot, but without several unwanted side effects:
 661     - Does not call equal when it finds an existing entry.
 662     - Does not change the count of elements/searches/collisions in the
 663       hash table.
 664    This function also assumes there are no deleted entries in the table.
 665    HASH is the hash value for the element to be inserted.  */
 666
 667 template<typename Descriptor, template<typename Type> class Allocator>
 668 typename hash_table<Descriptor, Allocator>::value_type *
 669 hash_table<Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash)
 670 {
 671   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
 672   size_t size = m_size;
 673   value_type *slot = m_entries + index;
 674   hashval_t hash2;
 675
 676   if (is_empty (*slot))
 677     return slot;
 678   gcc_checking_assert (!is_deleted (*slot));
 679
 680   hash2 = hash_table_mod2 (hash, m_size_prime_index);
 681   for (;;)
 682     {
 683       index += hash2;
 684       if (index >= size)
 685         index -= size;
 686
 687       slot = m_entries + index;
 688       if (is_empty (*slot))
 689         return slot;
 690       gcc_checking_assert (!is_deleted (*slot));
 691     }
 692 }
 693
 694 /* The following function changes size of memory allocated for the
 695    entries and repeatedly inserts the table elements.  The occupancy
 696    of the table after the call will be about 50%.  Naturally the hash
 697    table must already exist.  Remember also that the place of the
 698    table entries is changed.  If memory allocation fails, this function
 699    will abort.  */
 700
 701 template<typename Descriptor, template<typename Type> class Allocator>
 702 void
 703 hash_table<Descriptor, Allocator>::expand ()
 704 {
 705   value_type *oentries = m_entries;
 706   unsigned int oindex = m_size_prime_index;
 707   size_t osize = size ();
 708   value_type *olimit = oentries + osize;
 709   size_t elts = elements ();
 710
 711   /* Resize only when table after removal of unused elements is either
 712      too full or too empty.  */
 713   unsigned int nindex;
 714   size_t nsize;
 715   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
 716     {
 717       nindex = hash_table_higher_prime_index (elts * 2);
 718       nsize = prime_tab[nindex].prime;
 719     }
 720   else
 721     {
 722       nindex = oindex;
 723       nsize = osize;
 724     }
 725
 726   value_type *nentries = alloc_entries (nsize);
 727
 728   if (m_gather_mem_stats)
 729     hash_table_usage.release_instance_overhead (this, sizeof (value_type)
 730                                                     * osize);
 731
 732   m_entries = nentries;
 733   m_size = nsize;
 734   m_size_prime_index = nindex;
 735   m_n_elements -= m_n_deleted;
 736   m_n_deleted = 0;
 737
 738   value_type *p = oentries;
 739   do
 740     {
 741       value_type &x = *p;
 742
 743       if (!is_empty (x) && !is_deleted (x))
 744         {
 745           value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
 746
 747           *q = x;
 748         }
 749
 750       p++;
 751     }
 752   while (p < olimit);
 753
 754   if (!m_ggc)
 755     Allocator <value_type> ::data_free (oentries);
 756   else
 757     ggc_free (oentries);
 758 }
 759
 760 /* Implements empty() in cases where it isn't a no-op.  */
 761
 762 template<typename Descriptor, template<typename Type> class Allocator>
 763 void
 764 hash_table<Descriptor, Allocator>::empty_slow ()
 765 {
 766   size_t size = m_size;
 767   value_type *entries = m_entries;
 768   int i;
 769
 770   for (i = size - 1; i >= 0; i--)
 771     if (!is_empty (entries[i]) && !is_deleted (entries[i]))
 772       Descriptor::remove (entries[i]);
 773
 774   /* Instead of clearing megabyte, downsize the table.  */
 775   if (size > 1024*1024 / sizeof (PTR))
 776     {
 777       int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
 778       int nsize = prime_tab[nindex].prime;
 779
 780       if (!m_ggc)
 781         Allocator <value_type> ::data_free (m_entries);
 782       else
 783         ggc_free (m_entries);
 784
 785       m_entries = alloc_entries (nsize);
 786       m_size = nsize;
 787       m_size_prime_index = nindex;
 788     }
 789   else
 790     memset (entries, 0, size * sizeof (value_type));
 791   m_n_deleted = 0;
 792   m_n_elements = 0;
 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, template<typename Type> class Allocator>
 800 void
 801 hash_table<Descriptor, Allocator>::clear_slot (value_type *slot)
 802 {
 803   gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
 804                          || is_empty (*slot) || is_deleted (*slot)));
 805
 806   Descriptor::remove (*slot);
 807
 808   mark_deleted (*slot);
 809   m_n_deleted++;
 810 }
 811
 812 /* This function searches for a hash table entry equal to the given
 813    COMPARABLE element starting with the given HASH value.  It cannot
 814    be used to insert or delete an element. */
 815
 816 template<typename Descriptor, template<typename Type> class Allocator>
 817 typename hash_table<Descriptor, Allocator>::value_type &
 818 hash_table<Descriptor, Allocator>
 819 ::find_with_hash (const compare_type &comparable, hashval_t hash)
 820 {
 821   m_searches++;
 822   size_t size = m_size;
 823   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
 824
 825   value_type *entry = &m_entries[index];
 826   if (is_empty (*entry)
 827       || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
 828     return *entry;
 829
 830   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
 831   for (;;)
 832     {
 833       m_collisions++;
 834       index += hash2;
 835       if (index >= size)
 836         index -= size;
 837
 838       entry = &m_entries[index];
 839       if (is_empty (*entry)
 840           || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
 841         return *entry;
 842     }
 843 }
 844
 845 /* This function searches for a hash table slot containing an entry
 846    equal to the given COMPARABLE element and starting with the given
 847    HASH.  To delete an entry, call this with insert=NO_INSERT, then
 848    call clear_slot on the slot returned (possibly after doing some
 849    checks).  To insert an entry, call this with insert=INSERT, then
 850    write the value you want into the returned slot.  When inserting an
 851    entry, NULL may be returned if memory allocation fails. */
 852
 853 template<typename Descriptor, template<typename Type> class Allocator>
 854 typename hash_table<Descriptor, Allocator>::value_type *
 855 hash_table<Descriptor, Allocator>
 856 ::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
 857                        enum insert_option insert)
 858 {
 859   if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
 860     expand ();
 861
 862   m_searches++;
 863
 864   value_type *first_deleted_slot = NULL;
 865   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
 866   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
 867   value_type *entry = &m_entries[index];
 868   size_t size = m_size;
 869   if (is_empty (*entry))
 870     goto empty_entry;
 871   else if (is_deleted (*entry))
 872     first_deleted_slot = &m_entries[index];
 873   else if (Descriptor::equal (*entry, comparable))
 874     return &m_entries[index];
 875
 876   for (;;)
 877     {
 878       m_collisions++;
 879       index += hash2;
 880       if (index >= size)
 881         index -= size;
 882
 883       entry = &m_entries[index];
 884       if (is_empty (*entry))
 885         goto empty_entry;
 886       else if (is_deleted (*entry))
 887         {
 888           if (!first_deleted_slot)
 889             first_deleted_slot = &m_entries[index];
 890         }
 891       else if (Descriptor::equal (*entry, comparable))
 892         return &m_entries[index];
 893     }
 894
 895  empty_entry:
 896   if (insert == NO_INSERT)
 897     return NULL;
 898
 899   if (first_deleted_slot)
 900     {
 901       m_n_deleted--;
 902       mark_empty (*first_deleted_slot);
 903       return first_deleted_slot;
 904     }
 905
 906   m_n_elements++;
 907   return &m_entries[index];
 908 }
 909
 910 /* This function deletes an element with the given COMPARABLE value
 911    from hash table starting with the given HASH.  If there is no
 912    matching element in the hash table, this function does nothing. */
 913
 914 template<typename Descriptor, template<typename Type> class Allocator>
 915 void
 916 hash_table<Descriptor, Allocator>
 917 ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
 918 {
 919   value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
 920   if (is_empty (*slot))
 921     return;
 922
 923   Descriptor::remove (*slot);
 924
 925   mark_deleted (*slot);
 926   m_n_deleted++;
 927 }
 928
 929 /* This function scans over the entire hash table calling CALLBACK for
 930    each live entry.  If CALLBACK returns false, the iteration stops.
 931    ARGUMENT is passed as CALLBACK's second argument. */
 932
 933 template<typename Descriptor,
 934           template<typename Type> class Allocator>
 935 template<typename Argument,
 936           int (*Callback)
 937      (typename hash_table<Descriptor, Allocator>::value_type *slot,
 938       Argument argument)>
 939 void
 940 hash_table<Descriptor, Allocator>::traverse_noresize (Argument argument)
 941 {
 942   value_type *slot = m_entries;
 943   value_type *limit = slot + size ();
 944
 945   do
 946     {
 947       value_type &x = *slot;
 948
 949       if (!is_empty (x) && !is_deleted (x))
 950         if (! Callback (slot, argument))
 951           break;
 952     }
 953   while (++slot < limit);
 954 }
 955
 956 /* Like traverse_noresize, but does resize the table when it is too empty
 957    to improve effectivity of subsequent calls.  */
 958
 959 template <typename Descriptor,
 960           template <typename Type> class Allocator>
 961 template <typename Argument,
 962           int (*Callback)
 963      (typename hash_table<Descriptor, Allocator>::value_type *slot,
 964       Argument argument)>
 965 void
 966 hash_table<Descriptor, Allocator>::traverse (Argument argument)
 967 {
 968   size_t size = m_size;
 969   if (elements () * 8 < size && size > 32)
 970     expand ();
 971
 972   traverse_noresize <Argument, Callback> (argument);
 973 }
 974
 975 /* Slide down the iterator slots until an active entry is found.  */
 976
 977 template<typename Descriptor, template<typename Type> class Allocator>
 978 void
 979 hash_table<Descriptor, Allocator>::iterator::slide ()
 980 {
 981   for ( ; m_slot < m_limit; ++m_slot )
 982     {
 983       value_type &x = *m_slot;
 984       if (!is_empty (x) && !is_deleted (x))
 985         return;
 986     }
 987   m_slot = NULL;
 988   m_limit = NULL;
 989 }
 990
 991 /* Bump the iterator.  */
 992
 993 template<typename Descriptor, template<typename Type> class Allocator>
 994 inline typename hash_table<Descriptor, Allocator>::iterator &
 995 hash_table<Descriptor, Allocator>::iterator::operator ++ ()
 996 {
 997   ++m_slot;
 998   slide ();
 999   return *this;
1000 }
1001
1002
1003 /* Iterate through the elements of hash_table HTAB,
1004    using hash_table <....>::iterator ITER,
1005    storing each element in RESULT, which is of type TYPE.  */
1006
1007 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1008   for ((ITER) = (HTAB).begin (); \
1009        (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1010        ++(ITER))
1011
1012 /* ggc walking routines.  */
1013
1014 template<typename E>
1015 static inline void
1016 gt_ggc_mx (hash_table<E> *h)
1017 {
1018   typedef hash_table<E> table;
1019
1020   if (!ggc_test_and_set_mark (h->m_entries))
1021     return;
1022
1023   for (size_t i = 0; i < h->m_size; i++)
1024     {
1025       if (table::is_empty (h->m_entries[i])
1026           || table::is_deleted (h->m_entries[i]))
1027         continue;
1028
1029       E::ggc_mx (h->m_entries[i]);
1030     }
1031 }
1032
1033 template<typename D>
1034 static inline void
1035 hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
1036                              void *cookie)
1037 {
1038   hash_table<D> *map = static_cast<hash_table<D> *> (h);
1039   gcc_checking_assert (map->m_entries == obj);
1040   for (size_t i = 0; i < map->m_size; i++)
1041     {
1042       typedef hash_table<D> table;
1043       if (table::is_empty (map->m_entries[i])
1044           || table::is_deleted (map->m_entries[i]))
1045         continue;
1046
1047       D::pch_nx (map->m_entries[i], op, cookie);
1048     }
1049 }
1050
1051 template<typename D>
1052 static void
1053 gt_pch_nx (hash_table<D> *h)
1054 {
1055   bool success
1056     = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
1057   gcc_checking_assert (success);
1058   for (size_t i = 0; i < h->m_size; i++)
1059     {
1060       if (hash_table<D>::is_empty (h->m_entries[i])
1061           || hash_table<D>::is_deleted (h->m_entries[i]))
1062         continue;
1063
1064       D::pch_nx (h->m_entries[i]);
1065     }
1066 }
1067
1068 template<typename D>
1069 static inline void
1070 gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
1071 {
1072   op (&h->m_entries, cookie);
1073 }
1074
1075 template<typename H>
1076 inline void
1077 gt_cleare_cache (hash_table<H> *h)
1078 {
1079   extern void gt_ggc_mx (typename H::value_type &t);
1080   typedef hash_table<H> table;
1081   if (!h)
1082     return;
1083
1084   for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
1085     if (!table::is_empty (*iter) && !table::is_deleted (*iter))
1086       {
1087         int res = H::keep_cache_entry (*iter);
1088         if (res == 0)
1089           h->clear_slot (&*iter);
1090         else if (res != -1)
1091           gt_ggc_mx (*iter);
1092       }
1093 }
1094
1095 #endif /* TYPED_HASHTAB_H */