1 | /* Unit tests for hash-set.h. |
2 | Copyright (C) 2015-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 | #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 | 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 (k: 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 (k: 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 (k: 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 (k: 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 | |
187 | static hashval_t hash (const value_type &v) |
188 | { |
189 | return base_type::hash (x: v.val); |
190 | } |
191 | |
192 | static bool equal (const value_type &a, const compare_type &b) |
193 | { |
194 | return base_type::equal (x: a.val, y: b.val); |
195 | } |
196 | |
197 | static void mark_deleted (value_type &v) |
198 | { |
199 | base_type::mark_deleted (x&: v.val); |
200 | } |
201 | |
202 | static const bool empty_zero_p = false; |
203 | |
204 | static void mark_empty (value_type &v) |
205 | { |
206 | base_type::mark_empty (x&: v.val); |
207 | } |
208 | |
209 | static bool is_deleted (const value_type &v) |
210 | { |
211 | return base_type::is_deleted (x: v.val); |
212 | } |
213 | |
214 | static bool is_empty (const value_type &v) |
215 | { |
216 | return base_type::is_empty (x: v.val); |
217 | } |
218 | |
219 | static void remove (value_type &v) |
220 | { |
221 | v.~value_type (); |
222 | } |
223 | }; |
224 | |
225 | static void |
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 (k: v2); |
280 | ASSERT_EQ (true, 2 == s.elements ()); |
281 | s.remove (k: 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 |
296 | hash_set_tests_cc_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 | |