dexonsmith updated this revision to Diff 46603.
dexonsmith added a comment.
Eric, I think this addresses all of your review comments.
There are a couple of prep NFC commits that I sent for review:
http://lists.llvm.org/pipermail/cfe-commits/Week-of-Mon-20160201/148661.html
http://lists.llvm.org/pipermail/cfe-commits/Week-of-Mon-20160201/148662.html
What's changed here:
- insert() now calls emplace() -- this could be split out (it is locally).
- Renamed __hash_table::__insert_unique_value to __insert_unique_key_value and
updated callers -- this could also be split out (it is locally).
- Moved the dispatch logic to emplace().
- Changed the dispatch logic to use a type trait (although it's still
multi-stage to find the number of arguments).
- Removed the unnecessary #ifdefs in the hasher (etc.).
http://reviews.llvm.org/D16360
Files:
include/__hash_table
include/unordered_map
test/libcxx/containers/unord/unord.map/insert_dup_alloc.pass.cpp
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,87 @@
+//===----------------------------------------------------------------------===//
+//
+// 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 <unordered_map>
+#include "count_new.hpp"
+#include "MoveOnly.h"
+
+int main()
+{
+ {
+ std::unordered_map<int, int> s;
+ assert(globalMemCounter.checkNewCalledEq(0));
+
+ for(int i=0; i < 100; ++i) {
+ s.insert(std::make_pair(3, i));
+ s.insert(std::make_pair(3, unsigned(i)));
+ s.insert(s.end(), std::make_pair(3, i));
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+ s.emplace(std::make_pair(3, i));
+ s.emplace_hint(s.end(), std::make_pair(3, i));
+#endif
+ {
+ const std::pair<int, int> P(3, i);
+ s.insert(P);
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+ s.emplace(P);
+ s.emplace_hint(s.end(), P);
+#endif
+ }
+ }
+
+ assert(s.size() == 1);
+ assert(s.count(3) == 1);
+ assert(s.at(3) == 0);
+ assert(globalMemCounter.checkNewCalledEq(2));
+ }
+ assert(globalMemCounter.checkOutstandingNewEq(0));
+ globalMemCounter.reset();
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+ {
+ std::unordered_map<MoveOnly, MoveOnly> s;
+ assert(globalMemCounter.checkNewCalledEq(0));
+
+ for(int i=0; i<100; i++) {
+ s.insert(std::make_pair(MoveOnly(3), MoveOnly(i)));
+ s.insert(s.end(), std::make_pair(MoveOnly(3), MoveOnly(i)));
+ s.emplace(std::make_pair(MoveOnly(3), MoveOnly(i)));
+ s.emplace_hint(s.end(), std::make_pair(MoveOnly(3), MoveOnly(i)));
+ }
+
+ assert(s.size() == 1);
+ assert(s.count(MoveOnly(3)) == 1);
+ assert(s.at(MoveOnly(3)) == 0);
+ assert(globalMemCounter.checkNewCalledEq(2));
+ }
+ assert(globalMemCounter.checkOutstandingNewEq(0));
+ globalMemCounter.reset();
+ {
+ std::unordered_map<int, MoveOnly> s;
+ assert(globalMemCounter.checkNewCalledEq(0));
+
+ for(int i=0; i<100; i++) {
+ s.insert(std::make_pair(3, MoveOnly(i)));
+ s.insert(s.end(), std::make_pair(3, MoveOnly(i)));
+ s.emplace(std::make_pair(3, MoveOnly(i)));
+ s.emplace_hint(s.end(), std::make_pair(3, MoveOnly(i)));
+ }
+
+ assert(s.size() == 1);
+ assert(s.count(3) == 1);
+ assert(s.at(3) == 0);
+ assert(globalMemCounter.checkNewCalledEq(2));
+ }
+ assert(globalMemCounter.checkOutstandingNewEq(0));
+ globalMemCounter.reset();
+#endif
+}
Index: include/unordered_map
===================================================================
--- include/unordered_map
+++ include/unordered_map
@@ -399,6 +399,9 @@
size_t operator()(const _Cp& __x) const
{return static_cast<const _Hash&>(*this)(__x.__cc.first);}
_LIBCPP_INLINE_VISIBILITY
+ size_t operator()(const typename _Cp::value_type& __x) const
+ {return static_cast<const _Hash&>(*this)(__x.first);}
+ _LIBCPP_INLINE_VISIBILITY
size_t operator()(const _Key& __x) const
{return static_cast<const _Hash&>(*this)(__x);}
void swap(__unordered_map_hasher&__y)
@@ -429,6 +432,9 @@
size_t operator()(const _Cp& __x) const
{return __hash_(__x.__cc.first);}
_LIBCPP_INLINE_VISIBILITY
+ size_t operator()(const typename _Cp::value_type& __x) const
+ {return __hash_(__x.first);}
+ _LIBCPP_INLINE_VISIBILITY
size_t operator()(const _Key& __x) const
{return __hash_(__x);}
void swap(__unordered_map_hasher&__y)
@@ -475,6 +481,9 @@
_LIBCPP_INLINE_VISIBILITY
bool operator()(const _Key& __x, const _Cp& __y) const
{return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);}
+ _LIBCPP_INLINE_VISIBILITY
+ bool operator()(const _Cp& __x, const typename _Cp::value_type& __y) const
+ {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.first);}
void swap(__unordered_map_equal&__y)
_NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
{
@@ -508,6 +517,9 @@
_LIBCPP_INLINE_VISIBILITY
bool operator()(const _Key& __x, const _Cp& __y) const
{return __pred_(__x, __y.__cc.first);}
+ _LIBCPP_INLINE_VISIBILITY
+ bool operator()(const _Cp& __x, const typename _Cp::value_type& __y) const
+ {return __pred_(__x.__cc.first, __y.first);}
void swap(__unordered_map_equal&__y)
_NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
{
@@ -755,6 +767,13 @@
template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
};
+template <class _Key, class _Pair, class _RawPair = typename __uncvref<_Pair>::type>
+struct __is_keylike_pair : false_type {};
+
+template <class _Key, class _Pair, class _First, class _Second>
+struct __is_keylike_pair<_Key, _Pair, pair<_First, _Second> >
+ : is_same<typename remove_const<_First>::type, _Key> {};
+
template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
class _Alloc = allocator<pair<const _Key, _Tp> > >
class _LIBCPP_TYPE_VIS_ONLY unordered_map
@@ -923,8 +942,34 @@
template <class... _Args>
pair<iterator, bool> emplace(_Args&&... __args)
- {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
+ {return __emplace_impl(_VSTD::forward<_Args>(__args)...);}
+private:
+ template <class _Pp>
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool> __emplace_impl(_Pp&& __x)
+ {
+ return __emplace_extract_key(_VSTD::forward<_Pp>(__x),
+ __is_keylike_pair<key_type, _Pp>());
+ }
+ template <class _Arg1, class... _Args>
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool> __emplace_impl(_Arg1&& __arg1, _Args&&... __args)
+ {
+ return __table_.__emplace_unique(_VSTD::forward<_Arg1>(__arg1),
+ _VSTD::forward<_Args>(__args)...);
+ }
+
+ template <class _Pp>
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool> __emplace_extract_key(_Pp&& __x, false_type)
+ {return __table_.__emplace_unique(std::forward<_Pp>(__x));}
+ template <class _Pp>
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool> __emplace_extract_key(_Pp&& __x, true_type)
+ {return __table_.__insert_unique_key_value(__x.first, _VSTD::forward<_Pp>(__x));}
+
+public:
template <class... _Args>
_LIBCPP_INLINE_VISIBILITY
#if _LIBCPP_DEBUG_LEVEL >= 2
@@ -943,13 +988,14 @@
#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
_LIBCPP_INLINE_VISIBILITY
pair<iterator, bool> insert(const value_type& __x)
- {return __table_.__insert_unique(__x);}
+ {return __table_.__insert_unique_key_value(__x, __x);}
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
template <class _Pp,
class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
- _LIBCPP_INLINE_VISIBILITY
- pair<iterator, bool> insert(_Pp&& __x)
- {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool> insert(_Pp&& __x)
+ {return __emplace_impl(_VSTD::forward<_Pp>(__x));}
+
#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
_LIBCPP_INLINE_VISIBILITY
#if _LIBCPP_DEBUG_LEVEL >= 2
Index: include/__hash_table
===================================================================
--- include/__hash_table
+++ include/__hash_table
@@ -858,12 +858,13 @@
#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
- template <class _ValueTp>
+ template <class _KeyTp, class _ValueTp>
_LIBCPP_INLINE_VISIBILITY
- pair<iterator, bool> __insert_unique_value(_ValueTp&& __x);
+ pair<iterator, bool> __insert_unique_key_value(const _KeyTp& __key, _ValueTp&& __x);
#else
+ template <class _KeyTp, class _ValueTp>
_LIBCPP_INLINE_VISIBILITY
- pair<iterator, bool> __insert_unique_value(const value_type& __x);
+ pair<iterator, bool> __insert_unique_key_value(const _KeyTp& __key, const _ValueTp& __x);
#endif
pair<iterator, bool> __insert_unique(const value_type& __x);
@@ -1690,27 +1691,28 @@
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);
+ return __insert_unique_key_value(__x, __x);
}
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _ValueTp>
+template <class _KeyTp, 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)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_key_value(const _KeyTp& __key, _ValueTp&& __x)
#else
template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _KeyTp, class _RawValueTp>
_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)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_key_value(const _KeyTp& __key, const _RawValueTp& __x)
#endif
{
#if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
- typedef const value_type& _ValueTp;
+ typedef const _RawValueTp& _ValueTp;
#endif
- size_t __hash = hash_function()(__x);
+ size_t __hash = hash_function()(__key);
size_type __bc = bucket_count();
bool __inserted = false;
__node_pointer __nd;
@@ -1725,7 +1727,7 @@
__constrain_hash(__nd->__hash_, __bc) == __chash;
__nd = __nd->__next_)
{
- if (key_eq()(__nd->__value_, __x))
+ if (key_eq()(__nd->__value_, __key))
goto __done;
}
}
@@ -1818,7 +1820,7 @@
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));
+ return __insert_unique_key_value(__x, _VSTD::move(__x));
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
