1 | // List implementation (out of line) -*- C++ -*- |
2 | |
3 | // Copyright (C) 2001-2021 Free Software Foundation, Inc. |
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 |
8 | // Free Software Foundation; either version 3, or (at your option) |
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 | |
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. |
19 | |
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/>. |
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 | |
51 | /** @file bits/list.tcc |
52 | * This is an internal header file, included by other library headers. |
53 | * Do not attempt to use it directly. @headername{list} |
54 | */ |
55 | |
56 | #ifndef _LIST_TCC |
57 | #define _LIST_TCC 1 |
58 | |
59 | namespace std _GLIBCXX_VISIBILITY(default) |
60 | { |
61 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
62 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |
63 | |
64 | template<typename _Tp, typename _Alloc> |
65 | void |
66 | _List_base<_Tp, _Alloc>:: |
67 | _M_clear() _GLIBCXX_NOEXCEPT |
68 | { |
69 | typedef _List_node<_Tp> _Node; |
70 | __detail::_List_node_base* __cur = _M_impl._M_node._M_next; |
71 | while (__cur != &_M_impl._M_node) |
72 | { |
73 | _Node* __tmp = static_cast<_Node*>(__cur); |
74 | __cur = __tmp->_M_next; |
75 | _Tp* __val = __tmp->_M_valptr(); |
76 | #if __cplusplus >= 201103L |
77 | _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val); |
78 | #else |
79 | _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val); |
80 | #endif |
81 | _M_put_node(p: __tmp); |
82 | } |
83 | } |
84 | |
85 | #if __cplusplus >= 201103L |
86 | template<typename _Tp, typename _Alloc> |
87 | template<typename... _Args> |
88 | typename list<_Tp, _Alloc>::iterator |
89 | list<_Tp, _Alloc>:: |
90 | emplace(const_iterator __position, _Args&&... __args) |
91 | { |
92 | _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); |
93 | __tmp->_M_hook(__position._M_const_cast()._M_node); |
94 | this->_M_inc_size(1); |
95 | return iterator(__tmp); |
96 | } |
97 | #endif |
98 | |
99 | template<typename _Tp, typename _Alloc> |
100 | typename list<_Tp, _Alloc>::iterator |
101 | list<_Tp, _Alloc>:: |
102 | #if __cplusplus >= 201103L |
103 | insert(const_iterator __position, const value_type& __x) |
104 | #else |
105 | insert(iterator __position, const value_type& __x) |
106 | #endif |
107 | { |
108 | _Node* __tmp = _M_create_node(__x); |
109 | __tmp->_M_hook(__position._M_const_cast()._M_node); |
110 | this->_M_inc_size(1); |
111 | return iterator(__tmp); |
112 | } |
113 | |
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 | |
148 | template<typename _Tp, typename _Alloc> |
149 | typename list<_Tp, _Alloc>::iterator |
150 | list<_Tp, _Alloc>:: |
151 | #if __cplusplus >= 201103L |
152 | erase(const_iterator __position) noexcept |
153 | #else |
154 | erase(iterator __position) |
155 | #endif |
156 | { |
157 | iterator __ret = iterator(__position._M_node->_M_next); |
158 | _M_erase(position: __position._M_const_cast()); |
159 | return __ret; |
160 | } |
161 | |
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 | |
208 | #if __cplusplus >= 201103L |
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 | { |
233 | const_iterator __i = _M_resize_pos(__new_size); |
234 | if (__new_size) |
235 | _M_default_append(n: __new_size); |
236 | else |
237 | erase(__i, end()); |
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 | { |
245 | const_iterator __i = _M_resize_pos(__new_size); |
246 | if (__new_size) |
247 | insert(end(), __new_size, __x); |
248 | else |
249 | erase(__i, end()); |
250 | } |
251 | #else |
252 | template<typename _Tp, typename _Alloc> |
253 | void |
254 | list<_Tp, _Alloc>:: |
255 | resize(size_type __new_size, value_type __x) |
256 | { |
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()); |
262 | } |
263 | #endif |
264 | |
265 | template<typename _Tp, typename _Alloc> |
266 | list<_Tp, _Alloc>& |
267 | list<_Tp, _Alloc>:: |
268 | operator=(const list& __x) |
269 | { |
270 | if (this != std::__addressof(__x)) |
271 | { |
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()); |
287 | } |
288 | return *this; |
289 | } |
290 | |
291 | template<typename _Tp, typename _Alloc> |
292 | void |
293 | list<_Tp, _Alloc>:: |
294 | _M_fill_assign(size_type __n, const value_type& __val) |
295 | { |
296 | iterator __i = begin(); |
297 | for (; __i != end() && __n > 0; ++__i, --__n) |
298 | *__i = __val; |
299 | if (__n > 0) |
300 | insert(end(), __n, __val); |
301 | else |
302 | erase(__i, end()); |
303 | } |
304 | |
305 | template<typename _Tp, typename _Alloc> |
306 | template <typename _InputIterator> |
307 | void |
308 | list<_Tp, _Alloc>:: |
309 | _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, |
310 | __false_type) |
311 | { |
312 | iterator __first1 = begin(); |
313 | iterator __last1 = end(); |
314 | for (; __first1 != __last1 && __first2 != __last2; |
315 | ++__first1, (void)++__first2) |
316 | *__first1 = *__first2; |
317 | if (__first2 == __last2) |
318 | erase(__first1, __last1); |
319 | else |
320 | insert(__last1, __first2, __last2); |
321 | } |
322 | |
323 | #if __cplusplus > 201703L |
324 | # define _GLIBCXX20_ONLY(__expr) __expr |
325 | #else |
326 | # define _GLIBCXX20_ONLY(__expr) |
327 | #endif |
328 | |
329 | template<typename _Tp, typename _Alloc> |
330 | typename list<_Tp, _Alloc>::__remove_return_type |
331 | list<_Tp, _Alloc>:: |
332 | remove(const value_type& __value) |
333 | { |
334 | #if !_GLIBCXX_USE_CXX11_ABI |
335 | size_type __removed __attribute__((__unused__)) = 0; |
336 | #endif |
337 | list __to_destroy(get_allocator()); |
338 | iterator __first = begin(); |
339 | iterator __last = end(); |
340 | while (__first != __last) |
341 | { |
342 | iterator __next = __first; |
343 | ++__next; |
344 | if (*__first == __value) |
345 | { |
346 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
347 | // 526. Is it undefined if a function in the standard changes |
348 | // in parameters? |
349 | __to_destroy.splice(__to_destroy.begin(), *this, __first); |
350 | #if !_GLIBCXX_USE_CXX11_ABI |
351 | _GLIBCXX20_ONLY( __removed++ ); |
352 | #endif |
353 | } |
354 | |
355 | __first = __next; |
356 | } |
357 | |
358 | #if !_GLIBCXX_USE_CXX11_ABI |
359 | return _GLIBCXX20_ONLY( __removed ); |
360 | #else |
361 | return _GLIBCXX20_ONLY( __to_destroy.size() ); |
362 | #endif |
363 | } |
364 | |
365 | template<typename _Tp, typename _Alloc> |
366 | typename list<_Tp, _Alloc>::__remove_return_type |
367 | list<_Tp, _Alloc>:: |
368 | unique() |
369 | { |
370 | iterator __first = begin(); |
371 | iterator __last = end(); |
372 | if (__first == __last) |
373 | return _GLIBCXX20_ONLY( 0 ); |
374 | #if !_GLIBCXX_USE_CXX11_ABI |
375 | size_type __removed __attribute__((__unused__)) = 0; |
376 | #endif |
377 | list __to_destroy(get_allocator()); |
378 | iterator __next = __first; |
379 | while (++__next != __last) |
380 | { |
381 | if (*__first == *__next) |
382 | { |
383 | __to_destroy.splice(__to_destroy.begin(), *this, __next); |
384 | #if !_GLIBCXX_USE_CXX11_ABI |
385 | _GLIBCXX20_ONLY( __removed++ ); |
386 | #endif |
387 | } |
388 | else |
389 | __first = __next; |
390 | __next = __first; |
391 | } |
392 | |
393 | #if !_GLIBCXX_USE_CXX11_ABI |
394 | return _GLIBCXX20_ONLY( __removed ); |
395 | #else |
396 | return _GLIBCXX20_ONLY( __to_destroy.size() ); |
397 | #endif |
398 | } |
399 | |
400 | template<typename _Tp, typename _Alloc> |
401 | void |
402 | list<_Tp, _Alloc>:: |
403 | #if __cplusplus >= 201103L |
404 | merge(list&& __x) |
405 | #else |
406 | merge(list& __x) |
407 | #endif |
408 | { |
409 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
410 | // 300. list::merge() specification incomplete |
411 | if (this != std::__addressof(__x)) |
412 | { |
413 | _M_check_equal_allocators(__x); |
414 | |
415 | iterator __first1 = begin(); |
416 | iterator __last1 = end(); |
417 | iterator __first2 = __x.begin(); |
418 | iterator __last2 = __x.end(); |
419 | |
420 | const _Finalize_merge __fin(*this, __x, __first2); |
421 | |
422 | while (__first1 != __last1 && __first2 != __last2) |
423 | if (*__first2 < *__first1) |
424 | { |
425 | iterator __next = __first2; |
426 | _M_transfer(position: __first1, first: __first2, last: ++__next); |
427 | __first2 = __next; |
428 | } |
429 | else |
430 | ++__first1; |
431 | if (__first2 != __last2) |
432 | { |
433 | _M_transfer(position: __last1, first: __first2, last: __last2); |
434 | __first2 = __last2; |
435 | } |
436 | } |
437 | } |
438 | |
439 | template<typename _Tp, typename _Alloc> |
440 | template <typename _StrictWeakOrdering> |
441 | void |
442 | list<_Tp, _Alloc>:: |
443 | #if __cplusplus >= 201103L |
444 | merge(list&& __x, _StrictWeakOrdering __comp) |
445 | #else |
446 | merge(list& __x, _StrictWeakOrdering __comp) |
447 | #endif |
448 | { |
449 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
450 | // 300. list::merge() specification incomplete |
451 | if (this != std::__addressof(__x)) |
452 | { |
453 | _M_check_equal_allocators(__x); |
454 | |
455 | iterator __first1 = begin(); |
456 | iterator __last1 = end(); |
457 | iterator __first2 = __x.begin(); |
458 | iterator __last2 = __x.end(); |
459 | |
460 | const _Finalize_merge __fin(*this, __x, __first2); |
461 | |
462 | while (__first1 != __last1 && __first2 != __last2) |
463 | if (__comp(*__first2, *__first1)) |
464 | { |
465 | iterator __next = __first2; |
466 | _M_transfer(position: __first1, first: __first2, last: ++__next); |
467 | __first2 = __next; |
468 | } |
469 | else |
470 | ++__first1; |
471 | if (__first2 != __last2) |
472 | { |
473 | _M_transfer(position: __last1, first: __first2, last: __last2); |
474 | __first2 = __last2; |
475 | } |
476 | } |
477 | } |
478 | |
479 | template<typename _Tp, typename _Alloc> |
480 | void |
481 | list<_Tp, _Alloc>:: |
482 | sort() |
483 | { |
484 | // Do nothing if the list has length 0 or 1. |
485 | if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node |
486 | && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) |
487 | { |
488 | list __carry; |
489 | list __tmp[64]; |
490 | list * __fill = __tmp; |
491 | list * __counter; |
492 | __try |
493 | { |
494 | do |
495 | { |
496 | __carry.splice(__carry.begin(), *this, begin()); |
497 | |
498 | for(__counter = __tmp; |
499 | __counter != __fill && !__counter->empty(); |
500 | ++__counter) |
501 | { |
502 | __counter->merge(__carry); |
503 | __carry.swap(*__counter); |
504 | } |
505 | __carry.swap(*__counter); |
506 | if (__counter == __fill) |
507 | ++__fill; |
508 | } |
509 | while ( !empty() ); |
510 | |
511 | for (__counter = __tmp + 1; __counter != __fill; ++__counter) |
512 | __counter->merge(*(__counter - 1)); |
513 | swap( x&: *(__fill - 1) ); |
514 | } |
515 | __catch(...) |
516 | { |
517 | this->splice(this->end(), __carry); |
518 | for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) |
519 | this->splice(this->end(), __tmp[__i]); |
520 | __throw_exception_again; |
521 | } |
522 | } |
523 | } |
524 | |
525 | template<typename _Tp, typename _Alloc> |
526 | template <typename _Predicate> |
527 | typename list<_Tp, _Alloc>::__remove_return_type |
528 | list<_Tp, _Alloc>:: |
529 | remove_if(_Predicate __pred) |
530 | { |
531 | #if !_GLIBCXX_USE_CXX11_ABI |
532 | size_type __removed __attribute__((__unused__)) = 0; |
533 | #endif |
534 | list __to_destroy(get_allocator()); |
535 | iterator __first = begin(); |
536 | iterator __last = end(); |
537 | while (__first != __last) |
538 | { |
539 | iterator __next = __first; |
540 | ++__next; |
541 | if (__pred(*__first)) |
542 | { |
543 | __to_destroy.splice(__to_destroy.begin(), *this, __first); |
544 | #if !_GLIBCXX_USE_CXX11_ABI |
545 | _GLIBCXX20_ONLY( __removed++ ); |
546 | #endif |
547 | } |
548 | __first = __next; |
549 | } |
550 | |
551 | #if !_GLIBCXX_USE_CXX11_ABI |
552 | return _GLIBCXX20_ONLY( __removed ); |
553 | #else |
554 | return _GLIBCXX20_ONLY( __to_destroy.size() ); |
555 | #endif |
556 | } |
557 | |
558 | template<typename _Tp, typename _Alloc> |
559 | template <typename _BinaryPredicate> |
560 | typename list<_Tp, _Alloc>::__remove_return_type |
561 | list<_Tp, _Alloc>:: |
562 | unique(_BinaryPredicate __binary_pred) |
563 | { |
564 | iterator __first = begin(); |
565 | iterator __last = end(); |
566 | if (__first == __last) |
567 | return _GLIBCXX20_ONLY(0); |
568 | #if !_GLIBCXX_USE_CXX11_ABI |
569 | size_type __removed __attribute__((__unused__)) = 0; |
570 | #endif |
571 | list __to_destroy(get_allocator()); |
572 | iterator __next = __first; |
573 | while (++__next != __last) |
574 | { |
575 | if (__binary_pred(*__first, *__next)) |
576 | { |
577 | __to_destroy.splice(__to_destroy.begin(), *this, __next); |
578 | #if !_GLIBCXX_USE_CXX11_ABI |
579 | _GLIBCXX20_ONLY( __removed++ ); |
580 | #endif |
581 | } |
582 | else |
583 | __first = __next; |
584 | __next = __first; |
585 | } |
586 | |
587 | #if !_GLIBCXX_USE_CXX11_ABI |
588 | return _GLIBCXX20_ONLY( __removed ); |
589 | #else |
590 | return _GLIBCXX20_ONLY( __to_destroy.size() ); |
591 | #endif |
592 | } |
593 | |
594 | #undef _GLIBCXX20_ONLY |
595 | |
596 | template<typename _Tp, typename _Alloc> |
597 | template <typename _StrictWeakOrdering> |
598 | void |
599 | list<_Tp, _Alloc>:: |
600 | sort(_StrictWeakOrdering __comp) |
601 | { |
602 | // Do nothing if the list has length 0 or 1. |
603 | if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node |
604 | && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) |
605 | { |
606 | list __carry; |
607 | list __tmp[64]; |
608 | list * __fill = __tmp; |
609 | list * __counter; |
610 | __try |
611 | { |
612 | do |
613 | { |
614 | __carry.splice(__carry.begin(), *this, begin()); |
615 | |
616 | for(__counter = __tmp; |
617 | __counter != __fill && !__counter->empty(); |
618 | ++__counter) |
619 | { |
620 | __counter->merge(__carry, __comp); |
621 | __carry.swap(*__counter); |
622 | } |
623 | __carry.swap(*__counter); |
624 | if (__counter == __fill) |
625 | ++__fill; |
626 | } |
627 | while ( !empty() ); |
628 | |
629 | for (__counter = __tmp + 1; __counter != __fill; ++__counter) |
630 | __counter->merge(*(__counter - 1), __comp); |
631 | swap(x&: *(__fill - 1)); |
632 | } |
633 | __catch(...) |
634 | { |
635 | this->splice(this->end(), __carry); |
636 | for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) |
637 | this->splice(this->end(), __tmp[__i]); |
638 | __throw_exception_again; |
639 | } |
640 | } |
641 | } |
642 | |
643 | _GLIBCXX_END_NAMESPACE_CONTAINER |
644 | _GLIBCXX_END_NAMESPACE_VERSION |
645 | } // namespace std |
646 | |
647 | #endif /* _LIST_TCC */ |
648 | |
649 | |