1 /* Unit tests for hash-set.h.
2 Copyright (C) 2015-2021 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
test_set_of_strings()36 test_set_of_strings ()
37 {
38 hash_set <const char *> s;
39 ASSERT_EQ (0, s.elements ());
40
41 const char *red = "red";
42 const char *green = "green";
43 const char *blue = "blue";
44
45 ASSERT_EQ (false, s.contains (red));
46
47 for (hash_set<const char *>::iterator it = s.begin (); it != s.end (); ++it)
48 ASSERT_EQ (true, false);
49
50 /* Populate the hash_set. */
51 ASSERT_EQ (false, s.add (red));
52 ASSERT_EQ (false, s.add (green));
53 ASSERT_EQ (false, s.add (blue));
54 ASSERT_EQ (true, s.add (green));
55
56 /* Verify that the values are now within the set. */
57 ASSERT_EQ (true, s.contains (red));
58 ASSERT_EQ (true, s.contains (green));
59 ASSERT_EQ (true, s.contains (blue));
60 ASSERT_EQ (3, s.elements ());
61
62 /* Test removal. */
63 s.remove (red);
64 ASSERT_EQ (false, s.contains (red));
65 ASSERT_EQ (true, s.contains (green));
66 ASSERT_EQ (true, s.contains (blue));
67 ASSERT_EQ (2, s.elements ());
68
69 s.remove (red);
70 ASSERT_EQ (false, s.contains (red));
71 ASSERT_EQ (true, s.contains (green));
72 ASSERT_EQ (true, s.contains (blue));
73 ASSERT_EQ (2, s.elements ());
74
75 int seen = 0;
76 for (hash_set<const char *>::iterator it = s.begin (); it != s.end (); ++it)
77 {
78 int n = *it == green;
79 if (n == 0)
80 ASSERT_EQ (*it, blue);
81 ASSERT_EQ (seen & (1 << n), 0);
82 seen |= 1 << n;
83 }
84 ASSERT_EQ (seen, 3);
85
86 hash_set <const char *, true> t;
87 ASSERT_EQ (0, t.elements ());
88
89 ASSERT_EQ (false, t.contains (red));
90
91 for (hash_set<const char *, true>::iterator it = t.begin ();
92 it != t.end (); ++it)
93 ASSERT_EQ (true, false);
94
95 /* Populate the hash_set. */
96 ASSERT_EQ (false, t.add (red));
97 ASSERT_EQ (false, t.add (green));
98 ASSERT_EQ (false, t.add (blue));
99 ASSERT_EQ (true, t.add (green));
100
101 /* Verify that the values are now within the set. */
102 ASSERT_EQ (true, t.contains (red));
103 ASSERT_EQ (true, t.contains (green));
104 ASSERT_EQ (true, t.contains (blue));
105 ASSERT_EQ (3, t.elements ());
106
107 seen = 0;
108 for (hash_set<const char *, true>::iterator it = t.begin ();
109 it != t.end (); ++it)
110 {
111 int n = 2;
112 if (*it == green)
113 n = 0;
114 else if (*it == blue)
115 n = 1;
116 else
117 ASSERT_EQ (*it, red);
118 ASSERT_EQ (seen & (1 << n), 0);
119 seen |= 1 << n;
120 }
121 ASSERT_EQ (seen, 7);
122
123 /* Test removal. */
124 t.remove (red);
125 ASSERT_EQ (false, t.contains (red));
126 ASSERT_EQ (true, t.contains (green));
127 ASSERT_EQ (true, t.contains (blue));
128 ASSERT_EQ (2, t.elements ());
129
130 t.remove (red);
131 ASSERT_EQ (false, t.contains (red));
132 ASSERT_EQ (true, t.contains (green));
133 ASSERT_EQ (true, t.contains (blue));
134 ASSERT_EQ (2, t.elements ());
135 }
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 hash_set_test_value_t (int v = 1): pval (&val), val (v)
146 {
147 ++ndefault;
148 }
149
150 hash_set_test_value_t (const hash_set_test_value_t &rhs)
151 : pval (&val), val (rhs.val)
152 {
153 ++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 ~hash_set_test_value_t ()
164 {
165 /* Verify that the value hasn't been corrupted. */
166 gcc_assert (*pval > 0);
167 gcc_assert (pval == &val);
168 *pval = -3;
169 ++ndtor;
170 }
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
hashvalue_hash_traits187 static hashval_t hash (const value_type &v)
188 {
189 return base_type::hash (v.val);
190 }
191
equalvalue_hash_traits192 static bool equal (const value_type &a, const compare_type &b)
193 {
194 return base_type::equal (a.val, b.val);
195 }
196
mark_deletedvalue_hash_traits197 static void mark_deleted (value_type &v)
198 {
199 base_type::mark_deleted (v.val);
200 }
201
202 static const bool empty_zero_p = false;
203
mark_emptyvalue_hash_traits204 static void mark_empty (value_type &v)
205 {
206 base_type::mark_empty (v.val);
207 }
208
is_deletedvalue_hash_traits209 static bool is_deleted (const value_type &v)
210 {
211 return base_type::is_deleted (v.val);
212 }
213
is_emptyvalue_hash_traits214 static bool is_empty (const value_type &v)
215 {
216 return base_type::is_empty (v.val);
217 }
218
removevalue_hash_traits219 static void remove (value_type &v)
220 {
221 v.~value_type ();
222 }
223 };
224
225 static void
test_set_of_type_with_ctor_and_dtor()226 test_set_of_type_with_ctor_and_dtor ()
227 {
228 typedef hash_set <val_t, false, value_hash_traits> Set;
229
230 {
231 Set s;
232 (void)&s;
233 }
234
235 ASSERT_TRUE (val_t::ndefault == 0);
236 ASSERT_TRUE (val_t::ncopy == 0);
237 ASSERT_TRUE (val_t::nassign == 0);
238 ASSERT_TRUE (val_t::ndtor == 0);
239
240 {
241 Set s;
242 ASSERT_EQ (false, s.add (val_t ()));
243 ASSERT_EQ (true, 1 == s.elements ());
244 }
245
246 ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
247
248 {
249 Set s;
250 ASSERT_EQ (false, s.add (val_t ()));
251 ASSERT_EQ (true, s.add (val_t ()));
252 ASSERT_EQ (true, 1 == s.elements ());
253 }
254
255 ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
256
257 {
258 Set s;
259 val_t v1 (1), v2 (2), v3 (3);
260 int ndefault = val_t::ndefault;
261 int nassign = val_t::nassign;
262
263 ASSERT_EQ (false, s.add (v1));
264 ASSERT_EQ (true, s.contains (v1));
265 ASSERT_EQ (true, 1 == s.elements ());
266
267 ASSERT_EQ (false, s.add (v2));
268 ASSERT_EQ (true, s.contains (v2));
269 ASSERT_EQ (true, 2 == s.elements ());
270
271 ASSERT_EQ (false, s.add (v3));
272 ASSERT_EQ (true, s.contains (v3));
273 ASSERT_EQ (true, 3 == s.elements ());
274
275 ASSERT_EQ (true, s.add (v2));
276 ASSERT_EQ (true, s.contains (v2));
277 ASSERT_EQ (true, 3 == s.elements ());
278
279 s.remove (v2);
280 ASSERT_EQ (true, 2 == s.elements ());
281 s.remove (v3);
282 ASSERT_EQ (true, 1 == s.elements ());
283
284 /* Verify that no default ctors or assignment operators have
285 been called. */
286 ASSERT_EQ (true, ndefault == val_t::ndefault);
287 ASSERT_EQ (true, nassign == val_t::nassign);
288 }
289
290 ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
291 }
292
293 /* Run all of the selftests within this file. */
294
295 void
hash_set_tests_c_tests()296 hash_set_tests_c_tests ()
297 {
298 test_set_of_strings ();
299 test_set_of_type_with_ctor_and_dtor ();
300 }
301
302 } // namespace selftest
303
304 #endif /* #if CHECKING_P */
305