2012-01-13 François Dumont <fdumont@gcc.gnu.org>

	* include/bits/hashtable_policy.h (_Hash_node_base): New, use it as
	base class of ...
	(_Hash_node<Value, true>, _Hash_node<Value, false>): ... those.
	* include/bits/hashtable.h (_Hashtable): Replace _M_begin_bucket_index
	by _M_before_begin. Review implementation so that we do not need to
	look for previous non-empty bucket when inserting nodes.

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

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index da43715..fa87445 100644 (file)
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,12 @@
+2012-01-13  François Dumont  <fdumont@gcc.gnu.org>
+
+       * include/bits/hashtable_policy.h (_Hash_node_base): New, use it as
+       base class of ...
+       (_Hash_node<Value, true>, _Hash_node<Value, false>): ... those.
+       * include/bits/hashtable.h (_Hashtable): Replace _M_begin_bucket_index
+       by _M_before_begin. Review implementation so that we do not need to
+       look for previous non-empty bucket when inserting nodes.
+

 2012-01-09  Kai Tietz  <ktietz@redhat.com>
 
        PR libstc++/51673 part 2
 2012-01-09  Kai Tietz  <ktietz@redhat.com>
 
        PR libstc++/51673 part 2

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index c9f3419..37672a2 100644 (file)
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -93,13 +93,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // and unordered_multimap.
   /**
    * Here's _Hashtable data structure, each _Hashtable has:
   // and unordered_multimap.
   /**
    * Here's _Hashtable data structure, each _Hashtable has:

-   * - _Bucket[]     _M_buckets
-   * - size_type     _M_bucket_count
-   * - size_type     _M_begin_bucket_index
-   * - size_type     _M_element_count
+   * - _Bucket[]       _M_buckets
+   * - _Hash_node_base _M_before_begin
+   * - size_type       _M_bucket_count
+   * - size_type       _M_element_count

    *
    *

-   * with _Bucket being _Node* and _Node:
-   * - _Node*        _M_next
+   * with _Bucket being _Hash_node* and _Hash_node constaining:
+   * - _Hash_node*   _M_next

    * - Tp            _M_value
    * - size_t        _M_code if cache_hash_code is true
    *
    * - Tp            _M_value
    * - size_t        _M_code if cache_hash_code is true
    *


@@ -107,36 +107,34 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    * - std::forward_list<_Node> containing the elements
    * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
    *
    * - std::forward_list<_Node> containing the elements
    * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
    *

-   * The first non-empty bucket with index _M_begin_bucket_index contains the
-   * first container node which is also the first bucket node whereas other
-   * non-empty buckets contain the node before the first bucket node. This is so
-   * to implement something like a std::forward_list::erase_after on container
-   * erase calls.
+   * The non-empty buckets contain the node before the first bucket node. This
+   * design allow to implement something like a std::forward_list::insert_after
+   * on container insertion and std::forward_list::erase_after on container
+   * erase calls. _M_before_begin is equivalent to
+   * std::foward_list::before_begin. Empty buckets are containing nullptr.
+   * Note that one of the non-empty bucket contains &_M_before_begin which is
+   * not a derefenrenceable node so the node pointers in buckets shall never be
+   * derefenrenced, only its next node can be.

    * 
    * 

-   * Access to the bucket last element require a check on the hash code to see
-   * if the node is still in the bucket. Such a design impose a quite efficient
-   * hash functor and is one of the reasons it is highly advise to set
+   * Walk through a bucket nodes require a check on the hash code to see if the
+   * node is still in the bucket. Such a design impose a quite efficient hash
+   * functor and is one of the reasons it is highly advise to set

    * __cache_hash_code to true.
    *
    * The container iterators are simply built from nodes. This way incrementing
    * __cache_hash_code to true.
    *
    * The container iterators are simply built from nodes. This way incrementing

-   * the iterator is perfectly efficient no matter how many empty buckets there
-   * are in the container.
+   * the iterator is perfectly efficient independent of how many empty buckets
+   * there are in the container.

    *
    * On insert we compute element hash code and thanks to it find the bucket
    *
    * On insert we compute element hash code and thanks to it find the bucket

-   * index. If the element is the first one in the bucket we must find the
-   * previous non-empty bucket where the previous node rely. To keep this loop
-   * minimal it is important that the number of bucket is not too high compared
-   * to the number of elements. So the hash policy must be carefully design so
-   * that it computes a bucket count large enough to respect the user defined
-   * load factor but also not too large to limit impact on the insert operation.
+   * index. If the element must be inserted on an empty bucket we add it at the
+   * beginning of the singly linked list and make the bucket point to
+   * _M_before_begin. The bucket that used to point to _M_before_begin, if any,
+   * is updated to point to its new before begin node.

    *
    * On erase, the simple iterator design impose to use the hash functor to get
    * the index of the bucket to update. For this reason, when __cache_hash_code
    * is set to false, there is a static assertion that the hash functor cannot
    * throw.
    *
    * On erase, the simple iterator design impose to use the hash functor to get
    * the index of the bucket to update. For this reason, when __cache_hash_code
    * is set to false, there is a static assertion that the hash functor cannot
    * throw.

-   *
-   * _M_begin_bucket_index is used to offer contant time access to the container
-   * begin iterator.

    */
 
   template<typename _Key, typename _Value, typename _Allocator,
    */
 
   template<typename _Key, typename _Value, typename _Allocator,


@@ -182,6 +180,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        using __if_hash_code_not_cached
          = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
 
        using __if_hash_code_not_cached
          = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
 

+      // When hash codes are not cached the hash functor shall not throw
+      // because it is used in methods (erase, swap...) that shall not throw.

       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");
       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");


@@ -246,19 +246,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
       typedef typename _Allocator::template rebind<_Node>::other
                                                        _Node_allocator_type;
       typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
       typedef typename _Allocator::template rebind<_Node>::other
                                                        _Node_allocator_type;

