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 <map>
* 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<Key, Value>" to "__value_type<Key, Value>".
* 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
Cr-Mirrored-From: sso://chromium.googlesource.com/_direct/external/github.com/llvm/llvm-project
Cr-Mirrored-Commit: 5e3ea4dd7931a010de30ebef7606215b667ab529
diff --git a/include/map b/include/map
index c946ca0..a459146 100644
--- a/include/map
+++ b/include/map
@@ -626,33 +626,29 @@
value_type __cc;
__nc_value_type __nc;
- template <class ..._Args>
- _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 <class _ValueTp,
+ class = typename enable_if<
+ __is_same_uncvref<_ValueTp, value_type>::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 @@
value_type __cc;
- _LIBCPP_INLINE_VISIBILITY
- __value_type() {}
-
- template <class _A0>
- _LIBCPP_INLINE_VISIBILITY
- __value_type(const _A0& __a0)
- : __cc(__a0) {}
-
- template <class _A0, class _A1>
- _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 @@
_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 <class ..._Args>
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool> emplace(_Args&& ...__args) {
+ return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
+ }
template <class ..._Args>
- pair<iterator, bool>
- emplace(_Args&& ...__args);
-
- template <class ..._Args>
- 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 <class _Pp,
class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
@@ -1076,7 +1065,7 @@
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<iterator, bool>
@@ -1088,14 +1077,15 @@
{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<iterator, bool>
- insert( value_type&& __v) {return __tree_.__insert_unique(_VSTD::forward<value_type>(__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<value_type>(__v));}
+ iterator insert(const_iterator __p, value_type&& __v)
+ {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
#endif
template <class _InputIterator>
@@ -1331,16 +1321,10 @@
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 <class _A0>
- __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 <class _A0, class _A1, class ..._Args>
- __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 @@
return __parent->__left_;
}
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
template <class _Key, class _Tp, class _Compare, class _Allocator>
map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
@@ -1412,35 +1396,10 @@
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 <class _Key, class _Tp, class _Compare, class _Allocator>
-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 <class _Key, class _Tp, class _Compare, class _Allocator>
-template <class _A0>
-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 <class _Key, class _Tp, class _Compare, class _Allocator>
typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
@@ -1455,26 +1414,7 @@
return __h;
}
-#ifndef _LIBCPP_HAS_NO_VARIADICS
-
-template <class _Key, class _Tp, class _Compare, class _Allocator>
-template <class _A0, class _A1, class ..._Args>
-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 <class _Key, class _Tp, class _Compare, class _Allocator>
typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
@@ -1551,34 +1491,6 @@
return static_cast<__node_pointer>(__child)->__value_.__cc.second;
}
-#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
-
-template <class _Key, class _Tp, class _Compare, class _Allocator>
-template <class ..._Args>
-pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool>
-map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
-{
- __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
- pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get());
- if (__r.second)
- __h.release();
- return __r;
-}
-
-template <class _Key, class _Tp, class _Compare, class _Allocator>
-template <class ..._Args>
-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 <class _Key, class _Tp, class _Compare, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
@@ -1876,18 +1788,19 @@
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 <class ..._Args>
- iterator
- emplace(_Args&& ...__args);
+ _LIBCPP_INLINE_VISIBILITY
+ iterator emplace(_Args&& ...__args) {
+ return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
+ }
template <class ..._Args>
- 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 <class _Pp,
class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
@@ -1901,7 +1814,7 @@
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 @@
{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<value_type>(__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<value_type>(__v));}
+ {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
#endif
template <class _InputIterator>
@@ -2035,21 +1951,9 @@
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 <class _A0>
- __node_holder
- __construct_node(_A0&& __a0);
-#ifndef _LIBCPP_HAS_NO_VARIADICS
- template <class _A0, class _A1, class ..._Args>
- __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 <class _Key, class _Tp, class _Compare, class _Allocator>
multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
: __tree_(_VSTD::move(__m.__tree_), __a)
@@ -2059,82 +1963,10 @@
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 <class _Key, class _Tp, class _Compare, class _Allocator>
-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 <class _Key, class _Tp, class _Compare, class _Allocator>
-template <class _A0>
-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 <class _Key, class _Tp, class _Compare, class _Allocator>
-template <class _A0, class _A1, class ..._Args>
-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 <class _Key, class _Tp, class _Compare, class _Allocator>
-template <class ..._Args>
-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 <class _Key, class _Tp, class _Compare, class _Allocator>
-template <class ..._Args>
-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 <class _Key, class _Tp, class _Compare, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY