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_() {}
891 {return static_cast<__node_pointer> (__end_node()->__left_);}
894 {return static_cast<__node_const_pointer>(__end_node()->__left_);}
1175 __end_node()->__left_->__parent_ = nullptr;
1176 __end_node()->__left_ = nullptr;
1178 // __cache->__left_ == nullptr
1181 // __cache->__left_ == nullptr
1198 __cache->__parent_->__left_ = nullptr;
1207 if (__cache->__left_ == nullptr)
1209 return static_cast<__node_pointer>(__tree_leaf(__cache->__left_));
1329 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1331 __t.__end_node()->__left_ = nullptr;
1348 __end_node()->__left_ = __t.__end_node()->__left_;
1349 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1352 __t.__end_node()->__left_ = nullptr;
1368 destroy(static_cast<__node_pointer>(__end_node()->__left_));
1377 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1379 __t.__end_node()->__left_ = nullptr;
1458 destroy(static_cast<__node_pointer>(__nd->__left_));
1482 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1486 __t.__end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__t.__end_node());
1496 __end_node()->__left_ = nullptr;
1524 if (__nd->__left_ != nullptr)
1525 __nd = static_cast<__node_pointer>(__nd->__left_);
1529 return __parent->__left_;
1535 return __parent->__left_;
1553 if (__nd->__left_ != nullptr)
1554 __nd = static_cast<__node_pointer>(__nd->__left_);
1558 return __parent->__left_;
1574 return __parent->__left_;
1596 if (__hint.__ptr_->__left_ == nullptr)
1599 return __parent->__left_;
1631 if (__nd->__left_ != nullptr)
1632 __nd = static_cast<__node_pointer>(__nd->__left_);
1636 return __parent->__left_;
1657 return __parent->__left_;
1681 if (__hint.__ptr_->__left_ == nullptr)
1684 return __parent->__left_;
1710 return __parent->__left_;
1727 __new_node->__left_ = nullptr;
1731 if (__begin_node()->__left_ != nullptr)
1732 __begin_node() = static_cast<__node_pointer>(__begin_node()->__left_);
1733 __tree_balance_after_insert(__end_node()->__left_, __child);
1999 __tree_remove(__end_node()->__left_,
2073 __rt = static_cast<__node_const_pointer>(__rt->__left_);
2096 __rt = static_cast<__node_const_pointer>(__rt->__left_);
2102 __lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt),
2121 __root = static_cast<__node_pointer>(__root->__left_);
2141 __root = static_cast<__node_const_pointer>(__root->__left_);
2161 __root = static_cast<__node_pointer>(__root->__left_);
2181 __root = static_cast<__node_const_pointer>(__root->__left_);
2203 __rt = static_cast<__node_pointer>(__rt->__left_);
2231 __rt = static_cast<__node_const_pointer>(__rt->__left_);
2259 __rt = static_cast<__node_pointer>(__rt->__left_);
2264 return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt),
2284 __rt = static_cast<__node_const_pointer>(__rt->__left_);
2289 return _Pp(__lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt),
2308 __tree_remove(__end_node()->__left_,