-      typedef _Node* _Bucket;
+      typedef __detail::_Hash_node_base _BaseNode;
+      typedef _BaseNode* _Bucket;

       typedef typename _Allocator::template rebind<_Bucket>::other
                                                        _Bucket_allocator_type;
 
       typedef typename _Allocator::template rebind<_Value>::other
                                                        _Value_allocator_type;
 
       typedef typename _Allocator::template rebind<_Bucket>::other
                                                        _Bucket_allocator_type;
 
       typedef typename _Allocator::template rebind<_Value>::other
                                                        _Value_allocator_type;
 

-      _Node_allocator_type   _M_node_allocator;
-      _Bucket*               _M_buckets;
-      size_type              _M_bucket_count;
-      size_type              _M_begin_bucket_index; // First non-empty bucket.
-      size_type              _M_element_count;
-      _RehashPolicy          _M_rehash_policy;
+      _Node_allocator_type     _M_node_allocator;
+      _Bucket*                 _M_buckets;
+      size_type                        _M_bucket_count;
+      _BaseNode                        _M_before_begin;
+      size_type                        _M_element_count;
+      _RehashPolicy            _M_rehash_policy;

 
       template<typename... _Args>
        _Node*
 
       template<typename... _Args>
        _Node*


@@ -277,15 +278,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       _M_deallocate_buckets(_Bucket*, size_type __n);
 
       void
       _M_deallocate_buckets(_Bucket*, size_type __n);
 

-      // Gets bucket begin dealing with the difference between first non-empty
-      // bucket containing the first container node and the other non-empty
-      // buckets containing the node before the one belonging to the bucket.
+      // Gets bucket begin, deals with the fact that non-empty buckets contain
+      // their before begin node.

       _Node*
       _M_bucket_begin(size_type __bkt) const;
 
       _Node*
       _M_bucket_begin(size_type __bkt) const;
 

-      // Gets the bucket last node if any

       _Node*
       _Node*

-      _M_bucket_end(size_type __bkt) const;
+      _M_begin() const
+      { return static_cast<_Node*>(_M_before_begin._M_nxt); }

 
     public:
       // Constructor, destructor, assignment, swap
 
     public:
       // Constructor, destructor, assignment, swap


@@ -330,11 +330,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // Basic container operations
       iterator
       begin() noexcept
       // Basic container operations
       iterator
       begin() noexcept

-      { return iterator(_M_buckets[_M_begin_bucket_index]); }
+      { return iterator(_M_begin()); }

 
       const_iterator
       begin() const noexcept
 
       const_iterator
       begin() const noexcept

-      { return const_iterator(_M_buckets[_M_begin_bucket_index]); }
+      { return const_iterator(_M_begin()); }

 
       iterator
       end() noexcept
 
       iterator
       end() noexcept


@@ -346,7 +346,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       const_iterator
       cbegin() const noexcept
 
       const_iterator
       cbegin() const noexcept

-      { return const_iterator(_M_buckets[_M_begin_bucket_index]); }
+      { return const_iterator(_M_begin()); }

 
       const_iterator
       cend() const noexcept
 
       const_iterator
       cend() const noexcept


@@ -454,6 +454,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       equal_range(const key_type& __k) const;
 
     private:
       equal_range(const key_type& __k) const;
 
     private:

+      // Bucket index computation helpers.

       size_type
       _M_bucket_index(_Node* __n) const
       { return _HCBase::_M_bucket_index(__n, _M_bucket_count); }
       size_type
       _M_bucket_index(_Node* __n) const
       { return _HCBase::_M_bucket_index(__n, _M_bucket_count); }


@@ -464,26 +465,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); }
 
       // Find and insert helper functions and types
       { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); }
 
       // Find and insert helper functions and types

+      // Find the node before the one matching the criteria.
+      _BaseNode*
+      _M_find_before_node(size_type, const key_type&,
+                         typename _Hashtable::_Hash_code_type) const;
+

       _Node*
       _Node*

-      _M_find_node(size_type, const key_type&,
-                  typename _Hashtable::_Hash_code_type) const;
+      _M_find_node(size_type __bkt, const key_type& __key,
+                  typename _Hashtable::_Hash_code_type __c) const
+      {
+       _BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c);
+       if (__before_n)
+         return static_cast<_Node*>(__before_n->_M_nxt);
+       return nullptr;
+      }

 
 

-      // Insert a node in an empty bucket
+      // Insert a node at the beginning of a bucket.

       void
       _M_insert_bucket_begin(size_type, _Node*);
 
       void
       _M_insert_bucket_begin(size_type, _Node*);
 

-      // Insert a node after an other one in a non-empty bucket
-      void
-      _M_insert_after(size_type, _Node*, _Node*);
-

       // Remove the bucket first node
       void
       _M_remove_bucket_begin(size_type __bkt, _Node* __next_n,
                             size_type __next_bkt);
 
       // Get the node before __n in the bucket __bkt
       // Remove the bucket first node
       void
       _M_remove_bucket_begin(size_type __bkt, _Node* __next_n,
                             size_type __next_bkt);
 
       // Get the node before __n in the bucket __bkt

-      _Node*
-      _M_get_previous_node(size_type __bkt, _Node* __n);
+      _BaseNode*
+      _M_get_previous_node(size_type __bkt, _BaseNode* __n);

 
       template<typename _Arg>
        iterator
 
       template<typename _Arg>
        iterator


@@ -645,7 +653,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       while (__n)
        {
          _Node* __tmp = __n;
       while (__n)
        {
          _Node* __tmp = __n;

-         __n = __n->_M_next;
+         __n = __n->_M_next();

          _M_deallocate_node(__tmp);
        }
     }
          _M_deallocate_node(__tmp);
        }
     }


