===================================================================
@@ -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 \
===================================================================
@@ -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.
===================================================================
@@ -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>
===================================================================
@@ -0,0 +1,262 @@
+// 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);
+
+ void
+ _M_profile_destruct(std::false_type);
+ };
+
+ template<typename _UnorderedCont, bool _Unique_keys>
+ void
+ _Unordered_profile<_UnorderedCont, _Unique_keys>::
+ _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);
+ }
+
+ template<typename _UnorderedCont, bool _Unique_keys>
+ void
+ _Unordered_profile<_UnorderedCont, _Unique_keys>::
+ _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
===================================================================
@@ -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,
===================================================================
@@ -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; }
Attached patch applied. As requested, methods are not inline anymore. 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. François On 05/07/2013 11:30 AM, Paolo Carlini wrote: > Hi, > > On 05/06/2013 10:00 PM, François Dumont wrote: >> 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. > Patch looks great to me. Thanks. Careful, another two or three of > these and you risk being appointed profile-mode maintainer ;) > > While we are at it, the _M_profile_destruct seem very large to be > inline... >> 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 ? > Not to my best knowledge, I would recommend raising the issue on the > isocpp forums or the library evolution reflector. By the way, are you > already subscribed to the reflectors? In case, just send an email to > Andrew Koenig http://www.open-std.org/jtc1/sc22/wg21/docs/contacts > > Thanks, > Paolo. >