deque.tcc

Go to the documentation of this file.
00001 // Deque implementation (out of line) -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 2, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * 00032 * Copyright (c) 1994 00033 * Hewlett-Packard Company 00034 * 00035 * Permission to use, copy, modify, distribute and sell this software 00036 * and its documentation for any purpose is hereby granted without fee, 00037 * provided that the above copyright notice appear in all copies and 00038 * that both that copyright notice and this permission notice appear 00039 * in supporting documentation. Hewlett-Packard Company makes no 00040 * representations about the suitability of this software for any 00041 * purpose. It is provided "as is" without express or implied warranty. 00042 * 00043 * 00044 * Copyright (c) 1997 00045 * Silicon Graphics Computer Systems, Inc. 00046 * 00047 * Permission to use, copy, modify, distribute and sell this software 00048 * and its documentation for any purpose is hereby granted without fee, 00049 * provided that the above copyright notice appear in all copies and 00050 * that both that copyright notice and this permission notice appear 00051 * in supporting documentation. Silicon Graphics makes no 00052 * representations about the suitability of this software for any 00053 * purpose. It is provided "as is" without express or implied warranty. 00054 */ 00055 00056 /** @file deque.tcc 00057 * This is an internal header file, included by other library headers. 00058 * You should not attempt to use it directly. 00059 */ 00060 00061 #ifndef _DEQUE_TCC 00062 #define _DEQUE_TCC 1 00063 00064 namespace _GLIBCXX_STD 00065 { 00066 template <typename _Tp, typename _Alloc> 00067 deque<_Tp,_Alloc>& 00068 deque<_Tp,_Alloc>:: 00069 operator=(const deque& __x) 00070 { 00071 const size_type __len = size(); 00072 if (&__x != this) 00073 { 00074 if (__len >= __x.size()) 00075 erase(std::copy(__x.begin(), __x.end(), this->_M_impl._M_start), 00076 this->_M_impl._M_finish); 00077 else 00078 { 00079 const_iterator __mid = __x.begin() + difference_type(__len); 00080 std::copy(__x.begin(), __mid, this->_M_impl._M_start); 00081 insert(this->_M_impl._M_finish, __mid, __x.end()); 00082 } 00083 } 00084 return *this; 00085 } 00086 00087 template <typename _Tp, typename _Alloc> 00088 typename deque<_Tp,_Alloc>::iterator 00089 deque<_Tp,_Alloc>:: 00090 insert(iterator position, const value_type& __x) 00091 { 00092 if (position._M_cur == this->_M_impl._M_start._M_cur) 00093 { 00094 push_front(__x); 00095 return this->_M_impl._M_start; 00096 } 00097 else if (position._M_cur == this->_M_impl._M_finish._M_cur) 00098 { 00099 push_back(__x); 00100 iterator __tmp = this->_M_impl._M_finish; 00101 --__tmp; 00102 return __tmp; 00103 } 00104 else 00105 return _M_insert_aux(position, __x); 00106 } 00107 00108 template <typename _Tp, typename _Alloc> 00109 typename deque<_Tp,_Alloc>::iterator 00110 deque<_Tp,_Alloc>:: 00111 erase(iterator __position) 00112 { 00113 iterator __next = __position; 00114 ++__next; 00115 size_type __index = __position - this->_M_impl._M_start; 00116 if (__index < (size() >> 1)) 00117 { 00118 std::copy_backward(this->_M_impl._M_start, __position, __next); 00119 pop_front(); 00120 } 00121 else 00122 { 00123 std::copy(__next, this->_M_impl._M_finish, __position); 00124 pop_back(); 00125 } 00126 return this->_M_impl._M_start + __index; 00127 } 00128 00129 template <typename _Tp, typename _Alloc> 00130 typename deque<_Tp,_Alloc>::iterator 00131 deque<_Tp,_Alloc>:: 00132 erase(iterator __first, iterator __last) 00133 { 00134 if (__first == this->_M_impl._M_start && __last == this->_M_impl._M_finish) 00135 { 00136 clear(); 00137 return this->_M_impl._M_finish; 00138 } 00139 else 00140 { 00141 const difference_type __n = __last - __first; 00142 const difference_type __elems_before = __first - this->_M_impl._M_start; 00143 if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) 00144 { 00145 std::copy_backward(this->_M_impl._M_start, __first, __last); 00146 iterator __new_start = this->_M_impl._M_start + __n; 00147 std::_Destroy(this->_M_impl._M_start, __new_start); 00148 _M_destroy_nodes(this->_M_impl._M_start._M_node, __new_start._M_node); 00149 this->_M_impl._M_start = __new_start; 00150 } 00151 else 00152 { 00153 std::copy(__last, this->_M_impl._M_finish, __first); 00154 iterator __new_finish = this->_M_impl._M_finish - __n; 00155 std::_Destroy(__new_finish, this->_M_impl._M_finish); 00156 _M_destroy_nodes(__new_finish._M_node + 1, 00157 this->_M_impl._M_finish._M_node + 1); 00158 this->_M_impl._M_finish = __new_finish; 00159 } 00160 return this->_M_impl._M_start + __elems_before; 00161 } 00162 } 00163 00164 template <typename _Tp, typename _Alloc> 00165 void 00166 deque<_Tp,_Alloc>:: 00167 clear() 00168 { 00169 for (_Map_pointer __node = this->_M_impl._M_start._M_node + 1; 00170 __node < this->_M_impl._M_finish._M_node; 00171 ++__node) 00172 { 00173 std::_Destroy(*__node, *__node + _S_buffer_size()); 00174 _M_deallocate_node(*__node); 00175 } 00176 00177 if (this->_M_impl._M_start._M_node != this->_M_impl._M_finish._M_node) 00178 { 00179 std::_Destroy(this->_M_impl._M_start._M_cur, this->_M_impl._M_start._M_last); 00180 std::_Destroy(this->_M_impl._M_finish._M_first, this->_M_impl._M_finish._M_cur); 00181 _M_deallocate_node(this->_M_impl._M_finish._M_first); 00182 } 00183 else 00184 std::_Destroy(this->_M_impl._M_start._M_cur, this->_M_impl._M_finish._M_cur); 00185 00186 this->_M_impl._M_finish = this->_M_impl._M_start; 00187 } 00188 00189 template <typename _Tp, class _Alloc> 00190 template <typename _InputIterator> 00191 void 00192 deque<_Tp,_Alloc> 00193 ::_M_assign_aux(_InputIterator __first, _InputIterator __last, 00194 input_iterator_tag) 00195 { 00196 iterator __cur = begin(); 00197 for ( ; __first != __last && __cur != end(); ++__cur, ++__first) 00198 *__cur = *__first; 00199 if (__first == __last) 00200 erase(__cur, end()); 00201 else 00202 insert(end(), __first, __last); 00203 } 00204 00205 template <typename _Tp, typename _Alloc> 00206 void 00207 deque<_Tp,_Alloc>:: 00208 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) 00209 { 00210 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 00211 { 00212 iterator __new_start = _M_reserve_elements_at_front(__n); 00213 try 00214 { 00215 std::uninitialized_fill(__new_start, this->_M_impl._M_start, __x); 00216 this->_M_impl._M_start = __new_start; 00217 } 00218 catch(...) 00219 { 00220 _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node); 00221 __throw_exception_again; 00222 } 00223 } 00224 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 00225 { 00226 iterator __new_finish = _M_reserve_elements_at_back(__n); 00227 try 00228 { 00229 std::uninitialized_fill(this->_M_impl._M_finish, __new_finish, __x); 00230 this->_M_impl._M_finish = __new_finish; 00231 } 00232 catch(...) 00233 { 00234 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00235 __new_finish._M_node + 1); 00236 __throw_exception_again; 00237 } 00238 } 00239 else 00240 _M_insert_aux(__pos, __n, __x); 00241 } 00242 00243 template <typename _Tp, typename _Alloc> 00244 void 00245 deque<_Tp,_Alloc>:: 00246 _M_fill_initialize(const value_type& __value) 00247 { 00248 _Map_pointer __cur; 00249 try 00250 { 00251 for (__cur = this->_M_impl._M_start._M_node; 00252 __cur < this->_M_impl._M_finish._M_node; 00253 ++__cur) 00254 std::uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value); 00255 std::uninitialized_fill(this->_M_impl._M_finish._M_first, 00256 this->_M_impl._M_finish._M_cur, 00257 __value); 00258 } 00259 catch(...) 00260 { 00261 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur)); 00262 __throw_exception_again; 00263 } 00264 } 00265 00266 template <typename _Tp, typename _Alloc> 00267 template <typename _InputIterator> 00268 void 00269 deque<_Tp,_Alloc>:: 00270 _M_range_initialize(_InputIterator __first, _InputIterator __last, 00271 input_iterator_tag) 00272 { 00273 this->_M_initialize_map(0); 00274 try 00275 { 00276 for ( ; __first != __last; ++__first) 00277 push_back(*__first); 00278 } 00279 catch(...) 00280 { 00281 clear(); 00282 __throw_exception_again; 00283 } 00284 } 00285 00286 template <typename _Tp, typename _Alloc> 00287 template <typename _ForwardIterator> 00288 void 00289 deque<_Tp,_Alloc>:: 00290 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 00291 forward_iterator_tag) 00292 { 00293 const size_type __n = std::distance(__first, __last); 00294 this->_M_initialize_map(__n); 00295 00296 _Map_pointer __cur_node; 00297 try 00298 { 00299 for (__cur_node = this->_M_impl._M_start._M_node; 00300 __cur_node < this->_M_impl._M_finish._M_node; 00301 ++__cur_node) 00302 { 00303 _ForwardIterator __mid = __first; 00304 std::advance(__mid, _S_buffer_size()); 00305 std::uninitialized_copy(__first, __mid, *__cur_node); 00306 __first = __mid; 00307 } 00308 std::uninitialized_copy(__first, __last, this->_M_impl._M_finish._M_first); 00309 } 00310 catch(...) 00311 { 00312 std::_Destroy(this->_M_impl._M_start, iterator(*__cur_node, __cur_node)); 00313 __throw_exception_again; 00314 } 00315 } 00316 00317 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. 00318 template <typename _Tp, typename _Alloc> 00319 void 00320 deque<_Tp,_Alloc>:: 00321 _M_push_back_aux(const value_type& __t) 00322 { 00323 value_type __t_copy = __t; 00324 _M_reserve_map_at_back(); 00325 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); 00326 try 00327 { 00328 std::_Construct(this->_M_impl._M_finish._M_cur, __t_copy); 00329 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node + 1); 00330 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; 00331 } 00332 catch(...) 00333 { 00334 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); 00335 __throw_exception_again; 00336 } 00337 } 00338 00339 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. 00340 template <typename _Tp, typename _Alloc> 00341 void 00342 deque<_Tp,_Alloc>:: 00343 _M_push_front_aux(const value_type& __t) 00344 { 00345 value_type __t_copy = __t; 00346 _M_reserve_map_at_front(); 00347 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); 00348 try 00349 { 00350 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node - 1); 00351 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; 00352 std::_Construct(this->_M_impl._M_start._M_cur, __t_copy); 00353 } 00354 catch(...) 00355 { 00356 ++this->_M_impl._M_start; 00357 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); 00358 __throw_exception_again; 00359 } 00360 } 00361 00362 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. 00363 template <typename _Tp, typename _Alloc> 00364 void deque<_Tp,_Alloc>:: 00365 _M_pop_back_aux() 00366 { 00367 _M_deallocate_node(this->_M_impl._M_finish._M_first); 00368 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); 00369 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; 00370 std::_Destroy(this->_M_impl._M_finish._M_cur); 00371 } 00372 00373 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. Note that 00374 // if the deque has at least one element (a precondition for this member 00375 // function), and if _M_impl._M_start._M_cur == _M_impl._M_start._M_last, then the deque 00376 // must have at least two nodes. 00377 template <typename _Tp, typename _Alloc> 00378 void deque<_Tp,_Alloc>:: 00379 _M_pop_front_aux() 00380 { 00381 std::_Destroy(this->_M_impl._M_start._M_cur); 00382 _M_deallocate_node(this->_M_impl._M_start._M_first); 00383 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); 00384 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; 00385 } 00386 00387 template <typename _Tp, typename _Alloc> 00388 template <typename _InputIterator> 00389 void 00390 deque<_Tp,_Alloc>:: 00391 _M_range_insert_aux(iterator __pos, 00392 _InputIterator __first, _InputIterator __last, 00393 input_iterator_tag) 00394 { std::copy(__first, __last, std::inserter(*this, __pos)); } 00395 00396 template <typename _Tp, typename _Alloc> 00397 template <typename _ForwardIterator> 00398 void 00399 deque<_Tp,_Alloc>:: 00400 _M_range_insert_aux(iterator __pos, 00401 _ForwardIterator __first, _ForwardIterator __last, 00402 forward_iterator_tag) 00403 { 00404 size_type __n = std::distance(__first, __last); 00405 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 00406 { 00407 iterator __new_start = _M_reserve_elements_at_front(__n); 00408 try 00409 { 00410 std::uninitialized_copy(__first, __last, __new_start); 00411 this->_M_impl._M_start = __new_start; 00412 } 00413 catch(...) 00414 { 00415 _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node); 00416 __throw_exception_again; 00417 } 00418 } 00419 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 00420 { 00421 iterator __new_finish = _M_reserve_elements_at_back(__n); 00422 try 00423 { 00424 std::uninitialized_copy(__first, __last, this->_M_impl._M_finish); 00425 this->_M_impl._M_finish = __new_finish; 00426 } 00427 catch(...) 00428 { 00429 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00430 __new_finish._M_node + 1); 00431 __throw_exception_again; 00432 } 00433 } 00434 else 00435 _M_insert_aux(__pos, __first, __last, __n); 00436 } 00437 00438 template <typename _Tp, typename _Alloc> 00439 typename deque<_Tp, _Alloc>::iterator 00440 deque<_Tp,_Alloc>:: 00441 _M_insert_aux(iterator __pos, const value_type& __x) 00442 { 00443 difference_type __index = __pos - this->_M_impl._M_start; 00444 value_type __x_copy = __x; // XXX copy 00445 if (static_cast<size_type>(__index) < size() / 2) 00446 { 00447 push_front(front()); 00448 iterator __front1 = this->_M_impl._M_start; 00449 ++__front1; 00450 iterator __front2 = __front1; 00451 ++__front2; 00452 __pos = this->_M_impl._M_start + __index; 00453 iterator __pos1 = __pos; 00454 ++__pos1; 00455 std::copy(__front2, __pos1, __front1); 00456 } 00457 else 00458 { 00459 push_back(back()); 00460 iterator __back1 = this->_M_impl._M_finish; 00461 --__back1; 00462 iterator __back2 = __back1; 00463 --__back2; 00464 __pos = this->_M_impl._M_start + __index; 00465 std::copy_backward(__pos, __back2, __back1); 00466 } 00467 *__pos = __x_copy; 00468 return __pos; 00469 } 00470 00471 template <typename _Tp, typename _Alloc> 00472 void 00473 deque<_Tp,_Alloc>:: 00474 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) 00475 { 00476 const difference_type __elems_before = __pos - this->_M_impl._M_start; 00477 size_type __length = this->size(); 00478 value_type __x_copy = __x; 00479 if (__elems_before < difference_type(__length / 2)) 00480 { 00481 iterator __new_start = _M_reserve_elements_at_front(__n); 00482 iterator __old_start = this->_M_impl._M_start; 00483 __pos = this->_M_impl._M_start + __elems_before; 00484 try 00485 { 00486 if (__elems_before >= difference_type(__n)) 00487 { 00488 iterator __start_n = this->_M_impl._M_start + difference_type(__n); 00489 std::uninitialized_copy(this->_M_impl._M_start, __start_n, 00490 __new_start); 00491 this->_M_impl._M_start = __new_start; 00492 std::copy(__start_n, __pos, __old_start); 00493 fill(__pos - difference_type(__n), __pos, __x_copy); 00494 } 00495 else 00496 { 00497 std::__uninitialized_copy_fill(this->_M_impl._M_start, __pos, 00498 __new_start, 00499 this->_M_impl._M_start, __x_copy); 00500 this->_M_impl._M_start = __new_start; 00501 std::fill(__old_start, __pos, __x_copy); 00502 } 00503 } 00504 catch(...) 00505 { 00506 _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node); 00507 __throw_exception_again; 00508 } 00509 } 00510 else 00511 { 00512 iterator __new_finish = _M_reserve_elements_at_back(__n); 00513 iterator __old_finish = this->_M_impl._M_finish; 00514 const difference_type __elems_after = 00515 difference_type(__length) - __elems_before; 00516 __pos = this->_M_impl._M_finish - __elems_after; 00517 try 00518 { 00519 if (__elems_after > difference_type(__n)) 00520 { 00521 iterator __finish_n = this->_M_impl._M_finish - difference_type(__n); 00522 std::uninitialized_copy(__finish_n, this->_M_impl._M_finish, 00523 this->_M_impl._M_finish); 00524 this->_M_impl._M_finish = __new_finish; 00525 std::copy_backward(__pos, __finish_n, __old_finish); 00526 std::fill(__pos, __pos + difference_type(__n), __x_copy); 00527 } 00528 else 00529 { 00530 std::__uninitialized_fill_copy(this->_M_impl._M_finish, 00531 __pos + difference_type(__n), 00532 __x_copy, __pos, 00533 this->_M_impl._M_finish); 00534 this->_M_impl._M_finish = __new_finish; 00535 std::fill(__pos, __old_finish, __x_copy); 00536 } 00537 } 00538 catch(...) 00539 { 00540 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00541 __new_finish._M_node + 1); 00542 __throw_exception_again; 00543 } 00544 } 00545 } 00546 00547 template <typename _Tp, typename _Alloc> 00548 template <typename _ForwardIterator> 00549 void 00550 deque<_Tp,_Alloc>:: 00551 _M_insert_aux(iterator __pos, 00552 _ForwardIterator __first, _ForwardIterator __last, 00553 size_type __n) 00554 { 00555 const difference_type __elemsbefore = __pos - this->_M_impl._M_start; 00556 size_type __length = size(); 00557 if (static_cast<size_type>(__elemsbefore) < __length / 2) 00558 { 00559 iterator __new_start = _M_reserve_elements_at_front(__n); 00560 iterator __old_start = this->_M_impl._M_start; 00561 __pos = this->_M_impl._M_start + __elemsbefore; 00562 try 00563 { 00564 if (__elemsbefore >= difference_type(__n)) 00565 { 00566 iterator __start_n = this->_M_impl._M_start + difference_type(__n); 00567 std::uninitialized_copy(this->_M_impl._M_start, __start_n, 00568 __new_start); 00569 this->_M_impl._M_start = __new_start; 00570 std::copy(__start_n, __pos, __old_start); 00571 std::copy(__first, __last, __pos - difference_type(__n)); 00572 } 00573 else 00574 { 00575 _ForwardIterator __mid = __first; 00576 std::advance(__mid, difference_type(__n) - __elemsbefore); 00577 std::__uninitialized_copy_copy(this->_M_impl._M_start, __pos, 00578 __first, __mid, __new_start); 00579 this->_M_impl._M_start = __new_start; 00580 std::copy(__mid, __last, __old_start); 00581 } 00582 } 00583 catch(...) 00584 { 00585 _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node); 00586 __throw_exception_again; 00587 } 00588 } 00589 else 00590 { 00591 iterator __new_finish = _M_reserve_elements_at_back(__n); 00592 iterator __old_finish = this->_M_impl._M_finish; 00593 const difference_type __elemsafter = 00594 difference_type(__length) - __elemsbefore; 00595 __pos = this->_M_impl._M_finish - __elemsafter; 00596 try 00597 { 00598 if (__elemsafter > difference_type(__n)) 00599 { 00600 iterator __finish_n = this->_M_impl._M_finish - difference_type(__n); 00601 std::uninitialized_copy(__finish_n, 00602 this->_M_impl._M_finish, 00603 this->_M_impl._M_finish); 00604 this->_M_impl._M_finish = __new_finish; 00605 std::copy_backward(__pos, __finish_n, __old_finish); 00606 std::copy(__first, __last, __pos); 00607 } 00608 else 00609 { 00610 _ForwardIterator __mid = __first; 00611 std::advance(__mid, __elemsafter); 00612 std::__uninitialized_copy_copy(__mid, __last, __pos, 00613 this->_M_impl._M_finish, 00614 this->_M_impl._M_finish); 00615 this->_M_impl._M_finish = __new_finish; 00616 std::copy(__first, __mid, __pos); 00617 } 00618 } 00619 catch(...) 00620 { 00621 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00622 __new_finish._M_node + 1); 00623 __throw_exception_again; 00624 } 00625 } 00626 } 00627 00628 template <typename _Tp, typename _Alloc> 00629 void 00630 deque<_Tp,_Alloc>:: 00631 _M_new_elements_at_front(size_type __new_elems) 00632 { 00633 size_type __new_nodes 00634 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); 00635 _M_reserve_map_at_front(__new_nodes); 00636 size_type __i; 00637 try 00638 { 00639 for (__i = 1; __i <= __new_nodes; ++__i) 00640 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); 00641 } 00642 catch(...) 00643 { 00644 for (size_type __j = 1; __j < __i; ++__j) 00645 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); 00646 __throw_exception_again; 00647 } 00648 } 00649 00650 template <typename _Tp, typename _Alloc> 00651 void 00652 deque<_Tp,_Alloc>:: 00653 _M_new_elements_at_back(size_type __new_elems) 00654 { 00655 size_type __new_nodes 00656 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); 00657 _M_reserve_map_at_back(__new_nodes); 00658 size_type __i; 00659 try 00660 { 00661 for (__i = 1; __i <= __new_nodes; ++__i) 00662 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); 00663 } 00664 catch(...) 00665 { 00666 for (size_type __j = 1; __j < __i; ++__j) 00667 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); 00668 __throw_exception_again; 00669 } 00670 } 00671 00672 template <typename _Tp, typename _Alloc> 00673 void 00674 deque<_Tp,_Alloc>:: 00675 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) 00676 { 00677 size_type __old_num_nodes 00678 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; 00679 size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 00680 00681 _Map_pointer __new_nstart; 00682 if (this->_M_impl._M_map_size > 2 * __new_num_nodes) 00683 { 00684 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size 00685 - __new_num_nodes) / 2 00686 + (__add_at_front ? __nodes_to_add : 0); 00687 if (__new_nstart < this->_M_impl._M_start._M_node) 00688 std::copy(this->_M_impl._M_start._M_node, 00689 this->_M_impl._M_finish._M_node + 1, 00690 __new_nstart); 00691 else 00692 std::copy_backward(this->_M_impl._M_start._M_node, 00693 this->_M_impl._M_finish._M_node + 1, 00694 __new_nstart + __old_num_nodes); 00695 } 00696 else 00697 { 00698 size_type __new_map_size = this->_M_impl._M_map_size 00699 + std::max(this->_M_impl._M_map_size, 00700 __nodes_to_add) + 2; 00701 00702 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); 00703 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 00704 + (__add_at_front ? __nodes_to_add : 0); 00705 std::copy(this->_M_impl._M_start._M_node, 00706 this->_M_impl._M_finish._M_node + 1, 00707 __new_nstart); 00708 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 00709 00710 this->_M_impl._M_map = __new_map; 00711 this->_M_impl._M_map_size = __new_map_size; 00712 } 00713 00714 this->_M_impl._M_start._M_set_node(__new_nstart); 00715 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 00716 } 00717 } // namespace std 00718 00719 #endif

Generated on Tue Sep 7 10:05:03 2004 for libstdc++-v3 Source by doxygen 1.3.8