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)
7 #include "../helpers/prefix.hpp"
8 #include <boost/unordered_set.hpp>
9 #include <boost/unordered_map.hpp>
10 #include "../helpers/postfix.hpp"
13 #include "../helpers/test.hpp"
14 #include "../helpers/random_values.hpp"
15 #include "../helpers/tracker.hpp"
16 #include "../helpers/metafunctions.hpp"
17 #include "../objects/test.hpp"
19 namespace rehash_tests
{
21 test::seed_t
initialize_seed(2974);
24 bool postcondition(X
const& x
, BOOST_DEDUCED_TYPENAME
X::size_type n
)
26 return static_cast<double>(x
.bucket_count()) >=
27 static_cast<double>(x
.size()) / x
.max_load_factor() &&
28 x
.bucket_count() >= n
;
31 template <class X
> void rehash_empty_test1(X
*)
36 BOOST_TEST(postcondition(x
, 10000));
39 BOOST_TEST(postcondition(x
, 0));
42 BOOST_TEST(postcondition(x
, 10000000));
46 void rehash_empty_test2(X
*, test::random_generator generator
)
48 test::random_values
<X
> v(1000, generator
);
49 test::ordered
<X
> tracker
;
54 BOOST_TEST(postcondition(x
, 10000));
56 tracker
.insert_range(v
.begin(), v
.end());
57 x
.insert(v
.begin(), v
.end());
60 BOOST_TEST(postcondition(x
, 10000));
64 BOOST_TEST(postcondition(x
, 10000000));
68 void rehash_empty_test3(X
*, test::random_generator generator
)
70 test::random_values
<X
> v(1000, generator
);
71 test::ordered
<X
> tracker
;
76 BOOST_TEST(postcondition(x
, 0));
78 tracker
.insert_range(v
.begin(), v
.end());
79 x
.insert(v
.begin(), v
.end());
82 BOOST_TEST(postcondition(x
, 0));
85 template <class X
> void rehash_test1(X
*, test::random_generator generator
)
87 test::random_values
<X
> v(1000, generator
);
88 test::ordered
<X
> tracker
;
89 tracker
.insert_range(v
.begin(), v
.end());
90 X
x(v
.begin(), v
.end());
93 BOOST_TEST(postcondition(x
, 0));
96 x
.max_load_factor(0.25);
98 BOOST_TEST(postcondition(x
, 0));
101 x
.max_load_factor(50.0);
103 BOOST_TEST(postcondition(x
, 0));
107 BOOST_TEST(postcondition(x
, 1000));
111 template <class X
> void reserve_empty_test1(X
*)
116 BOOST_TEST(x
.bucket_count() >= 10000);
121 BOOST_TEST(x
.bucket_count() >= 10000000);
124 template <class X
> void reserve_empty_test2(X
*)
127 x
.max_load_factor(0.25);
130 BOOST_TEST(x
.bucket_count() >= 40000);
135 BOOST_TEST(x
.bucket_count() >= 40000000);
138 template <class X
> void reserve_test1(X
*, test::random_generator generator
)
140 for (int random_mlf
= 0; random_mlf
< 2; ++random_mlf
) {
141 for (std::size_t i
= 1; i
< 2000; i
+= i
< 50 ? 1 : 13) {
142 test::random_values
<X
> v(i
, generator
);
144 test::ordered
<X
> tracker
;
145 tracker
.insert_range(v
.begin(), v
.end());
149 random_mlf
? static_cast<float>(std::rand() % 1000) / 500.0f
+ 0.5f
151 x
.reserve(test::has_unique_keys
<X
>::value
? i
: v
.size());
153 // Insert an element before the range insert, otherwise there are
154 // no iterators to invalidate in the range insert, and it can
156 typename
test::random_values
<X
>::iterator it
= v
.begin();
160 std::size_t bucket_count
= x
.bucket_count();
161 x
.insert(it
, v
.end());
162 BOOST_TEST(bucket_count
== x
.bucket_count());
168 template <class X
> void reserve_test2(X
*, test::random_generator generator
)
170 for (int random_mlf
= 0; random_mlf
< 2; ++random_mlf
) {
171 for (std::size_t i
= 0; i
< 2000; i
+= i
< 50 ? 1 : 13) {
172 test::random_values
<X
> v(i
, generator
);
174 test::ordered
<X
> tracker
;
175 tracker
.insert_range(v
.begin(), v
.end());
179 random_mlf
? static_cast<float>(std::rand() % 1000) / 500.0f
+ 0.5f
182 x
.reserve(test::has_unique_keys
<X
>::value
? i
: v
.size());
184 std::size_t bucket_count
= x
.bucket_count();
185 for (typename
test::random_values
<X
>::iterator it
= v
.begin();
186 it
!= v
.end(); ++it
) {
190 BOOST_TEST(bucket_count
== x
.bucket_count());
196 boost::unordered_set
<int>* int_set_ptr
;
197 boost::unordered_multiset
<test::object
, test::hash
, test::equal_to
,
198 test::allocator2
<test::object
> >* test_multiset_ptr
;
199 boost::unordered_map
<test::movable
, test::movable
, test::hash
, test::equal_to
,
200 test::allocator2
<test::movable
> >* test_map_ptr
;
201 boost::unordered_multimap
<int, int>* int_multimap_ptr
;
203 using test::default_generator
;
204 using test::generate_collisions
;
205 using test::limited_range
;
207 UNORDERED_TEST(rehash_empty_test1
,
208 ((int_set_ptr
)(test_multiset_ptr
)(test_map_ptr
)(int_multimap_ptr
)))
209 UNORDERED_TEST(rehash_empty_test2
,
210 ((int_set_ptr
)(test_multiset_ptr
)(test_map_ptr
)(int_multimap_ptr
))(
211 (default_generator
)(generate_collisions
)(limited_range
)))
212 UNORDERED_TEST(rehash_empty_test3
,
213 ((int_set_ptr
)(test_multiset_ptr
)(test_map_ptr
)(int_multimap_ptr
))(
214 (default_generator
)(generate_collisions
)(limited_range
)))
215 UNORDERED_TEST(rehash_test1
,
216 ((int_set_ptr
)(test_multiset_ptr
)(test_map_ptr
)(int_multimap_ptr
))(
217 (default_generator
)(generate_collisions
)(limited_range
)))
218 UNORDERED_TEST(reserve_empty_test1
,
219 ((int_set_ptr
)(test_multiset_ptr
)(test_map_ptr
)(int_multimap_ptr
)))
220 UNORDERED_TEST(reserve_empty_test2
,
221 ((int_set_ptr
)(test_multiset_ptr
)(test_map_ptr
)(int_multimap_ptr
)))
222 UNORDERED_TEST(reserve_test1
,
223 ((int_set_ptr
)(test_multiset_ptr
)(test_map_ptr
)(int_multimap_ptr
))(
224 (default_generator
)(generate_collisions
)(limited_range
)))
225 UNORDERED_TEST(reserve_test2
,
226 ((int_set_ptr
)(test_multiset_ptr
)(test_map_ptr
)(int_multimap_ptr
))(
227 (default_generator
)(generate_collisions
)(limited_range
)))