Line data Source code
1 : /* Unit tests for hash-map.h.
2 : Copyright (C) 2015-2026 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 */
|
