29 #ifndef _GLIBCXX_DEBUG_FORWARD_LIST
30 #define _GLIBCXX_DEBUG_FORWARD_LIST 1
32 #pragma GCC system_header
40 #define __glibcxx_check_valid_fl_range(_First,_Last,_Dist) \
41 _GLIBCXX_DEBUG_VERIFY(_First._M_valid_range(_Last, _Dist, false), \
42 _M_message(__gnu_debug::__msg_valid_range) \
43 ._M_iterator(_First, #_First) \
44 ._M_iterator(_Last, #_Last))
50 template<
typename _SafeSequence>
56 {
return *
static_cast<_SafeSequence*
>(
this); }
70 using _Base_const_iterator = __decltype(_M_this()._M_base().
cend());
73 return __it != _M_this()._M_base().cbefore_begin()
74 && __it != _M_this()._M_base().cend(); });
80 template<
typename _SafeSequence>
88 using const_iterator =
typename _SafeSequence::const_iterator;
91 _SafeSequence& __rseq =
static_cast<_SafeSequence&
>(__rhs);
97 const_iterator* __victim =
98 static_cast<const_iterator*
>(__victim_base);
100 if (__victim->base() == __rseq._M_base().cbefore_begin())
103 if (__lhs_iterators == __victim_base)
104 __lhs_iterators = __victim_base->
_M_next;
107 __victim_base->
_M_next = __bbegin_its;
108 __bbegin_its->
_M_prior = __victim_base;
111 __last_bbegin = __victim_base;
112 __bbegin_its = __victim_base;
122 __rhs_iterators->
_M_prior = __last_bbegin;
123 __last_bbegin->
_M_next = __rhs_iterators;
125 __rhs_iterators = __bbegin_its;
129 template<
typename _SafeSequence>
131 _Safe_forward_list<_SafeSequence>::
132 _M_swap_single(_Safe_sequence_base& __other) noexcept
134 std::swap(_M_this()._M_iterators, __other._M_iterators);
135 std::swap(_M_this()._M_const_iterators, __other._M_const_iterators);
138 _Safe_iterator_base* __this_its = _M_this()._M_iterators;
139 _M_swap_aux(__other, __other._M_iterators,
140 _M_this(), _M_this()._M_iterators);
141 _Safe_iterator_base* __this_const_its = _M_this()._M_const_iterators;
142 _M_swap_aux(__other, __other._M_const_iterators,
143 _M_this(), _M_this()._M_const_iterators);
144 _M_swap_aux(_M_this(), __this_its,
145 __other, __other._M_iterators);
146 _M_swap_aux(_M_this(), __this_const_its,
147 __other, __other._M_const_iterators);
152 template<
typename _SafeSequence>
154 _Safe_forward_list<_SafeSequence>::
155 _M_swap(_Safe_sequence_base& __other) noexcept
158 using namespace __gnu_cxx;
159 __mutex *__this_mutex = &_M_this()._M_get_mutex();
160 __mutex *__other_mutex =
161 &
static_cast<_SafeSequence&
>(__other)._M_get_mutex();
162 if (__this_mutex == __other_mutex)
165 _M_swap_single(__other);
170 ? *__this_mutex : *__other_mutex);
172 ? *__other_mutex : *__this_mutex);
173 _M_swap_single(__other);
178 namespace std _GLIBCXX_VISIBILITY(default)
183 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
186 forward_list<_Tp, _Alloc>, _Alloc, __gnu_debug::_Safe_forward_list>,
187 public _GLIBCXX_STD_C::forward_list<_Tp, _Alloc>
189 typedef _GLIBCXX_STD_C::forward_list<_Tp, _Alloc>
_Base;
197 typedef typename _Base::reference reference;
198 typedef typename _Base::const_reference const_reference;
205 typedef typename _Base::size_type size_type;
206 typedef typename _Base::difference_type difference_type;
208 typedef _Tp value_type;
209 typedef typename _Base::allocator_type allocator_type;
210 typedef typename _Base::pointer pointer;
211 typedef typename _Base::const_pointer const_pointer;
222 :
_Base(__list, __al)
226 :
_Safe(std::move(__list._M_safe()), __al),
227 _Base(std::move(__list._M_base()), __al)
231 forward_list(size_type __n,
const allocator_type& __al = allocator_type())
236 const allocator_type& __al = allocator_type())
237 :
_Base(__n, __value, __al)
240 template<
typename _InputIterator,
241 typename = std::_RequireInputIter<_InputIterator>>
242 forward_list(_InputIterator __first, _InputIterator __last,
243 const allocator_type& __al = allocator_type())
244 :
_Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
246 __gnu_debug::__base(__last), __al)
249 forward_list(
const forward_list&) =
default;
251 forward_list(forward_list&&) =
default;
254 const allocator_type& __al = allocator_type())
258 ~forward_list() =
default;
261 operator=(
const forward_list&) =
default;
264 operator=(forward_list&&) =
default;
270 this->_M_invalidate_all();
274 template<
typename _InputIterator,
275 typename = std::_RequireInputIter<_InputIterator>>
277 assign(_InputIterator __first, _InputIterator __last)
280 __glibcxx_check_valid_range2(__first, __last, __dist);
282 if (__dist.
second >= __gnu_debug::__dp_sign)
283 _Base::assign(__gnu_debug::__unsafe(__first),
284 __gnu_debug::__unsafe(__last));
286 _Base::assign(__first, __last);
288 this->_M_invalidate_all();
292 assign(size_type __n,
const _Tp& __val)
294 _Base::assign(__n, __val);
295 this->_M_invalidate_all();
302 this->_M_invalidate_all();
305 using _Base::get_allocator;
310 before_begin() noexcept
311 {
return iterator(_Base::before_begin(),
this); }
314 before_begin()
const noexcept
322 begin()
const noexcept
338 cbefore_begin()
const noexcept
342 cend()
const noexcept
346 using _Base::max_size;
353 __glibcxx_check_nonempty();
354 return _Base::front();
360 __glibcxx_check_nonempty();
361 return _Base::front();
366 using _Base::emplace_front;
367 using _Base::push_front;
372 __glibcxx_check_nonempty();
374 {
return __it == this->_M_base().cbegin(); });
378 template<
typename... _Args>
384 std::forward<_Args>(__args)...),
392 return iterator(_Base::insert_after(__pos.
base(), __val),
this);
399 return iterator(_Base::insert_after(__pos.
base(), std::move(__val)),
404 insert_after(
const_iterator __pos, size_type __n,
const _Tp& __val)
407 return iterator(_Base::insert_after(__pos.
base(), __n, __val),
411 template<
typename _InputIterator,
412 typename = std::_RequireInputIter<_InputIterator>>
415 _InputIterator __first, _InputIterator __last)
420 if (__dist.
second >= __gnu_debug::__dp_sign)
423 _Base::insert_after(__pos.
base(),
424 __gnu_debug::__unsafe(__first),
425 __gnu_debug::__unsafe(__last)),
429 return { _Base::insert_after(__pos.
base(), __first, __last),
this };
436 return iterator(_Base::insert_after(__pos.
base(), __il),
this);
445 {
return __it == __next; });
446 return _Base::erase_after(__pos);
461 __victim != __last.
base(); ++__victim)
463 _GLIBCXX_DEBUG_VERIFY(__victim !=
_Base::end(),
464 _M_message(__gnu_debug::__msg_valid_range2)
465 ._M_sequence(*
this,
"this")
466 ._M_iterator(__pos,
"pos")
467 ._M_iterator(__last,
"last"));
469 {
return __it == __victim; });
475 swap(forward_list& __list)
476 noexcept( noexcept(declval<_Base&>().swap(__list)) )
478 _Safe::_M_swap(__list);
483 resize(size_type __sz)
485 this->_M_detach_singular();
490 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
493 for (; __victim != __end; ++__victim)
496 {
return __it == __victim; });
505 this->_M_revalidate_singular();
506 __throw_exception_again;
511 resize(size_type __sz,
const value_type& __val)
513 this->_M_detach_singular();
518 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
521 for (; __victim != __end; ++__victim)
524 {
return __it == __victim; });
529 _Base::resize(__sz, __val);
533 this->_M_revalidate_singular();
534 __throw_exception_again;
542 this->_M_invalidate_all();
551 _M_message(__gnu_debug::__msg_self_splice)
552 ._M_sequence(*
this,
"this"));
553 _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(),
554 _M_message(__gnu_debug::__msg_splice_alloc)
556 ._M_sequence(__list,
"__list"));
559 return __it != __list._M_base().cbefore_begin()
560 && __it != __list._M_base().end();
562 _Base::splice_after(__pos.
base(), std::move(__list._M_base()));
567 { splice_after(__pos, std::move(__list)); }
575 _M_message(__gnu_debug::__msg_splice_bad)
576 ._M_iterator(__i,
"__i"));
578 _M_message(__gnu_debug::__msg_splice_other)
579 ._M_iterator(__i,
"__i")
580 ._M_sequence(__list,
"__list"));
581 _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(),
582 _M_message(__gnu_debug::__msg_splice_alloc)
584 ._M_sequence(__list,
"__list"));
590 {
return __it == __next; });
591 _Base::splice_after(__pos.
base(), std::move(__list._M_base()),
598 { splice_after(__pos, std::move(__list), __i); }
607 __glibcxx_check_valid_fl_range(__before, __last, __dist);
609 _M_message(__gnu_debug::__msg_splice_other)
610 ._M_sequence(__list,
"list")
611 ._M_iterator(__before,
"before"));
614 _M_message(__gnu_debug::__msg_valid_range2)
615 ._M_sequence(__list,
"list")
616 ._M_iterator(__before,
"before")
617 ._M_iterator(__last,
"last"));
618 _GLIBCXX_DEBUG_VERIFY(__before != __last,
619 _M_message(__gnu_debug::__msg_valid_range2)
620 ._M_sequence(__list,
"list")
621 ._M_iterator(__before,
"before")
622 ._M_iterator(__last,
"last"));
623 _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(),
624 _M_message(__gnu_debug::__msg_splice_alloc)
626 ._M_sequence(__list,
"__list"));
629 __tmp != __last.
base(); ++__tmp)
631 _GLIBCXX_DEBUG_VERIFY(__tmp != __list._M_base().end(),
632 _M_message(__gnu_debug::__msg_valid_range2)
634 ._M_iterator(__before,
"before")
635 ._M_iterator(__last,
"last"));
636 _GLIBCXX_DEBUG_VERIFY(__listptr !=
this || __tmp != __pos.
base(),
637 _M_message(__gnu_debug::__msg_splice_overlap)
638 ._M_iterator(__tmp,
"position")
639 ._M_iterator(__before,
"before")
640 ._M_iterator(__last,
"last"));
644 {
return __it == __tmp; });
647 _Base::splice_after(__pos.
base(), std::move(__list._M_base()),
654 { splice_after(__pos, std::move(__list), __before, __last); }
657 remove(
const _Tp& __val)
664 __x = _M_erase_after(__old);
670 template<
typename _Pred>
672 remove_if(_Pred __pred)
679 __x = _M_erase_after(__old);
690 if (__first == __last)
693 while (__next != __last)
695 if (*__first == *__next)
696 __next = _M_erase_after(__first);
702 template<
typename _BinPred>
704 unique(_BinPred __binary_pred)
708 if (__first == __last)
711 while (__next != __last)
713 if (__binary_pred(*__first, *__next))
714 __next = _M_erase_after(__first);
721 merge(forward_list&& __list)
726 __glibcxx_check_sorted(__list._M_base().begin(),
727 __list._M_base().end());
730 return __it != __list._M_base().cbefore_begin()
731 && __it != __list._M_base().cend();
733 _Base::merge(std::move(__list._M_base()));
738 merge(forward_list& __list)
739 { merge(std::move(__list)); }
741 template<
typename _Comp>
743 merge(forward_list&& __list, _Comp __comp)
749 __list._M_base().end(), __comp);
750 this->_M_transfer_from_if(__list,
753 return __it != __list._M_base().cbefore_begin()
754 && __it != __list._M_base().cend();
756 _Base::merge(std::move(__list._M_base()), __comp);
760 template<
typename _Comp>
762 merge(forward_list& __list, _Comp __comp)
763 { merge(std::move(__list), __comp); }
766 using _Base::reverse;
769 _M_base() noexcept {
return *
this; }
772 _M_base()
const noexcept {
return *
this; }
775 template<
typename _Tp,
typename _Alloc>
779 {
return __lx._M_base() == __ly._M_base(); }
781 template<
typename _Tp,
typename _Alloc>
783 operator<(const forward_list<_Tp, _Alloc>& __lx,
785 {
return __lx._M_base() < __ly._M_base(); }
787 template<
typename _Tp,
typename _Alloc>
791 {
return !(__lx == __ly); }
794 template<
typename _Tp,
typename _Alloc>
798 {
return (__ly < __lx); }
801 template<
typename _Tp,
typename _Alloc>
805 {
return !(__lx < __ly); }
808 template<
typename _Tp,
typename _Alloc>
810 operator<=(const forward_list<_Tp, _Alloc>& __lx,
812 {
return !(__ly < __lx); }
815 template<
typename _Tp,
typename _Alloc>
818 noexcept(noexcept(__lx.swap(__ly)))
824 namespace __gnu_debug
826 template<
typename _Tp,
typename _Alloc>
827 struct _BeforeBeginHelper<std::__debug::forward_list<_Tp, _Alloc> >
831 template<
typename _Iterator>
833 _S_Is(
const _Safe_iterator<_Iterator, _Sequence>& __it)
836 __it.base() == __it._M_get_sequence()->_M_base().before_begin();
839 template<
typename _Iterator>
841 _S_Is_Beginnest(
const _Safe_iterator<_Iterator, _Sequence>& __it)
842 {
return _S_Is(__it); }
845 template<
typename _Tp,
typename _Alloc>
846 struct _Sequence_traits<std::__debug::forward_list<_Tp, _Alloc> >
850 static typename _Distance_traits<_It>::__type
858 #ifndef _GLIBCXX_DEBUG_PEDANTIC
859 template<
class _Tp,
class _Alloc>
860 struct _Insert_range_from_self_is_safe<
861 std::__debug::forward_list<_Tp, _Alloc> >
862 {
enum { __value = 1 }; };
#define __glibcxx_check_sorted_pred(_First, _Last, _Pred)
bool _M_dereferenceable() const
Is the iterator dereferenceable?
Special iterators swap and invalidation for forward_list because of the before_begin iterator...
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
_Iterator & base() noexcept
Return the underlying iterator.
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
#define __glibcxx_check_insert_range_after(_Position, _First, _Last, _Dist)
Safe class dealing with some allocator dependent operations.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
Basic functionality for a safe iterator.
Base class that supports tracking of iterators that reference a sequence.
#define __glibcxx_check_erase_after(_Position)
void swap(forward_list &__list) noexcept
Swaps data with another forward_list.
void _M_invalidate_if(_Predicate __pred)
#define __glibcxx_check_insert_after(_Position)
bool _M_is_before_begin() const
Is this iterator equal to the sequence's before_begin() iterator if any?
bool _M_before_dereferenceable() const
Is the iterator before a dereferenceable one?
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
_T2 second
first is a copy of the first object
bool _M_attached_to(const _Safe_sequence_base *__seq) const
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
_Safe_iterator_base * _M_next
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
Class std::forward_list with safety/checking/debug instrumentation.
Struct holding two objects of arbitrary type.
Base class for constructing a safe sequence type that tracks iterators that reference it...
_Safe_sequence_base * _M_sequence
_Safe_iterator_base * _M_prior
#define __glibcxx_check_erase_range_after(_First, _Last)