LCOV - code coverage report
Current view: top level - gcc - hash-set.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 46 52 88.5 %
Date: 2020-04-04 11:58:09 Functions: 57 66 86.4 %
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-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_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                 : 1206610488 : class hash_set
      37                 :            : {
      38                 :            : public:
      39                 :            :   typedef typename Traits::value_type Key;
      40                 : 1502621286 :   explicit hash_set (size_t n = 13, bool ggc = false CXX_MEM_STAT_INFO)
      41                 : 1220588970 :     : 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                 :    2654309 :   create_ggc (size_t n)
      47                 :            :     {
      48                 :    2654309 :       hash_set *set = ggc_alloc<hash_set> ();
      49                 :    2654309 :       new (set) hash_set (n, true);
      50                 :    2654309 :       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                 : 7937799000 :   bool add (const Key &k)
      57                 :            :     {
      58                 : 7937799080 :       Key *e = m_table.find_slot_with_hash (k, Traits::hash (k), INSERT);
      59                 : 7937799000 :       bool existed = !Traits::is_empty (*e);
      60                 : 7937798920 :       if (!existed)
      61                 : 7690445784 :         new (e) Key (k);
      62                 :            : 
      63                 : 7937799000 :       return existed;
      64                 :            :     }
      65                 :            : 
      66                 :            :   /* if the passed in key is in the map return its value otherwise NULL.  */
      67                 :            : 
      68                 : 8964283454 :   bool contains (const Key &k)
      69                 :            :     {
      70                 :            :       if (Lazy)
      71                 :            :         return (m_table.find_slot_with_hash (k, Traits::hash (k), NO_INSERT)
      72                 :        270 :                 != NULL);
      73                 : 8964283264 :       Key &e = m_table.find_with_hash (k, Traits::hash (k));
      74                 : 8960964582 :       return !Traits::is_empty (e);
      75                 :            :     }
      76                 :            : 
      77                 :    1346579 :   void remove (const Key &k)
      78                 :            :     {
      79                 :    1346579 :       m_table.remove_elt_with_hash (k, Traits::hash (k));
      80                 :    1346575 :     }
      81                 :            : 
      82                 :            :   /* Call the call back on each pair of key and value with the passed in
      83                 :            :      arg.  */
      84                 :            : 
      85                 :            :   template<typename Arg, bool (*f)(const typename Traits::value_type &, Arg)>
      86                 :   14551890 :   void traverse (Arg a) const
      87                 :            :     {
      88                 :   15239954 :       for (typename hash_table<Traits, Lazy>::iterator iter = m_table.begin ();
      89                 :   15239954 :            iter != m_table.end (); ++iter)
      90                 :     688071 :         f (*iter, a);
      91                 :   14551890 :     }
      92                 :            : 
      93                 :            :   /* Return the number of elements in the set.  */
      94                 :            : 
      95                 :    6269291 :   size_t elements () const { return m_table.elements (); }
      96                 :            : 
      97                 :            :   /* Clear the hash table.  */
      98                 :            : 
      99                 :   15483729 :   void empty () { m_table.empty (); }
     100                 :            : 
     101                 :            :   /* Return true when there are no elements in this hash set.  */
     102                 :    2341834 :   bool is_empty () const { return m_table.is_empty (); }
     103                 :            : 
     104                 :            :   class iterator
     105                 :            :   {
     106                 :            :   public:
     107                 :   14954154 :     explicit iterator (const typename hash_table<Traits,
     108                 :            :                                                  Lazy>::iterator &iter) :
     109                 :            :       m_iter (iter) {}
     110                 :            : 
     111                 :    6191006 :     iterator &operator++ ()
     112                 :            :       {
     113                 :   20938769 :         ++m_iter;
     114                 :            :         return *this;
     115                 :            :       }
     116                 :            : 
     117                 :            :     Key
     118                 :    6688299 :     operator* ()
     119                 :            :       {
     120                 :    6282742 :         return *m_iter;
     121                 :            :       }
     122                 :            : 
     123                 :            :     bool
     124                 :   14954124 :     operator != (const iterator &other) const
     125                 :            :       {
     126                 :   14954124 :         return m_iter != other.m_iter;
     127                 :            :       }
     128                 :            : 
     129                 :            :   private:
     130                 :            :     typename hash_table<Traits, Lazy>::iterator m_iter;
     131                 :            :   };
     132                 :            : 
     133                 :            :   /* Standard iterator retrieval methods.  */
     134                 :            : 
     135                 :   23717270 :   iterator begin () const { return iterator (m_table.begin ()); }
     136                 :   14954124 :   iterator end () const { return iterator (m_table.end ()); }
     137                 :            : 
     138                 :            : 
     139                 :            : private:
     140                 :            : 
     141                 :            :   template<typename T, typename U>
     142                 :            :   friend void gt_ggc_mx (hash_set<T, false, U> *);
     143                 :            :   template<typename T, typename U>
     144                 :            :   friend void gt_pch_nx (hash_set<T, false, U> *);
     145                 :            :   template<typename T, typename U>
     146                 :            :   friend void gt_pch_nx (hash_set<T, false, U> *, gt_pointer_operator, void *);
     147                 :            : 
     148                 :            :   hash_table<Traits, Lazy> m_table;
     149                 :            : };
     150                 :            : 
     151                 :            : /* Generic hash_set<TYPE> debug helper.
     152                 :            : 
     153                 :            :    This needs to be instantiated for each hash_set<TYPE> used throughout
     154                 :            :    the compiler like this:
     155                 :            : 
     156                 :            :     DEFINE_DEBUG_HASH_SET (TYPE)
     157                 :            : 
     158                 :            :    The reason we have a debug_helper() is because GDB can't
     159                 :            :    disambiguate a plain call to debug(some_hash), and it must be called
     160                 :            :    like debug<TYPE>(some_hash).  */
     161                 :            : template<typename T>
     162                 :            : void
     163                 :          0 : debug_helper (hash_set<T> &ref)
     164                 :            : {
     165                 :          0 :   for (typename hash_set<T>::iterator it = ref.begin ();
     166                 :          0 :        it != ref.end (); ++it)
     167                 :            :     {
     168                 :          0 :       debug_slim (*it);
     169                 :          0 :       fputc ('\n', stderr);
     170                 :            :     }
     171                 :          0 : }
     172                 :            : 
     173                 :            : #define DEFINE_DEBUG_HASH_SET(T) \
     174                 :            :   template void debug_helper (hash_set<T> &);         \
     175                 :            :   DEBUG_FUNCTION void                                   \
     176                 :            :   debug (hash_set<T> &ref)                            \
     177                 :            :   {                                                     \
     178                 :            :     debug_helper <T> (ref);                               \
     179                 :            :   }                                                     \
     180                 :            :   DEBUG_FUNCTION void                                   \
     181                 :            :   debug (hash_set<T> *ptr)                                \
     182                 :            :   {                                                     \
     183                 :            :     if (ptr)                                            \
     184                 :            :       debug (*ptr);                                     \
     185                 :            :     else                                                \
     186                 :            :       fprintf (stderr, "<nil>\n");                      \
     187                 :            :   }
     188                 :            : 
     189                 :            : /* ggc marking routines.  */
     190                 :            : 
     191                 :            : template<typename K, typename H>
     192                 :            : static inline void
     193                 :    3640750 : gt_ggc_mx (hash_set<K, false, H> *h)
     194                 :            : {
     195                 :    3640750 :   gt_ggc_mx (&h->m_table);
     196                 :    3640750 : }
     197                 :            : 
     198                 :            : template<typename K, typename H>
     199                 :            : static inline void
     200                 :       5694 : gt_pch_nx (hash_set<K, false, H> *h)
     201                 :            : {
     202                 :       5694 :   gt_pch_nx (&h->m_table);
     203                 :       5694 : }
     204                 :            : 
     205                 :            : template<typename K, typename H>
     206                 :            : static inline void
     207                 :       5694 : gt_pch_nx (hash_set<K, false, H> *h, gt_pointer_operator op, void *cookie)
     208                 :            : {
     209                 :       5694 :   op (&h->m_table.m_entries, cookie);
     210                 :       5694 : }
     211                 :            : 
     212                 :            : #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.