This takes a very similar approach to the changes for std::list.
libstdc++-v3/ChangeLog:
PR libstdc++/57272
* include/bits/forward_list.h (_GLIBCXX_USE_ALLOC_PTR_FOR_LIST):
Define.
(_Fwd_list_node_base::_M_base_ptr): New member functions.
(_Fwd_list_node::_M_node_ptr): New member function.
(_Fwd_list_iterator, _Fwd_list_const_iterator): Make internal
member functions and data member private. Declare forward_list
and _Fwd_list_base as friends.
(__fwdlist::_Node_base, __fwdlist::_Node, __fwdlist::_Iterator):
New class templates.
(__fwdlist::_Node_traits): New class template.
(_Fwd_list_base): Use _Node_traits to get types. Use _Base_ptr
instad of _Fwd_list_node_base*. Use _M_base_ptr() instead of
taking address of head node.
(forward_list): Likewise.
(_Fwd_list_base::_M_get_node): Do not define for versioned
namespace.
(_Fwd_list_base::_M_put_node): Only convert pointer if needed.
(_Fwd_list_base::_M_create_node): Use __allocate_guarded_obj.
(_Fwd_list_base::_M_destroy_node): New member function.
* include/bits/forward_list.tcc (_Fwd_list_base::_M_insert_after)
(forward_list::_M_splice_after, forward_list::insert_after): Use
const_iterator::_M_const_cast() instead of casting pointers.
(_Fwd_list_base::_M_erase_after): Use _M_destroy_node.
(forward_list::remove, forward_list::remove_if): Only do
downcasts when accessing the value.
(forward_list::sort): Likewise.
* testsuite/23_containers/forward_list/capacity/1.cc: Check
max_size for new node type.
* testsuite/23_containers/forward_list/capacity/node_sizes.cc:
New test.
*
testsuite/23_containers/forward_list/requirements/explicit_instantiation/alloc_ptr.cc:
New test.
*
testsuite/23_containers/forward_list/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
New test.
---
Tested x86_64-linux.
libstdc++-v3/include/bits/forward_list.h | 432 +++++++++++++++---
libstdc++-v3/include/bits/forward_list.tcc | 124 ++---
.../23_containers/forward_list/capacity/1.cc | 11 +-
.../forward_list/capacity/node_sizes.cc | 24 +
.../forward_list/requirements/completeness.cc | 19 +
.../explicit_instantiation/alloc_ptr.cc | 86 ++++
.../alloc_ptr_ignored.cc | 4 +
7 files changed, 581 insertions(+), 119 deletions(-)
create mode 100644
libstdc++-v3/testsuite/23_containers/forward_list/capacity/node_sizes.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/forward_list/requirements/completeness.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/forward_list/requirements/explicit_instantiation/alloc_ptr.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/forward_list/requirements/explicit_instantiation/alloc_ptr_ignored.cc
diff --git a/libstdc++-v3/include/bits/forward_list.h
b/libstdc++-v3/include/bits/forward_list.h
index c9238cef96f..e4d24c4b9ca 100644
--- a/libstdc++-v3/include/bits/forward_list.h
+++ b/libstdc++-v3/include/bits/forward_list.h
@@ -40,6 +40,9 @@
#include <bits/stl_algobase.h>
#include <bits/stl_function.h>
#include <bits/allocator.h>
+#include <bits/allocated_ptr.h>
+#include <bits/ptr_traits.h>
+#include <debug/assertions.h>
#include <ext/alloc_traits.h>
#include <ext/aligned_buffer.h>
#if __glibcxx_ranges_to_container // C++ >= 23
@@ -47,6 +50,10 @@
# include <bits/ranges_util.h> // ranges::subrange
#endif
+#if ! defined _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
+# define _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST 1
+#endif
+
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
@@ -54,11 +61,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
/**
* @brief A helper basic node class for %forward_list.
+ *
* This is just a linked list with nothing inside it.
* There are purely list shuffling utility methods here.
*/
struct _Fwd_list_node_base
{
+ using _Base_ptr = _Fwd_list_node_base*;
+
_Fwd_list_node_base() = default;
_Fwd_list_node_base(_Fwd_list_node_base&& __x) noexcept
: _M_next(__x._M_next)
@@ -107,6 +117,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
_M_next->_M_next = __keep;
}
}
+
+ _Fwd_list_node_base* _M_base_ptr() { return this; }
+ const _Fwd_list_node_base* _M_base_ptr() const { return this; }
};
/**
@@ -119,6 +132,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
struct _Fwd_list_node
: public _Fwd_list_node_base
{
+ using _Node_ptr = _Fwd_list_node*;
+
_Fwd_list_node() = default;
__gnu_cxx::__aligned_buffer<_Tp> _M_storage;
@@ -130,8 +145,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
const _Tp*
_M_valptr() const noexcept
{ return _M_storage._M_ptr(); }
+
+ _Node_ptr
+ _M_node_ptr()
+ { return this; }
};
+ template<typename _Tp> struct _Fwd_list_const_iterator;
+
/**
* @brief A forward_list::iterator.
*
@@ -199,6 +220,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
{ return __x._M_node != __y._M_node; }
#endif
+ private:
+ template<typename, typename>
+ friend class forward_list;
+ template<typename, typename>
+ friend struct _Fwd_list_base;
+ friend struct _Fwd_list_const_iterator<_Tp>;
+
_Self
_M_next() const noexcept
{
@@ -282,6 +310,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
{ return __x._M_node != __y._M_node; }
#endif
+ private:
+ template<typename, typename>
+ friend class forward_list;
+ template<typename, typename>
+ friend struct _Fwd_list_base;
+
_Self
_M_next() const noexcept
{
@@ -291,23 +325,295 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
return _Fwd_list_const_iterator(nullptr);
}
+ _Fwd_list_iterator<_Tp>
+ _M_const_cast() const noexcept
+ {
+ return _Fwd_list_iterator<_Tp>(
+ const_cast<_Fwd_list_node_base*>(_M_node));
+ }
+
const _Fwd_list_node_base* _M_node;
};
+ template<typename _Tp, typename _Allocator> class forward_list;
+ template<typename _Tp, typename _Allocator> struct _Fwd_list_base;
+
+namespace __fwdlist
+{
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
+ /// The node-base type for allocators that use fancy pointers.
+ template<typename _VoidPtr>
+ struct _Node_base
+ {
+ using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>;
+
+ _Node_base() = default;
+
+ _Node_base(_Node_base&& __x) noexcept
+ : _M_next(__x._M_next)
+ { __x._M_next = nullptr; }
+
+ _Node_base(const _Node_base&) = delete;
+ _Node_base& operator=(const _Node_base&) = delete;
+
+ _Node_base&
+ operator=(_Node_base&& __x) noexcept
+ {
+ _M_next = __x._M_next;
+ __x._M_next = nullptr;
+ return *this;
+ }
+
+ _Base_ptr _M_next = nullptr;
+
+ // Splice (begin,end) before _M_next.
+ _Base_ptr
+ _M_transfer_after(_Base_ptr __begin, _Base_ptr __end) noexcept
+ {
+ _Base_ptr __keep = __begin->_M_next;
+ if (__end)
+ {
+ __begin->_M_next = __end->_M_next;
+ __end->_M_next = _M_next;
+ }
+ else
+ __begin->_M_next = nullptr;
+ _M_next = __keep;
+ return __end;
+ }
+
+ void
+ _M_reverse_after() noexcept
+ {
+ _Base_ptr __tail = _M_next;
+ if (!__tail)
+ return;
+ while (_Base_ptr __temp = __tail->_M_next)
+ {
+ _Base_ptr __keep = _M_next;
+ _M_next = __temp;
+ __tail->_M_next = __temp->_M_next;
+ _M_next->_M_next = __keep;
+ }
+ }
+
+ // This is not const-correct, but it's only used in a const access path
+ // by std::forward_list::empty(), where it doesn't escape, and by
+ // std::forward_list::before_begin() const, where the pointer is used
+ // to initialize a const_iterator and so constness is restored.
+ _Base_ptr
+ _M_base_ptr() const
+ {
+ return pointer_traits<_Base_ptr>::
+ pointer_to(const_cast<_Node_base&>(*this));
+ }
+ };
+
+ /**
+ * @brief A helper node class for %forward_list.
+ */
+ template<typename _ValPtr>
+ struct _Node
+ : public _Node_base<__ptr_rebind<_ValPtr, void>>
+ {
+ using value_type = typename pointer_traits<_ValPtr>::element_type;
+ using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
+
+ _Node() { }
+ ~_Node() { }
+ _Node(_Node&&) = delete;
+
+ union {
+#if ! _GLIBCXX_INLINE_VERSION
+ // For ABI compatibility we need to overalign this member.
+ alignas(__alignof__(value_type)) // XXX GLIBCXX_ABI Deprecated
+#endif
+ value_type _M_data;
+ };
+
+ value_type*
+ _M_valptr() noexcept
+ { return std::__addressof(_M_data); }
+
+ const value_type*
+ _M_valptr() const noexcept
+ { return std::__addressof(_M_data); }
+
+ _Node_ptr
+ _M_node_ptr()
+ { return pointer_traits<_Node_ptr>::pointer_to(*this); }
+ };
+
+ /// A forward_list iterator when the allocator uses fancy pointers.
+ template<bool _Const, typename _Ptr>
+ class _Iterator
+ {
+ using _Node = __fwdlist::_Node<_Ptr>;
+ using _Base_ptr
+ = typename __fwdlist::_Node_base<__ptr_rebind<_Ptr, void>>::_Base_ptr;
+
+ template<typename _Tp>
+ using __maybe_const = __conditional_t<_Const, const _Tp, _Tp>;
+
+ public:
+ using value_type = typename pointer_traits<_Ptr>::element_type;
+ using difference_type = ptrdiff_t;
+ using iterator_category = forward_iterator_tag;
+ using pointer = __maybe_const<value_type>*;
+ using reference = __maybe_const<value_type>&;
+
+ constexpr _Iterator() noexcept : _M_node() { }
+
+ _Iterator(const _Iterator&) = default;
+ _Iterator& operator=(const _Iterator&) = default;
+
+#ifdef __glibcxx_concepts
+ constexpr
+ _Iterator(const _Iterator<false, _Ptr>& __i) requires _Const
+#else
+ template<bool _OtherConst,
+ typename = __enable_if_t<_Const && !_OtherConst>>
+ constexpr
+ _Iterator(const _Iterator<_OtherConst, _Ptr>& __i)
+#endif
+ : _M_node(__i._M_node) { }
+
+ constexpr explicit
+ _Iterator(_Base_ptr __x) noexcept
+ : _M_node(__x) { }
+
+ [[__nodiscard__]]
+ constexpr reference
+ operator*() const noexcept
+ { return static_cast<_Node&>(*this->_M_node)._M_data; }
+
+ [[__nodiscard__]]
+ constexpr pointer
+ operator->() const noexcept
+ { return static_cast<_Node&>(*this->_M_node)._M_valptr(); }
+
+ _GLIBCXX14_CONSTEXPR _Iterator&
+ operator++() noexcept
+ {
+ _M_node = _M_node->_M_next;
+ return *this;
+ }
+
+ _GLIBCXX14_CONSTEXPR _Iterator
+ operator++(int) noexcept
+ {
+ _Iterator __tmp(*this);
+ _M_node = _M_node->_M_next;
+ return __tmp;
+ }
+
+ /**
+ * @brief Forward list iterator equality comparison.
+ */
+ [[__nodiscard__]]
+ friend constexpr bool
+ operator==(const _Iterator& __x, const _Iterator& __y) noexcept
+ { return __x._M_node == __y._M_node; }
+
+#if __cpp_impl_three_way_comparison < 201907L
+ /**
+ * @brief Forward list iterator inequality comparison.
+ */
+ [[__nodiscard__]]
+ friend constexpr bool
+ operator!=(const _Iterator& __x, const _Iterator& __y) noexcept
+ { return __x._M_node != __y._M_node; }
+#endif
+
+ private:
+ template<typename _Tp, typename _Allocator>
+ friend class _GLIBCXX_STD_C::forward_list;
+ template<typename _Tp, typename _Allocator>
+ friend struct _GLIBCXX_STD_C::_Fwd_list_base;
+
+ constexpr _Iterator<false, _Ptr>
+ _M_const_cast() const noexcept
+ { return _Iterator<false, _Ptr>(_M_node); }
+
+ friend _Iterator<!_Const, _Ptr>;
+
+ constexpr _Iterator
+ _M_next() const noexcept
+ { return _Iterator(_M_node ? _M_node->_M_next : nullptr); }
+
+ _Base_ptr _M_node;
+ };
+#endif // USE_ALLOC_PTR_FOR_FWD_LIST
+
+ // Determine the node and iterator types used by std::forward_list.
+ template<typename _Tp, typename _Ptr>
+ struct _Node_traits;
+
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST <= 9000
+ // Specialization for the simple case where the allocator's pointer type
+ // is the same type as value_type*.
+ // For ABI compatibility we can't change the types used for this case.
+ template<typename _Tp>
+ struct _Node_traits<_Tp, _Tp*>
+ {
+ using _Node_base = _Fwd_list_node_base;
+ using _Node = _Fwd_list_node<_Tp>;
+ using _Iterator = _Fwd_list_iterator<_Tp>;
+ using _Const_iterator = _Fwd_list_const_iterator<_Tp>;
+ };
+#endif
+
+#if ! _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
+ // Always use the T* specialization.
+ template<typename _Tp, typename _Ptr>
+ struct _Node_traits
+ : _Node_traits<_Tp, _Tp*>
+ { };
+#else
+ // Primary template used when the allocator uses fancy pointers.
+ template<typename _Tp, typename _Ptr>
+ struct _Node_traits
+ {
+ private:
+ using _VoidPtr = __ptr_rebind<_Ptr, void>;
+ using _ValPtr = __ptr_rebind<_Ptr, _Tp>;
+
+ public:
+ using _Node_base = __fwdlist::_Node_base<_VoidPtr>;
+ using _Node = __fwdlist::_Node<_ValPtr>;
+ using _Iterator = __fwdlist::_Iterator<false, _ValPtr>;
+ using _Const_iterator = __fwdlist::_Iterator<true, _ValPtr>;
+ };
+#endif // USE_ALLOC_PTR_FOR_FWD_LIST
+} // namespace __fwdlist
+
/**
* @brief Base class for %forward_list.
*/
template<typename _Tp, typename _Alloc>
struct _Fwd_list_base
{
+#if __cplusplus > 201703L || defined __STRICT_ANSI__
+ // The static_assert in forward_list ensures _Alloc::value_type is _Tp.
+ using pointer = typename allocator_traits<_Alloc>::pointer;
+#else
+ using _Tp_alloc_traits
+ = typename allocator_traits<_Alloc>::template rebind_traits<_Tp>;
+ using pointer = typename _Tp_alloc_traits::pointer;
+#endif
+
protected:
- typedef __alloc_rebind<_Alloc, _Fwd_list_node<_Tp>> _Node_alloc_type;
- typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
+ using _Node_traits = __fwdlist::_Node_traits<_Tp, pointer>;
+ using _Node = typename _Node_traits::_Node;
+ using _Node_alloc_type = __alloc_rebind<_Alloc, _Node>;
+ using _Node_alloc_traits = __gnu_cxx::__alloc_traits<_Node_alloc_type>;
+ using _Node_ptr = typename _Node_alloc_traits::pointer;
+ using _Base_ptr = typename _Node_traits::_Node_base::_Base_ptr;
struct _Fwd_list_impl
: public _Node_alloc_type
{
- _Fwd_list_node_base _M_head;
+ typename _Node_traits::_Node_base _M_head;
_Fwd_list_impl()
noexcept(is_nothrow_default_constructible<_Node_alloc_type>::value)
@@ -328,9 +634,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
_Fwd_list_impl _M_impl;
public:
- typedef _Fwd_list_iterator<_Tp> iterator;
- typedef _Fwd_list_const_iterator<_Tp> const_iterator;
- typedef _Fwd_list_node<_Tp> _Node;
+ using iterator = typename _Node_traits::_Iterator;
+ using const_iterator = typename _Node_traits::_Const_iterator;
_Node_alloc_type&
_M_get_Node_allocator() noexcept
@@ -357,54 +662,71 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
_Fwd_list_base(_Fwd_list_base&&) = default;
~_Fwd_list_base()
- { _M_erase_after(&_M_impl._M_head, nullptr); }
+ { _M_erase_after(_M_impl._M_head._M_base_ptr(), nullptr); }
protected:
+#if ! _GLIBCXX_INLINE_VERSION
+ // XXX GLIBCXX_ABI Deprecated
_Node*
_M_get_node()
{
auto __ptr = _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);
return std::__to_address(__ptr);
}
-
- template<typename... _Args>
- _Node*
- _M_create_node(_Args&&... __args)
- {
- _Node* __node = this->_M_get_node();
- __try
- {
- ::new ((void*)__node) _Node;
- _Node_alloc_traits::construct(_M_get_Node_allocator(),
- __node->_M_valptr(),
- std::forward<_Args>(__args)...);
- }
- __catch(...)
- {
- this->_M_put_node(__node);
- __throw_exception_again;
- }
- return __node;
- }
-
- template<typename... _Args>
- _Fwd_list_node_base*
- _M_insert_after(const_iterator __pos, _Args&&... __args);
+#endif
void
- _M_put_node(_Node* __p)
+ _M_put_node(_Node_ptr __p)
{
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
+ _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1);
+#else
typedef typename _Node_alloc_traits::pointer _Ptr;
auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__p);
_Node_alloc_traits::deallocate(_M_get_Node_allocator(), __ptr, 1);
+#endif
}
- _Fwd_list_node_base*
- _M_erase_after(_Fwd_list_node_base* __pos);
+ template<typename... _Args>
+ _Node_ptr
+ _M_create_node(_Args&&... __args)
+ {
+ auto& __alloc = _M_get_Node_allocator();
+ auto __guard = std::__allocate_guarded_obj(__alloc);
+ _Node_alloc_traits::construct(__alloc, __guard->_M_valptr(),
+ std::forward<_Args>(__args)...);
+ auto __p = __guard.release();
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_FWD_LIST
+ return __p;
+#else
+ return std::__to_address(__p);
+#endif
+ }
- _Fwd_list_node_base*
- _M_erase_after(_Fwd_list_node_base* __pos,
- _Fwd_list_node_base* __last);
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
+ void
+ _M_destroy_node(_Node_ptr __p)
+ {
+ auto& __alloc = _M_get_Node_allocator();
+ // Destroy the element
+ _Node_alloc_traits::destroy(__alloc, __p->_M_valptr());
+ // Only destroy the node if the pointers require it.
+ if constexpr (!is_trivially_destructible<_Base_ptr>::value)
+ __p->~_Node();
+ _M_put_node(__p);
+ }
+#pragma GCC diagnostic pop
+
+ template<typename... _Args>
+ _Base_ptr
+ _M_insert_after(const_iterator __pos, _Args&&... __args);
+
+ _Base_ptr
+ _M_erase_after(_Base_ptr __pos);
+
+ _Base_ptr
+ _M_erase_after(_Base_ptr __pos, _Base_ptr __last);
};
/**
@@ -581,12 +903,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
forward_list(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc())
: _Base(_Node_alloc_type(__a))
{
- _Node_base* __to = &this->_M_impl._M_head;
+ auto __to = this->_M_impl._M_head._M_base_ptr();
auto __first = ranges::begin(__rg);
const auto __last = ranges::end(__rg);
for (; __first != __last; ++__first)
{
- __to->_M_next = this->_M_create_node(*__first);
+ __to->_M_next = this->_M_create_node(*__first)->_M_base_ptr();
__to = __to->_M_next;
}
}
@@ -776,7 +1098,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
[[__nodiscard__]]
iterator
before_begin() noexcept
- { return iterator(&this->_M_impl._M_head); }
+ { return iterator(this->_M_impl._M_head._M_base_ptr()); }
/**
* Returns a read-only (constant) iterator that points before the
@@ -786,7 +1108,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
[[__nodiscard__]]
const_iterator
before_begin() const noexcept
- { return const_iterator(&this->_M_impl._M_head); }
+ { return const_iterator(this->_M_impl._M_head._M_base_ptr()); }
/**
* Returns a read/write iterator that points to the first element
@@ -845,7 +1167,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
[[__nodiscard__]]
const_iterator
cbefore_begin() const noexcept
- { return const_iterator(&this->_M_impl._M_head); }
+ { return const_iterator(this->_M_impl._M_head._M_base_ptr()); }
/**
* Returns a read-only (constant) iterator that points one past
@@ -884,8 +1206,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
reference
front()
{
- _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next);
- return *__front->_M_valptr();
+ _Node& __front = static_cast<_Node&>(*this->_M_impl._M_head._M_next);
+ return *__front._M_valptr();
}
/**
@@ -896,8 +1218,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
const_reference
front() const
{
- _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next);
- return *__front->_M_valptr();
+ _Node& __front = static_cast<_Node&>(*this->_M_impl._M_head._M_next);
+ return *__front._M_valptr();
}
// 23.3.4.5 modifiers:
@@ -990,7 +1312,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
void
pop_front()
- { this->_M_erase_after(&this->_M_impl._M_head); }
+ {
+ __glibcxx_requires_nonempty();
+ this->_M_erase_after(this->_M_impl._M_head._M_base_ptr());
+ }
/**
* @brief Constructs object in %forward_list after the specified
@@ -1137,8 +1462,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
iterator
erase_after(const_iterator __pos)
- { return iterator(this->_M_erase_after(const_cast<_Node_base*>
- (__pos._M_node))); }
+ { return iterator(this->_M_erase_after(__pos._M_const_cast()._M_node)); }
/**
* @brief Remove a range of elements.
@@ -1160,10 +1484,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
iterator
erase_after(const_iterator __pos, const_iterator __last)
- { return iterator(this->_M_erase_after(const_cast<_Node_base*>
- (__pos._M_node),
- const_cast<_Node_base*>
- (__last._M_node))); }
+ {
+ return iterator(this->_M_erase_after(__pos._M_const_cast()._M_node,
+ __last._M_const_cast()._M_node));
+ }
/**
* @brief Swaps data with another %forward_list.
@@ -1225,7 +1549,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
void
clear() noexcept
- { this->_M_erase_after(&this->_M_impl._M_head, nullptr); }
+ { this->_M_erase_after(this->_M_impl._M_head._M_base_ptr(), nullptr); }
// 23.3.4.6 forward_list operations:
diff --git a/libstdc++-v3/include/bits/forward_list.tcc
b/libstdc++-v3/include/bits/forward_list.tcc
index 9750c7c0502..140e9955714 100644
--- a/libstdc++-v3/include/bits/forward_list.tcc
+++ b/libstdc++-v3/include/bits/forward_list.tcc
@@ -46,47 +46,42 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
template<typename _Tp, typename _Alloc>
template<typename... _Args>
- _Fwd_list_node_base*
+ auto
_Fwd_list_base<_Tp, _Alloc>::
_M_insert_after(const_iterator __pos, _Args&&... __args)
+ -> _Base_ptr
{
- _Fwd_list_node_base* __to
- = const_cast<_Fwd_list_node_base*>(__pos._M_node);
- _Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
+ auto __to = __pos._M_const_cast()._M_node;
+ _Node_ptr __thing = _M_create_node(std::forward<_Args>(__args)...);
__thing->_M_next = __to->_M_next;
- __to->_M_next = __thing;
+ __to->_M_next = __thing->_M_base_ptr();
return __to->_M_next;
}
template<typename _Tp, typename _Alloc>
- _Fwd_list_node_base*
+ auto
_Fwd_list_base<_Tp, _Alloc>::
- _M_erase_after(_Fwd_list_node_base* __pos)
+ _M_erase_after(_Base_ptr __pos)
+ -> _Base_ptr
{
- _Node* __curr = static_cast<_Node*>(__pos->_M_next);
- __pos->_M_next = __curr->_M_next;
- _Node_alloc_traits::destroy(_M_get_Node_allocator(),
- __curr->_M_valptr());
- __curr->~_Node();
- _M_put_node(__curr);
+ auto& __curr = static_cast<_Node&>(*__pos->_M_next);
+ __pos->_M_next = __curr._M_next;
+ _M_destroy_node(__curr._M_node_ptr());
return __pos->_M_next;
}
template<typename _Tp, typename _Alloc>
- _Fwd_list_node_base*
+ auto
_Fwd_list_base<_Tp, _Alloc>::
- _M_erase_after(_Fwd_list_node_base* __pos,
- _Fwd_list_node_base* __last)
+ _M_erase_after(_Base_ptr __pos, _Base_ptr __last)
+ -> _Base_ptr
{
- _Node* __curr = static_cast<_Node*>(__pos->_M_next);
+ _Base_ptr __curr = __pos->_M_next;
while (__curr != __last)
{
- _Node* __temp = __curr;
- __curr = static_cast<_Node*>(__curr->_M_next);
- _Node_alloc_traits::destroy(_M_get_Node_allocator(),
- __temp->_M_valptr());
- __temp->~_Node();
- _M_put_node(__temp);
+ auto& __node = static_cast<_Node&>(*__curr);
+ __curr = __curr->_M_next;
+ _M_destroy_node(__node._M_node_ptr());
}
__pos->_M_next = __last;
return __last;
@@ -99,10 +94,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
forward_list<_Tp, _Alloc>::
_M_range_initialize(_InputIterator __first, _InputIterator __last)
{
- _Node_base* __to = &this->_M_impl._M_head;
+ auto __to = this->_M_impl._M_head._M_base_ptr();
for (; __first != __last; ++__first)
{
- __to->_M_next = this->_M_create_node(*__first);
+ __to->_M_next = this->_M_create_node(*__first)->_M_base_ptr();
__to = __to->_M_next;
}
}
@@ -113,10 +108,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
forward_list<_Tp, _Alloc>::
_M_fill_initialize(size_type __n, const value_type& __value)
{
- _Node_base* __to = &this->_M_impl._M_head;
+ auto __to = this->_M_impl._M_head._M_base_ptr();
for (; __n; --__n)
{
- __to->_M_next = this->_M_create_node(__value);
+ __to->_M_next = this->_M_create_node(__value)->_M_base_ptr();
__to = __to->_M_next;
}
}
@@ -126,10 +121,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
forward_list<_Tp, _Alloc>::
_M_default_initialize(size_type __n)
{
- _Node_base* __to = &this->_M_impl._M_head;
+ auto __to = this->_M_impl._M_head._M_base_ptr();
for (; __n; --__n)
{
- __to->_M_next = this->_M_create_node();
+ __to->_M_next = this->_M_create_node()->_M_base_ptr();
__to = __to->_M_next;
}
}
@@ -220,9 +215,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
_M_splice_after(const_iterator __pos,
const_iterator __before, const_iterator __last)
{
- _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
- _Node_base* __b = const_cast<_Node_base*>(__before._M_node);
- _Node_base* __end = __b;
+ auto __tmp = __pos._M_const_cast()._M_node;
+ auto __b = __before._M_const_cast()._M_node;
+ auto __end = __b;
while (__end && __end->_M_next != __last._M_node)
__end = __end->_M_next;
@@ -245,9 +240,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
if (__pos == __i || __pos == __j)
return;
- _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
- __tmp->_M_transfer_after(const_cast<_Node_base*>(__i._M_node),
- const_cast<_Node_base*>(__j._M_node));
+ auto __tmp = __pos._M_const_cast()._M_node;
+ __tmp->_M_transfer_after(__i._M_const_cast()._M_node,
+ __j._M_const_cast()._M_node);
}
template<typename _Tp, typename _Alloc>
@@ -261,7 +256,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
}
else
- return iterator(const_cast<_Node_base*>(__pos._M_node));
+ return __pos._M_const_cast();
}
template<typename _Tp, typename _Alloc>
@@ -275,7 +270,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
if (!__tmp.empty())
return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
else
- return iterator(const_cast<_Node_base*>(__pos._M_node));
+ return __pos._M_const_cast();
}
#if __cplusplus > 201703L
@@ -293,8 +288,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
forward_list __to_destroy(get_allocator());
auto __prev_it = cbefore_begin();
- while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
- if (*__tmp->_M_valptr() == __val)
+ while (auto __tmp = __prev_it._M_node->_M_next)
+ if (*static_cast<_Node&>(*__tmp)._M_valptr() == __val)
{
__to_destroy.splice_after(__to_destroy.cbefore_begin(),
*this, __prev_it);
@@ -316,8 +311,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
forward_list __to_destroy(get_allocator());
auto __prev_it = cbefore_begin();
- while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
- if (__pred(*__tmp->_M_valptr()))
+ while (auto __tmp = __prev_it._M_node->_M_next)
+ if (__pred(*static_cast<_Node&>(*__tmp)._M_valptr()))
{
__to_destroy.splice_after(__to_destroy.cbefore_begin(),
*this, __prev_it);
@@ -372,15 +367,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
if (std::__addressof(__list) == this)
return;
- _Node_base* __node = &this->_M_impl._M_head;
- while (__node->_M_next && __list._M_impl._M_head._M_next)
+ using _Base_ptr = typename _Node::_Base_ptr;
+
+ _Base_ptr __node = this->_M_impl._M_head._M_base_ptr();
+ _Base_ptr __other = __list._M_impl._M_head._M_base_ptr();
+ while (__node->_M_next && __other->_M_next)
{
- if (__comp(*static_cast<_Node*>
- (__list._M_impl._M_head._M_next)->_M_valptr(),
- *static_cast<_Node*>
- (__node->_M_next)->_M_valptr()))
- __node->_M_transfer_after(&__list._M_impl._M_head,
- __list._M_impl._M_head._M_next);
+ auto& __l = static_cast<_Node&>(*__other->_M_next);
+ auto& __r = static_cast<_Node&>(*__node->_M_next);
+ if (__comp(*__l._M_valptr(), *__r._M_valptr()))
+ __node->_M_transfer_after(__other, __other->_M_next);
__node = __node->_M_next;
}
@@ -416,18 +412,21 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
forward_list<_Tp, _Alloc>::
sort(_Comp __comp)
{
- // If `next' is nullptr, return immediately.
- _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
- if (!__list)
+ if (empty())
return;
+ using _Base_ptr = typename _Node::_Base_ptr;
+
+ // If `next' is nullptr, return immediately.
+ _Base_ptr __list = this->_M_impl._M_head._M_next;
+
unsigned long __insize = 1;
while (1)
{
- _Node* __p = __list;
+ _Base_ptr __p = __list;
__list = nullptr;
- _Node* __tail = nullptr;
+ _Base_ptr __tail = nullptr;
// Count number of merges we do in this pass.
unsigned long __nmerges = 0;
@@ -437,12 +436,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
++__nmerges;
// There exists a merge to be done.
// Step `insize' places along from p.
- _Node* __q = __p;
+ _Base_ptr __q = __p;
unsigned long __psize = 0;
for (unsigned long __i = 0; __i < __insize; ++__i)
{
++__psize;
- __q = static_cast<_Node*>(__q->_M_next);
+ __q = __q->_M_next;
if (!__q)
break;
}
@@ -454,33 +453,34 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
while (__psize > 0 || (__qsize > 0 && __q))
{
// Decide whether next node of merge comes from p or q.
- _Node* __e;
+ _Base_ptr __e;
if (__psize == 0)
{
// p is empty; e must come from q.
__e = __q;
- __q = static_cast<_Node*>(__q->_M_next);
+ __q = __q->_M_next;
--__qsize;
}
else if (__qsize == 0 || !__q)
{
// q is empty; e must come from p.
__e = __p;
- __p = static_cast<_Node*>(__p->_M_next);
+ __p = __p->_M_next;
--__psize;
}
- else if (!__comp(*__q->_M_valptr(), *__p->_M_valptr()))
+ else if (!__comp(*static_cast<_Node&>(*__q)._M_valptr(),
+ *static_cast<_Node&>(*__p)._M_valptr()))
{
// First node of q is not lower; e must come from p.
__e = __p;
- __p = static_cast<_Node*>(__p->_M_next);
+ __p = __p->_M_next;
--__psize;
}
else
{
// First node of q is lower; e must come from q.
__e = __q;
- __q = static_cast<_Node*>(__q->_M_next);
+ __q = __q->_M_next;
--__qsize;
}
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/capacity/1.cc
b/libstdc++-v3/testsuite/23_containers/forward_list/capacity/1.cc
index 119bf6ca027..590bba5bd25 100644
--- a/libstdc++-v3/testsuite/23_containers/forward_list/capacity/1.cc
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/capacity/1.cc
@@ -36,13 +36,18 @@ test01()
VERIFY(fld.empty() == true);
#ifdef _GLIBCXX_DEBUG
- using std::_GLIBCXX_STD_C::_Fwd_list_node;
+ namespace C = std::_GLIBCXX_STD_C;
#else
- using std::_Fwd_list_node;
+ namespace C = std;
#endif
- std::allocator<_Fwd_list_node<double> > a;
+ std::allocator<C::_Fwd_list_node<double>> a;
VERIFY( fld.max_size() == __gnu_test::max_size(a) );
+
+#if _GLIBCXX_FWDLIST_USE_ALLOC_PTR
+ std::allocator<C::__fwdlist::_Node<double*>> b;
+ VERIFY( __gnu_test::max_size(b) == __gnu_test::max_size(a) );
+#endif
}
int
diff --git
a/libstdc++-v3/testsuite/23_containers/forward_list/capacity/node_sizes.cc
b/libstdc++-v3/testsuite/23_containers/forward_list/capacity/node_sizes.cc
new file mode 100644
index 00000000000..a709031783b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/capacity/node_sizes.cc
@@ -0,0 +1,24 @@
+// { dg-do compile { target c++11 } }
+
+#include <forward_list>
+
+#if _GLIBCXX_FWDLIST_USE_ALLOC_PTR
+
+#ifdef _GLIBCXX_DEBUG
+namespace C = std::_GLIBCXX_STD_C;
+#else
+namespace C = std;
+#endif
+
+// We use double here because for ADJUST_FIELD_ALIGN targets (like i386)
+// its alignment differs when used as a data member or as a complete object.
+static_assert(sizeof(C::_Fwd_list_node<double>)
+ == sizeof(C::__fwdlist::_Node<double*>),
+ "node types have same size");
+static_assert(alignof(C::_Fwd_list_node<double>)
+ == alignof(C::__fwdlist::_Node<double*>),
+ "node types have same alignment");
+static_assert(__alignof(C::_Fwd_list_node<double>)
+ == __alignof(C::__fwdlist::_Node<double*>),
+ "node types have same preferred alignment");
+#endif
diff --git
a/libstdc++-v3/testsuite/23_containers/forward_list/requirements/completeness.cc
b/libstdc++-v3/testsuite/23_containers/forward_list/requirements/completeness.cc
new file mode 100644
index 00000000000..abc9df504e2
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/forward_list/requirements/completeness.cc
@@ -0,0 +1,19 @@
+// { dg-do compile {target c++11 } }
+
+// C++17 [forwardlist.overview]
+// An incomplete type T may be used when instantiating forward_list if the
+// allocator satisfies the allocator completeness requirements (20.5.3.5.1).
+// T shall be complete before any member of the resulting specialization
+// of forward_list is referenced.
+
+#include <forward_list>
+
+struct Incomplete;
+
+// This instantiates std::forward_list, but none of its members.
+const int sz = sizeof(std::forward_list<Incomplete>);
+
+// Technically the following references a member of std::forward_list,
+// but because our iterators are SCARY it doesn't instantiate any members
+// of std::forward_list.
+std::forward_list<Incomplete>::iterator i{};
diff --git
a/libstdc++-v3/testsuite/23_containers/forward_list/requirements/explicit_instantiation/alloc_ptr.cc
b/libstdc++-v3/testsuite/23_containers/forward_list/requirements/explicit_instantiation/alloc_ptr.cc
new file mode 100644
index 00000000000..2f382649d92
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/forward_list/requirements/explicit_instantiation/alloc_ptr.cc
@@ -0,0 +1,86 @@
+// { dg-do compile { target c++11 } }
+
+#include <forward_list>
+#include <testsuite_allocator.h>
+
+// An allocator that uses __gnu_cxx::_Pointer_adapter as its pointer type.
+template class std::forward_list<int, __gnu_test::CustomPointerAlloc<int>>;
+
+// Unlike __gnu_cxx::_Pointer_adapter, this fancy pointer supports neither
+// implicit nor explicit conversions from raw pointers. The constructor from
+// a raw pointer is explicit and requires a second parameter. The only way for
+// containers to construct one of these pointers is pointer_traits::pointer_to.
+template<typename T>
+struct Pointer : __gnu_test::PointerBase<Pointer<T>, T>
+{
+ using Base = __gnu_test::PointerBase<Pointer<T>, T>;
+
+ Pointer() = default;
+ Pointer(std::nullptr_t) : Base() { }
+ explicit Pointer(T* p, int) : Base(p) { }
+
+ // Allow conversions to const_pointer and to void_pointer
+ template<typename U, typename = typename std::enable_if<
+ (!std::is_const<U>::value && std::is_same<T, const U>::value)
+ || (std::is_void<T>::value && std::is_convertible<U*, T*>::value)
+ >::type>
+ Pointer(const Pointer<U>& p) : Base(p.operator->()) { }
+
+ template<typename U>
+ static typename std::enable_if<std::is_same<U, T>::value, Pointer>::type
+ pointer_to(U& t)
+ { return Pointer(std::addressof(t), 1); }
+};
+
+// A minimal allocator that uses Pointer as its pointer type.
+template<typename T>
+struct Allocator
+{
+ using value_type = T;
+ using pointer = Pointer<T>;
+
+ Allocator() = default;
+ template<typename U>
+ Allocator(const Allocator<U>&) { }
+
+ pointer allocate(std::size_t n)
+ { return pointer(std::allocator<T>().allocate(n), 1); }
+
+ void deallocate(pointer p, std::size_t n)
+ {
+ std::allocator<T>().deallocate(p.operator->(), n);
+ }
+
+ bool operator==(const Allocator&) const { return true; }
+ bool operator!=(const Allocator&) const { return false; }
+};
+
+template class std::forward_list<int, Allocator<int>>;
+
+#include <testsuite_iterators.h>
+
+void
+test_template_members(__gnu_test::input_container<short>& c)
+{
+ // Use member functions that are not included in explicit instantiations.
+ std::forward_list<int, Allocator<int>> l(c.begin(), c.end());
+ l.assign(c.begin(), c.end());
+ l.insert_after(l.before_begin(), c.begin(), c.end());
+ l.emplace_front(1);
+ l.emplace_after(l.before_begin(), 1);
+ l.remove_if([](int) { return false; });
+ l.unique([](int, int) { return false; });
+ l.merge(l, [](int, int) { return false; });
+ l.merge(std::move(l), [](int, int) { return false; });
+ l.sort([](int, int) { return false; });
+
+#ifdef __glibcxx_ranges_to_container
+ short arr[2];
+ __gnu_test::test_input_range<short> r(arr);
+ std::forward_list<int, Allocator<int>> l2(std::from_range, r);
+ l2.assign_range(r);
+ l2.prepend_range(r);
+ l2.insert_range_after(l2.begin(), r);
+#endif
+}
+
diff --git
a/libstdc++-v3/testsuite/23_containers/forward_list/requirements/explicit_instantiation/alloc_ptr_ignored.cc
b/libstdc++-v3/testsuite/23_containers/forward_list/requirements/explicit_instantiation/alloc_ptr_ignored.cc
new file mode 100644
index 00000000000..6205a2ff3bf
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/forward_list/requirements/explicit_instantiation/alloc_ptr_ignored.cc
@@ -0,0 +1,4 @@
+// { dg-options "-D_GLIBCXX_FWDLIST_USE_ALLOC_PTR=0" }
+// { dg-do compile { target c++11 } }
+
+#include "alloc_ptr.cc"
--
2.47.0
