| /* Unit tests for hash-map.h. | |
| Copyright (C) 2015-2026 Free Software Foundation, Inc. | |
| This file is part of GCC. | |
| GCC is free software; you can redistribute it and/or modify it under | |
| the terms of the GNU General Public License as published by the Free | |
| Software Foundation; either version 3, or (at your option) any later | |
| version. | |
| GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
| WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| for more details. | |
| You should have received a copy of the GNU General Public License | |
| along with GCC; see the file COPYING3. If not see | |
| <http://www.gnu.org/licenses/>. */ | |
| #include "config.h" | |
| #include "system.h" | |
| #include "coretypes.h" | |
| #include "tm.h" | |
| #include "opts.h" | |
| #include "hash-set.h" | |
| #include "fixed-value.h" | |
| #include "alias.h" | |
| #include "flags.h" | |
| #include "symtab.h" | |
| #include "tree-core.h" | |
| #include "stor-layout.h" | |
| #include "tree.h" | |
| #include "stringpool.h" | |
| #include "selftest.h" | |
| #if CHECKING_P | |
| namespace selftest { | |
| /* Construct a hash_map <const char *, int> and verify that | |
| various operations work correctly. */ | |
| static void | |
| test_map_of_strings_to_int () | |
| { | |
| hash_map <const char *, int> m; | |
| const char *ostrich = "ostrich"; | |
| const char *elephant = "elephant"; | |
| const char *ant = "ant"; | |
| const char *spider = "spider"; | |
| const char *millipede = "Illacme plenipes"; | |
| const char *eric = "half a bee"; | |
| /* A fresh hash_map should be empty. */ | |
| ASSERT_TRUE (m.is_empty ()); | |
| ASSERT_EQ (NULL, m.get (ostrich)); | |
| /* Populate the hash_map. */ | |
| ASSERT_EQ (false, m.put (ostrich, 2)); | |
| ASSERT_EQ (false, m.put (elephant, 4)); | |
| ASSERT_EQ (false, m.put (ant, 6)); | |
| ASSERT_EQ (false, m.put (spider, 8)); | |
| ASSERT_EQ (false, m.put (millipede, 750)); | |
| ASSERT_EQ (false, m.put (eric, 3)); | |
| /* Verify that we can recover the stored values. */ | |
| ASSERT_EQ (6, m.elements ()); | |
| ASSERT_EQ (2, *m.get (ostrich)); | |
| ASSERT_EQ (4, *m.get (elephant)); | |
| ASSERT_EQ (6, *m.get (ant)); | |
| ASSERT_EQ (8, *m.get (spider)); | |
| ASSERT_EQ (750, *m.get (millipede)); | |
| ASSERT_EQ (3, *m.get (eric)); | |
| /* Verify removing an item. */ | |
| m.remove (eric); | |
| ASSERT_EQ (5, m.elements ()); | |
| ASSERT_EQ (NULL, m.get (eric)); | |
| m.remove (eric); | |
| ASSERT_EQ (5, m.elements ()); | |
| ASSERT_EQ (NULL, m.get (eric)); | |
| /* A plain char * key is hashed based on its value (address), rather | |
| than the string it points to. */ | |
| char *another_ant = static_cast <char *> (xcalloc (4, 1)); | |
| another_ant[0] = 'a'; | |
| another_ant[1] = 'n'; | |
| another_ant[2] = 't'; | |
| another_ant[3] = 0; | |
| ASSERT_NE (ant, another_ant); | |
| unsigned prev_size = m.elements (); | |
| ASSERT_EQ (false, m.put (another_ant, 7)); | |
| ASSERT_EQ (prev_size + 1, m.elements ()); | |
| /* Need to use string_hash or nofree_string_hash key types to hash | |
| based on the string contents. */ | |
| hash_map <nofree_string_hash, int> string_map; | |
| ASSERT_EQ (false, string_map.put (ant, 1)); | |
| ASSERT_EQ (1, string_map.elements ()); | |
| ASSERT_EQ (true, string_map.put (another_ant, 5)); | |
| ASSERT_EQ (1, string_map.elements ()); | |
| free (another_ant); | |
| } | |
| /* Construct a hash_map using int_hash and verify that | |
| various operations work correctly. */ | |
| static void | |
| test_map_of_int_to_strings () | |
| { | |
| const int EMPTY = -1; | |
| const int DELETED = -2; | |
| typedef int_hash <int, EMPTY, DELETED> int_hash_t; | |
| hash_map <int_hash_t, const char *> m; | |
| const char *ostrich = "ostrich"; | |
| const char *elephant = "elephant"; | |
| const char *ant = "ant"; | |
| const char *spider = "spider"; | |
| const char *millipede = "Illacme plenipes"; | |
| const char *eric = "half a bee"; | |
| /* A fresh hash_map should be empty. */ | |
| ASSERT_EQ (0, m.elements ()); | |
| ASSERT_EQ (NULL, m.get (2)); | |
| /* Populate the hash_map. */ | |
| ASSERT_EQ (false, m.put (2, ostrich)); | |
| ASSERT_EQ (false, m.put (4, elephant)); | |
| ASSERT_EQ (false, m.put (6, ant)); | |
| ASSERT_EQ (false, m.put (8, spider)); | |
| ASSERT_EQ (false, m.put (750, millipede)); | |
| ASSERT_EQ (false, m.put (3, eric)); | |
| /* Verify that we can recover the stored values. */ | |
| ASSERT_EQ (6, m.elements ()); | |
| ASSERT_EQ (*m.get (2), ostrich); | |
| ASSERT_EQ (*m.get (4), elephant); | |
| ASSERT_EQ (*m.get (6), ant); | |
| ASSERT_EQ (*m.get (8), spider); | |
| ASSERT_EQ (*m.get (750), millipede); | |
| ASSERT_EQ (*m.get (3), eric); | |
| } | |
| typedef class hash_map_test_val_t | |
| { | |
| public: | |
| static int ndefault; | |
| static int ncopy; | |
| static int nassign; | |
| static int ndtor; | |
| hash_map_test_val_t () | |
| : ptr (&ptr) | |
| { | |
| ++ndefault; | |
| } | |
| hash_map_test_val_t (const hash_map_test_val_t &rhs) | |
| : ptr (&ptr) | |
| { | |
| ++ncopy; | |
| gcc_assert (rhs.ptr == &rhs.ptr); | |
| } | |
| hash_map_test_val_t& operator= (const hash_map_test_val_t &rhs) | |
| { | |
| ++nassign; | |
| gcc_assert (ptr == &ptr); | |
| gcc_assert (rhs.ptr == &rhs.ptr); | |
| return *this; | |
| } | |
| ~hash_map_test_val_t () | |
| { | |
| gcc_assert (ptr == &ptr); | |
| ++ndtor; | |
| } | |
| void *ptr; | |
| } val_t; | |
| int val_t::ndefault; | |
| int val_t::ncopy; | |
| int val_t::nassign; | |
| int val_t::ndtor; | |
| static void | |
| test_map_of_type_with_ctor_and_dtor () | |
| { | |
| typedef hash_map <void *, val_t> Map; | |
| { | |
| /* Test default ctor. */ | |
| Map m; | |
| (void)&m; | |
| } | |
| ASSERT_TRUE (val_t::ndefault == 0); | |
| ASSERT_TRUE (val_t::ncopy == 0); | |
| ASSERT_TRUE (val_t::nassign == 0); | |
| ASSERT_TRUE (val_t::ndtor == 0); | |
| { | |
| /* Test single insertion. */ | |
| Map m; | |
| void *p = &p; | |
| m.get_or_insert (p); | |
| } | |
| ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor); | |
| { | |
| /* Test copy ctor. */ | |
| Map m1; | |
| void *p = &p; | |
| val_t &rv1 = m1.get_or_insert (p); | |
| int ncopy = val_t::ncopy; | |
| int nassign = val_t::nassign; | |
| Map m2 (m1); | |
| val_t *pv2 = m2.get (p); | |
| ASSERT_TRUE (ncopy + 1 == val_t::ncopy); | |
| ASSERT_TRUE (nassign == val_t::nassign); | |
| ASSERT_TRUE (&rv1 != pv2); | |
| } | |
| ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor); | |
| #if 0 /* Avoid testing until bug 90959 is fixed. */ | |
| { | |
| /* Test copy assignment into an empty map. */ | |
| Map m1; | |
| void *p = &p; | |
| val_t &rv1 = m1.get_or_insert (p); | |
| int ncopy = val_t::ncopy; | |
| int nassign = val_t::nassign; | |
| Map m2; | |
| m2 = m1; | |
| val_t *pv2 = m2.get (p); | |
| ASSERT_TRUE (ncopy == val_t::ncopy); | |
| ASSERT_TRUE (nassign + 1 == val_t::nassign); | |
| ASSERT_TRUE (&rv1 != pv2); | |
| } | |
| ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor); | |
| #endif | |
| { | |
| Map m; | |
| void *p = &p, *q = &q; | |
| val_t &v1 = m.get_or_insert (p); | |
| val_t &v2 = m.get_or_insert (q); | |
| ASSERT_TRUE (v1.ptr == &v1.ptr && &v2.ptr == v2.ptr); | |
| } | |
| ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor); | |
| { | |
| Map m; | |
| void *p = &p, *q = &q; | |
| m.get_or_insert (p); | |
| m.remove (p); | |
| m.get_or_insert (q); | |
| m.remove (q); | |
| ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor); | |
| } | |
| /* Verify basic construction and destruction of Value objects. */ | |
| { | |
| /* Configure, arbitrary. */ | |
| const size_t N_init = 0; | |
| const int N_elem = 28; | |
| void *a[N_elem]; | |
| for (size_t i = 0; i < N_elem; ++i) | |
| a[i] = &a[i]; | |
| val_t::ndefault = 0; | |
| val_t::ncopy = 0; | |
| val_t::nassign = 0; | |
| val_t::ndtor = 0; | |
| Map m (N_init); | |
| ASSERT_EQ (val_t::ndefault | |
| + val_t::ncopy | |
| + val_t::nassign | |
| + val_t::ndtor, 0); | |
| for (int i = 0; i < N_elem; ++i) | |
| { | |
| m.get_or_insert (a[i]); | |
| ASSERT_EQ (val_t::ndefault, 1 + i); | |
| ASSERT_EQ (val_t::ncopy, 0); | |
| ASSERT_EQ (val_t::nassign, 0); | |
| ASSERT_EQ (val_t::ndtor, i); | |
| m.remove (a[i]); | |
| ASSERT_EQ (val_t::ndefault, 1 + i); | |
| ASSERT_EQ (val_t::ncopy, 0); | |
| ASSERT_EQ (val_t::nassign, 0); | |
| ASSERT_EQ (val_t::ndtor, 1 + i); | |
| } | |
| } | |
| } | |
| /* Verify aspects of 'hash_table::expand', in particular that it doesn't leak | |
| Value objects. */ | |
| static void | |
| test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline) | |
| { | |
| /* Configure, so that hash table expansion triggers a few times. */ | |
| const size_t N_init = 0; | |
| const int N_elem = 70; | |
| size_t expand_c_expected = 4; | |
| size_t expand_c = 0; | |
| /* For stability of this testing, we need all Key values 'k' to produce | |
| unique hash values 'Traits::hash (k)', as otherwise the dynamic | |
| insert/remove behavior may diverge across different architectures. This | |
| is, for example, a problem when using the standard 'pointer_hash::hash', | |
| which is simply doing a 'k >> 3' operation, which is fine on 64-bit | |
| architectures, but on 32-bit architectures produces the same hash value | |
| for subsequent 'a[i] = &a[i]' array elements. Therefore, use an | |
| 'int_hash'. */ | |
| int a[N_elem]; | |
| for (size_t i = 0; i < N_elem; ++i) | |
| a[i] = i; | |
| const int EMPTY = -1; | |
| const int DELETED = -2; | |
| typedef hash_map<int_hash<int, EMPTY, DELETED>, val_t> Map; | |
| /* Note that we are starting with a fresh 'Map'. Even if an existing one has | |
| been cleared out completely, there remain 'deleted' elements, and these | |
| would disturb the following logic, where we don't have access to the | |
| actual 'm_n_deleted' value. */ | |
| size_t m_n_deleted = 0; | |
| val_t::ndefault = 0; | |
| val_t::ncopy = 0; | |
| val_t::nassign = 0; | |
| val_t::ndtor = 0; | |
| Map m (N_init); | |
| /* In the following, in particular related to 'expand', we're adapting from | |
| the internal logic of 'hash_table', glossing over "some details" not | |
| relevant for this testing here. */ | |
| /* Per 'hash_table::hash_table'. */ | |
| size_t m_size; | |
| { | |
| unsigned int size_prime_index_ = hash_table_higher_prime_index (N_init); | |
| m_size = prime_tab[size_prime_index_].prime; | |
| } | |
| int n_expand_moved = 0; | |
| for (int i = 0; i < N_elem; ++i) | |
| { | |
| size_t elts = m.elements (); | |
| /* Per 'hash_table::find_slot_with_hash'. */ | |
| size_t m_n_elements = elts + m_n_deleted; | |
| bool expand = m_size * 3 <= m_n_elements * 4; | |
| m.get_or_insert (a[i]); | |
| if (expand) | |
| { | |
| ++expand_c; | |
| /* Per 'hash_table::expand'. */ | |
| { | |
| unsigned int nindex = hash_table_higher_prime_index (elts * 2); | |
| m_size = prime_tab[nindex].prime; | |
| } | |
| m_n_deleted = 0; | |
| /* All non-deleted elements have been moved. */ | |
| n_expand_moved += i; | |
| if (remove_some_inline) | |
| n_expand_moved -= (i + 2) / 3; | |
| } | |
| ASSERT_EQ (val_t::ndefault, 1 + i); | |
| ASSERT_EQ (val_t::ncopy, n_expand_moved); | |
| ASSERT_EQ (val_t::nassign, 0); | |
| if (remove_some_inline) | |
| ASSERT_EQ (val_t::ndtor, n_expand_moved + (i + 2) / 3); | |
| else | |
| ASSERT_EQ (val_t::ndtor, n_expand_moved); | |
| /* Remove some inline. This never triggers an 'expand' here, but via | |
| 'm_n_deleted' does influence any following one. */ | |
| if (remove_some_inline | |
| && !(i % 3)) | |
| { | |
| m.remove (a[i]); | |
| /* Per 'hash_table::remove_elt_with_hash'. */ | |
| m_n_deleted++; | |
| ASSERT_EQ (val_t::ndefault, 1 + i); | |
| ASSERT_EQ (val_t::ncopy, n_expand_moved); | |
| ASSERT_EQ (val_t::nassign, 0); | |
| ASSERT_EQ (val_t::ndtor, n_expand_moved + 1 + (i + 2) / 3); | |
| } | |
| } | |
| ASSERT_EQ (expand_c, expand_c_expected); | |
| int ndefault = val_t::ndefault; | |
| int ncopy = val_t::ncopy; | |
| int nassign = val_t::nassign; | |
| int ndtor = val_t::ndtor; | |
| for (int i = 0; i < N_elem; ++i) | |
| { | |
| if (remove_some_inline | |
| && !(i % 3)) | |
| continue; | |
| m.remove (a[i]); | |
| ++ndtor; | |
| ASSERT_EQ (val_t::ndefault, ndefault); | |
| ASSERT_EQ (val_t::ncopy, ncopy); | |
| ASSERT_EQ (val_t::nassign, nassign); | |
| ASSERT_EQ (val_t::ndtor, ndtor); | |
| } | |
| ASSERT_EQ (val_t::ndefault + val_t::ncopy, val_t::ndtor); | |
| } | |
| /* Test calling empty on a hash_map that has a key type with non-zero | |
| "empty" value. */ | |
| static void | |
| test_nonzero_empty_key () | |
| { | |
| typedef int_hash<int, INT_MIN, INT_MAX> IntHash; | |
| hash_map<int, int, simple_hashmap_traits<IntHash, int> > x; | |
| for (int i = 1; i != 32; ++i) | |
| x.put (i, i); | |
| ASSERT_EQ (x.get (0), NULL); | |
| ASSERT_EQ (*x.get (1), 1); | |
| x.empty (); | |
| ASSERT_EQ (x.get (0), NULL); | |
| ASSERT_EQ (x.get (1), NULL); | |
| } | |
| /* Run all of the selftests within this file. */ | |
| void | |
| hash_map_tests_cc_tests () | |
| { | |
| test_map_of_strings_to_int (); | |
| test_map_of_int_to_strings (); | |
| test_map_of_type_with_ctor_and_dtor (); | |
| test_map_of_type_with_ctor_and_dtor_expand (false); | |
| test_map_of_type_with_ctor_and_dtor_expand (true); | |
| test_nonzero_empty_key (); | |
| } | |
| } // namespace selftest | |
| #endif /* CHECKING_P */ |