29 #ifndef _GLIBCXX_DEBUG_FORWARD_LIST 30 #define _GLIBCXX_DEBUG_FORWARD_LIST 1 32 #pragma GCC system_header 43 template<
typename _SafeSequence>
49 {
return *
static_cast<_SafeSequence*
>(
this); }
63 using _Base_const_iterator = __decltype(_M_this()._M_base().
cend());
66 return __it != _M_this()._M_base().cbefore_begin()
67 && __it != _M_this()._M_base().cend(); });
73 template<
typename _SafeSequence>
81 using const_iterator =
typename _SafeSequence::const_iterator;
84 _SafeSequence& __rseq =
static_cast<_SafeSequence&
>(__rhs);
90 const_iterator* __victim =
91 static_cast<const_iterator*
>(__victim_base);
93 if (__victim->base() == __rseq._M_base().cbefore_begin())
96 if (__lhs_iterators == __victim_base)
97 __lhs_iterators = __victim_base->
_M_next;
100 __victim_base->
_M_next = __bbegin_its;
101 __bbegin_its->
_M_prior = __victim_base;
104 __last_bbegin = __victim_base;
105 __bbegin_its = __victim_base;
115 __rhs_iterators->
_M_prior = __last_bbegin;
116 __last_bbegin->
_M_next = __rhs_iterators;
118 __rhs_iterators = __bbegin_its;
122 template<
typename _SafeSequence>
137 _M_swap_aux(_M_this(), __this_its,
139 _M_swap_aux(_M_this(), __this_const_its,
145 template<
typename _SafeSequence>
152 __mutex *__this_mutex = &_M_this()._M_get_mutex();
153 __mutex *__other_mutex =
155 if (__this_mutex == __other_mutex)
158 _M_swap_single(__other);
163 ? *__this_mutex : *__other_mutex);
165 ? *__other_mutex : *__this_mutex);
166 _M_swap_single(__other);
171 namespace std _GLIBCXX_VISIBILITY(default)
176 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
179 forward_list<_Tp, _Alloc>, _Alloc, __gnu_debug::_Safe_forward_list>,
180 public _GLIBCXX_STD_C::forward_list<_Tp, _Alloc>
182 typedef _GLIBCXX_STD_C::forward_list<_Tp, _Alloc>
_Base;
190 typedef typename _Base::reference reference;
191 typedef typename _Base::const_reference const_reference;
194 _Base_iterator, forward_list>
iterator;
198 typedef typename _Base::size_type size_type;
199 typedef typename _Base::difference_type difference_type;
201 typedef _Tp value_type;
202 typedef typename _Base::allocator_type allocator_type;
203 typedef typename _Base::pointer pointer;
204 typedef typename _Base::const_pointer const_pointer;
208 forward_list(
const allocator_type& __al = allocator_type())
211 forward_list(
const forward_list& __list,
const allocator_type& __al)
212 : _Base(__list, __al)
215 forward_list(forward_list&& __list,
const allocator_type& __al)
216 : _Safe(std::move(__list._M_safe()), __al),
217 _Base(std::move(__list._M_base()), __al)
221 forward_list(size_type __n,
const allocator_type& __al = allocator_type())
225 forward_list(size_type __n,
const _Tp& __value,
226 const allocator_type& __al = allocator_type())
227 : _Base(__n, __value, __al)
230 template<
typename _InputIterator,
231 typename = std::_RequireInputIter<_InputIterator>>
232 forward_list(_InputIterator __first, _InputIterator __last,
233 const allocator_type& __al = allocator_type())
239 forward_list(
const forward_list&) =
default;
241 forward_list(forward_list&&) =
default;
244 const allocator_type& __al = allocator_type())
248 ~forward_list() =
default;
251 operator=(
const forward_list&) =
default;
254 operator=(forward_list&&) =
default;
260 this->_M_invalidate_all();
264 template<
typename _InputIterator,
265 typename = std::_RequireInputIter<_InputIterator>>
267 assign(_InputIterator __first, _InputIterator __last)
269 __glibcxx_check_valid_range(__first, __last);
272 this->_M_invalidate_all();
276 assign(size_type __n,
const _Tp& __val)
278 _Base::assign(__n, __val);
279 this->_M_invalidate_all();
286 this->_M_invalidate_all();
289 using _Base::get_allocator;
294 before_begin() noexcept
295 {
return iterator(_Base::before_begin(),
this); }
298 before_begin()
const noexcept
299 {
return const_iterator(_Base::before_begin(),
this); }
306 begin()
const noexcept
315 {
return const_iterator(
_Base::end(),
this); }
322 cbefore_begin()
const noexcept
323 {
return const_iterator(_Base::cbefore_begin(),
this); }
326 cend()
const noexcept
330 using _Base::max_size;
337 __glibcxx_check_nonempty();
338 return _Base::front();
344 __glibcxx_check_nonempty();
345 return _Base::front();
350 using _Base::emplace_front;
351 using _Base::push_front;
356 __glibcxx_check_nonempty();
358 {
return __it == this->_M_base().cbegin(); });
362 template<
typename... _Args>
364 emplace_after(const_iterator __pos, _Args&&... __args)
367 return iterator(_Base::emplace_after(__pos.
base(),
368 std::forward<_Args>(__args)...),
373 insert_after(const_iterator __pos,
const _Tp& __val)
376 return iterator(_Base::insert_after(__pos.
base(), __val),
this);
380 insert_after(const_iterator __pos, _Tp&& __val)
383 return iterator(_Base::insert_after(__pos.
base(), std::move(__val)),
388 insert_after(const_iterator __pos, size_type __n,
const _Tp& __val)
391 return iterator(_Base::insert_after(__pos.
base(), __n, __val),
395 template<
typename _InputIterator,
396 typename = std::_RequireInputIter<_InputIterator>>
398 insert_after(const_iterator __pos,
399 _InputIterator __first, _InputIterator __last)
402 return iterator(_Base::insert_after(__pos.
base(),
412 return iterator(_Base::insert_after(__pos.
base(), __il),
this);
417 _M_erase_after(_Base_const_iterator __pos)
419 _Base_const_iterator __next = std::next(__pos);
421 {
return __it == __next; });
422 return _Base::erase_after(__pos);
426 erase_after(const_iterator __pos)
429 return iterator(_M_erase_after(__pos.
base()),
this);
433 erase_after(const_iterator __pos, const_iterator __last)
436 for (_Base_const_iterator __victim = std::next(__pos.
base());
437 __victim != __last.
base(); ++__victim)
439 _GLIBCXX_DEBUG_VERIFY(__victim !=
_Base::end(),
440 _M_message(__gnu_debug::__msg_valid_range2)
441 ._M_sequence(*
this,
"this")
442 ._M_iterator(__pos,
"pos")
443 ._M_iterator(__last,
"last"));
445 {
return __it == __victim; });
447 return iterator(_Base::erase_after(__pos.
base(), __last.
base()),
this);
451 swap(forward_list& __list)
452 noexcept( noexcept(declval<_Base>().swap(__list)) )
454 _Safe::_M_swap(__list);
459 resize(size_type __sz)
466 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
469 for (; __victim != __end; ++__victim)
472 {
return __it == __victim; });
482 __throw_exception_again;
487 resize(size_type __sz,
const value_type& __val)
494 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
497 for (; __victim != __end; ++__victim)
500 {
return __it == __victim; });
505 _Base::resize(__sz, __val);
510 __throw_exception_again;
518 this->_M_invalidate_all();
523 splice_after(const_iterator __pos, forward_list&& __list)
526 _GLIBCXX_DEBUG_VERIFY(&__list !=
this,
527 _M_message(__gnu_debug::__msg_self_splice)
528 ._M_sequence(*
this,
"this"));
529 _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(),
530 _M_message(__gnu_debug::__msg_splice_alloc)
532 ._M_sequence(__list,
"__list"));
535 return __it != __list._M_base().cbefore_begin()
536 && __it != __list._M_base().end();
538 _Base::splice_after(__pos.
base(), std::move(__list._M_base()));
542 splice_after(const_iterator __pos, forward_list& __list)
543 { splice_after(__pos, std::move(__list)); }
546 splice_after(const_iterator __pos, forward_list&& __list,
551 _M_message(__gnu_debug::__msg_splice_bad)
552 ._M_iterator(__i,
"__i"));
554 _M_message(__gnu_debug::__msg_splice_other)
555 ._M_iterator(__i,
"__i")
556 ._M_sequence(__list,
"__list"));
557 _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(),
558 _M_message(__gnu_debug::__msg_splice_alloc)
560 ._M_sequence(__list,
"__list"));
564 _Base_const_iterator __next = std::next(__i.
base());
566 {
return __it == __next; });
567 _Base::splice_after(__pos.
base(), std::move(__list._M_base()),
572 splice_after(const_iterator __pos, forward_list& __list,
574 { splice_after(__pos, std::move(__list), __i); }
577 splice_after(const_iterator __pos, forward_list&& __list,
578 const_iterator __before, const_iterator __last)
581 __glibcxx_check_valid_range(__before, __last);
583 _M_message(__gnu_debug::__msg_splice_other)
584 ._M_sequence(__list,
"list")
585 ._M_iterator(__before,
"before"));
588 _M_message(__gnu_debug::__msg_valid_range2)
589 ._M_sequence(__list,
"list")
590 ._M_iterator(__before,
"before")
591 ._M_iterator(__last,
"last"));
592 _GLIBCXX_DEBUG_VERIFY(__before != __last,
593 _M_message(__gnu_debug::__msg_valid_range2)
594 ._M_sequence(__list,
"list")
595 ._M_iterator(__before,
"before")
596 ._M_iterator(__last,
"last"));
597 _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(),
598 _M_message(__gnu_debug::__msg_splice_alloc)
600 ._M_sequence(__list,
"__list"));
602 for (_Base_const_iterator __tmp = std::next(__before.
base());
603 __tmp != __last.
base(); ++__tmp)
605 _GLIBCXX_DEBUG_VERIFY(__tmp != __list._M_base().end(),
606 _M_message(__gnu_debug::__msg_valid_range2)
608 ._M_iterator(__before,
"before")
609 ._M_iterator(__last,
"last"));
610 _GLIBCXX_DEBUG_VERIFY(&__list !=
this || __tmp != __pos.
base(),
611 _M_message(__gnu_debug::__msg_splice_overlap)
612 ._M_iterator(__tmp,
"position")
613 ._M_iterator(__before,
"before")
614 ._M_iterator(__last,
"last"));
618 {
return __it == __tmp; });
621 _Base::splice_after(__pos.
base(), std::move(__list._M_base()),
626 splice_after(const_iterator __pos, forward_list& __list,
627 const_iterator __before, const_iterator __last)
628 { splice_after(__pos, std::move(__list), __before, __last); }
631 remove(
const _Tp& __val)
633 _Base_iterator __x = _Base::before_begin();
634 _Base_iterator __old = __x++;
638 __x = _M_erase_after(__old);
644 template<
typename _Pred>
646 remove_if(_Pred __pred)
648 _Base_iterator __x = _Base::before_begin();
649 _Base_iterator __old = __x++;
653 __x = _M_erase_after(__old);
664 if (__first == __last)
666 _Base_iterator __next = std::next(__first);
667 while (__next != __last)
669 if (*__first == *__next)
670 __next = _M_erase_after(__first);
676 template<
typename _BinPred>
678 unique(_BinPred __binary_pred)
682 if (__first == __last)
684 _Base_iterator __next = std::next(__first);
685 while (__next != __last)
687 if (__binary_pred(*__first, *__next))
688 __next = _M_erase_after(__first);
695 merge(forward_list&& __list)
700 __glibcxx_check_sorted(__list._M_base().begin(),
701 __list._M_base().end());
704 return __it != __list._M_base().cbefore_begin()
705 && __it != __list._M_base().cend();
707 _Base::merge(std::move(__list._M_base()));
712 merge(forward_list& __list)
713 { merge(std::move(__list)); }
715 template<
typename _Comp>
717 merge(forward_list&& __list, _Comp __comp)
723 __list._M_base().end(), __comp);
725 [&__list](_Base_const_iterator __it)
727 return __it != __list._M_base().cbefore_begin()
728 && __it != __list._M_base().cend();
730 _Base::merge(std::move(__list._M_base()), __comp);
734 template<
typename _Comp>
736 merge(forward_list& __list, _Comp __comp)
737 { merge(std::move(__list), __comp); }
740 using _Base::reverse;
743 _M_base() noexcept {
return *
this; }
746 _M_base()
const noexcept {
return *
this; }
749 template<
typename _Tp,
typename _Alloc>
753 {
return __lx._M_base() == __ly._M_base(); }
755 template<
typename _Tp,
typename _Alloc>
757 operator<(const forward_list<_Tp, _Alloc>& __lx,
759 {
return __lx._M_base() < __ly._M_base(); }
761 template<
typename _Tp,
typename _Alloc>
765 {
return !(__lx == __ly); }
768 template<
typename _Tp,
typename _Alloc>
772 {
return (__ly < __lx); }
775 template<
typename _Tp,
typename _Alloc>
779 {
return !(__lx < __ly); }
782 template<
typename _Tp,
typename _Alloc>
784 operator<=(const forward_list<_Tp, _Alloc>& __lx,
786 {
return !(__ly < __lx); }
789 template<
typename _Tp,
typename _Alloc>
800 template<
class _Tp,
class _Alloc>
805 template<
typename _Iterator>
807 _S_Is(
const _Safe_iterator<_Iterator, _Sequence>& __it)
810 __it.base() == __it._M_get_sequence()->_M_base().before_begin();
813 template<
typename _Iterator>
815 _S_Is_Beginnest(
const _Safe_iterator<_Iterator, _Sequence>& __it)
816 {
return _S_Is(__it); }
819 #ifndef _GLIBCXX_DEBUG_PEDANTIC 820 template<
class _Tp,
class _Alloc>
821 struct _Insert_range_from_self_is_safe<
823 {
enum { __value = 1 }; };
_Safe_iterator_base * _M_prior
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.
_Safe_iterator_base * _M_const_iterators
The list of constant iterators that reference this container.
#define __glibcxx_check_insert_range_after(_Position, _First, _Last)
Base class that supports tracking of iterators that reference a sequence.
#define __glibcxx_check_erase_after(_Position)
bool _M_dereferenceable() const
Is the iterator dereferenceable?
_Iterator & base() noexcept
Return the underlying iterator.
GNU extensions for public use.
GNU debug classes for public use.
void _M_invalidate_if(_Predicate __pred)
Class std::forward_list with safety/checking/debug instrumentation.
Basic functionality for a safe iterator.
_Safe_sequence_base * _M_sequence
Special iterators swap and invalidation for forward_list because of the before_begin iterator...
ISO C++ entities toplevel namespace is std.
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
Safe class dealing with some allocator dependent operations.
bool _M_before_dereferenceable() const
Is the iterator before a dereferenceable one?
void swap(forward_list< _Tp, _Alloc > &__lx, forward_list< _Tp, _Alloc > &__ly)
See std::forward_list::swap().
Base class for constructing a safe sequence type that tracks iterators that reference it...
_Safe_iterator_base * _M_next
_Safe_iterator_base * _M_iterators
The list of mutable iterators that reference this container.
void _M_transfer_from_if(_Safe_sequence &__from, _Predicate __pred)
void _M_revalidate_singular()
#define __glibcxx_check_insert_after(_Position)
__gnu_cxx::__mutex & _M_get_mutex()
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
bool _M_attached_to(const _Safe_sequence_base *__seq) const
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.
#define __glibcxx_check_erase_range_after(_First, _Last)
#define __glibcxx_check_sorted_pred(_First, _Last, _Pred)
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
void _M_detach_singular()
bool _M_is_before_begin() const
Is this iterator equal to the sequence's before_begin() iterator if any?