OSDN Git Service

2011-12-29 Fran├žois Dumont <fdumont@gcc.gnu.org>
authorfdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4>
Thu, 29 Dec 2011 17:58:51 +0000 (17:58 +0000)
committerfdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4>
Thu, 29 Dec 2011 17:58:51 +0000 (17:58 +0000)
PR libstdc++/51608
* include/bits/hashtable_policy.h (_Equal_helper<>): New, change the
way the _Equal functor is used depending on whether hash code is
cached or not.
(_Ebo_helper<>): New helper type to introduce EBO when possible.
(_Hash_code_base): Use _Ebo_helper to limit memory footprint. Move
_Equal functor management...
(_Hashtable_base): ...here, new, use _Equal_helper.
(_Local_iterator_base<>, _Locale_iterator<>, _Locale_const_iterator<>):
New, use _Hash_code_base, implementation of...
* include/bits/hashtable.h (_Hashtable<>::local_iterator,
_Hashtable<>::const_local_iterator): ...those. Add static assertions
checking that some functors are empty depending on whether hash code
is cache or not.
(_Hashtable<>::_M_bucket_index): New overloads using current bucket
count, use through out the _Hastable<> implementation.
* include/bits/unordered_set.h (__unordered_set<>,
__unordered_multiset<>): Cache hash code iff hash functor is not
empty and not final.
* include/bits/unordered_map.h (__unordered_map<>,
__unordered_multimap<>): Likewise.
* include/debug/unordered_map
(unordered_map<>::_S_to_local, unordered_multimap<>::_S_to_local):
Adapt to match new local iterator implementation.
* include/debug/unordered_set (unordered_set<>::_S_to_local,
unordered_multiset<>::_S_to_local): Likewise.
* include/profile/unordered_map (unordered_map<>::_M_profile_destruct,
unordered_multimap<>::_M_profile_destruct): Enhance thanks to usage of
local iterators.
* include/profile/unordered_set (unordered_set<>::_M_profile_destruct,
unordered_multiset<>::_M_profile_destruct): Likewise.
* testsuite_files/23_containers/unordered_set/instantiation_neg.cc:
Fix error line.
* testsuite_files/23_containers/unordered_set/final_hash.cc: New.
* testsuite_files/23_containers/unordered_multiset/final_hash.cc: New.
* testsuite_files/23_containers/unordered_map/final_hash.cc: New.
* testsuite_files/23_containers/unordered_multimap/final_hash.cc: New.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@182727 138bc75d-0d04-0410-961f-82ee72b054a4

14 files changed:
libstdc++-v3/ChangeLog
libstdc++-v3/include/bits/hashtable.h
libstdc++-v3/include/bits/hashtable_policy.h
libstdc++-v3/include/bits/unordered_map.h
libstdc++-v3/include/bits/unordered_set.h
libstdc++-v3/include/debug/unordered_map
libstdc++-v3/include/debug/unordered_set
libstdc++-v3/include/profile/unordered_map
libstdc++-v3/include/profile/unordered_set
libstdc++-v3/testsuite/23_containers/unordered_map/final_hash.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/unordered_multimap/final_hash.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/unordered_multiset/final_hash.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/unordered_set/final_hash.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc

index 6b0220c..e697e4b 100644 (file)
@@ -1,3 +1,43 @@
+2011-12-29  Fran├žois Dumont <fdumont@gcc.gnu.org>
+
+       PR libstdc++/51608
+       * include/bits/hashtable_policy.h (_Equal_helper<>): New, change the
+       way the _Equal functor is used depending on whether hash code is
+       cached or not.
+       (_Ebo_helper<>): New helper type to introduce EBO when possible.
+       (_Hash_code_base): Use _Ebo_helper to limit memory footprint. Move
+       _Equal functor management...
+       (_Hashtable_base): ...here, new, use _Equal_helper.
+       (_Local_iterator_base<>, _Locale_iterator<>, _Locale_const_iterator<>):
+       New, use _Hash_code_base, implementation of...
+       * include/bits/hashtable.h (_Hashtable<>::local_iterator,
+       _Hashtable<>::const_local_iterator): ...those. Add static assertions
+       checking that some functors are empty depending on whether hash code
+       is cache or not.
+       (_Hashtable<>::_M_bucket_index): New overloads using current bucket
+       count, use through out the _Hastable<> implementation.
+       * include/bits/unordered_set.h (__unordered_set<>,
+       __unordered_multiset<>): Cache hash code iff hash functor is not
+       empty and not final.
+       * include/bits/unordered_map.h (__unordered_map<>,
+       __unordered_multimap<>): Likewise.
+       * include/debug/unordered_map
+       (unordered_map<>::_S_to_local, unordered_multimap<>::_S_to_local):
+       Adapt to match new local iterator implementation.
+       * include/debug/unordered_set (unordered_set<>::_S_to_local,
+       unordered_multiset<>::_S_to_local): Likewise.
+       * include/profile/unordered_map (unordered_map<>::_M_profile_destruct,
+       unordered_multimap<>::_M_profile_destruct): Enhance thanks to usage of
+       local iterators.
+       * include/profile/unordered_set (unordered_set<>::_M_profile_destruct,
+       unordered_multiset<>::_M_profile_destruct): Likewise.
+       * testsuite_files/23_containers/unordered_set/instantiation_neg.cc:
+       Fix error line.
+       * testsuite_files/23_containers/unordered_set/final_hash.cc: New.
+       * testsuite_files/23_containers/unordered_multiset/final_hash.cc: New.
+       * testsuite_files/23_containers/unordered_map/final_hash.cc: New.
+       * testsuite_files/23_containers/unordered_multimap/final_hash.cc: New.
+
 2011-12-29  Jonathan Wakely  <jwakely.gcc@gmail.com>
 
        PR libstdc++/51701
index 3874cbc..aeb330c 100644 (file)
@@ -155,7 +155,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
                                               __cache_hash_code,
                                               __constant_iterators,
                                               __unique_keys> >,
-      public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
+      public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
                                       _H1, _H2, _Hash, __cache_hash_code>,
       public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
                                 _Hashtable<_Key, _Value, _Allocator,
