1 /* A type-safe hash set.
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_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)
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 *
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
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 {
62 new (e) Key (k);
63 // Catch attempts to insert e.g. a NULL pointer.
64 gcc_checking_assert (!Traits::is_empty (*e)
65 && !Traits::is_deleted (*e));
66 }
67
68 return existed;
69 }
70
71 /* if the passed in key is in the map return its value otherwise NULL. */
72
73 bool contains (const Key &k)
74 {
75 if (Lazy)
76 return (m_table.find_slot_with_hash (k, Traits::hash (k), NO_INSERT)
77 != NULL);
78 Key &e = m_table.find_with_hash (k, Traits::hash (k));
79 return !Traits::is_empty (e);
80 }
81
82 void remove (const Key &k)
83 {
84 m_table.remove_elt_with_hash (k, Traits::hash (k));
85 }
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 void traverse (Arg a) const
92 {
93 for (typename hash_table<Traits, Lazy>::iterator iter = m_table.begin ();
94 iter != m_table.end (); ++iter)
95 f (*iter, a);
96 }
97
98 /* Return the number of elements in the set. */
99
100 size_t elements () const { return m_table.elements (); }
101
102 /* Clear the hash table. */
103
104 void empty () { m_table.empty (); }
105
106 /* Return true when there are no elements in this hash set. */
107 bool is_empty () const { return m_table.is_empty (); }
108
109 class iterator
110 {
111 public:
112 explicit iterator (const typename hash_table<Traits,
113 Lazy>::iterator &iter) :
114 m_iter (iter) {}
115
116 iterator &operator++ ()
117 {
118 ++m_iter;
119 return *this;
120 }
121
122 Key
123 operator* ()
124 {
125 return *m_iter;
126 }
127
128 bool
129 operator != (const iterator &other) const
130 {
131 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 iterator begin () const { return iterator (m_table.begin ()); }
141 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 debug_helper (hash_set<T> &ref)
169 {
170 for (typename hash_set<T>::iterator it = ref.begin ();
171 it != ref.end (); ++it)
172 {
173 debug_slim (*it);
174 fputc ('\n', stderr);
175 }
176 }
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 gt_ggc_mx (hash_set<K, false, H> *h)
199 {
200 gt_ggc_mx (&h->m_table);
201 }
202
203 template<typename K, typename H>
204 inline void
205 gt_pch_nx (hash_set<K, false, H> *h)
206 {
207 gt_pch_nx (&h->m_table);
208 }
209
210 template<typename K, typename H>
211 inline void
212 gt_pch_nx (hash_set<K, false, H> *h, gt_pointer_operator op, void *cookie)
213 {
214 op (&h->m_table.m_entries, NULL, cookie);
215 }
216
217 #endif