111 	node->right = right->left;  in rbtree_rotate_left()
112 	if (right->left != RBTREE_NULL)  in rbtree_rotate_left()
113 		right->left->parent = node;  in rbtree_rotate_left()
118 		if (node == node->parent->left) {  in rbtree_rotate_left()
119 			node->parent->left = right;  in rbtree_rotate_left()
126 	right->left = node;  in rbtree_rotate_left()
137 	rbnode_type *left = node->left;  in rbtree_rotate_right()  local
138 	node->left = left->right;  in rbtree_rotate_right()
139 	if (left->right != RBTREE_NULL)  in rbtree_rotate_right()
140 		left->right->parent = node;  in rbtree_rotate_right()
142 	left->parent = node->parent;  in rbtree_rotate_right()
146 			node->parent->right = left;  in rbtree_rotate_right()
148 			node->parent->left = left;  in rbtree_rotate_right()
151 		rbtree->root = left;  in rbtree_rotate_right()
153 	left->right = node;  in rbtree_rotate_right()
154 	node->parent = left;  in rbtree_rotate_right()
165 		if (node->parent == node->parent->parent->left) {  in rbtree_insert_fixup()
191 			uncle = node->parent->parent->left;  in rbtree_insert_fixup()
206 				if (node == node->parent->left) {  in rbtree_insert_fixup()
247 			node = node->left;  in rbtree_insert()
255 	data->left = data->right = RBTREE_NULL;  in rbtree_insert()
262 			parent->left = data;  in rbtree_insert()
314 	log_assert(parent->left == old || parent->right == old  in change_parent_ptr()
315 		|| parent->left == new || parent->right == new);  in change_parent_ptr()
316 	if(parent->left == old) parent->left = new;  in change_parent_ptr()
337 	if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL)  in rbtree_delete()
341 		while(smright->left != RBTREE_NULL)  in rbtree_delete()
342 			smright = smright->left;  in rbtree_delete()
357 		change_child_ptr(smright->left, smright, to_delete);  in rbtree_delete()
358 		change_child_ptr(smright->left, smright, to_delete);  in rbtree_delete()
361 		change_child_ptr(to_delete->left, to_delete, smright);  in rbtree_delete()
373 		swap_np(&to_delete->left, &smright->left);  in rbtree_delete()
378 	log_assert(to_delete->left == RBTREE_NULL || to_delete->right == RBTREE_NULL);  in rbtree_delete()
380 	if(to_delete->left != RBTREE_NULL) child = to_delete->left;  in rbtree_delete()
400 	to_delete->left = RBTREE_NULL;  in rbtree_delete()
413 	if(child_parent->right == child) sibling = child_parent->left;  in rbtree_delete_fixup()
432 			if(child_parent->right == child) sibling = child_parent->left;  in rbtree_delete_fixup()
438 			&& sibling->left->color == BLACK  in rbtree_delete_fixup()
447 			if(child_parent->right == child) sibling = child_parent->left;  in rbtree_delete_fixup()
455 		&& sibling->left->color == BLACK  in rbtree_delete_fixup()
471 		&& sibling->left->color == BLACK)  in rbtree_delete_fixup()
477 		if(child_parent->right == child) sibling = child_parent->left;  in rbtree_delete_fixup()
480 	else if(child_parent->left == child  in rbtree_delete_fixup()
482 		&& sibling->left->color == RED  in rbtree_delete_fixup()
486 		sibling->left->color = BLACK;  in rbtree_delete_fixup()
489 		if(child_parent->right == child) sibling = child_parent->left;  in rbtree_delete_fixup()
498 		log_assert(sibling->left->color == RED);  in rbtree_delete_fixup()
499 		sibling->left->color = BLACK;  in rbtree_delete_fixup()
534 			node = node->left;  in rbtree_find_less_equal()
553 	for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);  in rbtree_first()
577 		for (node = node->right; node->left != RBTREE_NULL; node = node->left);  in rbtree_next()
594 	if (node->left != RBTREE_NULL) {  in rbtree_previous()
596 		for (node = node->left; node->right != RBTREE_NULL; node = node->right);  in rbtree_previous()
599 		while (parent != RBTREE_NULL && node == parent->left) {  in rbtree_previous()
615 	traverse_post(func, arg, node->left);  in traverse_post()