@@ -174,9 +174,37 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
                                                 __constant_iterators,
                                                 __unique_keys> >
     {
-      static_assert(__or_<integral_constant<bool, __cache_hash_code>,
-                         __detail::__is_noexcept_hash<_Key, _H1>>::value,
+      template<typename _Cond>
+       using __if_hash_code_cached
+         = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>;
+
+      template<typename _Cond>
+       using __if_hash_code_not_cached
+         = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
+
+      static_assert(__if_hash_code_not_cached<__detail::__is_noexcept_hash<_Key,
+                                                               _H1>>::value,
            "Cache the hash code or qualify your hash functor with noexcept");
+
+      // Following two static assertions are necessary to guarantee that
+      // swapping two hashtable instances won't invalidate associated local
+      // iterators.
+
+      // When hash codes are cached local iterator only uses H2 which must then
+      // be empty.
+      static_assert(__if_hash_code_cached<is_empty<_H2>>::value,
+           "Functor used to map hash code to bucket index must be empty");
+
+      typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey,
+                                       _H1, _H2, _Hash,
+                                       __cache_hash_code> _HCBase;
+
+      // When hash codes are not cached local iterator is going to use _HCBase
+      // above to compute node bucket index so it has to be empty.
+      static_assert(__if_hash_code_not_cached<is_empty<_HCBase>>::value,
+           "Cache the hash code or make functors involved in hash code"
+           " and bucket index computation empty");
+
     public:
       typedef _Allocator                                  allocator_type;
       typedef _Value                                      value_type;
@@ -191,16 +219,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       typedef std::size_t                                 size_type;
       typedef std::ptrdiff_t                              difference_type;
+      typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey,
+                                       _H1, _H2, _Hash,
+                                       __constant_iterators,
+                                       __cache_hash_code>
+                                                         local_iterator;
+      typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey,
+                                             _H1, _H2, _Hash,
+                                             __constant_iterators,
+                                             __cache_hash_code>
+                                                         const_local_iterator;
       typedef __detail::_Node_iterator<value_type, __constant_iterators,
                                       __cache_hash_code>
-                                                         local_iterator;
+                                                         iterator;
       typedef __detail::_Node_const_iterator<value_type,
                                             __constant_iterators,
                                             __cache_hash_code>
-                                                         const_local_iterator;
-
-      typedef local_iterator iterator;
-      typedef const_local_iterator const_iterator;
+                                                         const_iterator;
 
       template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
               typename _Hashtable2>
@@ -212,7 +247,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       typedef typename _Allocator::template rebind<_Node>::other
                                                        _Node_allocator_type;
       typedef _Node* _Bucket;
-      //typedef __detail::_Bucket<_Value, __cache_hash_code> _Bucket;
       typedef typename _Allocator::template rebind<_Bucket>::other
                                                        _Bucket_allocator_type;
 
@@ -253,14 +287,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Node*
       _M_bucket_end(size_type __bkt) const;
 
-      // Gets the bucket node after the last if any
-      _Node*
-      _M_bucket_past_the_end(size_type __bkt) const
-        {
-         _Node* __end = _M_bucket_end(__bkt);
-         return __end ? __end->_M_next : nullptr;
-       }
-
     public:
       // Constructor, destructor, assignment, swap
       _Hashtable(size_type __bucket_hint,
@@ -364,35 +390,35 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       size_type
       bucket(const key_type& __k) const
-      {
-       return this->_M_bucket_index(__k, this->_M_hash_code(__k),
-                                    bucket_count());
-      }
+      { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
 
       local_iterator
       begin(size_type __n)
-      { return local_iterator(_M_bucket_begin(__n)); }
+      { return local_iterator(_M_bucket_begin(__n), __n,
+                             _M_bucket_count); }
 
       local_iterator
       end(size_type __n)
-      { return local_iterator(_M_bucket_past_the_end(__n)); }
+      { return local_iterator(nullptr, __n, _M_bucket_count); }
 
       const_local_iterator
       begin(size_type __n) const
-      { return const_local_iterator(_M_bucket_begin(__n)); }
+      { return const_local_iterator(_M_bucket_begin(__n), __n,
+                                   _M_bucket_count); }
 
       const_local_iterator
       end(size_type __n) const
-      { return const_local_iterator(_M_bucket_past_the_end(__n)); }
+      { return const_local_iterator(nullptr, __n, _M_bucket_count); }
 
       // DR 691.
       const_local_iterator
       cbegin(size_type __n) const
-      { return const_local_iterator(_M_bucket_begin(__n)); }
+      { return const_local_iterator(_M_bucket_begin(__n), __n,
+                                   _M_bucket_count); }
 
       const_local_iterator
       cend(size_type __n) const
-      { return const_local_iterator(_M_bucket_past_the_end(__n)); }
+      { return const_local_iterator(nullptr, __n, _M_bucket_count); }
 
       float
       load_factor() const noexcept
@@ -428,6 +454,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       equal_range(const key_type& __k) const;
 
     private:
+      size_type
+      _M_bucket_index(_Node* __n) const
+      { return _HCBase::_M_bucket_index(__n, _M_bucket_count); }
+
+      size_type
+      _M_bucket_index(const key_type& __k,
+                     typename _Hashtable::_Hash_code_type __c) const
+      { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); }
+
       // Find and insert helper functions and types
       _Node*
       _M_find_node(size_type, const key_type&,
@@ -679,9 +714,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Node* __n = _M_bucket_begin(__bkt);
       if (__n)
        for (;; __n = __n->_M_next)
-         if (!__n->_M_next 
-             || this->_M_bucket_index(__n->_M_next, _M_bucket_count)
-                != __bkt)
+         if (!__n->_M_next || _M_bucket_index(__n->_M_next) != __bkt)
            break;
       return __n;
     }
@@ -697,9 +730,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
               const _Equal& __eq, const _ExtractKey& __exk,
               const allocator_type& __a)
     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
-      __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
-                               _H1, _H2, _Hash, __chc>(__exk, __eq,
-                                                       __h1, __h2, __h),
+      __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
+                               _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
+                                                       __eq),
       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
       _M_node_allocator(__a),
       _M_bucket_count(0),
@@ -727,9 +760,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
                 const _Equal& __eq, const _ExtractKey& __exk,
                 const allocator_type& __a)
       : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
-       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
-                                 _H1, _H2, _Hash, __chc>(__exk, __eq,
-                                                         __h1, __h2, __h),
+       __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
+                                 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
+                                                         __eq),
        __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
        _M_node_allocator(__a),
        _M_bucket_count(0),
@@ -768,7 +801,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     _Hashtable(const _Hashtable& __ht)
     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
-      __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
+      __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
                                _H1, _H2, _Hash, __chc>(__ht),
       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
       _M_node_allocator(__ht._M_node_allocator),
@@ -833,7 +866,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     _Hashtable(_Hashtable&& __ht)
     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
-      __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
+      __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
                                _H1, _H2, _Hash, __chc>(__ht),
       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
       _M_node_allocator(std::move(__ht._M_node_allocator)),
@@ -874,8 +907,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // The only base class with member variables is hash_code_base.  We
       // define _Hash_code_base::_M_swap because different specializations
       // have different members.
-      __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
-       _H1, _H2, _Hash, __chc>::_M_swap(__x);
+      this->_M_swap(__x);
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
       // 431. Swapping containers with unequal allocators.
@@ -916,7 +948,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     find(const key_type& __k)
     {
       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
-      std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+      std::size_t __n = _M_bucket_index(__k, __code);
       _Node* __p = _M_find_node(__n, __k, __code);
       return __p ? iterator(__p) : this->end();
     }
