Lines Matching refs:__root
64 algorithms taking a parameter named __root should assume that __root
67 Each algorithm herein assumes that __root->__parent_ points to a non-null
68 structure which has a member __left_ which points back to __root. No other
69 member is read or written to at __root->__parent_.
71 __root->__parent_ will be referred to below (in comments only) as end_node.
72 end_node->__left_ is an externably accessible lvalue for __root, and can be
76 __root, have a non-null __parent_ field.
125 // Determines if the red black tree rooted at __root is a proper red black tree.
126 // __root == nullptr is a proper tree. Returns true is __root is a proper
130 __tree_invariant(_NodePtr __root)
132 if (__root == nullptr)
135 if (__root->__parent_ == nullptr)
137 if (!_VSTD::__tree_is_left_child(__root))
140 if (!__root->__is_black_)
143 return _VSTD::__tree_sub_invariant(__root) != 0;
277 // Effects: Rebalances __root after attaching __x to a leaf.
279 // __x == __root or == a direct or indirect child of __root.
280 // If __x were to be unlinked from __root (setting __root to
281 // nullptr if __root == __x), __tree_invariant(__root) == true.
283 // may be different than the value passed in as __root.
286 __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT
288 _LIBCPP_ASSERT(__root != nullptr, "Root of the tree shouldn't be null");
290 __x->__is_black_ = __x == __root;
291 while (__x != __root && !__x->__parent_unsafe()->__is_black_)
293 // __x->__parent_ != __root because __x->__parent_->__is_black == false
302 __x->__is_black_ = __x == __root;
328 __x->__is_black_ = __x == __root;
349 // Precondition: __z == __root or == a direct or indirect child of __root.
350 // Effects: unlinks __z from the tree rooted at __root, rebalancing as needed.
353 // may be different than the value passed in as __root.
356 __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT
358 _LIBCPP_ASSERT(__root != nullptr, "Root node should not be null");
360 _LIBCPP_DEBUG_ASSERT(__tree_invariant(__root), "The tree invariants should hold");
377 if (__y != __root)
380 __root = __x; // __w == nullptr
405 if (__root == __z)
406 __root = __y;
410 if (__removed_black && __root != nullptr)
415 // If __x is __root (in which case it can't be null), it is supposed
423 // if (__x == __root || __x != nullptr && !__x->__is_black_)
443 // reset __root only if necessary
444 if (__root == __w->__left_)
445 __root = __w;
456 if (__x == __root || !__x->__is_black_)
495 // reset __root only if necessary
496 if (__root == __w->__right_)
497 __root = __w;
508 if (!__x->__is_black_ || __x == __root)
1087 __node_pointer __root() const _NOEXCEPT
1375 {return __lower_bound(__v, __root(), __end_node());}
1378 __node_pointer __root,
1383 {return __lower_bound(__v, __root(), __end_node());}
1386 __node_pointer __root,
1391 {return __upper_bound(__v, __root(), __end_node());}
1394 __node_pointer __root,
1399 {return __upper_bound(__v, __root(), __end_node());}
1402 __node_pointer __root,
1788 destroy(__root());
1837 destroy(__root());
1851 __node_pointer __nd = __root();
1890 __node_pointer __nd = __root();
1968 __node_pointer __nd = __root();
2465 iterator __p = __lower_bound(__v, __root(), __end_node());
2476 const_iterator __p = __lower_bound(__v, __root(), __end_node());
2487 __node_pointer __rt = __root();
2508 __node_pointer __rt = __root();
2531 __node_pointer __root,
2534 while (__root != nullptr)
2536 if (!value_comp()(__root->__value_, __v))
2538 __result = static_cast<__iter_pointer>(__root);
2539 __root = static_cast<__node_pointer>(__root->__left_);
2542 __root = static_cast<__node_pointer>(__root->__right_);
2551 __node_pointer __root,
2554 while (__root != nullptr)
2556 if (!value_comp()(__root->__value_, __v))
2558 __result = static_cast<__iter_pointer>(__root);
2559 __root = static_cast<__node_pointer>(__root->__left_);
2562 __root = static_cast<__node_pointer>(__root->__right_);
2571 __node_pointer __root,
2574 while (__root != nullptr)
2576 if (value_comp()(__v, __root->__value_))
2578 __result = static_cast<__iter_pointer>(__root);
2579 __root = static_cast<__node_pointer>(__root->__left_);
2582 __root = static_cast<__node_pointer>(__root->__right_);
2591 __node_pointer __root,
2594 while (__root != nullptr)
2596 if (value_comp()(__v, __root->__value_))
2598 __result = static_cast<__iter_pointer>(__root);
2599 __root = static_cast<__node_pointer>(__root->__left_);
2602 __root = static_cast<__node_pointer>(__root->__right_);
2615 __node_pointer __rt = __root();
2643 __node_pointer __rt = __root();
2671 __node_pointer __rt = __root();
2696 __node_pointer __rt = __root();