[ceph.git] / ceph / src / boost / libs / unordered / test / unordered / node_handle_tests.cpp


// Copyright 2016 Daniel James.
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#include "../helpers/postfix.hpp"
#include "../helpers/prefix.hpp"
#include <boost/unordered_map.hpp>
#include <boost/unordered_set.hpp>

#include "../helpers/helpers.hpp"
#include "../helpers/metafunctions.hpp"
#include "../helpers/test.hpp"
#include <boost/core/pointer_traits.hpp>
#include <boost/static_assert.hpp>
#include <boost/type_traits/is_same.hpp>
#include <set>
#include <string>

UNORDERED_AUTO_TEST (example1) {
  typedef boost::unordered_map<int, std::string>::insert_return_type
    insert_return_type;

  boost::unordered_map<int, std::string> src;
  src.emplace(1, "one");
  src.emplace(2, "two");
  src.emplace(3, "buckle my shoe");
  boost::unordered_map<int, std::string> dst;
  dst.emplace(3, "three");

  dst.insert(src.extract(src.find(1)));
  dst.insert(src.extract(2));
  insert_return_type r = dst.insert(src.extract(3));

  BOOST_TEST(src.empty());
  BOOST_TEST(dst.size() == 3);
  BOOST_TEST(dst[1] == "one");
  BOOST_TEST(dst[2] == "two");
  BOOST_TEST(dst[3] == "three");
  BOOST_TEST(!r.inserted);
  BOOST_TEST(r.position == dst.find(3));
  BOOST_TEST(r.node.mapped() == "buckle my shoe");
}

UNORDERED_AUTO_TEST (example2) {
  boost::unordered_set<int> src;
  src.insert(1);
  src.insert(3);
  src.insert(5);
  boost::unordered_set<int> dst;
  dst.insert(2);
  dst.insert(4);
  dst.insert(5);
  // dst.merge(src);
  // Merge src into dst.
  // src == {5}
  // dst == {1, 2, 3, 4, 5}
}

UNORDERED_AUTO_TEST (example3) {
  typedef boost::unordered_set<int>::iterator iterator;

  boost::unordered_set<int> src;
  src.insert(1);
  src.insert(3);
  src.insert(5);
  boost::unordered_set<int> dst;
  dst.insert(2);
  dst.insert(4);
  dst.insert(5);
  for (iterator i = src.begin(); i != src.end();) {
    std::pair<iterator, iterator> p = dst.equal_range(*i);
    if (p.first == p.second)
      dst.insert(p.first, src.extract(i++));
    else
      ++i;
  }
  BOOST_TEST(src.size() == 1);
  BOOST_TEST(*src.begin() == 5);

  std::set<int> dst2(dst.begin(), dst.end());
  std::set<int>::iterator it = dst2.begin();
  BOOST_TEST(*it++ == 1);
  BOOST_TEST(*it++ == 2);
  BOOST_TEST(*it++ == 3);
  BOOST_TEST(*it++ == 4);
  BOOST_TEST(*it++ == 5);
  BOOST_TEST(it == dst2.end());
}

UNORDERED_AUTO_TEST (failed_insertion_with_hint) {
  {
    boost::unordered_set<int> src;
    boost::unordered_set<int> dst;
    src.emplace(10);
    src.emplace(20);
    dst.emplace(10);
    dst.emplace(20);

    boost::unordered_set<int>::node_type nh = src.extract(10);

    BOOST_TEST(dst.insert(dst.find(10), boost::move(nh)) == dst.find(10));
    BOOST_TEST(nh);
    BOOST_TEST(!nh.empty());
    BOOST_TEST(nh.value() == 10);

    BOOST_TEST(dst.insert(dst.find(20), boost::move(nh)) == dst.find(10));
    BOOST_TEST(nh);
    BOOST_TEST(!nh.empty());
    BOOST_TEST(nh.value() == 10);

    BOOST_TEST(src.count(10) == 0);
    BOOST_TEST(src.count(20) == 1);
    BOOST_TEST(dst.count(10) == 1);
    BOOST_TEST(dst.count(20) == 1);
  }

  {
    boost::unordered_map<int, int> src;
    boost::unordered_map<int, int> dst;
    src.emplace(10, 30);
    src.emplace(20, 5);
    dst.emplace(10, 20);
    dst.emplace(20, 2);

    boost::unordered_map<int, int>::node_type nh = src.extract(10);
    BOOST_TEST(dst.insert(dst.find(10), boost::move(nh)) == dst.find(10));
    BOOST_TEST(nh);
    BOOST_TEST(!nh.empty());
    BOOST_TEST(nh.key() == 10);
    BOOST_TEST(nh.mapped() == 30);
    BOOST_TEST(dst[10] == 20);

    BOOST_TEST(dst.insert(dst.find(20), boost::move(nh)) == dst.find(10));
    BOOST_TEST(nh);
    BOOST_TEST(!nh.empty());
    BOOST_TEST(nh.key() == 10);
    BOOST_TEST(nh.mapped() == 30);
    BOOST_TEST(dst[10] == 20);

    BOOST_TEST(src.count(10) == 0);
    BOOST_TEST(src.count(20) == 1);
    BOOST_TEST(dst.count(10) == 1);
    BOOST_TEST(dst.count(20) == 1);
  }
}

