From 86b46154256e7390a98355b904b90362eaba8c5e Mon Sep 17 00:00:00 2001 From: fdumont Date: Fri, 16 Mar 2012 21:03:15 +0000 Subject: [PATCH] =?utf8?q?2012-03-15=20=20Fran=C3=A7ois=20Dumont=20=20?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 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/trunk@185476 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 8 ++ libstdc++-v3/include/bits/hashtable.h | 160 +++++++++++++++++---- .../unordered_multimap/insert/52476.cc | 59 ++++++++ .../unordered_multiset/insert/52476.cc | 77 ++++++++++ 4 files changed, 279 insertions(+), 25 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/52476.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/52476.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 3da865f44d9..c48b1fa3091 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,11 @@ +2012-03-16 François Dumont + + 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-03-14 Rainer Orth * config/os/solaris/solaris2.8: Rename to ... diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index d4f2aedfccd..41418a8a509 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -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()); + } + __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 + 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 + 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 index 00000000000..f4f78398878 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/52476.cc @@ -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 +// . + +#include +#include +#include +#include + +void test01() +{ + using namespace std; + bool test __attribute__((unused)) = true; + + unordered_multimap mmap; + vector 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& p) { return p.second; }); + } + + vector rehash_values; + transform(mmap.begin(), mmap.end(), back_inserter(rehash_values), + [](const pair& 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 index 00000000000..45eeb71f55b --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/52476.cc @@ -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 +// . + +#include +#include +#include +#include + +namespace +{ + struct pair_hash + { + std::size_t + operator()(const std::pair& p) const noexcept + { return std::hash()(p.first); } + }; + + struct pair_equal_to + { + bool + operator()(const std::pair& x, + const std::pair& y) const noexcept + { return x.first == y.first; } + }; +} + +void test01() +{ + using namespace std; + bool test __attribute__((unused)) = true; + + unordered_multiset, pair_hash, pair_equal_to> mset; + vector 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& p) { return p.second; }); + } + + vector rehash_values; + transform(mset.begin(), mset.end(), back_inserter(rehash_values), + [](const pair& 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; +} -- 2.11.4.GIT