Lines Matching refs:__root
82 algorithms taking a parameter named __root should assume that __root
85 Each algorithm herein assumes that __root->__parent_ points to a non-null
86 structure which has a member __left_ which points back to __root. No other
87 member is read or written to at __root->__parent_.
89 __root->__parent_ will be referred to below (in comments only) as end_node.
90 end_node->__left_ is an externably accessible lvalue for __root, and can be
94 __root, have a non-null __parent_ field.
143 // Determines if the red black tree rooted at __root is a proper red black tree.
144 // __root == nullptr is a proper tree. Returns true is __root is a proper
148 __tree_invariant(_NodePtr __root)
150 if (__root == nullptr)
153 if (__root->__parent_ == nullptr)
155 if (!_VSTD::__tree_is_left_child(__root))
158 if (!__root->__is_black_)
161 return _VSTD::__tree_sub_invariant(__root) != 0;
295 // Effects: Rebalances __root after attaching __x to a leaf.
297 // __x == __root or == a direct or indirect child of __root.
298 // If __x were to be unlinked from __root (setting __root to
299 // nullptr if __root == __x), __tree_invariant(__root) == true.
301 // may be different than the value passed in as __root.
304 __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT
306 _LIBCPP_ASSERT(__root != nullptr, "Root of the tree shouldn't be null");
308 __x->__is_black_ = __x == __root;
309 while (__x != __root && !__x->__parent_unsafe()->__is_black_)
311 // __x->__parent_ != __root because __x->__parent_->__is_black == false
320 __x->__is_black_ = __x == __root;
346 __x->__is_black_ = __x == __root;
367 // Precondition: __z == __root or == a direct or indirect child of __root.
368 // Effects: unlinks __z from the tree rooted at __root, rebalancing as needed.
371 // may be different than the value passed in as __root.
374 __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT
376 _LIBCPP_ASSERT(__root != nullptr, "Root node should not be null");
378 _LIBCPP_DEBUG_ASSERT(__tree_invariant(__root), "The tree invariants should hold");
395 if (__y != __root)
398 __root = __x; // __w == nullptr
423 if (__root == __z)
424 __root = __y;
428 if (__removed_black && __root != nullptr)
433 // If __x is __root (in which case it can't be null), it is supposed
441 // if (__x == __root || __x != nullptr && !__x->__is_black_)
461 // reset __root only if necessary
462 if (__root == __w->__left_)
463 __root = __w;
474 if (__x == __root || !__x->__is_black_)
513 // reset __root only if necessary
514 if (__root == __w->__right_)
515 __root = __w;
526 if (!__x->__is_black_ || __x == __root)
1100 __node_pointer __root() const _NOEXCEPT
1388 {return __lower_bound(__v, __root(), __end_node());}
1391 __node_pointer __root,
1396 {return __lower_bound(__v, __root(), __end_node());}
1399 __node_pointer __root,
1404 {return __upper_bound(__v, __root(), __end_node());}
1407 __node_pointer __root,
1412 {return __upper_bound(__v, __root(), __end_node());}
1415 __node_pointer __root,
1801 destroy(__root());
1850 destroy(__root());
1864 __node_pointer __nd = __root();
1903 __node_pointer __nd = __root();
1981 __node_pointer __nd = __root();
2478 iterator __p = __lower_bound(__v, __root(), __end_node());
2489 const_iterator __p = __lower_bound(__v, __root(), __end_node());
2500 __node_pointer __rt = __root();
2521 __node_pointer __rt = __root();
2544 __node_pointer __root,
2547 while (__root != nullptr)
2549 if (!value_comp()(__root->__value_, __v))
2551 __result = static_cast<__iter_pointer>(__root);
2552 __root = static_cast<__node_pointer>(__root->__left_);
2555 __root = static_cast<__node_pointer>(__root->__right_);
2564 __node_pointer __root,
2567 while (__root != nullptr)
2569 if (!value_comp()(__root->__value_, __v))
2571 __result = static_cast<__iter_pointer>(__root);
2572 __root = static_cast<__node_pointer>(__root->__left_);
2575 __root = static_cast<__node_pointer>(__root->__right_);
2584 __node_pointer __root,
2587 while (__root != nullptr)
2589 if (value_comp()(__v, __root->__value_))
2591 __result = static_cast<__iter_pointer>(__root);
2592 __root = static_cast<__node_pointer>(__root->__left_);
2595 __root = static_cast<__node_pointer>(__root->__right_);
2604 __node_pointer __root,
2607 while (__root != nullptr)
2609 if (value_comp()(__v, __root->__value_))
2611 __result = static_cast<__iter_pointer>(__root);
2612 __root = static_cast<__node_pointer>(__root->__left_);
2615 __root = static_cast<__node_pointer>(__root->__right_);
2628 __node_pointer __rt = __root();
2656 __node_pointer __rt = __root();
2684 __node_pointer __rt = __root();
2709 __node_pointer __rt = __root();