@@ -663,10 +671,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       _Bucket_allocator_type __alloc(_M_node_allocator);
 
     {
       _Bucket_allocator_type __alloc(_M_node_allocator);
 

-      // We allocate one extra bucket to have _M_begin_bucket_index
-      // point to it as long as container is empty
-      _Bucket* __p = __alloc.allocate(__n + 1);
-      __builtin_memset(__p, 0, (__n + 1) * sizeof(_Bucket));
+      _Bucket* __p = __alloc.allocate(__n);
+      __builtin_memset(__p, 0, __n * sizeof(_Bucket));

       return __p;
     }
 
       return __p;
     }
 


@@ -680,7 +686,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _M_deallocate_buckets(_Bucket* __p, size_type __n)
     {
       _Bucket_allocator_type __alloc(_M_node_allocator);
     _M_deallocate_buckets(_Bucket* __p, size_type __n)
     {
       _Bucket_allocator_type __alloc(_M_node_allocator);

-      __alloc.deallocate(__p, __n + 1);
+      __alloc.deallocate(__p, __n);

     }
 
   template<typename _Key, typename _Value,
     }
 
   template<typename _Key, typename _Value,


@@ -694,29 +700,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     _M_bucket_begin(size_type __bkt) const
     {
               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     _M_bucket_begin(size_type __bkt) const
     {

-      if (__bkt == _M_begin_bucket_index)
-       return _M_buckets[__bkt];
-      _Node* __n = _M_buckets[__bkt];
-      return __n ? __n->_M_next : nullptr;
-    }
-
-  template<typename _Key, typename _Value,
-          typename _Allocator, typename _ExtractKey, typename _Equal,
-          typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
-          bool __chc, bool __cit, bool __uk>
-    typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
-                       _Equal, _H1, _H2, _Hash, _RehashPolicy,
-                       __chc, __cit, __uk>::_Node*
-    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
-              _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
-    _M_bucket_end(size_type __bkt) const
-    {
-      _Node* __n = _M_bucket_begin(__bkt);
-      if (__n)
-       for (;; __n = __n->_M_next)
-         if (!__n->_M_next || _M_bucket_index(__n->_M_next) != __bkt)
-           break;
-      return __n;
+      _BaseNode* __n = _M_buckets[__bkt];
+      return __n ? static_cast<_Node*>(__n->_M_nxt) : nullptr;

     }
 
   template<typename _Key, typename _Value,
     }
 
   template<typename _Key, typename _Value,


@@ -744,7 +729,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // on the first insertion so we need to reset its previous resize level.
       _M_rehash_policy._M_prev_resize = 0;
       _M_buckets = _M_allocate_buckets(_M_bucket_count);
       // on the first insertion so we need to reset its previous resize level.
       _M_rehash_policy._M_prev_resize = 0;
       _M_buckets = _M_allocate_buckets(_M_bucket_count);

-      _M_begin_bucket_index = _M_bucket_count;

     }
 
   template<typename _Key, typename _Value,
     }
 
   template<typename _Key, typename _Value,


@@ -779,7 +763,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        // level.
        _M_rehash_policy._M_prev_resize = 0;
        _M_buckets = _M_allocate_buckets(_M_bucket_count);
        // level.
        _M_rehash_policy._M_prev_resize = 0;
        _M_buckets = _M_allocate_buckets(_M_bucket_count);

-       _M_begin_bucket_index = _M_bucket_count;

        __try
          {
            for (; __f != __l; ++__f)
        __try
          {
            for (; __f != __l; ++__f)


@@ -806,48 +789,34 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
       _M_node_allocator(__ht._M_node_allocator),
       _M_bucket_count(__ht._M_bucket_count),
       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
       _M_node_allocator(__ht._M_node_allocator),
       _M_bucket_count(__ht._M_bucket_count),

-      _M_begin_bucket_index(__ht._M_begin_bucket_index),

       _M_element_count(__ht._M_element_count),
       _M_rehash_policy(__ht._M_rehash_policy)
     {
       _M_buckets = _M_allocate_buckets(_M_bucket_count);
       __try
        {
       _M_element_count(__ht._M_element_count),
       _M_rehash_policy(__ht._M_rehash_policy)
     {
       _M_buckets = _M_allocate_buckets(_M_bucket_count);
       __try
        {

-         const _Node* __ht_n = __ht._M_buckets[__ht._M_begin_bucket_index];
-         if (!__ht_n)
+         if (!__ht._M_before_begin._M_nxt)

            return;
 
            return;
 

-         // Note that the copy constructor do not rely on hash code usage.
-         // First deal with the special first node that is directly store in
-         // the first non-empty bucket
+         // First deal with the special first node pointed to by
+         // _M_before_begin.
+         const _Node* __ht_n = __ht._M_begin();

          _Node* __this_n = _M_allocate_node(__ht_n->_M_v);
          this->_M_copy_code(__this_n, __ht_n);
          _Node* __this_n = _M_allocate_node(__ht_n->_M_v);
          this->_M_copy_code(__this_n, __ht_n);

-         _M_buckets[_M_begin_bucket_index] = __this_n;
-         __ht_n = __ht_n->_M_next;
-         // Second deal with following non-empty buckets containing previous
-         // nodes node.
-         for (size_type __i = __ht._M_begin_bucket_index + 1;
-              __i != __ht._M_bucket_count; ++__i)
-           {
-             if (!__ht._M_buckets[__i])
-               continue;
+         _M_before_begin._M_nxt = __this_n;
+         _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;

 
 

-             for (; __ht_n != __ht._M_buckets[__i]->_M_next;
-                  __ht_n = __ht_n->_M_next)
-               {
-                 __this_n->_M_next = _M_allocate_node(__ht_n->_M_v);
-                 this->_M_copy_code(__this_n->_M_next, __ht_n);
-                 __this_n = __this_n->_M_next;
-               }
-
-             _M_buckets[__i] = __this_n;
-           }
-         // Last finalize copy of the nodes of the last non-empty bucket
-         for (; __ht_n; __ht_n = __ht_n->_M_next)
+         // Then deal with other nodes.
+         _BaseNode* __prev_n = __this_n;
+         for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())

            {
            {

-             __this_n->_M_next = _M_allocate_node(__ht_n->_M_v);
-             this->_M_copy_code(__this_n->_M_next, __ht_n);
-             __this_n = __this_n->_M_next;
+             __this_n = _M_allocate_node(__ht_n->_M_v);
+             __prev_n->_M_nxt = __this_n;
+             this->_M_copy_code(__this_n, __ht_n);
+             size_type __bkt = _M_bucket_index(__this_n);
+             if (!_M_buckets[__bkt])
+               _M_buckets[__bkt] = __prev_n;
+             __prev_n = __this_n;

            }
        }
       __catch(...)
            }
        }
       __catch(...)


@@ -872,14 +841,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_node_allocator(std::move(__ht._M_node_allocator)),
       _M_buckets(__ht._M_buckets),
       _M_bucket_count(__ht._M_bucket_count),
       _M_node_allocator(std::move(__ht._M_node_allocator)),
       _M_buckets(__ht._M_buckets),
       _M_bucket_count(__ht._M_bucket_count),

-      _M_begin_bucket_index(__ht._M_begin_bucket_index),
+      _M_before_begin(__ht._M_before_begin._M_nxt),

       _M_element_count(__ht._M_element_count),
       _M_rehash_policy(__ht._M_rehash_policy)
     {
       _M_element_count(__ht._M_element_count),
       _M_rehash_policy(__ht._M_rehash_policy)
     {

+      // Update, if necessary, bucket pointing to before begin that hasn't move.
+      if (_M_begin())
+       _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;

       __ht._M_rehash_policy = _RehashPolicy();
       __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
       __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);
       __ht._M_rehash_policy = _RehashPolicy();
       __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
       __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);

-      __ht._M_begin_bucket_index = __ht._M_bucket_count;
+      __ht._M_before_begin._M_nxt = nullptr;

       __ht._M_element_count = 0;
     }
 
       __ht._M_element_count = 0;
     }
 


@@ -917,8 +889,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       std::swap(_M_rehash_policy, __x._M_rehash_policy);
       std::swap(_M_buckets, __x._M_buckets);
       std::swap(_M_bucket_count, __x._M_bucket_count);
       std::swap(_M_rehash_policy, __x._M_rehash_policy);
       std::swap(_M_buckets, __x._M_buckets);
       std::swap(_M_bucket_count, __x._M_bucket_count);

-      std::swap(_M_begin_bucket_index, __x._M_begin_bucket_index);
+      std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);

       std::swap(_M_element_count, __x._M_element_count);
       std::swap(_M_element_count, __x._M_element_count);

