sudo-73/src/redblack.c

69  * A red-black tree is a binary search tree where each node has a color
72  * the color indicates whether the node is part of a 3-node or a 4-node.
76  *  1) Every node is either red or black.
79  *  4) Both children of each red node are black.
98      * We use a self-referencing sentinel node called nil to simplify the
106      * Similarly, the fake root node keeps us from having to worry
117  * Perform a left rotation starting at node.
120 rotate_left(tree, node)
122     struct rbnode *node;
126     child = node->right;
127     node->right = child->left;
130         child->left->parent = node;
131     child->parent = node->parent;
133     if (node == node->parent->left)
134 	node->parent->left = child;
136 	node->parent->right = child;
137     child->left = node;
138     node->parent = child;
142  * Perform a right rotation starting at node.
145 rotate_right(tree, node)
147     struct rbnode *node;
151     child = node->left;
152     node->left = child->right;
155         child->right->parent = node;
156     child->parent = node->parent;
158     if (node == node->parent->left)
159 	node->parent->left = child;
161 	node->parent->right = child;
162     child->right = node;
163     node->parent = child;
168  * Returns a NULL pointer on success.  If a node matching "data"
169  * already exists, a pointer to the existant node is returned.
176     struct rbnode *node = rbfirst(tree);
181     while (node != rbnil(tree)) {
182 	parent = node;
183 	if ((res = tree->compar(data, node->data)) == 0)
184 	    return node;
185 	node = res < 0 ? node->left : node->right;
188     node = (struct rbnode *) emalloc(sizeof(*node));
189     node->data = data;
190     node->left = node->right = rbnil(tree);
191     node->parent = parent;
193 	parent->left = node;
195 	parent->right = node;
196     node->color = red;
199      * If the parent node is black we are all set, if it is red we have
205      *     and repaint the grandparent node red.
207      *  2) The uncle is black and the new node is the right child of its
212      *  3) The uncle is black and the new node is the left child of its
216      *     parent the parent of the new node and the former grandparent.
218      * Note that because we use a sentinel for the root node we never
221     while (node->parent->color == red) {
223 	if (node->parent == node->parent->parent->left) {
224 	    uncle = node->parent->parent->right;
226 		node->parent->color = black;
228 		node->parent->parent->color = red;
229 		node = node->parent->parent;
231 		if (node == node->parent->right) {
232 		    node = node->parent;
233 		    rotate_left(tree, node);
235 		node->parent->color = black;
236 		node->parent->parent->color = red;
237 		rotate_right(tree, node->parent->parent);
239 	} else { /* if (node->parent == node->parent->parent->right) */
240 	    uncle = node->parent->parent->left;
242 		node->parent->color = black;
244 		node->parent->parent->color = red;
245 		node = node->parent->parent;
247 		if (node == node->parent->left) {
248 		    node = node->parent;
249 		    rotate_right(tree, node);
251 		node->parent->color = black;
252 		node->parent->parent->color = red;
253 		rotate_left(tree, node->parent->parent);
257     rbfirst(tree)->color = black;	/* first node is always black */
262  * Look for a node matching key in tree.
263  * Returns a pointer to the node if found, else NULL.
270     struct rbnode *node = rbfirst(tree);
273     while (node != rbnil(tree)) {
274 	if ((res = tree->compar(key, node->data)) == 0)
275 	    return node;
276 	node = res < 0 ? node->left : node->right;
282  * Call func() for each node, passing it the node data and a cookie;
283  * If func() returns non-zero for a node, the traversal stops and the
287 rbapply_node(tree, node, func, cookie, order)
289     struct rbnode *node;
296     if (node != rbnil(tree)) {
298 	    if ((error = func(node->data, cookie)) != 0)
300 	if ((error = rbapply_node(tree, node->left, func, cookie, order)) != 0)
303 	    if ((error = func(node->data, cookie)) != 0)
305 	if ((error = rbapply_node(tree, node->right, func, cookie, order)) != 0)
308 	    if ((error = func(node->data, cookie)) != 0)
315  * Returns the successor of node, or nil if there is none.
318 rbsuccessor(tree, node)
320     struct rbnode *node;
324     if ((succ = node->right) != rbnil(tree)) {
329 	for (succ = node->parent; node == succ->right; succ = succ->parent)
330 	    node = succ;
341 _rbdestroy(tree, node, destroy)
343     struct rbnode *node;
346     if (node != rbnil(tree)) {
347 	_rbdestroy(tree, node->left, destroy);
348 	_rbdestroy(tree, node->right, destroy);
350 	    destroy(node->data);
351 	efree(node);
357  * for each node and then freeing the tree itself.
369  * Delete node 'z' from the tree and return its data pointer.
411  * Repair the tree after a node has been deleted by rotating and repainting
415 rbrepair(tree, node)
417     struct rbnode *node;
421     while (node->color == black && node != rbfirst(tree)) {
422 	if (node == node->parent->left) {
423 	    sibling = node->parent->right;
426 		node->parent->color = red;
427 		rotate_left(tree, node->parent);
428 		sibling = node->parent->right;
432 		node = node->parent;
438 		      sibling = node->parent->right;
440 		sibling->color = node->parent->color;
441 		node->parent->color = black;
443 		rotate_left(tree, node->parent);
444 		node = rbfirst(tree); /* exit loop */
446 	} else { /* if (node == node->parent->right) */
447 	    sibling = node->parent->left;
450 		node->parent->color = red;
451 		rotate_right(tree, node->parent);
452 		sibling = node->parent->left;
456 		node = node->parent;
462 		    sibling = node->parent->left;
464 		sibling->color = node->parent->color;
465 		node->parent->color = black;
467 		rotate_right(tree, node->parent);
468 		node = rbfirst(tree); /* exit loop */
472     node->color = black;