From be1088fa6a41636642119ca4d3e231d112daf578 Mon Sep 17 00:00:00 2001 From: Matthew Levine Date: Mon, 2 Apr 2007 10:15:50 +0000 Subject: [PATCH] re PR libstdc++/31370 (resizing bugs in std::vector) 2007-04-02 Matthew Levine Paolo Carlini PR libstdc++/31370 * include/bits/stl_bvector.h (vector::max_size): Fix. (vector::_M_check_len): Add. * include/bits/vector.tcc (_M_fill_insert(iterator, size_type, bool), _M_insert_range(iterator, _ForwardIterator, _ForwardIterator, std::forward_iterator_tag), _M_insert_aux(iterator, bool)): Use it. * testsuite/23_containers/vector/bool/modifiers/insert/31370.cc: New. * testsuite/23_containers/vector/bool/capacity/29134.cc: Adjust. * include/bits/stl_vector.h (vector<>::_M_check_len): Add. * include/bits/vector.tcc (_M_insert_aux(iterator, const _Tp&), _M_fill_insert(iterator, size_type, const value_type&), _M_range_insert(iterator, _ForwardIterator, _ForwardIterator, std::forward_iterator_tag)): Use it. Co-Authored-By: Paolo Carlini From-SVN: r123424 --- libstdc++-v3/ChangeLog | 18 ++ libstdc++-v3/include/bits/stl_bvector.h | 16 +- libstdc++-v3/include/bits/stl_vector.h | 11 ++ libstdc++-v3/include/bits/vector.tcc | 45 ++--- .../23_containers/vector/bool/capacity/29134.cc | 8 +- .../vector/bool/modifiers/insert/31370.cc | 192 +++++++++++++++++++++ 6 files changed, 253 insertions(+), 37 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/31370.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 2007552..c59cfcd 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,21 @@ +2007-04-02 Matthew Levine + Paolo Carlini + + PR libstdc++/31370 + * include/bits/stl_bvector.h (vector::max_size): Fix. + (vector::_M_check_len): Add. + * include/bits/vector.tcc (_M_fill_insert(iterator, size_type, bool), + _M_insert_range(iterator, _ForwardIterator, _ForwardIterator, + std::forward_iterator_tag), _M_insert_aux(iterator, bool)): Use it. + * testsuite/23_containers/vector/bool/modifiers/insert/31370.cc: New. + * testsuite/23_containers/vector/bool/capacity/29134.cc: Adjust. + + * include/bits/stl_vector.h (vector<>::_M_check_len): Add. + * include/bits/vector.tcc (_M_insert_aux(iterator, const _Tp&), + _M_fill_insert(iterator, size_type, const value_type&), + _M_range_insert(iterator, _ForwardIterator, _ForwardIterator, + std::forward_iterator_tag)): Use it. + 2007-04-02 Paolo Carlini PR libstdc++/31401 (vstring bits) diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index 6f24154..d9863e0 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -582,9 +582,11 @@ template size_type max_size() const { + const size_type __isize = + std::numeric_limits::max() - int(_S_word_bit) + 1; const size_type __asize = _M_get_Bit_allocator().max_size(); - return (__asize <= size_type(-1) / int(_S_word_bit) ? - __asize * int(_S_word_bit) : size_type(-1)); + return (__asize <= __isize / int(_S_word_bit) + ? __asize * int(_S_word_bit) : __isize); } size_type @@ -922,6 +924,16 @@ template void _M_insert_aux(iterator __position, bool __x); + size_type + _M_check_len(size_type __n, const char* __s) const + { + if (max_size() - size() < __n) + __throw_length_error(__N(__s)); + + const size_type __len = size() + std::max(size(), __n); + return (__len < size() || __len > max_size()) ? max_size() : __len; + } + void _M_erase_at_end(iterator __pos) { this->_M_impl._M_finish = __pos; } diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h index a81c597..f2c4b4b 100644 --- a/libstdc++-v3/include/bits/stl_vector.h +++ b/libstdc++-v3/include/bits/stl_vector.h @@ -911,6 +911,17 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) void _M_insert_aux(iterator __position, const value_type& __x); + // Called by the latter. + size_type + _M_check_len(size_type __n, const char* __s) const + { + if (max_size() - size() < __n) + __throw_length_error(__N(__s)); + + const size_type __len = size() + std::max(size(), __n); + return (__len < size() || __len > max_size()) ? max_size() : __len; + } + // Internal erase functions follow. // Called by erase(q1,q2), clear(), resize(), _M_fill_assign, diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc index 9b416be..09266a2 100644 --- a/libstdc++-v3/include/bits/vector.tcc +++ b/libstdc++-v3/include/bits/vector.tcc @@ -258,17 +258,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) } else { - const size_type __old_size = size(); - if (__old_size == this->max_size()) - __throw_length_error(__N("vector::_M_insert_aux")); - - // When sizeof(value_type) == 1 and __old_size > size_type(-1)/2 - // __len overflows: if we don't notice and _M_allocate doesn't - // throw we crash badly later. - size_type __len = __old_size != 0 ? 2 * __old_size : 1; - if (__len < __old_size) - __len = this->max_size(); - + const size_type __len = + _M_check_len(size_type(1), "vector::_M_insert_aux"); pointer __new_start(this->_M_allocate(__len)); pointer __new_finish(__new_start); try @@ -343,15 +334,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) } else { - const size_type __old_size = size(); - if (this->max_size() - __old_size < __n) - __throw_length_error(__N("vector::_M_fill_insert")); - - // See _M_insert_aux above. - size_type __len = __old_size + std::max(__old_size, __n); - if (__len < __old_size) - __len = this->max_size(); - + const size_type __len = + _M_check_len(__n, "vector::_M_fill_insert"); pointer __new_start(this->_M_allocate(__len)); pointer __new_finish(__new_start); try @@ -447,15 +431,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) } else { - const size_type __old_size = size(); - if (this->max_size() - __old_size < __n) - __throw_length_error(__N("vector::_M_range_insert")); - - // See _M_insert_aux above. - size_type __len = __old_size + std::max(__old_size, __n); - if (__len < __old_size) - __len = this->max_size(); - + const size_type __len = + _M_check_len(__n, "vector::_M_range_insert"); pointer __new_start(this->_M_allocate(__len)); pointer __new_finish(__new_start); try @@ -512,7 +489,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) } else { - const size_type __len = size() + std::max(size(), __n); + const size_type __len = + _M_check_len(__n, "vector::_M_fill_insert"); _Bit_type * __q = this->_M_allocate(__len); iterator __i = _M_copy_aligned(begin(), __position, iterator(__q, 0)); @@ -547,7 +525,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) } else { - const size_type __len = size() + std::max(size(), __n); + const size_type __len = + _M_check_len(__n, "vector::_M_insert_range"); _Bit_type * __q = this->_M_allocate(__len); iterator __i = _M_copy_aligned(begin(), __position, iterator(__q, 0)); @@ -577,8 +556,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) } else { - const size_type __len = size() ? 2 * size() - : static_cast(_S_word_bit); + const size_type __len = + _M_check_len(size_type(1), "vector::_M_insert_aux"); _Bit_type * __q = this->_M_allocate(__len); iterator __i = _M_copy_aligned(begin(), __position, iterator(__q, 0)); diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/capacity/29134.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/capacity/29134.cc index 4290c86..69e5a53 100644 --- a/libstdc++-v3/testsuite/23_containers/vector/bool/capacity/29134.cc +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/capacity/29134.cc @@ -1,4 +1,4 @@ -// Copyright (C) 2006 Free Software Foundation, Inc. +// Copyright (C) 2006, 2007 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 @@ -28,7 +28,11 @@ void test01() std::vector vb; - VERIFY( vb.max_size() == std::vector::size_type(-1) ); + // Actually, vector is special, see libstdc++/31370. + typedef std::vector::difference_type difference_type; + VERIFY( vb.max_size() + == (std::numeric_limits::max() + - int(std::_S_word_bit) + 1) ); } int main() diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/31370.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/31370.cc new file mode 100644 index 0000000..0c4d0a8 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/31370.cc @@ -0,0 +1,192 @@ +// Copyright (C) 2007 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 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without Pred 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 COPYING. If not, write to the Free +// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, +// USA. + +// 23.2.5 class vector [lib.vector.bool] + +// { dg-do run { xfail *-*-darwin8.[0-4].* } } + +#include +#include +#include + +inline void +check_cap_ge_size(const std::vector& x) +{ + if (x.capacity() < x.size()) + throw std::logic_error(""); +} + +inline void +check_cap_eq_maxsize(const std::vector& x) +{ + if (x.capacity() != x.max_size()) + throw std::logic_error(""); +} + +// libstdc++/31370 +void test01() +{ + bool test __attribute__((unused)) = true; + int myexit = 0; + + try + { + std::vector x; + x.reserve(x.max_size()); + check_cap_eq_maxsize(x); + } + catch(std::bad_alloc&) + { } + catch(std::exception&) + { ++myexit; } + + // When doubling is too big, but smaller is sufficient, the resize + // should do smaller and be happy. It certainly shouldn't throw + // other exceptions or crash. + try + { + std::vector x; + x.resize(x.max_size() / 2 + 1, false); + for(int i = 0; i < std::_S_word_bit; ++i) + x.push_back(false); + check_cap_ge_size(x); + } + catch(std::bad_alloc&) + { } + catch(std::exception&) + { ++myexit; } + + try + { + std::vector x; + x.resize(x.max_size() / 2 + 1, false); + x.insert(x.end(), std::_S_word_bit, false); + check_cap_ge_size(x); + } + catch(std::bad_alloc&) + { } + catch(std::exception&) + { ++myexit; } + + try + { + std::vector x; + x.resize(x.max_size() / 2 + 1, false); + std::vector y(std::_S_word_bit, false); + x.insert(x.end(), y.begin(), y.end()); + check_cap_ge_size(x); + } + catch(std::bad_alloc&) + { } + catch(std::exception&) + { ++myexit; } + + // These tests are currently only relevant to bool: don't get burned + // by the attempt to round up when near the max size. + try + { + std::vector x; + x.resize(x.max_size() - std::_S_word_bit, false); + for(int i = 0; i < std::_S_word_bit; ++i) + x.push_back(false); + check_cap_ge_size(x); + } + catch(std::bad_alloc&) + { } + catch(std::exception&) + { ++myexit; } + + try + { + std::vector x; + x.resize(x.max_size() - std::_S_word_bit, false); + x.insert(x.end(), std::_S_word_bit, false); + check_cap_ge_size(x); + } + catch(std::bad_alloc&) + { } + catch(std::exception&) + { ++myexit; } + + try + { + std::vector x; + x.resize(x.max_size() - std::_S_word_bit, false); + std::vector y(std::_S_word_bit, false); + x.insert(x.end(), y.begin(), y.end()); + check_cap_ge_size(x); + } + catch(std::bad_alloc&) + { } + catch(std::exception&) + { ++myexit; } + + // Attempts to put in more than max_size() items should result in a + // length error. + try + { + std::vector x; + x.resize(x.max_size() - std::_S_word_bit, false); + for(int i = 0; i < std::_S_word_bit + 1; ++i) + x.push_back(false); + ++myexit; + } + catch(std::bad_alloc) + { } + catch(std::length_error) + { } + catch(std::exception) + { ++myexit; } + + try + { + std::vector x; + x.resize(x.max_size() - std::_S_word_bit, false); + x.insert(x.end(), std::_S_word_bit + 1, false); + ++myexit; + } + catch(std::bad_alloc) + { } + catch(std::length_error) + { } + catch(std::exception) + { ++myexit; } + + try + { + std::vector x; + x.resize(x.max_size() - std::_S_word_bit, false); + std::vector y(std::_S_word_bit + 1, false); + x.insert(x.end(), y.begin(), y.end()); + ++myexit; + } + catch(std::bad_alloc) + { } + catch(std::length_error) + { } + catch(std::exception) + { ++myexit; } + + VERIFY( !myexit ); +} + +int main() +{ + test01(); + return 0; +} -- 2.7.4