LCOV - code coverage report
Current view: top level - gcc - hash-map.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 110 113 97.3 %
Date: 2020-04-04 11:58:09 Functions: 229 253 90.5 %
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-2020 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                 :  275164174 : class GTY((user)) hash_map
      40                 :            : {
      41                 :            :   typedef typename Traits::key_type Key;
      42                 :        552 :   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                 :21435681364 :     static hashval_t hash (const hash_entry &e)
      51                 :            :       {
      52                 :21435681364 :         return Traits::hash (e.m_key);
      53                 :            :       }
      54                 :            : 
      55                 :27638839575 :     static bool equal (const hash_entry &a, const Key &b)
      56                 :            :         {
      57                 :27638879390 :           return Traits::equal_keys (a.m_key, b);
      58                 :            :         }
      59                 :            : 
      60                 :   34767916 :     static void remove (hash_entry &e) { Traits::remove (e); }
      61                 :            : 
      62                 :   10735336 :     static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
      63                 :            : 
      64                 :39040685099 :     static bool is_deleted (const hash_entry &e)
      65                 :            :       {
      66                 :39086465538 :         return Traits::is_deleted (e);
      67                 :            :       }
      68                 :            : 
      69                 :            :     static const bool empty_zero_p = Traits::empty_zero_p;
      70                 : 1285958644 :     static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
      71                 :85754131662 :     static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
      72                 :            : 
      73                 :    1275101 :     static void ggc_mx (hash_entry &e)
      74                 :            :       {
      75                 :    1275101 :         gt_ggc_mx (e.m_key);
      76                 :    1275101 :         gt_ggc_mx (e.m_value);
      77                 :    1275101 :       }
      78                 :            : 
      79                 :            :     static void ggc_maybe_mx (hash_entry &e)
      80                 :            :       {
      81                 :            :         if (Traits::maybe_mx)
      82                 :            :           ggc_mx (e);
      83                 :            :       }
      84                 :            : 
      85                 :       2352 :     static void pch_nx (hash_entry &e)
      86                 :            :       {
      87                 :       2352 :         gt_pch_nx (e.m_key);
      88                 :       2352 :         gt_pch_nx (e.m_value);
      89                 :       2352 :       }
      90                 :            : 
      91                 :       2352 :     static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
      92                 :            :       {
      93                 :       4075 :         pch_nx_helper (e.m_key, op, c);
      94                 :       2352 :         pch_nx_helper (e.m_value, op, c);
      95                 :       2352 :       }
      96                 :            : 
      97                 :    1291016 :     static int keep_cache_entry (hash_entry &e)
      98                 :            :       {
      99                 :    1291016 :         return ggc_marked_p (e.m_key);
     100                 :            :       }
     101                 :            : 
     102                 :            :   private:
     103                 :            :     template<typename T>
     104                 :            :     static void
     105                 :          0 :       pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
     106                 :            :         {
     107                 :          0 :           gt_pch_nx (&x, op, cookie);
     108                 :            :         }
     109                 :            : 
     110                 :            :     static void
     111                 :          0 :       pch_nx_helper (int, gt_pointer_operator, void *)
     112                 :            :         {
     113                 :            :         }
     114                 :            : 
     115                 :            :     static void
     116                 :        629 :       pch_nx_helper (unsigned int, gt_pointer_operator, void *)
     117                 :            :         {
     118                 :            :         }
     119                 :            : 
     120                 :            :     static void
     121                 :            :       pch_nx_helper (bool, gt_pointer_operator, void *)
     122                 :            :         {
     123                 :            :         }
     124                 :            : 
     125                 :            :     template<typename T>
     126                 :            :       static void
     127                 :       4075 :       pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
     128                 :            :         {
     129                 :       2352 :           op (&x, cookie);
     130                 :            :         }
     131                 :            :   };
     132                 :            : 
     133                 :            : public:
     134                 :  331981177 :   explicit hash_map (size_t n = default_hash_map_size, bool ggc = false,
     135                 :            :                      bool sanitize_eq_and_hash = true,
     136                 :            :                      bool gather_mem_stats = GATHER_STATISTICS
     137                 :            :                      CXX_MEM_STAT_INFO)
     138                 :            :     : m_table (n, ggc, sanitize_eq_and_hash, gather_mem_stats,
     139                 :  328705091 :                HASH_MAP_ORIGIN PASS_MEM_STAT)
     140                 :            :   {
     141                 :    2514750 :   }
     142                 :            : 
     143                 :    4012011 :   explicit hash_map (const hash_map &h, bool ggc = false,
     144                 :            :                      bool sanitize_eq_and_hash = true,
     145                 :            :                      bool gather_mem_stats = GATHER_STATISTICS
     146                 :            :                      CXX_MEM_STAT_INFO)
     147                 :    4012009 :     : m_table (h.m_table, ggc, sanitize_eq_and_hash, gather_mem_stats,
     148                 :    4012011 :                HASH_MAP_ORIGIN PASS_MEM_STAT) {}
     149                 :            : 
     150                 :            :   /* Create a hash_map in ggc memory.  */
     151                 :    1183364 :   static hash_map *create_ggc (size_t size = default_hash_map_size,
     152                 :            :                                bool gather_mem_stats = GATHER_STATISTICS
     153                 :            :                                CXX_MEM_STAT_INFO)
     154                 :            :     {
     155                 :    1183364 :       hash_map *map = ggc_alloc<hash_map> ();
     156                 :    1183364 :       new (map) hash_map (size, true, true, gather_mem_stats PASS_MEM_STAT);
     157                 :    1183364 :       return map;
     158                 :            :     }
     159                 :            : 
     160                 :            :   /* If key k isn't already in the map add key k with value v to the map, and
     161                 :            :      return false.  Otherwise set the value of the entry for key k to be v and
     162                 :            :      return true.  */
     163                 :            : 
     164                 :  965110409 :   bool put (const Key &k, const Value &v)
     165                 :            :     {
     166                 :  965110409 :       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
     167                 :            :                                                    INSERT);
     168                 :  965110409 :       bool ins = hash_entry::is_empty (*e);
     169                 :  965110409 :       if (ins)
     170                 :            :         {
     171                 :  944131261 :           e->m_key = k;
     172                 :  944131261 :           new ((void *) &e->m_value) Value (v);
     173                 :            :         }
     174                 :            :       else
     175                 :   20979204 :         e->m_value = v;
     176                 :            : 
     177                 :  965110409 :       return !ins;
     178                 :            :     }
     179                 :            : 
     180                 :            :   /* if the passed in key is in the map return its value otherwise NULL.  */
     181                 :            : 
     182                 : 7236733056 :   Value *get (const Key &k)
     183                 :            :     {
     184                 : 7236733056 :       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
     185                 : 7236733056 :       return Traits::is_empty (e) ? NULL : &e.m_value;
     186                 :            :     }
     187                 :            : 
     188                 :            :   /* Return a reference to the value for the passed in key, creating the entry
     189                 :            :      if it doesn't already exist.  If existed is not NULL then it is set to
     190                 :            :      false if the key was not previously in the map, and true otherwise.  */
     191                 :            : 
     192                 : 1849241070 :   Value &get_or_insert (const Key &k, bool *existed = NULL)
     193                 :            :     {
     194                 : 1849241070 :       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
     195                 :            :                                                    INSERT);
     196                 : 1849241070 :       bool ins = Traits::is_empty (*e);
     197                 : 1849241070 :       if (ins)
     198                 :            :         {
     199                 :  918989228 :           e->m_key = k;
     200                 :  918989228 :           new ((void *)&e->m_value) Value ();
     201                 :            :         }
     202                 :            : 
     203                 : 1849241070 :       if (existed != NULL)
     204                 : 1781019544 :         *existed = !ins;
     205                 :            : 
     206                 : 1849241070 :       return e->m_value;
     207                 :            :     }
     208                 :            : 
     209                 :   15143576 :   void remove (const Key &k)
     210                 :            :     {
     211                 :   15143576 :       m_table.remove_elt_with_hash (k, Traits::hash (k));
     212                 :   10448762 :     }
     213                 :            : 
     214                 :            :   /* Call the call back on each pair of key and value with the passed in
     215                 :            :      arg.  */
     216                 :            : 
     217                 :            :   template<typename Arg, bool (*f)(const typename Traits::key_type &,
     218                 :            :                                    const Value &, Arg)>
     219                 :   45742252 :   void traverse (Arg a) const
     220                 :            :     {
     221                 :  171994273 :       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
     222                 :  171994273 :            iter != m_table.end (); ++iter)
     223                 :  126252256 :         f ((*iter).m_key, (*iter).m_value, a);
     224                 :   45742252 :     }
     225                 :            : 
     226                 :            :   template<typename Arg, bool (*f)(const typename Traits::key_type &,
     227                 :            :                                    Value *, Arg)>
     228                 :      11407 :   void traverse (Arg a) const
     229                 :            :     {
     230                 :      41380 :       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
     231                 :      41380 :            iter != m_table.end (); ++iter)
     232                 :      29973 :         if (!f ((*iter).m_key, &(*iter).m_value, a))
     233                 :            :           break;
     234                 :      11407 :     }
     235                 :            : 
     236                 :    9934654 :   size_t elements () const { return m_table.elements (); }
     237                 :            : 
     238                 :  174934776 :   void empty () { m_table.empty(); }
     239                 :            : 
     240                 :            :   /* Return true when there are no elements in this hash map.  */
     241                 :     935117 :   bool is_empty () const { return m_table.is_empty (); }
     242                 :            : 
     243                 :            :   class iterator
     244                 :            :   {
     245                 :            :   public:
     246                 :  332330083 :     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
     247                 :            :       m_iter (iter) {}
     248                 :            : 
     249                 :  312621077 :     iterator &operator++ ()
     250                 :            :     {
     251                 :  624913237 :       ++m_iter;
     252                 :        667 :       return *this;
     253                 :            :     }
     254                 :            : 
     255                 :            :     /* Can't use std::pair here, because GCC before 4.3 don't handle
     256                 :            :        std::pair where template parameters are references well.
     257                 :            :        See PR86739.  */
     258                 :            :     class reference_pair {
     259                 :            :     public:
     260                 :            :       const Key &first;
     261                 :            :       Value &second;
     262                 :            : 
     263                 :  313660707 :       reference_pair (const Key &key, Value &value) : first (key), second (value) {}
     264                 :            : 
     265                 :            :       template <typename K, typename V>
     266                 :     139079 :       operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
     267                 :            :     };
     268                 :            : 
     269                 :  313660707 :     reference_pair operator* ()
     270                 :            :     {
     271                 :  313007326 :       hash_entry &e = *m_iter;
     272                 :  313007326 :       return reference_pair (e.m_key, e.m_value);
     273                 :            :     }
     274                 :            : 
     275                 :            :     bool
     276                 :  332330751 :     operator != (const iterator &other) const
     277                 :            :     {
     278                 :  332330751 :       return m_iter != other.m_iter;
     279                 :            :     }
     280                 :            : 
     281                 :            :   private:
     282                 :            :     typename hash_table<hash_entry>::iterator m_iter;
     283                 :            :   };
     284                 :            : 
     285                 :            :   /* Standard iterator retrieval methods.  */
     286                 :            : 
     287                 :  351746642 :   iterator  begin () const { return iterator (m_table.begin ()); }
     288                 :  332037931 :   iterator end () const { return iterator (m_table.end ()); }
     289                 :            : 
     290                 :            : private:
     291                 :            : 
     292                 :            :   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
     293                 :            :   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
     294                 :            :   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
     295                 :            :   template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *);
     296                 :            : 
     297                 :            :   hash_table<hash_entry> m_table;
     298                 :            : };
     299                 :            : 
     300                 :            : /* ggc marking routines.  */
     301                 :            : 
     302                 :            : template<typename K, typename V, typename H>
     303                 :            : static inline void
     304                 :   10503541 : gt_ggc_mx (hash_map<K, V, H> *h)
     305                 :            : {
     306                 :   10503541 :   gt_ggc_mx (&h->m_table);
     307                 :   10503541 : }
     308                 :            : 
     309                 :            : template<typename K, typename V, typename H>
     310                 :            : static inline void
     311                 :        465 : gt_pch_nx (hash_map<K, V, H> *h)
     312                 :            : {
     313                 :        465 :   gt_pch_nx (&h->m_table);
     314                 :        465 : }
     315                 :            : 
     316                 :            : template<typename K, typename V, typename H>
     317                 :            : static inline void
     318                 :     184626 : gt_cleare_cache (hash_map<K, V, H> *h)
     319                 :            : {
     320                 :     153924 :   if (h)
     321                 :      18063 :     gt_cleare_cache (&h->m_table);
     322                 :            : }
     323                 :            : 
     324                 :            : template<typename K, typename V, typename H>
     325                 :            : static inline void
     326                 :        465 : gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
     327                 :            : {
     328                 :        465 :   op (&h->m_table.m_entries, cookie);
     329                 :        465 : }
     330                 :            : 
     331                 :            : enum hm_alloc { hm_heap = false, hm_ggc = true };
     332                 :            : template<bool ggc, typename K, typename V, typename H>
     333                 :            : inline hash_map<K,V,H> *
     334                 :    7677058 : hash_map_maybe_create (hash_map<K,V,H> *&h,
     335                 :            :                        size_t size = default_hash_map_size)
     336                 :            : {
     337                 :    7677058 :   if (!h)
     338                 :            :     {
     339                 :            :       if (ggc)
     340                 :      60260 :         h = hash_map<K,V,H>::create_ggc (size);
     341                 :            :       else
     342                 :            :         h = new hash_map<K,V,H> (size);
     343                 :            :     }
     344                 :    7677058 :   return h;
     345                 :            : }
     346                 :            : 
     347                 :            : /* Like h->get, but handles null h.  */
     348                 :            : template<typename K, typename V, typename H>
     349                 :            : inline V*
     350                 :   34886076 : hash_map_safe_get (hash_map<K,V,H> *h, const K& k)
     351                 :            : {
     352                 :   34886076 :   return h ? h->get (k) : NULL;
     353                 :            : }
     354                 :            : 
     355                 :            : /* Like h->get, but handles null h.  */
     356                 :            : template<bool ggc, typename K, typename V, typename H>
     357                 :            : inline V&
     358                 :    1293152 : hash_map_safe_get_or_insert (hash_map<K,V,H> *&h, const K& k, bool *e = NULL,
     359                 :            :                              size_t size = default_hash_map_size)
     360                 :            : {
     361                 :    1293152 :   return hash_map_maybe_create<ggc> (h, size)->get_or_insert (k, e);
     362                 :            : }
     363                 :            : 
     364                 :            : /* Like h->put, but handles null h.  */
     365                 :            : template<bool ggc, typename K, typename V, typename H>
     366                 :            : inline bool
     367                 :    6383905 : hash_map_safe_put (hash_map<K,V,H> *&h, const K& k, const V& v,
     368                 :            :                    size_t size = default_hash_map_size)
     369                 :            : {
     370                 :    6383905 :   return hash_map_maybe_create<ggc> (h, size)->put (k, v);
     371                 :            : }
     372                 :            : 
     373                 :            : #endif

Generated by: LCOV version 1.0

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