Lines Matching refs:__parent_

48 Each algorithm herein assumes that __root->__parent_ points to a non-null
50 member is read or written to at __root->__parent_.
52 __root->__parent_ will be referred to below (in comments only) as end_node.
57 __root, have a non-null __parent_ field.
68     return __x == __x->__parent_->__left_;
82     if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x)
85     if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x)
115     // check __x->__parent_ consistency
116     if (__root->__parent_ == nullptr)
160         __x = __x->__parent_;
161     return __x->__parent_;
173         __x = __x->__parent_;
174     return __x->__parent_;
210         __x->__right_->__parent_ = __x;
211     __y->__parent_ = __x->__parent_;
213         __x->__parent_->__left_ = __y;
215         __x->__parent_->__right_ = __y;
217     __x->__parent_ = __y;
230         __x->__left_->__parent_ = __x;
231     __y->__parent_ = __x->__parent_;
233         __x->__parent_->__left_ = __y;
235         __x->__parent_->__right_ = __y;
237     __x->__parent_ = __y;
253     while (__x != __root && !__x->__parent_->__is_black_)
255         // __x->__parent_ != __root because __x->__parent_->__is_black == false
256         if (__tree_is_left_child(__x->__parent_))
258             _NodePtr __y = __x->__parent_->__parent_->__right_;
261                 __x = __x->__parent_;
263                 __x = __x->__parent_;
271                     __x = __x->__parent_;
274                 __x = __x->__parent_;
276                 __x = __x->__parent_;
284             _NodePtr __y = __x->__parent_->__parent_->__left_;
287                 __x = __x->__parent_;
289                 __x = __x->__parent_;
297                     __x = __x->__parent_;
300                 __x = __x->__parent_;
302                 __x = __x->__parent_;
334         __x->__parent_ = __y->__parent_;
337         __y->__parent_->__left_ = __x;
339             __w = __y->__parent_->__right_;
345         __y->__parent_->__right_ = __x;
347         __w = __y->__parent_->__left_;
355         __y->__parent_ = __z->__parent_;
357             __y->__parent_->__left_ = __y;
359             __y->__parent_->__right_ = __y;
361         __y->__left_->__parent_ = __y;
364             __y->__right_->__parent_ = __y;
401                         __w->__parent_->__is_black_ = false;
402                         __tree_left_rotate(__w->__parent_);
415                         __x = __w->__parent_;
424                                     __x->__parent_->__right_ :
425                                     __x->__parent_->__left_;
438                             __w = __w->__parent_;
441                         __w->__is_black_ = __w->__parent_->__is_black_;
442                         __w->__parent_->__is_black_ = true;
444                         __tree_left_rotate(__w->__parent_);
453                         __w->__parent_->__is_black_ = false;
454                         __tree_right_rotate(__w->__parent_);
467                         __x = __w->__parent_;
476                                     __x->__parent_->__right_ :
477                                     __x->__parent_->__left_;
490                             __w = __w->__parent_;
493                         __w->__is_black_ = __w->__parent_->__is_black_;
494                         __w->__parent_->__is_black_ = true;
496                         __tree_right_rotate(__w->__parent_);
587     pointer __parent_;
592         : __right_(), __parent_(), __is_black_(false) {}
1175     __end_node()->__left_->__parent_ = nullptr;
1194     if (__cache->__parent_ == nullptr)
1198         __cache->__parent_->__left_ = nullptr;
1199         __cache = static_cast<__node_pointer>(__cache->__parent_);
1205     __cache->__parent_->__right_ = nullptr;
1206     __cache = static_cast<__node_pointer>(__cache->__parent_);
1248             while (__cache->__parent_ != nullptr)
1249                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1256             while (__cache->__parent_ != nullptr)
1257                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1288             while (__cache->__parent_ != nullptr)
1289                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1296             while (__cache->__parent_ != nullptr)
1297                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1329         __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1349             __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1377         __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1412                 while (__cache->__parent_ != nullptr)
1413                     __cache = static_cast<__node_pointer>(__cache->__parent_);
1420                 while (__cache->__parent_ != nullptr)
1421                     __cache = static_cast<__node_pointer>(__cache->__parent_);
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());
1729     __new_node->__parent_ = __parent;
2305             __begin_node() = static_cast<__node_pointer>(__np->__parent_);