Skip to content

Commit fa1f613

Browse files
EricWFEricWF
committedApr 15, 2016
Extract key to avoid preemptive mallocs in insert/emplace in associative containers
Summary: This patch applies Duncan's work on __hash_table to __tree. Reviewers: mclow.lists, dexonsmith Subscribers: dexonsmith, cfe-commits Differential Revision: http://reviews.llvm.org/D18637 llvm-svn: 266491
1 parent db6861e commit fa1f613

17 files changed

+1004
-1018
lines changed
 

‎libcxx/include/__hash_table

-16
Original file line numberDiff line numberDiff line change
@@ -100,22 +100,6 @@ __next_hash_pow2(size_t __n)
100100
return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1));
101101
}
102102

103-
#ifndef _LIBCPP_CXX03_LANG
104-
struct __extract_key_fail_tag {};
105-
struct __extract_key_self_tag {};
106-
struct __extract_key_first_tag {};
107-
108-
template <class _ValTy, class _Key,
109-
class _RawValTy = typename __unconstref<_ValTy>::type>
110-
struct __can_extract_key
111-
: conditional<is_same<_RawValTy, _Key>::value, __extract_key_self_tag,
112-
__extract_key_fail_tag>::type {};
113-
114-
template <class _Pair, class _Key, class _First, class _Second>
115-
struct __can_extract_key<_Pair, _Key, pair<_First, _Second>>
116-
: conditional<is_same<typename remove_const<_First>::type, _Key>::value,
117-
__extract_key_first_tag, __extract_key_fail_tag>::type {};
118-
#endif
119103

120104
template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;
121105

‎libcxx/include/__tree

+73-4
Original file line numberDiff line numberDiff line change
@@ -1064,16 +1064,85 @@ public:
10641064
__emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...);
10651065

10661066
template <class... _Args>
1067-
pair<iterator, bool> __emplace_unique(_Args&&... __args);
1067+
pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
10681068

10691069
template <class... _Args>
1070-
iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args);
1070+
iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args);
10711071

10721072
template <class... _Args>
10731073
iterator __emplace_multi(_Args&&... __args);
10741074

