1 // Deque implementation (out of line) -*- C++ -*-
3 // Copyright (C) 2001, 2002 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.
61 #ifndef __GLIBCPP_INTERNAL_DEQUE_TCC
62 #define __GLIBCPP_INTERNAL_DEQUE_TCC
66 template <typename _Tp, typename _Alloc>
69 operator=(const deque& __x)
71 const size_type __len = size();
74 if (__len >= __x.size())
75 erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
78 const_iterator __mid = __x.begin() + difference_type(__len);
79 copy(__x.begin(), __mid, _M_start);
80 insert(_M_finish, __mid, __x.end());
86 template <typename _Tp, typename _Alloc>
87 typename deque<_Tp,_Alloc>::iterator
89 insert(iterator position, const value_type& __x)
91 if (position._M_cur == _M_start._M_cur)
96 else if (position._M_cur == _M_finish._M_cur)
99 iterator __tmp = _M_finish;
104 return _M_insert_aux(position, __x);
107 template <typename _Tp, typename _Alloc>
108 typename deque<_Tp,_Alloc>::iterator
110 erase(iterator __position)
112 iterator __next = __position;
114 size_type __index = __position - _M_start;
115 if (__index < (size() >> 1))
117 copy_backward(_M_start, __position, __next);
122 copy(__next, _M_finish, __position);
125 return _M_start + __index;
128 template <typename _Tp, typename _Alloc>
129 typename deque<_Tp,_Alloc>::iterator
131 erase(iterator __first, iterator __last)
133 if (__first == _M_start && __last == _M_finish)
140 difference_type __n = __last - __first;
141 difference_type __elems_before = __first - _M_start;
142 if (static_cast<size_type>(__elems_before) < (size() - __n) / 2)
144 copy_backward(_M_start, __first, __last);
145 iterator __new_start = _M_start + __n;
146 _Destroy(_M_start, __new_start);
147 _M_destroy_nodes(_M_start._M_node, __new_start._M_node);
148 _M_start = __new_start;
152 copy(__last, _M_finish, __first);
153 iterator __new_finish = _M_finish - __n;
154 _Destroy(__new_finish, _M_finish);
155 _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
156 _M_finish = __new_finish;
158 return _M_start + __elems_before;
162 template <typename _Tp, typename _Alloc>
167 for (_Map_pointer __node = _M_start._M_node + 1;
168 __node < _M_finish._M_node;
171 _Destroy(*__node, *__node + _S_buffer_size());
172 _M_deallocate_node(*__node);
175 if (_M_start._M_node != _M_finish._M_node)
177 _Destroy(_M_start._M_cur, _M_start._M_last);
178 _Destroy(_M_finish._M_first, _M_finish._M_cur);
179 _M_deallocate_node(_M_finish._M_first);
182 _Destroy(_M_start._M_cur, _M_finish._M_cur);
184 _M_finish = _M_start;
187 template <typename _Tp, class _Alloc>
188 template <typename _InputIter>
191 ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
193 iterator __cur = begin();
194 for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
196 if (__first == __last)
199 insert(end(), __first, __last);
202 template <typename _Tp, typename _Alloc>
205 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
207 if (__pos._M_cur == _M_start._M_cur)
209 iterator __new_start = _M_reserve_elements_at_front(__n);
212 uninitialized_fill(__new_start, _M_start, __x);
213 _M_start = __new_start;
217 _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
218 __throw_exception_again;
221 else if (__pos._M_cur == _M_finish._M_cur)
223 iterator __new_finish = _M_reserve_elements_at_back(__n);
226 uninitialized_fill(_M_finish, __new_finish, __x);
227 _M_finish = __new_finish;
231 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
232 __throw_exception_again;
236 _M_insert_aux(__pos, __n, __x);
239 template <typename _Tp, typename _Alloc>
242 _M_fill_initialize(const value_type& __value)
247 for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
248 uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
249 uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
253 _Destroy(_M_start, iterator(*__cur, __cur));
254 __throw_exception_again;
258 template <typename _Tp, typename _Alloc>
259 template <typename _InputIterator>
262 _M_range_initialize(_InputIterator __first, _InputIterator __last,
265 _M_initialize_map(0);
268 for ( ; __first != __last; ++__first)
274 __throw_exception_again;
278 template <typename _Tp, typename _Alloc>
279 template <typename _ForwardIterator>
282 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
283 forward_iterator_tag)
285 size_type __n = std::distance(__first, __last);
286 _M_initialize_map(__n);
288 _Map_pointer __cur_node;
291 for (__cur_node = _M_start._M_node;
292 __cur_node < _M_finish._M_node;
295 _ForwardIterator __mid = __first;
296 advance(__mid, _S_buffer_size());
297 uninitialized_copy(__first, __mid, *__cur_node);
300 uninitialized_copy(__first, __last, _M_finish._M_first);
304 _Destroy(_M_start, iterator(*__cur_node, __cur_node));
305 __throw_exception_again;
309 // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
310 template <typename _Tp, typename _Alloc>
313 _M_push_back_aux(const value_type& __t)
315 value_type __t_copy = __t;
316 _M_reserve_map_at_back();
317 *(_M_finish._M_node + 1) = _M_allocate_node();
320 _Construct(_M_finish._M_cur, __t_copy);
321 _M_finish._M_set_node(_M_finish._M_node + 1);
322 _M_finish._M_cur = _M_finish._M_first;
326 _M_deallocate_node(*(_M_finish._M_node + 1));
327 __throw_exception_again;
331 // Called only if _M_start._M_cur == _M_start._M_first.
332 template <typename _Tp, typename _Alloc>
335 _M_push_front_aux(const value_type& __t)
337 value_type __t_copy = __t;
338 _M_reserve_map_at_front();
339 *(_M_start._M_node - 1) = _M_allocate_node();
342 _M_start._M_set_node(_M_start._M_node - 1);
343 _M_start._M_cur = _M_start._M_last - 1;
344 _Construct(_M_start._M_cur, __t_copy);
349 _M_deallocate_node(*(_M_start._M_node - 1));
350 __throw_exception_again;
354 // Called only if _M_finish._M_cur == _M_finish._M_first.
355 template <typename _Tp, typename _Alloc>
356 void deque<_Tp,_Alloc>::
359 _M_deallocate_node(_M_finish._M_first);
360 _M_finish._M_set_node(_M_finish._M_node - 1);
361 _M_finish._M_cur = _M_finish._M_last - 1;
362 _Destroy(_M_finish._M_cur);
365 // Called only if _M_start._M_cur == _M_start._M_last - 1. Note that
366 // if the deque has at least one element (a precondition for this member
367 // function), and if _M_start._M_cur == _M_start._M_last, then the deque
368 // must have at least two nodes.
369 template <typename _Tp, typename _Alloc>
370 void deque<_Tp,_Alloc>::
373 _Destroy(_M_start._M_cur);
374 _M_deallocate_node(_M_start._M_first);
375 _M_start._M_set_node(_M_start._M_node + 1);
376 _M_start._M_cur = _M_start._M_first;
379 template <typename _Tp, typename _Alloc>
380 template <typename _InputIterator>
383 _M_range_insert_aux(iterator __pos,
384 _InputIterator __first, _InputIterator __last,
387 copy(__first, __last, inserter(*this, __pos));
390 template <typename _Tp, typename _Alloc>
391 template <typename _ForwardIterator>
394 _M_range_insert_aux(iterator __pos,
395 _ForwardIterator __first, _ForwardIterator __last,
396 forward_iterator_tag)
398 size_type __n = std::distance(__first, __last);
399 if (__pos._M_cur == _M_start._M_cur)
401 iterator __new_start = _M_reserve_elements_at_front(__n);
404 uninitialized_copy(__first, __last, __new_start);
405 _M_start = __new_start;
409 _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
410 __throw_exception_again;
413 else if (__pos._M_cur == _M_finish._M_cur)
415 iterator __new_finish = _M_reserve_elements_at_back(__n);
418 uninitialized_copy(__first, __last, _M_finish);
419 _M_finish = __new_finish;
423 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
424 __throw_exception_again;
428 _M_insert_aux(__pos, __first, __last, __n);
431 template <typename _Tp, typename _Alloc>
432 typename deque<_Tp, _Alloc>::iterator
434 _M_insert_aux(iterator __pos, const value_type& __x)
436 difference_type __index = __pos - _M_start;
437 value_type __x_copy = __x; // XXX copy
438 if (static_cast<size_type>(__index) < size() / 2)
441 iterator __front1 = _M_start;
443 iterator __front2 = __front1;
445 __pos = _M_start + __index;
446 iterator __pos1 = __pos;
448 copy(__front2, __pos1, __front1);
453 iterator __back1 = _M_finish;
455 iterator __back2 = __back1;
457 __pos = _M_start + __index;
458 copy_backward(__pos, __back2, __back1);
464 template <typename _Tp, typename _Alloc>
467 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
469 const difference_type __elems_before = __pos - _M_start;
470 size_type __length = this->size();
471 value_type __x_copy = __x;
472 if (__elems_before < difference_type(__length / 2))
474 iterator __new_start = _M_reserve_elements_at_front(__n);
475 iterator __old_start = _M_start;
476 __pos = _M_start + __elems_before;
479 if (__elems_before >= difference_type(__n))
481 iterator __start_n = _M_start + difference_type(__n);
482 uninitialized_copy(_M_start, __start_n, __new_start);
483 _M_start = __new_start;
484 copy(__start_n, __pos, __old_start);
485 fill(__pos - difference_type(__n), __pos, __x_copy);
489 __uninitialized_copy_fill(_M_start, __pos, __new_start,
491 _M_start = __new_start;
492 fill(__old_start, __pos, __x_copy);
497 _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
498 __throw_exception_again;
503 iterator __new_finish = _M_reserve_elements_at_back(__n);
504 iterator __old_finish = _M_finish;
505 const difference_type __elems_after =
506 difference_type(__length) - __elems_before;
507 __pos = _M_finish - __elems_after;
510 if (__elems_after > difference_type(__n))
512 iterator __finish_n = _M_finish - difference_type(__n);
513 uninitialized_copy(__finish_n, _M_finish, _M_finish);
514 _M_finish = __new_finish;
515 copy_backward(__pos, __finish_n, __old_finish);
516 fill(__pos, __pos + difference_type(__n), __x_copy);
520 __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
521 __x_copy, __pos, _M_finish);
522 _M_finish = __new_finish;
523 fill(__pos, __old_finish, __x_copy);
528 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
529 __throw_exception_again;
534 template <typename _Tp, typename _Alloc>
535 template <typename _ForwardIterator>
538 _M_insert_aux(iterator __pos,
539 _ForwardIterator __first, _ForwardIterator __last,
542 const difference_type __elemsbefore = __pos - _M_start;
543 size_type __length = size();
544 if (static_cast<size_type>(__elemsbefore) < __length / 2)
546 iterator __new_start = _M_reserve_elements_at_front(__n);
547 iterator __old_start = _M_start;
548 __pos = _M_start + __elemsbefore;
551 if (__elemsbefore >= difference_type(__n))
553 iterator __start_n = _M_start + difference_type(__n);
554 uninitialized_copy(_M_start, __start_n, __new_start);
555 _M_start = __new_start;
556 copy(__start_n, __pos, __old_start);
557 copy(__first, __last, __pos - difference_type(__n));
561 _ForwardIterator __mid = __first;
562 advance(__mid, difference_type(__n) - __elemsbefore);
563 __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
565 _M_start = __new_start;
566 copy(__mid, __last, __old_start);
571 _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
572 __throw_exception_again;
577 iterator __new_finish = _M_reserve_elements_at_back(__n);
578 iterator __old_finish = _M_finish;
579 const difference_type __elemsafter =
580 difference_type(__length) - __elemsbefore;
581 __pos = _M_finish - __elemsafter;
584 if (__elemsafter > difference_type(__n))
586 iterator __finish_n = _M_finish - difference_type(__n);
587 uninitialized_copy(__finish_n, _M_finish, _M_finish);
588 _M_finish = __new_finish;
589 copy_backward(__pos, __finish_n, __old_finish);
590 copy(__first, __last, __pos);
594 _ForwardIterator __mid = __first;
595 advance(__mid, __elemsafter);
596 __uninitialized_copy_copy(__mid, __last, __pos,
597 _M_finish, _M_finish);
598 _M_finish = __new_finish;
599 copy(__first, __mid, __pos);
604 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
605 __throw_exception_again;
610 template <typename _Tp, typename _Alloc>
613 _M_new_elements_at_front(size_type __new_elems)
615 size_type __new_nodes
616 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
617 _M_reserve_map_at_front(__new_nodes);
621 for (__i = 1; __i <= __new_nodes; ++__i)
622 *(_M_start._M_node - __i) = _M_allocate_node();
626 for (size_type __j = 1; __j < __i; ++__j)
627 _M_deallocate_node(*(_M_start._M_node - __j));
628 __throw_exception_again;
632 template <typename _Tp, typename _Alloc>
635 _M_new_elements_at_back(size_type __new_elems)
637 size_type __new_nodes
638 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
639 _M_reserve_map_at_back(__new_nodes);
643 for (__i = 1; __i <= __new_nodes; ++__i)
644 *(_M_finish._M_node + __i) = _M_allocate_node();
648 for (size_type __j = 1; __j < __i; ++__j)
649 _M_deallocate_node(*(_M_finish._M_node + __j));
650 __throw_exception_again;
654 template <typename _Tp, typename _Alloc>
657 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
659 size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
660 size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
662 _Map_pointer __new_nstart;
663 if (_M_map_size > 2 * __new_num_nodes)
665 __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2
666 + (__add_at_front ? __nodes_to_add : 0);
667 if (__new_nstart < _M_start._M_node)
668 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
670 copy_backward(_M_start._M_node, _M_finish._M_node + 1,
671 __new_nstart + __old_num_nodes);
675 size_type __new_map_size =
676 _M_map_size + std::max(_M_map_size, __nodes_to_add) + 2;
678 _Map_pointer __new_map = _M_allocate_map(__new_map_size);
679 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
680 + (__add_at_front ? __nodes_to_add : 0);
681 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
682 _M_deallocate_map(_M_map, _M_map_size);
685 _M_map_size = __new_map_size;
688 _M_start._M_set_node(__new_nstart);
689 _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
693 #endif /* __GLIBCPP_INTERNAL_DEQUE_TCC */