+      // Fix buckets containing the _M_before_begin pointers that can't be
+      // swapped.
+      if (_M_begin())
+       _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+      if (__x._M_begin())
+       __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
+         = &(__x._M_before_begin);

     }
 
   template<typename _Key, typename _Value,
     }
 
   template<typename _Key, typename _Value,


@@ -988,7 +967,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        return 0;
 
       std::size_t __result = 0;
        return 0;
 
       std::size_t __result = 0;

-      for (;; __p = __p->_M_next)
+      for (;; __p = __p->_M_next())

        {
          if (this->_M_equals(__k, __code, __p))
            ++__result;
        {
          if (this->_M_equals(__k, __code, __p))
            ++__result;


@@ -997,7 +976,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
            // equivalent value after an equivalent one it means that we won't
            // find anymore an equivalent value.
            break;
            // equivalent value after an equivalent one it means that we won't
            // find anymore an equivalent value.
            break;

-         if (!__p->_M_next || _M_bucket_index(__p->_M_next) != __n)
+         if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)

            break;
        }
       return __result;
            break;
        }
       return __result;


@@ -1025,10 +1004,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (__p)
        {
 
       if (__p)
        {

-         _Node* __p1 = __p->_M_next;
+         _Node* __p1 = __p->_M_next();

          while (__p1 && _M_bucket_index(__p1) == __n
                 && this->_M_equals(__k, __code, __p1))
          while (__p1 && _M_bucket_index(__p1) == __n
                 && this->_M_equals(__k, __code, __p1))

-           __p1 = __p1->_M_next;
+           __p1 = __p1->_M_next();

 
          return std::make_pair(iterator(__p), iterator(__p1));
        }
 
          return std::make_pair(iterator(__p), iterator(__p1));
        }


@@ -1058,10 +1037,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (__p)
        {
 
       if (__p)
        {

-         _Node* __p1 = __p->_M_next;
+         _Node* __p1 = __p->_M_next();

          while (__p1 && _M_bucket_index(__p1) == __n
                 && this->_M_equals(__k, __code, __p1))
          while (__p1 && _M_bucket_index(__p1) == __n
                 && this->_M_equals(__k, __code, __p1))

-           __p1 = __p1->_M_next;
+           __p1 = __p1->_M_next();

 
          return std::make_pair(const_iterator(__p), const_iterator(__p1));
        }
 
          return std::make_pair(const_iterator(__p), const_iterator(__p1));
        }


@@ -1077,21 +1056,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
           bool __chc, bool __cit, bool __uk>
     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
                        _Equal, _H1, _H2, _Hash, _RehashPolicy,
           bool __chc, bool __cit, bool __uk>
     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
                        _Equal, _H1, _H2, _Hash, _RehashPolicy,

-                       __chc, __cit, __uk>::_Node*
+                       __chc, __cit, __uk>::_BaseNode*

     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

