OSDN Git Service

2012-07-26 Fran├žois Dumont <fdumont@gcc.gnu.org>
authorfdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4>
Thu, 26 Jul 2012 12:31:50 +0000 (12:31 +0000)
committerfdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4>
Thu, 26 Jul 2012 12:31:50 +0000 (12:31 +0000)
PR libstdc++/54075
* include/bits/hashtable.h
(_Hashtable<>::_Hashtable(_InputIterator, _InputIterator,
size_type, ...): Remove std::max usage to guarantee that hashtable
state is consistent with hash policy state.
(_Hashtable<>::rehash): Likewise. Set _M_prev_resize to 0 to avoid
the hashtable shrinking on next insertion.
* testsuite/23_containers/unordered_set/modifiers/reserve.cc: New.
* testsuite/23_containers/unordered_multiset/modifiers/reserve.cc: New.
* testsuite/23_containers/unordered_map/modifiers/reserve.cc: New.
* testsuite/23_containers/unordered_multimap/modifiers/reserve.cc: New.

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

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

index 514c403..53d1489 100644 (file)
@@ -1,3 +1,17 @@
+2012-07-26  Fran├žois Dumont  <fdumont@gcc.gnu.org>
+
+       PR libstdc++/54075
+       * include/bits/hashtable.h
+       (_Hashtable<>::_Hashtable(_InputIterator, _InputIterator,
+       size_type, ...): Remove std::max usage to guarantee that hashtable
+       state is consistent with hash policy state.
+       (_Hashtable<>::rehash): Likewise. Set _M_prev_resize to 0 to avoid
+       the hashtable shrinking on next insertion.
+       * testsuite/23_containers/unordered_set/modifiers/reserve.cc: New.
+       * testsuite/23_containers/unordered_multiset/modifiers/reserve.cc: New.
+       * testsuite/23_containers/unordered_map/modifiers/reserve.cc: New.
+       * testsuite/23_containers/unordered_multimap/modifiers/reserve.cc: New.
+
 2012-07-20  Paolo Carlini  <paolo.carlini@oracle.com>
 
        * testsuite/30_threads/thread/adl.cc: Add missing dg-requires.
index af645a6..929f0bb 100644 (file)
@@ -760,11 +760,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        _M_element_count(0),
        _M_rehash_policy()
       {
-       _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
-                                  _M_rehash_policy.
-                                  _M_bkt_for_elements(__detail::
-                                                      __distance_fw(__f,
-                                                                    __l)));
+       _M_bucket_count =
+         _M_rehash_policy._M_bkt_for_elements(__detail::__distance_fw(__f,
+                                                                      __l));
+       if (_M_bucket_count <= __bucket_hint)
+         _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
+
         // We don't want the rehash policy to ask for the hashtable to shrink
         // on the first insertion so we need to reset its previous resize
        // level.
@@ -1582,10 +1583,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     rehash(size_type __n)
     {
       const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
-      _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
-                        _M_rehash_policy._M_bkt_for_elements(_M_element_count
-                                                             + 1)),
-               __saved_state);
+      std::size_t __buckets
+       = _M_rehash_policy._M_bkt_for_elements(_M_element_count + 1);
+      if (__buckets <= __n)
+       __buckets = _M_rehash_policy._M_next_bkt(__n);
+
+      if (__buckets != _M_bucket_count)
+       {
+         _M_rehash(__buckets, __saved_state);
+         
+         // We don't want the rehash policy to ask for the hashtable to shrink
+         // on the next insertion so we need to reset its previous resize
+         // level.
+         _M_rehash_policy._M_prev_resize = 0;
+       }
     }
 
   template<typename _Key, typename _Value,
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/reserve.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/reserve.cc
new file mode 100644 (file)
index 0000000..1c6d1bc
--- /dev/null
@@ -0,0 +1,47 @@
+// { 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 <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  const int N = 1000;
+
+  typedef std::unordered_map<int, int> Map;
+  Map m;
+  m.reserve(N);
+
+  std::size_t bkts = m.bucket_count();
+  for (int i = 0; i != N; ++i)
+    {
+      m.insert(std::make_pair(i, i));
+      // As long as we insert less than the reserved number of elements we
+      // shouldn't experiment any rehash.
+      VERIFY( m.bucket_count() == bkts );
+    }
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/reserve.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/reserve.cc
new file mode 100644 (file)
index 0000000..44a5918
--- /dev/null
@@ -0,0 +1,48 @@
+// { 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 <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  const int N = 1000;
+
+  typedef std::unordered_multimap<int, int> MMap;
+  MMap m;
+  m.reserve(N * 2);
+
+  std::size_t bkts = m.bucket_count();
+  for (int i = 0; i != N; ++i)
+    {
+      m.insert(std::make_pair(i, i));
+      m.insert(std::make_pair(i, i));
+      // As long as we insert less than the reserved number of elements we
+      // shouldn't experiment any rehash.
+      VERIFY( m.bucket_count() == bkts );
+    }
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/reserve.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/reserve.cc
new file mode 100644 (file)
index 0000000..6106b33
--- /dev/null
@@ -0,0 +1,48 @@
+// { 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 <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  const int N = 1000;
+
+  typedef std::unordered_multiset<int> MSet;
+  MSet s;
+  s.reserve(N * 2);
+
+  std::size_t bkts = s.bucket_count();
+  for (int i = 0; i != N; ++i)
+    {
+      s.insert(i);
+      s.insert(i);
+      // As long as we insert less than the reserved number of elements we
+      // shouldn't experiment any rehash.
+      VERIFY( s.bucket_count() == bkts );
+    }
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/reserve.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/reserve.cc
new file mode 100644 (file)
index 0000000..aba6f77
--- /dev/null
@@ -0,0 +1,47 @@
+// { 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 <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  const int N = 1000;
+
+  typedef std::unordered_set<int> Set;
+  Set s;
+  s.reserve(N);
+
+  std::size_t bkts = s.bucket_count();
+  for (int i = 0; i != N; ++i)
+    {
+      s.insert(i);
+      // As long as we insert less than the reserved number of elements we
+      // shouldn't experiment any rehash.
+      VERIFY( s.bucket_count() == bkts );
+    }
+}
+
+int main()
+{
+  test01();
+  return 0;
+}