@@ -933,7 +965,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     find(const key_type& __k) const
     {
       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
-      std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+      std::size_t __n = _M_bucket_index(__k, __code);
       _Node* __p = _M_find_node(__n, __k, __code);
       return __p ? const_iterator(__p) : this->end();
     }
@@ -950,7 +982,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     count(const key_type& __k) const
     {
       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
-      std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+      std::size_t __n = _M_bucket_index(__k, __code);
       _Node* __p = _M_bucket_begin(__n);
       if (!__p)
        return 0;
@@ -958,16 +990,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       std::size_t __result = 0;
       for (;; __p = __p->_M_next)
        {
-         if (this->_M_compare(__k, __code, __p))
+         if (this->_M_equals(__k, __code, __p))
            ++__result;
          else if (__result)
            // All equivalent values are next to each other, if we found a not
            // equivalent value after an equivalent one it means that we won't
            // find anymore an equivalent value.
            break;
-         if (!__p->_M_next
-             || this->_M_bucket_index(__p->_M_next, _M_bucket_count)
-                != __n)
+         if (!__p->_M_next || _M_bucket_index(__p->_M_next) != __n)
            break;
        }
       return __result;
@@ -990,15 +1020,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     equal_range(const key_type& __k)
     {
       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
-      std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+      std::size_t __n = _M_bucket_index(__k, __code);
       _Node* __p = _M_find_node(__n, __k, __code);
 
       if (__p)
        {
          _Node* __p1 = __p->_M_next;
-         while (__p1
-                && this->_M_bucket_index(__p1, _M_bucket_count) == __n
-                && this->_M_compare(__k, __code, __p1))
+         while (__p1 && _M_bucket_index(__p1) == __n
+                && this->_M_equals(__k, __code, __p1))
            __p1 = __p1->_M_next;
 
          return std::make_pair(iterator(__p), iterator(__p1));
@@ -1024,15 +1053,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     equal_range(const key_type& __k) const
     {
       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
-      std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+      std::size_t __n = _M_bucket_index(__k, __code);
       _Node* __p = _M_find_node(__n, __k, __code);
 
       if (__p)
        {
          _Node* __p1 = __p->_M_next;
-         while (__p1
-                && this->_M_bucket_index(__p1, _M_bucket_count) == __n
-                && this->_M_compare(__k, __code, __p1))
+         while (__p1 && _M_bucket_index(__p1) == __n
+                && this->_M_equals(__k, __code, __p1))
            __p1 = __p1->_M_next;
 
          return std::make_pair(const_iterator(__p), const_iterator(__p1));
@@ -1060,10 +1088,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        return nullptr;
       for (;; __p = __p->_M_next)
        {
-         if (this->_M_compare(__k, __code, __p))
+         if (this->_M_equals(__k, __code, __p))
            return __p;
-         if (!(__p->_M_next)
-             || this->_M_bucket_index(__p->_M_next, _M_bucket_count) != __n)
+         if (!(__p->_M_next) || _M_bucket_index(__p->_M_next) != __n)
            break;
        }
       return nullptr;
@@ -1119,8 +1146,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       if (__prev_n->_M_next)
        {
-         size_type __next_bkt =
-           this->_M_bucket_index(__prev_n->_M_next, _M_bucket_count);
+         size_type __next_bkt = _M_bucket_index(__prev_n->_M_next);
          if (__next_bkt != __bkt)
            _M_buckets[__next_bkt] = __new_n;
        }
@@ -1196,11 +1222,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
        __try
          {
-           const key_type& __k = this->_M_extract(__new_node->_M_v);
+           const key_type& __k = this->_M_extract()(__new_node->_M_v);
            typename _Hashtable::_Hash_code_type __code
              = this->_M_hash_code(__k);
-           size_type __bkt
-             = this->_M_bucket_index(__k, __code, _M_bucket_count);
+           size_type __bkt = _M_bucket_index(__k, __code);
 
            if (_Node* __p = _M_find_node(__bkt, __k, __code))
              {
@@ -1220,7 +1245,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
            if (__do_rehash.first)
              {
                _M_rehash(__do_rehash.second, __saved_state);
-               __bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+               __bkt = _M_bucket_index(__k, __code);
              }
 
            if (_M_buckets[__bkt])
@@ -1258,12 +1283,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
        __try
          {
-           const key_type& __k = this->_M_extract(__new_node->_M_v);
+           const key_type& __k = this->_M_extract()(__new_node->_M_v);
            typename _Hashtable::_Hash_code_type __code
              = this->_M_hash_code(__k);
            this->_M_store_code(__new_node, __code);
-           size_type __bkt
-             = this->_M_bucket_index(__k, __code, _M_bucket_count);
+           size_type __bkt = _M_bucket_index(__k, __code);
 
            // Second find the node, avoid rehash if compare throws.
            _Node* __prev = _M_find_node(__bkt, __k, __code);
@@ -1271,7 +1295,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
            if (__do_rehash.first)
              {
                _M_rehash(__do_rehash.second, __saved_state);
-               __bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+               __bkt = _M_bucket_index(__k, __code);
                // __prev is still valid because rehash do not invalidate nodes
              }
 
@@ -1322,8 +1346,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
        if (__do_rehash.first)
          {
-           const key_type& __k = this->_M_extract(__v);
-           __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
+           const key_type& __k = this->_M_extract()(__v);
+           __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second);
          }
 
        _Node* __new_node = nullptr;
@@ -1367,9 +1391,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
                 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
       _M_insert(_Arg&& __v, std::true_type)
       {
-       const key_type& __k = this->_M_extract(__v);
+       const key_type& __k = this->_M_extract()(__v);
        typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
-       size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+       size_type __n = _M_bucket_index(__k, __code);
 
        if (_Node* __p = _M_find_node(__n, __k, __code))
          return std::make_pair(iterator(__p), false);
@@ -1395,9 +1419,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
          = _M_rehash_policy._M_need_rehash(_M_bucket_count,
                                            _M_element_count, 1);
 
-       const key_type& __k = this->_M_extract(__v);
+       const key_type& __k = this->_M_extract()(__v);
        typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
-       size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+       size_type __n = _M_bucket_index(__k, __code);
 
        // First find the node, avoid leaking new_node if compare throws.
        _Node* __prev = _M_find_node(__n, __k, __code);
@@ -1410,7 +1434,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
            if (__do_rehash.first)
              {
                _M_rehash(__do_rehash.second, __saved_state);
-               __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+               __n = _M_bucket_index(__k, __code);
                // __prev is still valid because rehash do not invalidate nodes
              }
 
@@ -1477,7 +1501,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     erase(const_iterator __it)
     {
       _Node* __n = __it._M_cur;
-      std::size_t __bkt = this->_M_bucket_index(__n, _M_bucket_count);
+      std::size_t __bkt = _M_bucket_index(__n);
 
       // Look for previous node to unlink it from the erased one, this is why
       // we need buckets to contain the before begin node of the bucket to make
@@ -1485,12 +1509,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Node* __prev_n = _M_get_previous_node(__bkt, __n);
       if (__n == _M_bucket_begin(__bkt))
        _M_remove_bucket_begin(__bkt, __n->_M_next,
-          __n->_M_next ? this->_M_bucket_index(__n->_M_next, _M_bucket_count)
-                       : 0);
+          __n->_M_next ? _M_bucket_index(__n->_M_next) : 0);
       else if (__n->_M_next)
        {
-         size_type __next_bkt =
-           this->_M_bucket_index(__n->_M_next, _M_bucket_count);
+         size_type __next_bkt = _M_bucket_index(__n->_M_next);
          if (__next_bkt != __bkt)
            _M_buckets[__next_bkt] = __prev_n;
        }
@@ -1516,7 +1538,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     erase(const key_type& __k)
     {
       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
-      std::size_t __bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+      std::size_t __bkt = _M_bucket_index(__k, __code);
       // Look for the first matching node with its previous node at the same
       // time
       _Node* __n = _M_buckets[__bkt];
@@ -1531,10 +1553,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       bool __is_bucket_begin = true;
       for (;; __prev_n = __n, __n = __n->_M_next)
        {
-         if (this->_M_compare(__k, __code, __n))
+         if (this->_M_equals(__k, __code, __n))
            break;
-         if (!(__n->_M_next)
-             || this->_M_bucket_index(__n->_M_next, _M_bucket_count) != __bkt)
+         if (!(__n->_M_next) || _M_bucket_index(__n->_M_next) != __bkt)
            return 0;
          __is_bucket_begin = false;
        }
@@ -1551,7 +1572,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
          // _GLIBCXX_RESOLVE_LIB_DEFECTS
          // 526. Is it undefined if a function in the standard changes
          // in parameters?
-         if (std::__addressof(this->_M_extract(__p->_M_v))
+         if (std::__addressof(this->_M_extract()(__p->_M_v))
              != std::__addressof(__k))
            _M_deallocate_node(__p);
          else
@@ -1560,9 +1581,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
          ++__result;
          if (!__next_n)
            break;
-         __next_bkt = this->_M_bucket_index(__next_n, _M_bucket_count);
+         __next_bkt = _M_bucket_index(__next_n);
        }
-      while (__next_bkt == __bkt && this->_M_compare(__k, __code, __next_n));
+      while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
 
       if (__saved_n)
        _M_deallocate_node(__saved_n);
@@ -1591,7 +1612,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__n == __last_n)
        return iterator(__n);
 
-      std::size_t __bkt = this->_M_bucket_index(__n, _M_bucket_count);
+      std::size_t __bkt = _M_bucket_index(__n);
 
       _Node* __prev_n = _M_get_previous_node(__bkt, __n);
       bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
@@ -1606,7 +1627,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
              --_M_element_count;
              if (!__n)
                break;
-             __n_bkt = this->_M_bucket_index(__n, _M_bucket_count);
+             __n_bkt = _M_bucket_index(__n);
            }
          while (__n != __last_n && __n_bkt == __bkt);
          if (__is_bucket_begin)
@@ -1672,7 +1693,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
          while (__p)
            {
              _Node* __next = __p->_M_next;
-             std::size_t __new_index = this->_M_bucket_index(__p, __n);
+             std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
              if (!__new_buckets[__new_index])
                // Store temporarily bucket end node in _M_buckets if possible.
                // This will boost second loop where we need to access bucket
index e97685c..12a9ad9 100644 (file)
@@ -101,8 +101,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
          _M_next() { }
     };
 
-  // Local iterators, used to iterate within a bucket but not between
-  // buckets.
+  // Node iterators, used to iterate through all the hashtable.
   template<typename _Value, bool __cache>
     struct _Node_iterator_base
     {
@@ -425,8 +424,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       _Hashtable* __h = static_cast<_Hashtable*>(this);
       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
-      std::size_t __n = __h->_M_bucket_index(__k, __code,
-                                            __h->_M_bucket_count);
+      std::size_t __n = __h->_M_bucket_index(__k, __code);
 
       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
       if (!__p)
@@ -443,8 +441,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       _Hashtable* __h = static_cast<_Hashtable*>(this);
       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
-      std::size_t __n = __h->_M_bucket_index(__k, __code,
-                                            __h->_M_bucket_count);
+      std::size_t __n = __h->_M_bucket_index(__k, __code);
 
       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
       if (!__p)
@@ -462,8 +459,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       _Hashtable* __h = static_cast<_Hashtable*>(this);
       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
-      std::size_t __n = __h->_M_bucket_index(__k, __code,
-                                            __h->_M_bucket_count);
+      std::size_t __n = __h->_M_bucket_index(__k, __code);
 
       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
       if (!__p)
@@ -479,8 +475,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       const _Hashtable* __h = static_cast<const _Hashtable*>(this);
       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
-      std::size_t __n = __h->_M_bucket_index(__k, __code,
-                                            __h->_M_bucket_count);
+      std::size_t __n = __h->_M_bucket_index(__k, __code);
 
       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
       if (!__p)
@@ -518,6 +513,49 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       }
     };
 
+  // Helper class using EBO when it is not forbidden, type is not final,
+  // and when it worth it, type is empty.
+  template<int _N, typename _Tp,
+          bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
+    struct _Ebo_helper;
+
+  // Specialization using EBO
+  template<int _N, typename _Tp>
+    struct _Ebo_helper<_N, _Tp, true> : _Tp
+    {
+      _Ebo_helper() = default;
+      _Ebo_helper(const _Tp& __tp) : _Tp(__tp)
+      { }
+
+      static const _Tp&
+      _S_cget(const _Ebo_helper<_N, _Tp, true>& __eboh)
+      { return static_cast<const _Tp&>(__eboh); }
+
+      static _Tp&
+      _S_get(_Ebo_helper<_N, _Tp, true>& __eboh)
+      { return static_cast<_Tp&>(__eboh); }
+    };
+
+  // Specialization not using EBO
+  template<int _N, typename _Tp>
+    struct _Ebo_helper<_N, _Tp, false>
+    {
+      _Ebo_helper() = default;
+      _Ebo_helper(const _Tp& __tp) : m_tp(__tp)
+      { }
+
+      static const _Tp&
+      _S_cget(const _Ebo_helper<_N, _Tp, false>& __eboh)
+      { return __eboh.m_tp; }
+
+      static _Tp&
+      _S_get(_Ebo_helper<_N, _Tp, false>& __eboh)
+      { return __eboh.m_tp; }
+
+    private:
+      _Tp m_tp;
+    };
+
   // Class template _Hash_code_base.  Encapsulates two policy issues that
   // aren't quite orthogonal.
   //   (1) the difference between using a ranged hash function and using
@@ -526,28 +564,36 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   //       we have a dummy type as placeholder.
   //   (2) Whether or not we cache hash codes.  Caching hash codes is
   //       meaningless if we have a ranged hash function.
-  // We also put the key extraction and equality comparison function
-  // objects here, for convenience.
+  // We also put the key extraction objects here, for convenience.
+  //
+  // Each specialization derives from one or more of the template parameters to
+  // benefit from Ebo. This is important as this type is inherited in some cases
+  // by the _Local_iterator_base type used to implement local_iterator and
+  // const_local_iterator. As with any iterator type we prefer to make it as
+  // small as possible.
 
   // Primary template: unused except as a hook for specializations.
-  template<typename _Key, typename _Value,
-          typename _ExtractKey, typename _Equal,
+  template<typename _Key, typename _Value, typename _ExtractKey,
           typename _H1, typename _H2, typename _Hash,
           bool __cache_hash_code>
     struct _Hash_code_base;
 
   // Specialization: ranged hash function, no caching hash codes.  H1
   // and H2 are provided but ignored.  We define a dummy hash code type.
-  template<typename _Key, typename _Value,
-          typename _ExtractKey, typename _Equal,
+  template<typename _Key, typename _Value, typename _ExtractKey, 
           typename _H1, typename _H2, typename _Hash>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
-                          _Hash, false>
+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
+      : _Ebo_helper<0, _ExtractKey>, _Ebo_helper<1, _Hash>
     {
+    private:
+      typedef _Ebo_helper<0, _ExtractKey> _EboExtractKey;
+      typedef _Ebo_helper<1, _Hash> _EboHash;
     protected:
-      _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
+      // We need the default constructor for the local iterators.
+      _Hash_code_base() = default;
+      _Hash_code_base(const _ExtractKey& __ex,
                      const _H1&, const _H2&, const _Hash& __h)
-      : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
+       : _EboExtractKey(__ex), _EboHash(__h) { }
 
       typedef void* _Hash_code_type;
 
@@ -558,17 +604,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       std::size_t
       _M_bucket_index(const _Key& __k, _Hash_code_type,
                      std::size_t __n) const
-      { return _M_ranged_hash(__k, __n); }
+      { return _M_ranged_hash()(__k, __n); }
 
       std::size_t
       _M_bucket_index(const _Hash_node<_Value, false>* __p,
                      std::size_t __n) const
-      { return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
-
-      bool
-      _M_compare(const _Key& __k, _Hash_code_type,
-                _Hash_node<_Value, false>* __n) const
-      { return _M_eq(__k, _M_extract(__n->_M_v)); }
+      { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); }
 
       void
       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
@@ -582,72 +623,75 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       _M_swap(_Hash_code_base& __x)
       {
-       std::swap(_M_extract, __x._M_extract);
-       std::swap(_M_eq, __x._M_eq);
-       std::swap(_M_ranged_hash, __x._M_ranged_hash);
+       std::swap(_M_extract(), __x._M_extract());
+       std::swap(_M_ranged_hash(), __x._M_ranged_hash());
       }
 
     protected:
-      _ExtractKey  _M_extract;
-      _Equal       _M_eq;
-      _Hash        _M_ranged_hash;
+      const _ExtractKey&
+      _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+      _ExtractKey&
+      _M_extract() { return _EboExtractKey::_S_get(*this); }
+      const _Hash&
+      _M_ranged_hash() const { return _EboHash::_S_cget(*this); }
+      _Hash&
+      _M_ranged_hash() { return _EboHash::_S_get(*this); }
     };
 
-
   // No specialization for ranged hash function while caching hash codes.
   // That combination is meaningless, and trying to do it is an error.
 
-
   // Specialization: ranged hash function, cache hash codes.  This
   // combination is meaningless, so we provide only a declaration
   // and no definition.
-  template<typename _Key, typename _Value,
-          typename _ExtractKey, typename _Equal,
+  template<typename _Key, typename _Value, typename _ExtractKey,
           typename _H1, typename _H2, typename _Hash>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
-                          _Hash, true>;
+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
 
   // Specialization: hash function and range-hashing function, no
-  // caching of hash codes.  H is provided but ignored.  Provides
-  // typedef and accessor required by TR1.
-  template<typename _Key, typename _Value,
-          typename _ExtractKey, typename _Equal,
+  // caching of hash codes.
+  // Provides typedef and accessor required by TR1.
+  template<typename _Key, typename _Value, typename _ExtractKey,
           typename _H1, typename _H2>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
                           _Default_ranged_hash, false>
+      : _Ebo_helper<0, _ExtractKey>, _Ebo_helper<1, _H1>, _Ebo_helper<2, _H2>
     {
+    private:
+      typedef _Ebo_helper<0, _ExtractKey> _EboExtractKey;
+      typedef _Ebo_helper<1, _H1> _EboH1;
+      typedef _Ebo_helper<2, _H2> _EboH2;
+
+    public:
       typedef _H1 hasher;
 
       hasher
       hash_function() const
-      { return _M_h1; }
+      { return _M_h1(); }
 
     protected:
-      _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
+      // We need the default constructor for the local iterators.
+      _Hash_code_base() = default;
+      _Hash_code_base(const _ExtractKey& __ex,
                      const _H1& __h1, const _H2& __h2,
                      const _Default_ranged_hash&)
-      : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
+      : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
 
       typedef std::size_t _Hash_code_type;
 
       _Hash_code_type
       _M_hash_code(const _Key& __k) const
-      { return _M_h1(__k); }
+      { return _M_h1()(__k); }
 
       std::size_t
       _M_bucket_index(const _Key&, _Hash_code_type __c,
                      std::size_t __n) const
-      { return _M_h2(__c, __n); }
+      { return _M_h2()(__c, __n); }
 
       std::size_t
       _M_bucket_index(const _Hash_node<_Value, false>* __p,
                      std::size_t __n) const
-      { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
-
-      bool
-      _M_compare(const _Key& __k, _Hash_code_type,
-                _Hash_node<_Value, false>* __n) const
-      { return _M_eq(__k, _M_extract(__n->_M_v)); }
+      { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); }
 
       void
       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
@@ -661,60 +705,68 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       _M_swap(_Hash_code_base& __x)
       {
-       std::swap(_M_extract, __x._M_extract);
-       std::swap(_M_eq, __x._M_eq);
-       std::swap(_M_h1, __x._M_h1);
-       std::swap(_M_h2, __x._M_h2);
+       std::swap(_M_extract(), __x._M_extract());
+       std::swap(_M_h1(), __x._M_h1());
+       std::swap(_M_h2(), __x._M_h2());
       }
 
     protected:
-      _ExtractKey  _M_extract;
-      _Equal       _M_eq;
-      _H1          _M_h1;
-      _H2          _M_h2;
+      const _ExtractKey&
+      _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+      _ExtractKey&
+      _M_extract() { return _EboExtractKey::_S_get(*this); }
+      const _H1&
+      _M_h1() const { return _EboH1::_S_cget(*this); }
+      _H1&
+      _M_h1() { return _EboH1::_S_get(*this); }
+      const _H2&
+      _M_h2() const { return _EboH2::_S_cget(*this); }
+      _H2&
+      _M_h2() { return _EboH2::_S_get(*this); }
     };
 
   // Specialization: hash function and range-hashing function,
   // caching hash codes.  H is provided but ignored.  Provides
   // typedef and accessor required by TR1.
-  template<typename _Key, typename _Value,
-          typename _ExtractKey, typename _Equal,
+  template<typename _Key, typename _Value, typename _ExtractKey,
           typename _H1, typename _H2>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
                           _Default_ranged_hash, true>
+      : _Ebo_helper<0, _ExtractKey>, _Ebo_helper<1, _H1>, _Ebo_helper<2, _H2>
     {
+    private:
+      typedef _Ebo_helper<0, _ExtractKey> _EboExtractKey;
+      typedef _Ebo_helper<1, _H1> _EboH1;
+      typedef _Ebo_helper<2, _H2> _EboH2;
+
+    public:
       typedef _H1 hasher;
 
       hasher
       hash_function() const
-      { return _M_h1; }
+      { return _M_h1(); }
 
     protected:
-      _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
+      _Hash_code_base(const _ExtractKey& __ex,
                      const _H1& __h1, const _H2& __h2,
                      const _Default_ranged_hash&)
-      : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
+      : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
 
       typedef std::size_t _Hash_code_type;
 
       _Hash_code_type
       _M_hash_code(const _Key& __k) const
-      { return _M_h1(__k); }
+      { return _M_h1()(__k); }
 
       std::size_t
       _M_bucket_index(const _Key&, _Hash_code_type __c,
                      std::size_t __n) const
-      { return _M_h2(__c, __n); }
+      { return _M_h2()(__c, __n); }
 
       std::size_t
       _M_bucket_index(const _Hash_node<_Value, true>* __p,
                      std::size_t __n) const
-      { return _M_h2(__p->_M_hash_code, __n); }
-
-      bool
-      _M_compare(const _Key& __k, _Hash_code_type __c,
-                _Hash_node<_Value, true>* __n) const
-      { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
+      { return _M_h2()(__p->_M_hash_code, __n); }
 
       void
       _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
@@ -728,17 +780,290 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       _M_swap(_Hash_code_base& __x)
       {
-       std::swap(_M_extract, __x._M_extract);
-       std::swap(_M_eq, __x._M_eq);
-       std::swap(_M_h1, __x._M_h1);
-       std::swap(_M_h2, __x._M_h2);
+       std::swap(_M_extract(), __x._M_extract());
+       std::swap(_M_h1(), __x._M_h1());
+       std::swap(_M_h2(), __x._M_h2());
       }
 
     protected:
-      _ExtractKey  _M_extract;
-      _Equal       _M_eq;
-      _H1          _M_h1;
-      _H2          _M_h2;
+      const _ExtractKey&
+      _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+      _ExtractKey&
+      _M_extract() { return _EboExtractKey::_S_get(*this); }
+      const _H1&
+      _M_h1() const { return _EboH1::_S_cget(*this); }
+      _H1&
+      _M_h1() { return _EboH1::_S_get(*this); }
+      const _H2&
+      _M_h2() const { return _EboH2::_S_cget(*this); }
+      _H2&
+      _M_h2() { return _EboH2::_S_get(*this); }
+    };
+
+  template <typename _Key, typename _Value, typename _ExtractKey,
+           typename _Equal, typename _HashCodeType,
+           bool __cache_hash_code>
+  struct _Equal_helper;
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+          typename _Equal, typename _HashCodeType>
+  struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true>
+  {
+    static bool
+    _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
+             const _Key& __k, _HashCodeType __c,
+             _Hash_node<_Value, true>* __n)
+    { return __c == __n->_M_hash_code
+            && __eq(__k, __extract(__n->_M_v)); }
+  };
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+          typename _Equal, typename _HashCodeType>
+  struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false>
+  {
+    static bool
+    _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
+             const _Key& __k, _HashCodeType,
+             _Hash_node<_Value, false>* __n)
+    { return __eq(__k, __extract(__n->_M_v)); }
+  };
+
+  // Helper class adding management of _Equal functor to _Hash_code_base
+  // type.
+  template<typename _Key, typename _Value,
+          typename _ExtractKey, typename _Equal,
+          typename _H1, typename _H2, typename _Hash,
+          bool __cache_hash_code>
+  struct _Hashtable_base
+    : _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+                     __cache_hash_code>,
+      _Ebo_helper<0, _Equal>
+  {
+  private:
+    typedef _Ebo_helper<0, _Equal> _EboEqual;
+
+  protected:
+    typedef _Hash_code_base<_Key, _Value, _ExtractKey,
+                           _H1, _H2, _Hash, __cache_hash_code> _HCBase;
+    typedef typename _HCBase::_Hash_code_type _Hash_code_type;
+
+    _Hashtable_base(const _ExtractKey& __ex,
+                   const _H1& __h1, const _H2& __h2,
+                   const _Hash& __hash, const _Equal& __eq)
+      : _HCBase(__ex, __h1, __h2, __hash), _EboEqual(__eq) { }
+
+    bool
+    _M_equals(const _Key& __k, _Hash_code_type __c,
+             _Hash_node<_Value, __cache_hash_code>* __n) const
+    {
+      typedef _Equal_helper<_Key, _Value, _ExtractKey,
+                          _Equal, _Hash_code_type,
+                          __cache_hash_code> _EqualHelper;
+      return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), __k, __c, __n);
+    }
+
+    void
+    _M_swap(_Hashtable_base& __x)
+    {
+      _HCBase::_M_swap(__x);
+      std::swap(_M_eq(), __x._M_eq());
+    }
+
+  private:
+    const _Equal&
+    _M_eq() const { return _EboEqual::_S_cget(*this); }
+    _Equal&
+    _M_eq() { return _EboEqual::_S_get(*this); }
+  };
+
+  // Local iterators, used to iterate within a bucket but not between
+  // buckets.
+  template<typename _Key, typename _Value, typename _ExtractKey,
+          typename _H1, typename _H2, typename _Hash,
+          bool __cache_hash_code>
+    struct _Local_iterator_base;
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+          typename _H1, typename _H2, typename _Hash>
+    struct _Local_iterator_base<_Key, _Value, _ExtractKey,
+                               _H1, _H2, _Hash, true>
+      : _H2
+    {
+      _Local_iterator_base() = default;
+      _Local_iterator_base(_Hash_node<_Value, true>* __p,
+                          std::size_t __bkt, std::size_t __bkt_count)
+      : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+
+      void
+      _M_incr()
+      {
+       _M_cur = _M_cur->_M_next;
+       if (_M_cur)
+         {
+           std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count);
+           if (__bkt != _M_bucket)
+             _M_cur = nullptr;
+         }
+      }
+
+      const _H2& _M_h2() const
+      { return *this; }
+
+      _Hash_node<_Value, true>*  _M_cur;
+      std::size_t _M_bucket;
+      std::size_t _M_bucket_count;
+    };
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+          typename _H1, typename _H2, typename _Hash>
+    struct _Local_iterator_base<_Key, _Value, _ExtractKey,
+                               _H1, _H2, _Hash, false>
+      : _Hash_code_base<_Key, _Value, _ExtractKey,
+                       _H1, _H2, _Hash, false>
+    {
+      _Local_iterator_base() = default;
+      _Local_iterator_base(_Hash_node<_Value, false>* __p,
+                          std::size_t __bkt, std::size_t __bkt_count)
+      : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+
+      void
+      _M_incr()
+      {
+       _M_cur = _M_cur->_M_next;
+       if (_M_cur)
+         {
+           std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
+           if (__bkt != _M_bucket)
+             _M_cur = nullptr;
+         }
+      }
+
+      _Hash_node<_Value, false>*  _M_cur;
+      std::size_t _M_bucket;
+      std::size_t _M_bucket_count;
+    };
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+          typename _H1, typename _H2, typename _Hash, bool __cache>
+    inline bool
+    operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
+                                         _H1, _H2, _Hash, __cache>& __x,
+              const _Local_iterator_base<_Key, _Value, _ExtractKey,
+                                         _H1, _H2, _Hash, __cache>& __y)
+    { return __x._M_cur == __y._M_cur; }
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+          typename _H1, typename _H2, typename _Hash, bool __cache>
+    inline bool
+    operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
+                                         _H1, _H2, _Hash, __cache>& __x,
+              const _Local_iterator_base<_Key, _Value, _ExtractKey,
+                                         _H1, _H2, _Hash, __cache>& __y)
+    { return __x._M_cur != __y._M_cur; }
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+          typename _H1, typename _H2, typename _Hash,
+          bool __constant_iterators, bool __cache>
+    struct _Local_iterator
+    : public _Local_iterator_base<_Key, _Value, _ExtractKey,
+                                 _H1, _H2, _Hash, __cache>
+    {
+      typedef _Value                                   value_type;
+      typedef typename std::conditional<__constant_iterators,
+                                       const _Value*, _Value*>::type
+                                                      pointer;
+      typedef typename std::conditional<__constant_iterators,
+                                       const _Value&, _Value&>::type
+                                                      reference;
+      typedef std::ptrdiff_t                           difference_type;
+      typedef std::forward_iterator_tag                iterator_category;
+
+      _Local_iterator() = default;
+
+      explicit
+      _Local_iterator(_Hash_node<_Value, __cache>* __p,
+                     std::size_t __bkt, std::size_t __bkt_count)
+      : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+                            __cache>(__p, __bkt, __bkt_count)
+      { }
+
+      reference
+      operator*() const
+      { return this->_M_cur->_M_v; }
+
+      pointer
+      operator->() const
+      { return std::__addressof(this->_M_cur->_M_v); }
+
+      _Local_iterator&
+      operator++()
+      {
+       this->_M_incr();
+       return *this;
+      }
+
+      _Local_iterator
+      operator++(int)
+      {
+       _Local_iterator __tmp(*this);
+       this->_M_incr();
+       return __tmp;
+      }
+    };
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+          typename _H1, typename _H2, typename _Hash,
+          bool __constant_iterators, bool __cache>
+    struct _Local_const_iterator
+    : public _Local_iterator_base<_Key, _Value, _ExtractKey,
+                                 _H1, _H2, _Hash, __cache>
+    {
+      typedef _Value                                   value_type;
+      typedef const _Value*                            pointer;
+      typedef const _Value&                            reference;
+      typedef std::ptrdiff_t                           difference_type;
+      typedef std::forward_iterator_tag                iterator_category;
+
+      _Local_const_iterator() = default;
+
+      explicit
+      _Local_const_iterator(_Hash_node<_Value, __cache>* __p,
+                           std::size_t __bkt, std::size_t __bkt_count)
+      : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+                            __cache>(__p, __bkt, __bkt_count)
+      { }
+
+      _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
+                                                 _H1, _H2, _Hash,
+                                                 __constant_iterators,
+                                                 __cache>& __x)
+      : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+                            __cache>(__x._M_cur, __x._M_bucket,
+                                     __x._M_bucket_count)
+      { }
+
+      reference
+      operator*() const
+      { return this->_M_cur->_M_v; }
+
+      pointer
+      operator->() const
+      { return std::__addressof(this->_M_cur->_M_v); }
+
+      _Local_const_iterator&
+      operator++()
+      {
+       this->_M_incr();
+       return *this;
+      }
+
+      _Local_const_iterator
+      operator++(int)
+      {
+       _Local_const_iterator __tmp(*this);
+       this->_M_incr();
+       return __tmp;
+      }
     };
 
 
