+++ /dev/null
-/*
- * Copyright (c) 2004-2005, 2007,2009 Todd C. Miller <Todd.Miller@courtesan.com>
- *
- * Permission to use, copy, modify, and distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
- *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
- */
-
-/*
- * Adapted from the following code written by Emin Martinian:
- * http://web.mit.edu/~emin/www/source_code/red_black_tree/index.html
- *
- * Copyright (c) 2001 Emin Martinian
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that neither the name of Emin
- * Martinian nor the names of any contributors are be used to endorse or
- * promote products derived from this software without specific prior
- * written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
- * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#include <config.h>
-
-#include <sys/types.h>
-#include <sys/param.h>
-
-#include <stdio.h>
-#ifdef STDC_HEADERS
-# include <stdlib.h>
-# include <stddef.h>
-#else
-# ifdef HAVE_STDLIB_H
-# include <stdlib.h>
-# endif
-#endif /* STDC_HEADERS */
-
-#include "sudo.h"
-#include "redblack.h"
-
-static void rbrepair __P((struct rbtree *, struct rbnode *));
-static void rotate_left __P((struct rbtree *, struct rbnode *));
-static void rotate_right __P((struct rbtree *, struct rbnode *));
-static void _rbdestroy __P((struct rbtree *, struct rbnode *,
- void (*)(void *)));
-
-/*
- * Red-Black tree, see http://en.wikipedia.org/wiki/Red-black_tree
- *
- * A red-black tree is a binary search tree where each node has a color
- * attribute, the value of which is either red or black. Essentially, it
- * is just a convenient way to express a 2-3-4 binary search tree where
- * the color indicates whether the node is part of a 3-node or a 4-node.
- * In addition to the ordinary requirements imposed on binary search
- * trees, we make the following additional requirements of any valid
- * red-black tree:
- * 1) Every node is either red or black.
- * 2) The root is black.
- * 3) All leaves are black.
- * 4) Both children of each red node are black.
- * 5) The paths from each leaf up to the root each contain the same
- * number of black nodes.
- */
-
-/*
- * Create a red black tree struct using the specified compare routine.
- * Allocates and returns the initialized (empty) tree.
- */
-struct rbtree *
-rbcreate(compar)
- int (*compar)__P((const void *, const void*));
-{
- struct rbtree *tree;
-
- tree = (struct rbtree *) emalloc(sizeof(*tree));
- tree->compar = compar;
-
- /*
- * We use a self-referencing sentinel node called nil to simplify the
- * code by avoiding the need to check for NULL pointers.
- */
- tree->nil.left = tree->nil.right = tree->nil.parent = &tree->nil;
- tree->nil.color = black;
- tree->nil.data = NULL;
-
- /*
- * Similarly, the fake root node keeps us from having to worry
- * about splitting the root.
- */
- tree->root.left = tree->root.right = tree->root.parent = &tree->nil;
- tree->root.color = black;
- tree->root.data = NULL;
-
- return(tree);
-}
-
-/*
- * Perform a left rotation starting at node.
- */
-static void
-rotate_left(tree, node)
- struct rbtree *tree;
- struct rbnode *node;
-{
- struct rbnode *child;
-
- child = node->right;
- node->right = child->left;
-
- if (child->left != rbnil(tree))
- child->left->parent = node;
- child->parent = node->parent;
-
- if (node == node->parent->left)
- node->parent->left = child;
- else
- node->parent->right = child;
- child->left = node;
- node->parent = child;
-}
-
-/*
- * Perform a right rotation starting at node.
- */
-static void
-rotate_right(tree, node)
- struct rbtree *tree;
- struct rbnode *node;
-{
- struct rbnode *child;
-
- child = node->left;
- node->left = child->right;
-
- if (child->right != rbnil(tree))
- child->right->parent = node;
- child->parent = node->parent;
-
- if (node == node->parent->left)
- node->parent->left = child;
- else
- node->parent->right = child;
- child->right = node;
- node->parent = child;
-}
-
-/*
- * Insert data pointer into a redblack tree.
- * Returns a NULL pointer on success. If a node matching "data"
- * already exists, a pointer to the existant node is returned.
- */
-struct rbnode *
-rbinsert(tree, data)
- struct rbtree *tree;
- void *data;
-{
- struct rbnode *node = rbfirst(tree);
- struct rbnode *parent = rbroot(tree);
- int res;
-
- /* Find correct insertion point. */
- while (node != rbnil(tree)) {
- parent = node;
- if ((res = tree->compar(data, node->data)) == 0)
- return(node);
- node = res < 0 ? node->left : node->right;
- }
-
- node = (struct rbnode *) emalloc(sizeof(*node));
- node->data = data;
- node->left = node->right = rbnil(tree);
- node->parent = parent;
- if (parent == rbroot(tree) || tree->compar(data, parent->data) < 0)
- parent->left = node;
- else
- parent->right = node;
- node->color = red;
-
- /*
- * If the parent node is black we are all set, if it is red we have
- * the following possible cases to deal with. We iterate through
- * the rest of the tree to make sure none of the required properties
- * is violated.
- *
- * 1) The uncle is red. We repaint both the parent and uncle black
- * and repaint the grandparent node red.
- *
- * 2) The uncle is black and the new node is the right child of its
- * parent, and the parent in turn is the left child of its parent.
- * We do a left rotation to switch the roles of the parent and
- * child, relying on further iterations to fixup the old parent.
- *
- * 3) The uncle is black and the new node is the left child of its
- * parent, and the parent in turn is the left child of its parent.
- * We switch the colors of the parent and grandparent and perform
- * a right rotation around the grandparent. This makes the former
- * parent the parent of the new node and the former grandparent.
- *
- * Note that because we use a sentinel for the root node we never
- * need to worry about replacing the root.
- */
- while (node->parent->color == red) {
- struct rbnode *uncle;
- if (node->parent == node->parent->parent->left) {
- uncle = node->parent->parent->right;
- if (uncle->color == red) {
- node->parent->color = black;
- uncle->color = black;
- node->parent->parent->color = red;
- node = node->parent->parent;
- } else /* if (uncle->color == black) */ {
- if (node == node->parent->right) {
- node = node->parent;
- rotate_left(tree, node);
- }
- node->parent->color = black;
- node->parent->parent->color = red;
- rotate_right(tree, node->parent->parent);
- }
- } else { /* if (node->parent == node->parent->parent->right) */
- uncle = node->parent->parent->left;
- if (uncle->color == red) {
- node->parent->color = black;
- uncle->color = black;
- node->parent->parent->color = red;
- node = node->parent->parent;
- } else /* if (uncle->color == black) */ {
- if (node == node->parent->left) {
- node = node->parent;
- rotate_right(tree, node);
- }
- node->parent->color = black;
- node->parent->parent->color = red;
- rotate_left(tree, node->parent->parent);
- }
- }
- }
- rbfirst(tree)->color = black; /* first node is always black */
- return(NULL);
-}
-
-/*
- * Look for a node matching key in tree.
- * Returns a pointer to the node if found, else NULL.
- */
-struct rbnode *
-rbfind(tree, key)
- struct rbtree *tree;
- void *key;
-{
- struct rbnode *node = rbfirst(tree);
- int res;
-
- while (node != rbnil(tree)) {
- if ((res = tree->compar(key, node->data)) == 0)
- return(node);
- node = res < 0 ? node->left : node->right;
- }
- return(NULL);
-}
-
-/*
- * Call func() for each node, passing it the node data and a cookie;
- * If func() returns non-zero for a node, the traversal stops and the
- * error value is returned. Returns 0 on successful traversal.
- */
-int
-rbapply_node(tree, node, func, cookie, order)
- struct rbtree *tree;
- struct rbnode *node;
- int (*func)__P((void *, void *));
- void *cookie;
- enum rbtraversal order;
-{
- int error;
-
- if (node != rbnil(tree)) {
- if (order == preorder)
- if ((error = func(node->data, cookie)) != 0)
- return(error);
- if ((error = rbapply_node(tree, node->left, func, cookie, order)) != 0)
- return(error);
- if (order == inorder)
- if ((error = func(node->data, cookie)) != 0)
- return(error);
- if ((error = rbapply_node(tree, node->right, func, cookie, order)) != 0)
- return(error);
- if (order == postorder)
- if ((error = func(node->data, cookie)) != 0)
- return(error);
- }
- return (0);
-}
-
-/*
- * Returns the successor of node, or nil if there is none.
- */
-static struct rbnode *
-rbsuccessor(tree, node)
- struct rbtree *tree;
- struct rbnode *node;
-{
- struct rbnode *succ;
-
- if ((succ = node->right) != rbnil(tree)) {
- while (succ->left != rbnil(tree))
- succ = succ->left;
- } else {
- /* No right child, move up until we find it or hit the root */
- for (succ = node->parent; node == succ->right; succ = succ->parent)
- node = succ;
- if (succ == rbroot(tree))
- succ = rbnil(tree);
- }
- return(succ);
-}
-
-/*
- * Recursive portion of rbdestroy().
- */
-static void
-_rbdestroy(tree, node, destroy)
- struct rbtree *tree;
- struct rbnode *node;
- void (*destroy)__P((void *));
-{
- if (node != rbnil(tree)) {
- _rbdestroy(tree, node->left, destroy);
- _rbdestroy(tree, node->right, destroy);
- if (destroy != NULL)
- destroy(node->data);
- efree(node);
- }
-}
-
-/*
- * Destroy the specified tree, calling the destructor destroy
- * for each node and then freeing the tree itself.
- */
-void
-rbdestroy(tree, destroy)
- struct rbtree *tree;
- void (*destroy)__P((void *));
-{
- _rbdestroy(tree, rbfirst(tree), destroy);
- efree(tree);
-}
-
-/*
- * Delete node 'z' from the tree and return its data pointer.
- */
-void *rbdelete(tree, z)
- struct rbtree *tree;
- struct rbnode *z;
-{
- struct rbnode *x, *y;
- void *data = z->data;
-
- if (z->left == rbnil(tree) || z->right == rbnil(tree))
- y = z;
- else
- y = rbsuccessor(tree, z);
- x = (y->left == rbnil(tree)) ? y->right : y->left;
-
- if ((x->parent = y->parent) == rbroot(tree)) {
- rbfirst(tree) = x;
- } else {
- if (y == y->parent->left)
- y->parent->left = x;
- else
- y->parent->right = x;
- }
- if (y->color == black)
- rbrepair(tree, x);
- if (y != z) {
- y->left = z->left;
- y->right = z->right;
- y->parent = z->parent;
- y->color = z->color;
- z->left->parent = z->right->parent = y;
- if (z == z->parent->left)
- z->parent->left = y;
- else
- z->parent->right = y;
- }
- free(z);
-
- return (data);
-}
-
-/*
- * Repair the tree after a node has been deleted by rotating and repainting
- * colors to restore the 4 properties inherent in red-black trees.
- */
-static void
-rbrepair(tree, node)
- struct rbtree *tree;
- struct rbnode *node;
-{
- struct rbnode *sibling;
-
- while (node->color == black && node != rbroot(tree)) {
- if (node == node->parent->left) {
- sibling = node->parent->right;
- if (sibling->color == red) {
- sibling->color = black;
- node->parent->color = red;
- rotate_left(tree, node->parent);
- sibling = node->parent->right;
- }
- if (sibling->right->color == black && sibling->left->color == black) {
- sibling->color = red;
- node = node->parent;
- } else {
- if (sibling->right->color == black) {
- sibling->left->color = black;
- sibling->color = red;
- rotate_right(tree, sibling);
- sibling = node->parent->right;
- }
- sibling->color = node->parent->color;
- node->parent->color = black;
- sibling->right->color = black;
- rotate_left(tree, node->parent);
- node = rbroot(tree); /* exit loop */
- }
- } else { /* if (node == node->parent->right) */
- sibling = node->parent->left;
- if (sibling->color == red) {
- sibling->color = black;
- node->parent->color = red;
- rotate_right(tree, node->parent);
- sibling = node->parent->left;
- }
- if (sibling->right->color == black && sibling->left->color == black) {
- sibling->color = red;
- node = node->parent;
- } else {
- if (sibling->left->color == black) {
- sibling->right->color = black;
- sibling->color = red;
- rotate_left(tree, sibling);
- sibling = node->parent->left;
- }
- sibling->color = node->parent->color;
- node->parent->color = black;
- sibling->left->color = black;
- rotate_right(tree, node->parent);
- node = rbroot(tree); /* exit loop */
- }
- }
- }
- node->color = black;
-}
projects / debian / sudo / blobdiff