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