sudo-73/src/redblack.c

101     tree->nil.left = tree->nil.right = tree->nil.parent = &tree->nil;
109     tree->root.left = tree->root.right = tree->root.parent = &tree->nil;
117  * Perform a left rotation starting at node.
127     node->right = child->left;
129     if (child->left != rbnil(tree))
130         child->left->parent = node;
133     if (node == node->parent->left)
134 	node->parent->left = child;
137     child->left = node;
151     child = node->left;
152     node->left = child->right;
158     if (node == node->parent->left)
159 	node->parent->left = child;
185 	node = res < 0 ? node->left : node->right;
190     node->left = node->right = rbnil(tree);
193 	parent->left = node;
208      *     parent, and the parent in turn is the left child of its parent.
209      *     We do a left rotation to switch the roles of the parent and
212      *  3) The uncle is black and the new node is the left child of its
213      *     parent, and the parent in turn is the left child of its parent.
223 	if (node->parent == node->parent->parent->left) {
240 	    uncle = node->parent->parent->left;
247 		if (node == node->parent->left) {
276 	node = res < 0 ? node->left : node->right;
300 	if ((error = rbapply_node(tree, node->left, func, cookie, order)) != 0)
325 	while (succ->left != rbnil(tree))
326 	    succ = succ->left;
347 	_rbdestroy(tree, node->left, destroy);
378     if (z->left == rbnil(tree) || z->right == rbnil(tree))
382     x = (y->left == rbnil(tree)) ? y->right : y->left;
387 	if (y == y->parent->left)
388 	    y->parent->left = x;
395 	y->left = z->left;
399 	z->left->parent = z->right->parent = y;
400 	if (z == z->parent->left)
401 	    z->parent->left = y;
422 	if (node == node->parent->left) {
430 	    if (sibling->right->color == black && sibling->left->color == black) {
435 		      sibling->left->color = black;
447 	    sibling = node->parent->left;
452 		sibling = node->parent->left;
454 	    if (sibling->right->color == black && sibling->left->color == black) {
458 		if (sibling->left->color == black) {
462 		    sibling = node->parent->left;
466 		sibling->left->color = black;