template <typename NodeHandle>
bool node_handle_compare(
  NodeHandle const& nh, typename NodeHandle::value_type const& x)
{
  return x == nh.value();
}

template <typename NodeHandle>
bool node_handle_compare(
  NodeHandle const& nh, std::pair<typename NodeHandle::key_type const,
                          typename NodeHandle::mapped_type> const& x)
{
  return x.first == nh.key() && x.second == nh.mapped();
}

template <typename Container> void node_handle_tests_impl(Container& c)
{
  typedef typename Container::node_type node_type;

  typename Container::value_type value = *c.begin();

  node_type n1;
  BOOST_TEST(!n1);
  BOOST_TEST(n1.empty());

  node_type n2 = c.extract(c.begin());
  BOOST_TEST(n2);
  BOOST_TEST(!n2.empty());
  node_handle_compare(n2, value);

  node_type n3 = boost::move(n2);
  BOOST_TEST(n3);
  BOOST_TEST(!n2);
  node_handle_compare(n3, value);
  // TODO: Check that n2 doesn't have an allocator?
  //       Maybe by swapping and observing that the allocator is
  //       swapped rather than moved?

  n1 = boost::move(n3);
  BOOST_TEST(n1);
  BOOST_TEST(!n3);
  node_handle_compare(n1, value);

  // Self move-assignment empties the node_handle.
  n1 = boost::move(n1);
  BOOST_TEST(!n1);

  n3 = boost::move(n3);
  BOOST_TEST(!n3);

  typename Container::value_type value1 = *c.begin();
  n1 = c.extract(c.begin());
  typename Container::value_type value2 = *c.begin();
  n2 = c.extract(c.begin());
  n3 = node_type();

  node_handle_compare(n1, value1);
  node_handle_compare(n2, value2);
  n1.swap(n2);
  BOOST_TEST(n1);
  BOOST_TEST(n2);
  node_handle_compare(n1, value2);
  node_handle_compare(n2, value1);

  BOOST_TEST(n1);
  BOOST_TEST(!n3);
  n1.swap(n3);
  BOOST_TEST(!n1);
  BOOST_TEST(n3);
  node_handle_compare(n3, value2);

  BOOST_TEST(!n1);
  BOOST_TEST(n2);
  n1.swap(n2);
  BOOST_TEST(n1);
  BOOST_TEST(!n2);
  node_handle_compare(n1, value1);

  node_type n4;
  BOOST_TEST(!n2);
  BOOST_TEST(!n4);
  n2.swap(n4);
  BOOST_TEST(!n2);
  BOOST_TEST(!n4);
}

UNORDERED_AUTO_TEST (node_handle_tests) {
  boost::unordered_set<int> x1;
  x1.emplace(100);
  x1.emplace(140);
  x1.emplace(-55);
  node_handle_tests_impl(x1);

  boost::unordered_map<int, std::string> x2;
  x2.emplace(10, "ten");
  x2.emplace(-23, "twenty");
  x2.emplace(-76, "thirty");
  node_handle_tests_impl(x2);
}

template <typename Container1, typename Container2>
void insert_node_handle_unique(Container1& c1, Container2& c2)
{
  typedef typename Container1::node_type node_type;
  typedef typename Container1::value_type value_type;
  BOOST_STATIC_ASSERT(
    (boost::is_same<node_type, typename Container2::node_type>::value));

  typedef typename Container1::insert_return_type insert_return_type1;
  typedef typename Container2::insert_return_type insert_return_type2;

  insert_return_type1 r1 = c1.insert(node_type());
  insert_return_type2 r2 = c2.insert(node_type());
  BOOST_TEST(!r1.inserted);
  BOOST_TEST(!r1.node);
  BOOST_TEST(r1.position == c1.end());
  BOOST_TEST(!r2.inserted);
  BOOST_TEST(!r2.node);
  BOOST_TEST(r2.position == c2.end());

  while (!c1.empty()) {
    value_type v = *c1.begin();
    value_type const* v_ptr = boost::to_address(c1.begin());
    std::size_t count = c2.count(test::get_key<Container1>(v));
    insert_return_type2 r = c2.insert(c1.extract(c1.begin()));
    if (!count) {
      BOOST_TEST(r.inserted);
      BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count + 1);
      BOOST_TEST(r.position != c2.end());
      BOOST_TEST(boost::to_address(r.position) == v_ptr);
      BOOST_TEST(!r.node);
    } else {
      BOOST_TEST(!r.inserted);
      BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count);
      BOOST_TEST(r.position != c2.end());
      BOOST_TEST(
        test::get_key<Container2>(*r.position) == test::get_key<Container2>(v));
      BOOST_TEST(r.node);
      node_handle_compare(r.node, v);
    }
  }
}