index 7c810d3..95f5657 100644 (file)
@@ -41,7 +41,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
           class _Pred = std::equal_to<_Key>,
           class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
           bool __cache_hash_code =
-            __not_<__and_<is_integral<_Key>,
+            __not_<__and_<is_integral<_Key>, is_empty<_Hash>,
+                          integral_constant<bool, !__is_final(_Hash)>,
                           __detail::__is_noexcept_hash<_Key, _Hash>>>::value>
     class __unordered_map
     : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
@@ -112,7 +113,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
           class _Pred = std::equal_to<_Key>,
           class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
           bool __cache_hash_code =
-            __not_<__and_<is_integral<_Key>,
+            __not_<__and_<is_integral<_Key>, is_empty<_Hash>,
+                          integral_constant<bool, !__is_final(_Hash)>,
                           __detail::__is_noexcept_hash<_Key, _Hash>>>::value>
     class __unordered_multimap
     : public _Hashtable<_Key, std::pair<const _Key, _Tp>,
index 9aef082..3d5361d 100644 (file)
@@ -41,7 +41,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
           class _Pred = std::equal_to<_Value>,
           class _Alloc = std::allocator<_Value>,
           bool __cache_hash_code =
-            __not_<__and_<is_integral<_Value>,
+            __not_<__and_<is_integral<_Value>, is_empty<_Hash>,
+                          integral_constant<bool, !__is_final(_Hash)>,
                           __detail::__is_noexcept_hash<_Value, _Hash>>>::value>
     class __unordered_set
     : public _Hashtable<_Value, _Value, _Alloc,
