Branch data Line data Source code
1 : : /* A type-safe hash set.
2 : : Copyright (C) 2014-2024 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 : 4866889648 : class hash_set
37 : : {
38 : : public:
39 : : typedef typename Traits::value_type Key;
40 : 5380183891 : explicit hash_set (size_t n = 13, bool ggc = false CXX_MEM_STAT_INFO)
41 : 4881154055 : : 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 : 13379308 : create_ggc (size_t n)
47 : : {
48 : 13379308 : hash_set *set = ggc_alloc<hash_set> ();
49 : 13379308 : new (set) hash_set (n, true);
50 : 13379308 : 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 : 26452725678 : bool add (const Key &k)
57 : : {
58 : 26452725678 : Key *e = m_table.find_slot_with_hash (k, Traits::hash (k), INSERT);
59 : 26452725678 : bool existed = !Traits::is_empty (*e);
60 : 26452725678 : if (!existed)
61 : : {
62 : 24899049842 : new (e) Key (k);
63 : : // Catch attempts to insert e.g. a NULL pointer.
64 : 24899049842 : gcc_checking_assert (!Traits::is_empty (*e)
65 : : && !Traits::is_deleted (*e));
66 : : }
67 : :
68 : 26452725678 : return existed;
69 : : }
70 : :
71 : : /* if the passed in key is in the map return its value otherwise NULL. */
72 : :
73 : 16047159637 : bool contains (const Key &k)
74 : : {
75 : : if (Lazy)
76 : 647500 : return (m_table.find_slot_with_hash (k, Traits::hash (k), NO_INSERT)
77 : 647500 : != NULL);
78 : 16046512137 : Key &e = m_table.find_with_hash (k, Traits::hash (k));
79 : 16046512137 : return !Traits::is_empty (e);
80 : : }
81 : :
82 : 54329922 : void remove (const Key &k)
83 : : {
84 : 54329922 : m_table.remove_elt_with_hash (k, Traits::hash (k));
85 : 1768057 : }
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 : 22949432 : void traverse (Arg a) const
92 : : {
93 : 24045869 : for (typename hash_table<Traits, Lazy>::iterator iter = m_table.begin ();
94 : 25142266 : iter != m_table.end (); ++iter)
95 : 1096437 : f (*iter, a);
96 : 22949432 : }
97 : :
98 : : /* Return the number of elements in the set. */
99 : :
100 : 149470077 : size_t elements () const { return m_table.elements (); }
101 : :
102 : : /* Clear the hash table. */
103 : :
104 : 30262452 : void empty () { m_table.empty (); }
105 : :
106 : : /* Return true when there are no elements in this hash set. */
107 : 6611723 : bool is_empty () const { return m_table.is_empty (); }
108 : :
109 : : class iterator
110 : : {
111 : : public:
112 : 26206460 : explicit iterator (const typename hash_table<Traits,
113 : : Lazy>::iterator &iter) :
114 : 23653542 : m_iter (iter) {}
115 : :
116 : 18834059 : iterator &operator++ ()
117 : : {
118 : 18834059 : ++m_iter;
119 : 18832399 : return *this;
120 : : }
121 : :
122 : : Key
123 : 19888375 : operator* ()
124 : : {
125 : 19877265 : return *m_iter;
126 : : }
127 : :
128 : : bool
129 : 42430498 : operator != (const iterator &other) const
130 : : {
131 : 65105751 : 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 : 23653542 : iterator begin () const { return iterator (m_table.begin ()); }
141 : 36660092 : 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 : 0 : debug_helper (hash_set<T> &ref)
169 : : {
170 : 0 : for (typename hash_set<T>::iterator it = ref.begin ();
171 : 0 : it != ref.end (); ++it)
172 : : {
173 : 0 : debug_slim (*it);
174 : 0 : fputc ('\n', stderr);
175 : : }
176 : 0 : }
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 : 23420362 : gt_ggc_mx (hash_set<K, false, H> *h)
199 : : {
200 : 23420362 : gt_ggc_mx (&h->m_table);
201 : 23420362 : }
202 : :
203 : : template<typename K, typename H>
204 : : inline void
205 : 6431 : gt_pch_nx (hash_set<K, false, H> *h)
206 : : {
207 : 6431 : gt_pch_nx (&h->m_table);
208 : 6431 : }
209 : :
210 : : template<typename K, typename H>
211 : : inline void
212 : 6431 : gt_pch_nx (hash_set<K, false, H> *h, gt_pointer_operator op, void *cookie)
213 : : {
214 : 6431 : op (&h->m_table.m_entries, NULL, cookie);
215 : 6431 : }
216 : :
217 : : #endif
|