-    _M_find_node(size_type __n, const key_type& __k,
-               typename _Hashtable::_Hash_code_type __code) const
+    _M_find_before_node(size_type __n, const key_type& __k,
+                       typename _Hashtable::_Hash_code_type __code) const

     {
     {

-      _Node* __p = _M_bucket_begin(__n);
-      if (!__p)
+      _BaseNode* __prev_p = _M_buckets[__n];
+      if (!__prev_p)

        return nullptr;
        return nullptr;

-      for (;; __p = __p->_M_next)
+      _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt);
+      for (;; __p = __p->_M_next())

        {
          if (this->_M_equals(__k, __code, __p))
        {
          if (this->_M_equals(__k, __code, __p))

-           return __p;
-         if (!(__p->_M_next) || _M_bucket_index(__p->_M_next) != __n)
+           return __prev_p;
+         if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n)

            break;
            break;

+         __prev_p = __p;

        }
       return nullptr;
     }
        }
       return nullptr;
     }


@@ -1105,53 +1086,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     _M_insert_bucket_begin(size_type __bkt, _Node* __new_node)
     {
               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     _M_insert_bucket_begin(size_type __bkt, _Node* __new_node)
     {

-      _Node* __prev_n;
-      if (__bkt < _M_begin_bucket_index)
+      if (_M_buckets[__bkt])

        {
        {

-         if (_M_begin_bucket_index != _M_bucket_count)
-           {
-             __new_node->_M_next = _M_buckets[_M_begin_bucket_index];
-             _M_buckets[_M_begin_bucket_index] = __new_node;
-           }
-         __prev_n = __new_node;
-         _M_begin_bucket_index = __bkt;
+         // Bucket is not empty, we just need to insert the new node after the
+         // bucket before begin.
+         __new_node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
+         _M_buckets[__bkt]->_M_nxt = __new_node;

        }
       else
        {
        }
       else
        {

-         // We need to find previous non-empty bucket to link the new node.
-         // There are several ways to find this previous bucket:
-         // 1. Move backward until we find it (the current method)
-         // 2. Start from the begin bucket index and move forward until we
-         // cross __n position.
-         // 3. Move forward until we find a non-empty bucket that will
-         // contain the previous node.
-         size_type __prev_bkt;
-         for (__prev_bkt = __bkt; __prev_bkt-- != 0;)
-           if (_M_buckets[__prev_bkt])
-             break;
-         __prev_n = _M_bucket_end(__prev_bkt);
-         _M_insert_after(__prev_bkt, __prev_n, __new_node);
-       }
-      _M_buckets[__bkt] = __prev_n;
-    }
-
-  template<typename _Key, typename _Value,
-          typename _Allocator, typename _ExtractKey, typename _Equal,
-          typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
-          bool __chc, bool __cit, bool __uk>
-    void
-    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
-              _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
-    _M_insert_after(size_type __bkt, _Node* __prev_n, _Node* __new_n)
-    {
-      if (__prev_n->_M_next)
-       {
-         size_type __next_bkt = _M_bucket_index(__prev_n->_M_next);
-         if (__next_bkt != __bkt)
-           _M_buckets[__next_bkt] = __new_n;
+         // The bucket is empty, the new node is inserted at the beginning of
+         // the singly linked list and the bucket will contain _M_before_begin
+         // pointer.
+         __new_node->_M_nxt = _M_before_begin._M_nxt;
+         _M_before_begin._M_nxt = __new_node;
+         if (__new_node->_M_nxt)
+           // We must update former begin bucket that is pointing to
+           // _M_before_begin.
+           _M_buckets[_M_bucket_index(__new_node->_M_next())] = __new_node;
+         _M_buckets[__bkt] = &_M_before_begin;

        }
        }

-      __new_n->_M_next = __prev_n->_M_next;
-      __prev_n->_M_next = __new_n;

     }
 
   template<typename _Key, typename _Value,
     }
 
   template<typename _Key, typename _Value,


@@ -1166,22 +1120,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (!__next || __next_bkt != __bkt)
        {
          // Bucket is now empty
       if (!__next || __next_bkt != __bkt)
        {
          // Bucket is now empty

-         if (__next && __next_bkt != __bkt)
-           // Update next non-empty bucket before begin node
+         // First update next bucket if any
+         if (__next)

            _M_buckets[__next_bkt] = _M_buckets[__bkt];
            _M_buckets[__next_bkt] = _M_buckets[__bkt];

+         // Second update before begin node if necessary
+         if (&_M_before_begin == _M_buckets[__bkt])
+           _M_before_begin._M_nxt = __next;

          _M_buckets[__bkt] = nullptr;
          _M_buckets[__bkt] = nullptr;

-         if (__bkt == _M_begin_bucket_index)
-           // We need to update begin bucket index
-           if (__next)
-             {
-               _M_begin_bucket_index = __next_bkt;
-               _M_buckets[_M_begin_bucket_index] = __next;
-             }
-           else
-             _M_begin_bucket_index = _M_bucket_count;

        }
        }

-      else if (__bkt == _M_begin_bucket_index)
-       _M_buckets[__bkt] = __next;

     }
 
   template<typename _Key, typename _Value,
     }
 
   template<typename _Key, typename _Value,


@@ -1190,18 +1136,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
           bool __chc, bool __cit, bool __uk>
     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
                        _Equal, _H1, _H2, _Hash, _RehashPolicy,
           bool __chc, bool __cit, bool __uk>
     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
                        _Equal, _H1, _H2, _Hash, _RehashPolicy,

-                       __chc, __cit, __uk>::_Node*
+                       __chc, __cit, __uk>::_BaseNode*

     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

-    _M_get_previous_node(size_type __bkt, _Node* __n)
+    _M_get_previous_node(size_type __bkt, _BaseNode* __n)

     {
     {

-      _Node* __prev_n = nullptr;
-      if (__bkt != _M_begin_bucket_index || __n != _M_buckets[__bkt])
-       {
-         __prev_n = _M_buckets[__bkt];
-         while (__prev_n->_M_next != __n)
-           __prev_n = __prev_n->_M_next;
-       }
+      _BaseNode* __prev_n = _M_buckets[__bkt];
+      while (__prev_n->_M_nxt != __n)
+       __prev_n = __prev_n->_M_nxt;

       return __prev_n;
     }
 
       return __prev_n;
     }
 