@@ -124,7 +125,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
           class _Pred = std::equal_to<_Value>,
           class _Alloc = std::allocator<_Value>,
           bool __cache_hash_code =
-            __not_<__and_<is_integral<_Value>,
+            __not_<__and_<is_integral<_Value>, is_empty<_Hash>,
+                          integral_constant<bool, !__is_final(_Hash)>,
                           __detail::__is_noexcept_hash<_Value, _Hash>>>::value>
     class __unordered_multiset
     : public _Hashtable<_Value, _Value, _Alloc,
index cf84948..37ca3ce 100644 (file)
@@ -418,11 +418,19 @@ namespace __debug
 
       static _Base_local_iterator
       _S_to_local(_Base_iterator __it)
-      { return _Base_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+       // need to compute __it's node bucket
+       return _Base_local_iterator(__it._M_cur, 0, 0);
+      }
 
       static _Base_const_local_iterator
       _S_to_local(_Base_const_iterator __it)
-      { return _Base_const_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+       // need to compute __it's node bucket
+       return _Base_const_local_iterator(__it._M_cur, 0, 0);
+      }
     };
 
   template<typename _Key, typename _Tp, typename _Hash,
@@ -820,11 +828,19 @@ namespace __debug
 
       static _Base_local_iterator
       _S_to_local(_Base_iterator __it)
