216 lines
6.2 KiB
C
216 lines
6.2 KiB
C
/*
|
|
* Copyright (C) 2008-2011 Teluu Inc. (http://www.teluu.com)
|
|
* Copyright (C) 2003-2008 Benny Prijono <benny@prijono.org>
|
|
*
|
|
* This program is free software; you can redistribute it and/or modify
|
|
* it under the terms of the GNU General Public License as published by
|
|
* the Free Software Foundation; either version 2 of the License, or
|
|
* (at your option) any later version.
|
|
*
|
|
* This program is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
* GNU General Public License for more details.
|
|
*
|
|
* You should have received a copy of the GNU General Public License
|
|
* along with this program; if not, write to the Free Software
|
|
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
|
|
*/
|
|
#ifndef __PJ_RBTREE_H__
|
|
#define __PJ_RBTREE_H__
|
|
|
|
/**
|
|
* @file rbtree.h
|
|
* @brief Red/Black Tree
|
|
*/
|
|
|
|
#include <pj/types.h>
|
|
|
|
PJ_BEGIN_DECL
|
|
|
|
/**
|
|
* @defgroup PJ_RBTREE Red/Black Balanced Tree
|
|
* @ingroup PJ_DS
|
|
* @brief
|
|
* Red/Black tree is the variant of balanced tree, where the search, insert,
|
|
* and delete operation is \b guaranteed to take at most \a O( lg(n) ).
|
|
* @{
|
|
*/
|
|
/**
|
|
* Color type for Red-Black tree.
|
|
*/
|
|
typedef enum pj_rbcolor_t
|
|
{
|
|
PJ_RBCOLOR_BLACK,
|
|
PJ_RBCOLOR_RED
|
|
} pj_rbcolor_t;
|
|
|
|
/**
|
|
* The type of the node of the R/B Tree.
|
|
*/
|
|
typedef struct pj_rbtree_node
|
|
{
|
|
/** Pointers to the node's parent. */
|
|
struct pj_rbtree_node *parent;
|
|
|
|
/** Pointers to the node's left sibling. */
|
|
struct pj_rbtree_node *left;
|
|
|
|
/** Pointers to the node's right sibling. */
|
|
struct pj_rbtree_node *right;
|
|
|
|
/** Key associated with the node. */
|
|
const void *key;
|
|
|
|
/** User data associated with the node. */
|
|
void *user_data;
|
|
|
|
/** The R/B Tree node color. */
|
|
pj_rbcolor_t color;
|
|
|
|
} pj_rbtree_node;
|
|
|
|
|
|
/**
|
|
* The type of function use to compare key value of tree node.
|
|
* @return
|
|
* 0 if the keys are equal
|
|
* <0 if key1 is lower than key2
|
|
* >0 if key1 is greater than key2.
|
|
*/
|
|
typedef int pj_rbtree_comp(const void *key1, const void *key2);
|
|
|
|
|
|
/**
|
|
* Declaration of a red-black tree. All elements in the tree must have UNIQUE
|
|
* key.
|
|
* A red black tree always maintains the balance of the tree, so that the
|
|
* tree height will not be greater than lg(N). Insert, search, and delete
|
|
* operation will take lg(N) on the worst case. But for insert and delete,
|
|
* there is additional time needed to maintain the balance of the tree.
|
|
*/
|
|
typedef struct pj_rbtree
|
|
{
|
|
pj_rbtree_node null_node; /**< Constant to indicate NULL node. */
|
|
pj_rbtree_node *null; /**< Constant to indicate NULL node. */
|
|
pj_rbtree_node *root; /**< Root tree node. */
|
|
unsigned size; /**< Number of elements in the tree. */
|
|
pj_rbtree_comp *comp; /**< Key comparison function. */
|
|
} pj_rbtree;
|
|
|
|
|
|
/**
|
|
* Guidance on how much memory required for each of the node.
|
|
*/
|
|
#define PJ_RBTREE_NODE_SIZE (sizeof(pj_rbtree_node))
|
|
|
|
|
|
/**
|
|
* Guidance on memory required for the tree.
|
|
*/
|
|
#define PJ_RBTREE_SIZE (sizeof(pj_rbtree))
|
|
|
|
|
|
/**
|
|
* Initialize the tree.
|
|
* @param tree the tree to be initialized.
|
|
* @param comp key comparison function to be used for this tree.
|
|
*/
|
|
PJ_DECL(void) pj_rbtree_init( pj_rbtree *tree, pj_rbtree_comp *comp);
|
|
|
|
/**
|
|
* Get the first element in the tree.
|
|
* The first element always has the least value for the key, according to
|
|
* the comparison function.
|
|
* @param tree the tree.
|
|
* @return the tree node, or NULL if the tree has no element.
|
|
*/
|
|
PJ_DECL(pj_rbtree_node*) pj_rbtree_first( pj_rbtree *tree );
|
|
|
|
/**
|
|
* Get the last element in the tree.
|
|
* The last element always has the greatest key value, according to the
|
|
* comparison function defined for the tree.
|
|
* @param tree the tree.
|
|
* @return the tree node, or NULL if the tree has no element.
|
|
*/
|
|
PJ_DECL(pj_rbtree_node*) pj_rbtree_last( pj_rbtree *tree );
|
|
|
|
/**
|
|
* Get the successive element for the specified node.
|
|
* The successive element is an element with greater key value.
|
|
* @param tree the tree.
|
|
* @param node the node.
|
|
* @return the successive node, or NULL if the node has no successor.
|
|
*/
|
|
PJ_DECL(pj_rbtree_node*) pj_rbtree_next( pj_rbtree *tree,
|
|
pj_rbtree_node *node );
|
|
|
|
/**
|
|
* The the previous node for the specified node.
|
|
* The previous node is an element with less key value.
|
|
* @param tree the tree.
|
|
* @param node the node.
|
|
* @return the previous node, or NULL if the node has no previous node.
|
|
*/
|
|
PJ_DECL(pj_rbtree_node*) pj_rbtree_prev( pj_rbtree *tree,
|
|
pj_rbtree_node *node );
|
|
|
|
/**
|
|
* Insert a new node.
|
|
* The node will be inserted at sorted location. The key of the node must
|
|
* be UNIQUE, i.e. it hasn't existed in the tree.
|
|
* @param tree the tree.
|
|
* @param node the node to be inserted.
|
|
* @return zero on success, or -1 if the key already exist.
|
|
*/
|
|
PJ_DECL(int) pj_rbtree_insert( pj_rbtree *tree,
|
|
pj_rbtree_node *node );
|
|
|
|
/**
|
|
* Find a node which has the specified key.
|
|
* @param tree the tree.
|
|
* @param key the key to search.
|
|
* @return the tree node with the specified key, or NULL if the key can not
|
|
* be found.
|
|
*/
|
|
PJ_DECL(pj_rbtree_node*) pj_rbtree_find( pj_rbtree *tree,
|
|
const void *key );
|
|
|
|
/**
|
|
* Erase a node from the tree.
|
|
* @param tree the tree.
|
|
* @param node the node to be erased.
|
|
* @return the tree node itself.
|
|
*/
|
|
PJ_DECL(pj_rbtree_node*) pj_rbtree_erase( pj_rbtree *tree,
|
|
pj_rbtree_node *node );
|
|
|
|
/**
|
|
* Get the maximum tree height from the specified node.
|
|
* @param tree the tree.
|
|
* @param node the node, or NULL to get the root of the tree.
|
|
* @return the maximum height, which should be at most lg(N)
|
|
*/
|
|
PJ_DECL(unsigned) pj_rbtree_max_height( pj_rbtree *tree,
|
|
pj_rbtree_node *node );
|
|
|
|
/**
|
|
* Get the minumum tree height from the specified node.
|
|
* @param tree the tree.
|
|
* @param node the node, or NULL to get the root of the tree.
|
|
* @return the height
|
|
*/
|
|
PJ_DECL(unsigned) pj_rbtree_min_height( pj_rbtree *tree,
|
|
pj_rbtree_node *node );
|
|
|
|
|
|
/**
|
|
* @}
|
|
*/
|
|
|
|
PJ_END_DECL
|
|
|
|
#endif /* __PJ_RBTREE_H__ */
|
|
|