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