@@ -1248,10 +1190,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
                __bkt = _M_bucket_index(__k, __code);
              }
 
                __bkt = _M_bucket_index(__k, __code);
              }
 

-           if (_M_buckets[__bkt])
-             _M_insert_after(__bkt, _M_buckets[__bkt], __new_node);
-           else 
-             _M_insert_bucket_begin(__bkt, __new_node);
+           _M_insert_bucket_begin(__bkt, __new_node);

            ++_M_element_count;
            return std::make_pair(iterator(__new_node), true);
          }
            ++_M_element_count;
            return std::make_pair(iterator(__new_node), true);
          }


@@ -1279,7 +1218,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
          = _M_rehash_policy._M_need_rehash(_M_bucket_count,
                                            _M_element_count, 1);
 
          = _M_rehash_policy._M_need_rehash(_M_bucket_count,
                                            _M_element_count, 1);
 

-       // First build the node to get its hash code
+       // First build the node to get its hash code.

        _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
        __try
          {
        _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
        __try
          {


@@ -1287,33 +1226,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
            typename _Hashtable::_Hash_code_type __code
              = this->_M_hash_code(__k);
            this->_M_store_code(__new_node, __code);
            typename _Hashtable::_Hash_code_type __code
              = this->_M_hash_code(__k);
            this->_M_store_code(__new_node, __code);

-           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);
-           
+           // Second,  do rehash if necessary.

            if (__do_rehash.first)
            if (__do_rehash.first)

-             {

                _M_rehash(__do_rehash.second, __saved_state);
                _M_rehash(__do_rehash.second, __saved_state);

-               __bkt = _M_bucket_index(__k, __code);
-               // __prev is still valid because rehash do not invalidate nodes
-             }

 
 

+           // Third, find the node before an equivalent one.
+           size_type __bkt = _M_bucket_index(__k, __code);
+           _BaseNode* __prev = _M_find_before_node(__bkt, __k, __code);
+           

            if (__prev)
            if (__prev)

-             // Insert after the previous equivalent node
-             _M_insert_after(__bkt, __prev, __new_node);
-           else if (_M_buckets[__bkt])
-             // Bucket is not empty and the inserted node has no equivalent in
-             // the hashtable. We must insert the new node at the beginning or
-             // end of the bucket to preserve equivalent elements relative
-             // positions.
-             if (__bkt != _M_begin_bucket_index)
-               // We insert the new node at the beginning
-               _M_insert_after(__bkt, _M_buckets[__bkt], __new_node);
-             else
-               // We insert the new node at the end
-               _M_insert_after(__bkt, _M_bucket_end(__bkt), __new_node);
+             {
+               // Insert after the node before the equivalent one.
+               __new_node->_M_nxt = __prev->_M_nxt;
+               __prev->_M_nxt = __new_node;
+             }

            else
            else

+             // The inserted node has no equivalent in the hashtable. We must
+             // insert the new node at the beginning of the bucket to preserve
+             // equivalent elements relative positions.

              _M_insert_bucket_begin(__bkt, __new_node);
            ++_M_element_count;
            return iterator(__new_node);
              _M_insert_bucket_begin(__bkt, __new_node);
            ++_M_element_count;
            return iterator(__new_node);


@@ -1360,10 +1291,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
            if (__do_rehash.first)
              _M_rehash(__do_rehash.second, __saved_state);
 
            if (__do_rehash.first)
              _M_rehash(__do_rehash.second, __saved_state);
 

-           if (_M_buckets[__n])
-             _M_insert_after(__n, _M_buckets[__n], __new_node);
-           else 
-             _M_insert_bucket_begin(__n, __new_node);
+           _M_insert_bucket_begin(__n, __new_node);

            ++_M_element_count;
            return iterator(__new_node);
          }
            ++_M_element_count;
            return iterator(__new_node);
          }


@@ -1421,38 +1349,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
        const key_type& __k = this->_M_extract()(__v);
        typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 
        const key_type& __k = this->_M_extract()(__v);
        typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);

