astobj2_rbtree.c

/*
 * astobj2_hash - RBTree implementation for astobj2.
 *
 * Copyright (C) 2006 Marta Carbone, Luigi Rizzo - Univ. di Pisa, Italy
 *
 * See http://www.asterisk.org for more information about
 * the Asterisk project. Please do not directly contact
 * any of the maintainers of this project for assistance;
 * the project provides a web site, mailing lists and IRC
 * channels for your use.
 *
 * This program is free software, distributed under the terms of
 * the GNU General Public License Version 2. See the LICENSE file
 * at the top of the source tree.
 */

/*! \file
 *
 * \brief RBTree functions implementing astobj2 containers.
 *
 * \author Richard Mudgett <rmudgett@digium.com>
 */

#include "asterisk.h"

ASTERISK_FILE_VERSION(__FILE__, "$Revision$")

#include "asterisk/_private.h"
#include "asterisk/astobj2.h"
#include "asterisk/utils.h"
#include "astobj2_private.h"
#include "astobj2_container_private.h"

/*!
 * A structure to hold the object held by the container and
 * where it is located in it.
 *
 * A red-black tree has the following properties:
 *
 * 1) Every node is either black or red.
 *
 * 2) The root is black.
 *
 * 3) If a node has a NULL child, that "child" is considered
 * black.
 *
 * 4) If a node is red, then both of its children are black.
 *
 * 5) Every path from a node to a descendant NULL child has the
 * same number of black nodes.  (Including the black NULL
 * child.)
 */
struct rbtree_node {
	/*!
	 * \brief Items common to all container nodes.
	 * \note Must be first in the specific node struct.
	 */
	struct ao2_container_node common;
	/*! Parent node of this node. NULL if this is the root node. */
	struct rbtree_node *parent;
	/*! Left child node of this node.  NULL if does not have this child. */
	struct rbtree_node *left;
	/*! Right child node of this node.  NULL if does not have this child. */
	struct rbtree_node *right;
	/*! TRUE if the node is red. */
	unsigned int is_red:1;
};

/*!
 * A rbtree container in addition to values common to all
 * container types, stores the pointer to the root node of the
 * tree.
 */
struct ao2_container_rbtree {
	/*!
	 * \brief Items common to all containers.
	 * \note Must be first in the specific container struct.
	 */
	struct ao2_container common;
	/*! Root node of the tree.  NULL if the tree is empty. */
	struct rbtree_node *root;
#if defined(AO2_DEBUG)
	struct {
		/*! Fixup insert left cases 1-3 */
		int fixup_insert_left[3];
		/*! Fixup insert right cases 1-3 */
		int fixup_insert_right[3];
		/*! Fixup delete left cases 1-4 */
		int fixup_delete_left[4];
		/*! Fixup delete right cases 1-4 */
		int fixup_delete_right[4];
		/*! Deletion of node with number of children (0-2). */
		int delete_children[3];
	} stats;
#endif	/* defined(AO2_DEBUG) */
};

enum equal_node_bias {
	/*! Bias search toward first matching node in the container. */
	BIAS_FIRST,
	/*! Bias search toward any matching node. */
	BIAS_EQUAL,
	/*! Bias search toward last matching node in the container. */
	BIAS_LAST,
};

enum empty_node_direction {
	GO_LEFT,
	GO_RIGHT,
};

/*! Traversal state to restart a rbtree container traversal. */
struct rbtree_traversal_state {
	/*! Active sort function in the traversal if not NULL. */
	ao2_sort_fn *sort_fn;
	/*! Saved comparison callback arg pointer. */
	void *arg;
	/*! Saved search flags to control traversing the container. */
	enum search_flags flags;
};

struct rbtree_traversal_state_check {
	/*
	 * If we have a division by zero compile error here then there
	 * is not enough room for the state.  Increase AO2_TRAVERSAL_STATE_SIZE.
	 */
	char check[1 / (AO2_TRAVERSAL_STATE_SIZE / sizeof(struct rbtree_traversal_state))];
};

/*!
 * \internal
 * \brief Get the most left node in the tree.
 * \since 12.0.0
 *
 * \param node Starting node to find the most left node.
 *
 * \return Left most node.  Never NULL.
 */
static struct rbtree_node *rb_node_most_left(struct rbtree_node *node)
{
	while (node->left) {
		node = node->left;
	}

	return node;
}

/*!
 * \internal
 * \brief Get the most right node in the tree.
 * \since 12.0.0
 *
 * \param node Starting node to find the most right node.
 *
 * \return Right most node.  Never NULL.
 */
static struct rbtree_node *rb_node_most_right(struct rbtree_node *node)
{
	while (node->right) {
		node = node->right;
	}

	return node;
}

/*!
 * \internal
 * \brief Get the next node in ascending sequence.
 * \since 12.0.0
 *
 * \param node Starting node to find the next node.
 *
 * \retval node on success.
 * \retval NULL if no node.
 */
static struct rbtree_node *rb_node_next(struct rbtree_node *node)
{
	if (node->right) {
		return rb_node_most_left(node->right);
	}

	/* Find the parent that the node is a left child of. */
	while (node->parent) {
		if (node->parent->left == node) {
			/* We are the left child.  The parent is the next node. */
			return node->parent;
		}
		node = node->parent;
	}
	return NULL;
}

/*!
 * \internal
 * \brief Get the next node in descending sequence.
 * \since 12.0.0
 *
 * \param node Starting node to find the previous node.
 *
 * \retval node on success.