LCOV - code coverage report
Current view: top level - gcc - hash-map.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 87 103 84.5 %
Date: 2023-07-19 08:18:47 Functions: 60 63 95.2 %

          Line data    Source code
       1             : /* A type-safe hash map.
       2             :    Copyright (C) 2014-2023 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   267796226 : class GTY((user)) hash_map
      40             : {
      41             :   typedef typename Traits::key_type Key;
      42       59690 :   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 19884318444 :     static hashval_t hash (const hash_entry &e)
      51             :       {
      52 19905033121 :         return Traits::hash (e.m_key);
      53             :       }
      54             : 
      55 22736338919 :     static bool equal (const hash_entry &a, const Key &b)
      56             :         {
      57 22930969263 :           return Traits::equal_keys (a.m_key, b);
      58             :         }
      59             : 
      60    15482867 :     static void remove (hash_entry &e) { Traits::remove (e); }
      61             : 
      62    15441161 :     static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
      63             : 
      64 23143895248 :     static bool is_deleted (const hash_entry &e)
      65             :       {
      66 23143895785 :         return Traits::is_deleted (e);
      67             :       }
      68             : 
      69             :     static const bool empty_zero_p = Traits::empty_zero_p;
      70     2690333 :     static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
      71 >10040*10^7 :     static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
      72             : 
      73     3823117 :     static void ggc_mx (hash_entry &e)
      74             :       {
      75     3823117 :         gt_ggc_mx (e.m_key);
      76     3823117 :         gt_ggc_mx (e.m_value);
      77     3823084 :       }
      78             : 
      79          33 :     static void ggc_maybe_mx (hash_entry &e)
      80             :       {
      81             :         if (Traits::maybe_mx)
      82          33 :           ggc_mx (e);
      83          33 :       }
      84             : 
      85           0 :     static void pch_nx (hash_entry &e)
      86             :       {
      87           0 :         gt_pch_nx (e.m_key);
      88           0 :         gt_pch_nx (e.m_value);
      89           0 :       }
      90             : 
      91           0 :     static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
      92             :       {
      93           0 :         pch_nx_helper (e.m_key, op, c);
      94           0 :         pch_nx_helper (e.m_value, op, c);
      95           0 :       }
      96             : 
      97     3831721 :     static int keep_cache_entry (hash_entry &e)
      98             :       {
      99     3831721 :         return ggc_marked_p (e.m_key);
     100             :       }
     101             : 
     102             :   private:
     103             :     template<typename T>
     104             :     static void
     105             :       pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
     106             :         {
     107             :           gt_pch_nx (&x, op, cookie);
     108             :         }
     109             : 
     110             :     template<typename T>
     111             :       static void
     112           0 :       pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
     113             :         {
     114           0 :           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   267396370 :   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   267169317 :     : m_table (n, ggc, sanitize_eq_and_hash, gather_mem_stats,
     143             :                HASH_MAP_ORIGIN PASS_MEM_STAT)
     144             :   {
     145     1769143 :   }
     146             : 
     147      733661 :   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      733661 :     : 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      615029 :   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      615029 :       hash_map *map = ggc_alloc<hash_map> ();
     160      615029 :       new (map) hash_map (size, true, true, gather_mem_stats PASS_MEM_STAT);
     161      615029 :       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  1747208918 :   bool put (const Key &k, const Value &v)
     169             :     {
     170  1747208918 :       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
     171             :                                                    INSERT);
     172  1747208918 :       bool ins = Traits::is_empty (*e);
     173  1747208918 :       if (ins)
     174             :         {
     175  1636079643 :           e->m_key = k;
     176  1636079643 :           new ((void *)&e->m_value) Value (v);
     177  1636079643 :           gcc_checking_assert (!Traits::is_empty (*e)
     178             :                                && !Traits::is_deleted (*e));
     179             :         }
     180             :       else
     181   111129275 :         e->m_value = v;
     182             : 
     183  1747208918 :       return !ins;
     184             :     }
     185             : 
     186             :   /* If the passed in key is in the map return pointer to its value
     187             :      otherwise NULL.  */
     188             : 
     189  1881149481 :   Value *get (const Key &k)
     190             :     {
     191  1881149481 :       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
     192  1853949253 :       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    88165525 :   Value &get_or_insert (const Key &k, bool *existed = NULL)
     200             :     {
     201    88165525 :       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
     202             :                                                    INSERT);
     203    88209520 :       bool ins = Traits::is_empty (*e);
     204    87897095 :       if (ins)
     205             :         {
     206    77301498 :           e->m_key = k;
     207    77301498 :           new ((void *)&e->m_value) Value ();
     208    77525933 :           gcc_checking_assert (!Traits::is_empty (*e)
     209             :                                && !Traits::is_deleted (*e));
     210             :         }
     211             : 
     212    88165525 :       if (existed != NULL)
     213    87877929 :         *existed = !ins;
     214             : 
     215    88165525 :       return e->m_value;
     216             :     }
     217             : 
     218    15726178 :   void remove (const Key &k)
     219             :     {
     220    15726178 :       m_table.remove_elt_with_hash (k, Traits::hash (k));
     221      282374 :     }
     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             :   void traverse (Arg a) const
     230             :     {
     231             :       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
     232             :            iter != m_table.end (); ++iter)
     233             :         if (!f ((*iter).m_key, (*iter).m_value, a))
     234             :           break;
     235             :     }
     236             : 
     237             :   template<typename Arg, bool (*f)(const typename Traits::key_type &,
     238             :                                    Value *, Arg)>
     239             :   void traverse (Arg a) const
     240             :     {
     241             :       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
     242             :            iter != m_table.end (); ++iter)
     243             :         if (!f ((*iter).m_key, &(*iter).m_value, a))
     244             :           break;
     245             :     }
     246             : 
     247     2668940 :   size_t elements () const { return m_table.elements (); }
     248             : 
     249    45262870 :   void empty () { m_table.empty(); }
     250             : 
     251             :   /* Return true when there are no elements in this hash map.  */
     252       94268 :   bool is_empty () const { return m_table.is_empty (); }
     253             : 
     254             :   class iterator
     255             :   {
     256             :   public:
     257     2381810 :     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
     258     2381119 :       m_iter (iter) {}
     259             : 
     260   529556705 :     iterator &operator++ ()
     261             :     {
     262   529556705 :       ++m_iter;
     263   529556705 :       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   529556705 :       reference_pair (const Key &key, Value &value) : first (key), second (value) {}
     275             : 
     276             :       template <typename K, typename V>
     277             :       operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
     278             :     };
     279             : 
     280   529556705 :     reference_pair operator* ()
     281             :     {
     282   529556705 :       hash_entry &e = *m_iter;
     283   529556705 :       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   531937824 :     bool operator != (const iterator &other) const
     292             :     {
     293   534318943 :       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     2381119 :   iterator  begin () const { return iterator (m_table.begin ()); }
     303     2381751 :   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          33 : gt_ggc_mx (hash_map<K, V, H> *h)
     320             : {
     321          33 :   gt_ggc_mx (&h->m_table);
     322          33 : }
     323             : 
     324             : template<typename K, typename V, typename H>
     325             : inline void
     326           0 : gt_pch_nx (hash_map<K, V, H> *h)
     327             : {
     328           0 :   gt_pch_nx (&h->m_table);
     329           0 : }
     330             : 
     331             : template<typename K, typename V, typename H>
     332             : inline void
     333      380964 : gt_cleare_cache (hash_map<K, V, H> *h)
     334             : {
     335      380964 :   if (h)
     336       58818 :     gt_cleare_cache (&h->m_table);
     337             : }
     338             : 
     339             : template<typename K, typename V, typename H>
     340             : inline void
     341           0 : gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
     342             : {
     343           0 :   op (&h->m_table.m_entries, NULL, cookie);
     344           0 : }
     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    77933222 : hash_map_maybe_create (hash_map<K,V,H> *&h,
     350             :                        size_t size = default_hash_map_size)
     351             : {
     352    77933222 :   if (!h)
     353             :     {
     354             :       if (ggc)
     355      202907 :         h = hash_map<K,V,H>::create_ggc (size);
     356             :       else
     357             :         h = new hash_map<K,V,H> (size);
     358             :     }
     359    77933222 :   return h;
     360             : }
     361             : 
     362             : /* Like h->get, but handles null h.  */
     363             : template<typename K, typename V, typename H>
     364             : inline V*
     365    30371376 : hash_map_safe_get (hash_map<K,V,H> *h, const K& k)
     366             : {
     367    30371376 :   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     8606496 : 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     8606496 :   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     6333253 : 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     6333253 :   return hash_map_maybe_create<ggc> (h, size)->put (k, v);
     386             : }
     387             : 
     388             : #endif

Generated by: LCOV version 1.16