gcc/hash-table.h

   1 /* A type-safe hash table template.
   2    Copyright (C) 2012-2015 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   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 the given hash table.  */
 394   void empty ();
 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   value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
 503   value_type *find_empty_slot_for_expand (hashval_t);
 504   void expand ();
 505   static bool is_deleted (value_type &v)
 506   {
 507     return Descriptor::is_deleted (v);
 508   }
 509
 510   static bool is_empty (value_type &v)
 511   {
 512     return Descriptor::is_empty (v);
 513   }
 514
 515   static void mark_deleted (value_type &v)
 516   {
 517     Descriptor::mark_deleted (v);
 518   }
 519
 520   static void mark_empty (value_type &v)
 521   {
 522     Descriptor::mark_empty (v);
 523   }
 524
 525   /* Table itself.  */
 526   typename Descriptor::value_type *m_entries;
 527
 528   size_t m_size;
 529
 530   /* Current number of elements including also deleted elements.  */
 531   size_t m_n_elements;
 532
 533   /* Current number of deleted elements in the table.  */
 534   size_t m_n_deleted;
 535
 536   /* The following member is used for debugging. Its value is number
 537      of all calls of `htab_find_slot' for the hash table. */
 538   unsigned int m_searches;
 539
 540   /* The following member is used for debugging.  Its value is number
 541      of collisions fixed for time of work with the hash table. */
 542   unsigned int m_collisions;
 543
 544   /* Current size (in entries) of the hash table, as an index into the
 545      table of primes.  */
 546   unsigned int m_size_prime_index;
 547
 548   /* if m_entries is stored in ggc memory.  */
 549   bool m_ggc;
 550
 551   /* If we should gather memory statistics for the table.  */
 552   bool m_gather_mem_stats;
 553 };
 554
 555 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
 556    mem-stats.h after hash_table declaration.  */
 557
 558 #include "mem-stats.h"
 559 #include "hash-map.h"
 560
 561 extern mem_alloc_description<mem_usage> hash_table_usage;
 562
 563 /* Support function for statistics.  */
 564 extern void dump_hash_table_loc_statistics (void);
 565
 566 template<typename Descriptor, template<typename Type> class Allocator>
 567 hash_table<Descriptor, Allocator>::hash_table (size_t size, bool ggc, bool
 568                                                gather_mem_stats,
 569                                                mem_alloc_origin origin
 570                                                MEM_STAT_DECL) :
 571   m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
 572   m_ggc (ggc), m_gather_mem_stats (gather_mem_stats)
 573 {
 574   unsigned int size_prime_index;
 575
 576   size_prime_index = hash_table_higher_prime_index (size);
 577   size = prime_tab[size_prime_index].prime;
 578
 579   if (m_gather_mem_stats)
 580     hash_table_usage.register_descriptor (this, origin, ggc
 581                                           FINAL_PASS_MEM_STAT);
 582
 583   m_entries = alloc_entries (size PASS_MEM_STAT);
 584   m_size = size;
 585   m_size_prime_index = size_prime_index;
 586 }
 587
 588 template<typename Descriptor, template<typename Type> class Allocator>
 589 hash_table<Descriptor, Allocator>::hash_table (const hash_table &h, bool ggc,
 590                                                bool gather_mem_stats,
 591                                                mem_alloc_origin origin
 592                                                MEM_STAT_DECL) :
 593   m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
 594   m_searches (0), m_collisions (0), m_ggc (ggc),
 595   m_gather_mem_stats (gather_mem_stats)
 596 {
 597   size_t size = h.m_size;
 598
 599   if (m_gather_mem_stats)
 600     hash_table_usage.register_descriptor (this, origin, ggc
 601                                           FINAL_PASS_MEM_STAT);
 602
 603   value_type *nentries = alloc_entries (size PASS_MEM_STAT);
 604   for (size_t i = 0; i < size; ++i)
 605     {
 606       value_type &entry = h.m_entries[i];
 607       if (is_deleted (entry))
 608         mark_deleted (nentries[i]);
 609       else if (!is_empty (entry))
 610         nentries[i] = entry;
 611     }
 612   m_entries = nentries;
 613   m_size = size;
 614   m_size_prime_index = h.m_size_prime_index;
 615 }
 616
 617 template<typename Descriptor, template<typename Type> class Allocator>
 618 hash_table<Descriptor, Allocator>::~hash_table ()
 619 {
 620   for (size_t i = m_size - 1; i < m_size; i--)
 621     if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
 622       Descriptor::remove (m_entries[i]);
 623
 624   if (!m_ggc)
 625     Allocator <value_type> ::data_free (m_entries);
 626   else
 627     ggc_free (m_entries);
 628
 629   if (m_gather_mem_stats)
 630     hash_table_usage.release_instance_overhead (this,
 631                                                 sizeof (value_type) * m_size,
 632                                                 true);
 633 }
 634
 635 /* This function returns an array of empty hash table elements.  */
 636
 637 template<typename Descriptor, template<typename Type> class Allocator>
 638 inline typename hash_table<Descriptor, Allocator>::value_type *
 639 hash_table<Descriptor, Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const
 640 {
 641   value_type *nentries;
 642
 643   if (m_gather_mem_stats)
 644     hash_table_usage.register_instance_overhead (sizeof (value_type) * n, this);
 645
 646   if (!m_ggc)
 647     nentries = Allocator <value_type> ::data_alloc (n);
 648   else
 649     nentries = ::ggc_cleared_vec_alloc<value_type> (n PASS_MEM_STAT);
 650
 651   gcc_assert (nentries != NULL);
 652   for (size_t i = 0; i < n; i++)
 653     mark_empty (nentries[i]);
 654
 655   return nentries;
 656 }
 657
 658 /* Similar to find_slot, but without several unwanted side effects:
 659     - Does not call equal when it finds an existing entry.
 660     - Does not change the count of elements/searches/collisions in the
 661       hash table.
 662    This function also assumes there are no deleted entries in the table.
 663    HASH is the hash value for the element to be inserted.  */
 664
 665 template<typename Descriptor, template<typename Type> class Allocator>
 666 typename hash_table<Descriptor, Allocator>::value_type *
 667 hash_table<Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash)
 668 {
 669   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
 670   size_t size = m_size;
 671   value_type *slot = m_entries + index;
 672   hashval_t hash2;
 673
 674   if (is_empty (*slot))
 675     return slot;
 676   gcc_checking_assert (!is_deleted (*slot));
 677
 678   hash2 = hash_table_mod2 (hash, m_size_prime_index);
 679   for (;;)
 680     {
 681       index += hash2;
 682       if (index >= size)
 683         index -= size;
 684
 685       slot = m_entries + index;
 686       if (is_empty (*slot))
 687         return slot;
 688       gcc_checking_assert (!is_deleted (*slot));
 689     }
 690 }
 691
 692 /* The following function changes size of memory allocated for the
 693    entries and repeatedly inserts the table elements.  The occupancy
 694    of the table after the call will be about 50%.  Naturally the hash
 695    table must already exist.  Remember also that the place of the
 696    table entries is changed.  If memory allocation fails, this function
 697    will abort.  */
 698
 699 template<typename Descriptor, template<typename Type> class Allocator>
 700 void
 701 hash_table<Descriptor, Allocator>::expand ()
 702 {
 703   value_type *oentries = m_entries;
 704   unsigned int oindex = m_size_prime_index;
 705   size_t osize = size ();
 706   value_type *olimit = oentries + osize;
 707   size_t elts = elements ();
 708
 709   /* Resize only when table after removal of unused elements is either
 710      too full or too empty.  */
 711   unsigned int nindex;
 712   size_t nsize;
 713   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
 714     {
 715       nindex = hash_table_higher_prime_index (elts * 2);
 716       nsize = prime_tab[nindex].prime;
 717     }
 718   else
 719     {
 720       nindex = oindex;
 721       nsize = osize;
 722     }
 723
 724   value_type *nentries = alloc_entries (nsize);
 725
 726   if (m_gather_mem_stats)
 727     hash_table_usage.release_instance_overhead (this, sizeof (value_type)
 728                                                     * osize);
 729
 730   m_entries = nentries;
 731   m_size = nsize;
 732   m_size_prime_index = nindex;
 733   m_n_elements -= m_n_deleted;
 734   m_n_deleted = 0;
 735
 736   value_type *p = oentries;
 737   do
 738     {
 739       value_type &x = *p;
 740
 741       if (!is_empty (x) && !is_deleted (x))
 742         {
 743           value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
 744
 745           *q = x;
 746         }
 747
 748       p++;
 749     }
 750   while (p < olimit);
 751
 752   if (!m_ggc)
 753     Allocator <value_type> ::data_free (oentries);
 754   else
 755     ggc_free (oentries);
 756 }
 757
 758 template<typename Descriptor, template<typename Type> class Allocator>
 759 void
 760 hash_table<Descriptor, Allocator>::empty ()
 761 {
 762   size_t size = m_size;
 763   value_type *entries = m_entries;
 764   int i;
 765
 766   for (i = size - 1; i >= 0; i--)
 767     if (!is_empty (entries[i]) && !is_deleted (entries[i]))
 768       Descriptor::remove (entries[i]);
 769
 770   /* Instead of clearing megabyte, downsize the table.  */
 771   if (size > 1024*1024 / sizeof (PTR))
 772     {
 773       int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
 774       int nsize = prime_tab[nindex].prime;
 775
 776       if (!m_ggc)
 777         Allocator <value_type> ::data_free (m_entries);
 778       else
 779         ggc_free (m_entries);
 780
 781       m_entries = alloc_entries (nsize);
 782       m_size = nsize;
 783       m_size_prime_index = nindex;
 784     }
 785   else
 786     memset (entries, 0, size * sizeof (value_type));
 787   m_n_deleted = 0;
 788   m_n_elements = 0;
 789 }
 790
 791 /* This function clears a specified SLOT in a hash table.  It is
 792    useful when you've already done the lookup and don't want to do it
 793    again. */
 794
 795 template<typename Descriptor, template<typename Type> class Allocator>
 796 void
 797 hash_table<Descriptor, Allocator>::clear_slot (value_type *slot)
 798 {
 799   gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
 800                          || is_empty (*slot) || is_deleted (*slot)));
 801
 802   Descriptor::remove (*slot);
 803
 804   mark_deleted (*slot);
 805   m_n_deleted++;
 806 }
 807
 808 /* This function searches for a hash table entry equal to the given
 809    COMPARABLE element starting with the given HASH value.  It cannot
 810    be used to insert or delete an element. */
 811
 812 template<typename Descriptor, template<typename Type> class Allocator>
 813 typename hash_table<Descriptor, Allocator>::value_type &
 814 hash_table<Descriptor, Allocator>
 815 ::find_with_hash (const compare_type &comparable, hashval_t hash)
 816 {
 817   m_searches++;
 818   size_t size = m_size;
 819   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
 820
 821   value_type *entry = &m_entries[index];
 822   if (is_empty (*entry)
 823       || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
 824     return *entry;
 825
 826   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
 827   for (;;)
 828     {
 829       m_collisions++;
 830       index += hash2;
 831       if (index >= size)
 832         index -= size;
 833
 834       entry = &m_entries[index];
 835       if (is_empty (*entry)
 836           || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
 837         return *entry;
 838     }
 839 }
 840
 841 /* This function searches for a hash table slot containing an entry
 842    equal to the given COMPARABLE element and starting with the given
 843    HASH.  To delete an entry, call this with insert=NO_INSERT, then
 844    call clear_slot on the slot returned (possibly after doing some
 845    checks).  To insert an entry, call this with insert=INSERT, then
 846    write the value you want into the returned slot.  When inserting an
 847    entry, NULL may be returned if memory allocation fails. */
 848
 849 template<typename Descriptor, template<typename Type> class Allocator>
 850 typename hash_table<Descriptor, Allocator>::value_type *
 851 hash_table<Descriptor, Allocator>
 852 ::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
 853                        enum insert_option insert)
 854 {
 855   if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
 856     expand ();
 857
 858   m_searches++;
 859
 860   value_type *first_deleted_slot = NULL;
 861   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
 862   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
 863   value_type *entry = &m_entries[index];
 864   size_t size = m_size;
 865   if (is_empty (*entry))
 866     goto empty_entry;
 867   else if (is_deleted (*entry))
 868     first_deleted_slot = &m_entries[index];
 869   else if (Descriptor::equal (*entry, comparable))
 870     return &m_entries[index];
 871
 872   for (;;)
 873     {
 874       m_collisions++;
 875       index += hash2;
 876       if (index >= size)
 877         index -= size;
 878
 879       entry = &m_entries[index];
 880       if (is_empty (*entry))
 881         goto empty_entry;
 882       else if (is_deleted (*entry))
 883         {
 884           if (!first_deleted_slot)
 885             first_deleted_slot = &m_entries[index];
 886         }
 887       else if (Descriptor::equal (*entry, comparable))
 888         return &m_entries[index];
 889     }
 890
 891  empty_entry:
 892   if (insert == NO_INSERT)
 893     return NULL;
 894
 895   if (first_deleted_slot)
 896     {
 897       m_n_deleted--;
 898       mark_empty (*first_deleted_slot);
 899       return first_deleted_slot;
 900     }
 901
 902   m_n_elements++;
 903   return &m_entries[index];
 904 }
 905
 906 /* This function deletes an element with the given COMPARABLE value
 907    from hash table starting with the given HASH.  If there is no
 908    matching element in the hash table, this function does nothing. */
 909
 910 template<typename Descriptor, template<typename Type> class Allocator>
 911 void
 912 hash_table<Descriptor, Allocator>
 913 ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
 914 {
 915   value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
 916   if (is_empty (*slot))
 917     return;
 918
 919   Descriptor::remove (*slot);
 920
 921   mark_deleted (*slot);
 922   m_n_deleted++;
 923 }
 924
 925 /* This function scans over the entire hash table calling CALLBACK for
 926    each live entry.  If CALLBACK returns false, the iteration stops.
 927    ARGUMENT is passed as CALLBACK's second argument. */
 928
 929 template<typename Descriptor,
 930           template<typename Type> class Allocator>
 931 template<typename Argument,
 932           int (*Callback)
 933      (typename hash_table<Descriptor, Allocator>::value_type *slot,
 934       Argument argument)>
 935 void
 936 hash_table<Descriptor, Allocator>::traverse_noresize (Argument argument)
 937 {
 938   value_type *slot = m_entries;
 939   value_type *limit = slot + size ();
 940
 941   do
 942     {
 943       value_type &x = *slot;
 944
 945       if (!is_empty (x) && !is_deleted (x))
 946         if (! Callback (slot, argument))
 947           break;
 948     }
 949   while (++slot < limit);
 950 }
 951
 952 /* Like traverse_noresize, but does resize the table when it is too empty
 953    to improve effectivity of subsequent calls.  */
 954
 955 template <typename Descriptor,
 956           template <typename Type> class Allocator>
 957 template <typename Argument,
 958           int (*Callback)
 959      (typename hash_table<Descriptor, Allocator>::value_type *slot,
 960       Argument argument)>
 961 void
 962 hash_table<Descriptor, Allocator>::traverse (Argument argument)
 963 {
 964   size_t size = m_size;
 965   if (elements () * 8 < size && size > 32)
 966     expand ();
 967
 968   traverse_noresize <Argument, Callback> (argument);
 969 }
 970
 971 /* Slide down the iterator slots until an active entry is found.  */
 972
 973 template<typename Descriptor, template<typename Type> class Allocator>
 974 void
 975 hash_table<Descriptor, Allocator>::iterator::slide ()
 976 {
 977   for ( ; m_slot < m_limit; ++m_slot )
 978     {
 979       value_type &x = *m_slot;
 980       if (!is_empty (x) && !is_deleted (x))
 981         return;
 982     }
 983   m_slot = NULL;
 984   m_limit = NULL;
 985 }
 986
 987 /* Bump the iterator.  */
 988
 989 template<typename Descriptor, template<typename Type> class Allocator>
 990 inline typename hash_table<Descriptor, Allocator>::iterator &
 991 hash_table<Descriptor, Allocator>::iterator::operator ++ ()
 992 {
 993   ++m_slot;
 994   slide ();
 995   return *this;
 996 }
 997
 998
 999 /* Iterate through the elements of hash_table HTAB,
1000    using hash_table <....>::iterator ITER,
1001    storing each element in RESULT, which is of type TYPE.  */
1002
1003 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
1004   for ((ITER) = (HTAB).begin (); \
1005        (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
1006        ++(ITER))
1007
1008 /* ggc walking routines.  */
1009
1010 template<typename E>
1011 static inline void
1012 gt_ggc_mx (hash_table<E> *h)
1013 {
1014   typedef hash_table<E> table;
1015
1016   if (!ggc_test_and_set_mark (h->m_entries))
1017     return;
1018
1019   for (size_t i = 0; i < h->m_size; i++)
1020     {
1021       if (table::is_empty (h->m_entries[i])
1022           || table::is_deleted (h->m_entries[i]))
1023         continue;
1024
1025       E::ggc_mx (h->m_entries[i]);
1026     }
1027 }
1028
1029 template<typename D>
1030 static inline void
1031 hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
1032                              void *cookie)
1033 {
1034   hash_table<D> *map = static_cast<hash_table<D> *> (h);
1035   gcc_checking_assert (map->m_entries == obj);
1036   for (size_t i = 0; i < map->m_size; i++)
1037     {
1038       typedef hash_table<D> table;
1039       if (table::is_empty (map->m_entries[i])
1040           || table::is_deleted (map->m_entries[i]))
1041         continue;
1042
1043       D::pch_nx (map->m_entries[i], op, cookie);
1044     }
1045 }
1046
1047 template<typename D>
1048 static void
1049 gt_pch_nx (hash_table<D> *h)
1050 {
1051   bool success
1052     = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
1053   gcc_checking_assert (success);
1054   for (size_t i = 0; i < h->m_size; i++)
1055     {
1056       if (hash_table<D>::is_empty (h->m_entries[i])
1057           || hash_table<D>::is_deleted (h->m_entries[i]))
1058         continue;
1059
1060       D::pch_nx (h->m_entries[i]);
1061     }
1062 }
1063
1064 template<typename D>
1065 static inline void
1066 gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
1067 {
1068   op (&h->m_entries, cookie);
1069 }
1070
1071 template<typename H>
1072 inline void
1073 gt_cleare_cache (hash_table<H> *h)
1074 {
1075   extern void gt_ggc_mx (typename H::value_type &t);
1076   typedef hash_table<H> table;
1077   if (!h)
1078     return;
1079
1080   for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
1081     if (!table::is_empty (*iter) && !table::is_deleted (*iter))
1082       {
1083         int res = H::keep_cache_entry (*iter);
1084         if (res == 0)
1085           h->clear_slot (&*iter);
1086         else if (res != -1)
1087           gt_ggc_mx (*iter);
1088       }
1089 }
1090
1091 #endif /* TYPED_HASHTAB_H */