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 class hash_set
37 {
38 public:
39 typedef typename Traits::value_type Key;
40 explicit hash_set (size_t n = 13, bool ggc = false CXX_MEM_STAT_INFO)
m_table(n,ggc,true,GATHER_STATISTICS,HASH_SET_ORIGIN PASS_MEM_STAT)41 : 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 *
create_ggc(size_t n)46 create_ggc (size_t n)
47 {
48 hash_set *set = ggc_alloc<hash_set> ();
49 new (set) hash_set (n, true);
50 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
add(const Key & k)56 bool add (const Key &k)
57 {
58 Key *e = m_table.find_slot_with_hash (k, Traits::hash (k), INSERT);
59 bool existed = !Traits::is_empty (*e);
60 if (!existed)
61 new (e) Key (k);
62
63 return existed;
64 }
65
66 /* if the passed in key is in the map return its value otherwise NULL. */
67
contains(const Key & k)68 bool contains (const Key &k)
69 {
70 if (Lazy)
71 return (m_table.find_slot_with_hash (k, Traits::hash (k), NO_INSERT)
72 != NULL);
73 Key &e = m_table.find_with_hash (k, Traits::hash (k));
74 return !Traits::is_empty (e);
75 }
76
remove(const Key & k)77 void remove (const Key &k)
78 {
79 m_table.remove_elt_with_hash (k, Traits::hash (k));
80 }
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)>
traverse(Arg a)86 void traverse (Arg a) const
87 {
88 for (typename hash_table<Traits, Lazy>::iterator iter = m_table.begin ();
89 iter != m_table.end (); ++iter)
90 f (*iter, a);
91 }
92
93 /* Return the number of elements in the set. */
94
elements()95 size_t elements () const { return m_table.elements (); }
96
97 /* Clear the hash table. */
98
empty()99 void empty () { m_table.empty (); }
100
101 /* Return true when there are no elements in this hash set. */
is_empty()102 bool is_empty () const { return m_table.is_empty (); }
103
104 class iterator
105 {
106 public:
iterator(const typename hash_table<Traits,Lazy>::iterator & iter)107 explicit iterator (const typename hash_table<Traits,
108 Lazy>::iterator &iter) :
109 m_iter (iter) {}
110
111 iterator &operator++ ()
112 {
113 ++m_iter;
114 return *this;
115 }
116
117 Key
118 operator* ()
119 {
120 return *m_iter;
121 }
122
123 bool
124 operator != (const iterator &other) const
125 {
126 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
begin()135 iterator begin () const { return iterator (m_table.begin ()); }
end()136 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
debug_helper(hash_set<T> & ref)163 debug_helper (hash_set<T> &ref)
164 {
165 for (typename hash_set<T>::iterator it = ref.begin ();
166 it != ref.end (); ++it)
167 {
168 debug_slim (*it);
169 fputc ('\n', stderr);
170 }
171 }
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
gt_ggc_mx(hash_set<K,false,H> * h)193 gt_ggc_mx (hash_set<K, false, H> *h)
194 {
195 gt_ggc_mx (&h->m_table);
196 }
197
198 template<typename K, typename H>
199 static inline void
gt_pch_nx(hash_set<K,false,H> * h)200 gt_pch_nx (hash_set<K, false, H> *h)
201 {
202 gt_pch_nx (&h->m_table);
203 }
204
205 template<typename K, typename H>
206 static inline void
gt_pch_nx(hash_set<K,false,H> * h,gt_pointer_operator op,void * cookie)207 gt_pch_nx (hash_set<K, false, H> *h, gt_pointer_operator op, void *cookie)
208 {
209 op (&h->m_table.m_entries, cookie);
210 }
211
212 #endif
213