1 /* Unit tests for ordered-hash-map.h.
2 Copyright (C) 2015-2020 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
get_kv_pairs(const HashMap & m,auto_vec<std::pair<Key,Value>> * out_kvs)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
test_map_of_strings_to_int()58 test_map_of_strings_to_int ()
59 {
60 ordered_hash_map <const char *, int> m;
61
62 const char *ostrich = "ostrich";
63 const char *elephant = "elephant";
64 const char *ant = "ant";
65 const char *spider = "spider";
66 const char *millipede = "Illacme plenipes";
67 const char *eric = "half a bee";
68
69 /* A fresh hash_map should be empty. */
70 ASSERT_EQ (0, m.elements ());
71 ASSERT_EQ (NULL, m.get (ostrich));
72
73 /* Populate the hash_map. */
74 ASSERT_EQ (false, m.put (ostrich, 2));
75 ASSERT_EQ (false, m.put (elephant, 4));
76 ASSERT_EQ (false, m.put (ant, 6));
77 ASSERT_EQ (false, m.put (spider, 8));
78 ASSERT_EQ (false, m.put (millipede, 750));
79 ASSERT_EQ (false, m.put (eric, 3));
80
81 /* Verify that we can recover the stored values. */
82 ASSERT_EQ (6, m.elements ());
83 ASSERT_EQ (2, *m.get (ostrich));
84 ASSERT_EQ (4, *m.get (elephant));
85 ASSERT_EQ (6, *m.get (ant));
86 ASSERT_EQ (8, *m.get (spider));
87 ASSERT_EQ (750, *m.get (millipede));
88 ASSERT_EQ (3, *m.get (eric));
89
90 /* Verify that the order of insertion is preserved. */
91 auto_vec<std::pair<const char *, int> > kvs;
92 get_kv_pairs (m, &kvs);
93 ASSERT_EQ (kvs.length (), 6);
94 ASSERT_EQ (kvs[0].first, ostrich);
95 ASSERT_EQ (kvs[0].second, 2);
96 ASSERT_EQ (kvs[1].first, elephant);
97 ASSERT_EQ (kvs[1].second, 4);
98 ASSERT_EQ (kvs[2].first, ant);
99 ASSERT_EQ (kvs[2].second, 6);
100 ASSERT_EQ (kvs[3].first, spider);
101 ASSERT_EQ (kvs[3].second, 8);
102 ASSERT_EQ (kvs[4].first, millipede);
103 ASSERT_EQ (kvs[4].second, 750);
104 ASSERT_EQ (kvs[5].first, eric);
105 ASSERT_EQ (kvs[5].second, 3);
106 }
107
108 /* Construct an ordered_hash_map using int_hash and verify that various
109 operations work correctly. */
110
111 static void
test_map_of_int_to_strings()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 ordered_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 /* Verify that the order of insertion is preserved. */
148 auto_vec<std::pair<int, const char *> > kvs;
149 get_kv_pairs (m, &kvs);
150 ASSERT_EQ (kvs.length (), 6);
151 ASSERT_EQ (kvs[0].first, 2);
152 ASSERT_EQ (kvs[0].second, ostrich);
153 ASSERT_EQ (kvs[1].first, 4);
154 ASSERT_EQ (kvs[1].second, elephant);
155 ASSERT_EQ (kvs[2].first, 6);
156 ASSERT_EQ (kvs[2].second, ant);
157 ASSERT_EQ (kvs[3].first, 8);
158 ASSERT_EQ (kvs[3].second, spider);
159 ASSERT_EQ (kvs[4].first, 750);
160 ASSERT_EQ (kvs[4].second, millipede);
161 ASSERT_EQ (kvs[5].first, 3);
162 ASSERT_EQ (kvs[5].second, eric);
163 }
164
165 /* Verify that we can remove items from an ordered_hash_map. */
166
167 static void
test_removal()168 test_removal ()
169 {
170 ordered_hash_map <const char *, int> m;
171
172 const char *ostrich = "ostrich";
173 ASSERT_EQ (false, m.put (ostrich, 2));
174
175 ASSERT_EQ (1, m.elements ());
176 ASSERT_EQ (2, *m.get (ostrich));
177
178 {
179 auto_vec<std::pair<const char *, int> > kvs;
180 get_kv_pairs (m, &kvs);
181 ASSERT_EQ (kvs.length (), 1);
182 ASSERT_EQ (kvs[0].first, ostrich);
183 ASSERT_EQ (kvs[0].second, 2);
184 }
185
186 m.remove (ostrich);
187
188 ASSERT_EQ (0, m.elements ());
189 {
190 auto_vec<std::pair<const char *, int> > kvs;
191 get_kv_pairs (m, &kvs);
192 ASSERT_EQ (kvs.length (), 0);
193 }
194
195 /* Reinsertion (with a different value). */
196 ASSERT_EQ (false, m.put (ostrich, 42));
197 ASSERT_EQ (1, m.elements ());
198 ASSERT_EQ (42, *m.get (ostrich));
199 {
200 auto_vec<std::pair<const char *, int> > kvs;
201 get_kv_pairs (m, &kvs);
202 ASSERT_EQ (kvs.length (), 1);
203 ASSERT_EQ (kvs[0].first, ostrich);
204 ASSERT_EQ (kvs[0].second, 42);
205 }
206 }
207
208 /* Verify that ordered_hash_map's copy-ctor works. */
209
210 static void
test_copy_ctor()211 test_copy_ctor ()
212 {
213 ordered_hash_map <const char *, int> m;
214
215 const char *ostrich = "ostrich";
216 ASSERT_EQ (false, m.put (ostrich, 2));
217
218 ASSERT_EQ (1, m.elements ());
219 ASSERT_EQ (2, *m.get (ostrich));
220
221 ordered_hash_map <const char *, int> copy (m);
222 ASSERT_EQ (1, copy.elements ());
223 ASSERT_EQ (2, *copy.get (ostrich));
224
225 /* Remove from source. */
226 m.remove (ostrich);
227 ASSERT_EQ (0, m.elements ());
228
229 /* Copy should be unaffected. */
230 ASSERT_EQ (1, copy.elements ());
231 ASSERT_EQ (2, *copy.get (ostrich));
232 }
233
234 /* Run all of the selftests within this file. */
235
236 void
ordered_hash_map_tests_cc_tests()237 ordered_hash_map_tests_cc_tests ()
238 {
239 test_map_of_strings_to_int ();
240 test_map_of_int_to_strings ();
241 test_removal ();
242 test_copy_ctor ();
243 }
244
245 } // namespace selftest
246
247 #endif /* CHECKING_P */
248