1 /* A type-safe hash set.
2 Copyright (C) 2014-2019 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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/>. */
24 template<typename KeyId
, bool Lazy
= false,
25 typename Traits
= default_hash_traits
<KeyId
> >
29 typedef typename
Traits::value_type Key
;
30 explicit hash_set (size_t n
= 13, bool ggc
= false CXX_MEM_STAT_INFO
)
31 : m_table (n
, ggc
, GATHER_STATISTICS
, HASH_SET_ORIGIN PASS_MEM_STAT
) {}
33 /* Create a hash_set in gc memory with space for at least n elements. */
38 hash_set
*set
= ggc_alloc
<hash_set
> ();
39 new (set
) hash_set (n
, true);
43 /* If key k isn't already in the map add it to the map, and
44 return false. Otherwise return true. */
46 bool add (const Key
&k
)
48 Key
*e
= m_table
.find_slot_with_hash (k
, Traits::hash (k
), INSERT
);
49 bool existed
= !Traits::is_empty (*e
);
56 /* if the passed in key is in the map return its value otherwise NULL. */
58 bool contains (const Key
&k
)
61 return (m_table
.find_slot_with_hash (k
, Traits::hash (k
), NO_INSERT
)
63 Key
&e
= m_table
.find_with_hash (k
, Traits::hash (k
));
64 return !Traits::is_empty (e
);
67 void remove (const Key
&k
)
69 m_table
.remove_elt_with_hash (k
, Traits::hash (k
));
72 /* Call the call back on each pair of key and value with the passed in
75 template<typename Arg
, bool (*f
)(const typename
Traits::value_type
&, Arg
)>
76 void traverse (Arg a
) const
78 for (typename hash_table
<Traits
, Lazy
>::iterator iter
= m_table
.begin ();
79 iter
!= m_table
.end (); ++iter
)
83 /* Return the number of elements in the set. */
85 size_t elements () const { return m_table
.elements (); }
87 /* Clear the hash table. */
89 void empty () { m_table
.empty (); }
94 explicit iterator (const typename hash_table
<Traits
,
95 Lazy
>::iterator
&iter
) :
98 iterator
&operator++ ()
111 operator != (const iterator
&other
) const
113 return m_iter
!= other
.m_iter
;
117 typename hash_table
<Traits
, Lazy
>::iterator m_iter
;
120 /* Standard iterator retrieval methods. */
122 iterator
begin () const { return iterator (m_table
.begin ()); }
123 iterator
end () const { return iterator (m_table
.end ()); }
128 template<typename T
, typename U
>
129 friend void gt_ggc_mx (hash_set
<T
, false, U
> *);
130 template<typename T
, typename U
>
131 friend void gt_pch_nx (hash_set
<T
, false, U
> *);
132 template<typename T
, typename U
>
133 friend void gt_pch_nx (hash_set
<T
, false, U
> *, gt_pointer_operator
, void *);
135 hash_table
<Traits
, Lazy
> m_table
;
138 /* Generic hash_set<TYPE> debug helper.
140 This needs to be instantiated for each hash_set<TYPE> used throughout
141 the compiler like this:
143 DEFINE_DEBUG_HASH_SET (TYPE)
145 The reason we have a debug_helper() is because GDB can't
146 disambiguate a plain call to debug(some_hash), and it must be called
147 like debug<TYPE>(some_hash). */
150 debug_helper (hash_set
<T
> &ref
)
152 for (typename hash_set
<T
>::iterator it
= ref
.begin ();
153 it
!= ref
.end (); ++it
)
156 fputc ('\n', stderr
);
160 #define DEFINE_DEBUG_HASH_SET(T) \
161 template void debug_helper (hash_set<T> &); \
162 DEBUG_FUNCTION void \
163 debug (hash_set<T> &ref) \
165 debug_helper <T> (ref); \
167 DEBUG_FUNCTION void \
168 debug (hash_set<T> *ptr) \
173 fprintf (stderr, "<nil>\n"); \
176 /* ggc marking routines. */
178 template<typename K
, typename H
>
180 gt_ggc_mx (hash_set
<K
, false, H
> *h
)
182 gt_ggc_mx (&h
->m_table
);
185 template<typename K
, typename H
>
187 gt_pch_nx (hash_set
<K
, false, H
> *h
)
189 gt_pch_nx (&h
->m_table
);
192 template<typename K
, typename H
>
194 gt_pch_nx (hash_set
<K
, false, H
> *h
, gt_pointer_operator op
, void *cookie
)
196 op (&h
->m_table
.m_entries
, cookie
);