dexonsmith updated this revision to Diff 50869.
dexonsmith added a comment.
Eric and I had a quick chat on IRC.
- The asymmetric usage of __extract_key and __can_extract_key was awkward, as
Eric pointed out already.
- However, a symmetric __extract_key would have caused Clang (and other
compilers) to IRGen extra copies of operator().
- Eric suggested using a custom tag type (instead of true_type/false_type) to
avoid the problem entirely.
I implemented that in this updated patch, and it's way cleaner. I'm using:
- __extract_key_fail_tag: cannot extract key.
- __extract_key_self_tag: use the argument itself as the key.
- __extract_key_first_tag: use ".first" on the argument to grab the key.
http://reviews.llvm.org/D16360
Files:
include/__hash_table
test/libcxx/containers/unord/unord.map/insert_dup_alloc.pass.cpp
test/libcxx/containers/unord/unord.set/insert_dup_alloc.pass.cpp
Index: test/libcxx/containers/unord/unord.set/insert_dup_alloc.pass.cpp
===================================================================
--- test/libcxx/containers/unord/unord.set/insert_dup_alloc.pass.cpp
+++ test/libcxx/containers/unord/unord.set/insert_dup_alloc.pass.cpp
@@ -60,6 +60,21 @@
const ValueTp v(3);
assert(!c.insert(v).second);
}
+
+ PRINT("Checking for mallocs in emplace(value_type&&)");
+ assert(!c.emplace(ValueTp(3)).second);
+
+ PRINT("Checking for mallocs in emplace(value_type&)");
+ {
+ ValueTp v(3);
+ assert(!c.emplace(v).second);
+ }
+
+ PRINT("Checking for mallocs in emplace(const value_type&)");
+ {
+ const ValueTp v(3);
+ assert(!c.emplace(v).second);
+ }
}
int main()
Index: test/libcxx/containers/unord/unord.map/insert_dup_alloc.pass.cpp
===================================================================
--- /dev/null
+++ test/libcxx/containers/unord/unord.map/insert_dup_alloc.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.
+//
+//===----------------------------------------------------------------------===//
+
+// Check that we don't allocate when trying to insert a duplicate value into a
+// unordered_map.
+
+#include <cassert>
+#include <iostream>
+#include <unordered_map>
+
+#include "container_test_types.h"
+#include "count_new.hpp"
+#include "test_macros.h"
+
+#if TEST_STD_VER >= 11
+template <class Arg>
+void PrintInfo(int line, Arg&& arg)
+#else
+template <class Arg>
+void PrintInfo(int line, Arg arg)
+#endif
+{
+ std::cout << "In " << __FILE__ << ":" << line << ":\n " << arg << "\n" << std::endl;
+}
+#define PRINT(...) PrintInfo(__LINE__, __VA_ARGS__)
+
+template <class Container>
+void testContainerInsert()
+{
+ typedef typename Container::value_type ValueTp;
+ typedef std::pair<typename ValueTp::first_type, typename ValueTp::second_type>
+ PairTp;
+ typedef Container C;
+ typedef std::pair<typename C::iterator, bool> R;
+ ConstructController* cc = getConstructController();
+ cc->reset();
+ Container c;
+ cc->expect<ValueTp&&>();
+
+ PRINT("Expect a malloc in initial insertion");
+ assert(c.insert(ValueTp(3, 4)).second);
+ assert(!cc->unchecked());
+ DisableAllocationGuard g;
+
+ PRINT("Checking for mallocs in insert(value_type&&)");
+ assert(!c.insert(ValueTp(3, 4)).second);
+ assert(!c.insert(PairTp(3, 4)).second);
+
+ PRINT("Checking for mallocs in insert(value_type&)");
+ {
+ ValueTp v(3, 4);
+ assert(!c.insert(v).second);
+ }
+ {
+ PairTp v(3, 4);
+ assert(!c.insert(v).second);
+ }
+
+ PRINT("Checking for mallocs in insert(const value_type&)");
+ {
+ const ValueTp v(3, 4);
+ assert(!c.insert(v).second);
+ }
+ {
+ const PairTp v(3, 4);
+ assert(!c.insert(v).second);
+ }
+
+ PRINT("Checking for mallocs in emplace(value_type&&)");
+ assert(!c.emplace(ValueTp(3, 4)).second);
+ assert(!c.emplace(PairTp(3, 4)).second);
+
+ PRINT("Checking for mallocs in emplace(value_type&)");
+ {
+ ValueTp v(3, 4);
+ assert(!c.emplace(v).second);
+ }
+ {
+ PairTp v(3, 4);
+ assert(!c.emplace(v).second);
+ }
+
+ PRINT("Checking for mallocs in emplace(const value_type&)");
+ {
+ const ValueTp v(3, 4);
+ assert(!c.emplace(v).second);
+ }
+ {
+ const PairTp v(3, 4);
+ assert(!c.emplace(v).second);
+ }
+}
+
+int main()
+{
+ testContainerInsert<TCT::unordered_map<> >();
+}
Index: include/__hash_table
===================================================================
--- include/__hash_table
+++ include/__hash_table
@@ -100,6 +100,21 @@
return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1));
}
+struct __extract_key_fail_tag {};
+struct __extract_key_self_tag {};
+struct __extract_key_first_tag {};
+
+template <class _ValTy, class _Key,
+ class _RawValTy = typename __unconstref<_ValTy>::type>
+struct __can_extract_key
+ : conditional<is_same<_RawValTy, _Key>::value, __extract_key_self_tag,
+ __extract_key_fail_tag>::type {};
+
+template <class _Pair, class _Key, class _First, class _Second>
+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 {};
+
template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;
template <class _NodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_iterator;
@@ -903,6 +918,7 @@
typedef typename _NodeTypes::__node_value_type __node_value_type;
typedef typename _NodeTypes::__container_value_type __container_value_type;
+ typedef typename _NodeTypes::key_type key_type;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef typename __alloc_traits::pointer pointer;
@@ -1041,13 +1057,49 @@
#ifndef _LIBCPP_CXX03_LANG
template <class _Key, class ..._Args>
+ _LIBCPP_INLINE_VISIBILITY
pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
template <class... _Args>
- pair<iterator, bool> __emplace_unique(_Args&&... __args);
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
+
+ template <class _Pp>
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool> __emplace_unique(_Pp&& __x) {
+ return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x),
+ __can_extract_key<_Pp, key_type>());
+ }
+ template <class... _Args>
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool> __emplace_unique(_Args&&... __args) {
+ return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...);
+ }
+
+ template <class _Pp>
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool>
+ __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
+ return __emplace_unique_impl(_VSTD::forward<_Pp>(__x));
+ }
+ template <class _Pp>
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool>
+ __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
+ return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x));
+ }
+ template <class _Pp>
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool>
+ __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
+ return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x));
+ }
+
template <class... _Args>
+ _LIBCPP_INLINE_VISIBILITY
iterator __emplace_multi(_Args&&... __args);
template <class... _Args>
+ _LIBCPP_INLINE_VISIBILITY
iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
@@ -1989,7 +2041,7 @@
template <class _Tp, class _Hash, class _Equal, class _Alloc>
template <class... _Args>
pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args)
{
__node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
pair<iterator, bool> __r = __node_insert_unique(__h.get());
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
