deque.tcc

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

Generated on Wed Aug 4 21:43:09 2004 for libstdc++-v3 Source by doxygen 1.3.8