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