-      { return _Base_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+       // need to compute __it's node bucket
+       return _Base_local_iterator(__it._M_cur, 0, 0);
+      }
 
       static _Base_const_local_iterator
       _S_to_local(_Base_const_iterator __it)
-      { return _Base_const_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+       // need to compute __it's node bucket
+       return _Base_const_local_iterator(__it._M_cur, 0, 0);
+      }
     };
 
   template<typename _Key, typename _Tp, typename _Hash,
index ba44040..7323184 100644 (file)
@@ -417,11 +417,19 @@ namespace __debug
 
       static _Base_local_iterator
       _S_to_local(_Base_iterator __it)
-      { return _Base_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+       // need to compute __it's node bucket
+       return _Base_local_iterator(__it._M_cur, 0, 0);
+      }
 
       static _Base_const_local_iterator
       _S_to_local(_Base_const_iterator __it)
-      { return _Base_const_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+       // need to compute __it's node bucket
+       return _Base_const_local_iterator(__it._M_cur, 0, 0);
+      }
     };
 
   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
@@ -805,11 +813,19 @@ namespace __debug
 
       static _Base_local_iterator
       _S_to_local(_Base_iterator __it)
-      { return _Base_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+       // need to compute __it's node bucket
+       return _Base_local_iterator(__it._M_cur, 0, 0);
+      }
 
       static _Base_const_local_iterator
       _S_to_local(_Base_const_iterator __it)
