ceph/src/boost/libs/unordered/test/unordered/node_handle_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/helpers.hpp"
  12 #include "../helpers/metafunctions.hpp"
  13 #include "../helpers/test.hpp"
  14 #include <boost/static_assert.hpp>
  15 #include <boost/type_traits/is_same.hpp>
  16 #include <set>
  17 #include <string>
  18
  19 UNORDERED_AUTO_TEST (example1) {
  20   typedef boost::unordered_map<int, std::string>::insert_return_type
  21     insert_return_type;
  22
  23   boost::unordered_map<int, std::string> src;
  24   src.emplace(1, "one");
  25   src.emplace(2, "two");
  26   src.emplace(3, "buckle my shoe");
  27   boost::unordered_map<int, std::string> dst;
  28   dst.emplace(3, "three");
  29
  30   dst.insert(src.extract(src.find(1)));
  31   dst.insert(src.extract(2));
  32   insert_return_type r = dst.insert(src.extract(3));
  33
  34   BOOST_TEST(src.empty());
  35   BOOST_TEST(dst.size() == 3);
  36   BOOST_TEST(dst[1] == "one");
  37   BOOST_TEST(dst[2] == "two");
  38   BOOST_TEST(dst[3] == "three");
  39   BOOST_TEST(!r.inserted);
  40   BOOST_TEST(r.position == dst.find(3));
  41   BOOST_TEST(r.node.mapped() == "buckle my shoe");
  42 }
  43
  44 UNORDERED_AUTO_TEST (example2) {
  45   boost::unordered_set<int> src;
  46   src.insert(1);
  47   src.insert(3);
  48   src.insert(5);
  49   boost::unordered_set<int> dst;
  50   dst.insert(2);
  51   dst.insert(4);
  52   dst.insert(5);
  53   // dst.merge(src);
  54   // Merge src into dst.
  55   // src == {5}
  56   // dst == {1, 2, 3, 4, 5}
  57 }
  58
  59 UNORDERED_AUTO_TEST (example3) {
  60   typedef boost::unordered_set<int>::iterator iterator;
  61
  62   boost::unordered_set<int> src;
  63   src.insert(1);
  64   src.insert(3);
  65   src.insert(5);
  66   boost::unordered_set<int> dst;
  67   dst.insert(2);
  68   dst.insert(4);
  69   dst.insert(5);
  70   for (iterator i = src.begin(); i != src.end();) {
  71     std::pair<iterator, iterator> p = dst.equal_range(*i);
  72     if (p.first == p.second)
  73       dst.insert(p.first, src.extract(i++));
  74     else
  75       ++i;
  76   }
  77   BOOST_TEST(src.size() == 1);
  78   BOOST_TEST(*src.begin() == 5);
  79
  80   std::set<int> dst2(dst.begin(), dst.end());
  81   std::set<int>::iterator it = dst2.begin();
  82   BOOST_TEST(*it++ == 1);
  83   BOOST_TEST(*it++ == 2);
  84   BOOST_TEST(*it++ == 3);
  85   BOOST_TEST(*it++ == 4);
  86   BOOST_TEST(*it++ == 5);
  87   BOOST_TEST(it == dst2.end());
  88 }
  89
  90 UNORDERED_AUTO_TEST (failed_insertion_with_hint) {
  91   {
  92     boost::unordered_set<int> src;
  93     boost::unordered_set<int> dst;
  94     src.emplace(10);
  95     src.emplace(20);
  96     dst.emplace(10);
  97     dst.emplace(20);
  98
  99     boost::unordered_set<int>::node_type nh = src.extract(10);
 100
 101     BOOST_TEST(dst.insert(dst.find(10), boost::move(nh)) == dst.find(10));
 102     BOOST_TEST(nh);
 103     BOOST_TEST(!nh.empty());
 104     BOOST_TEST(nh.value() == 10);
 105
 106     BOOST_TEST(dst.insert(dst.find(20), boost::move(nh)) == dst.find(10));
 107     BOOST_TEST(nh);
 108     BOOST_TEST(!nh.empty());
 109     BOOST_TEST(nh.value() == 10);
 110
 111     BOOST_TEST(src.count(10) == 0);
 112     BOOST_TEST(src.count(20) == 1);
 113     BOOST_TEST(dst.count(10) == 1);
 114     BOOST_TEST(dst.count(20) == 1);
 115   }
 116
 117   {
 118     boost::unordered_map<int, int> src;
 119     boost::unordered_map<int, int> dst;
 120     src.emplace(10, 30);
 121     src.emplace(20, 5);
 122     dst.emplace(10, 20);
 123     dst.emplace(20, 2);
 124
 125     boost::unordered_map<int, int>::node_type nh = src.extract(10);
 126     BOOST_TEST(dst.insert(dst.find(10), boost::move(nh)) == dst.find(10));
 127     BOOST_TEST(nh);
 128     BOOST_TEST(!nh.empty());
 129     BOOST_TEST(nh.key() == 10);
 130     BOOST_TEST(nh.mapped() == 30);
 131     BOOST_TEST(dst[10] == 20);
 132
 133     BOOST_TEST(dst.insert(dst.find(20), boost::move(nh)) == dst.find(10));
 134     BOOST_TEST(nh);
 135     BOOST_TEST(!nh.empty());
 136     BOOST_TEST(nh.key() == 10);
 137     BOOST_TEST(nh.mapped() == 30);
 138     BOOST_TEST(dst[10] == 20);
 139
 140     BOOST_TEST(src.count(10) == 0);
 141     BOOST_TEST(src.count(20) == 1);
 142     BOOST_TEST(dst.count(10) == 1);
 143     BOOST_TEST(dst.count(20) == 1);
 144   }
 145 }
 146
 147 template <typename NodeHandle>
 148 bool node_handle_compare(
 149   NodeHandle const& nh, BOOST_DEDUCED_TYPENAME NodeHandle::value_type const& x)
 150 {
 151   return x == nh.value();
 152 }
 153
 154 template <typename NodeHandle>
 155 bool node_handle_compare(NodeHandle const& nh,
 156   std::pair<BOOST_DEDUCED_TYPENAME NodeHandle::key_type const,
 157     BOOST_DEDUCED_TYPENAME NodeHandle::mapped_type> const& x)
 158 {
 159   return x.first == nh.key() && x.second == nh.mapped();
 160 }
 161
 162 template <typename Container> void node_handle_tests_impl(Container& c)
 163 {
 164   typedef BOOST_DEDUCED_TYPENAME Container::node_type node_type;
 165
 166   BOOST_DEDUCED_TYPENAME Container::value_type value = *c.begin();
 167
 168   node_type n1;
 169   BOOST_TEST(!n1);
 170   BOOST_TEST(n1.empty());
 171
 172   node_type n2 = c.extract(c.begin());
 173   BOOST_TEST(n2);
 174   BOOST_TEST(!n2.empty());
 175   node_handle_compare(n2, value);
 176
 177   node_type n3 = boost::move(n2);
 178   BOOST_TEST(n3);
 179   BOOST_TEST(!n2);
 180   node_handle_compare(n3, value);
 181   // TODO: Check that n2 doesn't have an allocator?
 182   //       Maybe by swapping and observing that the allocator is
 183   //       swapped rather than moved?
 184
 185   n1 = boost::move(n3);
 186   BOOST_TEST(n1);
 187   BOOST_TEST(!n3);
 188   node_handle_compare(n1, value);
 189
 190   // Self move-assignment empties the node_handle.
 191   n1 = boost::move(n1);
 192   BOOST_TEST(!n1);
 193
 194   n3 = boost::move(n3);
 195   BOOST_TEST(!n3);
 196
 197   BOOST_DEDUCED_TYPENAME Container::value_type value1 = *c.begin();
 198   n1 = c.extract(c.begin());
 199   BOOST_DEDUCED_TYPENAME Container::value_type value2 = *c.begin();
 200   n2 = c.extract(c.begin());
 201   n3 = node_type();
 202
 203   node_handle_compare(n1, value1);
 204   node_handle_compare(n2, value2);
 205   n1.swap(n2);
 206   BOOST_TEST(n1);
 207   BOOST_TEST(n2);
 208   node_handle_compare(n1, value2);
 209   node_handle_compare(n2, value1);
 210
 211   BOOST_TEST(n1);
 212   BOOST_TEST(!n3);
 213   n1.swap(n3);
 214   BOOST_TEST(!n1);
 215   BOOST_TEST(n3);
 216   node_handle_compare(n3, value2);
 217
 218   BOOST_TEST(!n1);
 219   BOOST_TEST(n2);
 220   n1.swap(n2);
 221   BOOST_TEST(n1);
 222   BOOST_TEST(!n2);
 223   node_handle_compare(n1, value1);
 224
 225   node_type n4;
 226   BOOST_TEST(!n2);
 227   BOOST_TEST(!n4);
 228   n2.swap(n4);
 229   BOOST_TEST(!n2);
 230   BOOST_TEST(!n4);
 231 }
 232
 233 UNORDERED_AUTO_TEST (node_handle_tests) {
 234   boost::unordered_set<int> x1;
 235   x1.emplace(100);
 236   x1.emplace(140);
 237   x1.emplace(-55);
 238   node_handle_tests_impl(x1);
 239
 240   boost::unordered_map<int, std::string> x2;
 241   x2.emplace(10, "ten");
 242   x2.emplace(-23, "twenty");
 243   x2.emplace(-76, "thirty");
 244   node_handle_tests_impl(x2);
 245 }
 246
 247 template <typename Container1, typename Container2>
 248 void insert_node_handle_unique(Container1& c1, Container2& c2)
 249 {
 250   typedef BOOST_DEDUCED_TYPENAME Container1::node_type node_type;
 251   typedef BOOST_DEDUCED_TYPENAME Container1::value_type value_type;
 252   BOOST_STATIC_ASSERT(boost::is_same<node_type,
 253     BOOST_DEDUCED_TYPENAME Container2::node_type>::value);
 254
 255   typedef BOOST_DEDUCED_TYPENAME Container1::insert_return_type
 256     insert_return_type1;
 257   typedef BOOST_DEDUCED_TYPENAME Container2::insert_return_type
 258     insert_return_type2;
 259
 260   insert_return_type1 r1 = c1.insert(node_type());
 261   insert_return_type2 r2 = c2.insert(node_type());
 262   BOOST_TEST(!r1.inserted);
 263   BOOST_TEST(!r1.node);
 264   BOOST_TEST(r1.position == c1.end());
 265   BOOST_TEST(!r2.inserted);
 266   BOOST_TEST(!r2.node);
 267   BOOST_TEST(r2.position == c2.end());
 268
 269   while (!c1.empty()) {
 270     value_type v = *c1.begin();
 271     value_type const* v_ptr = boost::addressof(*c1.begin());
 272     std::size_t count = c2.count(test::get_key<Container1>(v));
 273     insert_return_type2 r = c2.insert(c1.extract(c1.begin()));
 274     if (!count) {
 275       BOOST_TEST(r.inserted);
 276       BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count + 1);
 277       BOOST_TEST(r.position != c2.end());
 278       BOOST_TEST(boost::addressof(*r.position) == v_ptr);
 279       BOOST_TEST(!r.node);
 280     } else {
 281       BOOST_TEST(!r.inserted);
 282       BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count);
 283       BOOST_TEST(r.position != c2.end());
 284       BOOST_TEST(
 285         test::get_key<Container2>(*r.position) == test::get_key<Container2>(v));
 286       BOOST_TEST(r.node);
 287       node_handle_compare(r.node, v);
 288     }
 289   }
 290 }
 291
 292 template <typename Container1, typename Container2>
 293 void insert_node_handle_unique2(Container1& c1, Container2& c2)
 294 {
 295   typedef BOOST_DEDUCED_TYPENAME Container1::node_type node_type;
 296   typedef BOOST_DEDUCED_TYPENAME Container1::value_type value_type;
 297   BOOST_STATIC_ASSERT(boost::is_same<node_type,
 298     BOOST_DEDUCED_TYPENAME Container2::node_type>::value);
 299
 300   // typedef BOOST_DEDUCED_TYPENAME Container1::insert_return_type
 301   // insert_return_type1;
 302   typedef BOOST_DEDUCED_TYPENAME Container2::insert_return_type
 303     insert_return_type2;
 304
 305   while (!c1.empty()) {
 306     value_type v = *c1.begin();
 307     value_type const* v_ptr = boost::addressof(*c1.begin());
 308     std::size_t count = c2.count(test::get_key<Container1>(v));
 309     insert_return_type2 r = c2.insert(c1.extract(test::get_key<Container1>(v)));
 310     if (r.inserted) {
 311       BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count + 1);
 312       BOOST_TEST(r.position != c2.end());
 313       BOOST_TEST(boost::addressof(*r.position) == v_ptr);
 314       BOOST_TEST(!r.node);
 315     } else {
 316       BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count);
 317       BOOST_TEST(r.position != c2.end());
 318       BOOST_TEST(
 319         test::get_key<Container2>(*r.position) == test::get_key<Container2>(v));
 320       BOOST_TEST(r.node);
 321       node_handle_compare(r.node, v);
 322     }
 323   }
 324 }
 325
 326 template <typename Container1, typename Container2>
 327 void insert_node_handle_equiv(Container1& c1, Container2& c2)
 328 {
 329   typedef BOOST_DEDUCED_TYPENAME Container1::node_type node_type;
 330   typedef BOOST_DEDUCED_TYPENAME Container1::value_type value_type;
 331   BOOST_STATIC_ASSERT(boost::is_same<node_type,
 332     BOOST_DEDUCED_TYPENAME Container2::node_type>::value);
 333
 334   typedef BOOST_DEDUCED_TYPENAME Container1::iterator iterator1;
 335   typedef BOOST_DEDUCED_TYPENAME Container2::iterator iterator2;
 336
 337   iterator1 r1 = c1.insert(node_type());
 338   iterator2 r2 = c2.insert(node_type());
 339   BOOST_TEST(r1 == c1.end());
 340   BOOST_TEST(r2 == c2.end());
 341
 342   while (!c1.empty()) {
 343     value_type v = *c1.begin();
 344     value_type const* v_ptr = boost::addressof(*c1.begin());
 345     std::size_t count = c2.count(test::get_key<Container1>(v));
 346     iterator2 r = c2.insert(c1.extract(c1.begin()));
 347     BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count + 1);
 348     BOOST_TEST(r != c2.end());
 349     BOOST_TEST(boost::addressof(*r) == v_ptr);
 350   }
 351 }
 352
 353 struct hash_thing
 354 {
 355   std::size_t operator()(int x) const
 356   {
 357     return static_cast<std::size_t>(x * 13 + 5);
 358   }
 359 };
 360
 361 UNORDERED_AUTO_TEST (insert_node_handle_unique_tests) {
 362   {
 363     boost::unordered_set<int> x1;
 364     boost::unordered_set<int> x2;
 365     x1.emplace(100);
 366     x1.emplace(140);
 367     x1.emplace(-55);
 368     x2.emplace(140);
 369     insert_node_handle_unique(x1, x2);
 370     BOOST_TEST(x2.size() == 3);
 371   }
 372
 373   {
 374     boost::unordered_map<int, int, hash_thing> x1;
 375     boost::unordered_map<int, int> x2;
 376     x1.emplace(67, 50);
 377     x1.emplace(23, 45);
 378     x1.emplace(18, 19);
 379     x2.emplace(23, 50);
 380     x2.emplace(12, 49);
 381     insert_node_handle_unique(x1, x2);
 382     BOOST_TEST(x2.size() == 4);
 383   }
 384 }
 385
 386 UNORDERED_AUTO_TEST (insert_node_handle_equiv_tests) {
 387   {
 388     boost::unordered_multimap<int, int, hash_thing> x1;
 389     boost::unordered_multimap<int, int> x2;
 390     x1.emplace(67, 50);
 391     x1.emplace(67, 100);
 392     x1.emplace(23, 45);
 393     x1.emplace(18, 19);
 394     x2.emplace(23, 50);
 395     x2.emplace(12, 49);
 396     insert_node_handle_equiv(x1, x2);
 397     BOOST_TEST(x2.size() == 6);
 398   }
 399 }
 400
 401 UNORDERED_AUTO_TEST (insert_node_handle_unique_tests2) {
 402   {
 403     boost::unordered_set<int> x1;
 404     boost::unordered_set<int> x2;
 405     x1.emplace(100);
 406     x1.emplace(140);
 407     x1.emplace(-55);
 408     x2.emplace(140);
 409     insert_node_handle_unique2(x1, x2);
 410     BOOST_TEST(x2.size() == 3);
 411   }
 412
 413   {
 414     boost::unordered_map<int, int, hash_thing> x1;
 415     boost::unordered_map<int, int> x2;
 416     x1.emplace(67, 50);
 417     x1.emplace(23, 45);
 418     x1.emplace(18, 19);
 419     x2.emplace(23, 50);
 420     x2.emplace(12, 49);
 421     insert_node_handle_unique2(x1, x2);
 422     BOOST_TEST(x2.size() == 4);
 423   }
 424 }
 425
 426 RUN_TESTS()