From 5e3ea4dd7931a010de30ebef7606215b667ab529 Mon Sep 17 00:00:00 2001 From: Eric Fiselier Date: Thu, 31 Mar 2016 02:15:15 +0000 Subject: [PATCH] Teach __tree how to handle map's __value_type This patch is fairly large and contains a number of changes. The changes all work towards allowing __tree to properly handle __value_type esspecially when inserting into the __tree. I chose not to break this change into smaller patches because it wouldn't be possible to write meaningful standard-compliant tests for each patch. It is very similar to r260513 "[libcxx] Teach __hash_table how to handle unordered_map's __hash_value_type". Changes in * Remove __value_type's constructors because it should never be constructed directly. * Make map::emplace and multimap::emplace forward to __tree and remove the old definitions * Remove "__construct_node" map and multimap member functions. Almost all of the construction is done within __tree. * Fix map's move constructor to access "__value_type.__nc" directly and pass this object to __tree::insert. Changes in <__tree> * Add traits to detect, handle, and unwrap, map's "__value_type". * Convert methods taking "value_type" to take "__container_value_type" instead. Previously these methods caused unwanted implicit conversions from "std::pair" to "__value_type". * Delete __tree_node and __tree_node_base's constructors and assignment operators. The node types should never be constructed because the "__value_" member of __tree_node must be constructed directly by the allocator. * Make the __tree_node_destructor class and "__construct_node" methods unwrap "__node_value_type" into "__container_value_type" before invoking the allocator. The user's allocator can only be used to construct and destroy the container's value_type. Passing it map's "__value_type" was incorrect. * Cleanup the "__insert" and "__emplace" methods. Have __insert forward to an __emplace function wherever possible to reduce code duplication. __insert_unique(value_type const&) and __insert_unique(value_type&&) forward to __emplace_unique_key_args. These functions will not allocate a new node if the value is already in the tree. * Change the __find* functions to take the "key_type" directly instead of passing in "value_type" and unwrapping the key later. This change allows the find functions to be used without having to construct a "value_type" first. This allows for a number of optimizations. * Teach __move_assign and __assign_multi methods to unwrap map's __value_type. llvm-svn: 264986 --- libcxx/include/__config | 6 + libcxx/include/__tree | 543 ++++++++++++--------- libcxx/include/map | 284 +++-------- .../insert_allocator_requirements.pass.cpp | 137 ++++++ .../insert_allocator_requirements.pass.cpp | 103 ++++ .../insert_allocator_requirements.pass.cpp | 102 ++++ .../set/insert_allocator_requirements.pass.cpp | 137 ++++++ 7 files changed, 856 insertions(+), 456 deletions(-) create mode 100644 libcxx/test/std/containers/associative/map/map.modifiers/insert_allocator_requirements.pass.cpp create mode 100644 libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_allocator_requirements.pass.cpp create mode 100644 libcxx/test/std/containers/associative/multiset/insert_allocator_requirements.pass.cpp create mode 100644 libcxx/test/std/containers/associative/set/insert_allocator_requirements.pass.cpp diff --git a/libcxx/include/__config b/libcxx/include/__config index f6047ca..b82c708 100644 --- a/libcxx/include/__config +++ b/libcxx/include/__config @@ -669,6 +669,12 @@ template struct __static_assert_check {}; #define _LIBCPP_DEFAULT = default; #endif +#ifdef _LIBCPP_HAS_NO_DELETED_FUNCTIONS +#define _LIBCPP_EQUAL_DELETE +#else +#define _LIBCPP_EQUAL_DELETE = delete +#endif + #ifdef __GNUC__ #define _NOALIAS __attribute__((__malloc__)) #else diff --git a/libcxx/include/__tree b/libcxx/include/__tree index d35ed12..314d5eb 100644 --- a/libcxx/include/__tree +++ b/libcxx/include/__tree @@ -510,42 +510,22 @@ __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT } } -template -class __tree_node_destructor -{ - typedef _Allocator allocator_type; - typedef allocator_traits __alloc_traits; - -public: - typedef typename __alloc_traits::pointer pointer; -private: - - allocator_type& __na_; - - __tree_node_destructor& operator=(const __tree_node_destructor&); +// node traits -public: - bool __value_constructed; - _LIBCPP_INLINE_VISIBILITY - explicit __tree_node_destructor(allocator_type& __na, bool __val = false) _NOEXCEPT - : __na_(__na), - __value_constructed(__val) - {} +#ifndef _LIBCPP_CXX03_LANG +template +struct __is_tree_value_type_imp : false_type {}; - _LIBCPP_INLINE_VISIBILITY - void operator()(pointer __p) _NOEXCEPT - { - if (__value_constructed) - __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_)); - if (__p) - __alloc_traits::deallocate(__na_, __p, 1); - } +template +struct __is_tree_value_type_imp<__value_type<_Key, _Value>> : true_type {}; - template friend class __map_node_destructor; -}; +template +struct __is_tree_value_type : false_type {}; -// node traits +template +struct __is_tree_value_type<_One> : __is_tree_value_type_imp::type> {}; +#endif template struct __tree_key_value_types { @@ -553,6 +533,26 @@ struct __tree_key_value_types { typedef _Tp __node_value_type; typedef _Tp __container_value_type; static const bool __is_map = false; + + _LIBCPP_INLINE_VISIBILITY + static key_type const& __get_key(_Tp const& __v) { + return __v; + } + _LIBCPP_INLINE_VISIBILITY + static __container_value_type const& __get_value(__node_value_type const& __v) { + return __v; + } + _LIBCPP_INLINE_VISIBILITY + static __container_value_type* __get_ptr(__node_value_type& __n) { + return _VSTD::addressof(__n); + } + +#ifndef _LIBCPP_CXX03_LANG + _LIBCPP_INLINE_VISIBILITY + static __container_value_type&& __move(__node_value_type& __v) { + return _VSTD::move(__v); + } +#endif }; template @@ -564,6 +564,46 @@ struct __tree_key_value_types<__value_type<_Key, _Tp> > { typedef pair<_Key, _Tp> __nc_value_type; typedef __container_value_type __map_value_type; static const bool __is_map = true; + + _LIBCPP_INLINE_VISIBILITY + static key_type const& + __get_key(__node_value_type const& __t) { + return __t.__cc.first; + } + + template + _LIBCPP_INLINE_VISIBILITY + static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value, + key_type const&>::type + __get_key(_Up& __t) { + return __t.first; + } + + _LIBCPP_INLINE_VISIBILITY + static __container_value_type const& + __get_value(__node_value_type const& __t) { + return __t.__cc; + } + + template + _LIBCPP_INLINE_VISIBILITY + static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value, + __container_value_type const&>::type + __get_value(_Up& __t) { + return __t; + } + + _LIBCPP_INLINE_VISIBILITY + static __container_value_type* __get_ptr(__node_value_type& __n) { + return _VSTD::addressof(__n.__cc); + } + +#ifndef _LIBCPP_CXX03_LANG + _LIBCPP_INLINE_VISIBILITY + static __nc_value_type&& __move(__node_value_type& __v) { + return _VSTD::move(__v.__nc); + } +#endif }; template @@ -650,8 +690,6 @@ class __tree_node_base { typedef __tree_node_base_types<_VoidPtr> _NodeBaseTypes; - __tree_node_base(const __tree_node_base&); - __tree_node_base& operator=(const __tree_node_base&); public: typedef typename _NodeBaseTypes::__node_base_pointer pointer; @@ -659,9 +697,10 @@ public: pointer __parent_; bool __is_black_; - _LIBCPP_INLINE_VISIBILITY - __tree_node_base() _NOEXCEPT - : __right_(), __parent_(), __is_black_(false) {} +private: + ~__tree_node_base() _LIBCPP_EQUAL_DELETE; + __tree_node_base(__tree_node_base const&) _LIBCPP_EQUAL_DELETE; + __tree_node_base& operator=(__tree_node_base const&) _LIBCPP_EQUAL_DELETE; }; template @@ -673,18 +712,49 @@ public: __node_value_type __value_; -#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) - template - _LIBCPP_INLINE_VISIBILITY - explicit __tree_node(_Args&& ...__args) - : __value_(_VSTD::forward<_Args>(__args)...) {} -#else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) +private: + ~__tree_node() _LIBCPP_EQUAL_DELETE; + __tree_node(__tree_node const&) _LIBCPP_EQUAL_DELETE; + __tree_node& operator=(__tree_node const&) _LIBCPP_EQUAL_DELETE; +}; + + +template +class __tree_node_destructor +{ + typedef _Allocator allocator_type; + typedef allocator_traits __alloc_traits; + +public: + typedef typename __alloc_traits::pointer pointer; +private: + typedef __tree_node_types _NodeTypes; + allocator_type& __na_; + + __tree_node_destructor& operator=(const __tree_node_destructor&); + +public: + bool __value_constructed; + _LIBCPP_INLINE_VISIBILITY - explicit __tree_node(const __node_value_type& __v) - : __value_(__v) {} -#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) + explicit __tree_node_destructor(allocator_type& __na, bool __val = false) _NOEXCEPT + : __na_(__na), + __value_constructed(__val) + {} + + _LIBCPP_INLINE_VISIBILITY + void operator()(pointer __p) _NOEXCEPT + { + if (__value_constructed) + __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_)); + if (__p) + __alloc_traits::deallocate(__na_, __p, 1); + } + + template friend class __map_node_destructor; }; + template class _LIBCPP_TYPE_VIS_ONLY __tree_iterator { @@ -840,6 +910,7 @@ private: typedef typename __make_tree_node_types::type _NodeTypes; + typedef typename _NodeTypes::key_type key_type; public: typedef typename _NodeTypes::__node_value_type __node_value_type; typedef typename _NodeTypes::__container_value_type __container_value_type; @@ -983,44 +1054,104 @@ public: #endif ); -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES -#ifndef _LIBCPP_HAS_NO_VARIADICS + +#ifndef _LIBCPP_CXX03_LANG + template + pair + __emplace_unique_key_args(_Key const&, _Args&&... __args); + template + iterator + __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...); + template - pair - __emplace_unique(_Args&&... __args); + pair __emplace_unique(_Args&&... __args); + template - iterator - __emplace_multi(_Args&&... __args); + iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args); template - iterator - __emplace_hint_unique(const_iterator __p, _Args&&... __args); + iterator __emplace_multi(_Args&&... __args); + template - iterator - __emplace_hint_multi(const_iterator __p, _Args&&... __args); -#endif // _LIBCPP_HAS_NO_VARIADICS + iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); +#else + template + _LIBCPP_INLINE_VISIBILITY + pair __emplace_unique_key_args(_Key const&, _Args& __args); + template + _LIBCPP_INLINE_VISIBILITY + iterator __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&); +#endif + + _LIBCPP_INLINE_VISIBILITY + pair __insert_unique(const __container_value_type& __v) { + return __emplace_unique_key_args(_NodeTypes::__get_key(__v), __v); + } + + _LIBCPP_INLINE_VISIBILITY + iterator __insert_unique(const_iterator __p, const __container_value_type& __v) { + return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v); + } + +#ifdef _LIBCPP_CXX03_LANG + _LIBCPP_INLINE_VISIBILITY + iterator __insert_multi(const __container_value_type& __v); + _LIBCPP_INLINE_VISIBILITY + iterator __insert_multi(const_iterator __p, const __container_value_type& __v); +#else + _LIBCPP_INLINE_VISIBILITY + pair __insert_unique(__container_value_type&& __v) { + return __emplace_unique_key_args(_NodeTypes::__get_key(__v), _VSTD::move(__v)); + } + + _LIBCPP_INLINE_VISIBILITY + iterator __insert_unique(const_iterator __p, __container_value_type&& __v) { + return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), _VSTD::move(__v)); + } + + template ::type, + __container_value_type + >::value + >::type> + _LIBCPP_INLINE_VISIBILITY + pair __insert_unique(_Vp&& __v) { + return __emplace_unique(_VSTD::forward<_Vp>(__v)); + } + + template ::type, + __container_value_type + >::value + >::type> + _LIBCPP_INLINE_VISIBILITY + iterator __insert_unique(const_iterator __p, _Vp&& __v) { + return __emplace_hint_unique(__p, _VSTD::forward<_Vp>(__v)); + } + + _LIBCPP_INLINE_VISIBILITY + iterator __insert_multi(__container_value_type&& __v) { + return __emplace_multi(_VSTD::move(__v)); + } + + _LIBCPP_INLINE_VISIBILITY + iterator __insert_multi(const_iterator __p, __container_value_type&& __v) { + return __emplace_hint_multi(__p, _VSTD::move(__v)); + } template - pair __insert_unique(_Vp&& __v); - template - iterator __insert_unique(const_iterator __p, _Vp&& __v); - template - iterator __insert_multi(_Vp&& __v); - template - iterator __insert_multi(const_iterator __p, _Vp&& __v); -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + _LIBCPP_INLINE_VISIBILITY + iterator __insert_multi(_Vp&& __v) { + return __emplace_multi(_VSTD::forward<_Vp>(__v)); + } - pair __insert_unique(const value_type& __v); - iterator __insert_unique(const_iterator __p, const value_type& __v); - iterator __insert_multi(const value_type& __v); - iterator __insert_multi(const_iterator __p, const value_type& __v); + template + _LIBCPP_INLINE_VISIBILITY + iterator __insert_multi(const_iterator __p, _Vp&& __v) { + return __emplace_hint_multi(__p, _VSTD::forward<_Vp>(__v)); + } -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - pair __insert_unique( value_type&& __v); - iterator __insert_unique(const_iterator __p, value_type&& __v); - iterator __insert_multi( value_type&& __v); - iterator __insert_multi(const_iterator __p, value_type&& __v); -#endif +#endif // !_LIBCPP_CXX03_LANG pair __node_insert_unique(__node_pointer __nd); iterator __node_insert_unique(const_iterator __p, @@ -1102,12 +1233,12 @@ public: __node_holder remove(const_iterator __p) _NOEXCEPT; private: typename __node_base::pointer& - __find_leaf_low(typename __node_base::pointer& __parent, const value_type& __v); + __find_leaf_low(typename __node_base::pointer& __parent, const key_type& __v); typename __node_base::pointer& - __find_leaf_high(typename __node_base::pointer& __parent, const value_type& __v); + __find_leaf_high(typename __node_base::pointer& __parent, const key_type& __v); typename __node_base::pointer& __find_leaf(const_iterator __hint, - typename __node_base::pointer& __parent, const value_type& __v); + typename __node_base::pointer& __parent, const key_type& __v); template typename __node_base::pointer& __find_equal(typename __node_base::pointer& __parent, const _Key& __v); @@ -1116,11 +1247,11 @@ private: __find_equal(const_iterator __hint, typename __node_base::pointer& __parent, const _Key& __v); -#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) +#ifndef _LIBCPP_CXX03_LANG template - __node_holder __construct_node(_Args&& ...__args); -#else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) - __node_holder __construct_node(const value_type& __v); + __node_holder __construct_node(_Args&& ...__args); +#else + __node_holder __construct_node(const __container_value_type& __v); #endif void destroy(__node_pointer __nd) _NOEXCEPT; @@ -1254,6 +1385,11 @@ template void __tree<_Tp, _Compare, _Allocator>::__assign_unique(_InputIterator __first, _InputIterator __last) { + typedef iterator_traits<_InputIterator> _ITraits; + typedef typename _ITraits::value_type _ItValueType; + static_assert((is_same<_ItValueType, __container_value_type>::value), + "__assign_unique may only be called with the containers value type"); + if (size() != 0) { __node_pointer __cache = __detach(); @@ -1294,6 +1430,12 @@ template void __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) { + typedef iterator_traits<_InputIterator> _ITraits; + typedef typename _ITraits::value_type _ItValueType; + static_assert((is_same<_ItValueType, __container_value_type>::value || + is_same<_ItValueType, __node_value_type>::value), + "__assign_multi may only be called with the containers value type" + " or the nodes value type"); if (size() != 0) { __node_pointer __cache = __detach(); @@ -1326,7 +1468,7 @@ __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _Input } } for (; __first != __last; ++__first) - __insert_multi(*__first); + __insert_multi(_NodeTypes::__get_value(*__first)); } template @@ -1450,7 +1592,7 @@ __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) } } while (__t.size() != 0) - __insert_multi(__e, _VSTD::move(__t.remove(__t.begin())->__value_)); + __insert_multi(__e, _NodeTypes::__move(__t.remove(__t.begin())->__value_)); } } @@ -1485,7 +1627,7 @@ __tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT destroy(static_cast<__node_pointer>(__nd->__left_)); destroy(static_cast<__node_pointer>(__nd->__right_)); __node_allocator& __na = __node_alloc(); - __node_traits::destroy(__na, _VSTD::addressof(__nd->__value_)); + __node_traits::destroy(__na, _NodeTypes::__get_ptr(__nd->__value_)); __node_traits::deallocate(__na, __nd, 1); } } @@ -1532,7 +1674,7 @@ __tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT template typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& __tree<_Tp, _Compare, _Allocator>::__find_leaf_low(typename __node_base::pointer& __parent, - const value_type& __v) + const key_type& __v) { __node_pointer __nd = __root(); if (__nd != nullptr) @@ -1571,7 +1713,7 @@ __tree<_Tp, _Compare, _Allocator>::__find_leaf_low(typename __node_base::pointer template typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& __tree<_Tp, _Compare, _Allocator>::__find_leaf_high(typename __node_base::pointer& __parent, - const value_type& __v) + const key_type& __v) { __node_pointer __nd = __root(); if (__nd != nullptr) @@ -1614,7 +1756,7 @@ template typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& __tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint, typename __node_base::pointer& __parent, - const value_type& __v) + const key_type& __v) { if (__hint == end() || !value_comp()(*__hint, __v)) // check before { @@ -1757,6 +1899,7 @@ __tree<_Tp, _Compare, _Allocator>::__insert_node_at(__node_base_pointer __parent __new_node->__left_ = nullptr; __new_node->__right_ = nullptr; __new_node->__parent_ = __parent; + // __new_node->__is_black_ is initialized in __tree_balance_after_insert __child = __new_node; if (__begin_node()->__left_ != nullptr) __begin_node() = static_cast<__node_pointer>(__begin_node()->__left_); @@ -1764,21 +1907,85 @@ __tree<_Tp, _Compare, _Allocator>::__insert_node_at(__node_base_pointer __parent ++size(); } -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES -#ifndef _LIBCPP_HAS_NO_VARIADICS +#ifndef _LIBCPP_CXX03_LANG +template +template +pair::iterator, bool> +__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) +#else +template +template +pair::iterator, bool> +__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args& __args) +#endif +{ + __node_base_pointer __parent; + __node_base_pointer& __child = __find_equal(__parent, __k); + __node_pointer __r = static_cast<__node_pointer>(__child); + bool __inserted = false; + if (__child == nullptr) + { +#ifndef _LIBCPP_CXX03_LANG + __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); +#else + __node_holder __h = __construct_node(__args); +#endif + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + __r = __h.release(); + __inserted = true; + } + return pair(iterator(__r), __inserted); +} + + +#ifndef _LIBCPP_CXX03_LANG +template +template +typename __tree<_Tp, _Compare, _Allocator>::iterator +__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args( + const_iterator __p, _Key const& __k, _Args&&... __args) +#else +template +template +typename __tree<_Tp, _Compare, _Allocator>::iterator +__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args( + const_iterator __p, _Key const& __k, _Args& __args) +#endif +{ + __node_base_pointer __parent; + __node_base_pointer& __child = __find_equal(__p, __parent, __k); + __node_pointer __r = static_cast<__node_pointer>(__child); + if (__child == nullptr) + { +#ifndef _LIBCPP_CXX03_LANG + __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); +#else + __node_holder __h = __construct_node(__args); +#endif + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + __r = __h.release(); + } + return iterator(__r); +} + + +#ifndef _LIBCPP_CXX03_LANG template template typename __tree<_Tp, _Compare, _Allocator>::__node_holder __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args) { + static_assert(!__is_tree_value_type<_Args...>::value, + "Cannot construct from __value_type"); __node_allocator& __na = __node_alloc(); __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); + __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...); __h.get_deleter().__value_constructed = true; return __h; } + template template pair::iterator, bool> @@ -1822,7 +2029,7 @@ __tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) { __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); __node_base_pointer __parent; - __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_); + __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__h->__value_)); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); return iterator(static_cast<__node_pointer>(__h.release())); } @@ -1835,160 +2042,34 @@ __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, { __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); __node_base_pointer __parent; - __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_); + __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__h->__value_)); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); return iterator(static_cast<__node_pointer>(__h.release())); } -#endif // _LIBCPP_HAS_NO_VARIADICS - -template -pair::iterator, bool> -__tree<_Tp, _Compare, _Allocator>::__insert_unique(value_type&& __v) -{ - __node_holder __h = __construct_node(_VSTD::forward(__v)); - pair __r = __node_insert_unique(__h.get()); - if (__r.second) - __h.release(); - return __r; -} - -template -typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, value_type&& __v) -{ - __node_holder __h = __construct_node(_VSTD::forward(__v)); - iterator __r = __node_insert_unique(__p, __h.get()); - if (__r.__ptr_ == __h.get()) - __h.release(); - return __r; -} - -template -template -pair::iterator, bool> -__tree<_Tp, _Compare, _Allocator>::__insert_unique(_Vp&& __v) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); - pair __r = __node_insert_unique(__h.get()); - if (__r.second) - __h.release(); - return __r; -} - -template -template -typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, _Vp&& __v) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); - iterator __r = __node_insert_unique(__p, __h.get()); - if (__r.__ptr_ == __h.get()) - __h.release(); - return __r; -} - -template -typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__insert_multi(value_type&& __v) -{ - __node_base_pointer __parent; - __node_base_pointer& __child = __find_leaf_high(__parent, __v); - __node_holder __h = __construct_node(_VSTD::forward(__v)); - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - return iterator(__h.release()); -} - -template -typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, value_type&& __v) -{ - __node_base_pointer __parent; - __node_base_pointer& __child = __find_leaf(__p, __parent, __v); - __node_holder __h = __construct_node(_VSTD::forward(__v)); - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - return iterator(__h.release()); -} -template -template -typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__insert_multi(_Vp&& __v) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); - __node_base_pointer __parent; - __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_); - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - return iterator(__h.release()); -} - -template -template -typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, _Vp&& __v) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); - __node_base_pointer __parent; - __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_); - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - return iterator(__h.release()); -} - -#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES +#else // _LIBCPP_CXX03_LANG template typename __tree<_Tp, _Compare, _Allocator>::__node_holder -__tree<_Tp, _Compare, _Allocator>::__construct_node(const value_type& __v) +__tree<_Tp, _Compare, _Allocator>::__construct_node(const __container_value_type& __v) { __node_allocator& __na = __node_alloc(); __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); + __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v); __h.get_deleter().__value_constructed = true; return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 } -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - -template -pair::iterator, bool> -__tree<_Tp, _Compare, _Allocator>::__insert_unique(const value_type& __v) -{ - __node_base_pointer __parent; - __node_base_pointer& __child = __find_equal(__parent, __v); - __node_pointer __r = static_cast<__node_pointer>(__child); - bool __inserted = false; - if (__child == nullptr) - { - __node_holder __h = __construct_node(__v); - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - __r = __h.release(); - __inserted = true; - } - return pair(iterator(__r), __inserted); -} - -template -typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, const value_type& __v) -{ - __node_base_pointer __parent; - __node_base_pointer& __child = __find_equal(__p, __parent, __v); - __node_pointer __r = static_cast<__node_pointer>(__child); - if (__child == nullptr) - { - __node_holder __h = __construct_node(__v); - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - __r = __h.release(); - } - return iterator(__r); -} +#endif // _LIBCPP_CXX03_LANG +#ifdef _LIBCPP_CXX03_LANG template typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__insert_multi(const value_type& __v) +__tree<_Tp, _Compare, _Allocator>::__insert_multi(const __container_value_type& __v) { __node_base_pointer __parent; - __node_base_pointer& __child = __find_leaf_high(__parent, __v); + __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__v)); __node_holder __h = __construct_node(__v); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); return iterator(__h.release()); @@ -1996,14 +2077,15 @@ __tree<_Tp, _Compare, _Allocator>::__insert_multi(const value_type& __v) template typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const value_type& __v) +__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const __container_value_type& __v) { __node_base_pointer __parent; - __node_base_pointer& __child = __find_leaf(__p, __parent, __v); + __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__v)); __node_holder __h = __construct_node(__v); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); return iterator(__h.release()); } +#endif template pair::iterator, bool> @@ -2043,7 +2125,7 @@ typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd) { __node_base_pointer __parent; - __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__value_); + __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__nd->__value_)); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); return iterator(__nd); } @@ -2054,7 +2136,7 @@ __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, __node_pointer __nd) { __node_base_pointer __parent; - __node_base_pointer& __child = __find_leaf(__p, __parent, __nd->__value_); + __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__nd->__value_)); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); return iterator(__nd); } @@ -2072,7 +2154,8 @@ __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p) __node_allocator& __na = __node_alloc(); __tree_remove(__end_node()->__left_, static_cast<__node_base_pointer>(__np)); - __node_traits::destroy(__na, const_cast(_VSTD::addressof(*__p))); + __node_traits::destroy(__na, _NodeTypes::__get_ptr( + const_cast<__node_value_type&>(*__p))); __node_traits::deallocate(__na, __np, 1); return __r; } diff --git a/libcxx/include/map b/libcxx/include/map index c946ca0..a459146 100644 --- a/libcxx/include/map +++ b/libcxx/include/map @@ -626,33 +626,29 @@ union __value_type value_type __cc; __nc_value_type __nc; - template - _LIBCPP_INLINE_VISIBILITY - __value_type(_Args&& ...__args) - : __cc(std::forward<_Args>(__args)...) {} - - _LIBCPP_INLINE_VISIBILITY - __value_type(const __value_type& __v) - : __cc(__v.__cc) {} - - _LIBCPP_INLINE_VISIBILITY - __value_type(__value_type& __v) - : __cc(__v.__cc) {} - - _LIBCPP_INLINE_VISIBILITY - __value_type(__value_type&& __v) - : __nc(std::move(__v.__nc)) {} - _LIBCPP_INLINE_VISIBILITY __value_type& operator=(const __value_type& __v) {__nc = __v.__cc; return *this;} _LIBCPP_INLINE_VISIBILITY __value_type& operator=(__value_type&& __v) - {__nc = std::move(__v.__nc); return *this;} + {__nc = _VSTD::move(__v.__nc); return *this;} + template ::value + >::type + > _LIBCPP_INLINE_VISIBILITY - ~__value_type() {__cc.~value_type();} + __value_type& operator=(_ValueTp&& __v) { + __nc = _VSTD::forward<_ValueTp>(__v); return *this; + } + +private: + __value_type() _LIBCPP_EQUAL_DELETE; + ~__value_type() _LIBCPP_EQUAL_DELETE; + __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE; + __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE; }; #else @@ -666,18 +662,11 @@ struct __value_type value_type __cc; - _LIBCPP_INLINE_VISIBILITY - __value_type() {} - - template - _LIBCPP_INLINE_VISIBILITY - __value_type(const _A0& __a0) - : __cc(__a0) {} - - template - _LIBCPP_INLINE_VISIBILITY - __value_type(const _A0& __a0, const _A1& __a1) - : __cc(__a0, __a1) {} +private: + __value_type(); + __value_type(__value_type const&); + __value_type& operator=(__value_type const&); + ~__value_type(); }; #endif @@ -1051,18 +1040,18 @@ public: _LIBCPP_INLINE_VISIBILITY value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());} -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES -#ifndef _LIBCPP_HAS_NO_VARIADICS - +#ifndef _LIBCPP_CXX03_LANG template - pair - emplace(_Args&& ...__args); + _LIBCPP_INLINE_VISIBILITY + pair emplace(_Args&& ...__args) { + return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...); + } template - iterator - emplace_hint(const_iterator __p, _Args&& ...__args); - -#endif // _LIBCPP_HAS_NO_VARIADICS + _LIBCPP_INLINE_VISIBILITY + iterator emplace_hint(const_iterator __p, _Args&& ...__args) { + return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...); + } template ::value>::type> @@ -1076,7 +1065,7 @@ public: iterator insert(const_iterator __pos, _Pp&& __p) {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));} -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES +#endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY pair @@ -1088,14 +1077,15 @@ public: {return __tree_.__insert_unique(__p.__i_, __v);} #if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) + // TODO(EricWF): These functions are C++17 only but they should probably + // be exposed in C++11. _LIBCPP_INLINE_VISIBILITY pair - insert( value_type&& __v) {return __tree_.__insert_unique(_VSTD::forward(__v));} + insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));} _LIBCPP_INLINE_VISIBILITY - iterator - insert(const_iterator __p, value_type&& __v) - {return __tree_.__insert_unique(__p.__i_, _VSTD::forward(__v));} + iterator insert(const_iterator __p, value_type&& __v) + {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));} #endif template @@ -1331,16 +1321,10 @@ private: typedef __map_node_destructor<__node_allocator> _Dp; typedef unique_ptr<__node, _Dp> __node_holder; -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - __node_holder __construct_node(); - template - __node_holder __construct_node(_A0&& __a0); +#ifndef _LIBCPP_CXX03_LANG __node_holder __construct_node_with_key(key_type&& __k); -#ifndef _LIBCPP_HAS_NO_VARIADICS - template - __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); -#endif // _LIBCPP_HAS_NO_VARIADICS #endif + __node_holder __construct_node_with_key(const key_type& __k); __node_base_pointer const& @@ -1401,7 +1385,7 @@ map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __pa return __parent->__left_; } -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES +#ifndef _LIBCPP_CXX03_LANG template map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) @@ -1412,35 +1396,10 @@ map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) const_iterator __e = cend(); while (!__m.empty()) __tree_.__insert_unique(__e.__i_, - _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_)); + _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc)); } } -template -typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder -map<_Key, _Tp, _Compare, _Allocator>::__construct_node() -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first)); - __h.get_deleter().__first_constructed = true; - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); - __h.get_deleter().__second_constructed = true; - return __h; -} - -template -template -typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder -map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0) -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0)); - __h.get_deleter().__first_constructed = true; - __h.get_deleter().__second_constructed = true; - return __h; -} template typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder @@ -1455,26 +1414,7 @@ map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(key_type&& __k) return __h; } -#ifndef _LIBCPP_HAS_NO_VARIADICS - -template -template -typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder -map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args) -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_), - _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), - _VSTD::forward<_Args>(__args)...); - __h.get_deleter().__first_constructed = true; - __h.get_deleter().__second_constructed = true; - return __h; -} - -#endif // _LIBCPP_HAS_NO_VARIADICS - -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES +#endif // !_LIBCPP_CXX03_LANG template typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder @@ -1551,34 +1491,6 @@ map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const return static_cast<__node_pointer>(__child)->__value_.__cc.second; } -#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) - -template -template -pair::iterator, bool> -map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - pair __r = __tree_.__node_insert_unique(__h.get()); - if (__r.second) - __h.release(); - return __r; -} - -template -template -typename map<_Key, _Tp, _Compare, _Allocator>::iterator -map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p, - _Args&& ...__args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get()); - if (__r.__i_.__ptr_ == __h.get()) - __h.release(); - return __r; -} - -#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) template inline _LIBCPP_INLINE_VISIBILITY @@ -1876,18 +1788,19 @@ public: value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());} -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES -#ifndef _LIBCPP_HAS_NO_VARIADICS +#ifndef _LIBCPP_CXX03_LANG template - iterator - emplace(_Args&& ...__args); + _LIBCPP_INLINE_VISIBILITY + iterator emplace(_Args&& ...__args) { + return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...); + } template - iterator - emplace_hint(const_iterator __p, _Args&& ...__args); - -#endif // _LIBCPP_HAS_NO_VARIADICS + _LIBCPP_INLINE_VISIBILITY + iterator emplace_hint(const_iterator __p, _Args&& ...__args) { + return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...); + } template ::value>::type> @@ -1901,7 +1814,7 @@ public: iterator insert(const_iterator __pos, _Pp&& __p) {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));} -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES +#endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);} @@ -1911,12 +1824,15 @@ public: {return __tree_.__insert_multi(__p.__i_, __v);} #if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) + // TODO(EricWF): These functions are C++17 only but they should probably + // be exposed in C++11. _LIBCPP_INLINE_VISIBILITY - iterator insert( value_type&& __v) {return __tree_.__insert_multi(_VSTD::forward(__v));} + iterator insert(value_type&& __v) + {return __tree_.__insert_multi(_VSTD::move(__v));} _LIBCPP_INLINE_VISIBILITY iterator insert(const_iterator __p, value_type&& __v) - {return __tree_.__insert_multi(__p.__i_, _VSTD::forward(__v));} + {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));} #endif template @@ -2035,21 +1951,9 @@ private: typedef __map_node_destructor<__node_allocator> _Dp; typedef unique_ptr<__node, _Dp> __node_holder; - -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - __node_holder __construct_node(); - template - __node_holder - __construct_node(_A0&& __a0); -#ifndef _LIBCPP_HAS_NO_VARIADICS - template - __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); -#endif // _LIBCPP_HAS_NO_VARIADICS -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES }; -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - +#ifndef _LIBCPP_CXX03_LANG template multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a) : __tree_(_VSTD::move(__m.__tree_), __a) @@ -2059,82 +1963,10 @@ multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const alloca const_iterator __e = cend(); while (!__m.empty()) __tree_.__insert_multi(__e.__i_, - _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_)); + _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc)); } } - -template -typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder -multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node() -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first)); - __h.get_deleter().__first_constructed = true; - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); - __h.get_deleter().__second_constructed = true; - return __h; -} - -template -template -typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder -multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0) -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0)); - __h.get_deleter().__first_constructed = true; - __h.get_deleter().__second_constructed = true; - return __h; -} - -#ifndef _LIBCPP_HAS_NO_VARIADICS - -template -template -typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder -multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args) -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_), - _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), - _VSTD::forward<_Args>(__args)...); - __h.get_deleter().__first_constructed = true; - __h.get_deleter().__second_constructed = true; - return __h; -} - -#endif // _LIBCPP_HAS_NO_VARIADICS -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - -#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) - -template -template -typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator -multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - iterator __r = __tree_.__node_insert_multi(__h.get()); - __h.release(); - return __r; -} - -template -template -typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator -multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p, - _Args&& ...__args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get()); - __h.release(); - return __r; -} - -#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) +#endif template inline _LIBCPP_INLINE_VISIBILITY diff --git a/libcxx/test/std/containers/associative/map/map.modifiers/insert_allocator_requirements.pass.cpp b/libcxx/test/std/containers/associative/map/map.modifiers/insert_allocator_requirements.pass.cpp new file mode 100644 index 0000000..adc5b31 --- /dev/null +++ b/libcxx/test/std/containers/associative/map/map.modifiers/insert_allocator_requirements.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. +// +//===----------------------------------------------------------------------===// + +// + +// class map + +// insert(...); + +// UNSUPPORTED: c++98, c++03 + +#include +#include +#include + +#include "test_macros.h" +#include "count_new.hpp" +#include "container_test_types.h" + +template +void PrintInfo(int line, Arg&& arg) +{ + std::cout << "In " << __FILE__ << ":" << line << ":\n " << arg << "\n" << std::endl; +} +#define PRINT(msg) PrintInfo(__LINE__, msg) + +template +void testContainerInsert() +{ + typedef typename Container::value_type ValueTp; + typedef Container C; + typedef std::pair R; + ConstructController* cc = getConstructController(); + cc->reset(); + { + PRINT("Testing C::insert(const value_type&)"); + Container c; + const ValueTp v(42, 1); + cc->expect(); + assert(c.insert(v).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + const ValueTp v2(42, 1); + assert(c.insert(v2).second == false); + } + } + { + PRINT("Testing C::insert(value_type&)"); + Container c; + ValueTp v(42, 1); + cc->expect(); + assert(c.insert(v).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + ValueTp v2(42, 1); + assert(c.insert(v2).second == false); + } + } + { + PRINT("Testing C::insert(value_type&&)"); + Container c; + ValueTp v(42, 1); + cc->expect(); + assert(c.insert(std::move(v)).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + ValueTp v2(42, 1); + assert(c.insert(std::move(v2)).second == false); + } + } + { + PRINT("Testing C::insert(std::initializer_list)"); + Container c; + std::initializer_list il = { ValueTp(1, 1), ValueTp(2, 1) }; + cc->expect(2); + c.insert(il); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + c.insert(il); + } + } + { + PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&"); + Container c; + const ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1), ValueTp(3, 1) }; + cc->expect(3); + c.insert(std::begin(ValueList), std::end(ValueList)); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + c.insert(std::begin(ValueList), std::end(ValueList)); + } + } + { + PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&"); + Container c; + ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) }; + cc->expect(3); + c.insert(std::move_iterator(std::begin(ValueList)), + std::move_iterator(std::end(ValueList))); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + ValueTp ValueList2[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) }; + c.insert(std::move_iterator(std::begin(ValueList2)), + std::move_iterator(std::end(ValueList2))); + } + } + { + PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&"); + Container c; + ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) }; + cc->expect(3); + c.insert(std::begin(ValueList), std::end(ValueList)); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + c.insert(std::begin(ValueList), std::end(ValueList)); + } + } +} + + +int main() +{ + testContainerInsert >(); +} diff --git a/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_allocator_requirements.pass.cpp b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_allocator_requirements.pass.cpp new file mode 100644 index 0000000..8e3677d --- /dev/null +++ b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_allocator_requirements.pass.cpp @@ -0,0 +1,103 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// + +// class multimap + +// insert(...) + +// UNSUPPORTED: c++98, c++03 + +#include +#include +#include + +#include "test_macros.h" +#include "count_new.hpp" +#include "container_test_types.h" + +template +void PrintInfo(int line, Arg&& arg) +{ + std::cout << "In " << __FILE__ << ":" << line << ":\n " << arg << "\n" << std::endl; +} +#define PRINT(msg) PrintInfo(__LINE__, msg) + +template +void testContainerInsert() +{ + typedef typename Container::value_type ValueTp; + typedef Container C; + ConstructController* cc = getConstructController(); + cc->reset(); + { + PRINT("Testing C::insert(const value_type&)"); + Container c; + const ValueTp v(42, 1); + cc->expect(); + c.insert(v); + assert(!cc->unchecked()); + } + { + PRINT("Testing C::insert(value_type&)"); + Container c; + ValueTp v(42, 1); + cc->expect(); + c.insert(v); + assert(!cc->unchecked()); + } + { + PRINT("Testing C::insert(value_type&&)"); + Container c; + ValueTp v(42, 1); + cc->expect(); + c.insert(std::move(v)); + assert(!cc->unchecked()); + } + { + PRINT("Testing C::insert(std::initializer_list)"); + Container c; + std::initializer_list il = { ValueTp(1, 1), ValueTp(2, 1) }; + cc->expect(2); + c.insert(il); + assert(!cc->unchecked()); + } + { + PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&"); + Container c; + const ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1), ValueTp(3, 1) }; + cc->expect(3); + c.insert(std::begin(ValueList), std::end(ValueList)); + assert(!cc->unchecked()); + } + { + PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&"); + Container c; + ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) }; + cc->expect(3); + c.insert(std::move_iterator(std::begin(ValueList)), + std::move_iterator(std::end(ValueList))); + assert(!cc->unchecked()); + } + { + PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&"); + Container c; + ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) }; + cc->expect(3); + c.insert(std::begin(ValueList), std::end(ValueList)); + assert(!cc->unchecked()); + } +} + + +int main() +{ + testContainerInsert >(); +} diff --git a/libcxx/test/std/containers/associative/multiset/insert_allocator_requirements.pass.cpp b/libcxx/test/std/containers/associative/multiset/insert_allocator_requirements.pass.cpp new file mode 100644 index 0000000..a85c776 --- /dev/null +++ b/libcxx/test/std/containers/associative/multiset/insert_allocator_requirements.pass.cpp @@ -0,0 +1,102 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// + +// class multiset + +// insert(...) + +// UNSUPPORTED: c++98, c++03 + +#include +#include +#include + +#include "test_macros.h" +#include "count_new.hpp" +#include "container_test_types.h" + +template +void PrintInfo(int line, Arg&& arg) +{ + std::cout << "In " << __FILE__ << ":" << line << ":\n " << arg << "\n" << std::endl; +} +#define PRINT(...) PrintInfo(__LINE__, __VA_ARGS__) + +template +void testContainerInsert() +{ + typedef typename Container::value_type ValueTp; + typedef Container C; + ConstructController* cc = getConstructController(); + cc->reset(); + { + PRINT("Testing C::insert(const value_type&)"); + Container c; + const ValueTp v(42); + cc->expect(); + c.insert(v); + assert(!cc->unchecked()); + } + { + PRINT("Testing C::insert(value_type&)"); + Container c; + ValueTp v(42); + cc->expect(); + c.insert(v); + assert(!cc->unchecked()); + } + { + PRINT("Testing C::insert(value_type&&)"); + Container c; + ValueTp v(42); + cc->expect(); + c.insert(std::move(v)); + assert(!cc->unchecked()); + } + { + PRINT("Testing C::insert(std::initializer_list)"); + Container c; + std::initializer_list il = { ValueTp(1), ValueTp(2) }; + cc->expect(2); + c.insert(il); + assert(!cc->unchecked()); + } + { + PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&"); + Container c; + const ValueTp ValueList[] = { ValueTp(1), ValueTp(2), ValueTp(3) }; + cc->expect(3); + c.insert(std::begin(ValueList), std::end(ValueList)); + assert(!cc->unchecked()); + } + { + PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&"); + Container c; + ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) }; + cc->expect(3); + c.insert(std::move_iterator(std::begin(ValueList)), + std::move_iterator(std::end(ValueList))); + assert(!cc->unchecked()); + } + { + PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&"); + Container c; + ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) }; + cc->expect(3); + c.insert(std::begin(ValueList), std::end(ValueList)); + assert(!cc->unchecked()); + } +} + +int main() +{ + testContainerInsert >(); +} diff --git a/libcxx/test/std/containers/associative/set/insert_allocator_requirements.pass.cpp b/libcxx/test/std/containers/associative/set/insert_allocator_requirements.pass.cpp new file mode 100644 index 0000000..f083669 --- /dev/null +++ b/libcxx/test/std/containers/associative/set/insert_allocator_requirements.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. +// +//===----------------------------------------------------------------------===// + +// + +// class set + +// insert(...) + +// UNSUPPORTED: c++98, c++03 + +#include +#include +#include + +#include "test_macros.h" +#include "count_new.hpp" +#include "container_test_types.h" + +template +void PrintInfo(int line, Arg&& arg) +{ + std::cout << "In " << __FILE__ << ":" << line << ":\n " << arg << "\n" << std::endl; +} +#define PRINT(msg) PrintInfo(__LINE__, msg) + +template +void testContainerInsert() +{ + typedef typename Container::value_type ValueTp; + typedef Container C; + typedef std::pair R; + ConstructController* cc = getConstructController(); + cc->reset(); + { + PRINT("Testing C::insert(const value_type&)"); + Container c; + const ValueTp v(42); + cc->expect(); + assert(c.insert(v).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + const ValueTp v2(42); + assert(c.insert(v2).second == false); + } + } + { + PRINT("Testing C::insert(value_type&)"); + Container c; + ValueTp v(42); + cc->expect(); + assert(c.insert(v).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + ValueTp v2(42); + assert(c.insert(v2).second == false); + } + } + { + PRINT("Testing C::insert(value_type&&)"); + Container c; + ValueTp v(42); + cc->expect(); + assert(c.insert(std::move(v)).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + ValueTp v2(42); + assert(c.insert(std::move(v2)).second == false); + } + } + { + PRINT("Testing C::insert(std::initializer_list)"); + Container c; + std::initializer_list il = { ValueTp(1), ValueTp(2) }; + cc->expect(2); + c.insert(il); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + c.insert(il); + } + } + { + PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&"); + Container c; + const ValueTp ValueList[] = { ValueTp(1), ValueTp(2), ValueTp(3) }; + cc->expect(3); + c.insert(std::begin(ValueList), std::end(ValueList)); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + c.insert(std::begin(ValueList), std::end(ValueList)); + } + } + { + PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&"); + Container c; + ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) }; + cc->expect(3); + c.insert(std::move_iterator(std::begin(ValueList)), + std::move_iterator(std::end(ValueList))); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + ValueTp ValueList2[] = { ValueTp(1), ValueTp(2) , ValueTp(3) }; + c.insert(std::move_iterator(std::begin(ValueList2)), + std::move_iterator(std::end(ValueList2))); + } + } + { + PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&"); + Container c; + ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) }; + cc->expect(3); + c.insert(std::begin(ValueList), std::end(ValueList)); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + c.insert(std::begin(ValueList), std::end(ValueList)); + } + } +} + + +int main() +{ + testContainerInsert >(); +} -- 2.7.4