-      { return _Base_const_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+       // need to compute __it's node bucket
+       return _Base_const_local_iterator(__it._M_cur, 0, 0);
+      }
     };
 
   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
index 3688d54..1d0f0d5 100644 (file)
@@ -308,9 +308,9 @@ namespace __profile
        while (__it != this->end())
          {
            size_type __bkt = this->bucket(__it->first);
-           for (++__it; __it != this->end()
-                        && this->bucket(__it->first) == __bkt;
-                ++__it)
+           auto __lit = this->begin(__bkt);
+           auto __lend = this->end(__bkt);
+           for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
              ++__chain;
            if (__chain)
              {
@@ -577,9 +577,9 @@ namespace __profile
        while (__it != this->end())
          {
            size_type __bkt = this->bucket(__it->first);
-           for (++__it; __it != this->end()
-                        && this->bucket(__it->first) == __bkt;
-                ++__it)
+           auto __lit = this->begin(__bkt);
+           auto __lend = this->end(__bkt);
+           for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
              ++__chain;
            if (__chain)
              {
index 55177b3..7bb10dc 100644 (file)
@@ -277,10 +277,10 @@ namespace __profile
        while (__it != this->end())
          {
            size_type __bkt = this->bucket(*__it);
-           for (++__it; __it != this->end() && this->bucket(*__it) == __bkt;
-                ++__it)
+           auto __lit = this->begin(__bkt);
+           auto __lend = this->end(__bkt);
+           for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
              ++__chain;
-
            if (__chain)
              {
                ++__chain;
@@ -539,10 +539,10 @@ namespace __profile
        while (__it != this->end())
          {
            size_type __bkt = this->bucket(*__it);
-           for (++__it; __it != this->end() && this->bucket(*__it) == __bkt;
-                ++__it)
+           auto __lit = this->begin(__bkt);
+           auto __lend = this->end(__bkt);
+           for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
              ++__chain;
-
            if (__chain)
              {
                ++__chain;
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/final_hash.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/final_hash.cc
new file mode 100644 (file)
index 0000000..c509a34
--- /dev/null
@@ -0,0 +1,39 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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 Pred 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/>.
+
+#include <string>
+#include <unordered_map>
+
+namespace
+{
+  template<typename _Tp>
+  struct final_hash final
+  {
+    std::size_t operator() (const _Tp&) const noexcept
+    { return 0; }
+  };
+}
+
+// A non-integral type:
+template class std::unordered_map<std::string, int, final_hash<std::string>>;
+
+// An integral type;
+template class std::unordered_map<int, int, final_hash<int>>;
+
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/final_hash.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/final_hash.cc
new file mode 100644 (file)
index 0000000..4e2920c
--- /dev/null
@@ -0,0 +1,40 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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 Pred 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/>.
+
+#include <string>
+#include <unordered_map>
+
+namespace
+{
+  template<typename _Tp>
+  struct final_hash final
+  {
+    std::size_t operator() (const _Tp&) const noexcept
+    { return 0; }
+  };
+}
+
+// A non-integral type:
+template class std::unordered_multimap<std::string, int,
+                                      final_hash<std::string>>;
+
+// An integral type;
+template class std::unordered_multimap<int, int, final_hash<int>>;
+
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/final_hash.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/final_hash.cc
new file mode 100644 (file)
index 0000000..242642f
--- /dev/null
@@ -0,0 +1,39 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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 Pred 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/>.
+
+#include <string>
+#include <unordered_set>
+
+namespace
+{
+  template<typename _Tp>
+  struct final_hash final
+  {
+    std::size_t operator() (const _Tp&) const noexcept
+    { return 0; }
+  };
+}
+
+// A non-integral type:
+template class std::unordered_multiset<std::string, final_hash<std::string>>;
+
+// An integral type;
+template class std::unordered_multiset<int, final_hash<int>>;
+
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/final_hash.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/final_hash.cc
new file mode 100644 (file)
index 0000000..5dced4c
--- /dev/null
@@ -0,0 +1,39 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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 Pred 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/>.
+
+#include <string>
+#include <unordered_set>
+
+namespace
+{
+  template<typename _Tp>
+  struct final_hash final
+  {
+    std::size_t operator() (const _Tp&) const noexcept
+    { return 0; }
+  };
+}
+
+// A non-integral type:
+template class std::unordered_set<std::string, final_hash<std::string>>;
+
+// An integral type;
+template class std::unordered_set<int, final_hash<int>>;
+
index aa52e6b..eb16e81 100644 (file)
@@ -19,7 +19,7 @@
 // with this library; see the file COPYING3.  If not see
 // <http://www.gnu.org/licenses/>.
 
-// { dg-error "static assertion failed" "" { target *-*-* } 177 }
+// { dg-error "static assertion failed" "" { target *-*-* } 185 }
 
 #include <unordered_set>