LCOV - code coverage report
Current view: top level - gcc - hash-table.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 98.9 % 349 345
Test Date: 2024-03-23 14:05:01 Functions: 88.0 % 5619 4944
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-2024 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                 :  6798325630 : xcallocator <Type>::data_alloc (size_t count)
     274                 :             : {
     275                 :  6798325630 :   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                 :  6796579728 : xcallocator <Type>::data_free (Type *memory)
     284                 :             : {
     285                 :  6796579728 :   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                 : >18104*10^7 : mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
     324                 :             : {
     325                 : >18104*10^7 :    hashval_t t1, t2, t3, t4, q, r;
     326                 :             : 
     327                 : >18104*10^7 :    t1 = ((uint64_t)x * inv) >> 32;
     328                 : >18104*10^7 :    t2 = x - t1;
     329                 : >18104*10^7 :    t3 = t2 >> 1;
     330                 : >18104*10^7 :    t4 = t1 + t3;
     331                 : >18104*10^7 :    q  = t4 >> shift;
     332                 : >18104*10^7 :    r  = x - (q * y);
     333                 :             : 
     334                 : >18104*10^7 :    return r;
     335                 :             : }
     336                 :             : 
     337                 :             : /* Compute the primary table index for HASH given current prime index.  */
     338                 :             : 
     339                 :             : inline hashval_t
     340                 : >11473*10^7 : hash_table_mod1 (hashval_t hash, unsigned int index)
     341                 :             : {
     342                 : >11473*10^7 :   const struct prime_ent *p = &prime_tab[index];
     343                 : >11473*10^7 :   gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
     344                 : >11473*10^7 :   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                 : 66316745947 : hash_table_mod2 (hashval_t hash, unsigned int index)
     351                 :             : {
     352                 : 66316745947 :   const struct prime_ent *p = &prime_tab[index];
     353                 : 66316745947 :   gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
     354                 : 66316745947 :   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                 :    45057183 :   create_ggc (size_t n, bool sanitize_eq_and_hash = true CXX_MEM_STAT_INFO)
     395                 :             :   {
     396                 :    45057183 :     hash_table *table = ggc_alloc<hash_table> ();
     397                 :    45057183 :     new (table) hash_table (n, true, sanitize_eq_and_hash, GATHER_STATISTICS,
     398                 :             :                             HASH_TABLE_ORIGIN PASS_MEM_STAT);
     399                 :    45057183 :     return table;
     400                 :             :   }
     401                 :             : 
     402                 :             :   /* Current size (in entries) of the hash table.  */
     403                 :   937201808 :   size_t size () const { return m_size; }
     404                 :             : 
     405                 :             :   /* Return the current number of elements in this hash table. */
     406                 :  1177186753 :   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                 :   468036197 :   void empty () { if (elements ()) empty_slow (); }
     413                 :             : 
     414                 :             :   /* Return true when there are no elements in this hash table.  */
     415                 :   113780725 :   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                 :   481281743 :   value_type &find (const value_type &value)
     429                 :             :     {
     430                 :   481281743 :       return find_with_hash (value, Descriptor::hash (value));
     431                 :             :     }
     432                 :             : 
     433                 :  1831727142 :   value_type *find_slot (const value_type &value, insert_option insert)
     434                 :             :     {
     435                 :  1834026495 :       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                 :     6112336 :   void remove_elt (const value_type &value)
     456                 :             :     {
     457                 :     6112336 :       remove_elt_with_hash (value, Descriptor::hash (value));
     458                 :     6110686 :     }
     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                 :  2454337004 :     iterator () : m_slot (NULL), m_limit (NULL) {}
     477                 :             : 
     478                 :   313767775 :     iterator (value_type *slot, value_type *limit) :
     479                 :   313767775 :       m_slot (slot), m_limit (limit) {}
     480                 :             : 
     481                 :     7275198 :     inline value_type &operator * () { return *m_slot; }
     482                 :             :     void slide ();
     483                 :             :     inline iterator &operator ++ ();
     484                 :  4364105043 :     bool operator != (const iterator &other) const
     485                 :             :       {
     486                 :  1470129455 :         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                 :   313767779 :   iterator begin () const
     495                 :             :     {
     496                 :           8 :       if (Lazy && m_entries == NULL)
     497                 :           4 :         return iterator ();
     498                 :   313767775 :       check_complete_insertion ();
     499                 :   313767775 :       iterator iter (m_entries, m_entries + m_size);
     500                 :   313767775 :       iter.slide ();
     501                 :   313767775 :       return iter;
     502                 :             :     }
     503                 :             : 
     504                 :  2431863347 :   iterator end () const { return iterator (); }
     505                 :             : 
     506                 :         320 :   double collisions () const
     507                 :             :     {
     508                 :         320 :       return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
     509                 :             :     }
     510                 :             : 
     511                 :             : private:
     512                 :             :   /* FIXME: Make the class assignable.  See pr90959.  */
     513                 :             :   void operator= (hash_table&);
     514                 :             : 
     515                 :             :   template<typename T> friend void gt_ggc_mx (hash_table<T> *);
     516                 :             :   template<typename T> friend void gt_pch_nx (hash_table<T> *);
     517                 :             :   template<typename T> friend void
     518                 :             :     hashtab_entry_note_pointers (void *, void *, gt_pointer_operator, void *);
     519                 :             :   template<typename T, typename U, typename V> friend void
     520                 :             :   gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
     521                 :             :   template<typename T, typename U>
     522                 :             :   friend void gt_pch_nx (hash_set<T, false, U> *, gt_pointer_operator, void *);
     523                 :             :   template<typename T> friend void gt_pch_nx (hash_table<T> *,
     524                 :             :                                               gt_pointer_operator, void *);
     525                 :             : 
     526                 :             :   template<typename T> friend void gt_cleare_cache (hash_table<T> *);
     527                 :             : 
     528                 :             :   void empty_slow ();
     529                 :             : 
     530                 :             :   value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
     531                 :             :   value_type *find_empty_slot_for_expand (hashval_t);
     532                 :             :   void verify (const compare_type &comparable, hashval_t hash);
     533                 :             :   bool too_empty_p (unsigned int);
     534                 :             :   void expand ();
     535                 : >52403*10^7 :   static bool is_deleted (value_type &v)
     536                 :             :   {
     537                 :             :     /* Traits are supposed to avoid recognizing elements as both empty
     538                 :             :        and deleted, but to fail safe in case custom traits fail to do
     539                 :             :        that, make sure we never test for is_deleted without having
     540                 :             :        first ruled out is_empty.  */
     541                 : >52403*10^7 :     gcc_checking_assert (!Descriptor::is_empty (v));
     542                 : >52403*10^7 :     return Descriptor::is_deleted (v);
     543                 :             :   }
     544                 :             : 
     545                 : >13389*10^8 :   static bool is_empty (value_type &v)
     546                 :             :   {
     547                 : >26672*10^7 :     return Descriptor::is_empty (v);
     548                 :             :   }
     549                 :             : 
     550                 :   613278210 :   static void mark_deleted (value_type &v)
     551                 :             :   {
     552                 :   613278210 :     Descriptor::mark_deleted (v);
     553                 :             :     /* Traits are supposed to refuse to set elements as deleted if
     554                 :             :        those would be indistinguishable from empty, but to fail safe
     555                 :             :        in case custom traits fail to do that, check that the
     556                 :             :        just-deleted element does not look empty.  */
     557                 :           0 :     gcc_checking_assert (!Descriptor::is_empty (v));
     558                 :     2535902 :   }
     559                 :             : 
     560                 :  1814614931 :   static void mark_empty (value_type &v)
     561                 :             :   {
     562                 :  1814614931 :     Descriptor::mark_empty (v);
     563                 :             :   }
     564                 :             : 
     565                 :             : public:
     566                 : >10014*10^7 :   void check_complete_insertion () const
     567                 :             :   {
     568                 :             : #if CHECKING_P
     569                 : >10014*10^7 :     if (!m_inserting_slot)
     570                 :             :       return;
     571                 :             : 
     572                 : 33255094286 :     gcc_checking_assert (m_inserting_slot >= &m_entries[0]
     573                 :             :                          && m_inserting_slot < &m_entries[m_size]);
     574                 :             : 
     575                 : 33255094286 :     if (!is_empty (*m_inserting_slot))
     576                 : 33255094286 :       m_inserting_slot = NULL;
     577                 :             :     else
     578                 :           0 :       gcc_unreachable ();
     579                 :             : #endif
     580                 :             :   }
     581                 :             : 
     582                 :             : private:
     583                 : 32649701212 :   value_type *check_insert_slot (value_type *ret)
     584                 :             :   {
     585                 :             : #if CHECKING_P
     586                 :  5548105265 :     gcc_checking_assert (is_empty (*ret));
     587                 : 33266552972 :     m_inserting_slot = ret;
     588                 :             : #endif
     589                 :       60373 :     return ret;
     590                 :             :   }
     591                 :             : 
     592                 :             : #if CHECKING_P
     593                 :             :   mutable value_type *m_inserting_slot;
     594                 :             : #endif
     595                 :             : 
     596                 :             :   /* Table itself.  */
     597                 :             :   value_type *m_entries;
     598                 :             : 
     599                 :             :   size_t m_size;
     600                 :             : 
     601                 :             :   /* Current number of elements including also deleted elements.  */
     602                 :             :   size_t m_n_elements;
     603                 :             : 
     604                 :             :   /* Current number of deleted elements in the table.  */
     605                 :             :   size_t m_n_deleted;
     606                 :             : 
     607                 :             :   /* The following member is used for debugging. Its value is number
     608                 :             :      of all calls of `htab_find_slot' for the hash table. */
     609                 :             :   unsigned int m_searches;
     610                 :             : 
     611                 :             :   /* The following member is used for debugging.  Its value is number
     612                 :             :      of collisions fixed for time of work with the hash table. */
     613                 :             :   unsigned int m_collisions;
     614                 :             : 
     615                 :             :   /* Current size (in entries) of the hash table, as an index into the
     616                 :             :      table of primes.  */
     617                 :             :   unsigned int m_size_prime_index;
     618                 :             : 
     619                 :             :   /* if m_entries is stored in ggc memory.  */
     620                 :             :   bool m_ggc;
     621                 :             : 
     622                 :             :   /* True if the table should be sanitized for equal and hash functions.  */
     623                 :             :   bool m_sanitize_eq_and_hash;
     624                 :             : 
     625                 :             :   /* If we should gather memory statistics for the table.  */
     626                 :             : #if GATHER_STATISTICS
     627                 :             :   bool m_gather_mem_stats;
     628                 :             : #else
     629                 :             :   static const bool m_gather_mem_stats = false;
     630                 :             : #endif
     631                 :             : };
     632                 :             : 
     633                 :             : /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
     634                 :             :    mem-stats.h after hash_table declaration.  */
     635                 :             : 
     636                 :             : #include "mem-stats.h"
     637                 :             : #include "hash-map.h"
     638                 :             : 
     639                 :             : extern mem_alloc_description<mem_usage>& hash_table_usage (void);
     640                 :             : 
     641                 :             : /* Support function for statistics.  */
     642                 :             : extern void dump_hash_table_loc_statistics (void);
     643                 :             : 
     644                 :             : template<typename Descriptor, bool Lazy,
     645                 :             :          template<typename Type> class Allocator>
     646                 :  6092625554 : hash_table<Descriptor, Lazy, Allocator>::hash_table (size_t size, bool ggc,
     647                 :             :                                                      bool sanitize_eq_and_hash,
     648                 :             :                                                      bool gather_mem_stats
     649                 :             :                                                      ATTRIBUTE_UNUSED,
     650                 :             :                                                      mem_alloc_origin origin
     651                 :             :                                                      MEM_STAT_DECL) :
     652                 :             : #if CHECKING_P
     653                 :  6092625554 :   m_inserting_slot (0),
     654                 :             : #endif
     655                 :  6092625554 :   m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
     656                 :  6092625554 :   m_ggc (ggc), m_sanitize_eq_and_hash (sanitize_eq_and_hash)
     657                 :             : #if GATHER_STATISTICS
     658                 :             :   , m_gather_mem_stats (gather_mem_stats)
     659                 :             : #endif
     660                 :             : {
     661                 :             :   unsigned int size_prime_index;
     662                 :             : 
     663                 :  6092625554 :   size_prime_index = hash_table_higher_prime_index (size);
     664                 :  6092625554 :   size = prime_tab[size_prime_index].prime;
     665                 :             : 
     666                 :             :   if (m_gather_mem_stats)
     667                 :             :     hash_table_usage ().register_descriptor (this, origin, ggc
     668                 :             :                                              FINAL_PASS_MEM_STAT);
     669                 :             : 
     670                 :             :   if (Lazy)
     671                 :     1507222 :     m_entries = NULL;
     672                 :             :   else
     673                 :  6091118332 :     m_entries = alloc_entries (size PASS_MEM_STAT);
     674                 :  6092625554 :   m_size = size;
     675                 :  6092625554 :   m_size_prime_index = size_prime_index;
     676                 :  6091118332 : }
     677                 :             : 
     678                 :             : template<typename Descriptor, bool Lazy,
     679                 :             :          template<typename Type> class Allocator>
     680                 :    61720647 : hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h,
     681                 :             :                                                      bool ggc,
     682                 :             :                                                      bool sanitize_eq_and_hash,
     683                 :             :                                                      bool gather_mem_stats
     684                 :             :                                                      ATTRIBUTE_UNUSED,
     685                 :             :                                                      mem_alloc_origin origin
     686                 :             :                                                      MEM_STAT_DECL) :
     687                 :             : #if CHECKING_P
     688                 :    61720647 :   m_inserting_slot (0),
     689                 :             : #endif
     690                 :    61720647 :   m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
     691                 :    61720647 :   m_searches (0), m_collisions (0), m_ggc (ggc),
     692                 :    61720647 :   m_sanitize_eq_and_hash (sanitize_eq_and_hash)
     693                 :             : #if GATHER_STATISTICS
     694                 :             :   , m_gather_mem_stats (gather_mem_stats)
     695                 :             : #endif
     696                 :             : {
     697                 :    61720647 :   h.check_complete_insertion ();
     698                 :             : 
     699                 :    61720647 :   size_t size = h.m_size;
     700                 :             : 
     701                 :             :   if (m_gather_mem_stats)
     702                 :             :     hash_table_usage ().register_descriptor (this, origin, ggc
     703                 :             :                                           FINAL_PASS_MEM_STAT);
     704                 :             : 
     705                 :             :   if (Lazy && h.m_entries == NULL)
     706                 :             :     m_entries = NULL;
     707                 :             :   else
     708                 :             :     {
     709                 :    61720647 :       value_type *nentries = alloc_entries (size PASS_MEM_STAT);
     710                 :   866515194 :       for (size_t i = 0; i < size; ++i)
     711                 :             :         {
     712                 :   804794547 :           value_type &entry = h.m_entries[i];
     713                 :   804794547 :           if (is_empty (entry))
     714                 :   758690566 :             continue;
     715                 :    46103981 :           else if (is_deleted (entry))
     716                 :     2531556 :             mark_deleted (nentries[i]);
     717                 :             :           else
     718                 :    43572425 :             new ((void*) (nentries + i)) value_type (entry);
     719                 :             :         }
     720                 :    61720647 :       m_entries = nentries;
     721                 :             :     }
     722                 :    61720647 :   m_size = size;
     723                 :    61720647 :   m_size_prime_index = h.m_size_prime_index;
     724                 :    61720647 : }
     725                 :             : 
     726                 :             : template<typename Descriptor, bool Lazy,
     727                 :             :          template<typename Type> class Allocator>
     728                 :  6111888593 : hash_table<Descriptor, Lazy, Allocator>::~hash_table ()
     729                 :             : {
     730                 :  6111888593 :   check_complete_insertion ();
     731                 :             : 
     732                 :     1507222 :   if (!Lazy || m_entries)
     733                 :             :     {
     734                 : >13696*10^7 :       for (size_t i = m_size - 1; i < m_size; i--)
     735                 : >13085*10^7 :         if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
     736                 :   920563034 :           Descriptor::remove (m_entries[i]);
     737                 :             : 
     738                 :  6110802085 :       if (!m_ggc)
     739                 :  6086151120 :         Allocator <value_type> ::data_free (m_entries);
     740                 :             :       else
     741                 :    24650965 :         ggc_free (m_entries);
     742                 :             :       if (m_gather_mem_stats)
     743                 :             :         hash_table_usage ().release_instance_overhead (this,
     744                 :             :                                                        sizeof (value_type)
     745                 :             :                                                        * m_size, true);
     746                 :             :     }
     747                 :             :   else if (m_gather_mem_stats)
     748                 :             :     hash_table_usage ().unregister_descriptor (this);
     749                 :  6111888593 : }
     750                 :             : 
     751                 :             : /* This function returns an array of empty hash table elements.  */
     752                 :             : 
     753                 :             : template<typename Descriptor, bool Lazy,
     754                 :             :          template<typename Type> class Allocator>
     755                 :             : inline typename hash_table<Descriptor, Lazy, Allocator>::value_type *
     756                 :  6882730927 : hash_table<Descriptor, Lazy,
     757                 :             :            Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const
     758                 :             : {
     759                 :             :   value_type *nentries;
     760                 :             : 
     761                 :             :   if (m_gather_mem_stats)
     762                 :             :     hash_table_usage ().register_instance_overhead (sizeof (value_type) * n, this);
     763                 :             : 
     764                 :  6882730927 :   if (!m_ggc)
     765                 :  6798325630 :     nentries = Allocator <value_type> ::data_alloc (n);
     766                 :             :   else
     767                 :    84405297 :     nentries = ::ggc_cleared_vec_alloc<value_type> (n PASS_MEM_STAT);
     768                 :             : 
     769                 :   110605693 :   gcc_assert (nentries != NULL);
     770                 :             :   if (!Descriptor::empty_zero_p)
     771                 :  1603991104 :     for (size_t i = 0; i < n; i++)
     772                 :  1576841476 :       mark_empty (nentries[i]);
     773                 :             : 
     774                 :  6882730927 :   return nentries;
     775                 :             : }
     776                 :             : 
     777                 :             : /* Similar to find_slot, but without several unwanted side effects:
     778                 :             :     - Does not call equal when it finds an existing entry.
     779                 :             :     - Does not change the count of elements/searches/collisions in the
     780                 :             :       hash table.
     781                 :             :    This function also assumes there are no deleted entries in the table.
     782                 :             :    HASH is the hash value for the element to be inserted.  */
     783                 :             : 
     784                 :             : template<typename Descriptor, bool Lazy,
     785                 :             :          template<typename Type> class Allocator>
     786                 :             : typename hash_table<Descriptor, Lazy, Allocator>::value_type *
     787                 : 22147416739 : hash_table<Descriptor, Lazy,
     788                 :             :            Allocator>::find_empty_slot_for_expand (hashval_t hash)
     789                 :             : {
     790                 : 22147416739 :   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
     791                 : 22147416739 :   size_t size = m_size;
     792                 : 22147416739 :   value_type *slot = m_entries + index;
     793                 :             :   hashval_t hash2;
     794                 :             : 
     795                 : 22147428490 :   if (is_empty (*slot))
     796                 :             :     return slot;
     797                 :  3550686339 :   gcc_checking_assert (!is_deleted (*slot));
     798                 :             : 
     799                 :  3550686339 :   hash2 = hash_table_mod2 (hash, m_size_prime_index);
     800                 :             :   for (;;)
     801                 :             :     {
     802                 :  5069331505 :       index += hash2;
     803                 :  5069331505 :       if (index >= size)
     804                 :  2415858542 :         index -= size;
     805                 :             : 
     806                 :  5069331505 :       slot = m_entries + index;
     807                 :  5069331505 :       if (is_empty (*slot))
     808                 :  3550686339 :         return slot;
     809                 :  1518645166 :       gcc_checking_assert (!is_deleted (*slot));
     810                 :             :     }
     811                 :             : }
     812                 :             : 
     813                 :             : /* Return true if the current table is excessively big for ELTS elements.  */
     814                 :             : 
     815                 :             : template<typename Descriptor, bool Lazy,
     816                 :             :          template<typename Type> class Allocator>
     817                 :             : inline bool
     818                 :   333433870 : hash_table<Descriptor, Lazy, Allocator>::too_empty_p (unsigned int elts)
     819                 :             : {
     820                 :   170002863 :   return elts * 8 < m_size && m_size > 32;
     821                 :             : }
     822                 :             : 
     823                 :             : /* The following function changes size of memory allocated for the
     824                 :             :    entries and repeatedly inserts the table elements.  The occupancy
     825                 :             :    of the table after the call will be about 50%.  Naturally the hash
     826                 :             :    table must already exist.  Remember also that the place of the
     827                 :             :    table entries is changed.  If memory allocation fails, this function
     828                 :             :    will abort.  */
     829                 :             : 
     830                 :             : template<typename Descriptor, bool Lazy,
     831                 :             :          template<typename Type> class Allocator>
     832                 :             : void
     833                 :   724304500 : hash_table<Descriptor, Lazy, Allocator>::expand ()
     834                 :             : {
     835                 :   724304500 :   check_complete_insertion ();
     836                 :             : 
     837                 :   724304500 :   value_type *oentries = m_entries;
     838                 :   724304500 :   unsigned int oindex = m_size_prime_index;
     839                 :   724304500 :   size_t osize = size ();
     840                 :   724304500 :   value_type *olimit = oentries + osize;
     841                 :   724304500 :   size_t elts = elements ();
     842                 :             : 
     843                 :             :   /* Resize only when table after removal of unused elements is either
     844                 :             :      too full or too empty.  */
     845                 :             :   unsigned int nindex;
     846                 :             :   size_t nsize;
     847                 :   724304500 :   if (elts * 2 > osize || too_empty_p (elts))
     848                 :             :     {
     849                 :   717383941 :       nindex = hash_table_higher_prime_index (elts * 2);
     850                 :   717383941 :       nsize = prime_tab[nindex].prime;
     851                 :             :     }
     852                 :             :   else
     853                 :             :     {
     854                 :             :       nindex = oindex;
     855                 :             :       nsize = osize;
     856                 :             :     }
     857                 :             : 
     858                 :   724304500 :   value_type *nentries = alloc_entries (nsize);
     859                 :             : 
     860                 :             :   if (m_gather_mem_stats)
     861                 :             :     hash_table_usage ().release_instance_overhead (this, sizeof (value_type)
     862                 :             :                                                     * osize);
     863                 :             : 
     864                 :   724304500 :   size_t n_deleted = m_n_deleted;
     865                 :             : 
     866                 :   724304500 :   m_entries = nentries;
     867                 :   724304500 :   m_size = nsize;
     868                 :   724304500 :   m_size_prime_index = nindex;
     869                 :   724304500 :   m_n_elements -= m_n_deleted;
     870                 :   724304500 :   m_n_deleted = 0;
     871                 :             : 
     872                 :   724304500 :   size_t n_elements = m_n_elements;
     873                 :             : 
     874                 :   724304500 :   value_type *p = oentries;
     875                 :             :   do
     876                 :             :     {
     877                 : 29731807828 :       value_type &x = *p;
     878                 :             : 
     879                 : 29731871336 :       if (is_empty (x))
     880                 :             :         ;
     881                 : 22330592115 :       else if (is_deleted (x))
     882                 :   183175376 :         n_deleted--;
     883                 :             :       else
     884                 :             :         {
     885                 : 22147416739 :           n_elements--;
     886                 : 22149130876 :           value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
     887                 : 22147416739 :           new ((void*) q) value_type (std::move (x));
     888                 :             :           /* After the resources of 'x' have been moved to a new object at 'q',
     889                 :             :              we now have to destroy the 'x' object, to end its lifetime.  */
     890                 : 22147416739 :           x.~value_type ();
     891                 :             :         }
     892                 :             : 
     893                 : 29731807828 :       p++;
     894                 :             :     }
     895                 : 29731807828 :   while (p < olimit);
     896                 :             : 
     897                 :   724304500 :   gcc_checking_assert (!n_elements && !n_deleted);
     898                 :             : 
     899                 :   724304500 :   if (!m_ggc)
     900                 :   709559646 :     Allocator <value_type> ::data_free (oentries);
     901                 :             :   else
     902                 :    14744854 :     ggc_free (oentries);
     903                 :   724304500 : }
     904                 :             : 
     905                 :             : /* Implements empty() in cases where it isn't a no-op.  */
     906                 :             : 
     907                 :             : template<typename Descriptor, bool Lazy,
     908                 :             :          template<typename Type> class Allocator>
     909                 :             : void
     910                 :    86914426 : hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
     911                 :             : {
     912                 :    86914426 :   check_complete_insertion ();
     913                 :             : 
     914                 :    86914426 :   size_t size = m_size;
     915                 :    86914426 :   size_t nsize = size;
     916                 :    86914426 :   value_type *entries = m_entries;
     917                 :             : 
     918                 :  8274594714 :   for (size_t i = size - 1; i < size; i--)
     919                 :  8187680288 :     if (!is_empty (entries[i]) && !is_deleted (entries[i]))
     920                 :    23663117 :       Descriptor::remove (entries[i]);
     921                 :             : 
     922                 :             :   /* Instead of clearing megabyte, downsize the table.  */
     923                 :    86914426 :   if (size > 1024*1024 / sizeof (value_type))
     924                 :             :     nsize = 1024 / sizeof (value_type);
     925                 :    86914408 :   else if (too_empty_p (m_n_elements))
     926                 :     5166716 :     nsize = m_n_elements * 2;
     927                 :             : 
     928                 :    86914408 :   if (nsize != size)
     929                 :             :     {
     930                 :     5166734 :       unsigned int nindex = hash_table_higher_prime_index (nsize);
     931                 :             : 
     932                 :     5166734 :       nsize = prime_tab[nindex].prime;
     933                 :             : 
     934                 :     5166734 :       if (!m_ggc)
     935                 :      868962 :         Allocator <value_type> ::data_free (m_entries);
     936                 :             :       else
     937                 :     4297772 :         ggc_free (m_entries);
     938                 :             : 
     939                 :     5166734 :       m_entries = alloc_entries (nsize);
     940                 :     5166734 :       m_size = nsize;
     941                 :     5166734 :       m_size_prime_index = nindex;
     942                 :             :     }
     943                 :             :   else if (Descriptor::empty_zero_p)
     944                 :    81747058 :     memset ((void *) entries, 0, size * sizeof (value_type));
     945                 :             :   else
     946                 :        9068 :     for (size_t i = 0; i < size; i++)
     947                 :        8434 :       mark_empty (entries[i]);
     948                 :             : 
     949                 :    86914426 :   m_n_deleted = 0;
     950                 :    86914426 :   m_n_elements = 0;
     951                 :    86914426 : }
     952                 :             : 
     953                 :             : /* This function clears a specified SLOT in a hash table.  It is
     954                 :             :    useful when you've already done the lookup and don't want to do it
     955                 :             :    again. */
     956                 :             : 
     957                 :             : template<typename Descriptor, bool Lazy,
     958                 :             :          template<typename Type> class Allocator>
     959                 :             : void
     960                 :   531055732 : hash_table<Descriptor, Lazy, Allocator>::clear_slot (value_type *slot)
     961                 :             : {
     962                 :   531055732 :   check_complete_insertion ();
     963                 :             : 
     964                 :   531055732 :   gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
     965                 :             :                          || is_empty (*slot) || is_deleted (*slot)));
     966                 :             : 
     967                 :   531055732 :   Descriptor::remove (*slot);
     968                 :             : 
     969                 :   531055732 :   mark_deleted (*slot);
     970                 :   531055732 :   m_n_deleted++;
     971                 :   531055732 : }
     972                 :             : 
     973                 :             : /* This function searches for a hash table entry equal to the given
     974                 :             :    COMPARABLE element starting with the given HASH value.  It cannot
     975                 :             :    be used to insert or delete an element. */
     976                 :             : 
     977                 :             : template<typename Descriptor, bool Lazy,
     978                 :             :          template<typename Type> class Allocator>
     979                 :             : typename hash_table<Descriptor, Lazy, Allocator>::value_type &
     980                 : 38784858167 : hash_table<Descriptor, Lazy, Allocator>
     981                 :             : ::find_with_hash (const compare_type &comparable, hashval_t hash)
     982                 :             : {
     983                 : 38784858167 :   m_searches++;
     984                 : 38784858167 :   size_t size = m_size;
     985                 : 38784858167 :   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
     986                 :             : 
     987                 :             :   if (Lazy && m_entries == NULL)
     988                 :             :     m_entries = alloc_entries (size);
     989                 :             : 
     990                 : 38784858167 :   check_complete_insertion ();
     991                 :             : 
     992                 :             : #if CHECKING_P
     993                 : 38784858167 :   if (m_sanitize_eq_and_hash)
     994                 : 38784858167 :     verify (comparable, hash);
     995                 :             : #endif
     996                 :             : 
     997                 : 38784858167 :   value_type *entry = &m_entries[index];
     998                 : 38786226500 :   if (is_empty (*entry)
     999                 : 38794156984 :       || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
    1000                 :   861958098 :     return *entry;
    1001                 :             : 
    1002                 :  8966796726 :   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
    1003                 :             :   for (;;)
    1004                 :             :     {
    1005                 : 19181683899 :       m_collisions++;
    1006                 : 19181683899 :       index += hash2;
    1007                 : 19181683899 :       if (index >= size)
    1008                 :  9417980826 :         index -= size;
    1009                 :             : 
    1010                 : 19181683899 :       entry = &m_entries[index];
    1011                 : 19214330712 :       if (is_empty (*entry)
    1012                 : 19219615367 :           || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
    1013                 :  8966796726 :         return *entry;
    1014                 :             :     }
    1015                 :             : }
    1016                 :             : 
    1017                 :             : /* This function searches for a hash table slot containing an entry
    1018                 :             :    equal to the given COMPARABLE element and starting with the given
    1019                 :             :    HASH.  To delete an entry, call this with insert=NO_INSERT, then
    1020                 :             :    call clear_slot on the slot returned (possibly after doing some
    1021                 :             :    checks).  To insert an entry, call this with insert=INSERT, then
    1022                 :             :    write the value you want into the returned slot.  When inserting an
    1023                 :             :    entry, NULL may be returned if memory allocation fails. */
    1024                 :             : 
    1025                 :             : template<typename Descriptor, bool Lazy,
    1026                 :             :          template<typename Type> class Allocator>
    1027                 :             : typename hash_table<Descriptor, Lazy, Allocator>::value_type *
    1028                 : 53799262886 : hash_table<Descriptor, Lazy, Allocator>
    1029                 :             : ::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
    1030                 :             :                        enum insert_option insert)
    1031                 :             : {
    1032                 :     1402384 :   if (Lazy && m_entries == NULL)
    1033                 :             :     {
    1034                 :      420718 :       if (insert == INSERT)
    1035                 :      420714 :         m_entries = alloc_entries (m_size);
    1036                 :             :       else
    1037                 :             :         return NULL;
    1038                 :             :     }
    1039                 : 53799262882 :   if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
    1040                 :   723183787 :     expand ();
    1041                 :             :   else
    1042                 : 53076079095 :     check_complete_insertion ();
    1043                 :             : 
    1044                 :             : #if CHECKING_P
    1045                 : 53799262882 :   if (m_sanitize_eq_and_hash)
    1046                 : 53049316887 :     verify (comparable, hash);
    1047                 :             : #endif
    1048                 :             : 
    1049                 : 53799262882 :   m_searches++;
    1050                 : 53799262882 :   value_type *first_deleted_slot = NULL;
    1051                 : 53799262882 :   hashval_t index = hash_table_mod1 (hash, m_size_prime_index);
    1052                 : 53799262882 :   hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index);
    1053                 : 53799262882 :   value_type *entry = &m_entries[index];
    1054                 : 53799262882 :   size_t size = m_size;
    1055                 : 53799262882 :   if (is_empty (*entry))
    1056                 : 30083411454 :     goto empty_entry;
    1057                 : 23715851428 :   else if (is_deleted (*entry))
    1058                 :             :     first_deleted_slot = &m_entries[index];
    1059                 : 23455540312 :   else if (Descriptor::equal (*entry, comparable))
    1060                 :  2216839995 :     return &m_entries[index];
    1061                 :             : 
    1062                 :             :   for (;;)
    1063                 :             :     {
    1064                 : 30667710252 :       m_collisions++;
    1065                 : 30667710252 :       index += hash2;
    1066                 : 30667710252 :       if (index >= size)
    1067                 : 14742718742 :         index -= size;
    1068                 :             : 
    1069                 : 30667710252 :       entry = &m_entries[index];
    1070                 : 30667710252 :       if (is_empty (*entry))
    1071                 : 11706209002 :         goto empty_entry;
    1072                 : 18961501250 :       else if (is_deleted (*entry))
    1073                 :             :         {
    1074                 :   235429156 :           if (!first_deleted_slot)
    1075                 : 16844002603 :             first_deleted_slot = &m_entries[index];
    1076                 :             :         }
    1077                 : 18726449061 :       else if (Descriptor::equal (*entry, comparable))
    1078                 :  2117498647 :         return &m_entries[index];
    1079                 :             :     }
    1080                 :             : 
    1081                 : 41789620456 :  empty_entry:
    1082                 : 41789620456 :   if (insert == NO_INSERT)
    1083                 :             :     return NULL;
    1084                 :             : 
    1085                 : 33266552972 :   if (first_deleted_slot)
    1086                 :             :     {
    1087                 :   237765021 :       m_n_deleted--;
    1088                 :   237765021 :       mark_empty (*first_deleted_slot);
    1089                 :   237765021 :       return check_insert_slot (first_deleted_slot);
    1090                 :             :     }
    1091                 :             : 
    1092                 : 33028787951 :   m_n_elements++;
    1093                 : 33028787951 :   return check_insert_slot (&m_entries[index]);
    1094                 :             : }
    1095                 :             : 
    1096                 :             : /* Verify that all existing elements in the hash table which are
    1097                 :             :    equal to COMPARABLE have an equal HASH value provided as argument.
    1098                 :             :    Also check that the hash table element counts are correct.  */
    1099                 :             : 
    1100                 :             : template<typename Descriptor, bool Lazy,
    1101                 :             :          template<typename Type> class Allocator>
    1102                 :             : void
    1103                 : 91834175054 : hash_table<Descriptor, Lazy, Allocator>
    1104                 :             : ::verify (const compare_type &comparable, hashval_t hash)
    1105                 :             : {
    1106                 : 91834175054 :   size_t n_elements = m_n_elements;
    1107                 : 91834175054 :   size_t n_deleted = m_n_deleted;
    1108                 : >10073*10^8 :   for (size_t i = 0; i < MIN (hash_table_sanitize_eq_limit, m_size); i++)
    1109                 :             :     {
    1110                 : >91551*10^7 :       value_type *entry = &m_entries[i];
    1111                 : >91551*10^7 :       if (!is_empty (*entry))
    1112                 :             :         {
    1113                 : >36115*10^7 :           n_elements--;
    1114                 : >36115*10^7 :           if (is_deleted (*entry))
    1115                 : 19591358173 :             n_deleted--;
    1116                 : >34149*10^7 :           else if (hash != Descriptor::hash (*entry)
    1117                 : >34283*10^7 :                    && Descriptor::equal (*entry, comparable))
    1118                 :           0 :             hashtab_chk_error ();
    1119                 :             :         }
    1120                 :             :     }
    1121                 : 91834175054 :   if (hash_table_sanitize_eq_limit >= m_size)
    1122                 :   333140517 :     gcc_checking_assert (!n_elements && !n_deleted);
    1123                 : 91834175054 : }
    1124                 :             : 
    1125                 :             : /* This function deletes an element with the given COMPARABLE value
    1126                 :             :    from hash table starting with the given HASH.  If there is no
    1127                 :             :    matching element in the hash table, this function does nothing. */
    1128                 :             : 
    1129                 :             : template<typename Descriptor, bool Lazy,
    1130                 :             :          template<typename Type> class Allocator>
    1131                 :             : void
    1132                 :   219650194 : hash_table<Descriptor, Lazy, Allocator>
    1133                 :             : ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
    1134                 :             : {
    1135                 :   219650194 :   check_complete_insertion ();
    1136                 :             : 
    1137                 :   219650194 :   value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
    1138                 :   219650194 :   if (slot == NULL)
    1139                 :             :     return;
    1140                 :             : 
    1141                 :    79693501 :   Descriptor::remove (*slot);
    1142                 :             : 
    1143                 :    79693501 :   mark_deleted (*slot);
    1144                 :    79693501 :   m_n_deleted++;
    1145                 :             : }
    1146                 :             : 
    1147                 :             : /* This function scans over the entire hash table calling CALLBACK for
    1148                 :             :    each live entry.  If CALLBACK returns false, the iteration stops.
    1149                 :             :    ARGUMENT is passed as CALLBACK's second argument. */
    1150                 :             : 
    1151                 :             : template<typename Descriptor, bool Lazy,
    1152                 :             :           template<typename Type> class Allocator>
    1153                 :             : template<typename Argument,
    1154                 :             :          int (*Callback)
    1155                 :             :          (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
    1156                 :             :          Argument argument)>
    1157                 :             : void
    1158                 :   238563320 : hash_table<Descriptor, Lazy, Allocator>::traverse_noresize (Argument argument)
    1159                 :             : {
    1160                 :             :   if (Lazy && m_entries == NULL)
    1161                 :             :     return;
    1162                 :             : 
    1163                 :   238563320 :   check_complete_insertion ();
    1164                 :             : 
    1165                 :   238563320 :   value_type *slot = m_entries;
    1166                 :   238563320 :   value_type *limit = slot + size ();
    1167                 :             : 
    1168                 :             :   do
    1169                 :             :     {
    1170                 : 10928701021 :       value_type &x = *slot;
    1171                 :             : 
    1172                 : 10928701021 :       if (!is_empty (x) && !is_deleted (x))
    1173                 :  3792550549 :         if (! Callback (slot, argument))
    1174                 :             :           break;
    1175                 :             :     }
    1176                 : 10928533310 :   while (++slot < limit);
    1177                 :             : }
    1178                 :             : 
    1179                 :             : /* Like traverse_noresize, but does resize the table when it is too empty
    1180                 :             :    to improve effectivity of subsequent calls.  */
    1181                 :             : 
    1182                 :             : template <typename Descriptor, bool Lazy,
    1183                 :             :           template <typename Type> class Allocator>
    1184                 :             : template <typename Argument,
    1185                 :             :           int (*Callback)
    1186                 :             :           (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
    1187                 :             :           Argument argument)>
    1188                 :             : void
    1189                 :   238418381 : hash_table<Descriptor, Lazy, Allocator>::traverse (Argument argument)
    1190                 :             : {
    1191                 :   238418381 :   if (too_empty_p (elements ()) && (!Lazy || m_entries))
    1192                 :     1120713 :     expand ();
    1193                 :             : 
    1194                 :   238418381 :   traverse_noresize <Argument, Callback> (argument);
    1195                 :   238418381 : }
    1196                 :             : 
    1197                 :             : /* Slide down the iterator slots until an active entry is found.  */
    1198                 :             : 
    1199                 :             : template<typename Descriptor, bool Lazy,
    1200                 :             :          template<typename Type> class Allocator>
    1201                 :             : void
    1202                 :  4364105067 : hash_table<Descriptor, Lazy, Allocator>::iterator::slide ()
    1203                 :             : {
    1204                 : 17189959015 :   for ( ; m_slot < m_limit; ++m_slot )
    1205                 :             :     {
    1206                 : 16877493151 :       value_type &x = *m_slot;
    1207                 : 16877493151 :       if (!is_empty (x) && !is_deleted (x))
    1208                 :             :         return;
    1209                 :             :     }
    1210                 :   312465864 :   m_slot = NULL;
    1211                 :   312465864 :   m_limit = NULL;
    1212                 :             : }
    1213                 :             : 
    1214                 :             : /* Bump the iterator.  */
    1215                 :             : 
    1216                 :             : template<typename Descriptor, bool Lazy,
    1217                 :             :          template<typename Type> class Allocator>
    1218                 :             : inline typename hash_table<Descriptor, Lazy, Allocator>::iterator &
    1219                 :  4050337292 : hash_table<Descriptor, Lazy, Allocator>::iterator::operator ++ ()
    1220                 :             : {
    1221                 :  4050337292 :   ++m_slot;
    1222                 :  2749279453 :   slide ();
    1223                 :  2388876195 :   return *this;
    1224                 :             : }
    1225                 :             : 
    1226                 :             : 
    1227                 :             : /* Iterate through the elements of hash_table HTAB,
    1228                 :             :    using hash_table <....>::iterator ITER,
    1229                 :             :    storing each element in RESULT, which is of type TYPE.  */
    1230                 :             : 
    1231                 :             : #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
    1232                 :             :   for ((ITER) = (HTAB).begin (); \
    1233                 :             :        (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
    1234                 :             :        ++(ITER))
    1235                 :             : 
    1236                 :             : /* ggc walking routines.  */
    1237                 :             : 
    1238                 :             : template<typename E>
    1239                 :             : inline void
    1240                 :    69898915 : gt_ggc_mx (hash_table<E> *h)
    1241                 :             : {
    1242                 :             :   typedef hash_table<E> table;
    1243                 :             : 
    1244                 :    69898915 :   if (!ggc_test_and_set_mark (h->m_entries))
    1245                 :           0 :     return;
    1246                 :             : 
    1247                 : 17043675544 :   for (size_t i = 0; i < h->m_size; i++)
    1248                 :             :     {
    1249                 : 27909300811 :       if (table::is_empty (h->m_entries[i])
    1250                 : 16973776389 :           || table::is_deleted (h->m_entries[i]))
    1251                 : 12134142176 :         continue;
    1252                 :             : 
    1253                 :             :       /* Use ggc_maxbe_mx so we don't mark right away for cache tables; we'll
    1254                 :             :          mark in gt_cleare_cache if appropriate.  */
    1255                 :  3302658264 :       E::ggc_maybe_mx (h->m_entries[i]);
    1256                 :             :     }
    1257                 :             : }
    1258                 :             : 
    1259                 :             : template<typename D>
    1260                 :             : inline void
    1261                 :       16937 : hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
    1262                 :             :                              void *cookie)
    1263                 :             : {
    1264                 :       16937 :   hash_table<D> *map = static_cast<hash_table<D> *> (h);
    1265                 :       16937 :   gcc_checking_assert (map->m_entries == obj);
    1266                 :     6735274 :   for (size_t i = 0; i < map->m_size; i++)
    1267                 :             :     {
    1268                 :             :       typedef hash_table<D> table;
    1269                 :    11496913 :       if (table::is_empty (map->m_entries[i])
    1270                 :     6717959 :           || table::is_deleted (map->m_entries[i]))
    1271                 :     5040070 :         continue;
    1272                 :             : 
    1273                 :     1678239 :       D::pch_nx (map->m_entries[i], op, cookie);
    1274                 :             :     }
    1275                 :       16937 : }
    1276                 :             : 
    1277                 :             : template<typename D>
    1278                 :             : void
    1279                 :       16937 : gt_pch_nx (hash_table<D> *h)
    1280                 :             : {
    1281                 :       16937 :   h->check_complete_insertion ();
    1282                 :       16937 :   bool success
    1283                 :       16937 :     = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
    1284                 :       16937 :   gcc_checking_assert (success);
    1285                 :     6735274 :   for (size_t i = 0; i < h->m_size; i++)
    1286                 :             :     {
    1287                 :    11496913 :       if (hash_table<D>::is_empty (h->m_entries[i])
    1288                 :     6717959 :           || hash_table<D>::is_deleted (h->m_entries[i]))
    1289                 :     5040070 :         continue;
    1290                 :             : 
    1291                 :     1678239 :       D::pch_nx (h->m_entries[i]);
    1292                 :             :     }
    1293                 :       16937 : }
    1294                 :             : 
    1295                 :             : template<typename D>
    1296                 :             : inline void
    1297                 :        9967 : gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
    1298                 :             : {
    1299                 :        9967 :   op (&h->m_entries, NULL, cookie);
    1300                 :        9967 : }
    1301                 :             : 
    1302                 :             : template<typename H>
    1303                 :             : inline void
    1304                 :    13686749 : gt_cleare_cache (hash_table<H> *h)
    1305                 :             : {
    1306                 :             :   typedef hash_table<H> table;
    1307                 :    13686749 :   if (!h)
    1308                 :             :     return;
    1309                 :             : 
    1310                 :  2575502373 :   for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
    1311                 :  1395985836 :     if (!table::is_empty (*iter) && !table::is_deleted (*iter))
    1312                 :             :       {
    1313                 :  1628695039 :         int res = H::keep_cache_entry (*iter);
    1314                 :  1163276633 :         if (res == 0)
    1315                 :   116646719 :           h->clear_slot (&*iter);
    1316                 :      284004 :         else if (res != -1)
    1317                 :  1078366997 :           H::ggc_mx (*iter);
    1318                 :             :       }
    1319                 :             : }
    1320                 :             : 
    1321                 :             : #endif /* TYPED_HASHTAB_H */
        

Generated by: LCOV version 2.0-1

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.