@@ -38,6 +38,8 @@
#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 <ext/alloc_traits.h>
#include <ext/aligned_buffer.h>
@@ -47,27 +49,44 @@ _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.
+ *
+ * The template is parameterized on the allocator's void_pointer type.
*/
+ template<typename _VoidPtr>
struct _Fwd_list_node_base
{
+ static_assert(is_void<typename pointer_traits<_VoidPtr>::element_type>{},
+ "the template argument must be a pointer to void");
+
+ using __pointer = __ptr_rebind<_VoidPtr, _Fwd_list_node_base>;
+ using __const_pointer = __ptr_rebind<_VoidPtr, const _Fwd_list_node_base>;
+ using __node_base = _Fwd_list_node_base;
+
_Fwd_list_node_base() = default;
- _Fwd_list_node_base* _M_next = nullptr;
+ __pointer _M_next = nullptr;
- _Fwd_list_node_base*
- _M_transfer_after(_Fwd_list_node_base* __begin,
- _Fwd_list_node_base* __end) noexcept
+ // Get a pointer-to-base from a pointer-to-derived
+ // (fancy pointers might not support an implicit conversion)
+ __pointer
+ _M_base()
+ { return pointer_traits<__pointer>::pointer_to(*this); }
+
+ __pointer
+ _M_transfer_after(__pointer __begin,
+ __pointer __end) noexcept
{
- _Fwd_list_node_base* __keep = __begin->_M_next;
+ __pointer __keep = __begin->_M_next;
if (__end)
{
__begin->_M_next = __end->_M_next;
__end->_M_next = _M_next;
}
else
- __begin->_M_next = 0;
+ __begin->_M_next = nullptr;
_M_next = __keep;
return __end;
}
@@ -75,38 +94,52 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
void
_M_reverse_after() noexcept
{
- _Fwd_list_node_base* __tail = _M_next;
+ __pointer __tail = _M_next;
if (!__tail)
return;
- while (_Fwd_list_node_base* __temp = __tail->_M_next)
+ while (__pointer __temp = __tail->_M_next)
{
- _Fwd_list_node_base* __keep = _M_next;
+ __pointer __keep = _M_next;
_M_next = __temp;
__tail->_M_next = __temp->_M_next;
_M_next->_M_next = __keep;
}
}
+
+ // Cast away constness
+ __pointer
+ _M_mutable() const noexcept
+ {
+ auto* __self = const_cast<_Fwd_list_node_base*>(this);
+ return pointer_traits<__pointer>::pointer_to(*__self);
+ }
};
/**
* @brief A helper node class for %forward_list.
- * This is just a linked list with uninitialized storage for a
- * data value in each node.
+ *
+ * This is just a linked list with uninitialized storage for a data value
+ * in each node.
* There is a sorting utility method.
*/
- template<typename _Tp>
+ template<typename _Ptr>
struct _Fwd_list_node
- : public _Fwd_list_node_base
+ : public _Fwd_list_node_base<__ptr_rebind<_Ptr, void>>
{
+ using value_type = typename pointer_traits<_Ptr>::element_type;
+
+ static_assert(!is_const<value_type>{},
+ "the template argument must be a pointer to non-const");
+
_Fwd_list_node() = default;
- __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
+ __gnu_cxx::__aligned_buffer<value_type> _M_storage;
- _Tp*
+ value_type*
_M_valptr() noexcept
{ return _M_storage._M_ptr(); }
- const _Tp*
+ const value_type*
_M_valptr() const noexcept
{ return _M_storage._M_ptr(); }
};
@@ -116,15 +149,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*
* All the functions are op overloads.
*/
- template<typename _Tp>
+ template<typename _Ptr>
struct _Fwd_list_iterator
{
- typedef _Fwd_list_iterator<_Tp> _Self;
- typedef _Fwd_list_node<_Tp> _Node;
+ typedef _Fwd_list_iterator _Self;
+ typedef _Fwd_list_node<_Ptr> _Node;
+ typedef typename _Node::__pointer __base_pointer;
- typedef _Tp value_type;
- typedef _Tp* pointer;
- typedef _Tp& reference;
+ typedef typename _Node::value_type value_type;
+ typedef value_type* pointer;
+ typedef value_type& reference;
typedef ptrdiff_t difference_type;
typedef std::forward_iterator_tag iterator_category;
@@ -132,16 +166,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
: _M_node() { }
explicit
- _Fwd_list_iterator(_Fwd_list_node_base* __n) noexcept
+ _Fwd_list_iterator(__base_pointer __n) noexcept
: _M_node(__n) { }
reference
operator*() const noexcept
- { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }
+ { return *static_cast<_Node&>(*_M_node)._M_valptr(); }
pointer
operator->() const noexcept
- { return static_cast<_Node*>(this->_M_node)->_M_valptr(); }
+ { return static_cast<_Node&>(*_M_node)._M_valptr(); }
_Self&
operator++() noexcept
@@ -168,14 +202,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
_Self
_M_next() const noexcept
- {
- if (_M_node)
- return _Fwd_list_iterator(_M_node->_M_next);
- else
- return _Fwd_list_iterator(0);
- }
+ { return _M_node ? _Self(_M_node->_M_next) : _Self{}; }
- _Fwd_list_node_base* _M_node;
+ __base_pointer _M_node;
};
/**
@@ -183,16 +212,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*
* All the functions are op overloads.
*/
- template<typename _Tp>
+ template<typename _Ptr>
struct _Fwd_list_const_iterator
{
- typedef _Fwd_list_const_iterator<_Tp> _Self;
- typedef const _Fwd_list_node<_Tp> _Node;
- typedef _Fwd_list_iterator<_Tp> iterator;
-
- typedef _Tp value_type;
- typedef const _Tp* pointer;
- typedef const _Tp& reference;
+ typedef _Fwd_list_const_iterator _Self;
+ typedef const _Fwd_list_node<_Ptr> _Node;
+ typedef typename _Node::__const_pointer __base_pointer;
+ typedef _Fwd_list_iterator<_Ptr> iterator;
+
+ typedef typename _Node::value_type value_type;
+ typedef const value_type* pointer;
+ typedef const value_type& reference;
typedef ptrdiff_t difference_type;
typedef std::forward_iterator_tag iterator_category;
@@ -200,7 +230,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
: _M_node() { }
explicit
- _Fwd_list_const_iterator(const _Fwd_list_node_base* __n) noexcept
+ _Fwd_list_const_iterator(__base_pointer __n) noexcept
: _M_node(__n) { }
_Fwd_list_const_iterator(const iterator& __iter) noexcept
@@ -208,11 +238,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
reference
operator*() const noexcept
- { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }
+ { return *static_cast<const _Node&>(*_M_node)._M_valptr(); }
pointer
operator->() const noexcept
- { return static_cast<_Node*>(this->_M_node)->_M_valptr(); }
+ { return static_cast<const _Node&>(*_M_node)._M_valptr(); }
_Self&
operator++() noexcept
@@ -239,49 +269,52 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
_Self
_M_next() const noexcept
- {
- if (this->_M_node)
- return _Fwd_list_const_iterator(_M_node->_M_next);
- else
- return _Fwd_list_const_iterator(0);
- }
+ { return _M_node ? _Self{_M_node->_M_next} : _Self{}; }
- const _Fwd_list_node_base* _M_node;
+ __base_pointer _M_node;
};
/**
* @brief Forward list iterator equality comparison.
*/
- template<typename _Tp>
+ template<typename _Ptr>
inline bool
- operator==(const _Fwd_list_iterator<_Tp>& __x,
- const _Fwd_list_const_iterator<_Tp>& __y) noexcept
+ operator==(const _Fwd_list_iterator<_Ptr>& __x,
+ const _Fwd_list_const_iterator<_Ptr>& __y) noexcept
{ return __x._M_node == __y._M_node; }
/**
* @brief Forward list iterator inequality comparison.
*/
- template<typename _Tp>
+ template<typename _Ptr>
inline bool
- operator!=(const _Fwd_list_iterator<_Tp>& __x,
- const _Fwd_list_const_iterator<_Tp>& __y) noexcept
+ operator!=(const _Fwd_list_iterator<_Ptr>& __x,
+ const _Fwd_list_const_iterator<_Ptr>& __y) noexcept
{ return __x._M_node != __y._M_node; }
/**
* @brief Base class for %forward_list.
*/
- template<typename _Tp, typename _Alloc>
+ template<typename _Alloc>
struct _Fwd_list_base
{
protected:
- typedef __alloc_rebind<_Alloc, _Tp> _Tp_alloc_type;
- typedef __alloc_rebind<_Alloc, _Fwd_list_node<_Tp>> _Node_alloc_type;
+ typedef typename allocator_traits<_Alloc>::pointer pointer;
+ typedef _Fwd_list_node<pointer> _Node;
+ typedef typename _Node::__node_base _Node_base;
+
+ typedef __alloc_rebind<_Alloc, _Node> _Node_alloc_type;
typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
+ typedef typename _Node_alloc_traits::pointer __node_pointer;
+
+ typedef _Fwd_list_iterator<pointer> iterator;
+ typedef _Fwd_list_const_iterator<pointer> const_iterator;
+
struct _Fwd_list_impl
: public _Node_alloc_type
{
- _Fwd_list_node_base _M_head;
+ _Node_base _M_head;
_Fwd_list_impl()
: _Node_alloc_type(), _M_head()
@@ -298,18 +331,13 @@ _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;
-
_Node_alloc_type&
_M_get_Node_allocator() noexcept
- { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
+ { return this->_M_impl; }
const _Node_alloc_type&
_M_get_Node_allocator() const noexcept
- { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
+ { return this->_M_impl; }
_Fwd_list_base()
: _M_impl() { }
@@ -323,60 +351,55 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
: _M_impl(std::move(__lst._M_get_Node_allocator()))
{
this->_M_impl._M_head._M_next = __lst._M_impl._M_head._M_next;
- __lst._M_impl._M_head._M_next = 0;
+ __lst._M_impl._M_head._M_next = nullptr;
}
~_Fwd_list_base()
- { _M_erase_after(&_M_impl._M_head, 0); }
+ { _M_erase_after(_M_head(), nullptr); }
- protected:
+ typedef typename _Node_base::__pointer __base_pointer;
+ typedef typename _Node_base::__const_pointer __const_base_pointer;
+
+ __base_pointer
+ _M_head() noexcept
+ { return pointer_traits<__base_pointer>::pointer_to(_M_impl._M_head); }
+
+ __const_base_pointer
+ _M_head() const noexcept
+ {
+ return pointer_traits<__const_base_pointer>::
+ pointer_to(_M_impl._M_head);
+ }
- _Node*
- _M_get_node()
+ // Cast _Fwd_list_node_base<VP>* to _Fwd_list_node<TP>*
+ static __node_pointer
+ _S_node_ptr(__base_pointer __p) noexcept
{
- auto __ptr = _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);
- return std::__addressof(*__ptr);
+ typedef typename allocator_traits<_Alloc>::void_pointer __void_pointer;
+ return __node_pointer(static_cast<__void_pointer>(__p));
}
template<typename... _Args>
- _Node*
+ __base_pointer
_M_create_node(_Args&&... __args)
{
- _Node* __node = this->_M_get_node();
- __try
- {
- _Tp_alloc_type __a(_M_get_Node_allocator());
- typedef allocator_traits<_Tp_alloc_type> _Alloc_traits;
- ::new ((void*)__node) _Node;
- _Alloc_traits::construct(__a, __node->_M_valptr(),
+ using __node_guard = __allocated_obj<_Node_alloc_type>;
+ auto& __alloc = _M_get_Node_allocator();
+ __node_guard __node{ std::__allocate_guarded(__alloc) };
+ _Node_alloc_traits::construct(__alloc, __node->_M_valptr(),
std::forward<_Args>(__args)...);
- }
- __catch(...)
- {
- this->_M_put_node(__node);
- __throw_exception_again;
- }
- return __node;
+ return __node.release()->_M_base();
}
template<typename... _Args>
- _Fwd_list_node_base*
+ __base_pointer
_M_insert_after(const_iterator __pos, _Args&&... __args);
- void
- _M_put_node(_Node* __p)
- {
- 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);
- }
-
- _Fwd_list_node_base*
- _M_erase_after(_Fwd_list_node_base* __pos);
+ __base_pointer
+ _M_erase_after(__base_pointer __pos);
- _Fwd_list_node_base*
- _M_erase_after(_Fwd_list_node_base* __pos,
- _Fwd_list_node_base* __last);
+ __base_pointer
+ _M_erase_after(__base_pointer __pos, __base_pointer __last);
};
/**
@@ -401,21 +424,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* [] ) access is not allowed. For algorithms which only need
* sequential access, this lack makes no difference.
*
- * Also unlike the other standard containers, std::forward_list provides
+ * Similar to std::list, std::forward_list provides
* specialized algorithms %unique to linked lists, such as
* splicing, sorting, and in-place reversal.
*/
- template<typename _Tp, typename _Alloc = allocator<_Tp> >
- class forward_list : private _Fwd_list_base<_Tp, _Alloc>
+ template<typename _Tp, typename _Alloc = allocator<_Tp>>
+ class forward_list
+ : private _Fwd_list_base<__alloc_rebind<_Alloc, _Tp>>
{
+#ifdef _GLIBCXX_DEBUG_PEDANTIC
+ static_assert(is_same<_Tp, typename _Alloc::value_type>{},
+ "allocator and container must have the same value_type");
+#endif
+ public:
+ typedef __alloc_rebind<_Alloc, _Tp> allocator_type;
+
private:
- typedef _Fwd_list_base<_Tp, _Alloc> _Base;
- typedef _Fwd_list_node<_Tp> _Node;
- typedef _Fwd_list_node_base _Node_base;
- typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
+ typedef allocator_traits<allocator_type> _Alloc_traits;
+ typedef _Fwd_list_base<allocator_type> _Base;
+ typedef typename _Base::_Node _Node;
+ typedef typename _Base::_Node_base _Node_base;
typedef typename _Base::_Node_alloc_type _Node_alloc_type;
typedef typename _Base::_Node_alloc_traits _Node_alloc_traits;
- typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits;
public:
// types:
@@ -425,11 +455,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
typedef value_type& reference;
typedef const value_type& const_reference;
- typedef _Fwd_list_iterator<_Tp> iterator;
- typedef _Fwd_list_const_iterator<_Tp> const_iterator;
+ typedef typename _Base::iterator iterator;
+ typedef typename _Base::const_iterator const_iterator;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
- typedef _Alloc allocator_type;
// 23.3.4.2 construct/copy/destroy:
@@ -437,8 +466,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* @brief Creates a %forward_list with no elements.
* @param __al An allocator object.
*/
+ forward_list() noexcept
+ : _Base(_Node_alloc_type())
+ { }
+
explicit
- forward_list(const _Alloc& __al = _Alloc())
+ forward_list(const _Alloc& __al)
: _Base(_Node_alloc_type(__al))
{ }
@@ -447,7 +480,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* @param __list Input list to copy.
* @param __al An allocator object.
*/
- forward_list(const forward_list& __list, const _Alloc& __al)
+ forward_list(const forward_list& __list, const allocator_type& __al)
: _Base(_Node_alloc_type(__al))
{ _M_range_initialize(__list.begin(), __list.end()); }
@@ -456,7 +489,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* @param __list Input list to move.
* @param __al An allocator object.
*/
- forward_list(forward_list&& __list, const _Alloc& __al)
+ forward_list(forward_list&& __list, const allocator_type& __al)
noexcept(_Node_alloc_traits::_S_always_equal())
: _Base(std::move(__list), _Node_alloc_type(__al))
{ }
@@ -469,7 +502,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* constructed elements.
*/
explicit
- forward_list(size_type __n, const _Alloc& __al = _Alloc())
+ forward_list(size_type __n, const allocator_type& __al = _Alloc())
: _Base(_Node_alloc_type(__al))
{ _M_default_initialize(__n); }
@@ -483,7 +516,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* @a __value.
*/
forward_list(size_type __n, const _Tp& __value,
- const _Alloc& __al = _Alloc())
+ const allocator_type& __al = _Alloc())
: _Base(_Node_alloc_type(__al))
{ _M_fill_initialize(__n, __value); }
@@ -500,7 +533,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
template<typename _InputIterator,
typename = std::_RequireInputIter<_InputIterator>>
forward_list(_InputIterator __first, _InputIterator __last,
- const _Alloc& __al = _Alloc())
+ const allocator_type& __al = _Alloc())
: _Base(_Node_alloc_type(__al))
{ _M_range_initialize(__first, __last); }
@@ -535,7 +568,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* in the initializer_list @a __il. This is linear in __il.size().
*/
forward_list(std::initializer_list<_Tp> __il,
- const _Alloc& __al = _Alloc())
+ const allocator_type& __al = _Alloc())
: _Base(_Node_alloc_type(__al))
{ _M_range_initialize(__il.begin(), __il.end()); }
@@ -652,7 +685,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
iterator
before_begin() noexcept
- { return iterator(&this->_M_impl._M_head); }
+ { return iterator(this->_M_head()); }
/**
* Returns a read-only (constant) iterator that points before the
@@ -661,7 +694,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
const_iterator
before_begin() const noexcept
- { return const_iterator(&this->_M_impl._M_head); }
+ { return const_iterator(this->_M_head()); }
/**
* Returns a read/write iterator that points to the first element
@@ -705,7 +738,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
const_iterator
cbegin() const noexcept
- { return const_iterator(this->_M_impl._M_head._M_next); }
+ { return const_iterator(this->_M_head()->_M_next); }
/**
* Returns a read-only (constant) iterator that points before the
@@ -714,7 +747,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
const_iterator
cbefore_begin() const noexcept
- { return const_iterator(&this->_M_impl._M_head); }
+ { return const_iterator(this->_M_head()); }
/**
* Returns a read-only (constant) iterator that points one past
@@ -723,7 +756,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
const_iterator
cend() const noexcept
- { return const_iterator(0); }
+ { return const_iterator(); }
/**
* Returns true if the %forward_list is empty. (Thus begin() would
@@ -731,7 +764,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
bool
empty() const noexcept
- { return this->_M_impl._M_head._M_next == 0; }
+ { return this->_M_impl._M_head._M_next == nullptr; }
/**
* Returns the largest possible number of elements of %forward_list.
@@ -749,8 +782,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_head()->_M_next);
+ return *__front._M_valptr();
}
/**
@@ -760,8 +793,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_head()->_M_next);
+ return *__front._M_valptr();
}
// 23.3.4.5 modiļ¬ers:
@@ -818,7 +851,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
void
pop_front()
- { this->_M_erase_after(&this->_M_impl._M_head); }
+ { this->_M_erase_after(this->_M_head()); }
/**
* @brief Constructs object in %forward_list after the specified
@@ -939,8 +972,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_node->_M_mutable())); }
/**
* @brief Remove a range of elements.
@@ -962,10 +994,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_node->_M_mutable(),
+ __last._M_node->_M_mutable()));
+ }
/**
* @brief Swaps data with another %forward_list.
@@ -1026,7 +1058,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
void
clear() noexcept
- { this->_M_erase_after(&this->_M_impl._M_head, 0); }
+ { this->_M_erase_after(this->_M_head(), {}); }
// 23.3.4.6 forward_list operations:
@@ -1326,6 +1358,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
clear();
insert_after(cbefore_begin(), __n, __val);
}
+
+ template<typename _Pred, typename... _Ptr>
+ static auto
+ _S_apply(_Pred __pred, _Ptr... __ptr)
+ -> decltype(__pred(*_Base::_S_node_ptr(__ptr)->_M_valptr()...))
+ { return __pred(*_Base::_S_node_ptr(__ptr)->_M_valptr()...); }
};
/**
@@ -34,75 +34,73 @@ namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
- template<typename _Tp, typename _Alloc>
- _Fwd_list_base<_Tp, _Alloc>::
+ template<typename _Alloc>
+ _Fwd_list_base<_Alloc>::
_Fwd_list_base(_Fwd_list_base&& __lst, const _Node_alloc_type& __a)
: _M_impl(__a)
{
if (__lst._M_get_Node_allocator() == __a)
{
this->_M_impl._M_head._M_next = __lst._M_impl._M_head._M_next;
- __lst._M_impl._M_head._M_next = 0;
+ __lst._M_impl._M_head._M_next = nullptr;
}
else
{
- this->_M_impl._M_head._M_next = 0;
- _Fwd_list_node_base* __to = &this->_M_impl._M_head;
- _Node* __curr = static_cast<_Node*>(__lst._M_impl._M_head._M_next);
+ this->_M_impl._M_head._M_next = nullptr;
+ auto __to = this->_M_head();
+ auto __curr = __lst._M_impl._M_head._M_next;
while (__curr)
{
- __to->_M_next =
- _M_create_node(std::move_if_noexcept(*__curr->_M_valptr()));
+ auto* __valptr = _S_node_ptr(__curr)->_M_valptr();
+ __to->_M_next = _M_create_node(std::move_if_noexcept(*__valptr));
__to = __to->_M_next;
- __curr = static_cast<_Node*>(__curr->_M_next);
+ __curr = __curr->_M_next;
}
}
}
- template<typename _Tp, typename _Alloc>
+ template<typename _Alloc>
template<typename... _Args>
- _Fwd_list_node_base*
- _Fwd_list_base<_Tp, _Alloc>::
+ auto
+ _Fwd_list_base<_Alloc>::
_M_insert_after(const_iterator __pos, _Args&&... __args)
+ -> __base_pointer
{
- _Fwd_list_node_base* __to
- = const_cast<_Fwd_list_node_base*>(__pos._M_node);
- _Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
- __thing->_M_next = __to->_M_next;
- __to->_M_next = __thing;
+ __base_pointer __to = __pos._M_node->_M_mutable();
+ __base_pointer __node = _M_create_node(std::forward<_Args>(__args)...);
+ __node->_M_next = __to->_M_next;
+ __to->_M_next = __node;
return __to->_M_next;
}
- template<typename _Tp, typename _Alloc>
- _Fwd_list_node_base*
- _Fwd_list_base<_Tp, _Alloc>::
- _M_erase_after(_Fwd_list_node_base* __pos)
- {
- _Node* __curr = static_cast<_Node*>(__pos->_M_next);
- __pos->_M_next = __curr->_M_next;
- _Tp_alloc_type __a(_M_get_Node_allocator());
- allocator_traits<_Tp_alloc_type>::destroy(__a, __curr->_M_valptr());
- __curr->~_Node();
- _M_put_node(__curr);
+ template<typename _Alloc>
+ auto
+ _Fwd_list_base<_Alloc>::
+ _M_erase_after(__base_pointer __pos)
+ -> __base_pointer
+ {
+ using __node_guard = __allocated_obj<_Node_alloc_type>;
+ __node_guard __n{_M_get_Node_allocator(), _S_node_ptr(__pos->_M_next)};
+ __pos->_M_next = __n->_M_next;
+ _Node_alloc_traits::destroy(_M_get_Node_allocator(), __n->_M_valptr());
return __pos->_M_next;
}
- template<typename _Tp, typename _Alloc>
- _Fwd_list_node_base*
- _Fwd_list_base<_Tp, _Alloc>::
- _M_erase_after(_Fwd_list_node_base* __pos,
- _Fwd_list_node_base* __last)
+ template<typename _Alloc>
+ auto
+ _Fwd_list_base<_Alloc>::
+ _M_erase_after(__base_pointer __pos, __base_pointer __last)
+ -> __base_pointer
{
- _Node* __curr = static_cast<_Node*>(__pos->_M_next);
+ using __node_guard = __allocated_obj<_Node_alloc_type>;
+ __base_pointer __curr = __pos->_M_next;
while (__curr != __last)
{
- _Node* __temp = __curr;
- __curr = static_cast<_Node*>(__curr->_M_next);
- _Tp_alloc_type __a(_M_get_Node_allocator());
- allocator_traits<_Tp_alloc_type>::destroy(__a, __temp->_M_valptr());
- __temp->~_Node();
- _M_put_node(__temp);
+ __node_guard __node{ _M_get_Node_allocator(), _S_node_ptr(__curr) };
+ __curr = __curr->_M_next;
+ _Node_alloc_traits::destroy(_M_get_Node_allocator(),
+ __node->_M_valptr());
}
__pos->_M_next = __last;
return __last;
@@ -115,7 +113,7 @@ _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_head();
for (; __first != __last; ++__first)
{
__to->_M_next = this->_M_create_node(*__first);
@@ -129,7 +127,7 @@ _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_head();
for (; __n; --__n)
{
__to->_M_next = this->_M_create_node(__value);
@@ -142,7 +140,7 @@ _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_head();
for (; __n; --__n)
{
__to->_M_next = this->_M_create_node();
@@ -236,9 +234,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_node->_M_mutable();
+ auto __b = __before._M_node->_M_mutable();
+ auto __end = __b;
while (__end && __end->_M_next != __last._M_node)
__end = __end->_M_next;
@@ -261,9 +259,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_node->_M_mutable();
+ __tmp->_M_transfer_after(__i._M_node->_M_mutable(),
+ __j._M_node->_M_mutable());
}
template<typename _Tp, typename _Alloc>
@@ -277,7 +275,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 iterator(__pos._M_node->_M_mutable());
}
template<typename _Tp, typename _Alloc>
@@ -291,7 +289,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 iterator(__pos._M_node->_M_mutable());
}
template<typename _Tp, typename _Alloc>
@@ -299,10 +297,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
forward_list<_Tp, _Alloc>::
remove(const _Tp& __val)
{
- _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
- _Node* __extra = 0;
+ auto __curr = this->_M_head();
+ decltype(__curr) __extra = nullptr;
- while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
+ while (auto __tmp = _Base::_S_node_ptr(__curr->_M_next))
{
if (*__tmp->_M_valptr() == __val)
{
@@ -314,7 +312,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
else
__extra = __curr;
}
- __curr = static_cast<_Node*>(__curr->_M_next);
+ __curr = __curr->_M_next;
}
if (__extra)
@@ -327,13 +325,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
forward_list<_Tp, _Alloc>::
remove_if(_Pred __pred)
{
- _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
- while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
+ auto __curr = this->_M_head();
+ while (auto __tmp = __curr->_M_next)
{
- if (__pred(*__tmp->_M_valptr()))
+ if (_S_apply(__pred, __tmp))
this->_M_erase_after(__curr);
else
- __curr = static_cast<_Node*>(__curr->_M_next);
+ __curr = __curr->_M_next;
}
}
@@ -364,21 +362,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
forward_list<_Tp, _Alloc>::
merge(forward_list&& __list, _Comp __comp)
{
- _Node_base* __node = &this->_M_impl._M_head;
+ auto __node = this->_M_head();
while (__node->_M_next && __list._M_impl._M_head._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 = __list._M_impl._M_head;
+ if (_S_apply(__comp, __l._M_next, __node->_M_next))
+ __node->_M_transfer_after(__list._M_head(), __l._M_next);
__node = __node->_M_next;
}
if (__list._M_impl._M_head._M_next)
{
__node->_M_next = __list._M_impl._M_head._M_next;
- __list._M_impl._M_head._M_next = 0;
+ __list._M_impl._M_head._M_next = nullptr;
}
}
@@ -410,8 +405,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
forward_list<_Tp, _Alloc>::
sort(_Comp __comp)
{
- // If `next' is 0, return immediately.
- _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
+ using __base_pointer = __ptr_rebind<pointer, _Node_base>;
+
+ // If `next' is null, return immediately.
+ __base_pointer __list = this->_M_impl._M_head._M_next;
if (!__list)
return;
@@ -419,9 +416,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
while (1)
{
- _Node* __p = __list;
- __list = 0;
- _Node* __tail = 0;
+ auto __p = __list;
+ __list = nullptr;
+ __base_pointer __tail = nullptr;
// Count number of merges we do in this pass.
unsigned long __nmerges = 0;
@@ -431,12 +428,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
++__nmerges;
// There exists a merge to be done.
// Step `insize' places along from p.
- _Node* __q = __p;
+ auto __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;
}
@@ -448,33 +445,33 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
while (__psize > 0 || (__qsize > 0 && __q))
{
// Decide whether next node of merge comes from p or q.
- _Node* __e;
+ decltype(__list) __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(*__p->_M_valptr(), *__q->_M_valptr()))
+ else if (_S_apply(__comp, __p, __q))
{
// First node of p is 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;
}
@@ -489,7 +486,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
// Now p has stepped `insize' places along, and q has too.
__p = __q;
}
- __tail->_M_next = 0;
+ __tail->_M_next = nullptr;
// If we have done only one merge, we're finished.
// Allow for nmerges == 0, the empty list case.
@@ -43,7 +43,7 @@ test01()
#endif
VERIFY( (fld.max_size()
- == std::allocator<_Fwd_list_node<double> >().max_size()) );
+ == std::allocator<_Fwd_list_node<double*> >().max_size()) );
}
int
@@ -27,7 +27,7 @@ void test01()
{
using namespace std;
using list = forward_list<int>;
- forward_list<list, scoped_allocator_adaptor<list::allocator_type>> l;
+ forward_list<list, scoped_allocator_adaptor<allocator<list>>> l;
// Check for forward_list(size_type, const allocator_type&)
l.emplace_front(1u);