erik.pilkington updated this revision to Diff 156912. erik.pilkington added a comment.
In this new patch: - Rebase on top of changes in https://reviews.llvm.org/D46845 - Move in some forward decls that I accidentally left in https://reviews.llvm.org/D46845 - Add some missing visibility attributes - Add `merge` to header summaries https://reviews.llvm.org/D48896 Files: libcxx/include/__hash_table 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/merge.pass.cpp libcxx/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp libcxx/test/std/containers/associative/multiset/merge.pass.cpp libcxx/test/std/containers/associative/set/merge.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/merge.pass.cpp libcxx/test/std/containers/unord/unord.multiset/merge.pass.cpp libcxx/test/std/containers/unord/unord.set/merge.pass.cpp
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,135 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_macros.h" +#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.multiset/merge.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/containers/unord/unord.multiset/merge.pass.cpp @@ -0,0 +1,135 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_macros.h" +#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.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,138 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_macros.h" +#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.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,138 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_macros.h" +#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/associative/set/merge.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/containers/associative/set/merge.pass.cpp @@ -0,0 +1,125 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_macros.h" +#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/multiset/merge.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/containers/associative/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 + +// <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 "test_macros.h" +#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/multimap/multimap.modifiers/merge.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp @@ -0,0 +1,125 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_macros.h" +#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/map/map.modifiers/merge.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/containers/associative/map/map.modifiers/merge.pass.cpp @@ -0,0 +1,125 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_macros.h" +#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/include/unordered_set =================================================================== --- libcxx/include/unordered_set +++ libcxx/include/unordered_set @@ -127,6 +127,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class H2, class P2> + void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17 + template<class H2, class P2> + void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17 + void swap(unordered_set&) noexcept(allocator_traits<Allocator>::is_always_equal::value && noexcept(swap(declval<hasher&>(), declval<hasher&>())) && @@ -282,6 +291,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class H2, class P2> + void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17 + template<class H2, class P2> + void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17 + void swap(unordered_multiset&) noexcept(allocator_traits<Allocator>::is_always_equal::value && noexcept(swap(declval<hasher&>(), declval<hasher&>())) && @@ -347,6 +365,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 @@ -384,6 +405,8 @@ typedef __insert_return_type<iterator, node_type> insert_return_type; #endif + _LIBCPP_INLINE_VISIBILITY __table& __get_table() { return __table_; } + _LIBCPP_INLINE_VISIBILITY unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -589,6 +612,39 @@ { return __table_.template __node_handle_extract<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 @@ -937,6 +993,8 @@ typedef __set_node_handle<typename __table::__node, allocator_type> node_type; #endif + _LIBCPP_INLINE_VISIBILITY __table& __get_table() { return __table_; } + _LIBCPP_INLINE_VISIBILITY unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1101,6 +1159,39 @@ { return __table_.template __node_handle_extract<node_type>(__key); } + + 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 Index: libcxx/include/unordered_map =================================================================== --- libcxx/include/unordered_map +++ libcxx/include/unordered_map @@ -153,6 +153,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class H2, class P2> + void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17 + template<class H2, class P2> + void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17 + void swap(unordered_map&) noexcept( (!allocator_type::propagate_on_container_swap::value || @@ -325,6 +334,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class H2, class P2> + void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17 + template<class H2, class P2> + void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17 + void swap(unordered_multimap&) noexcept( (!allocator_type::propagate_on_container_swap::value || @@ -807,6 +825,9 @@ template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; }; +template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> +class unordered_multimap; + template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, class _Alloc = allocator<pair<const _Key, _Tp> > > class _LIBCPP_TEMPLATE_VIS unordered_map @@ -864,6 +885,8 @@ typedef __insert_return_type<iterator, node_type> insert_return_type; #endif + _LIBCPP_INLINE_VISIBILITY __table& __get_table() { return __table_; } + _LIBCPP_INLINE_VISIBILITY unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1187,6 +1210,39 @@ return __table_.template __node_handle_extract<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 @@ -1645,6 +1701,8 @@ typedef __map_node_handle<__node, allocator_type> node_type; #endif + _LIBCPP_INLINE_VISIBILITY __table& __get_table() { return __table_; } + _LIBCPP_INLINE_VISIBILITY unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1846,6 +1904,39 @@ return __table_.template __node_handle_extract<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 Index: libcxx/include/set =================================================================== --- libcxx/include/set +++ libcxx/include/set @@ -128,6 +128,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class C2> + void merge(set<Key, C2, Allocator>& source); // C++17 + template<class C2> + void merge(set<Key, C2, Allocator>&& source); // C++17 + template<class C2> + void merge(multiset<Key, C2, Allocator>& source); // C++17 + template<class C2> + void merge(multiset<Key, C2, Allocator>&& source); // C++17 + void swap(set& s) noexcept( __is_nothrow_swappable<key_compare>::value && @@ -316,6 +325,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class C2> + void merge(multiset<Key, C2, Allocator>& source); // C++17 + template<class C2> + void merge(multiset<Key, C2, Allocator>&& source); // C++17 + template<class C2> + void merge(set<Key, C2, Allocator>& source); // C++17 + template<class C2> + void merge(set<Key, C2, Allocator>&& source); // C++17 + void swap(multiset& s) noexcept( __is_nothrow_swappable<key_compare>::value && @@ -409,6 +427,9 @@ _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 @@ -448,6 +469,8 @@ typedef __insert_return_type<iterator, node_type> insert_return_type; #endif + _LIBCPP_INLINE_VISIBILITY __base& __get_tree() { return __tree_; } + _LIBCPP_INLINE_VISIBILITY set() _NOEXCEPT_( @@ -680,6 +703,38 @@ { return __tree_.template __node_handle_extract<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 @@ -890,6 +945,8 @@ typedef __set_node_handle<typename __base::__node, allocator_type> node_type; #endif + _LIBCPP_INLINE_VISIBILITY __base& __get_tree() { return __tree_; } + // construct/copy/destroy: _LIBCPP_INLINE_VISIBILITY multiset() @@ -1121,6 +1178,38 @@ { return __tree_.template __node_handle_extract<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 Index: libcxx/include/map =================================================================== --- libcxx/include/map +++ libcxx/include/map @@ -167,6 +167,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class C2> + void merge(map<Key, T, C2, Allocator>& source); // C++17 + template<class C2> + void merge(map<Key, T, C2, Allocator>&& source); // C++17 + template<class C2> + void merge(multimap<Key, T, C2, Allocator>& source); // C++17 + template<class C2> + void merge(multimap<Key, T, C2, Allocator>&& source); // C++17 + void swap(map& m) noexcept(allocator_traits<allocator_type>::is_always_equal::value && is_nothrow_swappable<key_compare>::value); // C++17 @@ -368,6 +377,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class C2> + void merge(multimap<Key, T, C2, Allocator>& source); // C++17 + template<class C2> + void merge(multimap<Key, T, C2, Allocator>&& source); // C++17 + template<class C2> + void merge(map<Key, T, C2, Allocator>& source); // C++17 + template<class C2> + void merge(map<Key, T, C2, Allocator>&& source); // C++17 + void swap(multimap& m) noexcept(allocator_traits<allocator_type>::is_always_equal::value && is_nothrow_swappable<key_compare>::value); // C++17 @@ -925,6 +943,8 @@ typedef __insert_return_type<iterator, node_type> insert_return_type; #endif + _LIBCPP_INLINE_VISIBILITY __base& __get_tree() { return __tree_; } + _LIBCPP_INLINE_VISIBILITY map() _NOEXCEPT_( @@ -1299,6 +1319,38 @@ { return __tree_.template __node_handle_extract<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 @@ -1614,6 +1666,8 @@ typedef __map_node_handle<typename __base::__node, allocator_type> node_type; #endif + _LIBCPP_INLINE_VISIBILITY __base& __get_tree() { return __tree_; } + _LIBCPP_INLINE_VISIBILITY multimap() _NOEXCEPT_( @@ -1881,6 +1935,38 @@ return __tree_.template __node_handle_extract<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 Index: libcxx/include/__tree =================================================================== --- libcxx/include/__tree +++ libcxx/include/__tree @@ -1341,11 +1341,15 @@ #endif // !_LIBCPP_CXX03_LANG + _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __node_insert_unique(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_unique(const_iterator __p, __node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); @@ -1358,13 +1362,19 @@ template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&); + 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 _Tree> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_multi(_Tree& __source); template <class _NodeHandle> @@ -2471,6 +2481,30 @@ return _NodeHandle(__np, __alloc()); } +template <class _Tp, class _Compare, class _Allocator> +template <class _Tree> +_LIBCPP_INLINE_VISIBILITY +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); + __insert_node_at(__parent, __child, + static_cast<__node_base_pointer>(__src_ptr)); + } +} + template <class _Tp, class _Compare, class _Allocator> template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY @@ -2507,6 +2541,28 @@ return iterator(__ptr); } +template <class _Tp, class _Compare, class _Allocator> +template <class _Tree> +_LIBCPP_INLINE_VISIBILITY +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> Index: libcxx/include/__hash_table =================================================================== --- libcxx/include/__hash_table +++ libcxx/include/__hash_table @@ -1058,8 +1058,26 @@ ); } +private: + _LIBCPP_INLINE_VISIBILITY + __next_pointer __node_insert_multi_prepare(size_t __cp_hash, + value_type& __cp_val); + _LIBCPP_INLINE_VISIBILITY + void __node_insert_multi_perform(__node_pointer __cp, + __next_pointer __pn) _NOEXCEPT; + + _LIBCPP_INLINE_VISIBILITY + __next_pointer __node_insert_unique_prepare(size_t __nd_hash, + value_type& __nd_val); + _LIBCPP_INLINE_VISIBILITY + void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT; + +public: + _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __node_insert_unique(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); @@ -1170,13 +1188,19 @@ _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh); + 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 _Table> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_multi(_Table& __source); template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY @@ -1850,112 +1874,143 @@ } 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) +_LIBCPP_INLINE_VISIBILITY +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> +_LIBCPP_INLINE_VISIBILITY +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) @@ -1966,6 +2021,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 @@ -2216,6 +2282,33 @@ return _NodeHandle(remove(__p).release(), __alloc); } +template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _Table> +_LIBCPP_INLINE_VISIBILITY +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> _LIBCPP_INLINE_VISIBILITY @@ -2244,6 +2337,27 @@ return __result; } +template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _Table> +_LIBCPP_INLINE_VISIBILITY +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>
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits