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 // 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
  23   template <class X>
  24   bool postcondition(X const& x, BOOST_DEDUCED_TYPENAME X::size_type n)
  25   {
  26     return static_cast<double>(x.bucket_count()) >=
  27              static_cast<double>(x.size()) / x.max_load_factor() &&
  28            x.bucket_count() >= n;
  29   }
  30
  31   template <class X> 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> void rehash_test1(X*, test::random_generator generator)
  86   {
  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());
  91
  92     x.rehash(0);
  93     BOOST_TEST(postcondition(x, 0));
  94     tracker.compare(x);
  95
  96     x.max_load_factor(0.25);
  97     x.rehash(0);
  98     BOOST_TEST(postcondition(x, 0));
  99     tracker.compare(x);
 100
 101     x.max_load_factor(50.0);
 102     x.rehash(0);
 103     BOOST_TEST(postcondition(x, 0));
 104     tracker.compare(x);
 105
 106     x.rehash(1000);
 107     BOOST_TEST(postcondition(x, 1000));
 108     tracker.compare(x);
 109   }
 110
 111   template <class X> void reserve_empty_test1(X*)
 112   {
 113     X x;
 114
 115     x.reserve(10000);
 116     BOOST_TEST(x.bucket_count() >= 10000);
 117
 118     x.reserve(0);
 119
 120     x.reserve(10000000);
 121     BOOST_TEST(x.bucket_count() >= 10000000);
 122   }
 123
 124   template <class X> void reserve_empty_test2(X*)
 125   {
 126     X x;
 127     x.max_load_factor(0.25);
 128
 129     x.reserve(10000);
 130     BOOST_TEST(x.bucket_count() >= 40000);
 131
 132     x.reserve(0);
 133
 134     x.reserve(10000000);
 135     BOOST_TEST(x.bucket_count() >= 40000000);
 136   }
 137
 138   template <class X> void reserve_test1(X*, test::random_generator generator)
 139   {
 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);
 143
 144         test::ordered<X> tracker;
 145         tracker.insert_range(v.begin(), v.end());
 146
 147         X x;
 148         x.max_load_factor(
 149           random_mlf ? static_cast<float>(std::rand() % 1000) / 500.0f + 0.5f
 150                      : 1.0f);
 151         x.reserve(test::has_unique_keys<X>::value ? i : v.size());
 152
 153         // Insert an element before the range insert, otherwise there are
 154         // no iterators to invalidate in the range insert, and it can
 155         // rehash.
 156         typename test::random_values<X>::iterator it = v.begin();
 157         x.insert(*it);
 158         ++it;
 159
 160         std::size_t bucket_count = x.bucket_count();
 161         x.insert(it, v.end());
 162         BOOST_TEST(bucket_count == x.bucket_count());
 163         tracker.compare(x);
 164       }
 165     }
 166   }
 167
 168   template <class X> void reserve_test2(X*, test::random_generator generator)
 169   {
 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);
 173
 174         test::ordered<X> tracker;
 175         tracker.insert_range(v.begin(), v.end());
 176
 177         X x;
 178         x.max_load_factor(
 179           random_mlf ? static_cast<float>(std::rand() % 1000) / 500.0f + 0.5f
 180                      : 1.0f);
 181
 182         x.reserve(test::has_unique_keys<X>::value ? i : v.size());
 183
 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) {
 187           x.insert(*it);
 188         }
 189
 190         BOOST_TEST(bucket_count == x.bucket_count());
 191         tracker.compare(x);
 192       }
 193     }
 194   }
 195
 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;
 202
 203   using test::default_generator;
 204   using test::generate_collisions;
 205   using test::limited_range;
 206
 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)))
 228 }
 229
 230 RUN_TESTS()