1 // List implementation (out of line) -*- C++ -*-
3 // Copyright (C) 2001-2024 Free Software Foundation, Inc.
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)
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.
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.
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/>.
28 * Hewlett-Packard Company
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.
39 * Copyright (c) 1996,1997
40 * Silicon Graphics Computer Systems, Inc.
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.
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}
59 namespace std _GLIBCXX_VISIBILITY(default)
61 _GLIBCXX_BEGIN_NAMESPACE_VERSION
62 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
64 template<typename _Tp, typename _Alloc>
66 _List_base<_Tp, _Alloc>::
67 _M_clear() _GLIBCXX_NOEXCEPT
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)
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);
79 _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val);
85 #if __cplusplus >= 201103L
86 template<typename _Tp, typename _Alloc>
87 template<typename... _Args>
88 typename list<_Tp, _Alloc>::iterator
90 emplace(const_iterator __position, _Args&&... __args)
92 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
93 __tmp->_M_hook(__position._M_const_cast()._M_node);
95 return iterator(__tmp);
99 template<typename _Tp, typename _Alloc>
100 typename list<_Tp, _Alloc>::iterator
102 #if __cplusplus >= 201103L
103 insert(const_iterator __position, const value_type& __x)
105 insert(iterator __position, const value_type& __x)
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);
114 #if __cplusplus >= 201103L
115 template<typename _Tp, typename _Alloc>
116 typename list<_Tp, _Alloc>::iterator
118 insert(const_iterator __position, size_type __n, const value_type& __x)
122 list __tmp(__n, __x, get_allocator());
123 iterator __it = __tmp.begin();
124 splice(__position, __tmp);
127 return __position._M_const_cast();
130 template<typename _Tp, typename _Alloc>
131 template<typename _InputIterator, typename>
132 typename list<_Tp, _Alloc>::iterator
134 insert(const_iterator __position, _InputIterator __first,
135 _InputIterator __last)
137 list __tmp(__first, __last, get_allocator());
140 iterator __it = __tmp.begin();
141 splice(__position, __tmp);
144 return __position._M_const_cast();
148 template<typename _Tp, typename _Alloc>
149 typename list<_Tp, _Alloc>::iterator
151 #if __cplusplus >= 201103L
152 erase(const_iterator __position) noexcept
154 erase(iterator __position)
157 iterator __ret = iterator(__position._M_node->_M_next);
158 _M_erase(__position._M_const_cast());
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()) {
168 // return std::next(begin(), __new_size);
170 // __newsize -= size();
173 template<typename _Tp, typename _Alloc>
174 typename list<_Tp, _Alloc>::const_iterator
176 _M_resize_pos(size_type& __new_size) const
179 #if _GLIBCXX_USE_CXX11_ABI
180 const size_type __len = size();
181 if (__new_size < __len)
183 if (__new_size <= __len / 2)
186 std::advance(__i, __new_size);
191 ptrdiff_t __num_erase = __len - __new_size;
192 std::advance(__i, -__num_erase);
201 for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len)
208 #if __cplusplus >= 201103L
209 template<typename _Tp, typename _Alloc>
212 _M_default_append(size_type __n)
217 for (; __i < __n; ++__i)
224 __throw_exception_again;
228 template<typename _Tp, typename _Alloc>
231 resize(size_type __new_size)
233 const_iterator __i = _M_resize_pos(__new_size);
235 _M_default_append(__new_size);
240 template<typename _Tp, typename _Alloc>
243 resize(size_type __new_size, const value_type& __x)
245 const_iterator __i = _M_resize_pos(__new_size);
247 insert(end(), __new_size, __x);
252 template<typename _Tp, typename _Alloc>
255 resize(size_type __new_size, value_type __x)
257 const_iterator __i = _M_resize_pos(__new_size);
259 insert(end(), __new_size, __x);
261 erase(__i._M_const_cast(), end());
265 template<typename _Tp, typename _Alloc>
268 operator=(const list& __x)
270 if (this != std::__addressof(__x))
272 #if __cplusplus >= 201103L
273 if (_Node_alloc_traits::_S_propagate_on_copy_assign())
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)
280 // replacement allocator cannot free existing storage
283 std::__alloc_on_copy(__this_alloc, __that_alloc);
286 _M_assign_dispatch(__x.begin(), __x.end(), __false_type());
291 template<typename _Tp, typename _Alloc>
294 _M_fill_assign(size_type __n, const value_type& __val)
296 iterator __i = begin();
297 for (; __i != end() && __n > 0; ++__i, --__n)
300 insert(end(), __n, __val);
305 template<typename _Tp, typename _Alloc>
306 template <typename _InputIterator>
309 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
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);
320 insert(__last1, __first2, __last2);
323 #if __cplusplus > 201703L
324 # define _GLIBCXX20_ONLY(__expr) __expr
326 # define _GLIBCXX20_ONLY(__expr)
329 template<typename _Tp, typename _Alloc>
330 typename list<_Tp, _Alloc>::__remove_return_type
332 remove(const value_type& __value)
334 #if !_GLIBCXX_USE_CXX11_ABI
335 size_type __removed __attribute__((__unused__)) = 0;
337 list __to_destroy(get_allocator());
338 iterator __first = begin();
339 iterator __last = end();
340 while (__first != __last)
342 iterator __next = __first;
344 if (*__first == __value)
346 // _GLIBCXX_RESOLVE_LIB_DEFECTS
347 // 526. Is it undefined if a function in the standard changes
349 __to_destroy.splice(__to_destroy.begin(), *this, __first);
350 #if !_GLIBCXX_USE_CXX11_ABI
351 _GLIBCXX20_ONLY( __removed++ );
358 #if !_GLIBCXX_USE_CXX11_ABI
359 return _GLIBCXX20_ONLY( __removed );
361 return _GLIBCXX20_ONLY( __to_destroy.size() );
365 template<typename _Tp, typename _Alloc>
366 typename list<_Tp, _Alloc>::__remove_return_type
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;
377 list __to_destroy(get_allocator());
378 iterator __next = __first;
379 while (++__next != __last)
381 if (*__first == *__next)
383 __to_destroy.splice(__to_destroy.begin(), *this, __next);
384 #if !_GLIBCXX_USE_CXX11_ABI
385 _GLIBCXX20_ONLY( __removed++ );
393 #if !_GLIBCXX_USE_CXX11_ABI
394 return _GLIBCXX20_ONLY( __removed );
396 return _GLIBCXX20_ONLY( __to_destroy.size() );
400 template<typename _Tp, typename _Alloc>
403 #if __cplusplus >= 201103L
409 // _GLIBCXX_RESOLVE_LIB_DEFECTS
410 // 300. list::merge() specification incomplete
411 if (this != std::__addressof(__x))
413 _M_check_equal_allocators(__x);
415 iterator __first1 = begin();
416 iterator __last1 = end();
417 iterator __first2 = __x.begin();
418 iterator __last2 = __x.end();
420 const _Finalize_merge __fin(*this, __x, __first2);
422 while (__first1 != __last1 && __first2 != __last2)
423 if (*__first2 < *__first1)
425 iterator __next = __first2;
426 _M_transfer(__first1, __first2, ++__next);
431 if (__first2 != __last2)
433 _M_transfer(__last1, __first2, __last2);
439 template<typename _Tp, typename _Alloc>
440 template <typename _StrictWeakOrdering>
443 #if __cplusplus >= 201103L
444 merge(list&& __x, _StrictWeakOrdering __comp)
446 merge(list& __x, _StrictWeakOrdering __comp)
449 // _GLIBCXX_RESOLVE_LIB_DEFECTS
450 // 300. list::merge() specification incomplete
451 if (this != std::__addressof(__x))
453 _M_check_equal_allocators(__x);
455 iterator __first1 = begin();
456 iterator __last1 = end();
457 iterator __first2 = __x.begin();
458 iterator __last2 = __x.end();
460 const _Finalize_merge __fin(*this, __x, __first2);
462 while (__first1 != __last1 && __first2 != __last2)
463 if (__comp(*__first2, *__first1))
465 iterator __next = __first2;
466 _M_transfer(__first1, __first2, ++__next);
471 if (__first2 != __last2)
473 _M_transfer(__last1, __first2, __last2);
479 template<typename _Tp, typename _Alloc>
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)
488 using __detail::_Scratch_list;
489 // The algorithm used here is largely unchanged from the SGI STL
490 // and is described in The C++ Standard Template Library by Plauger,
491 // Stepanov, Lee, Musser.
492 // Each element of *this is spliced out and merged into one of the
493 // sorted lists in __tmp, then all the lists in __tmp are merged
494 // together and then swapped back into *this.
495 // Because all nodes end up back in *this we do not need to update
496 // this->size() while nodes are temporarily moved out.
497 _Scratch_list __carry;
498 _Scratch_list __tmp[64];
499 _Scratch_list* __fill = __tmp;
500 _Scratch_list* __counter;
502 _Scratch_list::_Ptr_cmp<iterator, void> __ptr_comp;
508 __carry._M_take_one(begin()._M_node);
510 for(__counter = __tmp;
511 __counter != __fill && !__counter->empty();
515 __counter->merge(__carry, __ptr_comp);
516 __carry.swap(*__counter);
518 __carry.swap(*__counter);
519 if (__counter == __fill)
524 for (__counter = __tmp + 1; __counter != __fill; ++__counter)
525 __counter->merge(__counter[-1], __ptr_comp);
526 __fill[-1].swap(this->_M_impl._M_node);
530 // Move all nodes back into *this.
531 __carry._M_put_all(end()._M_node);
532 for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
533 __tmp[__i]._M_put_all(end()._M_node);
534 __throw_exception_again;
539 template<typename _Tp, typename _Alloc>
540 template <typename _Predicate>
541 typename list<_Tp, _Alloc>::__remove_return_type
543 remove_if(_Predicate __pred)
545 #if !_GLIBCXX_USE_CXX11_ABI
546 size_type __removed __attribute__((__unused__)) = 0;
548 list __to_destroy(get_allocator());
549 iterator __first = begin();
550 iterator __last = end();
551 while (__first != __last)
553 iterator __next = __first;
555 if (__pred(*__first))
557 __to_destroy.splice(__to_destroy.begin(), *this, __first);
558 #if !_GLIBCXX_USE_CXX11_ABI
559 _GLIBCXX20_ONLY( __removed++ );
565 #if !_GLIBCXX_USE_CXX11_ABI
566 return _GLIBCXX20_ONLY( __removed );
568 return _GLIBCXX20_ONLY( __to_destroy.size() );
572 template<typename _Tp, typename _Alloc>
573 template <typename _BinaryPredicate>
574 typename list<_Tp, _Alloc>::__remove_return_type
576 unique(_BinaryPredicate __binary_pred)
578 iterator __first = begin();
579 iterator __last = end();
580 if (__first == __last)
581 return _GLIBCXX20_ONLY(0);
582 #if !_GLIBCXX_USE_CXX11_ABI
583 size_type __removed __attribute__((__unused__)) = 0;
585 list __to_destroy(get_allocator());
586 iterator __next = __first;
587 while (++__next != __last)
589 if (__binary_pred(*__first, *__next))
591 __to_destroy.splice(__to_destroy.begin(), *this, __next);
592 #if !_GLIBCXX_USE_CXX11_ABI
593 _GLIBCXX20_ONLY( __removed++ );
601 #if !_GLIBCXX_USE_CXX11_ABI
602 return _GLIBCXX20_ONLY( __removed );
604 return _GLIBCXX20_ONLY( __to_destroy.size() );
608 #undef _GLIBCXX20_ONLY
610 template<typename _Tp, typename _Alloc>
611 template <typename _StrictWeakOrdering>
614 sort(_StrictWeakOrdering __comp)
616 // Do nothing if the list has length 0 or 1.
617 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
618 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
620 using __detail::_Scratch_list;
621 _Scratch_list __carry;
622 _Scratch_list __tmp[64];
623 _Scratch_list* __fill = __tmp;
624 _Scratch_list* __counter;
626 _Scratch_list::_Ptr_cmp<iterator, _StrictWeakOrdering> __ptr_comp
633 __carry._M_take_one(begin()._M_node);
635 for(__counter = __tmp;
636 __counter != __fill && !__counter->empty();
640 __counter->merge(__carry, __ptr_comp);
641 __carry.swap(*__counter);
643 __carry.swap(*__counter);
644 if (__counter == __fill)
649 for (__counter = __tmp + 1; __counter != __fill; ++__counter)
650 __counter->merge(__counter[-1], __ptr_comp);
651 __fill[-1].swap(this->_M_impl._M_node);
655 // Move all nodes back into *this.
656 __carry._M_put_all(end()._M_node);
657 for (size_t __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
658 __tmp[__i]._M_put_all(end()._M_node);
659 __throw_exception_again;
664 _GLIBCXX_END_NAMESPACE_CONTAINER
665 _GLIBCXX_END_NAMESPACE_VERSION
668 #endif /* _LIST_TCC */