[prev in list] [next in list] [prev in thread] [next in thread]
List: cfe-commits
Subject: [PATCH] D46845: [libcxx][c++17] P0083R5: Splicing Maps and Sets
From: Erik Pilkington via Phabricator via cfe-commits <cfe-commits () lists ! llvm ! org>
Date: 2018-05-31 22:01:49
Message-ID: 385d8177958b1295dccc6a9f5c22c5ff () localhost ! localdomain
[Download RAW message or body]
erik.pilkington updated this revision to Diff 149362.
erik.pilkington added a comment.
Update this patch to depend on https://reviews.llvm.org/D47607, which fixes=
__value_type in map and unordered_map. Thanks!
https://reviews.llvm.org/D46845
Files:
libcxx/include/__hash_table
libcxx/include/__node_handle
libcxx/include/__tree
libcxx/include/map
libcxx/include/set
libcxx/include/unordered_map
libcxx/include/unordered_set
libcxx/test/std/containers/associative/map/map.modifiers/insert_extract.p=
ass.cpp
libcxx/test/std/containers/associative/map/map.modifiers/merge.pass.cpp
libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert=
_extract.pass.cpp
libcxx/test/std/containers/associative/multimap/multimap.modifiers/merge.=
pass.cpp
libcxx/test/std/containers/associative/multiset/insert_extract.pass.cpp
libcxx/test/std/containers/associative/multiset/merge.pass.cpp
libcxx/test/std/containers/associative/set/insert_extract.pass.cpp
libcxx/test/std/containers/associative/set/merge.pass.cpp
libcxx/test/std/containers/container.node/node_handle.pass.cpp
libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_ext=
ract.pass.cpp
libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass=
.cpp
libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/=
insert_extract.pass.cpp
libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/=
merge.pass.cpp
libcxx/test/std/containers/unord/unord.multiset/insert_extract.pass.cpp
libcxx/test/std/containers/unord/unord.multiset/merge.pass.cpp
libcxx/test/std/containers/unord/unord.set/insert_extract.pass.cpp
libcxx/test/std/containers/unord/unord.set/merge.pass.cpp
libcxx/test/support/Counter.h
["D46845.149362.patch" (text/x-patch)]
Index: libcxx/test/support/Counter.h
===================================================================
--- libcxx/test/support/Counter.h
+++ libcxx/test/support/Counter.h
@@ -49,7 +49,7 @@
typedef Counter<T> argument_type;
typedef std::size_t result_type;
- std::size_t operator()(const Counter<T>& x) const {return \
std::hash<T>(x.get());} + std::size_t operator()(const Counter<T>& x) const \
{return std::hash<T>()(x.get());} };
}
Index: libcxx/test/std/containers/unord/unord.set/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.set/merge.pass.cpp
@@ -0,0 +1,134 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_set
+
+// template <class C2>
+// void merge(unordered_set<key_type, C2, allocator_type>& source);
+
+#include <unordered_set>
+#include "Counter.h"
+
+template <class Set>
+bool set_equal(const Set& set, Set other)
+{
+ return set == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+template <class T>
+struct throw_hasher
+{
+ bool& should_throw_;
+
+ throw_hasher(bool& should_throw) : should_throw_(should_throw) {}
+
+ typedef size_t result_type;
+ typedef T argument_type;
+
+ size_t operator()(const T& p) const
+ {
+ if (should_throw_)
+ throw 0;
+ return std::hash<T>()(p);
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::unordered_set<int> src{1, 3, 5};
+ std::unordered_set<int> dst{2, 4, 5};
+ dst.merge(src);
+ assert(set_equal(src, {5}));
+ assert(set_equal(dst, {1, 2, 3, 4, 5}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::unordered_set<Counter<int>, throw_hasher<Counter<int>>> \
set_type; + set_type src({1, 3, 5}, 0, throw_hasher<Counter<int>>(do_throw));
+ set_type dst({2, 4, 5}, 0, throw_hasher<Counter<int>>(do_throw));
+
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(set_equal(src, set_type({1, 3, 5}, 0, \
throw_hasher<Counter<int>>(do_throw)))); + assert(set_equal(dst, set_type({2, \
4, 5}, 0, throw_hasher<Counter<int>>(do_throw)))); + }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct equal
+ {
+ equal() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs == rhs;
+ }
+ };
+ struct hasher
+ {
+ hasher() = default;
+ typedef Counter<int> argument_type;
+ typedef size_t result_type;
+ size_t operator()(const Counter<int>& p) const { return \
std::hash<Counter<int>>()(p); } + };
+ {
+ typedef std::unordered_set<Counter<int>, std::hash<Counter<int>>, \
std::equal_to<Counter<int>>> first_set_type; + typedef \
std::unordered_set<Counter<int>, hasher, equal> second_set_type; + typedef \
std::unordered_multiset<Counter<int>, hasher, equal> third_set_type; +
+ first_set_type first{1, 2, 3};
+ second_set_type second{2, 3, 4};
+ third_set_type third{1, 3};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(set_equal(first, {1, 2, 3, 4}));
+ assert(set_equal(second, {2, 3}));
+ assert(set_equal(third, {1, 3}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::unordered_set<int> first;
+ {
+ std::unordered_set<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::unordered_multiset<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/unord/unord.set/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.set/insert_extract.pass.cpp
@@ -0,0 +1,220 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_set
+
+#include <unordered_set>
+#include <type_traits>
+#include <iterator>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_irt
+{
+typedef std::unordered_set<int> int_set_type;
+using intIRT = int_set_type::insert_return_type;
+static_assert(std::is_move_constructible<intIRT>::value &&
+ std::is_move_assignable<intIRT>::value &&
+ std::is_default_constructible<intIRT>::value &&
+ std::is_destructible<intIRT>::value, "");
+
+typedef std::unordered_set<Counter<int>, std::hash<Counter<int>>,
+ std::equal_to<Counter<int>>,
+ min_allocator<Counter<int>>> set_type;
+using minIRT = set_type::insert_return_type;
+
+static_assert(std::is_move_constructible<minIRT>::value &&
+ std::is_move_assignable<minIRT>::value &&
+ std::is_default_constructible<minIRT>::value &&
+ std::is_destructible<minIRT>::value, "");
+
+static void doit()
+{
+ {
+ intIRT a, b;
+ std::swap(a, b);
+
+ minIRT c, d;
+ std::swap(c, d);
+ }
+
+ {
+ set_type st = {0};
+ set_type::node_type nh = st.extract(st.begin());
+ set_type::insert_return_type irt = st.insert(std::move(nh));
+ assert(irt.inserted);
+ assert(irt.position == st.begin());
+ assert(irt.node.empty());
+ }
+
+ {
+ set_type st = {0};
+ set_type::node_type nh = st.extract(st.begin());
+ st.insert(0);
+ set_type::insert_return_type irt = st.insert(std::move(nh));
+ assert(!irt.inserted);
+ assert(irt.position == st.begin());
+ assert(!irt.node.empty());
+ }
+
+ {
+ set_type st;
+ set_type::node_type nh;
+ set_type::insert_return_type irt = st.insert(std::move(nh));
+ assert(!irt.inserted);
+ assert(irt.position == st.end());
+ assert(irt.node.empty());
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_extract
+{
+using the_set = std::unordered_set<int>;
+
+static void doit()
+{
+ the_set s;
+ s.insert(1);
+ s.insert(2);
+ s.insert(3);
+ assert(s.size() == 3);
+
+ the_set::node_type handle = s.extract(2);
+ assert(s.size() == 2);
+ assert(s.count(1) == 1 && s.count(3) == 1);
+ the_set::iterator i = s.begin();
+ std::advance(i, 2);
+ assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::unordered_set<Counter<int>> set_type;
+
+static void doit()
+{
+ {
+ set_type dtc;
+ for (int i = 0; i != 10; ++i)
+ dtc.emplace(i);
+
+ assert(Counter_base::gConstructed == 10);
+ assert(dtc.size() == 10);
+
+ set_type::node_type nh3 = dtc.extract(Counter<int>(3));
+ set_type::node_type nh0 = dtc.extract(Counter<int>(0));
+ set_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+ assert(Counter_base::gConstructed == 10);
+ assert(dtc.size() == 7);
+
+ dtc.insert(std::move(nh3));
+ assert(dtc.size() == 8);
+
+ assert(Counter_base::gConstructed == 10);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::unordered_set<int, std::hash<int>, std::equal_to<int>, \
min_allocator<int>> set_type; +
+static void doit()
+{
+ set_type st;
+ st.insert(10);
+ set_type::node_type nt = st.extract(10);
+ assert(!nt.empty());
+ assert(st.empty());
+ st.insert(std::move(nt));
+ assert(st.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::unordered_set<Counter<int>, std::hash<Counter<int>>, \
std::equal_to<Counter<int>>, min_allocator<Counter<int>>> set_type; +
+static void doit()
+{
+ set_type::node_type nh;
+ assert(!static_cast<bool>(nh));
+
+ {
+ set_type st = {1, 2, 3, 4, 5};
+ assert(Counter_base::gConstructed == 5);
+ while (!st.empty())
+ {
+ nh = st.extract(st.begin());
+ }
+ assert(st.size() == 0);
+ assert(Counter_base::gConstructed == 1);
+ assert(static_cast<bool>(nh));
+ }
+
+ {
+ set_type other;
+ other.insert(std::move(nh));
+ assert(other.size() == 1);
+ assert(!static_cast<bool>(nh));
+ }
+
+ assert(Counter_base::gConstructed == 0);
+
+ {
+ set_type::node_type a, b;
+ std::swap(a, b);
+ set_type s = {42, 24};
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(s.begin());
+ a.swap(b);
+ assert(!static_cast<bool>(a) && static_cast<bool>(b));
+ s.insert(std::move(b));
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(s.begin());
+ b = s.extract(s.begin());
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ Counter<int>* aval = &a.value();
+ Counter<int>* bval = &b.value();
+ assert(aval->get() == 24);
+ assert(bval->get() == 42);
+
+ swap(a, b);
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ aval = &a.value();
+ bval = &b.value();
+ assert(aval->get() == 42);
+ assert(bval->get() == 24);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+ test_irt::doit();
+ test_extract::doit();
+ test_count_dtors::doit();
+ test_min_alloc::doit();
+ test_handle_operations::doit();
+}
Index: libcxx/test/std/containers/unord/unord.multiset/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.multiset/merge.pass.cpp
@@ -0,0 +1,134 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_multiset
+
+// template <class C2>
+// void merge(unordered_multiset<key_type, C2, allocator_type>& source);
+
+#include <unordered_set>
+#include "Counter.h"
+
+template <class Set>
+bool set_equal(const Set& set, Set other)
+{
+ return set == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+template <class T>
+struct throw_hasher
+{
+ bool& should_throw_;
+
+ throw_hasher(bool& should_throw) : should_throw_(should_throw) {}
+
+ typedef size_t result_type;
+ typedef T argument_type;
+
+ size_t operator()(const T& p) const
+ {
+ if (should_throw_)
+ throw 0;
+ return std::hash<T>()(p);
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::unordered_multiset<int> src{1, 3, 5};
+ std::unordered_multiset<int> dst{2, 4, 5};
+ dst.merge(src);
+ assert(set_equal(src, {}));
+ assert(set_equal(dst, {1, 2, 3, 4, 5, 5}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::unordered_multiset<Counter<int>, throw_hasher<Counter<int>>> \
set_type; + set_type src({1, 3, 5}, 0, throw_hasher<Counter<int>>(do_throw));
+ set_type dst({2, 4, 5}, 0, throw_hasher<Counter<int>>(do_throw));
+
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(set_equal(src, set_type({1, 3, 5}, 0, \
throw_hasher<Counter<int>>(do_throw)))); + assert(set_equal(dst, set_type({2, \
4, 5}, 0, throw_hasher<Counter<int>>(do_throw)))); + }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct equal
+ {
+ equal() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs == rhs;
+ }
+ };
+ struct hasher
+ {
+ hasher() = default;
+ typedef Counter<int> argument_type;
+ typedef size_t result_type;
+ size_t operator()(const Counter<int>& p) const { return \
std::hash<Counter<int>>()(p); } + };
+ {
+ typedef std::unordered_multiset<Counter<int>, std::hash<Counter<int>>, \
std::equal_to<Counter<int>>> first_set_type; + typedef \
std::unordered_multiset<Counter<int>, hasher, equal> second_set_type; + \
typedef std::unordered_set<Counter<int>, hasher, equal> third_set_type; +
+ first_set_type first{1, 2, 3};
+ second_set_type second{2, 3, 4};
+ third_set_type third{1, 3};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(set_equal(first, {1, 2, 3, 4, 2, 3, 1, 3}));
+ assert(set_equal(second, {}));
+ assert(set_equal(third, {}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::unordered_multiset<int> first;
+ {
+ std::unordered_multiset<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::unordered_set<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/unord/unord.multiset/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.multiset/insert_extract.pass.cpp
@@ -0,0 +1,158 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_multiset
+
+#include <unordered_set>
+#include <type_traits>
+#include <iterator>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_extract
+{
+using the_set = std::unordered_multiset<int>;
+
+static void doit()
+{
+ the_set s;
+ s.insert(1);
+ s.insert(2);
+ s.insert(3);
+ assert(s.size() == 3);
+
+ the_set::node_type handle = s.extract(2);
+ assert(s.size() == 2);
+ assert(s.count(1) == 1 && s.count(3) == 1);
+ the_set::iterator i = s.begin();
+ std::advance(i, 2);
+ assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::unordered_multiset<Counter<int>> set_type;
+
+static void doit()
+{
+ {
+ set_type dtc;
+ for (int i = 0; i != 10; ++i)
+ dtc.emplace(i);
+
+ assert(Counter_base::gConstructed == 10);
+ assert(dtc.size() == 10);
+
+ set_type::node_type nh3 = dtc.extract(Counter<int>(3));
+ set_type::node_type nh0 = dtc.extract(Counter<int>(0));
+ set_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+ assert(Counter_base::gConstructed == 10);
+ assert(dtc.size() == 7);
+
+ dtc.insert(std::move(nh3));
+ assert(dtc.size() == 8);
+
+ assert(Counter_base::gConstructed == 10);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::unordered_multiset<int, std::hash<int>, std::equal_to<int>, \
min_allocator<int>> set_type; +
+static void doit()
+{
+ set_type st;
+ st.insert(10);
+ set_type::node_type nt = st.extract(10);
+ assert(!nt.empty());
+ assert(st.empty());
+ st.insert(std::move(nt));
+ assert(st.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::unordered_multiset<Counter<int>, std::hash<Counter<int>>, \
std::equal_to<Counter<int>>, min_allocator<Counter<int>>> set_type; +
+static void doit()
+{
+ set_type::node_type nh;
+ assert(!static_cast<bool>(nh));
+
+ {
+ set_type st = {1, 2, 3, 4, 5};
+ assert(Counter_base::gConstructed == 5);
+ while (!st.empty())
+ {
+ nh = st.extract(st.begin());
+ }
+ assert(st.size() == 0);
+ assert(Counter_base::gConstructed == 1);
+ assert(static_cast<bool>(nh));
+ }
+
+ {
+ set_type other;
+ other.insert(std::move(nh));
+ assert(other.size() == 1);
+ assert(!static_cast<bool>(nh));
+ }
+
+ assert(Counter_base::gConstructed == 0);
+
+ {
+ set_type::node_type a, b;
+ std::swap(a, b);
+ set_type s = {42, 24};
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(s.begin());
+ a.swap(b);
+ assert(!static_cast<bool>(a) && static_cast<bool>(b));
+ s.insert(std::move(b));
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(s.begin());
+ b = s.extract(s.begin());
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ Counter<int>* aval = &a.value();
+ Counter<int>* bval = &b.value();
+ assert(aval->get() == 24);
+ assert(bval->get() == 42);
+
+ swap(a, b);
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ aval = &a.value();
+ bval = &b.value();
+ assert(aval->get() == 42);
+ assert(bval->get() == 24);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+ test_extract::doit();
+ test_count_dtors::doit();
+ test_min_alloc::doit();
+ test_handle_operations::doit();
+}
Index: libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp
@@ -0,0 +1,137 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_multimap
+
+// template <class C2>
+// void merge(unordered_multimap<key_type, C2, allocator_type>& source);
+
+#include <unordered_map>
+#include "Counter.h"
+
+template <class Map>
+bool map_equal(const Map& map, Map other)
+{
+ return map == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+template <class T>
+struct throw_hasher
+{
+ bool& should_throw_;
+
+ throw_hasher(bool& should_throw) : should_throw_(should_throw) {}
+
+ typedef size_t result_type;
+ typedef T argument_type;
+
+ size_t operator()(const T& p) const
+ {
+ if (should_throw_)
+ throw 0;
+ return std::hash<T>()(p);
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::unordered_multimap<int, int> src{{1, 0}, {3, 0}, {5, 0}};
+ std::unordered_multimap<int, int> dst{{2, 0}, {4, 0}, {5, 0}};
+ dst.merge(src);
+ assert(map_equal(src, {}));
+ assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {5, 0}}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::unordered_multimap<Counter<int>, int, \
throw_hasher<Counter<int>>> map_type; + map_type src({{1, 0}, {3, 0}, {5, 0}}, \
0, throw_hasher<Counter<int>>(do_throw)); + map_type dst({{2, 0}, {4, 0}, {5, \
0}}, 0, throw_hasher<Counter<int>>(do_throw)); +
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, 0, \
throw_hasher<Counter<int>>(do_throw)))); + assert(map_equal(dst, map_type({{2, \
0}, {4, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw)))); + }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct equal
+ {
+ equal() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs == rhs;
+ }
+ };
+ struct hasher
+ {
+ hasher() = default;
+ typedef Counter<int> argument_type;
+ typedef size_t result_type;
+ size_t operator()(const Counter<int>& p) const
+ {
+ return std::hash<Counter<int>>()(p);
+ }
+ };
+ {
+ typedef std::unordered_multimap<Counter<int>, int, std::hash<Counter<int>>, \
std::equal_to<Counter<int>>> first_map_type; + typedef \
std::unordered_multimap<Counter<int>, int, hasher, equal> second_map_type; + \
typedef std::unordered_map<Counter<int>, int, hasher, equal> third_map_type; +
+ first_map_type first{{1, 0}, {2, 0}, {3, 0}};
+ second_map_type second{{2, 0}, {3, 0}, {4, 0}};
+ third_map_type third{{1, 0}, {3, 0}};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {2, 0}, {3, 0}, {1, \
0}, {3, 0}})); + assert(map_equal(second, {}));
+ assert(map_equal(third, {}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::unordered_multimap<int, int> first;
+ {
+ std::unordered_multimap<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::unordered_map<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_extract.pass.cpp
@@ -0,0 +1,154 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_multimap
+
+#include <unordered_map>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_extract
+{
+using the_map = std::unordered_multimap<int, int>;
+
+static void doit()
+{
+ the_map s;
+ s.insert({1, 0});
+ s.insert({2, 0});
+ s.insert({3, 0});
+ assert(s.size() == 3);
+
+ the_map::node_type handle = s.extract(2);
+ assert(s.size() == 2);
+ assert(s.count(1) == 1 && s.count(3) == 1);
+ the_map::iterator i = s.begin();
+ std::advance(i, 2);
+ assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::unordered_multimap<Counter<int>, Counter<int>> map_type;
+
+static void doit()
+{
+ {
+ map_type dtc;
+ for (int i = 0; i != 10; ++i)
+ dtc.emplace(i, i + 10);
+
+ assert(Counter_base::gConstructed == 20);
+ assert(dtc.size() == 10);
+
+ map_type::node_type nh3 = dtc.extract(Counter<int>(3));
+ map_type::node_type nh0 = dtc.extract(Counter<int>(0));
+ map_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+ assert(static_cast<bool>(nh3) && static_cast<bool>(nh0) &&
+ static_cast<bool>(nh9));
+
+ assert(dtc.size() == 7);
+
+ dtc.insert(std::move(nh3));
+ assert(dtc.size() == 8);
+
+ assert(Counter_base::gConstructed == 20);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::unordered_multimap<int, int, std::hash<int>, std::equal_to<int>, \
min_allocator<std::pair<const int, int>>> map_type; +
+static void doit()
+{
+ map_type mp;
+ mp.insert({10, 10});
+ map_type::node_type nt = mp.extract(10);
+ assert(!nt.empty());
+ assert(mp.empty());
+ mp.insert(std::move(nt));
+ assert(mp.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::unordered_multimap<int, Counter<int>, std::hash<Counter<int>>, \
std::equal_to<Counter<int>>, min_allocator<std::pair<const int, Counter<int>>>> \
map_type; +
+static void doit()
+{
+ map_type::node_type nh;
+ assert(!static_cast<bool>(nh));
+
+ {
+ map_type mp = {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}};
+ assert(Counter_base::gConstructed == 5);
+ while (!mp.empty())
+ {
+ nh = mp.extract(mp.begin());
+ }
+ assert(mp.size() == 0);
+ assert(Counter_base::gConstructed == 1);
+ assert(static_cast<bool>(nh));
+ }
+
+ {
+ map_type other;
+ other.insert(std::move(nh));
+ assert(!static_cast<bool>(nh));
+ }
+
+ assert(Counter_base::gConstructed == 0);
+
+ {
+ map_type::node_type a, b;
+ std::swap(a, b);
+ map_type s = {{24, 101}, {42, 100}};
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(s.begin());
+ a.swap(b);
+ assert(!static_cast<bool>(a) && static_cast<bool>(b));
+ s.insert(std::move(b));
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(24);
+ b = s.extract(42);
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ assert(b.mapped() == 100 && b.key() == 42);
+ assert(a.mapped() == 101 && a.key() == 24);
+
+ swap(a, b);
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ assert(a.mapped() == 100 && a.key() == 42);
+ assert(b.mapped() == 101 && b.key() == 24);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+ test_extract::doit();
+ test_count_dtors::doit();
+ test_min_alloc::doit();
+ test_handle_operations::doit();
+}
Index: libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp
@@ -0,0 +1,137 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_map
+
+// template <class C2>
+// void merge(unordered_map<key_type, C2, allocator_type>& source);
+
+#include <unordered_map>
+#include "Counter.h"
+
+template <class Map>
+bool map_equal(const Map& map, Map other)
+{
+ return map == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+template <class T>
+struct throw_hasher
+{
+ bool& should_throw_;
+
+ throw_hasher(bool& should_throw) : should_throw_(should_throw) {}
+
+ typedef size_t result_type;
+ typedef T argument_type;
+
+ size_t operator()(const T& p) const
+ {
+ if (should_throw_)
+ throw 0;
+ return std::hash<T>()(p);
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::unordered_map<int, int> src{{1, 0}, {3, 0}, {5, 0}};
+ std::unordered_map<int, int> dst{{2, 0}, {4, 0}, {5, 0}};
+ dst.merge(src);
+ assert(map_equal(src, {{5,0}}));
+ assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::unordered_map<Counter<int>, int, throw_hasher<Counter<int>>> \
map_type; + map_type src({{1, 0}, {3, 0}, {5, 0}}, 0, \
throw_hasher<Counter<int>>(do_throw)); + map_type dst({{2, 0}, {4, 0}, {5, \
0}}, 0, throw_hasher<Counter<int>>(do_throw)); +
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, 0, \
throw_hasher<Counter<int>>(do_throw)))); + assert(map_equal(dst, map_type({{2, \
0}, {4, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw)))); + }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct equal
+ {
+ equal() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs == rhs;
+ }
+ };
+ struct hasher
+ {
+ hasher() = default;
+ typedef Counter<int> argument_type;
+ typedef size_t result_type;
+ size_t operator()(const Counter<int>& p) const
+ {
+ return std::hash<Counter<int>>()(p);
+ }
+ };
+ {
+ typedef std::unordered_map<Counter<int>, int, std::hash<Counter<int>>, \
std::equal_to<Counter<int>>> first_map_type; + typedef \
std::unordered_map<Counter<int>, int, hasher, equal> second_map_type; + \
typedef std::unordered_multimap<Counter<int>, int, hasher, equal> third_map_type; +
+ first_map_type first{{1, 0}, {2, 0}, {3, 0}};
+ second_map_type second{{2, 0}, {3, 0}, {4, 0}};
+ third_map_type third{{1, 0}, {3, 0}};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}}));
+ assert(map_equal(second, {{2, 0}, {3, 0}}));
+ assert(map_equal(third, {{1, 0}, {3, 0}}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::unordered_map<int, int> first;
+ {
+ std::unordered_map<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::unordered_multimap<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_extract.pass.cpp
@@ -0,0 +1,218 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_map
+
+#include <unordered_map>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_irt
+{
+typedef std::unordered_map<int, int> int_map_type;
+using intIRT = int_map_type::insert_return_type;
+static_assert(std::is_move_constructible<intIRT>::value &&
+ std::is_move_assignable<intIRT>::value &&
+ std::is_default_constructible<intIRT>::value &&
+ std::is_destructible<intIRT>::value, "");
+
+typedef std::unordered_map<
+ Counter<int>, Counter<int>, std::hash<Counter<int> >,
+ std::equal_to<Counter<int> >,
+ min_allocator<std::pair<const Counter<int>, Counter<int> > > >
+ map_type;
+using minIRT = map_type::insert_return_type;
+
+static_assert(std::is_move_constructible<minIRT>::value &&
+ std::is_move_assignable<minIRT>::value &&
+ std::is_default_constructible<minIRT>::value &&
+ std::is_destructible<minIRT>::value, "");
+
+static void doit()
+{
+ {
+ intIRT a, b;
+ std::swap(a, b);
+
+ minIRT c, d;
+ std::swap(c, d);
+ }
+
+ {
+ map_type mp = {{0, 0}};
+ map_type::node_type nh = mp.extract(mp.begin());
+ map_type::insert_return_type irt = mp.insert(std::move(nh));
+ assert(irt.inserted);
+ assert(irt.position == mp.begin());
+ assert(irt.node.empty());
+ }
+
+ {
+ map_type mp = {{0, 0}};
+ map_type::node_type nh = mp.extract(mp.begin());
+ mp.insert({0, 0});
+ map_type::insert_return_type irt = mp.insert(std::move(nh));
+ assert(!irt.inserted);
+ assert(irt.position == mp.begin());
+ assert(!irt.node.empty());
+ }
+
+ {
+ map_type mp;
+ map_type::node_type nh;
+ map_type::insert_return_type irt = mp.insert(std::move(nh));
+ assert(!irt.inserted);
+ assert(irt.position == mp.end());
+ assert(irt.node.empty());
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_extract
+{
+using the_map = std::unordered_map<int, int>;
+
+static void doit()
+{
+ the_map s;
+ s.insert({1, 0});
+ s.insert({2, 0});
+ s.insert({3, 0});
+ assert(s.size() == 3);
+
+ the_map::node_type handle = s.extract(2);
+ assert(s.size() == 2);
+ assert(s.count(1) == 1 && s.count(3) == 1);
+ the_map::iterator i = s.begin();
+ std::advance(i, 2);
+ assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::unordered_map<Counter<int>, Counter<int>> map_type;
+
+static void doit()
+{
+ {
+ map_type dtc;
+ for (int i = 0; i != 10; ++i)
+ dtc.emplace(i, i + 10);
+
+ assert(Counter_base::gConstructed == 20);
+ assert(dtc.size() == 10);
+
+ map_type::node_type nh3 = dtc.extract(Counter<int>(3));
+ map_type::node_type nh0 = dtc.extract(Counter<int>(0));
+ map_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+ assert(static_cast<bool>(nh3) && static_cast<bool>(nh0) &&
+ static_cast<bool>(nh9));
+
+ assert(dtc.size() == 7);
+
+ dtc.insert(std::move(nh3));
+ assert(dtc.size() == 8);
+
+ assert(Counter_base::gConstructed == 20);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, \
min_allocator<std::pair<const int, int>>> map_type; +
+static void doit()
+{
+ map_type mp;
+ mp.insert({10, 10});
+ map_type::node_type nt = mp.extract(10);
+ assert(!nt.empty());
+ assert(mp.empty());
+ mp.insert(std::move(nt));
+ assert(mp.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::unordered_map<int, Counter<int>, std::hash<Counter<int>>, \
std::equal_to<Counter<int>>, min_allocator<std::pair<const int, Counter<int>>>> \
map_type; +
+static void doit()
+{
+ map_type::node_type nh;
+ assert(!static_cast<bool>(nh));
+
+ {
+ map_type mp = {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}};
+ assert(Counter_base::gConstructed == 5);
+ while (!mp.empty())
+ {
+ nh = mp.extract(mp.begin());
+ }
+ assert(mp.size() == 0);
+ assert(Counter_base::gConstructed == 1);
+ assert(static_cast<bool>(nh));
+ }
+
+ {
+ map_type other;
+ other.insert(std::move(nh));
+ assert(!static_cast<bool>(nh));
+ }
+
+ assert(Counter_base::gConstructed == 0);
+
+ {
+ map_type::node_type a, b;
+ std::swap(a, b);
+ map_type s = {{24, 101}, {42, 100}};
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(s.begin());
+ a.swap(b);
+ assert(!static_cast<bool>(a) && static_cast<bool>(b));
+ s.insert(std::move(b));
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(24);
+ b = s.extract(42);
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ assert(b.mapped() == 100 && b.key() == 42);
+ assert(a.mapped() == 101 && a.key() == 24);
+
+ swap(a, b);
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ assert(a.mapped() == 100 && a.key() == 42);
+ assert(b.mapped() == 101 && b.key() == 24);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+ test_irt::doit();
+ test_extract::doit();
+ test_count_dtors::doit();
+ test_min_alloc::doit();
+ test_handle_operations::doit();
+}
Index: libcxx/test/std/containers/container.node/node_handle.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/container.node/node_handle.pass.cpp
@@ -0,0 +1,99 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+#include <unordered_set>
+#include <unordered_map>
+#include <set>
+#include <map>
+#include "min_allocator.h"
+
+using namespace std;
+
+// [container.node.overview] Table 83.
+template <class K, class T, class C1, class C2, class H1, class H2, class E1, class \
E2, class A_set, class A_map> +struct node_compatibility_table
+{
+ static constexpr bool value =
+ is_same_v<typename map<K, T, C1, A_map>::node_type, typename \
map<K, T, C2, A_map>::node_type> && + is_same_v<typename map<K, T, C1, \
A_map>::node_type, typename multimap<K, T, C2, A_map>::node_type> && + \
is_same_v<typename set<K, C1, A_set>::node_type, typename set<K, C2, \
A_set>::node_type> && + is_same_v<typename set<K, C1, A_set>::node_type, \
typename multiset<K, C2, A_set>::node_type> && + is_same_v<typename \
unordered_map<K, T, H1, E1, A_map>::node_type, typename unordered_map<K, T, H2, E2, \
A_map>::node_type> && + is_same_v<typename unordered_map<K, T, H1, E1, \
A_map>::node_type, typename unordered_multimap<K, T, H2, E2, A_map>::node_type> && + \
is_same_v<typename unordered_set<K, H1, E1, A_set>::node_type, typename \
unordered_set<K, H2, E2, A_set>::node_type> && + is_same_v<typename \
unordered_set<K, H1, E1, A_set>::node_type, typename unordered_multiset<K, H2, E2, \
A_set>::node_type>; +};
+
+template <class T> struct my_hash
+{
+ typedef T argument_type;
+ typedef size_t result_type;
+ my_hash() = default;
+ size_t operator()(const T&) const {return 0;}
+};
+
+template <class T> struct my_compare
+{
+ my_compare() = default;
+ bool operator()(const T&, const T&) const {return true;}
+};
+
+template <class T> struct my_equal
+{
+ my_equal() = default;
+ bool operator()(const T&, const T&) const {return true;}
+};
+
+struct Static
+{
+ Static() = default;
+ Static(const Static&) = delete;
+ Static(Static&&) = delete;
+ Static& operator=(const Static&) = delete;
+ Static& operator=(Static&&) = delete;
+};
+
+namespace std
+{
+template <> struct hash<Static>
+{
+ typedef Static argument_type;
+ typedef size_t result_type;
+ hash() = default;
+ size_t operator()(const Static&) const;
+};
+}
+
+static_assert(node_compatibility_table<
+ int, int, std::less<int>, std::less<int>, std::hash<int>,
+ std::hash<int>, std::equal_to<int>, std::equal_to<int>,
+ std::allocator<int>,
+ std::allocator<std::pair<const int, int> > >::value,
+ "");
+
+static_assert(
+ node_compatibility_table<int, int, std::less<int>, my_compare<int>,
+ std::hash<int>, my_hash<int>, std::equal_to<int>,
+ my_equal<int>, allocator<int>,
+ allocator<std::pair<const int, int> > >::value,
+ "");
+
+static_assert(node_compatibility_table<
+ Static, int, my_compare<Static>, std::less<Static>,
+ my_hash<Static>, std::hash<Static>, my_equal<Static>,
+ std::equal_to<Static>, min_allocator<Static>,
+ min_allocator<std::pair<const Static, int> > >::value,
+ "");
+
+int main()
+{
+ return 0;
+}
Index: libcxx/test/std/containers/associative/set/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/set/merge.pass.cpp
@@ -0,0 +1,124 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class set
+
+// template <class C2>
+// void merge(set<key_type, C2, allocator_type>& source);
+
+#include <set>
+#include "Counter.h"
+
+template <class Set>
+bool set_equal(const Set& set, Set other)
+{
+ return set == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+struct throw_comparator
+{
+ bool& should_throw_;
+
+ throw_comparator(bool& should_throw) : should_throw_(should_throw) {}
+
+ template <class T>
+ bool operator()(const T& lhs, const T& rhs) const
+ {
+ if (should_throw_)
+ throw 0;
+ return lhs < rhs;
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::set<int> src{1, 3, 5};
+ std::set<int> dst{2, 4, 5};
+ dst.merge(src);
+ assert(set_equal(src, {5}));
+ assert(set_equal(dst, {1, 2, 3, 4, 5}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::set<Counter<int>, throw_comparator> set_type;
+ set_type src({1, 3, 5}, throw_comparator(do_throw));
+ set_type dst({2, 4, 5}, throw_comparator(do_throw));
+
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(set_equal(src, set_type({1, 3, 5}, throw_comparator(do_throw))));
+ assert(set_equal(dst, set_type({2, 4, 5}, throw_comparator(do_throw))));
+ }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct comparator
+ {
+ comparator() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs < rhs;
+ }
+ };
+ {
+ typedef std::set<Counter<int>, std::less<Counter<int>>> first_set_type;
+ typedef std::set<Counter<int>, comparator> second_set_type;
+ typedef std::multiset<Counter<int>, comparator> third_set_type;
+
+ first_set_type first{1, 2, 3};
+ second_set_type second{2, 3, 4};
+ third_set_type third{1, 3};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(set_equal(first, {1, 2, 3, 4}));
+ assert(set_equal(second, {2, 3}));
+ assert(set_equal(third, {1, 3}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::set<int> first;
+ {
+ std::set<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::multiset<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/associative/set/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/set/insert_extract.pass.cpp
@@ -0,0 +1,218 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class set
+
+#include <set>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_irt
+{
+typedef std::set<int> int_set_type;
+using intIRT = int_set_type::insert_return_type;
+static_assert(std::is_move_constructible<intIRT>::value &&
+ std::is_move_assignable<intIRT>::value &&
+ std::is_default_constructible<intIRT>::value &&
+ std::is_destructible<intIRT>::value, "");
+
+typedef std::set<Counter<int>, std::less<Counter<int>>,
+ min_allocator<Counter<int>>> set_type;
+using minIRT = set_type::insert_return_type;
+
+static_assert(std::is_move_constructible<minIRT>::value &&
+ std::is_move_assignable<minIRT>::value &&
+ std::is_default_constructible<minIRT>::value &&
+ std::is_destructible<minIRT>::value, "");
+
+static void doit()
+{
+ {
+ intIRT a, b;
+ std::swap(a, b);
+
+ minIRT c, d;
+ std::swap(c, d);
+ }
+
+ {
+ set_type st = {0};
+ set_type::node_type nh = st.extract(st.begin());
+ set_type::insert_return_type irt = st.insert(std::move(nh));
+ assert(irt.inserted);
+ assert(irt.position == st.begin());
+ assert(irt.node.empty());
+ }
+
+ {
+ set_type st = {0};
+ set_type::node_type nh = st.extract(st.begin());
+ st.insert(0);
+ set_type::insert_return_type irt = st.insert(std::move(nh));
+ assert(!irt.inserted);
+ assert(irt.position == st.begin());
+ assert(!irt.node.empty());
+ }
+
+ {
+ set_type st;
+ set_type::node_type nh;
+ set_type::insert_return_type irt = st.insert(std::move(nh));
+ assert(!irt.inserted);
+ assert(irt.position == st.end());
+ assert(irt.node.empty());
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_extract
+{
+using the_set = std::set<int>;
+
+static void doit()
+{
+ the_set s;
+ s.insert(1);
+ s.insert(2);
+ s.insert(3);
+ assert(s.size() == 3);
+
+ the_set::node_type handle = s.extract(2);
+ assert(s.size() == 2);
+ the_set::iterator i = s.begin();
+ assert(*i == 1);
+ ++i;
+ assert(*i == 3);
+ ++i;
+ assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::set<Counter<int>> set_type;
+
+static void doit()
+{
+ {
+ set_type dtc;
+ for (int i = 0; i != 10; ++i)
+ dtc.emplace(i);
+
+ assert(Counter_base::gConstructed == 10);
+ assert(dtc.size() == 10);
+
+ set_type::node_type nh3 = dtc.extract(Counter<int>(3));
+ set_type::node_type nh0 = dtc.extract(Counter<int>(0));
+ set_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+ assert(Counter_base::gConstructed == 10);
+ assert(dtc.size() == 7);
+
+ dtc.insert(std::move(nh3));
+ assert(dtc.size() == 8);
+ assert(Counter_base::gConstructed == 10);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::set<int, std::less<int>, min_allocator<int>> set_type;
+
+static void doit()
+{
+ set_type st;
+ st.insert(10);
+ set_type::node_type nt = st.extract(10);
+ assert(!nt.empty());
+ assert(st.empty());
+ st.insert(std::move(nt));
+ assert(st.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::set<Counter<int>, std::less<Counter<int>>, min_allocator<Counter<int>>> \
set_type; +
+static void doit()
+{
+ set_type::node_type nh;
+ assert(!static_cast<bool>(nh));
+
+ {
+ set_type st = {1, 2, 3, 4, 5};
+ assert(Counter_base::gConstructed == 5);
+ while (!st.empty())
+ {
+ nh = st.extract(st.begin());
+ }
+ assert(st.size() == 0);
+ assert(Counter_base::gConstructed == 1);
+ assert(static_cast<bool>(nh));
+ }
+
+ {
+ set_type other;
+ other.insert(std::move(nh));
+ assert(!static_cast<bool>(nh));
+ }
+
+ assert(Counter_base::gConstructed == 0);
+
+ {
+ set_type::node_type a, b;
+ std::swap(a, b);
+ set_type s = {42, 24};
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(s.begin());
+ a.swap(b);
+ assert(!static_cast<bool>(a) && static_cast<bool>(b));
+ s.insert(std::move(b));
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(s.begin());
+ b = s.extract(s.begin());
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ Counter<int>* aval = &a.value();
+ Counter<int>* bval = &b.value();
+ assert(aval->get() == 24);
+ assert(bval->get() == 42);
+
+ swap(a, b);
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ aval = &a.value();
+ bval = &b.value();
+ assert(aval->get() == 42);
+ assert(bval->get() == 24);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+ test_irt::doit();
+ test_extract::doit();
+ test_count_dtors::doit();
+ test_min_alloc::doit();
+ test_handle_operations::doit();
+}
Index: libcxx/test/std/containers/associative/multiset/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/multiset/merge.pass.cpp
@@ -0,0 +1,133 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class multiset
+
+// template <class C2>
+// void merge(multiset<Key, C2, Allocator>& source);
+//
+// template <class C2>
+// void merge(multiset<Key, C2, Allocator>&& source);
+//
+// template <class C2>
+// void merge(set<Key, C2, Allocator>& source);
+//
+// template <class C2>
+// void merge(set<Key, C2, Allocator>&& source);
+
+#include <set>
+#include "Counter.h"
+
+template <class Set>
+bool set_equal(const Set& set, Set other)
+{
+ return set == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+struct throw_comparator
+{
+ bool& should_throw_;
+
+ throw_comparator(bool& should_throw) : should_throw_(should_throw) {}
+
+ template <class T>
+ bool operator()(const T& lhs, const T& rhs) const
+ {
+ if (should_throw_)
+ throw 0;
+ return lhs < rhs;
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::multiset<int> src{1, 3, 5};
+ std::multiset<int> dst{2, 4, 5};
+ dst.merge(src);
+ assert(set_equal(src, {}));
+ assert(set_equal(dst, {1, 2, 3, 4, 5, 5}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::multiset<Counter<int>, throw_comparator> set_type;
+ set_type src({1, 3, 5}, throw_comparator(do_throw));
+ set_type dst({2, 4, 5}, throw_comparator(do_throw));
+
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(set_equal(src, set_type({1, 3, 5}, throw_comparator(do_throw))));
+ assert(set_equal(dst, set_type({2, 4, 5}, throw_comparator(do_throw))));
+ }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct comparator
+ {
+ comparator() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs < rhs;
+ }
+ };
+ {
+ typedef std::multiset<Counter<int>, std::less<Counter<int>>> first_set_type;
+ typedef std::multiset<Counter<int>, comparator> second_set_type;
+ typedef std::set<Counter<int>, comparator> third_set_type;
+
+ first_set_type first{1, 2, 3};
+ second_set_type second{2, 3, 4};
+ third_set_type third{1, 3};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(set_equal(first, {1, 1, 2, 2, 3, 3, 3, 4}));
+ assert(set_equal(second, {}));
+ assert(set_equal(third, {}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::multiset<int> first;
+ {
+ std::multiset<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::set<int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/associative/multiset/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/multiset/insert_extract.pass.cpp
@@ -0,0 +1,200 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class multiset
+
+#include <set>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_extract
+{
+using the_set = std::multiset<int>;
+
+static void doit()
+{
+ the_set s;
+ s.insert(1);
+ s.insert(2);
+ s.insert(3);
+ assert(s.size() == 3);
+
+ the_set::node_type handle = s.extract(2);
+ assert(s.size() == 2);
+ the_set::iterator i = s.begin();
+ assert(*i == 1);
+ ++i;
+ assert(*i == 3);
+ ++i;
+ assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::multiset<Counter<int>> set_type;
+
+static void doit()
+{
+ {
+ set_type dtc;
+ for (int i = 0; i != 10; ++i)
+ dtc.emplace(i);
+
+ assert(Counter_base::gConstructed == 10);
+ assert(dtc.size() == 10);
+
+ set_type::node_type nh3 = dtc.extract(Counter<int>(3));
+ set_type::node_type nh0 = dtc.extract(Counter<int>(0));
+ set_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+ assert(Counter_base::gConstructed == 10);
+ assert(dtc.size() == 7);
+
+ dtc.insert(std::move(nh3));
+ assert(dtc.size() == 8);
+ assert(Counter_base::gConstructed == 10);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::multiset<int, std::less<int>, min_allocator<int>> set_type;
+
+static void doit()
+{
+ set_type st;
+ st.insert(10);
+ set_type::node_type nt = st.extract(10);
+ assert(!nt.empty());
+ assert(st.empty());
+ st.insert(std::move(nt));
+ assert(st.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::multiset<Counter<int>, std::less<Counter<int>>, \
min_allocator<Counter<int>>> set_type; +
+static void doit()
+{
+ set_type::node_type nh;
+ assert(!static_cast<bool>(nh));
+
+ {
+ set_type st = {1, 2, 3, 4, 5};
+ assert(Counter_base::gConstructed == 5);
+ while (!st.empty())
+ {
+ nh = st.extract(st.begin());
+ }
+ assert(st.size() == 0);
+ assert(Counter_base::gConstructed == 1);
+ assert(static_cast<bool>(nh));
+ }
+
+ {
+ set_type other;
+ other.insert(std::move(nh));
+ assert(!static_cast<bool>(nh));
+ }
+
+ assert(Counter_base::gConstructed == 0);
+
+ {
+ set_type::node_type a, b;
+ std::swap(a, b);
+ set_type s = {42, 24};
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(s.begin());
+ a.swap(b);
+ assert(!static_cast<bool>(a) && static_cast<bool>(b));
+ s.insert(std::move(b));
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(s.begin());
+ b = s.extract(s.begin());
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ Counter<int>* aval = &a.value();
+ Counter<int>* bval = &b.value();
+ assert(aval->get() == 24);
+ assert(bval->get() == 42);
+
+ swap(a, b);
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ aval = &a.value();
+ bval = &b.value();
+ assert(aval->get() == 42);
+ assert(bval->get() == 24);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_multi
+{
+typedef std::multiset<int> set_type;
+static void doit()
+{
+ {
+ set_type s = {1, 2, 2};
+ assert(s.count(2) == 2);
+ set_type::node_type nh = s.extract(2);
+ assert(s.count(1) == 1);
+ assert(s.count(2) == 1);
+ assert(s.size() == 2);
+ s.insert(std::move(nh));
+ assert(s.size() == 3);
+ assert(nh.empty());
+ }
+
+ {
+ set_type s = {0};
+ set_type::node_type nt = s.extract(s.begin());
+ assert(nt.value() == 0);
+ assert(s.size() == 0);
+ s.insert(std::move(nt));
+ }
+
+ {
+ set_type s = {1, 2};
+ set_type::node_type nh = s.extract(1);
+ s.insert(s.begin(), std::move(nh));
+ assert(nh.empty());
+ assert(s.size() == 2);
+ }
+
+ {
+ set_type s;
+ set_type::node_type nh;
+ set_type::iterator i = s.insert(std::move(nh));
+ assert(i == s.end());
+ }
+}
+}
+
+int main()
+{
+ test_extract::doit();
+ test_count_dtors::doit();
+ test_min_alloc::doit();
+ test_handle_operations::doit();
+ test_multi::doit();
+}
Index: libcxx/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp
@@ -0,0 +1,124 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class multimap
+
+// template <class C2>
+// void merge(multimap<key_type, C2, allocator_type>& source);
+
+#include <map>
+#include "Counter.h"
+
+template <class Map>
+bool map_equal(const Map& map, Map other)
+{
+ return map == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+struct throw_comparator
+{
+ bool& should_throw_;
+
+ throw_comparator(bool& should_throw) : should_throw_(should_throw) {}
+
+ template <class T>
+ bool operator()(const T& lhs, const T& rhs) const
+ {
+ if (should_throw_)
+ throw 0;
+ return lhs < rhs;
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::multimap<int, int> src{{1, 0}, {3, 0}, {5, 0}};
+ std::multimap<int, int> dst{{2, 0}, {4, 0}, {5, 0}};
+ dst.merge(src);
+ assert(map_equal(src, {}));
+ assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {5, 0}}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::multimap<Counter<int>, int, throw_comparator> map_type;
+ map_type src({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw));
+ map_type dst({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw));
+
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, \
throw_comparator(do_throw)))); + assert(map_equal(dst, map_type({{2, 0}, {4, \
0}, {5, 0}}, throw_comparator(do_throw)))); + }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct comparator
+ {
+ comparator() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs < rhs;
+ }
+ };
+ {
+ typedef std::multimap<Counter<int>, int, std::less<Counter<int>>> \
first_map_type; + typedef std::multimap<Counter<int>, int, comparator> \
second_map_type; + typedef std::map<Counter<int>, int, comparator> \
third_map_type; +
+ first_map_type first{{1, 0}, {2, 0}, {3, 0}};
+ second_map_type second{{2, 0}, {3, 0}, {4, 0}};
+ third_map_type third{{1, 0}, {3, 0}};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(map_equal(first, {{1, 0}, {1, 0}, {2, 0}, {2, 0}, {3, 0}, {3, 0}, {3, \
0}, {4, 0}})); + assert(map_equal(second, {}));
+ assert(map_equal(third, {}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::multimap<int, int> first;
+ {
+ std::multimap<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::multimap<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_extract.pass.cpp
@@ -0,0 +1,156 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class multimap
+
+#include <map>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_extract
+{
+using the_map = std::multimap<int, int>;
+
+static void doit()
+{
+ the_map s;
+ s.insert({1, 0});
+ s.insert({2, 0});
+ s.insert({3, 0});
+ assert(s.size() == 3);
+
+ the_map::node_type handle = s.extract(2);
+ assert(s.size() == 2);
+ the_map::iterator i = s.begin();
+ assert((*i).first == 1);
+ ++i;
+ assert((*i).first == 3);
+ ++i;
+ assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::multimap<Counter<int>, Counter<int>> map_type;
+
+static void doit()
+{
+ {
+ map_type dtc;
+ for (int i = 0; i != 10; ++i)
+ dtc.emplace(i, i + 10);
+
+ assert(Counter_base::gConstructed == 20);
+ assert(dtc.size() == 10);
+
+ map_type::node_type nh3 = dtc.extract(Counter<int>(3));
+ map_type::node_type nh0 = dtc.extract(Counter<int>(0));
+ map_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+ assert(static_cast<bool>(nh3) && static_cast<bool>(nh0) &&
+ static_cast<bool>(nh9));
+
+ assert(dtc.size() == 7);
+
+ dtc.insert(std::move(nh3));
+ assert(dtc.size() == 8);
+
+ assert(Counter_base::gConstructed == 20);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::multimap<int, int, std::less<int>, min_allocator<std::pair<const int, \
int>>> map_type; +
+static void doit()
+{
+ map_type mp;
+ mp.insert({10, 10});
+ map_type::node_type nt = mp.extract(10);
+ assert(!nt.empty());
+ assert(mp.empty());
+ mp.insert(std::move(nt));
+ assert(mp.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::multimap<int, Counter<int>, std::less<Counter<int>>, \
min_allocator<std::pair<const int, Counter<int>>>> map_type; +
+static void doit()
+{
+ map_type::node_type nh;
+ assert(!static_cast<bool>(nh));
+
+ {
+ map_type mp = {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}};
+ assert(Counter_base::gConstructed == 5);
+ while (!mp.empty())
+ {
+ nh = mp.extract(mp.begin());
+ }
+ assert(mp.size() == 0);
+ assert(Counter_base::gConstructed == 1);
+ assert(static_cast<bool>(nh));
+ }
+
+ {
+ map_type other;
+ other.insert(std::move(nh));
+ assert(!static_cast<bool>(nh));
+ }
+
+ assert(Counter_base::gConstructed == 0);
+
+ {
+ map_type::node_type a, b;
+ std::swap(a, b);
+ map_type s = {{24, 101}, {42, 100}};
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(s.begin());
+ a.swap(b);
+ assert(!static_cast<bool>(a) && static_cast<bool>(b));
+ s.insert(std::move(b));
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(s.begin());
+ b = s.extract(s.begin());
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ assert(b.mapped() == 100 && b.key() == 42);
+ assert(a.mapped() == 101 && a.key() == 24);
+
+ swap(a, b);
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ assert(a.mapped() == 100 && a.key() == 42);
+ assert(b.mapped() == 101 && b.key() == 24);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+ test_extract::doit();
+ test_count_dtors::doit();
+ test_min_alloc::doit();
+ test_handle_operations::doit();
+}
Index: libcxx/test/std/containers/associative/map/map.modifiers/merge.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/map/map.modifiers/merge.pass.cpp
@@ -0,0 +1,124 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class map
+
+// template <class C2>
+// void merge(map<key_type, C2, allocator_type>& source);
+
+#include <map>
+#include "Counter.h"
+
+template <class Map>
+bool map_equal(const Map& map, Map other)
+{
+ return map == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+struct throw_comparator
+{
+ bool& should_throw_;
+
+ throw_comparator(bool& should_throw) : should_throw_(should_throw) {}
+
+ template <class T>
+ bool operator()(const T& lhs, const T& rhs) const
+ {
+ if (should_throw_)
+ throw 0;
+ return lhs < rhs;
+ }
+};
+#endif
+
+int main()
+{
+ {
+ std::map<int, int> src{{1, 0}, {3, 0}, {5, 0}};
+ std::map<int, int> dst{{2, 0}, {4, 0}, {5, 0}};
+ dst.merge(src);
+ assert(map_equal(src, {{5,0}}));
+ assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}}));
+ }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+ {
+ bool do_throw = false;
+ typedef std::map<Counter<int>, int, throw_comparator> map_type;
+ map_type src({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw));
+ map_type dst({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw));
+
+ assert(Counter_base::gConstructed == 6);
+
+ do_throw = true;
+ try
+ {
+ dst.merge(src);
+ }
+ catch (int)
+ {
+ do_throw = false;
+ }
+ assert(!do_throw);
+ assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, \
throw_comparator(do_throw)))); + assert(map_equal(dst, map_type({{2, 0}, {4, \
0}, {5, 0}}, throw_comparator(do_throw)))); + }
+#endif
+ assert(Counter_base::gConstructed == 0);
+ struct comparator
+ {
+ comparator() = default;
+
+ bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+ {
+ return lhs < rhs;
+ }
+ };
+ {
+ typedef std::map<Counter<int>, int, std::less<Counter<int>>> first_map_type;
+ typedef std::map<Counter<int>, int, comparator> second_map_type;
+ typedef std::multimap<Counter<int>, int, comparator> third_map_type;
+
+ first_map_type first{{1, 0}, {2, 0}, {3, 0}};
+ second_map_type second{{2, 0}, {3, 0}, {4, 0}};
+ third_map_type third{{1, 0}, {3, 0}};
+
+ assert(Counter_base::gConstructed == 8);
+
+ first.merge(second);
+ first.merge(std::move(second));
+ first.merge(third);
+ first.merge(std::move(third));
+
+ assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}}));
+ assert(map_equal(second, {{2, 0}, {3, 0}}));
+ assert(map_equal(third, {{1, 0}, {3, 0}}));
+
+ assert(Counter_base::gConstructed == 8);
+ }
+ assert(Counter_base::gConstructed == 0);
+ {
+ std::map<int, int> first;
+ {
+ std::map<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ {
+ std::multimap<int, int> second;
+ first.merge(second);
+ first.merge(std::move(second));
+ }
+ }
+}
Index: libcxx/test/std/containers/associative/map/map.modifiers/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/map/map.modifiers/insert_extract.pass.cpp
@@ -0,0 +1,217 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class map
+
+#include <map>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_irt
+{
+typedef std::map<int, int> int_map_type;
+using intIRT = int_map_type::insert_return_type;
+static_assert(std::is_move_constructible<intIRT>::value &&
+ std::is_move_assignable<intIRT>::value &&
+ std::is_default_constructible<intIRT>::value &&
+ std::is_destructible<intIRT>::value, "");
+
+typedef std::map<Counter<int>, Counter<int>, std::less<Counter<int>>,
+ min_allocator<std::pair<const Counter<int>, Counter<int>>>> \
map_type; +using minIRT = map_type::insert_return_type;
+
+static_assert(std::is_move_constructible<minIRT>::value &&
+ std::is_move_assignable<minIRT>::value &&
+ std::is_default_constructible<minIRT>::value &&
+ std::is_destructible<minIRT>::value, "");
+
+static void doit()
+{
+ {
+ intIRT a, b;
+ std::swap(a, b);
+
+ minIRT c, d;
+ std::swap(c, d);
+ }
+
+ {
+ map_type mp = {{0, 0}};
+ map_type::node_type nh = mp.extract(mp.begin());
+ map_type::insert_return_type irt = mp.insert(std::move(nh));
+ assert(irt.inserted);
+ assert(irt.position == mp.begin());
+ assert(irt.node.empty());
+ }
+
+ {
+ map_type mp = {{0, 0}};
+ map_type::node_type nh = mp.extract(mp.begin());
+ mp.insert({0, 0});
+ map_type::insert_return_type irt = mp.insert(std::move(nh));
+ assert(!irt.inserted);
+ assert(irt.position == mp.begin());
+ assert(!irt.node.empty());
+ }
+
+ {
+ map_type mp;
+ map_type::node_type nh;
+ map_type::insert_return_type irt = mp.insert(std::move(nh));
+ assert(!irt.inserted);
+ assert(irt.position == mp.end());
+ assert(irt.node.empty());
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_extract
+{
+using the_map = std::map<int, int>;
+
+static void doit()
+{
+ the_map s;
+ s.insert({1, 0});
+ s.insert({2, 0});
+ s.insert({3, 0});
+ assert(s.size() == 3);
+
+ the_map::node_type handle = s.extract(2);
+ assert(s.size() == 2);
+ the_map::iterator i = s.begin();
+ assert((*i).first == 1);
+ ++i;
+ assert((*i).first == 3);
+ ++i;
+ assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::map<Counter<int>, Counter<int>> map_type;
+
+static void doit()
+{
+ {
+ map_type dtc;
+ for (int i = 0; i != 10; ++i)
+ dtc.emplace(i, i + 10);
+
+ assert(Counter_base::gConstructed == 20);
+ assert(dtc.size() == 10);
+
+ map_type::node_type nh3 = dtc.extract(Counter<int>(3));
+ map_type::node_type nh0 = dtc.extract(Counter<int>(0));
+ map_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+ assert(static_cast<bool>(nh3) && static_cast<bool>(nh0) &&
+ static_cast<bool>(nh9));
+
+ assert(dtc.size() == 7);
+
+ dtc.insert(std::move(nh3));
+ assert(dtc.size() == 8);
+
+ assert(Counter_base::gConstructed == 20);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::map<int, int, std::less<int>, min_allocator<std::pair<const int, int>>> \
map_type; +
+static void doit()
+{
+ map_type mp;
+ mp.insert({10, 10});
+ map_type::node_type nt = mp.extract(10);
+ assert(!nt.empty());
+ assert(mp.empty());
+ mp.insert(std::move(nt));
+ assert(mp.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::map<int, Counter<int>, std::less<Counter<int>>, \
min_allocator<std::pair<const int, Counter<int>>>> map_type; +
+static void doit()
+{
+ map_type::node_type nh;
+ assert(!static_cast<bool>(nh));
+
+ {
+ map_type mp = {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}};
+ assert(Counter_base::gConstructed == 5);
+ while (!mp.empty())
+ {
+ nh = mp.extract(mp.begin());
+ }
+ assert(mp.size() == 0);
+ assert(Counter_base::gConstructed == 1);
+ assert(static_cast<bool>(nh));
+ }
+
+ {
+ map_type other;
+ other.insert(std::move(nh));
+ assert(!static_cast<bool>(nh));
+ }
+
+ assert(Counter_base::gConstructed == 0);
+
+ {
+ map_type::node_type a, b;
+ std::swap(a, b);
+ map_type s = {{24, 101}, {42, 100}};
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(s.begin());
+ a.swap(b);
+ assert(!static_cast<bool>(a) && static_cast<bool>(b));
+ s.insert(std::move(b));
+ assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+ a = s.extract(s.begin());
+ b = s.extract(s.begin());
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ assert(b.mapped() == 100 && b.key() == 42);
+ assert(a.mapped() == 101 && a.key() == 24);
+
+ swap(a, b);
+ assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+ assert(a.mapped() == 100 && a.key() == 42);
+ assert(b.mapped() == 101 && b.key() == 24);
+ }
+
+ assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+ test_irt::doit();
+ test_extract::doit();
+ test_count_dtors::doit();
+ test_min_alloc::doit();
+ test_handle_operations::doit();
+}
Index: libcxx/include/unordered_set
===================================================================
--- libcxx/include/unordered_set
+++ libcxx/include/unordered_set
@@ -321,6 +321,7 @@
#include <__config>
#include <__hash_table>
+#include <__node_handle>
#include <functional>
#include <__debug>
@@ -331,6 +332,9 @@
_LIBCPP_BEGIN_NAMESPACE_STD
+template <class _Value, class _Hash, class _Pred, class _Alloc>
+class unordered_multiset;
+
template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
class _Alloc = allocator<_Value> >
class _LIBCPP_TEMPLATE_VIS unordered_set
@@ -363,6 +367,13 @@
typedef typename __table::const_local_iterator local_iterator;
typedef typename __table::const_local_iterator const_local_iterator;
+#if _LIBCPP_STD_VER > 14
+ typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
+ typedef __insert_return_type<iterator, node_type> insert_return_type;
+#endif
+
+ __table& __get_table() { return __table_; }
+
_LIBCPP_INLINE_VISIBILITY
unordered_set()
_NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
@@ -541,6 +552,67 @@
_LIBCPP_INLINE_VISIBILITY
void clear() _NOEXCEPT {__table_.clear();}
+#if _LIBCPP_STD_VER > 14
+ _LIBCPP_INLINE_VISIBILITY
+ insert_return_type insert(node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to \
unordered_set::insert()"); + return __table_.template \
__node_handle_insert_unique< + node_type, \
insert_return_type>(_VSTD::move(__nh)); + }
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(const_iterator, node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to \
unordered_set::insert()"); + return insert(_VSTD::move(__nh)).position;
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(key_type const& __key)
+ {
+ return __table_.template __node_handle_extract_unique<node_type>(__key);
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(const_iterator __it)
+ {
+ return __table_.template __node_handle_extract_unique<node_type>(__it);
+ }
+
+ template<class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __table_.__node_handle_merge_unique(__source.__get_table());
+ }
+ template<class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __table_.__node_handle_merge_unique(__source.__get_table());
+ }
+ template<class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __table_.__node_handle_merge_unique(__source.__get_table());
+ }
+ template<class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __table_.__node_handle_merge_unique(__source.__get_table());
+ }
+#endif
+
_LIBCPP_INLINE_VISIBILITY
void swap(unordered_set& __u)
_NOEXCEPT_(__is_nothrow_swappable<__table>::value)
@@ -883,6 +955,12 @@
typedef typename __table::const_local_iterator local_iterator;
typedef typename __table::const_local_iterator const_local_iterator;
+#if _LIBCPP_STD_VER > 14
+ typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
+#endif
+
+ __table& __get_table() { return __table_; }
+
_LIBCPP_INLINE_VISIBILITY
unordered_multiset()
_NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
@@ -1019,6 +1097,69 @@
_LIBCPP_INLINE_VISIBILITY
void insert(_InputIterator __first, _InputIterator __last);
+#if _LIBCPP_STD_VER > 14
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(const_iterator __position)
+ {
+ return __table_.template __node_handle_extract_multi<node_type>(
+ __position);
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(key_type const& __key)
+ {
+ return __table_.template __node_handle_extract_multi<node_type>(__key);
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to \
unordered_multiset::insert()"); + return __table_.template \
__node_handle_insert_multi<node_type>( + _VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(const_iterator __hint, node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to \
unordered_multiset::insert()"); + return __table_.template \
__node_handle_insert_multi<node_type>( + __hint, _VSTD::move(__nh));
+ }
+
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
+#endif
+
_LIBCPP_INLINE_VISIBILITY
iterator erase(const_iterator __p) {return __table_.erase(__p);}
_LIBCPP_INLINE_VISIBILITY
Index: libcxx/include/unordered_map
===================================================================
--- libcxx/include/unordered_map
+++ libcxx/include/unordered_map
@@ -367,6 +367,7 @@
#include <__config>
#include <__hash_table>
+#include <__node_handle>
#include <functional>
#include <stdexcept>
#include <tuple>
@@ -379,6 +380,9 @@
_LIBCPP_BEGIN_NAMESPACE_STD
+template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
+class unordered_multimap;
+
template <class _Key, class _Cp, class _Hash, bool _IsEmpty>
class __unordered_map_hasher
: private _Hash
@@ -837,6 +841,13 @@
typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
typedef __hash_map_const_iterator<typename __table::const_local_iterator> \
const_local_iterator;
+#if _LIBCPP_STD_VER > 14
+ typedef __map_node_handle<__node, allocator_type> node_type;
+ typedef __insert_return_type<iterator, node_type> insert_return_type;
+#endif
+
+ __table& __get_table() { return __table_; }
+
_LIBCPP_INLINE_VISIBILITY
unordered_map()
_NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
@@ -1130,7 +1141,70 @@
iterator erase(const_iterator __first, const_iterator __last)
{return __table_.erase(__first.__i_, __last.__i_);}
_LIBCPP_INLINE_VISIBILITY
- void clear() _NOEXCEPT {__table_.clear();}
+ void clear() _NOEXCEPT {__table_.clear();}
+
+#if _LIBCPP_STD_VER > 14
+ _LIBCPP_INLINE_VISIBILITY
+ insert_return_type insert(node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to \
unordered_map::insert()"); + return __table_.template \
__node_handle_insert_unique< + node_type, \
insert_return_type>(_VSTD::move(__nh)); + }
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(const_iterator __hint, node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to \
unordered_map::insert()"); + return __table_.template \
__node_handle_insert_unique<node_type>( + __hint.__i_, _VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(key_type const& __key)
+ {
+ return __table_.template __node_handle_extract_unique<node_type>(__key);
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(const_iterator __it)
+ {
+ return __table_.template __node_handle_extract_unique<node_type>(
+ __it.__i_);
+ }
+
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& \
__source) + {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_unique(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& \
__source) + {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_unique(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& \
__source) + {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_unique(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& \
__source) + {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_unique(__source.__get_table());
+ }
+#endif
_LIBCPP_INLINE_VISIBILITY
void swap(unordered_map& __u)
@@ -1584,6 +1658,12 @@
typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
typedef __hash_map_const_iterator<typename __table::const_local_iterator> \
const_local_iterator;
+#if _LIBCPP_STD_VER > 14
+ typedef __map_node_handle<__node, allocator_type> node_type;
+#endif
+
+ __table& __get_table() { return __table_; }
+
_LIBCPP_INLINE_VISIBILITY
unordered_multimap()
_NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
@@ -1757,6 +1837,69 @@
_LIBCPP_INLINE_VISIBILITY
void clear() _NOEXCEPT {__table_.clear();}
+#if _LIBCPP_STD_VER > 14
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to \
unordered_multimap::insert()"); + return __table_.template \
__node_handle_insert_multi<node_type>( + _VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(const_iterator __hint, node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to \
unordered_multimap::insert()"); + return __table_.template \
__node_handle_insert_multi<node_type>( + __hint.__i_, _VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(key_type const& __key)
+ {
+ return __table_.template __node_handle_extract_multi<node_type>(__key);
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(const_iterator __it)
+ {
+ return __table_.template __node_handle_extract_multi<node_type>(
+ __it.__i_);
+ }
+
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& \
__source) + {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& \
__source) + {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& \
__source) + {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
+ template <class _H2, class _P2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& \
__source) + {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __table_.__node_handle_merge_multi(__source.__get_table());
+ }
+#endif
+
_LIBCPP_INLINE_VISIBILITY
void swap(unordered_multimap& __u)
_NOEXCEPT_(__is_nothrow_swappable<__table>::value)
Index: libcxx/include/set
===================================================================
--- libcxx/include/set
+++ libcxx/include/set
@@ -387,14 +387,18 @@
#include <__config>
#include <__tree>
+#include <__node_handle>
#include <functional>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#pragma GCC system_header
#endif
_LIBCPP_BEGIN_NAMESPACE_STD
+template <class _Key, class _Compare, class _Allocator>
+class multiset;
+
template <class _Key, class _Compare = less<_Key>,
class _Allocator = allocator<_Key> >
class _LIBCPP_TEMPLATE_VIS set
@@ -429,6 +433,13 @@
typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
+#if _LIBCPP_STD_VER > 14
+ typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
+ typedef __insert_return_type<iterator, node_type> insert_return_type;
+#endif
+
+ __base& __get_tree() { return __tree_; }
+
_LIBCPP_INLINE_VISIBILITY
set()
_NOEXCEPT_(
@@ -634,6 +645,67 @@
_LIBCPP_INLINE_VISIBILITY
void clear() _NOEXCEPT {__tree_.clear();}
+#if _LIBCPP_STD_VER > 14
+ _LIBCPP_INLINE_VISIBILITY
+ insert_return_type insert(node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to set::insert()");
+ return __tree_.template __node_handle_insert_unique<
+ node_type, insert_return_type>(_VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(const_iterator __hint, node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to set::insert()");
+ return __tree_.template __node_handle_insert_unique<node_type>(
+ __hint, _VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(key_type const& __key)
+ {
+ return __tree_.template __node_handle_extract_unique<node_type>(__key);
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(const_iterator __it)
+ {
+ return __tree_.template __node_handle_extract_unique<node_type>(__it);
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(set<key_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(set<key_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multiset<key_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multiset<key_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
+#endif
+
_LIBCPP_INLINE_VISIBILITY
void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
{__tree_.swap(__s.__tree_);}
@@ -838,6 +910,12 @@
typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
+#if _LIBCPP_STD_VER > 14
+ typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
+#endif
+
+ __base& __get_tree() { return __tree_; }
+
// construct/copy/destroy:
_LIBCPP_INLINE_VISIBILITY
multiset()
@@ -1042,6 +1120,67 @@
_LIBCPP_INLINE_VISIBILITY
void clear() _NOEXCEPT {__tree_.clear();}
+#if _LIBCPP_STD_VER > 14
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to multiset::insert()");
+ return __tree_.template __node_handle_insert_multi<node_type>(
+ _VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(const_iterator __hint, node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to multiset::insert()");
+ return __tree_.template __node_handle_insert_multi<node_type>(
+ __hint, _VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(key_type const& __key)
+ {
+ return __tree_.template __node_handle_extract_multi<node_type>(__key);
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(const_iterator __it)
+ {
+ return __tree_.template __node_handle_extract_multi<node_type>(__it);
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multiset<key_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multiset<key_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(set<key_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(set<key_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
+#endif
+
_LIBCPP_INLINE_VISIBILITY
void swap(multiset& __s)
_NOEXCEPT_(__is_nothrow_swappable<__base>::value)
Index: libcxx/include/map
===================================================================
--- libcxx/include/map
+++ libcxx/include/map
@@ -440,6 +440,7 @@
#include <__config>
#include <__tree>
+#include <__node_handle>
#include <iterator>
#include <memory>
#include <utility>
@@ -901,6 +902,13 @@
typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
+#if _LIBCPP_STD_VER > 14
+ typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
+ typedef __insert_return_type<iterator, node_type> insert_return_type;
+#endif
+
+ __base& __get_tree() { return __tree_; }
+
_LIBCPP_INLINE_VISIBILITY
map()
_NOEXCEPT_(
@@ -1248,6 +1256,67 @@
_LIBCPP_INLINE_VISIBILITY
void clear() _NOEXCEPT {__tree_.clear();}
+#if _LIBCPP_STD_VER > 14
+ _LIBCPP_INLINE_VISIBILITY
+ insert_return_type insert(node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to map::insert()");
+ return __tree_.template __node_handle_insert_unique<
+ node_type, insert_return_type>(_VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(const_iterator __hint, node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to map::insert()");
+ return __tree_.template __node_handle_insert_unique<node_type>(
+ __hint.__i_, _VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(key_type const& __key)
+ {
+ return __tree_.template __node_handle_extract_unique<node_type>(__key);
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(const_iterator __it)
+ {
+ return __tree_.template __node_handle_extract_unique<node_type>(__it.__i_);
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(map<key_type, mapped_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(map<key_type, mapped_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multimap<key_type, mapped_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multimap<key_type, mapped_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ __tree_.__node_handle_merge_unique(__source.__get_tree());
+ }
+#endif
+
_LIBCPP_INLINE_VISIBILITY
void swap(map& __m)
_NOEXCEPT_(__is_nothrow_swappable<__base>::value)
@@ -1557,6 +1626,12 @@
typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
+#if _LIBCPP_STD_VER > 14
+ typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
+#endif
+
+ __base& __get_tree() { return __tree_; }
+
_LIBCPP_INLINE_VISIBILITY
multimap()
_NOEXCEPT_(
@@ -1795,6 +1870,69 @@
_LIBCPP_INLINE_VISIBILITY
iterator erase(const_iterator __f, const_iterator __l)
{return __tree_.erase(__f.__i_, __l.__i_);}
+
+#if _LIBCPP_STD_VER > 14
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to multimap::insert()");
+ return __tree_.template __node_handle_insert_multi<node_type>(
+ _VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ iterator insert(const_iterator __hint, node_type&& __nh)
+ {
+ _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+ "node_type with incompatible allocator passed to multimap::insert()");
+ return __tree_.template __node_handle_insert_multi<node_type>(
+ __hint.__i_, _VSTD::move(__nh));
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(key_type const& __key)
+ {
+ return __tree_.template __node_handle_extract_multi<node_type>(__key);
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ node_type extract(const_iterator __it)
+ {
+ return __tree_.template __node_handle_extract_multi<node_type>(
+ __it.__i_);
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multimap<key_type, mapped_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(multimap<key_type, mapped_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(map<key_type, mapped_type, _C2, allocator_type>& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
+ template <class _C2>
+ _LIBCPP_INLINE_VISIBILITY
+ void merge(map<key_type, mapped_type, _C2, allocator_type>&& __source)
+ {
+ _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+ "merging container with incompatible allocator");
+ return __tree_.__node_handle_merge_multi(__source.__get_tree());
+ }
+#endif
+
_LIBCPP_INLINE_VISIBILITY
void clear() {__tree_.clear();}
Index: libcxx/include/__tree
===================================================================
--- libcxx/include/__tree
+++ libcxx/include/__tree
@@ -800,6 +800,16 @@
template <class> friend class __map_node_destructor;
};
+#if _LIBCPP_STD_VER > 14
+template <class _NodeType, class _Alloc>
+struct __generic_container_node_destructor;
+template <class _Tp, class _VoidPtr, class _Alloc>
+struct __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc>
+ : __tree_node_destructor<_Alloc>
+{
+ using __tree_node_destructor<_Alloc>::__tree_node_destructor;
+};
+#endif
template <class _Tp, class _NodePtr, class _DiffType>
class _LIBCPP_TEMPLATE_VIS __tree_iterator
@@ -1342,6 +1352,42 @@
iterator __node_insert_multi(__node_pointer __nd);
iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
+
+ _LIBCPP_INLINE_VISIBILITY iterator __remove_node_pointer(__node_pointer);
+
+#if _LIBCPP_STD_VER > 14
+ template <class _NodeHandle, class _InsertReturnType>
+ _LIBCPP_INLINE_VISIBILITY
+ _InsertReturnType __node_handle_insert_unique(_NodeHandle&&);
+ template <class _NodeHandle>
+ _LIBCPP_INLINE_VISIBILITY
+ iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&);
+ template <class _NodeHandle>
+ _LIBCPP_INLINE_VISIBILITY
+ _NodeHandle __node_handle_extract_unique(key_type const&);
+ template <class _NodeHandle>
+ _LIBCPP_INLINE_VISIBILITY
+ _NodeHandle __node_handle_extract_unique(const_iterator);
+ template <class _Tree>
+ _LIBCPP_INLINE_VISIBILITY
+ void __node_handle_merge_unique(_Tree& __source);
+
+ template <class _NodeHandle>
+ _LIBCPP_INLINE_VISIBILITY
+ iterator __node_handle_insert_multi(_NodeHandle&&);
+ template <class _NodeHandle>
+ _LIBCPP_INLINE_VISIBILITY
+ iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&);
+ template <class _NodeHandle>
+ _LIBCPP_INLINE_VISIBILITY
+ _NodeHandle __node_handle_extract_multi(key_type const&);
+ template <class _NodeHandle>
+ _NodeHandle __node_handle_extract_multi(const_iterator);
+ template <class _Tree>
+ _LIBCPP_INLINE_VISIBILITY
+ void __node_handle_merge_multi(_Tree& __source);
+#endif
+
iterator erase(const_iterator __p);
iterator erase(const_iterator __f, const_iterator __l);
template <class _Key>
@@ -2351,17 +2397,201 @@
template <class _Tp, class _Compare, class _Allocator>
typename __tree<_Tp, _Compare, _Allocator>::iterator
-__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
+__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr)
{
- __node_pointer __np = __p.__get_np();
- iterator __r(__p.__ptr_);
+ iterator __r(__ptr);
++__r;
- if (__begin_node() == __p.__ptr_)
+ if (__begin_node() == __ptr)
__begin_node() = __r.__ptr_;
--size();
- __node_allocator& __na = __node_alloc();
__tree_remove(__end_node()->__left_,
- static_cast<__node_base_pointer>(__np));
+ static_cast<__node_base_pointer>(__ptr));
+ return __r;
+}
+
+#if _LIBCPP_STD_VER > 14
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle, class _InsertReturnType>
+_InsertReturnType
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(
+ _NodeHandle&& __nh)
+{
+ if (__nh.empty())
+ return _InsertReturnType{end(), false, _NodeHandle()};
+
+ __node_pointer __ptr = __nh.__ptr_;
+ __parent_pointer __parent;
+ __node_base_pointer& __child = __find_equal(__parent,
+ __ptr->__value_);
+ if (__child != nullptr)
+ return _InsertReturnType{
+ iterator(static_cast<__node_pointer>(__child)),
+ false, _VSTD::move(__nh)};
+
+ __insert_node_at(__parent, __child,
+ static_cast<__node_base_pointer>(__ptr));
+ __nh.__release();
+ return _InsertReturnType{iterator(__ptr), true, _NodeHandle()};
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(
+ const_iterator __hint, _NodeHandle&& __nh)
+{
+ if (__nh.empty())
+ return end();
+
+ __node_pointer __ptr = __nh.__ptr_;
+ __parent_pointer __parent;
+ __node_base_pointer __dummy;
+ __node_base_pointer& __child = __find_equal(__hint, __parent, __dummy,
+ __ptr->__value_);
+ __node_pointer __r = static_cast<__node_pointer>(__child);
+ if (__child == nullptr)
+ {
+ __insert_node_at(__parent, __child,
+ static_cast<__node_base_pointer>(__ptr));
+ __r = __ptr;
+ __nh.__release();
+ }
+ return iterator(__r);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_NodeHandle
+__tree<_Tp, _Compare, _Allocator>::__node_handle_extract_unique(key_type const& \
__key) +{
+ iterator __it = find(__key);
+ if (__it == end())
+ return _NodeHandle();
+ return __node_handle_extract_unique<_NodeHandle>(__it);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_NodeHandle
+__tree<_Tp, _Compare, _Allocator>::__node_handle_extract_unique(const_iterator __p)
+{
+ __node_pointer __np = __p.__get_np();
+ __remove_node_pointer(__np);
+ __np->__left_ = nullptr;
+ __np->__right_ = nullptr;
+ return _NodeHandle(__np, __alloc());
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _Tree>
+void
+__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source)
+{
+ static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, \
""); +
+ for (typename _Tree::iterator __i = __source.begin();
+ __i != __source.end();)
+ {
+ __node_pointer __src_ptr = __i.__get_np();
+ __parent_pointer __parent;
+ __node_base_pointer& __child = __find_equal(
+ __parent, _NodeTypes::__get_key(__src_ptr->__value_));
+ ++__i;
+ if (__child != nullptr)
+ continue;
+ __source.__remove_node_pointer(__src_ptr);
+ __src_ptr->__left_ = nullptr;
+ __src_ptr->__right_ = nullptr;
+ __insert_node_at(__parent, __child,
+ static_cast<__node_base_pointer>(__src_ptr));
+ }
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(_NodeHandle&& __nh)
+{
+ if (__nh.empty())
+ return end();
+ __node_pointer __ptr = __nh.__ptr_;
+ __parent_pointer __parent;
+ __node_base_pointer& __child = __find_leaf_high(
+ __parent, _NodeTypes::__get_key(__ptr->__value_));
+ __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
+ __nh.__release();
+ return iterator(__ptr);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(
+ const_iterator __hint, _NodeHandle&& __nh)
+{
+ if (__nh.empty())
+ return end();
+
+ __node_pointer __ptr = __nh.__ptr_;
+ __parent_pointer __parent;
+ __node_base_pointer& __child = __find_leaf(__hint, __parent,
+ \
_NodeTypes::__get_key(__ptr->__value_)); + __insert_node_at(__parent, __child, \
static_cast<__node_base_pointer>(__ptr)); + __nh.__release();
+ return iterator(__ptr);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_NodeHandle
+__tree<_Tp, _Compare, _Allocator>::__node_handle_extract_multi(key_type const& \
__key) +{
+ iterator __i = find(__key);
+ if (__i == end())
+ return _NodeHandle();
+ return __node_handle_extract_multi<_NodeHandle>(__i);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_NodeHandle
+__tree<_Tp, _Compare, _Allocator>::__node_handle_extract_multi(const_iterator __p)
+{
+ __node_pointer __np = __p.__get_np();
+ __remove_node_pointer(__np);
+ return _NodeHandle(__np, __alloc());
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _Tree>
+void
+__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source)
+{
+ static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, \
""); +
+ for (typename _Tree::iterator __i = __source.begin();
+ __i != __source.end();)
+ {
+ __node_pointer __src_ptr = __i.__get_np();
+ __parent_pointer __parent;
+ __node_base_pointer& __child = __find_leaf_high(
+ __parent, _NodeTypes::__get_key(__src_ptr->__value_));
+ ++__i;
+ __source.__remove_node_pointer(__src_ptr);
+ __insert_node_at(__parent, __child,
+ static_cast<__node_base_pointer>(__src_ptr));
+ }
+}
+
+#endif // _LIBCPP_STD_VER > 14
+
+template <class _Tp, class _Compare, class _Allocator>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
+{
+ __node_pointer __np = __p.__get_np();
+ iterator __r = __remove_node_pointer(__np);
+ __node_allocator& __na = __node_alloc();
__node_traits::destroy(__na, _NodeTypes::__get_ptr(
const_cast<__node_value_type&>(*__p)));
__node_traits::deallocate(__na, __np, 1);
Index: libcxx/include/__node_handle
===================================================================
--- /dev/null
+++ libcxx/include/__node_handle
@@ -0,0 +1,234 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___NODE_HANDLE
+#define _LIBCPP___NODE_HANDLE
+
+#include <__config>
+#include <memory>
+#include <optional>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 14
+
+#define __cpp_lib_node_extract 201606L
+
+// Specialized in __tree & __hash_table for their _NodeType.
+template <class _NodeType, class _Alloc>
+struct __generic_container_node_destructor;
+
+template <class _NodeType, class _Alloc>
+class __node_handle_base
+{
+public:
+ typedef allocator_traits<_Alloc> __alloc_traits;
+ typedef typename __rebind_pointer<typename __alloc_traits::void_pointer,
+ _NodeType>::type
+ __node_pointer_type;
+
+ typedef _Alloc allocator_type;
+ typedef typename _NodeType::__node_value_type value_type;
+
+ __node_pointer_type __ptr_ = nullptr;
+ optional<allocator_type> __alloc_;
+
+ _LIBCPP_INLINE_VISIBILITY
+ void __release()
+ {
+ __ptr_ = nullptr;
+ __alloc_ = _VSTD::nullopt;
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ void __destroy_node_pointer()
+ {
+ if (__ptr_ != nullptr)
+ {
+ typedef typename __allocator_traits_rebind<
+ allocator_type, _NodeType>::type __node_alloc_type;
+ __node_alloc_type __alloc(*__alloc_);
+ __generic_container_node_destructor<_NodeType, __node_alloc_type>(
+ __alloc, true)(__ptr_);
+ __ptr_ = nullptr;
+ }
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ __node_handle_base() = default;
+
+ _LIBCPP_INLINE_VISIBILITY
+ __node_handle_base(__node_pointer_type __ptr, allocator_type const& __alloc)
+ : __ptr_(__ptr), __alloc_(__alloc)
+ {
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ __node_handle_base(__node_handle_base&& __other) noexcept
+ : __ptr_(_VSTD::move(__other.__ptr_)),
+ __alloc_(_VSTD::move(__other.__alloc_))
+ {
+ __other.__ptr_ = nullptr;
+ __other.__alloc_ = _VSTD::nullopt;
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ __node_handle_base& operator=(__node_handle_base&& __other)
+ {
+ _LIBCPP_ASSERT(
+ __alloc_ == _VSTD::nullopt ||
+ __alloc_traits::propagate_on_container_move_assignment::value ||
+ __alloc_ == __other.__alloc_,
+ "node_type with incompatible allocator passed to "
+ "node_type::operator=(node_type&&)");
+
+ __destroy_node_pointer();
+ __ptr_ = __other.__ptr_;
+
+ if (__alloc_traits::propagate_on_container_move_assignment::value ||
+ __alloc_ == _VSTD::nullopt)
+ __alloc_ = _VSTD::move(__other.__alloc_);
+
+ __other.__ptr_ = nullptr;
+ __other.__alloc_ = _VSTD::nullopt;
+
+ return *this;
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ allocator_type get_allocator() const { return *__alloc_; }
+
+ _LIBCPP_INLINE_VISIBILITY
+ explicit operator bool() const { return __ptr_ != nullptr; }
+
+ _LIBCPP_INLINE_VISIBILITY
+ bool empty() const { return __ptr_ == nullptr; }
+
+ _LIBCPP_INLINE_VISIBILITY
+ void swap(__node_handle_base& __other) noexcept(
+ __alloc_traits::propagate_on_container_swap::value ||
+ __alloc_traits::is_always_equal::value)
+ {
+ using _VSTD::swap;
+ swap(__ptr_, __other.__ptr_);
+ if (__alloc_traits::propagate_on_container_swap::value ||
+ __alloc_ == _VSTD::nullopt || __other.__alloc_ == _VSTD::nullopt)
+ swap(__alloc_, __other.__alloc_);
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ ~__node_handle_base()
+ {
+ __destroy_node_pointer();
+ }
+};
+
+template <class _NodeType, class _Alloc>
+class _LIBCPP_TEMPLATE_VIS __set_node_handle
+ : public __node_handle_base<_NodeType, _Alloc>
+{
+ template <class _Tp, class _Compare, class _Allocator>
+ friend class __tree;
+ template <class _Tp, class _Hash, class _Equal, class _Allocator>
+ friend class __hash_table;
+
+ typedef __node_handle_base<_NodeType, _Alloc> __base;
+ using __base::__base;
+
+public:
+ typedef typename _NodeType::__node_value_type value_type;
+
+ _LIBCPP_INLINE_VISIBILITY
+ __set_node_handle() = default;
+
+ _LIBCPP_INLINE_VISIBILITY
+ __set_node_handle(__set_node_handle&& __other) noexcept = default;
+
+ _LIBCPP_INLINE_VISIBILITY
+ __set_node_handle& operator=(__set_node_handle&& __other) = default;
+
+ _LIBCPP_INLINE_VISIBILITY
+ value_type& value() const
+ {
+ return this->__ptr_->__value_;
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ friend void swap(__set_node_handle& __a, __set_node_handle& __b)
+ noexcept(noexcept(__a.swap(__b))) { __a.swap(__b); }
+
+ _LIBCPP_INLINE_VISIBILITY ~__set_node_handle() = default;
+};
+
+template <class _NodeType, class _Alloc>
+class _LIBCPP_TEMPLATE_VIS __map_node_handle
+ : public __node_handle_base<_NodeType, _Alloc>
+{
+ template <class _Tp, class _Compare, class _Allocator>
+ friend class __tree;
+ template <class _Tp, class _Hash, class _Equal, class _Allocator>
+ friend class __hash_table;
+
+ typedef __node_handle_base<_NodeType, _Alloc> __base;
+ using __base::__base;
+
+public:
+ typedef typename _NodeType::__node_value_type::key_type key_type;
+ typedef typename _NodeType::__node_value_type::mapped_type mapped_type;
+
+ _LIBCPP_INLINE_VISIBILITY
+ __map_node_handle() = default;
+
+ _LIBCPP_INLINE_VISIBILITY
+ __map_node_handle(__map_node_handle&& __other) noexcept = default;
+
+ _LIBCPP_INLINE_VISIBILITY
+ __map_node_handle& operator=(__map_node_handle&& __other) = default;
+
+ _LIBCPP_INLINE_VISIBILITY
+ key_type& key() const
+ {
+ return this->__ptr_->__value_.__ref().first;
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ mapped_type& mapped() const
+ {
+ return this->__ptr_->__value_.__ref().second;
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ friend void swap(__map_node_handle& __a, __map_node_handle& __b)
+ noexcept(noexcept(__a.swap(__b))) { __a.swap(__b); }
+
+ _LIBCPP_INLINE_VISIBILITY ~__map_node_handle() = default;
+};
+
+template <class _Iterator, class _NodeType>
+struct __insert_return_type
+{
+ _Iterator position;
+ bool inserted;
+ _NodeType node;
+};
+
+#endif // _LIBCPP_STD_VER > 14
+
+_LIBCPP_END_NAMESPACE_STD
+_LIBCPP_POP_MACROS
+
+#endif
Index: libcxx/include/__hash_table
===================================================================
--- libcxx/include/__hash_table
+++ libcxx/include/__hash_table
@@ -863,6 +863,17 @@
template <class> friend class __hash_map_node_destructor;
};
+#if _LIBCPP_STD_VER > 14
+template <class _NodeType, class _Alloc>
+struct __generic_container_node_destructor;
+
+template <class _Tp, class _VoidPtr, class _Alloc>
+struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc>
+ : __hash_node_destructor<_Alloc>
+{
+ using __hash_node_destructor<_Alloc>::__hash_node_destructor;
+};
+#endif
#ifndef _LIBCPP_CXX03_LANG
template <class _Key, class _Hash, class _Equal, class _Alloc>
@@ -1051,6 +1062,17 @@
);
}
+private:
+ __next_pointer __node_insert_multi_prepare(size_t __cp_hash,
+ value_type& __cp_val);
+ void __node_insert_multi_perform(__node_pointer __cp,
+ __next_pointer __pn) _NOEXCEPT;
+
+ __next_pointer __node_insert_unique_prepare(size_t __nd_hash,
+ value_type& __nd_val);
+ void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT;
+
+public:
pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
iterator __node_insert_multi(__node_pointer __nd);
iterator __node_insert_multi(const_iterator __p,
@@ -1155,6 +1177,40 @@
return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
}
+#if _LIBCPP_STD_VER > 14
+ template <class _NodeHandle, class _InsertReturnType>
+ _LIBCPP_INLINE_VISIBILITY
+ _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh);
+ template <class _NodeHandle>
+ _LIBCPP_INLINE_VISIBILITY
+ iterator __node_handle_insert_unique(const_iterator __hint,
+ _NodeHandle&& __nh);
+ template <class _NodeHandle>
+ _LIBCPP_INLINE_VISIBILITY
+ _NodeHandle __node_handle_extract_unique(key_type const& __key);
+ template <class _NodeHandle>
+ _NodeHandle __node_handle_extract_unique(const_iterator __it);
+ template <class _Table>
+ _LIBCPP_INLINE_VISIBILITY
+ void __node_handle_merge_unique(_Table& __source);
+
+ template <class _NodeHandle>
+ _LIBCPP_INLINE_VISIBILITY
+ iterator __node_handle_insert_multi(_NodeHandle&& __nh);
+ template <class _NodeHandle>
+ _LIBCPP_INLINE_VISIBILITY
+ iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);
+ template <class _NodeHandle>
+ _LIBCPP_INLINE_VISIBILITY
+ _NodeHandle __node_handle_extract_multi(key_type const&);
+ template <class _NodeHandle>
+ _LIBCPP_INLINE_VISIBILITY
+ _NodeHandle __node_handle_extract_multi(const_iterator __it);
+ template <class _Table>
+ _LIBCPP_INLINE_VISIBILITY
+ void __node_handle_merge_multi(_Table& __source);
+#endif
+
void clear() _NOEXCEPT;
void rehash(size_type __n);
_LIBCPP_INLINE_VISIBILITY void reserve(size_type __n)
@@ -1819,112 +1875,141 @@
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare(
+ size_t __hash, value_type& __value)
{
- __nd->__hash_ = hash_function()(__nd->__value_);
size_type __bc = bucket_count();
- bool __inserted = false;
- __next_pointer __ndptr;
- size_t __chash;
+
if (__bc != 0)
{
- __chash = __constrain_hash(__nd->__hash_, __bc);
- __ndptr = __bucket_list_[__chash];
+ size_t __chash = __constrain_hash(__hash, __bc);
+ __next_pointer __ndptr = __bucket_list_[__chash];
if (__ndptr != nullptr)
{
for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
- __constrain_hash(__ndptr->__hash(), \
__bc) == __chash;
- __ndptr = __ndptr->__next_)
+ __constrain_hash(__ndptr->__hash(), __bc) == __chash;
+ __ndptr = __ndptr->__next_)
{
- if (key_eq()(__ndptr->__upcast()->__value_, __nd->__value_))
- goto __done;
+ if (key_eq()(__ndptr->__upcast()->__value_, __value))
+ return __ndptr;
}
}
}
+ if (size()+1 > __bc * max_load_factor() || __bc == 0)
{
- if (size()+1 > __bc * max_load_factor() || __bc == 0)
- {
- rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
- size_type(ceil(float(size() + 1) / max_load_factor()))));
- __bc = bucket_count();
- __chash = __constrain_hash(__nd->__hash_, __bc);
- }
- // insert_after __bucket_list_[__chash], or __first_node if bucket is null
- __next_pointer __pn = __bucket_list_[__chash];
- if (__pn == nullptr)
- {
- __pn =__p1_.first().__ptr();
- __nd->__next_ = __pn->__next_;
- __pn->__next_ = __nd->__ptr();
- // fix up __bucket_list_
- __bucket_list_[__chash] = __pn;
- if (__nd->__next_ != nullptr)
- __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = \
__nd->__ptr();
- }
- else
- {
- __nd->__next_ = __pn->__next_;
- __pn->__next_ = __nd->__ptr();
- }
+ rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
+ size_type(ceil(float(size() + 1) / \
max_load_factor())))); + }
+ return nullptr;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform(
+ __node_pointer __nd) _NOEXCEPT
+{
+ size_type __bc = bucket_count();
+ size_t __chash = __constrain_hash(__nd->__hash(), __bc);
+ // insert_after __bucket_list_[__chash], or __first_node if bucket is null
+ __next_pointer __pn = __bucket_list_[__chash];
+ if (__pn == nullptr)
+ {
+ __pn =__p1_.first().__ptr();
+ __nd->__next_ = __pn->__next_;
+ __pn->__next_ = __nd->__ptr();
+ // fix up __bucket_list_
+ __bucket_list_[__chash] = __pn;
+ if (__nd->__next_ != nullptr)
+ __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = \
__nd->__ptr(); + }
+ else
+ {
+ __nd->__next_ = __pn->__next_;
+ __pn->__next_ = __nd->__ptr();
+ }
+ ++size();
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
+{
+ __nd->__hash_ = hash_function()(__nd->__value_);
+ __next_pointer __ndptr =
+ __node_insert_unique_prepare(__nd->__hash(), __nd->__value_);
+ bool __inserted = false;
+ if (__ndptr == nullptr)
+ {
+ __node_insert_unique_perform(__nd);
__ndptr = __nd->__ptr();
- // increment size
- ++size();
__inserted = true;
}
-__done:
#if _LIBCPP_DEBUG_LEVEL >= 2
return pair<iterator, bool>(iterator(__ndptr, this), __inserted);
#else
return pair<iterator, bool>(iterator(__ndptr), __inserted);
#endif
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare(
+ size_t __cp_hash, value_type& __cp_val)
{
- __cp->__hash_ = hash_function()(__cp->__value_);
size_type __bc = bucket_count();
if (size()+1 > __bc * max_load_factor() || __bc == 0)
{
rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
- size_type(ceil(float(size() + 1) / max_load_factor()))));
+ size_type(ceil(float(size() + 1) / \
max_load_factor())))); __bc = bucket_count();
}
- size_t __chash = __constrain_hash(__cp->__hash_, __bc);
+ size_t __chash = __constrain_hash(__cp_hash, __bc);
__next_pointer __pn = __bucket_list_[__chash];
- if (__pn == nullptr)
- {
- __pn =__p1_.first().__ptr();
- __cp->__next_ = __pn->__next_;
- __pn->__next_ = __cp->__ptr();
- // fix up __bucket_list_
- __bucket_list_[__chash] = __pn;
- if (__cp->__next_ != nullptr)
- __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)]
- = __cp->__ptr();
- }
- else
+ if (__pn != nullptr)
{
for (bool __found = false; __pn->__next_ != nullptr &&
- __constrain_hash(__pn->__next_->__hash(), __bc) \
== __chash;
- __pn = __pn->__next_)
+ __constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
+ __pn = __pn->__next_)
{
// __found key_eq() action
// false false loop
// true true loop
// false true set __found to true
// true false break
- if (__found != (__pn->__next_->__hash() == __cp->__hash_ &&
- key_eq()(__pn->__next_->__upcast()->__value_, \
__cp->__value_))) + if (__found != (__pn->__next_->__hash() == __cp_hash \
&& + key_eq()(__pn->__next_->__upcast()->__value_, \
__cp_val))) {
if (!__found)
__found = true;
else
break;
}
}
+ }
+ return __pn;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform(
+ __node_pointer __cp, __next_pointer __pn) _NOEXCEPT
+{
+ size_type __bc = bucket_count();
+ size_t __chash = __constrain_hash(__cp->__hash_, __bc);
+ if (__pn == nullptr)
+ {
+ __pn =__p1_.first().__ptr();
+ __cp->__next_ = __pn->__next_;
+ __pn->__next_ = __cp->__ptr();
+ // fix up __bucket_list_
+ __bucket_list_[__chash] = __pn;
+ if (__cp->__next_ != nullptr)
+ __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)]
+ = __cp->__ptr();
+ }
+ else
+ {
__cp->__next_ = __pn->__next_;
__pn->__next_ = __cp->__ptr();
if (__cp->__next_ != nullptr)
@@ -1935,6 +2020,17 @@
}
}
++size();
+}
+
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
+{
+ __cp->__hash_ = hash_function()(__cp->__value_);
+ __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), \
__cp->__value_); + __node_insert_multi_perform(__cp, __pn);
+
#if _LIBCPP_DEBUG_LEVEL >= 2
return iterator(__cp->__ptr(), this);
#else
@@ -2130,6 +2226,152 @@
#endif // _LIBCPP_CXX03_LANG
+#if _LIBCPP_STD_VER > 14
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle, class _InsertReturnType>
+_InsertReturnType
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
+ _NodeHandle&& __nh)
+{
+ if (__nh.empty())
+ return _InsertReturnType{end(), false, _NodeHandle()};
+ pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
+ if (__result.second)
+ __nh.__release();
+ return _InsertReturnType{__result.first, __result.second, _VSTD::move(__nh)};
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
+ const_iterator, _NodeHandle&& __nh)
+{
+ if (__nh.empty())
+ return end();
+ pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
+ if (__result.second)
+ __nh.__release();
+ return __result.first;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+_NodeHandle
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract_unique(
+ key_type const& __key)
+{
+ iterator __i = find(__key);
+ if (__i == end())
+ return _NodeHandle();
+ return __node_handle_extract_unique<_NodeHandle>(__i);
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+_NodeHandle
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract_unique(
+ const_iterator __p)
+{
+ allocator_type __alloc(__node_alloc());
+ return _NodeHandle(remove(__p).release(), __alloc);
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Table>
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique(
+ _Table& __source)
+{
+ static_assert(is_same<__node, typename _Table::__node>::value, "");
+
+ for (typename _Table::iterator __it = __source.begin();
+ __it != __source.end();)
+ {
+ __node_pointer __src_ptr = __it.__node_->__upcast();
+ size_t __hash = hash_function()(__src_ptr->__value_);
+ __next_pointer __ndptr =
+ __node_insert_unique_prepare(__hash, __src_ptr->__value_);
+ if (__ndptr == nullptr)
+ {
+ (void)__source.remove(__it++).release();
+ __src_ptr->__hash_ = __hash;
+ __node_insert_unique_perform(__src_ptr);
+ }
+ else
+ ++__it;
+ }
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
+ _NodeHandle&& __nh)
+{
+ if (__nh.empty())
+ return end();
+ iterator __result = __node_insert_multi(__nh.__ptr_);
+ __nh.__release();
+ return __result;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
+ const_iterator __hint, _NodeHandle&& __nh)
+{
+ if (__nh.empty())
+ return end();
+ iterator __result = __node_insert_multi(__hint, __nh.__ptr_);
+ __nh.__release();
+ return __result;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+_NodeHandle
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract_multi(
+ key_type const& __key)
+{
+ iterator __it = find(__key);
+ if (__it == end())
+ return _NodeHandle();
+ return __node_handle_extract_multi<_NodeHandle>(__it);
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+_NodeHandle
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract_multi(const_iterator \
__it) +{
+ allocator_type __alloc(__node_alloc());
+ return _NodeHandle(remove(__it).release(), __alloc);
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Table>
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi(
+ _Table& __source)
+{
+ static_assert(is_same<typename _Table::__node, __node>::value, "");
+
+ for (typename _Table::iterator __it = __source.begin();
+ __it != __source.end();)
+ {
+ __node_pointer __src_ptr = __it.__node_->__upcast();
+ size_t __src_hash = hash_function()(__src_ptr->__value_);
+ __next_pointer __pn =
+ __node_insert_multi_prepare(__src_hash, __src_ptr->__value_);
+ (void)__source.remove(__it++).release();
+ __src_ptr->__hash_ = __src_hash;
+ __node_insert_multi_perform(__src_ptr, __pn);
+ }
+}
+#endif // _LIBCPP_STD_VER > 14
+
template <class _Tp, class _Hash, class _Equal, class _Alloc>
void
__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
[Attachment #4 (text/plain)]
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic