Line data Source code
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 905669832 : class hash_set
37 : {
38 : public:
39 : typedef typename Traits::value_type Key;
40 906515387 : explicit hash_set (size_t n = 13, bool ggc = false CXX_MEM_STAT_INFO)
41 904886018 : : 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 221 : create_ggc (size_t n)
47 : {
48 221 : hash_set *set = ggc_alloc<hash_set> ();
49 221 : new (set) hash_set (n, true);
50 221 : 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 1836483878 : bool add (const Key &k)
57 : {
58 1836483878 : Key *e = m_table.find_slot_with_hash (k, Traits::hash (k), INSERT);
59 1836483878 : bool existed = !Traits::is_empty (*e);
60 1836483878 : if (!existed)
61 : {
62 1667745040 : new (e) Key (k);
63 : // Catch attempts to insert e.g. a NULL pointer.
64 1667745040 : gcc_checking_assert (!Traits::is_empty (*e)
65 : && !Traits::is_deleted (*e));
66 : }
67 :
68 1836483878 : return existed;
69 : }
70 :
71 : /* if the passed in key is in the map return its value otherwise NULL. */
72 :
73 895811218 : bool contains (const Key &k)
74 : {
75 : if (Lazy)
76 397440 : return (m_table.find_slot_with_hash (k, Traits::hash (k), NO_INSERT)
77 397440 : != NULL);
78 895413778 : Key &e = m_table.find_with_hash (k, Traits::hash (k));
79 895413778 : return !Traits::is_empty (e);
80 : }
81 :
82 431756 : void remove (const Key &k)
83 : {
84 431756 : m_table.remove_elt_with_hash (k, Traits::hash (k));
85 430292 : }
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 420 : size_t elements () const { return m_table.elements (); }
101 :
102 : /* Clear the hash table. */
103 :
104 23088 : void empty () { m_table.empty (); }
105 :
106 : /* Return true when there are no elements in this hash set. */
107 1218463 : bool is_empty () const { return m_table.is_empty (); }
108 :
109 : class iterator
110 : {
111 : public:
112 11992 : explicit iterator (const typename hash_table<Traits,
113 : Lazy>::iterator &iter) :
114 6039 : m_iter (iter) {}
115 :
116 36 : iterator &operator++ ()
117 : {
118 36 : ++m_iter;
119 36 : return *this;
120 : }
121 :
122 : Key
123 36 : operator* ()
124 : {
125 36 : return *m_iter;
126 : }
127 :
128 : bool
129 6075 : operator != (const iterator &other) const
130 : {
131 12114 : 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 6039 : iterator begin () const { return iterator (m_table.begin ()); }
141 6047 : 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
|
