Index: libcxx/include/__hash_table =================================================================== --- libcxx/include/__hash_table +++ libcxx/include/__hash_table @@ -865,6 +865,17 @@ template friend class __hash_map_node_destructor; }; +#if _LIBCPP_STD_VER > 14 +template +struct __generic_container_node_destructor; + +template +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 @@ -1053,6 +1064,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 __node_insert_unique(__node_pointer __nd); iterator __node_insert_multi(__node_pointer __nd); iterator __node_insert_multi(const_iterator __p, @@ -1157,6 +1179,40 @@ return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x); } +#if _LIBCPP_STD_VER > 14 + template + _LIBCPP_INLINE_VISIBILITY + _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh); + template + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_unique(const_iterator __hint, + _NodeHandle&& __nh); + template + _LIBCPP_INLINE_VISIBILITY + _NodeHandle __node_handle_extract_unique(key_type const& __key); + template + _NodeHandle __node_handle_extract_unique(const_iterator __it); + template + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_unique(_Table& __source); + + template + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_multi(_NodeHandle&& __nh); + template + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh); + template + _LIBCPP_INLINE_VISIBILITY + _NodeHandle __node_handle_extract_multi(key_type const&); + template + _LIBCPP_INLINE_VISIBILITY + _NodeHandle __node_handle_extract_multi(const_iterator __it); + template + _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) @@ -1821,60 +1877,76 @@ } template -pair::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(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(2 * __bc + !__is_hash_power2(__bc), + size_type(ceil(float(size() + 1) / max_load_factor())))); + } + return nullptr; +} + +template +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 +pair::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(__ndptr, this), __inserted); #else @@ -1883,43 +1955,32 @@ } template -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(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; @@ -1927,6 +1988,30 @@ break; } } + } + return __pn; +} + +template +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) @@ -1937,6 +2022,17 @@ } } ++size(); +} + + +template +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 @@ -2132,6 +2228,155 @@ #endif // _LIBCPP_CXX03_LANG +#if _LIBCPP_STD_VER > 14 +template +template +_InsertReturnType +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( + _NodeHandle&& __nh) +{ + if (__nh.empty()) + return _InsertReturnType{end(), false, _NodeHandle()}; + pair __result = + __node_insert_unique(__nh.__launder_node_pointer()); + if (__result.second) + __nh.__release(); + return _InsertReturnType{__result.first, __result.second, _VSTD::move(__nh)}; +} + +template +template +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 __result = + __node_insert_unique(__nh.__launder_node_pointer()); + if (__result.second) + __nh.__release(); + return __result.first; +} + +template +template +_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 +template +_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 +template +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 +template +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.__launder_node_pointer()); + __nh.__release(); + return __result; +} + +template +template +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.__launder_node_pointer()); + __nh.__release(); + return __result; +} + +template +template +_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 +template +_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 +template +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi( + _Table& __source) +{ + static_assert(is_same::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 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) Index: libcxx/include/__node_handle =================================================================== --- /dev/null +++ libcxx/include/__node_handle @@ -0,0 +1,252 @@ +// -*- 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 +#include + +#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 +struct __generic_container_node_destructor; + +template +class __node_handle_base +{ +public: + typedef allocator_traits<_Alloc> __alloc_traits; + typedef typename __rebind_pointer::type + __node_pointer_type; + + typedef _Alloc allocator_type; + typedef typename _NodeType::__node_value_type value_type; + + __node_pointer_type __ptr_ = nullptr; + optional __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 _LIBCPP_TEMPLATE_VIS __set_node_handle + : public __node_handle_base<_NodeType, _Alloc> +{ + template + friend class __tree; + template + 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 + typename __base::__node_pointer_type __launder_node_pointer() + { + // This is only for compatability with __map_node_handle, which has to + // actually call launder(). + return this->__ptr_; + } + + _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 _LIBCPP_TEMPLATE_VIS __map_node_handle + : public __node_handle_base<_NodeType, _Alloc> +{ + template + friend class __tree; + template + 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 + { + // We need to launder the pointer here to pick up the new value in case + // a previous call already mutated the const key. + return const_cast( + __launder_node_pointer()->__value_.__cc.first); + } + + _LIBCPP_INLINE_VISIBILITY + mapped_type& mapped() const + { + return this->__ptr_->__value_.__cc.second; + } + + _LIBCPP_INLINE_VISIBILITY + typename __base::__node_pointer_type __launder_node_pointer() const + { + return pointer_traits::pointer_to( + *_VSTD::launder(_VSTD::addressof(*this->__ptr_))); + } + + _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 +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/__tree =================================================================== --- libcxx/include/__tree +++ libcxx/include/__tree @@ -803,6 +803,16 @@ template friend class __map_node_destructor; }; +#if _LIBCPP_STD_VER > 14 +template +struct __generic_container_node_destructor; +template +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 _LIBCPP_TEMPLATE_VIS __tree_iterator @@ -1345,6 +1355,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 + _LIBCPP_INLINE_VISIBILITY + _InsertReturnType __node_handle_insert_unique(_NodeHandle&&); + template + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&); + template + _LIBCPP_INLINE_VISIBILITY + _NodeHandle __node_handle_extract_unique(key_type const&); + template + _LIBCPP_INLINE_VISIBILITY + _NodeHandle __node_handle_extract_unique(const_iterator); + template + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_unique(_Tree& __source); + + template + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_multi(_NodeHandle&&); + template + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&); + template + _LIBCPP_INLINE_VISIBILITY + _NodeHandle __node_handle_extract_multi(key_type const&); + template + _NodeHandle __node_handle_extract_multi(const_iterator); + template + _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 @@ -2354,17 +2400,201 @@ template 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 +template +_InsertReturnType +__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique( + _NodeHandle&& __nh) +{ + if (__nh.empty()) + return _InsertReturnType{end(), false, _NodeHandle()}; + + __node_pointer __ptr = __nh.__launder_node_pointer(); + __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 +template +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.__launder_node_pointer(); + __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 +template +_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 +template +_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 +template +void +__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source) +{ + static_assert(is_same::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 +template +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.__launder_node_pointer(); + __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 +template +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.__launder_node_pointer(); + __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 +template +_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 +template +_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 +template +void +__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source) +{ + static_assert(is_same::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 +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/map =================================================================== --- libcxx/include/map +++ libcxx/include/map @@ -440,6 +440,7 @@ #include <__config> #include <__tree> +#include <__node_handle> #include #include #include @@ -854,6 +855,13 @@ typedef _VSTD::reverse_iterator reverse_iterator; typedef _VSTD::reverse_iterator const_reverse_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __map_node_handle node_type; + typedef __insert_return_type insert_return_type; +#endif + + __base& __get_tree() { return __tree_; } + _LIBCPP_INLINE_VISIBILITY map() _NOEXCEPT_( @@ -1201,6 +1209,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( + __hint.__i_, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __tree_.template __node_handle_extract_unique(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __tree_.template __node_handle_extract_unique(__it.__i_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(map& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__get_tree()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(map&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__get_tree()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multimap& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__get_tree()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multimap&& __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) @@ -1511,6 +1580,12 @@ typedef _VSTD::reverse_iterator reverse_iterator; typedef _VSTD::reverse_iterator const_reverse_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __map_node_handle node_type; +#endif + + __base& __get_tree() { return __tree_; } + _LIBCPP_INLINE_VISIBILITY multimap() _NOEXCEPT_( @@ -1749,6 +1824,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( + _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( + __hint.__i_, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __tree_.template __node_handle_extract_multi(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __tree_.template __node_handle_extract_multi( + __it.__i_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multimap& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__get_tree()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multimap&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__get_tree()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(map& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__get_tree()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(map&& __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/set =================================================================== --- libcxx/include/set +++ libcxx/include/set @@ -387,6 +387,7 @@ #include <__config> #include <__tree> +#include <__node_handle> #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -395,6 +396,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template +class multiset; + template , class _Allocator = allocator<_Key> > class _LIBCPP_TEMPLATE_VIS set @@ -429,6 +433,13 @@ typedef _VSTD::reverse_iterator reverse_iterator; typedef _VSTD::reverse_iterator const_reverse_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __set_node_handle node_type; + typedef __insert_return_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( + __hint, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __tree_.template __node_handle_extract_unique(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __tree_.template __node_handle_extract_unique(__it); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(set& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__get_tree()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(set&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__get_tree()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multiset& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__get_tree()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multiset&& __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 reverse_iterator; typedef _VSTD::reverse_iterator const_reverse_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __set_node_handle 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( + _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( + __hint, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __tree_.template __node_handle_extract_multi(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __tree_.template __node_handle_extract_multi(__it); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multiset& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__get_tree()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multiset&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__get_tree()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(set& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__get_tree()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(set&& __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/unordered_map =================================================================== --- libcxx/include/unordered_map +++ libcxx/include/unordered_map @@ -367,6 +367,7 @@ #include <__config> #include <__hash_table> +#include <__node_handle> #include #include #include @@ -379,6 +380,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template +class unordered_multimap; + template class __unordered_map_hasher : private _Hash @@ -791,6 +795,13 @@ typedef __hash_map_iterator local_iterator; typedef __hash_map_const_iterator const_local_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __map_node_handle<__node, allocator_type> node_type; + typedef __insert_return_type insert_return_type; +#endif + + __table& __get_table() { return __table_; } + _LIBCPP_INLINE_VISIBILITY unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1084,7 +1095,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( + __hint.__i_, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __table_.template __node_handle_extract_unique(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __table_.template __node_handle_extract_unique( + __it.__i_); + } + + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_map& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_unique(__source.__get_table()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_map&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_unique(__source.__get_table()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multimap& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_unique(__source.__get_table()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multimap&& __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) @@ -1539,6 +1613,12 @@ typedef __hash_map_iterator local_iterator; typedef __hash_map_const_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) @@ -1712,6 +1792,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( + _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( + __hint.__i_, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __table_.template __node_handle_extract_multi(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __table_.template __node_handle_extract_multi( + __it.__i_); + } + + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multimap& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__get_table()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multimap&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__get_table()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_map& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__get_table()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_map&& __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/unordered_set =================================================================== --- libcxx/include/unordered_set +++ libcxx/include/unordered_set @@ -321,6 +321,7 @@ #include <__config> #include <__hash_table> +#include <__node_handle> #include #include <__debug> @@ -331,6 +332,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template +class unordered_multiset; + template , 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 node_type; + typedef __insert_return_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(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __table_.template __node_handle_extract_unique(__it); + } + + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_set& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __table_.__node_handle_merge_unique(__source.__get_table()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_set&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __table_.__node_handle_merge_unique(__source.__get_table()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __table_.__node_handle_merge_unique(__source.__get_table()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset&& __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 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( + __position); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __table_.template __node_handle_extract_multi(__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( + _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( + __hint, _VSTD::move(__nh)); + } + + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__get_table()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__get_table()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_set& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__get_table()); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_set&& __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/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 + +// + +// class map + +#include +#include +#include "min_allocator.h" +#include "Counter.h" + +namespace test_irt +{ +typedef std::map int_map_type; +using intIRT = int_map_type::insert_return_type; +static_assert(std::is_move_constructible::value && + std::is_move_assignable::value && + std::is_default_constructible::value && + std::is_destructible::value, ""); + +typedef std::map, Counter, std::less>, + min_allocator, Counter>>> map_type; +using minIRT = map_type::insert_return_type; + +static_assert(std::is_move_constructible::value && + std::is_move_assignable::value && + std::is_default_constructible::value && + std::is_destructible::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; + +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> 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(3)); + map_type::node_type nh0 = dtc.extract(Counter(0)); + map_type::node_type nh9 = dtc.extract(Counter(9)); + + assert(static_cast(nh3) && static_cast(nh0) && + static_cast(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, min_allocator>> 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, std::less>, min_allocator>>> map_type; + +static void doit() +{ + map_type::node_type nh; + assert(!static_cast(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(nh)); + } + + { + map_type other; + other.insert(std::move(nh)); + assert(!static_cast(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(a) && !static_cast(b)); + a = s.extract(s.begin()); + a.swap(b); + assert(!static_cast(a) && static_cast(b)); + s.insert(std::move(b)); + assert(!static_cast(a) && !static_cast(b)); + a = s.extract(s.begin()); + b = s.extract(s.begin()); + assert(static_cast(a) && static_cast(b)); + + assert(b.mapped() == 100 && b.key() == 42); + assert(a.mapped() == 101 && a.key() == 24); + + swap(a, b); + assert(static_cast(a) && static_cast(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/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 + +// + +// class map + +// template +// void merge(map& source); + +#include +#include "Counter.h" + +template +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 + bool operator()(const T& lhs, const T& rhs) const + { + if (should_throw_) + throw 0; + return lhs < rhs; + } +}; +#endif + +int main() +{ + { + std::map src{{1, 0}, {3, 0}, {5, 0}}; + std::map 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, 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& lhs, const Counter& rhs) const + { + return lhs < rhs; + } + }; + { + typedef std::map, int, std::less>> first_map_type; + typedef std::map, int, comparator> second_map_type; + typedef std::multimap, 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 first; + { + std::map second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::multimap 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 + +// + +// class multimap + +#include +#include +#include "min_allocator.h" +#include "Counter.h" + +namespace test_extract +{ +using the_map = std::multimap; + +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> 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(3)); + map_type::node_type nh0 = dtc.extract(Counter(0)); + map_type::node_type nh9 = dtc.extract(Counter(9)); + + assert(static_cast(nh3) && static_cast(nh0) && + static_cast(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, min_allocator>> 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, std::less>, min_allocator>>> map_type; + +static void doit() +{ + map_type::node_type nh; + assert(!static_cast(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(nh)); + } + + { + map_type other; + other.insert(std::move(nh)); + assert(!static_cast(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(a) && !static_cast(b)); + a = s.extract(s.begin()); + a.swap(b); + assert(!static_cast(a) && static_cast(b)); + s.insert(std::move(b)); + assert(!static_cast(a) && !static_cast(b)); + a = s.extract(s.begin()); + b = s.extract(s.begin()); + assert(static_cast(a) && static_cast(b)); + + assert(b.mapped() == 100 && b.key() == 42); + assert(a.mapped() == 101 && a.key() == 24); + + swap(a, b); + assert(static_cast(a) && static_cast(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/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 + +// + +// class multimap + +// template +// void merge(multimap& source); + +#include +#include "Counter.h" + +template +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 + bool operator()(const T& lhs, const T& rhs) const + { + if (should_throw_) + throw 0; + return lhs < rhs; + } +}; +#endif + +int main() +{ + { + std::multimap src{{1, 0}, {3, 0}, {5, 0}}; + std::multimap 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, 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& lhs, const Counter& rhs) const + { + return lhs < rhs; + } + }; + { + typedef std::multimap, int, std::less>> first_map_type; + typedef std::multimap, int, comparator> second_map_type; + typedef std::map, 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 first; + { + std::multimap second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::multimap 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 + +// + +// class multiset + +#include +#include +#include "min_allocator.h" +#include "Counter.h" + +namespace test_extract +{ +using the_set = std::multiset; + +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> 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(3)); + set_type::node_type nh0 = dtc.extract(Counter(0)); + set_type::node_type nh9 = dtc.extract(Counter(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, min_allocator> 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, std::less>, min_allocator>> set_type; + +static void doit() +{ + set_type::node_type nh; + assert(!static_cast(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(nh)); + } + + { + set_type other; + other.insert(std::move(nh)); + assert(!static_cast(nh)); + } + + assert(Counter_base::gConstructed == 0); + + { + set_type::node_type a, b; + std::swap(a, b); + set_type s = {42, 24}; + assert(!static_cast(a) && !static_cast(b)); + a = s.extract(s.begin()); + a.swap(b); + assert(!static_cast(a) && static_cast(b)); + s.insert(std::move(b)); + assert(!static_cast(a) && !static_cast(b)); + a = s.extract(s.begin()); + b = s.extract(s.begin()); + assert(static_cast(a) && static_cast(b)); + + Counter* aval = &a.value(); + Counter* bval = &b.value(); + assert(aval->get() == 24); + assert(bval->get() == 42); + + swap(a, b); + assert(static_cast(a) && static_cast(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 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/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 + +// + +// class multiset + +// template +// void merge(multiset& source); +// +// template +// void merge(multiset&& source); +// +// template +// void merge(set& source); +// +// template +// void merge(set&& source); + +#include +#include "Counter.h" + +template +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 + bool operator()(const T& lhs, const T& rhs) const + { + if (should_throw_) + throw 0; + return lhs < rhs; + } +}; +#endif + +int main() +{ + { + std::multiset src{1, 3, 5}; + std::multiset 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, 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& lhs, const Counter& rhs) const + { + return lhs < rhs; + } + }; + { + typedef std::multiset, std::less>> first_set_type; + typedef std::multiset, comparator> second_set_type; + typedef std::set, 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 first; + { + std::multiset second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::set 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 + +// + +// class set + +#include +#include +#include "min_allocator.h" +#include "Counter.h" + +namespace test_irt +{ +typedef std::set int_set_type; +using intIRT = int_set_type::insert_return_type; +static_assert(std::is_move_constructible::value && + std::is_move_assignable::value && + std::is_default_constructible::value && + std::is_destructible::value, ""); + +typedef std::set, std::less>, + min_allocator>> set_type; +using minIRT = set_type::insert_return_type; + +static_assert(std::is_move_constructible::value && + std::is_move_assignable::value && + std::is_default_constructible::value && + std::is_destructible::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; + +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> 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(3)); + set_type::node_type nh0 = dtc.extract(Counter(0)); + set_type::node_type nh9 = dtc.extract(Counter(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, min_allocator> 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, std::less>, min_allocator>> set_type; + +static void doit() +{ + set_type::node_type nh; + assert(!static_cast(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(nh)); + } + + { + set_type other; + other.insert(std::move(nh)); + assert(!static_cast(nh)); + } + + assert(Counter_base::gConstructed == 0); + + { + set_type::node_type a, b; + std::swap(a, b); + set_type s = {42, 24}; + assert(!static_cast(a) && !static_cast(b)); + a = s.extract(s.begin()); + a.swap(b); + assert(!static_cast(a) && static_cast(b)); + s.insert(std::move(b)); + assert(!static_cast(a) && !static_cast(b)); + a = s.extract(s.begin()); + b = s.extract(s.begin()); + assert(static_cast(a) && static_cast(b)); + + Counter* aval = &a.value(); + Counter* bval = &b.value(); + assert(aval->get() == 24); + assert(bval->get() == 42); + + swap(a, b); + assert(static_cast(a) && static_cast(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/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 + +// + +// class set + +// template +// void merge(set& source); + +#include +#include "Counter.h" + +template +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 + bool operator()(const T& lhs, const T& rhs) const + { + if (should_throw_) + throw 0; + return lhs < rhs; + } +}; +#endif + +int main() +{ + { + std::set src{1, 3, 5}; + std::set 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, 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& lhs, const Counter& rhs) const + { + return lhs < rhs; + } + }; + { + typedef std::set, std::less>> first_set_type; + typedef std::set, comparator> second_set_type; + typedef std::multiset, 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 first; + { + std::set second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::multiset second; + first.merge(second); + first.merge(std::move(second)); + } + } +} 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 +#include +#include +#include +#include "min_allocator.h" + +using namespace std; + +// [container.node.overview] Table 83. +template +struct node_compatibility_table +{ + static constexpr bool value = + is_same_v::node_type, typename map::node_type> && + is_same_v::node_type, typename multimap::node_type> && + is_same_v::node_type, typename set::node_type> && + is_same_v::node_type, typename multiset::node_type> && + is_same_v::node_type, typename unordered_map::node_type> && + is_same_v::node_type, typename unordered_multimap::node_type> && + is_same_v::node_type, typename unordered_set::node_type> && + is_same_v::node_type, typename unordered_multiset::node_type>; +}; + +template struct my_hash +{ + typedef T argument_type; + typedef size_t result_type; + my_hash() = default; + size_t operator()(const T&) const {return 0;} +}; + +template struct my_compare +{ + my_compare() = default; + bool operator()(const T&, const T&) const {return true;} +}; + +template 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 +{ + 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, std::less, std::hash, + std::hash, std::equal_to, std::equal_to, + std::allocator, + std::allocator > >::value, + ""); + +static_assert( + node_compatibility_table, my_compare, + std::hash, my_hash, std::equal_to, + my_equal, allocator, + allocator > >::value, + ""); + +static_assert(node_compatibility_table< + Static, int, my_compare, std::less, + my_hash, std::hash, my_equal, + std::equal_to, min_allocator, + min_allocator > >::value, + ""); + +int main() +{ + return 0; +} 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 + +// + +// class unordered_map + +#include +#include +#include "min_allocator.h" +#include "Counter.h" + +namespace test_irt +{ +typedef std::unordered_map int_map_type; +using intIRT = int_map_type::insert_return_type; +static_assert(std::is_move_constructible::value && + std::is_move_assignable::value && + std::is_default_constructible::value && + std::is_destructible::value, ""); + +typedef std::unordered_map< + Counter, Counter, std::hash >, + std::equal_to >, + min_allocator, Counter > > > + map_type; +using minIRT = map_type::insert_return_type; + +static_assert(std::is_move_constructible::value && + std::is_move_assignable::value && + std::is_default_constructible::value && + std::is_destructible::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; + +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> 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(3)); + map_type::node_type nh0 = dtc.extract(Counter(0)); + map_type::node_type nh9 = dtc.extract(Counter(9)); + + assert(static_cast(nh3) && static_cast(nh0) && + static_cast(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, std::equal_to, min_allocator>> 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, std::hash>, std::equal_to>, min_allocator>>> map_type; + +static void doit() +{ + map_type::node_type nh; + assert(!static_cast(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(nh)); + } + + { + map_type other; + other.insert(std::move(nh)); + assert(!static_cast(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(a) && !static_cast(b)); + a = s.extract(s.begin()); + a.swap(b); + assert(!static_cast(a) && static_cast(b)); + s.insert(std::move(b)); + assert(!static_cast(a) && !static_cast(b)); + a = s.extract(24); + b = s.extract(42); + assert(static_cast(a) && static_cast(b)); + + assert(b.mapped() == 100 && b.key() == 42); + assert(a.mapped() == 101 && a.key() == 24); + + swap(a, b); + assert(static_cast(a) && static_cast(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/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 + +// + +// class unordered_map + +// template +// void merge(unordered_map& source); + +#include +#include "Counter.h" + +template +bool map_equal(const Map& map, Map other) +{ + return map == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +template +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()(p); + } +}; +#endif + +int main() +{ + { + std::unordered_map src{{1, 0}, {3, 0}, {5, 0}}; + std::unordered_map 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, int, throw_hasher>> map_type; + map_type src({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher>(do_throw)); + map_type dst({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher>(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>(do_throw)))); + assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher>(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct equal + { + equal() = default; + + bool operator()(const Counter& lhs, const Counter& rhs) const + { + return lhs == rhs; + } + }; + struct hasher + { + hasher() = default; + typedef Counter argument_type; + typedef size_t result_type; + size_t operator()(const Counter& p) const + { + return std::hash>()(p); + } + }; + { + typedef std::unordered_map, int, std::hash>, std::equal_to>> first_map_type; + typedef std::unordered_map, int, hasher, equal> second_map_type; + typedef std::unordered_multimap, 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 first; + { + std::unordered_map second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::unordered_multimap 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 + +// + +// class unordered_multimap + +#include +#include +#include "min_allocator.h" +#include "Counter.h" + +namespace test_extract +{ +using the_map = std::unordered_multimap; + +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> 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(3)); + map_type::node_type nh0 = dtc.extract(Counter(0)); + map_type::node_type nh9 = dtc.extract(Counter(9)); + + assert(static_cast(nh3) && static_cast(nh0) && + static_cast(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, std::equal_to, min_allocator>> 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, std::hash>, std::equal_to>, min_allocator>>> map_type; + +static void doit() +{ + map_type::node_type nh; + assert(!static_cast(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(nh)); + } + + { + map_type other; + other.insert(std::move(nh)); + assert(!static_cast(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(a) && !static_cast(b)); + a = s.extract(s.begin()); + a.swap(b); + assert(!static_cast(a) && static_cast(b)); + s.insert(std::move(b)); + assert(!static_cast(a) && !static_cast(b)); + a = s.extract(24); + b = s.extract(42); + assert(static_cast(a) && static_cast(b)); + + assert(b.mapped() == 100 && b.key() == 42); + assert(a.mapped() == 101 && a.key() == 24); + + swap(a, b); + assert(static_cast(a) && static_cast(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.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 + +// + +// class unordered_multimap + +// template +// void merge(unordered_multimap& source); + +#include +#include "Counter.h" + +template +bool map_equal(const Map& map, Map other) +{ + return map == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +template +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()(p); + } +}; +#endif + +int main() +{ + { + std::unordered_multimap src{{1, 0}, {3, 0}, {5, 0}}; + std::unordered_multimap 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, int, throw_hasher>> map_type; + map_type src({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher>(do_throw)); + map_type dst({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher>(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>(do_throw)))); + assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher>(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct equal + { + equal() = default; + + bool operator()(const Counter& lhs, const Counter& rhs) const + { + return lhs == rhs; + } + }; + struct hasher + { + hasher() = default; + typedef Counter argument_type; + typedef size_t result_type; + size_t operator()(const Counter& p) const + { + return std::hash>()(p); + } + }; + { + typedef std::unordered_multimap, int, std::hash>, std::equal_to>> first_map_type; + typedef std::unordered_multimap, int, hasher, equal> second_map_type; + typedef std::unordered_map, 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 first; + { + std::unordered_multimap second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::unordered_map 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 + +// + +// class unordered_multiset + +#include +#include +#include +#include "min_allocator.h" +#include "Counter.h" + +namespace test_extract +{ +using the_set = std::unordered_multiset; + +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> 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(3)); + set_type::node_type nh0 = dtc.extract(Counter(0)); + set_type::node_type nh9 = dtc.extract(Counter(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, std::equal_to, min_allocator> 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, std::hash>, std::equal_to>, min_allocator>> set_type; + +static void doit() +{ + set_type::node_type nh; + assert(!static_cast(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(nh)); + } + + { + set_type other; + other.insert(std::move(nh)); + assert(other.size() == 1); + assert(!static_cast(nh)); + } + + assert(Counter_base::gConstructed == 0); + + { + set_type::node_type a, b; + std::swap(a, b); + set_type s = {42, 24}; + assert(!static_cast(a) && !static_cast(b)); + a = s.extract(s.begin()); + a.swap(b); + assert(!static_cast(a) && static_cast(b)); + s.insert(std::move(b)); + assert(!static_cast(a) && !static_cast(b)); + a = s.extract(s.begin()); + b = s.extract(s.begin()); + assert(static_cast(a) && static_cast(b)); + + Counter* aval = &a.value(); + Counter* bval = &b.value(); + assert(aval->get() == 24); + assert(bval->get() == 42); + + swap(a, b); + assert(static_cast(a) && static_cast(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.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 + +// + +// class unordered_multiset + +// template +// void merge(unordered_multiset& source); + +#include +#include "Counter.h" + +template +bool set_equal(const Set& set, Set other) +{ + return set == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +template +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()(p); + } +}; +#endif + +int main() +{ + { + std::unordered_multiset src{1, 3, 5}; + std::unordered_multiset 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, throw_hasher>> set_type; + set_type src({1, 3, 5}, 0, throw_hasher>(do_throw)); + set_type dst({2, 4, 5}, 0, throw_hasher>(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>(do_throw)))); + assert(set_equal(dst, set_type({2, 4, 5}, 0, throw_hasher>(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct equal + { + equal() = default; + + bool operator()(const Counter& lhs, const Counter& rhs) const + { + return lhs == rhs; + } + }; + struct hasher + { + hasher() = default; + typedef Counter argument_type; + typedef size_t result_type; + size_t operator()(const Counter& p) const { return std::hash>()(p); } + }; + { + typedef std::unordered_multiset, std::hash>, std::equal_to>> first_set_type; + typedef std::unordered_multiset, hasher, equal> second_set_type; + typedef std::unordered_set, 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 first; + { + std::unordered_multiset second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::unordered_set 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 + +// + +// class unordered_set + +#include +#include +#include +#include "min_allocator.h" +#include "Counter.h" + +namespace test_irt +{ +typedef std::unordered_set int_set_type; +using intIRT = int_set_type::insert_return_type; +static_assert(std::is_move_constructible::value && + std::is_move_assignable::value && + std::is_default_constructible::value && + std::is_destructible::value, ""); + +typedef std::unordered_set, std::hash>, + std::equal_to>, + min_allocator>> set_type; +using minIRT = set_type::insert_return_type; + +static_assert(std::is_move_constructible::value && + std::is_move_assignable::value && + std::is_default_constructible::value && + std::is_destructible::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; + +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> 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(3)); + set_type::node_type nh0 = dtc.extract(Counter(0)); + set_type::node_type nh9 = dtc.extract(Counter(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, std::equal_to, min_allocator> 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, std::hash>, std::equal_to>, min_allocator>> set_type; + +static void doit() +{ + set_type::node_type nh; + assert(!static_cast(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(nh)); + } + + { + set_type other; + other.insert(std::move(nh)); + assert(other.size() == 1); + assert(!static_cast(nh)); + } + + assert(Counter_base::gConstructed == 0); + + { + set_type::node_type a, b; + std::swap(a, b); + set_type s = {42, 24}; + assert(!static_cast(a) && !static_cast(b)); + a = s.extract(s.begin()); + a.swap(b); + assert(!static_cast(a) && static_cast(b)); + s.insert(std::move(b)); + assert(!static_cast(a) && !static_cast(b)); + a = s.extract(s.begin()); + b = s.extract(s.begin()); + assert(static_cast(a) && static_cast(b)); + + Counter* aval = &a.value(); + Counter* bval = &b.value(); + assert(aval->get() == 24); + assert(bval->get() == 42); + + swap(a, b); + assert(static_cast(a) && static_cast(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.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 + +// + +// class unordered_set + +// template +// void merge(unordered_set& source); + +#include +#include "Counter.h" + +template +bool set_equal(const Set& set, Set other) +{ + return set == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +template +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()(p); + } +}; +#endif + +int main() +{ + { + std::unordered_set src{1, 3, 5}; + std::unordered_set 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, throw_hasher>> set_type; + set_type src({1, 3, 5}, 0, throw_hasher>(do_throw)); + set_type dst({2, 4, 5}, 0, throw_hasher>(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>(do_throw)))); + assert(set_equal(dst, set_type({2, 4, 5}, 0, throw_hasher>(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct equal + { + equal() = default; + + bool operator()(const Counter& lhs, const Counter& rhs) const + { + return lhs == rhs; + } + }; + struct hasher + { + hasher() = default; + typedef Counter argument_type; + typedef size_t result_type; + size_t operator()(const Counter& p) const { return std::hash>()(p); } + }; + { + typedef std::unordered_set, std::hash>, std::equal_to>> first_set_type; + typedef std::unordered_set, hasher, equal> second_set_type; + typedef std::unordered_multiset, 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 first; + { + std::unordered_set second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::unordered_multiset second; + first.merge(second); + first.merge(std::move(second)); + } + } +} Index: libcxx/test/support/Counter.h =================================================================== --- libcxx/test/support/Counter.h +++ libcxx/test/support/Counter.h @@ -49,7 +49,7 @@ typedef Counter argument_type; typedef std::size_t result_type; - std::size_t operator()(const Counter& x) const {return std::hash(x.get());} + std::size_t operator()(const Counter& x) const {return std::hash()(x.get());} }; }