1117397Skan// Deque implementation (out of line) -*- C++ -*- 2117397Skan 3169691Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 4169691Skan// Free Software Foundation, Inc. 5117397Skan// 6117397Skan// This file is part of the GNU ISO C++ Library. This library is free 7117397Skan// software; you can redistribute it and/or modify it under the 8117397Skan// terms of the GNU General Public License as published by the 9117397Skan// Free Software Foundation; either version 2, or (at your option) 10117397Skan// any later version. 11117397Skan 12117397Skan// This library is distributed in the hope that it will be useful, 13117397Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of 14117397Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15117397Skan// GNU General Public License for more details. 16117397Skan 17117397Skan// You should have received a copy of the GNU General Public License along 18117397Skan// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 20117397Skan// USA. 21117397Skan 22117397Skan// As a special exception, you may use this file as part of a free software 23117397Skan// library without restriction. Specifically, if other files instantiate 24117397Skan// templates or use macros or inline functions from this file, or you compile 25117397Skan// this file and link it with other files to produce an executable, this 26117397Skan// file does not by itself cause the resulting executable to be covered by 27117397Skan// the GNU General Public License. This exception does not however 28117397Skan// invalidate any other reasons why the executable file might be covered by 29117397Skan// the GNU General Public License. 30117397Skan 31117397Skan/* 32117397Skan * 33117397Skan * Copyright (c) 1994 34117397Skan * Hewlett-Packard Company 35117397Skan * 36117397Skan * Permission to use, copy, modify, distribute and sell this software 37117397Skan * and its documentation for any purpose is hereby granted without fee, 38117397Skan * provided that the above copyright notice appear in all copies and 39117397Skan * that both that copyright notice and this permission notice appear 40117397Skan * in supporting documentation. Hewlett-Packard Company makes no 41117397Skan * representations about the suitability of this software for any 42117397Skan * purpose. It is provided "as is" without express or implied warranty. 43117397Skan * 44117397Skan * 45117397Skan * Copyright (c) 1997 46117397Skan * Silicon Graphics Computer Systems, Inc. 47117397Skan * 48117397Skan * Permission to use, copy, modify, distribute and sell this software 49117397Skan * and its documentation for any purpose is hereby granted without fee, 50117397Skan * provided that the above copyright notice appear in all copies and 51117397Skan * that both that copyright notice and this permission notice appear 52117397Skan * in supporting documentation. Silicon Graphics makes no 53117397Skan * representations about the suitability of this software for any 54117397Skan * purpose. It is provided "as is" without express or implied warranty. 55117397Skan */ 56117397Skan 57117397Skan/** @file deque.tcc 58117397Skan * This is an internal header file, included by other library headers. 59117397Skan * You should not attempt to use it directly. 60117397Skan */ 61117397Skan 62132720Skan#ifndef _DEQUE_TCC 63132720Skan#define _DEQUE_TCC 1 64117397Skan 65169691Skan_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) 66169691Skan 67117397Skan template <typename _Tp, typename _Alloc> 68169691Skan deque<_Tp, _Alloc>& 69169691Skan deque<_Tp, _Alloc>:: 70117397Skan operator=(const deque& __x) 71117397Skan { 72117397Skan const size_type __len = size(); 73117397Skan if (&__x != this) 74132720Skan { 75132720Skan if (__len >= __x.size()) 76169691Skan _M_erase_at_end(std::copy(__x.begin(), __x.end(), 77169691Skan this->_M_impl._M_start)); 78132720Skan else 79132720Skan { 80132720Skan const_iterator __mid = __x.begin() + difference_type(__len); 81132720Skan std::copy(__x.begin(), __mid, this->_M_impl._M_start); 82132720Skan insert(this->_M_impl._M_finish, __mid, __x.end()); 83132720Skan } 84132720Skan } 85117397Skan return *this; 86132720Skan } 87132720Skan 88117397Skan template <typename _Tp, typename _Alloc> 89169691Skan typename deque<_Tp, _Alloc>::iterator 90169691Skan deque<_Tp, _Alloc>:: 91169691Skan insert(iterator __position, const value_type& __x) 92117397Skan { 93169691Skan if (__position._M_cur == this->_M_impl._M_start._M_cur) 94132720Skan { 95132720Skan push_front(__x); 96132720Skan return this->_M_impl._M_start; 97132720Skan } 98169691Skan else if (__position._M_cur == this->_M_impl._M_finish._M_cur) 99132720Skan { 100132720Skan push_back(__x); 101132720Skan iterator __tmp = this->_M_impl._M_finish; 102132720Skan --__tmp; 103132720Skan return __tmp; 104132720Skan } 105117397Skan else 106169691Skan return _M_insert_aux(__position, __x); 107117397Skan } 108132720Skan 109117397Skan template <typename _Tp, typename _Alloc> 110169691Skan typename deque<_Tp, _Alloc>::iterator 111169691Skan deque<_Tp, _Alloc>:: 112117397Skan erase(iterator __position) 113117397Skan { 114117397Skan iterator __next = __position; 115117397Skan ++__next; 116169691Skan const difference_type __index = __position - begin(); 117169691Skan if (static_cast<size_type>(__index) < (size() >> 1)) 118132720Skan { 119169691Skan if (__position != begin()) 120169691Skan std::copy_backward(begin(), __position, __next); 121132720Skan pop_front(); 122132720Skan } 123117397Skan else 124132720Skan { 125169691Skan if (__next != end()) 126169691Skan std::copy(__next, end(), __position); 127132720Skan pop_back(); 128132720Skan } 129169691Skan return begin() + __index; 130117397Skan } 131132720Skan 132117397Skan template <typename _Tp, typename _Alloc> 133169691Skan typename deque<_Tp, _Alloc>::iterator 134169691Skan deque<_Tp, _Alloc>:: 135117397Skan erase(iterator __first, iterator __last) 136117397Skan { 137169691Skan if (__first == begin() && __last == end()) 138132720Skan { 139132720Skan clear(); 140169691Skan return end(); 141132720Skan } 142117397Skan else 143132720Skan { 144132720Skan const difference_type __n = __last - __first; 145169691Skan const difference_type __elems_before = __first - begin(); 146169691Skan if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2) 147132720Skan { 148169691Skan if (__first != begin()) 149169691Skan std::copy_backward(begin(), __first, __last); 150169691Skan _M_erase_at_begin(begin() + __n); 151132720Skan } 152132720Skan else 153132720Skan { 154169691Skan if (__last != end()) 155169691Skan std::copy(__last, end(), __first); 156169691Skan _M_erase_at_end(end() - __n); 157132720Skan } 158169691Skan return begin() + __elems_before; 159132720Skan } 160117397Skan } 161132720Skan 162117397Skan template <typename _Tp, class _Alloc> 163132720Skan template <typename _InputIterator> 164117397Skan void 165169691Skan deque<_Tp, _Alloc>:: 166169691Skan _M_assign_aux(_InputIterator __first, _InputIterator __last, 167169691Skan std::input_iterator_tag) 168117397Skan { 169117397Skan iterator __cur = begin(); 170169691Skan for (; __first != __last && __cur != end(); ++__cur, ++__first) 171117397Skan *__cur = *__first; 172117397Skan if (__first == __last) 173169691Skan _M_erase_at_end(__cur); 174117397Skan else 175117397Skan insert(end(), __first, __last); 176117397Skan } 177132720Skan 178117397Skan template <typename _Tp, typename _Alloc> 179117397Skan void 180169691Skan deque<_Tp, _Alloc>:: 181117397Skan _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) 182117397Skan { 183132720Skan if (__pos._M_cur == this->_M_impl._M_start._M_cur) 184132720Skan { 185132720Skan iterator __new_start = _M_reserve_elements_at_front(__n); 186132720Skan try 187132720Skan { 188169691Skan std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start, 189169691Skan __x, _M_get_Tp_allocator()); 190132720Skan this->_M_impl._M_start = __new_start; 191132720Skan } 192132720Skan catch(...) 193132720Skan { 194169691Skan _M_destroy_nodes(__new_start._M_node, 195169691Skan this->_M_impl._M_start._M_node); 196132720Skan __throw_exception_again; 197132720Skan } 198132720Skan } 199132720Skan else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 200132720Skan { 201132720Skan iterator __new_finish = _M_reserve_elements_at_back(__n); 202132720Skan try 203132720Skan { 204169691Skan std::__uninitialized_fill_a(this->_M_impl._M_finish, 205169691Skan __new_finish, __x, 206169691Skan _M_get_Tp_allocator()); 207132720Skan this->_M_impl._M_finish = __new_finish; 208132720Skan } 209132720Skan catch(...) 210132720Skan { 211132720Skan _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 212132720Skan __new_finish._M_node + 1); 213132720Skan __throw_exception_again; 214132720Skan } 215132720Skan } 216132720Skan else 217117397Skan _M_insert_aux(__pos, __n, __x); 218117397Skan } 219132720Skan 220117397Skan template <typename _Tp, typename _Alloc> 221117397Skan void 222169691Skan deque<_Tp, _Alloc>:: 223117397Skan _M_fill_initialize(const value_type& __value) 224117397Skan { 225117397Skan _Map_pointer __cur; 226117397Skan try 227117397Skan { 228132720Skan for (__cur = this->_M_impl._M_start._M_node; 229132720Skan __cur < this->_M_impl._M_finish._M_node; 230132720Skan ++__cur) 231169691Skan std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), 232169691Skan __value, _M_get_Tp_allocator()); 233169691Skan std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, 234169691Skan this->_M_impl._M_finish._M_cur, 235169691Skan __value, _M_get_Tp_allocator()); 236117397Skan } 237117397Skan catch(...) 238117397Skan { 239169691Skan std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), 240169691Skan _M_get_Tp_allocator()); 241117397Skan __throw_exception_again; 242117397Skan } 243117397Skan } 244132720Skan 245117397Skan template <typename _Tp, typename _Alloc> 246117397Skan template <typename _InputIterator> 247117397Skan void 248169691Skan deque<_Tp, _Alloc>:: 249117397Skan _M_range_initialize(_InputIterator __first, _InputIterator __last, 250169691Skan std::input_iterator_tag) 251117397Skan { 252132720Skan this->_M_initialize_map(0); 253117397Skan try 254117397Skan { 255169691Skan for (; __first != __last; ++__first) 256117397Skan push_back(*__first); 257117397Skan } 258117397Skan catch(...) 259117397Skan { 260117397Skan clear(); 261117397Skan __throw_exception_again; 262117397Skan } 263117397Skan } 264132720Skan 265117397Skan template <typename _Tp, typename _Alloc> 266117397Skan template <typename _ForwardIterator> 267117397Skan void 268169691Skan deque<_Tp, _Alloc>:: 269117397Skan _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 270169691Skan std::forward_iterator_tag) 271117397Skan { 272132720Skan const size_type __n = std::distance(__first, __last); 273132720Skan this->_M_initialize_map(__n); 274132720Skan 275117397Skan _Map_pointer __cur_node; 276117397Skan try 277117397Skan { 278132720Skan for (__cur_node = this->_M_impl._M_start._M_node; 279132720Skan __cur_node < this->_M_impl._M_finish._M_node; 280117397Skan ++__cur_node) 281169691Skan { 282169691Skan _ForwardIterator __mid = __first; 283169691Skan std::advance(__mid, _S_buffer_size()); 284169691Skan std::__uninitialized_copy_a(__first, __mid, *__cur_node, 285169691Skan _M_get_Tp_allocator()); 286169691Skan __first = __mid; 287169691Skan } 288169691Skan std::__uninitialized_copy_a(__first, __last, 289169691Skan this->_M_impl._M_finish._M_first, 290169691Skan _M_get_Tp_allocator()); 291117397Skan } 292117397Skan catch(...) 293117397Skan { 294169691Skan std::_Destroy(this->_M_impl._M_start, 295169691Skan iterator(*__cur_node, __cur_node), 296169691Skan _M_get_Tp_allocator()); 297117397Skan __throw_exception_again; 298117397Skan } 299117397Skan } 300132720Skan 301132720Skan // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. 302117397Skan template <typename _Tp, typename _Alloc> 303117397Skan void 304169691Skan deque<_Tp, _Alloc>:: 305117397Skan _M_push_back_aux(const value_type& __t) 306117397Skan { 307117397Skan value_type __t_copy = __t; 308117397Skan _M_reserve_map_at_back(); 309132720Skan *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); 310117397Skan try 311117397Skan { 312169691Skan this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t_copy); 313169691Skan this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node 314169691Skan + 1); 315132720Skan this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; 316117397Skan } 317117397Skan catch(...) 318117397Skan { 319132720Skan _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); 320117397Skan __throw_exception_again; 321117397Skan } 322117397Skan } 323132720Skan 324132720Skan // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. 325117397Skan template <typename _Tp, typename _Alloc> 326117397Skan void 327169691Skan deque<_Tp, _Alloc>:: 328117397Skan _M_push_front_aux(const value_type& __t) 329117397Skan { 330117397Skan value_type __t_copy = __t; 331117397Skan _M_reserve_map_at_front(); 332132720Skan *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); 333117397Skan try 334117397Skan { 335169691Skan this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node 336169691Skan - 1); 337132720Skan this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; 338169691Skan this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t_copy); 339117397Skan } 340117397Skan catch(...) 341117397Skan { 342132720Skan ++this->_M_impl._M_start; 343132720Skan _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); 344117397Skan __throw_exception_again; 345117397Skan } 346132720Skan } 347132720Skan 348132720Skan // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. 349117397Skan template <typename _Tp, typename _Alloc> 350169691Skan void deque<_Tp, _Alloc>:: 351117397Skan _M_pop_back_aux() 352117397Skan { 353132720Skan _M_deallocate_node(this->_M_impl._M_finish._M_first); 354132720Skan this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); 355132720Skan this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; 356169691Skan this->_M_impl.destroy(this->_M_impl._M_finish._M_cur); 357117397Skan } 358132720Skan 359169691Skan // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. 360169691Skan // Note that if the deque has at least one element (a precondition for this 361169691Skan // member function), and if 362169691Skan // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, 363169691Skan // then the deque must have at least two nodes. 364117397Skan template <typename _Tp, typename _Alloc> 365169691Skan void deque<_Tp, _Alloc>:: 366117397Skan _M_pop_front_aux() 367117397Skan { 368169691Skan this->_M_impl.destroy(this->_M_impl._M_start._M_cur); 369132720Skan _M_deallocate_node(this->_M_impl._M_start._M_first); 370132720Skan this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); 371132720Skan this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; 372132720Skan } 373132720Skan 374117397Skan template <typename _Tp, typename _Alloc> 375117397Skan template <typename _InputIterator> 376117397Skan void 377169691Skan deque<_Tp, _Alloc>:: 378117397Skan _M_range_insert_aux(iterator __pos, 379117397Skan _InputIterator __first, _InputIterator __last, 380169691Skan std::input_iterator_tag) 381132720Skan { std::copy(__first, __last, std::inserter(*this, __pos)); } 382132720Skan 383117397Skan template <typename _Tp, typename _Alloc> 384117397Skan template <typename _ForwardIterator> 385117397Skan void 386169691Skan deque<_Tp, _Alloc>:: 387117397Skan _M_range_insert_aux(iterator __pos, 388117397Skan _ForwardIterator __first, _ForwardIterator __last, 389169691Skan std::forward_iterator_tag) 390117397Skan { 391169691Skan const size_type __n = std::distance(__first, __last); 392132720Skan if (__pos._M_cur == this->_M_impl._M_start._M_cur) 393132720Skan { 394132720Skan iterator __new_start = _M_reserve_elements_at_front(__n); 395132720Skan try 396132720Skan { 397169691Skan std::__uninitialized_copy_a(__first, __last, __new_start, 398169691Skan _M_get_Tp_allocator()); 399132720Skan this->_M_impl._M_start = __new_start; 400132720Skan } 401132720Skan catch(...) 402132720Skan { 403169691Skan _M_destroy_nodes(__new_start._M_node, 404169691Skan this->_M_impl._M_start._M_node); 405132720Skan __throw_exception_again; 406132720Skan } 407132720Skan } 408132720Skan else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 409132720Skan { 410132720Skan iterator __new_finish = _M_reserve_elements_at_back(__n); 411132720Skan try 412132720Skan { 413169691Skan std::__uninitialized_copy_a(__first, __last, 414169691Skan this->_M_impl._M_finish, 415169691Skan _M_get_Tp_allocator()); 416132720Skan this->_M_impl._M_finish = __new_finish; 417132720Skan } 418132720Skan catch(...) 419132720Skan { 420132720Skan _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 421132720Skan __new_finish._M_node + 1); 422132720Skan __throw_exception_again; 423132720Skan } 424132720Skan } 425117397Skan else 426117397Skan _M_insert_aux(__pos, __first, __last, __n); 427117397Skan } 428132720Skan 429117397Skan template <typename _Tp, typename _Alloc> 430117397Skan typename deque<_Tp, _Alloc>::iterator 431169691Skan deque<_Tp, _Alloc>:: 432117397Skan _M_insert_aux(iterator __pos, const value_type& __x) 433117397Skan { 434132720Skan difference_type __index = __pos - this->_M_impl._M_start; 435117397Skan value_type __x_copy = __x; // XXX copy 436117397Skan if (static_cast<size_type>(__index) < size() / 2) 437132720Skan { 438132720Skan push_front(front()); 439132720Skan iterator __front1 = this->_M_impl._M_start; 440132720Skan ++__front1; 441132720Skan iterator __front2 = __front1; 442132720Skan ++__front2; 443132720Skan __pos = this->_M_impl._M_start + __index; 444132720Skan iterator __pos1 = __pos; 445132720Skan ++__pos1; 446132720Skan std::copy(__front2, __pos1, __front1); 447132720Skan } 448117397Skan else 449132720Skan { 450132720Skan push_back(back()); 451132720Skan iterator __back1 = this->_M_impl._M_finish; 452132720Skan --__back1; 453132720Skan iterator __back2 = __back1; 454132720Skan --__back2; 455132720Skan __pos = this->_M_impl._M_start + __index; 456132720Skan std::copy_backward(__pos, __back2, __back1); 457132720Skan } 458117397Skan *__pos = __x_copy; 459117397Skan return __pos; 460117397Skan } 461132720Skan 462117397Skan template <typename _Tp, typename _Alloc> 463117397Skan void 464169691Skan deque<_Tp, _Alloc>:: 465117397Skan _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) 466117397Skan { 467132720Skan const difference_type __elems_before = __pos - this->_M_impl._M_start; 468169691Skan const size_type __length = this->size(); 469117397Skan value_type __x_copy = __x; 470117397Skan if (__elems_before < difference_type(__length / 2)) 471132720Skan { 472132720Skan iterator __new_start = _M_reserve_elements_at_front(__n); 473132720Skan iterator __old_start = this->_M_impl._M_start; 474132720Skan __pos = this->_M_impl._M_start + __elems_before; 475132720Skan try 476132720Skan { 477132720Skan if (__elems_before >= difference_type(__n)) 478132720Skan { 479169691Skan iterator __start_n = (this->_M_impl._M_start 480169691Skan + difference_type(__n)); 481169691Skan std::__uninitialized_copy_a(this->_M_impl._M_start, 482169691Skan __start_n, __new_start, 483169691Skan _M_get_Tp_allocator()); 484132720Skan this->_M_impl._M_start = __new_start; 485132720Skan std::copy(__start_n, __pos, __old_start); 486169691Skan std::fill(__pos - difference_type(__n), __pos, __x_copy); 487132720Skan } 488132720Skan else 489132720Skan { 490169691Skan std::__uninitialized_copy_fill(this->_M_impl._M_start, 491169691Skan __pos, __new_start, 492169691Skan this->_M_impl._M_start, 493169691Skan __x_copy, 494169691Skan _M_get_Tp_allocator()); 495132720Skan this->_M_impl._M_start = __new_start; 496132720Skan std::fill(__old_start, __pos, __x_copy); 497132720Skan } 498132720Skan } 499132720Skan catch(...) 500132720Skan { 501169691Skan _M_destroy_nodes(__new_start._M_node, 502169691Skan this->_M_impl._M_start._M_node); 503132720Skan __throw_exception_again; 504132720Skan } 505132720Skan } 506117397Skan else 507132720Skan { 508132720Skan iterator __new_finish = _M_reserve_elements_at_back(__n); 509132720Skan iterator __old_finish = this->_M_impl._M_finish; 510132720Skan const difference_type __elems_after = 511132720Skan difference_type(__length) - __elems_before; 512132720Skan __pos = this->_M_impl._M_finish - __elems_after; 513132720Skan try 514132720Skan { 515132720Skan if (__elems_after > difference_type(__n)) 516132720Skan { 517169691Skan iterator __finish_n = (this->_M_impl._M_finish 518169691Skan - difference_type(__n)); 519169691Skan std::__uninitialized_copy_a(__finish_n, 520169691Skan this->_M_impl._M_finish, 521169691Skan this->_M_impl._M_finish, 522169691Skan _M_get_Tp_allocator()); 523132720Skan this->_M_impl._M_finish = __new_finish; 524132720Skan std::copy_backward(__pos, __finish_n, __old_finish); 525132720Skan std::fill(__pos, __pos + difference_type(__n), __x_copy); 526132720Skan } 527132720Skan else 528132720Skan { 529132720Skan std::__uninitialized_fill_copy(this->_M_impl._M_finish, 530132720Skan __pos + difference_type(__n), 531132720Skan __x_copy, __pos, 532169691Skan this->_M_impl._M_finish, 533169691Skan _M_get_Tp_allocator()); 534132720Skan this->_M_impl._M_finish = __new_finish; 535132720Skan std::fill(__pos, __old_finish, __x_copy); 536132720Skan } 537132720Skan } 538132720Skan catch(...) 539132720Skan { 540132720Skan _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 541132720Skan __new_finish._M_node + 1); 542132720Skan __throw_exception_again; 543132720Skan } 544132720Skan } 545117397Skan } 546132720Skan 547117397Skan template <typename _Tp, typename _Alloc> 548117397Skan template <typename _ForwardIterator> 549117397Skan void 550169691Skan deque<_Tp, _Alloc>:: 551117397Skan _M_insert_aux(iterator __pos, 552117397Skan _ForwardIterator __first, _ForwardIterator __last, 553117397Skan size_type __n) 554117397Skan { 555132720Skan const difference_type __elemsbefore = __pos - this->_M_impl._M_start; 556169691Skan const size_type __length = size(); 557117397Skan if (static_cast<size_type>(__elemsbefore) < __length / 2) 558132720Skan { 559132720Skan iterator __new_start = _M_reserve_elements_at_front(__n); 560132720Skan iterator __old_start = this->_M_impl._M_start; 561132720Skan __pos = this->_M_impl._M_start + __elemsbefore; 562132720Skan try 563132720Skan { 564132720Skan if (__elemsbefore >= difference_type(__n)) 565132720Skan { 566169691Skan iterator __start_n = (this->_M_impl._M_start 567169691Skan + difference_type(__n)); 568169691Skan std::__uninitialized_copy_a(this->_M_impl._M_start, 569169691Skan __start_n, __new_start, 570169691Skan _M_get_Tp_allocator()); 571132720Skan this->_M_impl._M_start = __new_start; 572132720Skan std::copy(__start_n, __pos, __old_start); 573132720Skan std::copy(__first, __last, __pos - difference_type(__n)); 574132720Skan } 575132720Skan else 576132720Skan { 577132720Skan _ForwardIterator __mid = __first; 578132720Skan std::advance(__mid, difference_type(__n) - __elemsbefore); 579169691Skan std::__uninitialized_copy_copy(this->_M_impl._M_start, 580169691Skan __pos, __first, __mid, 581169691Skan __new_start, 582169691Skan _M_get_Tp_allocator()); 583132720Skan this->_M_impl._M_start = __new_start; 584132720Skan std::copy(__mid, __last, __old_start); 585132720Skan } 586132720Skan } 587132720Skan catch(...) 588132720Skan { 589169691Skan _M_destroy_nodes(__new_start._M_node, 590169691Skan this->_M_impl._M_start._M_node); 591132720Skan __throw_exception_again; 592132720Skan } 593132720Skan } 594117397Skan else 595117397Skan { 596117397Skan iterator __new_finish = _M_reserve_elements_at_back(__n); 597132720Skan iterator __old_finish = this->_M_impl._M_finish; 598132720Skan const difference_type __elemsafter = 599117397Skan difference_type(__length) - __elemsbefore; 600132720Skan __pos = this->_M_impl._M_finish - __elemsafter; 601117397Skan try 602117397Skan { 603117397Skan if (__elemsafter > difference_type(__n)) 604132720Skan { 605169691Skan iterator __finish_n = (this->_M_impl._M_finish 606169691Skan - difference_type(__n)); 607169691Skan std::__uninitialized_copy_a(__finish_n, 608169691Skan this->_M_impl._M_finish, 609169691Skan this->_M_impl._M_finish, 610169691Skan _M_get_Tp_allocator()); 611132720Skan this->_M_impl._M_finish = __new_finish; 612132720Skan std::copy_backward(__pos, __finish_n, __old_finish); 613132720Skan std::copy(__first, __last, __pos); 614132720Skan } 615117397Skan else 616132720Skan { 617132720Skan _ForwardIterator __mid = __first; 618132720Skan std::advance(__mid, __elemsafter); 619132720Skan std::__uninitialized_copy_copy(__mid, __last, __pos, 620132720Skan this->_M_impl._M_finish, 621169691Skan this->_M_impl._M_finish, 622169691Skan _M_get_Tp_allocator()); 623132720Skan this->_M_impl._M_finish = __new_finish; 624132720Skan std::copy(__first, __mid, __pos); 625132720Skan } 626117397Skan } 627117397Skan catch(...) 628117397Skan { 629132720Skan _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 630132720Skan __new_finish._M_node + 1); 631117397Skan __throw_exception_again; 632117397Skan } 633117397Skan } 634117397Skan } 635132720Skan 636169691Skan template<typename _Tp, typename _Alloc> 637169691Skan void 638169691Skan deque<_Tp, _Alloc>:: 639169691Skan _M_destroy_data_aux(iterator __first, iterator __last) 640169691Skan { 641169691Skan for (_Map_pointer __node = __first._M_node + 1; 642169691Skan __node < __last._M_node; ++__node) 643169691Skan std::_Destroy(*__node, *__node + _S_buffer_size(), 644169691Skan _M_get_Tp_allocator()); 645169691Skan 646169691Skan if (__first._M_node != __last._M_node) 647169691Skan { 648169691Skan std::_Destroy(__first._M_cur, __first._M_last, 649169691Skan _M_get_Tp_allocator()); 650169691Skan std::_Destroy(__last._M_first, __last._M_cur, 651169691Skan _M_get_Tp_allocator()); 652169691Skan } 653169691Skan else 654169691Skan std::_Destroy(__first._M_cur, __last._M_cur, 655169691Skan _M_get_Tp_allocator()); 656169691Skan } 657169691Skan 658117397Skan template <typename _Tp, typename _Alloc> 659117397Skan void 660169691Skan deque<_Tp, _Alloc>:: 661117397Skan _M_new_elements_at_front(size_type __new_elems) 662117397Skan { 663169691Skan if (this->max_size() - this->size() < __new_elems) 664169691Skan __throw_length_error(__N("deque::_M_new_elements_at_front")); 665169691Skan 666169691Skan const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 667169691Skan / _S_buffer_size()); 668117397Skan _M_reserve_map_at_front(__new_nodes); 669117397Skan size_type __i; 670117397Skan try 671117397Skan { 672117397Skan for (__i = 1; __i <= __new_nodes; ++__i) 673132720Skan *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); 674117397Skan } 675117397Skan catch(...) 676117397Skan { 677117397Skan for (size_type __j = 1; __j < __i; ++__j) 678132720Skan _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); 679117397Skan __throw_exception_again; 680117397Skan } 681117397Skan } 682132720Skan 683117397Skan template <typename _Tp, typename _Alloc> 684117397Skan void 685169691Skan deque<_Tp, _Alloc>:: 686117397Skan _M_new_elements_at_back(size_type __new_elems) 687117397Skan { 688169691Skan if (this->max_size() - this->size() < __new_elems) 689169691Skan __throw_length_error(__N("deque::_M_new_elements_at_back")); 690169691Skan 691169691Skan const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 692169691Skan / _S_buffer_size()); 693117397Skan _M_reserve_map_at_back(__new_nodes); 694117397Skan size_type __i; 695117397Skan try 696117397Skan { 697117397Skan for (__i = 1; __i <= __new_nodes; ++__i) 698132720Skan *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); 699117397Skan } 700117397Skan catch(...) 701117397Skan { 702117397Skan for (size_type __j = 1; __j < __i; ++__j) 703132720Skan _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); 704117397Skan __throw_exception_again; 705117397Skan } 706117397Skan } 707132720Skan 708117397Skan template <typename _Tp, typename _Alloc> 709117397Skan void 710169691Skan deque<_Tp, _Alloc>:: 711117397Skan _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) 712117397Skan { 713169691Skan const size_type __old_num_nodes 714132720Skan = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; 715169691Skan const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 716132720Skan 717117397Skan _Map_pointer __new_nstart; 718132720Skan if (this->_M_impl._M_map_size > 2 * __new_num_nodes) 719132720Skan { 720132720Skan __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size 721132720Skan - __new_num_nodes) / 2 722132720Skan + (__add_at_front ? __nodes_to_add : 0); 723132720Skan if (__new_nstart < this->_M_impl._M_start._M_node) 724132720Skan std::copy(this->_M_impl._M_start._M_node, 725169691Skan this->_M_impl._M_finish._M_node + 1, 726169691Skan __new_nstart); 727132720Skan else 728132720Skan std::copy_backward(this->_M_impl._M_start._M_node, 729132720Skan this->_M_impl._M_finish._M_node + 1, 730132720Skan __new_nstart + __old_num_nodes); 731132720Skan } 732117397Skan else 733132720Skan { 734132720Skan size_type __new_map_size = this->_M_impl._M_map_size 735132720Skan + std::max(this->_M_impl._M_map_size, 736132720Skan __nodes_to_add) + 2; 737132720Skan 738132720Skan _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); 739132720Skan __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 740132720Skan + (__add_at_front ? __nodes_to_add : 0); 741132720Skan std::copy(this->_M_impl._M_start._M_node, 742132720Skan this->_M_impl._M_finish._M_node + 1, 743132720Skan __new_nstart); 744132720Skan _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 745132720Skan 746132720Skan this->_M_impl._M_map = __new_map; 747132720Skan this->_M_impl._M_map_size = __new_map_size; 748132720Skan } 749132720Skan 750132720Skan this->_M_impl._M_start._M_set_node(__new_nstart); 751132720Skan this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 752117397Skan } 753117397Skan 754169691Skan // Overload for deque::iterators, exploiting the "segmented-iterator 755169691Skan // optimization". NB: leave const_iterators alone! 756169691Skan template<typename _Tp> 757169691Skan void 758169691Skan fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, 759169691Skan const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value) 760169691Skan { 761169691Skan typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 762169691Skan 763169691Skan for (typename _Self::_Map_pointer __node = __first._M_node + 1; 764169691Skan __node < __last._M_node; ++__node) 765169691Skan std::fill(*__node, *__node + _Self::_S_buffer_size(), __value); 766169691Skan 767169691Skan if (__first._M_node != __last._M_node) 768169691Skan { 769169691Skan std::fill(__first._M_cur, __first._M_last, __value); 770169691Skan std::fill(__last._M_first, __last._M_cur, __value); 771169691Skan } 772169691Skan else 773169691Skan std::fill(__first._M_cur, __last._M_cur, __value); 774169691Skan } 775169691Skan 776169691Skan_GLIBCXX_END_NESTED_NAMESPACE 777169691Skan 778132720Skan#endif 779