]>
Commit | Line | Data |
---|---|---|
83144cfc PE |
1 | // List implementation (out of line) -*- C++ -*- |
2 | ||
99dee823 | 3 | // Copyright (C) 2001-2021 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) 1996,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/list.tcc |
83144cfc | 52 | * This is an internal header file, included by other library headers. |
f910786b | 53 | * Do not attempt to use it directly. @headername{list} |
83144cfc PE |
54 | */ |
55 | ||
3d7c150e BK |
56 | #ifndef _LIST_TCC |
57 | #define _LIST_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 | |
3971a4d2 PE |
64 | template<typename _Tp, typename _Alloc> |
65 | void | |
6e0a7f2b | 66 | _List_base<_Tp, _Alloc>:: |
837bf511 | 67 | _M_clear() _GLIBCXX_NOEXCEPT |
83144cfc | 68 | { |
3971a4d2 | 69 | typedef _List_node<_Tp> _Node; |
2a527383 | 70 | __detail::_List_node_base* __cur = _M_impl._M_node._M_next; |
0e83f45a | 71 | while (__cur != &_M_impl._M_node) |
6e0a7f2b | 72 | { |
2a527383 MG |
73 | _Node* __tmp = static_cast<_Node*>(__cur); |
74 | __cur = __tmp->_M_next; | |
cc7f3d0e | 75 | _Tp* __val = __tmp->_M_valptr(); |
734f5023 | 76 | #if __cplusplus >= 201103L |
cc7f3d0e | 77 | _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val); |
c841843f | 78 | #else |
cc7f3d0e | 79 | _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val); |
c841843f | 80 | #endif |
6e0a7f2b PC |
81 | _M_put_node(__tmp); |
82 | } | |
e3d51be2 | 83 | } |
ed6814f7 | 84 | |
734f5023 | 85 | #if __cplusplus >= 201103L |
84237dbb PC |
86 | template<typename _Tp, typename _Alloc> |
87 | template<typename... _Args> | |
88 | typename list<_Tp, _Alloc>::iterator | |
89 | list<_Tp, _Alloc>:: | |
7b61c5a9 | 90 | emplace(const_iterator __position, _Args&&... __args) |
84237dbb PC |
91 | { |
92 | _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); | |
7b61c5a9 | 93 | __tmp->_M_hook(__position._M_const_cast()._M_node); |
375f837b | 94 | this->_M_inc_size(1); |
84237dbb PC |
95 | return iterator(__tmp); |
96 | } | |
97 | #endif | |
98 | ||
3971a4d2 | 99 | template<typename _Tp, typename _Alloc> |
6e0a7f2b PC |
100 | typename list<_Tp, _Alloc>::iterator |
101 | list<_Tp, _Alloc>:: | |
7b61c5a9 PC |
102 | #if __cplusplus >= 201103L |
103 | insert(const_iterator __position, const value_type& __x) | |
104 | #else | |
3971a4d2 | 105 | insert(iterator __position, const value_type& __x) |
7b61c5a9 | 106 | #endif |
83144cfc | 107 | { |
3971a4d2 | 108 | _Node* __tmp = _M_create_node(__x); |
7b61c5a9 | 109 | __tmp->_M_hook(__position._M_const_cast()._M_node); |
375f837b | 110 | this->_M_inc_size(1); |
e182017e | 111 | return iterator(__tmp); |
83144cfc | 112 | } |
ed6814f7 | 113 | |
019fdb79 PC |
114 | #if __cplusplus >= 201103L |
115 | template<typename _Tp, typename _Alloc> | |
116 | typename list<_Tp, _Alloc>::iterator | |
117 | list<_Tp, _Alloc>:: | |
118 | insert(const_iterator __position, size_type __n, const value_type& __x) | |
119 | { | |
120 | if (__n) | |
121 | { | |
122 | list __tmp(__n, __x, get_allocator()); | |
123 | iterator __it = __tmp.begin(); | |
124 | splice(__position, __tmp); | |
125 | return __it; | |
126 | } | |
127 | return __position._M_const_cast(); | |
128 | } | |
129 | ||
130 | template<typename _Tp, typename _Alloc> | |
131 | template<typename _InputIterator, typename> | |
132 | typename list<_Tp, _Alloc>::iterator | |
133 | list<_Tp, _Alloc>:: | |
134 | insert(const_iterator __position, _InputIterator __first, | |
135 | _InputIterator __last) | |
136 | { | |
137 | list __tmp(__first, __last, get_allocator()); | |
138 | if (!__tmp.empty()) | |
139 | { | |
140 | iterator __it = __tmp.begin(); | |
141 | splice(__position, __tmp); | |
142 | return __it; | |
143 | } | |
144 | return __position._M_const_cast(); | |
145 | } | |
146 | #endif | |
147 | ||
3971a4d2 | 148 | template<typename _Tp, typename _Alloc> |
6e0a7f2b PC |
149 | typename list<_Tp, _Alloc>::iterator |
150 | list<_Tp, _Alloc>:: | |
94938aec | 151 | #if __cplusplus >= 201103L |
837bf511 | 152 | erase(const_iterator __position) noexcept |
94938aec | 153 | #else |
3971a4d2 | 154 | erase(iterator __position) |
94938aec | 155 | #endif |
83144cfc | 156 | { |
e182017e | 157 | iterator __ret = iterator(__position._M_node->_M_next); |
94938aec | 158 | _M_erase(__position._M_const_cast()); |
e135a038 | 159 | return __ret; |
83144cfc | 160 | } |
ed6814f7 | 161 | |
8e725716 JW |
162 | // Return a const_iterator indicating the position to start inserting or |
163 | // erasing elements (depending whether the list is growing or shrinking), | |
164 | // and set __new_size to the number of new elements that must be appended. | |
165 | // Equivalent to the following, but performed optimally: | |
166 | // if (__new_size < size()) { | |
167 | // __new_size = 0; | |
168 | // return std::next(begin(), __new_size); | |
169 | // } else { | |
170 | // __newsize -= size(); | |
171 | // return end(); | |
172 | // } | |
173 | template<typename _Tp, typename _Alloc> | |
174 | typename list<_Tp, _Alloc>::const_iterator | |
175 | list<_Tp, _Alloc>:: | |
176 | _M_resize_pos(size_type& __new_size) const | |
177 | { | |
178 | const_iterator __i; | |
179 | #if _GLIBCXX_USE_CXX11_ABI | |
180 | const size_type __len = size(); | |
181 | if (__new_size < __len) | |
182 | { | |
183 | if (__new_size <= __len / 2) | |
184 | { | |
185 | __i = begin(); | |
186 | std::advance(__i, __new_size); | |
187 | } | |
188 | else | |
189 | { | |
190 | __i = end(); | |
191 | ptrdiff_t __num_erase = __len - __new_size; | |
192 | std::advance(__i, -__num_erase); | |
193 | } | |
194 | __new_size = 0; | |
195 | return __i; | |
196 | } | |
197 | else | |
198 | __i = end(); | |
199 | #else | |
200 | size_type __len = 0; | |
201 | for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len) | |
202 | ; | |
203 | #endif | |
204 | __new_size -= __len; | |
205 | return __i; | |
206 | } | |
207 | ||
734f5023 | 208 | #if __cplusplus >= 201103L |
dc2cf706 PC |
209 | template<typename _Tp, typename _Alloc> |
210 | void | |
211 | list<_Tp, _Alloc>:: | |
212 | _M_default_append(size_type __n) | |
213 | { | |
214 | size_type __i = 0; | |
215 | __try | |
216 | { | |
217 | for (; __i < __n; ++__i) | |
218 | emplace_back(); | |
219 | } | |
220 | __catch(...) | |
221 | { | |
222 | for (; __i; --__i) | |
223 | pop_back(); | |
224 | __throw_exception_again; | |
225 | } | |
226 | } | |
227 | ||
228 | template<typename _Tp, typename _Alloc> | |
229 | void | |
230 | list<_Tp, _Alloc>:: | |
231 | resize(size_type __new_size) | |
232 | { | |
8e725716 JW |
233 | const_iterator __i = _M_resize_pos(__new_size); |
234 | if (__new_size) | |
235 | _M_default_append(__new_size); | |
236 | else | |
d695f915 | 237 | erase(__i, end()); |
dc2cf706 PC |
238 | } |
239 | ||
240 | template<typename _Tp, typename _Alloc> | |
241 | void | |
242 | list<_Tp, _Alloc>:: | |
243 | resize(size_type __new_size, const value_type& __x) | |
244 | { | |
8e725716 JW |
245 | const_iterator __i = _M_resize_pos(__new_size); |
246 | if (__new_size) | |
247 | insert(end(), __new_size, __x); | |
248 | else | |
d695f915 | 249 | erase(__i, end()); |
dc2cf706 PC |
250 | } |
251 | #else | |
3971a4d2 PE |
252 | template<typename _Tp, typename _Alloc> |
253 | void | |
6e0a7f2b | 254 | list<_Tp, _Alloc>:: |
2fecaef4 | 255 | resize(size_type __new_size, value_type __x) |
83144cfc | 256 | { |
8e725716 JW |
257 | const_iterator __i = _M_resize_pos(__new_size); |
258 | if (__new_size) | |
259 | insert(end(), __new_size, __x); | |
260 | else | |
261 | erase(__i._M_const_cast(), end()); | |
83144cfc | 262 | } |
dc2cf706 | 263 | #endif |
ed6814f7 | 264 | |
3971a4d2 | 265 | template<typename _Tp, typename _Alloc> |
6e0a7f2b PC |
266 | list<_Tp, _Alloc>& |
267 | list<_Tp, _Alloc>:: | |
3971a4d2 | 268 | operator=(const list& __x) |
83144cfc | 269 | { |
200fcd33 | 270 | if (this != std::__addressof(__x)) |
f6592a9e | 271 | { |
cc7f3d0e JW |
272 | #if __cplusplus >= 201103L |
273 | if (_Node_alloc_traits::_S_propagate_on_copy_assign()) | |
274 | { | |
275 | auto& __this_alloc = this->_M_get_Node_allocator(); | |
276 | auto& __that_alloc = __x._M_get_Node_allocator(); | |
277 | if (!_Node_alloc_traits::_S_always_equal() | |
278 | && __this_alloc != __that_alloc) | |
279 | { | |
280 | // replacement allocator cannot free existing storage | |
281 | clear(); | |
282 | } | |
283 | std::__alloc_on_copy(__this_alloc, __that_alloc); | |
284 | } | |
285 | #endif | |
286 | _M_assign_dispatch(__x.begin(), __x.end(), __false_type()); | |
f6592a9e | 287 | } |
3971a4d2 PE |
288 | return *this; |
289 | } | |
ed6814f7 | 290 | |
3971a4d2 PE |
291 | template<typename _Tp, typename _Alloc> |
292 | void | |
6e0a7f2b | 293 | list<_Tp, _Alloc>:: |
3971a4d2 | 294 | _M_fill_assign(size_type __n, const value_type& __val) |
83144cfc | 295 | { |
3971a4d2 | 296 | iterator __i = begin(); |
6e0a7f2b | 297 | for (; __i != end() && __n > 0; ++__i, --__n) |
3971a4d2 PE |
298 | *__i = __val; |
299 | if (__n > 0) | |
300 | insert(end(), __n, __val); | |
301 | else | |
302 | erase(__i, end()); | |
303 | } | |
ed6814f7 | 304 | |
3971a4d2 | 305 | template<typename _Tp, typename _Alloc> |
08addde6 | 306 | template <typename _InputIterator> |
3971a4d2 | 307 | void |
6e0a7f2b | 308 | list<_Tp, _Alloc>:: |
ed6814f7 | 309 | _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, |
4d54539c | 310 | __false_type) |
83144cfc | 311 | { |
3971a4d2 PE |
312 | iterator __first1 = begin(); |
313 | iterator __last1 = end(); | |
ed6814f7 | 314 | for (; __first1 != __last1 && __first2 != __last2; |
27db01d8 | 315 | ++__first1, (void)++__first2) |
3971a4d2 PE |
316 | *__first1 = *__first2; |
317 | if (__first2 == __last2) | |
318 | erase(__first1, __last1); | |
319 | else | |
320 | insert(__last1, __first2, __last2); | |
83144cfc | 321 | } |
ed6814f7 | 322 | |
ef45724a JW |
323 | #if __cplusplus > 201703L |
324 | # define _GLIBCXX20_ONLY(__expr) __expr | |
325 | #else | |
326 | # define _GLIBCXX20_ONLY(__expr) | |
327 | #endif | |
328 | ||
3971a4d2 | 329 | template<typename _Tp, typename _Alloc> |
ef45724a | 330 | typename list<_Tp, _Alloc>::__remove_return_type |
6e0a7f2b | 331 | list<_Tp, _Alloc>:: |
3971a4d2 | 332 | remove(const value_type& __value) |
83144cfc | 333 | { |
8b7af071 | 334 | #if !_GLIBCXX_USE_CXX11_ABI |
ef45724a | 335 | size_type __removed __attribute__((__unused__)) = 0; |
8b7af071 FD |
336 | #endif |
337 | list __to_destroy(get_allocator()); | |
83144cfc PE |
338 | iterator __first = begin(); |
339 | iterator __last = end(); | |
340 | while (__first != __last) | |
6e0a7f2b PC |
341 | { |
342 | iterator __next = __first; | |
343 | ++__next; | |
344 | if (*__first == __value) | |
687e00ee HH |
345 | { |
346 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
347 | // 526. Is it undefined if a function in the standard changes | |
348 | // in parameters? | |
8b7af071 FD |
349 | __to_destroy.splice(__to_destroy.begin(), *this, __first); |
350 | #if !_GLIBCXX_USE_CXX11_ABI | |
351 | _GLIBCXX20_ONLY( __removed++ ); | |
352 | #endif | |
687e00ee | 353 | } |
8b7af071 | 354 | |
6e0a7f2b PC |
355 | __first = __next; |
356 | } | |
8b7af071 FD |
357 | |
358 | #if !_GLIBCXX_USE_CXX11_ABI | |
359 | return _GLIBCXX20_ONLY( __removed ); | |
360 | #else | |
361 | return _GLIBCXX20_ONLY( __to_destroy.size() ); | |
362 | #endif | |
83144cfc | 363 | } |
ed6814f7 | 364 | |
3971a4d2 | 365 | template<typename _Tp, typename _Alloc> |
ef45724a | 366 | typename list<_Tp, _Alloc>::__remove_return_type |
6e0a7f2b | 367 | list<_Tp, _Alloc>:: |
3971a4d2 | 368 | unique() |
83144cfc PE |
369 | { |
370 | iterator __first = begin(); | |
371 | iterator __last = end(); | |
f6592a9e | 372 | if (__first == __last) |
ef45724a | 373 | return _GLIBCXX20_ONLY( 0 ); |
8b7af071 | 374 | #if !_GLIBCXX_USE_CXX11_ABI |
ef45724a | 375 | size_type __removed __attribute__((__unused__)) = 0; |
8b7af071 FD |
376 | #endif |
377 | list __to_destroy(get_allocator()); | |
83144cfc PE |
378 | iterator __next = __first; |
379 | while (++__next != __last) | |
6e0a7f2b PC |
380 | { |
381 | if (*__first == *__next) | |
ef45724a | 382 | { |
8b7af071 FD |
383 | __to_destroy.splice(__to_destroy.begin(), *this, __next); |
384 | #if !_GLIBCXX_USE_CXX11_ABI | |
ef45724a | 385 | _GLIBCXX20_ONLY( __removed++ ); |
8b7af071 | 386 | #endif |
ef45724a | 387 | } |
6e0a7f2b PC |
388 | else |
389 | __first = __next; | |
390 | __next = __first; | |
391 | } | |
8b7af071 FD |
392 | |
393 | #if !_GLIBCXX_USE_CXX11_ABI | |
ef45724a | 394 | return _GLIBCXX20_ONLY( __removed ); |
8b7af071 FD |
395 | #else |
396 | return _GLIBCXX20_ONLY( __to_destroy.size() ); | |
397 | #endif | |
83144cfc | 398 | } |
ed6814f7 | 399 | |
3971a4d2 | 400 | template<typename _Tp, typename _Alloc> |
83144cfc | 401 | void |
6e0a7f2b | 402 | list<_Tp, _Alloc>:: |
734f5023 | 403 | #if __cplusplus >= 201103L |
84237dbb PC |
404 | merge(list&& __x) |
405 | #else | |
3971a4d2 | 406 | merge(list& __x) |
84237dbb | 407 | #endif |
83144cfc | 408 | { |
41d3a0c3 PC |
409 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
410 | // 300. list::merge() specification incomplete | |
200fcd33 | 411 | if (this != std::__addressof(__x)) |
41d3a0c3 | 412 | { |
e5dcfacf | 413 | _M_check_equal_allocators(__x); |
af8590d2 | 414 | |
41d3a0c3 PC |
415 | iterator __first1 = begin(); |
416 | iterator __last1 = end(); | |
417 | iterator __first2 = __x.begin(); | |
418 | iterator __last2 = __x.end(); | |
e5dcfacf VV |
419 | const size_t __orig_size = __x.size(); |
420 | __try { | |
421 | while (__first1 != __last1 && __first2 != __last2) | |
422 | if (*__first2 < *__first1) | |
423 | { | |
424 | iterator __next = __first2; | |
425 | _M_transfer(__first1, __first2, ++__next); | |
426 | __first2 = __next; | |
427 | } | |
428 | else | |
429 | ++__first1; | |
430 | if (__first2 != __last2) | |
431 | _M_transfer(__last1, __first2, __last2); | |
375f837b | 432 | |
e5dcfacf VV |
433 | this->_M_inc_size(__x._M_get_size()); |
434 | __x._M_set_size(0); | |
435 | } | |
436 | __catch(...) | |
437 | { | |
648c9894 | 438 | const size_t __dist = std::distance(__first2, __last2); |
53426b63 VV |
439 | this->_M_inc_size(__orig_size - __dist); |
440 | __x._M_set_size(__dist); | |
e5dcfacf VV |
441 | __throw_exception_again; |
442 | } | |
41d3a0c3 | 443 | } |
83144cfc | 444 | } |
ed6814f7 | 445 | |
af8590d2 PC |
446 | template<typename _Tp, typename _Alloc> |
447 | template <typename _StrictWeakOrdering> | |
448 | void | |
449 | list<_Tp, _Alloc>:: | |
734f5023 | 450 | #if __cplusplus >= 201103L |
84237dbb PC |
451 | merge(list&& __x, _StrictWeakOrdering __comp) |
452 | #else | |
af8590d2 | 453 | merge(list& __x, _StrictWeakOrdering __comp) |
84237dbb | 454 | #endif |
af8590d2 PC |
455 | { |
456 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
457 | // 300. list::merge() specification incomplete | |
200fcd33 | 458 | if (this != std::__addressof(__x)) |
af8590d2 PC |
459 | { |
460 | _M_check_equal_allocators(__x); | |
461 | ||
462 | iterator __first1 = begin(); | |
463 | iterator __last1 = end(); | |
464 | iterator __first2 = __x.begin(); | |
465 | iterator __last2 = __x.end(); | |
e5dcfacf VV |
466 | const size_t __orig_size = __x.size(); |
467 | __try | |
468 | { | |
469 | while (__first1 != __last1 && __first2 != __last2) | |
470 | if (__comp(*__first2, *__first1)) | |
471 | { | |
472 | iterator __next = __first2; | |
473 | _M_transfer(__first1, __first2, ++__next); | |
474 | __first2 = __next; | |
475 | } | |
476 | else | |
477 | ++__first1; | |
478 | if (__first2 != __last2) | |
479 | _M_transfer(__last1, __first2, __last2); | |
480 | ||
481 | this->_M_inc_size(__x._M_get_size()); | |
482 | __x._M_set_size(0); | |
483 | } | |
484 | __catch(...) | |
485 | { | |
648c9894 | 486 | const size_t __dist = std::distance(__first2, __last2); |
53426b63 VV |
487 | this->_M_inc_size(__orig_size - __dist); |
488 | __x._M_set_size(__dist); | |
e5dcfacf VV |
489 | __throw_exception_again; |
490 | } | |
af8590d2 PC |
491 | } |
492 | } | |
493 | ||
3971a4d2 PE |
494 | template<typename _Tp, typename _Alloc> |
495 | void | |
6e0a7f2b | 496 | list<_Tp, _Alloc>:: |
3971a4d2 | 497 | sort() |
83144cfc | 498 | { |
3971a4d2 | 499 | // Do nothing if the list has length 0 or 1. |
03f9ea44 DM |
500 | if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node |
501 | && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) | |
83144cfc | 502 | { |
3971a4d2 | 503 | list __carry; |
e135a038 | 504 | list __tmp[64]; |
200fcd33 | 505 | list * __fill = __tmp; |
e135a038 | 506 | list * __counter; |
e5dcfacf | 507 | __try |
f6592a9e | 508 | { |
e5dcfacf | 509 | do |
f6592a9e | 510 | { |
e5dcfacf VV |
511 | __carry.splice(__carry.begin(), *this, begin()); |
512 | ||
513 | for(__counter = __tmp; | |
514 | __counter != __fill && !__counter->empty(); | |
515 | ++__counter) | |
516 | { | |
517 | __counter->merge(__carry); | |
518 | __carry.swap(*__counter); | |
519 | } | |
f6592a9e | 520 | __carry.swap(*__counter); |
e5dcfacf VV |
521 | if (__counter == __fill) |
522 | ++__fill; | |
f6592a9e | 523 | } |
e5dcfacf | 524 | while ( !empty() ); |
e135a038 | 525 | |
e5dcfacf VV |
526 | for (__counter = __tmp + 1; __counter != __fill; ++__counter) |
527 | __counter->merge(*(__counter - 1)); | |
528 | swap( *(__fill - 1) ); | |
529 | } | |
530 | __catch(...) | |
531 | { | |
532 | this->splice(this->end(), __carry); | |
d34d36ef JW |
533 | for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) |
534 | this->splice(this->end(), __tmp[__i]); | |
e5dcfacf VV |
535 | __throw_exception_again; |
536 | } | |
3971a4d2 PE |
537 | } |
538 | } | |
ed6814f7 | 539 | |
3971a4d2 PE |
540 | template<typename _Tp, typename _Alloc> |
541 | template <typename _Predicate> | |
ef45724a | 542 | typename list<_Tp, _Alloc>::__remove_return_type |
6e0a7f2b | 543 | list<_Tp, _Alloc>:: |
3971a4d2 PE |
544 | remove_if(_Predicate __pred) |
545 | { | |
8b7af071 | 546 | #if !_GLIBCXX_USE_CXX11_ABI |
ef45724a | 547 | size_type __removed __attribute__((__unused__)) = 0; |
8b7af071 FD |
548 | #endif |
549 | list __to_destroy(get_allocator()); | |
550 | iterator __first = begin(); | |
551 | iterator __last = end(); | |
552 | while (__first != __last) | |
6e0a7f2b PC |
553 | { |
554 | iterator __next = __first; | |
555 | ++__next; | |
556 | if (__pred(*__first)) | |
ef45724a | 557 | { |
8b7af071 FD |
558 | __to_destroy.splice(__to_destroy.begin(), *this, __first); |
559 | #if !_GLIBCXX_USE_CXX11_ABI | |
ef45724a | 560 | _GLIBCXX20_ONLY( __removed++ ); |
8b7af071 | 561 | #endif |
ef45724a | 562 | } |
6e0a7f2b PC |
563 | __first = __next; |
564 | } | |
8b7af071 FD |
565 | |
566 | #if !_GLIBCXX_USE_CXX11_ABI | |
ef45724a | 567 | return _GLIBCXX20_ONLY( __removed ); |
8b7af071 FD |
568 | #else |
569 | return _GLIBCXX20_ONLY( __to_destroy.size() ); | |
570 | #endif | |
3971a4d2 | 571 | } |
ed6814f7 | 572 | |
3971a4d2 PE |
573 | template<typename _Tp, typename _Alloc> |
574 | template <typename _BinaryPredicate> | |
ef45724a | 575 | typename list<_Tp, _Alloc>::__remove_return_type |
6e0a7f2b | 576 | list<_Tp, _Alloc>:: |
3971a4d2 PE |
577 | unique(_BinaryPredicate __binary_pred) |
578 | { | |
579 | iterator __first = begin(); | |
580 | iterator __last = end(); | |
6e0a7f2b | 581 | if (__first == __last) |
ef45724a | 582 | return _GLIBCXX20_ONLY(0); |
8b7af071 | 583 | #if !_GLIBCXX_USE_CXX11_ABI |
ef45724a | 584 | size_type __removed __attribute__((__unused__)) = 0; |
8b7af071 FD |
585 | #endif |
586 | list __to_destroy(get_allocator()); | |
3971a4d2 PE |
587 | iterator __next = __first; |
588 | while (++__next != __last) | |
6e0a7f2b PC |
589 | { |
590 | if (__binary_pred(*__first, *__next)) | |
ef45724a | 591 | { |
8b7af071 FD |
592 | __to_destroy.splice(__to_destroy.begin(), *this, __next); |
593 | #if !_GLIBCXX_USE_CXX11_ABI | |
ef45724a | 594 | _GLIBCXX20_ONLY( __removed++ ); |
8b7af071 | 595 | #endif |
ef45724a | 596 | } |
6e0a7f2b PC |
597 | else |
598 | __first = __next; | |
599 | __next = __first; | |
600 | } | |
8b7af071 FD |
601 | |
602 | #if !_GLIBCXX_USE_CXX11_ABI | |
ef45724a | 603 | return _GLIBCXX20_ONLY( __removed ); |
8b7af071 FD |
604 | #else |
605 | return _GLIBCXX20_ONLY( __to_destroy.size() ); | |
606 | #endif | |
3971a4d2 | 607 | } |
ed6814f7 | 608 | |
ef45724a JW |
609 | #undef _GLIBCXX20_ONLY |
610 | ||
3971a4d2 PE |
611 | template<typename _Tp, typename _Alloc> |
612 | template <typename _StrictWeakOrdering> | |
f6592a9e | 613 | void |
6e0a7f2b | 614 | list<_Tp, _Alloc>:: |
f6592a9e | 615 | sort(_StrictWeakOrdering __comp) |
3971a4d2 | 616 | { |
f6592a9e | 617 | // Do nothing if the list has length 0 or 1. |
03f9ea44 DM |
618 | if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node |
619 | && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) | |
f6592a9e PC |
620 | { |
621 | list __carry; | |
622 | list __tmp[64]; | |
200fcd33 | 623 | list * __fill = __tmp; |
f6592a9e | 624 | list * __counter; |
e5dcfacf | 625 | __try |
f6592a9e | 626 | { |
e5dcfacf | 627 | do |
f6592a9e | 628 | { |
e5dcfacf VV |
629 | __carry.splice(__carry.begin(), *this, begin()); |
630 | ||
631 | for(__counter = __tmp; | |
632 | __counter != __fill && !__counter->empty(); | |
633 | ++__counter) | |
634 | { | |
635 | __counter->merge(__carry, __comp); | |
636 | __carry.swap(*__counter); | |
637 | } | |
f6592a9e | 638 | __carry.swap(*__counter); |
e5dcfacf VV |
639 | if (__counter == __fill) |
640 | ++__fill; | |
f6592a9e | 641 | } |
e5dcfacf | 642 | while ( !empty() ); |
ed6814f7 | 643 | |
e5dcfacf VV |
644 | for (__counter = __tmp + 1; __counter != __fill; ++__counter) |
645 | __counter->merge(*(__counter - 1), __comp); | |
646 | swap(*(__fill - 1)); | |
647 | } | |
648 | __catch(...) | |
649 | { | |
650 | this->splice(this->end(), __carry); | |
d34d36ef JW |
651 | for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) |
652 | this->splice(this->end(), __tmp[__i]); | |
e5dcfacf VV |
653 | __throw_exception_again; |
654 | } | |
f6592a9e | 655 | } |
83144cfc | 656 | } |
3cbc7af0 | 657 | |
12ffa228 | 658 | _GLIBCXX_END_NAMESPACE_CONTAINER |
4a15d842 | 659 | _GLIBCXX_END_NAMESPACE_VERSION |
12ffa228 | 660 | } // namespace std |
83144cfc | 661 | |
3d7c150e | 662 | #endif /* _LIST_TCC */ |
e135a038 | 663 |