-       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);

        _Node* __new_node = nullptr;
        __try
          {
        _Node* __new_node = nullptr;
        __try
          {

-           // Second allocate new node so that we don't rehash if it throws
+           // First allocate new node so that we don't rehash if it throws.

            __new_node = _M_allocate_node(std::forward<_Arg>(__v));
            this->_M_store_code(__new_node, __code);
            if (__do_rehash.first)
            __new_node = _M_allocate_node(std::forward<_Arg>(__v));
            this->_M_store_code(__new_node, __code);
            if (__do_rehash.first)

-             {

                _M_rehash(__do_rehash.second, __saved_state);
                _M_rehash(__do_rehash.second, __saved_state);

-               __n = _M_bucket_index(__k, __code);
-               // __prev is still valid because rehash do not invalidate nodes
-             }

 
 

+           // Second, find the node before an equivalent one.
+           size_type __n = _M_bucket_index(__k, __code);
+           _BaseNode* __prev = _M_find_before_node(__n, __k, __code);

            if (__prev)
            if (__prev)

-             // Insert after the previous equivalent node
-             _M_insert_after(__n, __prev, __new_node);
-           else if (_M_buckets[__n])
-             // Bucket is not empty and the inserted node has no equivalent in
-             // the hashtable. We must insert the new node at the beginning or
-             // end of the bucket to preserve equivalent elements relative
-             // positions.
-             if (__n != _M_begin_bucket_index)
-               // We insert the new node at the beginning
-               _M_insert_after(__n, _M_buckets[__n], __new_node);
-             else
-               // We insert the new node at the end
-               _M_insert_after(__n, _M_bucket_end(__n), __new_node);
+             {
+               // Insert after the node before the equivalent one.
+               __new_node->_M_nxt = __prev->_M_nxt;
+               __prev->_M_nxt = __new_node;
+             }

            else
            else

+             // The inserted node has no equivalent in the hashtable. We must
+             // insert the new node at the beginning of the bucket to preserve
+             // equivalent elements relative positions.

              _M_insert_bucket_begin(__n, __new_node);
            ++_M_element_count;
            return iterator(__new_node);
              _M_insert_bucket_begin(__n, __new_node);
            ++_M_element_count;
            return iterator(__new_node);


@@ -1504,22 +1423,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       std::size_t __bkt = _M_bucket_index(__n);
 
       // Look for previous node to unlink it from the erased one, this is why
       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
-      // this research fast.
-      _Node* __prev_n = _M_get_previous_node(__bkt, __n);
+      // we need buckets to contain the before begin to make this research fast.
+      _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);

       if (__n == _M_bucket_begin(__bkt))
       if (__n == _M_bucket_begin(__bkt))

-       _M_remove_bucket_begin(__bkt, __n->_M_next,
-          __n->_M_next ? _M_bucket_index(__n->_M_next) : 0);
-      else if (__n->_M_next)
+       _M_remove_bucket_begin(__bkt, __n->_M_next(),
+          __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
+      else if (__n->_M_nxt)

        {
        {

-         size_type __next_bkt = _M_bucket_index(__n->_M_next);
+         size_type __next_bkt = _M_bucket_index(__n->_M_next());

          if (__next_bkt != __bkt)
            _M_buckets[__next_bkt] = __prev_n;
        }
 
          if (__next_bkt != __bkt)
            _M_buckets[__next_bkt] = __prev_n;
        }
 

-      if (__prev_n)
-       __prev_n->_M_next = __n->_M_next;
-      iterator __result(__n->_M_next);
+      __prev_n->_M_nxt = __n->_M_nxt;
+      iterator __result(__n->_M_next());

       _M_deallocate_node(__n);
       --_M_element_count;
 
       _M_deallocate_node(__n);
       --_M_element_count;
 


@@ -1539,26 +1456,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
       std::size_t __bkt = _M_bucket_index(__k, __code);
     {
       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
       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];
-      if (!__n)
+      // Look for the node before the first matching node.
+      _BaseNode* __prev_n = _M_find_before_node(__bkt, __k, __code);
+      if (!__prev_n)

        return 0;
        return 0;

-      _Node* __prev_n = nullptr;
-      if (__bkt != _M_begin_bucket_index)
-       {
-         __prev_n = __n;
-         __n = __n->_M_next;
-       }
-      bool __is_bucket_begin = true;
-      for (;; __prev_n = __n, __n = __n->_M_next)
-       {
-         if (this->_M_equals(__k, __code, __n))
-           break;
-         if (!(__n->_M_next) || _M_bucket_index(__n->_M_next) != __bkt)
-           return 0;
-         __is_bucket_begin = false;
-       }
+      _Node* __n = static_cast<_Node*>(__prev_n->_M_nxt);
+      bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n;

 
       // We found a matching node, start deallocation loop from it
       std::size_t __next_bkt = __bkt;
 
       // We found a matching node, start deallocation loop from it
       std::size_t __next_bkt = __bkt;


@@ -1568,7 +1471,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       do
        {
          _Node* __p = __next_n;
       do
        {
          _Node* __p = __next_n;

-         __next_n = __p->_M_next;
+         __next_n = __p->_M_next();

          // _GLIBCXX_RESOLVE_LIB_DEFECTS
          // 526. Is it undefined if a function in the standard changes
          // in parameters?
          // _GLIBCXX_RESOLVE_LIB_DEFECTS
          // 526. Is it undefined if a function in the standard changes
          // in parameters?


@@ -1592,7 +1495,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       else if (__next_n && __next_bkt != __bkt)
        _M_buckets[__next_bkt] = __prev_n;
       if (__prev_n)
       else if (__next_n && __next_bkt != __bkt)
        _M_buckets[__next_bkt] = __prev_n;
       if (__prev_n)

-       __prev_n->_M_next = __next_n;
+       __prev_n->_M_nxt = __next_n;

       return __result;
     }
 
       return __result;
     }
 


@@ -1614,7 +1517,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       std::size_t __bkt = _M_bucket_index(__n);
 
 
       std::size_t __bkt = _M_bucket_index(__n);
 

-      _Node* __prev_n = _M_get_previous_node(__bkt, __n);
+      _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);

       bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
       std::size_t __n_bkt = __bkt;
       for (;;)
       bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
       std::size_t __n_bkt = __bkt;
       for (;;)


@@ -1622,7 +1525,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
          do
            {
              _Node* __tmp = __n;
          do
            {
              _Node* __tmp = __n;

-             __n = __n->_M_next;
+             __n = __n->_M_next();

              _M_deallocate_node(__tmp);
              --_M_element_count;
              if (!__n)
              _M_deallocate_node(__tmp);
              --_M_element_count;
              if (!__n)


@@ -1640,8 +1543,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (__n && __n_bkt != __bkt)
        _M_buckets[__n_bkt] = __prev_n;
 
       if (__n && __n_bkt != __bkt)
        _M_buckets[__n_bkt] = __prev_n;

-      if (__prev_n)
-       __prev_n->_M_next = __n;
+      __prev_n->_M_nxt = __n;

       return iterator(__n);
     }
 
       return iterator(__n);
     }
 


@@ -1654,10 +1556,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     clear() noexcept
     {
               _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     clear() noexcept
     {

-      _M_deallocate_nodes(_M_buckets[_M_begin_bucket_index]);
+      _M_deallocate_nodes(_M_begin());

       __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket));
       _M_element_count = 0;
       __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket));
       _M_element_count = 0;

-      _M_begin_bucket_index = _M_bucket_count;
+      _M_before_begin._M_nxt = nullptr;

     }
 
   template<typename _Key, typename _Value,
     }
 
   template<typename _Key, typename _Value,


