This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Patch for stl_vector.h and vector.tcc.
- From: Dhruv Matani <dhruvbird at gmx dot net>
- To: Benjamin Kosnik <bkoz at redhat dot com>
- Cc: Matt Austern <austern at apple dot com>, Gabriel Dos Reis <gdr at integrable-solutions dot net>, libstdc++ <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: 12 Feb 2004 17:26:44 +0530
- Subject: Re: Patch for stl_vector.h and vector.tcc.
- Organization:
- References: <1076412225.2886.6.camel@localhost.localdomain> <20040211200957.25db8085.bkoz@redhat.com>
On Thu, 2004-02-12 at 07:39, Benjamin Kosnik wrote:
> >Also, I have attached a test case which seg_faults in the older
> >(unpatched) vector implementation. So, a way of testing whether the
> >patch worked!
>
> Nice job.
Thanks ;-)
> A couple of things
>
> 1) can you audit the other containers that changed, that may also have
> this problem? If they exhibit it, can you also do separate testcases for them?
Sure thing. I have attached a patch for deque. The test case attached
will result in mutual infinite recursion with the current(older) deque
implementation, and will work with the patched one (way to check if the
patch worked!)
> 2) cvs diff -N for new files.
Ok.
> 3) please pay attention to the coding conventions in C++STYLE, and the
> code surrounding your patch.
Ok. Done that this time around!
BTW, Benjamin, I have sent the copyrights by snail mail today. They
should reach in about 8~9 days. At least that's what I was told!
--
-Dhruv Matani.
http://www.geocities.com/dhruvbird/
#include <iostream>
using namespace std;
#include <vector>
#include <deque>
#include <algorithm>
#include <ext/new_allocator.h>
using namespace std;
using __gnu_cxx::new_allocator;
//#define CHECK_VECTOR
#define CHECK_DEQUE
#define CHECK_LIST
template <typename T>
class Whacky_Alloc : public new_allocator<T> {
static int Count;
Whacky_Alloc& operator= (Whacky_Alloc const&);
public:
virtual void clear ()
{
cout<<"In Whacky_Alloc::clear()"<<endl;
}
Whacky_Alloc () { cout<<"In ctor"<<endl; ++Count; }
Whacky_Alloc (Whacky_Alloc const& _wa) { cout<<"In copy ctor"<<endl; ++Count; }
virtual ~Whacky_Alloc ()
{
--Count;
cout<<"Calling My Clear -> Next Line Should be Whacky_Alloc::clear()"<<endl;
this->clear();
if (!Count)
cout<<"All Clear"<<endl;
}
T *allocate (typename new_allocator<T>::size_type n, const void *hint = 0)
{
cout<<"Call Clear Now! Next Line should be blank which is wrong behaviour."<<endl;
this->clear();
cout<<"\nAfter Clear"<<endl;
return new_allocator<T>::allocate(n, hint);
}
void deallocate (T *ptr, typename new_allocator<T>::size_type n)
{
cout<<"Call Clear Now! Next Line should be blank which is wrong behaviour."<<endl;
this->clear();
cout<<"\nAfter Clear"<<endl;
new_allocator<T>::deallocate (ptr, n);
}
};
template<typename X>
int Whacky_Alloc<X>::Count = 0;
int main()
{
#if defined CHECK_VECTOR
{
vector<int, Whacky_Alloc<int> > *piv = new vector<int, Whacky_Alloc<int> >;
int x = 23;
while (x--)
{
piv->push_back (x);
cout<<"Size of Vector is: "<<piv->size()<<endl;
}
vector<int, Whacky_Alloc<int> > tempiv;
std::swap (*piv, tempiv);
delete piv;
}
#endif
#if defined CHECK_DEQUE
{
deque<int, Whacky_Alloc<int> > *pid = new deque<int, Whacky_Alloc<int> >;
//We need a large x to force reallocation, since reallocation will
//happen only when size is > 512/sizeof(int).
int x = 230;
while (x--)
{
pid->push_back (x);
cout<<"Size of Deque is: "<<pid->size()<<endl;
}
//deque<int, Whacky_Alloc<int> > tempid;
// std::swap (*pid, tempid);
//The following should lead to Inifinite mutual function calling in
//the current (older) implementation.
cout<<"CALLING CLEAR!"<<endl;
pid->clear();
cout<<"CLEAR CALLED!"<<endl;
delete pid;
}
#endif
}
Common subdirectories: ./cvs_libstdc++/include/bits/CVS and ./modified_cvs_libstdc++/include/bits/CVS
diff -Ncp ./cvs_libstdc++/include/bits/deque.tcc ./modified_cvs_libstdc++/include/bits/deque.tcc
*** ./cvs_libstdc++/include/bits/deque.tcc 2004-02-09 18:23:05.000000000 +0530
--- ./modified_cvs_libstdc++/include/bits/deque.tcc 2004-02-12 16:34:45.000000000 +0530
*************** namespace __gnu_norm
*** 72,84 ****
if (&__x != this)
{
if (__len >= __x.size())
! erase(std::copy(__x.begin(), __x.end(), this->_M_start),
! this->_M_finish);
else
{
const_iterator __mid = __x.begin() + difference_type(__len);
! std::copy(__x.begin(), __mid, this->_M_start);
! insert(this->_M_finish, __mid, __x.end());
}
}
return *this;
--- 72,84 ----
if (&__x != this)
{
if (__len >= __x.size())
! erase(std::copy(__x.begin(), __x.end(), this->_M_impl._M_start),
! this->_M_impl._M_finish);
else
{
const_iterator __mid = __x.begin() + difference_type(__len);
! std::copy(__x.begin(), __mid, this->_M_impl._M_start);
! insert(this->_M_impl._M_finish, __mid, __x.end());
}
}
return *this;
*************** namespace __gnu_norm
*** 89,103 ****
deque<_Tp,_Alloc>::
insert(iterator position, const value_type& __x)
{
! if (position._M_cur == this->_M_start._M_cur)
{
push_front(__x);
! return this->_M_start;
}
! else if (position._M_cur == this->_M_finish._M_cur)
{
push_back(__x);
! iterator __tmp = this->_M_finish;
--__tmp;
return __tmp;
}
--- 89,103 ----
deque<_Tp,_Alloc>::
insert(iterator position, const value_type& __x)
{
! if (position._M_cur == this->_M_impl._M_start._M_cur)
{
push_front(__x);
! return this->_M_impl._M_start;
}
! else if (position._M_cur == this->_M_impl._M_finish._M_cur)
{
push_back(__x);
! iterator __tmp = this->_M_impl._M_finish;
--__tmp;
return __tmp;
}
*************** namespace __gnu_norm
*** 112,129 ****
{
iterator __next = __position;
++__next;
! size_type __index = __position - this->_M_start;
if (__index < (size() >> 1))
{
! std::copy_backward(this->_M_start, __position, __next);
pop_front();
}
else
{
! std::copy(__next, this->_M_finish, __position);
pop_back();
}
! return this->_M_start + __index;
}
template <typename _Tp, typename _Alloc>
--- 112,129 ----
{
iterator __next = __position;
++__next;
! size_type __index = __position - this->_M_impl._M_start;
if (__index < (size() >> 1))
{
! std::copy_backward(this->_M_impl._M_start, __position, __next);
pop_front();
}
else
{
! std::copy(__next, this->_M_impl._M_finish, __position);
pop_back();
}
! return this->_M_impl._M_start + __index;
}
template <typename _Tp, typename _Alloc>
*************** namespace __gnu_norm
*** 131,163 ****
deque<_Tp,_Alloc>::
erase(iterator __first, iterator __last)
{
! if (__first == this->_M_start && __last == this->_M_finish)
{
clear();
! return this->_M_finish;
}
else
{
const difference_type __n = __last - __first;
! const difference_type __elems_before = __first - this->_M_start;
if (static_cast<size_type>(__elems_before) < (size() - __n) / 2)
{
! std::copy_backward(this->_M_start, __first, __last);
! iterator __new_start = this->_M_start + __n;
! std::_Destroy(this->_M_start, __new_start);
! _M_destroy_nodes(this->_M_start._M_node, __new_start._M_node);
! this->_M_start = __new_start;
}
else
{
! std::copy(__last, this->_M_finish, __first);
! iterator __new_finish = this->_M_finish - __n;
! std::_Destroy(__new_finish, this->_M_finish);
_M_destroy_nodes(__new_finish._M_node + 1,
! this->_M_finish._M_node + 1);
! this->_M_finish = __new_finish;
}
! return this->_M_start + __elems_before;
}
}
--- 131,163 ----
deque<_Tp,_Alloc>::
erase(iterator __first, iterator __last)
{
! if (__first == this->_M_impl._M_start && __last == this->_M_impl._M_finish)
{
clear();
! return this->_M_impl._M_finish;
}
else
{
const difference_type __n = __last - __first;
! const difference_type __elems_before = __first - this->_M_impl._M_start;
if (static_cast<size_type>(__elems_before) < (size() - __n) / 2)
{
! std::copy_backward(this->_M_impl._M_start, __first, __last);
! iterator __new_start = this->_M_impl._M_start + __n;
! std::_Destroy(this->_M_impl._M_start, __new_start);
! _M_destroy_nodes(this->_M_impl._M_start._M_node, __new_start._M_node);
! this->_M_impl._M_start = __new_start;
}
else
{
! std::copy(__last, this->_M_impl._M_finish, __first);
! iterator __new_finish = this->_M_impl._M_finish - __n;
! std::_Destroy(__new_finish, this->_M_impl._M_finish);
_M_destroy_nodes(__new_finish._M_node + 1,
! this->_M_impl._M_finish._M_node + 1);
! this->_M_impl._M_finish = __new_finish;
}
! return this->_M_impl._M_start + __elems_before;
}
}
*************** namespace __gnu_norm
*** 166,189 ****
deque<_Tp,_Alloc>::
clear()
{
! for (_Map_pointer __node = this->_M_start._M_node + 1;
! __node < this->_M_finish._M_node;
++__node)
{
std::_Destroy(*__node, *__node + _S_buffer_size());
_M_deallocate_node(*__node);
}
! if (this->_M_start._M_node != this->_M_finish._M_node)
{
! std::_Destroy(this->_M_start._M_cur, this->_M_start._M_last);
! std::_Destroy(this->_M_finish._M_first, this->_M_finish._M_cur);
! _M_deallocate_node(this->_M_finish._M_first);
}
else
! std::_Destroy(this->_M_start._M_cur, this->_M_finish._M_cur);
! this->_M_finish = this->_M_start;
}
template <typename _Tp, class _Alloc>
--- 166,189 ----
deque<_Tp,_Alloc>::
clear()
{
! for (_Map_pointer __node = this->_M_impl._M_start._M_node + 1;
! __node < this->_M_impl._M_finish._M_node;
++__node)
{
std::_Destroy(*__node, *__node + _S_buffer_size());
_M_deallocate_node(*__node);
}
! if (this->_M_impl._M_start._M_node != this->_M_impl._M_finish._M_node)
{
! std::_Destroy(this->_M_impl._M_start._M_cur, this->_M_impl._M_start._M_last);
! std::_Destroy(this->_M_impl._M_finish._M_first, this->_M_impl._M_finish._M_cur);
! _M_deallocate_node(this->_M_impl._M_finish._M_first);
}
else
! std::_Destroy(this->_M_impl._M_start._M_cur, this->_M_impl._M_finish._M_cur);
! this->_M_impl._M_finish = this->_M_impl._M_start;
}
template <typename _Tp, class _Alloc>
*************** namespace __gnu_norm
*** 207,237 ****
deque<_Tp,_Alloc>::
_M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
{
! if (__pos._M_cur == this->_M_start._M_cur)
{
iterator __new_start = _M_reserve_elements_at_front(__n);
try
{
! std::uninitialized_fill(__new_start, this->_M_start, __x);
! this->_M_start = __new_start;
}
catch(...)
{
! _M_destroy_nodes(__new_start._M_node, this->_M_start._M_node);
__throw_exception_again;
}
}
! else if (__pos._M_cur == this->_M_finish._M_cur)
{
iterator __new_finish = _M_reserve_elements_at_back(__n);
try
{
! std::uninitialized_fill(this->_M_finish, __new_finish, __x);
! this->_M_finish = __new_finish;
}
catch(...)
{
! _M_destroy_nodes(this->_M_finish._M_node + 1,
__new_finish._M_node + 1);
__throw_exception_again;
}
--- 207,237 ----
deque<_Tp,_Alloc>::
_M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
{
! if (__pos._M_cur == this->_M_impl._M_start._M_cur)
{
iterator __new_start = _M_reserve_elements_at_front(__n);
try
{
! std::uninitialized_fill(__new_start, this->_M_impl._M_start, __x);
! this->_M_impl._M_start = __new_start;
}
catch(...)
{
! _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node);
__throw_exception_again;
}
}
! else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
{
iterator __new_finish = _M_reserve_elements_at_back(__n);
try
{
! std::uninitialized_fill(this->_M_impl._M_finish, __new_finish, __x);
! this->_M_impl._M_finish = __new_finish;
}
catch(...)
{
! _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
__new_finish._M_node + 1);
__throw_exception_again;
}
*************** namespace __gnu_norm
*** 248,264 ****
_Map_pointer __cur;
try
{
! for (__cur = this->_M_start._M_node;
! __cur < this->_M_finish._M_node;
++__cur)
std::uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
! std::uninitialized_fill(this->_M_finish._M_first,
! this->_M_finish._M_cur,
__value);
}
catch(...)
{
! std::_Destroy(this->_M_start, iterator(*__cur, __cur));
__throw_exception_again;
}
}
--- 248,264 ----
_Map_pointer __cur;
try
{
! for (__cur = this->_M_impl._M_start._M_node;
! __cur < this->_M_impl._M_finish._M_node;
++__cur)
std::uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
! std::uninitialized_fill(this->_M_impl._M_finish._M_first,
! this->_M_impl._M_finish._M_cur,
__value);
}
catch(...)
{
! std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur));
__throw_exception_again;
}
}
*************** namespace __gnu_norm
*** 296,303 ****
_Map_pointer __cur_node;
try
{
! for (__cur_node = this->_M_start._M_node;
! __cur_node < this->_M_finish._M_node;
++__cur_node)
{
_ForwardIterator __mid = __first;
--- 296,303 ----
_Map_pointer __cur_node;
try
{
! for (__cur_node = this->_M_impl._M_start._M_node;
! __cur_node < this->_M_impl._M_finish._M_node;
++__cur_node)
{
_ForwardIterator __mid = __first;
*************** namespace __gnu_norm
*** 305,320 ****
std::uninitialized_copy(__first, __mid, *__cur_node);
__first = __mid;
}
! std::uninitialized_copy(__first, __last, this->_M_finish._M_first);
}
catch(...)
{
! std::_Destroy(this->_M_start, iterator(*__cur_node, __cur_node));
__throw_exception_again;
}
}
! // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
template <typename _Tp, typename _Alloc>
void
deque<_Tp,_Alloc>::
--- 305,320 ----
std::uninitialized_copy(__first, __mid, *__cur_node);
__first = __mid;
}
! std::uninitialized_copy(__first, __last, this->_M_impl._M_finish._M_first);
}
catch(...)
{
! std::_Destroy(this->_M_impl._M_start, iterator(*__cur_node, __cur_node));
__throw_exception_again;
}
}
! // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
template <typename _Tp, typename _Alloc>
void
deque<_Tp,_Alloc>::
*************** namespace __gnu_norm
*** 322,342 ****
{
value_type __t_copy = __t;
_M_reserve_map_at_back();
! *(this->_M_finish._M_node + 1) = this->_M_allocate_node();
try
{
! std::_Construct(this->_M_finish._M_cur, __t_copy);
! this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
! this->_M_finish._M_cur = this->_M_finish._M_first;
}
catch(...)
{
! _M_deallocate_node(*(this->_M_finish._M_node + 1));
__throw_exception_again;
}
}
! // Called only if _M_start._M_cur == _M_start._M_first.
template <typename _Tp, typename _Alloc>
void
deque<_Tp,_Alloc>::
--- 322,342 ----
{
value_type __t_copy = __t;
_M_reserve_map_at_back();
! *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
try
{
! std::_Construct(this->_M_impl._M_finish._M_cur, __t_copy);
! this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node + 1);
! this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
}
catch(...)
{
! _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
__throw_exception_again;
}
}
! // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
template <typename _Tp, typename _Alloc>
void
deque<_Tp,_Alloc>::
*************** namespace __gnu_norm
*** 344,387 ****
{
value_type __t_copy = __t;
_M_reserve_map_at_front();
! *(this->_M_start._M_node - 1) = this->_M_allocate_node();
try
{
! this->_M_start._M_set_node(this->_M_start._M_node - 1);
! this->_M_start._M_cur = this->_M_start._M_last - 1;
! std::_Construct(this->_M_start._M_cur, __t_copy);
}
catch(...)
{
! ++this->_M_start;
! _M_deallocate_node(*(this->_M_start._M_node - 1));
__throw_exception_again;
}
}
! // Called only if _M_finish._M_cur == _M_finish._M_first.
template <typename _Tp, typename _Alloc>
void deque<_Tp,_Alloc>::
_M_pop_back_aux()
{
! _M_deallocate_node(this->_M_finish._M_first);
! this->_M_finish._M_set_node(this->_M_finish._M_node - 1);
! this->_M_finish._M_cur = this->_M_finish._M_last - 1;
! std::_Destroy(this->_M_finish._M_cur);
}
! // Called only if _M_start._M_cur == _M_start._M_last - 1. Note that
// if the deque has at least one element (a precondition for this member
! // function), and if _M_start._M_cur == _M_start._M_last, then the deque
// must have at least two nodes.
template <typename _Tp, typename _Alloc>
void deque<_Tp,_Alloc>::
_M_pop_front_aux()
{
! std::_Destroy(this->_M_start._M_cur);
! _M_deallocate_node(this->_M_start._M_first);
! this->_M_start._M_set_node(this->_M_start._M_node + 1);
! this->_M_start._M_cur = this->_M_start._M_first;
}
template <typename _Tp, typename _Alloc>
--- 344,387 ----
{
value_type __t_copy = __t;
_M_reserve_map_at_front();
! *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
try
{
! this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node - 1);
! this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
! std::_Construct(this->_M_impl._M_start._M_cur, __t_copy);
}
catch(...)
{
! ++this->_M_impl._M_start;
! _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
__throw_exception_again;
}
}
! // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
template <typename _Tp, typename _Alloc>
void deque<_Tp,_Alloc>::
_M_pop_back_aux()
{
! _M_deallocate_node(this->_M_impl._M_finish._M_first);
! this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
! this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
! std::_Destroy(this->_M_impl._M_finish._M_cur);
}
! // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. Note that
// if the deque has at least one element (a precondition for this member
! // function), and if _M_impl._M_start._M_cur == _M_impl._M_start._M_last, then the deque
// must have at least two nodes.
template <typename _Tp, typename _Alloc>
void deque<_Tp,_Alloc>::
_M_pop_front_aux()
{
! std::_Destroy(this->_M_impl._M_start._M_cur);
! _M_deallocate_node(this->_M_impl._M_start._M_first);
! this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
! this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
}
template <typename _Tp, typename _Alloc>
*************** namespace __gnu_norm
*** 402,432 ****
forward_iterator_tag)
{
size_type __n = std::distance(__first, __last);
! if (__pos._M_cur == this->_M_start._M_cur)
{
iterator __new_start = _M_reserve_elements_at_front(__n);
try
{
std::uninitialized_copy(__first, __last, __new_start);
! this->_M_start = __new_start;
}
catch(...)
{
! _M_destroy_nodes(__new_start._M_node, this->_M_start._M_node);
__throw_exception_again;
}
}
! else if (__pos._M_cur == this->_M_finish._M_cur)
{
iterator __new_finish = _M_reserve_elements_at_back(__n);
try
{
! std::uninitialized_copy(__first, __last, this->_M_finish);
! this->_M_finish = __new_finish;
}
catch(...)
{
! _M_destroy_nodes(this->_M_finish._M_node + 1,
__new_finish._M_node + 1);
__throw_exception_again;
}
--- 402,432 ----
forward_iterator_tag)
{
size_type __n = std::distance(__first, __last);
! if (__pos._M_cur == this->_M_impl._M_start._M_cur)
{
iterator __new_start = _M_reserve_elements_at_front(__n);
try
{
std::uninitialized_copy(__first, __last, __new_start);
! this->_M_impl._M_start = __new_start;
}
catch(...)
{
! _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node);
__throw_exception_again;
}
}
! else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
{
iterator __new_finish = _M_reserve_elements_at_back(__n);
try
{
! std::uninitialized_copy(__first, __last, this->_M_impl._M_finish);
! this->_M_impl._M_finish = __new_finish;
}
catch(...)
{
! _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
__new_finish._M_node + 1);
__throw_exception_again;
}
*************** namespace __gnu_norm
*** 440,455 ****
deque<_Tp,_Alloc>::
_M_insert_aux(iterator __pos, const value_type& __x)
{
! difference_type __index = __pos - this->_M_start;
value_type __x_copy = __x; // XXX copy
if (static_cast<size_type>(__index) < size() / 2)
{
push_front(front());
! iterator __front1 = this->_M_start;
++__front1;
iterator __front2 = __front1;
++__front2;
! __pos = this->_M_start + __index;
iterator __pos1 = __pos;
++__pos1;
std::copy(__front2, __pos1, __front1);
--- 440,455 ----
deque<_Tp,_Alloc>::
_M_insert_aux(iterator __pos, const value_type& __x)
{
! difference_type __index = __pos - this->_M_impl._M_start;
value_type __x_copy = __x; // XXX copy
if (static_cast<size_type>(__index) < size() / 2)
{
push_front(front());
! iterator __front1 = this->_M_impl._M_start;
++__front1;
iterator __front2 = __front1;
++__front2;
! __pos = this->_M_impl._M_start + __index;
iterator __pos1 = __pos;
++__pos1;
std::copy(__front2, __pos1, __front1);
*************** namespace __gnu_norm
*** 457,467 ****
else
{
push_back(back());
! iterator __back1 = this->_M_finish;
--__back1;
iterator __back2 = __back1;
--__back2;
! __pos = this->_M_start + __index;
std::copy_backward(__pos, __back2, __back1);
}
*__pos = __x_copy;
--- 457,467 ----
else
{
push_back(back());
! iterator __back1 = this->_M_impl._M_finish;
--__back1;
iterator __back2 = __back1;
--__back2;
! __pos = this->_M_impl._M_start + __index;
std::copy_backward(__pos, __back2, __back1);
}
*__pos = __x_copy;
*************** namespace __gnu_norm
*** 473,543 ****
deque<_Tp,_Alloc>::
_M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
{
! const difference_type __elems_before = __pos - this->_M_start;
size_type __length = this->size();
value_type __x_copy = __x;
if (__elems_before < difference_type(__length / 2))
{
iterator __new_start = _M_reserve_elements_at_front(__n);
! iterator __old_start = this->_M_start;
! __pos = this->_M_start + __elems_before;
try
{
if (__elems_before >= difference_type(__n))
{
! iterator __start_n = this->_M_start + difference_type(__n);
! std::uninitialized_copy(this->_M_start, __start_n,
__new_start);
! this->_M_start = __new_start;
std::copy(__start_n, __pos, __old_start);
fill(__pos - difference_type(__n), __pos, __x_copy);
}
else
{
! std::__uninitialized_copy_fill(this->_M_start, __pos,
__new_start,
! this->_M_start, __x_copy);
! this->_M_start = __new_start;
std::fill(__old_start, __pos, __x_copy);
}
}
catch(...)
{
! _M_destroy_nodes(__new_start._M_node, this->_M_start._M_node);
__throw_exception_again;
}
}
else
{
iterator __new_finish = _M_reserve_elements_at_back(__n);
! iterator __old_finish = this->_M_finish;
const difference_type __elems_after =
difference_type(__length) - __elems_before;
! __pos = this->_M_finish - __elems_after;
try
{
if (__elems_after > difference_type(__n))
{
! iterator __finish_n = this->_M_finish - difference_type(__n);
! std::uninitialized_copy(__finish_n, this->_M_finish,
! this->_M_finish);
! this->_M_finish = __new_finish;
std::copy_backward(__pos, __finish_n, __old_finish);
std::fill(__pos, __pos + difference_type(__n), __x_copy);
}
else
{
! std::__uninitialized_fill_copy(this->_M_finish,
__pos + difference_type(__n),
__x_copy, __pos,
! this->_M_finish);
! this->_M_finish = __new_finish;
std::fill(__pos, __old_finish, __x_copy);
}
}
catch(...)
{
! _M_destroy_nodes(this->_M_finish._M_node + 1,
__new_finish._M_node + 1);
__throw_exception_again;
}
--- 473,543 ----
deque<_Tp,_Alloc>::
_M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
{
! const difference_type __elems_before = __pos - this->_M_impl._M_start;
size_type __length = this->size();
value_type __x_copy = __x;
if (__elems_before < difference_type(__length / 2))
{
iterator __new_start = _M_reserve_elements_at_front(__n);
! iterator __old_start = this->_M_impl._M_start;
! __pos = this->_M_impl._M_start + __elems_before;
try
{
if (__elems_before >= difference_type(__n))
{
! iterator __start_n = this->_M_impl._M_start + difference_type(__n);
! std::uninitialized_copy(this->_M_impl._M_start, __start_n,
__new_start);
! this->_M_impl._M_start = __new_start;
std::copy(__start_n, __pos, __old_start);
fill(__pos - difference_type(__n), __pos, __x_copy);
}
else
{
! std::__uninitialized_copy_fill(this->_M_impl._M_start, __pos,
__new_start,
! this->_M_impl._M_start, __x_copy);
! this->_M_impl._M_start = __new_start;
std::fill(__old_start, __pos, __x_copy);
}
}
catch(...)
{
! _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node);
__throw_exception_again;
}
}
else
{
iterator __new_finish = _M_reserve_elements_at_back(__n);
! iterator __old_finish = this->_M_impl._M_finish;
const difference_type __elems_after =
difference_type(__length) - __elems_before;
! __pos = this->_M_impl._M_finish - __elems_after;
try
{
if (__elems_after > difference_type(__n))
{
! iterator __finish_n = this->_M_impl._M_finish - difference_type(__n);
! std::uninitialized_copy(__finish_n, this->_M_impl._M_finish,
! this->_M_impl._M_finish);
! this->_M_impl._M_finish = __new_finish;
std::copy_backward(__pos, __finish_n, __old_finish);
std::fill(__pos, __pos + difference_type(__n), __x_copy);
}
else
{
! std::__uninitialized_fill_copy(this->_M_impl._M_finish,
__pos + difference_type(__n),
__x_copy, __pos,
! this->_M_impl._M_finish);
! this->_M_impl._M_finish = __new_finish;
std::fill(__pos, __old_finish, __x_copy);
}
}
catch(...)
{
! _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
__new_finish._M_node + 1);
__throw_exception_again;
}
*************** namespace __gnu_norm
*** 552,572 ****
_ForwardIterator __first, _ForwardIterator __last,
size_type __n)
{
! const difference_type __elemsbefore = __pos - this->_M_start;
size_type __length = size();
if (static_cast<size_type>(__elemsbefore) < __length / 2)
{
iterator __new_start = _M_reserve_elements_at_front(__n);
! iterator __old_start = this->_M_start;
! __pos = this->_M_start + __elemsbefore;
try
{
if (__elemsbefore >= difference_type(__n))
{
! iterator __start_n = this->_M_start + difference_type(__n);
! std::uninitialized_copy(this->_M_start, __start_n,
__new_start);
! this->_M_start = __new_start;
std::copy(__start_n, __pos, __old_start);
std::copy(__first, __last, __pos - difference_type(__n));
}
--- 552,572 ----
_ForwardIterator __first, _ForwardIterator __last,
size_type __n)
{
! const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
size_type __length = size();
if (static_cast<size_type>(__elemsbefore) < __length / 2)
{
iterator __new_start = _M_reserve_elements_at_front(__n);
! iterator __old_start = this->_M_impl._M_start;
! __pos = this->_M_impl._M_start + __elemsbefore;
try
{
if (__elemsbefore >= difference_type(__n))
{
! iterator __start_n = this->_M_impl._M_start + difference_type(__n);
! std::uninitialized_copy(this->_M_impl._M_start, __start_n,
__new_start);
! this->_M_impl._M_start = __new_start;
std::copy(__start_n, __pos, __old_start);
std::copy(__first, __last, __pos - difference_type(__n));
}
*************** namespace __gnu_norm
*** 574,607 ****
{
_ForwardIterator __mid = __first;
std::advance(__mid, difference_type(__n) - __elemsbefore);
! std::__uninitialized_copy_copy(this->_M_start, __pos,
__first, __mid, __new_start);
! this->_M_start = __new_start;
std::copy(__mid, __last, __old_start);
}
}
catch(...)
{
! _M_destroy_nodes(__new_start._M_node, this->_M_start._M_node);
__throw_exception_again;
}
}
else
{
iterator __new_finish = _M_reserve_elements_at_back(__n);
! iterator __old_finish = this->_M_finish;
const difference_type __elemsafter =
difference_type(__length) - __elemsbefore;
! __pos = this->_M_finish - __elemsafter;
try
{
if (__elemsafter > difference_type(__n))
{
! iterator __finish_n = this->_M_finish - difference_type(__n);
std::uninitialized_copy(__finish_n,
! this->_M_finish,
! this->_M_finish);
! this->_M_finish = __new_finish;
std::copy_backward(__pos, __finish_n, __old_finish);
std::copy(__first, __last, __pos);
}
--- 574,607 ----
{
_ForwardIterator __mid = __first;
std::advance(__mid, difference_type(__n) - __elemsbefore);
! std::__uninitialized_copy_copy(this->_M_impl._M_start, __pos,
__first, __mid, __new_start);
! this->_M_impl._M_start = __new_start;
std::copy(__mid, __last, __old_start);
}
}
catch(...)
{
! _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node);
__throw_exception_again;
}
}
else
{
iterator __new_finish = _M_reserve_elements_at_back(__n);
! iterator __old_finish = this->_M_impl._M_finish;
const difference_type __elemsafter =
difference_type(__length) - __elemsbefore;
! __pos = this->_M_impl._M_finish - __elemsafter;
try
{
if (__elemsafter > difference_type(__n))
{
! iterator __finish_n = this->_M_impl._M_finish - difference_type(__n);
std::uninitialized_copy(__finish_n,
! this->_M_impl._M_finish,
! this->_M_impl._M_finish);
! this->_M_impl._M_finish = __new_finish;
std::copy_backward(__pos, __finish_n, __old_finish);
std::copy(__first, __last, __pos);
}
*************** namespace __gnu_norm
*** 610,624 ****
_ForwardIterator __mid = __first;
std::advance(__mid, __elemsafter);
std::__uninitialized_copy_copy(__mid, __last, __pos,
! this->_M_finish,
! this->_M_finish);
! this->_M_finish = __new_finish;
std::copy(__first, __mid, __pos);
}
}
catch(...)
{
! _M_destroy_nodes(this->_M_finish._M_node + 1,
__new_finish._M_node + 1);
__throw_exception_again;
}
--- 610,624 ----
_ForwardIterator __mid = __first;
std::advance(__mid, __elemsafter);
std::__uninitialized_copy_copy(__mid, __last, __pos,
! this->_M_impl._M_finish,
! this->_M_impl._M_finish);
! this->_M_impl._M_finish = __new_finish;
std::copy(__first, __mid, __pos);
}
}
catch(...)
{
! _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
__new_finish._M_node + 1);
__throw_exception_again;
}
*************** namespace __gnu_norm
*** 637,648 ****
try
{
for (__i = 1; __i <= __new_nodes; ++__i)
! *(this->_M_start._M_node - __i) = this->_M_allocate_node();
}
catch(...)
{
for (size_type __j = 1; __j < __i; ++__j)
! _M_deallocate_node(*(this->_M_start._M_node - __j));
__throw_exception_again;
}
}
--- 637,648 ----
try
{
for (__i = 1; __i <= __new_nodes; ++__i)
! *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
}
catch(...)
{
for (size_type __j = 1; __j < __i; ++__j)
! _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
__throw_exception_again;
}
}
*************** namespace __gnu_norm
*** 659,670 ****
try
{
for (__i = 1; __i <= __new_nodes; ++__i)
! *(this->_M_finish._M_node + __i) = this->_M_allocate_node();
}
catch(...)
{
for (size_type __j = 1; __j < __i; ++__j)
! _M_deallocate_node(*(this->_M_finish._M_node + __j));
__throw_exception_again;
}
}
--- 659,670 ----
try
{
for (__i = 1; __i <= __new_nodes; ++__i)
! *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
}
catch(...)
{
for (size_type __j = 1; __j < __i; ++__j)
! _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
__throw_exception_again;
}
}
*************** namespace __gnu_norm
*** 675,718 ****
_M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
{
size_type __old_num_nodes
! = this->_M_finish._M_node - this->_M_start._M_node + 1;
size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
_Map_pointer __new_nstart;
! if (this->_M_map_size > 2 * __new_num_nodes)
{
! __new_nstart = this->_M_map + (this->_M_map_size
- __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
! if (__new_nstart < this->_M_start._M_node)
! std::copy(this->_M_start._M_node,
! this->_M_finish._M_node + 1,
__new_nstart);
else
! std::copy_backward(this->_M_start._M_node,
! this->_M_finish._M_node + 1,
__new_nstart + __old_num_nodes);
}
else
{
! size_type __new_map_size = this->_M_map_size
! + std::max(this->_M_map_size,
__nodes_to_add) + 2;
_Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
! std::copy(this->_M_start._M_node,
! this->_M_finish._M_node + 1,
__new_nstart);
! _M_deallocate_map(this->_M_map, this->_M_map_size);
! this->_M_map = __new_map;
! this->_M_map_size = __new_map_size;
}
! this->_M_start._M_set_node(__new_nstart);
! this->_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
}
} // namespace __gnu_norm
--- 675,718 ----
_M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
{
size_type __old_num_nodes
! = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
_Map_pointer __new_nstart;
! if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
{
! __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
- __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
! if (__new_nstart < this->_M_impl._M_start._M_node)
! std::copy(this->_M_impl._M_start._M_node,
! this->_M_impl._M_finish._M_node + 1,
__new_nstart);
else
! std::copy_backward(this->_M_impl._M_start._M_node,
! this->_M_impl._M_finish._M_node + 1,
__new_nstart + __old_num_nodes);
}
else
{
! size_type __new_map_size = this->_M_impl._M_map_size
! + std::max(this->_M_impl._M_map_size,
__nodes_to_add) + 2;
_Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
! std::copy(this->_M_impl._M_start._M_node,
! this->_M_impl._M_finish._M_node + 1,
__new_nstart);
! _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
! this->_M_impl._M_map = __new_map;
! this->_M_impl._M_map_size = __new_map_size;
}
! this->_M_impl._M_start._M_set_node(__new_nstart);
! this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
}
} // namespace __gnu_norm
diff -Ncp ./cvs_libstdc++/include/bits/stl_deque.h ./modified_cvs_libstdc++/include/bits/stl_deque.h
*** ./cvs_libstdc++/include/bits/stl_deque.h 2004-02-09 18:23:09.000000000 +0530
--- ./modified_cvs_libstdc++/include/bits/stl_deque.h 2004-02-12 17:14:30.000000000 +0530
*************** namespace __gnu_norm
*** 351,389 ****
*/
template<typename _Tp, typename _Alloc>
class _Deque_base
- : public _Alloc
{
public:
typedef _Alloc allocator_type;
allocator_type
get_allocator() const
! { return *static_cast<const _Alloc*>(this); }
typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator;
typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
_Deque_base(const allocator_type& __a, size_t __num_elements)
! : _Alloc(__a), _M_start(), _M_finish()
{ _M_initialize_map(__num_elements); }
_Deque_base(const allocator_type& __a)
! : _Alloc(__a), _M_start(), _M_finish() { }
~_Deque_base();
protected:
typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
_Map_alloc_type _M_get_map_allocator() const
{ return _Map_alloc_type(this->get_allocator()); }
_Tp*
_M_allocate_node()
! { return _Alloc::allocate(__deque_buf_size(sizeof(_Tp))); }
void
_M_deallocate_node(_Tp* __p)
! { _Alloc::deallocate(__p, __deque_buf_size(sizeof(_Tp))); }
_Tp**
_M_allocate_map(size_t __n)
--- 351,401 ----
*/
template<typename _Tp, typename _Alloc>
class _Deque_base
{
public:
typedef _Alloc allocator_type;
allocator_type
get_allocator() const
! { return *static_cast<const _Alloc*>(&this->_M_impl); }
typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator;
typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
_Deque_base(const allocator_type& __a, size_t __num_elements)
! : _M_impl(__a)
{ _M_initialize_map(__num_elements); }
_Deque_base(const allocator_type& __a)
! : _M_impl(__a) { }
~_Deque_base();
protected:
+ //This struct encapsulates the implementation of the std::deque
+ //standard container and at the same time makes use of the EBO
+ //for empty allocators.
+ struct _Deque_impl : public _Alloc {
+ _Tp** _M_map;
+ size_t _M_map_size;
+ iterator _M_start;
+ iterator _M_finish;
+
+ _Deque_impl (const _Alloc& __a)
+ : _Alloc(__a), _M_map(0), _M_map_size(0), _M_start(), _M_finish() { }
+ };
+
typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
_Map_alloc_type _M_get_map_allocator() const
{ return _Map_alloc_type(this->get_allocator()); }
_Tp*
_M_allocate_node()
! { return _M_impl._Alloc::allocate(__deque_buf_size(sizeof(_Tp))); }
void
_M_deallocate_node(_Tp* __p)
! { _M_impl._Alloc::deallocate(__p, __deque_buf_size(sizeof(_Tp))); }
_Tp**
_M_allocate_map(size_t __n)
*************** namespace __gnu_norm
*** 399,417 ****
void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
enum { _S_initial_map_size = 8 };
! _Tp** _M_map;
! size_t _M_map_size;
! iterator _M_start;
! iterator _M_finish;
};
template<typename _Tp, typename _Alloc>
_Deque_base<_Tp,_Alloc>::~_Deque_base()
{
! if (this->_M_map)
{
! _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
! _M_deallocate_map(this->_M_map, this->_M_map_size);
}
}
--- 411,426 ----
void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
enum { _S_initial_map_size = 8 };
! _Deque_impl _M_impl;
};
template<typename _Tp, typename _Alloc>
_Deque_base<_Tp,_Alloc>::~_Deque_base()
{
! if (this->_M_impl._M_map)
{
! _M_destroy_nodes(this->_M_impl._M_start._M_node, this->_M_impl._M_finish._M_node + 1);
! _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
}
}
*************** namespace __gnu_norm
*** 431,462 ****
{
size_t __num_nodes = __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
! this->_M_map_size = std::max((size_t) _S_initial_map_size,
__num_nodes + 2);
! this->_M_map = _M_allocate_map(this->_M_map_size);
// For "small" maps (needing less than _M_map_size nodes), allocation
// starts in the middle elements and grows outwards. So nstart may be
// the beginning of _M_map, but for small maps it may be as far in as
// _M_map+3.
! _Tp** __nstart = this->_M_map + (this->_M_map_size - __num_nodes) / 2;
_Tp** __nfinish = __nstart + __num_nodes;
try
{ _M_create_nodes(__nstart, __nfinish); }
catch(...)
{
! _M_deallocate_map(this->_M_map, this->_M_map_size);
! this->_M_map = 0;
! this->_M_map_size = 0;
__throw_exception_again;
}
! _M_start._M_set_node(__nstart);
! _M_finish._M_set_node(__nfinish - 1);
! _M_start._M_cur = _M_start._M_first;
! _M_finish._M_cur = _M_finish._M_first + __num_elements
% __deque_buf_size(sizeof(_Tp));
}
--- 440,471 ----
{
size_t __num_nodes = __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
! this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
__num_nodes + 2);
! this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
// For "small" maps (needing less than _M_map_size nodes), allocation
// starts in the middle elements and grows outwards. So nstart may be
// the beginning of _M_map, but for small maps it may be as far in as
// _M_map+3.
! _Tp** __nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size - __num_nodes) / 2;
_Tp** __nfinish = __nstart + __num_nodes;
try
{ _M_create_nodes(__nstart, __nfinish); }
catch(...)
{
! _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
! this->_M_impl._M_map = 0;
! this->_M_impl._M_map_size = 0;
__throw_exception_again;
}
! this->_M_impl._M_start._M_set_node(__nstart);
! this->_M_impl._M_finish._M_set_node(__nfinish - 1);
! this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
! this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first + __num_elements
% __deque_buf_size(sizeof(_Tp));
}
*************** namespace __gnu_norm
*** 608,619 ****
/** @if maint
* A total of four data members accumulated down the heirarchy.
* @endif
*/
! using _Base::_M_map;
! using _Base::_M_map_size;
! using _Base::_M_start;
! using _Base::_M_finish;
public:
// [23.2.1.1] construct/copy/destroy
--- 617,626 ----
/** @if maint
* A total of four data members accumulated down the heirarchy.
+ * May be accessed via _M_impl.*
* @endif
*/
! using _Base::_M_impl;
public:
// [23.2.1.1] construct/copy/destroy
*************** namespace __gnu_norm
*** 658,664 ****
*/
deque(const deque& __x)
: _Base(__x.get_allocator(), __x.size())
! { std::uninitialized_copy(__x.begin(), __x.end(), this->_M_start); }
/**
* @brief Builds a %deque from a range.
--- 665,671 ----
*/
deque(const deque& __x)
: _Base(__x.get_allocator(), __x.size())
! { std::uninitialized_copy(__x.begin(), __x.end(), this->_M_impl._M_start); }
/**
* @brief Builds a %deque from a range.
*************** namespace __gnu_norm
*** 690,696 ****
* way. Managing the pointer is the user's responsibilty.
*/
~deque()
! { std::_Destroy(this->_M_start, this->_M_finish); }
/**
* @brief %Deque assignment operator.
--- 697,703 ----
* way. Managing the pointer is the user's responsibilty.
*/
~deque()
! { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); }
/**
* @brief %Deque assignment operator.
*************** namespace __gnu_norm
*** 748,754 ****
*/
iterator
begin()
! { return this->_M_start; }
/**
* Returns a read-only (constant) iterator that points to the first
--- 755,761 ----
*/
iterator
begin()
! { return this->_M_impl._M_start; }
/**
* Returns a read-only (constant) iterator that points to the first
*************** namespace __gnu_norm
*** 756,762 ****
*/
const_iterator
begin() const
! { return this->_M_start; }
/**
* Returns a read/write iterator that points one past the last element in
--- 763,769 ----
*/
const_iterator
begin() const
! { return this->_M_impl._M_start; }
/**
* Returns a read/write iterator that points one past the last element in
*************** namespace __gnu_norm
*** 764,770 ****
*/
iterator
end()
! { return this->_M_finish; }
/**
* Returns a read-only (constant) iterator that points one past the last
--- 771,777 ----
*/
iterator
end()
! { return this->_M_impl._M_finish; }
/**
* Returns a read-only (constant) iterator that points one past the last
*************** namespace __gnu_norm
*** 772,778 ****
*/
const_iterator
end() const
! { return this->_M_finish; }
/**
* Returns a read/write reverse iterator that points to the last element
--- 779,785 ----
*/
const_iterator
end() const
! { return this->_M_impl._M_finish; }
/**
* Returns a read/write reverse iterator that points to the last element
*************** namespace __gnu_norm
*** 780,786 ****
*/
reverse_iterator
rbegin()
! { return reverse_iterator(this->_M_finish); }
/**
* Returns a read-only (constant) reverse iterator that points to the
--- 787,793 ----
*/
reverse_iterator
rbegin()
! { return reverse_iterator(this->_M_impl._M_finish); }
/**
* Returns a read-only (constant) reverse iterator that points to the
*************** namespace __gnu_norm
*** 789,795 ****
*/
const_reverse_iterator
rbegin() const
! { return const_reverse_iterator(this->_M_finish); }
/**
* Returns a read/write reverse iterator that points to one before the
--- 796,802 ----
*/
const_reverse_iterator
rbegin() const
! { return const_reverse_iterator(this->_M_impl._M_finish); }
/**
* Returns a read/write reverse iterator that points to one before the
*************** namespace __gnu_norm
*** 797,803 ****
* order.
*/
reverse_iterator
! rend() { return reverse_iterator(this->_M_start); }
/**
* Returns a read-only (constant) reverse iterator that points to one
--- 804,810 ----
* order.
*/
reverse_iterator
! rend() { return reverse_iterator(this->_M_impl._M_start); }
/**
* Returns a read-only (constant) reverse iterator that points to one
*************** namespace __gnu_norm
*** 806,818 ****
*/
const_reverse_iterator
rend() const
! { return const_reverse_iterator(this->_M_start); }
// [23.2.1.2] capacity
/** Returns the number of elements in the %deque. */
size_type
size() const
! { return this->_M_finish - this->_M_start; }
/** Returns the size() of the largest possible %deque. */
size_type
--- 813,825 ----
*/
const_reverse_iterator
rend() const
! { return const_reverse_iterator(this->_M_impl._M_start); }
// [23.2.1.2] capacity
/** Returns the number of elements in the %deque. */
size_type
size() const
! { return this->_M_impl._M_finish - this->_M_impl._M_start; }
/** Returns the size() of the largest possible %deque. */
size_type
*************** namespace __gnu_norm
*** 834,842 ****
{
const size_type __len = size();
if (__new_size < __len)
! erase(this->_M_start + __new_size, this->_M_finish);
else
! insert(this->_M_finish, __new_size - __len, __x);
}
/**
--- 841,849 ----
{
const size_type __len = size();
if (__new_size < __len)
! erase(this->_M_impl._M_start + __new_size, this->_M_impl._M_finish);
else
! insert(this->_M_impl._M_finish, __new_size - __len, __x);
}
/**
*************** namespace __gnu_norm
*** 857,863 ****
*/
bool
empty() const
! { return this->_M_finish == this->_M_start; }
// element access
/**
--- 864,870 ----
*/
bool
empty() const
! { return this->_M_impl._M_finish == this->_M_impl._M_start; }
// element access
/**
*************** namespace __gnu_norm
*** 871,877 ****
*/
reference
operator[](size_type __n)
! { return this->_M_start[difference_type(__n)]; }
/**
* @brief Subscript access to the data contained in the %deque.
--- 878,884 ----
*/
reference
operator[](size_type __n)
! { return this->_M_impl._M_start[difference_type(__n)]; }
/**
* @brief Subscript access to the data contained in the %deque.
*************** namespace __gnu_norm
*** 884,890 ****
*/
const_reference
operator[](size_type __n) const
! { return this->_M_start[difference_type(__n)]; }
protected:
/// @if maint Safety check used only from at(). @endif
--- 891,897 ----
*/
const_reference
operator[](size_type __n) const
! { return this->_M_impl._M_start[difference_type(__n)]; }
protected:
/// @if maint Safety check used only from at(). @endif
*************** namespace __gnu_norm
*** 933,939 ****
*/
reference
front()
! { return *this->_M_start; }
/**
* Returns a read-only (constant) reference to the data at the first
--- 940,946 ----
*/
reference
front()
! { return *this->_M_impl._M_start; }
/**
* Returns a read-only (constant) reference to the data at the first
*************** namespace __gnu_norm
*** 941,947 ****
*/
const_reference
front() const
! { return *this->_M_start; }
/**
* Returns a read/write reference to the data at the last element of the
--- 948,954 ----
*/
const_reference
front() const
! { return *this->_M_impl._M_start; }
/**
* Returns a read/write reference to the data at the last element of the
*************** namespace __gnu_norm
*** 950,956 ****
reference
back()
{
! iterator __tmp = this->_M_finish;
--__tmp;
return *__tmp;
}
--- 957,963 ----
reference
back()
{
! iterator __tmp = this->_M_impl._M_finish;
--__tmp;
return *__tmp;
}
*************** namespace __gnu_norm
*** 962,968 ****
const_reference
back() const
{
! const_iterator __tmp = this->_M_finish;
--__tmp;
return *__tmp;
}
--- 969,975 ----
const_reference
back() const
{
! const_iterator __tmp = this->_M_impl._M_finish;
--__tmp;
return *__tmp;
}
*************** namespace __gnu_norm
*** 979,988 ****
void
push_front(const value_type& __x)
{
! if (this->_M_start._M_cur != this->_M_start._M_first)
{
! std::_Construct(this->_M_start._M_cur - 1, __x);
! --this->_M_start._M_cur;
}
else
_M_push_front_aux(__x);
--- 986,995 ----
void
push_front(const value_type& __x)
{
! if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
{
! std::_Construct(this->_M_impl._M_start._M_cur - 1, __x);
! --this->_M_impl._M_start._M_cur;
}
else
_M_push_front_aux(__x);
*************** namespace __gnu_norm
*** 999,1008 ****
void
push_back(const value_type& __x)
{
! if (this->_M_finish._M_cur != this->_M_finish._M_last - 1)
{
! std::_Construct(this->_M_finish._M_cur, __x);
! ++this->_M_finish._M_cur;
}
else
_M_push_back_aux(__x);
--- 1006,1015 ----
void
push_back(const value_type& __x)
{
! if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_last - 1)
{
! std::_Construct(this->_M_impl._M_finish._M_cur, __x);
! ++this->_M_impl._M_finish._M_cur;
}
else
_M_push_back_aux(__x);
*************** namespace __gnu_norm
*** 1019,1028 ****
void
pop_front()
{
! if (this->_M_start._M_cur != this->_M_start._M_last - 1)
{
! std::_Destroy(this->_M_start._M_cur);
! ++this->_M_start._M_cur;
}
else
_M_pop_front_aux();
--- 1026,1035 ----
void
pop_front()
{
! if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_last - 1)
{
! std::_Destroy(this->_M_impl._M_start._M_cur);
! ++this->_M_impl._M_start._M_cur;
}
else
_M_pop_front_aux();
*************** namespace __gnu_norm
*** 1039,1048 ****
void
pop_back()
{
! if (this->_M_finish._M_cur != this->_M_finish._M_first)
{
! --this->_M_finish._M_cur;
! std::_Destroy(this->_M_finish._M_cur);
}
else
_M_pop_back_aux();
--- 1046,1055 ----
void
pop_back()
{
! if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_first)
{
! --this->_M_impl._M_finish._M_cur;
! std::_Destroy(this->_M_impl._M_finish._M_cur);
}
else
_M_pop_back_aux();
*************** namespace __gnu_norm
*** 1140,1149 ****
void
swap(deque& __x)
{
! std::swap(this->_M_start, __x._M_start);
! std::swap(this->_M_finish, __x._M_finish);
! std::swap(this->_M_map, __x._M_map);
! std::swap(this->_M_map_size, __x._M_map_size);
}
/**
--- 1147,1156 ----
void
swap(deque& __x)
{
! std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
! std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
! std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
! std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
}
/**
*************** namespace __gnu_norm
*** 1362,1382 ****
iterator
_M_reserve_elements_at_front(size_type __n)
{
! const size_type __vacancies = this->_M_start._M_cur
! - this->_M_start._M_first;
if (__n > __vacancies)
_M_new_elements_at_front(__n - __vacancies);
! return this->_M_start - difference_type(__n);
}
iterator
_M_reserve_elements_at_back(size_type __n)
{
! const size_type __vacancies = (this->_M_finish._M_last
! - this->_M_finish._M_cur) - 1;
if (__n > __vacancies)
_M_new_elements_at_back(__n - __vacancies);
! return this->_M_finish + difference_type(__n);
}
void
--- 1369,1389 ----
iterator
_M_reserve_elements_at_front(size_type __n)
{
! const size_type __vacancies = this->_M_impl._M_start._M_cur
! - this->_M_impl._M_start._M_first;
if (__n > __vacancies)
_M_new_elements_at_front(__n - __vacancies);
! return this->_M_impl._M_start - difference_type(__n);
}
iterator
_M_reserve_elements_at_back(size_type __n)
{
! const size_type __vacancies = (this->_M_impl._M_finish._M_last
! - this->_M_impl._M_finish._M_cur) - 1;
if (__n > __vacancies)
_M_new_elements_at_back(__n - __vacancies);
! return this->_M_impl._M_finish + difference_type(__n);
}
void
*************** namespace __gnu_norm
*** 1400,1414 ****
void
_M_reserve_map_at_back (size_type __nodes_to_add = 1)
{
! if (__nodes_to_add + 1 > this->_M_map_size
! - (this->_M_finish._M_node - this->_M_map))
_M_reallocate_map(__nodes_to_add, false);
}
void
_M_reserve_map_at_front (size_type __nodes_to_add = 1)
{
! if (__nodes_to_add > size_type(this->_M_start._M_node - this->_M_map))
_M_reallocate_map(__nodes_to_add, true);
}
--- 1407,1421 ----
void
_M_reserve_map_at_back (size_type __nodes_to_add = 1)
{
! if (__nodes_to_add + 1 > this->_M_impl._M_map_size
! - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
_M_reallocate_map(__nodes_to_add, false);
}
void
_M_reserve_map_at_front (size_type __nodes_to_add = 1)
{
! if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node - this->_M_impl._M_map))
_M_reallocate_map(__nodes_to_add, true);
}