LCOV - code coverage report
Current view: top level - gcc - hash-table.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 295 297 99.3 %
Date: 2020-03-28 11:57:23 Functions: 2301 2792 82.4 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       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                 :    6211730 : xcallocator <Type>::data_alloc (size_t count)
     274                 :            : {
     275                 :    6211730 :   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                 : 2157200573 : xcallocator <Type>::data_free (Type *memory)
     284                 :            : {
     285                 :  251041308 :   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                 :56207177494 : mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
     324                 :            : {
     325                 :56207177494 :    hashval_t t1, t2, t3, t4, q, r;
     326                 :            : 
     327                 :56207177494 :    t1 = ((uint64_t)x * inv) >> 32;
     328                 :56207177494 :    t2 = x - t1;
     329                 :56207177494 :    t3 = t2 >> 1;
     330                 :56207177494 :    t4 = t1 + t3;
     331                 :56207177494 :    q  = t4 >> shift;
     332                 :56207177494 :    r  = x - (q * y);
     333                 :            : 
     334                 :56207177494 :    return r;
     335                 :            : }
     336                 :            : 
     337                 :            : /* Compute the primary table index for HASH given current prime index.  */
     338                 :            : 
     339                 :            : inline hashval_t
     340                 :50154219628 : hash_table_mod1 (hashval_t hash, unsigned int index)
     341                 :            : {
     342                 :50154219628 :   const struct prime_ent *p = &prime_tab[index];
     343                 :50154219628 :   gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
     344                 :50154219628 :   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                 :25756421537 : hash_table_mod2 (hashval_t hash, unsigned int index)
     351                 :            : {
     352                 :25756421537 :   const struct prime_ent *p = &prime_tab[index];
     353                 :25756421537 :   gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
     354                 :25756421537 :   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                 :   30096810 :   create_ggc (size_t n, bool sanitize_eq_and_hash = true CXX_MEM_STAT_INFO)
     395                 :            :   {
     396                 :   30096810 :     hash_table *table = ggc_alloc<hash_table> ();
     397                 :   30096810 :     new (table) hash_table (n, true, sanitize_eq_and_hash, GATHER_STATISTICS,
     398                 :            :                             HASH_TABLE_ORIGIN PASS_MEM_STAT);
     399                 :   30096810 :     return table;
     400                 :            :   }
     401                 :            : 
     402                 :            :   /* Current size (in entries) of the hash table.  */
     403                 :  775602645 :   size_t size () const { return m_size; }
     404                 :            : 
     405                 :            :   /* Return the current number of elements in this hash table. */
     406                 :  497178417 :   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                 :  274592934 :   void empty () { if (elements ()) empty_slow (); }
     413                 :            : 
     414                 :            :   /* Return true when there are no elements in this hash table.  */
     415                 :   87113290 :   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                 :  617672801 :   value_type &find (const value_type &value)
     429                 :            :     {
     430                 :  628556201 :       return find_with_hash (value, Descriptor::hash (value));
     431                 :            :     }
     432                 :            : 
     433                 : 1081782836 :   value_type *find_slot (const value_type &value, insert_option insert)
     434                 :            :     {
     435                 : 1102304589 :       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                 :     187006 :   void remove_elt (const value_type &value)
     456                 :            :     {
     457                 :     187006 :       remove_elt_with_hash (value, Descriptor::hash (value));
     458                 :     187006 :     }
     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                 :  902358969 :     iterator () : m_slot (NULL), m_limit (NULL) {}
     477                 :            : 
     478                 :  130704591 :     iterator (value_type *slot, value_type *limit) :
     479                 :  130704591 :       m_slot (slot), m_limit (limit) {}
     480                 :            : 
     481                 : 1924698913 :     inline value_type &operator * () { return *m_slot; }
     482                 :            :     void slide ();
     483                 :            :     inline iterator &operator ++ ();
     484                 : 2158060425 :     bool operator != (const iterator &other) const
     485                 :            :       {
     486                 :  449311731 :         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                 :  130704593 :   iterator begin () const
     495                 :            :     {
     496                 :          4 :       if (Lazy && m_entries == NULL)
     497                 :         10 :         return iterator ();
     498                 :  233149734 :       iterator iter (m_entries, m_entries + m_size);
     499                 :         84 :       iter.slide ();
     500                 :          2 :       return iter;
     501                 :            :     }
     502                 :            : 
     503                 : 1890093418 :   iterator end () const { return iterator (); }
     504                 :            : 
     505                 :        136 :   double collisions () const
     506                 :            :     {
     507                 :        136 :       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                 :97875665596 :   static bool is_deleted (value_type &v)
     535                 :            :   {
     536                 :>14460*10^7 :     return Descriptor::is_deleted (v);
     537                 :            :   }
     538                 :            : 
     539                 :>41316*10^7 :   static bool is_empty (value_type &v)
     540                 :            :   {
     541                 :>38345*10^7 :     return Descriptor::is_empty (v);
     542                 :            :   }
     543                 :            : 
     544                 :  397095668 :   static void mark_deleted (value_type &v)
     545                 :            :   {
     546                 :  413477763 :     Descriptor::mark_deleted (v);
     547                 :     465986 :   }
     548                 :            : 
     549                 : 1429943154 :   static void mark_empty (value_type &v)
     550                 :            :   {
     551                 : 1429943154 :     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                 : 1968361202 : 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                 : 1968361202 :   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                 : 1968361202 :   size_prime_index = hash_table_higher_prime_index (size);
     619                 : 1968361202 :   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                 : 1968361202 :   if (Lazy)
     626                 :            :     m_entries = NULL;
     627                 :            :   else
     628                 : 1968236951 :     m_entries = alloc_entries (size PASS_MEM_STAT);
     629                 : 1968361202 :   m_size = size;
     630                 : 1968282910 :   m_size_prime_index = size_prime_index;
     631                 : 1968236951 : }
     632                 :            : 
     633                 :            : template<typename Descriptor, bool Lazy,
     634                 :            :          template<typename Type> class Allocator>
     635                 :    4028450 : 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                 :    4028450 :   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                 :    4028450 :   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                 :    4028450 :   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                 :    4028450 :       value_type *nentries = alloc_entries (size PASS_MEM_STAT);
     660                 :   58761928 :       for (size_t i = 0; i < size; ++i)
     661                 :            :         {
     662                 :   54733371 :           value_type &entry = h.m_entries[i];
     663                 :   54733371 :           if (is_deleted (entry))
     664                 :   54733371 :             mark_deleted (nentries[i]);
     665                 :   54267431 :           else if (!is_empty (entry))
     666                 :   10998262 :             new ((void*) (nentries + i)) value_type (entry);
     667                 :            :         }
     668                 :    4028450 :       m_entries = nentries;
     669                 :            :     }
     670                 :    4028450 :   m_size = size;
     671                 :    4028450 :   m_size_prime_index = h.m_size_prime_index;
     672                 :    4028450 : }
     673                 :            : 
     674                 :            : template<typename Descriptor, bool Lazy,
     675                 :            :          template<typename Type> class Allocator>
     676                 : 1926944639 : hash_table<Descriptor, Lazy, Allocator>::~hash_table ()
     677                 :            : {
     678                 :     124251 :   if (!Lazy || m_entries)
     679                 :            :     {
     680                 :63622564293 :       for (size_t i = m_size - 1; i < m_size; i--)
     681                 :61695727858 :         if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
     682                 :12827508681 :           Descriptor::remove (m_entries[i]);
     683                 :            : 
     684                 : 1926821293 :       if (!m_ggc)
     685                 : 1910397953 :         Allocator <value_type> ::data_free (m_entries);
     686                 :            :       else
     687                 :   16423455 :         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                 : 1926944639 : }
     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                 :    7005478 : 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                 :    7005478 :   if (!m_ggc)
     711                 :    6211730 :     nentries = Allocator <value_type> ::data_alloc (n);
     712                 :            :   else
     713                 :     793748 :     nentries = ::ggc_cleared_vec_alloc<value_type> (n PASS_MEM_STAT);
     714                 :            : 
     715                 :    7005478 :   gcc_assert (nentries != NULL);
     716                 :            :   if (!Descriptor::empty_zero_p)
     717                 : 1289428794 :     for (size_t i = 0; i < n; i++)
     718                 : 1282427146 :       mark_empty (nentries[i]);
     719                 :            : 
     720                 :    7005478 :   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                 : 9051548299 : hash_table<Descriptor, Lazy,
     734                 :            :            Allocator>::find_empty_slot_for_expand (hashval_t hash)
     735                 :            : {
     736                 : 9051548299 :   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
     737                 : 9051548299 :   size_t size = m_size;
     738                 : 9051548299 :   value_type *slot = m_entries + index;
     739                 :            :   hashval_t hash2;
     740                 :            : 
     741                 : 9051548261 :   if (is_empty (*slot))
     742                 :            :     return slot;
     743                 : 1369700720 :   gcc_checking_assert (!is_deleted (*slot));
     744                 :            : 
     745                 : 1369700720 :   hash2 = hash_table_mod2 (hash, m_size_prime_index);
     746                 :            :   for (;;)
     747                 :            :     {
     748                 : 2060630208 :       index += hash2;
     749                 : 2060630208 :       if (index >= size)
     750                 :  934206253 :         index -= size;
     751                 :            : 
     752                 : 2060630208 :       slot = m_entries + index;
     753                 : 2060630238 :       if (is_empty (*slot))
     754                 : 1369700720 :         return slot;
     755                 :  677707049 :       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                 :  248399379 : hash_table<Descriptor, Lazy, Allocator>::too_empty_p (unsigned int elts)
     765                 :            : {
     766                 :  129624118 :   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                 :  249341931 : hash_table<Descriptor, Lazy, Allocator>::expand ()
     780                 :            : {
     781                 :  249341931 :   value_type *oentries = m_entries;
     782                 :  249341931 :   unsigned int oindex = m_size_prime_index;
     783                 :  249341931 :   size_t osize = size ();
     784                 :  249341931 :   value_type *olimit = oentries + osize;
     785                 :  249341931 :   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                 :  249341931 :   if (elts * 2 > osize || too_empty_p (elts))
     792                 :            :     {
     793                 :  245095152 :       nindex = hash_table_higher_prime_index (elts * 2);
     794                 :  245095152 :       nsize = prime_tab[nindex].prime;
     795                 :            :     }
     796                 :            :   else
     797                 :            :     {
     798                 :            :       nindex = oindex;
     799                 :            :       nsize = osize;
     800                 :            :     }
     801                 :            : 
     802                 :  249341931 :   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                 :  249341931 :   m_entries = nentries;
     809                 :  249341931 :   m_size = nsize;
     810                 :  249341931 :   m_size_prime_index = nindex;
     811                 :  249341931 :   m_n_elements -= m_n_deleted;
     812                 :  249341931 :   m_n_deleted = 0;
     813                 :            : 
     814                 :  249341931 :   value_type *p = oentries;
     815                 :            :   do
     816                 :            :     {
     817                 :12232369446 :       value_type &x = *p;
     818                 :            : 
     819                 :12232369426 :       if (!is_empty (x) && !is_deleted (x))
     820                 :            :         {
     821                 : 9108916687 :           value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
     822                 : 9051548299 :           new ((void*) q) value_type (x);
     823                 :            :         }
     824                 :            : 
     825                 :12232369446 :       p++;
     826                 :            :     }
     827                 :12232369446 :   while (p < olimit);
     828                 :            : 
     829                 :  249341931 :   if (!m_ggc)
     830                 :  249341931 :     Allocator <value_type> ::data_free (oentries);
     831                 :            :   else
     832                 :    3285058 :     ggc_free (oentries);
     833                 :  249341931 : }
     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                 :   52101341 : hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
     841                 :            : {
     842                 :   52101341 :   size_t size = m_size;
     843                 :   52101341 :   size_t nsize = size;
     844                 :   52101341 :   value_type *entries = m_entries;
     845                 :            : 
     846                 :  152779196 :   for (size_t i = size - 1; i < size; i--)
     847                 :  100677820 :     if (!is_empty (entries[i]) && !is_deleted (entries[i]))
     848                 :   90557964 :       Descriptor::remove (entries[i]);
     849                 :            : 
     850                 :            :   /* Instead of clearing megabyte, downsize the table.  */
     851                 :   52101341 :   if (size > 1024*1024 / sizeof (value_type))
     852                 :            :     nsize = 1024 / sizeof (value_type);
     853                 :   52101326 :   else if (too_empty_p (m_n_elements))
     854                 :    2049336 :     nsize = m_n_elements * 2;
     855                 :            : 
     856                 :   52101341 :   if (nsize != size)
     857                 :            :     {
     858                 :    2049348 :       unsigned int nindex = hash_table_higher_prime_index (nsize);
     859                 :            : 
     860                 :    2049348 :       nsize = prime_tab[nindex].prime;
     861                 :            : 
     862                 :    2049348 :       if (!m_ggc)
     863                 :     747627 :         Allocator <value_type> ::data_free (m_entries);
     864                 :            :       else
     865                 :    1301721 :         ggc_free (m_entries);
     866                 :            : 
     867                 :    2049348 :       m_entries = alloc_entries (nsize);
     868                 :    2049348 :       m_size = nsize;
     869                 :    2049348 :       m_size_prime_index = nindex;
     870                 :            :     }
     871                 :            :   else if (Descriptor::empty_zero_p)
     872                 :   50020068 :     memset ((void *) entries, 0, size * sizeof (value_type));
     873                 :            :   else
     874                 :     447924 :     for (size_t i = 0; i < size; i++)
     875                 :     415998 :       mark_empty (entries[i]);
     876                 :            : 
     877                 :   52101341 :   m_n_deleted = 0;
     878                 :   52101341 :   m_n_elements = 0;
     879                 :   52101341 : }
     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                 :  391447839 : hash_table<Descriptor, Lazy, Allocator>::clear_slot (value_type *slot)
     889                 :            : {
     890                 :  391447839 :   gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
     891                 :            :                          || is_empty (*slot) || is_deleted (*slot)));
     892                 :            : 
     893                 :  391447839 :   Descriptor::remove (*slot);
     894                 :            : 
     895                 :  391447839 :   mark_deleted (*slot);
     896                 :  391447839 :   m_n_deleted++;
     897                 :  391447839 : }
     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                 :21399188982 : hash_table<Descriptor, Lazy, Allocator>
     907                 :            : ::find_with_hash (const compare_type &comparable, hashval_t hash)
     908                 :            : {
     909                 :21399188982 :   m_searches++;
     910                 :21399188982 :   size_t size = m_size;
     911                 :21399188982 :   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                 :21399188982 :   value_type *entry = &m_entries[index];
     916                 :            :   if (is_empty (*entry)
     917                 :21417654062 :       || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
     918                 :  390120506 :     return *entry;
     919                 :            : 
     920                 : 4683255752 :   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
     921                 :            :   for (;;)
     922                 :            :     {
     923                 :10148562381 :       m_collisions++;
     924                 :10148562381 :       index += hash2;
     925                 :10148562381 :       if (index >= size)
     926                 : 4982991165 :         index -= size;
     927                 :            : 
     928                 :10148562381 :       entry = &m_entries[index];
     929                 :            :       if (is_empty (*entry)
     930                 :10164142256 :           || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
     931                 :            :         {
     932                 :            : #if CHECKING_P
     933                 : 4683255752 :           if (m_sanitize_eq_and_hash)
     934                 : 4565501752 :             verify (comparable, hash);
     935                 :            : #endif
     936                 :  317936766 :           return *entry;
     937                 :            :         }
     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                 :19703468854 : hash_table<Descriptor, Lazy, Allocator>
     953                 :            : ::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
     954                 :            :                        enum insert_option insert)
     955                 :            : {
     956                 :       2286 :   if (Lazy && m_entries == NULL)
     957                 :            :     {
     958                 :        907 :       if (insert == INSERT)
     959                 :        905 :         m_entries = alloc_entries (m_size);
     960                 :            :       else
     961                 :            :         return NULL;
     962                 :            :     }
     963                 :19703468852 :   if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
     964                 :  248501348 :     expand ();
     965                 :            : 
     966                 :            : #if CHECKING_P
     967                 :19703468852 :   if (m_sanitize_eq_and_hash)
     968                 :19093995052 :     verify (comparable, hash);
     969                 :            : #endif
     970                 :            : 
     971                 :19703468852 :   m_searches++;
     972                 :19703468852 :   value_type *first_deleted_slot = NULL;
     973                 :19703468852 :   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
     974                 :19703468852 :   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
     975                 :19703468852 :   value_type *entry = &m_entries[index];
     976                 :19703468852 :   size_t size = m_size;
     977                 :19703468803 :   if (is_empty (*entry))
     978                 : 9262408581 :     goto empty_entry;
     979                 :10441080073 :   else if (is_deleted (*entry))
     980                 :          0 :     first_deleted_slot = &m_entries[index];
     981                 :10294720782 :   else if (Descriptor::equal (*entry, comparable))
     982                 : 1235042622 :     return &m_entries[index];
     983                 :            : 
     984                 :            :   for (;;)
     985                 :            :     {
     986                 :12268237193 :       m_collisions++;
     987                 :12268237193 :       index += hash2;
     988                 :12268237193 :       if (index >= size)
     989                 : 5752655751 :         index -= size;
     990                 :            : 
     991                 :12268237193 :       entry = &m_entries[index];
     992                 :12268237133 :       if (is_empty (*entry))
     993                 : 4461079466 :         goto empty_entry;
     994                 : 7807156490 :       else if (is_deleted (*entry))
     995                 :            :         {
     996                 :  197768573 :           if (!first_deleted_slot)
     997                 :   34644282 :             first_deleted_slot = &m_entries[index];
     998                 :            :         }
     999                 : 8373178338 :       else if (Descriptor::equal (*entry, comparable))
    1000                 :  726958444 :         return &m_entries[index];
    1001                 :            :     }
    1002                 :            : 
    1003                 :13723470101 :  empty_entry:
    1004                 :13723470101 :   if (insert == NO_INSERT)
    1005                 :            :     return NULL;
    1006                 :            : 
    1007                 :11658727669 :   if (first_deleted_slot)
    1008                 :            :     {
    1009                 :  147100019 :       m_n_deleted--;
    1010                 :  147100019 :       mark_empty (*first_deleted_slot);
    1011                 :  147100019 :       return first_deleted_slot;
    1012                 :            :     }
    1013                 :            : 
    1014                 :11801302727 :   m_n_elements++;
    1015                 :11801302727 :   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                 :23654408190 : hash_table<Descriptor, Lazy, Allocator>
    1025                 :            : ::verify (const compare_type &comparable, hashval_t hash)
    1026                 :            : {
    1027                 :>25906*10^7 :   for (size_t i = 0; i < MIN (hash_table_sanitize_eq_limit, m_size); i++)
    1028                 :            :     {
    1029                 :>23540*10^7 :       value_type *entry = &m_entries[i];
    1030                 :>20839*10^7 :       if (!is_empty (*entry) && !is_deleted (*entry)
    1031                 :96551969737 :           && hash != Descriptor::hash (*entry)
    1032                 :>33362*10^7 :           && Descriptor::equal (*entry, comparable))
    1033                 :          0 :         hashtab_chk_error ();
    1034                 :            :     }
    1035                 :23654408190 : }
    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                 :   26748865 : hash_table<Descriptor, Lazy, Allocator>
    1045                 :            : ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
    1046                 :            : {
    1047                 :   26748865 :   value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
    1048                 :   26748865 :   if (slot == NULL)
    1049                 :            :     return;
    1050                 :            : 
    1051                 :   21564107 :   Descriptor::remove (*slot);
    1052                 :            : 
    1053                 :   21564107 :   mark_deleted (*slot);
    1054                 :   21564107 :   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                 :  517456116 : hash_table<Descriptor, Lazy, Allocator>::traverse_noresize (Argument argument)
    1069                 :            : {
    1070                 :            :   if (Lazy && m_entries == NULL)
    1071                 :            :     return;
    1072                 :            : 
    1073                 :  517456116 :   value_type *slot = m_entries;
    1074                 :  517456116 :   value_type *limit = slot + size ();
    1075                 :            : 
    1076                 :            :   do
    1077                 :            :     {
    1078                 :19712396096 :       value_type &x = *slot;
    1079                 :            : 
    1080                 :19712396096 :       if (!is_empty (x) && !is_deleted (x))
    1081                 : 3444114694 :         if (! Callback (slot, argument))
    1082                 :            :           break;
    1083                 :            :     }
    1084                 :19711981092 :   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                 :  191161487 : hash_table<Descriptor, Lazy, Allocator>::traverse (Argument argument)
    1098                 :            : {
    1099                 :  191161487 :   if (too_empty_p (elements ()) && (!Lazy || m_entries))
    1100                 :     840611 :     expand ();
    1101                 :            : 
    1102                 :  191161487 :   traverse_noresize <Argument, Callback> (argument);
    1103                 :  191161487 : }
    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                 : 2027356382 : hash_table<Descriptor, Lazy, Allocator>::iterator::slide ()
    1111                 :            : {
    1112                 :10110980341 :   for ( ; m_slot < m_limit; ++m_slot )
    1113                 :            :     {
    1114                 : 8261763404 :       value_type &x = *m_slot;
    1115                 : 9981146016 :       if (!is_empty (x) && !is_deleted (x))
    1116                 :            :         return;
    1117                 :            :     }
    1118                 :        155 :   m_slot = NULL;
    1119                 :        155 :   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                 : 2027356390 : hash_table<Descriptor, Lazy, Allocator>::iterator::operator ++ ()
    1128                 :            : {
    1129                 : 2027356390 :   ++m_slot;
    1130                 : 1762871485 :   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                 :      13617 : hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
    1170                 :            :                              void *cookie)
    1171                 :            : {
    1172                 :      13617 :   hash_table<D> *map = static_cast<hash_table<D> *> (h);
    1173                 :      13617 :   gcc_checking_assert (map->m_entries == obj);
    1174                 :    4594546 :   for (size_t i = 0; i < map->m_size; i++)
    1175                 :            :     {
    1176                 :            :       typedef hash_table<D> table;
    1177                 :    4580929 :       if (table::is_empty (map->m_entries[i])
    1178                 :    4580929 :           || table::is_deleted (map->m_entries[i]))
    1179                 :    3482069 :         continue;
    1180                 :            : 
    1181                 :    5679787 :       D::pch_nx (map->m_entries[i], op, cookie);
    1182                 :            :     }
    1183                 :      13617 : }
    1184                 :            : 
    1185                 :            : template<typename D>
    1186                 :            : static void
    1187                 :      13617 : gt_pch_nx (hash_table<D> *h)
    1188                 :            : {
    1189                 :      13617 :   bool success
    1190                 :      13617 :     = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
    1191                 :      13617 :   gcc_checking_assert (success);
    1192                 :    4596324 :   for (size_t i = 0; i < h->m_size; i++)
    1193                 :            :     {
    1194                 :    4582707 :       if (hash_table<D>::is_empty (h->m_entries[i])
    1195                 :    4580929 :           || hash_table<D>::is_deleted (h->m_entries[i]))
    1196                 :    3482069 :         continue;
    1197                 :            : 
    1198                 :    5679787 :       D::pch_nx (h->m_entries[i]);
    1199                 :            :     }
    1200                 :      13617 : }
    1201                 :            : 
    1202                 :            : template<typename D>
    1203                 :            : static inline void
    1204                 :       7459 : gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
    1205                 :            : {
    1206                 :       7459 :   op (&h->m_entries, cookie);
    1207                 :       7459 : }
    1208                 :            : 
    1209                 :            : template<typename H>
    1210                 :            : inline void
    1211                 :    8717195 : gt_cleare_cache (hash_table<H> *h)
    1212                 :            : {
    1213                 :            :   typedef hash_table<H> table;
    1214                 :    8717195 :   if (!h)
    1215                 :            :     return;
    1216                 :            : 
    1217                 :  319296568 :   for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
    1218                 :  308542194 :     if (!table::is_empty (*iter) && !table::is_deleted (*iter))
    1219                 :            :       {
    1220                 :  308542194 :         int res = H::keep_cache_entry (*iter);
    1221                 :  221907236 :         if (res == 0)
    1222                 :   28824964 :           h->clear_slot (&*iter);
    1223                 :  212226629 :         else if (res != -1)
    1224                 :  520767823 :           H::ggc_mx (*iter);
    1225                 :            :       }
    1226                 :            : }
    1227                 :            : 
    1228                 :            : #endif /* TYPED_HASHTAB_H */

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.