44 	node->parent = node->right = node->left = NULL;  in rbnode_construct()
56 	rbnode_destruct(node->right, d);  in rbnode_destruct()
65 	/* Recursively determine the depth of the left and right  in rbnode_depth()
68 	int irightdepth = (node->right) ? rbnode_depth(node->right) : 0;  in rbnode_depth()
89 	while (node->right)  in rbnode_maximum()
90 		node = node->right;  in rbnode_maximum()
110 	if (node->right) {  in rbnode_successor()
112 		/* If there is a right child, the successor is the  in rbnode_successor()
117 		succ_node = node->right;  in rbnode_successor()
128 		while (succ_node && prev_node == succ_node->right) {  in rbnode_successor()
151 		while (pred_node->right)  in rbnode_predecessor()
152 			pred_node = pred_node->right;  in rbnode_predecessor()
156 		 * from the right direction.  in rbnode_predecessor()
182 	if (node->right) {  in rbnode_duplicate()
183 		dup_node->right = rbnode_duplicate(node->right);  in rbnode_duplicate()
184 		dup_node->right->parent = dup_node;  in rbnode_duplicate()
186 		dup_node->right = NULL;  in rbnode_duplicate()
207 	rbnode_traverse(node->right, op);  in rbnode_traverse()
333 			if (!(cur_node->right)) {  in rbtree_insert()
334 				/* Insert the new leaf as the right  in rbtree_insert()
337 				cur_node->right = new_node;  in rbtree_insert()
341 				/* Go to the right subtree */  in rbtree_insert()
342 				cur_node = cur_node->right;  in rbtree_insert()
392 		 * order In case given node has no right child, place  in insert_successor_at()
393 		 * the new node as its right child. Otherwise, place  in insert_successor_at()
395 		 * at its right side.  in insert_successor_at()
397 		if (!at_node->right) {  in insert_successor_at()
399 			parent->right = new_node;  in insert_successor_at()
401 			parent = rbnode_minimum(at_node->right);  in insert_successor_at()
446 		 * is as the right child of the current maximal leaf  in insert_predecessor_at()
449 		parent->right = new_node;  in insert_predecessor_at()
462 			parent->right = new_node;  in insert_predecessor_at()
502 	if (node->left && node->right) {  in rbtree_remove_at()
505 		 * its right sub-tree and has at most one child (it  in rbtree_remove_at()
506 		 * may have a right child).  in rbtree_remove_at()
508 		rb_node *succ_node = rbnode_minimum(node->right);  in rbtree_remove_at()
516 		int immediate_succ = (node->right == succ_node);  in rbtree_remove_at()
519 		rb_node *succ_right = succ_node->right;  in rbtree_remove_at()
524 		succ_node->right = immediate_succ ? node : node->right;  in rbtree_remove_at()
529 		node->right = succ_right;  in rbtree_remove_at()
536 				node->parent->right = node;  in rbtree_remove_at()
541 		if (node->right)  in rbtree_remove_at()
542 			node->right->parent = node;  in rbtree_remove_at()
548 				succ_node->parent->right = succ_node;  in rbtree_remove_at()
555 		if (succ_node->right)  in rbtree_remove_at()
556 			succ_node->right->parent = succ_node;  in rbtree_remove_at()
562 	child = (node->left) ? node->left : node->right;  in rbtree_remove_at()
580 			node->parent->right = child;  in rbtree_remove_at()
594 	node->right = NULL;  in rbtree_remove_at()
637 		/* Go down to the left or right child. */  in rbtree_find()
638 		cur_node = (comp_result > 0) ? cur_node->left : cur_node->right;  in rbtree_find()
647 	/* Get the right child of the node */  in rbtree_rotate_left()
648 	rb_node *y_node = x_node->right;  in rbtree_rotate_left()
650 	/* Change its left subtree (T2) to x's right subtree */  in rbtree_rotate_left()
651 	x_node->right = y_node->left;  in rbtree_rotate_left()
668 			x_node->parent->right = y_node;  in rbtree_rotate_left()
676 /* Right-rotate the sub-tree spanned by the given node */
683 	/* Change its right subtree (T2) to y's left subtree */  in rbtree_rotate_right()
684 	y_node->left = x_node->right;  in rbtree_rotate_right()
687 	if (x_node->right != NULL)  in rbtree_rotate_right()
688 		x_node->right->parent = y_node;  in rbtree_rotate_right()
701 			y_node->parent->right = x_node;  in rbtree_rotate_right()
704 	/* Assign y to be x's right child */  in rbtree_rotate_right()
705 	x_node->right = y_node;  in rbtree_rotate_right()
733 			 * uncle is the right child of the grandparent.  in rbtree_insert_fixup()
735 			uncle = grandparent->right;  in rbtree_insert_fixup()
752 				 * right child. If not, left-rotate the  in rbtree_insert_fixup()
754 				 * becomes the right child of the  in rbtree_insert_fixup()
757 				if (curr_node == curr_node->parent->right) {  in rbtree_insert_fixup()
768 				/* Right-rotate the grandparent's  in rbtree_insert_fixup()
774 			/* If the red parent is a right child, the  in rbtree_insert_fixup()
793 				 * left child. If not, right-rotate  in rbtree_insert_fixup()
833 			 * sibling is the right child of the parent.  in rbtree_remove_fixup()
835 			sibling = curr_node->parent->right;  in rbtree_remove_fixup()
850 				sibling = curr_node->parent->right;  in rbtree_remove_fixup()
855 			    && (!(sibling->right)  in rbtree_remove_fixup()
856 				|| sibling->right->color == black)) {  in rbtree_remove_fixup()
899 					if (sibling->right  in rbtree_remove_fixup()
900 					    && sibling->right->color == red) {  in rbtree_remove_fixup()
901 						/* If the right child  in rbtree_remove_fixup()
907 						sibling->right->color = black;  in rbtree_remove_fixup()
923 						    curr_node->parent->right;  in rbtree_remove_fixup()
942 			/* If the current node is a right child, its  in rbtree_remove_fixup()
966 			    && (!(sibling->right)  in rbtree_remove_fixup()
967 				|| sibling->right->color == black)) {  in rbtree_remove_fixup()
1022 						/* If the right child  in rbtree_remove_fixup()