10751075
template <class... _Args>
10761076
iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
1077+
1078+
template <class _Pp>
1079+
_LIBCPP_INLINE_VISIBILITY
1080+
pair<iterator, bool> __emplace_unique(_Pp&& __x) {
1081+
return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x),
1082+
__can_extract_key<_Pp, key_type>());
1083+
}
1084+
1085+
template <class... _Args>
1086+
_LIBCPP_INLINE_VISIBILITY
1087+
pair<iterator, bool> __emplace_unique(_Args&&... __args) {
1088+
return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...);
1089+
}
1090+
1091+
template <class _Pp>
1092+
_LIBCPP_INLINE_VISIBILITY
1093+
pair<iterator, bool>
1094+
__emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
1095+
return __emplace_unique_impl(_VSTD::forward<_Pp>(__x));
1096+
}
1097+
1098+
template <class _Pp>
1099+
_LIBCPP_INLINE_VISIBILITY
1100+
pair<iterator, bool>
1101+
__emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
1102+
return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x));
1103+
}
1104+
1105+
template <class _Pp>
1106+
_LIBCPP_INLINE_VISIBILITY
1107+
pair<iterator, bool>
1108+
__emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
1109+
return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x));
1110+
}
1111+
1112+
template <class _Pp>
1113+
_LIBCPP_INLINE_VISIBILITY
1114+
iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) {
1115+
return __emplace_hint_unique_extract_key(__p, _VSTD::forward<_Pp>(__x),
1116+
__can_extract_key<_Pp, key_type>());
1117+
}
1118+
1119+
template <class... _Args>
1120+
_LIBCPP_INLINE_VISIBILITY
1121+
iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) {
1122+
return __emplace_hint_unique_impl(__p, _VSTD::forward<_Args>(__args)...);
1123+
}
1124+
1125+
template <class _Pp>
1126+
_LIBCPP_INLINE_VISIBILITY
1127+
iterator
1128+
__emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) {
1129+
return __emplace_hint_unique_impl(__p, _VSTD::forward<_Pp>(__x));
1130+
}
1131+
1132+
template <class _Pp>
1133+
_LIBCPP_INLINE_VISIBILITY
1134+
iterator
1135+
__emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) {
1136+
return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x));
1137+
}
1138+
1139+
template <class _Pp>
1140+
_LIBCPP_INLINE_VISIBILITY
1141+
iterator
1142+
__emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) {
1143+
return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x));
1144+
}
1145+
10771146
#else
10781147
template <class _Key, class _Args>
10791148
_LIBCPP_INLINE_VISIBILITY
@@ -1989,7 +2058,7 @@ __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args)
19892058
template <class _Tp, class _Compare, class _Allocator>
19902059
template <class... _Args>
19912060
pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
1992-
__tree<_Tp, _Compare, _Allocator>::__emplace_unique(_Args&&... __args)
2061+
__tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args)
19932062
{
19942063
__node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
19952064
__node_base_pointer __parent;
@@ -2008,7 +2077,7 @@ __tree<_Tp, _Compare, _Allocator>::__emplace_unique(_Args&&... __args)
20082077
template <class _Tp, class _Compare, class _Allocator>
20092078
template <class... _Args>
20102079
typename __tree<_Tp, _Compare, _Allocator>::iterator
2011-
__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique(const_iterator __p, _Args&&... __args)
2080+
__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args)
20122081
{
20132082
__node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
20142083
__node_base_pointer __parent;

‎libcxx/include/__tuple

-2
Original file line numberDiff line numberDiff line change
@@ -95,8 +95,6 @@ get(const tuple<_Tp...>&&) _NOEXCEPT;
9595

9696
// pair specializations
9797

98-
template <class _T1, class _T2> struct _LIBCPP_TYPE_VIS_ONLY pair;
99-
10098
template <class _T1, class _T2> struct __tuple_like<pair<_T1, _T2> > : true_type {};
10199

102100
template <size_t _Ip, class _T1, class _T2>

‎libcxx/include/type_traits

+20
Original file line numberDiff line numberDiff line change
@@ -368,6 +368,8 @@ namespace std
368368

369369
_LIBCPP_BEGIN_NAMESPACE_STD
370370

371+
template <class _T1, class _T2> struct _LIBCPP_TYPE_VIS_ONLY pair;
372+
371373
template <class>
372374
struct __void_t { typedef void type; };
373375

@@ -4434,6 +4436,24 @@ template<class _Tp> constexpr bool negation_v = negation<_Tp>::value;
44344436
# endif // _LIBCPP_HAS_NO_VARIADICS
44354437
#endif // _LIBCPP_STD_VER > 14
44364438

4439+
// These traits are used in __tree and __hash_table
4440+
#ifndef _LIBCPP_CXX03_LANG
4441+
struct __extract_key_fail_tag {};
4442+
struct __extract_key_self_tag {};
4443+
struct __extract_key_first_tag {};
4444+
4445+
template <class _ValTy, class _Key,
4446+
class _RawValTy = typename __unconstref<_ValTy>::type>
4447+
struct __can_extract_key
4448+
: conditional<is_same<_RawValTy, _Key>::value, __extract_key_self_tag,
4449+
__extract_key_fail_tag>::type {};
4450+
4451+
template <class _Pair, class _Key, class _First, class _Second>
4452+
struct __can_extract_key<_Pair, _Key, pair<_First, _Second>>
4453+
: conditional<is_same<typename remove_const<_First>::type, _Key>::value,
4454+
__extract_key_first_tag, __extract_key_fail_tag>::type {};
4455+
#endif
4456+
44374457
_LIBCPP_END_NAMESPACE_STD
44384458

44394459
#endif // _LIBCPP_TYPE_TRAITS

‎libcxx/test/std/containers/associative/map/map.modifiers/insert_allocator_requirements.pass.cpp

-137
This file was deleted.

‎libcxx/test/std/containers/associative/map/map.modifiers/insert_and_emplace_allocator_requirements.pass.cpp

+30
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
//===----------------------------------------------------------------------===//
2+
//
3+
// The LLVM Compiler Infrastructure
4+
//
5+
// This file is dual licensed under the MIT and the University of Illinois Open
6+
// Source Licenses. See LICENSE.TXT for details.
7+
//
8+
//===----------------------------------------------------------------------===//
9+
10+
// <map>
11+
12+
// class map
13+
14+
// insert(...);
15+
// emplace(...);
16+
// emplace_hint(...);
17+
18+
// UNSUPPORTED: c++98, c++03
19+
20+
#include <map>
21+
22+
#include "container_test_types.h"
23+
#include "../../../map_allocator_requirement_test_templates.h"
24+
25+
int main()
26+
{
27+
testMapInsert<TCT::map<> >();
28+
testMapEmplace<TCT::map<> >();
29+
testMapEmplaceHint<TCT::map<> >();
30+
}

0 commit comments

Comments
 (0)
Please sign in to comment.