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 // clang-format off 7 #include "../helpers/prefix.hpp" 8 #include <boost/unordered_set.hpp> 9 #include <boost/unordered_map.hpp> 10 #include "../helpers/postfix.hpp" 11 // clang-format on 12 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" 18 19 namespace rehash_tests { 20 21 test::seed_t initialize_seed(2974); 22 postcondition(X const & x,typename X::size_type n)23 template <class X> bool postcondition(X const& x, typename X::size_type n) 24 { 25 return static_cast<double>(x.bucket_count()) >= 26 static_cast<double>(x.size()) / x.max_load_factor() && 27 x.bucket_count() >= n; 28 } 29 rehash_empty_test1(X *)30 template <class X> void rehash_empty_test1(X*) 31 { 32 X x; 33 34 x.rehash(10000); 35 BOOST_TEST(postcondition(x, 10000)); 36 37 x.rehash(0); 38 BOOST_TEST(postcondition(x, 0)); 39 40 x.rehash(10000000); 41 BOOST_TEST(postcondition(x, 10000000)); 42 } 43 44 template <class X> rehash_empty_test2(X *,test::random_generator generator)45 void rehash_empty_test2(X*, test::random_generator generator) 46 { 47 test::random_values<X> v(1000, generator); 48 test::ordered<X> tracker; 49 50 X x; 51 52 x.rehash(10000); 53 BOOST_TEST(postcondition(x, 10000)); 54 55 tracker.insert_range(v.begin(), v.end()); 56 x.insert(v.begin(), v.end()); 57 tracker.compare(x); 58 59 BOOST_TEST(postcondition(x, 10000)); 60 61 x.rehash(10000000); 62 tracker.compare(x); 63 BOOST_TEST(postcondition(x, 10000000)); 64 } 65 66 template <class X> rehash_empty_test3(X *,test::random_generator generator)67 void rehash_empty_test3(X*, test::random_generator generator) 68 { 69 test::random_values<X> v(1000, generator); 70 test::ordered<X> tracker; 71 72 X x; 73 74 x.rehash(0); 75 BOOST_TEST(postcondition(x, 0)); 76 77 tracker.insert_range(v.begin(), v.end()); 78 x.insert(v.begin(), v.end()); 79 tracker.compare(x); 80 81 BOOST_TEST(postcondition(x, 0)); 82 } 83 rehash_test1(X *,test::random_generator generator)84 template <class X> void rehash_test1(X*, test::random_generator generator) 85 { 86 test::random_values<X> v(1000, generator); 87 test::ordered<X> tracker; 88 tracker.insert_range(v.begin(), v.end()); 89 X x(v.begin(), v.end()); 90 91 x.rehash(0); 92 BOOST_TEST(postcondition(x, 0)); 93 tracker.compare(x); 94 95 x.max_load_factor(0.25); 96 x.rehash(0); 97 BOOST_TEST(postcondition(x, 0)); 98 tracker.compare(x); 99 100 x.max_load_factor(50.0); 101 x.rehash(0); 102 BOOST_TEST(postcondition(x, 0)); 103 tracker.compare(x); 104 105 x.rehash(1000); 106 BOOST_TEST(postcondition(x, 1000)); 107 tracker.compare(x); 108 } 109 reserve_empty_test1(X *)110 template <class X> void reserve_empty_test1(X*) 111 { 112 X x; 113 114 x.reserve(10000); 115 BOOST_TEST(x.bucket_count() >= 10000); 116 117 x.reserve(0); 118 119 x.reserve(10000000); 120 BOOST_TEST(x.bucket_count() >= 10000000); 121 } 122 reserve_empty_test2(X *)123 template <class X> void reserve_empty_test2(X*) 124 { 125 X x; 126 x.max_load_factor(0.25); 127 128 x.reserve(10000); 129 BOOST_TEST(x.bucket_count() >= 40000); 130 131 x.reserve(0); 132 133 x.reserve(10000000); 134 BOOST_TEST(x.bucket_count() >= 40000000); 135 } 136 reserve_test1(X *,test::random_generator generator)137 template <class X> void reserve_test1(X*, test::random_generator generator) 138 { 139 for (int random_mlf = 0; random_mlf < 2; ++random_mlf) { 140 for (std::size_t i = 1; i < 2000; i += i < 50 ? 1 : 13) { 141 test::random_values<X> v(i, generator); 142 143 test::ordered<X> tracker; 144 tracker.insert_range(v.begin(), v.end()); 145 146 X x; 147 x.max_load_factor( 148 random_mlf ? static_cast<float>(std::rand() % 1000) / 500.0f + 0.5f 149 : 1.0f); 150 x.reserve(test::has_unique_keys<X>::value ? i : v.size()); 151 152 // Insert an element before the range insert, otherwise there are 153 // no iterators to invalidate in the range insert, and it can 154 // rehash. 155 typename test::random_values<X>::iterator it = v.begin(); 156 x.insert(*it); 157 ++it; 158 159 std::size_t bucket_count = x.bucket_count(); 160 x.insert(it, v.end()); 161 BOOST_TEST(bucket_count == x.bucket_count()); 162 tracker.compare(x); 163 } 164 } 165 } 166 reserve_test2(X *,test::random_generator generator)167 template <class X> void reserve_test2(X*, test::random_generator generator) 168 { 169 for (int random_mlf = 0; random_mlf < 2; ++random_mlf) { 170 for (std::size_t i = 0; i < 2000; i += i < 50 ? 1 : 13) { 171 test::random_values<X> v(i, generator); 172 173 test::ordered<X> tracker; 174 tracker.insert_range(v.begin(), v.end()); 175 176 X x; 177 x.max_load_factor( 178 random_mlf ? static_cast<float>(std::rand() % 1000) / 500.0f + 0.5f 179 : 1.0f); 180 181 x.reserve(test::has_unique_keys<X>::value ? i : v.size()); 182 183 std::size_t bucket_count = x.bucket_count(); 184 for (typename test::random_values<X>::iterator it = v.begin(); 185 it != v.end(); ++it) { 186 x.insert(*it); 187 } 188 189 BOOST_TEST(bucket_count == x.bucket_count()); 190 tracker.compare(x); 191 } 192 } 193 } 194 195 boost::unordered_set<int>* int_set_ptr; 196 boost::unordered_multiset<test::object, test::hash, test::equal_to, 197 test::allocator2<test::object> >* test_multiset_ptr; 198 boost::unordered_map<test::movable, test::movable, test::hash, test::equal_to, 199 test::allocator2<test::movable> >* test_map_ptr; 200 boost::unordered_multimap<int, int>* int_multimap_ptr; 201 202 using test::default_generator; 203 using test::generate_collisions; 204 using test::limited_range; 205 206 UNORDERED_TEST(rehash_empty_test1, 207 ((int_set_ptr)(test_multiset_ptr)(test_map_ptr)(int_multimap_ptr))) 208 UNORDERED_TEST(rehash_empty_test2, 209 ((int_set_ptr)(test_multiset_ptr)(test_map_ptr)(int_multimap_ptr))( 210 (default_generator)(generate_collisions)(limited_range))) 211 UNORDERED_TEST(rehash_empty_test3, 212 ((int_set_ptr)(test_multiset_ptr)(test_map_ptr)(int_multimap_ptr))( 213 (default_generator)(generate_collisions)(limited_range))) 214 UNORDERED_TEST(rehash_test1, 215 ((int_set_ptr)(test_multiset_ptr)(test_map_ptr)(int_multimap_ptr))( 216 (default_generator)(generate_collisions)(limited_range))) 217 UNORDERED_TEST(reserve_empty_test1, 218 ((int_set_ptr)(test_multiset_ptr)(test_map_ptr)(int_multimap_ptr))) 219 UNORDERED_TEST(reserve_empty_test2, 220 ((int_set_ptr)(test_multiset_ptr)(test_map_ptr)(int_multimap_ptr))) 221 UNORDERED_TEST(reserve_test1, 222 ((int_set_ptr)(test_multiset_ptr)(test_map_ptr)(int_multimap_ptr))( 223 (default_generator)(generate_collisions)(limited_range))) 224 UNORDERED_TEST(reserve_test2, 225 ((int_set_ptr)(test_multiset_ptr)(test_map_ptr)(int_multimap_ptr))( 226 (default_generator)(generate_collisions)(limited_range))) 227 } 228 229 RUN_TESTS() 230