nest-open-source / nest-learning-thermostat / 5.0.1 / sudo / refs/heads/master / . / sudo-1.7.4p4 / redblack.c

/* | |

* 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; | |

} |