Lines Matching full:parent
44 node->parent = node->right = node->left = NULL; in rbnode_construct()
122 /* Otherwise, go up the tree until reaching the parent in rbnode_successor()
127 succ_node = node->parent; in rbnode_successor()
130 succ_node = succ_node->parent; in rbnode_successor()
155 /* Otherwise, go up the tree until reaching the parent in rbnode_predecessor()
160 pred_node = node->parent; in rbnode_predecessor()
163 pred_node = pred_node->parent; in rbnode_predecessor()
184 dup_node->right->parent = dup_node; in rbnode_duplicate()
191 dup_node->left->parent = dup_node; in rbnode_duplicate()
326 new_node->parent = cur_node; in rbtree_insert()
338 new_node->parent = cur_node; in rbtree_insert()
362 rb_node *parent; in insert_successor_at() local
388 parent = rbnode_minimum(tree->root); in insert_successor_at()
389 parent->left = new_node; in insert_successor_at()
398 parent = at_node; in insert_successor_at()
399 parent->right = new_node; in insert_successor_at()
401 parent = rbnode_minimum(at_node->right); in insert_successor_at()
402 parent->left = new_node; in insert_successor_at()
406 new_node->parent = parent; in insert_successor_at()
422 rb_node *parent; in insert_predecessor_at() local
448 parent = rbnode_maximum(tree->root); in insert_predecessor_at()
449 parent->right = new_node; in insert_predecessor_at()
458 parent = at_node; in insert_predecessor_at()
459 parent->left = new_node; in insert_predecessor_at()
461 parent = rbnode_maximum(at_node->left); in insert_predecessor_at()
462 parent->right = new_node; in insert_predecessor_at()
466 new_node->parent = parent; in insert_predecessor_at()
517 rb_node *succ_parent = succ_node->parent; in rbtree_remove_at()
522 succ_node->parent = node->parent; in rbtree_remove_at()
527 node->parent = immediate_succ ? succ_node : succ_parent; in rbtree_remove_at()
533 if (succ_node == node->parent->left) in rbtree_remove_at()
534 node->parent->left = node; in rbtree_remove_at()
536 node->parent->right = node; in rbtree_remove_at()
540 node->left->parent = node; in rbtree_remove_at()
542 node->right->parent = node; in rbtree_remove_at()
544 if (succ_node->parent) { in rbtree_remove_at()
545 if (node == succ_node->parent->left) in rbtree_remove_at()
546 succ_node->parent->left = succ_node; in rbtree_remove_at()
548 succ_node->parent->right = succ_node; in rbtree_remove_at()
554 succ_node->left->parent = succ_node; in rbtree_remove_at()
556 succ_node->right->parent = succ_node; in rbtree_remove_at()
564 /* Splice out the node to be removed, by linking its parent in rbtree_remove_at()
568 child->parent = node->parent; in rbtree_remove_at()
570 if (!(node->parent)) { in rbtree_remove_at()
576 /* Link the removed node parent to its child */ in rbtree_remove_at()
577 if (node == node->parent->left) in rbtree_remove_at()
578 node->parent->left = child; in rbtree_remove_at()
580 node->parent->right = child; in rbtree_remove_at()
653 /* Link T2 to its new parent x */ in rbtree_rotate_left()
655 y_node->left->parent = x_node; in rbtree_rotate_left()
657 /* Assign x's parent to be y's parent */ in rbtree_rotate_left()
658 y_node->parent = x_node->parent; in rbtree_rotate_left()
660 if (!(x_node->parent)) { in rbtree_rotate_left()
664 /* Assign a pointer to y from x's parent */ in rbtree_rotate_left()
665 if (x_node == x_node->parent->left) in rbtree_rotate_left()
666 x_node->parent->left = y_node; in rbtree_rotate_left()
668 x_node->parent->right = y_node; in rbtree_rotate_left()
673 x_node->parent = y_node; in rbtree_rotate_left()
686 /* Link T2 to its new parent y */ in rbtree_rotate_right()
688 x_node->right->parent = y_node; in rbtree_rotate_right()
690 /* Assign y's parent to be x's parent */ in rbtree_rotate_right()
691 x_node->parent = y_node->parent; in rbtree_rotate_right()
693 if (!(y_node->parent)) { in rbtree_rotate_right()
697 /* Assign a pointer to x from y's parent */ in rbtree_rotate_right()
698 if (y_node == y_node->parent->left) in rbtree_rotate_right()
699 y_node->parent->left = x_node; in rbtree_rotate_right()
701 y_node->parent->right = x_node; in rbtree_rotate_right()
706 y_node->parent = x_node; in rbtree_rotate_right()
714 * leaf as the child of a red parent - so we have to fix the in rbtree_insert_fixup()
715 * coloring of the parent recursively. in rbtree_insert_fixup()
723 while (curr_node != tree->root && curr_node->parent->color == red) { in rbtree_insert_fixup()
725 * (the root is always black, so the red parent must in rbtree_insert_fixup()
726 * have a parent). in rbtree_insert_fixup()
729 grandparent = curr_node->parent->parent; in rbtree_insert_fixup()
731 if (curr_node->parent == grandparent->left) { in rbtree_insert_fixup()
732 /* If the red parent is a left child, the in rbtree_insert_fixup()
739 /* If both parent and uncle are red, in rbtree_insert_fixup()
744 curr_node->parent->color = black; in rbtree_insert_fixup()
753 * parent's sub-tree so the parent in rbtree_insert_fixup()
757 if (curr_node == curr_node->parent->right) { in rbtree_insert_fixup()
758 curr_node = curr_node->parent; in rbtree_insert_fixup()
762 /* Color the parent black and the in rbtree_insert_fixup()
765 curr_node->parent->color = black; in rbtree_insert_fixup()
774 /* If the red parent is a right child, the in rbtree_insert_fixup()
780 /* If both parent and uncle are red, in rbtree_insert_fixup()
785 curr_node->parent->color = black; in rbtree_insert_fixup()
794 * the parent's sub-tree so the parent in rbtree_insert_fixup()
798 if (curr_node == curr_node->parent->left) { in rbtree_insert_fixup()
799 curr_node = curr_node->parent; in rbtree_insert_fixup()
803 /* Color the parent black and the in rbtree_insert_fixup()
806 curr_node->parent->color = black; in rbtree_insert_fixup()
828 * that the node's parent must exist, since the node in rbtree_remove_fixup()
831 if (curr_node == curr_node->parent->left) { in rbtree_remove_fixup()
833 * sibling is the right child of the parent. in rbtree_remove_fixup()
835 sibling = curr_node->parent->right; in rbtree_remove_fixup()
844 * the parent red (the grandparent is in rbtree_remove_fixup()
848 curr_node->parent->color = red; in rbtree_remove_fixup()
849 rbtree_rotate_left(tree, curr_node->parent); in rbtree_remove_fixup()
850 sibling = curr_node->parent->right; in rbtree_remove_fixup()
861 if (curr_node->parent->color == red) { in rbtree_remove_fixup()
862 /* If the parent is red, we in rbtree_remove_fixup()
867 curr_node->parent->color = black; in rbtree_remove_fixup()
873 * the parent is now too small in rbtree_remove_fixup()
876 curr_node = curr_node->parent; in rbtree_remove_fixup()
883 if (curr_node->parent->color == red) { in rbtree_remove_fixup()
884 curr_node->parent->color = in rbtree_remove_fixup()
890 curr_node = curr_node->parent; in rbtree_remove_fixup()
905 * the current parent. in rbtree_remove_fixup()
910 parent); in rbtree_remove_fixup()
923 curr_node->parent->right; in rbtree_remove_fixup()
929 * parent black and to in rbtree_remove_fixup()
932 if (curr_node->parent->parent) in rbtree_remove_fixup()
933 curr_node->parent->parent-> in rbtree_remove_fixup()
935 curr_node->parent->color; in rbtree_remove_fixup()
936 curr_node->parent->color = black; in rbtree_remove_fixup()
943 * sibling is the left child of the parent. in rbtree_remove_fixup()
945 sibling = curr_node->parent->left; in rbtree_remove_fixup()
954 * the parent red (the grandparent is in rbtree_remove_fixup()
958 curr_node->parent->color = red; in rbtree_remove_fixup()
959 rbtree_rotate_right(tree, curr_node->parent); in rbtree_remove_fixup()
961 sibling = curr_node->parent->left; in rbtree_remove_fixup()
970 if (curr_node->parent->color == red) { in rbtree_remove_fixup()
971 /* If the parent is red, we in rbtree_remove_fixup()
976 curr_node->parent->color = black; in rbtree_remove_fixup()
984 * the parent is now too small in rbtree_remove_fixup()
987 curr_node = curr_node->parent; in rbtree_remove_fixup()
993 if (curr_node->parent->color == red) { in rbtree_remove_fixup()
994 curr_node->parent->color = in rbtree_remove_fixup()
1000 curr_node = curr_node->parent; in rbtree_remove_fixup()
1015 * the current parent in rbtree_remove_fixup()
1020 parent); in rbtree_remove_fixup()
1033 curr_node->parent->left; in rbtree_remove_fixup()
1039 * parent black and to in rbtree_remove_fixup()
1042 if (curr_node->parent->parent) in rbtree_remove_fixup()
1043 curr_node->parent->parent-> in rbtree_remove_fixup()
1045 curr_node->parent->color; in rbtree_remove_fixup()
1046 curr_node->parent->color = black; in rbtree_remove_fixup()