/*

 * SPDX-License-Identifier: ISC

 *

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

 */

/*

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

    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;

}