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