On 04/12/24 19:27 +0100, François Dumont wrote:
HiI've completed the synchronization with your equivalent PR for std::list so here is the updated patch.PR updated a couple of days ago. Note that I've started to rework the patch for the same in _Hashtable.
Great, thanks.
François On 30/11/2024 18:21, Jonathan Wakely wrote:On Sat, 30 Nov 2024, 13:52 François Dumont, <frs.dum...@gmail.com> wrote: Hi I've applied all your comments below and the ones you did on the PR directly. When all new types totally seperated from the legacy types _Rb_tree_node_traits is indeed useless. Regarding _Rb_tree_helpers I got rid of it but move the insert-and-rebalance and rebalance-for-erase function to _Node_traits<>. PR updated: 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::_Node<_ValPtr> as a pointer to __rb_tree::_Node_base<_VoidPtr>. 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 _Const_Node_ptr and all methods associated with it. Sounds good! I'll take another look on Monday. libstdc++-v3/ChangeLog: * include/bits/stl_tree.h [_GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE]: New macro to control usage of the code required to support fancy allocator pointer type. (_Rb_tree_node_base::_Const_Base_ptr): Remove. (_Rb_tree_node_base::_S_minimum, _Rb_tree_node_base::_S_maximum): Remove overloads for _Const_Base_ptr. (_Rb_tree_node_base::_M_base_ptr()): New. (_Rb_tree_node_base::_M_node_ptr<_NodePtr>()): New. (_Rb_tree_node::_Link_type): Rename into... (_Rb_tree_node::_Node_ptr): ...this. (__rb_tree::_Node_base<>): New. (__rb_tree::_Header<>): New. (__rb_tree::_Node<>): New. (_Rb_tree_increment(const _Rb_tree_node_base*)): Remove declaration. (_Rb_tree_decrement(const _Rb_tree_node_base*)): Remove declaration. (_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_const_cast): Remove. (_Rb_tree_const_iterator<>::_M_node): Change type into _Base_ptr. (__rb_tree::_Iterator<>): New. (__rb_tree::_Node_traits<>): New. (_Rb_tree<>::_Node_base, _Rb_tree::_Node_type): New. (_Rb_tree<>::_Link_type): Rename into... (_Rb_tree<>::_Node_ptr): ...this. (_Rb_tree<>::_Const_Base_ptr, _Rb_tree<>::_Const_Node_ptr): Remove. (_Rb_tree<>): Adapt to generalize usage of _Base_ptr in place of former _Link_type now _Node_ptr. (_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. I've tested it in C++98/C++17/C++20 with default _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE and with it 9001. François On 18/11/2024 17:39, Jonathan Wakely wrote:On 18/11/24 06:57 +0100, François Dumont wrote: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 instd::_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.Please take a look at the _GLIBCXX_USE_ALLOC_PTR_xxx macros in https://gcc.gnu.org/pipermail/gcc-patches/2024-November/669128.html andhttps://gcc.gnu.org/pipermail/gcc-patches/2024-November/669127.html Those macros allow the fancy pointer support to be disabled, in case it will break anything for current users. Maybe more importantly, it allows the new node types to be used always, even for T*. That means we can run the entire testsuite using the new nodes without tweaking the implementation. Please consider a _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE macro (or some other name).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> <mailto: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> <mailto: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> <mailto:jwakely....@gmail.com> wrote:On Thu, 17 Oct 2024 at 20:52, François Dumont<frs.dum...@gmail.com> <mailto: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 potentialallocator::const_pointer.Do you mean consider the case whereAlloc::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 needSorry, 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>; };This only seems to be used in one place, can you just use __ptr_rebind directly in that one place?+ + template<typename _BasePtr> + static _Ptr + _S_ptr_to(_BasePtr __this) noexcept + { return pointer_traits<_Ptr>::pointer_to(*__this); }This is also only needed in exactly one place. I avoided needing this function by adding _M_base_ptr() to the node base classes. The whole of this _Rb_tree_ptr_traits class template seems unnecessary to me. Just inline the code directly into the places it's needed. You're not optimizing anything by replacing pointer_traits<T*>::pointer_to with _Rb_tree_ptr_traits<T*>::_S_ptr_to, it's still a class template specialization and a function call.+ + template<typename _BasePtr, typename _UpPtr> + static _UpPtr + _S_up_ptr_to(_BasePtr __this) noexceptpointer_to is not guaranteed to be noexcept. This appears to be a downcast, i.e. a base-to-derived cast, having "up" in the name is a bit confusing.+ { + 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;The names _BasePtr and _Base_ptr are very similar, and confusing. It looks like sometimes the template argument that is substituted for _BasePtr is sometimes a derived class (_Rb_tree_node_base) and sometimes is _ValPtr. It's never a "base" pointer. Please rename it.- 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_NOEXCEPTWhy do we need a non-const overload? The const one will work for all cases, right? I added a comment to my list patches pointing out that it's not const-correct, but is safe as long as only used carefully.+ { 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*> + { };This approaches means that the existing specializations of RB trees all get twice as many base classes. I don't see an ABI problem, and it should generate the same code for optimized builds, but increasing the inheritance depth and the number of class template instantiations gives the compiler more work to do, compiling slower, and generating additional debug info (and maybe RTTI?) Please take a look at how I did it for the linked lists, where specializations for non-fancy pointers, e.g. _List_node<T>, are mostly unchanged. They don't get any new base classes, just some new typedefs and new accessors like: _Base_ptr _M_base() { return this; } const _List_node* _M_base() const { return this; } The _List_node_traits class template is used bystd::list etc. to select whether to use _List_node<Alloc::value_type> or __list::_Node<Alloc::pointer>. All the fancy pointer support is in the new type hierarchy, __list::_Node_base, __list::_Node, and __list::_Iterator. The old types like _List_node don't really change. I found that using the __list namespace with new types reduced a lot of confusion I had between the very similar names _List_node and _List_pnode (or _List_ptr_node, or other names like that). Maybe we could call it _List::_Node instead of __list::_Node, so it's a bit closer to _List_node but still distinguishable (and would produce very slightly shorter mangled names). I didn't do that, because our convention is to name impl namespaces as __foo not _Foo. That pattern could naturally be extended to __tree::_Node (or _Tree::_Node) as well.// 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() { returnstd::__addressof(_M_value_field); } + __attribute__((__always_inline__)) const _Val* _M_valptr() const { returnstd::__addressof(_M_value_field); } #else __gnu_cxx::__aligned_membuf<_Val> _M_storage;For the new __list::_Node type I took the opportunity to replace __aligned_membuf with a union { _Val _M_data; }; which is simpler and produces the same code. We could probably make that change for the existing node types, I think it's safe, but making it only for the new _Node type means the old node type isn't affected.+ [[__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>This makes _Rb_tree_pnode_base depend on the value_type, which means you instantiate a different specialization of _Rb_tree_pnode_base for every _Rb_tree. There's no point even having a common base class if every specialization is different. You might as well just put the _M_parent/_M_left/_M_right pointers in _Rb_tree_pnode directly. The point of the node_base class is to have a common base that is not dependent on the value type, so thatstd::set<int> andstd::set<long> andstd::set<int, Cmp> all use the same node base. The way this patch works,std::set<int> will use _Rb_tree_pnode_base<int*> and std::set<long> will use _Rb_tree_pnode_base<long*>. This is why my patch for lists uses __ptr_rebind<_ValPtr, void> as the template argument to _Node_base, so that they all use _Node_base<void*>. Obviously for a fancy pointer, it will be a different specialization, sostd::list<int, A<int>> uses _Node_base<A::void_pointer>, but std::list<long, A<long>> uses the same _Node_base<A::void_pointer>.+ , _Rb_tree_node_val<typenamestd::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 ();[...]+#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_piteratorFor the linked lists, I didn't add two new iterator types, just _Iterator<_Const, _ValPtr> which is used for iterator and const_iterator. It seemed nice not to duplicate the iterator type, since the iterator and const_iterator are 95% the same. If we don't need to support C++98, we can write a single iterator implementation. If you have a single iterator implementation, you probably don't need the _Rb_tree_helpers. There would still be uses of insert-and-rebalance and rebalance-for-erase, but those could just be new overloads for fancy pointers. I don't think we need the _Rb_tree_helpers class template.+ { + 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 typenameiterator::_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);You need the iterator increment code here, but you can define it inline without the _Increment helper.+ return *this; + } + + _Self + operator++(int) _GLIBCXX_NOEXCEPT + { + _Self __tmp = *this; + _M_node = _Tree_helpers::_Increment(_M_node);This could just use ++*this. So if there's no separate const iterator implementation, there's no more use of _Increment.+ 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;Accessing a member of _Node_type here requires _Node_type to be complete, which requires _Tp to be complete. That's allowed by the standard, becausestd::map andstd::set don't support incomplete types (unlike vector and the linked lists). But we don't really ned to instantiate _Node_type here, we could use _Alloc_traits::pointer instead. [...]@@ -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));I think this relies on implicit conversion from _Node_ptr to _Base_ptr, which is not necessarily possible. It works for the _Pointer_adapter type in <ext/pointer.h> because it has a template<typename U> _Pointer_adapter(_Pointer_adapter<U>) constructor that supports implicit conversions. There seems to be a few other places with this problem. Please take a look at the Pointer type in the new test for my list and forward_list fancy ptr patches (that Pointer should probably be added to the testsuite/util/testsuite_allocator.h header for reuse). I solved these problems by adding a _M_base_ptr() function to the node_base type, which means that instead of relying on an implicit conversion from node_ptr to _Base_ptr you call node_ptr->_M_base_ptr() to get a _Base_ptr.@@ -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();This removes __pos ...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;But it's still used here.- 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;And here. I think they should both be __position._M_const_cast().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 HThis struct H occurs in several tests but seems to be unused.+{ +std::size_t + operator()(const T& t) const noexcept + { return t.i; } +}; + +struct L :std::less<T> +{ }; + +using __gnu_test::CustomPointerAlloc; + +template classstd::map<T, int, L, + CustomPointerAlloc<std::pair<const T, int>>>; + +void test01() +{ + typedef CustomPointerAlloc<std::pair<const T, int>> alloc_type; + typedefstd::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(); +}I'd be interested on your opinion on my patches for fancy pointer support in the linked lists. I think it's cleaner and requires fewer changes to the existing specializations. My changes can also be disabled by a macro (to avoid breaking any users who are somehow managing to use allocators-with-fancy-pointers with RB trees today, which could be useful unless that's completely broken today), and to be enabled for non-fancy pointers (for test coverage).
diff --git a/libstdc++-v3/include/bits/stl_tree.h
b/libstdc++-v3/include/bits/stl_tree.h
index bc27e191e8b..bed7266c688 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -66,6 +66,7 @@
#include <bits/allocator.h>
#include <bits/stl_function.h>
#include <bits/cpp_type_traits.h>
+#include <bits/ptr_traits.h>
#include <ext/alloc_traits.h>
#if __cplusplus >= 201103L
# include <ext/aligned_buffer.h>
@@ -74,6 +75,13 @@
# include <bits/node_handle.h>
#endif
+#if __cplusplus < 201103L
+# undef _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
+# define _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 0
+#elif ! defined _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
+# define _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 1
+#endif
+
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
@@ -99,7 +107,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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;
@@ -113,13 +120,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __x;
}
- static _Const_Base_ptr
- _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
- {
- while (__x->_M_left != 0) __x = __x->_M_left;
- return __x;
- }
-
static _Base_ptr
_S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
{
@@ -127,12 +127,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __x;
}
- static _Const_Base_ptr
- _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
- {
- while (__x->_M_right != 0) __x = __x->_M_right;
- return __x;
- }
+ // This is not const-correct, but it's only used in a const access path
+ // by std::_Rb_tree::_M_end() where the pointer is used to initialize a
+ // const_iterator and so constness is restored.
+ _Base_ptr
+ _M_base_ptr() const _GLIBCXX_NOEXCEPT
+ { return const_cast<_Rb_tree_node_base*>(this); }
+
+ template<typename _NodePtr>
+ _NodePtr
+ _M_node_ptr() _GLIBCXX_NOEXCEPT
+ { return static_cast<_NodePtr>(this); }
};
// Helper type offering value initialization guarantee on the compare functor.
@@ -213,7 +218,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Val>
struct _Rb_tree_node : public _Rb_tree_node_base
{
- typedef _Rb_tree_node<_Val>* _Link_type;
+ typedef _Rb_tree_node<_Val>* _Node_ptr;
#if __cplusplus < 201103L
_Val _M_value_field;
@@ -238,18 +243,136 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#endif
};
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
+namespace __rb_tree
+{
+ template<typename _VoidPtr>
+ struct _Node_base
+ {
+ using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>;
+
+ _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;
+ }
+
+ // This is not const-correct, but it's only used in a const access path
+ // by std::_Rb_tree::_M_end() where the pointer is used to initialize a
+ // const_iterator and so constness is restored.
+ _Base_ptr
+ _M_base_ptr() const
+ {
+ return pointer_traits<_Base_ptr>::pointer_to
+ (*const_cast<_Node_base*>(this));
+ }
+
+ template<typename _NodePtr>
+ _NodePtr
+ _M_node_ptr() _GLIBCXX_NOEXCEPT
+ {
+ using __ptr_traits = pointer_traits<_NodePtr>;
+ using __node_type = typename __ptr_traits::element_type;
+ auto __this = static_cast<__node_type*>(this);
+ return __ptr_traits::pointer_to(*__this);
+ }
+ };
+
+ // Helper type to manage default initialization of node count and header.
+ template<typename _NodeBase>
+ struct _Header
+ {
+ private:
+ using _Base_ptr = typename _NodeBase::_Base_ptr;
+
+ public:
+ _NodeBase _M_header;
+ size_t _M_node_count; // Keeps track of size of tree.
+
+ _Header() noexcept
+ {
+ _M_header._M_color = _S_red;
+ _M_reset();
+ }
+
+ _Header(_Header&& __x) noexcept
+ {
+ if (__x._M_header._M_parent)
+ _M_move_data(__x);
+ else
+ {
+ _M_header._M_color = _S_red;
+ _M_reset();
+ }
+ }
+
+ void
+ _M_move_data(_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_base_ptr();
+ _M_node_count = __from._M_node_count;
+
+ __from._M_reset();
+ }
+
+ void
+ _M_reset()
+ {
+ _M_header._M_parent = _Base_ptr{};
+ _M_header._M_left = _M_header._M_right = _M_header._M_base_ptr();
+ _M_node_count = 0;
+ }
+ };
+
+ template<typename _ValPtr>
+ struct _Node : public __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>
+ {
+ using value_type = typename pointer_traits<_ValPtr>::element_type;
+ using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
+
+ union
+ {
+ value_type _M_storage;
+ };
+
+ _Node() { }
+ ~_Node() { }
+ _Node(_Node&&) = delete;
+
+ value_type*
+ _M_valptr()
+ { return std::__addressof(_M_storage); }
+
+ value_type const*
+ _M_valptr() const
+ { return std::__addressof(_M_storage); }
+ };
+} // namespace __rb_tree
+#endif
+
_GLIBCXX_PURE _Rb_tree_node_base*
_Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
- _GLIBCXX_PURE const _Rb_tree_node_base*
- _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
-
_GLIBCXX_PURE _Rb_tree_node_base*
_Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
- _GLIBCXX_PURE const _Rb_tree_node_base*
- _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
-
template<typename _Tp>
struct _Rb_tree_iterator
{
@@ -260,9 +383,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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_node<_Tp>* _Node_ptr;
_Rb_tree_iterator() _GLIBCXX_NOEXCEPT
: _M_node() { }
@@ -273,49 +395,51 @@ _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&
+ _Rb_tree_iterator&
operator++() _GLIBCXX_NOEXCEPT
{
_M_node = _Rb_tree_increment(_M_node);
return *this;
}
- _Self
+ _Rb_tree_iterator
operator++(int) _GLIBCXX_NOEXCEPT
{
- _Self __tmp = *this;
+ _Rb_tree_iterator __tmp = *this;
_M_node = _Rb_tree_increment(_M_node);
return __tmp;
}
- _Self&
+ _Rb_tree_iterator&
operator--() _GLIBCXX_NOEXCEPT
{
_M_node = _Rb_tree_decrement(_M_node);
return *this;
}
- _Self
+ _Rb_tree_iterator
operator--(int) _GLIBCXX_NOEXCEPT
{
- _Self __tmp = *this;
+ _Rb_tree_iterator __tmp = *this;
_M_node = _Rb_tree_decrement(_M_node);
return __tmp;
}
friend bool
- operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
+ operator==(const _Rb_tree_iterator& __x,
+ const _Rb_tree_iterator& __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
+ operator!=(const _Rb_tree_iterator& __x,
+ const _Rb_tree_iterator& __y) _GLIBCXX_NOEXCEPT
{ return __x._M_node != __y._M_node; }
#endif
@@ -334,9 +458,8 @@ _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_node_base::_Base_ptr _Base_ptr;
+ typedef const _Rb_tree_node<_Tp>* _Node_ptr;
_Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
: _M_node() { }
@@ -348,55 +471,53 @@ _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&
+ _Rb_tree_const_iterator&
operator++() _GLIBCXX_NOEXCEPT
{
_M_node = _Rb_tree_increment(_M_node);
return *this;
}
- _Self
+ _Rb_tree_const_iterator
operator++(int) _GLIBCXX_NOEXCEPT
{
- _Self __tmp = *this;
+ _Rb_tree_const_iterator __tmp = *this;
_M_node = _Rb_tree_increment(_M_node);
return __tmp;
}
- _Self&
+ _Rb_tree_const_iterator&
operator--() _GLIBCXX_NOEXCEPT
{
_M_node = _Rb_tree_decrement(_M_node);
return *this;
}
- _Self
+ _Rb_tree_const_iterator
operator--(int) _GLIBCXX_NOEXCEPT
{
- _Self __tmp = *this;
+ _Rb_tree_const_iterator __tmp = *this;
_M_node = _Rb_tree_decrement(_M_node);
return __tmp;
}
friend bool
- operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
+ operator==(const _Rb_tree_const_iterator& __x,
+ const _Rb_tree_const_iterator& __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
+ operator!=(const _Rb_tree_const_iterator& __x,
+ const _Rb_tree_const_iterator& __y) _GLIBCXX_NOEXCEPT
{ return __x._M_node != __y._M_node; }
#endif
@@ -415,6 +536,485 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
_Rb_tree_node_base& __header) throw ();
+namespace __rb_tree
+{
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
+ template<bool _Const, typename _ValPtr>
+ struct _Iterator
+ {
+ template<typename _Tp>
+ using __maybe_const = __conditional_t<_Const, const _Tp, _Tp>;
+
+ using __ptr_traits = pointer_traits<_ValPtr>;
+ using value_type = typename __ptr_traits::element_type;
+ using reference = __maybe_const<value_type>&;
+ using pointer = __maybe_const<value_type>*;
+
+ using iterator_category = bidirectional_iterator_tag;
+ using difference_type = ptrdiff_t;
+
+ using _Node = __rb_tree::_Node<_ValPtr>;
+ using _Node_base = __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>;
+ using _Base_ptr = typename _Node_base::_Base_ptr;
+
+ _Iterator() _GLIBCXX_NOEXCEPT
+ : _M_node() { }
+
+ constexpr explicit
+ _Iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
+ : _M_node(__x) { }
+
+#if __cplusplus >= 201103L
+ _Iterator(const _Iterator&) = default;
+ _Iterator& operator=(const _Iterator&) = default;
+#endif
+
+#ifdef __glibcxx_concepts
+ constexpr
+ _Iterator(const _Iterator<false, _ValPtr>& __it) requires _Const
+#else
+ template<bool _OtherConst,
+ typename = __enable_if_t<_Const && !_OtherConst>>
+ constexpr
+ _Iterator(const _Iterator<_OtherConst, _ValPtr>& __it)
+#endif
+ : _M_node(__it._M_node) { }
+
+ [[__nodiscard__]]
+ reference
+ operator*() const _GLIBCXX_NOEXCEPT
+ { return *static_cast<_Node&>(*_M_node)._M_valptr(); }
+
+ [[__nodiscard__]]
+ pointer
+ operator->() const _GLIBCXX_NOEXCEPT
+ { return static_cast<_Node&>(*_M_node)._M_valptr(); }
+
+ _GLIBCXX14_CONSTEXPR _Iterator&
+ operator++() _GLIBCXX_NOEXCEPT
+ {
+ if (_M_node->_M_right)
+ {
+ _M_node = _M_node->_M_right;
+ while (_M_node->_M_left)
+ _M_node = _M_node->_M_left;
+ }
+ else
+ {
+ _Base_ptr __y = _M_node->_M_parent;
+ while (_M_node == __y->_M_right)
+ {
+ _M_node = __y;
+ __y = __y->_M_parent;
+ }
+ if (_M_node->_M_right != __y)
+ _M_node = __y;
+ }
+
+ return *this;
+ }
+
+ _GLIBCXX14_CONSTEXPR _Iterator
+ operator++(int) _GLIBCXX_NOEXCEPT
+ {
+ _Iterator __tmp(this->_M_node);
+ ++*this;
+ return __tmp;
+ }
+
+ _GLIBCXX14_CONSTEXPR _Iterator&
+ operator--() _GLIBCXX_NOEXCEPT
+ {
+ if (_M_node->_M_color == _S_red
+ && _M_node->_M_parent->_M_parent == _M_node)
+ _M_node = _M_node->_M_right;
+ else if (_M_node->_M_left)
+ {
+ _Base_ptr __y = _M_node->_M_left;
+ while (__y->_M_right)
+ __y = __y->_M_right;
+ _M_node = __y;
+ }
+ else
+ {
+ _Base_ptr __y = _M_node->_M_parent;
+ while (_M_node == __y->_M_left)
+ {
+ _M_node = __y;
+ __y = __y->_M_parent;
+ }
+ _M_node = __y;
+ }
+ return *this;
+ }
+
+ _GLIBCXX14_CONSTEXPR _Iterator
+ operator--(int) _GLIBCXX_NOEXCEPT
+ {
+ _Iterator __tmp(this->_M_node);
+ --*this;
+ return __tmp;
+ }
+
+ [[__nodiscard__]]
+ friend bool
+ operator==(const _Iterator& __x, const _Iterator& __y) _GLIBCXX_NOEXCEPT
+ { return __x._M_node == __y._M_node; }
+
+#if ! __cpp_lib_three_way_comparison
+ [[__nodiscard__]]
+ friend bool
+ operator!=(const _Iterator& __x, const _Iterator& __y) _GLIBCXX_NOEXCEPT
+ { return __x._M_node != __y._M_node; }
+#endif
+
+ _Base_ptr _M_node;
+ };
+#endif // USE_ALLOC_PTR_FOR_RB_TREE
+
+ // Determine the node and iterator types used by std::_Rb_tree.
+ template<typename _Val, typename _Ptr>
+ struct _Node_traits;
+
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE <= 9000
+ // Specialization for the simple case where the allocator's pointer type
+ // is the same type as value_type*.
+ // For ABI compatibility we can't change the types used for this case.
+ template<typename _Val>
+ struct _Node_traits<_Val, _Val*>
+ {
+ typedef _Rb_tree_node<_Val> _Node;
+ typedef _Rb_tree_node_base _Node_base;
+ typedef _Rb_tree_header _Header_t;
+ typedef _Rb_tree_iterator<_Val> _Iterator;
+ typedef _Rb_tree_const_iterator<_Val> _Const_iterator;
+
+ __attribute__((__nonnull__))
+ static void
+ _S_insert_and_rebalance(const bool __insert_left,
+ _Node_base* __x, _Node_base* __p,
+ _Node_base& __header) _GLIBCXX_USE_NOEXCEPT
+ {
+ return _Rb_tree_insert_and_rebalance(__insert_left, __x, __p, __header);
+ }
+
+ __attribute__((__nonnull__,__returns_nonnull__))
+ static _Node_base*
+ _S_rebalance_for_erase(_Node_base* const __z,
+ _Node_base& __header) _GLIBCXX_USE_NOEXCEPT
+ { return _Rb_tree_rebalance_for_erase(__z, __header); }
+ };
+#endif
+
+#if ! _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
+ // Always use the T* specialization.
+ template<typename _Val, typename _Ptr>
+ struct _Node_traits
+ : _Node_traits<_Val, _Val*>
+ { };
+#else
+ // Primary template used when the allocator uses fancy pointers.
+ template<typename _Val, typename _ValPtr>
+ struct _Node_traits
+ {
+ using _Node = __rb_tree::_Node<_ValPtr>;
+ using _Node_base = __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>;
+ using _Header_t = __rb_tree::_Header<_Node_base>;
+ using _Iterator = __rb_tree::_Iterator<false, _ValPtr>;
+ using _Const_iterator = __rb_tree::_Iterator<true, _ValPtr>;
+
+ using _Base_ptr = typename _Node_base::_Base_ptr;
+
+ 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,
+ _Node_base& __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, _Node_base& __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 = _Node_base::_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 = _Node_base::_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;
+ }
+ };
+#endif
+} // namespace __rb_tree
+
#if __cplusplus > 201402L
template<typename _Tree1, typename _Cmp2>
struct _Rb_tree_merge_helper { };
@@ -425,15 +1025,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
class _Rb_tree
{
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
- rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
+ rebind<_Val>::other _Val_alloc_type;
+
+ typedef __gnu_cxx::__alloc_traits<_Val_alloc_type> _Val_alloc_traits;
+ typedef typename _Val_alloc_traits::pointer _ValPtr;
+ typedef __rb_tree::_Node_traits<_Val, _ValPtr> _Node_traits;
+
+ typedef typename _Node_traits::_Node_base _Node_base;
+ typedef typename _Node_traits::_Node _Node;
+
+ typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
+ rebind<_Node>::other _Node_allocator;
- typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
+ typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Node_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_alloc_traits::pointer _Node_ptr;
private:
// Functor recycling a pool of nodes and using allocation once the pool
@@ -445,13 +1053,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
if (_M_root)
{
- _M_root->_M_parent = 0;
+ _M_root->_M_parent = _Base_ptr();
if (_M_nodes->_M_left)
_M_nodes = _M_nodes->_M_left;
}
else
- _M_nodes = 0;
+ _M_nodes = _Base_ptr();
}
#if __cplusplus >= 201103L
@@ -459,13 +1067,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
Changing this from a node pointer to a base pointer seems to weaken the API. We know it returns a pointer to a node, so can it return the correct type?
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);
@@ -489,7 +1097,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
if (_M_nodes->_M_right == __node)
{
- _M_nodes->_M_right = 0;
+ _M_nodes->_M_right = _Base_ptr();
if (_M_nodes->_M_left)
{
@@ -503,10 +1111,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
}
else // __node is on the left.
- _M_nodes->_M_left = 0;
+ _M_nodes->_M_left = _Base_ptr();
}
else
- _M_root = 0;
+ _M_root = _Base_ptr();
return __node;
}
@@ -524,9 +1132,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
: _M_t(__t) { }
template<typename _Arg>
- _Link_type
+ _Base_ptr
Same comment here.
operator()(_GLIBCXX_FWDREF(_Arg) __arg) const
- { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
+ {
+ return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
+ }
private:
_Rb_tree& _M_t;
@@ -556,18 +1166,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); }
+ { return _Node_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
+ {
+ _Node_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)
And can this be left as _Node_ptr instead of changed to _Base_ptr? Then it wouldn't need the static_cast, and the callers wouldn't need to use _M_base_ptr(). Logically, it has to be a _Node_ptr or the cast isn't valid anyway. There seem to be several places like this where we're giving up valuable type information by using _base_ptr instead of _Node_ptr. Is that really necessary? If we have a _Node_ptr we can always get a _Base_ptr easily by calling _M_base_ptr(). Is it a constness thing, because _M_begin() const was changed to return _Base_ptr instead of _Const_link_ptr?
{
+ _Node_ptr __node = static_cast<_Node_ptr>(__p);
__try
{ get_allocator().construct(__node->_M_valptr(), __x); }
__catch(...)
@@ -577,79 +1191,83 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
}
- _Link_type
+ _Base_ptr
_M_create_node(const value_type& __x)
{
- _Link_type __tmp = _M_get_node();
+ _Base_ptr __tmp = _M_get_node()->_M_base_ptr();
_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& __node = static_cast<_Node&>(*__p);
__try
{
- ::new(__node) _Rb_tree_node<_Val>;
- _Alloc_traits::construct(_M_get_Node_allocator(),
- __node->_M_valptr(),
- std::forward<_Args>(__args)...);
+ ::new(std::__addressof(__node)) _Node;
+ _Node_alloc_traits::construct(_M_get_Node_allocator(),
+ __node._M_valptr(),
+ std::forward<_Args>(__args)...);
}
__catch(...)
{
- __node->~_Rb_tree_node<_Val>();
- _M_put_node(__node);
+ __node.~_Node();
+ _M_put_node(__p);
__throw_exception_again;
}
}
template<typename... _Args>
- _Link_type
+ _Base_ptr
_M_create_node(_Args&&... __args)
{
- _Link_type __tmp = _M_get_node();
+ _Base_ptr __tmp = _M_get_node()->_M_base_ptr();
_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& __node = static_cast<_Node&>(*__p);
+ _Node_alloc_traits::destroy(_M_get_Node_allocator(),
+ __node._M_valptr());
+ __node.~_Node();
#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&>(*__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 +1278,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;
@@ -672,9 +1290,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{ }
_Rb_tree_impl(const _Rb_tree_impl& __x)
- : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x))
+ : _Node_allocator(_Node_alloc_traits::_S_select_on_copy(__x))
, _Base_key_compare(__x._M_key_compare)
- , _Rb_tree_header()
+ , _Header_t()
{ }
#if __cplusplus < 201103L
@@ -694,7 +1312,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 +1328,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 +1336,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 +1344,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_base_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 +1375,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
# endif // C++17
#endif // C++11
- return _KeyOfValue()(*__x->_M_valptr());
+ return _KeyOfValue()(*static_cast<const _Node&>(*__x)._M_valptr());
}
- static _Link_type
- _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
- { return static_cast<_Link_type>(__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
- _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)); }
-
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); }
+ _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
+ { return __x->_M_left; }
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); }
+ _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
+ { return __x->_M_right; }
public:
- typedef _Rb_tree_iterator<value_type> iterator;
- typedef _Rb_tree_const_iterator<value_type> const_iterator;
+ typedef typename _Node_traits::_Iterator iterator;
+ typedef typename _Node_traits::_Const_iterator const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
@@ -846,7 +1421,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 +1432,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 +1454,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() = _Node_base::_S_minimum(__root);
+ _M_rightmost() = _Node_base::_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 +1477,14 @@ _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,
- const _Key& __k);
-
- 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 +1502,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 +1514,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 +1533,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{});
}
@@ -974,9 +1541,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
noexcept( noexcept(
_Rb_tree(std::declval<_Rb_tree&&>(), std::declval<_Node_allocator&&>(),
- std::declval<typename _Alloc_traits::is_always_equal>())) )
+ std::declval<typename _Node_alloc_traits::is_always_equal>()))
)
: _Rb_tree(std::move(__x), std::move(__a),
- typename _Alloc_traits::is_always_equal{})
+ typename _Node_alloc_traits::is_always_equal{})
{ }
#endif
@@ -1001,11 +1568,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator
end() _GLIBCXX_NOEXCEPT
- { return iterator(&this->_M_impl._M_header); }
+ { return iterator(_M_end()); }
const_iterator
end() const _GLIBCXX_NOEXCEPT
- { return const_iterator(&this->_M_impl._M_header); }
+ { return const_iterator(_M_end()); }
reverse_iterator
rbegin() _GLIBCXX_NOEXCEPT
@@ -1033,7 +1600,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
size_type
max_size() const _GLIBCXX_NOEXCEPT
- { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
+ { return _Node_alloc_traits::max_size(_M_get_Node_allocator()); }
void
swap(_Rb_tree& __t)
@@ -1194,7 +1761,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 +1802,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 +1833,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 +1866,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 +1874,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,21 +1891,12 @@ _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();
auto __y = _M_end();
- while (__x != 0)
+ while (__x)
if (!_M_impl._M_key_compare(_S_key(__x), __k))
{
__y = __x;
@@ -1340,26 +1904,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
else
__x = _S_right(__x);
- return const_iterator(__y);
+ return __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();
- }
-
- 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();
auto __y = _M_end();
- while (__x != 0)
+ while (__x)
if (_M_impl._M_key_compare(__k, _S_key(__x)))
{
__y = __x;
@@ -1367,7 +1922,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
else
__x = _S_right(__x);
- return const_iterator(__y);
+ return __y;
}
template<typename _Kt,
@@ -1377,7 +1932,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 +1941,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)))
@@ -1401,7 +1957,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#if __cplusplus >= 201103L
_Rb_tree&
operator=(_Rb_tree&&)
- noexcept(_Alloc_traits::_S_nothrow_move()
+ noexcept(_Node_alloc_traits::_S_nothrow_move()
&& is_nothrow_move_assignable<_Compare>::value);
template<typename _Iterator>
@@ -1449,8 +2005,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto __res = _M_get_insert_unique_pos(__nh._M_key());
if (__res.second)
{
- __ret.position
- = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
+ __ret.position = _M_insert_node(__res.first, __res.second,
+ __nh._M_ptr->_M_base_ptr());
__nh.release();
__ret.inserted = true;
}
@@ -1476,9 +2032,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
auto __res = _M_get_insert_equal_pos(__nh._M_key());
if (__res.second)
- __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
+ __ret = _M_insert_node(__res.first, __res.second,
+ __nh._M_ptr->_M_base_ptr());
else
- __ret = _M_insert_equal_lower_node(__nh._M_ptr);
+ __ret = _M_insert_equal_lower_node(__nh._M_ptr->_M_base_ptr());
__nh.release();
}
return __ret;
@@ -1497,7 +2054,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key());
if (__res.second)
{
- __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
+ __ret = _M_insert_node(__res.first, __res.second,
+ __nh._M_ptr->_M_base_ptr());
__nh.release();
}
else
@@ -1518,9 +2076,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key());
if (__res.second)
- __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
+ __ret = _M_insert_node(__res.first, __res.second,
+ __nh._M_ptr->_M_base_ptr());
else
- __ret = _M_insert_equal_lower_node(__nh._M_ptr);
+ __ret = _M_insert_equal_lower_node(__nh._M_ptr->_M_base_ptr());
__nh.release();
}
return __ret;
@@ -1530,10 +2089,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 = _Node_traits::_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 +2127,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 = _Node_traits::_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 +2148,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 = _Node_traits::_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 +2224,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
_Rb_tree& _M_t;
- _Link_type _M_node;
+ _Base_ptr _M_node;
};
#endif // C++11
};
@@ -1704,7 +2262,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 +2281,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();
@@ -1735,11 +2293,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
operator=(_Rb_tree&& __x)
- noexcept(_Alloc_traits::_S_nothrow_move()
+ noexcept(_Node_alloc_traits::_S_nothrow_move()
&& is_nothrow_move_assignable<_Compare>::value)
{
_M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
- _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>());
+ _M_move_assign(__x,
+ __bool_constant<_Node_alloc_traits::_S_nothrow_move()>());
return *this;
}
@@ -1780,11 +2339,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
// Note that _Key may be a constant type.
#if __cplusplus >= 201103L
- if (_Alloc_traits::_S_propagate_on_copy_assign())
+ if (_Node_alloc_traits::_S_propagate_on_copy_assign())
{
auto& __this_alloc = this->_M_get_Node_allocator();
auto& __that_alloc = __x._M_get_Node_allocator();
- if (!_Alloc_traits::_S_always_equal()
+ if (!_Node_alloc_traits::_S_always_equal()
&& __this_alloc != __that_alloc)
{
// Replacement allocator cannot free existing storage, we need
@@ -1798,7 +2357,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);
}
@@ -1822,14 +2381,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#endif
_NodeGen& __node_gen)
{
- bool __insert_left = (__x != 0 || __p == _M_end()
+ bool __insert_left = (__x || __p == _M_end()
|| _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);
+ _Node_traits::_S_insert_and_rebalance
+ (__insert_left, __z, __p, this->_M_impl._M_header);
++_M_impl._M_node_count;
return iterator(__z);
}
@@ -1851,10 +2410,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
|| !_M_impl._M_key_compare(_S_key(__p),
_KeyOfValue()(__v)));
- _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
-
- _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
- this->_M_impl._M_header);
+ _Base_ptr __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
+ _Node_traits::_S_insert_and_rebalance
+ (__insert_left, __z, __p, this->_M_impl._M_header);
++_M_impl._M_node_count;
return iterator(__z);
}
@@ -1872,9 +2430,9 @@ _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)
+ while (__x)
{
__y = __x;
__x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
@@ -1886,12 +2444,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
@@ -1902,9 +2460,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__p = __top;
__x = _S_left(__x);
- while (__x != 0)
+ while (__x)
{
- _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 +2484,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)
+ while (__x)
{
_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 +2499,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);
- }
-
- template<typename _Key, typename _Val, typename _KeyOfValue,
- typename _Compare, typename _Alloc>
- 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,
- 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);
+ return __y;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue,
- _Compare, _Alloc>::const_iterator
+ _Compare, _Alloc>::_Base_ptr
_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 +2537,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 +2547,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,9 +2568,9 @@ _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();
- while (__x != 0)
+ _Base_ptr __x = _M_begin();
+ _Base_ptr __y = _M_end();
+ while (__x)
{
if (_M_impl._M_key_compare(_S_key(__x), __k))
__x = _S_right(__x);
@@ -2053,13 +2578,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),
@@ -2073,12 +2597,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
swap(_Rb_tree& __t)
_GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
{
- if (_M_root() == 0)
+ if (!_M_root())
{
- if (__t._M_root() != 0)
+ if (__t._M_root())
_M_impl._M_move_data(__t._M_impl);
}
- else if (__t._M_root() == 0)
+ else if (!__t._M_root())
__t._M_impl._M_move_data(_M_impl);
else
{
@@ -2093,8 +2617,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// No need to swap header's color as it does not change.
std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
- _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
- __t._M_get_Node_allocator());
+ _Node_alloc_traits::_S_on_swap(_M_get_Node_allocator(),
+ __t._M_get_Node_allocator());
}
template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -2107,10 +2631,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));
@@ -2126,7 +2650,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
return _Res(__x, __y);
- return _Res(__j._M_node, 0);
+ return _Res(__j._M_node, _Base_ptr());
}
template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -2139,9 +2663,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,44 +2733,43 @@ _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))
- return _Res(0, _M_rightmost());
+ return _Res(_Base_ptr(), _M_rightmost());
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);
+ if (!_S_right(__before._M_node))
+ return _Res(_Base_ptr(), __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())
- return _Res(0, _M_rightmost());
+ iterator __after(__position._M_node);
+ if (__position._M_node == _M_rightmost())
+ return _Res(_Base_ptr(), _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))
+ return _Res(_Base_ptr(), __position._M_node);
else
return _Res(__after._M_node, __after._M_node);
}
@@ -2255,7 +2778,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
else
// Equivalent keys.
- return _Res(__pos._M_node, 0);
+ return _Res(__position._M_node, _Base_ptr());
}
template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -2294,30 +2817,29 @@ _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())))
- return _Res(0, _M_rightmost());
+ return _Res(_Base_ptr(), _M_rightmost());
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()
+ 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(__k, _S_key((--__before)._M_node)))
{
- if (_S_right(__before._M_node) == 0)
- return _Res(0, __before._M_node);
+ if (!_S_right(__before._M_node))
+ return _Res(_Base_ptr(), __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);
@@ -2325,18 +2847,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
else
{
// ... then try after.
- iterator __after = __pos;
- if (__pos._M_node == _M_rightmost())
- return _Res(0, _M_rightmost());
+ iterator __after(__position._M_node);
+ if (__position._M_node == _M_rightmost())
+ return _Res(_Base_ptr(), _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))
+ return _Res(_Base_ptr(), __position._M_node);
else
return _Res(__after._M_node, __after._M_node);
}
else
- return _Res(0, 0);
+ return _Res(_Base_ptr(), _Base_ptr());
}
}
@@ -2373,15 +2895,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()
+ bool __insert_left = (__x || __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);
+ _Node_traits::_S_insert_and_rebalance
+ (__insert_left, __z, __p, this->_M_impl._M_header);
++_M_impl._M_node_count;
return iterator(__z);
}
@@ -2390,15 +2912,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);
+ _Node_traits::_S_insert_and_rebalance
+ (__insert_left, __z, __p, this->_M_impl._M_header);
++_M_impl._M_node_count;
return iterator(__z);
}
@@ -2407,12 +2929,12 @@ _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)
+ while (__x)
{
__y = __x;
__x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
@@ -2487,10 +3009,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 = _Node_traits::_S_rebalance_for_erase
+ (__position._M_node, this->_M_impl._M_header);
_M_drop_node(__y);
--_M_impl._M_node_count;
}
@@ -2527,7 +3047,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 +3060,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 +3094,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);
+ _Base_ptr __x = __it._M_node;
+ _Base_ptr __L = _S_left(__x);
+ _Base_ptr __R = _S_right(__x);
if (__x->_M_color == _S_red)
if ((__L && __L->_M_color == _S_red)
@@ -2592,9 +3112,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return false;
}
- if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
+ if (_M_leftmost() != _Node_base::_S_minimum(_M_root()))
return false;
- if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
+ if (_M_rightmost() != _Node_base::_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..3d83738f86b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/allocator/ext_ptr.cc
@@ -0,0 +1,37 @@
+// { 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 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..41689ef43b7
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multimap/allocator/ext_ptr.cc
@@ -0,0 +1,33 @@
+// { 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 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..589e6b0a617
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/allocator/ext_ptr.cc
@@ -0,0 +1,32 @@
+// { 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 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..bbcf32b20be
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/allocator/ext_ptr.cc
@@ -0,0 +1,32 @@
+// { 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 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();
+}
