1// Deque implementation (out of line) -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 4// Free Software Foundation, Inc. 5// 6// This file is part of the GNU ISO C++ Library. This library is free 7// software; you can redistribute it and/or modify it under the 8// terms of the GNU General Public License as published by the 9// Free Software Foundation; either version 2, or (at your option) 10// any later version. 11 12// This library is distributed in the hope that it will be useful, 13// but WITHOUT ANY WARRANTY; without even the implied warranty of 14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15// GNU General Public License for more details. 16 17// You should have received a copy of the GNU General Public License along 18// with this library; see the file COPYING. If not, write to the Free 19// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 20// USA. 21 22// As a special exception, you may use this file as part of a free software 23// library without restriction. Specifically, if other files instantiate 24// templates or use macros or inline functions from this file, or you compile 25// this file and link it with other files to produce an executable, this 26// file does not by itself cause the resulting executable to be covered by 27// the GNU General Public License. This exception does not however 28// invalidate any other reasons why the executable file might be covered by 29// the GNU General Public License. 30 31/* 32 * 33 * Copyright (c) 1994 34 * Hewlett-Packard Company 35 * 36 * Permission to use, copy, modify, distribute and sell this software 37 * and its documentation for any purpose is hereby granted without fee, 38 * provided that the above copyright notice appear in all copies and 39 * that both that copyright notice and this permission notice appear 40 * in supporting documentation. Hewlett-Packard Company makes no 41 * representations about the suitability of this software for any 42 * purpose. It is provided "as is" without express or implied warranty. 43 * 44 * 45 * Copyright (c) 1997 46 * Silicon Graphics Computer Systems, Inc. 47 * 48 * Permission to use, copy, modify, distribute and sell this software 49 * and its documentation for any purpose is hereby granted without fee, 50 * provided that the above copyright notice appear in all copies and 51 * that both that copyright notice and this permission notice appear 52 * in supporting documentation. Silicon Graphics makes no 53 * representations about the suitability of this software for any 54 * purpose. It is provided "as is" without express or implied warranty. 55 */ 56 57/** @file deque.tcc 58 * This is an internal header file, included by other library headers. 59 * You should not attempt to use it directly. 60 */ 61 62#ifndef _DEQUE_TCC 63#define _DEQUE_TCC 1 64 65_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) 66 67 template <typename _Tp, typename _Alloc> 68 deque<_Tp, _Alloc>& 69 deque<_Tp, _Alloc>:: 70 operator=(const deque& __x) 71 { 72 const size_type __len = size(); 73 if (&__x != this) 74 { 75 if (__len >= __x.size()) 76 _M_erase_at_end(std::copy(__x.begin(), __x.end(), 77 this->_M_impl._M_start)); 78 else 79 { 80 const_iterator __mid = __x.begin() + difference_type(__len); 81 std::copy(__x.begin(), __mid, this->_M_impl._M_start); 82 insert(this->_M_impl._M_finish, __mid, __x.end()); 83 } 84 } 85 return *this; 86 } 87 88 template <typename _Tp, typename _Alloc> 89 typename deque<_Tp, _Alloc>::iterator 90 deque<_Tp, _Alloc>:: 91 insert(iterator __position, const value_type& __x) 92 { 93 if (__position._M_cur == this->_M_impl._M_start._M_cur) 94 { 95 push_front(__x); 96 return this->_M_impl._M_start; 97 } 98 else if (__position._M_cur == this->_M_impl._M_finish._M_cur) 99 { 100 push_back(__x); 101 iterator __tmp = this->_M_impl._M_finish; 102 --__tmp; 103 return __tmp; 104 } 105 else 106 return _M_insert_aux(__position, __x); 107 } 108 109 template <typename _Tp, typename _Alloc> 110 typename deque<_Tp, _Alloc>::iterator 111 deque<_Tp, _Alloc>:: 112 erase(iterator __position) 113 { 114 iterator __next = __position; 115 ++__next; 116 const difference_type __index = __position - begin(); 117 if (static_cast<size_type>(__index) < (size() >> 1)) 118 { 119 if (__position != begin()) 120 std::copy_backward(begin(), __position, __next); 121 pop_front(); 122 } 123 else 124 { 125 if (__next != end()) 126 std::copy(__next, end(), __position); 127 pop_back(); 128 } 129 return begin() + __index; 130 } 131 132 template <typename _Tp, typename _Alloc> 133 typename deque<_Tp, _Alloc>::iterator 134 deque<_Tp, _Alloc>:: 135 erase(iterator __first, iterator __last) 136 { 137 if (__first == begin() && __last == end()) 138 { 139 clear(); 140 return end(); 141 } 142 else 143 { 144 const difference_type __n = __last - __first; 145 const difference_type __elems_before = __first - begin(); 146 if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2) 147 { 148 if (__first != begin()) 149 std::copy_backward(begin(), __first, __last); 150 _M_erase_at_begin(begin() + __n); 151 } 152 else 153 { 154 if (__last != end()) 155 std::copy(__last, end(), __first); 156 _M_erase_at_end(end() - __n); 157 } 158 return begin() + __elems_before; 159 } 160 } 161 162 template <typename _Tp, class _Alloc> 163 template <typename _InputIterator> 164 void 165 deque<_Tp, _Alloc>:: 166 _M_assign_aux(_InputIterator __first, _InputIterator __last, 167 std::input_iterator_tag) 168 { 169 iterator __cur = begin(); 170 for (; __first != __last && __cur != end(); ++__cur, ++__first) 171 *__cur = *__first; 172 if (__first == __last) 173 _M_erase_at_end(__cur); 174 else 175 insert(end(), __first, __last); 176 } 177 178 template <typename _Tp, typename _Alloc> 179 void 180 deque<_Tp, _Alloc>:: 181 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) 182 { 183 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 184 { 185 iterator __new_start = _M_reserve_elements_at_front(__n); 186 try 187 { 188 std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start, 189 __x, _M_get_Tp_allocator()); 190 this->_M_impl._M_start = __new_start; 191 } 192 catch(...) 193 { 194 _M_destroy_nodes(__new_start._M_node, 195 this->_M_impl._M_start._M_node); 196 __throw_exception_again; 197 } 198 } 199 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 200 { 201 iterator __new_finish = _M_reserve_elements_at_back(__n); 202 try 203 { 204 std::__uninitialized_fill_a(this->_M_impl._M_finish, 205 __new_finish, __x, 206 _M_get_Tp_allocator()); 207 this->_M_impl._M_finish = __new_finish; 208 } 209 catch(...) 210 { 211 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 212 __new_finish._M_node + 1); 213 __throw_exception_again; 214 } 215 } 216 else 217 _M_insert_aux(__pos, __n, __x); 218 } 219 220 template <typename _Tp, typename _Alloc> 221 void 222 deque<_Tp, _Alloc>:: 223 _M_fill_initialize(const value_type& __value) 224 { 225 _Map_pointer __cur; 226 try 227 { 228 for (__cur = this->_M_impl._M_start._M_node; 229 __cur < this->_M_impl._M_finish._M_node; 230 ++__cur) 231 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), 232 __value, _M_get_Tp_allocator()); 233 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, 234 this->_M_impl._M_finish._M_cur, 235 __value, _M_get_Tp_allocator()); 236 } 237 catch(...) 238 { 239 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), 240 _M_get_Tp_allocator()); 241 __throw_exception_again; 242 } 243 } 244 245 template <typename _Tp, typename _Alloc> 246 template <typename _InputIterator> 247 void 248 deque<_Tp, _Alloc>:: 249 _M_range_initialize(_InputIterator __first, _InputIterator __last, 250 std::input_iterator_tag) 251 { 252 this->_M_initialize_map(0); 253 try 254 { 255 for (; __first != __last; ++__first) 256 push_back(*__first); 257 } 258 catch(...) 259 { 260 clear(); 261 __throw_exception_again; 262 } 263 } 264 265 template <typename _Tp, typename _Alloc> 266 template <typename _ForwardIterator> 267 void 268 deque<_Tp, _Alloc>:: 269 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 270 std::forward_iterator_tag) 271 { 272 const size_type __n = std::distance(__first, __last); 273 this->_M_initialize_map(__n); 274 275 _Map_pointer __cur_node; 276 try 277 { 278 for (__cur_node = this->_M_impl._M_start._M_node; 279 __cur_node < this->_M_impl._M_finish._M_node; 280 ++__cur_node) 281 { 282 _ForwardIterator __mid = __first; 283 std::advance(__mid, _S_buffer_size()); 284 std::__uninitialized_copy_a(__first, __mid, *__cur_node, 285 _M_get_Tp_allocator()); 286 __first = __mid; 287 } 288 std::__uninitialized_copy_a(__first, __last, 289 this->_M_impl._M_finish._M_first, 290 _M_get_Tp_allocator()); 291 } 292 catch(...) 293 { 294 std::_Destroy(this->_M_impl._M_start, 295 iterator(*__cur_node, __cur_node), 296 _M_get_Tp_allocator()); 297 __throw_exception_again; 298 } 299 } 300 301 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. 302 template <typename _Tp, typename _Alloc> 303 void 304 deque<_Tp, _Alloc>:: 305 _M_push_back_aux(const value_type& __t) 306 { 307 value_type __t_copy = __t; 308 _M_reserve_map_at_back(); 309 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); 310 try 311 { 312 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t_copy); 313 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node 314 + 1); 315 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; 316 } 317 catch(...) 318 { 319 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); 320 __throw_exception_again; 321 } 322 } 323 324 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. 325 template <typename _Tp, typename _Alloc> 326 void 327 deque<_Tp, _Alloc>:: 328 _M_push_front_aux(const value_type& __t) 329 { 330 value_type __t_copy = __t; 331 _M_reserve_map_at_front(); 332 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); 333 try 334 { 335 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node 336 - 1); 337 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; 338 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t_copy); 339 } 340 catch(...) 341 { 342 ++this->_M_impl._M_start; 343 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); 344 __throw_exception_again; 345 } 346 } 347 348 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. 349 template <typename _Tp, typename _Alloc> 350 void deque<_Tp, _Alloc>:: 351 _M_pop_back_aux() 352 { 353 _M_deallocate_node(this->_M_impl._M_finish._M_first); 354 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); 355 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; 356 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur); 357 } 358 359 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. 360 // Note that if the deque has at least one element (a precondition for this 361 // member function), and if 362 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, 363 // then the deque must have at least two nodes. 364 template <typename _Tp, typename _Alloc> 365 void deque<_Tp, _Alloc>:: 366 _M_pop_front_aux() 367 { 368 this->_M_impl.destroy(this->_M_impl._M_start._M_cur); 369 _M_deallocate_node(this->_M_impl._M_start._M_first); 370 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); 371 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; 372 } 373 374 template <typename _Tp, typename _Alloc> 375 template <typename _InputIterator> 376 void 377 deque<_Tp, _Alloc>:: 378 _M_range_insert_aux(iterator __pos, 379 _InputIterator __first, _InputIterator __last, 380 std::input_iterator_tag) 381 { std::copy(__first, __last, std::inserter(*this, __pos)); } 382 383 template <typename _Tp, typename _Alloc> 384 template <typename _ForwardIterator> 385 void 386 deque<_Tp, _Alloc>:: 387 _M_range_insert_aux(iterator __pos, 388 _ForwardIterator __first, _ForwardIterator __last, 389 std::forward_iterator_tag) 390 { 391 const size_type __n = std::distance(__first, __last); 392 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 393 { 394 iterator __new_start = _M_reserve_elements_at_front(__n); 395 try 396 { 397 std::__uninitialized_copy_a(__first, __last, __new_start, 398 _M_get_Tp_allocator()); 399 this->_M_impl._M_start = __new_start; 400 } 401 catch(...) 402 { 403 _M_destroy_nodes(__new_start._M_node, 404 this->_M_impl._M_start._M_node); 405 __throw_exception_again; 406 } 407 } 408 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 409 { 410 iterator __new_finish = _M_reserve_elements_at_back(__n); 411 try 412 { 413 std::__uninitialized_copy_a(__first, __last, 414 this->_M_impl._M_finish, 415 _M_get_Tp_allocator()); 416 this->_M_impl._M_finish = __new_finish; 417 } 418 catch(...) 419 { 420 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 421 __new_finish._M_node + 1); 422 __throw_exception_again; 423 } 424 } 425 else 426 _M_insert_aux(__pos, __first, __last, __n); 427 } 428 429 template <typename _Tp, typename _Alloc> 430 typename deque<_Tp, _Alloc>::iterator 431 deque<_Tp, _Alloc>:: 432 _M_insert_aux(iterator __pos, const value_type& __x) 433 { 434 difference_type __index = __pos - this->_M_impl._M_start; 435 value_type __x_copy = __x; // XXX copy 436 if (static_cast<size_type>(__index) < size() / 2) 437 { 438 push_front(front()); 439 iterator __front1 = this->_M_impl._M_start; 440 ++__front1; 441 iterator __front2 = __front1; 442 ++__front2; 443 __pos = this->_M_impl._M_start + __index; 444 iterator __pos1 = __pos; 445 ++__pos1; 446 std::copy(__front2, __pos1, __front1); 447 } 448 else 449 { 450 push_back(back()); 451 iterator __back1 = this->_M_impl._M_finish; 452 --__back1; 453 iterator __back2 = __back1; 454 --__back2; 455 __pos = this->_M_impl._M_start + __index; 456 std::copy_backward(__pos, __back2, __back1); 457 } 458 *__pos = __x_copy; 459 return __pos; 460 } 461 462 template <typename _Tp, typename _Alloc> 463 void 464 deque<_Tp, _Alloc>:: 465 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) 466 { 467 const difference_type __elems_before = __pos - this->_M_impl._M_start; 468 const size_type __length = this->size(); 469 value_type __x_copy = __x; 470 if (__elems_before < difference_type(__length / 2)) 471 { 472 iterator __new_start = _M_reserve_elements_at_front(__n); 473 iterator __old_start = this->_M_impl._M_start; 474 __pos = this->_M_impl._M_start + __elems_before; 475 try 476 { 477 if (__elems_before >= difference_type(__n)) 478 { 479 iterator __start_n = (this->_M_impl._M_start 480 + difference_type(__n)); 481 std::__uninitialized_copy_a(this->_M_impl._M_start, 482 __start_n, __new_start, 483 _M_get_Tp_allocator()); 484 this->_M_impl._M_start = __new_start; 485 std::copy(__start_n, __pos, __old_start); 486 std::fill(__pos - difference_type(__n), __pos, __x_copy); 487 } 488 else 489 { 490 std::__uninitialized_copy_fill(this->_M_impl._M_start, 491 __pos, __new_start, 492 this->_M_impl._M_start, 493 __x_copy, 494 _M_get_Tp_allocator()); 495 this->_M_impl._M_start = __new_start; 496 std::fill(__old_start, __pos, __x_copy); 497 } 498 } 499 catch(...) 500 { 501 _M_destroy_nodes(__new_start._M_node, 502 this->_M_impl._M_start._M_node); 503 __throw_exception_again; 504 } 505 } 506 else 507 { 508 iterator __new_finish = _M_reserve_elements_at_back(__n); 509 iterator __old_finish = this->_M_impl._M_finish; 510 const difference_type __elems_after = 511 difference_type(__length) - __elems_before; 512 __pos = this->_M_impl._M_finish - __elems_after; 513 try 514 { 515 if (__elems_after > difference_type(__n)) 516 { 517 iterator __finish_n = (this->_M_impl._M_finish 518 - difference_type(__n)); 519 std::__uninitialized_copy_a(__finish_n, 520 this->_M_impl._M_finish, 521 this->_M_impl._M_finish, 522 _M_get_Tp_allocator()); 523 this->_M_impl._M_finish = __new_finish; 524 std::copy_backward(__pos, __finish_n, __old_finish); 525 std::fill(__pos, __pos + difference_type(__n), __x_copy); 526 } 527 else 528 { 529 std::__uninitialized_fill_copy(this->_M_impl._M_finish, 530 __pos + difference_type(__n), 531 __x_copy, __pos, 532 this->_M_impl._M_finish, 533 _M_get_Tp_allocator()); 534 this->_M_impl._M_finish = __new_finish; 535 std::fill(__pos, __old_finish, __x_copy); 536 } 537 } 538 catch(...) 539 { 540 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 541 __new_finish._M_node + 1); 542 __throw_exception_again; 543 } 544 } 545 } 546 547 template <typename _Tp, typename _Alloc> 548 template <typename _ForwardIterator> 549 void 550 deque<_Tp, _Alloc>:: 551 _M_insert_aux(iterator __pos, 552 _ForwardIterator __first, _ForwardIterator __last, 553 size_type __n) 554 { 555 const difference_type __elemsbefore = __pos - this->_M_impl._M_start; 556 const size_type __length = size(); 557 if (static_cast<size_type>(__elemsbefore) < __length / 2) 558 { 559 iterator __new_start = _M_reserve_elements_at_front(__n); 560 iterator __old_start = this->_M_impl._M_start; 561 __pos = this->_M_impl._M_start + __elemsbefore; 562 try 563 { 564 if (__elemsbefore >= difference_type(__n)) 565 { 566 iterator __start_n = (this->_M_impl._M_start 567 + difference_type(__n)); 568 std::__uninitialized_copy_a(this->_M_impl._M_start, 569 __start_n, __new_start, 570 _M_get_Tp_allocator()); 571 this->_M_impl._M_start = __new_start; 572 std::copy(__start_n, __pos, __old_start); 573 std::copy(__first, __last, __pos - difference_type(__n)); 574 } 575 else 576 { 577 _ForwardIterator __mid = __first; 578 std::advance(__mid, difference_type(__n) - __elemsbefore); 579 std::__uninitialized_copy_copy(this->_M_impl._M_start, 580 __pos, __first, __mid, 581 __new_start, 582 _M_get_Tp_allocator()); 583 this->_M_impl._M_start = __new_start; 584 std::copy(__mid, __last, __old_start); 585 } 586 } 587 catch(...) 588 { 589 _M_destroy_nodes(__new_start._M_node, 590 this->_M_impl._M_start._M_node); 591 __throw_exception_again; 592 } 593 } 594 else 595 { 596 iterator __new_finish = _M_reserve_elements_at_back(__n); 597 iterator __old_finish = this->_M_impl._M_finish; 598 const difference_type __elemsafter = 599 difference_type(__length) - __elemsbefore; 600 __pos = this->_M_impl._M_finish - __elemsafter; 601 try 602 { 603 if (__elemsafter > difference_type(__n)) 604 { 605 iterator __finish_n = (this->_M_impl._M_finish 606 - difference_type(__n)); 607 std::__uninitialized_copy_a(__finish_n, 608 this->_M_impl._M_finish, 609 this->_M_impl._M_finish, 610 _M_get_Tp_allocator()); 611 this->_M_impl._M_finish = __new_finish; 612 std::copy_backward(__pos, __finish_n, __old_finish); 613 std::copy(__first, __last, __pos); 614 } 615 else 616 { 617 _ForwardIterator __mid = __first; 618 std::advance(__mid, __elemsafter); 619 std::__uninitialized_copy_copy(__mid, __last, __pos, 620 this->_M_impl._M_finish, 621 this->_M_impl._M_finish, 622 _M_get_Tp_allocator()); 623 this->_M_impl._M_finish = __new_finish; 624 std::copy(__first, __mid, __pos); 625 } 626 } 627 catch(...) 628 { 629 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 630 __new_finish._M_node + 1); 631 __throw_exception_again; 632 } 633 } 634 } 635 636 template<typename _Tp, typename _Alloc> 637 void 638 deque<_Tp, _Alloc>:: 639 _M_destroy_data_aux(iterator __first, iterator __last) 640 { 641 for (_Map_pointer __node = __first._M_node + 1; 642 __node < __last._M_node; ++__node) 643 std::_Destroy(*__node, *__node + _S_buffer_size(), 644 _M_get_Tp_allocator()); 645 646 if (__first._M_node != __last._M_node) 647 { 648 std::_Destroy(__first._M_cur, __first._M_last, 649 _M_get_Tp_allocator()); 650 std::_Destroy(__last._M_first, __last._M_cur, 651 _M_get_Tp_allocator()); 652 } 653 else 654 std::_Destroy(__first._M_cur, __last._M_cur, 655 _M_get_Tp_allocator()); 656 } 657 658 template <typename _Tp, typename _Alloc> 659 void 660 deque<_Tp, _Alloc>:: 661 _M_new_elements_at_front(size_type __new_elems) 662 { 663 if (this->max_size() - this->size() < __new_elems) 664 __throw_length_error(__N("deque::_M_new_elements_at_front")); 665 666 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 667 / _S_buffer_size()); 668 _M_reserve_map_at_front(__new_nodes); 669 size_type __i; 670 try 671 { 672 for (__i = 1; __i <= __new_nodes; ++__i) 673 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); 674 } 675 catch(...) 676 { 677 for (size_type __j = 1; __j < __i; ++__j) 678 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); 679 __throw_exception_again; 680 } 681 } 682 683 template <typename _Tp, typename _Alloc> 684 void 685 deque<_Tp, _Alloc>:: 686 _M_new_elements_at_back(size_type __new_elems) 687 { 688 if (this->max_size() - this->size() < __new_elems) 689 __throw_length_error(__N("deque::_M_new_elements_at_back")); 690 691 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) 692 / _S_buffer_size()); 693 _M_reserve_map_at_back(__new_nodes); 694 size_type __i; 695 try 696 { 697 for (__i = 1; __i <= __new_nodes; ++__i) 698 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); 699 } 700 catch(...) 701 { 702 for (size_type __j = 1; __j < __i; ++__j) 703 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); 704 __throw_exception_again; 705 } 706 } 707 708 template <typename _Tp, typename _Alloc> 709 void 710 deque<_Tp, _Alloc>:: 711 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) 712 { 713 const size_type __old_num_nodes 714 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; 715 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 716 717 _Map_pointer __new_nstart; 718 if (this->_M_impl._M_map_size > 2 * __new_num_nodes) 719 { 720 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size 721 - __new_num_nodes) / 2 722 + (__add_at_front ? __nodes_to_add : 0); 723 if (__new_nstart < this->_M_impl._M_start._M_node) 724 std::copy(this->_M_impl._M_start._M_node, 725 this->_M_impl._M_finish._M_node + 1, 726 __new_nstart); 727 else 728 std::copy_backward(this->_M_impl._M_start._M_node, 729 this->_M_impl._M_finish._M_node + 1, 730 __new_nstart + __old_num_nodes); 731 } 732 else 733 { 734 size_type __new_map_size = this->_M_impl._M_map_size 735 + std::max(this->_M_impl._M_map_size, 736 __nodes_to_add) + 2; 737 738 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); 739 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 740 + (__add_at_front ? __nodes_to_add : 0); 741 std::copy(this->_M_impl._M_start._M_node, 742 this->_M_impl._M_finish._M_node + 1, 743 __new_nstart); 744 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 745 746 this->_M_impl._M_map = __new_map; 747 this->_M_impl._M_map_size = __new_map_size; 748 } 749 750 this->_M_impl._M_start._M_set_node(__new_nstart); 751 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 752 } 753 754 // Overload for deque::iterators, exploiting the "segmented-iterator 755 // optimization". NB: leave const_iterators alone! 756 template<typename _Tp> 757 void 758 fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, 759 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value) 760 { 761 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; 762 763 for (typename _Self::_Map_pointer __node = __first._M_node + 1; 764 __node < __last._M_node; ++__node) 765 std::fill(*__node, *__node + _Self::_S_buffer_size(), __value); 766 767 if (__first._M_node != __last._M_node) 768 { 769 std::fill(__first._M_cur, __first._M_last, __value); 770 std::fill(__last._M_first, __last._M_cur, __value); 771 } 772 else 773 std::fill(__first._M_cur, __last._M_cur, __value); 774 } 775 776_GLIBCXX_END_NESTED_NAMESPACE 777 778#endif 779