1 | /* Unit tests for hash-map.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 "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 | test_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 | |
111 | static void |
112 | test_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 | |
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 | 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 | |
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 | test_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 | |
323 | static void |
324 | 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 | 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 | |
449 | static void |
450 | test_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 | |
469 | void |
470 | hash_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 | |