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

   1
   2 // Copyright 2016 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/postfix.hpp"
   7 #include "../helpers/prefix.hpp"
   8 #include <boost/unordered_map.hpp>
   9 #include <boost/unordered_set.hpp>
  10
  11 #include "../helpers/count.hpp"
  12 #include "../helpers/helpers.hpp"
  13 #include "../helpers/invariants.hpp"
  14 #include "../helpers/random_values.hpp"
  15 #include "../helpers/test.hpp"
  16 #include "../helpers/tracker.hpp"
  17 #include "../objects/test.hpp"
  18 #include <boost/next_prior.hpp>
  19
  20 namespace merge_tests {
  21
  22   UNORDERED_AUTO_TEST (merge_set) {
  23     boost::unordered_set<int> x;
  24     boost::unordered_set<int> y;
  25
  26     x.merge(y);
  27     BOOST_TEST(x.empty());
  28     BOOST_TEST(y.empty());
  29
  30     x.insert(10);
  31     x.merge(y);
  32     BOOST_TEST(x.size() == 1);
  33     BOOST_TEST(x.count(10) == 1);
  34     BOOST_TEST(y.empty());
  35
  36     y.merge(x);
  37     BOOST_TEST(x.empty());
  38     BOOST_TEST(y.size() == 1);
  39     BOOST_TEST(y.count(10) == 1);
  40
  41     x.insert(10);
  42     x.insert(50);
  43     y.insert(70);
  44     y.insert(80);
  45     x.merge(y);
  46     BOOST_TEST_EQ(x.size(), 4u);
  47     BOOST_TEST_EQ(y.size(), 1u);
  48     BOOST_TEST_EQ(x.count(10), 1u);
  49     BOOST_TEST_EQ(x.count(50), 1u);
  50     BOOST_TEST_EQ(x.count(70), 1u);
  51     BOOST_TEST_EQ(x.count(80), 1u);
  52     BOOST_TEST_EQ(y.count(10), 1u);
  53     BOOST_TEST_EQ(y.count(50), 0u);
  54     BOOST_TEST_EQ(y.count(70), 0u);
  55     BOOST_TEST_EQ(y.count(80), 0u);
  56
  57     test::check_equivalent_keys(x);
  58     test::check_equivalent_keys(y);
  59   }
  60
  61   UNORDERED_AUTO_TEST (merge_multiset) {
  62     boost::unordered_multiset<int> x;
  63     boost::unordered_multiset<int> y;
  64
  65     x.merge(y);
  66     BOOST_TEST(x.empty());
  67     BOOST_TEST(y.empty());
  68
  69     x.insert(10);
  70     x.merge(y);
  71     BOOST_TEST(x.size() == 1);
  72     BOOST_TEST(x.count(10) == 1);
  73     BOOST_TEST(y.empty());
  74
  75     y.merge(x);
  76     BOOST_TEST(x.empty());
  77     BOOST_TEST(y.size() == 1);
  78     BOOST_TEST(y.count(10) == 1);
  79
  80     x.insert(10);
  81     x.insert(50);
  82     y.insert(70);
  83     y.insert(80);
  84     x.merge(y);
  85     BOOST_TEST_EQ(x.size(), 5u);
  86     BOOST_TEST_EQ(y.size(), 0u);
  87     BOOST_TEST_EQ(x.count(10), 2u);
  88     BOOST_TEST_EQ(x.count(50), 1u);
  89     BOOST_TEST_EQ(x.count(70), 1u);
  90     BOOST_TEST_EQ(x.count(80), 1u);
  91     BOOST_TEST_EQ(y.count(10), 0u);
  92     BOOST_TEST_EQ(y.count(50), 0u);
  93     BOOST_TEST_EQ(y.count(70), 0u);
  94     BOOST_TEST_EQ(y.count(80), 0u);
  95
  96     test::check_equivalent_keys(x);
  97     test::check_equivalent_keys(y);
  98   }
  99
 100   UNORDERED_AUTO_TEST (merge_set_and_multiset) {
 101     boost::unordered_set<int> x;
 102     boost::unordered_multiset<int> y;
 103
 104     x.merge(y);
 105     BOOST_TEST(x.empty());
 106     BOOST_TEST(y.empty());
 107
 108     x.insert(10);
 109     x.merge(y);
 110     BOOST_TEST(x.size() == 1);
 111     BOOST_TEST(x.count(10) == 1);
 112     BOOST_TEST(y.empty());
 113
 114     y.merge(x);
 115     BOOST_TEST(x.empty());
 116     BOOST_TEST(y.size() == 1);
 117     BOOST_TEST(y.count(10) == 1);
 118
 119     x.insert(10);
 120     x.insert(50);
 121     y.insert(70);
 122     y.insert(80);
 123     x.merge(y);
 124     BOOST_TEST_EQ(x.size(), 4u);
 125     BOOST_TEST_EQ(y.size(), 1u);
 126     BOOST_TEST_EQ(x.count(10), 1u);
 127     BOOST_TEST_EQ(x.count(50), 1u);
 128     BOOST_TEST_EQ(x.count(70), 1u);
 129     BOOST_TEST_EQ(x.count(80), 1u);
 130     BOOST_TEST_EQ(y.count(10), 1u);
 131     BOOST_TEST_EQ(y.count(50), 0u);
 132     BOOST_TEST_EQ(y.count(70), 0u);
 133     BOOST_TEST_EQ(y.count(80), 0u);
 134
 135     test::check_equivalent_keys(x);
 136     test::check_equivalent_keys(y);
 137   }
 138
 139   template <class X1, class X2>
 140   void merge_empty_test(X1*, X2*, test::random_generator generator)
 141   {
 142     test::check_instances check_;
 143
 144     test::random_values<X1> v(1000, generator);
 145     X1 x1(v.begin(), v.end());
 146     X2 x2;
 147     x1.merge(x2);
 148     test::check_container(x1, v);
 149     BOOST_TEST(x2.empty());
 150     test::check_equivalent_keys(x1);
 151     test::check_equivalent_keys(x2);
 152   }
 153
 154   template <class X>
 155   void merge_into_empty_test(X*, test::random_generator generator)
 156   {
 157     test::check_instances check_;
 158
 159     test::random_values<X> v(1000, generator);
 160     X x1;
 161     X x2(v.begin(), v.end());
 162     x1.merge(x2);
 163     test::check_container(x1, v);
 164     BOOST_TEST(x2.empty());
 165     test::check_equivalent_keys(x1);
 166     test::check_equivalent_keys(x2);
 167   }
 168
 169   template <class X1, class X2>
 170   void merge_into_unique_keys_test(X1*, X2*, int hash_equal1, int hash_equal2,
 171     test::random_generator generator)
 172   {
 173     test::check_instances check_;
 174
 175     test::random_values<X1> v1(1000, generator);
 176     test::random_values<X2> v2(1000, generator);
 177     v1.insert(v2.begin(), boost::next(v2.begin(), 100));
 178     v2.insert(v1.begin(), boost::next(v1.begin(), 100));
 179
 180     X1 x1(v1.begin(), v1.end(), 0, test::hash(hash_equal1),
 181       test::equal_to(hash_equal1));
 182     X2 x2(v2.begin(), v2.end(), 0, test::hash(hash_equal2),
 183       test::equal_to(hash_equal2));
 184
 185     test::ordered<X1> tracker1 = test::create_ordered(x1);
 186     test::ordered<X2> tracker2 = test::create_ordered(x2);
 187     tracker1.insert(v1.begin(), v1.end());
 188     for (typename X2::iterator it = x2.begin(); it != x2.end(); ++it) {
 189       if (!tracker1.insert(*it).second) {
 190         tracker2.insert(*it);
 191       }
 192     }
 193
 194     x1.merge(x2);
 195
 196     tracker1.compare(x1);
 197     tracker2.compare(x2);
 198     test::check_equivalent_keys(x1);
 199     test::check_equivalent_keys(x2);
 200   }
 201
 202   template <class X1, class X2>
 203   void merge_into_equiv_keys_test(X1*, X2*, int hash_equal1, int hash_equal2,
 204     test::random_generator generator)
 205   {
 206     test::check_instances check_;
 207
 208     test::random_values<X1> v1(1000, generator);
 209     test::random_values<X2> v2(1000, generator);
 210     v1.insert(v2.begin(), boost::next(v2.begin(), 100));
 211     v2.insert(v1.begin(), boost::next(v1.begin(), 100));
 212
 213     X1 x1(v1.begin(), v1.end(), 0, test::hash(hash_equal1),
 214       test::equal_to(hash_equal1));
 215     X2 x2(v2.begin(), v2.end(), 0, test::hash(hash_equal2),
 216       test::equal_to(hash_equal2));
 217     x1.merge(x2);
 218
 219     test::ordered<X1> tracker1 = test::create_ordered(x1);
 220     test::ordered<X2> tracker2 = test::create_ordered(x2);
 221     tracker1.insert(v1.begin(), v1.end());
 222     tracker2.insert(v2.begin(), v2.end());
 223     tracker1.insert(tracker2.begin(), tracker2.end());
 224     tracker2.clear();
 225
 226     tracker1.compare(x1);
 227     tracker2.compare(x2);
 228     test::check_equivalent_keys(x1);
 229     test::check_equivalent_keys(x2);
 230   }
 231
 232   boost::unordered_set<test::movable, test::hash, test::equal_to,
 233     std::allocator<test::movable> >* test_set_std_alloc;
 234   boost::unordered_multiset<test::movable, test::hash, test::equal_to,
 235     std::allocator<test::movable> >* test_multiset_std_alloc;
 236
 237   boost::unordered_map<test::object, test::object, test::hash, test::equal_to,
 238     std::allocator<test::object> >* test_map_std_alloc;
 239   boost::unordered_multimap<test::object, test::object, test::hash,
 240     test::equal_to, std::allocator<test::object> >* test_multimap_std_alloc;
 241
 242   boost::unordered_set<test::object, test::hash, test::equal_to,
 243     test::allocator1<test::object> >* test_set;
 244   boost::unordered_multiset<test::object, test::hash, test::equal_to,
 245     test::allocator1<test::object> >* test_multiset;
 246
 247   boost::unordered_map<test::movable, test::movable, test::hash, test::equal_to,
 248     test::allocator2<test::movable> >* test_map;
 249   boost::unordered_multimap<test::movable, test::movable, test::hash,
 250     test::equal_to, test::allocator2<test::movable> >* test_multimap;
 251
 252   using test::default_generator;
 253   using test::generate_collisions;
 254
 255   // clang-format off
 256 UNORDERED_TEST(merge_empty_test,
 257     ((test_set_std_alloc)(test_multiset_std_alloc))
 258     ((test_set_std_alloc)(test_multiset_std_alloc))
 259     ((default_generator)(generate_collisions)))
 260 UNORDERED_TEST(merge_empty_test,
 261     ((test_map_std_alloc)(test_multimap_std_alloc))
 262     ((test_map_std_alloc)(test_multimap_std_alloc))
 263     ((default_generator)(generate_collisions)))
 264 UNORDERED_TEST(merge_empty_test,
 265     ((test_set)(test_multiset))
 266     ((test_set)(test_multiset))
 267     ((default_generator)(generate_collisions)))
 268 UNORDERED_TEST(merge_empty_test,
 269     ((test_map)(test_multimap))
 270     ((test_map)(test_multimap))
 271     ((default_generator)(generate_collisions)))
 272
 273 UNORDERED_TEST(merge_into_empty_test,
 274     ((test_set_std_alloc)(test_multiset_std_alloc))
 275     ((default_generator)(generate_collisions)))
 276 UNORDERED_TEST(merge_into_empty_test,
 277     ((test_map_std_alloc)(test_multimap_std_alloc))
 278     ((default_generator)(generate_collisions)))
 279 UNORDERED_TEST(merge_into_empty_test,
 280     ((test_set)(test_multiset))
 281     ((default_generator)(generate_collisions)))
 282 UNORDERED_TEST(merge_into_empty_test,
 283     ((test_map)(test_multimap))
 284     ((default_generator)(generate_collisions)))
 285
 286 UNORDERED_TEST(merge_into_unique_keys_test,
 287     ((test_set_std_alloc))
 288     ((test_set_std_alloc)(test_multiset_std_alloc))
 289     ((0)(1)(2))
 290     ((0)(1)(2))
 291     ((default_generator)(generate_collisions)))
 292 UNORDERED_TEST(merge_into_unique_keys_test,
 293     ((test_map_std_alloc))
 294     ((test_map_std_alloc)(test_multimap_std_alloc))
 295     ((0)(1)(2))
 296     ((0)(1)(2))
 297     ((default_generator)(generate_collisions)))
 298 UNORDERED_TEST(merge_into_unique_keys_test,
 299     ((test_set))
 300     ((test_set)(test_multiset))
 301     ((0)(1)(2))
 302     ((0)(1)(2))
 303     ((default_generator)(generate_collisions)))
 304 UNORDERED_TEST(merge_into_unique_keys_test,
 305     ((test_map))
 306     ((test_map)(test_multimap))
 307     ((0)(1)(2))
 308     ((0)(1)(2))
 309     ((default_generator)(generate_collisions)))
 310
 311 UNORDERED_TEST(merge_into_equiv_keys_test,
 312     ((test_multiset_std_alloc))
 313     ((test_set_std_alloc)(test_multiset_std_alloc))
 314     ((0)(1)(2))
 315     ((0)(1)(2))
 316     ((default_generator)(generate_collisions)))
 317 UNORDERED_TEST(merge_into_equiv_keys_test,
 318     ((test_multimap_std_alloc))
 319     ((test_map_std_alloc)(test_multimap_std_alloc))
 320     ((0)(1)(2))
 321     ((0)(1)(2))
 322     ((default_generator)(generate_collisions)))
 323 UNORDERED_TEST(merge_into_equiv_keys_test,
 324     ((test_multiset))
 325     ((test_set)(test_multiset))
 326     ((0)(1)(2))
 327     ((0)(1)(2))
 328     ((default_generator)(generate_collisions)))
 329 UNORDERED_TEST(merge_into_equiv_keys_test,
 330     ((test_multimap))
 331     ((test_map)(test_multimap))
 332     ((0)(1)(2))
 333     ((0)(1)(2))
 334     ((default_generator)(generate_collisions)))
 335   // clang-format on
 336 }
 337
 338 RUN_TESTS()