Adding upstream version 1.8.27.upstream/1.8.27upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 479 insertions, 0 deletions

diff --git a/plugins/sudoers/redblack.c b/plugins/sudoers/redblack.c
new file mode 100644
index 0000000..ef7e8f5
--- /dev/null
+++ b/plugins/sudoers/redblack.c
@@ -0,0 +1,479 @@
+/*
+ * Copyright (c) 2004-2005, 2007, 2009-2015
+ *	Todd C. Miller <Todd.Miller@sudo.ws>
+ *
+ * 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.
+ */
+
+/*
+ * This is an open source non-commercial project. Dear PVS-Studio, please check it.
+ * PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com
+ */
+
+/*
+ * 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 <stdio.h>
+#include <stdlib.h>
+
+#include "sudoers.h"
+#include "redblack.h"
+
+static void rbrepair(struct rbtree *, struct rbnode *);
+static void rotate_left(struct rbtree *, struct rbnode *);
+static void rotate_right(struct rbtree *, struct rbnode *);
+static void rbdestroy_int(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 or NULL if
+ * memory cannot be allocated.
+ */
+struct rbtree *
+rbcreate(int (*compar)(const void *, const void*))
+{
+    struct rbtree *tree;
+    debug_decl(rbcreate, SUDOERS_DEBUG_RBTREE)
+
+    if ((tree = malloc(sizeof(*tree))) == NULL) {
+	sudo_debug_printf(SUDO_DEBUG_ERROR|SUDO_DEBUG_LINENO,
+	    "unable to allocate memory");
+	debug_return_ptr(NULL);
+    }
+
+    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;
+
+    debug_return_ptr(tree);
+}
+
+/*
+ * Perform a left rotation starting at node.
+ */
+static void
+rotate_left(struct rbtree *tree, struct rbnode *node)
+{
+    struct rbnode *child;
+    debug_decl(rotate_left, SUDOERS_DEBUG_RBTREE)
+
+    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;
+
+    debug_return;
+}
+
+/*
+ * Perform a right rotation starting at node.
+ */
+static void
+rotate_right(struct rbtree *tree, struct rbnode *node)
+{
+    struct rbnode *child;
+    debug_decl(rotate_right, SUDOERS_DEBUG_RBTREE)
+
+    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;
+
+    debug_return;
+}
+
+/*
+ * Insert data pointer into a redblack tree.
+ * Returns a 0 on success, 1 if a node matching "data" already exists
+ * (filling in "existing" if not NULL), or -1 on malloc() failure.
+ */
+int
+rbinsert(struct rbtree *tree, void *data, struct rbnode **existing)
+{
+    struct rbnode *node = rbfirst(tree);
+    struct rbnode *parent = rbroot(tree);
+    int res;
+    debug_decl(rbinsert, SUDOERS_DEBUG_RBTREE)
+
+    /* Find correct insertion point. */
+    while (node != rbnil(tree)) {
+	parent = node;
+	if ((res = tree->compar(data, node->data)) == 0) {
+	    if (existing != NULL)
+		*existing = node;
+	    debug_return_int(1);
+	}
+	node = res < 0 ? node->left : node->right;
+    }
+
+    node = malloc(sizeof(*node));
+    if (node == NULL) {
+	sudo_debug_printf(SUDO_DEBUG_ERROR|SUDO_DEBUG_LINENO,
+	    "unable to allocate memory");
+	debug_return_int(-1);
+    }
+    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 */
+    debug_return_int(0);
+}
+
+/*
+ * Look for a node matching key in tree.
+ * Returns a pointer to the node if found, else NULL.
+ */
+struct rbnode *
+rbfind(struct rbtree *tree, void *key)
+{
+    struct rbnode *node = rbfirst(tree);
+    int res;
+    debug_decl(rbfind, SUDOERS_DEBUG_RBTREE)
+
+    while (node != rbnil(tree)) {
+	if ((res = tree->compar(key, node->data)) == 0)
+	    debug_return_ptr(node);
+	node = res < 0 ? node->left : node->right;
+    }
+    debug_return_ptr(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(struct rbtree *tree, struct rbnode *node,
+    int (*func)(void *, void *), void *cookie, enum rbtraversal order)
+{
+    int error;
+    debug_decl(rbapply_node, SUDOERS_DEBUG_RBTREE)
+
+    if (node != rbnil(tree)) {
+	if (order == preorder)
+	    if ((error = func(node->data, cookie)) != 0)
+		debug_return_int(error);
+	if ((error = rbapply_node(tree, node->left, func, cookie, order)) != 0)
+	    debug_return_int(error);
+	if (order == inorder)
+	    if ((error = func(node->data, cookie)) != 0)
+		debug_return_int(error);
+	if ((error = rbapply_node(tree, node->right, func, cookie, order)) != 0)
+	    debug_return_int(error);
+	if (order == postorder)
+	    if ((error = func(node->data, cookie)) != 0)
+		debug_return_int(error);
+    }
+    debug_return_int(0);
+}
+
+/*
+ * Returns the successor of node, or nil if there is none.
+ */
+static struct rbnode *
+rbsuccessor(struct rbtree *tree, struct rbnode *node)
+{
+    struct rbnode *succ;
+    debug_decl(rbsuccessor, SUDOERS_DEBUG_RBTREE)
+
+    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);
+    }
+    debug_return_ptr(succ);
+}
+
+/*
+ * Recursive portion of rbdestroy().
+ */
+static void
+rbdestroy_int(struct rbtree *tree, struct rbnode *node, void (*destroy)(void *))
+{
+    debug_decl(rbdestroy_int, SUDOERS_DEBUG_RBTREE)
+    if (node != rbnil(tree)) {
+	rbdestroy_int(tree, node->left, destroy);
+	rbdestroy_int(tree, node->right, destroy);
+	if (destroy != NULL)
+	    destroy(node->data);
+	free(node);
+    }
+    debug_return;
+}
+
+/*
+ * Destroy the specified tree, calling the destructor "destroy"
+ * for each node and then freeing the tree itself.
+ */
+void
+rbdestroy(struct rbtree *tree, void (*destroy)(void *))
+{
+    debug_decl(rbdestroy, SUDOERS_DEBUG_RBTREE)
+    rbdestroy_int(tree, rbfirst(tree), destroy);
+    free(tree);
+    debug_return;
+}
+
+/*
+ * Delete node 'z' from the tree and return its data pointer.
+ */
+void *rbdelete(struct rbtree *tree, struct rbnode *z)
+{
+    struct rbnode *x, *y;
+    void *data = z->data;
+    debug_decl(rbdelete, SUDOERS_DEBUG_RBTREE)
+
+    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); 
+    
+    debug_return_ptr(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(struct rbtree *tree, struct rbnode *node)
+{
+    struct rbnode *sibling;
+    debug_decl(rbrepair, SUDOERS_DEBUG_RBTREE)
+
+    while (node->color == black && node != rbfirst(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 = rbfirst(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 = rbfirst(tree); /* exit loop */
+	    }
+	}
+    }
+    node->color = black;
+
+    debug_return;
+}