OSDN Git Service

2012-04-09 Fran├žois Dumont <fdumont@gcc.gnu.org>
authorfdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4>
Mon, 9 Apr 2012 19:12:18 +0000 (19:12 +0000)
committerfdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4>
Mon, 9 Apr 2012 19:12:18 +0000 (19:12 +0000)
PR libstdc++/52476
* include/bits/hashtable.h (_Hashtable<>::_M_rehash_aux): Add.
(_Hashtable<>::_M_rehash): Use the latter.
* testsuite/23_containers/unordered_multimap/insert/52476.cc: New.
* testsuite/23_containers/unordered_multiset/insert/52476.cc: New.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/gcc-4_7-branch@186249 138bc75d-0d04-0410-961f-82ee72b054a4

libstdc++-v3/ChangeLog
libstdc++-v3/include/bits/hashtable.h
libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/52476.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/52476.cc [new file with mode: 0644]

index 218a6b6..2811abf 100644 (file)
@@ -1,3 +1,11 @@
+2012-04-09  Fran├žois Dumont  <fdumont@gcc.gnu.org>
+
+       PR libstdc++/52476
+       * include/bits/hashtable.h (_Hashtable<>::_M_rehash_aux): Add.
+       (_Hashtable<>::_M_rehash): Use the latter.
+       * testsuite/23_containers/unordered_multimap/insert/52476.cc: New.
+       * testsuite/23_containers/unordered_multiset/insert/52476.cc: New.
+
 2012-04-09  Terry Guo  <terry.guo@arm.com>
 
        Backport from mainline
index d4f2aed..41418a8 100644 (file)
@@ -596,6 +596,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // reserve, if present, comes from _Rehash_base.
 
     private:
