Branch data Line data Source code
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_D)
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 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
110 : : template<typename _Tp, typename _Alloc>
111 : : template<typename... _Args>
112 : : typename deque<_Tp, _Alloc>::iterator
113 : : deque<_Tp, _Alloc>::
114 : : emplace(iterator __position, _Args&&... __args)
115 : : {
116 : : if (__position._M_cur == this->_M_impl._M_start._M_cur)
117 : : {
118 : : push_front(std::forward<_Args>(__args)...);
119 : : return this->_M_impl._M_start;
120 : : }
121 : : else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
122 : : {
123 : : push_back(std::forward<_Args>(__args)...);
124 : : iterator __tmp = this->_M_impl._M_finish;
125 : : --__tmp;
126 : : return __tmp;
127 : : }
128 : : else
129 : : return _M_insert_aux(__position, std::forward<_Args>(__args)...);
130 : : }
131 : : #endif
132 : :
133 : : template <typename _Tp, typename _Alloc>
134 : : typename deque<_Tp, _Alloc>::iterator
135 : : deque<_Tp, _Alloc>::
136 : : erase(iterator __position)
137 : : {
138 : : iterator __next = __position;
139 : : ++__next;
140 : : const difference_type __index = __position - begin();
141 : : if (static_cast<size_type>(__index) < (size() >> 1))
142 : : {
143 : : if (__position != begin())
144 : : _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
145 : : pop_front();
146 : : }
147 : : else
148 : : {
149 : : if (__next != end())
150 : : _GLIBCXX_MOVE3(__next, end(), __position);
151 : : pop_back();
152 : : }
153 : : return begin() + __index;
154 : : }
155 : :
156 : : template <typename _Tp, typename _Alloc>
157 : : typename deque<_Tp, _Alloc>::iterator
158 : : deque<_Tp, _Alloc>::
159 : : erase(iterator __first, iterator __last)
160 : : {
161 : : if (__first == begin() && __last == end())
162 : : {
163 : : clear();
164 : : return end();
165 : : }
166 : : else
167 : : {
168 : : const difference_type __n = __last - __first;
169 : : const difference_type __elems_before = __first - begin();
170 : : if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
171 : : {
172 : : if (__first != begin())
173 : : _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
174 : : _M_erase_at_begin(begin() + __n);
175 : : }
176 : : else
177 : : {
178 : : if (__last != end())
179 : : _GLIBCXX_MOVE3(__last, end(), __first);
180 : : _M_erase_at_end(end() - __n);
181 : : }
182 : : return begin() + __elems_before;
183 : : }
184 : : }
185 : :
186 : : template <typename _Tp, class _Alloc>
187 : : template <typename _InputIterator>
188 : : void
189 : : deque<_Tp, _Alloc>::
190 : : _M_assign_aux(_InputIterator __first, _InputIterator __last,
191 : : std::input_iterator_tag)
192 : : {
193 : : iterator __cur = begin();
194 : : for (; __first != __last && __cur != end(); ++__cur, ++__first)
195 : : *__cur = *__first;
196 : : if (__first == __last)
197 : : _M_erase_at_end(__cur);
198 : : else
199 : : insert(end(), __first, __last);
200 : : }
201 : :
202 : : template <typename _Tp, typename _Alloc>
203 : : void
204 : : deque<_Tp, _Alloc>::
205 : 8 : _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
206 : : {
207 [ + + ][ + + ]: 8 : if (__pos._M_cur == this->_M_impl._M_start._M_cur)
208 : : {
209 : 4 : iterator __new_start = _M_reserve_elements_at_front(__n);
210 : : try
211 : : {
212 : 4 : std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
213 : : __x, _M_get_Tp_allocator());
214 : 4 : this->_M_impl._M_start = __new_start;
215 : : }
216 : 0 : catch(...)
217 : : {
218 : 0 : _M_destroy_nodes(__new_start._M_node,
219 : : this->_M_impl._M_start._M_node);
220 : 0 : __throw_exception_again;
221 : : }
222 : : }
223 [ + - ][ + - ]: 4 : else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
224 : : {
225 : 4 : iterator __new_finish = _M_reserve_elements_at_back(__n);
226 : : try
227 : : {
228 : 4 : std::__uninitialized_fill_a(this->_M_impl._M_finish,
229 : : __new_finish, __x,
230 : : _M_get_Tp_allocator());
231 : 4 : this->_M_impl._M_finish = __new_finish;
232 : : }
233 : 0 : catch(...)
234 : : {
235 : 0 : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
236 : : __new_finish._M_node + 1);
237 : 0 : __throw_exception_again;
238 : : }
239 : : }
240 : : else
241 : 0 : _M_insert_aux(__pos, __n, __x);
242 : 8 : }
243 : :
244 : : template <typename _Tp, typename _Alloc>
245 : : void
246 : : deque<_Tp, _Alloc>::
247 : : _M_fill_initialize(const value_type& __value)
248 : : {
249 : : _Map_pointer __cur;
250 : : try
251 : : {
252 : : for (__cur = this->_M_impl._M_start._M_node;
253 : : __cur < this->_M_impl._M_finish._M_node;
254 : : ++__cur)
255 : : std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
256 : : __value, _M_get_Tp_allocator());
257 : : std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
258 : : this->_M_impl._M_finish._M_cur,
259 : : __value, _M_get_Tp_allocator());
260 : : }
261 : : catch(...)
262 : : {
263 : : std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
264 : : _M_get_Tp_allocator());
265 : : __throw_exception_again;
266 : : }
267 : : }
268 : :
269 : : template <typename _Tp, typename _Alloc>
270 : : template <typename _InputIterator>
271 : : void
272 : : deque<_Tp, _Alloc>::
273 : : _M_range_initialize(_InputIterator __first, _InputIterator __last,
274 : : std::input_iterator_tag)
275 : : {
276 : : this->_M_initialize_map(0);
277 : : try
278 : : {
279 : : for (; __first != __last; ++__first)
280 : : push_back(*__first);
281 : : }
282 : : catch(...)
283 : : {
284 : : clear();
285 : : __throw_exception_again;
286 : : }
287 : : }
288 : :
289 : : template <typename _Tp, typename _Alloc>
290 : : template <typename _ForwardIterator>
291 : : void
292 : : deque<_Tp, _Alloc>::
293 : : _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
294 : : std::forward_iterator_tag)
295 : : {
296 : : const size_type __n = std::distance(__first, __last);
297 : : this->_M_initialize_map(__n);
298 : :
299 : : _Map_pointer __cur_node;
300 : : try
301 : : {
302 : : for (__cur_node = this->_M_impl._M_start._M_node;
303 : : __cur_node < this->_M_impl._M_finish._M_node;
304 : : ++__cur_node)
305 : : {
306 : : _ForwardIterator __mid = __first;
307 : : std::advance(__mid, _S_buffer_size());
308 : : std::__uninitialized_copy_a(__first, __mid, *__cur_node,
309 : : _M_get_Tp_allocator());
310 : : __first = __mid;
311 : : }
312 : : std::__uninitialized_copy_a(__first, __last,
313 : : this->_M_impl._M_finish._M_first,
314 : : _M_get_Tp_allocator());
315 : : }
316 : : catch(...)
317 : : {
318 : : std::_Destroy(this->_M_impl._M_start,
319 : : iterator(*__cur_node, __cur_node),
320 : : _M_get_Tp_allocator());
321 : : __throw_exception_again;
322 : : }
323 : : }
324 : :
325 : : // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
326 : : template<typename _Tp, typename _Alloc>
327 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
328 : : template<typename... _Args>
329 : : void
330 : : deque<_Tp, _Alloc>::
331 : : _M_push_back_aux(_Args&&... __args)
332 : : #else
333 : : void
334 : : deque<_Tp, _Alloc>::
335 : 0 : _M_push_back_aux(const value_type& __t)
336 : : #endif
337 : : {
338 : : _M_reserve_map_at_back();
339 : 0 : *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
340 : : try
341 : : {
342 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
343 : : this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
344 : : std::forward<_Args>(__args)...);
345 : : #else
346 : 0 : this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
347 : : #endif
348 : 0 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
349 : : + 1);
350 : 0 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
351 : : }
352 : 0 : catch(...)
353 : : {
354 : 0 : _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
355 : 0 : __throw_exception_again;
356 : : }
357 : 0 : }
358 : :
359 : : // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
360 : : template<typename _Tp, typename _Alloc>
361 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
362 : : template<typename... _Args>
363 : : void
364 : : deque<_Tp, _Alloc>::
365 : : _M_push_front_aux(_Args&&... __args)
366 : : #else
367 : : void
368 : : deque<_Tp, _Alloc>::
369 : 61725 : _M_push_front_aux(const value_type& __t)
370 : : #endif
371 : : {
372 : : _M_reserve_map_at_front();
373 : 61725 : *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
374 : : try
375 : : {
376 : 61725 : this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
377 : : - 1);
378 : 61725 : this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
379 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
380 : : this->_M_impl.construct(this->_M_impl._M_start._M_cur,
381 : : std::forward<_Args>(__args)...);
382 : : #else
383 : 61725 : this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
384 : : #endif
385 : : }
386 : 0 : catch(...)
387 : : {
388 : 0 : ++this->_M_impl._M_start;
389 : 0 : _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
390 : 0 : __throw_exception_again;
391 : : }
392 : 61725 : }
393 : :
394 : : // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
395 : : template <typename _Tp, typename _Alloc>
396 : : void deque<_Tp, _Alloc>::
397 : : _M_pop_back_aux()
398 : : {
399 : 61718 : _M_deallocate_node(this->_M_impl._M_finish._M_first);
400 : 61718 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
401 : 61718 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
402 : 61718 : this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
403 : : }
404 : :
405 : : // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
406 : : // Note that if the deque has at least one element (a precondition for this
407 : : // member function), and if
408 : : // _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
409 : : // then the deque must have at least two nodes.
410 : : template <typename _Tp, typename _Alloc>
411 : : void deque<_Tp, _Alloc>::
412 : : _M_pop_front_aux()
413 : : {
414 : 0 : this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
415 : 0 : _M_deallocate_node(this->_M_impl._M_start._M_first);
416 : 0 : this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
417 : 0 : this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
418 : : }
419 : :
420 : : template <typename _Tp, typename _Alloc>
421 : : template <typename _InputIterator>
422 : : void
423 : : deque<_Tp, _Alloc>::
424 : : _M_range_insert_aux(iterator __pos,
425 : : _InputIterator __first, _InputIterator __last,
426 : : std::input_iterator_tag)
427 : : { std::copy(__first, __last, std::inserter(*this, __pos)); }
428 : :
429 : : template <typename _Tp, typename _Alloc>
430 : : template <typename _ForwardIterator>
431 : : void
432 : : deque<_Tp, _Alloc>::
433 : : _M_range_insert_aux(iterator __pos,
434 : : _ForwardIterator __first, _ForwardIterator __last,
435 : : std::forward_iterator_tag)
436 : : {
437 : : const size_type __n = std::distance(__first, __last);
438 : : if (__pos._M_cur == this->_M_impl._M_start._M_cur)
439 : : {
440 : : iterator __new_start = _M_reserve_elements_at_front(__n);
441 : : try
442 : : {
443 : : std::__uninitialized_copy_a(__first, __last, __new_start,
444 : : _M_get_Tp_allocator());
445 : : this->_M_impl._M_start = __new_start;
446 : : }
447 : : catch(...)
448 : : {
449 : : _M_destroy_nodes(__new_start._M_node,
450 : : this->_M_impl._M_start._M_node);
451 : : __throw_exception_again;
452 : : }
453 : : }
454 : : else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
455 : : {
456 : : iterator __new_finish = _M_reserve_elements_at_back(__n);
457 : : try
458 : : {
459 : : std::__uninitialized_copy_a(__first, __last,
460 : : this->_M_impl._M_finish,
461 : : _M_get_Tp_allocator());
462 : : this->_M_impl._M_finish = __new_finish;
463 : : }
464 : : catch(...)
465 : : {
466 : : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
467 : : __new_finish._M_node + 1);
468 : : __throw_exception_again;
469 : : }
470 : : }
471 : : else
472 : : _M_insert_aux(__pos, __first, __last, __n);
473 : : }
474 : :
475 : : template<typename _Tp, typename _Alloc>
476 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
477 : : template<typename... _Args>
478 : : typename deque<_Tp, _Alloc>::iterator
479 : : deque<_Tp, _Alloc>::
480 : : _M_insert_aux(iterator __pos, _Args&&... __args)
481 : : {
482 : : value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
483 : : #else
484 : : typename deque<_Tp, _Alloc>::iterator
485 : : deque<_Tp, _Alloc>::
486 : : _M_insert_aux(iterator __pos, const value_type& __x)
487 : : {
488 : : value_type __x_copy = __x; // XXX copy
489 : : #endif
490 : : difference_type __index = __pos - this->_M_impl._M_start;
491 : : if (static_cast<size_type>(__index) < size() / 2)
492 : : {
493 : : push_front(_GLIBCXX_MOVE(front()));
494 : : iterator __front1 = this->_M_impl._M_start;
495 : : ++__front1;
496 : : iterator __front2 = __front1;
497 : : ++__front2;
498 : : __pos = this->_M_impl._M_start + __index;
499 : : iterator __pos1 = __pos;
500 : : ++__pos1;
501 : : _GLIBCXX_MOVE3(__front2, __pos1, __front1);
502 : : }
503 : : else
504 : : {
505 : : push_back(_GLIBCXX_MOVE(back()));
506 : : iterator __back1 = this->_M_impl._M_finish;
507 : : --__back1;
508 : : iterator __back2 = __back1;
509 : : --__back2;
510 : : __pos = this->_M_impl._M_start + __index;
511 : : _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
512 : : }
513 : : *__pos = _GLIBCXX_MOVE(__x_copy);
514 : : return __pos;
515 : : }
516 : :
517 : : template <typename _Tp, typename _Alloc>
518 : : void
519 : : deque<_Tp, _Alloc>::
520 : 0 : _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
521 : : {
522 : 0 : const difference_type __elems_before = __pos - this->_M_impl._M_start;
523 : 0 : const size_type __length = this->size();
524 : 0 : value_type __x_copy = __x;
525 [ # # # # ]: 0 : if (__elems_before < difference_type(__length / 2))
526 : : {
527 : 0 : iterator __new_start = _M_reserve_elements_at_front(__n);
528 : 0 : iterator __old_start = this->_M_impl._M_start;
529 : 0 : __pos = this->_M_impl._M_start + __elems_before;
530 : : try
531 : : {
532 [ # # # # ]: 0 : if (__elems_before >= difference_type(__n))
533 : : {
534 : : iterator __start_n = (this->_M_impl._M_start
535 : 0 : + difference_type(__n));
536 : 0 : std::__uninitialized_move_a(this->_M_impl._M_start,
537 : : __start_n, __new_start,
538 : : _M_get_Tp_allocator());
539 : 0 : this->_M_impl._M_start = __new_start;
540 : : _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
541 : 0 : std::fill(__pos - difference_type(__n), __pos, __x_copy);
542 : : }
543 : : else
544 : : {
545 : 0 : std::__uninitialized_move_fill(this->_M_impl._M_start,
546 : : __pos, __new_start,
547 : : this->_M_impl._M_start,
548 : : __x_copy,
549 : : _M_get_Tp_allocator());
550 : 0 : this->_M_impl._M_start = __new_start;
551 : 0 : std::fill(__old_start, __pos, __x_copy);
552 : : }
553 : : }
554 : 0 : catch(...)
555 : : {
556 : 0 : _M_destroy_nodes(__new_start._M_node,
557 : : this->_M_impl._M_start._M_node);
558 : 0 : __throw_exception_again;
559 : : }
560 : : }
561 : : else
562 : : {
563 : 0 : iterator __new_finish = _M_reserve_elements_at_back(__n);
564 : 0 : iterator __old_finish = this->_M_impl._M_finish;
565 : : const difference_type __elems_after =
566 : 0 : difference_type(__length) - __elems_before;
567 : 0 : __pos = this->_M_impl._M_finish - __elems_after;
568 : : try
569 : : {
570 [ # # # # ]: 0 : if (__elems_after > difference_type(__n))
571 : : {
572 : : iterator __finish_n = (this->_M_impl._M_finish
573 : 0 : - difference_type(__n));
574 : 0 : std::__uninitialized_move_a(__finish_n,
575 : : this->_M_impl._M_finish,
576 : : this->_M_impl._M_finish,
577 : : _M_get_Tp_allocator());
578 : 0 : this->_M_impl._M_finish = __new_finish;
579 : : _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
580 : 0 : std::fill(__pos, __pos + difference_type(__n), __x_copy);
581 : : }
582 : : else
583 : : {
584 : 0 : std::__uninitialized_fill_move(this->_M_impl._M_finish,
585 : : __pos + difference_type(__n),
586 : : __x_copy, __pos,
587 : : this->_M_impl._M_finish,
588 : : _M_get_Tp_allocator());
589 : 0 : this->_M_impl._M_finish = __new_finish;
590 : 0 : std::fill(__pos, __old_finish, __x_copy);
591 : : }
592 : : }
593 : 0 : catch(...)
594 : : {
595 : 0 : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
596 : : __new_finish._M_node + 1);
597 : 0 : __throw_exception_again;
598 : : }
599 : : }
600 : 0 : }
601 : :
602 : : template <typename _Tp, typename _Alloc>
603 : : template <typename _ForwardIterator>
604 : : void
605 : : deque<_Tp, _Alloc>::
606 : : _M_insert_aux(iterator __pos,
607 : : _ForwardIterator __first, _ForwardIterator __last,
608 : : size_type __n)
609 : : {
610 : : const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
611 : : const size_type __length = size();
612 : : if (static_cast<size_type>(__elemsbefore) < __length / 2)
613 : : {
614 : : iterator __new_start = _M_reserve_elements_at_front(__n);
615 : : iterator __old_start = this->_M_impl._M_start;
616 : : __pos = this->_M_impl._M_start + __elemsbefore;
617 : : try
618 : : {
619 : : if (__elemsbefore >= difference_type(__n))
620 : : {
621 : : iterator __start_n = (this->_M_impl._M_start
622 : : + difference_type(__n));
623 : : std::__uninitialized_move_a(this->_M_impl._M_start,
624 : : __start_n, __new_start,
625 : : _M_get_Tp_allocator());
626 : : this->_M_impl._M_start = __new_start;
627 : : _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
628 : : std::copy(__first, __last, __pos - difference_type(__n));
629 : : }
630 : : else
631 : : {
632 : : _ForwardIterator __mid = __first;
633 : : std::advance(__mid, difference_type(__n) - __elemsbefore);
634 : : std::__uninitialized_move_copy(this->_M_impl._M_start,
635 : : __pos, __first, __mid,
636 : : __new_start,
637 : : _M_get_Tp_allocator());
638 : : this->_M_impl._M_start = __new_start;
639 : : std::copy(__mid, __last, __old_start);
640 : : }
641 : : }
642 : : catch(...)
643 : : {
644 : : _M_destroy_nodes(__new_start._M_node,
645 : : this->_M_impl._M_start._M_node);
646 : : __throw_exception_again;
647 : : }
648 : : }
649 : : else
650 : : {
651 : : iterator __new_finish = _M_reserve_elements_at_back(__n);
652 : : iterator __old_finish = this->_M_impl._M_finish;
653 : : const difference_type __elemsafter =
654 : : difference_type(__length) - __elemsbefore;
655 : : __pos = this->_M_impl._M_finish - __elemsafter;
656 : : try
657 : : {
658 : : if (__elemsafter > difference_type(__n))
659 : : {
660 : : iterator __finish_n = (this->_M_impl._M_finish
661 : : - difference_type(__n));
662 : : std::__uninitialized_move_a(__finish_n,
663 : : this->_M_impl._M_finish,
664 : : this->_M_impl._M_finish,
665 : : _M_get_Tp_allocator());
666 : : this->_M_impl._M_finish = __new_finish;
667 : : _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
668 : : std::copy(__first, __last, __pos);
669 : : }
670 : : else
671 : : {
672 : : _ForwardIterator __mid = __first;
673 : : std::advance(__mid, __elemsafter);
674 : : std::__uninitialized_copy_move(__mid, __last, __pos,
675 : : this->_M_impl._M_finish,
676 : : this->_M_impl._M_finish,
677 : : _M_get_Tp_allocator());
678 : : this->_M_impl._M_finish = __new_finish;
679 : : std::copy(__first, __mid, __pos);
680 : : }
681 : : }
682 : : catch(...)
683 : : {
684 : : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
685 : : __new_finish._M_node + 1);
686 : : __throw_exception_again;
687 : : }
688 : : }
689 : : }
690 : :
691 : : template<typename _Tp, typename _Alloc>
692 : : void
693 : : deque<_Tp, _Alloc>::
694 : : _M_destroy_data_aux(iterator __first, iterator __last)
695 : : {
696 [ # # ][ # # ]: 18 : for (_Map_pointer __node = __first._M_node + 1;
[ - + ][ + + ]
697 : : __node < __last._M_node; ++__node)
698 : 6 : std::_Destroy(*__node, *__node + _S_buffer_size(),
699 : : _M_get_Tp_allocator());
700 : :
701 [ + + ][ + - ]: 12 : if (__first._M_node != __last._M_node)
702 : : {
703 : 8 : std::_Destroy(__first._M_cur, __first._M_last,
704 : : _M_get_Tp_allocator());
705 : 8 : std::_Destroy(__last._M_first, __last._M_cur,
706 : : _M_get_Tp_allocator());
707 : : }
708 : : else
709 : 4 : std::_Destroy(__first._M_cur, __last._M_cur,
710 : : _M_get_Tp_allocator());
711 : : }
712 : :
713 : : template <typename _Tp, typename _Alloc>
714 : : void
715 : : deque<_Tp, _Alloc>::
716 : 4 : _M_new_elements_at_front(size_type __new_elems)
717 : : {
718 [ - + - + ]: 4 : if (this->max_size() - this->size() < __new_elems)
719 : 0 : __throw_length_error(__N("deque::_M_new_elements_at_front"));
720 : :
721 : : const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
722 : 8 : / _S_buffer_size());
723 : : _M_reserve_map_at_front(__new_nodes);
724 : : size_type __i;
725 : : try
726 : : {
727 [ + + ][ + + ]: 11 : for (__i = 1; __i <= __new_nodes; ++__i)
728 : 7 : *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
729 : : }
730 : 0 : catch(...)
731 : : {
732 [ # # ][ # # ]: 0 : for (size_type __j = 1; __j < __i; ++__j)
733 : 0 : _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
734 : 0 : __throw_exception_again;
735 : : }
736 : 4 : }
737 : :
738 : : template <typename _Tp, typename _Alloc>
739 : : void
740 : : deque<_Tp, _Alloc>::
741 : 0 : _M_new_elements_at_back(size_type __new_elems)
742 : : {
743 [ # # # # ]: 0 : if (this->max_size() - this->size() < __new_elems)
744 : 0 : __throw_length_error(__N("deque::_M_new_elements_at_back"));
745 : :
746 : : const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
747 : 0 : / _S_buffer_size());
748 : : _M_reserve_map_at_back(__new_nodes);
749 : : size_type __i;
750 : : try
751 : : {
752 [ # # ][ # # ]: 0 : for (__i = 1; __i <= __new_nodes; ++__i)
753 : 0 : *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
754 : : }
755 : 0 : catch(...)
756 : : {
757 [ # # ][ # # ]: 0 : for (size_type __j = 1; __j < __i; ++__j)
758 : 0 : _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
759 : 0 : __throw_exception_again;
760 : : }
761 : 0 : }
762 : :
763 : : template <typename _Tp, typename _Alloc>
764 : : void
765 : : deque<_Tp, _Alloc>::
766 : 9645 : _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
767 : : {
768 : : const size_type __old_num_nodes
769 : 9645 : = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
770 : 9645 : const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
771 : :
772 : : _Map_pointer __new_nstart;
773 [ + - ][ + + ]: 9645 : if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
774 : : {
775 [ + - ][ + - ]: 9644 : __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
776 : : - __new_num_nodes) / 2
777 : : + (__add_at_front ? __nodes_to_add : 0);
778 [ - + ][ - + ]: 9644 : if (__new_nstart < this->_M_impl._M_start._M_node)
779 : 0 : std::copy(this->_M_impl._M_start._M_node,
780 : : this->_M_impl._M_finish._M_node + 1,
781 : : __new_nstart);
782 : : else
783 : 9644 : std::copy_backward(this->_M_impl._M_start._M_node,
784 : : this->_M_impl._M_finish._M_node + 1,
785 : : __new_nstart + __old_num_nodes);
786 : : }
787 : : else
788 : : {
789 : : size_type __new_map_size = this->_M_impl._M_map_size
790 : : + std::max(this->_M_impl._M_map_size,
791 : 2 : __nodes_to_add) + 2;
792 : :
793 : 2 : _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
794 [ # # ][ + - ]: 1 : __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
795 : : + (__add_at_front ? __nodes_to_add : 0);
796 : 1 : std::copy(this->_M_impl._M_start._M_node,
797 : : this->_M_impl._M_finish._M_node + 1,
798 : : __new_nstart);
799 : 1 : _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
800 : :
801 : 1 : this->_M_impl._M_map = __new_map;
802 : 1 : this->_M_impl._M_map_size = __new_map_size;
803 : : }
804 : :
805 : 9645 : this->_M_impl._M_start._M_set_node(__new_nstart);
806 : 9645 : this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
807 : 9645 : }
808 : :
809 : : // Overload for deque::iterators, exploiting the "segmented-iterator
810 : : // optimization". NB: leave const_iterators alone!
811 : : template<typename _Tp>
812 : : void
813 : : fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
814 : 0 : const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
815 : : {
816 : : typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
817 : :
818 [ # # ][ # # ]: 0 : for (typename _Self::_Map_pointer __node = __first._M_node + 1;
819 : : __node < __last._M_node; ++__node)
820 : 0 : std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
821 : :
822 [ # # ][ # # ]: 0 : if (__first._M_node != __last._M_node)
823 : : {
824 : 0 : std::fill(__first._M_cur, __first._M_last, __value);
825 : 0 : std::fill(__last._M_first, __last._M_cur, __value);
826 : : }
827 : : else
828 : 0 : std::fill(__first._M_cur, __last._M_cur, __value);
829 : 0 : }
830 : :
831 : : _GLIBCXX_END_NESTED_NAMESPACE
832 : :
833 : : #endif
|
