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