Branch data Line data Source code
1 : : /* Unit tests for hash-map.h.
2 : : Copyright (C) 2015-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 : : #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 "fixed-value.h"
27 : : #include "alias.h"
28 : : #include "flags.h"
29 : : #include "symtab.h"
30 : : #include "tree-core.h"
31 : : #include "stor-layout.h"
32 : : #include "tree.h"
33 : : #include "stringpool.h"
34 : : #include "selftest.h"
35 : :
36 : : #if CHECKING_P
37 : :
38 : : namespace selftest {
39 : :
40 : : /* Construct a hash_map <const char *, int> and verify that
41 : : various operations work correctly. */
42 : :
43 : : static void
44 : 4 : test_map_of_strings_to_int ()
45 : : {
46 : 4 : hash_map <const char *, int> m;
47 : :
48 : 4 : const char *ostrich = "ostrich";
49 : 4 : const char *elephant = "elephant";
50 : 4 : const char *ant = "ant";
51 : 4 : const char *spider = "spider";
52 : 4 : const char *millipede = "Illacme plenipes";
53 : 4 : const char *eric = "half a bee";
54 : :
55 : : /* A fresh hash_map should be empty. */
56 : 4 : ASSERT_TRUE (m.is_empty ());
57 : 4 : ASSERT_EQ (NULL, m.get (ostrich));
58 : :
59 : : /* Populate the hash_map. */
60 : 4 : ASSERT_EQ (false, m.put (ostrich, 2));
61 : 4 : ASSERT_EQ (false, m.put (elephant, 4));
62 : 4 : ASSERT_EQ (false, m.put (ant, 6));
63 : 4 : ASSERT_EQ (false, m.put (spider, 8));
64 : 4 : ASSERT_EQ (false, m.put (millipede, 750));
65 : 4 : ASSERT_EQ (false, m.put (eric, 3));
66 : :
67 : : /* Verify that we can recover the stored values. */
68 : 4 : ASSERT_EQ (6, m.elements ());
69 : 4 : ASSERT_EQ (2, *m.get (ostrich));
70 : 4 : ASSERT_EQ (4, *m.get (elephant));
71 : 4 : ASSERT_EQ (6, *m.get (ant));
72 : 4 : ASSERT_EQ (8, *m.get (spider));
73 : 4 : ASSERT_EQ (750, *m.get (millipede));
74 : 4 : ASSERT_EQ (3, *m.get (eric));
75 : :
76 : : /* Verify removing an item. */
77 : 4 : m.remove (eric);
78 : 4 : ASSERT_EQ (5, m.elements ());
79 : 4 : ASSERT_EQ (NULL, m.get (eric));
80 : :
81 : 4 : m.remove (eric);
82 : 4 : ASSERT_EQ (5, m.elements ());
83 : 4 : ASSERT_EQ (NULL, m.get (eric));
84 : :
85 : : /* A plain char * key is hashed based on its value (address), rather
86 : : than the string it points to. */
87 : 4 : char *another_ant = static_cast <char *> (xcalloc (4, 1));
88 : 4 : another_ant[0] = 'a';
89 : 4 : another_ant[1] = 'n';
90 : 4 : another_ant[2] = 't';
91 : 4 : another_ant[3] = 0;
92 : 4 : ASSERT_NE (ant, another_ant);
93 : 4 : unsigned prev_size = m.elements ();
94 : 4 : ASSERT_EQ (false, m.put (another_ant, 7));
95 : 4 : ASSERT_EQ (prev_size + 1, m.elements ());
96 : :
97 : : /* Need to use string_hash or nofree_string_hash key types to hash
98 : : based on the string contents. */
99 : 4 : hash_map <nofree_string_hash, int> string_map;
100 : 4 : ASSERT_EQ (false, string_map.put (ant, 1));
101 : 4 : ASSERT_EQ (1, string_map.elements ());
102 : 4 : ASSERT_EQ (true, string_map.put (another_ant, 5));
103 : 4 : ASSERT_EQ (1, string_map.elements ());
104 : :
105 : 4 : free (another_ant);
106 : 4 : }
107 : :
108 : : /* Construct a hash_map using int_hash and verify that
109 : : various operations work correctly. */
110 : :
111 : : static void
112 : 4 : test_map_of_int_to_strings ()
113 : : {
114 : 4 : const int EMPTY = -1;
115 : 4 : const int DELETED = -2;
116 : 4 : typedef int_hash <int, EMPTY, DELETED> int_hash_t;
117 : 4 : hash_map <int_hash_t, const char *> m;
118 : :
119 : 4 : const char *ostrich = "ostrich";
120 : 4 : const char *elephant = "elephant";
121 : 4 : const char *ant = "ant";
122 : 4 : const char *spider = "spider";
123 : 4 : const char *millipede = "Illacme plenipes";
124 : 4 : const char *eric = "half a bee";
125 : :
126 : : /* A fresh hash_map should be empty. */
127 : 4 : ASSERT_EQ (0, m.elements ());
128 : 4 : ASSERT_EQ (NULL, m.get (2));
129 : :
130 : : /* Populate the hash_map. */
131 : 4 : ASSERT_EQ (false, m.put (2, ostrich));
132 : 4 : ASSERT_EQ (false, m.put (4, elephant));
133 : 4 : ASSERT_EQ (false, m.put (6, ant));
134 : 4 : ASSERT_EQ (false, m.put (8, spider));
135 : 4 : ASSERT_EQ (false, m.put (750, millipede));
136 : 4 : ASSERT_EQ (false, m.put (3, eric));
137 : :
138 : : /* Verify that we can recover the stored values. */
139 : 4 : ASSERT_EQ (6, m.elements ());
140 : 4 : ASSERT_EQ (*m.get (2), ostrich);
141 : 4 : ASSERT_EQ (*m.get (4), elephant);
142 : 4 : ASSERT_EQ (*m.get (6), ant);
143 : 4 : ASSERT_EQ (*m.get (8), spider);
144 : 4 : ASSERT_EQ (*m.get (750), millipede);
145 : 4 : ASSERT_EQ (*m.get (3), eric);
146 : 4 : }
147 : :
148 : : typedef class hash_map_test_val_t
149 : : {
150 : : public:
151 : : static int ndefault;
152 : : static int ncopy;
153 : : static int nassign;
154 : : static int ndtor;
155 : :
156 : 696 : hash_map_test_val_t ()
157 : 696 : : ptr (&ptr)
158 : : {
159 : 696 : ++ndefault;
160 : : }
161 : :
162 : 616 : hash_map_test_val_t (const hash_map_test_val_t &rhs)
163 : 616 : : ptr (&ptr)
164 : : {
165 : 616 : ++ncopy;
166 : 616 : gcc_assert (rhs.ptr == &rhs.ptr);
167 : 616 : }
168 : :
169 : : hash_map_test_val_t& operator= (const hash_map_test_val_t &rhs)
170 : : {
171 : : ++nassign;
172 : : gcc_assert (ptr == &ptr);
173 : : gcc_assert (rhs.ptr == &rhs.ptr);
174 : : return *this;
175 : : }
176 : :
177 : 1312 : ~hash_map_test_val_t ()
178 : : {
179 : 1312 : gcc_assert (ptr == &ptr);
180 : 1312 : ++ndtor;
181 : 1312 : }
182 : :
183 : : void *ptr;
184 : : } val_t;
185 : :
186 : : int val_t::ndefault;
187 : : int val_t::ncopy;
188 : : int val_t::nassign;
189 : : int val_t::ndtor;
190 : :
191 : : static void
192 : 4 : test_map_of_type_with_ctor_and_dtor ()
193 : : {
194 : 4 : typedef hash_map <void *, val_t> Map;
195 : :
196 : 4 : {
197 : : /* Test default ctor. */
198 : 4 : Map m;
199 : 4 : (void)&m;
200 : 4 : }
201 : :
202 : 4 : ASSERT_TRUE (val_t::ndefault == 0);
203 : 4 : ASSERT_TRUE (val_t::ncopy == 0);
204 : 4 : ASSERT_TRUE (val_t::nassign == 0);
205 : 4 : ASSERT_TRUE (val_t::ndtor == 0);
206 : :
207 : 4 : {
208 : : /* Test single insertion. */
209 : 4 : Map m;
210 : 4 : void *p = &p;
211 : 4 : m.get_or_insert (p);
212 : 4 : }
213 : :
214 : 4 : ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
215 : :
216 : 4 : {
217 : : /* Test copy ctor. */
218 : 4 : Map m1;
219 : 4 : void *p = &p;
220 : 4 : val_t &rv1 = m1.get_or_insert (p);
221 : :
222 : 4 : int ncopy = val_t::ncopy;
223 : 4 : int nassign = val_t::nassign;
224 : :
225 : 4 : Map m2 (m1);
226 : 4 : val_t *pv2 = m2.get (p);
227 : :
228 : 4 : ASSERT_TRUE (ncopy + 1 == val_t::ncopy);
229 : 4 : ASSERT_TRUE (nassign == val_t::nassign);
230 : :
231 : 4 : ASSERT_TRUE (&rv1 != pv2);
232 : 4 : }
233 : :
234 : 4 : ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
235 : :
236 : : #if 0 /* Avoid testing until bug 90959 is fixed. */
237 : : {
238 : : /* Test copy assignment into an empty map. */
239 : : Map m1;
240 : : void *p = &p;
241 : : val_t &rv1 = m1.get_or_insert (p);
242 : :
243 : : int ncopy = val_t::ncopy;
244 : : int nassign = val_t::nassign;
245 : :
246 : : Map m2;
247 : : m2 = m1;
248 : : val_t *pv2 = m2.get (p);
249 : :
250 : : ASSERT_TRUE (ncopy == val_t::ncopy);
251 : : ASSERT_TRUE (nassign + 1 == val_t::nassign);
252 : :
253 : : ASSERT_TRUE (&rv1 != pv2);
254 : : }
255 : :
256 : : ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
257 : :
258 : : #endif
259 : :
260 : 4 : {
261 : 4 : Map m;
262 : 4 : void *p = &p, *q = &q;
263 : 4 : val_t &v1 = m.get_or_insert (p);
264 : 4 : val_t &v2 = m.get_or_insert (q);
265 : :
266 : 4 : ASSERT_TRUE (v1.ptr == &v1.ptr && &v2.ptr == v2.ptr);
267 : 4 : }
268 : :
269 : 4 : ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
270 : :
271 : 4 : {
272 : 4 : Map m;
273 : 4 : void *p = &p, *q = &q;
274 : 4 : m.get_or_insert (p);
275 : 4 : m.remove (p);
276 : 4 : m.get_or_insert (q);
277 : 4 : m.remove (q);
278 : :
279 : 4 : ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
280 : 4 : }
281 : :
282 : :
283 : : /* Verify basic construction and destruction of Value objects. */
284 : 4 : {
285 : : /* Configure, arbitrary. */
286 : 4 : const size_t N_init = 0;
287 : 4 : const int N_elem = 28;
288 : :
289 : 4 : void *a[N_elem];
290 : 116 : for (size_t i = 0; i < N_elem; ++i)
291 : 112 : a[i] = &a[i];
292 : :
293 : 4 : val_t::ndefault = 0;
294 : 4 : val_t::ncopy = 0;
295 : 4 : val_t::nassign = 0;
296 : 4 : val_t::ndtor = 0;
297 : 4 : Map m (N_init);
298 : 4 : ASSERT_EQ (val_t::ndefault
299 : : + val_t::ncopy
300 : : + val_t::nassign
301 : : + val_t::ndtor, 0);
302 : :
303 : 116 : for (int i = 0; i < N_elem; ++i)
304 : : {
305 : 112 : m.get_or_insert (a[i]);
306 : 112 : ASSERT_EQ (val_t::ndefault, 1 + i);
307 : 112 : ASSERT_EQ (val_t::ncopy, 0);
308 : 112 : ASSERT_EQ (val_t::nassign, 0);
309 : 112 : ASSERT_EQ (val_t::ndtor, i);
310 : :
311 : 112 : m.remove (a[i]);
312 : 112 : ASSERT_EQ (val_t::ndefault, 1 + i);
313 : 112 : ASSERT_EQ (val_t::ncopy, 0);
314 : 112 : ASSERT_EQ (val_t::nassign, 0);
315 : 112 : ASSERT_EQ (val_t::ndtor, 1 + i);
316 : : }
317 : 4 : }
318 : 4 : }
319 : :
320 : : /* Verify aspects of 'hash_table::expand', in particular that it doesn't leak
321 : : Value objects. */
322 : :
323 : : static void
324 : 8 : test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
325 : : {
326 : : /* Configure, so that hash table expansion triggers a few times. */
327 : 8 : const size_t N_init = 0;
328 : 8 : const int N_elem = 70;
329 : 8 : size_t expand_c_expected = 4;
330 : 8 : size_t expand_c = 0;
331 : :
332 : : /* For stability of this testing, we need all Key values 'k' to produce
333 : : unique hash values 'Traits::hash (k)', as otherwise the dynamic
334 : : insert/remove behavior may diverge across different architectures. This
335 : : is, for example, a problem when using the standard 'pointer_hash::hash',
336 : : which is simply doing a 'k >> 3' operation, which is fine on 64-bit
337 : : architectures, but on 32-bit architectures produces the same hash value
338 : : for subsequent 'a[i] = &a[i]' array elements. Therefore, use an
339 : : 'int_hash'. */
340 : :
341 : 8 : int a[N_elem];
342 : 568 : for (size_t i = 0; i < N_elem; ++i)
343 : 560 : a[i] = i;
344 : :
345 : 8 : const int EMPTY = -1;
346 : 8 : const int DELETED = -2;
347 : 8 : typedef hash_map<int_hash<int, EMPTY, DELETED>, val_t> Map;
348 : :
349 : : /* Note that we are starting with a fresh 'Map'. Even if an existing one has
350 : : been cleared out completely, there remain 'deleted' elements, and these
351 : : would disturb the following logic, where we don't have access to the
352 : : actual 'm_n_deleted' value. */
353 : 8 : size_t m_n_deleted = 0;
354 : :
355 : 8 : val_t::ndefault = 0;
356 : 8 : val_t::ncopy = 0;
357 : 8 : val_t::nassign = 0;
358 : 8 : val_t::ndtor = 0;
359 : 8 : Map m (N_init);
360 : :
361 : : /* In the following, in particular related to 'expand', we're adapting from
362 : : the internal logic of 'hash_table', glossing over "some details" not
363 : : relevant for this testing here. */
364 : :
365 : : /* Per 'hash_table::hash_table'. */
366 : 8 : size_t m_size;
367 : 8 : {
368 : 8 : unsigned int size_prime_index_ = hash_table_higher_prime_index (N_init);
369 : 8 : m_size = prime_tab[size_prime_index_].prime;
370 : : }
371 : :
372 : 8 : int n_expand_moved = 0;
373 : :
374 : 568 : for (int i = 0; i < N_elem; ++i)
375 : : {
376 : 560 : size_t elts = m.elements ();
377 : :
378 : : /* Per 'hash_table::find_slot_with_hash'. */
379 : 560 : size_t m_n_elements = elts + m_n_deleted;
380 : 560 : bool expand = m_size * 3 <= m_n_elements * 4;
381 : :
382 : 560 : m.get_or_insert (a[i]);
383 : 560 : if (expand)
384 : : {
385 : 32 : ++expand_c;
386 : :
387 : : /* Per 'hash_table::expand'. */
388 : 32 : {
389 : 32 : unsigned int nindex = hash_table_higher_prime_index (elts * 2);
390 : 32 : m_size = prime_tab[nindex].prime;
391 : : }
392 : 32 : m_n_deleted = 0;
393 : :
394 : : /* All non-deleted elements have been moved. */
395 : 32 : n_expand_moved += i;
396 : 32 : if (remove_some_inline)
397 : 16 : n_expand_moved -= (i + 2) / 3;
398 : : }
399 : :
400 : 560 : ASSERT_EQ (val_t::ndefault, 1 + i);
401 : 560 : ASSERT_EQ (val_t::ncopy, n_expand_moved);
402 : 560 : ASSERT_EQ (val_t::nassign, 0);
403 : 560 : if (remove_some_inline)
404 : 280 : ASSERT_EQ (val_t::ndtor, n_expand_moved + (i + 2) / 3);
405 : : else
406 : 280 : ASSERT_EQ (val_t::ndtor, n_expand_moved);
407 : :
408 : : /* Remove some inline. This never triggers an 'expand' here, but via
409 : : 'm_n_deleted' does influence any following one. */
410 : 560 : if (remove_some_inline
411 : 280 : && !(i % 3))
412 : : {
413 : 96 : m.remove (a[i]);
414 : : /* Per 'hash_table::remove_elt_with_hash'. */
415 : 96 : m_n_deleted++;
416 : :
417 : 96 : ASSERT_EQ (val_t::ndefault, 1 + i);
418 : 96 : ASSERT_EQ (val_t::ncopy, n_expand_moved);
419 : 96 : ASSERT_EQ (val_t::nassign, 0);
420 : 96 : ASSERT_EQ (val_t::ndtor, n_expand_moved + 1 + (i + 2) / 3);
421 : : }
422 : : }
423 : 8 : ASSERT_EQ (expand_c, expand_c_expected);
424 : :
425 : 8 : int ndefault = val_t::ndefault;
426 : 8 : int ncopy = val_t::ncopy;
427 : 8 : int nassign = val_t::nassign;
428 : 8 : int ndtor = val_t::ndtor;
429 : :
430 : 568 : for (int i = 0; i < N_elem; ++i)
431 : : {
432 : 560 : if (remove_some_inline
433 : 280 : && !(i % 3))
434 : 96 : continue;
435 : :
436 : 464 : m.remove (a[i]);
437 : 464 : ++ndtor;
438 : 464 : ASSERT_EQ (val_t::ndefault, ndefault);
439 : 464 : ASSERT_EQ (val_t::ncopy, ncopy);
440 : 464 : ASSERT_EQ (val_t::nassign, nassign);
441 : 560 : ASSERT_EQ (val_t::ndtor, ndtor);
442 : : }
443 : 8 : ASSERT_EQ (val_t::ndefault + val_t::ncopy, val_t::ndtor);
444 : 8 : }
445 : :
446 : : /* Test calling empty on a hash_map that has a key type with non-zero
447 : : "empty" value. */
448 : :
449 : : static void
450 : 4 : test_nonzero_empty_key ()
451 : : {
452 : 4 : typedef int_hash<int, INT_MIN, INT_MAX> IntHash;
453 : 4 : hash_map<int, int, simple_hashmap_traits<IntHash, int> > x;
454 : :
455 : 128 : for (int i = 1; i != 32; ++i)
456 : 124 : x.put (i, i);
457 : :
458 : 4 : ASSERT_EQ (x.get (0), NULL);
459 : 4 : ASSERT_EQ (*x.get (1), 1);
460 : :
461 : 4 : x.empty ();
462 : :
463 : 4 : ASSERT_EQ (x.get (0), NULL);
464 : 4 : ASSERT_EQ (x.get (1), NULL);
465 : 4 : }
466 : :
467 : : /* Run all of the selftests within this file. */
468 : :
469 : : void
470 : 4 : hash_map_tests_cc_tests ()
471 : : {
472 : 4 : test_map_of_strings_to_int ();
473 : 4 : test_map_of_int_to_strings ();
474 : 4 : test_map_of_type_with_ctor_and_dtor ();
475 : 4 : test_map_of_type_with_ctor_and_dtor_expand (false);
476 : 4 : test_map_of_type_with_ctor_and_dtor_expand (true);
477 : 4 : test_nonzero_empty_key ();
478 : 4 : }
479 : :
480 : : } // namespace selftest
481 : :
482 : : #endif /* CHECKING_P */
|
