LCOV - code coverage report
Current view: top level - gcc - hash-set.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 89.3 % 56 50
Test Date: 2024-09-28 13:20:55 Functions: 90.4 % 136 123
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 set.
       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_set_h
      22                 :             : #define hash_set_h
      23                 :             : 
      24                 :             : /* Class hash_set is a hash-value based container for objects of
      25                 :             :    KeyId type.
      26                 :             :    KeyId may be a non-trivial (non-POD) type provided a suitabe Traits
      27                 :             :    class.  Default Traits specializations are provided for basic types
      28                 :             :    such as integers, pointers, and std::pair.  Inserted elements are
      29                 :             :    value-initialized either to zero for POD types or by invoking their
      30                 :             :    default ctor.  Removed elements are destroyed by invoking their dtor.
      31                 :             :    On hash_set destruction all elements are removed.  Objects of
      32                 :             :    hash_set type are copy-constructible but not assignable.  */
      33                 :             : 
      34                 :             : template<typename KeyId, bool Lazy = false,
      35                 :             :          typename Traits = default_hash_traits<KeyId> >
      36                 :  4854200568 : class hash_set
      37                 :             : {
      38                 :             : public:
      39                 :             :   typedef typename Traits::value_type Key;
      40                 :  5365540701 :   explicit hash_set (size_t n = 13, bool ggc = false CXX_MEM_STAT_INFO)
      41                 :  4868621129 :     : m_table (n, ggc, true, GATHER_STATISTICS, HASH_SET_ORIGIN PASS_MEM_STAT) {}
      42                 :             : 
      43                 :             :   /* Create a hash_set in gc memory with space for at least n elements.  */
      44                 :             : 
      45                 :             :   static hash_set *
      46                 :    13363070 :   create_ggc (size_t n)
      47                 :             :     {
      48                 :    13363070 :       hash_set *set = ggc_alloc<hash_set> ();
      49                 :    13363070 :       new (set) hash_set (n, true);
      50                 :    13363070 :       return set;
      51                 :             :     }
      52                 :             : 
      53                 :             :   /* If key k isn't already in the map add it to the map, and
      54                 :             :      return false.  Otherwise return true.  */
      55                 :             : 
      56                 : 26120695216 :   bool add (const Key &k)
      57                 :             :     {
      58                 : 26120695216 :       Key *e = m_table.find_slot_with_hash (k, Traits::hash (k), INSERT);
      59                 : 26120695216 :       bool existed = !Traits::is_empty (*e);
      60                 : 26120695216 :       if (!existed)
      61                 :             :         {
      62                 : 24578310796 :           new (e) Key (k);
      63                 :             :           // Catch attempts to insert e.g. a NULL pointer.
      64                 : 24578310796 :           gcc_checking_assert (!Traits::is_empty (*e)
      65                 :             :                                && !Traits::is_deleted (*e));
      66                 :             :         }
      67                 :             : 
      68                 : 26120695216 :       return existed;
      69                 :             :     }
      70                 :             : 
      71                 :             :   /* if the passed in key is in the map return its value otherwise NULL.  */
      72                 :             : 
      73                 : 15667808618 :   bool contains (const Key &k)
      74                 :             :     {
      75                 :             :       if (Lazy)
      76                 :      644374 :         return (m_table.find_slot_with_hash (k, Traits::hash (k), NO_INSERT)
      77                 :      644374 :                 != NULL);
      78                 : 15667164244 :       Key &e = m_table.find_with_hash (k, Traits::hash (k));
      79                 : 15667164244 :       return !Traits::is_empty (e);
      80                 :             :     }
      81                 :             : 
      82                 :    52615653 :   void remove (const Key &k)
      83                 :             :     {
      84                 :    52615653 :       m_table.remove_elt_with_hash (k, Traits::hash (k));
      85                 :     1741519 :     }
      86                 :             : 
      87                 :             :   /* Call the call back on each pair of key and value with the passed in
      88                 :             :      arg.  */
      89                 :             : 
      90                 :             :   template<typename Arg, bool (*f)(const typename Traits::value_type &, Arg)>
      91                 :    22881357 :   void traverse (Arg a) const
      92                 :             :     {
      93                 :    23964142 :       for (typename hash_table<Traits, Lazy>::iterator iter = m_table.begin ();
      94                 :    25061299 :            iter != m_table.end (); ++iter)
      95                 :     1089991 :         f (*iter, a);
      96                 :    22881357 :     }
      97                 :             : 
      98                 :             :   /* Return the number of elements in the set.  */
      99                 :             : 
     100                 :   149745198 :   size_t elements () const { return m_table.elements (); }
     101                 :             : 
     102                 :             :   /* Clear the hash table.  */
     103                 :             : 
     104                 :    29308846 :   void empty () { m_table.empty (); }
     105                 :             : 
     106                 :             :   /* Return true when there are no elements in this hash set.  */
     107                 :     6596168 :   bool is_empty () const { return m_table.is_empty (); }
     108                 :             : 
     109                 :             :   class iterator
     110                 :             :   {
     111                 :             :   public:
     112                 :    25533618 :     explicit iterator (const typename hash_table<Traits,
     113                 :             :                                                  Lazy>::iterator &iter) :
     114                 :    23274983 :       m_iter (iter) {}
     115                 :             : 
     116                 :    18689179 :     iterator &operator++ ()
     117                 :             :       {
     118                 :    18689179 :         ++m_iter;
     119                 :    18687519 :         return *this;
     120                 :             :       }
     121                 :             : 
     122                 :             :     Key
     123                 :    19705659 :     operator* ()
     124                 :             :       {
     125                 :    19700439 :         return *m_iter;
     126                 :             :       }
     127                 :             : 
     128                 :             :     bool
     129                 :    41964138 :     operator != (const iterator &other) const
     130                 :             :       {
     131                 :    64232295 :         return m_iter != other.m_iter;
     132                 :             :       }
     133                 :             : 
     134                 :             :   private:
     135                 :             :     typename hash_table<Traits, Lazy>::iterator m_iter;
     136                 :             :   };
     137                 :             : 
     138                 :             :   /* Standard iterator retrieval methods.  */
     139                 :             : 
     140                 :    23274983 :   iterator begin () const { return iterator (m_table.begin ()); }
     141                 :    36242600 :   iterator end () const { return iterator (m_table.end ()); }
     142                 :             : 
     143                 :             : 
     144                 :             : private:
     145                 :             : 
     146                 :             :   template<typename T, typename U>
     147                 :             :   friend void gt_ggc_mx (hash_set<T, false, U> *);
     148                 :             :   template<typename T, typename U>
     149                 :             :   friend void gt_pch_nx (hash_set<T, false, U> *);
     150                 :             :   template<typename T, typename U>
     151                 :             :   friend void gt_pch_nx (hash_set<T, false, U> *, gt_pointer_operator, void *);
     152                 :             : 
     153                 :             :   hash_table<Traits, Lazy> m_table;
     154                 :             : };
     155                 :             : 
     156                 :             : /* Generic hash_set<TYPE> debug helper.
     157                 :             : 
     158                 :             :    This needs to be instantiated for each hash_set<TYPE> used throughout
     159                 :             :    the compiler like this:
     160                 :             : 
     161                 :             :     DEFINE_DEBUG_HASH_SET (TYPE)
     162                 :             : 
     163                 :             :    The reason we have a debug_helper() is because GDB can't
     164                 :             :    disambiguate a plain call to debug(some_hash), and it must be called
     165                 :             :    like debug<TYPE>(some_hash).  */
     166                 :             : template<typename T>
     167                 :             : void
     168                 :           0 : debug_helper (hash_set<T> &ref)
     169                 :             : {
     170                 :           0 :   for (typename hash_set<T>::iterator it = ref.begin ();
     171                 :           0 :        it != ref.end (); ++it)
     172                 :             :     {
     173                 :           0 :       debug_slim (*it);
     174                 :           0 :       fputc ('\n', stderr);
     175                 :             :     }
     176                 :           0 : }
     177                 :             : 
     178                 :             : #define DEFINE_DEBUG_HASH_SET(T) \
     179                 :             :   template void debug_helper (hash_set<T> &);         \
     180                 :             :   DEBUG_FUNCTION void                                   \
     181                 :             :   debug (hash_set<T> &ref)                            \
     182                 :             :   {                                                     \
     183                 :             :     debug_helper <T> (ref);                               \
     184                 :             :   }                                                     \
     185                 :             :   DEBUG_FUNCTION void                                   \
     186                 :             :   debug (hash_set<T> *ptr)                                \
     187                 :             :   {                                                     \
     188                 :             :     if (ptr)                                            \
     189                 :             :       debug (*ptr);                                     \
     190                 :             :     else                                                \
     191                 :             :       fprintf (stderr, "<nil>\n");                      \
     192                 :             :   }
     193                 :             : 
     194                 :             : /* ggc marking routines.  */
     195                 :             : 
     196                 :             : template<typename K, typename H>
     197                 :             : inline void
     198                 :    24239805 : gt_ggc_mx (hash_set<K, false, H> *h)
     199                 :             : {
     200                 :    24239805 :   gt_ggc_mx (&h->m_table);
     201                 :    24239805 : }
     202                 :             : 
     203                 :             : template<typename K, typename H>
     204                 :             : inline void
     205                 :        6335 : gt_pch_nx (hash_set<K, false, H> *h)
     206                 :             : {
     207                 :        6335 :   gt_pch_nx (&h->m_table);
     208                 :        6335 : }
     209                 :             : 
     210                 :             : template<typename K, typename H>
     211                 :             : inline void
     212                 :        6335 : gt_pch_nx (hash_set<K, false, H> *h, gt_pointer_operator op, void *cookie)
     213                 :             : {
     214                 :        6335 :   op (&h->m_table.m_entries, NULL, cookie);
     215                 :        6335 : }
     216                 :             : 
     217                 :             : #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.