1*e4b17023SJohn Marino // Deque implementation (out of line) -*- C++ -*- 2*e4b17023SJohn Marino 3*e4b17023SJohn Marino // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 4*e4b17023SJohn Marino // 2009, 2010, 2011, 2012 5*e4b17023SJohn Marino // Free Software Foundation, Inc. 6*e4b17023SJohn Marino // 7*e4b17023SJohn Marino // This file is part of the GNU ISO C++ Library. This library is free 8*e4b17023SJohn Marino // software; you can redistribute it and/or modify it under the 9*e4b17023SJohn Marino // terms of the GNU General Public License as published by the 10*e4b17023SJohn Marino // Free Software Foundation; either version 3, or (at your option) 11*e4b17023SJohn Marino // any later version. 12*e4b17023SJohn Marino 13*e4b17023SJohn Marino // This library is distributed in the hope that it will be useful, 14*e4b17023SJohn Marino // but WITHOUT ANY WARRANTY; without even the implied warranty of 15*e4b17023SJohn Marino // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16*e4b17023SJohn Marino // GNU General Public License for more details. 17*e4b17023SJohn Marino 18*e4b17023SJohn Marino // Under Section 7 of GPL version 3, you are granted additional 19*e4b17023SJohn Marino // permissions described in the GCC Runtime Library Exception, version 20*e4b17023SJohn Marino // 3.1, as published by the Free Software Foundation. 21*e4b17023SJohn Marino 22*e4b17023SJohn Marino // You should have received a copy of the GNU General Public License and 23*e4b17023SJohn Marino // a copy of the GCC Runtime Library Exception along with this program; 24*e4b17023SJohn Marino // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 25*e4b17023SJohn Marino // <http://www.gnu.org/licenses/>. 26*e4b17023SJohn Marino 27*e4b17023SJohn Marino /* 28*e4b17023SJohn Marino * 29*e4b17023SJohn Marino * Copyright (c) 1994 30*e4b17023SJohn Marino * Hewlett-Packard Company 31*e4b17023SJohn Marino * 32*e4b17023SJohn Marino * Permission to use, copy, modify, distribute and sell this software 33*e4b17023SJohn Marino * and its documentation for any purpose is hereby granted without fee, 34*e4b17023SJohn Marino * provided that the above copyright notice appear in all copies and 35*e4b17023SJohn Marino * that both that copyright notice and this permission notice appear 36*e4b17023SJohn Marino * in supporting documentation. Hewlett-Packard Company makes no 37*e4b17023SJohn Marino * representations about the suitability of this software for any 38*e4b17023SJohn Marino * purpose. It is provided "as is" without express or implied warranty. 39*e4b17023SJohn Marino * 40*e4b17023SJohn Marino * 41*e4b17023SJohn Marino * Copyright (c) 1997 42*e4b17023SJohn Marino * Silicon Graphics Computer Systems, Inc. 43*e4b17023SJohn Marino * 44*e4b17023SJohn Marino * Permission to use, copy, modify, distribute and sell this software 45*e4b17023SJohn Marino * and its documentation for any purpose is hereby granted without fee, 46*e4b17023SJohn Marino * provided that the above copyright notice appear in all copies and 47*e4b17023SJohn Marino * that both that copyright notice and this permission notice appear 48*e4b17023SJohn Marino * in supporting documentation. Silicon Graphics makes no 49*e4b17023SJohn Marino * representations about the suitability of this software for any 50*e4b17023SJohn Marino * purpose. It is provided "as is" without express or implied warranty. 51*e4b17023SJohn Marino */ 52*e4b17023SJohn Marino 53*e4b17023SJohn Marino /** @file bits/deque.tcc 54*e4b17023SJohn Marino * This is an internal header file, included by other library headers. 55*e4b17023SJohn Marino * Do not attempt to use it directly. @headername{deque} 56*e4b17023SJohn Marino */ 57*e4b17023SJohn Marino 58*e4b17023SJohn Marino #ifndef _DEQUE_TCC 59*e4b17023SJohn Marino #define _DEQUE_TCC 1 60*e4b17023SJohn Marino 61*e4b17023SJohn Marino namespace std _GLIBCXX_VISIBILITY(default) 62*e4b17023SJohn Marino { 63*e4b17023SJohn Marino _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 64*e4b17023SJohn Marino 65*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__ 66*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 67*e4b17023SJohn Marino void 68*e4b17023SJohn Marino deque<_Tp, _Alloc>:: _M_default_initialize()69*e4b17023SJohn Marino _M_default_initialize() 70*e4b17023SJohn Marino { 71*e4b17023SJohn Marino _Map_pointer __cur; 72*e4b17023SJohn Marino __try 73*e4b17023SJohn Marino { 74*e4b17023SJohn Marino for (__cur = this->_M_impl._M_start._M_node; 75*e4b17023SJohn Marino __cur < this->_M_impl._M_finish._M_node; 76*e4b17023SJohn Marino ++__cur) 77*e4b17023SJohn Marino std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(), 78*e4b17023SJohn Marino _M_get_Tp_allocator()); 79*e4b17023SJohn Marino std::__uninitialized_default_a(this->_M_impl._M_finish._M_first, 80*e4b17023SJohn Marino this->_M_impl._M_finish._M_cur, 81*e4b17023SJohn Marino _M_get_Tp_allocator()); 82*e4b17023SJohn Marino } 83*e4b17023SJohn Marino __catch(...) 84*e4b17023SJohn Marino { 85*e4b17023SJohn Marino std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), 86*e4b17023SJohn Marino _M_get_Tp_allocator()); 87*e4b17023SJohn Marino __throw_exception_again; 88*e4b17023SJohn Marino } 89*e4b17023SJohn Marino } 90*e4b17023SJohn Marino #endif 91*e4b17023SJohn Marino 92*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 93*e4b17023SJohn Marino deque<_Tp, _Alloc>& 94*e4b17023SJohn Marino deque<_Tp, _Alloc>:: operator =(const deque & __x)95*e4b17023SJohn Marino operator=(const deque& __x) 96*e4b17023SJohn Marino { 97*e4b17023SJohn Marino const size_type __len = size(); 98*e4b17023SJohn Marino if (&__x != this) 99*e4b17023SJohn Marino { 100*e4b17023SJohn Marino if (__len >= __x.size()) 101*e4b17023SJohn Marino _M_erase_at_end(std::copy(__x.begin(), __x.end(), 102*e4b17023SJohn Marino this->_M_impl._M_start)); 103*e4b17023SJohn Marino else 104*e4b17023SJohn Marino { 105*e4b17023SJohn Marino const_iterator __mid = __x.begin() + difference_type(__len); 106*e4b17023SJohn Marino std::copy(__x.begin(), __mid, this->_M_impl._M_start); 107*e4b17023SJohn Marino insert(this->_M_impl._M_finish, __mid, __x.end()); 108*e4b17023SJohn Marino } 109*e4b17023SJohn Marino } 110*e4b17023SJohn Marino return *this; 111*e4b17023SJohn Marino } 112*e4b17023SJohn Marino 113*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__ 114*e4b17023SJohn Marino template<typename _Tp, typename _Alloc> 115*e4b17023SJohn Marino template<typename... _Args> 116*e4b17023SJohn Marino void 117*e4b17023SJohn Marino deque<_Tp, _Alloc>:: emplace_front(_Args &&...__args)118*e4b17023SJohn Marino emplace_front(_Args&&... __args) 119*e4b17023SJohn Marino { 120*e4b17023SJohn Marino if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) 121*e4b17023SJohn Marino { 122*e4b17023SJohn Marino this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, 123*e4b17023SJohn Marino std::forward<_Args>(__args)...); 124*e4b17023SJohn Marino --this->_M_impl._M_start._M_cur; 125*e4b17023SJohn Marino } 126*e4b17023SJohn Marino else 127*e4b17023SJohn Marino _M_push_front_aux(std::forward<_Args>(__args)...); 128*e4b17023SJohn Marino } 129*e4b17023SJohn Marino 130*e4b17023SJohn Marino template<typename _Tp, typename _Alloc> 131*e4b17023SJohn Marino template<typename... _Args> 132*e4b17023SJohn Marino void 133*e4b17023SJohn Marino deque<_Tp, _Alloc>:: emplace_back(_Args &&...__args)134*e4b17023SJohn Marino emplace_back(_Args&&... __args) 135*e4b17023SJohn Marino { 136*e4b17023SJohn Marino if (this->_M_impl._M_finish._M_cur 137*e4b17023SJohn Marino != this->_M_impl._M_finish._M_last - 1) 138*e4b17023SJohn Marino { 139*e4b17023SJohn Marino this->_M_impl.construct(this->_M_impl._M_finish._M_cur, 140*e4b17023SJohn Marino std::forward<_Args>(__args)...); 141*e4b17023SJohn Marino ++this->_M_impl._M_finish._M_cur; 142*e4b17023SJohn Marino } 143*e4b17023SJohn Marino else 144*e4b17023SJohn Marino _M_push_back_aux(std::forward<_Args>(__args)...); 145*e4b17023SJohn Marino } 146*e4b17023SJohn Marino #endif 147*e4b17023SJohn Marino 148*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 149*e4b17023SJohn Marino typename deque<_Tp, _Alloc>::iterator 150*e4b17023SJohn Marino deque<_Tp, _Alloc>:: insert(iterator __position,const value_type & __x)151*e4b17023SJohn Marino insert(iterator __position, const value_type& __x) 152*e4b17023SJohn Marino { 153*e4b17023SJohn Marino if (__position._M_cur == this->_M_impl._M_start._M_cur) 154*e4b17023SJohn Marino { 155*e4b17023SJohn Marino push_front(__x); 156*e4b17023SJohn Marino return this->_M_impl._M_start; 157*e4b17023SJohn Marino } 158*e4b17023SJohn Marino else if (__position._M_cur == this->_M_impl._M_finish._M_cur) 159*e4b17023SJohn Marino { 160*e4b17023SJohn Marino push_back(__x); 161*e4b17023SJohn Marino iterator __tmp = this->_M_impl._M_finish; 162*e4b17023SJohn Marino --__tmp; 163*e4b17023SJohn Marino return __tmp; 164*e4b17023SJohn Marino } 165*e4b17023SJohn Marino else 166*e4b17023SJohn Marino return _M_insert_aux(__position, __x); 167*e4b17023SJohn Marino } 168*e4b17023SJohn Marino 169*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__ 170*e4b17023SJohn Marino template<typename _Tp, typename _Alloc> 171*e4b17023SJohn Marino template<typename... _Args> 172*e4b17023SJohn Marino typename deque<_Tp, _Alloc>::iterator 173*e4b17023SJohn Marino deque<_Tp, _Alloc>:: emplace(iterator __position,_Args &&...__args)174*e4b17023SJohn Marino emplace(iterator __position, _Args&&... __args) 175*e4b17023SJohn Marino { 176*e4b17023SJohn Marino if (__position._M_cur == this->_M_impl._M_start._M_cur) 177*e4b17023SJohn Marino { 178*e4b17023SJohn Marino emplace_front(std::forward<_Args>(__args)...); 179*e4b17023SJohn Marino return this->_M_impl._M_start; 180*e4b17023SJohn Marino } 181*e4b17023SJohn Marino else if (__position._M_cur == this->_M_impl._M_finish._M_cur) 182*e4b17023SJohn Marino { 183*e4b17023SJohn Marino emplace_back(std::forward<_Args>(__args)...); 184*e4b17023SJohn Marino iterator __tmp = this->_M_impl._M_finish; 185*e4b17023SJohn Marino --__tmp; 186*e4b17023SJohn Marino return __tmp; 187*e4b17023SJohn Marino } 188*e4b17023SJohn Marino else 189*e4b17023SJohn Marino return _M_insert_aux(__position, std::forward<_Args>(__args)...); 190*e4b17023SJohn Marino } 191*e4b17023SJohn Marino #endif 192*e4b17023SJohn Marino 193*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 194*e4b17023SJohn Marino typename deque<_Tp, _Alloc>::iterator 195*e4b17023SJohn Marino deque<_Tp, _Alloc>:: erase(iterator __position)196*e4b17023SJohn Marino erase(iterator __position) 197*e4b17023SJohn Marino { 198*e4b17023SJohn Marino iterator __next = __position; 199*e4b17023SJohn Marino ++__next; 200*e4b17023SJohn Marino const difference_type __index = __position - begin(); 201*e4b17023SJohn Marino if (static_cast<size_type>(__index) < (size() >> 1)) 202*e4b17023SJohn Marino { 203*e4b17023SJohn Marino if (__position != begin()) 204*e4b17023SJohn Marino _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next); 205*e4b17023SJohn Marino pop_front(); 206*e4b17023SJohn Marino } 207*e4b17023SJohn Marino else 208*e4b17023SJohn Marino { 209*e4b17023SJohn Marino if (__next != end()) 210*e4b17023SJohn Marino _GLIBCXX_MOVE3(__next, end(), __position); 211*e4b17023SJohn Marino pop_back(); 212*e4b17023SJohn Marino } 213*e4b17023SJohn Marino return begin() + __index; 214*e4b17023SJohn Marino } 215*e4b17023SJohn Marino 216*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 217*e4b17023SJohn Marino typename deque<_Tp, _Alloc>::iterator 218*e4b17023SJohn Marino deque<_Tp, _Alloc>:: erase(iterator __first,iterator __last)219*e4b17023SJohn Marino erase(iterator __first, iterator __last) 220*e4b17023SJohn Marino { 221*e4b17023SJohn Marino if (__first == __last) 222*e4b17023SJohn Marino return __first; 223*e4b17023SJohn Marino else if (__first == begin() && __last == end()) 224*e4b17023SJohn Marino { 225*e4b17023SJohn Marino clear(); 226*e4b17023SJohn Marino return end(); 227*e4b17023SJohn Marino } 228*e4b17023SJohn Marino else 229*e4b17023SJohn Marino { 230*e4b17023SJohn Marino const difference_type __n = __last - __first; 231*e4b17023SJohn Marino const difference_type __elems_before = __first - begin(); 232*e4b17023SJohn Marino if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2) 233*e4b17023SJohn Marino { 234*e4b17023SJohn Marino if (__first != begin()) 235*e4b17023SJohn Marino _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last); 236*e4b17023SJohn Marino _M_erase_at_begin(begin() + __n); 237*e4b17023SJohn Marino } 238*e4b17023SJohn Marino else 239*e4b17023SJohn Marino { 240*e4b17023SJohn Marino if (__last != end()) 241*e4b17023SJohn Marino _GLIBCXX_MOVE3(__last, end(), __first); 242*e4b17023SJohn Marino _M_erase_at_end(end() - __n); 243*e4b17023SJohn Marino } 244*e4b17023SJohn Marino return begin() + __elems_before; 245*e4b17023SJohn Marino } 246*e4b17023SJohn Marino } 247*e4b17023SJohn Marino 248*e4b17023SJohn Marino template <typename _Tp, class _Alloc> 249*e4b17023SJohn Marino template <typename _InputIterator> 250*e4b17023SJohn Marino void 251*e4b17023SJohn Marino deque<_Tp, _Alloc>:: _M_assign_aux(_InputIterator __first,_InputIterator __last,std::input_iterator_tag)252*e4b17023SJohn Marino _M_assign_aux(_InputIterator __first, _InputIterator __last, 253*e4b17023SJohn Marino std::input_iterator_tag) 254*e4b17023SJohn Marino { 255*e4b17023SJohn Marino iterator __cur = begin(); 256*e4b17023SJohn Marino for (; __first != __last && __cur != end(); ++__cur, ++__first) 257*e4b17023SJohn Marino *__cur = *__first; 258*e4b17023SJohn Marino if (__first == __last) 259*e4b17023SJohn Marino _M_erase_at_end(__cur); 260*e4b17023SJohn Marino else 261*e4b17023SJohn Marino insert(end(), __first, __last); 262*e4b17023SJohn Marino } 263*e4b17023SJohn Marino 264*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 265*e4b17023SJohn Marino void 266*e4b17023SJohn Marino deque<_Tp, _Alloc>:: _M_fill_insert(iterator __pos,size_type __n,const value_type & __x)267*e4b17023SJohn Marino _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) 268*e4b17023SJohn Marino { 269*e4b17023SJohn Marino if (__pos._M_cur == this->_M_impl._M_start._M_cur) 270*e4b17023SJohn Marino { 271*e4b17023SJohn Marino iterator __new_start = _M_reserve_elements_at_front(__n); 272*e4b17023SJohn Marino __try 273*e4b17023SJohn Marino { 274*e4b17023SJohn Marino std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start, 275*e4b17023SJohn Marino __x, _M_get_Tp_allocator()); 276*e4b17023SJohn Marino this->_M_impl._M_start = __new_start; 277*e4b17023SJohn Marino } 278*e4b17023SJohn Marino __catch(...) 279*e4b17023SJohn Marino { 280*e4b17023SJohn Marino _M_destroy_nodes(__new_start._M_node, 281*e4b17023SJohn Marino this->_M_impl._M_start._M_node); 282*e4b17023SJohn Marino __throw_exception_again; 283*e4b17023SJohn Marino } 284*e4b17023SJohn Marino } 285*e4b17023SJohn Marino else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 286*e4b17023SJohn Marino { 287*e4b17023SJohn Marino iterator __new_finish = _M_reserve_elements_at_back(__n); 288*e4b17023SJohn Marino __try 289*e4b17023SJohn Marino { 290*e4b17023SJohn Marino std::__uninitialized_fill_a(this->_M_impl._M_finish, 291*e4b17023SJohn Marino __new_finish, __x, 292*e4b17023SJohn Marino _M_get_Tp_allocator()); 293*e4b17023SJohn Marino this->_M_impl._M_finish = __new_finish; 294*e4b17023SJohn Marino } 295*e4b17023SJohn Marino __catch(...) 296*e4b17023SJohn Marino { 297*e4b17023SJohn Marino _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 298*e4b17023SJohn Marino __new_finish._M_node + 1); 299*e4b17023SJohn Marino __throw_exception_again; 300*e4b17023SJohn Marino } 301*e4b17023SJohn Marino } 302*e4b17023SJohn Marino else 303*e4b17023SJohn Marino _M_insert_aux(__pos, __n, __x); 304*e4b17023SJohn Marino } 305*e4b17023SJohn Marino 306*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__ 307*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 308*e4b17023SJohn Marino void 309*e4b17023SJohn Marino deque<_Tp, _Alloc>:: _M_default_append(size_type __n)310*e4b17023SJohn Marino _M_default_append(size_type __n) 311*e4b17023SJohn Marino { 312*e4b17023SJohn Marino if (__n) 313*e4b17023SJohn Marino { 314*e4b17023SJohn Marino iterator __new_finish = _M_reserve_elements_at_back(__n); 315*e4b17023SJohn Marino __try 316*e4b17023SJohn Marino { 317*e4b17023SJohn Marino std::__uninitialized_default_a(this->_M_impl._M_finish, 318*e4b17023SJohn Marino __new_finish, 319*e4b17023SJohn Marino _M_get_Tp_allocator()); 320*e4b17023SJohn Marino this->_M_impl._M_finish = __new_finish; 321*e4b17023SJohn Marino } 322*e4b17023SJohn Marino __catch(...) 323*e4b17023SJohn Marino { 324*e4b17023SJohn Marino _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 325*e4b17023SJohn Marino __new_finish._M_node + 1); 326*e4b17023SJohn Marino __throw_exception_again; 327*e4b17023SJohn Marino } 328*e4b17023SJohn Marino } 329*e4b17023SJohn Marino } 330*e4b17023SJohn Marino 331*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 332*e4b17023SJohn Marino bool 333*e4b17023SJohn Marino deque<_Tp, _Alloc>:: _M_shrink_to_fit()334*e4b17023SJohn Marino _M_shrink_to_fit() 335*e4b17023SJohn Marino { 336*e4b17023SJohn Marino const difference_type __front_capacity 337*e4b17023SJohn Marino = (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first); 338*e4b17023SJohn Marino if (__front_capacity == 0) 339*e4b17023SJohn Marino return false; 340*e4b17023SJohn Marino 341*e4b17023SJohn Marino const difference_type __back_capacity 342*e4b17023SJohn Marino = (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur); 343*e4b17023SJohn Marino if (__front_capacity + __back_capacity < _S_buffer_size()) 344*e4b17023SJohn Marino return false; 345*e4b17023SJohn Marino 346*e4b17023SJohn Marino return std::__shrink_to_fit_aux<deque>::_S_do_it(*this); 347*e4b17023SJohn Marino } 348*e4b17023SJohn Marino #endif 349*e4b17023SJohn Marino 350*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 351*e4b17023SJohn Marino void 352*e4b17023SJohn Marino deque<_Tp, _Alloc>:: _M_fill_initialize(const value_type & __value)353*e4b17023SJohn Marino _M_fill_initialize(const value_type& __value) 354*e4b17023SJohn Marino { 355*e4b17023SJohn Marino _Map_pointer __cur; 356*e4b17023SJohn Marino __try 357*e4b17023SJohn Marino { 358*e4b17023SJohn Marino for (__cur = this->_M_impl._M_start._M_node; 359*e4b17023SJohn Marino __cur < this->_M_impl._M_finish._M_node; 360*e4b17023SJohn Marino ++__cur) 361*e4b17023SJohn Marino std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), 362*e4b17023SJohn Marino __value, _M_get_Tp_allocator()); 363*e4b17023SJohn Marino std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, 364*e4b17023SJohn Marino this->_M_impl._M_finish._M_cur, 365*e4b17023SJohn Marino __value, _M_get_Tp_allocator()); 366*e4b17023SJohn Marino } 367*e4b17023SJohn Marino __catch(...) 368*e4b17023SJohn Marino { 369*e4b17023SJohn Marino std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), 370*e4b17023SJohn Marino _M_get_Tp_allocator()); 371*e4b17023SJohn Marino __throw_exception_again; 372*e4b17023SJohn Marino } 373*e4b17023SJohn Marino } 374*e4b17023SJohn Marino 375*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 376*e4b17023SJohn Marino template <typename _InputIterator> 377*e4b17023SJohn Marino void 378*e4b17023SJohn Marino deque<_Tp, _Alloc>:: _M_range_initialize(_InputIterator __first,_InputIterator __last,std::input_iterator_tag)379*e4b17023SJohn Marino _M_range_initialize(_InputIterator __first, _InputIterator __last, 380*e4b17023SJohn Marino std::input_iterator_tag) 381*e4b17023SJohn Marino { 382*e4b17023SJohn Marino this->_M_initialize_map(0); 383*e4b17023SJohn Marino __try 384*e4b17023SJohn Marino { 385*e4b17023SJohn Marino for (; __first != __last; ++__first) 386*e4b17023SJohn Marino push_back(*__first); 387*e4b17023SJohn Marino } 388*e4b17023SJohn Marino __catch(...) 389*e4b17023SJohn Marino { 390*e4b17023SJohn Marino clear(); 391*e4b17023SJohn Marino __throw_exception_again; 392*e4b17023SJohn Marino } 393*e4b17023SJohn Marino } 394*e4b17023SJohn Marino 395*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 396*e4b17023SJohn Marino template <typename _ForwardIterator> 397*e4b17023SJohn Marino void 398*e4b17023SJohn Marino deque<_Tp, _Alloc>:: _M_range_initialize(_ForwardIterator __first,_ForwardIterator __last,std::forward_iterator_tag)399*e4b17023SJohn Marino _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 400*e4b17023SJohn Marino std::forward_iterator_tag) 401*e4b17023SJohn Marino { 402*e4b17023SJohn Marino const size_type __n = std::distance(__first, __last); 403*e4b17023SJohn Marino this->_M_initialize_map(__n); 404*e4b17023SJohn Marino 405*e4b17023SJohn Marino _Map_pointer __cur_node; 406*e4b17023SJohn Marino __try 407*e4b17023SJohn Marino { 408*e4b17023SJohn Marino for (__cur_node = this->_M_impl._M_start._M_node; 409*e4b17023SJohn Marino __cur_node < this->_M_impl._M_finish._M_node; 410*e4b17023SJohn Marino ++__cur_node) 411*e4b17023SJohn Marino { 412*e4b17023SJohn Marino _ForwardIterator __mid = __first; 413*e4b17023SJohn Marino std::advance(__mid, _S_buffer_size()); 414*e4b17023SJohn Marino std::__uninitialized_copy_a(__first, __mid, *__cur_node, 415*e4b17023SJohn Marino _M_get_Tp_allocator()); 416*e4b17023SJohn Marino __first = __mid; 417*e4b17023SJohn Marino } 418*e4b17023SJohn Marino std::__uninitialized_copy_a(__first, __last, 419*e4b17023SJohn Marino this->_M_impl._M_finish._M_first, 420*e4b17023SJohn Marino _M_get_Tp_allocator()); 421*e4b17023SJohn Marino } 422*e4b17023SJohn Marino __catch(...) 423*e4b17023SJohn Marino { 424*e4b17023SJohn Marino std::_Destroy(this->_M_impl._M_start, 425*e4b17023SJohn Marino iterator(*__cur_node, __cur_node), 426*e4b17023SJohn Marino _M_get_Tp_allocator()); 427*e4b17023SJohn Marino __throw_exception_again; 428*e4b17023SJohn Marino } 429*e4b17023SJohn Marino } 430*e4b17023SJohn Marino 431*e4b17023SJohn Marino // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. 432*e4b17023SJohn Marino template<typename _Tp, typename _Alloc> 433*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__ 434*e4b17023SJohn Marino template<typename... _Args> 435*e4b17023SJohn Marino void 436*e4b17023SJohn Marino deque<_Tp, _Alloc>:: _M_push_back_aux(_Args &&...__args)437*e4b17023SJohn Marino _M_push_back_aux(_Args&&... __args) 438*e4b17023SJohn Marino #else 439*e4b17023SJohn Marino void 440*e4b17023SJohn Marino deque<_Tp, _Alloc>:: 441*e4b17023SJohn Marino _M_push_back_aux(const value_type& __t) 442*e4b17023SJohn Marino #endif 443*e4b17023SJohn Marino { 444*e4b17023SJohn Marino _M_reserve_map_at_back(); 445*e4b17023SJohn Marino *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); 446*e4b17023SJohn Marino __try 447*e4b17023SJohn Marino { 448*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__ 449*e4b17023SJohn Marino this->_M_impl.construct(this->_M_impl._M_finish._M_cur, 450*e4b17023SJohn Marino std::forward<_Args>(__args)...); 451*e4b17023SJohn Marino #else 452*e4b17023SJohn Marino this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t); 453*e4b17023SJohn Marino #endif 454*e4b17023SJohn Marino this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node 455*e4b17023SJohn Marino + 1); 456*e4b17023SJohn Marino this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; 457*e4b17023SJohn Marino } 458*e4b17023SJohn Marino __catch(...) 459*e4b17023SJohn Marino { 460*e4b17023SJohn Marino _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); 461*e4b17023SJohn Marino __throw_exception_again; 462*e4b17023SJohn Marino } 463*e4b17023SJohn Marino } 464*e4b17023SJohn Marino 465*e4b17023SJohn Marino // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. 466*e4b17023SJohn Marino template<typename _Tp, typename _Alloc> 467*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__ 468*e4b17023SJohn Marino template<typename... _Args> 469*e4b17023SJohn Marino void 470*e4b17023SJohn Marino deque<_Tp, _Alloc>:: _M_push_front_aux(_Args &&...__args)471*e4b17023SJohn Marino _M_push_front_aux(_Args&&... __args) 472*e4b17023SJohn Marino #else 473*e4b17023SJohn Marino void 474*e4b17023SJohn Marino deque<_Tp, _Alloc>:: 475*e4b17023SJohn Marino _M_push_front_aux(const value_type& __t) 476*e4b17023SJohn Marino #endif 477*e4b17023SJohn Marino { 478*e4b17023SJohn Marino _M_reserve_map_at_front(); 479*e4b17023SJohn Marino *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); 480*e4b17023SJohn Marino __try 481*e4b17023SJohn Marino { 482*e4b17023SJohn Marino this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node 483*e4b17023SJohn Marino - 1); 484*e4b17023SJohn Marino this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; 485*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__ 486*e4b17023SJohn Marino this->_M_impl.construct(this->_M_impl._M_start._M_cur, 487*e4b17023SJohn Marino std::forward<_Args>(__args)...); 488*e4b17023SJohn Marino #else 489*e4b17023SJohn Marino this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t); 490*e4b17023SJohn Marino #endif 491*e4b17023SJohn Marino } 492*e4b17023SJohn Marino __catch(...) 493*e4b17023SJohn Marino { 494*e4b17023SJohn Marino ++this->_M_impl._M_start; 495*e4b17023SJohn Marino _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); 496*e4b17023SJohn Marino __throw_exception_again; 497*e4b17023SJohn Marino } 498*e4b17023SJohn Marino } 499*e4b17023SJohn Marino 500*e4b17023SJohn Marino // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. 501*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 502*e4b17023SJohn Marino void deque<_Tp, _Alloc>:: _M_pop_back_aux()503*e4b17023SJohn Marino _M_pop_back_aux() 504*e4b17023SJohn Marino { 505*e4b17023SJohn Marino _M_deallocate_node(this->_M_impl._M_finish._M_first); 506*e4b17023SJohn Marino this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); 507*e4b17023SJohn Marino this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; 508*e4b17023SJohn Marino this->_M_impl.destroy(this->_M_impl._M_finish._M_cur); 509*e4b17023SJohn Marino } 510*e4b17023SJohn Marino 511*e4b17023SJohn Marino // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. 512*e4b17023SJohn Marino // Note that if the deque has at least one element (a precondition for this 513*e4b17023SJohn Marino // member function), and if 514*e4b17023SJohn Marino // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, 515*e4b17023SJohn Marino // then the deque must have at least two nodes. 516*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 517*e4b17023SJohn Marino void deque<_Tp, _Alloc>:: _M_pop_front_aux()518*e4b17023SJohn Marino _M_pop_front_aux() 519*e4b17023SJohn Marino { 520*e4b17023SJohn Marino this->_M_impl.destroy(this->_M_impl._M_start._M_cur); 521*e4b17023SJohn Marino _M_deallocate_node(this->_M_impl._M_start._M_first); 522*e4b17023SJohn Marino this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); 523*e4b17023SJohn Marino this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; 524*e4b17023SJohn Marino } 525*e4b17023SJohn Marino 526*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 527*e4b17023SJohn Marino template <typename _InputIterator> 528*e4b17023SJohn Marino void 529*e4b17023SJohn Marino deque<_Tp, _Alloc>:: _M_range_insert_aux(iterator __pos,_InputIterator __first,_InputIterator __last,std::input_iterator_tag)530*e4b17023SJohn Marino _M_range_insert_aux(iterator __pos, 531*e4b17023SJohn Marino _InputIterator __first, _InputIterator __last, 532*e4b17023SJohn Marino std::input_iterator_tag) 533*e4b17023SJohn Marino { std::copy(__first, __last, std::inserter(*this, __pos)); } 534*e4b17023SJohn Marino 535*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 536*e4b17023SJohn Marino template <typename _ForwardIterator> 537*e4b17023SJohn Marino void 538*e4b17023SJohn Marino deque<_Tp, _Alloc>:: _M_range_insert_aux(iterator __pos,_ForwardIterator __first,_ForwardIterator __last,std::forward_iterator_tag)539*e4b17023SJohn Marino _M_range_insert_aux(iterator __pos, 540*e4b17023SJohn Marino _ForwardIterator __first, _ForwardIterator __last, 541*e4b17023SJohn Marino std::forward_iterator_tag) 542*e4b17023SJohn Marino { 543*e4b17023SJohn Marino const size_type __n = std::distance(__first, __last); 544*e4b17023SJohn Marino if (__pos._M_cur == this->_M_impl._M_start._M_cur) 545*e4b17023SJohn Marino { 546*e4b17023SJohn Marino iterator __new_start = _M_reserve_elements_at_front(__n); 547*e4b17023SJohn Marino __try 548*e4b17023SJohn Marino { 549*e4b17023SJohn Marino std::__uninitialized_copy_a(__first, __last, __new_start, 550*e4b17023SJohn Marino _M_get_Tp_allocator()); 551*e4b17023SJohn Marino this->_M_impl._M_start = __new_start; 552*e4b17023SJohn Marino } 553*e4b17023SJohn Marino __catch(...) 554*e4b17023SJohn Marino { 555*e4b17023SJohn Marino _M_destroy_nodes(__new_start._M_node, 556*e4b17023SJohn Marino this->_M_impl._M_start._M_node); 557*e4b17023SJohn Marino __throw_exception_again; 558*e4b17023SJohn Marino } 559*e4b17023SJohn Marino } 560*e4b17023SJohn Marino else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 561*e4b17023SJohn Marino { 562*e4b17023SJohn Marino iterator __new_finish = _M_reserve_elements_at_back(__n); 563*e4b17023SJohn Marino __try 564*e4b17023SJohn Marino { 565*e4b17023SJohn Marino std::__uninitialized_copy_a(__first, __last, 566*e4b17023SJohn Marino this->_M_impl._M_finish, 567*e4b17023SJohn Marino _M_get_Tp_allocator()); 568*e4b17023SJohn Marino this->_M_impl._M_finish = __new_finish; 569*e4b17023SJohn Marino } 570*e4b17023SJohn Marino __catch(...) 571*e4b17023SJohn Marino { 572*e4b17023SJohn Marino _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 573*e4b17023SJohn Marino __new_finish._M_node + 1); 574*e4b17023SJohn Marino __throw_exception_again; 575*e4b17023SJohn Marino } 576*e4b17023SJohn Marino } 577*e4b17023SJohn Marino else 578*e4b17023SJohn Marino _M_insert_aux(__pos, __first, __last, __n); 579*e4b17023SJohn Marino } 580*e4b17023SJohn Marino 581*e4b17023SJohn Marino template<typename _Tp, typename _Alloc> 582*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__ 583*e4b17023SJohn Marino template<typename... _Args> 584*e4b17023SJohn Marino typename deque<_Tp, _Alloc>::iterator 585*e4b17023SJohn Marino deque<_Tp, _Alloc>:: _M_insert_aux(iterator __pos,_Args &&...__args)586*e4b17023SJohn Marino _M_insert_aux(iterator __pos, _Args&&... __args) 587*e4b17023SJohn Marino { 588*e4b17023SJohn Marino value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy 589*e4b17023SJohn Marino #else 590*e4b17023SJohn Marino typename deque<_Tp, _Alloc>::iterator 591*e4b17023SJohn Marino deque<_Tp, _Alloc>:: 592*e4b17023SJohn Marino _M_insert_aux(iterator __pos, const value_type& __x) 593*e4b17023SJohn Marino { 594*e4b17023SJohn Marino value_type __x_copy = __x; // XXX copy 595*e4b17023SJohn Marino #endif 596*e4b17023SJohn Marino difference_type __index = __pos - this->_M_impl._M_start; 597*e4b17023SJohn Marino if (static_cast<size_type>(__index) < size() / 2) 598*e4b17023SJohn Marino { 599*e4b17023SJohn Marino push_front(_GLIBCXX_MOVE(front())); 600*e4b17023SJohn Marino iterator __front1 = this->_M_impl._M_start; 601*e4b17023SJohn Marino ++__front1; 602*e4b17023SJohn Marino iterator __front2 = __front1; 603*e4b17023SJohn Marino ++__front2; 604*e4b17023SJohn Marino __pos = this->_M_impl._M_start + __index; 605*e4b17023SJohn Marino iterator __pos1 = __pos; 606*e4b17023SJohn Marino ++__pos1; 607*e4b17023SJohn Marino _GLIBCXX_MOVE3(__front2, __pos1, __front1); 608*e4b17023SJohn Marino } 609*e4b17023SJohn Marino else 610*e4b17023SJohn Marino { 611*e4b17023SJohn Marino push_back(_GLIBCXX_MOVE(back())); 612*e4b17023SJohn Marino iterator __back1 = this->_M_impl._M_finish; 613*e4b17023SJohn Marino --__back1; 614*e4b17023SJohn Marino iterator __back2 = __back1; 615*e4b17023SJohn Marino --__back2; 616*e4b17023SJohn Marino __pos = this->_M_impl._M_start + __index; 617*e4b17023SJohn Marino _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1); 618*e4b17023SJohn Marino } 619*e4b17023SJohn Marino *__pos = _GLIBCXX_MOVE(__x_copy); 620*e4b17023SJohn Marino return __pos; 621*e4b17023SJohn Marino } 622*e4b17023SJohn Marino 623*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 624*e4b17023SJohn Marino void 625*e4b17023SJohn Marino deque<_Tp, _Alloc>:: 626*e4b17023SJohn Marino _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) 627*e4b17023SJohn Marino { 628*e4b17023SJohn Marino const difference_type __elems_before = __pos - this->_M_impl._M_start; 629*e4b17023SJohn Marino const size_type __length = this->size(); 630*e4b17023SJohn Marino value_type __x_copy = __x; 631*e4b17023SJohn Marino if (__elems_before < difference_type(__length / 2)) 632*e4b17023SJohn Marino { 633*e4b17023SJohn Marino iterator __new_start = _M_reserve_elements_at_front(__n); 634*e4b17023SJohn Marino iterator __old_start = this->_M_impl._M_start; 635*e4b17023SJohn Marino __pos = this->_M_impl._M_start + __elems_before; 636*e4b17023SJohn Marino __try 637*e4b17023SJohn Marino { 638*e4b17023SJohn Marino if (__elems_before >= difference_type(__n)) 639*e4b17023SJohn Marino { 640*e4b17023SJohn Marino iterator __start_n = (this->_M_impl._M_start 641*e4b17023SJohn Marino + difference_type(__n)); 642*e4b17023SJohn Marino std::__uninitialized_move_a(this->_M_impl._M_start, 643*e4b17023SJohn Marino __start_n, __new_start, 644*e4b17023SJohn Marino _M_get_Tp_allocator()); 645*e4b17023SJohn Marino this->_M_impl._M_start = __new_start; 646*e4b17023SJohn Marino _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 647*e4b17023SJohn Marino std::fill(__pos - difference_type(__n), __pos, __x_copy); 648*e4b17023SJohn Marino } 649*e4b17023SJohn Marino else 650*e4b17023SJohn Marino { 651*e4b17023SJohn Marino std::__uninitialized_move_fill(this->_M_impl._M_start, 652*e4b17023SJohn Marino __pos, __new_start, 653*e4b17023SJohn Marino this->_M_impl._M_start, 654*e4b17023SJohn Marino __x_copy, 655*e4b17023SJohn Marino _M_get_Tp_allocator()); 656*e4b17023SJohn Marino this->_M_impl._M_start = __new_start; 657*e4b17023SJohn Marino std::fill(__old_start, __pos, __x_copy); 658*e4b17023SJohn Marino } 659*e4b17023SJohn Marino } 660*e4b17023SJohn Marino __catch(...) 661*e4b17023SJohn Marino { 662*e4b17023SJohn Marino _M_destroy_nodes(__new_start._M_node, 663*e4b17023SJohn Marino this->_M_impl._M_start._M_node); 664*e4b17023SJohn Marino __throw_exception_again; 665*e4b17023SJohn Marino } 666*e4b17023SJohn Marino } 667*e4b17023SJohn Marino else 668*e4b17023SJohn Marino { 669*e4b17023SJohn Marino iterator __new_finish = _M_reserve_elements_at_back(__n); 670*e4b17023SJohn Marino iterator __old_finish = this->_M_impl._M_finish; 671*e4b17023SJohn Marino const difference_type __elems_after = 672*e4b17023SJohn Marino difference_type(__length) - __elems_before; 673*e4b17023SJohn Marino __pos = this->_M_impl._M_finish - __elems_after; 674*e4b17023SJohn Marino __try 675*e4b17023SJohn Marino { 676*e4b17023SJohn Marino if (__elems_after > difference_type(__n)) 677*e4b17023SJohn Marino { 678*e4b17023SJohn Marino iterator __finish_n = (this->_M_impl._M_finish 679*e4b17023SJohn Marino - difference_type(__n)); 680*e4b17023SJohn Marino std::__uninitialized_move_a(__finish_n, 681*e4b17023SJohn Marino this->_M_impl._M_finish, 682*e4b17023SJohn Marino this->_M_impl._M_finish, 683*e4b17023SJohn Marino _M_get_Tp_allocator()); 684*e4b17023SJohn Marino this->_M_impl._M_finish = __new_finish; 685*e4b17023SJohn Marino _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 686*e4b17023SJohn Marino std::fill(__pos, __pos + difference_type(__n), __x_copy); 687*e4b17023SJohn Marino } 688*e4b17023SJohn Marino else 689*e4b17023SJohn Marino { 690*e4b17023SJohn Marino std::__uninitialized_fill_move(this->_M_impl._M_finish, 691*e4b17023SJohn Marino __pos + difference_type(__n), 692*e4b17023SJohn Marino __x_copy, __pos, 693*e4b17023SJohn Marino this->_M_impl._M_finish, 694*e4b17023SJohn Marino _M_get_Tp_allocator()); 695*e4b17023SJohn Marino this->_M_impl._M_finish = __new_finish; 696*e4b17023SJohn Marino std::fill(__pos, __old_finish, __x_copy); 697*e4b17023SJohn Marino } 698*e4b17023SJohn Marino } 699*e4b17023SJohn Marino __catch(...) 700*e4b17023SJohn Marino { 701*e4b17023SJohn Marino _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 702*e4b17023SJohn Marino __new_finish._M_node + 1); 703*e4b17023SJohn Marino __throw_exception_again; 704*e4b17023SJohn Marino } 705*e4b17023SJohn Marino } 706*e4b17023SJohn Marino } 707*e4b17023SJohn Marino 708*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 709*e4b17023SJohn Marino template <typename _ForwardIterator> 710*e4b17023SJohn Marino void 711*e4b17023SJohn Marino deque<_Tp, _Alloc>:: 712*e4b17023SJohn Marino _M_insert_aux(iterator __pos, 713*e4b17023SJohn Marino _ForwardIterator __first, _ForwardIterator __last, 714*e4b17023SJohn Marino size_type __n) 715*e4b17023SJohn Marino { 716*e4b17023SJohn Marino const difference_type __elemsbefore = __pos - this->_M_impl._M_start; 717*e4b17023SJohn Marino const size_type __length = size(); 718*e4b17023SJohn Marino if (static_cast<size_type>(__elemsbefore) < __length / 2) 719*e4b17023SJohn Marino { 720*e4b17023SJohn Marino iterator __new_start = _M_reserve_elements_at_front(__n); 721*e4b17023SJohn Marino iterator __old_start = this->_M_impl._M_start; 722*e4b17023SJohn Marino __pos = this->_M_impl._M_start + __elemsbefore; 723*e4b17023SJohn Marino __try 724*e4b17023SJohn Marino { 725*e4b17023SJohn Marino if (__elemsbefore >= difference_type(__n)) 726*e4b17023SJohn Marino { 727*e4b17023SJohn Marino iterator __start_n = (this->_M_impl._M_start 728*e4b17023SJohn Marino + difference_type(__n)); 729*e4b17023SJohn Marino std::__uninitialized_move_a(this->_M_impl._M_start, 730*e4b17023SJohn Marino __start_n, __new_start, 731*e4b17023SJohn Marino _M_get_Tp_allocator()); 732*e4b17023SJohn Marino this->_M_impl._M_start = __new_start; 733*e4b17023SJohn Marino _GLIBCXX_MOVE3(__start_n, __pos, __old_start); 734*e4b17023SJohn Marino std::copy(__first, __last, __pos - difference_type(__n)); 735*e4b17023SJohn Marino } 736*e4b17023SJohn Marino else 737*e4b17023SJohn Marino { 738*e4b17023SJohn Marino _ForwardIterator __mid = __first; 739*e4b17023SJohn Marino std::advance(__mid, difference_type(__n) - __elemsbefore); 740*e4b17023SJohn Marino std::__uninitialized_move_copy(this->_M_impl._M_start, 741*e4b17023SJohn Marino __pos, __first, __mid, 742*e4b17023SJohn Marino __new_start, 743*e4b17023SJohn Marino _M_get_Tp_allocator()); 744*e4b17023SJohn Marino this->_M_impl._M_start = __new_start; 745*e4b17023SJohn Marino std::copy(__mid, __last, __old_start); 746*e4b17023SJohn Marino } 747*e4b17023SJohn Marino } 748*e4b17023SJohn Marino __catch(...) 749*e4b17023SJohn Marino { 750*e4b17023SJohn Marino _M_destroy_nodes(__new_start._M_node, 751*e4b17023SJohn Marino this->_M_impl._M_start._M_node); 752*e4b17023SJohn Marino __throw_exception_again; 753*e4b17023SJohn Marino } 754*e4b17023SJohn Marino } 755*e4b17023SJohn Marino else 756*e4b17023SJohn Marino { 757*e4b17023SJohn Marino iterator __new_finish = _M_reserve_elements_at_back(__n); 758*e4b17023SJohn Marino iterator __old_finish = this->_M_impl._M_finish; 759*e4b17023SJohn Marino const difference_type __elemsafter = 760*e4b17023SJohn Marino difference_type(__length) - __elemsbefore; 761*e4b17023SJohn Marino __pos = this->_M_impl._M_finish - __elemsafter; 762*e4b17023SJohn Marino __try 763*e4b17023SJohn Marino { 764*e4b17023SJohn Marino if (__elemsafter > difference_type(__n)) 765*e4b17023SJohn Marino { 766*e4b17023SJohn Marino iterator __finish_n = (this->_M_impl._M_finish 767*e4b17023SJohn Marino - difference_type(__n)); 768*e4b17023SJohn Marino std::__uninitialized_move_a(__finish_n, 769*e4b17023SJohn Marino this->_M_impl._M_finish, 770*e4b17023SJohn Marino this->_M_impl._M_finish, 771*e4b17023SJohn Marino _M_get_Tp_allocator()); 772*e4b17023SJohn Marino this->_M_impl._M_finish = __new_finish; 773*e4b17023SJohn Marino _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); 774*e4b17023SJohn Marino std::copy(__first, __last, __pos); 775*e4b17023SJohn Marino } 776*e4b17023SJohn Marino else 777*e4b17023SJohn Marino { 778*e4b17023SJohn Marino _ForwardIterator __mid = __first; 779*e4b17023SJohn Marino std::advance(__mid, __elemsafter); 780*e4b17023SJohn Marino std::__uninitialized_copy_move(__mid, __last, __pos, 781*e4b17023SJohn Marino this->_M_impl._M_finish, 782*e4b17023SJohn Marino this->_M_impl._M_finish, 783*e4b17023SJohn Marino _M_get_Tp_allocator()); 784*e4b17023SJohn Marino this->_M_impl._M_finish = __new_finish; 785*e4b17023SJohn Marino std::copy(__first, __mid, __pos); 786*e4b17023SJohn Marino } 787*e4b17023SJohn Marino } 788*e4b17023SJohn Marino __catch(...) 789*e4b17023SJohn Marino { 790*e4b17023SJohn Marino _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 791*e4b17023SJohn Marino __new_finish._M_node + 1); 792*e4b17023SJohn Marino __throw_exception_again; 793*e4b17023SJohn Marino } 794*e4b17023SJohn Marino } 795*e4b17023SJohn Marino } 796*e4b17023SJohn Marino 797*e4b17023SJohn Marino template<typename _Tp, typename _Alloc> 798*e4b17023SJohn Marino void 799*e4b17023SJohn Marino deque<_Tp, _Alloc>:: 800*e4b17023SJohn Marino _M_destroy_data_aux(iterator __first, iterator __last) 801*e4b17023SJohn Marino { 802*e4b17023SJohn Marino for (_Map_pointer __node = __first._M_node + 1; 803*e4b17023SJohn Marino __node < __last._M_node; ++__node) 804*e4b17023SJohn Marino std::_Destroy(*__node, *__node + _S_buffer_size(), 805*e4b17023SJohn Marino _M_get_Tp_allocator()); 806*e4b17023SJohn Marino 807*e4b17023SJohn Marino if (__first._M_node != __last._M_node) 808*e4b17023SJohn Marino { 809*e4b17023SJohn Marino std::_Destroy(__first._M_cur, __first._M_last, 810*e4b17023SJohn Marino _M_get_Tp_allocator()); 811*e4b17023SJohn Marino std::_Destroy(__last._M_first, __last._M_cur, 812*e4b17023SJohn Marino _M_get_Tp_allocator()); 813*e4b17023SJohn Marino } 814*e4b17023SJohn Marino else 815*e4b17023SJohn Marino std::_Destroy(__first._M_cur, __last._M_cur, 816*e4b17023SJohn Marino _M_get_Tp_allocator()); 817*e4b17023SJohn Marino } 818*e4b17023SJohn Marino 819*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 820*e4b17023SJohn Marino void 821*e4b17023SJohn Marino deque<_Tp, _Alloc>:: 822*e4b17023SJohn Marino _M_new_elements_at_front(size_type __new_elems) 823*e4b17023SJohn Marino { 824*e4b17023SJohn Marino if (this->max_size() - this->size() < __new_elems) 825*e4b17023SJohn Marino __throw_length_error(__N("deque::_M_new_elements_at_front")); 826*e4b17023SJohn Marino 827*e4b17023SJohn Marino const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 828*e4b17023SJohn Marino / _S_buffer_size()); 829*e4b17023SJohn Marino _M_reserve_map_at_front(__new_nodes); 830*e4b17023SJohn Marino size_type __i; 831*e4b17023SJohn Marino __try 832*e4b17023SJohn Marino { 833*e4b17023SJohn Marino for (__i = 1; __i <= __new_nodes; ++__i) 834*e4b17023SJohn Marino *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); 835*e4b17023SJohn Marino } 836*e4b17023SJohn Marino __catch(...) 837*e4b17023SJohn Marino { 838*e4b17023SJohn Marino for (size_type __j = 1; __j < __i; ++__j) 839*e4b17023SJohn Marino _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); 840*e4b17023SJohn Marino __throw_exception_again; 841*e4b17023SJohn Marino } 842*e4b17023SJohn Marino } 843*e4b17023SJohn Marino 844*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 845*e4b17023SJohn Marino void 846*e4b17023SJohn Marino deque<_Tp, _Alloc>:: 847*e4b17023SJohn Marino _M_new_elements_at_back(size_type __new_elems) 848*e4b17023SJohn Marino { 849*e4b17023SJohn Marino if (this->max_size() - this->size() < __new_elems) 850*e4b17023SJohn Marino __throw_length_error(__N("deque::_M_new_elements_at_back")); 851*e4b17023SJohn Marino 852*e4b17023SJohn Marino const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 853*e4b17023SJohn Marino / _S_buffer_size()); 854*e4b17023SJohn Marino _M_reserve_map_at_back(__new_nodes); 855*e4b17023SJohn Marino size_type __i; 856*e4b17023SJohn Marino __try 857*e4b17023SJohn Marino { 858*e4b17023SJohn Marino for (__i = 1; __i <= __new_nodes; ++__i) 859*e4b17023SJohn Marino *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); 860*e4b17023SJohn Marino } 861*e4b17023SJohn Marino __catch(...) 862*e4b17023SJohn Marino { 863*e4b17023SJohn Marino for (size_type __j = 1; __j < __i; ++__j) 864*e4b17023SJohn Marino _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); 865*e4b17023SJohn Marino __throw_exception_again; 866*e4b17023SJohn Marino } 867*e4b17023SJohn Marino } 868*e4b17023SJohn Marino 869*e4b17023SJohn Marino template <typename _Tp, typename _Alloc> 870*e4b17023SJohn Marino void 871*e4b17023SJohn Marino deque<_Tp, _Alloc>:: 872*e4b17023SJohn Marino _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) 873*e4b17023SJohn Marino { 874*e4b17023SJohn Marino const size_type __old_num_nodes 875*e4b17023SJohn Marino = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; 876*e4b17023SJohn Marino const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 877*e4b17023SJohn Marino 878*e4b17023SJohn Marino _Map_pointer __new_nstart; 879*e4b17023SJohn Marino if (this->_M_impl._M_map_size > 2 * __new_num_nodes) 880*e4b17023SJohn Marino { 881*e4b17023SJohn Marino __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size 882*e4b17023SJohn Marino - __new_num_nodes) / 2 883*e4b17023SJohn Marino + (__add_at_front ? __nodes_to_add : 0); 884*e4b17023SJohn Marino if (__new_nstart < this->_M_impl._M_start._M_node) 885*e4b17023SJohn Marino std::copy(this->_M_impl._M_start._M_node, 886*e4b17023SJohn Marino this->_M_impl._M_finish._M_node + 1, 887*e4b17023SJohn Marino __new_nstart); 888*e4b17023SJohn Marino else 889*e4b17023SJohn Marino std::copy_backward(this->_M_impl._M_start._M_node, 890*e4b17023SJohn Marino this->_M_impl._M_finish._M_node + 1, 891*e4b17023SJohn Marino __new_nstart + __old_num_nodes); 892*e4b17023SJohn Marino } 893*e4b17023SJohn Marino else 894*e4b17023SJohn Marino { 895*e4b17023SJohn Marino size_type __new_map_size = this->_M_impl._M_map_size 896*e4b17023SJohn Marino + std::max(this->_M_impl._M_map_size, 897*e4b17023SJohn Marino __nodes_to_add) + 2; 898*e4b17023SJohn Marino 899*e4b17023SJohn Marino _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); 900*e4b17023SJohn Marino __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 901*e4b17023SJohn Marino + (__add_at_front ? __nodes_to_add : 0); 902*e4b17023SJohn Marino std::copy(this->_M_impl._M_start._M_node, 903*e4b17023SJohn Marino this->_M_impl._M_finish._M_node + 1, 904*e4b17023SJohn Marino __new_nstart); 905*e4b17023SJohn Marino _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 906*e4b17023SJohn Marino 907*e4b17023SJohn Marino this->_M_impl._M_map = __new_map; 908*e4b17023SJohn Marino this->_M_impl._M_map_size = __new_map_size; 909*e4b17023SJohn Marino } 910*e4b17023SJohn Marino 911*e4b17023SJohn Marino this->_M_impl._M_start._M_set_node(__new_nstart); 912*e4b17023SJohn Marino this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 913*e4b17023SJohn Marino } 914*e4b17023SJohn Marino 915*e4b17023SJohn Marino // Overload for deque::iterators, exploiting the "segmented-iterator 916*e4b17023SJohn Marino // optimization". 917*e4b17023SJohn Marino template<typename _Tp> 918*e4b17023SJohn Marino void 919*e4b17023SJohn Marino fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, 920*e4b17023SJohn Marino const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value) 921*e4b17023SJohn Marino { 922*e4b17023SJohn Marino typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 923*e4b17023SJohn Marino 924*e4b17023SJohn Marino for (typename _Self::_Map_pointer __node = __first._M_node + 1; 925*e4b17023SJohn Marino __node < __last._M_node; ++__node) 926*e4b17023SJohn Marino std::fill(*__node, *__node + _Self::_S_buffer_size(), __value); 927*e4b17023SJohn Marino 928*e4b17023SJohn Marino if (__first._M_node != __last._M_node) 929*e4b17023SJohn Marino { 930*e4b17023SJohn Marino std::fill(__first._M_cur, __first._M_last, __value); 931*e4b17023SJohn Marino std::fill(__last._M_first, __last._M_cur, __value); 932*e4b17023SJohn Marino } 933*e4b17023SJohn Marino else 934*e4b17023SJohn Marino std::fill(__first._M_cur, __last._M_cur, __value); 935*e4b17023SJohn Marino } 936*e4b17023SJohn Marino 937*e4b17023SJohn Marino template<typename _Tp> 938*e4b17023SJohn Marino _Deque_iterator<_Tp, _Tp&, _Tp*> 939*e4b17023SJohn Marino copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 940*e4b17023SJohn Marino _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 941*e4b17023SJohn Marino _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 942*e4b17023SJohn Marino { 943*e4b17023SJohn Marino typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 944*e4b17023SJohn Marino typedef typename _Self::difference_type difference_type; 945*e4b17023SJohn Marino 946*e4b17023SJohn Marino difference_type __len = __last - __first; 947*e4b17023SJohn Marino while (__len > 0) 948*e4b17023SJohn Marino { 949*e4b17023SJohn Marino const difference_type __clen 950*e4b17023SJohn Marino = std::min(__len, std::min(__first._M_last - __first._M_cur, 951*e4b17023SJohn Marino __result._M_last - __result._M_cur)); 952*e4b17023SJohn Marino std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur); 953*e4b17023SJohn Marino __first += __clen; 954*e4b17023SJohn Marino __result += __clen; 955*e4b17023SJohn Marino __len -= __clen; 956*e4b17023SJohn Marino } 957*e4b17023SJohn Marino return __result; 958*e4b17023SJohn Marino } 959*e4b17023SJohn Marino 960*e4b17023SJohn Marino template<typename _Tp> 961*e4b17023SJohn Marino _Deque_iterator<_Tp, _Tp&, _Tp*> 962*e4b17023SJohn Marino copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 963*e4b17023SJohn Marino _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 964*e4b17023SJohn Marino _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 965*e4b17023SJohn Marino { 966*e4b17023SJohn Marino typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 967*e4b17023SJohn Marino typedef typename _Self::difference_type difference_type; 968*e4b17023SJohn Marino 969*e4b17023SJohn Marino difference_type __len = __last - __first; 970*e4b17023SJohn Marino while (__len > 0) 971*e4b17023SJohn Marino { 972*e4b17023SJohn Marino difference_type __llen = __last._M_cur - __last._M_first; 973*e4b17023SJohn Marino _Tp* __lend = __last._M_cur; 974*e4b17023SJohn Marino 975*e4b17023SJohn Marino difference_type __rlen = __result._M_cur - __result._M_first; 976*e4b17023SJohn Marino _Tp* __rend = __result._M_cur; 977*e4b17023SJohn Marino 978*e4b17023SJohn Marino if (!__llen) 979*e4b17023SJohn Marino { 980*e4b17023SJohn Marino __llen = _Self::_S_buffer_size(); 981*e4b17023SJohn Marino __lend = *(__last._M_node - 1) + __llen; 982*e4b17023SJohn Marino } 983*e4b17023SJohn Marino if (!__rlen) 984*e4b17023SJohn Marino { 985*e4b17023SJohn Marino __rlen = _Self::_S_buffer_size(); 986*e4b17023SJohn Marino __rend = *(__result._M_node - 1) + __rlen; 987*e4b17023SJohn Marino } 988*e4b17023SJohn Marino 989*e4b17023SJohn Marino const difference_type __clen = std::min(__len, 990*e4b17023SJohn Marino std::min(__llen, __rlen)); 991*e4b17023SJohn Marino std::copy_backward(__lend - __clen, __lend, __rend); 992*e4b17023SJohn Marino __last -= __clen; 993*e4b17023SJohn Marino __result -= __clen; 994*e4b17023SJohn Marino __len -= __clen; 995*e4b17023SJohn Marino } 996*e4b17023SJohn Marino return __result; 997*e4b17023SJohn Marino } 998*e4b17023SJohn Marino 999*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__ 1000*e4b17023SJohn Marino template<typename _Tp> 1001*e4b17023SJohn Marino _Deque_iterator<_Tp, _Tp&, _Tp*> 1002*e4b17023SJohn Marino move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 1003*e4b17023SJohn Marino _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 1004*e4b17023SJohn Marino _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 1005*e4b17023SJohn Marino { 1006*e4b17023SJohn Marino typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 1007*e4b17023SJohn Marino typedef typename _Self::difference_type difference_type; 1008*e4b17023SJohn Marino 1009*e4b17023SJohn Marino difference_type __len = __last - __first; 1010*e4b17023SJohn Marino while (__len > 0) 1011*e4b17023SJohn Marino { 1012*e4b17023SJohn Marino const difference_type __clen 1013*e4b17023SJohn Marino = std::min(__len, std::min(__first._M_last - __first._M_cur, 1014*e4b17023SJohn Marino __result._M_last - __result._M_cur)); 1015*e4b17023SJohn Marino std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur); 1016*e4b17023SJohn Marino __first += __clen; 1017*e4b17023SJohn Marino __result += __clen; 1018*e4b17023SJohn Marino __len -= __clen; 1019*e4b17023SJohn Marino } 1020*e4b17023SJohn Marino return __result; 1021*e4b17023SJohn Marino } 1022*e4b17023SJohn Marino 1023*e4b17023SJohn Marino template<typename _Tp> 1024*e4b17023SJohn Marino _Deque_iterator<_Tp, _Tp&, _Tp*> 1025*e4b17023SJohn Marino move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, 1026*e4b17023SJohn Marino _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, 1027*e4b17023SJohn Marino _Deque_iterator<_Tp, _Tp&, _Tp*> __result) 1028*e4b17023SJohn Marino { 1029*e4b17023SJohn Marino typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 1030*e4b17023SJohn Marino typedef typename _Self::difference_type difference_type; 1031*e4b17023SJohn Marino 1032*e4b17023SJohn Marino difference_type __len = __last - __first; 1033*e4b17023SJohn Marino while (__len > 0) 1034*e4b17023SJohn Marino { 1035*e4b17023SJohn Marino difference_type __llen = __last._M_cur - __last._M_first; 1036*e4b17023SJohn Marino _Tp* __lend = __last._M_cur; 1037*e4b17023SJohn Marino 1038*e4b17023SJohn Marino difference_type __rlen = __result._M_cur - __result._M_first; 1039*e4b17023SJohn Marino _Tp* __rend = __result._M_cur; 1040*e4b17023SJohn Marino 1041*e4b17023SJohn Marino if (!__llen) 1042*e4b17023SJohn Marino { 1043*e4b17023SJohn Marino __llen = _Self::_S_buffer_size(); 1044*e4b17023SJohn Marino __lend = *(__last._M_node - 1) + __llen; 1045*e4b17023SJohn Marino } 1046*e4b17023SJohn Marino if (!__rlen) 1047*e4b17023SJohn Marino { 1048*e4b17023SJohn Marino __rlen = _Self::_S_buffer_size(); 1049*e4b17023SJohn Marino __rend = *(__result._M_node - 1) + __rlen; 1050*e4b17023SJohn Marino } 1051*e4b17023SJohn Marino 1052*e4b17023SJohn Marino const difference_type __clen = std::min(__len, 1053*e4b17023SJohn Marino std::min(__llen, __rlen)); 1054*e4b17023SJohn Marino std::move_backward(__lend - __clen, __lend, __rend); 1055*e4b17023SJohn Marino __last -= __clen; 1056*e4b17023SJohn Marino __result -= __clen; 1057*e4b17023SJohn Marino __len -= __clen; 1058*e4b17023SJohn Marino } 1059*e4b17023SJohn Marino return __result; 1060*e4b17023SJohn Marino } 1061*e4b17023SJohn Marino #endif 1062*e4b17023SJohn Marino 1063*e4b17023SJohn Marino _GLIBCXX_END_NAMESPACE_CONTAINER 1064*e4b17023SJohn Marino } // namespace std 1065*e4b17023SJohn Marino 1066*e4b17023SJohn Marino #endif 1067