1 // Deque implementation (out of line) -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
33 * Hewlett-Packard Company
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation. Hewlett-Packard Company makes no
40 * representations about the suitability of this software for any
41 * purpose. It is provided "as is" without express or implied warranty.
45 * Silicon Graphics Computer Systems, Inc.
47 * Permission to use, copy, modify, distribute and sell this software
48 * and its documentation for any purpose is hereby granted without fee,
49 * provided that the above copyright notice appear in all copies and
50 * that both that copyright notice and this permission notice appear
51 * in supporting documentation. Silicon Graphics makes no
52 * representations about the suitability of this software for any
53 * purpose. It is provided "as is" without express or implied warranty.
57 * This is an internal header file, included by other library headers.
58 * You should not attempt to use it directly.
66 template <typename _Tp, typename _Alloc>
69 operator=(const deque& __x)
71 const size_type __len = size();
74 if (__len >= __x.size())
75 erase(std::copy(__x.begin(), __x.end(), this->_M_start),
79 const_iterator __mid = __x.begin() + difference_type(__len);
80 std::copy(__x.begin(), __mid, this->_M_start);
81 insert(this->_M_finish, __mid, __x.end());
87 template <typename _Tp, typename _Alloc>
88 typename deque<_Tp,_Alloc>::iterator
90 insert(iterator position, const value_type& __x)
92 if (position._M_cur == this->_M_start._M_cur)
95 return this->_M_start;
97 else if (position._M_cur == this->_M_finish._M_cur)
100 iterator __tmp = this->_M_finish;
105 return _M_insert_aux(position, __x);
108 template <typename _Tp, typename _Alloc>
109 typename deque<_Tp,_Alloc>::iterator
111 erase(iterator __position)
113 iterator __next = __position;
115 size_type __index = __position - this->_M_start;
116 if (__index < (size() >> 1))
118 std::copy_backward(this->_M_start, __position, __next);
123 std::copy(__next, this->_M_finish, __position);
126 return this->_M_start + __index;
129 template <typename _Tp, typename _Alloc>
130 typename deque<_Tp,_Alloc>::iterator
132 erase(iterator __first, iterator __last)
134 if (__first == this->_M_start && __last == this->_M_finish)
137 return this->_M_finish;
141 const difference_type __n = __last - __first;
142 const difference_type __elems_before = __first - this->_M_start;
143 if (static_cast<size_type>(__elems_before) < (size() - __n) / 2)
145 std::copy_backward(this->_M_start, __first, __last);
146 iterator __new_start = this->_M_start + __n;
147 std::_Destroy(this->_M_start, __new_start);
148 _M_destroy_nodes(this->_M_start._M_node, __new_start._M_node);
149 this->_M_start = __new_start;
153 std::copy(__last, this->_M_finish, __first);
154 iterator __new_finish = this->_M_finish - __n;
155 std::_Destroy(__new_finish, this->_M_finish);
156 _M_destroy_nodes(__new_finish._M_node + 1,
157 this->_M_finish._M_node + 1);
158 this->_M_finish = __new_finish;
160 return this->_M_start + __elems_before;
164 template <typename _Tp, typename _Alloc>
169 for (_Map_pointer __node = this->_M_start._M_node + 1;
170 __node < this->_M_finish._M_node;
173 std::_Destroy(*__node, *__node + _S_buffer_size());
174 _M_deallocate_node(*__node);
177 if (this->_M_start._M_node != this->_M_finish._M_node)
179 std::_Destroy(this->_M_start._M_cur, this->_M_start._M_last);
180 std::_Destroy(this->_M_finish._M_first, this->_M_finish._M_cur);
181 _M_deallocate_node(this->_M_finish._M_first);
184 std::_Destroy(this->_M_start._M_cur, this->_M_finish._M_cur);
186 this->_M_finish = this->_M_start;
189 template <typename _Tp, class _Alloc>
190 template <typename _InputIterator>
193 ::_M_assign_aux(_InputIterator __first, _InputIterator __last,
196 iterator __cur = begin();
197 for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
199 if (__first == __last)
202 insert(end(), __first, __last);
205 template <typename _Tp, typename _Alloc>
208 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
210 if (__pos._M_cur == this->_M_start._M_cur)
212 iterator __new_start = _M_reserve_elements_at_front(__n);
215 std::uninitialized_fill(__new_start, this->_M_start, __x);
216 this->_M_start = __new_start;
220 _M_destroy_nodes(__new_start._M_node, this->_M_start._M_node);
221 __throw_exception_again;
224 else if (__pos._M_cur == this->_M_finish._M_cur)
226 iterator __new_finish = _M_reserve_elements_at_back(__n);
229 std::uninitialized_fill(this->_M_finish, __new_finish, __x);
230 this->_M_finish = __new_finish;
234 _M_destroy_nodes(this->_M_finish._M_node + 1,
235 __new_finish._M_node + 1);
236 __throw_exception_again;
240 _M_insert_aux(__pos, __n, __x);
243 template <typename _Tp, typename _Alloc>
246 _M_fill_initialize(const value_type& __value)
251 for (__cur = this->_M_start._M_node;
252 __cur < this->_M_finish._M_node;
254 std::uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
255 std::uninitialized_fill(this->_M_finish._M_first,
256 this->_M_finish._M_cur,
261 std::_Destroy(this->_M_start, iterator(*__cur, __cur));
262 __throw_exception_again;
266 template <typename _Tp, typename _Alloc>
267 template <typename _InputIterator>
270 _M_range_initialize(_InputIterator __first, _InputIterator __last,
273 this->_M_initialize_map(0);
276 for ( ; __first != __last; ++__first)
282 __throw_exception_again;
286 template <typename _Tp, typename _Alloc>
287 template <typename _ForwardIterator>
290 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
291 forward_iterator_tag)
293 const size_type __n = std::distance(__first, __last);
294 this->_M_initialize_map(__n);
296 _Map_pointer __cur_node;
299 for (__cur_node = this->_M_start._M_node;
300 __cur_node < this->_M_finish._M_node;
303 _ForwardIterator __mid = __first;
304 std::advance(__mid, _S_buffer_size());
305 std::uninitialized_copy(__first, __mid, *__cur_node);
308 std::uninitialized_copy(__first, __last, this->_M_finish._M_first);
312 std::_Destroy(this->_M_start, iterator(*__cur_node, __cur_node));
313 __throw_exception_again;
317 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
318 template <typename _Tp, typename _Alloc>
321 _M_push_back_aux(const value_type& __t)
323 value_type __t_copy = __t;
324 _M_reserve_map_at_back();
325 *(this->_M_finish._M_node + 1) = this->_M_allocate_node();
328 std::_Construct(this->_M_finish._M_cur, __t_copy);
329 this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
330 this->_M_finish._M_cur = this->_M_finish._M_first;
334 _M_deallocate_node(*(this->_M_finish._M_node + 1));
335 __throw_exception_again;
339 // Called only if _M_start._M_cur == _M_start._M_first.
340 template <typename _Tp, typename _Alloc>
343 _M_push_front_aux(const value_type& __t)
345 value_type __t_copy = __t;
346 _M_reserve_map_at_front();
347 *(this->_M_start._M_node - 1) = this->_M_allocate_node();
350 this->_M_start._M_set_node(this->_M_start._M_node - 1);
351 this->_M_start._M_cur = this->_M_start._M_last - 1;
352 std::_Construct(this->_M_start._M_cur, __t_copy);
357 _M_deallocate_node(*(this->_M_start._M_node - 1));
358 __throw_exception_again;
362 // Called only if _M_finish._M_cur == _M_finish._M_first.
363 template <typename _Tp, typename _Alloc>
364 void deque<_Tp,_Alloc>::
367 _M_deallocate_node(this->_M_finish._M_first);
368 this->_M_finish._M_set_node(this->_M_finish._M_node - 1);
369 this->_M_finish._M_cur = this->_M_finish._M_last - 1;
370 std::_Destroy(this->_M_finish._M_cur);
373 // Called only if _M_start._M_cur == _M_start._M_last - 1. Note that
374 // if the deque has at least one element (a precondition for this member
375 // function), and if _M_start._M_cur == _M_start._M_last, then the deque
376 // must have at least two nodes.
377 template <typename _Tp, typename _Alloc>
378 void deque<_Tp,_Alloc>::
381 std::_Destroy(this->_M_start._M_cur);
382 _M_deallocate_node(this->_M_start._M_first);
383 this->_M_start._M_set_node(this->_M_start._M_node + 1);
384 this->_M_start._M_cur = this->_M_start._M_first;
387 template <typename _Tp, typename _Alloc>
388 template <typename _InputIterator>
391 _M_range_insert_aux(iterator __pos,
392 _InputIterator __first, _InputIterator __last,
394 { std::copy(__first, __last, std::inserter(*this, __pos)); }
396 template <typename _Tp, typename _Alloc>
397 template <typename _ForwardIterator>
400 _M_range_insert_aux(iterator __pos,
401 _ForwardIterator __first, _ForwardIterator __last,
402 forward_iterator_tag)
404 size_type __n = std::distance(__first, __last);
405 if (__pos._M_cur == this->_M_start._M_cur)
407 iterator __new_start = _M_reserve_elements_at_front(__n);
410 std::uninitialized_copy(__first, __last, __new_start);
411 this->_M_start = __new_start;
415 _M_destroy_nodes(__new_start._M_node, this->_M_start._M_node);
416 __throw_exception_again;
419 else if (__pos._M_cur == this->_M_finish._M_cur)
421 iterator __new_finish = _M_reserve_elements_at_back(__n);
424 std::uninitialized_copy(__first, __last, this->_M_finish);
425 this->_M_finish = __new_finish;
429 _M_destroy_nodes(this->_M_finish._M_node + 1,
430 __new_finish._M_node + 1);
431 __throw_exception_again;
435 _M_insert_aux(__pos, __first, __last, __n);
438 template <typename _Tp, typename _Alloc>
439 typename deque<_Tp, _Alloc>::iterator
441 _M_insert_aux(iterator __pos, const value_type& __x)
443 difference_type __index = __pos - this->_M_start;
444 value_type __x_copy = __x; // XXX copy
445 if (static_cast<size_type>(__index) < size() / 2)
448 iterator __front1 = this->_M_start;
450 iterator __front2 = __front1;
452 __pos = this->_M_start + __index;
453 iterator __pos1 = __pos;
455 std::copy(__front2, __pos1, __front1);
460 iterator __back1 = this->_M_finish;
462 iterator __back2 = __back1;
464 __pos = this->_M_start + __index;
465 std::copy_backward(__pos, __back2, __back1);
471 template <typename _Tp, typename _Alloc>
474 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
476 const difference_type __elems_before = __pos - this->_M_start;
477 size_type __length = this->size();
478 value_type __x_copy = __x;
479 if (__elems_before < difference_type(__length / 2))
481 iterator __new_start = _M_reserve_elements_at_front(__n);
482 iterator __old_start = this->_M_start;
483 __pos = this->_M_start + __elems_before;
486 if (__elems_before >= difference_type(__n))
488 iterator __start_n = this->_M_start + difference_type(__n);
489 std::uninitialized_copy(this->_M_start, __start_n,
491 this->_M_start = __new_start;
492 std::copy(__start_n, __pos, __old_start);
493 fill(__pos - difference_type(__n), __pos, __x_copy);
497 std::__uninitialized_copy_fill(this->_M_start, __pos,
499 this->_M_start, __x_copy);
500 this->_M_start = __new_start;
501 std::fill(__old_start, __pos, __x_copy);
506 _M_destroy_nodes(__new_start._M_node, this->_M_start._M_node);
507 __throw_exception_again;
512 iterator __new_finish = _M_reserve_elements_at_back(__n);
513 iterator __old_finish = this->_M_finish;
514 const difference_type __elems_after =
515 difference_type(__length) - __elems_before;
516 __pos = this->_M_finish - __elems_after;
519 if (__elems_after > difference_type(__n))
521 iterator __finish_n = this->_M_finish - difference_type(__n);
522 std::uninitialized_copy(__finish_n, this->_M_finish,
524 this->_M_finish = __new_finish;
525 std::copy_backward(__pos, __finish_n, __old_finish);
526 std::fill(__pos, __pos + difference_type(__n), __x_copy);
530 std::__uninitialized_fill_copy(this->_M_finish,
531 __pos + difference_type(__n),
534 this->_M_finish = __new_finish;
535 std::fill(__pos, __old_finish, __x_copy);
540 _M_destroy_nodes(this->_M_finish._M_node + 1,
541 __new_finish._M_node + 1);
542 __throw_exception_again;
547 template <typename _Tp, typename _Alloc>
548 template <typename _ForwardIterator>
551 _M_insert_aux(iterator __pos,
552 _ForwardIterator __first, _ForwardIterator __last,
555 const difference_type __elemsbefore = __pos - this->_M_start;
556 size_type __length = size();
557 if (static_cast<size_type>(__elemsbefore) < __length / 2)
559 iterator __new_start = _M_reserve_elements_at_front(__n);
560 iterator __old_start = this->_M_start;
561 __pos = this->_M_start + __elemsbefore;
564 if (__elemsbefore >= difference_type(__n))
566 iterator __start_n = this->_M_start + difference_type(__n);
567 std::uninitialized_copy(this->_M_start, __start_n,
569 this->_M_start = __new_start;
570 std::copy(__start_n, __pos, __old_start);
571 std::copy(__first, __last, __pos - difference_type(__n));
575 _ForwardIterator __mid = __first;
576 std::advance(__mid, difference_type(__n) - __elemsbefore);
577 std::__uninitialized_copy_copy(this->_M_start, __pos,
578 __first, __mid, __new_start);
579 this->_M_start = __new_start;
580 std::copy(__mid, __last, __old_start);
585 _M_destroy_nodes(__new_start._M_node, this->_M_start._M_node);
586 __throw_exception_again;
591 iterator __new_finish = _M_reserve_elements_at_back(__n);
592 iterator __old_finish = this->_M_finish;
593 const difference_type __elemsafter =
594 difference_type(__length) - __elemsbefore;
595 __pos = this->_M_finish - __elemsafter;
598 if (__elemsafter > difference_type(__n))
600 iterator __finish_n = this->_M_finish - difference_type(__n);
601 std::uninitialized_copy(__finish_n,
604 this->_M_finish = __new_finish;
605 std::copy_backward(__pos, __finish_n, __old_finish);
606 std::copy(__first, __last, __pos);
610 _ForwardIterator __mid = __first;
611 std::advance(__mid, __elemsafter);
612 std::__uninitialized_copy_copy(__mid, __last, __pos,
615 this->_M_finish = __new_finish;
616 std::copy(__first, __mid, __pos);
621 _M_destroy_nodes(this->_M_finish._M_node + 1,
622 __new_finish._M_node + 1);
623 __throw_exception_again;
628 template <typename _Tp, typename _Alloc>
631 _M_new_elements_at_front(size_type __new_elems)
633 size_type __new_nodes
634 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
635 _M_reserve_map_at_front(__new_nodes);
639 for (__i = 1; __i <= __new_nodes; ++__i)
640 *(this->_M_start._M_node - __i) = this->_M_allocate_node();
644 for (size_type __j = 1; __j < __i; ++__j)
645 _M_deallocate_node(*(this->_M_start._M_node - __j));
646 __throw_exception_again;
650 template <typename _Tp, typename _Alloc>
653 _M_new_elements_at_back(size_type __new_elems)
655 size_type __new_nodes
656 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
657 _M_reserve_map_at_back(__new_nodes);
661 for (__i = 1; __i <= __new_nodes; ++__i)
662 *(this->_M_finish._M_node + __i) = this->_M_allocate_node();
666 for (size_type __j = 1; __j < __i; ++__j)
667 _M_deallocate_node(*(this->_M_finish._M_node + __j));
668 __throw_exception_again;
672 template <typename _Tp, typename _Alloc>
675 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
677 size_type __old_num_nodes
678 = this->_M_finish._M_node - this->_M_start._M_node + 1;
679 size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
681 _Map_pointer __new_nstart;
682 if (this->_M_map_size > 2 * __new_num_nodes)
684 __new_nstart = this->_M_map + (this->_M_map_size
685 - __new_num_nodes) / 2
686 + (__add_at_front ? __nodes_to_add : 0);
687 if (__new_nstart < this->_M_start._M_node)
688 std::copy(this->_M_start._M_node,
689 this->_M_finish._M_node + 1,
692 std::copy_backward(this->_M_start._M_node,
693 this->_M_finish._M_node + 1,
694 __new_nstart + __old_num_nodes);
698 size_type __new_map_size = this->_M_map_size
699 + std::max(this->_M_map_size,
702 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
703 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
704 + (__add_at_front ? __nodes_to_add : 0);
705 std::copy(this->_M_start._M_node,
706 this->_M_finish._M_node + 1,
708 _M_deallocate_map(this->_M_map, this->_M_map_size);
710 this->_M_map = __new_map;
711 this->_M_map_size = __new_map_size;
714 this->_M_start._M_set_node(__new_nstart);
715 this->_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
717 } // namespace __gnu_norm