This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [v3] fix libstdc++/52446

Hi,

Here a patch proposition to fix PR 52446.

I have introduce 2 version of the _M_rehash method. One used when keys are unique which is very close to the existing one. The second that take care of keeping equivalent keys relative order on rehash. The second one might seem complicated but I wanted to avoid to recompute a bucket index each time we find an equivalent element. If the hash code is cached it is ok but if it is not I prefer to limit the number of time it is recalculated.

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

    PR libstdc++/52446
    * include/bits/hashtable.h (_Hashtable<>::_M_rehash): Split into 2
    methods, the first, copy of the existing one, is used when keys
    are unique, the second purpose is to keep equivalent keys relative
    orders.
The "purpose of the second", maybe? Can we use a new name for the new functions, instead of overloading? A descriptive name or suffix would add clarity to the code.

* testsuite/23_containers/unordered_multimap/insert/52446.cc: New.

Tested under linux x86_64.

If ok tell me if I must also apply it to 4.7 branch.
We are going to fix this in mainline and, then, if everything goes well, in 4.7.1.

Minor nits:

François


52446.patch


Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 185352)
+++ include/bits/hashtable.h	(working copy)
@@ -596,6 +596,11 @@
        // reserve, if present, comes from _Rehash_base.

      private:
+      // Rehash method when keys are unique
+      void _M_rehash(size_type __n, std::true_type);
A blank line here. 
+      // Rehash method when there might be equivalent keys.
+      void _M_rehash(size_type __n, std::false_type);
+
        // Unconditionally change size of bucket array to n, restore hash policy
        // state to __state on exception.
        void _M_rehash(size_type __n, const _RehashPolicyState&  __state);
@@ -1592,41 +1597,141 @@
      {
        __try
  	{
-	  _Bucket* __new_buckets = _M_allocate_buckets(__n);
-	  _Node* __p = _M_begin();
-	  _M_before_begin._M_nxt = nullptr;
-	  std::size_t __cur_bbegin_bkt;
-	  while (__p)
+	  _M_rehash(__n, integral_constant<bool, __uk>());
+	}
+      __catch(...)
+	{
+	  // A failure here means that buckets allocation failed.  We only
+	  // have to restore hash policy previous state.
+	  _M_rehash_policy._M_reset(__state);
+	  __throw_exception_again;
+	}
+    }
+
+  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_rehash(size_type __n, std::true_type)
+    {
+      // This version of rehash do not have to care about equivalent elements
+      // relative order.
+      _Bucket* __new_buckets = _M_allocate_buckets(__n);
+      _Node* __p = _M_begin();
+      _M_before_begin._M_nxt = nullptr;
+      std::size_t __cur_bbegin_bkt;
+      while (__p)
+	{
+	  _Node* __next = __p->_M_next();
+	  std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
+	  if (!__new_buckets[__new_index])
  	    {
-	      _Node* __next = __p->_M_next();
-	      std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
-	      if (!__new_buckets[__new_index])
+	      __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;
+	}
+      _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+      _M_bucket_count = __n;
+      _M_buckets = __new_buckets;
+    }
+
+  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_rehash(size_type __n, std::false_type)
+    {
+      // This version of rehash must guaranty that equivalent elements relative
+      // order is preserve.
+      _Bucket* __new_buckets = _M_allocate_buckets(__n);
+      _Node* __p = _M_begin();
+      _M_before_begin._M_nxt = nullptr;
+      std::size_t __cur_bbegin_bkt;
+      std::size_t __prev_index;
+      _Node* __prev_p = nullptr;
+      bool __check_next_bucket = false;
+      while (__p)
+	{
+	  bool __check_now = true;
+	  _Node* __next = __p->_M_next();
+	  std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
+	  if (!__new_buckets[__new_index])
+	    {
+	      __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
+	    {
+	      if (__prev_p&&  __prev_index == __new_index)
  		{
-		  __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;
+		  // Previous insert was already in this bucket, we insert after
+		  // the previously inserted one to preserve equivalent elements
+		  // relative order.
+		  __p->_M_nxt = __prev_p->_M_nxt;
+		  __prev_p->_M_nxt = __p;
And here. As a general style, I would say always when the comment itself is preceded by code != open curly bracket. 
+		  // Request a check as soon as we move out of the sequence of
+		  // equivalent nodes.
+		  __check_next_bucket = true;
+		  __check_now = false;
In terms of testcases, I would also add something more straightforward, close to what we have in the PR, and duplicated for map and set. But I'm not going to insist ;)

Thanks!
Paolo.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]