]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | |
2 | // Copyright 2006-2009 Daniel James. | |
3 | // Distributed under the Boost Software License, Version 1.0. (See accompanying | |
4 | // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
7c673cae | 5 | #include "./containers.hpp" |
b32b8144 FG |
6 | |
7 | #include "../helpers/helpers.hpp" | |
7c673cae | 8 | #include "../helpers/invariants.hpp" |
b32b8144 | 9 | #include "../helpers/random_values.hpp" |
7c673cae | 10 | #include "../helpers/strong.hpp" |
b32b8144 | 11 | #include "../helpers/tracker.hpp" |
7c673cae | 12 | #include <cmath> |
b32b8144 | 13 | #include <string> |
7c673cae FG |
14 | |
15 | test::seed_t initialize_seed(747373); | |
16 | ||
b32b8144 FG |
17 | // Fill in a container so that it's about to rehash |
18 | template <typename T> void rehash_prep(T& x) | |
7c673cae | 19 | { |
b32b8144 FG |
20 | using namespace std; |
21 | typedef BOOST_DEDUCED_TYPENAME T::size_type size_type; | |
22 | ||
23 | x.max_load_factor(0.25); | |
24 | size_type bucket_count = x.bucket_count(); | |
25 | size_type initial_elements = static_cast<size_type>( | |
26 | ceil((double)bucket_count * (double)x.max_load_factor()) - 1); | |
27 | test::random_values<T> v(initial_elements); | |
28 | x.insert(v.begin(), v.end()); | |
29 | BOOST_TEST(bucket_count == x.bucket_count()); | |
30 | } | |
31 | ||
32 | // Overload to generate inserters that need type information. | |
33 | ||
34 | template <typename Inserter, typename T> | |
35 | Inserter generate(Inserter inserter, T&) | |
36 | { | |
37 | return inserter; | |
38 | } | |
7c673cae | 39 | |
b32b8144 | 40 | // Get the iterator returned from an insert/emplace. |
7c673cae | 41 | |
b32b8144 | 42 | template <typename T> T get_iterator(T const& x) { return x; } |
7c673cae | 43 | |
b32b8144 FG |
44 | template <typename T> T get_iterator(std::pair<T, bool> const& x) |
45 | { | |
46 | return x.first; | |
47 | } | |
7c673cae | 48 | |
b32b8144 | 49 | // Generic insert exception test for typical single element inserts.. |
7c673cae | 50 | |
b32b8144 FG |
51 | template <typename T, typename Inserter, typename Values> |
52 | void insert_exception_test_impl(T x, Inserter insert, Values const& v) | |
7c673cae | 53 | { |
b32b8144 | 54 | test::strong<T> strong; |
7c673cae | 55 | |
b32b8144 FG |
56 | test::ordered<T> tracker; |
57 | tracker.insert(x.begin(), x.end()); | |
58 | ||
59 | try { | |
60 | ENABLE_EXCEPTIONS; | |
61 | ||
62 | for (typename Values::const_iterator it = v.begin(); it != v.end(); ++it) { | |
63 | strong.store(x, test::detail::tracker.count_allocations); | |
64 | insert(x, it); | |
7c673cae | 65 | } |
b32b8144 FG |
66 | } catch (...) { |
67 | test::check_equivalent_keys(x); | |
68 | insert.exception_check(x, strong); | |
69 | throw; | |
70 | } | |
71 | ||
72 | test::check_equivalent_keys(x); | |
73 | insert.track(tracker, v.begin(), v.end()); | |
74 | tracker.compare(x); | |
75 | } | |
7c673cae | 76 | |
b32b8144 | 77 | // Simple insert exception test |
7c673cae | 78 | |
b32b8144 FG |
79 | template <typename T, typename Inserter> |
80 | void insert_exception_test(T*, Inserter insert, test::random_generator gen) | |
7c673cae | 81 | { |
b32b8144 FG |
82 | for (int i = 0; i < 5; ++i) { |
83 | test::random_values<T> v(10, gen); | |
84 | T x; | |
7c673cae | 85 | |
b32b8144 FG |
86 | EXCEPTION_LOOP(insert_exception_test_impl(x, generate(insert, x), v)); |
87 | } | |
88 | } | |
7c673cae | 89 | |
b32b8144 FG |
90 | // Insert into a container which is about to hit its max load, so that it |
91 | // rehashes. | |
92 | ||
93 | template <typename T, typename Inserter> | |
94 | void insert_rehash_exception_test( | |
95 | T*, Inserter insert, test::random_generator gen) | |
7c673cae | 96 | { |
b32b8144 FG |
97 | for (int i = 0; i < 5; ++i) { |
98 | T x; | |
99 | rehash_prep(x); | |
7c673cae | 100 | |
b32b8144 FG |
101 | test::random_values<T> v2(5, gen); |
102 | EXCEPTION_LOOP(insert_exception_test_impl(x, generate(insert, x), v2)); | |
103 | } | |
104 | } | |
7c673cae | 105 | |
b32b8144 | 106 | // Various methods for inserting a single element |
7c673cae | 107 | |
b32b8144 FG |
108 | struct inserter_base |
109 | { | |
110 | template <typename T> void exception_check(T& x, test::strong<T>& strong) | |
111 | { | |
112 | std::string scope(test::scope); | |
113 | ||
114 | if (scope.find("hash::operator()") == std::string::npos) | |
115 | strong.test(x, test::detail::tracker.count_allocations); | |
116 | } | |
117 | ||
118 | template <typename T, typename Iterator> | |
119 | void track(T& tracker, Iterator begin, Iterator end) | |
120 | { | |
121 | tracker.insert(begin, end); | |
122 | } | |
7c673cae FG |
123 | }; |
124 | ||
b32b8144 | 125 | struct insert_lvalue_type : inserter_base |
7c673cae | 126 | { |
b32b8144 FG |
127 | template <typename T, typename Iterator> void operator()(T& x, Iterator it) |
128 | { | |
129 | x.insert(*it); | |
130 | } | |
131 | } insert_lvalue; | |
7c673cae | 132 | |
b32b8144 FG |
133 | struct insert_lvalue_begin_type : inserter_base |
134 | { | |
135 | template <typename T, typename Iterator> void operator()(T& x, Iterator it) | |
136 | { | |
137 | x.insert(x.begin(), *it); | |
138 | } | |
139 | } insert_lvalue_begin; | |
7c673cae | 140 | |
b32b8144 | 141 | struct insert_lvalue_end_type : inserter_base |
7c673cae | 142 | { |
b32b8144 FG |
143 | template <typename T, typename Iterator> void operator()(T& x, Iterator it) |
144 | { | |
145 | x.insert(x.end(), *it); | |
146 | } | |
147 | } insert_lvalue_end; | |
7c673cae | 148 | |
b32b8144 FG |
149 | struct insert_lvalue_pos_type |
150 | { | |
151 | template <typename T> struct impl : inserter_base | |
152 | { | |
153 | typename T::iterator pos; | |
7c673cae | 154 | |
b32b8144 | 155 | impl(T& x) : pos(x.begin()) {} |
7c673cae | 156 | |
b32b8144 FG |
157 | template <typename Iterator> void operator()(T& x, Iterator it) |
158 | { | |
159 | pos = get_iterator(x.insert(pos, *it)); | |
7c673cae | 160 | } |
b32b8144 | 161 | }; |
7c673cae | 162 | |
b32b8144 FG |
163 | template <typename T> friend impl<T> generate(insert_lvalue_pos_type, T& x) |
164 | { | |
165 | return impl<T>(x); | |
166 | } | |
167 | } insert_lvalue_pos; | |
7c673cae | 168 | |
b32b8144 | 169 | struct insert_single_item_range_type : inserter_base |
7c673cae | 170 | { |
b32b8144 FG |
171 | template <typename T, typename Iterator> void operator()(T& x, Iterator it) |
172 | { | |
173 | x.insert(it, test::next(it)); | |
174 | } | |
175 | } insert_single_item_range; | |
7c673cae | 176 | |
b32b8144 | 177 | struct emplace_lvalue_type : inserter_base |
7c673cae | 178 | { |
b32b8144 FG |
179 | template <typename T, typename Iterator> void operator()(T& x, Iterator it) |
180 | { | |
181 | x.emplace(*it); | |
182 | } | |
183 | } emplace_lvalue; | |
7c673cae | 184 | |
b32b8144 FG |
185 | struct emplace_lvalue_begin_type : inserter_base |
186 | { | |
187 | template <typename T, typename Iterator> void operator()(T& x, Iterator it) | |
188 | { | |
189 | x.emplace_hint(x.begin(), *it); | |
190 | } | |
191 | } emplace_lvalue_begin; | |
7c673cae | 192 | |
b32b8144 FG |
193 | struct emplace_lvalue_end_type : inserter_base |
194 | { | |
195 | template <typename T, typename Iterator> void operator()(T& x, Iterator it) | |
196 | { | |
197 | x.emplace_hint(x.end(), *it); | |
198 | } | |
199 | } emplace_lvalue_end; | |
7c673cae | 200 | |
b32b8144 FG |
201 | struct emplace_lvalue_pos_type |
202 | { | |
203 | template <typename T> struct impl : inserter_base | |
204 | { | |
205 | typename T::iterator pos; | |
7c673cae | 206 | |
b32b8144 | 207 | impl(T& x) : pos(x.begin()) {} |
7c673cae | 208 | |
b32b8144 FG |
209 | template <typename Iterator> void operator()(T& x, Iterator it) |
210 | { | |
211 | pos = get_iterator(x.emplace_hint(pos, *it)); | |
7c673cae | 212 | } |
b32b8144 FG |
213 | }; |
214 | ||
215 | template <typename T> friend impl<T> generate(emplace_lvalue_pos_type, T& x) | |
216 | { | |
217 | return impl<T>(x); | |
218 | } | |
219 | } emplace_lvalue_pos; | |
220 | ||
221 | // Run the exception tests in various combinations. | |
222 | ||
223 | test_set* test_set_; | |
224 | test_multiset* test_multiset_; | |
225 | test_map* test_map_; | |
226 | test_multimap* test_multimap_; | |
227 | ||
228 | using test::default_generator; | |
229 | using test::limited_range; | |
230 | using test::generate_collisions; | |
231 | ||
232 | // clang-format off | |
233 | UNORDERED_TEST(insert_exception_test, | |
234 | ((test_set_)(test_multiset_)(test_map_)(test_multimap_)) | |
235 | ((insert_lvalue)(insert_lvalue_begin)(insert_lvalue_end) | |
236 | (insert_lvalue_pos)(insert_single_item_range) | |
237 | (emplace_lvalue)(emplace_lvalue_begin)(emplace_lvalue_end) | |
238 | (emplace_lvalue_pos) | |
239 | ) | |
240 | ((default_generator)(limited_range)(generate_collisions)) | |
241 | ) | |
242 | ||
243 | UNORDERED_TEST(insert_rehash_exception_test, | |
244 | ((test_set_)(test_multiset_)(test_map_)(test_multimap_)) | |
245 | ((insert_lvalue)(insert_lvalue_begin)(insert_lvalue_end) | |
246 | (insert_lvalue_pos)(insert_single_item_range) | |
247 | (emplace_lvalue)(emplace_lvalue_begin)(emplace_lvalue_end) | |
248 | (emplace_lvalue_pos) | |
249 | ) | |
250 | ((default_generator)(limited_range)(generate_collisions)) | |
251 | ) | |
252 | // clang-format on | |
253 | ||
254 | // Repeat insert tests with pairs | |
255 | ||
256 | struct pair_emplace_type : inserter_base | |
257 | { | |
258 | template <typename T, typename Iterator> void operator()(T& x, Iterator it) | |
259 | { | |
260 | x.emplace(boost::unordered::piecewise_construct, | |
261 | boost::make_tuple(it->first), boost::make_tuple(it->second)); | |
262 | } | |
263 | } pair_emplace; | |
264 | ||
265 | struct pair_emplace2_type : inserter_base | |
266 | { | |
267 | template <typename T, typename Iterator> void operator()(T& x, Iterator it) | |
268 | { | |
269 | x.emplace_hint(x.begin(), boost::unordered::piecewise_construct, | |
270 | boost::make_tuple(it->first), | |
271 | boost::make_tuple(it->second.tag1_, it->second.tag2_)); | |
272 | } | |
273 | } pair_emplace2; | |
274 | ||
275 | test_pair_set* test_pair_set_; | |
276 | test_pair_multiset* test_pair_multiset_; | |
277 | ||
278 | // clang-format off | |
279 | UNORDERED_TEST(insert_exception_test, | |
280 | ((test_pair_set_)(test_pair_multiset_)(test_map_)(test_multimap_)) | |
281 | ((pair_emplace)(pair_emplace2)) | |
282 | ((default_generator)(limited_range)(generate_collisions)) | |
283 | ) | |
284 | UNORDERED_TEST(insert_rehash_exception_test, | |
285 | ((test_pair_set_)(test_pair_multiset_)(test_map_)(test_multimap_)) | |
286 | ((pair_emplace)(pair_emplace2)) | |
287 | ((default_generator)(limited_range)(generate_collisions)) | |
288 | ) | |
289 | // clang-format on | |
290 | ||
291 | // Test inserting using operator[] | |
292 | ||
293 | struct try_emplace_type : inserter_base | |
294 | { | |
295 | template <typename T, typename Iterator> void operator()(T& x, Iterator it) | |
296 | { | |
297 | x.try_emplace(it->first, it->second); | |
298 | } | |
299 | } try_emplace; | |
7c673cae | 300 | |
b32b8144 FG |
301 | struct try_emplace2_type : inserter_base |
302 | { | |
303 | template <typename T, typename Iterator> void operator()(T& x, Iterator it) | |
304 | { | |
305 | x.try_emplace(it->first, it->second.tag1_, it->second.tag2_); | |
306 | } | |
307 | } try_emplace2; | |
7c673cae | 308 | |
b32b8144 FG |
309 | struct map_inserter_base |
310 | { | |
311 | template <typename T> void exception_check(T& x, test::strong<T>& strong) | |
312 | { | |
313 | std::string scope(test::scope); | |
314 | ||
315 | if (scope.find("hash::operator()") == std::string::npos && | |
316 | scope.find("::operator=") == std::string::npos) | |
317 | strong.test(x, test::detail::tracker.count_allocations); | |
318 | } | |
319 | ||
320 | template <typename T, typename Iterator> | |
321 | void track(T& tracker, Iterator begin, Iterator end) | |
322 | { | |
323 | for (; begin != end; ++begin) { | |
324 | tracker[begin->first] = begin->second; | |
7c673cae | 325 | } |
b32b8144 | 326 | } |
7c673cae FG |
327 | }; |
328 | ||
b32b8144 FG |
329 | struct map_insert_operator_type : map_inserter_base |
330 | { | |
331 | template <typename T, typename Iterator> void operator()(T& x, Iterator it) | |
332 | { | |
333 | x[it->first] = it->second; | |
334 | } | |
335 | } map_insert_operator; | |
7c673cae | 336 | |
b32b8144 FG |
337 | struct map_insert_or_assign_type : map_inserter_base |
338 | { | |
339 | template <typename T, typename Iterator> void operator()(T& x, Iterator it) | |
340 | { | |
341 | x.insert_or_assign(it->first, it->second); | |
342 | } | |
343 | } map_insert_or_assign; | |
344 | ||
345 | // clang-format off | |
346 | UNORDERED_TEST(insert_exception_test, | |
347 | ((test_map_)) | |
348 | ((try_emplace)(try_emplace2)(map_insert_operator)(map_insert_or_assign)) | |
349 | ((default_generator)(limited_range)(generate_collisions)) | |
350 | ) | |
351 | UNORDERED_TEST(insert_rehash_exception_test, | |
352 | ((test_map_)) | |
353 | ((try_emplace)(try_emplace2)(map_insert_operator)(map_insert_or_assign)) | |
354 | ((default_generator)(limited_range)(generate_collisions)) | |
355 | ) | |
356 | // clang-format on | |
357 | ||
358 | // Range insert tests | |
359 | ||
360 | template <typename T, typename Values> | |
361 | void insert_range_exception_test_impl(T x, Values const& v) | |
362 | { | |
363 | test::ordered<T> tracker; | |
364 | tracker.insert(x.begin(), x.end()); | |
365 | ||
366 | try { | |
367 | ENABLE_EXCEPTIONS; | |
368 | x.insert(v.begin(), v.end()); | |
369 | } catch (...) { | |
370 | test::check_equivalent_keys(x); | |
371 | throw; | |
372 | } | |
373 | ||
374 | test::check_equivalent_keys(x); | |
375 | tracker.insert(v.begin(), v.end()); | |
376 | tracker.compare(x); | |
377 | } | |
378 | ||
379 | template <typename T> | |
380 | void insert_range_exception_test(T*, test::random_generator gen) | |
381 | { | |
382 | for (int i = 0; i < 5; ++i) { | |
383 | test::random_values<T> v(10, gen); | |
384 | T x; | |
385 | ||
386 | EXCEPTION_LOOP(insert_range_exception_test_impl(x, v)); | |
387 | } | |
388 | } | |
7c673cae | 389 | |
b32b8144 FG |
390 | template <typename T> |
391 | void insert_range_rehash_exception_test(T*, test::random_generator gen) | |
392 | { | |
393 | for (int i = 0; i < 5; ++i) { | |
394 | T x; | |
395 | rehash_prep(x); | |
396 | ||
397 | test::random_values<T> v2(5, gen); | |
398 | EXCEPTION_LOOP(insert_range_exception_test_impl(x, v2)); | |
399 | } | |
400 | } | |
401 | ||
402 | // clang-format off | |
403 | UNORDERED_TEST(insert_range_exception_test, | |
404 | ((test_set_)(test_multiset_)(test_map_)(test_multimap_)) | |
405 | ((default_generator)(limited_range)(generate_collisions)) | |
406 | ) | |
407 | ||
408 | UNORDERED_TEST(insert_range_rehash_exception_test, | |
409 | ((test_set_)(test_multiset_)(test_map_)(test_multimap_)) | |
410 | ((default_generator)(limited_range)(generate_collisions)) | |
411 | ) | |
412 | // clang-format on | |
7c673cae | 413 | |
7c673cae | 414 | RUN_TESTS() |