Hi
Here is a new proposal with all the cleanup regarding _Const_Base_ptr
that makes support of allocator's fancy pointer type simpler.
Also submitted as PR:
https://forge.sourceware.org/gcc/gcc-TEST/pulls/27
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.
As all node are stored as _Base_ptr have all methods working with
this type
and remove _Const_Base_ptr and all methods associated to it.
libstdc++-v3/ChangeLog:
* include/bits/stl_set.h (std::set<>::upper_bound<>(const
_Kt&) const): Fix
decltype typo to use const_iterator.
* include/bits/stl_tree.h
(_Rb_tree_ptr_traits<>): New.
(_Rb_tree_pnode_base<>): New.
(_Rb_tree_node_base): Inherit from latter.
(_Rb_tree_node_base::_Const_Base_ptr): Remove.
(_Rb_tree_node_base::_S_minimum(_Const_Base_ptr)): Remove.
(_Rb_tree_node_base::_S_maximum(_Const_Base_ptr)): Remove.
(_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_ptr): ...this.
(_Rb_tree_const_iterator<>::_Link_type): Rename into...
(_Rb_tree_const_iterator<>::_Node_ptr): ...this.
(_Rb_tree_const_iterator<>::_M_node): Change type into
_Base_ptr.
(_Rb_tree_const_iterator<>::_M_const_cast): Remove.
(_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<>::_Const_Base_ptr): Remove.
(_Rb_tree): Adapt to generalize usage of _Base_ptr in place
of _Link_type.
(_Rb_tree<>::_M_mbegin): Remove.
(_Rb_tree<>::_S_left(_Const_Base_ptr)): Remove.
(_Rb_tree<>::_S_right(_Const_Base_ptr)): Remove.
(_Rb_tree<>::_S_maximum(_Const_Base_ptr)): Remove.
(_Rb_tree<>::_S_minimum(_Const_Base_ptr)): Remove.
* 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.
Note that I've also run the 23_containers tests on map, multimap,
multiset and set tweaking implementation
so that new types are being used when C++11 or later even if allocator
pointer type is a C pointer.
Ok to commit ?
François
On 12/11/2024 15:56, Jonathan Wakely wrote:
On Mon, 4 Nov 2024 at 21:34, François Dumont <frs.dum...@gmail.com> wrote:
On 04/11/2024 19:45, Jonathan Wakely wrote:
On Mon, 4 Nov 2024 at 18:30, François Dumont <frs.dum...@gmail.com> wrote:
On 21/10/2024 06:56, François Dumont wrote:
On 17/10/2024 23:11, Jonathan Wakely wrote:
On Thu, 17 Oct 2024 at 21:39, Jonathan Wakely <jwakely....@gmail.com> wrote:
On Thu, 17 Oct 2024 at 20:52, François Dumont <frs.dum...@gmail.com> wrote:
Here is an updated version that compiles, I think, all your feedbacks. It's
much cleaner indeed.
Thanks, I'll take a look tomorrow.
It's also tested in C++98/17/23.
I'm surprised that we do not need to consider potential
allocator::const_pointer.
Do you mean consider the case where Alloc::const_pointer is not the same type
as rebinding 'pointer' to a const element type?
Yes, exactly.
We don't need to consider that because we never get a 'const_pointer' from the
allocator, and we never need to pass a 'const_pointer' to the allocator. The
allocator's 'allocate' and 'deallocate' members both work with the 'pointer' type, so
we only need to use that type when interacting with the allocator. For all the other
uses, such as _Const_Node_ptr, what we need is a pointer-to-const that's compatible
with the allocator's pointer type. It doesn't actually matter if it's the same type
as allocator_traits<Alloc>::const_pointer, because we don't need
Sorry, I sent the email before finishing that thought!
... we don't need to pass a const_pointer to anything, we only need it for the
container's own purposes.
But thinking about it some more, do we even need a const-pointer for the
container? Currently the const_iterator stores a const-pointer, and some
members like _M_root() and _M_leftmost() return a const-pointer. But they don't
need to. The nodes are all pointed to by a non-const _Base_ptr, none of the
storage managed by the container is const.
Except _M_impl._M_header in a const context.
Using const_cast would result in a similar UB that you fixed on _GLIBCXX_DEBUG
containers, no ?
We only use a pointer to _M_header for the past-the-end iterator,
which is not dereferenceable. It's OK to do the const_cast, it's not
OK to write something through that pointer/reference if the object is
really const. But you can't write through a past-the-end pointer
anyway.
One last question then to complete this work, is it fine to change
_Rb_tree_const_iterator::_M_node to _Base_ptr ? No abi issue in doing so ?
I thought I'd sent a reply to this question, but I don't see it in the
archives, sorry.
So changing from _Const_Base_ptr to _Base_ptr? Yes, I think that's OK.
diff --git a/libstdc++-v3/include/bits/stl_set.h
b/libstdc++-v3/include/bits/stl_set.h
index c0eb4dbf65f..3d17626f330 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -875,7 +875,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
template<typename _Kt>
auto
upper_bound(const _Kt& __x) const
- -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
+ -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))
{ return const_iterator(_M_t._M_upper_bound_tr(__x)); }
#endif
///@}
diff --git a/libstdc++-v3/include/bits/stl_tree.h
b/libstdc++-v3/include/bits/stl_tree.h
index bc27e191e8b..c6cba99726d 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -96,44 +96,100 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
enum _Rb_tree_color { _S_red = false, _S_black = true };
- struct _Rb_tree_node_base
- {
- typedef _Rb_tree_node_base* _Base_ptr;
- typedef const _Rb_tree_node_base* _Const_Base_ptr;
-
- _Rb_tree_color _M_color;
- _Base_ptr _M_parent;
- _Base_ptr _M_left;
- _Base_ptr _M_right;
-
- static _Base_ptr
- _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
+#if __cplusplus >= 201103L
+ template<typename _Ptr>
+ struct _Rb_tree_ptr_traits
{
- while (__x->_M_left != 0) __x = __x->_M_left;
- return __x;
- }
+ 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
- static _Const_Base_ptr
- _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
+ template<typename _Tp>
+ struct _Rb_tree_ptr_traits<_Tp*>
{
- while (__x->_M_left != 0) __x = __x->_M_left;
- return __x;
- }
+ 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); }
+ };
- static _Base_ptr
- _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
+ template<typename _BasePtr>
+ struct _Rb_tree_pnode_base
{
- while (__x->_M_right != 0) __x = __x->_M_right;
- return __x;
- }
+ typedef typename _Rb_tree_ptr_traits<_BasePtr>::template
+ __rebind<_Rb_tree_pnode_base>::__type _Base_ptr;
- static _Const_Base_ptr
- _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
- {
- while (__x->_M_right != 0) __x = __x->_M_right;
- return __x;
- }
- };
+ _Base_ptr
+ _M_self_ptr() _GLIBCXX_NOEXCEPT
+ { return _Rb_tree_ptr_traits<_Base_ptr>::_S_ptr_to(this); }
+
+ _Base_ptr
+ _M_self_ptr() 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
+ {
+ 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;
+ _Base_ptr _M_left;
+ _Base_ptr _M_right;
+
+ static _Base_ptr
+ _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
+ {
+ while (__x->_M_left) __x = __x->_M_left;
+ return __x;
+ }
+
+ static _Base_ptr
+ _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
+ {
+ 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>
@@ -163,81 +219,108 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
};
// Helper type to manage default initialization of node count and header.
- struct _Rb_tree_header
- {
- _Rb_tree_node_base _M_header;
- size_t _M_node_count; // Keeps track of size of tree.
-
- _Rb_tree_header() _GLIBCXX_NOEXCEPT
+ template<typename _NodeBase>
+ struct _Rb_tree_pheader
{
- _M_header._M_color = _S_red;
- _M_reset();
- }
+ private:
+ typedef typename _NodeBase::_Base_ptr _Base_ptr;
+
+ public:
+ _NodeBase _M_header;
+ size_t _M_node_count; // Keeps track of size of tree.
+
+ _Rb_tree_pheader() _GLIBCXX_NOEXCEPT
+ {
+ _M_header._M_color = _S_red;
+ _M_reset();
+ }
#if __cplusplus >= 201103L
- _Rb_tree_header(_Rb_tree_header&& __x) noexcept
- {
- if (__x._M_header._M_parent != nullptr)
- _M_move_data(__x);
- else
- {
- _M_header._M_color = _S_red;
- _M_reset();
- }
- }
+ _Rb_tree_pheader(_Rb_tree_pheader&& __x) noexcept
+ {
+ if (__x._M_header._M_parent)
+ _M_move_data(__x);
+ else
+ {
+ _M_header._M_color = _S_red;
+ _M_reset();
+ }
+ }
#endif
- void
- _M_move_data(_Rb_tree_header& __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_node_count = __from._M_node_count;
-
- __from._M_reset();
- }
+ void
+ _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_self_ptr();
+ _M_node_count = __from._M_node_count;
+
+ __from._M_reset();
+ }
- void
- _M_reset()
- {
- _M_header._M_parent = 0;
- _M_header._M_left = &_M_header;
- _M_header._M_right = &_M_header;
- _M_node_count = 0;
- }
- };
+ void
+ _M_reset()
+ {
+ _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;
+ };
+
+#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>;
+ };
+#endif
+
_GLIBCXX_PURE _Rb_tree_node_base*
_Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
@@ -250,6 +333,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
{
@@ -257,12 +352,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typedef _Tp& reference;
typedef _Tp* pointer;
- typedef bidirectional_iterator_tag iterator_category;
- typedef ptrdiff_t difference_type;
+ typedef bidirectional_iterator_tag iterator_category;
+ 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 _Rb_tree_iterator<_Tp> _Self;
+ 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 +368,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
@@ -334,9 +429,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typedef bidirectional_iterator_tag iterator_category;
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 _Rb_tree_const_iterator<_Tp> _Self;
+ typedef typename _Rb_tree_node_base::_Base_ptr _Base_ptr;
+ typedef const _Rb_tree_node<_Tp>*
_Node_ptr;
_Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
: _M_node() { }
@@ -348,17 +443,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
: _M_node(__it._M_node) { }
- iterator
- _M_const_cast() const _GLIBCXX_NOEXCEPT
- { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
-
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 +494,570 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Base_ptr _M_node;
};
- __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 ();
+#if __cplusplus >= 201103L
+ template<typename _NodeBase>
+ struct _Rb_tree_helpers
+ {
+ using _Base_ptr = typename _NodeBase::_Base_ptr;
- __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 ();
+ static _Base_ptr
+ _S_minimum(_Base_ptr __x)
+ { return _NodeBase::_S_minimum(__x); }
+
+ static _Base_ptr
+ _S_maximum(_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 _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 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 _Rb_tree_node_base*
+ _S_maximum(_Rb_tree_node_base* __x) _GLIBCXX_NOEXCEPT
+ { return _Rb_tree_node_base::_S_maximum(__x); }
+
+ __attribute__((__nonnull__))
+ 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__))
+ 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 _Rb_tree_helpers<_Node_base> _Tree_helpers;
+
+ _Rb_tree_const_piterator() _GLIBCXX_NOEXCEPT
+ : _M_node() { }
+
+ explicit
+ _Rb_tree_const_piterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
+ : _M_node(__x) { }
+
+ _Rb_tree_const_piterator(const iterator& __it) _GLIBCXX_NOEXCEPT
+ : _M_node(__it._M_node) { }
+
+ 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;
+ };
+#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 +1068,21 @@ _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_type::_Node_ptr _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 +1108,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 +1173,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 +1205,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 +1230,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 +1316,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 +1330,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 +1350,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)
@@ -710,7 +1366,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_root() _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_parent; }
- _Const_Base_ptr
+ _Base_ptr
_M_root() const _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_parent; }
@@ -718,7 +1374,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_leftmost() _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_left; }
- _Const_Base_ptr
+ _Base_ptr
_M_leftmost() const _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_left; }
@@ -726,35 +1382,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_rightmost() _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_right; }
- _Const_Base_ptr
+ _Base_ptr
_M_rightmost() const _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_right; }
- _Link_type
- _M_mbegin() const _GLIBCXX_NOEXCEPT
- { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
-
- _Link_type
- _M_begin() _GLIBCXX_NOEXCEPT
- { return _M_mbegin(); }
-
- _Const_Link_type
+ _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; }
-
- _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(_Base_ptr __x)
{
#if __cplusplus >= 201103L
// If we're asking for the key we're presumably using the comparison
@@ -772,48 +1413,28 @@ _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
- _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
- { return static_cast<_Const_Link_type>(__x->_M_left); }
-
- static _Link_type
+ static _Base_ptr
_S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
- { return static_cast<_Link_type>(__x->_M_right); }
-
- static _Const_Link_type
- _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); }
-
- 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); }
-
- 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 +1467,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 +1478,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 +1500,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 =
- _M_copy<_MoveValues>(__x._M_mbegin(), _M_end(), __gen);
- _M_leftmost() = _S_minimum(__root);
- _M_rightmost() = _S_maximum(__root);
+ _Base_ptr __root =
+ _M_copy<_MoveValues>(__x._M_begin(), _M_end(), __gen);
+ _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 +1523,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
void
- _M_erase(_Link_type __x);
-
- iterator
- _M_lower_bound(_Link_type __x, _Base_ptr __y,
- const _Key& __k);
+ _M_erase(_Base_ptr __x);
- const_iterator
- _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
+ _Base_ptr
+ _M_lower_bound(_Base_ptr __x, _Base_ptr __y,
const _Key& __k) const;
- iterator
- _M_upper_bound(_Link_type __x, _Base_ptr __y,
- const _Key& __k);
-
- const_iterator
- _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
+ _Base_ptr
+ _M_upper_bound(_Base_ptr __x, _Base_ptr __y,
const _Key& __k) const;
public:
@@ -935,7 +1548,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 +1560,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 +1579,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 +1614,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
@@ -1194,7 +1807,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
const_iterator __result = __position;
++__result;
_M_erase_aux(__position);
- return __result._M_const_cast();
+ return iterator(__result._M_node);
}
// LWG 2059.
@@ -1235,7 +1848,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
erase(const_iterator __first, const_iterator __last)
{
_M_erase_aux(__first, __last);
- return __last._M_const_cast();
+ return iterator(__last._M_node);
}
#else
void
@@ -1266,19 +1879,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator
lower_bound(const key_type& __k)
- { return _M_lower_bound(_M_begin(), _M_end(), __k); }
+ { return iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); }
const_iterator
lower_bound(const key_type& __k) const
- { return _M_lower_bound(_M_begin(), _M_end(), __k); }
+ {
+ return const_iterator
+ (_M_lower_bound(_M_begin(), _M_end(), __k));
+ }
iterator
upper_bound(const key_type& __k)
- { return _M_upper_bound(_M_begin(), _M_end(), __k); }
+ { return iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); }
const_iterator
upper_bound(const key_type& __k) const
- { return _M_upper_bound(_M_begin(), _M_end(), __k); }
+ {
+ return const_iterator
+ (_M_upper_bound(_M_begin(), _M_end(), __k));
+ }
pair<iterator, iterator>
equal_range(const key_type& __k);
@@ -1293,7 +1912,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_find_tr(const _Kt& __k)
{
const _Rb_tree* __const_this = this;
- return __const_this->_M_find_tr(__k)._M_const_cast();
+ return iterator(__const_this->_M_find_tr(__k)._M_node);
}
template<typename _Kt,
@@ -1301,7 +1920,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
const_iterator
_M_find_tr(const _Kt& __k) const
{
- auto __j = _M_lower_bound_tr(__k);
+ const_iterator __j(_M_lower_bound_tr(__k));
if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
__j = end();
return __j;
@@ -1318,16 +1937,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Kt,
typename _Req = __has_is_transparent_t<_Compare, _Kt>>
- iterator
- _M_lower_bound_tr(const _Kt& __k)
- {
- const _Rb_tree* __const_this = this;
- return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
- }
-
- template<typename _Kt,
- typename _Req = __has_is_transparent_t<_Compare, _Kt>>
- const_iterator
+ _Base_ptr
_M_lower_bound_tr(const _Kt& __k) const
{
auto __x = _M_begin();
@@ -1340,21 +1950,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
else
__x = _S_right(__x);
- return const_iterator(__y);
- }
-
- template<typename _Kt,
- typename _Req = __has_is_transparent_t<_Compare, _Kt>>
- iterator
- _M_upper_bound_tr(const _Kt& __k)
- {
- const _Rb_tree* __const_this = this;
- return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
+ return __y;
}
template<typename _Kt,
typename _Req = __has_is_transparent_t<_Compare, _Kt>>
- const_iterator
+ _Base_ptr
_M_upper_bound_tr(const _Kt& __k) const
{
auto __x = _M_begin();
@@ -1367,7 +1968,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
else
__x = _S_right(__x);
- return const_iterator(__y);
+ return __y;
}
template<typename _Kt,
@@ -1377,7 +1978,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
const _Rb_tree* __const_this = this;
auto __ret = __const_this->_M_equal_range_tr(__k);
- return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
+ return
+ { iterator(__ret.first._M_node), iterator(__ret.second._M_node) };
}
template<typename _Kt,
@@ -1385,7 +1987,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
pair<const_iterator, const_iterator>
_M_equal_range_tr(const _Kt& __k) const
{
- auto __low = _M_lower_bound_tr(__k);
+ const_iterator __low(_M_lower_bound_tr(__k));
auto __high = __low;
auto& __cmp = _M_impl._M_key_compare;
while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
@@ -1530,10 +2132,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_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 +2170,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 +2191,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 +2267,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
_Rb_tree& _M_t;
- _Link_type _M_node;
+ _Node_ptr _M_node;
};
#endif // C++11
};
@@ -1704,7 +2305,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 +2324,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 +2399,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 +2427,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 +2452,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 +2473,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 +2487,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 +2505,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 +2527,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;
}
@@ -1941,65 +2542,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue,
- _Compare, _Alloc>::iterator
+ _Compare, _Alloc>::_Base_ptr
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_lower_bound(_Link_type __x, _Base_ptr __y,
- const _Key& __k)
- {
- while (__x != 0)
- if (!_M_impl._M_key_compare(_S_key(__x), __k))
- __y = __x, __x = _S_left(__x);
- else
- __x = _S_right(__x);
- return iterator(__y);
- }
-
- template<typename _Key, typename _Val, typename _KeyOfValue,
- typename _Compare, typename _Alloc>
- 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(_Base_ptr __x, _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
__x = _S_right(__x);
- return const_iterator(__y);
+ return __y;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue,
- _Compare, _Alloc>::iterator
+ _Compare, _Alloc>::_Base_ptr
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_upper_bound(_Link_type __x, _Base_ptr __y,
- const _Key& __k)
- {
- while (__x != 0)
- if (_M_impl._M_key_compare(__k, _S_key(__x)))
- __y = __x, __x = _S_left(__x);
- else
- __x = _S_right(__x);
- return iterator(__y);
- }
-
- template<typename _Key, typename _Val, typename _KeyOfValue,
- typename _Compare, typename _Alloc>
- 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(_Base_ptr __x, _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
__x = _S_right(__x);
- return const_iterator(__y);
+ return __y;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -2011,9 +2580,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,13 +2590,12 @@ _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);
- return pair<iterator,
- iterator>(_M_lower_bound(__x, __y, __k),
- _M_upper_bound(__xu, __yu, __k));
+ return make_pair(iterator(_M_lower_bound(__x, __y, __k)),
+ iterator(_M_upper_bound(__xu, __yu, __k)));
}
}
return pair<iterator, iterator>(iterator(__y),
@@ -2043,8 +2611,8 @@ _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 __y = _M_end();
+ _Base_ptr __x = _M_begin();
+ _Base_ptr __y = _M_end();
while (__x != 0)
{
if (_M_impl._M_key_compare(_S_key(__x), __k))
@@ -2053,13 +2621,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__y = __x, __x = _S_left(__x);
else
{
- _Const_Link_type __xu(__x);
- _Const_Base_ptr __yu(__y);
+ _Base_ptr __xu(__x);
+ _Base_ptr __yu(__y);
__y = __x, __x = _S_left(__x);
__xu = _S_right(__xu);
- return pair<const_iterator,
- const_iterator>(_M_lower_bound(__x, __y, __k),
- _M_upper_bound(__xu, __yu, __k));
+ return make_pair(const_iterator(_M_lower_bound(__x, __y, __k)),
+ const_iterator(_M_upper_bound(__xu, __yu, __k)));
}
}
return pair<const_iterator, const_iterator>(const_iterator(__y),
@@ -2107,10 +2674,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 +2706,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)) ?
@@ -2209,11 +2776,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_get_insert_hint_unique_pos(const_iterator __position,
const key_type& __k)
{
- iterator __pos = __position._M_const_cast();
typedef pair<_Base_ptr, _Base_ptr> _Res;
// end()
- if (__pos._M_node == _M_end())
+ if (__position._M_node == _M_end())
{
if (size() > 0
&& _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
@@ -2221,32 +2787,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
else
return _M_get_insert_unique_pos(__k);
}
- else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
+ else if (_M_impl._M_key_compare(__k, _S_key(__position._M_node)))
{
// First, try before...
- iterator __before = __pos;
- if (__pos._M_node == _M_leftmost()) // begin()
+ iterator __before(__position._M_node);
+ if (__position._M_node == _M_leftmost()) // begin()
return _Res(_M_leftmost(), _M_leftmost());
else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
{
if (_S_right(__before._M_node) == 0)
return _Res(0, __before._M_node);
else
- return _Res(__pos._M_node, __pos._M_node);
+ return _Res(__position._M_node, __position._M_node);
}
else
return _M_get_insert_unique_pos(__k);
}
- else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
+ else if (_M_impl._M_key_compare(_S_key(__position._M_node), __k))
{
// ... then try after.
- iterator __after = __pos;
- if (__pos._M_node == _M_rightmost())
+ iterator __after(__position._M_node);
+ if (__position._M_node == _M_rightmost())
return _Res(0, _M_rightmost());
else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
{
- if (_S_right(__pos._M_node) == 0)
- return _Res(0, __pos._M_node);
+ if (_S_right(__position._M_node) == 0)
+ return _Res(0, __position._M_node);
else
return _Res(__after._M_node, __after._M_node);
}
@@ -2255,7 +2821,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
else
// Equivalent keys.
- return _Res(__pos._M_node, 0);
+ return _Res(__position._M_node, 0);
}
template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -2294,11 +2860,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_get_insert_hint_equal_pos(const_iterator __position, const key_type&
__k)
{
- iterator __pos = __position._M_const_cast();
typedef pair<_Base_ptr, _Base_ptr> _Res;
// end()
- if (__pos._M_node == _M_end())
+ if (__position._M_node == _M_end())
{
if (size() > 0
&& !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
@@ -2306,18 +2871,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
else
return _M_get_insert_equal_pos(__k);
}
- else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
+ else if (!_M_impl._M_key_compare(_S_key(__position._M_node), __k))
{
// First, try before...
iterator __before = __pos;
- if (__pos._M_node == _M_leftmost()) // begin()
+ if (__position._M_node == _M_leftmost()) // begin()
return _Res(_M_leftmost(), _M_leftmost());
else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
{
if (_S_right(__before._M_node) == 0)
return _Res(0, __before._M_node);
else
- return _Res(__pos._M_node, __pos._M_node);
+ return _Res(__position._M_node, __position._M_node);
}
else
return _M_get_insert_equal_pos(__k);
@@ -2326,12 +2891,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
// ... then try after.
iterator __after = __pos;
- if (__pos._M_node == _M_rightmost())
+ if (__position._M_node == _M_rightmost())
return _Res(0, _M_rightmost());
else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
{
- if (_S_right(__pos._M_node) == 0)
- return _Res(0, __pos._M_node);
+ if (_S_right(__position._M_node) == 0)
+ return _Res(0, __position._M_node);
else
return _Res(__after._M_node, __after._M_node);
}
@@ -2373,15 +2938,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 +2955,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 +2972,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 +3052,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_node, this->_M_impl._M_header);
_M_drop_node(__y);
--_M_impl._M_node_count;
}
@@ -2527,7 +3090,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
find(const _Key& __k)
{
- iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
+ iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k));
return (__j == end()
|| _M_impl._M_key_compare(__k,
_S_key(__j._M_node))) ? end() : __j;
@@ -2540,7 +3103,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
find(const _Key& __k) const
{
- const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
+ const_iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k));
return (__j == end()
|| _M_impl._M_key_compare(__k,
_S_key(__j._M_node))) ? end() : __j;
@@ -2574,9 +3137,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);
+ _Node_ptr __x = static_cast<_Node_ptr>(__it._M_node);
+ _Node_ptr __L = _S_left(__x);
+ _Node_ptr __R = _S_right(__x);
if (__x->_M_color == _S_red)
if ((__L && __L->_M_color == _S_red)
@@ -2592,9 +3155,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();
+}
