codekingpro/portable-devtools
114k
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCUDACXX___TREE11#define _LIBCUDACXX___TREE12 13#include <__config>14#include <iterator>15#include <memory>16#include <stdexcept>17#include <algorithm>18 19#if defined(_CCCL_IMPLICIT_SYSTEM_HEADER_GCC)20# pragma GCC system_header21#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_CLANG)22# pragma clang system_header23#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_MSVC)24# pragma system_header25#endif // no system header26 27_LIBCUDACXX_PUSH_MACROS28#include <__undef_macros>29 30 31_LIBCUDACXX_BEGIN_NAMESPACE_STD32 33#if defined(_LIBCUDACXX_COMPILER_GCC) // gcc.gnu.org/PR3780434template <class, class, class, class> class _LIBCUDACXX_TEMPLATE_VIS map;35template <class, class, class, class> class _LIBCUDACXX_TEMPLATE_VIS multimap;36template <class, class, class> class _LIBCUDACXX_TEMPLATE_VIS set;37template <class, class, class> class _LIBCUDACXX_TEMPLATE_VIS multiset;38#endif // _LIBCUDACXX_COMPILER_GCC39 40template <class _Tp, class _Compare, class _Allocator> class __tree;41template <class _Tp, class _NodePtr, class _DiffType>42 class _LIBCUDACXX_TEMPLATE_VIS __tree_iterator;43template <class _Tp, class _ConstNodePtr, class _DiffType>44 class _LIBCUDACXX_TEMPLATE_VIS __tree_const_iterator;45 46template <class _Pointer> class __tree_end_node;47template <class _VoidPtr> class __tree_node_base;48template <class _Tp, class _VoidPtr> class __tree_node;49 50template <class _Key, class _Value>51struct __value_type;52 53template <class _Allocator> class __map_node_destructor;54template <class _TreeIterator> class _LIBCUDACXX_TEMPLATE_VIS __map_iterator;55template <class _TreeIterator> class _LIBCUDACXX_TEMPLATE_VIS __map_const_iterator;56 57/*58 59_NodePtr algorithms60 61The algorithms taking _NodePtr are red black tree algorithms. Those62algorithms taking a parameter named __root should assume that __root63points to a proper red black tree (unless otherwise specified).64 65Each algorithm herein assumes that __root->__parent_ points to a non-null66structure which has a member __left_ which points back to __root. No other67member is read or written to at __root->__parent_.68 69__root->__parent_ will be referred to below (in comments only) as end_node.70end_node->__left_ is an externably accessible lvalue for __root, and can be71changed by node insertion and removal (without explicit reference to end_node).72 73All nodes (with the exception of end_node), even the node referred to as74__root, have a non-null __parent_ field.75 76*/77 78// Returns: true if __x is a left child of its parent, else false79// Precondition: __x != nullptr.80template <class _NodePtr>81inline _LIBCUDACXX_INLINE_VISIBILITY82bool83__tree_is_left_child(_NodePtr __x) noexcept84{85 return __x == __x->__parent_->__left_;86}87 88// Determines if the subtree rooted at __x is a proper red black subtree. If89// __x is a proper subtree, returns the black height (null counts as 1). If90// __x is an improper subtree, returns 0.91template <class _NodePtr>92unsigned93__tree_sub_invariant(_NodePtr __x)94{95 if (__x == nullptr)96 return 1;97 // parent consistency checked by caller98 // check __x->__left_ consistency99 if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x)100 return 0;101 // check __x->__right_ consistency102 if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x)103 return 0;104 // check __x->__left_ != __x->__right_ unless both are nullptr105 if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr)106 return 0;107 // If this is red, neither child can be red108 if (!__x->__is_black_)109 {110 if (__x->__left_ && !__x->__left_->__is_black_)111 return 0;112 if (__x->__right_ && !__x->__right_->__is_black_)113 return 0;114 }115 unsigned __h = __tree_sub_invariant(__x->__left_);116 if (__h == 0)117 return 0; // invalid left subtree118 if (__h != __tree_sub_invariant(__x->__right_))119 return 0; // invalid or different height right subtree120 return __h + __x->__is_black_; // return black height of this node121}122 123// Determines if the red black tree rooted at __root is a proper red black tree.124// __root == nullptr is a proper tree. Returns true is __root is a proper125// red black tree, else returns false.126template <class _NodePtr>127bool128__tree_invariant(_NodePtr __root)129{130 if (__root == nullptr)131 return true;132 // check __x->__parent_ consistency133 if (__root->__parent_ == nullptr)134 return false;135 if (!__tree_is_left_child(__root))136 return false;137 // root must be black138 if (!__root->__is_black_)139 return false;140 // do normal node checks141 return __tree_sub_invariant(__root) != 0;142}143 144// Returns: pointer to the left-most node under __x.145// Precondition: __x != nullptr.146template <class _NodePtr>147inline _LIBCUDACXX_INLINE_VISIBILITY148_NodePtr149__tree_min(_NodePtr __x) noexcept150{151 while (__x->__left_ != nullptr)152 __x = __x->__left_;153 return __x;154}155 156// Returns: pointer to the right-most node under __x.157// Precondition: __x != nullptr.158template <class _NodePtr>159inline _LIBCUDACXX_INLINE_VISIBILITY160_NodePtr161__tree_max(_NodePtr __x) noexcept162{163 while (__x->__right_ != nullptr)164 __x = __x->__right_;165 return __x;166}167 168// Returns: pointer to the next in-order node after __x.169// Precondition: __x != nullptr.170template <class _NodePtr>171_NodePtr172__tree_next(_NodePtr __x) noexcept173{174 if (__x->__right_ != nullptr)175 return __tree_min(__x->__right_);176 while (!__tree_is_left_child(__x))177 __x = __x->__parent_unsafe();178 return __x->__parent_unsafe();179}180 181template <class _EndNodePtr, class _NodePtr>182inline _LIBCUDACXX_INLINE_VISIBILITY183_EndNodePtr184__tree_next_iter(_NodePtr __x) noexcept185{186 if (__x->__right_ != nullptr)187 return static_cast<_EndNodePtr>(__tree_min(__x->__right_));188 while (!__tree_is_left_child(__x))189 __x = __x->__parent_unsafe();190 return static_cast<_EndNodePtr>(__x->__parent_);191}192 193// Returns: pointer to the previous in-order node before __x.194// Precondition: __x != nullptr.195// Note: __x may be the end node.196template <class _NodePtr, class _EndNodePtr>197inline _LIBCUDACXX_INLINE_VISIBILITY198_NodePtr199__tree_prev_iter(_EndNodePtr __x) noexcept200{201 if (__x->__left_ != nullptr)202 return __tree_max(__x->__left_);203 _NodePtr __xx = static_cast<_NodePtr>(__x);204 while (__tree_is_left_child(__xx))205 __xx = __xx->__parent_unsafe();206 return __xx->__parent_unsafe();207}208 209// Returns: pointer to a node which has no children210// Precondition: __x != nullptr.211template <class _NodePtr>212_NodePtr213__tree_leaf(_NodePtr __x) noexcept214{215 while (true)216 {217 if (__x->__left_ != nullptr)218 {219 __x = __x->__left_;220 continue;221 }222 if (__x->__right_ != nullptr)223 {224 __x = __x->__right_;225 continue;226 }227 break;228 }229 return __x;230}231 232// Effects: Makes __x->__right_ the subtree root with __x as its left child233// while preserving in-order order.234// Precondition: __x->__right_ != nullptr235template <class _NodePtr>236void237__tree_left_rotate(_NodePtr __x) noexcept238{239 _NodePtr __y = __x->__right_;240 __x->__right_ = __y->__left_;241 if (__x->__right_ != nullptr)242 __x->__right_->__set_parent(__x);243 __y->__parent_ = __x->__parent_;244 if (__tree_is_left_child(__x))245 __x->__parent_->__left_ = __y;246 else247 __x->__parent_unsafe()->__right_ = __y;248 __y->__left_ = __x;249 __x->__set_parent(__y);250}251 252// Effects: Makes __x->__left_ the subtree root with __x as its right child253// while preserving in-order order.254// Precondition: __x->__left_ != nullptr255template <class _NodePtr>256void257__tree_right_rotate(_NodePtr __x) noexcept258{259 _NodePtr __y = __x->__left_;260 __x->__left_ = __y->__right_;261 if (__x->__left_ != nullptr)262 __x->__left_->__set_parent(__x);263 __y->__parent_ = __x->__parent_;264 if (__tree_is_left_child(__x))265 __x->__parent_->__left_ = __y;266 else267 __x->__parent_unsafe()->__right_ = __y;268 __y->__right_ = __x;269 __x->__set_parent(__y);270}271 272// Effects: Rebalances __root after attaching __x to a leaf.273// Precondition: __root != nulptr && __x != nullptr.274// __x has no children.275// __x == __root or == a direct or indirect child of __root.276// If __x were to be unlinked from __root (setting __root to277// nullptr if __root == __x), __tree_invariant(__root) == true.278// Postcondition: __tree_invariant(end_node->__left_) == true. end_node->__left_279// may be different than the value passed in as __root.280template <class _NodePtr>281void282__tree_balance_after_insert(_NodePtr __root, _NodePtr __x) noexcept283{284 __x->__is_black_ = __x == __root;285 while (__x != __root && !__x->__parent_unsafe()->__is_black_)286 {287 // __x->__parent_ != __root because __x->__parent_->__is_black == false288 if (__tree_is_left_child(__x->__parent_unsafe()))289 {290 _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_;291 if (__y != nullptr && !__y->__is_black_)292 {293 __x = __x->__parent_unsafe();294 __x->__is_black_ = true;295 __x = __x->__parent_unsafe();296 __x->__is_black_ = __x == __root;297 __y->__is_black_ = true;298 }299 else300 {301 if (!__tree_is_left_child(__x))302 {303 __x = __x->__parent_unsafe();304 __tree_left_rotate(__x);305 }306 __x = __x->__parent_unsafe();307 __x->__is_black_ = true;308 __x = __x->__parent_unsafe();309 __x->__is_black_ = false;310 __tree_right_rotate(__x);311 break;312 }313 }314 else315 {316 _NodePtr __y = __x->__parent_unsafe()->__parent_->__left_;317 if (__y != nullptr && !__y->__is_black_)318 {319 __x = __x->__parent_unsafe();320 __x->__is_black_ = true;321 __x = __x->__parent_unsafe();322 __x->__is_black_ = __x == __root;323 __y->__is_black_ = true;324 }325 else326 {327 if (__tree_is_left_child(__x))328 {329 __x = __x->__parent_unsafe();330 __tree_right_rotate(__x);331 }332 __x = __x->__parent_unsafe();333 __x->__is_black_ = true;334 __x = __x->__parent_unsafe();335 __x->__is_black_ = false;336 __tree_left_rotate(__x);337 break;338 }339 }340 }341}342 343// Precondition: __root != nullptr && __z != nullptr.344// __tree_invariant(__root) == true.345// __z == __root or == a direct or indirect child of __root.346// Effects: unlinks __z from the tree rooted at __root, rebalancing as needed.347// Postcondition: __tree_invariant(end_node->__left_) == true && end_node->__left_348// nor any of its children refer to __z. end_node->__left_349// may be different than the value passed in as __root.350template <class _NodePtr>351void352__tree_remove(_NodePtr __root, _NodePtr __z) noexcept353{354 // __z will be removed from the tree. Client still needs to destruct/deallocate it355 // __y is either __z, or if __z has two children, __tree_next(__z).356 // __y will have at most one child.357 // __y will be the initial hole in the tree (make the hole at a leaf)358 _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ?359 __z : __tree_next(__z);360 // __x is __y's possibly null single child361 _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_;362 // __w is __x's possibly null uncle (will become __x's sibling)363 _NodePtr __w = nullptr;364 // link __x to __y's parent, and find __w365 if (__x != nullptr)366 __x->__parent_ = __y->__parent_;367 if (__tree_is_left_child(__y))368 {369 __y->__parent_->__left_ = __x;370 if (__y != __root)371 __w = __y->__parent_unsafe()->__right_;372 else373 __root = __x; // __w == nullptr374 }375 else376 {377 __y->__parent_unsafe()->__right_ = __x;378 // __y can't be root if it is a right child379 __w = __y->__parent_->__left_;380 }381 bool __removed_black = __y->__is_black_;382 // If we didn't remove __z, do so now by splicing in __y for __z,383 // but copy __z's color. This does not impact __x or __w.384 if (__y != __z)385 {386 // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr387 __y->__parent_ = __z->__parent_;388 if (__tree_is_left_child(__z))389 __y->__parent_->__left_ = __y;390 else391 __y->__parent_unsafe()->__right_ = __y;392 __y->__left_ = __z->__left_;393 __y->__left_->__set_parent(__y);394 __y->__right_ = __z->__right_;395 if (__y->__right_ != nullptr)396 __y->__right_->__set_parent(__y);397 __y->__is_black_ = __z->__is_black_;398 if (__root == __z)399 __root = __y;400 }401 // There is no need to rebalance if we removed a red, or if we removed402 // the last node.403 if (__removed_black && __root != nullptr)404 {405 // Rebalance:406 // __x has an implicit black color (transferred from the removed __y)407 // associated with it, no matter what its color is.408 // If __x is __root (in which case it can't be null), it is supposed409 // to be black anyway, and if it is doubly black, then the double410 // can just be ignored.411 // If __x is red (in which case it can't be null), then it can absorb412 // the implicit black just by setting its color to black.413 // Since __y was black and only had one child (which __x points to), __x414 // is either red with no children, else null, otherwise __y would have415 // different black heights under left and right pointers.416 // if (__x == __root || __x != nullptr && !__x->__is_black_)417 if (__x != nullptr)418 __x->__is_black_ = true;419 else420 {421 // Else __x isn't root, and is "doubly black", even though it may422 // be null. __w can not be null here, else the parent would423 // see a black height >= 2 on the __x side and a black height424 // of 1 on the __w side (__w must be a non-null black or a red425 // with a non-null black child).426 while (true)427 {428 if (!__tree_is_left_child(__w)) // if x is left child429 {430 if (!__w->__is_black_)431 {432 __w->__is_black_ = true;433 __w->__parent_unsafe()->__is_black_ = false;434 __tree_left_rotate(__w->__parent_unsafe());435 // __x is still valid436 // reset __root only if necessary437 if (__root == __w->__left_)438 __root = __w;439 // reset sibling, and it still can't be null440 __w = __w->__left_->__right_;441 }442 // __w->__is_black_ is now true, __w may have null children443 if ((__w->__left_ == nullptr || __w->__left_->__is_black_) &&444 (__w->__right_ == nullptr || __w->__right_->__is_black_))445 {446 __w->__is_black_ = false;447 __x = __w->__parent_unsafe();448 // __x can no longer be null449 if (__x == __root || !__x->__is_black_)450 {451 __x->__is_black_ = true;452 break;453 }454 // reset sibling, and it still can't be null455 __w = __tree_is_left_child(__x) ?456 __x->__parent_unsafe()->__right_ :457 __x->__parent_->__left_;458 // continue;459 }460 else // __w has a red child461 {462 if (__w->__right_ == nullptr || __w->__right_->__is_black_)463 {464 // __w left child is non-null and red465 __w->__left_->__is_black_ = true;466 __w->__is_black_ = false;467 __tree_right_rotate(__w);468 // __w is known not to be root, so root hasn't changed469 // reset sibling, and it still can't be null470 __w = __w->__parent_unsafe();471 }472 // __w has a right red child, left child may be null473 __w->__is_black_ = __w->__parent_unsafe()->__is_black_;474 __w->__parent_unsafe()->__is_black_ = true;475 __w->__right_->__is_black_ = true;476 __tree_left_rotate(__w->__parent_unsafe());477 break;478 }479 }480 else481 {482 if (!__w->__is_black_)483 {484 __w->__is_black_ = true;485 __w->__parent_unsafe()->__is_black_ = false;486 __tree_right_rotate(__w->__parent_unsafe());487 // __x is still valid488 // reset __root only if necessary489 if (__root == __w->__right_)490 __root = __w;491 // reset sibling, and it still can't be null492 __w = __w->__right_->__left_;493 }494 // __w->__is_black_ is now true, __w may have null children495 if ((__w->__left_ == nullptr || __w->__left_->__is_black_) &&496 (__w->__right_ == nullptr || __w->__right_->__is_black_))497 {498 __w->__is_black_ = false;499 __x = __w->__parent_unsafe();500 // __x can no longer be null501 if (!__x->__is_black_ || __x == __root)502 {503 __x->__is_black_ = true;504 break;505 }506 // reset sibling, and it still can't be null507 __w = __tree_is_left_child(__x) ?508 __x->__parent_unsafe()->__right_ :509 __x->__parent_->__left_;510 // continue;511 }512 else // __w has a red child513 {514 if (__w->__left_ == nullptr || __w->__left_->__is_black_)515 {516 // __w right child is non-null and red517 __w->__right_->__is_black_ = true;518 __w->__is_black_ = false;519 __tree_left_rotate(__w);520 // __w is known not to be root, so root hasn't changed521 // reset sibling, and it still can't be null522 __w = __w->__parent_unsafe();523 }524 // __w has a left red child, right child may be null525 __w->__is_black_ = __w->__parent_unsafe()->__is_black_;526 __w->__parent_unsafe()->__is_black_ = true;527 __w->__left_->__is_black_ = true;528 __tree_right_rotate(__w->__parent_unsafe());529 break;530 }531 }532 }533 }534 }535}536 537// node traits538 539 540template <class _Tp>541struct __is_tree_value_type_imp : false_type {};542 543template <class _Key, class _Value>544struct __is_tree_value_type_imp<__value_type<_Key, _Value>> : true_type {};545 546template <class ..._Args>547struct __is_tree_value_type : false_type {};548 549template <class _One>550struct __is_tree_value_type<_One> : __is_tree_value_type_imp<__remove_cvref_t<_One>> {};551 552template <class _Tp>553struct __tree_key_value_types {554 typedef _Tp key_type;555 typedef _Tp __node_value_type;556 typedef _Tp __container_value_type;557 static const bool __is_map = false;558 559 _LIBCUDACXX_INLINE_VISIBILITY560 static key_type const& __get_key(_Tp const& __v) {561 return __v;562 }563 _LIBCUDACXX_INLINE_VISIBILITY564 static __container_value_type const& __get_value(__node_value_type const& __v) {565 return __v;566 }567 _LIBCUDACXX_INLINE_VISIBILITY568 static __container_value_type* __get_ptr(__node_value_type& __n) {569 return _CUDA_VSTD::addressof(__n);570 }571 _LIBCUDACXX_INLINE_VISIBILITY572 static __container_value_type&& __move(__node_value_type& __v) {573 return _CUDA_VSTD::move(__v);574 }575};576 577template <class _Key, class _Tp>578struct __tree_key_value_types<__value_type<_Key, _Tp> > {579 typedef _Key key_type;580 typedef _Tp mapped_type;581 typedef __value_type<_Key, _Tp> __node_value_type;582 typedef pair<const _Key, _Tp> __container_value_type;583 typedef __container_value_type __map_value_type;584 static const bool __is_map = true;585 586 _LIBCUDACXX_INLINE_VISIBILITY587 static key_type const&588 __get_key(__node_value_type const& __t) {589 return __t.__get_value().first;590 }591 592 template <class _Up>593 _LIBCUDACXX_INLINE_VISIBILITY594 static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value,595 key_type const&>::type596 __get_key(_Up& __t) {597 return __t.first;598 }599 600 _LIBCUDACXX_INLINE_VISIBILITY601 static __container_value_type const&602 __get_value(__node_value_type const& __t) {603 return __t.__get_value();604 }605 606 template <class _Up>607 _LIBCUDACXX_INLINE_VISIBILITY608 static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value,609 __container_value_type const&>::type610 __get_value(_Up& __t) {611 return __t;612 }613 614 _LIBCUDACXX_INLINE_VISIBILITY615 static __container_value_type* __get_ptr(__node_value_type& __n) {616 return _CUDA_VSTD::addressof(__n.__get_value());617 }618 619 _LIBCUDACXX_INLINE_VISIBILITY620 static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) {621 return __v.__move();622 }623};624 625template <class _VoidPtr>626struct __tree_node_base_types {627 typedef _VoidPtr __void_pointer;628 629 typedef __tree_node_base<__void_pointer> __node_base_type;630 typedef typename __rebind_pointer<_VoidPtr, __node_base_type>::type631 __node_base_pointer;632 633 typedef __tree_end_node<__node_base_pointer> __end_node_type;634 typedef typename __rebind_pointer<_VoidPtr, __end_node_type>::type635 __end_node_pointer;636#if defined(_LIBCUDACXX_ABI_TREE_REMOVE_NODE_POINTER_UB)637 typedef __end_node_pointer __parent_pointer;638#else639 typedef typename conditional<640 is_pointer<__end_node_pointer>::value,641 __end_node_pointer,642 __node_base_pointer>::type __parent_pointer;643#endif644 645private:646 static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value),647 "_VoidPtr does not point to unqualified void type");648};649 650template <class _Tp, class _AllocPtr, class _KVTypes = __tree_key_value_types<_Tp>,651 bool = _KVTypes::__is_map>652struct __tree_map_pointer_types {};653 654template <class _Tp, class _AllocPtr, class _KVTypes>655struct __tree_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> {656 typedef typename _KVTypes::__map_value_type _Mv;657 typedef typename __rebind_pointer<_AllocPtr, _Mv>::type658 __map_value_type_pointer;659 typedef typename __rebind_pointer<_AllocPtr, const _Mv>::type660 __const_map_value_type_pointer;661};662 663template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>664struct __tree_node_types;665 666template <class _NodePtr, class _Tp, class _VoidPtr>667struct __tree_node_types<_NodePtr, __tree_node<_Tp, _VoidPtr> >668 : public __tree_node_base_types<_VoidPtr>,669 __tree_key_value_types<_Tp>,670 __tree_map_pointer_types<_Tp, _VoidPtr>671{672 typedef __tree_node_base_types<_VoidPtr> __base;673 typedef __tree_key_value_types<_Tp> __key_base;674 typedef __tree_map_pointer_types<_Tp, _VoidPtr> __map_pointer_base;675public:676 677 typedef typename pointer_traits<_NodePtr>::element_type __node_type;678 typedef _NodePtr __node_pointer;679 680 typedef _Tp __node_value_type;681 typedef typename __rebind_pointer<_VoidPtr, __node_value_type>::type682 __node_value_type_pointer;683 typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type684 __const_node_value_type_pointer;685#if defined(_LIBCUDACXX_ABI_TREE_REMOVE_NODE_POINTER_UB)686 typedef typename __base::__end_node_pointer __iter_pointer;687#else688 typedef typename conditional<689 is_pointer<__node_pointer>::value,690 typename __base::__end_node_pointer,691 __node_pointer>::type __iter_pointer;692#endif693private:694 static_assert(!is_const<__node_type>::value,695 "_NodePtr should never be a pointer to const");696 static_assert((is_same<typename __rebind_pointer<_VoidPtr, __node_type>::type,697 _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr.");698};699 700template <class _ValueTp, class _VoidPtr>701struct __make_tree_node_types {702 typedef typename __rebind_pointer<_VoidPtr, __tree_node<_ValueTp, _VoidPtr> >::type703 _NodePtr;704 typedef __tree_node_types<_NodePtr> type;705};706 707// node708 709template <class _Pointer>710class __tree_end_node711{712public:713 typedef _Pointer pointer;714 pointer __left_;715 716 _LIBCUDACXX_INLINE_VISIBILITY717 __tree_end_node() noexcept : __left_() {}718};719 720template <class _VoidPtr>721class __tree_node_base722 : public __tree_node_base_types<_VoidPtr>::__end_node_type723{724 typedef __tree_node_base_types<_VoidPtr> _NodeBaseTypes;725 726public:727 typedef typename _NodeBaseTypes::__node_base_pointer pointer;728 typedef typename _NodeBaseTypes::__parent_pointer __parent_pointer;729 730 pointer __right_;731 __parent_pointer __parent_;732 bool __is_black_;733 734 _LIBCUDACXX_INLINE_VISIBILITY735 pointer __parent_unsafe() const { return static_cast<pointer>(__parent_);}736 737 _LIBCUDACXX_INLINE_VISIBILITY738 void __set_parent(pointer __p) {739 __parent_ = static_cast<__parent_pointer>(__p);740 }741 742private:743 ~__tree_node_base() = delete;744 __tree_node_base(__tree_node_base const&) = delete;745 __tree_node_base& operator=(__tree_node_base const&) = delete;746};747 748template <class _Tp, class _VoidPtr>749class __tree_node750 : public __tree_node_base<_VoidPtr>751{752public:753 typedef _Tp __node_value_type;754 755 __node_value_type __value_;756 757private:758 ~__tree_node() = delete;759 __tree_node(__tree_node const&) = delete;760 __tree_node& operator=(__tree_node const&) = delete;761};762 763 764template <class _Allocator>765class __tree_node_destructor766{767 typedef _Allocator allocator_type;768 typedef allocator_traits<allocator_type> __alloc_traits;769 770public:771 typedef typename __alloc_traits::pointer pointer;772private:773 typedef __tree_node_types<pointer> _NodeTypes;774 allocator_type& __na_;775 776public:777 bool __value_constructed;778 779 __tree_node_destructor(const __tree_node_destructor &) = default;780 __tree_node_destructor& operator=(const __tree_node_destructor&) = delete;781 782 _LIBCUDACXX_INLINE_VISIBILITY783 explicit __tree_node_destructor(allocator_type& __na, bool __val = false) noexcept784 : __na_(__na),785 __value_constructed(__val)786 {}787 788 _LIBCUDACXX_INLINE_VISIBILITY789 void operator()(pointer __p) noexcept790 {791 if (__value_constructed)792 __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));793 if (__p)794 __alloc_traits::deallocate(__na_, __p, 1);795 }796 797 template <class> friend class __map_node_destructor;798};799 800#if _LIBCUDACXX_STD_VER > 14801template <class _NodeType, class _Alloc>802struct __generic_container_node_destructor;803template <class _Tp, class _VoidPtr, class _Alloc>804struct __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc>805 : __tree_node_destructor<_Alloc>806{807 using __tree_node_destructor<_Alloc>::__tree_node_destructor;808};809#endif810 811template <class _Tp, class _NodePtr, class _DiffType>812class _LIBCUDACXX_TEMPLATE_VIS __tree_iterator813{814 typedef __tree_node_types<_NodePtr> _NodeTypes;815 typedef _NodePtr __node_pointer;816 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;817 typedef typename _NodeTypes::__end_node_pointer __end_node_pointer;818 typedef typename _NodeTypes::__iter_pointer __iter_pointer;819 typedef pointer_traits<__node_pointer> __pointer_traits;820 821 __iter_pointer __ptr_;822 823public:824 typedef bidirectional_iterator_tag iterator_category;825 typedef _Tp value_type;826 typedef _DiffType difference_type;827 typedef value_type& reference;828 typedef typename _NodeTypes::__node_value_type_pointer pointer;829 830 _LIBCUDACXX_INLINE_VISIBILITY __tree_iterator() noexcept831#if _LIBCUDACXX_STD_VER > 11832 : __ptr_(nullptr)833#endif834 {}835 836 _LIBCUDACXX_INLINE_VISIBILITY reference operator*() const837 {return __get_np()->__value_;}838 _LIBCUDACXX_INLINE_VISIBILITY pointer operator->() const839 {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);}840 841 _LIBCUDACXX_INLINE_VISIBILITY842 __tree_iterator& operator++() {843 __ptr_ = static_cast<__iter_pointer>(844 __tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));845 return *this;846 }847 _LIBCUDACXX_INLINE_VISIBILITY848 __tree_iterator operator++(int)849 {__tree_iterator __t(*this); ++(*this); return __t;}850 851 _LIBCUDACXX_INLINE_VISIBILITY852 __tree_iterator& operator--() {853 __ptr_ = static_cast<__iter_pointer>(__tree_prev_iter<__node_base_pointer>(854 static_cast<__end_node_pointer>(__ptr_)));855 return *this;856 }857 _LIBCUDACXX_INLINE_VISIBILITY858 __tree_iterator operator--(int)859 {__tree_iterator __t(*this); --(*this); return __t;}860 861 friend _LIBCUDACXX_INLINE_VISIBILITY862 bool operator==(const __tree_iterator& __x, const __tree_iterator& __y)863 {return __x.__ptr_ == __y.__ptr_;}864 friend _LIBCUDACXX_INLINE_VISIBILITY865 bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y)866 {return !(__x == __y);}867 868private:869 _LIBCUDACXX_INLINE_VISIBILITY870 explicit __tree_iterator(__node_pointer __p) noexcept : __ptr_(__p) {}871 _LIBCUDACXX_INLINE_VISIBILITY872 explicit __tree_iterator(__end_node_pointer __p) noexcept : __ptr_(__p) {}873 _LIBCUDACXX_INLINE_VISIBILITY874 __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); }875 template <class, class, class> friend class __tree;876 template <class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS __tree_const_iterator;877 template <class> friend class _LIBCUDACXX_TEMPLATE_VIS __map_iterator;878 template <class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS map;879 template <class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS multimap;880 template <class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS set;881 template <class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS multiset;882};883 884template <class _Tp, class _NodePtr, class _DiffType>885class _LIBCUDACXX_TEMPLATE_VIS __tree_const_iterator886{887 typedef __tree_node_types<_NodePtr> _NodeTypes;888 typedef typename _NodeTypes::__node_pointer __node_pointer;889 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;890 typedef typename _NodeTypes::__end_node_pointer __end_node_pointer;891 typedef typename _NodeTypes::__iter_pointer __iter_pointer;892 typedef pointer_traits<__node_pointer> __pointer_traits;893 894 __iter_pointer __ptr_;895 896public:897 typedef bidirectional_iterator_tag iterator_category;898 typedef _Tp value_type;899 typedef _DiffType difference_type;900 typedef const value_type& reference;901 typedef typename _NodeTypes::__const_node_value_type_pointer pointer;902 903 _LIBCUDACXX_INLINE_VISIBILITY __tree_const_iterator() noexcept904#if _LIBCUDACXX_STD_VER > 11905 : __ptr_(nullptr)906#endif907 {}908 909private:910 typedef __tree_iterator<value_type, __node_pointer, difference_type>911 __non_const_iterator;912public:913 _LIBCUDACXX_INLINE_VISIBILITY914 __tree_const_iterator(__non_const_iterator __p) noexcept915 : __ptr_(__p.__ptr_) {}916 917 _LIBCUDACXX_INLINE_VISIBILITY reference operator*() const918 {return __get_np()->__value_;}919 _LIBCUDACXX_INLINE_VISIBILITY pointer operator->() const920 {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);}921 922 _LIBCUDACXX_INLINE_VISIBILITY923 __tree_const_iterator& operator++() {924 __ptr_ = static_cast<__iter_pointer>(925 __tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));926 return *this;927 }928 929 _LIBCUDACXX_INLINE_VISIBILITY930 __tree_const_iterator operator++(int)931 {__tree_const_iterator __t(*this); ++(*this); return __t;}932 933 _LIBCUDACXX_INLINE_VISIBILITY934 __tree_const_iterator& operator--() {935 __ptr_ = static_cast<__iter_pointer>(__tree_prev_iter<__node_base_pointer>(936 static_cast<__end_node_pointer>(__ptr_)));937 return *this;938 }939 940 _LIBCUDACXX_INLINE_VISIBILITY941 __tree_const_iterator operator--(int)942 {__tree_const_iterator __t(*this); --(*this); return __t;}943 944 friend _LIBCUDACXX_INLINE_VISIBILITY945 bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y)946 {return __x.__ptr_ == __y.__ptr_;}947 friend _LIBCUDACXX_INLINE_VISIBILITY948 bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y)949 {return !(__x == __y);}950 951private:952 _LIBCUDACXX_INLINE_VISIBILITY953 explicit __tree_const_iterator(__node_pointer __p) noexcept954 : __ptr_(__p) {}955 _LIBCUDACXX_INLINE_VISIBILITY956 explicit __tree_const_iterator(__end_node_pointer __p) noexcept957 : __ptr_(__p) {}958 _LIBCUDACXX_INLINE_VISIBILITY959 __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); }960 961 template <class, class, class> friend class __tree;962 template <class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS map;963 template <class, class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS multimap;964 template <class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS set;965 template <class, class, class> friend class _LIBCUDACXX_TEMPLATE_VIS multiset;966 template <class> friend class _LIBCUDACXX_TEMPLATE_VIS __map_const_iterator;967 968};969 970template<class _Tp, class _Compare>971 _LIBCUDACXX_DIAGNOSE_WARNING(!std::__invokable<_Compare const&, _Tp const&, _Tp const&>::value,972 "the specified comparator type does not provide a viable const call operator")973int __diagnose_non_const_comparator();974 975template <class _Tp, class _Compare, class _Allocator>976class __tree977{978public:979 typedef _Tp value_type;980 typedef _Compare value_compare;981 typedef _Allocator allocator_type;982 983private:984 typedef allocator_traits<allocator_type> __alloc_traits;985 typedef typename __make_tree_node_types<value_type,986 typename __alloc_traits::void_pointer>::type987 _NodeTypes;988 typedef typename _NodeTypes::key_type key_type;989public:990 typedef typename _NodeTypes::__node_value_type __node_value_type;991 typedef typename _NodeTypes::__container_value_type __container_value_type;992 993 typedef typename __alloc_traits::pointer pointer;994 typedef typename __alloc_traits::const_pointer const_pointer;995 typedef typename __alloc_traits::size_type size_type;996 typedef typename __alloc_traits::difference_type difference_type;997 998public:999 typedef typename _NodeTypes::__void_pointer __void_pointer;1000 1001 typedef typename _NodeTypes::__node_type __node;1002 typedef typename _NodeTypes::__node_pointer __node_pointer;1003 1004 typedef typename _NodeTypes::__node_base_type __node_base;1005 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;1006 1007 typedef typename _NodeTypes::__end_node_type __end_node_t;1008 typedef typename _NodeTypes::__end_node_pointer __end_node_ptr;1009 1010 typedef typename _NodeTypes::__parent_pointer __parent_pointer;1011 typedef typename _NodeTypes::__iter_pointer __iter_pointer;1012 1013 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;1014 typedef allocator_traits<__node_allocator> __node_traits;1015 1016private:1017 // check for sane allocator pointer rebinding semantics. Rebinding the1018 // allocator for a new pointer type should be exactly the same as rebinding1019 // the pointer using 'pointer_traits'.1020 static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value),1021 "Allocator does not rebind pointers in a sane manner.");1022 typedef typename __rebind_alloc_helper<__node_traits, __node_base>::type1023 __node_base_allocator;1024 typedef allocator_traits<__node_base_allocator> __node_base_traits;1025 static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value),1026 "Allocator does not rebind pointers in a sane manner.");1027 1028private:1029 __iter_pointer __begin_node_;1030 __compressed_pair<__end_node_t, __node_allocator> __pair1_;1031 __compressed_pair<size_type, value_compare> __pair3_;1032 1033public:1034 _LIBCUDACXX_INLINE_VISIBILITY1035 __iter_pointer __end_node() noexcept1036 {1037 return static_cast<__iter_pointer>(1038 pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first())1039 );1040 }1041 _LIBCUDACXX_INLINE_VISIBILITY1042 __iter_pointer __end_node() const noexcept1043 {1044 return static_cast<__iter_pointer>(1045 pointer_traits<__end_node_ptr>::pointer_to(1046 const_cast<__end_node_t&>(__pair1_.first())1047 )1048 );1049 }1050 _LIBCUDACXX_INLINE_VISIBILITY1051 __node_allocator& __node_alloc() noexcept {return __pair1_.second();}1052private:1053 _LIBCUDACXX_INLINE_VISIBILITY1054 const __node_allocator& __node_alloc() const noexcept1055 {return __pair1_.second();}1056 _LIBCUDACXX_INLINE_VISIBILITY1057 __iter_pointer& __begin_node() noexcept {return __begin_node_;}1058 _LIBCUDACXX_INLINE_VISIBILITY1059 const __iter_pointer& __begin_node() const noexcept {return __begin_node_;}1060public:1061 _LIBCUDACXX_INLINE_VISIBILITY1062 allocator_type __alloc() const noexcept1063 {return allocator_type(__node_alloc());}1064private:1065 _LIBCUDACXX_INLINE_VISIBILITY1066 size_type& size() noexcept {return __pair3_.first();}1067public:1068 _LIBCUDACXX_INLINE_VISIBILITY1069 const size_type& size() const noexcept {return __pair3_.first();}1070 _LIBCUDACXX_INLINE_VISIBILITY1071 value_compare& value_comp() noexcept {return __pair3_.second();}1072 _LIBCUDACXX_INLINE_VISIBILITY1073 const value_compare& value_comp() const noexcept1074 {return __pair3_.second();}1075public:1076 1077 _LIBCUDACXX_INLINE_VISIBILITY1078 __node_pointer __root() const noexcept1079 {return static_cast<__node_pointer>(__end_node()->__left_);}1080 1081 __node_base_pointer* __root_ptr() const noexcept {1082 return _CUDA_VSTD::addressof(__end_node()->__left_);1083 }1084 1085 typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator;1086 typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator;1087 1088 explicit __tree(const value_compare& __comp)1089 noexcept(1090 is_nothrow_default_constructible<__node_allocator>::value &&1091 is_nothrow_copy_constructible<value_compare>::value);1092 explicit __tree(const allocator_type& __a);1093 __tree(const value_compare& __comp, const allocator_type& __a);1094 __tree(const __tree& __t);1095 __tree& operator=(const __tree& __t);1096 template <class _ForwardIterator>1097 void __assign_unique(_ForwardIterator __first, _ForwardIterator __last);1098 template <class _InputIterator>1099 void __assign_multi(_InputIterator __first, _InputIterator __last);1100 __tree(__tree&& __t)1101 noexcept(1102 is_nothrow_move_constructible<__node_allocator>::value &&1103 is_nothrow_move_constructible<value_compare>::value);1104 __tree(__tree&& __t, const allocator_type& __a);1105 __tree& operator=(__tree&& __t)1106 noexcept(1107 __node_traits::propagate_on_container_move_assignment::value &&1108 is_nothrow_move_assignable<value_compare>::value &&1109 is_nothrow_move_assignable<__node_allocator>::value);1110 1111 ~__tree();1112 1113 _LIBCUDACXX_INLINE_VISIBILITY1114 iterator begin() noexcept {return iterator(__begin_node());}1115 _LIBCUDACXX_INLINE_VISIBILITY1116 const_iterator begin() const noexcept {return const_iterator(__begin_node());}1117 _LIBCUDACXX_INLINE_VISIBILITY1118 iterator end() noexcept {return iterator(__end_node());}1119 _LIBCUDACXX_INLINE_VISIBILITY1120 const_iterator end() const noexcept {return const_iterator(__end_node());}1121 1122 _LIBCUDACXX_INLINE_VISIBILITY1123 size_type max_size() const noexcept1124 {return std::min<size_type>(1125 __node_traits::max_size(__node_alloc()),1126 numeric_limits<difference_type >::max());}1127 1128 void clear() noexcept;1129 1130 void swap(__tree& __t)1131#if _LIBCUDACXX_STD_VER <= 111132 noexcept(1133 __is_nothrow_swappable<value_compare>::value1134 && (!__node_traits::propagate_on_container_swap::value ||1135 __is_nothrow_swappable<__node_allocator>::value)1136 );1137#else1138 noexcept(__is_nothrow_swappable<value_compare>::value);1139#endif1140 1141 template <class _Key, class ..._Args>1142 pair<iterator, bool>1143 __emplace_unique_key_args(_Key const&, _Args&&... __args);1144 template <class _Key, class ..._Args>1145 iterator1146 __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...);1147 1148 template <class... _Args>1149 pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);1150 1151 template <class... _Args>1152 iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args);1153 1154 template <class... _Args>1155 iterator __emplace_multi(_Args&&... __args);1156 1157 template <class... _Args>1158 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);1159 1160 template <class _Pp>1161 _LIBCUDACXX_INLINE_VISIBILITY1162 pair<iterator, bool> __emplace_unique(_Pp&& __x) {1163 return __emplace_unique_extract_key(_CUDA_VSTD::forward<_Pp>(__x),1164 __can_extract_key<_Pp, key_type>());1165 }1166 1167 template <class _First, class _Second>1168 _LIBCUDACXX_INLINE_VISIBILITY1169 typename enable_if<1170 __can_extract_map_key<_First, key_type, __container_value_type>::value,1171 pair<iterator, bool>1172 >::type __emplace_unique(_First&& __f, _Second&& __s) {1173 return __emplace_unique_key_args(__f, _CUDA_VSTD::forward<_First>(__f),1174 _CUDA_VSTD::forward<_Second>(__s));1175 }1176 1177 template <class... _Args>1178 _LIBCUDACXX_INLINE_VISIBILITY1179 pair<iterator, bool> __emplace_unique(_Args&&... __args) {1180 return __emplace_unique_impl(_CUDA_VSTD::forward<_Args>(__args)...);1181 }1182 1183 template <class _Pp>1184 _LIBCUDACXX_INLINE_VISIBILITY1185 pair<iterator, bool>1186 __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {1187 return __emplace_unique_impl(_CUDA_VSTD::forward<_Pp>(__x));1188 }1189 1190 template <class _Pp>1191 _LIBCUDACXX_INLINE_VISIBILITY1192 pair<iterator, bool>1193 __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {1194 return __emplace_unique_key_args(__x, _CUDA_VSTD::forward<_Pp>(__x));1195 }1196 1197 template <class _Pp>1198 _LIBCUDACXX_INLINE_VISIBILITY1199 pair<iterator, bool>1200 __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {