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 00135 && __last == this->_M_impl._M_finish) 00136 { 00137 clear(); 00138 return this->_M_impl._M_finish; 00139 } 00140 else 00141 { 00142 const difference_type __n = __last - __first; 00143 const difference_type __elems_before = (__first 00144 - this->_M_impl._M_start); 00145 if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) 00146 { 00147 std::copy_backward(this->_M_impl._M_start, __first, __last); 00148 iterator __new_start = this->_M_impl._M_start + __n; 00149 std::_Destroy(this->_M_impl._M_start, __new_start); 00150 _M_destroy_nodes(this->_M_impl._M_start._M_node, 00151 __new_start._M_node); 00152 this->_M_impl._M_start = __new_start; 00153 } 00154 else 00155 { 00156 std::copy(__last, this->_M_impl._M_finish, __first); 00157 iterator __new_finish = this->_M_impl._M_finish - __n; 00158 std::_Destroy(__new_finish, this->_M_impl._M_finish); 00159 _M_destroy_nodes(__new_finish._M_node + 1, 00160 this->_M_impl._M_finish._M_node + 1); 00161 this->_M_impl._M_finish = __new_finish; 00162 } 00163 return this->_M_impl._M_start + __elems_before; 00164 } 00165 } 00166 00167 template <typename _Tp, typename _Alloc> 00168 void 00169 deque<_Tp,_Alloc>:: 00170 clear() 00171 { 00172 for (_Map_pointer __node = this->_M_impl._M_start._M_node + 1; 00173 __node < this->_M_impl._M_finish._M_node; 00174 ++__node) 00175 { 00176 std::_Destroy(*__node, *__node + _S_buffer_size()); 00177 _M_deallocate_node(*__node); 00178 } 00179 00180 if (this->_M_impl._M_start._M_node != this->_M_impl._M_finish._M_node) 00181 { 00182 std::_Destroy(this->_M_impl._M_start._M_cur, 00183 this->_M_impl._M_start._M_last); 00184 std::_Destroy(this->_M_impl._M_finish._M_first, 00185 this->_M_impl._M_finish._M_cur); 00186 _M_deallocate_node(this->_M_impl._M_finish._M_first); 00187 } 00188 else 00189 std::_Destroy(this->_M_impl._M_start._M_cur, 00190 this->_M_impl._M_finish._M_cur); 00191 00192 this->_M_impl._M_finish = this->_M_impl._M_start; 00193 } 00194 00195 template <typename _Tp, class _Alloc> 00196 template <typename _InputIterator> 00197 void 00198 deque<_Tp,_Alloc> 00199 ::_M_assign_aux(_InputIterator __first, _InputIterator __last, 00200 input_iterator_tag) 00201 { 00202 iterator __cur = begin(); 00203 for ( ; __first != __last && __cur != end(); ++__cur, ++__first) 00204 *__cur = *__first; 00205 if (__first == __last) 00206 erase(__cur, end()); 00207 else 00208 insert(end(), __first, __last); 00209 } 00210 00211 template <typename _Tp, typename _Alloc> 00212 void 00213 deque<_Tp,_Alloc>:: 00214 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) 00215 { 00216 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 00217 { 00218 iterator __new_start = _M_reserve_elements_at_front(__n); 00219 try 00220 { 00221 std::uninitialized_fill(__new_start, this->_M_impl._M_start, __x); 00222 this->_M_impl._M_start = __new_start; 00223 } 00224 catch(...) 00225 { 00226 _M_destroy_nodes(__new_start._M_node, 00227 this->_M_impl._M_start._M_node); 00228 __throw_exception_again; 00229 } 00230 } 00231 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 00232 { 00233 iterator __new_finish = _M_reserve_elements_at_back(__n); 00234 try 00235 { 00236 std::uninitialized_fill(this->_M_impl._M_finish, 00237 __new_finish, __x); 00238 this->_M_impl._M_finish = __new_finish; 00239 } 00240 catch(...) 00241 { 00242 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00243 __new_finish._M_node + 1); 00244 __throw_exception_again; 00245 } 00246 } 00247 else 00248 _M_insert_aux(__pos, __n, __x); 00249 } 00250 00251 template <typename _Tp, typename _Alloc> 00252 void 00253 deque<_Tp,_Alloc>:: 00254 _M_fill_initialize(const value_type& __value) 00255 { 00256 _Map_pointer __cur; 00257 try 00258 { 00259 for (__cur = this->_M_impl._M_start._M_node; 00260 __cur < this->_M_impl._M_finish._M_node; 00261 ++__cur) 00262 std::uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value); 00263 std::uninitialized_fill(this->_M_impl._M_finish._M_first, 00264 this->_M_impl._M_finish._M_cur, 00265 __value); 00266 } 00267 catch(...) 00268 { 00269 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur)); 00270 __throw_exception_again; 00271 } 00272 } 00273 00274 template <typename _Tp, typename _Alloc> 00275 template <typename _InputIterator> 00276 void 00277 deque<_Tp,_Alloc>:: 00278 _M_range_initialize(_InputIterator __first, _InputIterator __last, 00279 input_iterator_tag) 00280 { 00281 this->_M_initialize_map(0); 00282 try 00283 { 00284 for ( ; __first != __last; ++__first) 00285 push_back(*__first); 00286 } 00287 catch(...) 00288 { 00289 clear(); 00290 __throw_exception_again; 00291 } 00292 } 00293 00294 template <typename _Tp, typename _Alloc> 00295 template <typename _ForwardIterator> 00296 void 00297 deque<_Tp,_Alloc>:: 00298 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, 00299 forward_iterator_tag) 00300 { 00301 const size_type __n = std::distance(__first, __last); 00302 this->_M_initialize_map(__n); 00303 00304 _Map_pointer __cur_node; 00305 try 00306 { 00307 for (__cur_node = this->_M_impl._M_start._M_node; 00308 __cur_node < this->_M_impl._M_finish._M_node; 00309 ++__cur_node) 00310 { 00311 _ForwardIterator __mid = __first; 00312 std::advance(__mid, _S_buffer_size()); 00313 std::uninitialized_copy(__first, __mid, *__cur_node); 00314 __first = __mid; 00315 } 00316 std::uninitialized_copy(__first, __last, 00317 this->_M_impl._M_finish._M_first); 00318 } 00319 catch(...) 00320 { 00321 std::_Destroy(this->_M_impl._M_start, 00322 iterator(*__cur_node, __cur_node)); 00323 __throw_exception_again; 00324 } 00325 } 00326 00327 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. 00328 template <typename _Tp, typename _Alloc> 00329 void 00330 deque<_Tp,_Alloc>:: 00331 _M_push_back_aux(const value_type& __t) 00332 { 00333 value_type __t_copy = __t; 00334 _M_reserve_map_at_back(); 00335 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); 00336 try 00337 { 00338 std::_Construct(this->_M_impl._M_finish._M_cur, __t_copy); 00339 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node 00340 + 1); 00341 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; 00342 } 00343 catch(...) 00344 { 00345 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); 00346 __throw_exception_again; 00347 } 00348 } 00349 00350 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. 00351 template <typename _Tp, typename _Alloc> 00352 void 00353 deque<_Tp,_Alloc>:: 00354 _M_push_front_aux(const value_type& __t) 00355 { 00356 value_type __t_copy = __t; 00357 _M_reserve_map_at_front(); 00358 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); 00359 try 00360 { 00361 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node 00362 - 1); 00363 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; 00364 std::_Construct(this->_M_impl._M_start._M_cur, __t_copy); 00365 } 00366 catch(...) 00367 { 00368 ++this->_M_impl._M_start; 00369 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); 00370 __throw_exception_again; 00371 } 00372 } 00373 00374 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. 00375 template <typename _Tp, typename _Alloc> 00376 void deque<_Tp,_Alloc>:: 00377 _M_pop_back_aux() 00378 { 00379 _M_deallocate_node(this->_M_impl._M_finish._M_first); 00380 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); 00381 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; 00382 std::_Destroy(this->_M_impl._M_finish._M_cur); 00383 } 00384 00385 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. 00386 // Note that if the deque has at least one element (a precondition for this 00387 // member function), and if 00388 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, 00389 // then the deque must have at least two nodes. 00390 template <typename _Tp, typename _Alloc> 00391 void deque<_Tp,_Alloc>:: 00392 _M_pop_front_aux() 00393 { 00394 std::_Destroy(this->_M_impl._M_start._M_cur); 00395 _M_deallocate_node(this->_M_impl._M_start._M_first); 00396 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); 00397 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; 00398 } 00399 00400 template <typename _Tp, typename _Alloc> 00401 template <typename _InputIterator> 00402 void 00403 deque<_Tp,_Alloc>:: 00404 _M_range_insert_aux(iterator __pos, 00405 _InputIterator __first, _InputIterator __last, 00406 input_iterator_tag) 00407 { std::copy(__first, __last, std::inserter(*this, __pos)); } 00408 00409 template <typename _Tp, typename _Alloc> 00410 template <typename _ForwardIterator> 00411 void 00412 deque<_Tp,_Alloc>:: 00413 _M_range_insert_aux(iterator __pos, 00414 _ForwardIterator __first, _ForwardIterator __last, 00415 forward_iterator_tag) 00416 { 00417 size_type __n = std::distance(__first, __last); 00418 if (__pos._M_cur == this->_M_impl._M_start._M_cur) 00419 { 00420 iterator __new_start = _M_reserve_elements_at_front(__n); 00421 try 00422 { 00423 std::uninitialized_copy(__first, __last, __new_start); 00424 this->_M_impl._M_start = __new_start; 00425 } 00426 catch(...) 00427 { 00428 _M_destroy_nodes(__new_start._M_node, 00429 this->_M_impl._M_start._M_node); 00430 __throw_exception_again; 00431 } 00432 } 00433 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) 00434 { 00435 iterator __new_finish = _M_reserve_elements_at_back(__n); 00436 try 00437 { 00438 std::uninitialized_copy(__first, __last, 00439 this->_M_impl._M_finish); 00440 this->_M_impl._M_finish = __new_finish; 00441 } 00442 catch(...) 00443 { 00444 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00445 __new_finish._M_node + 1); 00446 __throw_exception_again; 00447 } 00448 } 00449 else 00450 _M_insert_aux(__pos, __first, __last, __n); 00451 } 00452 00453 template <typename _Tp, typename _Alloc> 00454 typename deque<_Tp, _Alloc>::iterator 00455 deque<_Tp,_Alloc>:: 00456 _M_insert_aux(iterator __pos, const value_type& __x) 00457 { 00458 difference_type __index = __pos - this->_M_impl._M_start; 00459 value_type __x_copy = __x; // XXX copy 00460 if (static_cast<size_type>(__index) < size() / 2) 00461 { 00462 push_front(front()); 00463 iterator __front1 = this->_M_impl._M_start; 00464 ++__front1; 00465 iterator __front2 = __front1; 00466 ++__front2; 00467 __pos = this->_M_impl._M_start + __index; 00468 iterator __pos1 = __pos; 00469 ++__pos1; 00470 std::copy(__front2, __pos1, __front1); 00471 } 00472 else 00473 { 00474 push_back(back()); 00475 iterator __back1 = this->_M_impl._M_finish; 00476 --__back1; 00477 iterator __back2 = __back1; 00478 --__back2; 00479 __pos = this->_M_impl._M_start + __index; 00480 std::copy_backward(__pos, __back2, __back1); 00481 } 00482 *__pos = __x_copy; 00483 return __pos; 00484 } 00485 00486 template <typename _Tp, typename _Alloc> 00487 void 00488 deque<_Tp,_Alloc>:: 00489 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) 00490 { 00491 const difference_type __elems_before = __pos - this->_M_impl._M_start; 00492 size_type __length = this->size(); 00493 value_type __x_copy = __x; 00494 if (__elems_before < difference_type(__length / 2)) 00495 { 00496 iterator __new_start = _M_reserve_elements_at_front(__n); 00497 iterator __old_start = this->_M_impl._M_start; 00498 __pos = this->_M_impl._M_start + __elems_before; 00499 try 00500 { 00501 if (__elems_before >= difference_type(__n)) 00502 { 00503 iterator __start_n = (this->_M_impl._M_start 00504 + difference_type(__n)); 00505 std::uninitialized_copy(this->_M_impl._M_start, __start_n, 00506 __new_start); 00507 this->_M_impl._M_start = __new_start; 00508 std::copy(__start_n, __pos, __old_start); 00509 fill(__pos - difference_type(__n), __pos, __x_copy); 00510 } 00511 else 00512 { 00513 std::__uninitialized_copy_fill(this->_M_impl._M_start, 00514 __pos, __new_start, 00515 this->_M_impl._M_start, 00516 __x_copy); 00517 this->_M_impl._M_start = __new_start; 00518 std::fill(__old_start, __pos, __x_copy); 00519 } 00520 } 00521 catch(...) 00522 { 00523 _M_destroy_nodes(__new_start._M_node, 00524 this->_M_impl._M_start._M_node); 00525 __throw_exception_again; 00526 } 00527 } 00528 else 00529 { 00530 iterator __new_finish = _M_reserve_elements_at_back(__n); 00531 iterator __old_finish = this->_M_impl._M_finish; 00532 const difference_type __elems_after = 00533 difference_type(__length) - __elems_before; 00534 __pos = this->_M_impl._M_finish - __elems_after; 00535 try 00536 { 00537 if (__elems_after > difference_type(__n)) 00538 { 00539 iterator __finish_n = (this->_M_impl._M_finish 00540 - difference_type(__n)); 00541 std::uninitialized_copy(__finish_n, this->_M_impl._M_finish, 00542 this->_M_impl._M_finish); 00543 this->_M_impl._M_finish = __new_finish; 00544 std::copy_backward(__pos, __finish_n, __old_finish); 00545 std::fill(__pos, __pos + difference_type(__n), __x_copy); 00546 } 00547 else 00548 { 00549 std::__uninitialized_fill_copy(this->_M_impl._M_finish, 00550 __pos + difference_type(__n), 00551 __x_copy, __pos, 00552 this->_M_impl._M_finish); 00553 this->_M_impl._M_finish = __new_finish; 00554 std::fill(__pos, __old_finish, __x_copy); 00555 } 00556 } 00557 catch(...) 00558 { 00559 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00560 __new_finish._M_node + 1); 00561 __throw_exception_again; 00562 } 00563 } 00564 } 00565 00566 template <typename _Tp, typename _Alloc> 00567 template <typename _ForwardIterator> 00568 void 00569 deque<_Tp,_Alloc>:: 00570 _M_insert_aux(iterator __pos, 00571 _ForwardIterator __first, _ForwardIterator __last, 00572 size_type __n) 00573 { 00574 const difference_type __elemsbefore = __pos - this->_M_impl._M_start; 00575 size_type __length = size(); 00576 if (static_cast<size_type>(__elemsbefore) < __length / 2) 00577 { 00578 iterator __new_start = _M_reserve_elements_at_front(__n); 00579 iterator __old_start = this->_M_impl._M_start; 00580 __pos = this->_M_impl._M_start + __elemsbefore; 00581 try 00582 { 00583 if (__elemsbefore >= difference_type(__n)) 00584 { 00585 iterator __start_n = (this->_M_impl._M_start 00586 + difference_type(__n)); 00587 std::uninitialized_copy(this->_M_impl._M_start, __start_n, 00588 __new_start); 00589 this->_M_impl._M_start = __new_start; 00590 std::copy(__start_n, __pos, __old_start); 00591 std::copy(__first, __last, __pos - difference_type(__n)); 00592 } 00593 else 00594 { 00595 _ForwardIterator __mid = __first; 00596 std::advance(__mid, difference_type(__n) - __elemsbefore); 00597 std::__uninitialized_copy_copy(this->_M_impl._M_start, 00598 __pos, __first, __mid, 00599 __new_start); 00600 this->_M_impl._M_start = __new_start; 00601 std::copy(__mid, __last, __old_start); 00602 } 00603 } 00604 catch(...) 00605 { 00606 _M_destroy_nodes(__new_start._M_node, 00607 this->_M_impl._M_start._M_node); 00608 __throw_exception_again; 00609 } 00610 } 00611 else 00612 { 00613 iterator __new_finish = _M_reserve_elements_at_back(__n); 00614 iterator __old_finish = this->_M_impl._M_finish; 00615 const difference_type __elemsafter = 00616 difference_type(__length) - __elemsbefore; 00617 __pos = this->_M_impl._M_finish - __elemsafter; 00618 try 00619 { 00620 if (__elemsafter > difference_type(__n)) 00621 { 00622 iterator __finish_n = (this->_M_impl._M_finish 00623 - difference_type(__n)); 00624 std::uninitialized_copy(__finish_n, 00625 this->_M_impl._M_finish, 00626 this->_M_impl._M_finish); 00627 this->_M_impl._M_finish = __new_finish; 00628 std::copy_backward(__pos, __finish_n, __old_finish); 00629 std::copy(__first, __last, __pos); 00630 } 00631 else 00632 { 00633 _ForwardIterator __mid = __first; 00634 std::advance(__mid, __elemsafter); 00635 std::__uninitialized_copy_copy(__mid, __last, __pos, 00636 this->_M_impl._M_finish, 00637 this->_M_impl._M_finish); 00638 this->_M_impl._M_finish = __new_finish; 00639 std::copy(__first, __mid, __pos); 00640 } 00641 } 00642 catch(...) 00643 { 00644 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, 00645 __new_finish._M_node + 1); 00646 __throw_exception_again; 00647 } 00648 } 00649 } 00650 00651 template <typename _Tp, typename _Alloc> 00652 void 00653 deque<_Tp,_Alloc>:: 00654 _M_new_elements_at_front(size_type __new_elems) 00655 { 00656 size_type __new_nodes 00657 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); 00658 _M_reserve_map_at_front(__new_nodes); 00659 size_type __i; 00660 try 00661 { 00662 for (__i = 1; __i <= __new_nodes; ++__i) 00663 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); 00664 } 00665 catch(...) 00666 { 00667 for (size_type __j = 1; __j < __i; ++__j) 00668 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); 00669 __throw_exception_again; 00670 } 00671 } 00672 00673 template <typename _Tp, typename _Alloc> 00674 void 00675 deque<_Tp,_Alloc>:: 00676 _M_new_elements_at_back(size_type __new_elems) 00677 { 00678 size_type __new_nodes 00679 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); 00680 _M_reserve_map_at_back(__new_nodes); 00681 size_type __i; 00682 try 00683 { 00684 for (__i = 1; __i <= __new_nodes; ++__i) 00685 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); 00686 } 00687 catch(...) 00688 { 00689 for (size_type __j = 1; __j < __i; ++__j) 00690 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); 00691 __throw_exception_again; 00692 } 00693 } 00694 00695 template <typename _Tp, typename _Alloc> 00696 void 00697 deque<_Tp,_Alloc>:: 00698 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) 00699 { 00700 size_type __old_num_nodes 00701 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; 00702 size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 00703 00704 _Map_pointer __new_nstart; 00705 if (this->_M_impl._M_map_size > 2 * __new_num_nodes) 00706 { 00707 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size 00708 - __new_num_nodes) / 2 00709 + (__add_at_front ? __nodes_to_add : 0); 00710 if (__new_nstart < this->_M_impl._M_start._M_node) 00711 std::copy(this->_M_impl._M_start._M_node, 00712 this->_M_impl._M_finish._M_node + 1, 00713 __new_nstart); 00714 else 00715 std::copy_backward(this->_M_impl._M_start._M_node, 00716 this->_M_impl._M_finish._M_node + 1, 00717 __new_nstart + __old_num_nodes); 00718 } 00719 else 00720 { 00721 size_type __new_map_size = this->_M_impl._M_map_size 00722 + std::max(this->_M_impl._M_map_size, 00723 __nodes_to_add) + 2; 00724 00725 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); 00726 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 00727 + (__add_at_front ? __nodes_to_add : 0); 00728 std::copy(this->_M_impl._M_start._M_node, 00729 this->_M_impl._M_finish._M_node + 1, 00730 __new_nstart); 00731 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); 00732 00733 this->_M_impl._M_map = __new_map; 00734 this->_M_impl._M_map_size = __new_map_size; 00735 } 00736 00737 this->_M_impl._M_start._M_set_node(__new_nstart); 00738 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 00739 } 00740 } // namespace std 00741 00742 #endif

Generated on Wed Jun 9 11:18:20 2004 for libstdc++-v3 Source by doxygen 1.3.7