The issue in PR 56267 is that unordered_xxx::local_iterator sometimes
inherits from the user-defined hash function (via _Hash_code_base,
which inherits from the hash function to use the EBO), and
local_iterator must be DefaultConstructible and Assignable, even when
the hash function isn't.
My solution is to remove the inheritance from _Hash_code_base, and
instead construct/destroy the _Hash_code_base in a block of
uninitialized memory (via __gnu_cxx::__aligned_buffer). This would
mean we can't use the EBO and increase the size of local_iterator, and
past measurements have shown that the unordered containers'
performance is sensitive to such changes, so there's a partial
specialization that doesn't have the __aligned_buffer member for the
case where the _Hash_code_base is empty and needs no storage.
François, do you have any comments on this? Can you see a better solution?
While working on this I decided I didn't like everything in
_Local_iterator_base being public, so I added some accessors to the
only members that are needed by unrelated types.
2014-01-17 Jonathan Wakely <jwak...@redhat.com>
PR libstdc++/56267
* include/bits/hashtable_policy.h (_Local_iterator_base): Give
protected access to all existing members.
(_Local_iterator_base::_M_curr()): New public accessor.
(_Local_iterator_base::_M_get_bucket()): New public accessor.
(_Local_iterator_base<..., false>::_M_init()): New function to manage
the lifetime of the _Hash_code_base explicitly.
(_Local_iterator_base<..., false>::_M_destroy()): Likewise.
(_Local_iterator_base<..., false>): Define copy constructor and copy
assignment operator that use new functions to manage _Hash_code_base.
(operator==(const _Local_iterator_base&, const _Local_iterator_base&),
operator==(const _Local_iterator_base&, const _Local_iterator_base&)):
Use public API for _Local_iterator_base.
* include/debug/safe_local_iterator.h (_Safe_local_iterator): Likewise.
* include/debug/unordered_map (__debug::unordered_map::erase(),
__debug::unordered_multimap::erase()): Likewise.
* include/debug/unordered_set (__debug::unordered_set::erase(),
__debug::unordered_multiset::erase()): Likewise.
* testsuite/23_containers/unordered_set/56267-2.cc: New test.
commit f9c852223230da4e4fc761f72905c7acacfa4399
Author: Jonathan Wakely <jwak...@redhat.com>
Date: Fri Jan 17 15:10:48 2014 +0000
PR libstdc++/56267
* include/bits/hashtable_policy.h (_Local_iterator_base): Give
protected access to all existing members.
(_Local_iterator_base::_M_curr()): New public accessor.
(_Local_iterator_base::_M_get_bucket()): New public accessor.
(operator==(const _Local_iterator_base&, const _Local_iterator_base&),
operator==(const _Local_iterator_base&, const _Local_iterator_base&)):
Use public API for _Local_iterator_base.
* include/debug/safe_local_iterator.h (_Safe_local_iterator): Likewise.
* include/debug/unordered_map (__debug::unordered_map::erase(),
__debug::unordered_multimap::erase()): Likewise.
* include/debug/unordered_set (__debug::unordered_set::erase(),
__debug::unordered_multiset::erase()): Likewise.
* testsuite/23_containers/unordered_set/56267-2.cc: New test.
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h
b/libstdc++-v3/include/bits/hashtable_policy.h
index f64d2d3..817b190 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -1145,6 +1145,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
+ // Gives the local iterator implementation access to _M_bucket_index().
+ friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
+ _Default_ranged_hash, false>;
+
public:
typedef _H1 hasher;
@@ -1225,7 +1229,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
private _Hashtable_ebo_helper<2, _H2>
{
private:
- // Gives access to _M_h2() to the local iterator implementation.
+ // Gives the local iterator implementation access to _M_h2().
friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
_Default_ranged_hash, true>;
@@ -1331,7 +1335,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
};
- /// Specialization.
+ /// Partial specialization used when nodes contain a cached hash code.
template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash>
struct _Local_iterator_base<_Key, _Value, _ExtractKey,
@@ -1343,7 +1347,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, true>;
- public:
_Local_iterator_base() = default;
_Local_iterator_base(const __hash_code_base& __base,
_Hash_node<_Value, true>* __p,
@@ -1368,27 +1371,97 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hash_node<_Value, true>* _M_cur;
std::size_t _M_bucket;
std::size_t _M_bucket_count;
+
+ public:
+ const void*
+ _M_curr() const { return _M_cur; } // for equality ops
+
+ std::size_t
+ _M_get_bucket() const { return _M_bucket; } // for debug mode
+ };
+
+ // Uninitialized storage for a _Hash_code_base.
+ // This type is DefaultConstructible and Assignable even if the
+ // _Hash_code_base type isn't, // so that _Local_iterator_base<..., false>
+ // can be DefaultConstructible and Assignable.
+ template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
+ struct _Hash_code_storage
+ {
+ __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
+
+ _Tp*
+ _M_h() { return _M_storage._M_ptr(); }
+
+ const _Tp*
+ _M_h() const { return _M_storage._M_ptr(); }
+ };
+
+ // Empty partial specialization for empty _Hash_code_base types.
+ template<typename _Tp>
+ struct _Hash_code_storage<_Tp, true>
+ {
+ static_assert( std::is_empty<_Tp>::value, "Type must be empty" );
+
+ // As _Tp is an empty type there will be no bytes written/read through
+ // the cast pointer, so no strict-aliasing violation.
+ _Tp*
+ _M_h() { return reinterpret_cast<_Tp*>(this); }
+
+ const _Tp*
+ _M_h() const { return reinterpret_cast<const _Tp*>(this); }
};
- /// Specialization.
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash>
+ using __hash_code_for_local_iter
+ = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, false>>;
+
+ // Partial specialization used when hash codes are not cached
template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash>
struct _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, false>
- : private _Hash_code_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, false>
+ : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
{
protected:
using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, false>;
- public:
- _Local_iterator_base() = default;
+ _Local_iterator_base() : _M_bucket_count(-1) { }
+
_Local_iterator_base(const __hash_code_base& __base,
_Hash_node<_Value, false>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : __hash_code_base(__base),
- _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+ : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
+ { _M_init(__base); }
+
+ ~_Local_iterator_base()
+ {
+ if (_M_bucket_count != -1)
+ _M_destroy();
+ }
+
+ _Local_iterator_base(const _Local_iterator_base& __iter)
+ : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
+ _M_bucket_count(__iter._M_bucket_count)
+ {
+ if (_M_bucket_count != -1)
+ _M_init(*__iter._M_h());
+ }
+
+ _Local_iterator_base&
+ operator=(const _Local_iterator_base& __iter)
+ {
+ if (_M_bucket_count != -1)
+ _M_destroy();
+ _M_cur = __iter._M_cur;
+ _M_bucket = __iter._M_bucket;
+ _M_bucket_count = __iter._M_bucket_count;
+ if (_M_bucket_count != -1)
+ _M_init(*__iter._M_h());
+ return *this;
+ }
void
_M_incr()
@@ -1396,7 +1469,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_cur = _M_cur->_M_next();
if (_M_cur)
{
- std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
+ std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
+ _M_bucket_count);
if (__bkt != _M_bucket)
_M_cur = nullptr;
}
@@ -1405,6 +1479,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hash_node<_Value, false>* _M_cur;
std::size_t _M_bucket;
std::size_t _M_bucket_count;
+
+ void
+ _M_init(const __hash_code_base& __base)
+ { ::new(this->_M_h()) __hash_code_base(__base); }
+
+ void
+ _M_destroy() { this->_M_h()->~__hash_code_base(); }
+
+ public:
+ const void*
+ _M_curr() const { return _M_cur; } // for equality ops and debug mode
+
+ std::size_t
+ _M_get_bucket() const { return _M_bucket; } // for debug mode
};
template<typename _Key, typename _Value, typename _ExtractKey,
@@ -1414,7 +1502,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_H1, _H2, _Hash, __cache>& __x,
const _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, __cache>& __y)
- { return __x._M_cur == __y._M_cur; }
+ { return __x._M_curr() == __y._M_curr(); }
template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash, bool __cache>
@@ -1423,7 +1511,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_H1, _H2, _Hash, __cache>& __x,
const _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, __cache>& __y)
- { return __x._M_cur != __y._M_cur; }
+ { return __x._M_curr() != __y._M_curr(); }
/// local iterators
template<typename _Key, typename _Value, typename _ExtractKey,
diff --git a/libstdc++-v3/include/debug/safe_local_iterator.h
b/libstdc++-v3/include/debug/safe_local_iterator.h
index f5e9893..77552ce 100644
--- a/libstdc++-v3/include/debug/safe_local_iterator.h
+++ b/libstdc++-v3/include/debug/safe_local_iterator.h
@@ -219,7 +219,7 @@ namespace __gnu_debug
* @brief Return the bucket
*/
size_type
- bucket() const { return _M_current._M_bucket; }
+ bucket() const { return _M_current._M_get_bucket(); }
/**
* @brief Conversion to underlying non-debug iterator to allow
diff --git a/libstdc++-v3/include/debug/unordered_map
b/libstdc++-v3/include/debug/unordered_map
index a1eccde..821bf0b 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -389,7 +389,7 @@ namespace __debug
{ return __it == __victim; });
this->_M_invalidate_local_if(
[__victim](_Base_const_local_iterator __it)
- { return __it._M_cur == __victim._M_cur; });
+ { return __it._M_curr() == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base::erase(__victim);
_M_check_rehashed(__bucket_count);
@@ -407,7 +407,7 @@ namespace __debug
{ return __it == __victim; });
this->_M_invalidate_local_if(
[__victim](_Base_const_local_iterator __it)
- { return __it._M_cur == __victim._M_cur; });
+ { return __it._M_curr() == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__it.base());
_M_check_rehashed(__bucket_count);
@@ -433,7 +433,7 @@ namespace __debug
{ return __it == __tmp; });
this->_M_invalidate_local_if(
[__tmp](_Base_const_local_iterator __it)
- { return __it._M_cur == __tmp._M_cur; });
+ { return __it._M_curr() == __tmp._M_cur; });
}
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__first.base(), __last.base());
@@ -842,7 +842,7 @@ namespace __debug
{ return __it == __victim; });
this->_M_invalidate_local_if(
[__victim](_Base_const_local_iterator __it)
- { return __it._M_cur == __victim._M_cur; });
+ { return __it._M_curr() == __victim._M_cur; });
_Base::erase(__victim++);
++__ret;
}
@@ -859,7 +859,7 @@ namespace __debug
{ return __it == __victim; });
this->_M_invalidate_local_if(
[__victim](_Base_const_local_iterator __it)
- { return __it._M_cur == __victim._M_cur; });
+ { return __it._M_curr() == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__it.base());
_M_check_rehashed(__bucket_count);
@@ -885,7 +885,7 @@ namespace __debug
{ return __it == __tmp; });
this->_M_invalidate_local_if(
[__tmp](_Base_const_local_iterator __it)
- { return __it._M_cur == __tmp._M_cur; });
+ { return __it._M_curr() == __tmp._M_cur; });
}
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__first.base(), __last.base());
diff --git a/libstdc++-v3/include/debug/unordered_set
b/libstdc++-v3/include/debug/unordered_set
index 8246141..3bc3fab 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -383,7 +383,7 @@ namespace __debug
{ return __it == __victim; });
this->_M_invalidate_local_if(
[__victim](_Base_const_local_iterator __it)
- { return __it._M_cur == __victim._M_cur; });
+ { return __it._M_curr() == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base::erase(__victim);
_M_check_rehashed(__bucket_count);
@@ -402,7 +402,7 @@ namespace __debug
{ return __it == __victim; });
this->_M_invalidate_local_if(
[__victim](_Base_const_local_iterator __it)
- { return __it._M_cur == __victim._M_cur; });
+ { return __it._M_curr() == __victim._M_cur; });
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__it.base());
_M_check_rehashed(__bucket_count);
@@ -429,7 +429,7 @@ namespace __debug
{ return __it == __tmp; });
this->_M_invalidate_local_if(
[__tmp](_Base_const_local_iterator __it)
- { return __it._M_cur == __tmp._M_cur; });
+ { return __it._M_curr() == __tmp._M_cur; });
}
size_type __bucket_count = this->bucket_count();
_Base_iterator __next = _Base::erase(__first.base(),
@@ -832,7 +832,7 @@ namespace __debug
{ return __it == __victim; });
this->_M_invalidate_local_if(
[__victim](_Base_const_local_iterator __it)
- { return __it._M_cur == __victim._M_cur; });
+ { return __it._M_curr() == __victim._M_cur; });
_Base::erase(__victim++);
++__ret;
}
@@ -848,7 +848,7 @@ namespace __debug
{ return __it == __victim; });
this->_M_invalidate_local_if(
[__victim](_Base_const_local_iterator __it)
- { return __it._M_cur == __victim._M_cur; });
+ { return __it._M_curr() == __victim._M_cur; });
return iterator(_Base::erase(__it.base()), this);
}
@@ -871,7 +871,7 @@ namespace __debug
{ return __it == __tmp; });
this->_M_invalidate_local_if(
[__tmp](_Base_const_local_iterator __it)
- { return __it._M_cur == __tmp._M_cur; });
+ { return __it._M_curr() == __tmp._M_cur; });
}
return iterator(_Base::erase(__first.base(),
__last.base()), this);
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/56267-2.cc
b/libstdc++-v3/testsuite/23_containers/unordered_set/56267-2.cc
new file mode 100644
index 0000000..cae451a
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/56267-2.cc
@@ -0,0 +1,43 @@
+// Copyright (C) 2014 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.
+
+// 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/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <unordered_set>
+
+struct audrey2hash : std::hash<int>
+{
+ audrey2hash() { throw "Seed me, Seymour"; } // must not use default ctor
+
+ audrey2hash(int) { }
+
+ audrey2hash&
+ operator=(const audrey2hash&) { throw "Don't assign the plants"; }
+};
+
+void test01()
+{
+ typedef std::unordered_set<int, audrey2hash> test_type;
+ test_type::local_iterator it __attribute__((unused));
+ test_type c{ {1, 2, 3}, 3u, audrey2hash{1} };
+ it = c.begin(0);
+}
+
+int main()
+{
+ test01();
+}
