1/* Unit tests for hash-map.h.
2 Copyright (C) 2015-2023 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
38namespace selftest {
39
40/* Construct a hash_map <const char *, int> and verify that
41 various operations work correctly. */
42
43static void
44test_map_of_strings_to_int ()
45{
46 hash_map <const char *, int> m;
47
48 const char *ostrich = "ostrich";
49 const char *elephant = "elephant";
50 const char *ant = "ant";
51 const char *spider = "spider";
52 const char *millipede = "Illacme plenipes";
53 const char *eric = "half a bee";
54
55 /* A fresh hash_map should be empty. */
56 ASSERT_TRUE (m.is_empty ());
57 ASSERT_EQ (NULL, m.get (ostrich));
58
59 /* Populate the hash_map. */
60 ASSERT_EQ (false, m.put (ostrich, 2));
61 ASSERT_EQ (false, m.put (elephant, 4));
62 ASSERT_EQ (false, m.put (ant, 6));
63 ASSERT_EQ (false, m.put (spider, 8));
64 ASSERT_EQ (false, m.put (millipede, 750));
65 ASSERT_EQ (false, m.put (eric, 3));
66
67 /* Verify that we can recover the stored values. */
68 ASSERT_EQ (6, m.elements ());
69 ASSERT_EQ (2, *m.get (ostrich));
70 ASSERT_EQ (4, *m.get (elephant));
71 ASSERT_EQ (6, *m.get (ant));
72 ASSERT_EQ (8, *m.get (spider));
73 ASSERT_EQ (750, *m.get (millipede));
74 ASSERT_EQ (3, *m.get (eric));
75
76 /* Verify removing an item. */
77 m.remove (k: eric);
78 ASSERT_EQ (5, m.elements ());
79 ASSERT_EQ (NULL, m.get (eric));
80
81 m.remove (k: eric);
82 ASSERT_EQ (5, m.elements ());
83 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 char *another_ant = static_cast <char *> (xcalloc (4, 1));
88 another_ant[0] = 'a';
89 another_ant[1] = 'n';
90 another_ant[2] = 't';
91 another_ant[3] = 0;
92 ASSERT_NE (ant, another_ant);
93 unsigned prev_size = m.elements ();
94 ASSERT_EQ (false, m.put (another_ant, 7));
95 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 hash_map <nofree_string_hash, int> string_map;
100 ASSERT_EQ (false, string_map.put (ant, 1));
101 ASSERT_EQ (1, string_map.elements ());
102 ASSERT_EQ (true, string_map.put (another_ant, 5));
103 ASSERT_EQ (1, string_map.elements ());
104
105 free (ptr: another_ant);
106}
107
108/* Construct a hash_map using int_hash and verify that
109 various operations work correctly. */
110
111static void
112test_map_of_int_to_strings ()
113{
114 const int EMPTY = -1;
115 const int DELETED = -2;
116 typedef int_hash <int, EMPTY, DELETED> int_hash_t;
117 hash_map <int_hash_t, const char *> m;
118
119 const char *ostrich = "ostrich";
120 const char *elephant = "elephant";
121 const char *ant = "ant";
122 const char *spider = "spider";
123 const char *millipede = "Illacme plenipes";
124 const char *eric = "half a bee";
125
126 /* A fresh hash_map should be empty. */
127 ASSERT_EQ (0, m.elements ());
128 ASSERT_EQ (NULL, m.get (2));
129
130 /* Populate the hash_map. */
131 ASSERT_EQ (false, m.put (2, ostrich));
132 ASSERT_EQ (false, m.put (4, elephant));
133 ASSERT_EQ (false, m.put (6, ant));
134 ASSERT_EQ (false, m.put (8, spider));
135 ASSERT_EQ (false, m.put (750, millipede));
136 ASSERT_EQ (false, m.put (3, eric));
137
138 /* Verify that we can recover the stored values. */
139 ASSERT_EQ (6, m.elements ());
140 ASSERT_EQ (*m.get (2), ostrich);
141 ASSERT_EQ (*m.get (4), elephant);
142 ASSERT_EQ (*m.get (6), ant);
143 ASSERT_EQ (*m.get (8), spider);
144 ASSERT_EQ (*m.get (750), millipede);
145 ASSERT_EQ (*m.get (3), eric);
146}
147
148typedef class hash_map_test_val_t
149{
150public:
151 static int ndefault;
152 static int ncopy;
153 static int nassign;
154 static int ndtor;
155
156 hash_map_test_val_t ()
157 : ptr (&ptr)
158 {
159 ++ndefault;
160 }
161
162 hash_map_test_val_t (const hash_map_test_val_t &rhs)
163 : ptr (&ptr)
164 {
165 ++ncopy;
166 gcc_assert (rhs.ptr == &rhs.ptr);
167 }
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 ~hash_map_test_val_t ()
178 {
179 gcc_assert (ptr == &ptr);
180 ++ndtor;
181 }
182
183 void *ptr;
184} val_t;
185
186int val_t::ndefault;
187int val_t::ncopy;
188int val_t::nassign;
189int val_t::ndtor;
190
191static void
192test_map_of_type_with_ctor_and_dtor ()
193{
194 typedef hash_map <void *, val_t> Map;
195
196 {
197 /* Test default ctor. */
198 Map m;
199 (void)&m;
200 }
201
202 ASSERT_TRUE (val_t::ndefault == 0);
203 ASSERT_TRUE (val_t::ncopy == 0);
204 ASSERT_TRUE (val_t::nassign == 0);
205 ASSERT_TRUE (val_t::ndtor == 0);
206
207 {
208 /* Test single insertion. */
209 Map m;
210 void *p = &p;
211 m.get_or_insert (k: p);
212 }
213
214 ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
215
216 {
217 /* Test copy ctor. */
218 Map m1;
219 void *p = &p;
220 val_t &rv1 = m1.get_or_insert (k: p);
221
222 int ncopy = val_t::ncopy;
223 int nassign = val_t::nassign;
224
225 Map m2 (m1);
226 val_t *pv2 = m2.get (k: p);
227
228 ASSERT_TRUE (ncopy + 1 == val_t::ncopy);
229 ASSERT_TRUE (nassign == val_t::nassign);
230
231 ASSERT_TRUE (&rv1 != pv2);
232 }
233
234 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 {
261 Map m;
262 void *p = &p, *q = &q;
263 val_t &v1 = m.get_or_insert (k: p);
264 val_t &v2 = m.get_or_insert (k: q);
265
266 ASSERT_TRUE (v1.ptr == &v1.ptr && &v2.ptr == v2.ptr);
267 }
268
269 ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
270
271 {
272 Map m;
273 void *p = &p, *q = &q;
274 m.get_or_insert (k: p);
275 m.remove (k: p);
276 m.get_or_insert (k: q);
277 m.remove (k: q);
278
279 ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
280 }
281
282
283 /* Verify basic construction and destruction of Value objects. */
284 {
285 /* Configure, arbitrary. */
286 const size_t N_init = 0;
287 const int N_elem = 28;
288
289 void *a[N_elem];
290 for (size_t i = 0; i < N_elem; ++i)
291 a[i] = &a[i];
292
293 val_t::ndefault = 0;
294 val_t::ncopy = 0;
295 val_t::nassign = 0;
296 val_t::ndtor = 0;
297 Map m (N_init);
298 ASSERT_EQ (val_t::ndefault
299 + val_t::ncopy
300 + val_t::nassign
301 + val_t::ndtor, 0);
302
303 for (int i = 0; i < N_elem; ++i)
304 {
305 m.get_or_insert (k: a[i]);
306 ASSERT_EQ (val_t::ndefault, 1 + i);
307 ASSERT_EQ (val_t::ncopy, 0);
308 ASSERT_EQ (val_t::nassign, 0);
309 ASSERT_EQ (val_t::ndtor, i);
310
311 m.remove (k: a[i]);
312 ASSERT_EQ (val_t::ndefault, 1 + i);
313 ASSERT_EQ (val_t::ncopy, 0);
314 ASSERT_EQ (val_t::nassign, 0);
315 ASSERT_EQ (val_t::ndtor, 1 + i);
316 }
317 }
318}
319
320/* Verify aspects of 'hash_table::expand', in particular that it doesn't leak
321 Value objects. */
322
323static void
324test_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 const size_t N_init = 0;
328 const int N_elem = 70;
329 size_t expand_c_expected = 4;
330 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 int a[N_elem];
342 for (size_t i = 0; i < N_elem; ++i)
343 a[i] = i;
344
345 const int EMPTY = -1;
346 const int DELETED = -2;
347 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 size_t m_n_deleted = 0;
354
355 val_t::ndefault = 0;
356 val_t::ncopy = 0;
357 val_t::nassign = 0;
358 val_t::ndtor = 0;
359 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 size_t m_size;
367 {
368 unsigned int size_prime_index_ = hash_table_higher_prime_index (n: N_init);
369 m_size = prime_tab[size_prime_index_].prime;
370 }
371
372 int n_expand_moved = 0;
373
374 for (int i = 0; i < N_elem; ++i)
375 {
376 size_t elts = m.elements ();
377
378 /* Per 'hash_table::find_slot_with_hash'. */
379 size_t m_n_elements = elts + m_n_deleted;
380 bool expand = m_size * 3 <= m_n_elements * 4;
381
382 m.get_or_insert (k: a[i]);
383 if (expand)
384 {
385 ++expand_c;
386
387 /* Per 'hash_table::expand'. */
388 {
389 unsigned int nindex = hash_table_higher_prime_index (n: elts * 2);
390 m_size = prime_tab[nindex].prime;
391 }
392 m_n_deleted = 0;
393
394 /* All non-deleted elements have been moved. */
395 n_expand_moved += i;
396 if (remove_some_inline)
397 n_expand_moved -= (i + 2) / 3;
398 }
399
400 ASSERT_EQ (val_t::ndefault, 1 + i);
401 ASSERT_EQ (val_t::ncopy, n_expand_moved);
402 ASSERT_EQ (val_t::nassign, 0);
403 if (remove_some_inline)
404 ASSERT_EQ (val_t::ndtor, n_expand_moved + (i + 2) / 3);
405 else
406 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 if (remove_some_inline
411 && !(i % 3))
412 {
413 m.remove (k: a[i]);
414 /* Per 'hash_table::remove_elt_with_hash'. */
415 m_n_deleted++;
416
417 ASSERT_EQ (val_t::ndefault, 1 + i);
418 ASSERT_EQ (val_t::ncopy, n_expand_moved);
419 ASSERT_EQ (val_t::nassign, 0);
420 ASSERT_EQ (val_t::ndtor, n_expand_moved + 1 + (i + 2) / 3);
421 }
422 }
423 ASSERT_EQ (expand_c, expand_c_expected);
424
425 int ndefault = val_t::ndefault;
426 int ncopy = val_t::ncopy;
427 int nassign = val_t::nassign;
428 int ndtor = val_t::ndtor;
429
430 for (int i = 0; i < N_elem; ++i)
431 {
432 if (remove_some_inline
433 && !(i % 3))
434 continue;
435
436 m.remove (k: a[i]);
437 ++ndtor;
438 ASSERT_EQ (val_t::ndefault, ndefault);
439 ASSERT_EQ (val_t::ncopy, ncopy);
440 ASSERT_EQ (val_t::nassign, nassign);
441 ASSERT_EQ (val_t::ndtor, ndtor);
442 }
443 ASSERT_EQ (val_t::ndefault + val_t::ncopy, val_t::ndtor);
444}
445
446/* Test calling empty on a hash_map that has a key type with non-zero
447 "empty" value. */
448
449static void
450test_nonzero_empty_key ()
451{
452 typedef int_hash<int, INT_MIN, INT_MAX> IntHash;
453 hash_map<int, int, simple_hashmap_traits<IntHash, int> > x;
454
455 for (int i = 1; i != 32; ++i)
456 x.put (k: i, v: i);
457
458 ASSERT_EQ (x.get (0), NULL);
459 ASSERT_EQ (*x.get (1), 1);
460
461 x.empty ();
462
463 ASSERT_EQ (x.get (0), NULL);
464 ASSERT_EQ (x.get (1), NULL);
465}
466
467/* Run all of the selftests within this file. */
468
469void
470hash_map_tests_cc_tests ()
471{
472 test_map_of_strings_to_int ();
473 test_map_of_int_to_strings ();
474 test_map_of_type_with_ctor_and_dtor ();
475 test_map_of_type_with_ctor_and_dtor_expand (remove_some_inline: false);
476 test_map_of_type_with_ctor_and_dtor_expand (remove_some_inline: true);
477 test_nonzero_empty_key ();
478}
479
480} // namespace selftest
481
482#endif /* CHECKING_P */
483

source code of gcc/hash-map-tests.cc