// xtree internal header #ifndef _XTREE_ #define _XTREE_ #include #include #include #if _HAS_CPP17 #include #endif /* _HAS_CPP17 */ #if defined(__ghs) #include #endif /* defined(__ghs) */ #if defined(__ghs) #pragma ghs start_cxx_lib_header #pragma ghs startdata #if defined(__ghs_max_pack_value) #pragma pack (push, __ghs_max_pack_value) #endif /* defined(__ghs_max_pack_value) */ #endif /* defined(__ghs) */ _STD_BEGIN // CLASS _Bad_tree_node_access class _Bad_tree_node_access : public logic_error { // signals access attempt for an empty node_type object public: typedef logic_error _Mybase; explicit _Bad_tree_node_access(const string& _Message) : _Mybase(_Message.c_str()) { // construct from message string } explicit _Bad_tree_node_access( const char *_Message = "map/set: access to empty node_type object") : _Mybase(_Message) { // construct from message string } }; // TEMPLATE CLASS _Tree_unchecked_const_iterator template class _Tree_unchecked_const_iterator : public _Iterator012 { // unchecked iterator for nonmutable tree public: typedef _Tree_unchecked_const_iterator<_Mytree, _Base> _Myiter; typedef bidirectional_iterator_tag iterator_category; typedef typename _Mytree::_Nodeptr _Nodeptr; typedef typename _Mytree::value_type value_type; typedef typename _Mytree::difference_type difference_type; typedef typename _Mytree::const_pointer pointer; typedef typename _Mytree::const_reference reference; _Tree_unchecked_const_iterator() #if defined(__ghs) && _HAS_CPP11 // C++11 does not require that the (possibly user provided) // pointer type must be initializable with 0. Use nullptr instead. : _Ptr(nullptr) #else : _Ptr(0) #endif /* defined(__ghs) && _HAS_CPP11 */ { // construct with null node pointer } _Tree_unchecked_const_iterator(_Nodeptr _Pnode, const _Mytree *_Plist) : _Ptr(_Pnode) { // construct with node pointer _Pnode this->_Adopt(_Plist); } #if defined(__ghs) // PJP-B06 _Tree_unchecked_const_iterator(_Nodeptr _Pnode) : _Ptr(_Pnode) { // construct with node pointer _Pnode } #endif /* __ghs */ reference operator*() const { // return designated value return (_Mytree::_Myval(_Ptr)); } pointer operator->() const { // return pointer to class object return (_POINTER_TO(**this)); } _Myiter& operator++() { // preincrement if (_Mytree::_Isnil(_Ptr)) ; // end() shouldn't be incremented, don't move else if (!_Mytree::_Isnil(_Mytree::_Right(_Ptr))) _Ptr = _Mytree::_Min( _Mytree::_Right(_Ptr)); // ==> smallest of right subtree else { // climb looking for right subtree _Nodeptr _Pnode; while (!_Mytree::_Isnil(_Pnode = _Mytree::_Parent(_Ptr)) && _Ptr == _Mytree::_Right(_Pnode)) _Ptr = _Pnode; // ==> parent while right subtree _Ptr = _Pnode; // ==> parent (head if end()) } return (*this); } _Myiter operator++(int) { // postincrement _Myiter _Tmp = *this; ++*this; return (_Tmp); } _Myiter& operator--() { // predecrement if (_Mytree::_Isnil(_Ptr)) _Ptr = _Mytree::_Right(_Ptr); // end() ==> rightmost else if (!_Mytree::_Isnil(_Mytree::_Left(_Ptr))) _Ptr = _Mytree::_Max( _Mytree::_Left(_Ptr)); // ==> largest of left subtree else { // climb looking for left subtree _Nodeptr _Pnode; while (!_Mytree::_Isnil(_Pnode = _Mytree::_Parent(_Ptr)) && _Ptr == _Mytree::_Left(_Pnode)) _Ptr = _Pnode; // ==> parent while left subtree if (_Mytree::_Isnil(_Ptr)) ; // begin() shouldn't be decremented, don't move else _Ptr = _Pnode; // ==> parent if not head } return (*this); } _Myiter operator--(int) { // postdecrement _Myiter _Tmp = *this; --*this; return (_Tmp); } bool operator==(const _Myiter& _Right) const { // test for iterator equality return (_Ptr == _Right._Ptr); } bool operator!=(const _Myiter& _Right) const { // test for iterator inequality return (!(*this == _Right)); } _Nodeptr _Mynode() const { // return node pointer return (_Ptr); } _Nodeptr _Ptr; // pointer to node }; // TEMPLATE CLASS _Tree_unchecked_iterator template class _Tree_unchecked_iterator : public _Tree_unchecked_const_iterator<_Mytree> { // unchecked iterator for mutable tree public: typedef _Tree_unchecked_iterator<_Mytree> _Myiter; typedef _Tree_unchecked_const_iterator<_Mytree> _Mybase; typedef bidirectional_iterator_tag iterator_category; typedef typename _Mytree::_Nodeptr _Nodeptr; typedef typename _Mytree::value_type value_type; typedef typename _Mytree::difference_type difference_type; typedef typename _Mytree::pointer pointer; typedef typename _Mytree::reference reference; _Tree_unchecked_iterator() { // construct with null node } _Tree_unchecked_iterator(_Nodeptr _Pnode, const _Mytree *_Plist) : _Mybase(_Pnode, _Plist) { // construct with node pointer _Pnode } #if defined(__ghs) // PJP-B06 _Tree_unchecked_iterator(_Nodeptr _Pnode) : _Mybase(_Pnode) { // construct with node pointer _Pnode } #endif /* __ghs */ reference operator*() const { // return designated value return ((reference)**(_Mybase *)this); } pointer operator->() const { // return pointer to class object return (_POINTER_TO(**this)); } _Myiter& operator++() { // preincrement ++(*(_Mybase *)this); return (*this); } _Myiter operator++(int) { // postincrement _Myiter _Tmp = *this; ++*this; return (_Tmp); } _Myiter& operator--() { // predecrement --(*(_Mybase *)this); return (*this); } _Myiter operator--(int) { // postdecrement _Myiter _Tmp = *this; --*this; return (_Tmp); } }; // TEMPLATE CLASS _Tree_const_iterator template class _Tree_const_iterator : public _Tree_unchecked_const_iterator<_Mytree, _Iterator_base> { // iterator for nonmutable tree public: typedef _Tree_const_iterator<_Mytree> _Myiter; typedef _Tree_unchecked_const_iterator<_Mytree, _Iterator_base> _Mybase; typedef bidirectional_iterator_tag iterator_category; typedef typename _Mytree::_Nodeptr _Nodeptr; typedef typename _Mytree::value_type value_type; typedef typename _Mytree::difference_type difference_type; typedef typename _Mytree::const_pointer pointer; typedef typename _Mytree::const_reference reference; _Tree_const_iterator() : _Mybase() { // construct with null node pointer } _Tree_const_iterator(_Nodeptr _Pnode, const _Mytree *_Plist) : _Mybase(_Pnode, _Plist) { // construct with node pointer _Pnode } #if defined(__ghs) // PJP-B06 #if _HAS_CPP17 && !defined(__IMPLICIT_ONE_ARG_CONSTRUCTOR_FOR_TREE_ITERATOR) explicit #endif _Tree_const_iterator(_Nodeptr _Pnode) : _Mybase(_Pnode) { // construct with node pointer _Pnode } #endif /* __ghs */ typedef _Tree_unchecked_const_iterator<_Mytree> _Unchecked_type; _Myiter& _Rechecked(_Unchecked_type _Right) { // reset from unchecked iterator this->_Ptr = _Right._Ptr; return (*this); } _Unchecked_type _Unchecked() const { // make an unchecked iterator return (_Unchecked_type(this->_Ptr, (_Mytree *)this->_Getcont())); } reference operator*() const { // return designated value #if _ITERATOR_DEBUG_LEVEL == 2 if (this->_Getcont() == 0 || this->_Ptr == 0 || this->_Ptr == ((_Mytree *)this->_Getcont())->_Myhead) { // report error _DEBUG_ERROR("map/set iterator not dereferencable"); _SCL_SECURE_OUT_OF_RANGE; } #elif _ITERATOR_DEBUG_LEVEL == 1 _SCL_SECURE_VALIDATE(this->_Getcont() != 0 && this->_Ptr != 0); _SCL_SECURE_VALIDATE_RANGE(this->_Ptr != ((_Mytree *)this->_Getcont())->_Myhead); #endif /* _ITERATOR_DEBUG_LEVEL */ return (_Mytree::_Myval(this->_Ptr)); } pointer operator->() const { // return pointer to class object return (_POINTER_TO(**this)); } _Myiter& operator++() { // preincrement #if _ITERATOR_DEBUG_LEVEL == 2 if (this->_Getcont() == 0 || this->_Ptr == 0 || _Mytree::_Isnil(this->_Ptr)) { // report error _DEBUG_ERROR("map/set iterator not incrementable"); _SCL_SECURE_OUT_OF_RANGE; } #elif _ITERATOR_DEBUG_LEVEL == 1 _SCL_SECURE_VALIDATE(this->_Getcont() != 0 && this->_Ptr != 0); _SCL_SECURE_VALIDATE_RANGE(!_Mytree::_Isnil(this->_Ptr)); #endif /* _ITERATOR_DEBUG_LEVEL */ ++(*(_Mybase *)this); return (*this); } _Myiter operator++(int) { // postincrement _Myiter _Tmp = *this; ++*this; return (_Tmp); } _Myiter& operator--() { // predecrement #if _ITERATOR_DEBUG_LEVEL == 2 if (this->_Getcont() == 0 || this->_Ptr == 0) { // report error _DEBUG_ERROR("map/set iterator not decrementable"); _SCL_SECURE_OUT_OF_RANGE; } _Nodeptr _Ptrsav = this->_Ptr; --(*(_Mybase *)this); if (_Ptrsav == this->_Ptr) { // report error _DEBUG_ERROR("map/set iterator not decrementable"); _SCL_SECURE_OUT_OF_RANGE; } #elif _ITERATOR_DEBUG_LEVEL == 1 _SCL_SECURE_VALIDATE(this->_Getcont() != 0 && this->_Ptr != 0); _Nodeptr _Ptrsav = this->_Ptr; --(*(_Mybase *)this); _SCL_SECURE_VALIDATE(_Ptrsav != this->_Ptr); #else /* _ITERATOR_DEBUG_LEVEL == 0 */ --(*(_Mybase *)this); #endif /* _ITERATOR_DEBUG_LEVEL */ return (*this); } _Myiter operator--(int) { // postdecrement _Myiter _Tmp = *this; --*this; return (_Tmp); } bool operator==(const _Myiter& _Right) const { // test for iterator equality #if _ITERATOR_DEBUG_LEVEL == 2 if (this->_Getcont() != _Right._Getcont()) { // report error _DEBUG_ERROR("map/set iterators incompatible"); _SCL_SECURE_INVALID_ARGUMENT; } #elif _ITERATOR_DEBUG_LEVEL == 1 _SCL_SECURE_VALIDATE(this->_Getcont() == _Right._Getcont()); #endif /* _ITERATOR_DEBUG_LEVEL */ return (this->_Ptr == _Right._Ptr); } bool operator!=(const _Myiter& _Right) const { // test for iterator inequality return (!(*this == _Right)); } }; template inline typename _Tree_const_iterator<_Mytree>::_Unchecked_type _Unchecked(_Tree_const_iterator<_Mytree> _Iter) { // convert to unchecked return (_Iter._Unchecked()); } template inline _Tree_const_iterator<_Mytree>& _Rechecked(_Tree_const_iterator<_Mytree>& _Iter, typename _Tree_const_iterator<_Mytree> ::_Unchecked_type _Right) { // convert to checked return (_Iter._Rechecked(_Right)); } // TEMPLATE CLASS _Tree_iterator template class _Tree_iterator : public _Tree_const_iterator<_Mytree> { // iterator for mutable tree public: typedef _Tree_iterator<_Mytree> _Myiter; typedef _Tree_const_iterator<_Mytree> _Mybase; typedef bidirectional_iterator_tag iterator_category; typedef typename _Mytree::_Nodeptr _Nodeptr; typedef typename _Mytree::value_type value_type; typedef typename _Mytree::difference_type difference_type; typedef typename _Mytree::pointer pointer; typedef typename _Mytree::reference reference; _Tree_iterator() { // construct with null node } _Tree_iterator(_Nodeptr _Pnode, const _Mytree *_Plist) : _Mybase(_Pnode, _Plist) { // construct with node pointer _Pnode } #if defined(__ghs) // PJP-B06 #if _HAS_CPP17 && !defined(__IMPLICIT_ONE_ARG_CONSTRUCTOR_FOR_TREE_ITERATOR) explicit #endif _Tree_iterator(_Nodeptr _Pnode) : _Mybase(_Pnode) { // construct with node pointer _Pnode } #endif /* __ghs */ typedef _Tree_unchecked_iterator<_Mytree> _Unchecked_type; _Myiter& _Rechecked(_Unchecked_type _Right) { // reset from unchecked iterator this->_Ptr = _Right._Ptr; return (*this); } _Unchecked_type _Unchecked() const { // make an unchecked iterator return (_Unchecked_type(this->_Ptr, (_Mytree *)this->_Getcont())); } reference operator*() const { // return designated value return ((reference)**(_Mybase *)this); } pointer operator->() const { // return pointer to class object return (_POINTER_TO(**this)); } _Myiter& operator++() { // preincrement ++(*(_Mybase *)this); return (*this); } _Myiter operator++(int) { // postincrement _Myiter _Tmp = *this; ++*this; return (_Tmp); } _Myiter& operator--() { // predecrement --(*(_Mybase *)this); return (*this); } _Myiter operator--(int) { // postdecrement _Myiter _Tmp = *this; --*this; return (_Tmp); } }; template inline typename _Tree_iterator<_Mytree>::_Unchecked_type _Unchecked(_Tree_iterator<_Mytree> _Iter) { // convert to unchecked return (_Iter._Unchecked()); } template inline _Tree_iterator<_Mytree>& _Rechecked(_Tree_iterator<_Mytree>& _Iter, typename _Tree_iterator<_Mytree> ::_Unchecked_type _Right) { // convert to checked return (_Iter._Rechecked(_Right)); } // tree TYPE WRAPPERS template struct _Tree_iter_types { // wraps types needed by iterators typedef _Value_type value_type; typedef _Size_type size_type; typedef _Difference_type difference_type; typedef _Pointer pointer; typedef _Const_pointer const_pointer; typedef _Reference reference; typedef _Const_reference const_reference; typedef _Nodeptr_type _Nodeptr; }; template struct _Tree_node { // tree node _Voidptr _Left; // left subtree, or smallest element if head _Voidptr _Parent; // parent, or root of tree if head _Voidptr _Right; // right subtree, or largest element if head char _Color; // _Red or _Black, _Black if head char _Isnil; // true only if head (also nil) node _Value_type _Myval; // the stored value, unused if head private: _Tree_node& operator=(const _Tree_node&); }; template struct _Tree_node<_Value_type, void *> { // tree node typedef _Tree_node<_Value_type, void *> *_Nodeptr; _Nodeptr _Left; // left subtree, or smallest element if head _Nodeptr _Parent; // parent, or root of tree if head _Nodeptr _Right; // right subtree, or largest element if head char _Color; // _Red or _Black, _Black if head char _Isnil; // true only if head (also nil) node _Value_type _Myval; // the stored value, unused if head private: _Tree_node& operator=(const _Tree_node&); }; template struct _Tree_simple_types : public _Simple_types<_Ty> { // wraps types needed by iterators typedef _Tree_node<_Ty, void *> _Node; typedef _Node *_Nodeptr; }; template struct _Tree_base_types { // types needed for a container base #if _HAS_CPP17 typedef typename conditional::value || is_same<_Alloc0, void *>::value || is_same<_Alloc0, pmr::memory_resource *>::value, pmr::polymorphic_allocator, _Alloc0>::type _Alloc; #else /* _HAS_CPP17 */ typedef _Alloc0 _Alloc; #endif /* _HAS_CPP17 */ typedef _Tree_base_types<_Ty, _Alloc0> _Myt; typedef _Wrap_alloc<_Alloc> _Alty0; typedef typename _Alty0::template rebind<_Ty>::other _Alty; typedef typename _Get_voidptr<_Alty, typename _Alty::pointer>::type _Voidptr; typedef _Tree_node _Node; typedef typename _Alty::template rebind<_Node>::other _Alnod_type; typedef typename _Alnod_type::pointer _Nodeptr; typedef _Nodeptr& _Nodepref; typedef typename _If<_Is_simple_alloc<_Alty>::value, _Tree_simple_types, _Tree_iter_types >::type _Val_types; }; // TEMPLATE CLASS _Tree_val template class _Tree_val : public _Container_base { // base class for tree to hold data public: typedef _Tree_val<_Val_types> _Myt; typedef typename _Val_types::_Nodeptr _Nodeptr; typedef _Nodeptr& _Nodepref; typedef typename _Val_types::value_type value_type; typedef typename _Val_types::size_type size_type; typedef typename _Val_types::difference_type difference_type; typedef typename _Val_types::pointer pointer; typedef typename _Val_types::const_pointer const_pointer; typedef typename _Val_types::reference reference; typedef typename _Val_types::const_reference const_reference; typedef _Tree_const_iterator<_Myt> const_iterator; typedef _Tree_iterator<_Myt> iterator; _Tree_val() { // initialize data this->_Myhead = 0; this->_Mysize = 0; } enum _Redbl { // colors for link to parent _Red, _Black}; static char& _Color(_Nodeptr _Pnode) { // return reference to color in node return ((char&)_Pnode->_Color); } static char& _Isnil(_Nodeptr _Pnode) { // return reference to nil flag in node return ((char&)_Pnode->_Isnil); } static _Nodepref _Left(_Nodeptr _Pnode) { // return reference to left pointer in node return ((_Nodepref)_Pnode->_Left); } static _Nodepref _Parent(_Nodeptr _Pnode) { // return reference to parent pointer in node return ((_Nodepref)_Pnode->_Parent); } static _Nodepref _Right(_Nodeptr _Pnode) { // return reference to right pointer in node return ((_Nodepref)_Pnode->_Right); } static reference _Myval(_Nodeptr _Pnode) { // return reference to value in node return ((reference)_Pnode->_Myval); } #if defined(__ghs) __noinline #endif /* __ghs */ static _Nodeptr _Max(_Nodeptr _Pnode) { // return rightmost node in subtree at _Pnode while (!_Isnil(_Right(_Pnode))) _Pnode = _Right(_Pnode); return (_Pnode); } #if defined(__ghs) __noinline #endif /* __ghs */ static _Nodeptr _Min(_Nodeptr _Pnode) { // return leftmost node in subtree at _Pnode while (!_Isnil(_Left(_Pnode))) _Pnode = _Left(_Pnode); return (_Pnode); } _Nodeptr _Myhead; // pointer to head node size_type _Mysize; // number of elements }; // TEMPLATE CLASS _Tree_comp_alloc template class _Tree_comp_alloc { // base class for tree to hold ordering predicate, allocator public: typedef _Tree_comp_alloc<_Traits> _Myt; typedef typename _Traits::allocator_type allocator_type; typedef typename _Traits::key_compare key_compare; typedef _Tree_base_types _Alloc_types; typedef typename _Alloc_types::_Alloc _Alloc0; typedef typename _Alloc_types::_Alnod_type _Alty; typedef typename _Alloc_types::_Node _Node; typedef typename _Alloc_types::_Nodeptr _Nodeptr; typedef typename _Alloc_types::_Val_types _Val_types; typedef _Nodeptr& _Nodepref; typedef typename _Val_types::value_type value_type; typedef typename _Val_types::size_type size_type; typedef typename _Val_types::difference_type difference_type; typedef typename _Val_types::pointer pointer; typedef typename _Val_types::const_pointer const_pointer; typedef typename _Val_types::reference reference; typedef typename _Val_types::const_reference const_reference; typedef _Tree_const_iterator<_Tree_val<_Val_types> > const_iterator; typedef _Tree_iterator<_Tree_val<_Val_types> > iterator; enum _Redbl { // colors for link to parent _Red, _Black #if defined(__ghs) , _Redbl_dummy = _DUMMY_ENUM_MAX #endif /* __ghs */ }; static char& _Color(_Nodeptr _Pnode) { // return reference to color in node return (_Tree_val<_Val_types>::_Color(_Pnode)); } static char& _Isnil(_Nodeptr _Pnode) { // return reference to nil flag in node return (_Tree_val<_Val_types>::_Isnil(_Pnode)); } static _Nodepref _Left(_Nodeptr _Pnode) { // return reference to left pointer in node return (_Tree_val<_Val_types>::_Left(_Pnode)); } static _Nodepref _Parent(_Nodeptr _Pnode) { // return reference to parent pointer in node return (_Tree_val<_Val_types>::_Parent(_Pnode)); } static _Nodepref _Right(_Nodeptr _Pnode) { // return reference to right pointer in node return (_Tree_val<_Val_types>::_Right(_Pnode)); } static reference _Myval(_Nodeptr _Pnode) { // return reference to value in node return (_Tree_val<_Val_types>::_Myval(_Pnode)); } static _Nodeptr _Max(_Nodeptr _Pnode) { // return rightmost node in subtree at _Pnode return (_Tree_val<_Val_types>::_Max(_Pnode)); } static _Nodeptr _Min(_Nodeptr _Pnode) { // return leftmost node in subtree at _Pnode return (_Tree_val<_Val_types>::_Min(_Pnode)); } _Tree_comp_alloc(const key_compare& _Parg, const allocator_type& _Al) : _Mypair(_One_then_variadic_args_t(), _Parg, _One_then_variadic_args_t(), _Al) { // construct from comparator, allocator _Construct(); } #if !defined(__ghs) || _HAS_CPP11 _Tree_comp_alloc(const key_compare& _Parg, allocator_type&& _Al) : _Mypair(_One_then_variadic_args_t(), _Parg, _One_then_variadic_args_t(), _STD move(_Al)) { // construct from comparator, allocator _Construct(); } #endif /* !defined(__ghs) || _HAS_CPP11 */ #if _ITERATOR_DEBUG_LEVEL == 0 void _Construct() { // construct head node _Myhead() = _Buyheadnode(); } ~_Tree_comp_alloc() _NOEXCEPT { // destroy head node _Freeheadnode(_Myhead()); } void _Copy_alloc(const _Alty& _Al) { // replace old allocator _Pocca(_Getal(), _Al); } void _Move_alloc(_Alty& _Al) { // replace old allocator _Pocma(_Getal(), _Al); } void _Swap_alloc(_Myt& _Right) { // swap allocators _Pocs(_Getal(), _Right._Getal()); } #else /* _ITERATOR_DEBUG_LEVEL == 0 */ void _Construct() { // construct head node, proxy _Myhead() = _Buyheadnode(); _TRY_BEGIN _Alloc_proxy(); _CATCH_ALL _Freeheadnode(_Myhead()); _RERAISE; _CATCH_END } ~_Tree_comp_alloc() _NOEXCEPT { // destroy head node, proxy _Freeheadnode(_Myhead()); _Free_proxy(); } void _Copy_alloc(const _Alty& _Al) { // replace old allocator _Free_proxy(); _Pocca(_Getal(), _Al); _Alloc_proxy(); } void _Move_alloc(_Alty& _Al) { // replace old allocator _Free_proxy(); _Pocma(_Getal(), _Al); _Alloc_proxy(); } void _Swap_alloc(_Myt& _Right) { // swap allocators _Pocs(_Getal(), _Right._Getal()); _Swap_adl(_Myproxy(), _Right._Myproxy()); } void _Alloc_proxy() { // construct proxy typename _Alty::template rebind<_Container_proxy>::other _Alproxy(_Getal()); _Myproxy() = _Alproxy.allocate(1); _Alproxy.construct(_Myproxy(), _Container_proxy()); _Myproxy()->_Mycont = &_Get_data(); } void _Free_proxy() { // destroy proxy typename _Alty::template rebind<_Container_proxy>::other _Alproxy(_Getal()); _Orphan_all(); _Alproxy.destroy(_Myproxy()); _Alproxy.deallocate(_Myproxy(), 1); _Myproxy() = 0; } _Iterator_base12 **_Getpfirst() const { // get address of iterator chain return (_Get_data()._Getpfirst()); } _Container_proxy * & _Myproxy() _NOEXCEPT { // return reference to _Myproxy return (_Get_data()._Myproxy); } _Container_proxy * const & _Myproxy() const _NOEXCEPT { // return const reference to _Myproxy return (_Get_data()._Myproxy); } #endif /* _ITERATOR_DEBUG_LEVEL == 0 */ void _Orphan_all() { // orphan all iterators _Get_data()._Orphan_all(); } void _Swap_all(_Myt& _Right) { // swap all iterators _Get_data()._Swap_all(_Right._Get_data()); } _Nodeptr _Buyheadnode() { // get head node using current allocator _Nodeptr _Pnode = _Getal().allocate(1); _TRY_BEGIN #if defined(__ghs) ::new (_STD addressof(_Left(_Pnode))) _Nodeptr(_Pnode); ::new (_STD addressof(_Parent(_Pnode))) _Nodeptr(_Pnode); ::new (_STD addressof(_Right(_Pnode))) _Nodeptr(_Pnode); #else _Getal().construct( _STD addressof(_Left(_Pnode)), _Pnode); _Getal().construct( _STD addressof(_Parent(_Pnode)), _Pnode); _Getal().construct( _STD addressof(_Right(_Pnode)), _Pnode); #endif /* defined(__ghs) */ _CATCH_ALL _Getal().deallocate(_Pnode, 1); _RERAISE; _CATCH_END _Color(_Pnode) = _Black; _Isnil(_Pnode) = true; return (_Pnode); } void _Freeheadnode(_Nodeptr _Pnode) { // free head node using current allocator #if defined(__ghs) _Left(_Pnode).~_Nodeptr(); _Parent(_Pnode).~_Nodeptr(); _Right(_Pnode).~_Nodeptr(); #else _Getal().destroy( _STD addressof(_Left(_Pnode))); _Getal().destroy( _STD addressof(_Parent(_Pnode))); _Getal().destroy( _STD addressof(_Right(_Pnode))); #endif /* defined(__ghs) */ _Getal().deallocate(_Pnode, 1); } #if defined(__ghs) && !_HAS_CPP11 _Nodeptr _Buynode0(_Nodeptr _Pnode = 0) #else _Nodeptr _Buynode0(_Nodeptr _Pnode = nullptr) #endif /* defined(__ghs) && !_HAS_CPP11 */ { // allocate a non-value node if (_Pnode == #if defined(__ghs) && !_HAS_CPP11 0) #else nullptr) #endif /* defined(__ghs) && !_HAS_CPP11 */ _Pnode = this->_Getal().allocate(1); _TRY_BEGIN #if defined(__ghs) ::new (_STD addressof(_Left(_Pnode))) _Nodeptr(_Myhead()); ::new (_STD addressof(_Parent(_Pnode))) _Nodeptr(_Myhead()); ::new (_STD addressof(_Right(_Pnode))) _Nodeptr(_Myhead()); #else _Getal().construct( _STD addressof(_Left(_Pnode)), _Myhead()); _Getal().construct( _STD addressof(_Parent(_Pnode)), _Myhead()); _Getal().construct( _STD addressof(_Right(_Pnode)), _Myhead()); #endif /* defined(__ghs) */ _CATCH_ALL _Getal().deallocate(_Pnode, 1); _RERAISE; _CATCH_END this->_Color(_Pnode) = _Red; this->_Isnil(_Pnode) = false; return (_Pnode); } void _Freenode0(_Nodeptr _Pnode) { // free non-value node using current allocator #if defined(__ghs) _Left(_Pnode).~_Nodeptr(); _Parent(_Pnode).~_Nodeptr(); _Right(_Pnode).~_Nodeptr(); #else _Getal().destroy( _STD addressof(_Left(_Pnode))); _Getal().destroy( _STD addressof(_Parent(_Pnode))); _Getal().destroy( _STD addressof(_Right(_Pnode))); #endif /* defined(__ghs) */ _Getal().deallocate(_Pnode, 1); } #if _HAS_VARIADIC_TEMPLATES template #if defined(__ghs) __noinline #endif /* __ghs */ _Nodeptr _Buynode(_Valty&&... _Val) { // allocate a node with defaults and set links and value _Nodeptr _Pnode = _Buynode0(); _TRY_BEGIN this->_Getal().construct( _STD addressof(_Myval(_Pnode)), _STD forward<_Valty>(_Val)...); _CATCH_ALL _Freenode0(_Pnode); _RERAISE; _CATCH_END return (_Pnode); } #else /* _HAS_VARIADIC_TEMPLATES */ #if defined(__ghs) // use __noinline #define _TREE_BUYNODE( \ TEMPLATE_LIST, PADDING_LIST, LIST, C, X1, X2, X3, X4) \ TEMPLATE_LIST(_CLASS_TYPE) \ __noinline \ _Nodeptr _Buynode(LIST(_TYPE_REFREF_ARG)) \ { /* allocate a node with defaults and set links and value */ \ _Nodeptr _Pnode = _Buynode0(); \ _TRY_BEGIN \ this->_Getal().construct( \ _STD addressof(_Myval(_Pnode)) \ _EX(C) LIST(_FORWARD_ARG)); \ _CATCH_ALL \ _Freenode0(_Pnode); \ _RERAISE; \ _CATCH_END \ return (_Pnode); \ } #else #define _TREE_BUYNODE( \ TEMPLATE_LIST, PADDING_LIST, LIST, C, X1, X2, X3, X4) \ TEMPLATE_LIST(_CLASS_TYPE) \ _Nodeptr _Buynode(LIST(_TYPE_REFREF_ARG)) \ { /* allocate a node with defaults and set links and value */ \ _Nodeptr _Pnode = _Buynode0(); \ _TRY_BEGIN \ this->_Getal().construct( \ _STD addressof(_Myval(_Pnode)) \ _EX(C) LIST(_FORWARD_ARG)); \ _CATCH_ALL \ _Freenode0(_Pnode); \ _RERAISE; \ _CATCH_END \ return (_Pnode); \ } #endif /* __ghs */ #if defined(__ghs) # pragma ghs nowarning 76 #endif /* defined(__ghs) */ _VARIADIC_EXPAND_0X(_TREE_BUYNODE, , , , ) #if defined(__ghs) # pragma ghs endnowarning 76 #endif /* defined(__ghs) */ #undef _TREE_BUYNODE #endif /* _HAS_VARIADIC_TEMPLATES */ key_compare& _Getcomp() _NOEXCEPT { // return reference to ordering predicate return (_Mypair._Get_first()); } const key_compare& _Getcomp() const _NOEXCEPT { // return const reference to ordering predicate return (_Mypair._Get_first()); } _Alty& _Getal() _NOEXCEPT { // return reference to allocator return (_Mypair._Get_second()._Get_first()); } const _Alty& _Getal() const _NOEXCEPT { // return const reference to allocator return (_Mypair._Get_second()._Get_first()); } _Tree_val<_Val_types>& _Get_data() _NOEXCEPT { // return reference to _Tree_val return (_Mypair._Get_second()._Get_second()); } const _Tree_val<_Val_types>& _Get_data() const _NOEXCEPT { // return const reference to _Tree_val return (_Mypair._Get_second()._Get_second()); } _Nodeptr& _Myhead() _NOEXCEPT { // return reference to _Myhead return (_Get_data()._Myhead); } const _Nodeptr& _Myhead() const _NOEXCEPT { // return const reference to _Myhead return (_Get_data()._Myhead); } size_type& _Mysize() _NOEXCEPT { // return reference to _Mysize return (_Get_data()._Mysize); } const size_type& _Mysize() const _NOEXCEPT { // return const reference to _Mysize return (_Get_data()._Mysize); } private: _Compressed_pair > > _Mypair; }; //The following node_handle definition is moved from within the _Tree class where it was previously defined. #if defined(__ghs) && _HAS_CPP17 // INSERT/EXTRACT NODE FOR MAPS template class _Node_handle_for_maps { // stores element extracted from an associative container typedef allocator_traits<_Alloc> _Alloc_traits; #if defined(__ghs) typedef typename _Alloc_traits::template rebind_traits<_Node_type> _Al_nod; typedef typename _Al_nod::pointer _Nodeptr; #else typedef _Node_type *_Nodeptr; #endif /* defined(__ghs) */ public: typedef _Alloc allocator_type; typedef _Node_type container_node_type; typedef _Key key_type; typedef typename _Value::second_type mapped_type; #if defined(__ghs) _Node_handle_for_maps() : _Myptr(nullptr), _Myalloc() { } #else _Node_handle_for_maps() = default; #endif _Node_handle_for_maps(_Node_handle_for_maps&& _Right) : _Myptr(_Right._Myptr), _Myalloc(_Right._Myalloc) { // transfer ownership of the node pointer _Right._Myptr = nullptr; } _Node_handle_for_maps(_Nodeptr _Nodep_arg, allocator_type _Alloc_arg) : _Myptr(_Nodep_arg), _Myalloc(_Alloc_arg) { // construct from node pointer and allocator } ~_Node_handle_for_maps() _NOEXCEPT { // destroy the object _Destroy_node(); } _Node_handle_for_maps& operator=(_Node_handle_for_maps&& _Right) { // move assign _Destroy_node(); // destroy current value _Myptr = _Right._Myptr; if (_Myalloc == allocator_type() #if defined(__ghs) || _Alloc_traits::propagate_on_container_move_assignment::value) #else || _Alloc::propagate_on_container_move_assignment()) #endif /* defined(__ghs) */ _Myalloc = _STD move(_Right._Myalloc); _Right._Myptr = nullptr; _Right._Myalloc = nullopt; return (*this); } void _Destroy_node() { // destroy the object if (_Myptr != nullptr) { // destroy current value _Alloc_traits::destroy((_Alloc&)_Myalloc, &_Myptr->_Myval); #if defined(__ghs) typename _Alloc_traits::template rebind_alloc<_Node_type> _Alnod; // allocator object for nodes #else typename _Alloc::template rebind<_Node_type>::other _Alnod; // allocator object for nodes #endif /* defined(__ghs) */ _Alnod.deallocate(_Myptr, 1); } } void _Release_node() { // destroy the object _Myptr = nullptr; } _Nodeptr _Get_node() const { // return node pointer return (_Myptr); } #if defined(__ghs) key_type& key() const { if (empty()) _THROW_N(_Bad_tree_node_access, "map/set" "node_type::key(): access to empty object"); return *_STD __ghs_const_launder(_STD addressof( _Myptr->_Myval.first)); } mapped_type& mapped() const { if (empty()) _THROW_N(_Bad_tree_node_access, "map/set" "node_type::mapped(): access to empty object"); return (_Myptr->_Myval.second); } #else const key_type& key() const { if (empty()) _THROW_N(_Bad_tree_node_access, "map/set" "node_type::key(): access to empty object"); return (_Myptr->_Myval.first); } const mapped_type& mapped() const { if (empty()) _THROW_N(_Bad_tree_node_access, "map/set" "node_type::mapped(): access to empty object"); return (_Myptr->_Myval.second); } #endif /* defined(__ghs) */ allocator_type get_allocator() const { // get stored allocator if (empty()) _THROW_N(_Bad_tree_node_access, "map/set::" "node_type::get_allocator(): access to empty object"); return ((_Alloc&)_Myalloc); } explicit operator bool() const _NOEXCEPT { // test for not empty return (!empty()); } bool empty() const _NOEXCEPT { // test for empty return (_Myptr == nullptr); } void swap(_Node_handle_for_maps& _Right) _NOEXCEPT_OP(_NOEXCEPT_OP( _Alloc_traits::propagate_on_container_swap::value || _Alloc_traits::is_always_equal::value)) { // swap stored values _STD swap(_Myptr, _Right._Myptr); _STD swap(_Myalloc, _Right._Myalloc); } template friend void swap(_Node_handle_for_maps<_Key2, _Value2, _Alloc2, _Node_type2>& _Left, _Node_handle_for_maps<_Key2, _Value2, _Alloc2, _Node_type2>& _Right) _NOEXCEPT_OP(_NOEXCEPT_OP(_Left.swap(_Right))); private: _Nodeptr _Myptr; optional<_Alloc> _Myalloc; }; template void swap(_Node_handle_for_maps<_Key2, _Value2, _Alloc2, _Node_type2>& _Left, _Node_handle_for_maps<_Key2, _Value2, _Alloc2, _Node_type2>& _Right) _NOEXCEPT_OP(_NOEXCEPT_OP(_Left.swap(_Right))) { // swap nodes _Left.swap(_Right); } // INSERT/EXTRACT NODE FOR SETS template class _Node_handle_for_sets { // stores element extracted from an associative container typedef allocator_traits<_Alloc> _Alloc_traits; #if defined(__ghs) typedef typename _Alloc_traits::template rebind_traits<_Node_type> _Al_nod; typedef typename _Al_nod::pointer _Nodeptr; #else typedef _Node_type *_Nodeptr; #endif /* defined(__ghs) */ public: typedef _Alloc allocator_type; typedef _Node_type container_node_type; typedef _Value value_type; #if defined(__ghs) _Node_handle_for_sets() : _Myptr(nullptr), _Myalloc() { } #else _Node_handle_for_sets() = default; #endif _Node_handle_for_sets(_Node_handle_for_sets&& _Right) : _Myptr(_Right._Myptr), _Myalloc(_Right._Myalloc) { // transfer ownership of the node pointer _Right._Myptr = nullptr; } _Node_handle_for_sets(_Nodeptr _Nodep_arg, allocator_type _Alloc_arg) : _Myptr(_Nodep_arg), _Myalloc(_Alloc_arg) { // construct from node pointer and allocator } ~_Node_handle_for_sets() _NOEXCEPT { // destroy the object _Destroy_node(); } _Node_handle_for_sets& operator=(_Node_handle_for_sets&& _Right) { // move assign _Destroy_node(); // destroy current value _Myptr = _Right._Myptr; if (_Myalloc == allocator_type() || #if defined(__ghs) _Alloc_traits::propagate_on_container_move_assignment::value) #else _Alloc::propagate_on_container_move_assignment()) #endif /* defined(__ghs) */ _Myalloc = _STD move(_Right._Myalloc); _Right._Myptr = nullptr; _Right._Myalloc = nullopt; return (*this); } void _Destroy_node() { // destroy the object if (_Myptr != nullptr) { // destroy current value _Alloc_traits::destroy((_Alloc&)_Myalloc, &_Myptr->_Myval); #if defined(__ghs) typename _Alloc_traits::template rebind_alloc<_Node_type> _Alnod; // allocator object for nodes #else typename _Alloc::template rebind<_Node_type>::other _Alnod; // allocator object for nodes #endif /* defined(__ghs) */ _Alnod.deallocate(_Myptr, 1); } } void _Release_node() { // destroy the object _Myptr = nullptr; } _Nodeptr _Get_node() const { // return node pointer return (_Myptr); } value_type& value() const { // get stored value if (empty()) _THROW_N(_Bad_tree_node_access, "map/set" "node_type::value(): access to empty object"); return (_Myptr->_Myval); } allocator_type get_allocator() const { // get stored allocator if (empty()) _THROW_N(_Bad_tree_node_access, "map/set::" "node_type::get_allocator(): access to empty object"); return ((_Alloc&)_Myalloc); } explicit operator bool() const _NOEXCEPT { // test for not empty return (!empty()); } bool empty() const _NOEXCEPT { // test for empty return (_Myptr == nullptr); } void swap(_Node_handle_for_sets& _Right) _NOEXCEPT_OP(_NOEXCEPT_OP( _Alloc_traits::propagate_on_container_swap::value || _Alloc_traits::is_always_equal::value)) { // swap stored values _STD swap(_Myptr, _Right._Myptr); _STD swap(_Myalloc, _Right._Myalloc); } template friend void swap(_Node_handle_for_sets<_Key2, _Value2, _Alloc2, _Node_type2>& _Left, _Node_handle_for_sets<_Key2, _Value2, _Alloc2, _Node_type2>& _Right) _NOEXCEPT_OP(_NOEXCEPT_OP(_Left.swap(_Right))); private: _Nodeptr _Myptr; optional<_Alloc> _Myalloc; }; template void swap(_Node_handle_for_sets<_Key2, _Value2, _Alloc2, _Node_type2>& _Left, _Node_handle_for_sets<_Key2, _Value2, _Alloc2, _Node_type2>& _Right) _NOEXCEPT_OP(_NOEXCEPT_OP(_Left.swap(_Right))) { // swap nodes _Left.swap(_Right); } #endif /* defined(__ghs) && _HAS_CPP17 */ // TEMPLATE CLASS _Tree template class _Tree : public _Tree_comp_alloc<_Traits> { // ordered red-black tree for map/multimap/set/multiset public: typedef _Tree<_Traits> _Myt; typedef _Tree_comp_alloc<_Traits> _Mybase; typedef typename _Traits::key_type key_type; typedef typename _Traits::value_compare value_compare; enum { // get multi parameter _Multi = _Traits::_Multi}; typedef typename _Mybase::_Node _Node; typedef typename _Mybase::_Nodeptr _Nodeptr; typedef typename _Mybase::_Alty _Alty; typedef typename _Mybase::key_compare key_compare; typedef typename _Mybase::allocator_type allocator_type; typedef typename _Mybase::value_type value_type; typedef typename _Mybase::size_type size_type; typedef typename _Mybase::difference_type difference_type; typedef typename _Mybase::pointer pointer; typedef typename _Mybase::const_pointer const_pointer; typedef typename _Mybase::reference reference; typedef typename _Mybase::const_reference const_reference; typedef typename _Mybase::const_iterator const_iterator; #if defined(__ghs) && !_HAS_CPP11 // PJP-B07 typedef typename _Mybase::iterator iterator; #else typedef typename _If::value, typename _Mybase::const_iterator, typename _Mybase::iterator>::type iterator; #endif /* __ghs */ typedef _STD reverse_iterator reverse_iterator; typedef _STD reverse_iterator const_reverse_iterator; typedef pair _Pairib; typedef pair _Pairii; typedef pair _Paircc; struct _Copy_tag { // signals copying }; struct _Move_tag { // signals moving }; _Tree(const key_compare& _Parg, const allocator_type& _Al) : _Mybase(_Parg, _Al) { // construct empty tree } _Tree(const _Myt& _Right, const allocator_type& _Al) : _Mybase(_Right.key_comp(), _Al) { // construct tree by copying _Right, allocator _TRY_BEGIN _Copy(_Right, _Copy_tag()); _CATCH_ALL _Tidy(); _RERAISE; _CATCH_END } #if _HAS_RVALUE_REFERENCES #if _HAS_CPP11 _Tree(_Myt&& _Right) : _Mybase(_Right.key_comp(), _STD move(_Right._Getal())) { // construct tree by moving _Right _Assign_rv(_STD forward<_Myt>(_Right), true_type()); } _Tree(_Myt&& _Right, const allocator_type& _Al) : _Mybase(_Right.key_comp(), _Al) { // construct tree by moving _Right, allocator _Assign_rv(_STD forward<_Myt>(_Right)); } _Myt& operator=(_Myt&& _Right) { // assign by moving _Right if (this != &_Right) { // different, move it clear(); if (_Alty::propagate_on_container_move_assignment::value && this->_Getal() != _Right._Getal()) this->_Move_alloc(_Right._Getal()); _Assign_rv(_STD forward<_Myt>(_Right)); } return (*this); } void _Assign_rv(_Myt&& _Right, true_type) { // move from _Right, stealing its contents this->_Swap_all(_Right); _Swap_adl(this->_Getcomp(), _Right._Getcomp()); _Swap_adl(this->_Myhead(), _Right._Myhead()); _STD swap(this->_Mysize(), _Right._Mysize()); } void _Assign_rv(_Myt&& _Right, false_type) { // move from _Right, possibly moving its contents if (get_allocator() == _Right.get_allocator()) _Assign_rv(_STD forward<_Myt>(_Right), true_type()); else _Copy(_Right, _Move_tag()); } void _Assign_rv(_Myt&& _Right) { // assign by moving _Right _Assign_rv(_STD forward<_Myt>(_Right), typename _Alty::propagate_on_container_move_assignment()); } #else /* _HAS_CPP11 */ _Tree(_Myt&& _Right) : _Mybase(_Right.key_comp(), _Right._Getal()) { // construct tree by moving _Right _Assign_rv(_STD forward<_Myt>(_Right)); } _Tree(_Myt&& _Right, const allocator_type& _Al) : _Mybase(_Right.key_comp(), _Al) { // construct tree by moving _Right, allocator if (this->_Getal() != _Right._Getal()) _Copy(_Right, true_type()); else _Assign_rv(_STD forward<_Myt>(_Right)); } _Myt& operator=(_Myt&& _Right) { // assign by moving _Right if (this != &_Right) { // different, move it clear(); if (this->_Getal() != _Right._Getal()) _Copy(_Right, true_type()); else _Assign_rv(_STD forward<_Myt>(_Right)); } return (*this); } void _Assign_rv(_Myt&& _Right) { // assign by moving _Right this->_Swap_all(_Right); _Swap_adl(this->_Getcomp(), _Right._Getcomp()); _Swap_adl(this->_Myhead(), _Right._Myhead()); _STD swap(this->_Mysize(), _Right._Mysize()); } #endif /* _HAS_CPP11 */ _Pairib insert(value_type&& _Val) { // try to insert node with value _Val, favoring right side return (_Insert_nohint(false, _STD forward(_Val), _Nil())); } iterator insert(const_iterator _Where, value_type&& _Val) { // try to insert node with value _Val using _Where as a hint return (_Insert_hint(_Where, _STD forward(_Val), _Nil())); } template::value, #else class = enable_if_t::value, #endif /* defined(__ghs) */ void> > _Pairib insert(_Valty&& _Val) { // try to insert node with value _Val, favoring right side _Nodeptr _Newnode = this->_Buynode(_STD forward<_Valty>(_Val)); return (_Insert_nohint(false, this->_Myval(_Newnode), _Newnode)); } template::value, #else class = enable_if_t::value, #endif /* defined(__ghs) */ void> > iterator insert(const_iterator _Where, _Valty&& _Val) { // try to insert node with value _Val using _Where as a hint _Nodeptr _Newnode = this->_Buynode(_STD forward<_Valty>(_Val)); return (_Insert_hint(_Where, this->_Myval(_Newnode), _Newnode)); } #if _HAS_VARIADIC_TEMPLATES template _Pairib emplace(_Valty&&... _Val) { // try to insert value_type(_Val...), favoring right side _Nodeptr _Newnode = this->_Buynode(_STD forward<_Valty>(_Val)...); return (_Insert_nohint(false, this->_Myval(_Newnode), _Newnode)); } template iterator emplace_hint(const_iterator _Where, _Valty&&... _Val) { // insert value_type(_Val...) at _Where _Nodeptr _Newnode = this->_Buynode(_STD forward<_Valty>(_Val)...); return (_Insert_hint(_Where, this->_Myval(_Newnode), _Newnode)); } #else /* _HAS_VARIADIC_TEMPLATES */ #define _TREE_EMPLACE( \ TEMPLATE_LIST, PADDING_LIST, LIST, C, X1, X2, X3, X4) \ TEMPLATE_LIST(_CLASS_TYPE) \ _Pairib emplace(LIST(_TYPE_REFREF_ARG)) \ { /* try to insert value_type(_Val...), favoring right side */ \ _Nodeptr _Newnode = this->_Buynode(LIST(_FORWARD_ARG)); \ return (_Insert_nohint(false, \ this->_Myval(_Newnode), _Newnode)); \ } \ TEMPLATE_LIST(_CLASS_TYPE) \ iterator emplace_hint(const_iterator _Where \ _EX(C) LIST(_TYPE_REFREF_ARG)) \ { /* insert value_type(_Val...) at _Where */ \ _Nodeptr _Newnode = this->_Buynode(LIST(_FORWARD_ARG)); \ return (_Insert_hint(_Where, \ this->_Myval(_Newnode), _Newnode)); \ } _VARIADIC_EXPAND_0X(_TREE_EMPLACE, , , , ) #undef _TREE_EMPLACE #endif /* _HAS_VARIADIC_TEMPLATES */ #endif /* _HAS_RVALUE_REFERENCES */ ~_Tree() _NOEXCEPT { // destroy tree _Tidy(); } #if defined(__ghs) __noinline #endif /* __ghs */ _Myt& operator=(const _Myt& _Right) { // replace contents from _Right if (this != &_Right) { // different, assign it clear(); if (this->_Getal() != _Right._Getal() && _Alty::propagate_on_container_copy_assignment::value) this->_Copy_alloc(_Right._Getal()); this->_Getcomp() = _Right._Getcomp(); _Copy(_Right, _Copy_tag()); } return (*this); } iterator begin() _NOEXCEPT { // return iterator for beginning of mutable sequence return (iterator(_Lmost(), &this->_Get_data())); } const_iterator begin() const _NOEXCEPT { // return iterator for beginning of nonmutable sequence return (const_iterator(_Lmost(), &this->_Get_data())); } iterator end() _NOEXCEPT { // return iterator for end of mutable sequence return (iterator(this->_Myhead(), &this->_Get_data())); } const_iterator end() const _NOEXCEPT { // return iterator for end of nonmutable sequence return (const_iterator(this->_Myhead(), &this->_Get_data())); } reverse_iterator rbegin() _NOEXCEPT { // return iterator for beginning of reversed mutable sequence return (reverse_iterator(end())); } const_reverse_iterator rbegin() const _NOEXCEPT { // return iterator for beginning of reversed nonmutable sequence return (const_reverse_iterator(end())); } reverse_iterator rend() _NOEXCEPT { // return iterator for end of reversed mutable sequence return (reverse_iterator(begin())); } const_reverse_iterator rend() const _NOEXCEPT { // return iterator for end of reversed nonmutable sequence return (const_reverse_iterator(begin())); } #if _HAS_CPP11 const_iterator cbegin() const _NOEXCEPT { // return iterator for beginning of nonmutable sequence return (begin()); } const_iterator cend() const _NOEXCEPT { // return iterator for end of nonmutable sequence return (end()); } const_reverse_iterator crbegin() const _NOEXCEPT { // return iterator for beginning of reversed nonmutable sequence return (rbegin()); } const_reverse_iterator crend() const _NOEXCEPT { // return iterator for end of reversed nonmutable sequence return (rend()); } #endif /* _HAS_CPP11 */ size_type size() const _NOEXCEPT { // return length of sequence return (this->_Mysize()); } size_type max_size() const _NOEXCEPT { // return maximum possible length of sequence return (this->_Getal().max_size()); } bool empty() const _NOEXCEPT { // return true only if sequence is empty return (size() == 0); } allocator_type get_allocator() const _NOEXCEPT { // return allocator object for values return (this->_Getal()); } key_compare key_comp() const { // return object for comparing keys return (this->_Getcomp()); } value_compare value_comp() const { // return object for comparing values return (value_compare(key_comp())); } #if _HAS_CPP17 #if !defined(__ghs) // INSERT/EXTRACT NODE template class _Node_handle { // stores element extracted from an associative container typedef allocator_traits<_Alloc> _Alloc_traits; typedef _Node_type *_Nodeptr; public: typedef _Alloc allocator_type; typedef _Node_type container_node_type; typedef _Value value_type; #if defined(__ghs) _Node_handle() : _Myptr(nullptr), _Myalloc() { } #else _Node_handle() = default; #endif _Node_handle(_Node_handle&& _Right) : _Myptr(_Right._Myptr), _Myalloc(_Right._Myalloc) { // transfer ownership of the node pointer _Right._Myptr = nullptr; } _Node_handle(_Nodeptr _Nodep_arg, allocator_type _Alloc_arg) : _Myptr(_Nodep_arg), _Myalloc(_Alloc_arg) { // construct from node pointer and allocator } ~_Node_handle() _NOEXCEPT { // destroy the object _Destroy_node(); } _Node_handle& operator=(_Node_handle&& _Right) { // move assign _Destroy_node(); // destroy current value _Myptr = _Right._Myptr; if (_Myalloc == allocator_type() || _Alloc::propagate_on_container_move_assignment) _Myalloc = _STD move(_Right._Myalloc); _Right._Myptr = nullptr; _Right._Myalloc = nullopt; return (*this); } void _Destroy_node() { // destroy the object if (_Myptr != nullptr) { // destroy current value _Alloc_traits::destroy((_Alloc&)_Myalloc, &_Myptr->_Myval); typename _Alloc::template rebind<_Node_type>::other _Alnod; // allocator object for nodes _Alnod.deallocate(_Myptr, 1); } } void _Release_node() { // destroy the object _Myptr = nullptr; } _Nodeptr _Get_node() const { // return node pointer return (_Myptr); } value_type& value() const { // get stored value if (empty()) _THROW_N(_Bad_tree_node_access, "map/set" "node_type::value(): access to empty object"); return (_Myptr->_Myval); } allocator_type get_allocator() const { // get stored allocator if (empty()) _THROW_N(_Bad_tree_node_access, "map/set::" "node_type::get_allocator(): access to empty object"); return ((_Alloc&)_Myalloc); } explicit operator bool() const _NOEXCEPT { // test for not empty return (!empty()); } bool empty() const _NOEXCEPT { // test for empty return (_Myptr == nullptr); } void swap(_Node_handle& _Right) _NOEXCEPT_OP(_NOEXCEPT_OP( _Alloc_traits::propagate_on_container_swap::value || _Alloc_traits::is_always_equal::value)) { // swap stored values _STD swap(_Myptr, _Right._Myptr); _STD swap(_Myalloc, _Right._Myalloc); } private: _Nodeptr _Myptr; optional<_Alloc> _Myalloc; }; template void swap(_Node_handle<_Value, _Alloc, _Node_type>& _Left, _Node_handle<_Value, _Alloc, _Node_type>& _Right) _NOEXCEPT_OP(_NOEXCEPT_OP(_Left.swap(_Right))) { // swap nodes _Left.swap(_Right); } #endif /* !defined(__ghs) */ #if defined(__ghs) // Structure to hold enough information to know where to insert // something into a tree. Contains the relevant node and whether // the item should go as a left child or a right child for this // node. _Node == nullptr means no insertion. struct _Insert_locator { _Insert_locator(bool _Left, _Nodeptr _Node) : _Left(_Left), _Node(_Node) {} _Insert_locator() : _Left(false), _Node(nullptr) {} bool _Left; _Nodeptr _Node; }; typedef typename _STD conditional, _Node_handle_for_sets, _Node_handle_for_maps>::type _Node_type; #else typedef _Node_handle _Node_type; #endif struct insert_return_type { // stores return information from insert(_Node_type) insert_return_type() : position(), inserted(), node() { // default construct } #if defined(__ghs) insert_return_type(iterator _Itr) : position(_Itr), inserted(), node() { } insert_return_type& operator=(insert_return_type&&) = default; #endif insert_return_type(insert_return_type&& _Right) : position(_Right.position), inserted(_Right.inserted), node(_STD move(_Right.node)) { // copy construct } insert_return_type(iterator _Position_arg, bool _Inserted_arg, _Node_type&& _Node_arg) : position(_Position_arg), inserted(_Inserted_arg), node(_STD move(_Node_arg)) { // construct from values } iterator position; bool inserted; _Node_type node; }; #if defined(__ghs) && _HAS_CPP17 template void _Node_handle_merge_unique(_Tree<_Traits2>& _Source) { for (auto _Itr = _Source.begin(); _Itr != _Source.end();) { _Nodeptr _Mynode = _Itr._Mynode(); auto _Mykey = _Key(_Mynode); // increment the iterator below because extracting a node invalidates its iterator. auto _Where = _Itr++; if (find(_Mykey) == end()) { //element not found, insert auto _Node = _Source.extract(_Where); insert(_STD move(_Node)); } } } template void _Node_handle_merge_equal(_Tree<_Traits2>& _Source) { for (auto _Itr = _Source.begin(); _Itr != _Source.end();) { #if defined(__ghs) auto _Where = _Itr++; _Insert_locator _Ret = _Insert_nohint_prepare(false, *_Where); _TRY_BEGIN if (_Ret._Node) { _Node_type _NodeHandle = _Source.extract( _Where); // Fill in the fields via placement new. _Nodeptr _Mynode = this->_Buynode0(_NodeHandle. _Get_node()); _Insert_at(_Ret._Left, _Ret._Node, *_Where, _Mynode); _NodeHandle._Release_node(); } _CATCH_ALL // This shouldn't be able to happen. _STD terminate(); _CATCH_END #else // increment the iterator below because extracting a node invalidates its iterator. auto _Where = _Itr++; auto _Node = _Source.extract(_Where); insert(_STD move(_Node)); #endif /* defined(__ghs) */ } } #endif /* defined(__ghs) && _HAS_CPP17 */ _Node_type extract(const_iterator _Where) { // copy out element and erase it if (_Where == end()) return (_Node_type()); else { // copy node and erase it _Nodeptr _Mynode = _Where._Mynode(); erase(_Where, true); // remove from tree, but keep values return (_Node_type(_Mynode, get_allocator())); } } _Node_type extract(const key_type& _Keyval) { // find element and extract it return (extract(find(_Keyval))); } insert_return_type insert(_Node_type&& _Nhand) { // insert node, assuming unique keys (!this->_Multi) if (_Nhand.empty() || _Nhand.get_allocator() != get_allocator()) #if defined(__ghs) //insert_return_type should contain the end iterator when node_handle is empty. return (insert_return_type(this->end())); #else return (insert_return_type()); #endif else { // not empty, insert the node #if defined(__ghs) bool _Node_already_allocated = (_Nhand._Get_node() != nullptr); #endif /* defined(__ghs) */ _Nodeptr _Newnode = this->_Buynode0(_Nhand._Get_node()); _Pairib _Ans = _Insert_nohint(false, _STD forward(this->_Myval(_Newnode)), #if defined(__ghs) //If the insert fails free the node instead of destroying, since _Buynode0 was used to create the node _Newnode, false, !_Node_already_allocated); #else _Newnode); #endif if (_Ans.second) _Nhand._Release_node(); return (insert_return_type(_Ans.first, _Ans.second, _STD move(_Nhand))); } } iterator insert(const_iterator, _Node_type&& _Nhand) { // insert node, ignore hint, assuming unique keys (!this->_Multi) return (insert(_STD move(_Nhand)).position); } #endif /* _HAS_CPP17 */ #if defined(__ghs) __noinline #endif /* __ghs */ _Pairib insert(const value_type& _Val) { // try to insert node with value _Val, favoring right side return (_Insert_nohint(false, _Val, _Nil())); } #if defined(__ghs) __noinline #endif /* __ghs */ iterator insert(const_iterator _Where, const value_type& _Val) { // try to insert node with value _Val using _Where as a hint return (_Insert_hint(_Where, _Val, _Nil())); } template #if defined(__ghs) __noinline #endif /* __ghs */ void insert(_Iter _First, _Iter _Last) { // insert [_First, _Last) one at a time _DEBUG_RANGE(_First, _Last); for (; _First != _Last; ++_First) #if _HAS_RVALUE_REFERENCES emplace_hint(end(), *_First); #else /* _HAS_RVALUE_REFERENCES */ insert(end(), *_First); #endif /* _HAS_RVALUE_REFERENCES */ } #if _HAS_INITIALIZER_LISTS void insert(_XSTD initializer_list _Ilist) { // insert initializer_list insert(_Ilist.begin(), _Ilist.end()); } #endif /* _HAS_INITIALIZER_LISTS */ #if defined(__ghs) __noinline #endif /* __ghs */ #if defined(__ghs) && !_HAS_CPP11 // PJP-P01, PJP-P02 void erase(iterator _Where, #else iterator erase(const_iterator _Where, #endif /* __ghs && !_HAS_CPP11 */ bool _Keep = false) { // erase element at _Where #if _ITERATOR_DEBUG_LEVEL == 2 if (_Where._Getcont() != &this->_Get_data() || this->_Isnil(_Where._Mynode())) _DEBUG_ERROR("map/set erase iterator outside range"); _Nodeptr _Erasednode = _Where._Mynode(); // node to erase ++_Where; // save successor iterator for return if (!_Keep) _Orphan_ptr(_Erasednode); #else /* _ITERATOR_DEBUG_LEVEL == 2 */ _Nodeptr _Erasednode = _Where._Mynode(); // node to erase ++_Where; // save successor iterator for return #endif /* _ITERATOR_DEBUG_LEVEL == 2 */ _Nodeptr _Fixnode; // the node to recolor as needed _Nodeptr _Fixnodeparent; // parent of _Fixnode (which may be nil) _Nodeptr _Pnode = _Erasednode; if (this->_Isnil(this->_Left(_Pnode))) _Fixnode = this->_Right(_Pnode); // stitch up right subtree else if (this->_Isnil(this->_Right(_Pnode))) _Fixnode = this->_Left(_Pnode); // stitch up left subtree else { // two subtrees, must lift successor node to replace erased _Pnode = _Where._Mynode(); // _Pnode is successor node _Fixnode = this->_Right(_Pnode); // _Fixnode is only subtree } if (_Pnode == _Erasednode) { // at most one subtree, relink it _Fixnodeparent = this->_Parent(_Erasednode); if (!this->_Isnil(_Fixnode)) this->_Parent(_Fixnode) = _Fixnodeparent; // link up if (_Root() == _Erasednode) _Root() = _Fixnode; // link down from root else if (this->_Left(_Fixnodeparent) == _Erasednode) this->_Left(_Fixnodeparent) = _Fixnode; // link down to left else this->_Right(_Fixnodeparent) = _Fixnode; // link down to right if (_Lmost() == _Erasednode) _Lmost() = this->_Isnil(_Fixnode) ? _Fixnodeparent // smallest is parent of erased node : this->_Min(_Fixnode); // smallest in relinked subtree if (_Rmost() == _Erasednode) _Rmost() = this->_Isnil(_Fixnode) ? _Fixnodeparent // largest is parent of erased node : this->_Max(_Fixnode); // largest in relinked subtree } else { // erased has two subtrees, _Pnode is successor to erased this->_Parent(this->_Left(_Erasednode)) = _Pnode; // link left up this->_Left(_Pnode) = this->_Left(_Erasednode); // link successor down if (_Pnode == this->_Right(_Erasednode)) _Fixnodeparent = _Pnode; // successor is next to erased else { // successor further down, link in place of erased _Fixnodeparent = this->_Parent(_Pnode); // parent is successor's if (!this->_Isnil(_Fixnode)) this->_Parent(_Fixnode) = _Fixnodeparent; // link fix up this->_Left(_Fixnodeparent) = _Fixnode; // link fix down this->_Right(_Pnode) = this->_Right(_Erasednode); // link next down this->_Parent(this->_Right(_Erasednode)) = _Pnode; // right up } if (_Root() == _Erasednode) _Root() = _Pnode; // link down from root else if (this->_Left(this->_Parent(_Erasednode)) == _Erasednode) this->_Left(this->_Parent(_Erasednode)) = _Pnode; // link down to left else this->_Right(this->_Parent(_Erasednode)) = _Pnode; // link down to right this->_Parent(_Pnode) = this->_Parent(_Erasednode); // link successor up _STD swap(this->_Color(_Pnode), this->_Color(_Erasednode)); // recolor it } if (this->_Color(_Erasednode) == this->_Black) { // erasing black link, must recolor/rebalance tree for (; _Fixnode != _Root() && this->_Color(_Fixnode) == this->_Black; _Fixnodeparent = this->_Parent(_Fixnode)) if (_Fixnode == this->_Left(_Fixnodeparent)) { // fixup left subtree _Pnode = this->_Right(_Fixnodeparent); if (this->_Color(_Pnode) == this->_Red) { // rotate red up from right subtree this->_Color(_Pnode) = this->_Black; this->_Color(_Fixnodeparent) = this->_Red; _Lrotate(_Fixnodeparent); _Pnode = this->_Right(_Fixnodeparent); } if (this->_Isnil(_Pnode)) _Fixnode = _Fixnodeparent; // shouldn't happen else if (this->_Color(this->_Left(_Pnode)) == this->_Black && this->_Color(this->_Right(_Pnode)) == this->_Black) { // redden right subtree with black children this->_Color(_Pnode) = this->_Red; _Fixnode = _Fixnodeparent; } else { // must rearrange right subtree if (this->_Color(this->_Right(_Pnode)) == this->_Black) { // rotate red up from left sub-subtree this->_Color(this->_Left(_Pnode)) = this->_Black; this->_Color(_Pnode) = this->_Red; _Rrotate(_Pnode); _Pnode = this->_Right(_Fixnodeparent); } this->_Color(_Pnode) = this->_Color(_Fixnodeparent); this->_Color(_Fixnodeparent) = this->_Black; this->_Color(this->_Right(_Pnode)) = this->_Black; _Lrotate(_Fixnodeparent); break; // tree now recolored/rebalanced } } else { // fixup right subtree _Pnode = this->_Left(_Fixnodeparent); if (this->_Color(_Pnode) == this->_Red) { // rotate red up from left subtree this->_Color(_Pnode) = this->_Black; this->_Color(_Fixnodeparent) = this->_Red; _Rrotate(_Fixnodeparent); _Pnode = this->_Left(_Fixnodeparent); } if (this->_Isnil(_Pnode)) _Fixnode = _Fixnodeparent; // shouldn't happen else if (this->_Color(this->_Right(_Pnode)) == this->_Black && this->_Color(this->_Left(_Pnode)) == this->_Black) { // redden left subtree with black children this->_Color(_Pnode) = this->_Red; _Fixnode = _Fixnodeparent; } else { // must rearrange left subtree if (this->_Color(this->_Left(_Pnode)) == this->_Black) { // rotate red up from right sub-subtree this->_Color(this->_Right(_Pnode)) = this->_Black; this->_Color(_Pnode) = this->_Red; _Lrotate(_Pnode); _Pnode = this->_Left(_Fixnodeparent); } this->_Color(_Pnode) = this->_Color(_Fixnodeparent); this->_Color(_Fixnodeparent) = this->_Black; this->_Color(this->_Left(_Pnode)) = this->_Black; _Rrotate(_Fixnodeparent); break; // tree now recolored/rebalanced } } this->_Color(_Fixnode) = this->_Black; // stopping node is black } if (!_Keep) { // destroy the element this->_Getal().destroy( _STD addressof(this->_Myval(_Erasednode))); // delete node this->_Getal().deallocate(_Erasednode, 1); } if (0 < this->_Mysize()) --this->_Mysize(); #if !defined(__ghs) || _HAS_CPP11 // PJP-P02 return (iterator(_Where._Ptr, &this->_Get_data())); // return successor iterator #endif /* !__ghs || _HAS_CPP11 */ } #if defined(__ghs) __noinline #endif /* __ghs */ #if defined(__ghs) && !_HAS_CPP11 // PJP-P01, PJP-P02 void erase(iterator _First, iterator _Last) #else iterator erase(const_iterator _First, const_iterator _Last) #endif /* __ghs && !_HAS_CPP11 */ { // erase [_First, _Last) if (_First == begin() && _Last == end()) { // erase all clear(); #if !defined(__ghs) || _HAS_CPP11 // PJP-P02 return (begin()); #endif /* !__ghs || _HAS_CPP11 */ } else { // partial erase, one at a time while (_First != _Last) erase(_First++); #if !defined(__ghs) || _HAS_CPP11 // PJP-P02 return (iterator(_First._Ptr, &this->_Get_data())); #endif /* !__ghs || _HAS_CPP11 */ } } #if defined(__ghs) __noinline #endif /* __ghs */ size_type erase(const key_type& _Keyval) { // erase and count all that match _Keyval _Pairii _Where = equal_range(_Keyval); size_type _Num = 0; _Distance(_Where.first, _Where.second, _Num); erase(_Where.first, _Where.second); return (_Num); } #if defined(__ghs) __noinline #endif /* __ghs */ void clear() _NOEXCEPT { // erase all #if _ITERATOR_DEBUG_LEVEL == 2 this->_Orphan_ptr(0); #endif /* _ITERATOR_DEBUG_LEVEL == 2 */ _Erase(_Root()); _Root() = this->_Myhead(); _Lmost() = this->_Myhead(); _Rmost() = this->_Myhead(); this->_Mysize() = 0; } #if defined(__ghs) __noinline #endif /* __ghs */ iterator find(const key_type& _Keyval) { // find an element in mutable sequence that matches _Keyval iterator _Where = lower_bound(_Keyval); return (_Where == end() || _DEBUG_LT_PRED(this->_Getcomp(), _Keyval, this->_Key(_Where._Mynode())) ? end() : _Where); } #if defined(__ghs) __noinline #endif /* __ghs */ const_iterator find(const key_type& _Keyval) const { // find an element in nonmutable sequence that matches _Keyval const_iterator _Where = lower_bound(_Keyval); return (_Where == end() || _DEBUG_LT_PRED(this->_Getcomp(), _Keyval, this->_Key(_Where._Mynode())) ? end() : _Where); } #if _HAS_CPP14 template iterator find(const _Other& _Keyval) { // find an element in mutable sequence that matches _Keyval iterator _Where = lower_bound(_Keyval); return (_Where == end() || _DEBUG_LT_PRED(this->_Getcomp(), _Keyval, this->_Key(_Where._Mynode())) ? end() : _Where); } template const_iterator find(const _Other& _Keyval) const { // find an element in nonmutable sequence that matches _Keyval const_iterator _Where = lower_bound(_Keyval); return (_Where == end() || _DEBUG_LT_PRED(this->_Getcomp(), _Keyval, this->_Key(_Where._Mynode())) ? end() : _Where); } #endif /* _HAS_CPP14 */ #if defined(__ghs) __noinline #endif /* __ghs */ size_type count(const key_type& _Keyval) const { // count all elements that match _Keyval _Paircc _Ans = equal_range(_Keyval); size_type _Num = 0; _Distance(_Ans.first, _Ans.second, _Num); return (_Num); } #if _HAS_CPP14 template size_type count(const _Other& _Keyval) const { // count all elements that match _Keyval _Paircc _Ans = equal_range(_Keyval); size_type _Num = 0; _Distance(_Ans.first, _Ans.second, _Num); return (_Num); } #endif /* _HAS_CPP14 */ iterator lower_bound(const key_type& _Keyval) { // find leftmost node not less than _Keyval in mutable tree return (iterator(_Lbound(_Keyval), &this->_Get_data())); } const_iterator lower_bound(const key_type& _Keyval) const { // find leftmost node not less than _Keyval in nonmutable tree return (const_iterator(_Lbound(_Keyval), &this->_Get_data())); } #if _HAS_CPP14 template iterator lower_bound(const _Other& _Keyval) { // find leftmost node not less than _Keyval in mutable tree return (iterator(_Lbound(_Keyval), &this->_Get_data())); } template const_iterator lower_bound(const _Other& _Keyval) const { // find leftmost node not less than _Keyval in nonmutable tree return (const_iterator(_Lbound(_Keyval), &this->_Get_data())); } #endif /* _HAS_CPP14 */ iterator upper_bound(const key_type& _Keyval) { // find leftmost node greater than _Keyval in mutable tree return (iterator(_Ubound(_Keyval), &this->_Get_data())); } const_iterator upper_bound(const key_type& _Keyval) const { // find leftmost node greater than _Keyval in nonmutable tree return (const_iterator(_Ubound(_Keyval), &this->_Get_data())); } #if _HAS_CPP14 template iterator upper_bound(const _Other& _Keyval) { // find leftmost node greater than _Keyval in mutable tree return (iterator(_Ubound(_Keyval), &this->_Get_data())); } template const_iterator upper_bound(const _Other& _Keyval) const { // find leftmost node greater than _Keyval in nonmutable tree return (const_iterator(_Ubound(_Keyval), &this->_Get_data())); } #endif /* _HAS_CPP14 */ _Pairii equal_range(const key_type& _Keyval) { // find range equivalent to _Keyval in mutable tree return (_Eqrange(_Keyval)); } _Paircc equal_range(const key_type& _Keyval) const { // find range equivalent to _Keyval in nonmutable tree return (_Eqrange(_Keyval)); } #if _HAS_CPP14 template _Pairii equal_range(const _Other& _Keyval) { // find range equivalent to _Keyval in mutable tree return (_Eqrange(_Keyval)); } template _Paircc equal_range(const _Other& _Keyval) const { // find range equivalent to _Keyval in nonmutable tree return (_Eqrange(_Keyval)); } #endif /* _HAS_CPP14 */ #if defined(__ghs) __noinline #endif /* __ghs */ void swap(_Myt& _Right) { // exchange contents with _Right if (this == &_Right) ; // same object, do nothing else if (this->_Getal() == _Right._Getal()) { // same allocator, swap control information this->_Swap_all(_Right); _Swap_adl(this->_Getcomp(), _Right._Getcomp()); _Swap_adl(this->_Myhead(), _Right._Myhead()); _STD swap(this->_Mysize(), _Right._Mysize()); } else if (_Alty::propagate_on_container_swap::value) { // swap allocators and control information this->_Swap_alloc(_Right); _Swap_adl(this->_Getcomp(), _Right._Getcomp()); _Swap_adl(this->_Myhead(), _Right._Myhead()); _STD swap(this->_Mysize(), _Right._Mysize()); } else { // containers are incompatible #if _ITERATOR_DEBUG_LEVEL == 2 _DEBUG_ERROR("map/set containers incompatible for swap"); #elif defined(__ghs) && !_HAS_EXCEPTIONS // PJP-B02 // Do nothing, the behavior is undefined #else /* ITERATOR_DEBUG_LEVEL == 2 */ _XSTD terminate(); #endif /* ITERATOR_DEBUG_LEVEL == 2 */ } } protected: template _Nodeptr _Buynode_if_nil(_Nodeptr _Node, _Valty _REFREF) { // node exists, just return it return (_Node); } template _Nodeptr _Buynode_if_nil(_Nil, _Valty _REFREF _Val) { // node doesn't exist, make it return (this->_Buynode(_STD forward<_Valty>(_Val))); } void _Destroy_if_not_nil(_Nodeptr _Newnode) { // node exists, destroy it this->_Getal().destroy( _STD addressof(this->_Myval(_Newnode))); this->_Getal().deallocate(_Newnode, 1); } void _Destroy_if_not_nil(_Nil) { // node doesn't exist, do nothing } #if defined(__ghs) void _Free_if_not_nil(_Nodeptr _Newnode) { // node exists, free it this->_Freenode0(_Newnode); } void _Free_if_not_nil(_Nil) { // node doesn't exist, do nothing } #endif template #if defined(__ghs) __noinline #endif /* __ghs */ iterator _Insert_hint(const_iterator _Where, _Valty _REFREF _Val, _Nodety _Newnode) { // try to insert node using _Where as a hint const_iterator _Next; bool _Leftish = false; // assume nearest point is end of sequence _TRY_BEGIN #if _ITERATOR_DEBUG_LEVEL == 2 if (_Where._Getcont() != &this->_Get_data()) _DEBUG_ERROR("map/set insert iterator outside range"); #endif /* _ITERATOR_DEBUG_LEVEL == 2 */ if (size() == 0) return (_Insert_at(true, this->_Myhead(), _STD forward<_Valty>(_Val), _Newnode)); // empty tree else if (this->_Multi) { // insert even if duplicate if (_Where == begin()) { // insert at beginning if before first element if (!_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Where._Mynode()), this->_Kfn(_Val))) return (_Insert_at(true, _Where._Mynode(), _STD forward<_Valty>(_Val), _Newnode)); _Leftish = true; // nearest point is beginning of sequence } else if (_Where == end()) { // insert at end if after last element if (!_DEBUG_LT_PRED(this->_Getcomp(), this->_Kfn(_Val), this->_Key(_Rmost()))) return (_Insert_at(false, _Rmost(), _STD forward<_Valty>(_Val), _Newnode)); } else if (!_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Where._Mynode()), this->_Kfn(_Val)) && !_DEBUG_LT_PRED(this->_Getcomp(), this->_Kfn(_Val), this->_Key((--(_Next = _Where))._Mynode()))) { // insert before _Where if (this->_Isnil(this->_Right(_Next._Mynode()))) return (_Insert_at(false, _Next._Mynode(), _STD forward<_Valty>(_Val), _Newnode)); else return (_Insert_at(true, _Where._Mynode(), _STD forward<_Valty>(_Val), _Newnode)); } else if (!_DEBUG_LT_PRED(this->_Getcomp(), this->_Kfn(_Val), this->_Key(_Where._Mynode())) && (++(_Next = _Where) == end() || !_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Next._Mynode()), this->_Kfn(_Val)))) { // insert after _Where if (this->_Isnil(this->_Right(_Where._Mynode()))) return (_Insert_at(false, _Where._Mynode(), _STD forward<_Valty>(_Val), _Newnode)); else return (_Insert_at(true, _Next._Mynode(), _STD forward<_Valty>(_Val), _Newnode)); } else _Leftish = true; // nearest point is beginning of sequence } else { // insert only if unique if (_Where == begin()) { // insert at beginning if before first element if (_DEBUG_LT_PRED(this->_Getcomp(), this->_Kfn(_Val), this->_Key(_Where._Mynode()))) return (_Insert_at(true, _Where._Mynode(), _STD forward<_Valty>(_Val), _Newnode)); } else if (_Where == end()) { // insert at end if after last element if (_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Rmost()), this->_Kfn(_Val))) return (_Insert_at(false, _Rmost(), _STD forward<_Valty>(_Val), _Newnode)); } else if (_DEBUG_LT_PRED(this->_Getcomp(), this->_Kfn(_Val), this->_Key(_Where._Mynode())) && _DEBUG_LT_PRED(this->_Getcomp(), this->_Key((--(_Next = _Where))._Mynode()), this->_Kfn(_Val))) { // insert before _Where if (this->_Isnil(this->_Right(_Next._Mynode()))) return (_Insert_at(false, _Next._Mynode(), _STD forward<_Valty>(_Val), _Newnode)); else return (_Insert_at(true, _Where._Mynode(), _STD forward<_Valty>(_Val), _Newnode)); } else if (_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Where._Mynode()), this->_Kfn(_Val)) && (++(_Next = _Where) == end() || _DEBUG_LT_PRED(this->_Getcomp(), this->_Kfn(_Val), this->_Key(_Next._Mynode())))) { // insert after _Where if (this->_Isnil(this->_Right(_Where._Mynode()))) return (_Insert_at(false, _Where._Mynode(), _STD forward<_Valty>(_Val), _Newnode)); else return (_Insert_at(true, _Next._Mynode(), _STD forward<_Valty>(_Val), _Newnode)); } } _CATCH_ALL _Destroy_if_not_nil(_Newnode); _RERAISE; _CATCH_END return (_Insert_nohint(_Leftish, _STD forward<_Valty>(_Val), _Newnode).first); } template #if defined(__ghs) __noinline #endif /* __ghs */ _Pairib _Insert_nohint(bool _Leftish, #if defined(__ghs) _Valty _REFREF _Val, _Nodety _Newnode, bool _Destroy = true, bool _Free = true) #else _Valty _REFREF _Val, _Nodety _Newnode) #endif { // try to insert node, on left if _Leftish _TRY_BEGIN _Nodeptr _Trynode = _Root(); _Nodeptr _Wherenode = this->_Myhead(); bool _Addleft = true; // add to left of head if tree empty while (!this->_Isnil(_Trynode)) { // look for leaf to insert before (_Addleft) or after _Wherenode = _Trynode; if (_Leftish) _Addleft = !_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Trynode), this->_Kfn(_Val)); // favor left end else _Addleft = _DEBUG_LT_PRED(this->_Getcomp(), this->_Kfn(_Val), this->_Key(_Trynode)); // favor right end _Trynode = _Addleft ? this->_Left(_Trynode) : this->_Right(_Trynode); } if (this->_Multi) return (_Pairib(_Insert_at(_Addleft, _Wherenode, _STD forward<_Valty>(_Val), _Newnode), true)); else { // insert only if unique iterator _Where = iterator(_Wherenode, &this->_Get_data()); if (!_Addleft) ; // need to test if insert after is okay else if (_Where == begin()) return (_Pairib(_Insert_at(true, _Wherenode, _STD forward<_Valty>(_Val), _Newnode), true)); else --_Where; // need to test if insert before is okay if (_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Where._Mynode()), this->_Kfn(_Val))) return (_Pairib(_Insert_at(_Addleft, _Wherenode, _STD forward<_Valty>(_Val), _Newnode), true)); else { // duplicate, don't insert #if defined(__ghs) if (_Destroy) _Destroy_if_not_nil(_Newnode); else if (_Free) _Free_if_not_nil(_Newnode); #else _Destroy_if_not_nil(_Newnode); #endif return (_Pairib(_Where, false)); } } _CATCH_ALL #if defined(__ghs) if (_Destroy) _Destroy_if_not_nil(_Newnode); else if (_Free) _Free_if_not_nil(_Newnode); #else _Destroy_if_not_nil(_Newnode); #endif _RERAISE; _CATCH_END #if defined(__ghs) /* NOTREACHED */ #endif /* defined(__ghs) */ } #if defined(__ghs) && _HAS_CPP17 template // This is a version of the _Insert_nohint function that // returns an insert_locator (similar to an insert_return_type) // if the insert can proceed. The idea is to do all of this // before possibly unlinking a node from // the old set in the when doing merge. If the compariator // throws, we will not have extracted the node from the old // set by this point. _Insert_locator _Insert_nohint_prepare(bool _Leftish, const _Valty & _Val) { // try to insert node, on left if _Leftish _TRY_BEGIN _Nodeptr _Trynode = _Root(); _Nodeptr _Wherenode = this->_Myhead(); bool _Addleft = true; // add to left of head if tree empty while (!this->_Isnil(_Trynode)) { // look for leaf to insert before (_Addleft) or after _Wherenode = _Trynode; if (_Leftish) _Addleft = !_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Trynode), this->_Kfn(_Val)); // favor left end else _Addleft = _DEBUG_LT_PRED(this->_Getcomp(), this->_Kfn(_Val), this->_Key(_Trynode)); // favor right end _Trynode = _Addleft ? this->_Left(_Trynode) : this->_Right(_Trynode); } if (this->_Multi) return _Insert_locator(_Addleft, _Wherenode); else { // insert only if unique iterator _Where = iterator(_Wherenode, &this->_Get_data()); if (!_Addleft) ; // need to test if insert after is okay else if (_Where == begin()) return _Insert_locator(true, _Wherenode); else --_Where; // need to test if insert before is okay if (_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Where._Mynode()), this->_Kfn(_Val))) return _Insert_locator(_Addleft, _Wherenode); else { // duplicate, don't insert return _Insert_locator(); } } _CATCH_ALL _RERAISE; _CATCH_END /* NOTREACHED */ } #endif /* defined(__ghs) && _HAS_CPP17 */ template iterator _Insert_at(bool _Addleft, _Nodeptr _Wherenode, _Valty _REFREF _Val, _Nodety _Node) { // add node with value next to _Wherenode, to left if _Addleft if (max_size() - 1 <= this->_Mysize()) { // tree would get too big, fail _Destroy_if_not_nil(_Node); _Xlength_error("map/set too long"); } _Nodeptr _Newnode = _Buynode_if_nil(_Node, _STD forward<_Valty>(_Val)); ++this->_Mysize(); _Newnode->_Parent = _Wherenode; if (_Wherenode == this->_Myhead()) { // first node in tree, just set head values _Root() = _Newnode; _Lmost() = _Newnode; _Rmost() = _Newnode; } else if (_Addleft) { // add to left of _Wherenode this->_Left(_Wherenode) = _Newnode; if (_Wherenode == _Lmost()) _Lmost() = _Newnode; } else { // add to right of _Wherenode this->_Right(_Wherenode) = _Newnode; if (_Wherenode == _Rmost()) _Rmost() = _Newnode; } for (_Nodeptr _Pnode = _Newnode; this->_Color(this->_Parent(_Pnode)) == this->_Red; ) if (this->_Parent(_Pnode) == this->_Left(this->_Parent(this->_Parent(_Pnode)))) { // fixup red-red in left subtree _Wherenode = this->_Right(this->_Parent(this->_Parent(_Pnode))); if (this->_Color(_Wherenode) == this->_Red) { // parent has two red children, blacken both this->_Color(this->_Parent(_Pnode)) = this->_Black; this->_Color(_Wherenode) = this->_Black; this->_Color(this->_Parent(this->_Parent(_Pnode))) = this->_Red; _Pnode = this->_Parent(this->_Parent(_Pnode)); } else { // parent has red and black children if (_Pnode == this->_Right(this->_Parent(_Pnode))) { // rotate right child to left _Pnode = this->_Parent(_Pnode); _Lrotate(_Pnode); } this->_Color(this->_Parent(_Pnode)) = this->_Black; // propagate red up this->_Color(this->_Parent(this->_Parent(_Pnode))) = this->_Red; _Rrotate(this->_Parent(this->_Parent(_Pnode))); } } else { // fixup red-red in right subtree _Wherenode = this->_Left(this->_Parent(this->_Parent(_Pnode))); if (this->_Color(_Wherenode) == this->_Red) { // parent has two red children, blacken both this->_Color(this->_Parent(_Pnode)) = this->_Black; this->_Color(_Wherenode) = this->_Black; this->_Color(this->_Parent(this->_Parent(_Pnode))) = this->_Red; _Pnode = this->_Parent(this->_Parent(_Pnode)); } else { // parent has red and black children if (_Pnode == this->_Left(this->_Parent(_Pnode))) { // rotate left child to right _Pnode = this->_Parent(_Pnode); _Rrotate(_Pnode); } this->_Color(this->_Parent(_Pnode)) = this->_Black; // propagate red up this->_Color(this->_Parent(this->_Parent(_Pnode))) = this->_Red; _Lrotate(this->_Parent(this->_Parent(_Pnode))); } } this->_Color(_Root()) = this->_Black; // root is always black return (iterator(_Newnode, &this->_Get_data())); } template #if defined(__ghs) __noinline #endif /* __ghs */ void _Copy(const _Myt& _Right, _Moveit _Movefl) { // copy or move entire tree from _Right _Root() = _Copy_nodes(_Right._Root(), this->_Myhead(), _Movefl); this->_Mysize() = _Right.size(); this->_Getcomp() = _Right._Getcomp(); if (!this->_Isnil(_Root())) { // nonempty tree, look for new smallest and largest _Lmost() = this->_Min(_Root()); _Rmost() = this->_Max(_Root()); } else { // empty tree, just tidy head pointers _Lmost() = this->_Myhead(); _Rmost() = this->_Myhead(); } } template _Nodeptr _Copy_or_move(_Ty& _Val, _Copy_tag, _Is_set) { // copy to new node return (this->_Buynode(_Val)); } template _Nodeptr _Copy_or_move(_Ty& _Val, _Move_tag, true_type) { // move to new node -- set return (this->_Buynode(_STD move(_Val))); } template _Nodeptr _Copy_or_move(_Ty& _Val, _Move_tag, false_type) { // move to new node -- map return (this->_Buynode( _STD move(const_cast(_Val.first)), _STD move(_Val.second))); } template _Nodeptr _Copy_nodes(_Nodeptr _Rootnode, _Nodeptr _Wherenode, _Moveit _Movefl) { // copy entire subtree, recursively _Nodeptr _Newroot = this->_Myhead(); // point at nil node if (!this->_Isnil(_Rootnode)) { // copy or move a node, then any subtrees typename is_same::type _Is_set; _Nodeptr _Pnode = _Copy_or_move( this->_Myval(_Rootnode), _Movefl, _Is_set); _Pnode->_Parent = _Wherenode; _Pnode->_Color = this->_Color(_Rootnode); if (this->_Isnil(_Newroot)) _Newroot = _Pnode; // memorize new root _TRY_BEGIN this->_Left(_Pnode) = _Copy_nodes(this->_Left(_Rootnode), _Pnode, _Movefl); this->_Right(_Pnode) = _Copy_nodes(this->_Right(_Rootnode), _Pnode, _Movefl); _CATCH_ALL _Erase(_Newroot); // subtree copy failed, bail out _RERAISE; _CATCH_END } return (_Newroot); // return newly constructed tree } template _Paircc _Eqrange(const _Other& _Keyval) const { // find leftmost node not less than _Keyval _Nodeptr _Pnode = _Root(); _Nodeptr _Lonode = this->_Myhead(); // end() if search fails _Nodeptr _Hinode = this->_Myhead(); // end() if search fails while (!this->_Isnil(_Pnode)) if (_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Pnode), _Keyval)) _Pnode = this->_Right(_Pnode); // descend right subtree else { // _Pnode not less than _Keyval, remember it if (this->_Isnil(_Hinode) && _DEBUG_LT_PRED(this->_Getcomp(), _Keyval, this->_Key(_Pnode))) _Hinode = _Pnode; // _Pnode greater, remember it _Lonode = _Pnode; _Pnode = this->_Left(_Pnode); // descend left subtree } _Pnode = this->_Isnil(_Hinode) ? _Root() : this->_Left(_Hinode); // continue scan for upper bound while (!this->_Isnil(_Pnode)) if (_DEBUG_LT_PRED(this->_Getcomp(), _Keyval, this->_Key(_Pnode))) { // _Pnode greater than _Keyval, remember it _Hinode = _Pnode; _Pnode = this->_Left(_Pnode); // descend left subtree } else _Pnode = this->_Right(_Pnode); // descend right subtree const_iterator _First = const_iterator(_Lonode, &this->_Get_data()); const_iterator _Last = const_iterator(_Hinode, &this->_Get_data()); return (_Paircc(_First, _Last)); } template _Pairii _Eqrange(const _Other& _Keyval) { // find leftmost node not less than _Keyval _Paircc _Ans(static_cast(this)->_Eqrange(_Keyval)); iterator _First = iterator(_Ans.first._Ptr, &this->_Get_data()); iterator _Last = iterator(_Ans.second._Ptr, &this->_Get_data()); return (_Pairii(_First, _Last)); } #if defined(__ghs) __noinline #endif /* __ghs */ void _Erase(_Nodeptr _Rootnode) { // free entire subtree, recursively for (_Nodeptr _Pnode = _Rootnode; !this->_Isnil(_Pnode); _Rootnode = _Pnode) { // free subtrees, then node _Erase(this->_Right(_Pnode)); _Pnode = this->_Left(_Pnode); this->_Getal().destroy( _STD addressof(this->_Myval(_Rootnode))); this->_Getal().deallocate(_Rootnode, 1); } } bool _Compare(const key_type& _Left, const key_type& _Right) const { // compare key_type to key_type, with debug checks return (_DEBUG_LT_PRED(this->_Getcomp(), _Left, _Right)); } template bool _Compare(const _Ty1& _Left, const _Ty2& _Right) const { // compare _Ty1 to _Ty2, without debug checks return (this->_Getcomp()(_Left, _Right)); } template #if defined(__ghs) __noinline #endif /* __ghs */ _Nodeptr _Lbound(const _Other& _Keyval) const { // find leftmost node not less than _Keyval _Nodeptr _Pnode = _Root(); _Nodeptr _Wherenode = this->_Myhead(); // end() if search fails while (!this->_Isnil(_Pnode)) if (_Compare(this->_Key(_Pnode), _Keyval)) _Pnode = this->_Right(_Pnode); // descend right subtree else { // _Pnode not less than _Keyval, remember it _Wherenode = _Pnode; _Pnode = this->_Left(_Pnode); // descend left subtree } return (_Wherenode); // return best remembered candidate } _Nodeptr& _Lmost() const { // return leftmost node in nonmutable tree return (this->_Left(this->_Myhead())); } #if defined(__ghs) __noinline #endif /* __ghs */ void _Lrotate(_Nodeptr _Wherenode) { // promote right node to root of subtree _Nodeptr _Pnode = this->_Right(_Wherenode); this->_Right(_Wherenode) = this->_Left(_Pnode); if (!this->_Isnil(this->_Left(_Pnode))) this->_Parent(this->_Left(_Pnode)) = _Wherenode; this->_Parent(_Pnode) = this->_Parent(_Wherenode); if (_Wherenode == _Root()) _Root() = _Pnode; else if (_Wherenode == this->_Left(this->_Parent(_Wherenode))) this->_Left(this->_Parent(_Wherenode)) = _Pnode; else this->_Right(this->_Parent(_Wherenode)) = _Pnode; this->_Left(_Pnode) = _Wherenode; this->_Parent(_Wherenode) = _Pnode; } _Nodeptr& _Rmost() const { // return rightmost node in nonmutable tree return (this->_Right(this->_Myhead())); } _Nodeptr& _Root() const { // return root of nonmutable tree return (this->_Parent(this->_Myhead())); } #if defined(__ghs) __noinline #endif /* __ghs */ void _Rrotate(_Nodeptr _Wherenode) { // promote left node to root of subtree _Nodeptr _Pnode = this->_Left(_Wherenode); this->_Left(_Wherenode) = this->_Right(_Pnode); if (!this->_Isnil(this->_Right(_Pnode))) this->_Parent(this->_Right(_Pnode)) = _Wherenode; this->_Parent(_Pnode) = this->_Parent(_Wherenode); if (_Wherenode == _Root()) _Root() = _Pnode; else if (_Wherenode == this->_Right(this->_Parent(_Wherenode))) this->_Right(this->_Parent(_Wherenode)) = _Pnode; else this->_Left(this->_Parent(_Wherenode)) = _Pnode; this->_Right(_Pnode) = _Wherenode; this->_Parent(_Wherenode) = _Pnode; } template #if defined(__ghs) __noinline #endif /* __ghs */ _Nodeptr _Ubound(const _Other& _Keyval) const { // find leftmost node greater than _Keyval _Nodeptr _Pnode = _Root(); _Nodeptr _Wherenode = this->_Myhead(); // end() if search fails while (!this->_Isnil(_Pnode)) if (_Compare(_Keyval, this->_Key(_Pnode))) { // _Pnode greater than _Keyval, remember it _Wherenode = _Pnode; _Pnode = this->_Left(_Pnode); // descend left subtree } else _Pnode = this->_Right(_Pnode); // descend right subtree return (_Wherenode); // return best remembered candidate } #if _ITERATOR_DEBUG_LEVEL == 2 void _Orphan_ptr(_Nodeptr _Ptr) { // orphan iterators with specified node pointers _Lockit _Lock(_LOCK_DEBUG); const_iterator **_Pnext = (const_iterator **)this->_Getpfirst(); if (_Pnext != 0) while (*_Pnext != 0) if ((*_Pnext)->_Ptr == this->_Myhead() || _Ptr != 0 && (*_Pnext)->_Ptr != _Ptr) _Pnext = (const_iterator **)(*_Pnext)->_Getpnext(); else { // orphan the iterator (*_Pnext)->_Clrcont(); *_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext(); } } #endif /* _ITERATOR_DEBUG_LEVEL == 2 */ void _Tidy() { // free all storage erase(begin(), end()); } const key_type& _Kfn(const value_type& _Val) const { // get key from value return (_Traits::_Kfn(_Val)); } const key_type& _Key(_Nodeptr _Pnode) const { // return reference to key in node return ((const key_type&)this->_Kfn(this->_Myval(_Pnode))); } }; // _Tree TEMPLATE OPERATORS template inline bool operator==(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right) { // test for _Tree equality return (_Left.size() == _Right.size() && _STD equal(_Left.begin(), _Left.end(), _Right.begin())); } template inline bool operator!=(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right) { // test for _Tree inequality return (!(_Left == _Right)); } template inline bool operator<(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right) { // test if _Less < _Right for _Trees return (_STD lexicographical_compare(_Left.begin(), _Left.end(), _Right.begin(), _Right.end())); } template inline bool operator>(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right) { // test if _Less > _Right for _Trees return (_Right < _Left); } template inline bool operator<=(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right) { // test if _Less <= _Right for _Trees return (!(_Right < _Left)); } template inline bool operator>=(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right) { // test if _Less >= _Right for _Trees return (!(_Left < _Right)); } _STD_END #if defined(__ghs) #if defined(__ghs_max_pack_value) #pragma pack(pop) #endif /* defined(__ghs_max_pack_value) */ #pragma ghs enddata #pragma ghs end_cxx_lib_header #endif /* defined(__ghs) */ #endif /* _XTREE_ */ /* * Copyright (c) by P.J. Plauger. All rights reserved. * Consult your license regarding permissions and restrictions. V8.03b/17:0063 */