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)
5
6// The code for erasing elements from containers with equivalent keys is very
7// hairy with several tricky edge cases - so explicitly test each one.
8
9// clang-format off
10#include "../helpers/prefix.hpp"
11#include <boost/unordered_map.hpp>
12#include "../helpers/postfix.hpp"
13// clang-format on
14
15#include "../helpers/test.hpp"
16#include "../helpers/list.hpp"
17#include "../helpers/invariants.hpp"
18#include "../helpers/helpers.hpp"
19#include <algorithm>
20#include <set>
21#include <iterator>
22#include "../objects/test.hpp"
23
24#if BOOST_WORKAROUND(BOOST_MSVC, < 1400)
25#pragma warning(disable : 4267) // conversion from 'size_t' to 'unsigned int',
26 // possible loss of data.
27#endif
28
29struct write_pair_type
30{
31 template <class X1, class X2>
32 void operator()(std::pair<X1, X2> const& x) const
33 {
34 BOOST_LIGHTWEIGHT_TEST_OSTREAM << "(" << x.first << "," << x.second << ")";
35 }
36} write_pair;
37
38template <class Container> void write_container(Container const& x)
39{
40 std::for_each(x.begin(), x.end(), write_pair);
41 BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n";
42}
43
44// Make everything collide - for testing erase in a single bucket.
45struct collision_hash
46{
47 std::size_t operator()(int) const { return 0; }
48};
49
50// For testing erase in 2 buckets.
51struct collision2_hash
52{
53 std::size_t operator()(int x) const
54 {
55 return static_cast<std::size_t>(x & 1);
56 }
57};
58
59// For testing erase in lots of buckets.
60struct collision3_hash
61{
62 std::size_t operator()(int x) const { return static_cast<std::size_t>(x); }
63};
64
65typedef boost::unordered_multimap<int, int, collision_hash, std::equal_to<int>,
66 test::allocator1<std::pair<int const, int> > >
67 collide_map;
68typedef boost::unordered_multimap<int, int, collision2_hash, std::equal_to<int>,
69 test::allocator2<std::pair<int const, int> > >
70 collide_map2;
71typedef boost::unordered_multimap<int, int, collision3_hash, std::equal_to<int>,
72 test::allocator2<std::pair<int const, int> > >
73 collide_map3;
74typedef collide_map::value_type collide_value;
75typedef test::list<collide_value> collide_list;
76
77UNORDERED_AUTO_TEST (empty_range_tests) {
78 collide_map x;
79 x.erase(first: x.begin(), last: x.end());
80 x.erase(first: x.begin(), last: x.begin());
81 x.erase(first: x.end(), last: x.end());
82 test::check_equivalent_keys(x1: x);
83}
84
85UNORDERED_AUTO_TEST (single_item_tests) {
86 collide_list init;
87 init.push_back(v: collide_value(1, 1));
88
89 collide_map x(init.begin(), init.end());
90 x.erase(first: x.begin(), last: x.begin());
91 BOOST_TEST(x.count(1) == 1 && x.size() == 1);
92 test::check_equivalent_keys(x1: x);
93 x.erase(first: x.end(), last: x.end());
94 BOOST_TEST(x.count(1) == 1 && x.size() == 1);
95 test::check_equivalent_keys(x1: x);
96 x.erase(first: x.begin(), last: x.end());
97 BOOST_TEST(x.count(1) == 0 && x.size() == 0);
98 test::check_equivalent_keys(x1: x);
99}
100
101UNORDERED_AUTO_TEST (two_equivalent_item_tests) {
102 collide_list init;
103 init.push_back(v: collide_value(1, 1));
104 init.push_back(v: collide_value(1, 2));
105
106 {
107 collide_map x(init.begin(), init.end());
108 x.erase(first: x.begin(), last: x.end());
109 BOOST_TEST(x.count(1) == 0 && x.size() == 0);
110 test::check_equivalent_keys(x1: x);
111 }
112
113 {
114 collide_map x(init.begin(), init.end());
115 int value = test::next(it: x.begin())->second;
116 x.erase(first: x.begin(), last: test::next(it: x.begin()));
117 BOOST_TEST(x.count(1) == 1 && x.size() == 1 && x.begin()->first == 1 &&
118 x.begin()->second == value);
119 test::check_equivalent_keys(x1: x);
120 }
121
122 {
123 collide_map x(init.begin(), init.end());
124 int value = x.begin()->second;
125 x.erase(first: test::next(it: x.begin()), last: x.end());
126 BOOST_TEST(x.count(1) == 1 && x.size() == 1 && x.begin()->first == 1 &&
127 x.begin()->second == value);
128 test::check_equivalent_keys(x1: x);
129 }
130}
131
132// More automated tests...
133
134template <class Range1, class Range2>
135bool compare(Range1 const& x, Range2 const& y)
136{
137 collide_list a(x.begin(), x.end());
138 collide_list b(y.begin(), y.end());
139 a.sort();
140 b.sort();
141 return a == b;
142}
143
144template <class Container>
145bool general_erase_range_test(Container& x, std::size_t start, std::size_t end)
146{
147 collide_list l(x.begin(), x.end());
148
149 l.erase(i: test::next(it: l.begin(), x: start), j: test::next(it: l.begin(), x: end));
150 x.erase(test::next(x.begin(), start), test::next(x.begin(), end));
151
152 test::check_equivalent_keys(x);
153 return compare(l, x);
154}
155
156template <class Container> void erase_subrange_tests(Container const& x)
157{
158 for (std::size_t length = 0; length < x.size(); ++length) {
159 for (std::size_t position = 0; position < x.size() - length; ++position) {
160 Container y(x);
161 collide_list init(y.begin(), y.end());
162 if (!general_erase_range_test(y, position, position + length)) {
163 BOOST_ERROR("general_erase_range_test failed.");
164 BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Erase: [" << position << ","
165 << position + length << ")\n";
166 write_container(x: init);
167 write_container(y);
168 }
169 }
170 }
171}
172
173template <class Container>
174void x_by_y_erase_range_tests(Container*, int values, int duplicates)
175{
176 Container y;
177
178 for (int i = 0; i < values; ++i) {
179 for (int j = 0; j < duplicates; ++j) {
180 y.insert(collide_value(i, j));
181 }
182 }
183
184 BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Values: " << values
185 << ", Duplicates: " << duplicates << "\n";
186 erase_subrange_tests(y);
187}
188
189template <class Container>
190void exhaustive_erase_tests(Container* x, int num_values, int num_duplicated)
191{
192 for (int i = 0; i < num_values; ++i) {
193 for (int j = 0; j < num_duplicated; ++j) {
194 x_by_y_erase_range_tests(x, i, j);
195 }
196 }
197}
198
199UNORDERED_AUTO_TEST (exhaustive_collide_tests) {
200 BOOST_LIGHTWEIGHT_TEST_OSTREAM << "exhaustive_collide_tests:\n";
201 collide_map m;
202 exhaustive_erase_tests(x: (collide_map*)0, num_values: 4, num_duplicated: 4);
203 BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n";
204}
205
206UNORDERED_AUTO_TEST (exhaustive_collide2_tests) {
207 BOOST_LIGHTWEIGHT_TEST_OSTREAM << "exhaustive_collide2_tests:\n";
208 exhaustive_erase_tests(x: (collide_map2*)0, num_values: 8, num_duplicated: 4);
209 BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n";
210}
211
212UNORDERED_AUTO_TEST (exhaustive_collide3_tests) {
213 BOOST_LIGHTWEIGHT_TEST_OSTREAM << "exhaustive_collide3_tests:\n";
214 exhaustive_erase_tests(x: (collide_map3*)0, num_values: 8, num_duplicated: 4);
215 BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n";
216}
217
218RUN_TESTS()
219

source code of boost/libs/unordered/test/unordered/erase_equiv_tests.cpp