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
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
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/>. */
22 #include "coretypes.h"
26 #include "fixed-value.h"
30 #include "tree-core.h"
31 #include "stor-layout.h"
33 #include "stringpool.h"
40 /* Construct a hash_map <const char *, int> and verify that
41 various operations work correctly. */
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. */
78 ASSERT_EQ (5, m
.elements ());
79 ASSERT_EQ (NULL
, m
.get (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));
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 ());
108 /* Construct a hash_map using int_hash and verify that
109 various operations work correctly. */
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
156 hash_map_test_val_t ()
162 hash_map_test_val_t (const hash_map_test_val_t
&rhs
)
166 gcc_assert (rhs
.ptr
== &rhs
.ptr
);
169 hash_map_test_val_t
& operator= (const hash_map_test_val_t
&rhs
)
172 gcc_assert (ptr
== &ptr
);
173 gcc_assert (rhs
.ptr
== &rhs
.ptr
);
177 ~hash_map_test_val_t ()
179 gcc_assert (ptr
== &ptr
);
192 test_map_of_type_with_ctor_and_dtor ()
194 typedef hash_map
<void *, val_t
> Map
;
197 /* Test default ctor. */
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. */
214 ASSERT_TRUE (val_t::ndefault
+ val_t::ncopy
== val_t::ndtor
);
217 /* Test copy ctor. */
220 val_t
&rv1
= m1
.get_or_insert (p
);
222 int ncopy
= val_t::ncopy
;
223 int nassign
= val_t::nassign
;
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. */
241 val_t
&rv1
= m1
.get_or_insert (p
);
243 int ncopy
= val_t::ncopy
;
244 int nassign
= val_t::nassign
;
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
);
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
);
273 void *p
= &p
, *q
= &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;
290 for (size_t i
= 0; i
< N_elem
; ++i
)
298 ASSERT_EQ (val_t::ndefault
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
);
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
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;
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
342 for (size_t i
= 0; i
< N_elem
; ++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;
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'. */
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
]);
387 /* Per 'hash_table::expand'. */
389 unsigned int nindex
= hash_table_higher_prime_index (elts
* 2);
390 m_size
= prime_tab
[nindex
].prime
;
394 /* All non-deleted elements have been moved. */
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);
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
414 /* Per 'hash_table::remove_elt_with_hash'. */
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
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
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
)
458 ASSERT_EQ (x
.get (0), NULL
);
459 ASSERT_EQ (*x
.get (1), 1);
463 ASSERT_EQ (x
.get (0), NULL
);
464 ASSERT_EQ (x
.get (1), NULL
);
467 /* Run all of the selftests within this file. */
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 */