Branch data Line data Source code
1 : : /* Unit tests for hash-set.h.
2 : : Copyright (C) 2015-2025 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 : : #include "config.h"
21 : : #include "system.h"
22 : : #include "coretypes.h"
23 : : #include "tm.h"
24 : : #include "opts.h"
25 : : #include "hash-set.h"
26 : : #include "selftest.h"
27 : :
28 : : #if CHECKING_P
29 : :
30 : : namespace selftest {
31 : :
32 : : /* Construct a hash_set <const char *> and verify that various operations
33 : : work correctly. */
34 : :
35 : : static void
36 : 4 : test_set_of_strings ()
37 : : {
38 : 4 : hash_set <const char *> s;
39 : 4 : ASSERT_EQ (0, s.elements ());
40 : :
41 : 4 : const char *red = "red";
42 : 4 : const char *green = "green";
43 : 4 : const char *blue = "blue";
44 : :
45 : 4 : ASSERT_EQ (false, s.contains (red));
46 : :
47 : 4 : for (hash_set<const char *>::iterator it = s.begin (); it != s.end (); ++it)
48 : 0 : ASSERT_EQ (true, false);
49 : :
50 : : /* Populate the hash_set. */
51 : 4 : ASSERT_EQ (false, s.add (red));
52 : 4 : ASSERT_EQ (false, s.add (green));
53 : 4 : ASSERT_EQ (false, s.add (blue));
54 : 4 : ASSERT_EQ (true, s.add (green));
55 : :
56 : : /* Verify that the values are now within the set. */
57 : 4 : ASSERT_EQ (true, s.contains (red));
58 : 4 : ASSERT_EQ (true, s.contains (green));
59 : 4 : ASSERT_EQ (true, s.contains (blue));
60 : 4 : ASSERT_EQ (3, s.elements ());
61 : :
62 : : /* Test removal. */
63 : 4 : s.remove (red);
64 : 4 : ASSERT_EQ (false, s.contains (red));
65 : 4 : ASSERT_EQ (true, s.contains (green));
66 : 4 : ASSERT_EQ (true, s.contains (blue));
67 : 4 : ASSERT_EQ (2, s.elements ());
68 : :
69 : 4 : s.remove (red);
70 : 4 : ASSERT_EQ (false, s.contains (red));
71 : 4 : ASSERT_EQ (true, s.contains (green));
72 : 4 : ASSERT_EQ (true, s.contains (blue));
73 : 4 : ASSERT_EQ (2, s.elements ());
74 : :
75 : 4 : int seen = 0;
76 : 12 : for (hash_set<const char *>::iterator it = s.begin (); it != s.end (); ++it)
77 : : {
78 : 8 : int n = *it == green;
79 : 8 : if (n == 0)
80 : 4 : ASSERT_EQ (*it, blue);
81 : 8 : ASSERT_EQ (seen & (1 << n), 0);
82 : 8 : seen |= 1 << n;
83 : : }
84 : 4 : ASSERT_EQ (seen, 3);
85 : :
86 : 4 : hash_set <const char *, true> t;
87 : 4 : ASSERT_EQ (0, t.elements ());
88 : :
89 : 4 : ASSERT_EQ (false, t.contains (red));
90 : :
91 : 4 : for (hash_set<const char *, true>::iterator it = t.begin ();
92 : 4 : it != t.end (); ++it)
93 : 0 : ASSERT_EQ (true, false);
94 : :
95 : : /* Populate the hash_set. */
96 : 4 : ASSERT_EQ (false, t.add (red));
97 : 4 : ASSERT_EQ (false, t.add (green));
98 : 4 : ASSERT_EQ (false, t.add (blue));
99 : 4 : ASSERT_EQ (true, t.add (green));
100 : :
101 : : /* Verify that the values are now within the set. */
102 : 4 : ASSERT_EQ (true, t.contains (red));
103 : 4 : ASSERT_EQ (true, t.contains (green));
104 : 4 : ASSERT_EQ (true, t.contains (blue));
105 : 4 : ASSERT_EQ (3, t.elements ());
106 : :
107 : 4 : seen = 0;
108 : 4 : for (hash_set<const char *, true>::iterator it = t.begin ();
109 : 28 : it != t.end (); ++it)
110 : : {
111 : 12 : int n = 2;
112 : 12 : if (*it == green)
113 : : n = 0;
114 : 8 : else if (*it == blue)
115 : : n = 1;
116 : : else
117 : 4 : ASSERT_EQ (*it, red);
118 : 12 : ASSERT_EQ (seen & (1 << n), 0);
119 : 12 : seen |= 1 << n;
120 : : }
121 : 4 : ASSERT_EQ (seen, 7);
122 : :
123 : : /* Test removal. */
124 : 4 : t.remove (red);
125 : 4 : ASSERT_EQ (false, t.contains (red));
126 : 4 : ASSERT_EQ (true, t.contains (green));
127 : 4 : ASSERT_EQ (true, t.contains (blue));
128 : 4 : ASSERT_EQ (2, t.elements ());
129 : :
130 : 4 : t.remove (red);
131 : 4 : ASSERT_EQ (false, t.contains (red));
132 : 4 : ASSERT_EQ (true, t.contains (green));
133 : 4 : ASSERT_EQ (true, t.contains (blue));
134 : 4 : ASSERT_EQ (2, t.elements ());
135 : 4 : }
136 : :
137 : : typedef class hash_set_test_value_t
138 : : {
139 : : public:
140 : : static int ndefault;
141 : : static int ncopy;
142 : : static int nassign;
143 : : static int ndtor;
144 : :
145 : 16 : hash_set_test_value_t (int v = 1): pval (&val), val (v)
146 : : {
147 : 16 : ++ndefault;
148 : : }
149 : :
150 : 20 : hash_set_test_value_t (const hash_set_test_value_t &rhs)
151 : 20 : : pval (&val), val (rhs.val)
152 : : {
153 : 0 : ++ncopy;
154 : : }
155 : :
156 : : hash_set_test_value_t& operator= (const hash_set_test_value_t &rhs)
157 : : {
158 : : ++nassign;
159 : : val = rhs.val;
160 : : return *this;
161 : : }
162 : :
163 : 44 : ~hash_set_test_value_t ()
164 : : {
165 : : /* Verify that the value hasn't been corrupted. */
166 : 44 : gcc_assert (*pval > 0);
167 : 44 : gcc_assert (pval == &val);
168 : 44 : *pval = -3;
169 : 44 : ++ndtor;
170 : 44 : }
171 : :
172 : : int *pval;
173 : : int val;
174 : : } val_t;
175 : :
176 : : int val_t::ndefault;
177 : : int val_t::ncopy;
178 : : int val_t::nassign;
179 : : int val_t::ndtor;
180 : :
181 : : struct value_hash_traits: int_hash<int, -1, -2>
182 : : {
183 : : typedef int_hash<int, -1, -2> base_type;
184 : : typedef val_t value_type;
185 : : typedef value_type compare_type;
186 : :
187 : 136 : static hashval_t hash (const value_type &v)
188 : : {
189 : 136 : return base_type::hash (v.val);
190 : : }
191 : :
192 : 84 : static bool equal (const value_type &a, const compare_type &b)
193 : : {
194 : 84 : return base_type::equal (a.val, b.val);
195 : : }
196 : :
197 : 8 : static void mark_deleted (value_type &v)
198 : : {
199 : 8 : base_type::mark_deleted (v.val);
200 : : }
201 : :
202 : : static const bool empty_zero_p = false;
203 : :
204 : 208 : static void mark_empty (value_type &v)
205 : : {
206 : 208 : base_type::mark_empty (v.val);
207 : : }
208 : :
209 : 140 : static bool is_deleted (const value_type &v)
210 : : {
211 : 20 : return base_type::is_deleted (v.val);
212 : : }
213 : :
214 : 1004 : static bool is_empty (const value_type &v)
215 : : {
216 : 988 : return base_type::is_empty (v.val);
217 : : }
218 : :
219 : 20 : static void remove (value_type &v)
220 : : {
221 : 20 : v.~value_type ();
222 : 12 : }
223 : : };
224 : :
225 : : static void
226 : 4 : test_set_of_type_with_ctor_and_dtor ()
227 : : {
228 : 4 : typedef hash_set <val_t, false, value_hash_traits> Set;
229 : :
230 : 4 : {
231 : 4 : Set s;
232 : 4 : (void)&s;
233 : 4 : }
234 : :
235 : 4 : ASSERT_TRUE (val_t::ndefault == 0);
236 : 4 : ASSERT_TRUE (val_t::ncopy == 0);
237 : 4 : ASSERT_TRUE (val_t::nassign == 0);
238 : 4 : ASSERT_TRUE (val_t::ndtor == 0);
239 : :
240 : 4 : {
241 : 4 : Set s;
242 : 4 : ASSERT_EQ (false, s.add (val_t ()));
243 : 4 : ASSERT_EQ (true, 1 == s.elements ());
244 : 4 : }
245 : :
246 : 4 : ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
247 : :
248 : 4 : {
249 : 4 : Set s;
250 : 4 : ASSERT_EQ (false, s.add (val_t ()));
251 : 4 : ASSERT_EQ (true, s.add (val_t ()));
252 : 4 : ASSERT_EQ (true, 1 == s.elements ());
253 : 4 : }
254 : :
255 : 4 : ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
256 : :
257 : 4 : {
258 : 4 : Set s;
259 : 4 : val_t v1 (1), v2 (2), v3 (3);
260 : 4 : int ndefault = val_t::ndefault;
261 : 4 : int nassign = val_t::nassign;
262 : :
263 : 4 : ASSERT_EQ (false, s.add (v1));
264 : 4 : ASSERT_EQ (true, s.contains (v1));
265 : 4 : ASSERT_EQ (true, 1 == s.elements ());
266 : :
267 : 4 : ASSERT_EQ (false, s.add (v2));
268 : 4 : ASSERT_EQ (true, s.contains (v2));
269 : 4 : ASSERT_EQ (true, 2 == s.elements ());
270 : :
271 : 4 : ASSERT_EQ (false, s.add (v3));
272 : 4 : ASSERT_EQ (true, s.contains (v3));
273 : 4 : ASSERT_EQ (true, 3 == s.elements ());
274 : :
275 : 4 : ASSERT_EQ (true, s.add (v2));
276 : 4 : ASSERT_EQ (true, s.contains (v2));
277 : 4 : ASSERT_EQ (true, 3 == s.elements ());
278 : :
279 : 4 : s.remove (v2);
280 : 4 : ASSERT_EQ (true, 2 == s.elements ());
281 : 4 : s.remove (v3);
282 : 4 : ASSERT_EQ (true, 1 == s.elements ());
283 : :
284 : : /* Verify that no default ctors or assignment operators have
285 : : been called. */
286 : 4 : ASSERT_EQ (true, ndefault == val_t::ndefault);
287 : 4 : ASSERT_EQ (true, nassign == val_t::nassign);
288 : 4 : }
289 : :
290 : 4 : ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
291 : 4 : }
292 : :
293 : : /* Run all of the selftests within this file. */
294 : :
295 : : void
296 : 4 : hash_set_tests_cc_tests ()
297 : : {
298 : 4 : test_set_of_strings ();
299 : 4 : test_set_of_type_with_ctor_and_dtor ();
300 : 4 : }
301 : :
302 : : } // namespace selftest
303 : :
304 : : #endif /* #if CHECKING_P */
|
