OSDN Git Service

2012-05-01 Fran├žois Dumont <fdumont@gcc.gnu.org>
authorfdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4>
Tue, 1 May 2012 19:38:28 +0000 (19:38 +0000)
committerfdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4>
Tue, 1 May 2012 19:38:28 +0000 (19:38 +0000)
PR libstdc++/53115
* include/bits/hashtable.h
(_Hashtable<>::_M_rehash_aux(size_type, false_type)): Fix buckets
after insertion of several equivalent elements.
* testsuite/23_containers/unordered_multiset/insert/53115.cc: New.
* testsuite/23_containers/unordered_multimap/insert/53115.cc: New.

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

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

index c2d9ed9..0bd2e4b 100644 (file)
@@ -1,3 +1,12 @@
+2012-05-01  Fran├žois Dumont  <fdumont@gcc.gnu.org>
+
+       PR libstdc++/53115
+       * include/bits/hashtable.h
+       (_Hashtable<>::_M_rehash_aux(size_type, false_type)): Fix buckets
+       after insertion of several equivalent elements.
+       * testsuite/23_containers/unordered_multiset/insert/53115.cc: New.
+       * testsuite/23_containers/unordered_multimap/insert/53115.cc: New.
+
 2012-04-30  Andreas Tobler  <andreast@fgznet.ch>
 
        Backport from mainline
index 41418a8..2dfed94 100644 (file)
@@ -1,6 +1,7 @@
 // hashtable.h header -*- C++ -*-
 
-// Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008, 2009, 2010, 2011, 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
@@ -1670,36 +1671,47 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       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])
+         if (__prev_p && __prev_bkt == __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;
+             // 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;
            }
          else
            {
-             if (__prev_p && __prev_bkt == __bkt)
+             if (__check_bucket)
                {
-                 // 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;
+                 // 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;
+               }
+             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
                {
@@ -1707,20 +1719,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
                  __new_buckets[__bkt]->_M_nxt = __p;
                }
            }
-         
-         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;
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/53115.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/53115.cc
new file mode 100644 (file)
index 0000000..4eb5d42
--- /dev/null
@@ -0,0 +1,101 @@
+// { dg-options "-std=gnu++11" }
+//
+// 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 <testsuite_hooks.h>
+
+namespace
+{
+  std::size_t
+  get_nb_bucket_elems(const std::unordered_multimap<int, int>& us)
+  {
+    std::size_t nb = 0;
+    for (std::size_t b = 0; b != us.bucket_count(); ++b)
+      nb += us.bucket_size(b);
+    return nb;
+  }
+}
+
+void test01()
+{
+  using namespace std;
+  bool test __attribute__((unused)) = true;
+
+  std::unordered_multimap<int, int> umm;
+  umm.insert(make_pair(10, 1));
+  VERIFY( umm.size() == 1 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(10, 2)); 
+  VERIFY( umm.size() == 2 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(10, 3));
+  VERIFY( umm.size() == 3 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(10, 4));
+  VERIFY( umm.size() == 4 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(10, 5));
+  VERIFY( umm.size() == 5 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(24, 6));
+  VERIFY( umm.size() == 6 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(25, 7));
+  VERIFY( umm.size() == 7 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(2, 8));
+  VERIFY( umm.size() == 8 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(2, 9));
+  VERIFY( umm.size() == 9 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(1, 10));
+  VERIFY( umm.size() == 10 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+
+  umm.insert(make_pair(10, 11));
+  VERIFY( umm.size() == 11 );
+  VERIFY( std::distance(umm.begin(), umm.end()) == umm.size() );
+  VERIFY( get_nb_bucket_elems(umm) == umm.size() );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/53115.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/53115.cc
new file mode 100644 (file)
index 0000000..a23eacb
--- /dev/null
@@ -0,0 +1,101 @@
+// { dg-options "-std=gnu++11" }
+//
+// 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 <testsuite_hooks.h>
+
+namespace
+{
+  std::size_t
+  get_nb_bucket_elems(const std::unordered_multiset<int>& us)
+  {
+    std::size_t nb = 0;
+    for (std::size_t b = 0; b != us.bucket_count(); ++b)
+      nb += us.bucket_size(b);
+    return nb;
+  }
+}
+
+void test01()
+{
+  using namespace std;
+  bool test __attribute__((unused)) = true;
+
+  std::unordered_multiset<int> mms;
+  mms.insert(10);
+  VERIFY( mms.size() == 1 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(10); 
+  VERIFY( mms.size() == 2 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(10);
+  VERIFY( mms.size() == 3 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(10);
+  VERIFY( mms.size() == 4 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(10);
+  VERIFY( mms.size() == 5 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(24);
+  VERIFY( mms.size() == 6 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(25);
+  VERIFY( mms.size() == 7 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(2);
+  VERIFY( mms.size() == 8 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(2);
+  VERIFY( mms.size() == 9 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(1);
+  VERIFY( mms.size() == 10 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+
+  mms.insert(10);
+  VERIFY( mms.size() == 11 );
+  VERIFY( std::distance(mms.begin(), mms.end()) == mms.size() );
+  VERIFY( get_nb_bucket_elems(mms) == mms.size() );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}