1 | /* Unit tests for ordered-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 "ordered-hash-map.h" |
35 | #include "selftest.h" |
36 | |
37 | #if CHECKING_P |
38 | |
39 | namespace selftest { |
40 | |
41 | /* Populate *OUT_KVS with the key/value pairs of M. */ |
42 | |
43 | template <typename HashMap, typename Key, typename Value> |
44 | static void |
45 | get_kv_pairs (const HashMap &m, |
46 | auto_vec<std::pair<Key, Value> > *out_kvs) |
47 | { |
48 | for (typename HashMap::iterator iter = m.begin (); |
49 | iter != m.end (); |
50 | ++iter) |
51 | out_kvs->safe_push (std::make_pair ((*iter).first, (*iter).second)); |
52 | } |
53 | |
54 | /* Construct an ordered_hash_map <const char *, int> and verify that |
55 | various operations work correctly. */ |
56 | |
57 | static void |
58 | test_map_of_strings_to_int () |
59 | { |
60 | ordered_hash_map <const char *, int> m; |
61 | bool existed; |
62 | |
63 | const char *ostrich = "ostrich" ; |
64 | const char *elephant = "elephant" ; |
65 | const char *ant = "ant" ; |
66 | const char *spider = "spider" ; |
67 | const char *millipede = "Illacme plenipes" ; |
68 | const char *eric = "half a bee" ; |
69 | |
70 | /* A fresh hash_map should be empty. */ |
71 | ASSERT_EQ (0, m.elements ()); |
72 | ASSERT_EQ (NULL, m.get (ostrich)); |
73 | |
74 | /* Populate the hash_map. */ |
75 | ASSERT_EQ (false, m.put (ostrich, 2)); |
76 | ASSERT_EQ (false, m.put (elephant, 4)); |
77 | ASSERT_EQ (false, m.put (ant, 6)); |
78 | existed = true; |
79 | int &value = m.get_or_insert (k: spider, existed: &existed); |
80 | value = 8; |
81 | ASSERT_EQ (false, existed); |
82 | ASSERT_EQ (false, m.put (millipede, 750)); |
83 | ASSERT_EQ (false, m.put (eric, 3)); |
84 | |
85 | |
86 | /* Verify that we can recover the stored values. */ |
87 | ASSERT_EQ (6, m.elements ()); |
88 | ASSERT_EQ (2, *m.get (ostrich)); |
89 | ASSERT_EQ (4, *m.get (elephant)); |
90 | ASSERT_EQ (6, *m.get (ant)); |
91 | ASSERT_EQ (8, *m.get (spider)); |
92 | existed = false; |
93 | ASSERT_EQ (750, m.get_or_insert (millipede, &existed)); |
94 | ASSERT_EQ (true, existed); |
95 | ASSERT_EQ (3, *m.get (eric)); |
96 | |
97 | /* Verify that the order of insertion is preserved. */ |
98 | auto_vec<std::pair<const char *, int> > kvs; |
99 | get_kv_pairs (m, out_kvs: &kvs); |
100 | ASSERT_EQ (kvs.length (), 6); |
101 | ASSERT_EQ (kvs[0].first, ostrich); |
102 | ASSERT_EQ (kvs[0].second, 2); |
103 | ASSERT_EQ (kvs[1].first, elephant); |
104 | ASSERT_EQ (kvs[1].second, 4); |
105 | ASSERT_EQ (kvs[2].first, ant); |
106 | ASSERT_EQ (kvs[2].second, 6); |
107 | ASSERT_EQ (kvs[3].first, spider); |
108 | ASSERT_EQ (kvs[3].second, 8); |
109 | ASSERT_EQ (kvs[4].first, millipede); |
110 | ASSERT_EQ (kvs[4].second, 750); |
111 | ASSERT_EQ (kvs[5].first, eric); |
112 | ASSERT_EQ (kvs[5].second, 3); |
113 | } |
114 | |
115 | /* Construct an ordered_hash_map using int_hash and verify that various |
116 | operations work correctly. */ |
117 | |
118 | static void |
119 | test_map_of_int_to_strings () |
120 | { |
121 | const int EMPTY = -1; |
122 | const int DELETED = -2; |
123 | bool existed; |
124 | typedef int_hash <int, EMPTY, DELETED> int_hash_t; |
125 | ordered_hash_map <int_hash_t, const char *> m; |
126 | |
127 | const char *ostrich = "ostrich" ; |
128 | const char *elephant = "elephant" ; |
129 | const char *ant = "ant" ; |
130 | const char *spider = "spider" ; |
131 | const char *millipede = "Illacme plenipes" ; |
132 | const char *eric = "half a bee" ; |
133 | |
134 | /* A fresh hash_map should be empty. */ |
135 | ASSERT_EQ (0, m.elements ()); |
136 | ASSERT_EQ (NULL, m.get (2)); |
137 | |
138 | /* Populate the hash_map. */ |
139 | ASSERT_EQ (false, m.put (2, ostrich)); |
140 | ASSERT_EQ (false, m.put (4, elephant)); |
141 | ASSERT_EQ (false, m.put (6, ant)); |
142 | const char* &value = m.get_or_insert (k: 8, existed: &existed); |
143 | value = spider; |
144 | ASSERT_EQ (false, existed); |
145 | ASSERT_EQ (false, m.put (750, millipede)); |
146 | ASSERT_EQ (false, m.put (3, eric)); |
147 | |
148 | /* Verify that we can recover the stored values. */ |
149 | ASSERT_EQ (6, m.elements ()); |
150 | ASSERT_EQ (*m.get (2), ostrich); |
151 | ASSERT_EQ (*m.get (4), elephant); |
152 | ASSERT_EQ (*m.get (6), ant); |
153 | ASSERT_EQ (*m.get (8), spider); |
154 | ASSERT_EQ (m.get_or_insert (750, &existed), millipede); |
155 | ASSERT_EQ (existed, true); |
156 | ASSERT_EQ (*m.get (3), eric); |
157 | |
158 | /* Verify that the order of insertion is preserved. */ |
159 | auto_vec<std::pair<int, const char *> > kvs; |
160 | get_kv_pairs (m, out_kvs: &kvs); |
161 | ASSERT_EQ (kvs.length (), 6); |
162 | ASSERT_EQ (kvs[0].first, 2); |
163 | ASSERT_EQ (kvs[0].second, ostrich); |
164 | ASSERT_EQ (kvs[1].first, 4); |
165 | ASSERT_EQ (kvs[1].second, elephant); |
166 | ASSERT_EQ (kvs[2].first, 6); |
167 | ASSERT_EQ (kvs[2].second, ant); |
168 | ASSERT_EQ (kvs[3].first, 8); |
169 | ASSERT_EQ (kvs[3].second, spider); |
170 | ASSERT_EQ (kvs[4].first, 750); |
171 | ASSERT_EQ (kvs[4].second, millipede); |
172 | ASSERT_EQ (kvs[5].first, 3); |
173 | ASSERT_EQ (kvs[5].second, eric); |
174 | } |
175 | |
176 | /* Verify that we can remove items from an ordered_hash_map. */ |
177 | |
178 | static void |
179 | test_removal () |
180 | { |
181 | ordered_hash_map <const char *, int> m; |
182 | |
183 | const char *ostrich = "ostrich" ; |
184 | ASSERT_EQ (false, m.put (ostrich, 2)); |
185 | |
186 | ASSERT_EQ (1, m.elements ()); |
187 | ASSERT_EQ (2, *m.get (ostrich)); |
188 | |
189 | { |
190 | auto_vec<std::pair<const char *, int> > kvs; |
191 | get_kv_pairs (m, out_kvs: &kvs); |
192 | ASSERT_EQ (kvs.length (), 1); |
193 | ASSERT_EQ (kvs[0].first, ostrich); |
194 | ASSERT_EQ (kvs[0].second, 2); |
195 | } |
196 | |
197 | m.remove (k: ostrich); |
198 | |
199 | ASSERT_EQ (0, m.elements ()); |
200 | { |
201 | auto_vec<std::pair<const char *, int> > kvs; |
202 | get_kv_pairs (m, out_kvs: &kvs); |
203 | ASSERT_EQ (kvs.length (), 0); |
204 | } |
205 | |
206 | /* Reinsertion (with a different value). */ |
207 | ASSERT_EQ (false, m.put (ostrich, 42)); |
208 | ASSERT_EQ (1, m.elements ()); |
209 | ASSERT_EQ (42, *m.get (ostrich)); |
210 | { |
211 | auto_vec<std::pair<const char *, int> > kvs; |
212 | get_kv_pairs (m, out_kvs: &kvs); |
213 | ASSERT_EQ (kvs.length (), 1); |
214 | ASSERT_EQ (kvs[0].first, ostrich); |
215 | ASSERT_EQ (kvs[0].second, 42); |
216 | } |
217 | } |
218 | |
219 | /* Verify that ordered_hash_map's copy-ctor works. */ |
220 | |
221 | static void |
222 | test_copy_ctor () |
223 | { |
224 | ordered_hash_map <const char *, int> m; |
225 | |
226 | const char *ostrich = "ostrich" ; |
227 | ASSERT_EQ (false, m.put (ostrich, 2)); |
228 | |
229 | ASSERT_EQ (1, m.elements ()); |
230 | ASSERT_EQ (2, *m.get (ostrich)); |
231 | |
232 | ordered_hash_map <const char *, int> copy (m); |
233 | ASSERT_EQ (1, copy.elements ()); |
234 | ASSERT_EQ (2, *copy.get (ostrich)); |
235 | |
236 | /* Remove from source. */ |
237 | m.remove (k: ostrich); |
238 | ASSERT_EQ (0, m.elements ()); |
239 | |
240 | /* Copy should be unaffected. */ |
241 | ASSERT_EQ (1, copy.elements ()); |
242 | ASSERT_EQ (2, *copy.get (ostrich)); |
243 | } |
244 | |
245 | /* Run all of the selftests within this file. */ |
246 | |
247 | void |
248 | ordered_hash_map_tests_cc_tests () |
249 | { |
250 | test_map_of_strings_to_int (); |
251 | test_map_of_int_to_strings (); |
252 | test_removal (); |
253 | test_copy_ctor (); |
254 | } |
255 | |
256 | } // namespace selftest |
257 | |
258 | #endif /* CHECKING_P */ |
259 | |