+      // Helper rehash method used when keys are unique.
+      void _M_rehash_aux(size_type __n, std::true_type);
+
+      // Helper rehash method used when keys can be non-unique.
+      void _M_rehash_aux(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 +1598,145 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       __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_aux(__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;
+       }
+    }
+
+  // Rehash when there is no equivalent elements.
+  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_aux(size_type __n, std::true_type)
+    {
+      _Bucket* __new_buckets = _M_allocate_buckets(__n);
+      _Node* __p = _M_begin();
+      _M_before_begin._M_nxt = nullptr;
+      std::size_t __bbegin_bkt;
+      while (__p)
+       {
+         _Node* __next = __p->_M_next();
+         std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
+         if (!__new_buckets[__bkt])
            {
-             _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[__bkt] = &_M_before_begin;
+             if (__p->_M_nxt)
+               __new_buckets[__bbegin_bkt] = __p;
+             __bbegin_bkt = __bkt;
+           }
+         else
+           {
+             __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
+             __new_buckets[__bkt]->_M_nxt = __p;
+           }
+         __p = __next;
+       }
+      _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+      _M_bucket_count = __n;
+      _M_buckets = __new_buckets;
+    }
+
+  // Rehash when there can be equivalent elements, preserve their relative
+  // order.
+  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_aux(size_type __n, std::false_type)
+    {
+      _Bucket* __new_buckets = _M_allocate_buckets(__n);
+
+      _Node* __p = _M_begin();
+      _M_before_begin._M_nxt = nullptr;
+      std::size_t __bbegin_bkt;
+      std::size_t __prev_bkt;
+      _Node* __prev_p = nullptr;
+      bool __check_bucket = false;
+
+      while (__p)
+       {
+         bool __check_now = true;
+         _Node* __next = __p->_M_next();
+         std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
+
+         if (!__new_buckets[__bkt])
+           {
+             __p->_M_nxt = _M_before_begin._M_nxt;
+             _M_before_begin._M_nxt = __p;
+             __new_buckets[__bkt] = &_M_before_begin;
+             if (__p->_M_nxt)
+               __new_buckets[__bbegin_bkt] = __p;
+             __bbegin_bkt = __bkt;
+           }
+         else
+           {
+             if (__prev_p && __prev_bkt == __bkt)
                {
-                 __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;
+
+                 // Inserting after a node in a bucket require to check that we
+                 // haven't change the bucket last node, in this case next
+                 // bucket containing its before begin node must be updated. We
+                 // schedule a check as soon as we move out of the sequence of
+                 // equivalent nodes to limit the number of checks.
+                 __check_bucket = true;
+                 __check_now = false;
                }
              else
                {
-                 __p->_M_nxt = __new_buckets[__new_index]->_M_nxt;
-                 __new_buckets[__new_index]->_M_nxt = __p;
+                 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
+                 __new_buckets[__bkt]->_M_nxt = __p;
                }
-             __p = __next;
            }
-         _M_deallocate_buckets(_M_buckets, _M_bucket_count);
-         _M_bucket_count = __n;
-         _M_buckets = __new_buckets;
+         
+         if (__check_now && __check_bucket)
+           {
+             // Check if we shall update the next bucket because of insertions
+             // into __prev_bkt bucket.
+             if (__prev_p->_M_nxt)
+               {
+                 std::size_t __next_bkt
+                   = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
+                 if (__next_bkt != __prev_bkt)
+                   __new_buckets[__next_bkt] = __prev_p;
+               }
+             __check_bucket = false;
+           }
+         __prev_p = __p;
+         __prev_bkt = __bkt;
+         __p = __next;
        }
-      __catch(...)
+
+      if (__check_bucket && __prev_p->_M_nxt)
        {
-         // 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;
+         std::size_t __next_bkt
+           = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
+         if (__next_bkt != __prev_bkt)
+           __new_buckets[__next_bkt] = __prev_p;
        }
+
+      _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+      _M_bucket_count = __n;
+      _M_buckets = __new_buckets;
     }
 
 _GLIBCXX_END_NAMESPACE_VERSION
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/52476.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/52476.cc
new file mode 100644 (file)
index 0000000..f4f7839
--- /dev/null
@@ -0,0 +1,59 @@
+// { dg-options "-std=gnu++0x" }
+//
+// Copyright (C) 2012 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <unordered_map>
+#include <vector>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  using namespace std;
+  bool test __attribute__((unused)) = true;
+  
+  unordered_multimap<int, int> mmap;
+  vector<int> values;
+
+  size_t nb_bkts = mmap.bucket_count();
+  int i = 0;
+  for (;; ++i)
+    {
+      mmap.insert(make_pair(0, i));
+      if (mmap.bucket_count() != nb_bkts)
+       // Container got rehash
+       break;
+      values.clear();
+      transform(mmap.begin(), mmap.end(), back_inserter(values),
+               [](const pair<int, int>& p) { return p.second; });
+    }
+
+  vector<int> rehash_values;
+  transform(mmap.begin(), mmap.end(), back_inserter(rehash_values),
+           [](const pair<int, int>& p) { return p.second; });
+  // Remove the value that result in a rehash
+  rehash_values.erase(remove(rehash_values.begin(), rehash_values.end(), i));
+
+  VERIFY( rehash_values == values );
+}
+  
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/52476.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/52476.cc
new file mode 100644 (file)
index 0000000..45eeb71
--- /dev/null
@@ -0,0 +1,77 @@
+// { dg-options "-std=gnu++0x" }
+//
+// Copyright (C) 2012 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <unordered_set>
+#include <vector>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+namespace
+{
+  struct pair_hash
+  {
+    std::size_t
+    operator()(const std::pair<int, int>& p) const noexcept
+    { return std::hash<int>()(p.first); }
+  };
+
+  struct pair_equal_to
+  {
+    bool
+    operator()(const std::pair<int, int>& x,
+              const std::pair<int, int>& y) const noexcept
+    { return x.first == y.first; }
+  };
+}
+
+void test01()
+{
+  using namespace std;
+  bool test __attribute__((unused)) = true;
+  
+  unordered_multiset<pair<int, int>, pair_hash, pair_equal_to> mset;
+  vector<int> values;
+
+  size_t nb_bkts = mset.bucket_count();
+  int i = 0;
+  for (;; ++i)
+    {
+      mset.insert(make_pair(0, i));
+      if (mset.bucket_count() != nb_bkts)
+       // Container got rehash
+       break;
+      values.clear();
+      transform(mset.begin(), mset.end(), back_inserter(values),
+               [](const pair<int, int>& p) { return p.second; });
+    }
+
+  vector<int> rehash_values;
+  transform(mset.begin(), mset.end(), back_inserter(rehash_values),
+           [](const pair<int, int>& p) { return p.second; });
+  // Remove the value that result in a rehash
+  rehash_values.erase(remove(rehash_values.begin(), rehash_values.end(), i));
+
+  VERIFY( rehash_values == values );
+}
+  
+int main()
+{
+  test01();
+  return 0;
+}