template <typename Container1, typename Container2>
void insert_node_handle_unique2(Container1& c1, Container2& c2)
{
  typedef typename Container1::node_type node_type;
  typedef typename Container1::value_type value_type;
  BOOST_STATIC_ASSERT(
    (boost::is_same<node_type, typename Container2::node_type>::value));

  // typedef typename Container1::insert_return_type
  // insert_return_type1;
  typedef typename Container2::insert_return_type insert_return_type2;

  while (!c1.empty()) {
    value_type v = *c1.begin();
    value_type const* v_ptr = boost::to_address(c1.begin());
    std::size_t count = c2.count(test::get_key<Container1>(v));
    insert_return_type2 r = c2.insert(c1.extract(test::get_key<Container1>(v)));
    if (r.inserted) {
      BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count + 1);
      BOOST_TEST(r.position != c2.end());
      BOOST_TEST(boost::to_address(r.position) == v_ptr);
      BOOST_TEST(!r.node);
    } else {
      BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count);
      BOOST_TEST(r.position != c2.end());
      BOOST_TEST(
        test::get_key<Container2>(*r.position) == test::get_key<Container2>(v));
      BOOST_TEST(r.node);
      node_handle_compare(r.node, v);
    }
  }
}

template <typename Container1, typename Container2>
void insert_node_handle_equiv(Container1& c1, Container2& c2)
{
  typedef typename Container1::node_type node_type;
  typedef typename Container1::value_type value_type;
  BOOST_STATIC_ASSERT(
    (boost::is_same<node_type, typename Container2::node_type>::value));

  typedef typename Container1::iterator iterator1;
  typedef typename Container2::iterator iterator2;

  iterator1 r1 = c1.insert(node_type());
  iterator2 r2 = c2.insert(node_type());
  BOOST_TEST(r1 == c1.end());
  BOOST_TEST(r2 == c2.end());

  while (!c1.empty()) {
    value_type v = *c1.begin();
    value_type const* v_ptr = boost::to_address(c1.begin());
    std::size_t count = c2.count(test::get_key<Container1>(v));
    iterator2 r = c2.insert(c1.extract(c1.begin()));
    BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count + 1);
    BOOST_TEST(r != c2.end());
    BOOST_TEST(boost::to_address(r) == v_ptr);
  }
}

struct hash_thing
{
  std::size_t operator()(int x) const
  {
    return static_cast<std::size_t>(x * 13 + 5);
  }
};

UNORDERED_AUTO_TEST (insert_node_handle_unique_tests) {
  {
    boost::unordered_set<int> x1;
    boost::unordered_set<int> x2;
    x1.emplace(100);
    x1.emplace(140);
    x1.emplace(-55);
    x2.emplace(140);
    insert_node_handle_unique(x1, x2);
    BOOST_TEST(x2.size() == 3);
  }

  {
    boost::unordered_map<int, int, hash_thing> x1;
    boost::unordered_map<int, int> x2;
    x1.emplace(67, 50);
    x1.emplace(23, 45);
    x1.emplace(18, 19);
    x2.emplace(23, 50);
    x2.emplace(12, 49);
    insert_node_handle_unique(x1, x2);
    BOOST_TEST(x2.size() == 4);
  }
}

UNORDERED_AUTO_TEST (insert_node_handle_equiv_tests) {
  {
    boost::unordered_multimap<int, int, hash_thing> x1;
    boost::unordered_multimap<int, int> x2;
    x1.emplace(67, 50);
    x1.emplace(67, 100);
    x1.emplace(23, 45);
    x1.emplace(18, 19);
    x2.emplace(23, 50);
    x2.emplace(12, 49);
    insert_node_handle_equiv(x1, x2);
    BOOST_TEST(x2.size() == 6);
  }
}

UNORDERED_AUTO_TEST (insert_node_handle_unique_tests2) {
  {
    boost::unordered_set<int> x1;
    boost::unordered_set<int> x2;
    x1.emplace(100);
    x1.emplace(140);
    x1.emplace(-55);
    x2.emplace(140);
    insert_node_handle_unique2(x1, x2);
    BOOST_TEST(x2.size() == 3);
  }

  {
    boost::unordered_map<int, int, hash_thing> x1;
    boost::unordered_map<int, int> x2;
    x1.emplace(67, 50);
    x1.emplace(23, 45);
    x1.emplace(18, 19);
    x2.emplace(23, 50);
    x2.emplace(12, 49);
    insert_node_handle_unique2(x1, x2);
    BOOST_TEST(x2.size() == 4);
  }
}

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