diff options
Diffstat (limited to 'libstdc++-v3')
6 files changed, 223 insertions, 9 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 7c78a82af6b..a56f1e77f2f 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,17 @@ +2012-07-25 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 to be 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 Chip Salzenberg <chip@pobox.com> Jonathan Wakely <jwakely.gcc@gmail.com> diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index f5bc3583f22..2faf0b3bd88 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -803,11 +803,11 @@ _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 @@ -1609,10 +1609,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION rehash(size_type __n) { const __rehash_state& __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 index 00000000000..1c6d1bc4a84 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/reserve.cc @@ -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 index 00000000000..44a59189aed --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/reserve.cc @@ -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 index 00000000000..6106b3336ff --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/reserve.cc @@ -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 index 00000000000..aba6f771d81 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/reserve.cc @@ -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; +} |