ceph/src/boost/libs/unordered/test/unordered/rehash_tests.cpp

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