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