@@ -1688,45 +1590,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __try
        {
          _Bucket* __new_buckets = _M_allocate_buckets(__n);
       __try
        {
          _Bucket* __new_buckets = _M_allocate_buckets(__n);

-         _Node* __p = _M_buckets[_M_begin_bucket_index];
-         // First loop to store each node in its new bucket
+         _Node* __p = _M_begin();
+         _M_before_begin._M_nxt = nullptr;
+         std::size_t __cur_bbegin_bkt;

          while (__p)
            {
          while (__p)
            {

-             _Node* __next = __p->_M_next;
+             _Node* __next = __p->_M_next();

              std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
              if (!__new_buckets[__new_index])
              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
-               // end node quickly.
-               if (__new_index < _M_bucket_count)
-                 _M_buckets[__new_index] = __p;
-             __p->_M_next = __new_buckets[__new_index];
-             __new_buckets[__new_index] = __p;
+               {
+                 __p->_M_nxt = _M_before_begin._M_nxt;
+                 _M_before_begin._M_nxt = __p;
+                 __new_buckets[__new_index] = &_M_before_begin;
+                 if (__p->_M_nxt)
+                   __new_buckets[__cur_bbegin_bkt] = __p;
+                 __cur_bbegin_bkt = __new_index;
+               }
+             else
+               {
+                 __p->_M_nxt = __new_buckets[__new_index]->_M_nxt;
+                 __new_buckets[__new_index]->_M_nxt = __p;
+               }

              __p = __next;
            }
              __p = __next;
            }

-         _M_begin_bucket_index = __n;
-         _Node* __prev_node = nullptr;
-         // Second loop to link all nodes together and to fix bucket values so
-         // that they contain the before begin node of the bucket.
-         for (size_type __i = 0; __i != __n; ++__i)
-           if (__new_buckets[__i])
-             {
-               if (__prev_node)
-                 {
-                   __prev_node->_M_next = __new_buckets[__i];
-                   __new_buckets[__i] = __prev_node;
-                 }
-               else
-                 _M_begin_bucket_index = __i;
-               if (__i < _M_bucket_count)
-                 __prev_node = _M_buckets[__i];
-               else
-                 {
-                   __prev_node = __new_buckets[__i];
-                   while (__prev_node->_M_next)
-                     __prev_node = __prev_node->_M_next;
-                 }
-             }

          _M_deallocate_buckets(_M_buckets, _M_bucket_count);
          _M_bucket_count = __n;
          _M_buckets = __new_buckets;
          _M_deallocate_buckets(_M_buckets, _M_bucket_count);
          _M_bucket_count = __n;
          _M_buckets = __new_buckets;

diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 993f630..a06f6e3 100644 (file)
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -73,32 +73,44 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // template parameter of class template _Hashtable controls whether
   // nodes also store a hash code. In some cases (e.g. strings) this
   // may be a performance win.
   // template parameter of class template _Hashtable controls whether
   // nodes also store a hash code. In some cases (e.g. strings) this
   // may be a performance win.

+  struct _Hash_node_base
+  {
+    _Hash_node_base* _M_nxt;
+
+    _Hash_node_base()
+      : _M_nxt() { }
+    _Hash_node_base(_Hash_node_base* __next)
+      : _M_nxt(__next) { }
+  };
+

   template<typename _Value, bool __cache_hash_code>
     struct _Hash_node;
 
   template<typename _Value>
   template<typename _Value, bool __cache_hash_code>
     struct _Hash_node;
 
   template<typename _Value>

-    struct _Hash_node<_Value, true>
+    struct _Hash_node<_Value, true> : _Hash_node_base

     {
       _Value       _M_v;
       std::size_t  _M_hash_code;
     {
       _Value       _M_v;
       std::size_t  _M_hash_code;

-      _Hash_node*  _M_next;

 
       template<typename... _Args>
        _Hash_node(_Args&&... __args)
 
       template<typename... _Args>
        _Hash_node(_Args&&... __args)

-       : _M_v(std::forward<_Args>(__args)...),
-         _M_hash_code(), _M_next() { }
+       : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { }
+
+      _Hash_node* _M_next() const
+      { return static_cast<_Hash_node*>(_M_nxt); }

     };
 
   template<typename _Value>
     };
 
   template<typename _Value>

-    struct _Hash_node<_Value, false>
+    struct _Hash_node<_Value, false> : _Hash_node_base

     {
       _Value       _M_v;
     {
       _Value       _M_v;

-      _Hash_node*  _M_next;

 
       template<typename... _Args>
        _Hash_node(_Args&&... __args)
 
       template<typename... _Args>
        _Hash_node(_Args&&... __args)

-       : _M_v(std::forward<_Args>(__args)...),
-         _M_next() { }
+       : _M_v(std::forward<_Args>(__args)...) { }
+
+      _Hash_node* _M_next() const
+      { return static_cast<_Hash_node*>(_M_nxt); }

     };
 
   // Node iterators, used to iterate through all the hashtable.
     };
 
   // Node iterators, used to iterate through all the hashtable.


@@ -110,7 +122,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       void
       _M_incr()
 
       void
       _M_incr()

-      { _M_cur = _M_cur->_M_next; }
+      { _M_cur = _M_cur->_M_next(); }

 
       _Hash_node<_Value, __cache>*  _M_cur;
     };
 
       _Hash_node<_Value, __cache>*  _M_cur;
     };


@@ -904,7 +916,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       _M_incr()
       {
       void
       _M_incr()
       {

-       _M_cur = _M_cur->_M_next;
+       _M_cur = _M_cur->_M_next();

        if (_M_cur)
          {
            std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count);
        if (_M_cur)
          {
            std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count);


@@ -936,7 +948,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       _M_incr()
       {
       void
       _M_incr()
       {

-       _M_cur = _M_cur->_M_next;
+       _M_cur = _M_cur->_M_next();

        if (_M_cur)
          {
            std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
        if (_M_cur)
          {
            std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);