Teach map/unordered_map how to optimize 'emplace(Key, T)'.
In cases where emplace is called with two arguments and the first one
matches the key_type we can Key to check for duplicates before allocating.
This patch expands on work done by dexonsmith@apple.com.
git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@266498 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/__hash_table b/include/__hash_table
index 2ea1a30..13ab928 100644
--- a/include/__hash_table
+++ b/include/__hash_table
@@ -1056,6 +1056,17 @@
return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x),
__can_extract_key<_Pp, key_type>());
}
+
+ template <class _First, class _Second>
+ _LIBCPP_INLINE_VISIBILITY
+ typename enable_if<
+ __can_extract_map_key<_First, key_type, __container_value_type>::value,
+ pair<iterator, bool>
+ >::type __emplace_unique(_First&& __f, _Second&& __s) {
+ return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f),
+ _VSTD::forward<_Second>(__s));
+ }
+
template <class... _Args>
_LIBCPP_INLINE_VISIBILITY
pair<iterator, bool> __emplace_unique(_Args&&... __args) {
diff --git a/include/__tree b/include/__tree
index eb6ff05..89707e3 100644
--- a/include/__tree
+++ b/include/__tree
@@ -1082,6 +1082,16 @@
__can_extract_key<_Pp, key_type>());
}
+ template <class _First, class _Second>
+ _LIBCPP_INLINE_VISIBILITY
+ typename enable_if<
+ __can_extract_map_key<_First, key_type, __container_value_type>::value,
+ pair<iterator, bool>
+ >::type __emplace_unique(_First&& __f, _Second&& __s) {
+ return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f),
+ _VSTD::forward<_Second>(__s));
+ }
+
template <class... _Args>
_LIBCPP_INLINE_VISIBILITY
pair<iterator, bool> __emplace_unique(_Args&&... __args) {
@@ -1116,6 +1126,17 @@
__can_extract_key<_Pp, key_type>());
}
+ template <class _First, class _Second>
+ _LIBCPP_INLINE_VISIBILITY
+ typename enable_if<
+ __can_extract_map_key<_First, key_type, __container_value_type>::value,
+ iterator
+ >::type __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) {
+ return __emplace_hint_unique_key_args(__p, __f,
+ _VSTD::forward<_First>(__f),
+ _VSTD::forward<_Second>(__s));
+ }
+
template <class... _Args>
_LIBCPP_INLINE_VISIBILITY
iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) {
diff --git a/include/type_traits b/include/type_traits
index 12e24b7..b7b0d4d 100644
--- a/include/type_traits
+++ b/include/type_traits
@@ -4452,6 +4452,21 @@
struct __can_extract_key<_Pair, _Key, pair<_First, _Second>>
: conditional<is_same<typename remove_const<_First>::type, _Key>::value,
__extract_key_first_tag, __extract_key_fail_tag>::type {};
+
+// __can_extract_map_key uses true_type/false_type instead of the tags.
+// It returns true if _Key != _ContainerValueTy (the container is a map not a set)
+// and _ValTy == _Key.
+template <class _ValTy, class _Key, class _ContainerValueTy,
+ class _RawValTy = typename __unconstref<_ValTy>::type>
+struct __can_extract_map_key
+ : integral_constant<bool, is_same<_RawValTy, _Key>::value> {};
+
+// This specialization returns __extract_key_fail_tag for non-map containers
+// because _Key == _ContainerValueTy
+template <class _ValTy, class _Key, class _RawValTy>
+struct __can_extract_map_key<_ValTy, _Key, _Key, _RawValTy>
+ : false_type {};
+
#endif
_LIBCPP_END_NAMESPACE_STD
diff --git a/test/std/containers/map_allocator_requirement_test_templates.h b/test/std/containers/map_allocator_requirement_test_templates.h
index b5958f7..91b209d 100644
--- a/test/std/containers/map_allocator_requirement_test_templates.h
+++ b/test/std/containers/map_allocator_requirement_test_templates.h
@@ -231,6 +231,62 @@
assert(c.emplace(std::move(v2)).second == false);
}
}
+ {
+ CHECKPOINT("Testing C::emplace(const Key&, ConvertibleToMapped&&)");
+ Container c;
+ const Key k(42);
+ cc->expect<Key const&, int&&>();
+ assert(c.emplace(k, 1).second);
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ const Key k2(42);
+ assert(c.emplace(k2, 2).second == false);
+ }
+ }
+ {
+ CHECKPOINT("Testing C::emplace(Key&, Mapped&)");
+ Container c;
+ Key k(42);
+ Mapped m(1);
+ cc->expect<Key&, Mapped&>();
+ assert(c.emplace(k, m).second);
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ Key k2(42);
+ assert(c.emplace(k2, m).second == false);
+ }
+ }
+ {
+ CHECKPOINT("Testing C::emplace(Key&&, Mapped&&)");
+ Container c;
+ Key k(42);
+ Mapped m(1);
+ cc->expect<Key&&, Mapped&&>();
+ assert(c.emplace(std::move(k), std::move(m)).second);
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ Key k2(42);
+ Mapped m2(2);
+ assert(c.emplace(std::move(k2), std::move(m2)).second == false);
+ }
+ }
+ {
+ CHECKPOINT("Testing C::emplace(ConvertibleToKey&&, ConvertibleToMapped&&)");
+ Container c;
+ cc->expect<int&&, int&&>();
+ assert(c.emplace(42, 1).second);
+ assert(!cc->unchecked());
+ {
+ // test that emplacing a duplicate item allocates. We cannot optimize
+ // this case because int&& does not match the type of key exactly.
+ cc->expect<int&&, int&&>();
+ assert(c.emplace(42, 1).second == false);
+ assert(!cc->unchecked());
+ }
+ }
}
@@ -347,6 +403,78 @@
assert(c.size() == 1);
}
}
+ {
+ CHECKPOINT("Testing C::emplace_hint(p, const Key&, ConvertibleToMapped&&)");
+ Container c;
+ const Key k(42);
+ cc->expect<Key const&, int&&>();
+ It ret = c.emplace_hint(c.end(), k, 42);
+ assert(ret != c.end());
+ assert(c.size() == 1);
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ const Key k2(42);
+ It ret2 = c.emplace_hint(c.begin(), k2, 1);
+ assert(&(*ret2) == &(*ret));
+ assert(c.size() == 1);
+ }
+ }
+ {
+ CHECKPOINT("Testing C::emplace_hint(p, Key&, Mapped&)");
+ Container c;
+ Key k(42);
+ Mapped m(1);
+ cc->expect<Key&, Mapped&>();
+ It ret = c.emplace_hint(c.end(), k, m);
+ assert(ret != c.end());
+ assert(c.size() == 1);
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ Key k2(42);
+ Mapped m2(2);
+ It ret2 = c.emplace_hint(c.begin(), k2, m2);
+ assert(&(*ret2) == &(*ret));
+ assert(c.size() == 1);
+ }
+ }
+ {
+ CHECKPOINT("Testing C::emplace_hint(p, Key&&, Mapped&&)");
+ Container c;
+ Key k(42);
+ Mapped m(1);
+ cc->expect<Key&&, Mapped&&>();
+ It ret = c.emplace_hint(c.end(), std::move(k), std::move(m));
+ assert(ret != c.end());
+ assert(c.size() == 1);
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ Key k2(42);
+ Mapped m2(2);
+ It ret2 = c.emplace_hint(c.begin(), std::move(k2), std::move(m2));
+ assert(&(*ret2) == &(*ret));
+ assert(c.size() == 1);
+ }
+ }
+ {
+ CHECKPOINT("Testing C::emplace_hint(p, ConvertibleToKey&&, ConvertibleToMapped&&)");
+ Container c;
+ cc->expect<int&&, int&&>();
+ It ret = c.emplace_hint(c.end(), 42, 1);
+ assert(ret != c.end());
+ assert(c.size() == 1);
+ assert(!cc->unchecked());
+ {
+ cc->expect<int&&, int&&>();
+ It ret2 = c.emplace_hint(c.begin(), 42, 2);
+ assert(&(*ret2) == &(*ret));
+ assert(c.size() == 1);
+ assert(!cc->unchecked());
+ }
+ }
+
}
@@ -414,6 +542,7 @@
c.insert(std::begin(ValueList), std::end(ValueList));
assert(!cc->unchecked());
}
+
}
-#endif
\ No newline at end of file
+#endif
diff --git a/test/std/containers/set_allocator_requirement_test_templates.h b/test/std/containers/set_allocator_requirement_test_templates.h
index fe72bf8..2e3346f 100644
--- a/test/std/containers/set_allocator_requirement_test_templates.h
+++ b/test/std/containers/set_allocator_requirement_test_templates.h
@@ -351,6 +351,4 @@
}
}
-
-
-#endif
\ No newline at end of file
+#endif
diff --git a/test/std/containers/unord/unord.map/unord.map.modifiers/insert_and_emplace_allocator_requirements.pass.cpp b/test/std/containers/unord/unord.map/unord.map.modifiers/insert_and_emplace_allocator_requirements.pass.cpp
index 5ee206a..3b44e94 100644
--- a/test/std/containers/unord/unord.map/unord.map.modifiers/insert_and_emplace_allocator_requirements.pass.cpp
+++ b/test/std/containers/unord/unord.map/unord.map.modifiers/insert_and_emplace_allocator_requirements.pass.cpp
@@ -26,4 +26,5 @@
{
testMapInsert<TCT::unordered_map<> >();
testMapEmplace<TCT::unordered_map<> >();
+ testMapEmplaceHint<TCT::unordered_map<> >();
}
diff --git a/test/support/container_test_types.h b/test/support/container_test_types.h
index 7a3f5ac..0b97f2e 100644
--- a/test/support/container_test_types.h
+++ b/test/support/container_test_types.h
@@ -158,6 +158,11 @@
bool m_allow_unchecked;
int m_expected_count;
+ void clear() {
+ m_expected_args = nullptr;
+ m_expected_count = -1;
+ }
+
// Check for and consume an expected construction added by 'expect'.
// Return true if the construction was expected and false otherwise.
// This should only be called by 'Allocator.construct'.