LCOV - code coverage report
Current view: top level - gcc - hash-map.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 100.0 % 116 116
Test Date: 2024-12-21 13:15:12 Functions: 92.6 % 662 613
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 map.
       2                 :             :    Copyright (C) 2014-2024 Free Software Foundation, Inc.
       3                 :             : 
       4                 :             : This file is part of GCC.
       5                 :             : 
       6                 :             : GCC is free software; you can redistribute it and/or modify it under
       7                 :             : the terms of the GNU General Public License as published by the Free
       8                 :             : Software Foundation; either version 3, or (at your option) any later
       9                 :             : version.
      10                 :             : 
      11                 :             : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12                 :             : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :             : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :             : for more details.
      15                 :             : 
      16                 :             : You should have received a copy of the GNU General Public License
      17                 :             : along with GCC; see the file COPYING3.  If not see
      18                 :             : <http://www.gnu.org/licenses/>.  */
      19                 :             : 
      20                 :             : 
      21                 :             : #ifndef hash_map_h
      22                 :             : #define hash_map_h
      23                 :             : 
      24                 :             : /* Class hash_map is a hash-value based container mapping objects of
      25                 :             :    KeyId type to those of the Value type.
      26                 :             :    Both KeyId and Value may be non-trivial (non-POD) types provided
      27                 :             :    a suitabe Traits class.  A few default Traits specializations are
      28                 :             :    provided for basic types such as integers, pointers, and std::pair.
      29                 :             :    Inserted elements are value-initialized either to zero for POD types
      30                 :             :    or by invoking their default ctor.  Removed elements are destroyed
      31                 :             :    by invoking their dtor.   On hash_map destruction all elements are
      32                 :             :    removed.  Objects of hash_map type are copy-constructible but not
      33                 :             :    assignable.  */
      34                 :             : 
      35                 :             : const size_t default_hash_map_size = 13;
      36                 :             : template<typename KeyId, typename Value,
      37                 :             :          typename Traits /* = simple_hashmap_traits<default_hash_traits<Key>,
      38                 :             :                                                     Value> */>
      39                 :   950851915 : class GTY((user)) hash_map
      40                 :             : {
      41                 :             :   typedef typename Traits::key_type Key;
      42                 :     7193919 :   struct hash_entry
      43                 :             :   {
      44                 :             :     Key m_key;
      45                 :             :     Value m_value;
      46                 :             : 
      47                 :             :     typedef hash_entry value_type;
      48                 :             :     typedef Key compare_type;
      49                 :             : 
      50                 : 82307503778 :     static hashval_t hash (const hash_entry &e)
      51                 :             :       {
      52                 : 82455376060 :         return Traits::hash (e.m_key);
      53                 :             :       }
      54                 :             : 
      55                 : 94638763128 :     static bool equal (const hash_entry &a, const Key &b)
      56                 :             :         {
      57                 : 95093605728 :           return Traits::equal_keys (a.m_key, b);
      58                 :             :         }
      59                 :             : 
      60                 :   850166315 :     static void remove (hash_entry &e) { Traits::remove (e); }
      61                 :             : 
      62                 :    16721634 :     static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
      63                 :             : 
      64                 : >12642*10^7 :     static bool is_deleted (const hash_entry &e)
      65                 :             :       {
      66                 : >12612*10^7 :         return Traits::is_deleted (e);
      67                 :             :       }
      68                 :             : 
      69                 :             :     static const bool empty_zero_p = Traits::empty_zero_p;
      70                 :  1589695516 :     static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
      71                 : >46606*10^7 :     static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
      72                 :             : 
      73                 :   721647054 :     static void ggc_mx (hash_entry &e)
      74                 :             :       {
      75                 :    45651739 :         gt_ggc_mx (e.m_key);
      76                 :   712991413 :         gt_ggc_mx (e.m_value);
      77                 :    28014436 :       }
      78                 :             : 
      79                 :    15061138 :     static void ggc_maybe_mx (hash_entry &e)
      80                 :             :       {
      81                 :             :         if (Traits::maybe_mx)
      82                 :   695291555 :           ggc_mx (e);
      83                 :   693346992 :       }
      84                 :             : 
      85                 :      187227 :     static void pch_nx (hash_entry &e)
      86                 :             :       {
      87                 :        1545 :         gt_pch_nx (e.m_key);
      88                 :      187227 :         gt_pch_nx (e.m_value);
      89                 :      187227 :       }
      90                 :             : 
      91                 :      187227 :     static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
      92                 :             :       {
      93                 :        3090 :         pch_nx_helper (e.m_key, op, c);
      94                 :      188772 :         pch_nx_helper (e.m_value, op, c);
      95                 :      187227 :       }
      96                 :             : 
      97                 :    28099289 :     static int keep_cache_entry (hash_entry &e)
      98                 :             :       {
      99                 :    28099289 :         return ggc_marked_p (e.m_key);
     100                 :             :       }
     101                 :             : 
     102                 :             :   private:
     103                 :             :     template<typename T>
     104                 :             :     static void
     105                 :      184351 :       pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
     106                 :             :         {
     107                 :      184351 :           gt_pch_nx (&x, op, cookie);
     108                 :             :         }
     109                 :             : 
     110                 :             :     template<typename T>
     111                 :             :       static void
     112                 :        4421 :       pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
     113                 :             :         {
     114                 :        2876 :           op (&x, NULL, cookie);
     115                 :             :         }
     116                 :             : 
     117                 :             :     /* The overloads below should match those in ggc.h.  */
     118                 :             : #define DEFINE_PCH_HELPER(T)                    \
     119                 :             :     static void pch_nx_helper (T, gt_pointer_operator, void *) { }
     120                 :             : 
     121                 :             :     DEFINE_PCH_HELPER (bool);
     122                 :             :     DEFINE_PCH_HELPER (char);
     123                 :             :     DEFINE_PCH_HELPER (signed char);
     124                 :             :     DEFINE_PCH_HELPER (unsigned char);
     125                 :             :     DEFINE_PCH_HELPER (short);
     126                 :             :     DEFINE_PCH_HELPER (unsigned short);
     127                 :             :     DEFINE_PCH_HELPER (int);
     128                 :             :     DEFINE_PCH_HELPER (unsigned int);
     129                 :             :     DEFINE_PCH_HELPER (long);
     130                 :             :     DEFINE_PCH_HELPER (unsigned long);
     131                 :             :     DEFINE_PCH_HELPER (long long);
     132                 :             :     DEFINE_PCH_HELPER (unsigned long long);
     133                 :             : 
     134                 :             : #undef DEFINE_PCH_HELPER
     135                 :             :   };
     136                 :             : 
     137                 :             : public:
     138                 :   906889958 :   explicit hash_map (size_t n = default_hash_map_size, bool ggc = false,
     139                 :             :                      bool sanitize_eq_and_hash = true,
     140                 :             :                      bool gather_mem_stats = GATHER_STATISTICS
     141                 :             :                      CXX_MEM_STAT_INFO)
     142                 :   901185877 :     : m_table (n, ggc, sanitize_eq_and_hash, gather_mem_stats,
     143                 :             :                HASH_MAP_ORIGIN PASS_MEM_STAT)
     144                 :             :   {
     145                 :     2411904 :   }
     146                 :             : 
     147                 :    28940760 :   explicit hash_map (const hash_map &h, bool ggc = false,
     148                 :             :                      bool sanitize_eq_and_hash = true,
     149                 :             :                      bool gather_mem_stats = GATHER_STATISTICS
     150                 :             :                      CXX_MEM_STAT_INFO)
     151                 :    28940760 :     : m_table (h.m_table, ggc, sanitize_eq_and_hash, gather_mem_stats,
     152                 :             :                HASH_MAP_ORIGIN PASS_MEM_STAT) {}
     153                 :             : 
     154                 :             :   /* Create a hash_map in ggc memory.  */
     155                 :     2277676 :   static hash_map *create_ggc (size_t size = default_hash_map_size,
     156                 :             :                                bool gather_mem_stats = GATHER_STATISTICS
     157                 :             :                                CXX_MEM_STAT_INFO)
     158                 :             :     {
     159                 :     2277676 :       hash_map *map = ggc_alloc<hash_map> ();
     160                 :     2277676 :       new (map) hash_map (size, true, true, gather_mem_stats PASS_MEM_STAT);
     161                 :     2277676 :       return map;
     162                 :             :     }
     163                 :             : 
     164                 :             :   /* If key k isn't already in the map add key k with value v to the map, and
     165                 :             :      return false.  Otherwise set the value of the entry for key k to be v and
     166                 :             :      return true.  */
     167                 :             : 
     168                 :  4302573583 :   bool put (const Key &k, const Value &v)
     169                 :             :     {
     170                 :  4302573583 :       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
     171                 :             :                                                    INSERT);
     172                 :  4302573583 :       bool ins = Traits::is_empty (*e);
     173                 :  4302573583 :       if (ins)
     174                 :             :         {
     175                 :  3965374293 :           e->m_key = k;
     176                 :  3965374293 :           new ((void *)&e->m_value) Value (v);
     177                 :  3965374293 :           gcc_checking_assert (!Traits::is_empty (*e)
     178                 :             :                                && !Traits::is_deleted (*e));
     179                 :             :         }
     180                 :             :       else
     181                 :   337199290 :         e->m_value = v;
     182                 :             : 
     183                 :  4302573583 :       return !ins;
     184                 :             :     }
     185                 :             : 
     186                 :             :   /* If the passed in key is in the map return pointer to its value
     187                 :             :      otherwise NULL.  */
     188                 :             : 
     189                 : 16736587924 :   Value *get (const Key &k)
     190                 :             :     {
     191                 : 16736587924 :       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
     192                 : 16698612380 :       return Traits::is_empty (e) ? NULL : &e.m_value;
     193                 :             :     }
     194                 :             : 
     195                 :             :   /* Return a reference to the value for the passed in key, creating the entry
     196                 :             :      if it doesn't already exist.  If existed is not NULL then it is set to
     197                 :             :      false if the key was not previously in the map, and true otherwise.  */
     198                 :             : 
     199                 :  2479585336 :   Value &get_or_insert (const Key &k, bool *existed = NULL)
     200                 :             :     {
     201                 :  2479585336 :       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
     202                 :             :                                                    INSERT);
     203                 :  2479653648 :       bool ins = Traits::is_empty (*e);
     204                 :  2479231953 :       if (ins)
     205                 :             :         {
     206                 :  1714978500 :           e->m_key = k;
     207                 :  1714978500 :           new ((void *)&e->m_value) Value ();
     208                 :  1715263571 :           gcc_checking_assert (!Traits::is_empty (*e)
     209                 :             :                                && !Traits::is_deleted (*e));
     210                 :             :         }
     211                 :             : 
     212                 :  2479585336 :       if (existed != NULL)
     213                 :  2344122894 :         *existed = !ins;
     214                 :             : 
     215                 :  2479585336 :       return e->m_value;
     216                 :             :     }
     217                 :             : 
     218                 :   161042658 :   void remove (const Key &k)
     219                 :             :     {
     220                 :   161042658 :       m_table.remove_elt_with_hash (k, Traits::hash (k));
     221                 :   138457839 :     }
     222                 :             : 
     223                 :             :   /* Call the call back on each pair of key and value with the passed in
     224                 :             :      arg until either the call back returns false or all pairs have been seen.
     225                 :             :      The traversal is unordered.  */
     226                 :             : 
     227                 :             :   template<typename Arg, bool (*f)(const typename Traits::key_type &,
     228                 :             :                                    const Value &, Arg)>
     229                 :    71317126 :   void traverse (Arg a) const
     230                 :             :     {
     231                 :   267867354 :       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
     232                 :   464417582 :            iter != m_table.end (); ++iter)
     233                 :   196550228 :         if (!f ((*iter).m_key, (*iter).m_value, a))
     234                 :             :           break;
     235                 :    71317126 :     }
     236                 :             : 
     237                 :             :   template<typename Arg, bool (*f)(const typename Traits::key_type &,
     238                 :             :                                    Value *, Arg)>
     239                 :       16559 :   void traverse (Arg a) const
     240                 :             :     {
     241                 :       61245 :       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
     242                 :      105931 :            iter != m_table.end (); ++iter)
     243                 :       44686 :         if (!f ((*iter).m_key, &(*iter).m_value, a))
     244                 :             :           break;
     245                 :       16559 :     }
     246                 :             : 
     247                 :    31364151 :   size_t elements () const { return m_table.elements (); }
     248                 :             : 
     249                 :   357654093 :   void empty () { m_table.empty(); }
     250                 :             : 
     251                 :             :   /* Return true when there are no elements in this hash map.  */
     252                 :     4541448 :   bool is_empty () const { return m_table.is_empty (); }
     253                 :             : 
     254                 :             :   class iterator
     255                 :             :   {
     256                 :             :   public:
     257                 :   484111865 :     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
     258                 :   127170909 :       m_iter (iter) {}
     259                 :             : 
     260                 :  1230834742 :     iterator &operator++ ()
     261                 :             :     {
     262                 :  1230834742 :       ++m_iter;
     263                 :  1173244258 :       return *this;
     264                 :             :     }
     265                 :             : 
     266                 :             :     /* Can't use std::pair here, because GCC before 4.3 don't handle
     267                 :             :        std::pair where template parameters are references well.
     268                 :             :        See PR86739.  */
     269                 :             :     class reference_pair {
     270                 :             :     public:
     271                 :             :       const Key &first;
     272                 :             :       Value &second;
     273                 :             : 
     274                 :  1287912756 :       reference_pair (const Key &key, Value &value) : first (key), second (value) {}
     275                 :             : 
     276                 :             :       template <typename K, typename V>
     277                 :      238133 :       operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
     278                 :             :     };
     279                 :             : 
     280                 :  1287912756 :     reference_pair operator* ()
     281                 :             :     {
     282                 :  1287912756 :       hash_entry &e = *m_iter;
     283                 :   497817324 :       return reference_pair (e.m_key, e.m_value);
     284                 :             :     }
     285                 :             : 
     286                 :             :     bool operator== (const iterator &other) const
     287                 :             :     {
     288                 :             :       return m_iter == other.m_iter;
     289                 :             :     }
     290                 :             : 
     291                 :  1358005651 :     bool operator != (const iterator &other) const
     292                 :             :     {
     293                 :  1484638798 :       return m_iter != other.m_iter;
     294                 :             :     }
     295                 :             : 
     296                 :             :   private:
     297                 :             :     typename hash_table<hash_entry>::iterator m_iter;
     298                 :             :   };
     299                 :             : 
     300                 :             :   /* Standard iterator retrieval methods.  */
     301                 :             : 
     302                 :   127170909 :   iterator  begin () const { return iterator (m_table.begin ()); }
     303                 :   622165998 :   iterator end () const { return iterator (m_table.end ()); }
     304                 :             : 
     305                 :             : private:
     306                 :             : 
     307                 :             :   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
     308                 :             :   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
     309                 :             :   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
     310                 :             :   template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *);
     311                 :             : 
     312                 :             :   hash_table<hash_entry> m_table;
     313                 :             : };
     314                 :             : 
     315                 :             : /* ggc marking routines.  */
     316                 :             : 
     317                 :             : template<typename K, typename V, typename H>
     318                 :             : inline void
     319                 :     5875593 : gt_ggc_mx (hash_map<K, V, H> *h)
     320                 :             : {
     321                 :     5875593 :   gt_ggc_mx (&h->m_table);
     322                 :     5370571 : }
     323                 :             : 
     324                 :             : template<typename K, typename V, typename H>
     325                 :             : inline void
     326                 :         691 : gt_pch_nx (hash_map<K, V, H> *h)
     327                 :             : {
     328                 :         691 :   gt_pch_nx (&h->m_table);
     329                 :         691 : }
     330                 :             : 
     331                 :             : template<typename K, typename V, typename H>
     332                 :             : inline void
     333                 :      614166 : gt_cleare_cache (hash_map<K, V, H> *h)
     334                 :             : {
     335                 :      614166 :   if (h)
     336                 :       90456 :     gt_cleare_cache (&h->m_table);
     337                 :             : }
     338                 :             : 
     339                 :             : template<typename K, typename V, typename H>
     340                 :             : inline void
     341                 :         691 : gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
     342                 :             : {
     343                 :         691 :   op (&h->m_table.m_entries, NULL, cookie);
     344                 :         691 : }
     345                 :             : 
     346                 :             : enum hm_alloc { hm_heap = false, hm_ggc = true };
     347                 :             : template<bool ggc, typename K, typename V, typename H>
     348                 :             : inline hash_map<K,V,H> *
     349                 :   124680851 : hash_map_maybe_create (hash_map<K,V,H> *&h,
     350                 :             :                        size_t size = default_hash_map_size)
     351                 :             : {
     352                 :   124680851 :   if (!h)
     353                 :             :     {
     354                 :             :       if (ggc)
     355                 :      251534 :         h = hash_map<K,V,H>::create_ggc (size);
     356                 :             :       else
     357                 :             :         h = new hash_map<K,V,H> (size);
     358                 :             :     }
     359                 :   124680851 :   return h;
     360                 :             : }
     361                 :             : 
     362                 :             : /* Like h->get, but handles null h.  */
     363                 :             : template<typename K, typename V, typename H>
     364                 :             : inline V*
     365                 :   304869221 : hash_map_safe_get (hash_map<K,V,H> *h, const K& k)
     366                 :             : {
     367                 :   304869221 :   return h ? h->get (k) : NULL;
     368                 :             : }
     369                 :             : 
     370                 :             : /* Like h->get, but handles null h.  */
     371                 :             : template<bool ggc, typename K, typename V, typename H>
     372                 :             : inline V&
     373                 :    37452924 : hash_map_safe_get_or_insert (hash_map<K,V,H> *&h, const K& k, bool *e = NULL,
     374                 :             :                              size_t size = default_hash_map_size)
     375                 :             : {
     376                 :    37452924 :   return hash_map_maybe_create<ggc> (h, size)->get_or_insert (k, e);
     377                 :             : }
     378                 :             : 
     379                 :             : /* Like h->put, but handles null h.  */
     380                 :             : template<bool ggc, typename K, typename V, typename H>
     381                 :             : inline bool
     382                 :    57338139 : hash_map_safe_put (hash_map<K,V,H> *&h, const K& k, const V& v,
     383                 :             :                    size_t size = default_hash_map_size)
     384                 :             : {
     385                 :    57338139 :   return hash_map_maybe_create<ggc> (h, size)->put (k, v);
     386                 :             : }
     387                 :             : 
     388                 :             : #endif
        

Generated by: LCOV version 2.1-beta

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.