Lines Matching refs:__w
352 // __w is __x's possibly null uncle (will become __x's sibling)
353 _NodePtr __w = nullptr;
354 // link __x to __y's parent, and find __w
361 __w = __y->__parent_unsafe()->__right_;
363 __root = __x; // __w == nullptr
369 __w = __y->__parent_->__left_;
373 // but copy __z's color. This does not impact __x or __w.
412 // be null. __w can not be null here, else the parent would
414 // of 1 on the __w side (__w must be a non-null black or a red
418 if (!__tree_is_left_child(__w)) // if x is left child
420 if (!__w->__is_black_)
422 __w->__is_black_ = true;
423 __w->__parent_unsafe()->__is_black_ = false;
424 __tree_left_rotate(__w->__parent_unsafe());
427 if (__root == __w->__left_)
428 __root = __w;
430 __w = __w->__left_->__right_;
432 // __w->__is_black_ is now true, __w may have null children
433 if ((__w->__left_ == nullptr || __w->__left_->__is_black_) &&
434 (__w->__right_ == nullptr || __w->__right_->__is_black_))
436 __w->__is_black_ = false;
437 __x = __w->__parent_unsafe();
445 __w = __tree_is_left_child(__x) ?
450 else // __w has a red child
452 if (__w->__right_ == nullptr || __w->__right_->__is_black_)
454 // __w left child is non-null and red
455 __w->__left_->__is_black_ = true;
456 __w->__is_black_ = false;
457 __tree_right_rotate(__w);
458 // __w is known not to be root, so root hasn't changed
460 __w = __w->__parent_unsafe();
462 // __w has a right red child, left child may be null
463 __w->__is_black_ = __w->__parent_unsafe()->__is_black_;
464 __w->__parent_unsafe()->__is_black_ = true;
465 __w->__right_->__is_black_ = true;
466 __tree_left_rotate(__w->__parent_unsafe());
472 if (!__w->__is_black_)
474 __w->__is_black_ = true;
475 __w->__parent_unsafe()->__is_black_ = false;
476 __tree_right_rotate(__w->__parent_unsafe());
479 if (__root == __w->__right_)
480 __root = __w;
482 __w = __w->__right_->__left_;
484 // __w->__is_black_ is now true, __w may have null children
485 if ((__w->__left_ == nullptr || __w->__left_->__is_black_) &&
486 (__w->__right_ == nullptr || __w->__right_->__is_black_))
488 __w->__is_black_ = false;
489 __x = __w->__parent_unsafe();
497 __w = __tree_is_left_child(__x) ?
502 else // __w has a red child
504 if (__w->__left_ == nullptr || __w->__left_->__is_black_)
506 // __w right child is non-null and red
507 __w->__right_->__is_black_ = true;
508 __w->__is_black_ = false;
509 __tree_left_rotate(__w);
510 // __w is known not to be root, so root hasn't changed
512 __w = __w->__parent_unsafe();
514 // __w has a left red child, right child may be null
515 __w->__is_black_ = __w->__parent_unsafe()->__is_black_;
516 __w->__parent_unsafe()->__is_black_ = true;
517 __w->__left_->__is_black_ = true;
518 __tree_right_rotate(__w->__parent_unsafe());