Lines Matching refs:__left_
49 structure which has a member __left_ which points back to __root. No other
53 end_node->__left_ is an externably accessible lvalue for __root, and can be
68 return __x == __x->__parent_->__left_;
81 // check __x->__left_ consistency
82 if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x)
87 // check __x->__left_ != __x->__right_ unless both are nullptr
88 if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr)
93 if (__x->__left_ && !__x->__left_->__is_black_)
98 unsigned __h = __tree_sub_invariant(__x->__left_);
134 while (__x->__left_ != nullptr)
135 __x = __x->__left_;
170 if (__x->__left_ != nullptr)
171 return __tree_max(__x->__left_);
185 if (__x->__left_ != nullptr)
187 __x = __x->__left_;
208 __x->__right_ = __y->__left_;
213 __x->__parent_->__left_ = __y;
216 __y->__left_ = __x;
220 // Effects: Makes __x->__left_ the subtree root with __x as its right child
222 // Precondition: __x->__left_ != nullptr
227 _NodePtr __y = __x->__left_;
228 __x->__left_ = __y->__right_;
229 if (__x->__left_ != nullptr)
230 __x->__left_->__parent_ = __x;
233 __x->__parent_->__left_ = __y;
246 // Postcondition: __tree_invariant(end_node->__left_) == true. end_node->__left_
284 _NodePtr __y = __x->__parent_->__parent_->__left_;
315 // Postcondition: __tree_invariant(end_node->__left_) == true && end_node->__left_
316 // nor any of its children refer to __z. end_node->__left_
326 _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ?
329 _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_;
337 __y->__parent_->__left_ = __x;
347 __w = __y->__parent_->__left_;
354 // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr
357 __y->__parent_->__left_ = __y;
360 __y->__left_ = __z->__left_;
361 __y->__left_->__parent_ = __y;
405 if (__root == __w->__left_)
408 __w = __w->__left_->__right_;
411 if ((__w->__left_ == nullptr || __w->__left_->__is_black_) &&
425 __x->__parent_->__left_;
433 __w->__left_->__is_black_ = true;
460 __w = __w->__right_->__left_;
463 if ((__w->__left_ == nullptr || __w->__left_->__is_black_) &&
477 __x->__parent_->__left_;
482 if (__w->__left_ == nullptr || __w->__left_->__is_black_)
495 __w->__left_->__is_black_ = true;
549 pointer __left_;
552 __tree_end_node() _NOEXCEPT : __left_() {}
885 {return static_cast<__node_pointer> (__end_node()->__left_);}
888 {return static_cast<__node_const_pointer>(__end_node()->__left_);}
1153 __end_node()->__left_->__parent_ = nullptr;
1154 __end_node()->__left_ = nullptr;
1156 // __cache->__left_ == nullptr
1159 // __cache->__left_ == nullptr
1176 __cache->__parent_->__left_ = nullptr;
1185 if (__cache->__left_ == nullptr)
1187 return static_cast<__node_pointer>(__tree_leaf(__cache->__left_));
1307 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1309 __t.__end_node()->__left_ = nullptr;
1326 __end_node()->__left_ = __t.__end_node()->__left_;
1327 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1330 __t.__end_node()->__left_ = nullptr;
1346 destroy(static_cast<__node_pointer>(__end_node()->__left_));
1355 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1357 __t.__end_node()->__left_ = nullptr;
1436 destroy(static_cast<__node_pointer>(__nd->__left_));
1463 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1467 __t.__end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__t.__end_node());
1477 __end_node()->__left_ = nullptr;
1505 if (__nd->__left_ != nullptr)
1506 __nd = static_cast<__node_pointer>(__nd->__left_);
1510 return __parent->__left_;
1516 return __parent->__left_;
1534 if (__nd->__left_ != nullptr)
1535 __nd = static_cast<__node_pointer>(__nd->__left_);
1539 return __parent->__left_;
1555 return __parent->__left_;
1577 if (__hint.__ptr_->__left_ == nullptr)
1580 return __parent->__left_;
1612 if (__nd->__left_ != nullptr)
1613 __nd = static_cast<__node_pointer>(__nd->__left_);
1617 return __parent->__left_;
1638 return __parent->__left_;
1662 if (__hint.__ptr_->__left_ == nullptr)
1665 return __parent->__left_;
1691 return __parent->__left_;
1708 __new_node->__left_ = nullptr;
1712 if (__begin_node()->__left_ != nullptr)
1713 __begin_node() = static_cast<__node_pointer>(__begin_node()->__left_);
1714 __tree_balance_after_insert(__end_node()->__left_, __child);
1980 __tree_remove(__end_node()->__left_,
2054 __rt = static_cast<__node_const_pointer>(__rt->__left_);
2076 __rt = static_cast<__node_const_pointer>(__rt->__left_);
2082 __lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt),
2101 __root = static_cast<__node_pointer>(__root->__left_);
2121 __root = static_cast<__node_const_pointer>(__root->__left_);
2141 __root = static_cast<__node_pointer>(__root->__left_);
2161 __root = static_cast<__node_const_pointer>(__root->__left_);
2183 __rt = static_cast<__node_pointer>(__rt->__left_);
2211 __rt = static_cast<__node_const_pointer>(__rt->__left_);
2239 __rt = static_cast<__node_pointer>(__rt->__left_);
2244 return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt),
2264 __rt = static_cast<__node_const_pointer>(__rt->__left_);
2269 return _Pp(__lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt),
2288 __tree_remove(__end_node()->__left_,