Lines Matching refs:__root
90 algorithms taking a parameter named __root should assume that __root
93 Each algorithm herein assumes that __root->__parent_ points to a non-null
94 structure which has a member __left_ which points back to __root. No other
95 member is read or written to at __root->__parent_.
97 __root->__parent_ will be referred to below (in comments only) as end_node.
98 end_node->__left_ is an externably accessible lvalue for __root, and can be
102 __root, have a non-null __parent_ field.
145 // Determines if the red black tree rooted at __root is a proper red black tree.
146 // __root == nullptr is a proper tree. Returns true is __root is a proper
149 _LIBCPP_HIDE_FROM_ABI bool __tree_invariant(_NodePtr __root) {
150 if (__root == nullptr)
153 if (__root->__parent_ == nullptr)
155 if (!std::__tree_is_left_child(__root))
158 if (!__root->__is_black_)
161 return std::__tree_sub_invariant(__root) != 0;
272 // Effects: Rebalances __root after attaching __x to a leaf.
274 // __x == __root or == a direct or indirect child of __root.
275 // If __x were to be unlinked from __root (setting __root to
276 // nullptr if __root == __x), __tree_invariant(__root) == true.
278 // may be different than the value passed in as __root.
280 _LIBCPP_HIDE_FROM_ABI void __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT {
281 _LIBCPP_ASSERT_INTERNAL(__root != nullptr, "Root of the tree shouldn't be null");
283 __x->__is_black_ = __x == __root;
284 while (__x != __root && !__x->__parent_unsafe()->__is_black_) {
285 // __x->__parent_ != __root because __x->__parent_->__is_black == false
292 __x->__is_black_ = __x == __root;
312 __x->__is_black_ = __x == __root;
330 // Precondition: __z == __root or == a direct or indirect child of __root.
331 // Effects: unlinks __z from the tree rooted at __root, rebalancing as needed.
334 // may be different than the value passed in as __root.
336 _LIBCPP_HIDE_FROM_ABI void __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT {
337 _LIBCPP_ASSERT_INTERNAL(__root != nullptr, "Root node should not be null");
339 _LIBCPP_ASSERT_INTERNAL(std::__tree_invariant(__root), "The tree invariants should hold");
354 if (__y != __root)
357 __root = __x; // __w == nullptr
379 if (__root == __z)
380 __root = __y;
384 if (__removed_black && __root != nullptr) {
388 // If __x is __root (in which case it can't be null), it is supposed
396 // if (__x == __root || __x != nullptr && !__x->__is_black_)
413 // reset __root only if necessary
414 if (__root == __w->__left_)
415 __root = __w;
425 if (__x == __root || !__x->__is_black_) {
456 // reset __root only if necessary
457 if (__root == __w->__right_)
458 __root = __w;
468 if (!__x->__is_black_ || __x == __root) {
965 _LIBCPP_HIDE_FROM_ABI __node_pointer __root() const _NOEXCEPT {
1192 return __lower_bound(__v, __root(), __end_node());
1195 …_LIBCPP_HIDE_FROM_ABI iterator __lower_bound(const _Key& __v, __node_pointer __root, __iter_pointe…
1198 return __lower_bound(__v, __root(), __end_node());
1202 __lower_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) const;
1205 return __upper_bound(__v, __root(), __end_node());
1208 …_LIBCPP_HIDE_FROM_ABI iterator __upper_bound(const _Key& __v, __node_pointer __root, __iter_pointe…
1211 return __upper_bound(__v, __root(), __end_node());
1215 __upper_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) const;
1532 destroy(__root());
1572 destroy(__root());
1584 __node_pointer __nd = __root();
1614 __node_pointer __nd = __root();
1676 __node_pointer __nd = __root();
2081 iterator __p = __lower_bound(__v, __root(), __end_node());
2091 const_iterator __p = __lower_bound(__v, __root(), __end_node());
2101 __node_pointer __rt = __root();
2118 __node_pointer __rt = __root();
2136 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, __node_pointer __root, __iter_poi…
2137 while (__root != nullptr) {
2138 if (!value_comp()(__root->__value_, __v)) {
2139 __result = static_cast<__iter_pointer>(__root);
2140 __root = static_cast<__node_pointer>(__root->__left_);
2142 __root = static_cast<__node_pointer>(__root->__right_);
2150 const _Key& __v, __node_pointer __root, __iter_pointer __result) const {
2151 while (__root != nullptr) {
2152 if (!value_comp()(__root->__value_, __v)) {
2153 __result = static_cast<__iter_pointer>(__root);
2154 __root = static_cast<__node_pointer>(__root->__left_);
2156 __root = static_cast<__node_pointer>(__root->__right_);
2164 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, __node_pointer __root, __iter_poi…
2165 while (__root != nullptr) {
2166 if (value_comp()(__v, __root->__value_)) {
2167 __result = static_cast<__iter_pointer>(__root);
2168 __root = static_cast<__node_pointer>(__root->__left_);
2170 __root = static_cast<__node_pointer>(__root->__right_);
2178 const _Key& __v, __node_pointer __root, __iter_pointer __result) const {
2179 while (__root != nullptr) {
2180 if (value_comp()(__v, __root->__value_)) {
2181 __result = static_cast<__iter_pointer>(__root);
2182 __root = static_cast<__node_pointer>(__root->__left_);
2184 __root = static_cast<__node_pointer>(__root->__right_);
2195 __node_pointer __rt = __root();
2217 __node_pointer __rt = __root();
2239 __node_pointer __rt = __root();
2260 __node_pointer __rt = __root();