gcc/hash-table.h

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