This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
unordered profile mode patch
- From: François Dumont <frs dot dumont at gmail dot com>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Mon, 06 May 2013 22:00:25 +0200
- Subject: unordered profile mode patch
Hi
Here is the patch to fix the unordered containers profile mode.
There are a number of enhancements/fixes:
- Use inheritance to play code on instantiation/destruction. This way
some constructors and assignment operators can be defaulted like in the
normal implementation and then be deleted if the normal implementation
has his special function deleted.
- Extend the Inefficient Hash diagnostic to the unordered_multiset and
unordered_multimap. Surprisingly __profcxx_hashtable_destruct2 was
called without __profcxx_hashtable_construct2 so having only the
performance drawback without beneficing from the diagnostic result. I
implemented it by simply ignoring equivalent elements.
- Do not collect data for the Inefficient Hash diagnostic if it is not
On, it is a costly operation.
- Use an implementation detail, the cached hash code, when possible.
This is good for performance and mandatory for robustness because the
hash functor can throw and the code is called from the destructor. Some
tests were failing because of that since I had the
__gnu_cxx::throw_value_* hash functor to conditionally throw.
- Remove useless non-Standard insert(const value_type*, const
value_type*) overloads.
I also add a missing & in the MoveOnly equality functor signature of
55043.cc test file. I don't think it was intentional and it was a
problem for the profile modes that uses it.
Regarding usage of cached hash code I realized that none of the Standard
methods of the unordered containers allowed to benefit from it. There is
no gate between iterator and local_iterator. Has a size_type
bucket(const_iterator) signature been discussed ?
Tested on x86_64 linux profile mode.
2013-05-07 François Dumont <fdumont@gcc.gnu.org>
* include/profile/unordered_base.h: New.
* include/Makefile.am: Add new profile header.
* include/Makefile.in: Regenerate.
* include/profile/impl/profiler.h
(__profcxx_inefficient_hash_is_on): New macro.
* include/profile/unordered_map (std::profile::unordered_map<>):
Use new _Unordered_profile base class. Use default implementations
for special functions.
(std::profile::unordered_multimap<>): Likewise.
* include/profile/unordered_set (std::profile::unordered_set<>):
Likewise.
(std::profile::unordered_multiset<>): Likewise.
* testsuite/23_containers/unordered_multiset/55043.cc: Fix
MoveOnly equality operator signature.
Ok to commit ?
François
Index: include/Makefile.am
===================================================================
--- include/Makefile.am (revision 198608)
+++ include/Makefile.am (working copy)
@@ -788,6 +788,7 @@
profile_headers = \
${profile_srcdir}/array \
${profile_srcdir}/base.h \
+ ${profile_srcdir}/unordered_base.h \
${profile_srcdir}/unordered_map \
${profile_srcdir}/unordered_set \
${profile_srcdir}/vector \
Index: include/profile/impl/profiler.h
===================================================================
--- include/profile/impl/profiler.h (revision 198608)
+++ include/profile/impl/profiler.h (working copy)
@@ -188,7 +188,7 @@
_GLIBCXX_PROFILE_REENTRANCE_GUARD(__gnu_profile::__is_invalid())
#define __profcxx_is_on() \
_GLIBCXX_PROFILE_REENTRANCE_GUARD(__gnu_profile::__is_on())
-#define __profcxx__is_off() \
+#define __profcxx_is_off() \
_GLIBCXX_PROFILE_REENTRANCE_GUARD(__gnu_profile::__is_off())
#else
#define __profcxx_report()
@@ -237,6 +237,8 @@
// Turn on/off instrumentation for INEFFICIENT_HASH.
#if defined(_GLIBCXX_PROFILE_INEFFICIENT_HASH)
+#define __profcxx_inefficient_hash_is_on() \
+ __gnu_profile::__is_on()
#define __profcxx_hashtable_construct2(__x...) \
_GLIBCXX_PROFILE_REENTRANCE_GUARD( \
__gnu_profile::__trace_hash_func_construct(__x))
@@ -244,8 +246,9 @@
_GLIBCXX_PROFILE_REENTRANCE_GUARD( \
__gnu_profile::__trace_hash_func_destruct(__x))
#else
-#define __profcxx_hashtable_destruct2(__x...)
-#define __profcxx_hashtable_construct2(__x...)
+#define __profcxx_inefficient_hash_is_on() false
+#define __profcxx_hashtable_destruct2(__x...)
+#define __profcxx_hashtable_construct2(__x...)
#endif
// Turn on/off instrumentation for VECTOR_TO_LIST.
Index: include/profile/unordered_set
===================================================================
--- include/profile/unordered_set (revision 198608)
+++ include/profile/unordered_set (working copy)
@@ -34,6 +34,7 @@
# include <unordered_set>
#include <profile/base.h>
+#include <profile/unordered_base.h>
#define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc>
#define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
@@ -44,14 +45,22 @@
{
/** @brief Unordered_set wrapper with performance instrumentation. */
template<typename _Key,
- typename _Hash = std::hash<_Key>,
+ typename _Hash = std::hash<_Key>,
typename _Pred = std::equal_to<_Key>,
typename _Alloc = std::allocator<_Key> >
class unordered_set
- : public _GLIBCXX_STD_BASE
+ : public _GLIBCXX_STD_BASE,
+ public _Unordered_profile<unordered_set<_Key, _Hash, _Pred, _Alloc>,
+ true>
{
typedef _GLIBCXX_STD_BASE _Base;
+ _Base&
+ _M_base() noexcept { return *this; }
+
+ const _Base&
+ _M_base() const noexcept { return *this; }
+
public:
typedef typename _Base::size_type size_type;
typedef typename _Base::hasher hasher;
@@ -71,11 +80,8 @@
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
- : _Base(__n, __hf, __eql, __a)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- __profcxx_hashtable_construct2(this);
- }
+ : _Base(__n, __hf, __eql, __a)
+ { }
template<typename _InputIterator>
unordered_set(_InputIterator __f, _InputIterator __l,
@@ -83,84 +89,64 @@
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
- : _Base(__f, __l, __n, __hf, __eql, __a)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- __profcxx_hashtable_construct2(this);
- }
+ : _Base(__f, __l, __n, __hf, __eql, __a)
+ { }
- unordered_set(const unordered_set& __x)
- : _Base(__x)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- __profcxx_hashtable_construct2(this);
- }
+ unordered_set(const unordered_set&) = default;
unordered_set(const _Base& __x)
- : _Base(__x)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- __profcxx_hashtable_construct2(this);
- }
+ : _Base(__x)
+ { }
- unordered_set(unordered_set&& __x)
- : _Base(std::move(__x))
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- __profcxx_hashtable_construct2(this);
- }
+ unordered_set(unordered_set&&) = default;
+ explicit
+ unordered_set(const allocator_type& __a)
+ : _Base(__a)
+ { }
+
+ unordered_set(const unordered_set& __uset,
+ const allocator_type& __a)
+ : _Base(__uset._M_base(), __a)
+ { }
+
+ unordered_set(unordered_set&& __uset,
+ const allocator_type& __a)
+ : _Base(std::move(__uset._M_base()), __a)
+ { }
+
unordered_set(initializer_list<value_type> __l,
size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
- : _Base(__l, __n, __hf, __eql, __a) { }
+ : _Base(__l, __n, __hf, __eql, __a)
+ { }
unordered_set&
- operator=(const unordered_set& __x)
- {
- *static_cast<_Base*>(this) = __x;
- return *this;
- }
+ operator=(const unordered_set&) = default;
unordered_set&
- operator=(unordered_set&& __x)
- {
- // NB: DR 1204.
- // NB: DR 675.
- this->clear();
- this->swap(__x);
- return *this;
- }
+ operator=(unordered_set&&) = default;
unordered_set&
operator=(initializer_list<value_type> __l)
{
- this->clear();
- this->insert(__l);
+ _M_base() = __l;
return *this;
}
- ~unordered_set() noexcept
- {
- __profcxx_hashtable_destruct(this, _Base::bucket_count(),
- _Base::size());
- _M_profile_destruct();
- }
-
void
swap(unordered_set& __x)
- {
- _Base::swap(__x);
- }
+ noexcept( noexcept(__x._M_base().swap(__x)) )
+ { _Base::swap(__x); }
void
clear() noexcept
{
__profcxx_hashtable_destruct(this, _Base::bucket_count(),
_Base::size());
- _M_profile_destruct();
+ this->_M_profile_destruct();
_Base::clear();
}
@@ -240,15 +226,8 @@
}
void
- insert(const value_type* __first, const value_type* __last)
+ rehash(size_type __n)
{
- size_type __old_size = _Base::bucket_count();
- _Base::insert(__first, __last);
- _M_profile_resize(__old_size);
- }
-
- void rehash(size_type __n)
- {
size_type __old_size = _Base::bucket_count();
_Base::rehash(__n);
_M_profile_resize(__old_size);
@@ -262,29 +241,6 @@
if (__old_size != __new_size)
__profcxx_hashtable_resize(this, __old_size, __new_size);
}
-
- void
- _M_profile_destruct()
- {
- size_type __hops = 0, __lc = 0, __chain = 0;
- iterator __it = this->begin();
- while (__it != this->end())
- {
- size_type __bkt = this->bucket(*__it);
- auto __lit = this->begin(__bkt);
- auto __lend = this->end(__bkt);
- for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
- ++__chain;
- if (__chain)
- {
- ++__chain;
- __lc = __lc > __chain ? __lc : __chain;
- __hops += __chain * (__chain - 1) / 2;
- __chain = 0;
- }
- }
- __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
- }
};
template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
@@ -312,14 +268,23 @@
/** @brief Unordered_multiset wrapper with performance instrumentation. */
template<typename _Value,
- typename _Hash = std::hash<_Value>,
- typename _Pred = std::equal_to<_Value>,
- typename _Alloc = std::allocator<_Value> >
+ typename _Hash = std::hash<_Value>,
+ typename _Pred = std::equal_to<_Value>,
+ typename _Alloc = std::allocator<_Value> >
class unordered_multiset
- : public _GLIBCXX_STD_BASE
+ : public _GLIBCXX_STD_BASE,
+ public _Unordered_profile<unordered_multiset<_Value,
+ _Hash, _Pred, _Alloc>,
+ false>
{
typedef _GLIBCXX_STD_BASE _Base;
+ _Base&
+ _M_base() noexcept { return *this; }
+
+ const _Base&
+ _M_base() const noexcept { return *this; }
+
public:
typedef typename _Base::size_type size_type;
typedef typename _Base::hasher hasher;
@@ -339,10 +304,8 @@
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
- : _Base(__n, __hf, __eql, __a)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- }
+ : _Base(__n, __hf, __eql, __a)
+ { }
template<typename _InputIterator>
unordered_multiset(_InputIterator __f, _InputIterator __l,
@@ -350,80 +313,64 @@
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
- : _Base(__f, __l, __n, __hf, __eql, __a)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- }
+ : _Base(__f, __l, __n, __hf, __eql, __a)
+ { }
- unordered_multiset(const unordered_multiset& __x)
- : _Base(__x)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- }
+ unordered_multiset(const unordered_multiset&) = default;
unordered_multiset(const _Base& __x)
- : _Base(__x)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- }
+ : _Base(__x)
+ { }
- unordered_multiset(unordered_multiset&& __x)
- : _Base(std::move(__x))
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- }
+ unordered_multiset(unordered_multiset&&) = default;
+ explicit
+ unordered_multiset(const allocator_type& __a)
+ : _Base(__a)
+ { }
+
+ unordered_multiset(const unordered_multiset& __umset,
+ const allocator_type& __a)
+ : _Base(__umset._M_base(), __a)
+ { }
+
+ unordered_multiset(unordered_multiset&& __umset,
+ const allocator_type& __a)
+ : _Base(std::move(__umset._M_base()), __a)
+ { }
+
unordered_multiset(initializer_list<value_type> __l,
size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
- : _Base(__l, __n, __hf, __eql, __a) { }
+ : _Base(__l, __n, __hf, __eql, __a)
+ { }
unordered_multiset&
- operator=(const unordered_multiset& __x)
- {
- *static_cast<_Base*>(this) = __x;
- return *this;
- }
+ operator=(const unordered_multiset&) = default;
unordered_multiset&
- operator=(unordered_multiset&& __x)
- {
- // NB: DR 1204.
- // NB: DR 675.
- this->clear();
- this->swap(__x);
- return *this;
- }
+ operator=(unordered_multiset&&) = default;
unordered_multiset&
operator=(initializer_list<value_type> __l)
{
- this->clear();
- this->insert(__l);
+ _M_base() = __l;
return *this;
}
- ~unordered_multiset() noexcept
- {
- __profcxx_hashtable_destruct(this, _Base::bucket_count(),
- _Base::size());
- _M_profile_destruct();
- }
-
void
swap(unordered_multiset& __x)
- {
- _Base::swap(__x);
- }
+ noexcept( noexcept(__x._M_base().swap(__x)) )
+ { _Base::swap(__x); }
void
clear() noexcept
{
__profcxx_hashtable_destruct(this, _Base::bucket_count(),
_Base::size());
- _M_profile_destruct();
+ this->_M_profile_destruct();
_Base::clear();
}
@@ -502,15 +449,8 @@
}
void
- insert(const value_type* __first, const value_type* __last)
+ rehash(size_type __n)
{
- size_type __old_size = _Base::bucket_count();
- _Base::insert(__first, __last);
- _M_profile_resize(__old_size);
- }
-
- void rehash(size_type __n)
- {
size_type __old_size = _Base::bucket_count();
_Base::rehash(__n);
_M_profile_resize(__old_size);
@@ -524,29 +464,6 @@
if (__old_size != __new_size)
__profcxx_hashtable_resize(this, __old_size, __new_size);
}
-
- void
- _M_profile_destruct()
- {
- size_type __hops = 0, __lc = 0, __chain = 0;
- iterator __it = this->begin();
- while (__it != this->end())
- {
- size_type __bkt = this->bucket(*__it);
- auto __lit = this->begin(__bkt);
- auto __lend = this->end(__bkt);
- for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
- ++__chain;
- if (__chain)
- {
- ++__chain;
- __lc = __lc > __chain ? __lc : __chain;
- __hops += __chain * (__chain - 1) / 2;
- __chain = 0;
- }
- }
- __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
- }
};
template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
Index: include/profile/unordered_base.h
===================================================================
--- include/profile/unordered_base.h (revision 0)
+++ include/profile/unordered_base.h (revision 0)
@@ -0,0 +1,252 @@
+// Profiling unordered containers implementation details -*- C++ -*-
+
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+/** @file profile/unordered_base.h
+ * This file is a GNU profile extension to the Standard C++ Library.
+ */
+
+#ifndef _GLIBCXX_PROFILE_UNORDERED
+#define _GLIBCXX_PROFILE_UNORDERED 1
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+namespace __profile
+{
+ template<typename _UnorderedCont,
+ typename _Value, bool _Cache_hash_code>
+ struct _Bucket_index_helper;
+
+ template<typename _UnorderedCont, typename _Value>
+ struct _Bucket_index_helper<_UnorderedCont, _Value, true>
+ {
+ static std::size_t
+ bucket(const _UnorderedCont& __uc,
+ const __detail::_Hash_node<_Value, true>* __node)
+ { return __node->_M_hash_code % __uc.bucket_count(); }
+ };
+
+ template<typename _UnorderedCont, typename _Value>
+ struct _Bucket_index_helper<_UnorderedCont, _Value, false>
+ {
+ static std::size_t
+ bucket(const _UnorderedCont& __uc,
+ const __detail::_Hash_node<_Value, false>* __node)
+ { return __uc.bucket(__node->_M_v()); }
+ };
+
+ template<typename _UnorderedCont, typename _Key, typename _Mapped>
+ struct _Bucket_index_helper<_UnorderedCont,
+ std::pair<const _Key, _Mapped>, false>
+ {
+ typedef std::pair<const _Key, _Mapped> _Value;
+
+ static std::size_t
+ bucket(const _UnorderedCont& __uc,
+ const __detail::_Hash_node<_Value, false>* __node)
+ { return __uc.bucket(__node->_M_v().first); }
+ };
+
+ template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code>
+ std::size_t
+ __get_bucket_index(const _UnorderedCont& __uc,
+ const __detail::_Hash_node<_Value, _Cache_hash_code>* __node)
+ {
+ using __bucket_index_helper
+ = _Bucket_index_helper<_UnorderedCont, _Value, _Cache_hash_code>;
+ return __bucket_index_helper::bucket(__uc, __node);
+ }
+
+ template<typename _UnorderedCont,
+ typename _Value, bool _Cache_hash_code>
+ struct _Equal_helper;
+
+ template<typename _UnorderedCont, typename _Value>
+ struct _Equal_helper<_UnorderedCont, _Value, true>
+ {
+ static std::size_t
+ are_equal(const _UnorderedCont& __uc,
+ const __detail::_Hash_node<_Value, true>* __lhs,
+ const __detail::_Hash_node<_Value, true>* __rhs)
+ {
+ return __lhs->_M_hash_code == __rhs->_M_hash_code
+ && __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v());
+ }
+ };
+
+ template<typename _UnorderedCont,
+ typename _Value>
+ struct _Equal_helper<_UnorderedCont, _Value, false>
+ {
+ static std::size_t
+ are_equal(const _UnorderedCont& __uc,
+ const __detail::_Hash_node<_Value, false>* __lhs,
+ const __detail::_Hash_node<_Value, false>* __rhs)
+ { return __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v()); }
+ };
+
+ template<typename _UnorderedCont,
+ typename _Key, typename _Mapped>
+ struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, true>
+ {
+ typedef std::pair<const _Key, _Mapped> _Value;
+
+ static std::size_t
+ are_equal(const _UnorderedCont& __uc,
+ const __detail::_Hash_node<_Value, true>* __lhs,
+ const __detail::_Hash_node<_Value, true>* __rhs)
+ {
+ return __lhs->_M_hash_code == __rhs->_M_hash_code
+ && __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first);
+ }
+ };
+
+ template<typename _UnorderedCont,
+ typename _Key, typename _Mapped>
+ struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, false>
+ {
+ typedef std::pair<const _Key, _Mapped> _Value;
+
+ static std::size_t
+ are_equal(const _UnorderedCont& __uc,
+ const __detail::_Hash_node<_Value, false>* __lhs,
+ const __detail::_Hash_node<_Value, false>* __rhs)
+ { return __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first); }
+ };
+
+ template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code>
+ bool
+ __are_equal(const _UnorderedCont& __uc,
+ const __detail::_Hash_node<_Value, _Cache_hash_code>* __lhs,
+ const __detail::_Hash_node<_Value, _Cache_hash_code>* __rhs)
+ {
+ using __equal_helper
+ = _Equal_helper<_UnorderedCont, _Value, _Cache_hash_code>;
+ return __equal_helper::are_equal(__uc, __lhs, __rhs);
+ }
+
+ template<typename _UnorderedCont, bool _Unique_keys>
+ class _Unordered_profile
+ {
+ _UnorderedCont&
+ _M_conjure()
+ { return *(static_cast<_UnorderedCont*>(this)); }
+
+ using __unique_keys = std::integral_constant<bool, _Unique_keys>;
+
+ protected:
+ _Unordered_profile()
+ {
+ auto& __uc = _M_conjure();
+ __profcxx_hashtable_construct(&__uc, __uc.bucket_count());
+ __profcxx_hashtable_construct2(&__uc);
+ }
+ _Unordered_profile(const _Unordered_profile&)
+ : _Unordered_profile() { }
+ _Unordered_profile(_Unordered_profile&&)
+ : _Unordered_profile() { }
+
+ ~_Unordered_profile() noexcept
+ {
+ auto& __uc = _M_conjure();
+ __profcxx_hashtable_destruct(&__uc, __uc.bucket_count(), __uc.size());
+ _M_profile_destruct();
+ }
+
+ _Unordered_profile&
+ operator=(const _Unordered_profile&) = default;
+
+ _Unordered_profile&
+ operator=(_Unordered_profile&&) = default;
+
+ void
+ _M_profile_destruct()
+ {
+ if (!__profcxx_inefficient_hash_is_on())
+ return;
+
+ _M_profile_destruct(__unique_keys());
+ }
+
+ private:
+ void
+ _M_profile_destruct(std::true_type)
+ {
+ auto& __uc = _M_conjure();
+ std::size_t __hops = 0, __lc = 0, __chain = 0;
+ auto __it = __uc.begin();
+ while (__it != __uc.end())
+ {
+ auto __bkt = __get_bucket_index(__uc, __it._M_cur);
+ auto __lit = __uc.begin(__bkt);
+ auto __lend = __uc.end(__bkt);
+ for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
+ ++__chain;
+ if (__chain)
+ {
+ ++__chain;
+ __lc = __lc > __chain ? __lc : __chain;
+ __hops += __chain * (__chain - 1) / 2;
+ __chain = 0;
+ }
+ }
+ __profcxx_hashtable_destruct2(&__uc, __lc, __uc.size(), __hops);
+ }
+
+ void
+ _M_profile_destruct(std::false_type)
+ {
+ auto& __uc = _M_conjure();
+ std::size_t __hops = 0, __lc = 0, __chain = 0, __unique_size = 0;;
+ auto __it = __uc.begin();
+ while (__it != __uc.end())
+ {
+ auto __bkt = __get_bucket_index(__uc, __it._M_cur);
+ auto __lit = __uc.begin(__bkt);
+ auto __lend = __uc.end(__bkt);
+ auto __pit = __it;
+ ++__unique_size;
+ for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
+ {
+ if (!__are_equal(__uc, __pit._M_cur, __it._M_cur))
+ {
+ ++__chain;
+ ++__unique_size;
+ __pit = __it;
+ }
+ }
+ if (__chain)
+ {
+ ++__chain;
+ __lc = __lc > __chain ? __lc : __chain;
+ __hops += __chain * (__chain - 1) / 2;
+ __chain = 0;
+ }
+ }
+ __profcxx_hashtable_destruct2(&__uc, __lc, __unique_size, __hops);
+ }
+ };
+
+} // namespace __profile
+} // namespace std
+
+#endif
Property changes on: include/profile/unordered_base.h
___________________________________________________________________
Added: svn:eol-style
+ native
Index: include/profile/unordered_map
===================================================================
--- include/profile/unordered_map (revision 198608)
+++ include/profile/unordered_map (working copy)
@@ -34,6 +34,7 @@
# include <unordered_map>
#include <profile/base.h>
+#include <profile/unordered_base.h>
#define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
#define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
@@ -48,10 +49,18 @@
typename _Pred = std::equal_to<_Key>,
typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class unordered_map
- : public _GLIBCXX_STD_BASE
+ : public _GLIBCXX_STD_BASE,
+ public _Unordered_profile<unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
+ true>
{
typedef typename _GLIBCXX_STD_BASE _Base;
+ _Base&
+ _M_base() noexcept { return *this; }
+
+ const _Base&
+ _M_base() const noexcept { return *this; }
+
public:
typedef typename _Base::size_type size_type;
typedef typename _Base::hasher hasher;
@@ -72,11 +81,8 @@
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
- : _Base(__n, __hf, __eql, __a)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- __profcxx_hashtable_construct2(this);
- }
+ : _Base(__n, __hf, __eql, __a)
+ { }
template<typename _InputIterator>
unordered_map(_InputIterator __f, _InputIterator __l,
@@ -84,85 +90,60 @@
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
- : _Base(__f, __l, __n, __hf, __eql, __a)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- __profcxx_hashtable_construct2(this);
- }
+ : _Base(__f, __l, __n, __hf, __eql, __a)
+ { }
- unordered_map(const unordered_map& __x)
- : _Base(__x)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- __profcxx_hashtable_construct2(this);
- }
+ unordered_map(const unordered_map&) = default;
unordered_map(const _Base& __x)
- : _Base(__x)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- __profcxx_hashtable_construct2(this);
- }
+ : _Base(__x)
+ { }
- unordered_map(unordered_map&& __x)
- : _Base(std::move(__x))
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- __profcxx_hashtable_construct2(this);
- }
+ unordered_map(unordered_map&&) = default;
+ explicit
+ unordered_map(const allocator_type& __a)
+ : _Base(__a)
+ { }
+
+ unordered_map(const unordered_map& __umap,
+ const allocator_type& __a)
+ : _Base(__umap, __a)
+ { }
+
+ unordered_map(unordered_map&& __umap,
+ const allocator_type& __a)
+ : _Base(std::move(__umap._M_base()), __a)
+ { }
+
unordered_map(initializer_list<value_type> __l,
size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
- : _Base(__l, __n, __hf, __eql, __a) { }
+ : _Base(__l, __n, __hf, __eql, __a)
+ { }
unordered_map&
- operator=(const unordered_map& __x)
- {
- *static_cast<_Base*>(this) = __x;
- return *this;
- }
+ operator=(const unordered_map&) = default;
unordered_map&
- operator=(unordered_map&& __x)
- {
- // NB: DR 1204.
- // NB: DR 675.
- this->clear();
- this->swap(__x);
- return *this;
- }
+ operator=(unordered_map&&) = default;
unordered_map&
operator=(initializer_list<value_type> __l)
{
- this->clear();
- this->insert(__l);
+ _M_base() = __l;
return *this;
}
- ~unordered_map() noexcept
- {
- __profcxx_hashtable_destruct(this, _Base::bucket_count(),
- _Base::size());
- _M_profile_destruct();
- }
-
- _Base&
- _M_base() noexcept { return *this; }
-
- const _Base&
- _M_base() const noexcept { return *this; }
-
void
clear() noexcept
{
__profcxx_hashtable_destruct(this, _Base::bucket_count(),
_Base::size());
- _M_profile_destruct();
- _Base::clear();
+ this->_M_profile_destruct();
+ _Base::clear();
}
template<typename... _Args>
@@ -247,14 +228,6 @@
_M_profile_resize(__old_size);
}
- void
- insert(const value_type* __first, const value_type* __last)
- {
- size_type __old_size = _Base::bucket_count();
- _Base::insert(__first, __last);
- _M_profile_resize(__old_size);
- }
-
// operator[]
mapped_type&
operator[](const _Key& __k)
@@ -276,7 +249,8 @@
void
swap(unordered_map& __x)
- { _Base::swap(__x); }
+ noexcept( noexcept(__x._M_base().swap(__x)) )
+ { _Base::swap(__x._M_base()); }
void rehash(size_type __n)
{
@@ -293,29 +267,6 @@
if (__old_size != __new_size)
__profcxx_hashtable_resize(this, __old_size, __new_size);
}
-
- void
- _M_profile_destruct()
- {
- size_type __hops = 0, __lc = 0, __chain = 0;
- iterator __it = this->begin();
- while (__it != this->end())
- {
- size_type __bkt = this->bucket(__it->first);
- auto __lit = this->begin(__bkt);
- auto __lend = this->end(__bkt);
- for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
- ++__chain;
- if (__chain)
- {
- ++__chain;
- __lc = __lc > __chain ? __lc : __chain;
- __hops += __chain * (__chain - 1) / 2;
- __chain = 0;
- }
- }
- __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
- }
};
template<typename _Key, typename _Tp, typename _Hash,
@@ -350,10 +301,19 @@
typename _Pred = std::equal_to<_Key>,
typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class unordered_multimap
- : public _GLIBCXX_STD_BASE
+ : public _GLIBCXX_STD_BASE,
+ public _Unordered_profile<unordered_multimap<_Key, _Tp,
+ _Hash, _Pred, _Alloc>,
+ false>
{
typedef typename _GLIBCXX_STD_BASE _Base;
+ _Base&
+ _M_base() noexcept { return *this; }
+
+ const _Base&
+ _M_base() const noexcept { return *this; }
+
public:
typedef typename _Base::size_type size_type;
typedef typename _Base::hasher hasher;
@@ -373,85 +333,69 @@
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
- : _Base(__n, __hf, __eql, __a)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- }
+ : _Base(__n, __hf, __eql, __a)
+ { }
+
template<typename _InputIterator>
unordered_multimap(_InputIterator __f, _InputIterator __l,
size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
- : _Base(__f, __l, __n, __hf, __eql, __a)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- }
+ : _Base(__f, __l, __n, __hf, __eql, __a)
+ { }
- unordered_multimap(const unordered_multimap& __x)
- : _Base(__x)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- }
+ unordered_multimap(const unordered_multimap&) = default;
unordered_multimap(const _Base& __x)
- : _Base(__x)
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- }
+ : _Base(__x)
+ { }
- unordered_multimap(unordered_multimap&& __x)
- : _Base(std::move(__x))
- {
- __profcxx_hashtable_construct(this, _Base::bucket_count());
- }
+ unordered_multimap(unordered_multimap&&) = default;
+ explicit
+ unordered_multimap(const allocator_type& __a)
+ : _Base(__a)
+ { }
+
+ unordered_multimap(const unordered_multimap& __ummap,
+ const allocator_type& __a)
+ : _Base(__ummap._M_base(), __a)
+ { }
+
+ unordered_multimap(unordered_multimap&& __ummap,
+ const allocator_type& __a)
+ : _Base(std::move(__ummap._M_base()), __a)
+ { }
+
unordered_multimap(initializer_list<value_type> __l,
size_type __n = 0,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
- : _Base(__l, __n, __hf, __eql, __a) { }
+ : _Base(__l, __n, __hf, __eql, __a)
+ { }
unordered_multimap&
- operator=(const unordered_multimap& __x)
- {
- *static_cast<_Base*>(this) = __x;
- return *this;
- }
+ operator=(const unordered_multimap&) = default;
unordered_multimap&
- operator=(unordered_multimap&& __x)
- {
- // NB: DR 1204.
- // NB: DR 675.
- this->clear();
- this->swap(__x);
- return *this;
- }
+ operator=(unordered_multimap&&) = default;
unordered_multimap&
operator=(initializer_list<value_type> __l)
{
- this->clear();
- this->insert(__l);
+ _M_base() = __l;
return *this;
}
- ~unordered_multimap() noexcept
- {
- __profcxx_hashtable_destruct(this, _Base::bucket_count(),
- _Base::size());
- _M_profile_destruct();
- }
-
void
clear() noexcept
{
- __profcxx_hashtable_destruct(this, _Base::bucket_count(),
+ __profcxx_hashtable_destruct(this, _Base::bucket_count(),
_Base::size());
- _M_profile_destruct();
- _Base::clear();
+ this->_M_profile_destruct();
+ _Base::clear();
}
template<typename... _Args>
@@ -536,18 +480,12 @@
}
void
- insert(const value_type* __first, const value_type* __last)
- {
- size_type __old_size = _Base::bucket_count();
- _Base::insert(__first, __last);
- _M_profile_resize(__old_size);
- }
-
- void
swap(unordered_multimap& __x)
- { _Base::swap(__x); }
+ noexcept( noexcept(__x._M_base().swap(__x)) )
+ { _Base::swap(__x._M_base()); }
- void rehash(size_type __n)
+ void
+ rehash(size_type __n)
{
size_type __old_size = _Base::bucket_count();
_Base::rehash(__n);
@@ -562,29 +500,6 @@
if (__old_size != __new_size)
__profcxx_hashtable_resize(this, __old_size, __new_size);
}
-
- void
- _M_profile_destruct()
- {
- size_type __hops = 0, __lc = 0, __chain = 0;
- iterator __it = this->begin();
- while (__it != this->end())
- {
- size_type __bkt = this->bucket(__it->first);
- auto __lit = this->begin(__bkt);
- auto __lend = this->end(__bkt);
- for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
- ++__chain;
- if (__chain)
- {
- ++__chain;
- __lc = __lc > __chain ? __lc : __chain;
- __hops += __chain * (__chain - 1) / 2;
- __chain = 0;
- }
- }
- __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
- }
};
template<typename _Key, typename _Tp, typename _Hash,
Index: testsuite/23_containers/unordered_multiset/55043.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/55043.cc (revision 198608)
+++ testsuite/23_containers/unordered_multiset/55043.cc (working copy)
@@ -30,7 +30,7 @@
};
struct equal {
- bool operator()(const MoveOnly&, const MoveOnly) const { return true; }
+ bool operator()(const MoveOnly&, const MoveOnly&) const { return true; }
};
struct hash {
std::size_t operator()(const MoveOnly&) const { return 0; }