gcc/hash-table.h

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