Here is an updated version that compiles, I think, all your feedbacks.
It's much cleaner indeed.
It's also tested in C++98/17/23.
I'm surprised that we do not need to consider potential
allocator::const_pointer. Is there a plan to deprecate it ?
And if not, should not alloc traits const_pointer be per default a
rebind of pointer for const element_type like in the __add_const_to_ptr
you made me add ? I can try to work on a patch for that if needed.
libstdc++: Add fancy pointer support in map and set
Support fancy allocator pointer type in std::_Rb_tree<>.
In case of fancy pointer type the container is now storing the
pointer to
_Rb_tree_pnode<> as a pointer to _Rb_tree_pnode_base<>.
Many methods are adapted to take and return _Base_ptr in place of
_Link_type
which has been renamed into _Node_ptr.
libstdc++-v3/ChangeLog:
* include/bits/stl_tree.h
(__add_const_to_ptr<>): New.
(_Rb_tree_ptr_traits<>): New.
(_Rb_tree_pnode_base<>): New.
(_Rb_tree_node_base): Inherit from latter.
(_Rb_tree_pheader): New.
(_Rb_tree_header): Inherit from latter.
(_Rb_tree_node_val): New.
(_Rb_tree_node): Inherit from latter.
(_Rb_tree_pnode): New.
(_Rb_tree_iterator<>::_Link_type): Rename into...
(_Rb_tree_iterator<>::_Node_type): ...this.
(_Rb_tree_const_iterator<>::_Link_type): Rename into...
(_Rb_tree_const_iterator<>::_Node_type): ...this.
(_Rb_tree_const_iterator<>::_M_const_cast()): Adapt to use
_Rb_tree_pnode_base<>::_M_self_ptr_nc method.
(_Rb_tree_helpers<>): New.
(_Rb_tree_piterator): New.
(_Rb_tree_const_piterator): New.
(_Rb_tree_node_traits<>): New.
(_Rb_tree::_Node_base, _Rb_tree::_Node_type): New.
(_Rb_tree): Adapt to generalize usage of _Base_ptr in place
of _Link_type.
* testsuite/23_containers/map/allocator/ext_ptr.cc: New
test case.
* testsuite/23_containers/multimap/allocator/ext_ptr.cc:
New test case.
* testsuite/23_containers/multiset/allocator/ext_ptr.cc:
New test case.
* testsuite/23_containers/set/allocator/ext_ptr.cc: New
test case.
Ok to commit ?
François
On 09/10/2024 00:02, Jonathan Wakely wrote:
On Tue, 8 Oct 2024 at 22:50, Jonathan Wakely <jwakely....@gmail.com>
wrote:
On Thu, 1 Aug 2024 at 18:28, François Dumont
<frs.dum...@gmail.com> wrote:
Hi
Here is a proposal to add fancy pointer support in
std::_Rb_tree container.
As you'll see there are still several usages of
pointer_traits<>::pointer_to. The ones in _M_header_ptr() are
unavoidable.
Yes, those are necessary.
The pointer_to use in _M_const_cast could be simplified by adding
a _M_self_ptr() member to _Rb_tree_pnode_base:
_Base_ptr
_M_self_ptr() _GLIBCXX_NOEXCEPT
{ return pointer_traits<_Base_ptr>::pointer_to(*this); }
I don't think it's needed (because _M_const_cast is only in C++11
code, I think?) but you could define that for both C++11 and C++98:
#if __cplusplus
_Base_ptr
_M_self_ptr() noexcept
{ return pointer_traits<_Base_ptr>::pointer_to(*this); }
#else
_Base_ptr _M_self_ptr() { return this; }
#endif
Then this works for both (if you replace the 'auto'):
_Base_ptr
_M_self_ptr_nc() const _GLIBCXX_NOEXCEPT
{
auto __self = const_cast<_Rb_tree_pnode_base*>(this);
return __self->_M_self_ptr();
}
_Const_Base_ptr
_M_self_ptr() const _GLIBCXX_NOEXCEPT
{ return pointer_traits<_Const_Base_ptr>::pointer_to(*this); }
Then _M_const_cast would do:
return iterator(_M_node->_M_self_ptr_nc());
The ones to extract a node or to return a node to the
allocator are more questionable. Are they fine ? Is there
another way to
mimic the static_cast<_Link_type> that can be done on raw
pointers with
fancy pointers ?
I think you can just do
static_cast<_Link_type>(_M_node->_M_self_ptr()) i.e. convert the
_Base_ptr to the derived _Link_type
(we should really rename _Link_type to _Node_ptr, I keep getting
confused by the fact that the actual links between nodes are
_Base_ptr, so what does _Link_type mean now?!)
Alternatively, you could add a _M_node_ptr() to the
_Rb_tree_pnode_base type:
template<typename _NodeT>
__ptr_rebind<_BasePtr, _NodeT>
_M_node_ptr() _GLIBCXX_NOEXCEPT
{
auto __node = static_cast<_NodeT*>(this);
using _Node_ptr = __ptr_rebind<_BasePtr, _NodeT>;
return pointer_traits<_Node_ptr>::pointer_to(*__node);
}
You could add a C++98 version of this as well:
#if __cplusplus >= 201103L
// as above
#else
template<typename _NodeT>
_NodeT*
_M_node_ptr() _GLIBCXX_NOEXCEPT
{ return static_cast<_Node*>(this); }
#endif
Then the code to deallocate the node would not need to use #if:
_Link_type __np = __p->template _M_node_ptr<_Node_type>();
_Alloc_traits::deallocate(_M_get_Node_allocator(), __np, 1);
Then:
auto __np = __p->template _M_node_ptr<_Node_type>()
_Alloc_traits::deallocate(_M_get_Node_allocator(), __np, 1);
Some more general comments:
_Rb_tree_pnode_base and the iterators could just take one template
argument, and use __ptr_rebind to get the const pointer from the
non-const pointer. We can add a helper to do that:
template<typename _Ptr> struct __add_const_to_ptr;
#if __cplusplus >= 201103L
template<typename _Ptr>
using __add_const_to_ptr = __ptr_rebind<_Ptr, const typename
pointer_traits<_Ptr>::element_type>;
#else
template<typename _Ptr> struct __add_const_to_ptr;
template<typename _Tp>
struct __add_const_to_ptr<_Tp*>
{ typedef const _Tp* __type; };
#endif
This will let you get the FooCPtr type from the FooPtr type.
A traits class could replace all the __conditional_t uses:
#if __cplusplus >= 201103L
template<typename _ValPtr>
struct _Rb_tree_node_traits
{
using _Base = _Rb_tree_pnode_base<_ValPtr>;
using _Node_type = _Rb_tree_pnode<_ValPtr>;
using _Base_ptr = __ptr_rebind<_ValPtr, _Base>;
using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
using iterator = _Rb_tree_piterator<_ValPtr>;
using const_iterator = _Rb_tree_const_piterator<_ValPtr>;
};
#else
template<typename _ValPtr>
struct _Rb_tree_node_traits;
#endif
template<typename _Val>
struct _Rb_tree_node_traits<_Val*>
{
typedef _Rb_tree_node_base _Base;
typedef _Rb_tree_node<_Val> _Node_type;
typedef _Base* _Base_ptr;
typedef _Node* _Node_ptr;
typedef _Rb_tree_iterator<_Val> iterator;
typedef _Rb_tree_const_iterator<_Val> const_iterator;
};
I think this would get rid of a lot of the #if checks and the
__conditional_t uses.
Otherwise this looks really good, nice work!
A solution to this (potential) issue would be to:
1. Store _Node_type pointer in the data structure rather than
_Node_base
pointer. But then _Rb_tree_pheader _M_left/_M_right could not be
initialized with a pointer to _M_parent which is only a
_Node_base
instance. We would then need to init it to nullptr but I
haven't check
impact on code and more importantly it would be an abi
breaking change.
2. Still store _Node_type pointer in the data structure but
then make
_M_header a _Node_type instance. In this case memory area of the
value_type would just be lost bytes.
libstdc++: Add fancy pointer support in std::[multi][map/set]
Let's just say "maps and sets" or "RB trees" instead of the more
cryptic std::[multi][map/set].
Support fancy allocator pointer type in std::_Rb_tree<>.
In case of fancy pointer type the container is now
storing the
pointer to
_Rb_tree_pnode<> as a pointer to _Rb_tree_pnode_base<>.
Many methods are adapted to take and return _Base_ptr in
place of
_Link_type.
libstdc++-v3/ChangeLog:
* include/bits/stl_tree.h
(_Rb_tree_pnode_base<>): New.
(_Rb_tree_node_base): Inherit from latter.
(_Rb_tree_pheader): New.
(_Rb_tree_header): Inherit from latter.
(_Rb_tree_node_val): New.
(_Rb_tree_node): Inherit from latter.
(_Rb_tree_pnode): New.
(_Rb_tree_helpers): New.
(_Rb_tree_piterator): New.
(_Rb_tree_const_piterator): New.
(_Rb_tree::_Node_base, _Rb_tree::_Node_type): New.
(_Rb_tree): Adapt to generalize usage of
_Base_ptr in place
of _Link_type.
*
testsuite/23_containers/map/allocator/ext_ptr.cc: New
test case.
*
testsuite/23_containers/multimap/allocator/ext_ptr.cc:
New test case.
*
testsuite/23_containers/multiset/allocator/ext_ptr.cc:
New test case.
*
testsuite/23_containers/set/allocator/ext_ptr.cc: New
test case.
Tested under Linux x64.
François
diff --git a/libstdc++-v3/include/bits/stl_tree.h
b/libstdc++-v3/include/bits/stl_tree.h
index bc27e191e8b..6ea7aa54750 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -96,10 +96,97 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
enum _Rb_tree_color { _S_red = false, _S_black = true };
- struct _Rb_tree_node_base
+#if __cplusplus >= 201103L
+ template<typename _Ptr>
+ struct __add_const_to_ptr
+ {
+ using __type =
+ __ptr_rebind<_Ptr, const typename pointer_traits<_Ptr>::element_type>;
+ };
+#else
+ template<typename _Ptr>
+ struct __add_const_to_ptr;
+#endif
+
+ template<typename _Tp>
+ struct __add_const_to_ptr<_Tp*>
+ { typedef const _Tp* __type; };
+
+#if __cplusplus >= 201103L
+ template<typename _Ptr>
+ struct _Rb_tree_ptr_traits
+ {
+ template<typename _Tp>
+ struct __rebind
+ { using __type = __ptr_rebind<_Ptr, _Tp>; };
+
+ template<typename _BasePtr>
+ static _Ptr
+ _S_ptr_to(_BasePtr __this) noexcept
+ { return pointer_traits<_Ptr>::pointer_to(*__this); }
+
+ template<typename _BasePtr, typename _UpPtr>
+ static _UpPtr
+ _S_up_ptr_to(_BasePtr __this) noexcept
+ {
+ using __ptr_traits = pointer_traits<_UpPtr>;
+ using __up_type = typename __ptr_traits::element_type;
+ auto __up_this = static_cast<__up_type*>(__this);
+ return __ptr_traits::pointer_to(*__up_this);
+ }
+ };
+#else
+ template<typename _Ptr>
+ struct _Rb_tree_ptr_traits;
+#endif
+
+ template<typename _Tp>
+ struct _Rb_tree_ptr_traits<_Tp*>
+ {
+ template<typename>
+ struct __rebind
+ { typedef _Tp* __type; };
+
+ template<typename _BasePtr>
+ static _Tp*
+ _S_ptr_to(_BasePtr __this) _GLIBCXX_NOEXCEPT
+ { return static_cast<_Tp*>(__this); }
+
+ template<typename _BasePtr, typename _UpPtr>
+ static _UpPtr
+ _S_up_ptr_to(_BasePtr __this) _GLIBCXX_NOEXCEPT
+ { return static_cast<_UpPtr>(__this); }
+ };
+
+ template<typename _BasePtr>
+ struct _Rb_tree_pnode_base
+ {
+ typedef typename _Rb_tree_ptr_traits<_BasePtr>::template
+ __rebind<_Rb_tree_pnode_base>::__type _Base_ptr;
+ typedef typename __add_const_to_ptr<_Base_ptr>::__type _Const_Base_ptr;
+
+ _Base_ptr
+ _M_self_ptr() _GLIBCXX_NOEXCEPT
+ { return _Rb_tree_ptr_traits<_Base_ptr>::_S_ptr_to(this); }
+
+ _Const_Base_ptr
+ _M_self_ptr() const _GLIBCXX_NOEXCEPT
+ { return _Rb_tree_ptr_traits<_Const_Base_ptr>::_S_ptr_to(this); }
+
+ _Base_ptr
+ _M_self_ptr_nc() const _GLIBCXX_NOEXCEPT
+ {
+ _Rb_tree_pnode_base* __self = const_cast<_Rb_tree_pnode_base*>(this);
+ return __self->_M_self_ptr();
+ }
+
+ template<typename _NodePtr>
+ _NodePtr
+ _M_node_ptr() _GLIBCXX_NOEXCEPT
{
- typedef _Rb_tree_node_base* _Base_ptr;
- typedef const _Rb_tree_node_base* _Const_Base_ptr;
+ return _Rb_tree_ptr_traits<_Base_ptr>::template
+ _S_up_ptr_to<_Rb_tree_pnode_base*, _NodePtr>(this);
+ }
_Rb_tree_color _M_color;
_Base_ptr _M_parent;
@@ -109,32 +196,36 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
static _Base_ptr
_S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
{
- while (__x->_M_left != 0) __x = __x->_M_left;
+ while (__x->_M_left) __x = __x->_M_left;
return __x;
}
static _Const_Base_ptr
_S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
{
- while (__x->_M_left != 0) __x = __x->_M_left;
+ while (__x->_M_left) __x = __x->_M_left;
return __x;
}
static _Base_ptr
_S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
{
- while (__x->_M_right != 0) __x = __x->_M_right;
+ while (__x->_M_right) __x = __x->_M_right;
return __x;
}
static _Const_Base_ptr
_S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
{
- while (__x->_M_right != 0) __x = __x->_M_right;
+ while (__x->_M_right) __x = __x->_M_right;
return __x;
}
};
+ struct _Rb_tree_node_base
+ : _Rb_tree_pnode_base<_Rb_tree_node_base*>
+ { };
+
// Helper type offering value initialization guarantee on the compare
functor.
template<typename _Key_compare>
struct _Rb_tree_key_compare
@@ -163,21 +254,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
};
// Helper type to manage default initialization of node count and header.
- struct _Rb_tree_header
+ template<typename _NodeBase>
+ struct _Rb_tree_pheader
{
- _Rb_tree_node_base _M_header;
+ private:
+ typedef typename _NodeBase::_Base_ptr _Base_ptr;
+ typedef typename _NodeBase::_Const_Base_ptr _Const_Base_ptr;
+
+ public:
+ _NodeBase _M_header;
size_t _M_node_count; // Keeps track of size of tree.
- _Rb_tree_header() _GLIBCXX_NOEXCEPT
+ _Rb_tree_pheader() _GLIBCXX_NOEXCEPT
{
_M_header._M_color = _S_red;
_M_reset();
}
#if __cplusplus >= 201103L
- _Rb_tree_header(_Rb_tree_header&& __x) noexcept
+ _Rb_tree_pheader(_Rb_tree_pheader&& __x) noexcept
{
- if (__x._M_header._M_parent != nullptr)
+ if (__x._M_header._M_parent)
_M_move_data(__x);
else
{
@@ -188,13 +285,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#endif
void
- _M_move_data(_Rb_tree_header& __from)
+ _M_move_data(_Rb_tree_pheader& __from)
{
_M_header._M_color = __from._M_header._M_color;
_M_header._M_parent = __from._M_header._M_parent;
_M_header._M_left = __from._M_header._M_left;
_M_header._M_right = __from._M_header._M_right;
- _M_header._M_parent->_M_parent = &_M_header;
+ _M_header._M_parent->_M_parent = _M_header._M_self_ptr();
_M_node_count = __from._M_node_count;
__from._M_reset();
@@ -203,41 +300,65 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
_M_reset()
{
- _M_header._M_parent = 0;
- _M_header._M_left = &_M_header;
- _M_header._M_right = &_M_header;
+ _M_header._M_parent = _Base_ptr();
+ _M_header._M_left = _M_header._M_right = _M_header._M_self_ptr();
_M_node_count = 0;
}
};
+ struct _Rb_tree_header : _Rb_tree_pheader<_Rb_tree_node_base>
+ { };
+
template<typename _Val>
- struct _Rb_tree_node : public _Rb_tree_node_base
+ struct _Rb_tree_node_val
{
- typedef _Rb_tree_node<_Val>* _Link_type;
-
#if __cplusplus < 201103L
_Val _M_value_field;
+ __attribute__((__always_inline__))
_Val*
_M_valptr()
{ return std::__addressof(_M_value_field); }
+ __attribute__((__always_inline__))
const _Val*
_M_valptr() const
{ return std::__addressof(_M_value_field); }
#else
__gnu_cxx::__aligned_membuf<_Val> _M_storage;
+ [[__gnu__::__always_inline__]]
_Val*
_M_valptr()
{ return _M_storage._M_ptr(); }
+ [[__gnu__::__always_inline__]]
const _Val*
_M_valptr() const
{ return _M_storage._M_ptr(); }
#endif
};
+ template<typename _Val>
+ struct _Rb_tree_node
+ : _Rb_tree_node_base
+ , _Rb_tree_node_val<_Val>
+ {
+ typedef _Rb_tree_node<_Val>* _Node_ptr;
+ typedef const _Rb_tree_node<_Val>* _Const_Node_ptr;
+ };
+
+#if __cplusplus >= 201103L
+ template<typename _ValPtr>
+ struct _Rb_tree_pnode
+ : _Rb_tree_pnode_base<_ValPtr>
+ , _Rb_tree_node_val<typename std::pointer_traits<_ValPtr>::element_type>
+ {
+ using _Node_ptr = __ptr_rebind<_ValPtr, _Rb_tree_pnode>;
+ using _Const_Node_ptr = typename __add_const_to_ptr<_Node_ptr>::__type;
+ };
+#endif
+
_GLIBCXX_PURE _Rb_tree_node_base*
_Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
@@ -250,6 +371,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_GLIBCXX_PURE const _Rb_tree_node_base*
_Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
+ __attribute__((__nonnull__))
+ void
+ _Rb_tree_insert_and_rebalance(const bool __insert_left,
+ _Rb_tree_node_base* __x,
+ _Rb_tree_node_base* __p,
+ _Rb_tree_node_base& __header) throw ();
+
+ __attribute__((__nonnull__,__returns_nonnull__))
+ _Rb_tree_node_base*
+ _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
+ _Rb_tree_node_base& __header) throw ();
+
template<typename _Tp>
struct _Rb_tree_iterator
{
@@ -261,8 +394,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typedef ptrdiff_t difference_type;
typedef _Rb_tree_iterator<_Tp> _Self;
- typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
- typedef _Rb_tree_node<_Tp>* _Link_type;
+ typedef typename _Rb_tree_node_base::_Base_ptr _Base_ptr;
+ typedef _Rb_tree_node<_Tp>* _Node_ptr;
_Rb_tree_iterator() _GLIBCXX_NOEXCEPT
: _M_node() { }
@@ -273,11 +406,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
reference
operator*() const _GLIBCXX_NOEXCEPT
- { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
+ { return *static_cast<_Node_ptr>(_M_node)->_M_valptr(); }
pointer
operator->() const _GLIBCXX_NOEXCEPT
- { return static_cast<_Link_type> (_M_node)->_M_valptr(); }
+ { return static_cast<_Node_ptr>(_M_node)->_M_valptr(); }
_Self&
operator++() _GLIBCXX_NOEXCEPT
@@ -335,8 +468,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typedef ptrdiff_t difference_type;
typedef _Rb_tree_const_iterator<_Tp> _Self;
- typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
- typedef const _Rb_tree_node<_Tp>* _Link_type;
+ typedef typename _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
+ typedef const _Rb_tree_node<_Tp>*
_Node_ptr;
_Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
: _M_node() { }
@@ -350,15 +483,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator
_M_const_cast() const _GLIBCXX_NOEXCEPT
- { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
+ { return iterator(_M_node->_M_self_ptr_nc()); }
reference
operator*() const _GLIBCXX_NOEXCEPT
- { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
+ { return *static_cast<_Node_ptr>(_M_node)->_M_valptr(); }
pointer
operator->() const _GLIBCXX_NOEXCEPT
- { return static_cast<_Link_type>(_M_node)->_M_valptr(); }
+ { return static_cast<_Node_ptr>(_M_node)->_M_valptr(); }
_Self&
operator++() _GLIBCXX_NOEXCEPT
@@ -403,17 +536,641 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Base_ptr _M_node;
};
+#if __cplusplus >= 201103L
+ template<typename _NodeBase>
+ struct _Rb_tree_helpers
+ {
+ using _Base_ptr = typename _NodeBase::_Base_ptr;
+ using _Const_Base_ptr = typename _NodeBase::_Const_Base_ptr;
+
+ static _Base_ptr
+ _S_minimum(_Base_ptr __x)
+ { return _NodeBase::_S_minimum(__x); }
+
+ static _Const_Base_ptr
+ _S_minimum(_Const_Base_ptr __x)
+ { return _NodeBase::_S_minimum(__x); }
+
+ static _Base_ptr
+ _S_maximum(_Base_ptr __x)
+ { return _NodeBase::_S_maximum(__x); }
+
+ static _Const_Base_ptr
+ _S_maximum(_Const_Base_ptr __x)
+ { return _NodeBase::_S_maximum(__x); }
+
+ static _Base_ptr
+ _Increment(_Base_ptr __x) noexcept
+ {
+ if (__x->_M_right)
+ {
+ __x = __x->_M_right;
+ while (__x->_M_left)
+ __x = __x->_M_left;
+ }
+ else
+ {
+ _Base_ptr __y = __x->_M_parent;
+ while (__x == __y->_M_right)
+ {
+ __x = __y;
+ __y = __y->_M_parent;
+ }
+ if (__x->_M_right != __y)
+ __x = __y;
+ }
+ return __x;
+ }
+
+ static _Const_Base_ptr
+ _Increment(_Const_Base_ptr __x) noexcept
+ {
+ if (__x->_M_right)
+ {
+ __x = __x->_M_right;
+ while (__x->_M_left)
+ __x = __x->_M_left;
+ }
+ else
+ {
+ _Const_Base_ptr __y = __x->_M_parent;
+ while (__x == __y->_M_right)
+ {
+ __x = __y;
+ __y = __y->_M_parent;
+ }
+ if (__x->_M_right != __y)
+ __x = __y;
+ }
+ return __x;
+ }
+
+ static _Base_ptr
+ _Decrement(_Base_ptr __x) noexcept
+ {
+ if (__x->_M_color == _S_red
+ && __x->_M_parent->_M_parent == __x)
+ __x = __x->_M_right;
+ else if (__x->_M_left)
+ {
+ _Base_ptr __y = __x->_M_left;
+ while (__y->_M_right)
+ __y = __y->_M_right;
+ __x = __y;
+ }
+ else
+ {
+ _Base_ptr __y = __x->_M_parent;
+ while (__x == __y->_M_left)
+ {
+ __x = __y;
+ __y = __y->_M_parent;
+ }
+ __x = __y;
+ }
+ return __x;
+ }
+
+ static _Const_Base_ptr
+ _Decrement(_Const_Base_ptr __x) noexcept
+ {
+ if (__x->_M_color == _S_red
+ && __x->_M_parent->_M_parent == __x)
+ __x = __x->_M_right;
+ else if (__x->_M_left)
+ {
+ _Const_Base_ptr __y = __x->_M_left;
+ while (__y->_M_right)
+ __y = __y->_M_right;
+ __x = __y;
+ }
+ else
+ {
+ _Const_Base_ptr __y = __x->_M_parent;
+ while (__x == __y->_M_left)
+ {
+ __x = __y;
+ __y = __y->_M_parent;
+ }
+ __x = __y;
+ }
+ return __x;
+ }
+
+ static void
+ _Rotate_left(_Base_ptr __x, _Base_ptr& __root)
+ {
+ const _Base_ptr __y = __x->_M_right;
+
+ __x->_M_right = __y->_M_left;
+ if (__y->_M_left)
+ __y->_M_left->_M_parent = __x;
+ __y->_M_parent = __x->_M_parent;
+
+ if (__x == __root)
+ __root = __y;
+ else if (__x == __x->_M_parent->_M_left)
+ __x->_M_parent->_M_left = __y;
+ else
+ __x->_M_parent->_M_right = __y;
+ __y->_M_left = __x;
+ __x->_M_parent = __y;
+ }
+
+ static void
+ _Rotate_right(_Base_ptr __x, _Base_ptr& __root)
+ {
+ const _Base_ptr __y = __x->_M_left;
+
+ __x->_M_left = __y->_M_right;
+ if (__y->_M_right)
+ __y->_M_right->_M_parent = __x;
+ __y->_M_parent = __x->_M_parent;
+
+ if (__x == __root)
+ __root = __y;
+ else if (__x == __x->_M_parent->_M_right)
+ __x->_M_parent->_M_right = __y;
+ else
+ __x->_M_parent->_M_left = __y;
+ __y->_M_right = __x;
+ __x->_M_parent = __y;
+ }
+
+ static void
+ _S_insert_and_rebalance(const bool __insert_left,
+ _Base_ptr __x, _Base_ptr __p,
+ _NodeBase& __header)
+ {
+ _Base_ptr& __root = __header._M_parent;
+
+ // Initialize fields in new node to insert.
+ __x->_M_parent = __p;
+ __x->_M_left = __x->_M_right = nullptr;
+ __x->_M_color = _S_red;
+
+ // Insert.
+ // Make new node child of parent and maintain root, leftmost and
+ // rightmost nodes.
+ // N.B. First node is always inserted left.
+ if (__insert_left)
+ {
+ __p->_M_left = __x; // also makes leftmost = __x when __p ==
&__header
+
+ if (std::__to_address(__p) == std::addressof(__header))
+ {
+ __header._M_parent = __x;
+ __header._M_right = __x;
+ }
+ else if (__p == __header._M_left)
+ __header._M_left = __x; // maintain leftmost pointing to min node
+ }
+ else
+ {
+ __p->_M_right = __x;
+
+ if (__p == __header._M_right)
+ __header._M_right = __x; // maintain rightmost pointing to max
node
+ }
+ // Rebalance.
+ while (__x != __root
+ && __x->_M_parent->_M_color == _S_red)
+ {
+ const _Base_ptr __xpp = __x->_M_parent->_M_parent;
+
+ if (__x->_M_parent == __xpp->_M_left)
+ {
+ const _Base_ptr __y = __xpp->_M_right;
+ if (__y && __y->_M_color == _S_red)
+ {
+ __x->_M_parent->_M_color = _S_black;
+ __y->_M_color = _S_black;
+ __xpp->_M_color = _S_red;
+ __x = __xpp;
+ }
+ else
+ {
+ if (__x == __x->_M_parent->_M_right)
+ {
+ __x = __x->_M_parent;
+ _Rotate_left(__x, __root);
+ }
+ __x->_M_parent->_M_color = _S_black;
+ __xpp->_M_color = _S_red;
+ _Rotate_right(__xpp, __root);
+ }
+ }
+ else
+ {
+ const _Base_ptr __y = __xpp->_M_left;
+ if (__y && __y->_M_color == _S_red)
+ {
+ __x->_M_parent->_M_color = _S_black;
+ __y->_M_color = _S_black;
+ __xpp->_M_color = _S_red;
+ __x = __xpp;
+ }
+ else
+ {
+ if (__x == __x->_M_parent->_M_left)
+ {
+ __x = __x->_M_parent;
+ _Rotate_right(__x, __root);
+ }
+ __x->_M_parent->_M_color = _S_black;
+ __xpp->_M_color = _S_red;
+ _Rotate_left(__xpp, __root);
+ }
+ }
+ }
+ __root->_M_color = _S_black;
+ }
+
+ static _Base_ptr
+ _S_rebalance_for_erase(_Base_ptr __z, _NodeBase& __header)
+ {
+ _Base_ptr& __root = __header._M_parent;
+ _Base_ptr& __leftmost = __header._M_left;
+ _Base_ptr& __rightmost = __header._M_right;
+ _Base_ptr __y = __z;
+ _Base_ptr __x{};
+ _Base_ptr __x_parent{};
+
+ if (!__y->_M_left) // __z has at most one non-null child. y == z.
+ __x = __y->_M_right; // __x might be null.
+ else
+ if (!__y->_M_right) // __z has exactly one non-null child. y == z.
+ __x = __y->_M_left; // __x is not null.
+ else
+ {
+ // __z has two non-null children. Set __y to
+ __y = __y->_M_right; // __z's successor. __x might be null.
+ while (__y->_M_left)
+ __y = __y->_M_left;
+ __x = __y->_M_right;
+ }
+ if (__y != __z)
+ {
+ // relink y in place of z. y is z's successor
+ __z->_M_left->_M_parent = __y;
+ __y->_M_left = __z->_M_left;
+ if (__y != __z->_M_right)
+ {
+ __x_parent = __y->_M_parent;
+ if (__x)
+ __x->_M_parent = __y->_M_parent;
+ __y->_M_parent->_M_left = __x; // __y must be a child of
_M_left
+ __y->_M_right = __z->_M_right;
+ __z->_M_right->_M_parent = __y;
+ }
+ else
+ __x_parent = __y;
+ if (__root == __z)
+ __root = __y;
+ else if (__z->_M_parent->_M_left == __z)
+ __z->_M_parent->_M_left = __y;
+ else
+ __z->_M_parent->_M_right = __y;
+ __y->_M_parent = __z->_M_parent;
+ std::swap(__y->_M_color, __z->_M_color);
+ __y = __z;
+ // __y now points to node to be actually deleted
+ }
+ else
+ { // __y == __z
+ __x_parent = __y->_M_parent;
+ if (__x)
+ __x->_M_parent = __y->_M_parent;
+ if (__root == __z)
+ __root = __x;
+ else
+ if (__z->_M_parent->_M_left == __z)
+ __z->_M_parent->_M_left = __x;
+ else
+ __z->_M_parent->_M_right = __x;
+ if (__leftmost == __z)
+ {
+ if (!__z->_M_right) // __z->_M_left must be null also
+ __leftmost = __z->_M_parent;
+ // makes __leftmost == _M_header if __z == __root
+ else
+ __leftmost = _S_minimum(__x);
+ }
+ if (__rightmost == __z)
+ {
+ if (__z->_M_left == 0) // __z->_M_right must be null
also
+ __rightmost = __z->_M_parent;
+ // makes __rightmost == _M_header if __z == __root
+ else // __x == __z->_M_left
+ __rightmost = _S_maximum(__x);
+ }
+ }
+ if (__y->_M_color != _S_red)
+ {
+ while (__x != __root && (__x == 0 || __x->_M_color == _S_black))
+ if (__x == __x_parent->_M_left)
+ {
+ _Base_ptr __w = __x_parent->_M_right;
+ if (__w->_M_color == _S_red)
+ {
+ __w->_M_color = _S_black;
+ __x_parent->_M_color = _S_red;
+ _Rotate_left(__x_parent, __root);
+ __w = __x_parent->_M_right;
+ }
+ if ((!__w->_M_left || __w->_M_left->_M_color == _S_black) &&
+ (!__w->_M_right || __w->_M_right->_M_color == _S_black))
+ {
+ __w->_M_color = _S_red;
+ __x = __x_parent;
+ __x_parent = __x_parent->_M_parent;
+ }
+ else
+ {
+ if (!__w->_M_right || __w->_M_right->_M_color == _S_black)
+ {
+ __w->_M_left->_M_color = _S_black;
+ __w->_M_color = _S_red;
+ _Rotate_right(__w, __root);
+ __w = __x_parent->_M_right;
+ }
+ __w->_M_color = __x_parent->_M_color;
+ __x_parent->_M_color = _S_black;
+ if (__w->_M_right)
+ __w->_M_right->_M_color = _S_black;
+ _Rotate_left(__x_parent, __root);
+ break;
+ }
+ }
+ else
+ {
+ // same as above, with _M_right <-> _M_left.
+ _Base_ptr __w = __x_parent->_M_left;
+ if (__w->_M_color == _S_red)
+ {
+ __w->_M_color = _S_black;
+ __x_parent->_M_color = _S_red;
+ _Rotate_right(__x_parent, __root);
+ __w = __x_parent->_M_left;
+ }
+ if ((!__w->_M_right || __w->_M_right->_M_color == _S_black) &&
+ (!__w->_M_left || __w->_M_left->_M_color == _S_black))
+ {
+ __w->_M_color = _S_red;
+ __x = __x_parent;
+ __x_parent = __x_parent->_M_parent;
+ }
+ else
+ {
+ if (!__w->_M_left || __w->_M_left->_M_color == _S_black)
+ {
+ __w->_M_right->_M_color = _S_black;
+ __w->_M_color = _S_red;
+ _Rotate_left(__w, __root);
+ __w = __x_parent->_M_left;
+ }
+ __w->_M_color = __x_parent->_M_color;
+ __x_parent->_M_color = _S_black;
+ if (__w->_M_left)
+ __w->_M_left->_M_color = _S_black;
+ _Rotate_right(__x_parent, __root);
+ break;
+ }
+ }
+ if (__x)
+ __x->_M_color = _S_black;
+ }
+
+ return __y;
+ }
+ };
+#else
+ template<typename _NodeBase>
+ struct _Rb_tree_helpers;
+#endif
+
+ template<>
+ struct _Rb_tree_helpers<_Rb_tree_node_base>
+ {
+ static _Rb_tree_node_base*
+ _S_minimum(_Rb_tree_node_base* __x) _GLIBCXX_NOEXCEPT
+ { return _Rb_tree_node_base::_S_minimum(__x); }
+
+ static const _Rb_tree_node_base*
+ _S_minimum(const _Rb_tree_node_base* __x) _GLIBCXX_NOEXCEPT
+ { return _Rb_tree_node_base::_S_minimum(__x); }
+
+ static _Rb_tree_node_base*
+ _S_maximum(_Rb_tree_node_base* __x) _GLIBCXX_NOEXCEPT
+ { return _Rb_tree_node_base::_S_maximum(__x); }
+
+ static const _Rb_tree_node_base*
+ _S_maximum(const _Rb_tree_node_base* __x) _GLIBCXX_NOEXCEPT
+ { return _Rb_tree_node_base::_S_maximum(__x); }
+
__attribute__((__nonnull__))
- void
- _Rb_tree_insert_and_rebalance(const bool __insert_left,
- _Rb_tree_node_base* __x,
- _Rb_tree_node_base* __p,
- _Rb_tree_node_base& __header) throw ();
+ static void
+ _S_insert_and_rebalance(const bool __insert_left,
+ _Rb_tree_node_base* __x, _Rb_tree_node_base* __p,
+ _Rb_tree_node_base& __header) throw ()
+ {
+ return _Rb_tree_insert_and_rebalance(__insert_left, __x, __p, __header);
+ }
- __attribute__((__nonnull__,__returns_nonnull__))
- _Rb_tree_node_base*
- _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
- _Rb_tree_node_base& __header) throw ();
+ __attribute__((__nonnull__))
+ static _Rb_tree_node_base*
+ _S_rebalance_for_erase(_Rb_tree_node_base* const __z,
+ _Rb_tree_node_base& __header) throw ()
+ { return _Rb_tree_rebalance_for_erase(__z, __header); }
+ };
+
+#if __cplusplus >= 201103L
+ template<typename _ValPtr>
+ struct _Rb_tree_piterator
+ {
+ using __ptr_traits = pointer_traits<_ValPtr>;
+ using value_type = typename __ptr_traits::element_type;
+ using reference = value_type&;
+ using pointer = value_type*;
+
+ typedef bidirectional_iterator_tag iterator_category;
+ typedef ptrdiff_t difference_type;
+
+ typedef _Rb_tree_piterator _Self;
+ typedef _Rb_tree_pnode_base<_ValPtr> _Node_base;
+ typedef _Rb_tree_pnode<_ValPtr> _Node_type;
+ typedef typename _Node_type::_Base_ptr _Base_ptr;
+ typedef typename _Node_type::_Node_ptr _Node_ptr;
+ typedef _Rb_tree_helpers<_Node_base> _Tree_helpers;
+
+ _Rb_tree_piterator() _GLIBCXX_NOEXCEPT
+ : _M_node() { }
+
+ explicit
+ _Rb_tree_piterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
+ : _M_node(__x) { }
+
+ reference
+ operator*() const _GLIBCXX_NOEXCEPT
+ { return *static_cast<_Node_type&>(*_M_node)._M_valptr(); }
+
+ pointer
+ operator->() const _GLIBCXX_NOEXCEPT
+ { return static_cast<_Node_type&>(*_M_node)._M_valptr(); }
+
+ _Self&
+ operator++() _GLIBCXX_NOEXCEPT
+ {
+ _M_node = _Tree_helpers::_Increment(_M_node);
+ return *this;
+ }
+
+ _Self
+ operator++(int) _GLIBCXX_NOEXCEPT
+ {
+ _Self __tmp = *this;
+ _M_node = _Tree_helpers::_Increment(_M_node);
+ return __tmp;
+ }
+
+ _Self&
+ operator--() _GLIBCXX_NOEXCEPT
+ {
+ _M_node = _Tree_helpers::_Decrement(_M_node);
+ return *this;
+ }
+
+ _Self
+ operator--(int) _GLIBCXX_NOEXCEPT
+ {
+ _Self __tmp = *this;
+ _M_node = _Tree_helpers::_Decrement(_M_node);
+ return __tmp;
+ }
+
+ friend bool
+ operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
+ { return __x._M_node == __y._M_node; }
+
+#if ! __cpp_lib_three_way_comparison
+ friend bool
+ operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
+ { return __x._M_node != __y._M_node; }
+#endif
+
+ _Base_ptr _M_node;
+ };
+
+ template<typename _ValPtr>
+ struct _Rb_tree_const_piterator
+ {
+ using __ptr_traits = pointer_traits<_ValPtr>;
+ using value_type = typename __ptr_traits::element_type;
+ using reference = const value_type&;
+ using pointer = const value_type*;
+
+ typedef _Rb_tree_piterator<_ValPtr> iterator;
+ typedef typename iterator::_Base_ptr _Base_ptr;
+
+ typedef bidirectional_iterator_tag iterator_category;
+ typedef ptrdiff_t difference_type;
+
+ typedef _Rb_tree_const_piterator _Self;
+ typedef _Rb_tree_pnode_base<_ValPtr> _Node_base;
+ typedef _Rb_tree_pnode<_ValPtr> _Node_type;
+ typedef typename _Node_type::_Const_Base_ptr _Const_Base_ptr;
+ typedef _Rb_tree_helpers<_Node_base> _Tree_helpers;
+
+ _Rb_tree_const_piterator() _GLIBCXX_NOEXCEPT
+ : _M_node() { }
+
+ explicit
+ _Rb_tree_const_piterator(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
+ : _M_node(__x) { }
+
+ _Rb_tree_const_piterator(const iterator& __it) _GLIBCXX_NOEXCEPT
+ : _M_node(__it._M_node) { }
+
+ iterator
+ _M_const_cast() const _GLIBCXX_NOEXCEPT
+ { return iterator(_M_node->_M_self_ptr_nc()); }
+
+ reference
+ operator*() const _GLIBCXX_NOEXCEPT
+ { return *static_cast<const _Node_type&>(*_M_node)._M_valptr(); }
+
+ pointer
+ operator->() const _GLIBCXX_NOEXCEPT
+ { return static_cast<const _Node_type&>(*_M_node)._M_valptr(); }
+
+ _Self&
+ operator++() _GLIBCXX_NOEXCEPT
+ {
+ _M_node = _Tree_helpers::_Increment(_M_node);
+ return *this;
+ }
+
+ _Self
+ operator++(int) _GLIBCXX_NOEXCEPT
+ {
+ _Self __tmp = *this;
+ _M_node = _Tree_helpers::_Increment(_M_node);
+ return __tmp;
+ }
+
+ _Self&
+ operator--() _GLIBCXX_NOEXCEPT
+ {
+ _M_node = _Tree_helpers::_Decrement(_M_node);
+ return *this;
+ }
+
+ _Self
+ operator--(int) _GLIBCXX_NOEXCEPT
+ {
+ _Self __tmp = *this;
+ _M_node = _Tree_helpers::_Decrement(_M_node);
+ return __tmp;
+ }
+
+ friend bool
+ operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
+ { return __x._M_node == __y._M_node; }
+
+#if ! __cpp_lib_three_way_comparison
+ friend bool
+ operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
+ { return __x._M_node != __y._M_node; }
+#endif
+
+ _Const_Base_ptr _M_node;
+ };
+#endif // C++11
+
+#if __cplusplus >= 201103L
+ template<typename _ValPtr>
+ struct _Rb_tree_node_traits
+ {
+ using _Node_base = _Rb_tree_pnode_base<_ValPtr>;
+ using _Node_type = _Rb_tree_pnode<_ValPtr>;
+ using _Header_t = _Rb_tree_pheader<_Node_base>;
+ using _Iterator_t = _Rb_tree_piterator<_ValPtr>;
+ using _Const_iterator_t = _Rb_tree_const_piterator<_ValPtr>;
+ };
+#else
+ template<typename _ValPtr>
+ struct _Rb_tree_node_traits;
+#endif
+
+ template<typename _Val>
+ struct _Rb_tree_node_traits<_Val*>
+ {
+ typedef _Rb_tree_node_base _Node_base;
+ typedef _Rb_tree_node<_Val> _Node_type;
+ typedef _Rb_tree_header _Header_t;
+ typedef _Rb_tree_iterator<_Val> _Iterator_t;
+ typedef _Rb_tree_const_iterator<_Val> _Const_iterator_t;
+ };
#if __cplusplus > 201402L
template<typename _Tree1, typename _Cmp2>
@@ -424,16 +1181,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Compare, typename _Alloc = allocator<_Val> >
class _Rb_tree
{
+ typedef typename __gnu_cxx::__alloc_traits<_Alloc>::pointer _ValPtr;
+ typedef _Rb_tree_node_traits<_ValPtr> _Node_traits;
+
+ typedef typename _Node_traits::_Node_base _Node_base;
+ typedef typename _Node_traits::_Node_type _Node_type;
+
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
- rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
+ rebind<_Node_type>::other _Node_allocator;
typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
protected:
- typedef _Rb_tree_node_base* _Base_ptr;
- typedef const _Rb_tree_node_base* _Const_Base_ptr;
- typedef _Rb_tree_node<_Val>* _Link_type;
- typedef const _Rb_tree_node<_Val>* _Const_Link_type;
+ typedef typename _Node_base::_Base_ptr _Base_ptr;
+ typedef typename _Node_base::_Const_Base_ptr _Const_Base_ptr;
+ typedef typename _Node_type::_Node_ptr _Node_ptr;
+ typedef typename _Node_type::_Const_Node_ptr _Const_Node_ptr;
+ typedef _Rb_tree_helpers<_Node_base> _Tree_helpers;
private:
// Functor recycling a pool of nodes and using allocation once the pool
@@ -459,13 +1223,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#endif
~_Reuse_or_alloc_node()
- { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
+ { _M_t._M_erase(_M_root); }
template<typename _Arg>
- _Link_type
+ _Base_ptr
operator()(_GLIBCXX_FWDREF(_Arg) __arg)
{
- _Link_type __node = static_cast<_Link_type>(_M_extract());
+ _Base_ptr __node = _M_extract();
if (__node)
{
_M_t._M_destroy_node(__node);
@@ -524,7 +1288,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
: _M_t(__t) { }
template<typename _Arg>
- _Link_type
+ _Node_ptr
operator()(_GLIBCXX_FWDREF(_Arg) __arg) const
{ return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
@@ -556,18 +1320,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{ return allocator_type(_M_get_Node_allocator()); }
protected:
- _Link_type
+ _Node_ptr
_M_get_node()
{ return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
void
- _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
- { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
+ _M_put_node(_Base_ptr __p) _GLIBCXX_NOEXCEPT
+ {
+ _Alloc_traits::deallocate
+ (_M_get_Node_allocator(), __p->template _M_node_ptr<_Node_ptr>(), 1);
+ }
#if __cplusplus < 201103L
void
- _M_construct_node(_Link_type __node, const value_type& __x)
+ _M_construct_node(_Base_ptr __p, const value_type& __x)
{
+ _Node_ptr __node = static_cast<_Node_ptr>(__p);
__try
{ get_allocator().construct(__node->_M_valptr(), __x); }
__catch(...)
@@ -577,79 +1345,82 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
}
- _Link_type
+ _Node_ptr
_M_create_node(const value_type& __x)
{
- _Link_type __tmp = _M_get_node();
+ _Node_ptr __tmp = _M_get_node();
_M_construct_node(__tmp, __x);
return __tmp;
}
#else
template<typename... _Args>
void
- _M_construct_node(_Link_type __node, _Args&&... __args)
+ _M_construct_node(_Base_ptr __p, _Args&&... __args)
{
+ _Node_type& __node = static_cast<_Node_type&>(*__p);
__try
{
- ::new(__node) _Rb_tree_node<_Val>;
+ ::new(std::__addressof(__node)) _Node_type;
_Alloc_traits::construct(_M_get_Node_allocator(),
- __node->_M_valptr(),
+ __node._M_valptr(),
std::forward<_Args>(__args)...);
}
__catch(...)
{
- __node->~_Rb_tree_node<_Val>();
- _M_put_node(__node);
+ __node.~_Node_type();
+ _M_put_node(__p);
__throw_exception_again;
}
}
template<typename... _Args>
- _Link_type
+ _Node_ptr
_M_create_node(_Args&&... __args)
{
- _Link_type __tmp = _M_get_node();
+ _Node_ptr __tmp = _M_get_node();
_M_construct_node(__tmp, std::forward<_Args>(__args)...);
return __tmp;
}
#endif
void
- _M_destroy_node(_Link_type __p) _GLIBCXX_NOEXCEPT
+ _M_destroy_node(_Base_ptr __p) _GLIBCXX_NOEXCEPT
{
#if __cplusplus < 201103L
- get_allocator().destroy(__p->_M_valptr());
+ get_allocator().destroy(static_cast<_Node_ptr>(__p)->_M_valptr());
#else
- _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
- __p->~_Rb_tree_node<_Val>();
+ _Node_type& __node = static_cast<_Node_type&>(*__p);
+ _Alloc_traits::destroy(_M_get_Node_allocator(), __node._M_valptr());
+ __node.~_Node_type();
#endif
}
void
- _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
+ _M_drop_node(_Base_ptr __p) _GLIBCXX_NOEXCEPT
{
_M_destroy_node(__p);
_M_put_node(__p);
}
template<bool _MoveValue, typename _NodeGen>
- _Link_type
- _M_clone_node(_Link_type __x, _NodeGen& __node_gen)
+ _Base_ptr
+ _M_clone_node(_Base_ptr __x, _NodeGen& __node_gen)
{
#if __cplusplus >= 201103L
using _Vp = __conditional_t<_MoveValue,
value_type&&,
const value_type&>;
#endif
- _Link_type __tmp
- = __node_gen(_GLIBCXX_FORWARD(_Vp, *__x->_M_valptr()));
+ _Base_ptr __tmp = __node_gen
+ (_GLIBCXX_FORWARD(_Vp,
*static_cast<_Node_type&>(*__x)._M_valptr()));
__tmp->_M_color = __x->_M_color;
- __tmp->_M_left = 0;
- __tmp->_M_right = 0;
+ __tmp->_M_left = __tmp->_M_right = _Base_ptr();
return __tmp;
}
protected:
+ typedef typename _Node_traits::_Header_t _Header_t;
+
#if _GLIBCXX_INLINE_VERSION
template<typename _Key_compare>
#else
@@ -660,7 +1431,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
struct _Rb_tree_impl
: public _Node_allocator
, public _Rb_tree_key_compare<_Key_compare>
- , public _Rb_tree_header
+ , public _Header_t
{
typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;
@@ -674,7 +1445,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Rb_tree_impl(const _Rb_tree_impl& __x)
: _Node_allocator(_Alloc_traits::_S_select_on_copy(__x))
, _Base_key_compare(__x._M_key_compare)
- , _Rb_tree_header()
+ , _Header_t()
{ }
#if __cplusplus < 201103L
@@ -694,7 +1465,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
: _Node_allocator(std::move(__a)),
_Base_key_compare(std::move(__x)),
- _Rb_tree_header(std::move(__x))
+ _Header_t(std::move(__x))
{ }
_Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
@@ -730,31 +1501,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_rightmost() const _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_right; }
- _Link_type
+ _Base_ptr
_M_mbegin() const _GLIBCXX_NOEXCEPT
- { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
+ { return this->_M_impl._M_header._M_parent; }
- _Link_type
+ _Base_ptr
_M_begin() _GLIBCXX_NOEXCEPT
{ return _M_mbegin(); }
- _Const_Link_type
+ _Const_Base_ptr
_M_begin() const _GLIBCXX_NOEXCEPT
- {
- return static_cast<_Const_Link_type>
- (this->_M_impl._M_header._M_parent);
- }
+ { return this->_M_impl._M_header._M_parent; }
_Base_ptr
_M_end() _GLIBCXX_NOEXCEPT
- { return &this->_M_impl._M_header; }
+ { return this->_M_impl._M_header._M_self_ptr(); }
_Const_Base_ptr
_M_end() const _GLIBCXX_NOEXCEPT
- { return &this->_M_impl._M_header; }
+ { return this->_M_impl._M_header._M_self_ptr(); }
static const _Key&
- _S_key(_Const_Link_type __x)
+ _S_key(_Const_Base_ptr __x)
{
#if __cplusplus >= 201103L
// If we're asking for the key we're presumably using the comparison
@@ -772,48 +1540,44 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
# endif // C++17
#endif // C++11
- return _KeyOfValue()(*__x->_M_valptr());
+ return _KeyOfValue()(*static_cast<const _Node_type&>(*__x)._M_valptr());
}
- static _Link_type
+ static _Base_ptr
_S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
- { return static_cast<_Link_type>(__x->_M_left); }
+ { return __x->_M_left; }
- static _Const_Link_type
+ static _Const_Base_ptr
_S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
- { return static_cast<_Const_Link_type>(__x->_M_left); }
+ { return __x->_M_left; }
- static _Link_type
+ static _Base_ptr
_S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
- { return static_cast<_Link_type>(__x->_M_right); }
+ { return __x->_M_right; }
- static _Const_Link_type
+ static _Const_Base_ptr
_S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
- { return static_cast<_Const_Link_type>(__x->_M_right); }
-
- static const _Key&
- _S_key(_Const_Base_ptr __x)
- { return _S_key(static_cast<_Const_Link_type>(__x)); }
+ { return __x->_M_right; }
static _Base_ptr
_S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
- { return _Rb_tree_node_base::_S_minimum(__x); }
+ { return _Tree_helpers::_S_minimum(__x); }
static _Const_Base_ptr
_S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
- { return _Rb_tree_node_base::_S_minimum(__x); }
+ { return _Tree_helpers::_S_minimum(__x); }
static _Base_ptr
_S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
- { return _Rb_tree_node_base::_S_maximum(__x); }
+ { return _Tree_helpers::_S_maximum(__x); }
static _Const_Base_ptr
_S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
- { return _Rb_tree_node_base::_S_maximum(__x); }
+ { return _Tree_helpers::_S_maximum(__x); }
public:
- typedef _Rb_tree_iterator<value_type> iterator;
- typedef _Rb_tree_const_iterator<value_type> const_iterator;
+ typedef typename _Node_traits::_Iterator_t iterator;
+ typedef typename _Node_traits::_Const_iterator_t const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
@@ -846,7 +1610,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
iterator
- _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
+ _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Base_ptr __z);
template<typename _Arg>
iterator
@@ -857,10 +1621,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_insert_equal_lower(_Arg&& __x);
iterator
- _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
+ _M_insert_lower_node(_Base_ptr __p, _Base_ptr __z);
iterator
- _M_insert_equal_lower_node(_Link_type __z);
+ _M_insert_equal_lower_node(_Base_ptr __z);
#else
template<typename _NodeGen>
iterator
@@ -879,22 +1643,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
enum { __as_lvalue, __as_rvalue };
template<bool _MoveValues, typename _NodeGen>
- _Link_type
- _M_copy(_Link_type, _Base_ptr, _NodeGen&);
+ _Base_ptr
+ _M_copy(_Base_ptr, _Base_ptr, _NodeGen&);
template<bool _MoveValues, typename _NodeGen>
- _Link_type
+ _Base_ptr
_M_copy(const _Rb_tree& __x, _NodeGen& __gen)
{
- _Link_type __root =
+ _Base_ptr __root =
_M_copy<_MoveValues>(__x._M_mbegin(), _M_end(), __gen);
- _M_leftmost() = _S_minimum(__root);
- _M_rightmost() = _S_maximum(__root);
+ _M_leftmost() = _Tree_helpers::_S_minimum(__root);
+ _M_rightmost() = _Tree_helpers::_S_maximum(__root);
_M_impl._M_node_count = __x._M_impl._M_node_count;
return __root;
}
- _Link_type
+ _Base_ptr
_M_copy(const _Rb_tree& __x)
{
_Alloc_node __an(*this);
@@ -902,22 +1666,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
void
- _M_erase(_Link_type __x);
+ _M_erase(_Base_ptr __x);
iterator
- _M_lower_bound(_Link_type __x, _Base_ptr __y,
+ _M_lower_bound(_Base_ptr __x, _Base_ptr __y,
const _Key& __k);
const_iterator
- _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
+ _M_lower_bound(_Const_Base_ptr __x, _Const_Base_ptr __y,
const _Key& __k) const;
iterator
- _M_upper_bound(_Link_type __x, _Base_ptr __y,
+ _M_upper_bound(_Base_ptr __x, _Base_ptr __y,
const _Key& __k);
const_iterator
- _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
+ _M_upper_bound(_Const_Base_ptr __x, _Const_Base_ptr __y,
const _Key& __k) const;
public:
@@ -935,7 +1699,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Rb_tree(const _Rb_tree& __x)
: _M_impl(__x._M_impl)
{
- if (__x._M_root() != 0)
+ if (__x._M_root())
_M_root() = _M_copy(__x);
}
@@ -947,7 +1711,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
: _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
{
- if (__x._M_root() != nullptr)
+ if (__x._M_root())
_M_root() = _M_copy(__x);
}
@@ -966,7 +1730,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
: _M_impl(__x._M_impl._M_key_compare, std::move(__a))
{
- if (__x._M_root() != nullptr)
+ if (__x._M_root())
_M_move_data(__x, false_type{});
}
@@ -1001,11 +1765,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator
end() _GLIBCXX_NOEXCEPT
- { return iterator(&this->_M_impl._M_header); }
+ { return iterator(this->_M_impl._M_header._M_self_ptr()); }
const_iterator
end() const _GLIBCXX_NOEXCEPT
- { return const_iterator(&this->_M_impl._M_header); }
+ { return const_iterator(this->_M_impl._M_header._M_self_ptr()); }
reverse_iterator
rbegin() _GLIBCXX_NOEXCEPT
@@ -1530,10 +2294,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type
extract(const_iterator __pos)
{
- auto __ptr = _Rb_tree_rebalance_for_erase(
- __pos._M_const_cast()._M_node, _M_impl._M_header);
+ auto __ptr = _Tree_helpers::_S_rebalance_for_erase
+ (__pos._M_const_cast()._M_node, _M_impl._M_header);
--_M_impl._M_node_count;
- return { static_cast<_Link_type>(__ptr), _M_get_Node_allocator() };
+ return
+ { __ptr->template _M_node_ptr<_Node_ptr>(), _M_get_Node_allocator() };
}
/// Extract a node.
@@ -1567,11 +2332,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__res.second)
{
auto& __src_impl = _Merge_helper::_S_get_impl(__src);
- auto __ptr = _Rb_tree_rebalance_for_erase(
- __pos._M_node, __src_impl._M_header);
+ auto __ptr = _Tree_helpers::_S_rebalance_for_erase
+ (__pos._M_node, __src_impl._M_header);
--__src_impl._M_node_count;
- _M_insert_node(__res.first, __res.second,
- static_cast<_Link_type>(__ptr));
+ _M_insert_node(__res.first, __res.second, __ptr);
}
}
}
@@ -1589,11 +2353,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__res.second)
{
auto& __src_impl = _Merge_helper::_S_get_impl(__src);
- auto __ptr = _Rb_tree_rebalance_for_erase(
- __pos._M_node, __src_impl._M_header);
+ auto __ptr = _Tree_helpers::_S_rebalance_for_erase
+ (__pos._M_node, __src_impl._M_header);
--__src_impl._M_node_count;
- _M_insert_node(__res.first, __res.second,
- static_cast<_Link_type>(__ptr));
+ _M_insert_node(__res.first, __res.second, __ptr);
}
}
}
@@ -1666,7 +2429,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
_Rb_tree& _M_t;
- _Link_type _M_node;
+ _Node_ptr _M_node;
};
#endif // C++11
};
@@ -1704,7 +2467,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_move_assign(_Rb_tree& __x, true_type)
{
clear();
- if (__x._M_root() != nullptr)
+ if (__x._M_root())
_M_move_data(__x, true_type());
std::__alloc_on_move(_M_get_Node_allocator(),
__x._M_get_Node_allocator());
@@ -1723,7 +2486,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// structure.
_Reuse_or_alloc_node __roan(*this);
_M_impl._M_reset();
- if (__x._M_root() != nullptr)
+ if (__x._M_root())
{
_M_root() = _M_copy<__as_rvalue>(__x, __roan);
__x.clear();
@@ -1798,7 +2561,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Reuse_or_alloc_node __roan(*this);
_M_impl._M_reset();
_M_impl._M_key_compare = __x._M_impl._M_key_compare;
- if (__x._M_root() != 0)
+ if (__x._M_root())
_M_root() = _M_copy<__as_lvalue>(__x, __roan);
}
@@ -1826,10 +2589,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
|| _M_impl._M_key_compare(_KeyOfValue()(__v),
_S_key(__p)));
- _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
+ _Base_ptr __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
- _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
- this->_M_impl._M_header);
+ _Tree_helpers::_S_insert_and_rebalance
+ (__insert_left, __z, __p, this->_M_impl._M_header);
++_M_impl._M_node_count;
return iterator(__z);
}
@@ -1851,10 +2614,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
|| !_M_impl._M_key_compare(_S_key(__p),
_KeyOfValue()(__v)));
- _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
+ _Base_ptr __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
- _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
- this->_M_impl._M_header);
+ _Tree_helpers::_S_insert_and_rebalance
+ (__insert_left, __z, __p, this->_M_impl._M_header);
++_M_impl._M_node_count;
return iterator(__z);
}
@@ -1872,7 +2635,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_insert_equal_lower(const _Val& __v)
#endif
{
- _Link_type __x = _M_begin();
+ _Base_ptr __x = _M_begin();
_Base_ptr __y = _M_end();
while (__x != 0)
{
@@ -1886,12 +2649,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Key, typename _Val, typename _KoV,
typename _Compare, typename _Alloc>
template<bool _MoveValues, typename _NodeGen>
- typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
+ typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Base_ptr
_Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
- _M_copy(_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
+ _M_copy(_Base_ptr __x, _Base_ptr __p, _NodeGen& __node_gen)
{
// Structural copy. __x and __p must be non-null.
- _Link_type __top = _M_clone_node<_MoveValues>(__x, __node_gen);
+ _Base_ptr __top = _M_clone_node<_MoveValues>(__x, __node_gen);
__top->_M_parent = __p;
__try
@@ -1904,7 +2667,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
while (__x != 0)
{
- _Link_type __y = _M_clone_node<_MoveValues>(__x, __node_gen);
+ _Base_ptr __y = _M_clone_node<_MoveValues>(__x, __node_gen);
__p->_M_left = __y;
__y->_M_parent = __p;
if (__x->_M_right)
@@ -1926,13 +2689,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Compare, typename _Alloc>
void
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_erase(_Link_type __x)
+ _M_erase(_Base_ptr __x)
{
// Erase without rebalancing.
while (__x != 0)
{
_M_erase(_S_right(__x));
- _Link_type __y = _S_left(__x);
+ _Base_ptr __y = _S_left(__x);
_M_drop_node(__x);
__x = __y;
}
@@ -1943,10 +2706,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_lower_bound(_Link_type __x, _Base_ptr __y,
+ _M_lower_bound(_Base_ptr __x, _Base_ptr __y,
const _Key& __k)
{
- while (__x != 0)
+ while (__x)
if (!_M_impl._M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
@@ -1959,10 +2722,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::const_iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
+ _M_lower_bound(_Const_Base_ptr __x, _Const_Base_ptr __y,
const _Key& __k) const
{
- while (__x != 0)
+ while (__x)
if (!_M_impl._M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
@@ -1975,10 +2738,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_upper_bound(_Link_type __x, _Base_ptr __y,
+ _M_upper_bound(_Base_ptr __x, _Base_ptr __y,
const _Key& __k)
{
- while (__x != 0)
+ while (__x)
if (_M_impl._M_key_compare(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
@@ -1991,10 +2754,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::const_iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
+ _M_upper_bound(_Const_Base_ptr __x, _Const_Base_ptr __y,
const _Key& __k) const
{
- while (__x != 0)
+ while (__x)
if (_M_impl._M_key_compare(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
@@ -2011,9 +2774,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
equal_range(const _Key& __k)
{
- _Link_type __x = _M_begin();
+ _Base_ptr __x = _M_begin();
_Base_ptr __y = _M_end();
- while (__x != 0)
+ while (__x)
{
if (_M_impl._M_key_compare(_S_key(__x), __k))
__x = _S_right(__x);
@@ -2021,7 +2784,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__y = __x, __x = _S_left(__x);
else
{
- _Link_type __xu(__x);
+ _Base_ptr __xu(__x);
_Base_ptr __yu(__y);
__y = __x, __x = _S_left(__x);
__xu = _S_right(__xu);
@@ -2043,7 +2806,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
equal_range(const _Key& __k) const
{
- _Const_Link_type __x = _M_begin();
+ _Const_Base_ptr __x = _M_begin();
_Const_Base_ptr __y = _M_end();
while (__x != 0)
{
@@ -2053,7 +2816,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__y = __x, __x = _S_left(__x);
else
{
- _Const_Link_type __xu(__x);
+ _Const_Base_ptr __xu(__x);
_Const_Base_ptr __yu(__y);
__y = __x, __x = _S_left(__x);
__xu = _S_right(__xu);
@@ -2107,10 +2870,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_get_insert_unique_pos(const key_type& __k)
{
typedef pair<_Base_ptr, _Base_ptr> _Res;
- _Link_type __x = _M_begin();
+ _Base_ptr __x = _M_begin();
_Base_ptr __y = _M_end();
bool __comp = true;
- while (__x != 0)
+ while (__x)
{
__y = __x;
__comp = _M_impl._M_key_compare(__k, _S_key(__x));
@@ -2139,9 +2902,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_get_insert_equal_pos(const key_type& __k)
{
typedef pair<_Base_ptr, _Base_ptr> _Res;
- _Link_type __x = _M_begin();
+ _Base_ptr __x = _M_begin();
_Base_ptr __y = _M_end();
- while (__x != 0)
+ while (__x)
{
__y = __x;
__x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
@@ -2373,15 +3136,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Compare, typename _Alloc>
auto
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
+ _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Base_ptr __z)
-> iterator
{
bool __insert_left = (__x != 0 || __p == _M_end()
|| _M_impl._M_key_compare(_S_key(__z),
_S_key(__p)));
- _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
- this->_M_impl._M_header);
+ _Tree_helpers::_S_insert_and_rebalance
+ (__insert_left, __z, __p, this->_M_impl._M_header);
++_M_impl._M_node_count;
return iterator(__z);
}
@@ -2390,15 +3153,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Compare, typename _Alloc>
auto
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
+ _M_insert_lower_node(_Base_ptr __p, _Base_ptr __z)
-> iterator
{
bool __insert_left = (__p == _M_end()
|| !_M_impl._M_key_compare(_S_key(__p),
_S_key(__z)));
- _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
- this->_M_impl._M_header);
+ _Tree_helpers::_S_insert_and_rebalance
+ (__insert_left, __z, __p, this->_M_impl._M_header);
++_M_impl._M_node_count;
return iterator(__z);
}
@@ -2407,10 +3170,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Compare, typename _Alloc>
auto
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_insert_equal_lower_node(_Link_type __z)
+ _M_insert_equal_lower_node(_Base_ptr __z)
-> iterator
{
- _Link_type __x = _M_begin();
+ _Base_ptr __x = _M_begin();
_Base_ptr __y = _M_end();
while (__x != 0)
{
@@ -2487,10 +3250,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_erase_aux(const_iterator __position)
{
- _Link_type __y =
- static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
- (const_cast<_Base_ptr>(__position._M_node),
- this->_M_impl._M_header));
+ _Base_ptr __y = _Tree_helpers::_S_rebalance_for_erase
+ (__position._M_const_cast()._M_node, this->_M_impl._M_header);
_M_drop_node(__y);
--_M_impl._M_node_count;
}
@@ -2574,9 +3335,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
for (const_iterator __it = begin(); __it != end(); ++__it)
{
- _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
- _Const_Link_type __L = _S_left(__x);
- _Const_Link_type __R = _S_right(__x);
+ _Const_Node_ptr __x = static_cast<_Const_Node_ptr>(__it._M_node);
+ _Const_Node_ptr __L = _S_left(__x);
+ _Const_Node_ptr __R = _S_right(__x);
if (__x->_M_color == _S_red)
if ((__L && __L->_M_color == _S_red)
@@ -2592,9 +3353,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return false;
}
- if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
+ if (_M_leftmost() != _Tree_helpers::_S_minimum(_M_root()))
return false;
- if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
+ if (_M_rightmost() != _Tree_helpers::_S_maximum(_M_root()))
return false;
return true;
}
diff --git a/libstdc++-v3/testsuite/23_containers/map/allocator/ext_ptr.cc
b/libstdc++-v3/testsuite/23_containers/map/allocator/ext_ptr.cc
new file mode 100644
index 00000000000..758beedccfd
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/allocator/ext_ptr.cc
@@ -0,0 +1,44 @@
+// { dg-do run { target c++11 } }
+
+#include <map>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+bool operator<(const T& l, const T& r)
+{ return l.i < r.i; }
+
+struct H
+{
+ std::size_t
+ operator()(const T& t) const noexcept
+ { return t.i; }
+};
+
+struct L : std::less<T>
+{ };
+
+using __gnu_test::CustomPointerAlloc;
+
+template class std::map<T, int, L,
+ CustomPointerAlloc<std::pair<const T, int>>>;
+
+void test01()
+{
+ typedef CustomPointerAlloc<std::pair<const T, int>> alloc_type;
+ typedef std::map<T, int, L, alloc_type> test_type;
+ test_type v;
+ v.insert({ T(), 0 });
+ VERIFY( v.begin()->second == 0 );
+ VERIFY( ++v.begin() == v.end() );
+ v.insert({ T { 1 }, 1 });
+ VERIFY( v.size() == 2 );
+ VERIFY( v.find(T()) != v.end() );
+}
+
+int main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/allocator/ext_ptr.cc
b/libstdc++-v3/testsuite/23_containers/multimap/allocator/ext_ptr.cc
new file mode 100644
index 00000000000..1a9e198531f
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multimap/allocator/ext_ptr.cc
@@ -0,0 +1,40 @@
+// { dg-do run { target c++11 } }
+
+#include <map>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+bool operator<(const T& l, const T& r)
+{ return l.i < r.i; }
+
+struct H
+{
+ std::size_t
+ operator()(const T& t) const noexcept
+ { return t.i; }
+};
+
+struct L : std::less<T>
+{ };
+
+using __gnu_test::CustomPointerAlloc;
+
+template class std::multimap<T, int, L,
+ CustomPointerAlloc<std::pair<const T, int>>>;
+
+void test01()
+{
+ typedef CustomPointerAlloc<std::pair<const T, int>> alloc_type;
+ typedef std::multimap<T, int, L, alloc_type> test_type;
+ test_type v;
+ v.insert({ T(), 0 });
+ VERIFY( ++v.begin() == v.end() );
+}
+
+int main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/allocator/ext_ptr.cc
b/libstdc++-v3/testsuite/23_containers/multiset/allocator/ext_ptr.cc
new file mode 100644
index 00000000000..d4796e37672
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/allocator/ext_ptr.cc
@@ -0,0 +1,39 @@
+// { dg-do run { target c++11 } }
+
+#include <set>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+bool operator<(const T& l, const T& r)
+{ return l.i < r.i; }
+
+struct H
+{
+ std::size_t
+ operator()(const T& t) const noexcept
+ { return t.i; }
+};
+
+struct L : std::less<T>
+{ };
+
+using __gnu_test::CustomPointerAlloc;
+
+template class std::multiset<T, L, CustomPointerAlloc<T>>;
+
+void test01()
+{
+ typedef CustomPointerAlloc<T> alloc_type;
+ typedef std::multiset<T, L, alloc_type> test_type;
+ test_type v;
+ v.insert(T());
+ VERIFY( ++v.begin() == v.end() );
+}
+
+int main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/set/allocator/ext_ptr.cc
b/libstdc++-v3/testsuite/23_containers/set/allocator/ext_ptr.cc
new file mode 100644
index 00000000000..1cf479083eb
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/allocator/ext_ptr.cc
@@ -0,0 +1,39 @@
+// { dg-do run { target c++11 } }
+
+#include <set>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+bool operator<(const T& l, const T& r)
+{ return l.i < r.i; }
+
+struct H
+{
+ std::size_t
+ operator()(const T& t) const noexcept
+ { return t.i; }
+};
+
+struct L : std::less<T>
+{ };
+
+using __gnu_test::CustomPointerAlloc;
+
+template class std::set<T, L, CustomPointerAlloc<T>>;
+
+void test01()
+{
+ typedef CustomPointerAlloc<T> alloc_type;
+ typedef std::set<T, L, alloc_type> test_type;
+ test_type v;
+ v.insert(T());
+ VERIFY( ++v.begin() == v.end() );
+}
+
+int main()
+{
+ test01();
+}
