Hi mclow.lists, danalbert,
when `unordered_set::insert(value_type&&)` was called it would be treated like
`unordered_set::emplace(Args&&)` and it would allocate and construct a node
before trying to insert it.
This caused unnecessary allocations when the value was already in the set. This
patch adds an overload to `__hash_table::__insert_unique` that specifically
handles `value_type&&` more link `value_type const &`.
This patch also adds a single unified insert function for values into
`__hash_table` called `__insert_unique_value` that handles the cases for
`__insert_unique(value_type&&)` and `__insert_unique(value_type const &)`.
This patch fixes PR12999: http://llvm.org/bugs/show_bug.cgi?id=12999.
http://reviews.llvm.org/D7570
Files:
include/__hash_table
test/libcxx/containers/unord/unord.set/insert_dup_alloc.pass.cpp
EMAIL PREFERENCES
http://reviews.llvm.org/settings/panel/emailpreferences/
Index: include/__hash_table
===================================================================
--- include/__hash_table
+++ include/__hash_table
@@ -909,11 +909,21 @@
iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+ template <class _ValueTp>
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool> __insert_unique_value(_ValueTp&& __x);
+#else
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool> __insert_unique_value(const value_type& __x);
+#endif
+
pair<iterator, bool> __insert_unique(const value_type& __x);
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+ pair<iterator, bool> __insert_unique(value_type&& __x);
template <class _Pp>
- pair<iterator, bool> __insert_unique(_Pp&& __x);
+ pair<iterator, bool> __insert_unique(_Pp&& __x);
#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
@@ -1752,6 +1762,26 @@
pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x)
{
+ return __insert_unique_value(__x);
+}
+
+
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _ValueTp>
+_LIBCPP_INLINE_VISIBILITY
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(_ValueTp&& __x)
+#else
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+_LIBCPP_INLINE_VISIBILITY
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(const value_type& __x)
+#endif
+{
+#if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
+ typedef const value_type& _ValueTp;
+#endif
size_t __hash = hash_function()(__x);
size_type __bc = bucket_count();
bool __inserted = false;
@@ -1773,7 +1803,7 @@
}
}
{
- __node_holder __h = __construct_node(__x, __hash);
+ __node_holder __h = __construct_node(_VSTD::forward<_ValueTp>(__x), __hash);
if (size()+1 > __bc * max_load_factor() || __bc == 0)
{
rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
@@ -1857,6 +1887,13 @@
#endif // _LIBCPP_HAS_NO_VARIADICS
template <class _Tp, class _Hash, class _Equal, class _Alloc>
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(value_type&& __x)
+{
+ return __insert_unique_value(_VSTD::move(__x));
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
template <class _Pp>
pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x)
Index: test/libcxx/containers/unord/unord.set/insert_dup_alloc.pass.cpp
===================================================================
--- /dev/null
+++ test/libcxx/containers/unord/unord.set/insert_dup_alloc.pass.cpp
@@ -0,0 +1,48 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_set. See PR12999 http://llvm.org/bugs/show_bug.cgi?id=12999
+
+#include <cassert>
+#include <unordered_set>
+#include "count_new.hpp"
+#include "MoveOnly.h"
+
+int main()
+{
+ {
+ std::unordered_set<int> s;
+ assert(globalMemCounter.checkNewCalledEq(0));
+
+ for(int i=0; i < 100; ++i)
+ s.insert(3);
+
+ assert(s.size() == 1);
+ assert(s.count(3) == 1);
+ assert(globalMemCounter.checkNewCalledEq(2));
+ }
+ assert(globalMemCounter.checkOutstandingNewEq(0));
+ globalMemCounter.reset();
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+ {
+ std::unordered_set<MoveOnly> s;
+ assert(globalMemCounter.checkNewCalledEq(0));
+
+ for(int i=0; i<100; i++)
+ s.insert(MoveOnly(3));
+
+ assert(s.size() == 1);
+ assert(s.count(MoveOnly(3)) == 1);
+ assert(globalMemCounter.checkNewCalledEq(2));
+ }
+ assert(globalMemCounter.checkOutstandingNewEq(0));
+ globalMemCounter.reset();
+#endif
+}
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
