1 /*
2  *
3  *
4  * Copyright (c) 1994
5  * Hewlett-Packard Company
6  *
7  * Copyright (c) 1996,1997
8  * Silicon Graphics Computer Systems, Inc.
9  *
10  * Copyright (c) 1997
11  * Moscow Center for SPARC Technology
12  *
13  * Copyright (c) 1999
14  * Boris Fomitchev
15  *
16  * This material is provided "as is", with absolutely no warranty expressed
17  * or implied. Any use is at your own risk.
18  *
19  * Permission to use or copy this software for any purpose is hereby granted
20  * without fee, provided the above notices are retained on all copies.
21  * Permission to modify the code and to distribute modified code is granted,
22  * provided the above notices are retained, and a notice that the code was
23  * modified is included with the above copyright notice.
24  *
25  */
26 #ifndef _STLP_DEQUE_C
27 #define _STLP_DEQUE_C
28 
29 #ifndef _STLP_INTERNAL_DEQUE_H
30 #  include <stl/_deque.h>
31 #endif
32 
33 _STLP_BEGIN_NAMESPACE
34 
35 _STLP_MOVE_TO_PRIV_NAMESPACE
36 
37 // Non-inline member functions from _Deque_base.
38 
39 template <class _Tp, class _Alloc >
~_Deque_base()40 _Deque_base<_Tp,_Alloc >::~_Deque_base() {
41   if (_M_map._M_data) {
42     _M_destroy_nodes(_M_start._M_node, this->_M_finish._M_node + 1);
43     _M_map.deallocate(_M_map._M_data, _M_map_size._M_data);
44   }
45 }
46 
47 template <class _Tp, class _Alloc >
_M_initialize_map(size_t __num_elements)48 void _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements) {
49   size_t __num_nodes = __num_elements / this->buffer_size() + 1 ;
50 
51   _M_map_size._M_data = (max)((size_t) _S_initial_map_size, __num_nodes + 2);
52   _M_map._M_data = _M_map.allocate(_M_map_size._M_data);
53 
54   _Tp** __nstart = _M_map._M_data + (_M_map_size._M_data - __num_nodes) / 2;
55   _Tp** __nfinish = __nstart + __num_nodes;
56 
57   _STLP_TRY {
58     _M_create_nodes(__nstart, __nfinish);
59   }
60   _STLP_UNWIND((_M_map.deallocate(_M_map._M_data, _M_map_size._M_data),
61                 _M_map._M_data = 0, _M_map_size._M_data = 0))
62   _M_start._M_set_node(__nstart);
63   this->_M_finish._M_set_node(__nfinish - 1);
64   _M_start._M_cur = _M_start._M_first;
65   this->_M_finish._M_cur = this->_M_finish._M_first + __num_elements % this->buffer_size();
66 }
67 
68 template <class _Tp, class _Alloc >
_M_create_nodes(_Tp ** __nstart,_Tp ** __nfinish)69 void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart,
70                                               _Tp** __nfinish) {
71   _Tp** __cur = __nstart;
72   _STLP_TRY {
73     for (; __cur < __nfinish; ++__cur)
74       *__cur = _M_map_size.allocate(this->buffer_size());
75   }
76   _STLP_UNWIND(_M_destroy_nodes(__nstart, __cur))
77 }
78 
79 template <class _Tp, class _Alloc >
_M_destroy_nodes(_Tp ** __nstart,_Tp ** __nfinish)80 void _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart,
81                                                _Tp** __nfinish) {
82   for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
83     _M_map_size.deallocate(*__n, this->buffer_size());
84 }
85 
86 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
87 #  define deque _STLP_PTR_IMPL_NAME(deque)
88 #elif defined (_STLP_DEBUG)
89 #  define deque _STLP_NON_DBG_NAME(deque)
90 #else
91 _STLP_MOVE_TO_STD_NAMESPACE
92 #endif
93 
94 #if defined (_STLP_NESTED_TYPE_PARAM_BUG)
95 // qualified references
96 #  define __iterator__   _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >
97 #  define const_iterator _Deque_iterator<_Tp, _Const_traits<_Tp>  >
98 #  define iterator       __iterator__
99 #  define size_type      size_t
100 #  define value_type     _Tp
101 #else
102 #  define __iterator__   _STLP_TYPENAME_ON_RETURN_TYPE deque<_Tp, _Alloc>::iterator
103 #endif
104 
105 template <class _Tp, class _Alloc >
106 deque<_Tp, _Alloc >&
107 deque<_Tp, _Alloc >::operator= (const deque<_Tp, _Alloc >& __x) {
108   const size_type __len = size();
109   if (&__x != this) {
110     if (__len >= __x.size())
111       erase(_STLP_STD::copy(__x.begin(), __x.end(), this->_M_start), this->_M_finish);
112     else {
113       const_iterator __mid = __x.begin() + difference_type(__len);
114       _STLP_STD::copy(__x.begin(), __mid, this->_M_start);
115       insert(this->_M_finish, __mid, __x.end());
116     }
117   }
118   return *this;
119 }
120 
121 template <class _Tp, class _Alloc >
_M_fill_insert(iterator __pos,size_type __n,const value_type & __x)122 void deque<_Tp, _Alloc >::_M_fill_insert(iterator __pos,
123                                          size_type __n, const value_type& __x) {
124 #if !defined (_STLP_NO_MOVE_SEMANTIC)
125   typedef typename __move_traits<_Tp>::implemented _Movable;
126 #endif
127   if (__pos._M_cur == this->_M_start._M_cur) {
128     iterator __new_start = _M_reserve_elements_at_front(__n);
129     _STLP_TRY {
130       uninitialized_fill(__new_start, this->_M_start, __x);
131     }
132     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
133     this->_M_start = __new_start;
134   }
135   else if (__pos._M_cur == this->_M_finish._M_cur) {
136     iterator __new_finish = _M_reserve_elements_at_back(__n);
137     _STLP_TRY {
138       uninitialized_fill(this->_M_finish, __new_finish, __x);
139     }
140     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node+1, __new_finish._M_node+1))
141     this->_M_finish = __new_finish;
142   }
143   else
144     _M_fill_insert_aux(__pos, __n, __x, _Movable());
145 }
146 
147 #if !defined (_STLP_MEMBER_TEMPLATES)
148 
149 template <class _Tp, class _Alloc >
insert(iterator __pos,const value_type * __first,const value_type * __last)150 void deque<_Tp, _Alloc>::insert(iterator __pos,
151                                 const value_type* __first, const value_type* __last) {
152 #if !defined (_STLP_NO_MOVE_SEMANTIC)
153   typedef typename __move_traits<_Tp>::implemented _Movable;
154 #endif
155   size_type __n = __last - __first;
156   if (__pos._M_cur == this->_M_start._M_cur) {
157     iterator __new_start = _M_reserve_elements_at_front(__n);
158     _STLP_TRY {
159       _STLP_PRIV __ucopy(__first, __last, __new_start);
160     }
161     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
162     this->_M_start = __new_start;
163   }
164   else if (__pos._M_cur == this->_M_finish._M_cur) {
165     iterator __new_finish = _M_reserve_elements_at_back(__n);
166     _STLP_TRY {
167       _STLP_PRIV __ucopy(__first, __last, this->_M_finish);
168     }
169     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,
170                                         __new_finish._M_node + 1))
171     this->_M_finish = __new_finish;
172   }
173   else
174     _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
175 }
176 
177 template <class _Tp, class _Alloc >
insert(iterator __pos,const_iterator __first,const_iterator __last)178 void deque<_Tp,_Alloc>::insert(iterator __pos,
179                                const_iterator __first, const_iterator __last) {
180 #if !defined (_STLP_NO_MOVE_SEMANTIC)
181   typedef typename __move_traits<_Tp>::implemented _Movable;
182 #endif
183   size_type __n = __last - __first;
184   if (__pos._M_cur == this->_M_start._M_cur) {
185     iterator __new_start = _M_reserve_elements_at_front(__n);
186     _STLP_TRY {
187       _STLP_PRIV __ucopy(__first, __last, __new_start);
188     }
189     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
190     this->_M_start = __new_start;
191   }
192   else if (__pos._M_cur == this->_M_finish._M_cur) {
193     iterator __new_finish = _M_reserve_elements_at_back(__n);
194     _STLP_TRY {
195       _STLP_PRIV __ucopy(__first, __last, this->_M_finish);
196     }
197     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,
198                                         __new_finish._M_node + 1))
199     this->_M_finish = __new_finish;
200   }
201   else
202     _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
203 }
204 
205 #endif /* _STLP_MEMBER_TEMPLATES */
206 
207 template <class _Tp, class _Alloc >
_M_erase(iterator __pos,const __true_type &)208 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos,
209                                          const __true_type& /*_Movable*/) {
210   difference_type __index = __pos - this->_M_start;
211   if (size_type(__index) < this->size() >> 1) {
212     //We move the start of the deque one position to the right
213     //starting from the rightmost element to move.
214     iterator __src = __pos, __dst = __pos;
215     _STLP_STD::_Destroy(&(*__dst));
216     if (__src != this->_M_start) {
217       for (--__src; __dst != this->_M_start; --__src, --__dst) {
218         _STLP_STD::_Move_Construct(&(*__dst), *__src);
219         _STLP_STD::_Destroy_Moved(&(*__src));
220       }
221     }
222     _M_pop_front_aux();
223   }
224   else {
225     iterator __src = __pos, __dst = __pos;
226     _STLP_STD::_Destroy(&(*__dst));
227     for (++__src; __src != this->_M_finish; ++__src, ++__dst) {
228       _STLP_STD::_Move_Construct(&(*__dst), *__src);
229       _STLP_STD::_Destroy_Moved(&(*__src));
230     }
231     //Duplication of the pop_back code without the destroy which has already been done:
232     if (this->_M_finish._M_cur != this->_M_finish._M_first) {
233       --this->_M_finish._M_cur;
234     }
235     else {
236       _M_pop_back_aux();
237     }
238   }
239   return this->_M_start + __index;
240 }
241 
242 template <class _Tp, class _Alloc >
_M_erase(iterator __pos,const __false_type &)243 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos,
244                                          const __false_type& /*_Movable*/) {
245   iterator __next = __pos;
246   ++__next;
247   difference_type __index = __pos - this->_M_start;
248   if (size_type(__index) < this->size() >> 1) {
249     copy_backward(this->_M_start, __pos, __next);
250     pop_front();
251   }
252   else {
253     _STLP_STD::copy(__next, this->_M_finish, __pos);
254     pop_back();
255   }
256   return this->_M_start + __index;
257 }
258 
259 template <class _Tp, class _Alloc >
_M_erase(iterator __first,iterator __last,const __true_type &)260 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last,
261                                          const __true_type& /*_Movable*/) {
262   difference_type __n = __last - __first;
263   difference_type __elems_before = __first - this->_M_start;
264   if (__elems_before <= difference_type(this->size() - __n) / 2) {
265     iterator __src = __first, __dst = __last;
266     if (__src != this->_M_start) {
267       for (--__src, --__dst; (__src >= this->_M_start) && (__dst >= __first); --__src, --__dst) {
268         _STLP_STD::_Destroy(&(*__dst));
269         _STLP_STD::_Move_Construct(&(*__dst), *__src);
270       }
271       if (__dst >= __first) {
272         //There are more elements to erase than elements to move
273         _STLP_STD::_Destroy_Range(__first, ++__dst);
274         _STLP_STD::_Destroy_Moved_Range(this->_M_start, __first);
275       }
276       else {
277         //There are more elements to move than elements to erase
278         for (; __src >= this->_M_start; --__src, --__dst) {
279           _STLP_STD::_Destroy_Moved(&(*__dst));
280           _STLP_STD::_Move_Construct(&(*__dst), *__src);
281         }
282         _STLP_STD::_Destroy_Moved_Range(this->_M_start, ++__dst);
283       }
284     }
285     else {
286       _STLP_STD::_Destroy_Range(this->_M_start, __last);
287     }
288     iterator __new_start = this->_M_start + __n;
289     this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node);
290     this->_M_start = __new_start;
291   }
292   else {
293     if (__last != this->_M_finish) {
294       iterator __src = __last, __dst = __first;
295       for (; (__src != this->_M_finish) && (__dst != __last); ++__src, ++__dst) {
296         _STLP_STD::_Destroy(&(*__dst));
297         _STLP_STD::_Move_Construct(&(*__dst), *__src);
298       }
299       if (__dst != __last) {
300         //There are more elements to erase than elements to move
301         _STLP_STD::_Destroy_Range(__dst, __last);
302         _STLP_STD::_Destroy_Moved_Range(__last, this->_M_finish);
303       }
304       else {
305         //There are more elements to move than elements to erase
306         for (; __src != this->_M_finish; ++__src, ++__dst) {
307           _STLP_STD::_Destroy_Moved(&(*__dst));
308           _STLP_STD::_Move_Construct(&(*__dst), *__src);
309         }
310         _STLP_STD::_Destroy_Moved_Range(__dst, this->_M_finish);
311       }
312     }
313     else {
314       _STLP_STD::_Destroy_Range(__first, this->_M_finish);
315     }
316     iterator __new_finish = this->_M_finish - __n;
317     this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1);
318     this->_M_finish = __new_finish;
319   }
320   return this->_M_start + __elems_before;
321 }
322 
323 template <class _Tp, class _Alloc >
_M_erase(iterator __first,iterator __last,const __false_type &)324 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last,
325                                          const __false_type& /*_Movable*/) {
326   difference_type __n = __last - __first;
327   difference_type __elems_before = __first - this->_M_start;
328   if (__elems_before <= difference_type(this->size() - __n) / 2) {
329     copy_backward(this->_M_start, __first, __last);
330     iterator __new_start = this->_M_start + __n;
331     _STLP_STD::_Destroy_Range(this->_M_start, __new_start);
332     this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node);
333     this->_M_start = __new_start;
334   }
335   else {
336     _STLP_STD::copy(__last, this->_M_finish, __first);
337     iterator __new_finish = this->_M_finish - __n;
338     _STLP_STD::_Destroy_Range(__new_finish, this->_M_finish);
339     this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1);
340     this->_M_finish = __new_finish;
341   }
342   return this->_M_start + __elems_before;
343 }
344 
345 template <class _Tp, class _Alloc >
clear()346 void deque<_Tp,_Alloc>::clear() {
347   for (_Map_pointer __node = this->_M_start._M_node + 1;
348        __node < this->_M_finish._M_node;
349        ++__node) {
350     _STLP_STD::_Destroy_Range(*__node, *__node + this->buffer_size());
351     this->_M_map_size.deallocate(*__node, this->buffer_size());
352   }
353 
354   if (this->_M_start._M_node != this->_M_finish._M_node) {
355     _STLP_STD::_Destroy_Range(this->_M_start._M_cur, this->_M_start._M_last);
356     _STLP_STD::_Destroy_Range(this->_M_finish._M_first, this->_M_finish._M_cur);
357     this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size());
358   }
359   else
360     _STLP_STD::_Destroy_Range(this->_M_start._M_cur, this->_M_finish._M_cur);
361 
362   this->_M_finish = this->_M_start;
363 }
364 
365 // Precondition: this->_M_start and this->_M_finish have already been initialized,
366 // but none of the deque's elements have yet been constructed.
367 template <class _Tp, class _Alloc >
_M_fill_initialize(const value_type & __val,const __false_type &)368 void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __val,
369                                            const __false_type& /*_TrivialInit*/) {
370   _Map_pointer __cur = this->_M_start._M_node;
371   _STLP_TRY {
372     for (; __cur < this->_M_finish._M_node; ++__cur)
373       uninitialized_fill(*__cur, *__cur + this->buffer_size(), __val);
374     uninitialized_fill(this->_M_finish._M_first, this->_M_finish._M_cur, __val);
375   }
376   _STLP_UNWIND(_STLP_STD::_Destroy_Range(this->_M_start, iterator(*__cur, __cur)))
377 }
378 
379 
380 // Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1.
381 template <class _Tp, class _Alloc >
_M_push_back_aux_v(const value_type & __t)382 void deque<_Tp,_Alloc>::_M_push_back_aux_v(const value_type& __t) {
383   _M_reserve_map_at_back();
384   *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size());
385   _STLP_TRY {
386     _Copy_Construct(this->_M_finish._M_cur, __t);
387     this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
388     this->_M_finish._M_cur = this->_M_finish._M_first;
389   }
390   _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1),
391                                             this->buffer_size()))
392 }
393 
394 #if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
395 // Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1.
396 template <class _Tp, class _Alloc >
_M_push_back_aux()397 void deque<_Tp,_Alloc>::_M_push_back_aux() {
398   _M_reserve_map_at_back();
399   *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size());
400   _STLP_TRY {
401     _STLP_STD::_Construct(this->_M_finish._M_cur);
402     this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
403     this->_M_finish._M_cur = this->_M_finish._M_first;
404   }
405   _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1),
406                                             this->buffer_size()))
407 }
408 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
409 
410 // Called only if this->_M_start._M_cur == this->_M_start._M_first.
411 template <class _Tp, class _Alloc >
_M_push_front_aux_v(const value_type & __t)412 void deque<_Tp,_Alloc>::_M_push_front_aux_v(const value_type& __t) {
413   _M_reserve_map_at_front();
414   *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size());
415   _STLP_TRY {
416     this->_M_start._M_set_node(this->_M_start._M_node - 1);
417     this->_M_start._M_cur = this->_M_start._M_last - 1;
418     _Copy_Construct(this->_M_start._M_cur, __t);
419   }
420   _STLP_UNWIND((++this->_M_start,
421                 this->_M_map_size.deallocate(*(this->_M_start._M_node - 1), this->buffer_size())))
422 }
423 
424 
425 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
426 // Called only if this->_M_start._M_cur == this->_M_start._M_first.
427 template <class _Tp, class _Alloc >
_M_push_front_aux()428 void deque<_Tp,_Alloc>::_M_push_front_aux() {
429   _M_reserve_map_at_front();
430   *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size());
431   _STLP_TRY {
432     this->_M_start._M_set_node(this->_M_start._M_node - 1);
433     this->_M_start._M_cur = this->_M_start._M_last - 1;
434     _STLP_STD::_Construct(this->_M_start._M_cur);
435   }
436   _STLP_UNWIND((++this->_M_start, this->_M_map_size.deallocate(*(this->_M_start._M_node - 1),
437                                                                this->buffer_size())))
438 }
439 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
440 
441 // Called only if this->_M_finish._M_cur == this->_M_finish._M_first.
442 template <class _Tp, class _Alloc >
_M_pop_back_aux()443 void deque<_Tp,_Alloc>::_M_pop_back_aux() {
444   this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size());
445   this->_M_finish._M_set_node(this->_M_finish._M_node - 1);
446   this->_M_finish._M_cur = this->_M_finish._M_last - 1;
447 }
448 
449 // Note that if the deque has at least one element (a precondition for this member
450 // function), and if this->_M_start._M_cur == this->_M_start._M_last, then the deque
451 // must have at least two nodes.
452 template <class _Tp, class _Alloc >
_M_pop_front_aux()453 void deque<_Tp,_Alloc>::_M_pop_front_aux() {
454   if (this->_M_start._M_cur != this->_M_start._M_last - 1)
455     ++this->_M_start._M_cur;
456   else {
457     this->_M_map_size.deallocate(this->_M_start._M_first, this->buffer_size());
458     this->_M_start._M_set_node(this->_M_start._M_node + 1);
459     this->_M_start._M_cur = this->_M_start._M_first;
460   }
461 }
462 
463 template <class _Tp, class _Alloc >
_M_fill_insert_aux(iterator __pos,size_type __n,const value_type & __x,const __true_type &)464 __iterator__ deque<_Tp,_Alloc>::_M_fill_insert_aux(iterator __pos, size_type __n,
465                                                    const value_type& __x,
466                                                    const __true_type& /*_Movable*/) {
467   const difference_type __elems_before = __pos - this->_M_start;
468   size_type __length = this->size();
469   value_type __x_copy = __x;
470   if (__elems_before <= difference_type(__length / 2)) {
471     iterator __new_start = _M_reserve_elements_at_front(__n);
472     __pos = this->_M_start + __elems_before;
473     _STLP_TRY {
474       iterator __dst = __new_start;
475       iterator __src = this->_M_start;
476       for (; __src != __pos; ++__dst, ++__src) {
477         _STLP_STD::_Move_Construct(&(*__dst), *__src);
478         _STLP_STD::_Destroy_Moved(&(*__src));
479       }
480       this->_M_start = __new_start;
481       uninitialized_fill(__dst, __src, __x_copy);
482       __pos = __dst;
483     }
484     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
485   }
486   else {
487     iterator __new_finish = _M_reserve_elements_at_back(__n);
488     const difference_type __elems_after = difference_type(__length) - __elems_before;
489     __pos = this->_M_finish - __elems_after;
490     _STLP_TRY {
491       iterator __dst = __new_finish;
492       iterator __src = this->_M_finish;
493       for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
494         _STLP_STD::_Move_Construct(&(*__dst), *__src);
495         _STLP_STD::_Destroy_Moved(&(*__src));
496       }
497       this->_M_finish = __new_finish;
498       uninitialized_fill(__pos, __pos + __n, __x_copy);
499     }
500     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
501   }
502   return __pos;
503 }
504 
505 template <class _Tp, class _Alloc >
_M_fill_insert_aux(iterator __pos,size_type __n,const value_type & __x,const __false_type &)506 __iterator__ deque<_Tp,_Alloc>::_M_fill_insert_aux(iterator __pos, size_type __n,
507                                                    const value_type& __x,
508                                                    const __false_type& /*_Movable*/) {
509   const difference_type __elems_before = __pos - this->_M_start;
510   size_type __length = this->size();
511   value_type __x_copy = __x;
512   if (__elems_before <= difference_type(__length / 2)) {
513     iterator __new_start = _M_reserve_elements_at_front(__n);
514     iterator __old_start = this->_M_start;
515     __pos = this->_M_start + __elems_before;
516     _STLP_TRY {
517       if (__elems_before >= difference_type(__n)) {
518         iterator __start_n = this->_M_start + difference_type(__n);
519         _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
520         this->_M_start = __new_start;
521         _STLP_STD::copy(__start_n, __pos, __old_start);
522         _STLP_STD::fill(__pos - difference_type(__n), __pos, __x_copy);
523         __pos -= difference_type(__n);
524       }
525       else {
526         _STLP_PRIV __uninitialized_copy_fill(this->_M_start, __pos, __new_start,
527                                              this->_M_start, __x_copy);
528         this->_M_start = __new_start;
529         fill(__old_start, __pos, __x_copy);
530       }
531     }
532     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
533   }
534   else {
535     iterator __new_finish = _M_reserve_elements_at_back(__n);
536     iterator __old_finish = this->_M_finish;
537     const difference_type __elems_after =
538       difference_type(__length) - __elems_before;
539     __pos = this->_M_finish - __elems_after;
540     _STLP_TRY {
541       if (__elems_after > difference_type(__n)) {
542         iterator __finish_n = this->_M_finish - difference_type(__n);
543         _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
544         this->_M_finish = __new_finish;
545         copy_backward(__pos, __finish_n, __old_finish);
546         fill(__pos, __pos + difference_type(__n), __x_copy);
547       }
548       else {
549         _STLP_PRIV __uninitialized_fill_copy(this->_M_finish, __pos + difference_type(__n),
550                                              __x_copy, __pos, this->_M_finish);
551         this->_M_finish = __new_finish;
552         fill(__pos, __old_finish, __x_copy);
553       }
554     }
555     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
556   }
557   return __pos;
558 }
559 
560 #if !defined (_STLP_MEMBER_TEMPLATES)
561 template <class _Tp, class _Alloc >
_M_insert_range_aux(iterator __pos,const value_type * __first,const value_type * __last,size_type __n,const __true_type &)562 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
563                                             const value_type* __first, const value_type* __last,
564                                             size_type __n, const __true_type& /*_Movable*/) {
565   const difference_type __elems_before = __pos - this->_M_start;
566   size_type __length = size();
567   if (__elems_before <= difference_type(__length / 2)) {
568     iterator __new_start = _M_reserve_elements_at_front(__n);
569     __pos = this->_M_start + __elems_before;
570     _STLP_TRY {
571       iterator __dst = __new_start;
572       iterator __src = this->_M_start;
573       for (; __src != __pos; ++__dst, ++__src) {
574         _STLP_STD::_Move_Construct(&(*__dst), *__src);
575         _STLP_STD::_Destroy_Moved(&(*__src));
576       }
577       this->_M_start = __new_start;
578       _STLP_PRIV __ucopy(__first, __last, __dst);
579     }
580     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
581   }
582   else {
583     iterator __new_finish = _M_reserve_elements_at_back(__n);
584     const difference_type __elems_after = difference_type(__length) - __elems_before;
585     __pos = this->_M_finish - __elems_after;
586     _STLP_TRY {
587       iterator __dst = __new_finish;
588       iterator __src = this->_M_finish;
589       for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
590         _STLP_STD::_Move_Construct(&(*__dst), *__src);
591         _STLP_STD::_Destroy_Moved(&(*__src));
592       }
593       this->_M_finish = __new_finish;
594       _STLP_PRIV __ucopy(__first, __last, __pos);
595     }
596     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
597   }
598 }
599 
600 template <class _Tp, class _Alloc >
_M_insert_range_aux(iterator __pos,const value_type * __first,const value_type * __last,size_type __n,const __false_type &)601 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
602                                             const value_type* __first, const value_type* __last,
603                                             size_type __n, const __false_type& /*_Movable*/) {
604   const difference_type __elems_before = __pos - this->_M_start;
605   size_type __length = size();
606   if (__elems_before <= difference_type(__length / 2)) {
607     iterator __new_start = _M_reserve_elements_at_front(__n);
608     iterator __old_start = this->_M_start;
609     __pos = this->_M_start + __elems_before;
610     _STLP_TRY {
611       if (__elems_before >= difference_type(__n)) {
612         iterator __start_n = this->_M_start + difference_type(__n);
613         _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
614         this->_M_start = __new_start;
615         _STLP_STD::copy(__start_n, __pos, __old_start);
616         _STLP_STD::copy(__first, __last, __pos - difference_type(__n));
617       }
618       else {
619         const value_type* __mid = __first + (difference_type(__n) - __elems_before);
620         _STLP_PRIV __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);
621         this->_M_start = __new_start;
622         _STLP_STD::copy(__mid, __last, __old_start);
623       }
624     }
625     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
626   }
627   else {
628     iterator __new_finish = _M_reserve_elements_at_back(__n);
629     iterator __old_finish = this->_M_finish;
630     const difference_type __elems_after =
631       difference_type(__length) - __elems_before;
632     __pos = this->_M_finish - __elems_after;
633     _STLP_TRY {
634 
635       if (__elems_after > difference_type(__n)) {
636         iterator __finish_n = this->_M_finish - difference_type(__n);
637         _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
638         this->_M_finish = __new_finish;
639         _STLP_STD::copy_backward(__pos, __finish_n, __old_finish);
640         _STLP_STD::copy(__first, __last, __pos);
641       }
642       else {
643         const value_type* __mid = __first + __elems_after;
644         _STLP_PRIV __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);
645         this->_M_finish = __new_finish;
646         _STLP_STD::copy(__first, __mid, __pos);
647       }
648     }
649     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
650   }
651 }
652 
653 template <class _Tp, class _Alloc >
_M_insert_range_aux(iterator __pos,const_iterator __first,const_iterator __last,size_type __n,const __true_type &)654 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
655                                             const_iterator __first, const_iterator __last,
656                                             size_type __n, const __true_type& /*_Movable*/) {
657   const difference_type __elems_before = __pos - this->_M_start;
658   size_type __length = size();
659   if (__elems_before <= difference_type(__length / 2)) {
660     iterator __new_start = _M_reserve_elements_at_front(__n);
661     __pos = this->_M_start + __elems_before;
662     _STLP_TRY {
663       iterator __dst = __new_start;
664       iterator __src = this->_M_start;
665       for (; __src != __pos; ++__dst, ++__src) {
666         _STLP_STD::_Move_Construct(&(*__dst), *__src);
667         _STLP_STD::_Destroy_Moved(&(*__src));
668       }
669       this->_M_start = __new_start;
670       _STLP_PRIV __ucopy(__first, __last, __dst);
671     }
672     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
673   }
674   else {
675     iterator __new_finish = _M_reserve_elements_at_back(__n);
676     const difference_type __elems_after = difference_type(__length) - __elems_before;
677     __pos = this->_M_finish - __elems_after;
678     _STLP_TRY {
679       iterator __dst = __new_finish;
680       iterator __src = this->_M_finish;
681       for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
682         _STLP_STD::_Move_Construct(&(*__dst), *__src);
683         _STLP_STD::_Destroy_Moved(&(*__src));
684       }
685       this->_M_finish = __new_finish;
686       _STLP_PRIV __ucopy(__first, __last, __pos);
687     }
688     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
689   }
690 }
691 
692 template <class _Tp, class _Alloc >
_M_insert_range_aux(iterator __pos,const_iterator __first,const_iterator __last,size_type __n,const __false_type &)693 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
694                                             const_iterator __first, const_iterator __last,
695                                             size_type __n, const __false_type& /*_Movable*/) {
696   const difference_type __elems_before = __pos - this->_M_start;
697   size_type __length = size();
698   if (__elems_before < difference_type(__length / 2)) {
699     iterator __new_start = _M_reserve_elements_at_front(__n);
700     iterator __old_start = this->_M_start;
701     __pos = this->_M_start + __elems_before;
702     _STLP_TRY {
703       if (__elems_before >= difference_type(__n)) {
704         iterator __start_n = this->_M_start + __n;
705         _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
706         this->_M_start = __new_start;
707         _STLP_STD::copy(__start_n, __pos, __old_start);
708         _STLP_STD::copy(__first, __last, __pos - difference_type(__n));
709       }
710       else {
711         const_iterator __mid = __first + (__n - __elems_before);
712         _STLP_PRIV __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);
713         this->_M_start = __new_start;
714         _STLP_STD::copy(__mid, __last, __old_start);
715       }
716     }
717     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
718   }
719   else {
720     iterator __new_finish = _M_reserve_elements_at_back(__n);
721     iterator __old_finish = this->_M_finish;
722     const difference_type __elems_after = __length - __elems_before;
723     __pos = this->_M_finish - __elems_after;
724     _STLP_TRY {
725       if (__elems_after > difference_type(__n)) {
726         iterator __finish_n = this->_M_finish - difference_type(__n);
727         _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
728         this->_M_finish = __new_finish;
729         _STLP_STD::copy_backward(__pos, __finish_n, __old_finish);
730         _STLP_STD::copy(__first, __last, __pos);
731       }
732       else {
733         const_iterator __mid = __first + __elems_after;
734         _STLP_PRIV __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);
735         this->_M_finish = __new_finish;
736         _STLP_STD::copy(__first, __mid, __pos);
737       }
738     }
739     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
740   }
741 }
742 #endif /* _STLP_MEMBER_TEMPLATES */
743 
744 template <class _Tp, class _Alloc >
_M_new_elements_at_front(size_type __new_elems)745 void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems) {
746   size_type __new_nodes
747       = (__new_elems + this->buffer_size() - 1) / this->buffer_size();
748   _M_reserve_map_at_front(__new_nodes);
749   size_type __i = 1;
750   _STLP_TRY {
751     for (; __i <= __new_nodes; ++__i)
752       *(this->_M_start._M_node - __i) = this->_M_map_size.allocate(this->buffer_size());
753   }
754   _STLP_UNWIND(for (size_type __j = 1; __j < __i; ++__j)
755                  this->_M_map_size.deallocate(*(this->_M_start._M_node - __j), this->buffer_size()))
756 }
757 
758 template <class _Tp, class _Alloc >
_M_new_elements_at_back(size_type __new_elems)759 void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems) {
760   size_type __new_nodes
761       = (__new_elems + this->buffer_size() - 1) / this->buffer_size();
762   _M_reserve_map_at_back(__new_nodes);
763   size_type __i = 1;
764   _STLP_TRY {
765     for (; __i <= __new_nodes; ++__i)
766       *(this->_M_finish._M_node + __i) = this->_M_map_size.allocate(this->buffer_size());
767   }
768   _STLP_UNWIND(for (size_type __j = 1; __j < __i; ++__j)
769                  this->_M_map_size.deallocate(*(this->_M_finish._M_node + __j), this->buffer_size()))
770 }
771 
772 template <class _Tp, class _Alloc >
_M_reallocate_map(size_type __nodes_to_add,bool __add_at_front)773 void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
774                                           bool __add_at_front) {
775   size_type __old_num_nodes = this->_M_finish._M_node - this->_M_start._M_node + 1;
776   size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
777 
778   _Map_pointer __new_nstart;
779   if (this->_M_map_size._M_data > 2 * __new_num_nodes) {
780     __new_nstart = this->_M_map._M_data + (this->_M_map_size._M_data - __new_num_nodes) / 2
781                      + (__add_at_front ? __nodes_to_add : 0);
782     if (__new_nstart < this->_M_start._M_node)
783       _STLP_STD::copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart);
784     else
785       _STLP_STD::copy_backward(this->_M_start._M_node, this->_M_finish._M_node + 1,
786                                __new_nstart + __old_num_nodes);
787   }
788   else {
789     size_type __new_map_size =
790       this->_M_map_size._M_data + (max)((size_t)this->_M_map_size._M_data, __nodes_to_add) + 2;
791 
792     _Map_pointer __new_map = this->_M_map.allocate(__new_map_size);
793     __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
794                              + (__add_at_front ? __nodes_to_add : 0);
795     _STLP_STD::copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart);
796     this->_M_map.deallocate(this->_M_map._M_data, this->_M_map_size._M_data);
797 
798     this->_M_map._M_data = __new_map;
799     this->_M_map_size._M_data = __new_map_size;
800   }
801 
802   this->_M_start._M_set_node(__new_nstart);
803   this->_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
804 }
805 
806 #if defined (deque)
807 #  undef deque
808 _STLP_MOVE_TO_STD_NAMESPACE
809 #endif
810 
811 _STLP_END_NAMESPACE
812 
813 #undef __iterator__
814 #undef iterator
815 #undef const_iterator
816 #undef size_type
817 #undef value_type
818 
819 #endif /*  _STLP_DEQUE_C */
820 
821 // Local Variables:
822 // mode:C++
823 // End:
824