]>
Commit | Line | Data |
---|---|---|
83144cfc PE |
1 | // Deque implementation (out of line) -*- C++ -*- |
2 | ||
a5544970 | 3 | // Copyright (C) 2001-2019 Free Software Foundation, Inc. |
83144cfc PE |
4 | // |
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 | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
83144cfc PE |
9 | // any later version. |
10 | ||
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. | |
15 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
83144cfc | 19 | |
748086b7 JJ |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
83144cfc PE |
24 | |
25 | /* | |
26 | * | |
27 | * Copyright (c) 1994 | |
28 | * Hewlett-Packard Company | |
29 | * | |
30 | * Permission to use, copy, modify, distribute and sell this software | |
31 | * and its documentation for any purpose is hereby granted without fee, | |
32 | * provided that the above copyright notice appear in all copies and | |
33 | * that both that copyright notice and this permission notice appear | |
34 | * in supporting documentation. Hewlett-Packard Company makes no | |
35 | * representations about the suitability of this software for any | |
36 | * purpose. It is provided "as is" without express or implied warranty. | |
37 | * | |
38 | * | |
39 | * Copyright (c) 1997 | |
40 | * Silicon Graphics Computer Systems, Inc. | |
41 | * | |
42 | * Permission to use, copy, modify, distribute and sell this software | |
43 | * and its documentation for any purpose is hereby granted without fee, | |
44 | * provided that the above copyright notice appear in all copies and | |
45 | * that both that copyright notice and this permission notice appear | |
46 | * in supporting documentation. Silicon Graphics makes no | |
47 | * representations about the suitability of this software for any | |
48 | * purpose. It is provided "as is" without express or implied warranty. | |
49 | */ | |
50 | ||
f910786b | 51 | /** @file bits/deque.tcc |
83144cfc | 52 | * This is an internal header file, included by other library headers. |
f910786b | 53 | * Do not attempt to use it directly. @headername{deque} |
83144cfc PE |
54 | */ |
55 | ||
3d7c150e BK |
56 | #ifndef _DEQUE_TCC |
57 | #define _DEQUE_TCC 1 | |
83144cfc | 58 | |
6004c17b FD |
59 | #include <bits/stl_algobase.h> |
60 | ||
12ffa228 BK |
61 | namespace std _GLIBCXX_VISIBILITY(default) |
62 | { | |
4a15d842 | 63 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
12ffa228 | 64 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |
3cbc7af0 | 65 | |
734f5023 | 66 | #if __cplusplus >= 201103L |
dc2cf706 PC |
67 | template <typename _Tp, typename _Alloc> |
68 | void | |
69 | deque<_Tp, _Alloc>:: | |
70 | _M_default_initialize() | |
71 | { | |
72 | _Map_pointer __cur; | |
73 | __try | |
6f1becb6 FD |
74 | { |
75 | for (__cur = this->_M_impl._M_start._M_node; | |
dc2cf706 PC |
76 | __cur < this->_M_impl._M_finish._M_node; |
77 | ++__cur) | |
6f1becb6 | 78 | std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(), |
dc2cf706 | 79 | _M_get_Tp_allocator()); |
6f1becb6 | 80 | std::__uninitialized_default_a(this->_M_impl._M_finish._M_first, |
dc2cf706 PC |
81 | this->_M_impl._M_finish._M_cur, |
82 | _M_get_Tp_allocator()); | |
6f1becb6 | 83 | } |
dc2cf706 | 84 | __catch(...) |
6f1becb6 FD |
85 | { |
86 | std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), | |
dc2cf706 | 87 | _M_get_Tp_allocator()); |
6f1becb6 FD |
88 | __throw_exception_again; |
89 | } | |
dc2cf706 PC |
90 | } |
91 | #endif | |
92 | ||
3971a4d2 | 93 | template <typename _Tp, typename _Alloc> |
23d4fa49 PC |
94 | deque<_Tp, _Alloc>& |
95 | deque<_Tp, _Alloc>:: | |
3971a4d2 | 96 | operator=(const deque& __x) |
83144cfc | 97 | { |
3971a4d2 | 98 | if (&__x != this) |
f6592a9e | 99 | { |
fd18c76a JW |
100 | #if __cplusplus >= 201103L |
101 | if (_Alloc_traits::_S_propagate_on_copy_assign()) | |
102 | { | |
103 | if (!_Alloc_traits::_S_always_equal() | |
6f1becb6 FD |
104 | && _M_get_Tp_allocator() != __x._M_get_Tp_allocator()) |
105 | { | |
fd18c76a JW |
106 | // Replacement allocator cannot free existing storage, |
107 | // so deallocate everything and take copy of __x's data. | |
108 | _M_replace_map(__x, __x.get_allocator()); | |
109 | std::__alloc_on_copy(_M_get_Tp_allocator(), | |
110 | __x._M_get_Tp_allocator()); | |
111 | return *this; | |
112 | } | |
113 | std::__alloc_on_copy(_M_get_Tp_allocator(), | |
114 | __x._M_get_Tp_allocator()); | |
115 | } | |
116 | #endif | |
117 | const size_type __len = size(); | |
f6592a9e | 118 | if (__len >= __x.size()) |
d2cc7f92 PC |
119 | _M_erase_at_end(std::copy(__x.begin(), __x.end(), |
120 | this->_M_impl._M_start)); | |
f6592a9e PC |
121 | else |
122 | { | |
123 | const_iterator __mid = __x.begin() + difference_type(__len); | |
03f9ea44 | 124 | std::copy(__x.begin(), __mid, this->_M_impl._M_start); |
d7e16fc5 FD |
125 | _M_range_insert_aux(this->_M_impl._M_finish, __mid, __x.end(), |
126 | std::random_access_iterator_tag()); | |
f6592a9e PC |
127 | } |
128 | } | |
3971a4d2 | 129 | return *this; |
ed6814f7 BI |
130 | } |
131 | ||
734f5023 | 132 | #if __cplusplus >= 201103L |
4dc3e453 PC |
133 | template<typename _Tp, typename _Alloc> |
134 | template<typename... _Args> | |
594ef205 JW |
135 | #if __cplusplus > 201402L |
136 | typename deque<_Tp, _Alloc>::reference | |
137 | #else | |
4dc3e453 | 138 | void |
594ef205 | 139 | #endif |
4dc3e453 PC |
140 | deque<_Tp, _Alloc>:: |
141 | emplace_front(_Args&&... __args) | |
142 | { | |
143 | if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) | |
144 | { | |
fd18c76a | 145 | _Alloc_traits::construct(this->_M_impl, |
6f1becb6 FD |
146 | this->_M_impl._M_start._M_cur - 1, |
147 | std::forward<_Args>(__args)...); | |
4dc3e453 PC |
148 | --this->_M_impl._M_start._M_cur; |
149 | } | |
150 | else | |
151 | _M_push_front_aux(std::forward<_Args>(__args)...); | |
594ef205 JW |
152 | #if __cplusplus > 201402L |
153 | return front(); | |
154 | #endif | |
4dc3e453 PC |
155 | } |
156 | ||
157 | template<typename _Tp, typename _Alloc> | |
158 | template<typename... _Args> | |
594ef205 JW |
159 | #if __cplusplus > 201402L |
160 | typename deque<_Tp, _Alloc>::reference | |
161 | #else | |
4dc3e453 | 162 | void |
594ef205 | 163 | #endif |
4dc3e453 PC |
164 | deque<_Tp, _Alloc>:: |
165 | emplace_back(_Args&&... __args) | |
166 | { | |
167 | if (this->_M_impl._M_finish._M_cur | |
168 | != this->_M_impl._M_finish._M_last - 1) | |
169 | { | |
fd18c76a | 170 | _Alloc_traits::construct(this->_M_impl, |
6f1becb6 FD |
171 | this->_M_impl._M_finish._M_cur, |
172 | std::forward<_Args>(__args)...); | |
4dc3e453 PC |
173 | ++this->_M_impl._M_finish._M_cur; |
174 | } | |
175 | else | |
176 | _M_push_back_aux(std::forward<_Args>(__args)...); | |
594ef205 JW |
177 | #if __cplusplus > 201402L |
178 | return back(); | |
179 | #endif | |
4dc3e453 PC |
180 | } |
181 | #endif | |
182 | ||
734f5023 | 183 | #if __cplusplus >= 201103L |
7ffec97f CJ |
184 | template<typename _Tp, typename _Alloc> |
185 | template<typename... _Args> | |
186 | typename deque<_Tp, _Alloc>::iterator | |
187 | deque<_Tp, _Alloc>:: | |
7b61c5a9 | 188 | emplace(const_iterator __position, _Args&&... __args) |
7ffec97f CJ |
189 | { |
190 | if (__position._M_cur == this->_M_impl._M_start._M_cur) | |
191 | { | |
195940ad | 192 | emplace_front(std::forward<_Args>(__args)...); |
7ffec97f CJ |
193 | return this->_M_impl._M_start; |
194 | } | |
195 | else if (__position._M_cur == this->_M_impl._M_finish._M_cur) | |
196 | { | |
195940ad | 197 | emplace_back(std::forward<_Args>(__args)...); |
7ffec97f CJ |
198 | iterator __tmp = this->_M_impl._M_finish; |
199 | --__tmp; | |
200 | return __tmp; | |
201 | } | |
202 | else | |
7b61c5a9 PC |
203 | return _M_insert_aux(__position._M_const_cast(), |
204 | std::forward<_Args>(__args)...); | |
7ffec97f CJ |
205 | } |
206 | #endif | |
207 | ||
7b61c5a9 PC |
208 | template <typename _Tp, typename _Alloc> |
209 | typename deque<_Tp, _Alloc>::iterator | |
210 | deque<_Tp, _Alloc>:: | |
211 | #if __cplusplus >= 201103L | |
212 | insert(const_iterator __position, const value_type& __x) | |
213 | #else | |
214 | insert(iterator __position, const value_type& __x) | |
215 | #endif | |
216 | { | |
217 | if (__position._M_cur == this->_M_impl._M_start._M_cur) | |
218 | { | |
219 | push_front(__x); | |
220 | return this->_M_impl._M_start; | |
221 | } | |
222 | else if (__position._M_cur == this->_M_impl._M_finish._M_cur) | |
223 | { | |
224 | push_back(__x); | |
225 | iterator __tmp = this->_M_impl._M_finish; | |
226 | --__tmp; | |
227 | return __tmp; | |
228 | } | |
229 | else | |
230 | return _M_insert_aux(__position._M_const_cast(), __x); | |
231 | } | |
232 | ||
3971a4d2 | 233 | template <typename _Tp, typename _Alloc> |
23d4fa49 | 234 | typename deque<_Tp, _Alloc>::iterator |
43da93a7 | 235 | deque<_Tp, _Alloc>:: |
94938aec | 236 | _M_erase(iterator __position) |
83144cfc | 237 | { |
3971a4d2 PE |
238 | iterator __next = __position; |
239 | ++__next; | |
1b4454bf PC |
240 | const difference_type __index = __position - begin(); |
241 | if (static_cast<size_type>(__index) < (size() >> 1)) | |
f6592a9e | 242 | { |
d2cc7f92 | 243 | if (__position != begin()) |
245a5fe5 | 244 | _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next); |
f6592a9e PC |
245 | pop_front(); |
246 | } | |
3971a4d2 | 247 | else |
f6592a9e | 248 | { |
d2cc7f92 | 249 | if (__next != end()) |
245a5fe5 | 250 | _GLIBCXX_MOVE3(__next, end(), __position); |
f6592a9e PC |
251 | pop_back(); |
252 | } | |
d2cc7f92 | 253 | return begin() + __index; |
3971a4d2 | 254 | } |
ed6814f7 | 255 | |
3971a4d2 | 256 | template <typename _Tp, typename _Alloc> |
23d4fa49 | 257 | typename deque<_Tp, _Alloc>::iterator |
43da93a7 | 258 | deque<_Tp, _Alloc>:: |
94938aec | 259 | _M_erase(iterator __first, iterator __last) |
83144cfc | 260 | { |
a7cee01d PC |
261 | if (__first == __last) |
262 | return __first; | |
263 | else if (__first == begin() && __last == end()) | |
f6592a9e PC |
264 | { |
265 | clear(); | |
d2cc7f92 | 266 | return end(); |
f6592a9e | 267 | } |
3971a4d2 | 268 | else |
f6592a9e PC |
269 | { |
270 | const difference_type __n = __last - __first; | |
d2cc7f92 | 271 | const difference_type __elems_before = __first - begin(); |
45dc23a6 | 272 | if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2) |
f6592a9e | 273 | { |
d2cc7f92 | 274 | if (__first != begin()) |
245a5fe5 | 275 | _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last); |
d2cc7f92 | 276 | _M_erase_at_begin(begin() + __n); |
f6592a9e PC |
277 | } |
278 | else | |
279 | { | |
d2cc7f92 | 280 | if (__last != end()) |
245a5fe5 | 281 | _GLIBCXX_MOVE3(__last, end(), __first); |
d2cc7f92 | 282 | _M_erase_at_end(end() - __n); |
f6592a9e | 283 | } |
d2cc7f92 | 284 | return begin() + __elems_before; |
f6592a9e | 285 | } |
3971a4d2 | 286 | } |
ed6814f7 | 287 | |
3971a4d2 | 288 | template <typename _Tp, class _Alloc> |
08addde6 | 289 | template <typename _InputIterator> |
3971a4d2 | 290 | void |
2fecaef4 PC |
291 | deque<_Tp, _Alloc>:: |
292 | _M_assign_aux(_InputIterator __first, _InputIterator __last, | |
293 | std::input_iterator_tag) | |
83144cfc | 294 | { |
6f1becb6 FD |
295 | iterator __cur = begin(); |
296 | for (; __first != __last && __cur != end(); ++__cur, (void)++__first) | |
297 | *__cur = *__first; | |
298 | if (__first == __last) | |
299 | _M_erase_at_end(__cur); | |
300 | else | |
301 | _M_range_insert_aux(end(), __first, __last, | |
d7e16fc5 | 302 | std::__iterator_category(__first)); |
83144cfc | 303 | } |
ed6814f7 | 304 | |
3971a4d2 | 305 | template <typename _Tp, typename _Alloc> |
83144cfc | 306 | void |
43da93a7 | 307 | deque<_Tp, _Alloc>:: |
3971a4d2 | 308 | _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) |
83144cfc | 309 | { |
03f9ea44 | 310 | if (__pos._M_cur == this->_M_impl._M_start._M_cur) |
f6592a9e PC |
311 | { |
312 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
bc2631e0 | 313 | __try |
f6592a9e | 314 | { |
1985f1cd | 315 | std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start, |
1b4454bf | 316 | __x, _M_get_Tp_allocator()); |
03f9ea44 | 317 | this->_M_impl._M_start = __new_start; |
f6592a9e | 318 | } |
bc2631e0 | 319 | __catch(...) |
f6592a9e | 320 | { |
0d8c9baf PC |
321 | _M_destroy_nodes(__new_start._M_node, |
322 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
323 | __throw_exception_again; |
324 | } | |
325 | } | |
03f9ea44 | 326 | else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) |
f6592a9e PC |
327 | { |
328 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
bc2631e0 | 329 | __try |
f6592a9e | 330 | { |
1985f1cd MA |
331 | std::__uninitialized_fill_a(this->_M_impl._M_finish, |
332 | __new_finish, __x, | |
4fd20a8f | 333 | _M_get_Tp_allocator()); |
03f9ea44 | 334 | this->_M_impl._M_finish = __new_finish; |
f6592a9e | 335 | } |
bc2631e0 | 336 | __catch(...) |
f6592a9e | 337 | { |
03f9ea44 | 338 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
ed6814f7 | 339 | __new_finish._M_node + 1); |
f6592a9e PC |
340 | __throw_exception_again; |
341 | } | |
342 | } | |
ed6814f7 | 343 | else |
6f1becb6 | 344 | _M_insert_aux(__pos, __n, __x); |
83144cfc | 345 | } |
ed6814f7 | 346 | |
734f5023 | 347 | #if __cplusplus >= 201103L |
dc2cf706 PC |
348 | template <typename _Tp, typename _Alloc> |
349 | void | |
350 | deque<_Tp, _Alloc>:: | |
351 | _M_default_append(size_type __n) | |
352 | { | |
353 | if (__n) | |
354 | { | |
355 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
356 | __try | |
357 | { | |
358 | std::__uninitialized_default_a(this->_M_impl._M_finish, | |
359 | __new_finish, | |
360 | _M_get_Tp_allocator()); | |
361 | this->_M_impl._M_finish = __new_finish; | |
362 | } | |
363 | __catch(...) | |
364 | { | |
365 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, | |
366 | __new_finish._M_node + 1); | |
367 | __throw_exception_again; | |
368 | } | |
369 | } | |
370 | } | |
8a752dfe FD |
371 | |
372 | template <typename _Tp, typename _Alloc> | |
373 | bool | |
374 | deque<_Tp, _Alloc>:: | |
375 | _M_shrink_to_fit() | |
376 | { | |
377 | const difference_type __front_capacity | |
378 | = (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first); | |
379 | if (__front_capacity == 0) | |
380 | return false; | |
381 | ||
382 | const difference_type __back_capacity | |
383 | = (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur); | |
384 | if (__front_capacity + __back_capacity < _S_buffer_size()) | |
385 | return false; | |
386 | ||
387 | return std::__shrink_to_fit_aux<deque>::_S_do_it(*this); | |
388 | } | |
dc2cf706 PC |
389 | #endif |
390 | ||
3971a4d2 PE |
391 | template <typename _Tp, typename _Alloc> |
392 | void | |
43da93a7 | 393 | deque<_Tp, _Alloc>:: |
3971a4d2 | 394 | _M_fill_initialize(const value_type& __value) |
83144cfc | 395 | { |
3971a4d2 | 396 | _Map_pointer __cur; |
bc2631e0 | 397 | __try |
6f1becb6 FD |
398 | { |
399 | for (__cur = this->_M_impl._M_start._M_node; | |
03f9ea44 | 400 | __cur < this->_M_impl._M_finish._M_node; |
8fbc5ae7 | 401 | ++__cur) |
6f1becb6 | 402 | std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), |
4fd20a8f | 403 | __value, _M_get_Tp_allocator()); |
6f1becb6 | 404 | std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, |
1985f1cd | 405 | this->_M_impl._M_finish._M_cur, |
4fd20a8f | 406 | __value, _M_get_Tp_allocator()); |
6f1becb6 | 407 | } |
bc2631e0 | 408 | __catch(...) |
6f1becb6 FD |
409 | { |
410 | std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), | |
4fd20a8f | 411 | _M_get_Tp_allocator()); |
6f1becb6 FD |
412 | __throw_exception_again; |
413 | } | |
83144cfc | 414 | } |
ed6814f7 | 415 | |
3971a4d2 PE |
416 | template <typename _Tp, typename _Alloc> |
417 | template <typename _InputIterator> | |
418 | void | |
43da93a7 | 419 | deque<_Tp, _Alloc>:: |
3971a4d2 | 420 | _M_range_initialize(_InputIterator __first, _InputIterator __last, |
6f1becb6 | 421 | std::input_iterator_tag) |
3971a4d2 | 422 | { |
6f1becb6 FD |
423 | this->_M_initialize_map(0); |
424 | __try | |
425 | { | |
426 | for (; __first != __last; ++__first) | |
ad6fdc19 PC |
427 | #if __cplusplus >= 201103L |
428 | emplace_back(*__first); | |
429 | #else | |
6f1becb6 | 430 | push_back(*__first); |
ad6fdc19 | 431 | #endif |
6f1becb6 FD |
432 | } |
433 | __catch(...) | |
434 | { | |
435 | clear(); | |
436 | __throw_exception_again; | |
437 | } | |
3971a4d2 | 438 | } |
ed6814f7 | 439 | |
3971a4d2 PE |
440 | template <typename _Tp, typename _Alloc> |
441 | template <typename _ForwardIterator> | |
442 | void | |
43da93a7 | 443 | deque<_Tp, _Alloc>:: |
3971a4d2 | 444 | _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, |
6f1becb6 | 445 | std::forward_iterator_tag) |
3971a4d2 | 446 | { |
6f1becb6 FD |
447 | const size_type __n = std::distance(__first, __last); |
448 | this->_M_initialize_map(_S_check_init_len(__n, _M_get_Tp_allocator())); | |
449 | ||
450 | _Map_pointer __cur_node; | |
451 | __try | |
452 | { | |
453 | for (__cur_node = this->_M_impl._M_start._M_node; | |
454 | __cur_node < this->_M_impl._M_finish._M_node; | |
455 | ++__cur_node) | |
1f9c69a9 PC |
456 | { |
457 | _ForwardIterator __mid = __first; | |
458 | std::advance(__mid, _S_buffer_size()); | |
459 | std::__uninitialized_copy_a(__first, __mid, *__cur_node, | |
460 | _M_get_Tp_allocator()); | |
461 | __first = __mid; | |
462 | } | |
6f1becb6 | 463 | std::__uninitialized_copy_a(__first, __last, |
1985f1cd | 464 | this->_M_impl._M_finish._M_first, |
4fd20a8f | 465 | _M_get_Tp_allocator()); |
6f1becb6 FD |
466 | } |
467 | __catch(...) | |
468 | { | |
469 | std::_Destroy(this->_M_impl._M_start, | |
1985f1cd | 470 | iterator(*__cur_node, __cur_node), |
4fd20a8f | 471 | _M_get_Tp_allocator()); |
6f1becb6 FD |
472 | __throw_exception_again; |
473 | } | |
3971a4d2 | 474 | } |
ed6814f7 | 475 | |
03f9ea44 | 476 | // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. |
7ffec97f | 477 | template<typename _Tp, typename _Alloc> |
734f5023 | 478 | #if __cplusplus >= 201103L |
7ffec97f CJ |
479 | template<typename... _Args> |
480 | void | |
481 | deque<_Tp, _Alloc>:: | |
482 | _M_push_back_aux(_Args&&... __args) | |
7ffec97f CJ |
483 | #else |
484 | void | |
485 | deque<_Tp, _Alloc>:: | |
486 | _M_push_back_aux(const value_type& __t) | |
7ffec97f | 487 | #endif |
b4d9ec93 | 488 | { |
af55b3af JW |
489 | if (size() == max_size()) |
490 | __throw_length_error( | |
491 | __N("cannot create std::deque larger than max_size()")); | |
492 | ||
7ffec97f CJ |
493 | _M_reserve_map_at_back(); |
494 | *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); | |
bc2631e0 | 495 | __try |
7ffec97f | 496 | { |
734f5023 | 497 | #if __cplusplus >= 201103L |
fd18c76a | 498 | _Alloc_traits::construct(this->_M_impl, |
6f1becb6 FD |
499 | this->_M_impl._M_finish._M_cur, |
500 | std::forward<_Args>(__args)...); | |
b4d9ec93 PC |
501 | #else |
502 | this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t); | |
503 | #endif | |
7ffec97f CJ |
504 | this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node |
505 | + 1); | |
506 | this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; | |
507 | } | |
bc2631e0 | 508 | __catch(...) |
7ffec97f CJ |
509 | { |
510 | _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); | |
511 | __throw_exception_again; | |
512 | } | |
513 | } | |
ed6814f7 | 514 | |
03f9ea44 | 515 | // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. |
7ffec97f | 516 | template<typename _Tp, typename _Alloc> |
734f5023 | 517 | #if __cplusplus >= 201103L |
7ffec97f CJ |
518 | template<typename... _Args> |
519 | void | |
520 | deque<_Tp, _Alloc>:: | |
521 | _M_push_front_aux(_Args&&... __args) | |
7ffec97f CJ |
522 | #else |
523 | void | |
524 | deque<_Tp, _Alloc>:: | |
525 | _M_push_front_aux(const value_type& __t) | |
7ffec97f | 526 | #endif |
b4d9ec93 | 527 | { |
af55b3af JW |
528 | if (size() == max_size()) |
529 | __throw_length_error( | |
530 | __N("cannot create std::deque larger than max_size()")); | |
531 | ||
7ffec97f CJ |
532 | _M_reserve_map_at_front(); |
533 | *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); | |
bc2631e0 | 534 | __try |
7ffec97f CJ |
535 | { |
536 | this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node | |
537 | - 1); | |
538 | this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; | |
734f5023 | 539 | #if __cplusplus >= 201103L |
fd18c76a | 540 | _Alloc_traits::construct(this->_M_impl, |
6f1becb6 FD |
541 | this->_M_impl._M_start._M_cur, |
542 | std::forward<_Args>(__args)...); | |
b4d9ec93 PC |
543 | #else |
544 | this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t); | |
545 | #endif | |
7ffec97f | 546 | } |
bc2631e0 | 547 | __catch(...) |
7ffec97f CJ |
548 | { |
549 | ++this->_M_impl._M_start; | |
550 | _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); | |
551 | __throw_exception_again; | |
552 | } | |
553 | } | |
ed6814f7 | 554 | |
03f9ea44 | 555 | // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. |
3971a4d2 | 556 | template <typename _Tp, typename _Alloc> |
43da93a7 | 557 | void deque<_Tp, _Alloc>:: |
3971a4d2 PE |
558 | _M_pop_back_aux() |
559 | { | |
03f9ea44 DM |
560 | _M_deallocate_node(this->_M_impl._M_finish._M_first); |
561 | this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); | |
562 | this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; | |
fd18c76a JW |
563 | _Alloc_traits::destroy(_M_get_Tp_allocator(), |
564 | this->_M_impl._M_finish._M_cur); | |
83144cfc | 565 | } |
ed6814f7 | 566 | |
0d8c9baf PC |
567 | // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. |
568 | // Note that if the deque has at least one element (a precondition for this | |
569 | // member function), and if | |
570 | // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, | |
571 | // then the deque must have at least two nodes. | |
3971a4d2 | 572 | template <typename _Tp, typename _Alloc> |
43da93a7 | 573 | void deque<_Tp, _Alloc>:: |
3971a4d2 PE |
574 | _M_pop_front_aux() |
575 | { | |
fd18c76a JW |
576 | _Alloc_traits::destroy(_M_get_Tp_allocator(), |
577 | this->_M_impl._M_start._M_cur); | |
03f9ea44 DM |
578 | _M_deallocate_node(this->_M_impl._M_start._M_first); |
579 | this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); | |
580 | this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; | |
ed6814f7 BI |
581 | } |
582 | ||
3971a4d2 PE |
583 | template <typename _Tp, typename _Alloc> |
584 | template <typename _InputIterator> | |
585 | void | |
43da93a7 | 586 | deque<_Tp, _Alloc>:: |
3971a4d2 | 587 | _M_range_insert_aux(iterator __pos, |
6f1becb6 FD |
588 | _InputIterator __first, _InputIterator __last, |
589 | std::input_iterator_tag) | |
f6592a9e | 590 | { std::copy(__first, __last, std::inserter(*this, __pos)); } |
ed6814f7 | 591 | |
3971a4d2 PE |
592 | template <typename _Tp, typename _Alloc> |
593 | template <typename _ForwardIterator> | |
594 | void | |
43da93a7 | 595 | deque<_Tp, _Alloc>:: |
3971a4d2 | 596 | _M_range_insert_aux(iterator __pos, |
6f1becb6 FD |
597 | _ForwardIterator __first, _ForwardIterator __last, |
598 | std::forward_iterator_tag) | |
3971a4d2 | 599 | { |
6f1becb6 FD |
600 | const size_type __n = std::distance(__first, __last); |
601 | if (__pos._M_cur == this->_M_impl._M_start._M_cur) | |
f6592a9e PC |
602 | { |
603 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
bc2631e0 | 604 | __try |
f6592a9e | 605 | { |
1985f1cd | 606 | std::__uninitialized_copy_a(__first, __last, __new_start, |
4fd20a8f | 607 | _M_get_Tp_allocator()); |
03f9ea44 | 608 | this->_M_impl._M_start = __new_start; |
f6592a9e | 609 | } |
bc2631e0 | 610 | __catch(...) |
f6592a9e | 611 | { |
0d8c9baf PC |
612 | _M_destroy_nodes(__new_start._M_node, |
613 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
614 | __throw_exception_again; |
615 | } | |
616 | } | |
6f1becb6 | 617 | else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) |
f6592a9e PC |
618 | { |
619 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
bc2631e0 | 620 | __try |
f6592a9e | 621 | { |
1985f1cd MA |
622 | std::__uninitialized_copy_a(__first, __last, |
623 | this->_M_impl._M_finish, | |
4fd20a8f | 624 | _M_get_Tp_allocator()); |
03f9ea44 | 625 | this->_M_impl._M_finish = __new_finish; |
f6592a9e | 626 | } |
bc2631e0 | 627 | __catch(...) |
f6592a9e | 628 | { |
03f9ea44 | 629 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
f6592a9e PC |
630 | __new_finish._M_node + 1); |
631 | __throw_exception_again; | |
632 | } | |
633 | } | |
6f1becb6 FD |
634 | else |
635 | _M_insert_aux(__pos, __first, __last, __n); | |
3971a4d2 | 636 | } |
ed6814f7 | 637 | |
7ffec97f | 638 | template<typename _Tp, typename _Alloc> |
734f5023 | 639 | #if __cplusplus >= 201103L |
7ffec97f CJ |
640 | template<typename... _Args> |
641 | typename deque<_Tp, _Alloc>::iterator | |
642 | deque<_Tp, _Alloc>:: | |
643 | _M_insert_aux(iterator __pos, _Args&&... __args) | |
644 | { | |
645 | value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy | |
646 | #else | |
3971a4d2 | 647 | typename deque<_Tp, _Alloc>::iterator |
7ffec97f CJ |
648 | deque<_Tp, _Alloc>:: |
649 | _M_insert_aux(iterator __pos, const value_type& __x) | |
650 | { | |
651 | value_type __x_copy = __x; // XXX copy | |
652 | #endif | |
653 | difference_type __index = __pos - this->_M_impl._M_start; | |
654 | if (static_cast<size_type>(__index) < size() / 2) | |
655 | { | |
656 | push_front(_GLIBCXX_MOVE(front())); | |
657 | iterator __front1 = this->_M_impl._M_start; | |
658 | ++__front1; | |
659 | iterator __front2 = __front1; | |
660 | ++__front2; | |
661 | __pos = this->_M_impl._M_start + __index; | |
662 | iterator __pos1 = __pos; | |
663 | ++__pos1; | |
664 | _GLIBCXX_MOVE3(__front2, __pos1, __front1); | |
665 | } | |
666 | else | |
667 | { | |
668 | push_back(_GLIBCXX_MOVE(back())); | |
669 | iterator __back1 = this->_M_impl._M_finish; | |
670 | --__back1; | |
671 | iterator __back2 = __back1; | |
672 | --__back2; | |
673 | __pos = this->_M_impl._M_start + __index; | |
674 | _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1); | |
675 | } | |
676 | *__pos = _GLIBCXX_MOVE(__x_copy); | |
677 | return __pos; | |
678 | } | |
ed6814f7 | 679 | |
3971a4d2 | 680 | template <typename _Tp, typename _Alloc> |
83144cfc | 681 | void |
43da93a7 | 682 | deque<_Tp, _Alloc>:: |
3971a4d2 | 683 | _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) |
83144cfc | 684 | { |
03f9ea44 | 685 | const difference_type __elems_before = __pos - this->_M_impl._M_start; |
43da93a7 | 686 | const size_type __length = this->size(); |
3971a4d2 PE |
687 | value_type __x_copy = __x; |
688 | if (__elems_before < difference_type(__length / 2)) | |
f6592a9e PC |
689 | { |
690 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
03f9ea44 DM |
691 | iterator __old_start = this->_M_impl._M_start; |
692 | __pos = this->_M_impl._M_start + __elems_before; | |
bc2631e0 | 693 | __try |
f6592a9e PC |
694 | { |
695 | if (__elems_before >= difference_type(__n)) | |
696 | { | |
0d8c9baf PC |
697 | iterator __start_n = (this->_M_impl._M_start |
698 | + difference_type(__n)); | |
7ffec97f | 699 | std::__uninitialized_move_a(this->_M_impl._M_start, |
ba43cf0b | 700 | __start_n, __new_start, |
4fd20a8f | 701 | _M_get_Tp_allocator()); |
03f9ea44 | 702 | this->_M_impl._M_start = __new_start; |
7ffec97f | 703 | _GLIBCXX_MOVE3(__start_n, __pos, __old_start); |
1b4454bf | 704 | std::fill(__pos - difference_type(__n), __pos, __x_copy); |
f6592a9e PC |
705 | } |
706 | else | |
707 | { | |
7ffec97f | 708 | std::__uninitialized_move_fill(this->_M_impl._M_start, |
0d8c9baf PC |
709 | __pos, __new_start, |
710 | this->_M_impl._M_start, | |
1985f1cd | 711 | __x_copy, |
4fd20a8f | 712 | _M_get_Tp_allocator()); |
03f9ea44 | 713 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
714 | std::fill(__old_start, __pos, __x_copy); |
715 | } | |
716 | } | |
bc2631e0 | 717 | __catch(...) |
ed6814f7 | 718 | { |
0d8c9baf PC |
719 | _M_destroy_nodes(__new_start._M_node, |
720 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
721 | __throw_exception_again; |
722 | } | |
723 | } | |
83144cfc | 724 | else |
f6592a9e PC |
725 | { |
726 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
03f9ea44 | 727 | iterator __old_finish = this->_M_impl._M_finish; |
ed6814f7 | 728 | const difference_type __elems_after = |
f6592a9e | 729 | difference_type(__length) - __elems_before; |
03f9ea44 | 730 | __pos = this->_M_impl._M_finish - __elems_after; |
bc2631e0 | 731 | __try |
f6592a9e PC |
732 | { |
733 | if (__elems_after > difference_type(__n)) | |
734 | { | |
0d8c9baf PC |
735 | iterator __finish_n = (this->_M_impl._M_finish |
736 | - difference_type(__n)); | |
7ffec97f | 737 | std::__uninitialized_move_a(__finish_n, |
ba43cf0b | 738 | this->_M_impl._M_finish, |
1985f1cd | 739 | this->_M_impl._M_finish, |
4fd20a8f | 740 | _M_get_Tp_allocator()); |
03f9ea44 | 741 | this->_M_impl._M_finish = __new_finish; |
7ffec97f | 742 | _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); |
f6592a9e PC |
743 | std::fill(__pos, __pos + difference_type(__n), __x_copy); |
744 | } | |
745 | else | |
746 | { | |
7ffec97f | 747 | std::__uninitialized_fill_move(this->_M_impl._M_finish, |
f6592a9e PC |
748 | __pos + difference_type(__n), |
749 | __x_copy, __pos, | |
1985f1cd | 750 | this->_M_impl._M_finish, |
4fd20a8f | 751 | _M_get_Tp_allocator()); |
03f9ea44 | 752 | this->_M_impl._M_finish = __new_finish; |
f6592a9e PC |
753 | std::fill(__pos, __old_finish, __x_copy); |
754 | } | |
755 | } | |
bc2631e0 | 756 | __catch(...) |
ed6814f7 | 757 | { |
03f9ea44 | 758 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
f6592a9e PC |
759 | __new_finish._M_node + 1); |
760 | __throw_exception_again; | |
761 | } | |
762 | } | |
83144cfc | 763 | } |
ed6814f7 | 764 | |
3971a4d2 PE |
765 | template <typename _Tp, typename _Alloc> |
766 | template <typename _ForwardIterator> | |
767 | void | |
43da93a7 | 768 | deque<_Tp, _Alloc>:: |
3971a4d2 | 769 | _M_insert_aux(iterator __pos, |
6f1becb6 FD |
770 | _ForwardIterator __first, _ForwardIterator __last, |
771 | size_type __n) | |
83144cfc | 772 | { |
6f1becb6 FD |
773 | const difference_type __elemsbefore = __pos - this->_M_impl._M_start; |
774 | const size_type __length = size(); | |
775 | if (static_cast<size_type>(__elemsbefore) < __length / 2) | |
f6592a9e PC |
776 | { |
777 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
03f9ea44 DM |
778 | iterator __old_start = this->_M_impl._M_start; |
779 | __pos = this->_M_impl._M_start + __elemsbefore; | |
bc2631e0 | 780 | __try |
f6592a9e PC |
781 | { |
782 | if (__elemsbefore >= difference_type(__n)) | |
783 | { | |
0d8c9baf PC |
784 | iterator __start_n = (this->_M_impl._M_start |
785 | + difference_type(__n)); | |
7ffec97f | 786 | std::__uninitialized_move_a(this->_M_impl._M_start, |
ba43cf0b | 787 | __start_n, __new_start, |
4fd20a8f | 788 | _M_get_Tp_allocator()); |
03f9ea44 | 789 | this->_M_impl._M_start = __new_start; |
7ffec97f | 790 | _GLIBCXX_MOVE3(__start_n, __pos, __old_start); |
f6592a9e PC |
791 | std::copy(__first, __last, __pos - difference_type(__n)); |
792 | } | |
793 | else | |
794 | { | |
795 | _ForwardIterator __mid = __first; | |
796 | std::advance(__mid, difference_type(__n) - __elemsbefore); | |
7ffec97f | 797 | std::__uninitialized_move_copy(this->_M_impl._M_start, |
0d8c9baf | 798 | __pos, __first, __mid, |
1985f1cd | 799 | __new_start, |
4fd20a8f | 800 | _M_get_Tp_allocator()); |
03f9ea44 | 801 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
802 | std::copy(__mid, __last, __old_start); |
803 | } | |
804 | } | |
bc2631e0 | 805 | __catch(...) |
f6592a9e | 806 | { |
0d8c9baf PC |
807 | _M_destroy_nodes(__new_start._M_node, |
808 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
809 | __throw_exception_again; |
810 | } | |
811 | } | |
6f1becb6 FD |
812 | else |
813 | { | |
814 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
815 | iterator __old_finish = this->_M_impl._M_finish; | |
816 | const difference_type __elemsafter = | |
817 | difference_type(__length) - __elemsbefore; | |
818 | __pos = this->_M_impl._M_finish - __elemsafter; | |
819 | __try | |
820 | { | |
821 | if (__elemsafter > difference_type(__n)) | |
f6592a9e | 822 | { |
0d8c9baf PC |
823 | iterator __finish_n = (this->_M_impl._M_finish |
824 | - difference_type(__n)); | |
7ffec97f | 825 | std::__uninitialized_move_a(__finish_n, |
1985f1cd MA |
826 | this->_M_impl._M_finish, |
827 | this->_M_impl._M_finish, | |
4fd20a8f | 828 | _M_get_Tp_allocator()); |
03f9ea44 | 829 | this->_M_impl._M_finish = __new_finish; |
7ffec97f | 830 | _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); |
f6592a9e PC |
831 | std::copy(__first, __last, __pos); |
832 | } | |
6f1becb6 | 833 | else |
f6592a9e PC |
834 | { |
835 | _ForwardIterator __mid = __first; | |
836 | std::advance(__mid, __elemsafter); | |
7ffec97f | 837 | std::__uninitialized_copy_move(__mid, __last, __pos, |
03f9ea44 | 838 | this->_M_impl._M_finish, |
1985f1cd | 839 | this->_M_impl._M_finish, |
4fd20a8f | 840 | _M_get_Tp_allocator()); |
03f9ea44 | 841 | this->_M_impl._M_finish = __new_finish; |
f6592a9e PC |
842 | std::copy(__first, __mid, __pos); |
843 | } | |
6f1becb6 FD |
844 | } |
845 | __catch(...) | |
846 | { | |
847 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, | |
8fbc5ae7 | 848 | __new_finish._M_node + 1); |
6f1becb6 FD |
849 | __throw_exception_again; |
850 | } | |
851 | } | |
83144cfc | 852 | } |
ed6814f7 | 853 | |
d2cc7f92 PC |
854 | template<typename _Tp, typename _Alloc> |
855 | void | |
856 | deque<_Tp, _Alloc>:: | |
857 | _M_destroy_data_aux(iterator __first, iterator __last) | |
858 | { | |
859 | for (_Map_pointer __node = __first._M_node + 1; | |
860 | __node < __last._M_node; ++__node) | |
861 | std::_Destroy(*__node, *__node + _S_buffer_size(), | |
862 | _M_get_Tp_allocator()); | |
863 | ||
864 | if (__first._M_node != __last._M_node) | |
865 | { | |
866 | std::_Destroy(__first._M_cur, __first._M_last, | |
867 | _M_get_Tp_allocator()); | |
868 | std::_Destroy(__last._M_first, __last._M_cur, | |
869 | _M_get_Tp_allocator()); | |
870 | } | |
871 | else | |
872 | std::_Destroy(__first._M_cur, __last._M_cur, | |
873 | _M_get_Tp_allocator()); | |
874 | } | |
875 | ||
3971a4d2 PE |
876 | template <typename _Tp, typename _Alloc> |
877 | void | |
43da93a7 | 878 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
879 | _M_new_elements_at_front(size_type __new_elems) |
880 | { | |
1f9c69a9 PC |
881 | if (this->max_size() - this->size() < __new_elems) |
882 | __throw_length_error(__N("deque::_M_new_elements_at_front")); | |
883 | ||
884 | const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) | |
885 | / _S_buffer_size()); | |
3971a4d2 PE |
886 | _M_reserve_map_at_front(__new_nodes); |
887 | size_type __i; | |
bc2631e0 | 888 | __try |
6f1becb6 FD |
889 | { |
890 | for (__i = 1; __i <= __new_nodes; ++__i) | |
891 | *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); | |
892 | } | |
bc2631e0 | 893 | __catch(...) |
6f1becb6 FD |
894 | { |
895 | for (size_type __j = 1; __j < __i; ++__j) | |
896 | _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); | |
897 | __throw_exception_again; | |
898 | } | |
3971a4d2 | 899 | } |
ed6814f7 | 900 | |
3971a4d2 PE |
901 | template <typename _Tp, typename _Alloc> |
902 | void | |
43da93a7 | 903 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
904 | _M_new_elements_at_back(size_type __new_elems) |
905 | { | |
1f9c69a9 PC |
906 | if (this->max_size() - this->size() < __new_elems) |
907 | __throw_length_error(__N("deque::_M_new_elements_at_back")); | |
908 | ||
909 | const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) | |
910 | / _S_buffer_size()); | |
3971a4d2 PE |
911 | _M_reserve_map_at_back(__new_nodes); |
912 | size_type __i; | |
bc2631e0 | 913 | __try |
6f1becb6 FD |
914 | { |
915 | for (__i = 1; __i <= __new_nodes; ++__i) | |
916 | *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); | |
917 | } | |
bc2631e0 | 918 | __catch(...) |
6f1becb6 FD |
919 | { |
920 | for (size_type __j = 1; __j < __i; ++__j) | |
921 | _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); | |
922 | __throw_exception_again; | |
923 | } | |
3971a4d2 | 924 | } |
ed6814f7 | 925 | |
3971a4d2 PE |
926 | template <typename _Tp, typename _Alloc> |
927 | void | |
43da93a7 | 928 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
929 | _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) |
930 | { | |
43da93a7 | 931 | const size_type __old_num_nodes |
03f9ea44 | 932 | = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; |
43da93a7 | 933 | const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; |
ed6814f7 | 934 | |
3971a4d2 | 935 | _Map_pointer __new_nstart; |
03f9ea44 | 936 | if (this->_M_impl._M_map_size > 2 * __new_num_nodes) |
f6592a9e | 937 | { |
03f9ea44 | 938 | __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size |
ed6814f7 | 939 | - __new_num_nodes) / 2 |
6f1becb6 | 940 | + (__add_at_front ? __nodes_to_add : 0); |
03f9ea44 DM |
941 | if (__new_nstart < this->_M_impl._M_start._M_node) |
942 | std::copy(this->_M_impl._M_start._M_node, | |
1f9c69a9 PC |
943 | this->_M_impl._M_finish._M_node + 1, |
944 | __new_nstart); | |
f6592a9e | 945 | else |
03f9ea44 DM |
946 | std::copy_backward(this->_M_impl._M_start._M_node, |
947 | this->_M_impl._M_finish._M_node + 1, | |
f6592a9e PC |
948 | __new_nstart + __old_num_nodes); |
949 | } | |
3971a4d2 | 950 | else |
f6592a9e | 951 | { |
03f9ea44 | 952 | size_type __new_map_size = this->_M_impl._M_map_size |
6f1becb6 | 953 | + std::max(this->_M_impl._M_map_size, |
f6592a9e | 954 | __nodes_to_add) + 2; |
ed6814f7 | 955 | |
f6592a9e PC |
956 | _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); |
957 | __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 | |
6f1becb6 | 958 | + (__add_at_front ? __nodes_to_add : 0); |
03f9ea44 DM |
959 | std::copy(this->_M_impl._M_start._M_node, |
960 | this->_M_impl._M_finish._M_node + 1, | |
f6592a9e | 961 | __new_nstart); |
03f9ea44 | 962 | _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); |
ed6814f7 | 963 | |
03f9ea44 DM |
964 | this->_M_impl._M_map = __new_map; |
965 | this->_M_impl._M_map_size = __new_map_size; | |
f6592a9e | 966 | } |
ed6814f7 | 967 | |
03f9ea44 DM |
968 | this->_M_impl._M_start._M_set_node(__new_nstart); |
969 | this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); | |
83144cfc | 970 | } |
3cbc7af0 | 971 | |
6004c17b FD |
972 | _GLIBCXX_END_NAMESPACE_CONTAINER |
973 | ||
62c7a041 | 974 | // Overload for deque::iterators, exploiting the "segmented-iterator |
e2bf2007 | 975 | // optimization". |
6004c17b | 976 | template<typename _Tp, typename _VTp> |
62c7a041 | 977 | void |
6004c17b FD |
978 | __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first, |
979 | const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last, | |
980 | const _VTp& __value) | |
62c7a041 | 981 | { |
6004c17b FD |
982 | typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; |
983 | if (__first._M_node != __last._M_node) | |
984 | { | |
985 | std::__fill_a1(__first._M_cur, __first._M_last, __value); | |
62c7a041 | 986 | |
6004c17b FD |
987 | for (typename _Iter::_Map_pointer __node = __first._M_node + 1; |
988 | __node < __last._M_node; ++__node) | |
989 | std::__fill_a1(*__node, *__node + _Iter::_S_buffer_size(), __value); | |
62c7a041 | 990 | |
6004c17b FD |
991 | std::__fill_a1(__last._M_first, __last._M_cur, __value); |
992 | } | |
993 | else | |
994 | std::__fill_a1(__first._M_cur, __last._M_cur, __value); | |
995 | } | |
996 | ||
997 | template<bool _IsMove, | |
998 | typename _Tp, typename _Ref, typename _Ptr, typename _OI> | |
999 | _OI | |
1000 | __copy_move_dit(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, | |
1001 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, | |
1002 | _OI __result) | |
1003 | { | |
1004 | typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; | |
62c7a041 PC |
1005 | if (__first._M_node != __last._M_node) |
1006 | { | |
6004c17b FD |
1007 | __result |
1008 | = std::__copy_move_a1<_IsMove>(__first._M_cur, __first._M_last, | |
1009 | __result); | |
1010 | ||
1011 | for (typename _Iter::_Map_pointer __node = __first._M_node + 1; | |
1012 | __node != __last._M_node; ++__node) | |
1013 | __result | |
1014 | = std::__copy_move_a1<_IsMove>(*__node, | |
1015 | *__node + _Iter::_S_buffer_size(), | |
1016 | __result); | |
1017 | ||
1018 | return std::__copy_move_a1<_IsMove>(__last._M_first, __last._M_cur, | |
1019 | __result); | |
62c7a041 | 1020 | } |
6004c17b FD |
1021 | |
1022 | return std::__copy_move_a1<_IsMove>(__first._M_cur, __last._M_cur, | |
1023 | __result); | |
62c7a041 PC |
1024 | } |
1025 | ||
6004c17b FD |
1026 | template<bool _IsMove, |
1027 | typename _Tp, typename _Ref, typename _Ptr, typename _OI> | |
1028 | _OI | |
1029 | __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, | |
1030 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, | |
1031 | _OI __result) | |
1032 | { return __copy_move_dit<_IsMove>(__first, __last, __result); } | |
1033 | ||
1034 | template<bool _IsMove, | |
1035 | typename _ITp, typename _IRef, typename _IPtr, typename _OTp> | |
1036 | _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> | |
1037 | __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first, | |
1038 | _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last, | |
1039 | _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result) | |
1040 | { return __copy_move_dit<_IsMove>(__first, __last, __result); } | |
1041 | ||
1042 | template<bool _IsMove, typename _II, typename _Tp> | |
1043 | typename __gnu_cxx::__enable_if< | |
1044 | __is_random_access_iter<_II>::__value, | |
1045 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type | |
1046 | __copy_move_a1(_II __first, _II __last, | |
1047 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result) | |
e2bf2007 | 1048 | { |
6004c17b FD |
1049 | typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; |
1050 | typedef typename _Iter::difference_type difference_type; | |
e2bf2007 | 1051 | |
0800b8ea | 1052 | difference_type __len = __last - __first; |
e2bf2007 PC |
1053 | while (__len > 0) |
1054 | { | |
0800b8ea | 1055 | const difference_type __clen |
6004c17b FD |
1056 | = std::min(__len, __result._M_last - __result._M_cur); |
1057 | std::__copy_move_a1<_IsMove>(__first, __first + __clen, | |
1058 | __result._M_cur); | |
1059 | ||
e2bf2007 PC |
1060 | __first += __clen; |
1061 | __result += __clen; | |
1062 | __len -= __clen; | |
1063 | } | |
6004c17b | 1064 | |
e2bf2007 PC |
1065 | return __result; |
1066 | } | |
1067 | ||
6004c17b FD |
1068 | template<bool _IsMove, |
1069 | typename _Tp, typename _Ref, typename _Ptr, typename _OI> | |
1070 | _OI | |
1071 | __copy_move_backward_dit( | |
1072 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, | |
1073 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, | |
1074 | _OI __result) | |
1075 | { | |
1076 | typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; | |
1077 | if (__first._M_node != __last._M_node) | |
1078 | { | |
1079 | __result = std::__copy_move_backward_a1<_IsMove>( | |
1080 | __last._M_first, __last._M_cur, __result); | |
1081 | ||
1082 | for (typename _Iter::_Map_pointer __node = __last._M_node - 1; | |
1083 | __node != __first._M_node; --__node) | |
1084 | __result = std::__copy_move_backward_a1<_IsMove>( | |
1085 | *__node, *__node + _Iter::_S_buffer_size(), __result); | |
1086 | ||
1087 | return std::__copy_move_backward_a1<_IsMove>( | |
1088 | __first._M_cur, __first._M_last, __result); | |
1089 | } | |
1090 | ||
1091 | return std::__copy_move_backward_a1<_IsMove>( | |
1092 | __first._M_cur, __last._M_cur, __result); | |
1093 | } | |
1094 | ||
1095 | template<bool _IsMove, | |
1096 | typename _Tp, typename _Ref, typename _Ptr, typename _OI> | |
1097 | _OI | |
1098 | __copy_move_backward_a1( | |
1099 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, | |
1100 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, | |
1101 | _OI __result) | |
1102 | { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); } | |
1103 | ||
1104 | template<bool _IsMove, | |
1105 | typename _ITp, typename _IRef, typename _IPtr, typename _OTp> | |
1106 | _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> | |
1107 | __copy_move_backward_a1( | |
1108 | _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first, | |
1109 | _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last, | |
1110 | _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result) | |
1111 | { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); } | |
1112 | ||
1113 | template<bool _IsMove, typename _II, typename _Tp> | |
1114 | typename __gnu_cxx::__enable_if< | |
1115 | __is_random_access_iter<_II>::__value, | |
1116 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type | |
1117 | __copy_move_backward_a1(_II __first, _II __last, | |
1118 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result) | |
0800b8ea | 1119 | { |
6004c17b FD |
1120 | typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; |
1121 | typedef typename _Iter::difference_type difference_type; | |
0800b8ea PC |
1122 | |
1123 | difference_type __len = __last - __first; | |
1124 | while (__len > 0) | |
1125 | { | |
0800b8ea PC |
1126 | difference_type __rlen = __result._M_cur - __result._M_first; |
1127 | _Tp* __rend = __result._M_cur; | |
0800b8ea PC |
1128 | if (!__rlen) |
1129 | { | |
6004c17b | 1130 | __rlen = _Iter::_S_buffer_size(); |
0800b8ea PC |
1131 | __rend = *(__result._M_node - 1) + __rlen; |
1132 | } | |
1133 | ||
6004c17b FD |
1134 | const difference_type __clen = std::min(__len, __rlen); |
1135 | std::__copy_move_backward_a1<_IsMove>(__last - __clen, __last, __rend); | |
1136 | ||
0800b8ea PC |
1137 | __last -= __clen; |
1138 | __result -= __clen; | |
1139 | __len -= __clen; | |
1140 | } | |
6004c17b | 1141 | |
0800b8ea PC |
1142 | return __result; |
1143 | } | |
1144 | ||
6004c17b FD |
1145 | template<typename _Tp, typename _Ref, typename _Ptr, typename _II> |
1146 | bool | |
1147 | __equal_dit( | |
1148 | const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1, | |
1149 | const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1, | |
1150 | _II __first2) | |
e2bf2007 | 1151 | { |
6004c17b FD |
1152 | typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; |
1153 | if (__first1._M_node != __last1._M_node) | |
e2bf2007 | 1154 | { |
6004c17b FD |
1155 | if (!std::__equal_aux1(__first1._M_cur, __first1._M_last, __first2)) |
1156 | return false; | |
1157 | ||
1158 | __first2 += __first1._M_last - __first1._M_cur; | |
1159 | for (typename _Iter::_Map_pointer __node = __first1._M_node + 1; | |
1160 | __node != __last1._M_node; | |
1161 | __first2 += _Iter::_S_buffer_size(), ++__node) | |
1162 | if (!std::__equal_aux1(*__node, *__node + _Iter::_S_buffer_size(), | |
1163 | __first2)) | |
1164 | return false; | |
1165 | ||
1166 | return std::__equal_aux1(__last1._M_first, __last1._M_cur, __first2); | |
e2bf2007 | 1167 | } |
6004c17b FD |
1168 | |
1169 | return std::__equal_aux1(__first1._M_cur, __last1._M_cur, __first2); | |
e2bf2007 | 1170 | } |
0800b8ea | 1171 | |
6004c17b FD |
1172 | template<typename _Tp, typename _Ref, typename _Ptr, typename _II> |
1173 | typename __gnu_cxx::__enable_if< | |
1174 | __is_random_access_iter<_II>::__value, bool>::__type | |
1175 | __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first1, | |
1176 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last1, | |
1177 | _II __first2) | |
1178 | { return std::__equal_dit(__first1, __last1, __first2); } | |
1179 | ||
1180 | template<typename _Tp1, typename _Ref1, typename _Ptr1, | |
1181 | typename _Tp2, typename _Ref2, typename _Ptr2> | |
1182 | bool | |
1183 | __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1, | |
1184 | _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1, | |
1185 | _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2) | |
1186 | { return std::__equal_dit(__first1, __last1, __first2); } | |
1187 | ||
1188 | template<typename _II, typename _Tp, typename _Ref, typename _Ptr> | |
1189 | typename __gnu_cxx::__enable_if< | |
1190 | __is_random_access_iter<_II>::__value, bool>::__type | |
1191 | __equal_aux1(_II __first1, _II __last1, | |
1192 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first2) | |
0800b8ea | 1193 | { |
6004c17b FD |
1194 | typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; |
1195 | typedef typename _Iter::difference_type difference_type; | |
0800b8ea | 1196 | |
6004c17b | 1197 | difference_type __len = __last1 - __first1; |
0800b8ea PC |
1198 | while (__len > 0) |
1199 | { | |
6004c17b FD |
1200 | const difference_type __clen |
1201 | = std::min(__len, __first2._M_last - __first2._M_cur); | |
1202 | if (!std::__equal_aux1(__first1, __first1 + __clen, __first2._M_cur)) | |
1203 | return false; | |
0800b8ea | 1204 | |
6004c17b | 1205 | __first1 += __clen; |
0800b8ea | 1206 | __len -= __clen; |
6004c17b | 1207 | __first2 += __clen; |
0800b8ea | 1208 | } |
6004c17b FD |
1209 | |
1210 | return true; | |
0800b8ea | 1211 | } |
e2bf2007 | 1212 | |
4a15d842 | 1213 | _GLIBCXX_END_NAMESPACE_VERSION |
12ffa228 | 1214 | } // namespace std |
f6592a9e | 1215 | |
3d7c150e | 1216 | #endif |