Daily bump.
[official-gcc.git] / gcc / hash-map-tests.c
blob511d4342087e972f2b036b63afc67c1304b781ad
1 /* Unit tests for hash-map.h.
2 Copyright (C) 2015-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
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"
36 #if CHECKING_P
38 namespace selftest {
40 /* Construct a hash_map <const char *, int> and verify that
41 various operations work correctly. */
43 static void
44 test_map_of_strings_to_int ()
46 hash_map <const char *, int> m;
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";
55 /* A fresh hash_map should be empty. */
56 ASSERT_TRUE (m.is_empty ());
57 ASSERT_EQ (NULL, m.get (ostrich));
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));
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));
76 /* Verify removing an item. */
77 m.remove (eric);
78 ASSERT_EQ (5, m.elements ());
79 ASSERT_EQ (NULL, m.get (eric));
81 m.remove (eric);
82 ASSERT_EQ (5, m.elements ());
83 ASSERT_EQ (NULL, m.get (eric));
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 ());
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 ());
105 free (another_ant);
108 /* Construct a hash_map using int_hash and verify that
109 various operations work correctly. */
111 static void
112 test_map_of_int_to_strings ()
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;
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";
126 /* A fresh hash_map should be empty. */
127 ASSERT_EQ (0, m.elements ());
128 ASSERT_EQ (NULL, m.get (2));
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));
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);
148 typedef class hash_map_test_val_t
150 public:
151 static int ndefault;
152 static int ncopy;
153 static int nassign;
154 static int ndtor;
156 hash_map_test_val_t ()
157 : ptr (&ptr)
159 ++ndefault;
162 hash_map_test_val_t (const hash_map_test_val_t &rhs)
163 : ptr (&ptr)
165 ++ncopy;
166 gcc_assert (rhs.ptr == &rhs.ptr);
169 hash_map_test_val_t& operator= (const hash_map_test_val_t &rhs)
171 ++nassign;
172 gcc_assert (ptr == &ptr);
173 gcc_assert (rhs.ptr == &rhs.ptr);
174 return *this;
177 ~hash_map_test_val_t ()
179 gcc_assert (ptr == &ptr);
180 ++ndtor;
183 void *ptr;
184 } val_t;
186 int val_t::ndefault;
187 int val_t::ncopy;
188 int val_t::nassign;
189 int val_t::ndtor;
191 static void
192 test_map_of_type_with_ctor_and_dtor ()
194 typedef hash_map <void *, val_t> Map;
197 /* Test default ctor. */
198 Map m;
199 (void)&m;
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);
208 /* Test single insertion. */
209 Map m;
210 void *p = &p;
211 m.get_or_insert (p);
214 ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
217 /* Test copy ctor. */
218 Map m1;
219 void *p = &p;
220 val_t &rv1 = m1.get_or_insert (p);
222 int ncopy = val_t::ncopy;
223 int nassign = val_t::nassign;
225 Map m2 (m1);
226 val_t *pv2 = m2.get (p);
228 ASSERT_TRUE (ncopy + 1 == val_t::ncopy);
229 ASSERT_TRUE (nassign == val_t::nassign);
231 ASSERT_TRUE (&rv1 != pv2);
234 ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
236 #if 0 /* Avoid testing until bug 90959 is fixed. */
238 /* Test copy assignment into an empty map. */
239 Map m1;
240 void *p = &p;
241 val_t &rv1 = m1.get_or_insert (p);
243 int ncopy = val_t::ncopy;
244 int nassign = val_t::nassign;
246 Map m2;
247 m2 = m1;
248 val_t *pv2 = m2.get (p);
250 ASSERT_TRUE (ncopy == val_t::ncopy);
251 ASSERT_TRUE (nassign + 1 == val_t::nassign);
253 ASSERT_TRUE (&rv1 != pv2);
256 ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
258 #endif
261 Map m;
262 void *p = &p, *q = &q;
263 val_t &v1 = m.get_or_insert (p);
264 val_t &v2 = m.get_or_insert (q);
266 ASSERT_TRUE (v1.ptr == &v1.ptr && &v2.ptr == v2.ptr);
269 ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
272 Map m;
273 void *p = &p, *q = &q;
274 m.get_or_insert (p);
275 m.remove (p);
276 m.get_or_insert (q);
277 m.remove (q);
279 ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
283 /* Verify basic construction and destruction of Value objects. */
285 /* Configure, arbitrary. */
286 const size_t N_init = 0;
287 const int N_elem = 28;
289 void *a[N_elem];
290 for (size_t i = 0; i < N_elem; ++i)
291 a[i] = &a[i];
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);
303 for (int i = 0; i < N_elem; ++i)
305 m.get_or_insert (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);
311 m.remove (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);
320 /* Verify aspects of 'hash_table::expand', in particular that it doesn't leak
321 Value objects. */
323 static void
324 test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
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;
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'. */
341 int a[N_elem];
342 for (size_t i = 0; i < N_elem; ++i)
343 a[i] = i;
345 const int EMPTY = -1;
346 const int DELETED = -2;
347 typedef hash_map<int_hash<int, EMPTY, DELETED>, val_t> Map;
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;
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);
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. */
365 /* Per 'hash_table::hash_table'. */
366 size_t m_size;
368 unsigned int size_prime_index_ = hash_table_higher_prime_index (N_init);
369 m_size = prime_tab[size_prime_index_].prime;
372 int n_expand_moved = 0;
374 for (int i = 0; i < N_elem; ++i)
376 size_t elts = m.elements ();
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;
382 m.get_or_insert (a[i]);
383 if (expand)
385 ++expand_c;
387 /* Per 'hash_table::expand'. */
389 unsigned int nindex = hash_table_higher_prime_index (elts * 2);
390 m_size = prime_tab[nindex].prime;
392 m_n_deleted = 0;
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;
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);
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))
413 m.remove (a[i]);
414 /* Per 'hash_table::remove_elt_with_hash'. */
415 m_n_deleted++;
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);
423 ASSERT_EQ (expand_c, expand_c_expected);
425 int ndefault = val_t::ndefault;
426 int ncopy = val_t::ncopy;
427 int nassign = val_t::nassign;
428 int ndtor = val_t::ndtor;
430 for (int i = 0; i < N_elem; ++i)
432 if (remove_some_inline
433 && !(i % 3))
434 continue;
436 m.remove (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);
443 ASSERT_EQ (val_t::ndefault + val_t::ncopy, val_t::ndtor);
446 /* Test calling empty on a hash_map that has a key type with non-zero
447 "empty" value. */
449 static void
450 test_nonzero_empty_key ()
452 typedef int_hash<int, INT_MIN, INT_MAX> IntHash;
453 hash_map<int, int, simple_hashmap_traits<IntHash, int> > x;
455 for (int i = 1; i != 32; ++i)
456 x.put (i, i);
458 ASSERT_EQ (x.get (0), NULL);
459 ASSERT_EQ (*x.get (1), 1);
461 x.empty ();
463 ASSERT_EQ (x.get (0), NULL);
464 ASSERT_EQ (x.get (1), NULL);
467 /* Run all of the selftests within this file. */
469 void
470 hash_map_tests_c_tests ()
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 (false);
476 test_map_of_type_with_ctor_and_dtor_expand (true);
477 test_nonzero_empty_key ();
480 } // namespace selftest
482 #endif /* CHECKING_P */