This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [Patch] libstdc++/25288
Paolo Carlini wrote:
>Yes, let's wait a bit more. Really, I think it's safe because nothing of
>this is exported from the library, of course, we are touching only
>internal implementation functions, and we are changing completely the
>names. Frankly, if for some crazy reason we had to keep around
>_M_fill_insert and _M_insert_dispatch, then I would rather prefer going
>with my first try (out of line, of course).
>
>
Eventually, I committed the attached. The only changes are the new
initialize helpers moved up in the file (consistently with the other
containers) and badly wrong comments fixed.
Paolo.
///////////////
2005-12-09 Paolo Carlini <pcarlini@suse.de>
Howard Hinnant <hhinnant@apple.com>
PR libstdc++/25288
* include/bits/stl_list.h (list<>::_M_insert_dispatch, _M_fill_insert):
Remove.
(_M_initialize_dispatch, _M_fill_initialize): Add.
(list(size_type, const value_type&, const allocator_type&),
list(const list&), list(_InputIterator, _InputIterator,
const allocator_type&): Use the latter.
(insert(iterator, size_type, const value_type&), insert(iterator,
_InputIterator, _InputIterator)): Use construction & splice.
* testsuite/23_containers/list/modifiers/insert/25288.cc: New.
* testsuite/testsuite_allocator.h (class throw_allocator): Add.
* include/bits/stl_list.h (list<>::insert, erase): Fix wrong comments.
Index: include/bits/stl_list.h
===================================================================
--- include/bits/stl_list.h (revision 108252)
+++ include/bits/stl_list.h (working copy)
@@ -479,7 +479,7 @@
list(size_type __n, const value_type& __value = value_type(),
const allocator_type& __a = allocator_type())
: _Base(__a)
- { this->insert(begin(), __n, __value); }
+ { _M_fill_initialize(__n, __value); }
/**
* @brief %List copy constructor.
@@ -490,7 +490,7 @@
*/
list(const list& __x)
: _Base(__x.get_allocator())
- { this->insert(begin(), __x.begin(), __x.end()); }
+ { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
/**
* @brief Builds a %list from a range.
@@ -500,17 +500,16 @@
* Create a %list consisting of copies of the elements from
* [@a first,@a last). This is linear in N (where N is
* distance(@a first,@a last)).
- *
- * @if maint
- * We don't need any dispatching tricks here, because insert does all of
- * that anyway.
- * @endif
*/
template<typename _InputIterator>
list(_InputIterator __first, _InputIterator __last,
const allocator_type& __a = allocator_type())
: _Base(__a)
- { this->insert(begin(), __first, __last); }
+ {
+ // Check whether it's an integral type. If so, it's not an iterator.
+ typedef typename std::__is_integer<_InputIterator>::__type _Integral;
+ _M_initialize_dispatch(__first, __last, _Integral());
+ }
/**
* No explicit dtor needed as the _Base dtor takes care of
@@ -798,13 +797,15 @@
* This function will insert a specified number of copies of the
* given data before the location specified by @a position.
*
- * Due to the nature of a %list this operation can be done in
- * constant time, and does not invalidate iterators and
- * references.
+ * This operation is linear in the number of elements inserted and
+ * does not invalidate iterators and references.
*/
void
insert(iterator __position, size_type __n, const value_type& __x)
- { _M_fill_insert(__position, __n, __x); }
+ {
+ list __tmp(__n, __x, get_allocator());
+ splice(__position, __tmp);
+ }
/**
* @brief Inserts a range into the %list.
@@ -816,18 +817,16 @@
* first,@a last) into the %list before the location specified by
* @a position.
*
- * Due to the nature of a %list this operation can be done in
- * constant time, and does not invalidate iterators and
- * references.
+ * This operation is linear in the number of elements inserted and
+ * does not invalidate iterators and references.
*/
template<typename _InputIterator>
void
insert(iterator __position, _InputIterator __first,
_InputIterator __last)
{
- // Check whether it's an integral type. If so, it's not an iterator.
- typedef typename std::__is_integer<_InputIterator>::__type _Integral;
- _M_insert_dispatch(__position, __first, __last, _Integral());
+ list __tmp(__first, __last, get_allocator());
+ splice(__position, __tmp);
}
/**
@@ -859,13 +858,12 @@
* This function will erase the elements in the range @a
* [first,last) and shorten the %list accordingly.
*
- * Due to the nature of a %list this operation can be done in
- * constant time, and only invalidates iterators/references to
- * the element being removed. The user is also cautioned that
- * this function only erases the elements, and that if the
- * elements themselves are pointers, the pointed-to memory is not
- * touched in any way. Managing the pointer is the user's
- * responsibilty.
+ * This operation is linear time in the size of the range and only
+ * invalidates iterators/references to the element being removed.
+ * The user is also cautioned that this function only erases the
+ * elements, and that if the elements themselves are pointers, the
+ * pointed-to memory is not touched in any way. Managing the pointer
+ * is the user's responsibilty.
*/
iterator
erase(iterator __first, iterator __last)
@@ -1071,60 +1069,58 @@
sort(_StrictWeakOrdering);
protected:
- // Internal assign functions follow.
+ // Internal constructor functions follow.
- // Called by the range assign to implement [23.1.1]/9
+ // Called by the range constructor to implement [23.1.1]/9
template<typename _Integer>
void
- _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
+ _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
{
- _M_fill_assign(static_cast<size_type>(__n),
- static_cast<value_type>(__val));
+ _M_fill_initialize(static_cast<size_type>(__n),
+ static_cast<value_type>(__x));
}
- // Called by the range assign to implement [23.1.1]/9
+ // Called by the range constructor to implement [23.1.1]/9
template<typename _InputIterator>
void
- _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
- __false_type);
+ _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
+ __false_type)
+ {
+ for (; __first != __last; ++__first)
+ push_back(*__first);
+ }
- // Called by assign(n,t), and the range assign when it turns out
+ // Called by list(n,v,a), and the range constructor when it turns out
// to be the same thing.
void
- _M_fill_assign(size_type __n, const value_type& __val);
+ _M_fill_initialize(size_type __n, const value_type& __x)
+ {
+ for (; __n > 0; --__n)
+ push_back(__x);
+ }
- // Internal insert functions follow.
+ // Internal assign functions follow.
- // Called by the range insert to implement [23.1.1]/9
+ // Called by the range assign to implement [23.1.1]/9
template<typename _Integer>
void
- _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
- __true_type)
+ _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
{
- _M_fill_insert(__pos, static_cast<size_type>(__n),
- static_cast<value_type>(__x));
+ _M_fill_assign(static_cast<size_type>(__n),
+ static_cast<value_type>(__val));
}
- // Called by the range insert to implement [23.1.1]/9
+ // Called by the range assign to implement [23.1.1]/9
template<typename _InputIterator>
void
- _M_insert_dispatch(iterator __pos,
- _InputIterator __first, _InputIterator __last,
- __false_type)
- {
- for (; __first != __last; ++__first)
- _M_insert(__pos, *__first);
- }
+ _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
+ __false_type);
- // Called by insert(p,n,x), and the range insert when it turns out
+ // Called by assign(n,t), and the range assign when it turns out
// to be the same thing.
void
- _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
- {
- for (; __n > 0; --__n)
- _M_insert(__pos, __x);
- }
+ _M_fill_assign(size_type __n, const value_type& __val);
// Moves the elements from [first,last) before position.
Index: testsuite/23_containers/list/modifiers/insert/25288.cc
===================================================================
--- testsuite/23_containers/list/modifiers/insert/25288.cc (revision 0)
+++ testsuite/23_containers/list/modifiers/insert/25288.cc (revision 0)
@@ -0,0 +1,92 @@
+// Copyright (C) 2005 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.2.3 list modifiers [lib.list.modifiers]
+
+#include <list>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+// libstdc++/25288
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ typedef __gnu_test::throw_allocator<int> my_alloc;
+ typedef std::list<int, my_alloc > my_list;
+
+ for (int j = 0; j < 10; ++j)
+ for (int i = 0; i < 10; ++i)
+ {
+ my_alloc alloc1(j + i);
+ my_list list1(alloc1);
+
+ for (int k = 0; k < j; ++k)
+ list1.push_back(-(k + 1));
+
+ try
+ {
+ list1.insert(list1.begin(), 10, 99);
+ VERIFY( false );
+ }
+ catch (std::bad_alloc&)
+ {
+ VERIFY( true );
+ }
+ catch (...)
+ {
+ VERIFY( false );
+ }
+
+ VERIFY( list1.size() == my_list::size_type(j) );
+ VERIFY( list1.size() == 0 || list1.back() == -j );
+ VERIFY( list1.size() == 0 || list1.front() == -1 );
+
+ my_alloc alloc2(j + i);
+ my_list list2(alloc2);
+
+ const int data[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
+
+ for (int k = 0; k < j; ++k)
+ list2.push_back(-(k + 1));
+
+ try
+ {
+ list2.insert(list2.begin(), data, data + 10);
+ VERIFY( false );
+ }
+ catch (std::bad_alloc&)
+ {
+ VERIFY( true );
+ }
+ catch (...)
+ {
+ VERIFY( false );
+ }
+
+ VERIFY( list2.size() == my_list::size_type(j) );
+ VERIFY( list2.size() == 0 || list2.back() == -j );
+ VERIFY( list2.size() == 0 || list2.front() == -1 );
+ }
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/testsuite_allocator.h
===================================================================
--- testsuite/testsuite_allocator.h (revision 108226)
+++ testsuite/testsuite_allocator.h (working copy)
@@ -1,7 +1,7 @@
// -*- C++ -*-
// Testing allocator for the C++ library testsuite.
//
-// Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
+// Copyright (C) 2002, 2003, 2004, 2005 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
@@ -229,6 +229,81 @@
}
throw;
}
+
+ template<typename Tp>
+ class throw_allocator
+ {
+ public:
+ typedef std::size_t size_type;
+ typedef std::ptrdiff_t difference_type;
+ typedef Tp* pointer;
+ typedef const Tp* const_pointer;
+ typedef Tp& reference;
+ typedef const Tp& const_reference;
+ typedef Tp value_type;
+
+ template<typename Tp1>
+ struct rebind
+ { typedef throw_allocator<Tp1> other; };
+
+ throw_allocator() throw()
+ : count(size_type(-1)) { }
+
+ throw_allocator(size_type c) throw()
+ : count(c) { }
+
+ template<typename Tp1>
+ throw_allocator(const throw_allocator<Tp1>& b) throw()
+ : count(b.get_count()) { }
+
+ size_type get_count() const { return count; }
+
+ pointer
+ address(reference x) const { return &x; }
+
+ const_pointer
+ address(const_reference x) const { return &x; }
+
+ pointer
+ allocate(size_type n, const void* = 0)
+ {
+ if (count == 0)
+ throw std::bad_alloc();
+
+ if (count != size_type(-1))
+ --count;
+
+ return static_cast<Tp*>(::operator new(n * sizeof(Tp)));
+ }
+
+ void
+ deallocate(pointer p, size_type)
+ { ::operator delete(p); }
+
+ size_type
+ max_size() const throw()
+ { return size_type(-1) / sizeof(Tp); }
+
+ void
+ construct(pointer p, const Tp& val)
+ { ::new(p) Tp(val); }
+
+ void
+ destroy(pointer p) { p->~Tp(); }
+
+ private:
+ template<typename Tp1>
+ friend inline bool
+ operator==(const throw_allocator&, const throw_allocator<Tp1>&)
+ { return true; }
+
+ template<typename Tp1>
+ friend inline bool
+ operator!=(const throw_allocator&, const throw_allocator<Tp1>&)
+ { return false; }
+
+ size_type count;
+ };
}; // namespace __gnu_test
#endif // _GLIBCXX_TESTSUITE_ALLOCATOR_H