/**
* @file rtems/score/rbtree.h
*
* @brief Constants and Structures Associated with the Red-Black Tree Handler
*
* This include file contains all the constants and structures associated
* with the Red-Black Tree Handler.
*/
/*
* Copyright (c) 2010 Gedare Bloom.
*
* The license and distribution terms for this file may be
* found in the file LICENSE in this distribution or at
* http://www.rtems.org/license/LICENSE.
*/
#ifndef _RTEMS_SCORE_RBTREE_H
#define _RTEMS_SCORE_RBTREE_H
#include <stddef.h>
#include <rtems/score/address.h>
#ifdef __cplusplus
extern "C" {
#endif
/**
* @defgroup ScoreRBTree Red-Black Tree Handler
*
* @ingroup Score
*
* The Red-Black Tree Handler is used to manage sets of entities. This handler
* provides two data structures. The rbtree Node data structure is included
* as the first part of every data structure that will be placed on
* a RBTree. The second data structure is rbtree Control which is used
* to manage a set of rbtree Nodes.
*/
/**@{*/
/**
* @typedef RBTree_Node
*
* This type definition promotes the name for the RBTree Node used by
* all RTEMS code. It is a separate type definition because a forward
* reference is required to define it. See @ref RBTree_Node_struct for
* detailed information.
*/
typedef struct RBTree_Node_struct RBTree_Node;
/**
* This enum type defines the colors available for the RBTree Nodes
*/
typedef enum {
RBT_BLACK,
RBT_RED
} RBTree_Color;
/**
* @struct RBTree_Node_struct
*
* This is used to manage each element (node) which is placed
* on a RBT.
*
* @note Typically, a more complicated structure will use the
* rbtree package. The more complicated structure will
* include a rbtree node as the first element in its
* control structure. It will then call the rbtree package
* with a pointer to that node element. The node pointer
* and the higher level structure start at the same address
* so the user can cast the pointers back and forth.
*
*/
struct RBTree_Node_struct {
/** This points to the node's parent */
RBTree_Node *parent;
/** child[0] points to the left child, child[1] points to the right child */
RBTree_Node *child[2];
/** The color of the node. Either red or black */
RBTree_Color color;
};
/**
* This type indicates the direction.
*/
typedef enum {
RBT_LEFT=0,
RBT_RIGHT=1
} RBTree_Direction;
/**
* @brief Integer type for compare results.
*
* The type is large enough to represent pointers and 32-bit signed integers.
*
* @see RBTree_Compare.
*/
typedef long RBTree_Compare_result;
/**
* @brief Compares two red-black tree nodes.
*
* @param[in] first The first node.
* @param[in] second The second node.
*
* @retval positive The key value of the first node is greater than the one of
* the second node.
* @retval 0 The key value of the first node is equal to the one of the second
* node.
* @retval negative The key value of the first node is less than the one of the
* second node.
*/
typedef RBTree_Compare_result ( *RBTree_Compare )(
const RBTree_Node *first,
const RBTree_Node *second
);
/**
* @struct RBTree_Control
*
* This is used to manage a RBT. A rbtree consists of a tree of zero or more
* nodes.
*
* @note This implementation does not require special checks for
* manipulating the root element of the RBT.
* To accomplish this the @a RBTree_Control structure can be overlaid
* with a @ref RBTree_Node structure to act as a "dummy root",
* which has a NULL parent and its left child is the root.
*/
/* the RBTree_Control is actually part of the RBTree structure as an
* RBTree_Node. The mapping of fields from RBTree_Control to RBTree_Node are:
* permanent_null == parent
* root == left
* first[0] == right
*/
typedef struct {
/** This points to a NULL. Useful for finding the root. */
RBTree_Node *permanent_null;
/** This points to the root node of the RBT. */
RBTree_Node *root;
/** This points to the min and max nodes of this RBT. */
RBTree_Node *first[2];
} RBTree_Control;
/**
* @brief RBTree initializer for an empty rbtree with designator @a name.
*/
#define RBTREE_INITIALIZER_EMPTY( name ) \
{ NULL, NULL, { NULL, NULL } }
/**
* @brief RBTree definition for an empty rbtree with designator @a name.
*/
#define RBTREE_DEFINE_EMPTY( name ) \
RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )
/**
* @brief RBTree_Node initializer for an empty node with designator @a name.
*/
#define RBTREE_NODE_INITIALIZER_EMPTY( name ) \
{ NULL, { NULL, NULL }, RBT_RED }
/**
* @brief RBTree definition for an empty rbtree with designator @a name.
*/
#define RBTREE_NODE_DEFINE_EMPTY( name ) \
RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY( name )
/**
* @brief Tries to find a node for the specified key in the tree.
*
* @param[in] the_rbtree The red-black tree control.
* @param[in] the_node A node specifying the key.
* @param[in] compare The node compare function.
* @param[in] is_unique If true, then return the first node with a key equal to
* the one of the node specified if it exits, else return the last node if it
* exists.
*
* @retval node A node corresponding to the key. If the tree is not unique
* and contains duplicate keys, the set of duplicate keys acts as FIFO.
* @retval NULL No node exists in the tree for the key.
*/
RBTree_Node *_RBTree_Find(
const RBTree_Control *the_rbtree,
const RBTree_Node *the_node,
RBTree_Compare compare,
bool is_unique
);
/**
* @brief Inserts the node into the red-black tree.
*
* In case the node is already a node of a tree, then this function yields
* unpredictable results.
*
* @param[in] the_rbtree The red-black tree control.
* @param[in] the_node The node to insert.
* @param[in] compare The node compare function.
* @param[in] is_unique If true, then reject nodes with a duplicate key, else
* insert nodes in FIFO order in case the key value is equal to existing nodes.
*
* @retval NULL Successfully inserted.
* @retval existing_node This is a unique insert and there exists a node with
* an equal key in the tree already.
*/
RBTree_Node *_RBTree_Insert(
RBTree_Control *the_rbtree,
RBTree_Node *the_node,
RBTree_Compare compare,
bool is_unique
);
/**
* @brief Extracts (removes) the node from the red-black tree.
*
* This function does not set the node off-tree. In case this is desired, then
* call _RBTree_Set_off_tree() after the extraction.
*
* In case the node to extract is not a node of the tree, then this function
* yields unpredictable results.
*
* @param[in] the_rbtree The red-black tree control.
* @param[in] the_node The node to extract.
*/
void _RBTree_Extract(
RBTree_Control *the_rbtree,
RBTree_Node *the_node
);
/**
* @brief Returns the in-order next node of a node.
*
* @param[in] node The node.
* @param[in] dir The direction.
*
* @retval NULL The in-order next node does not exist.
* @retval otherwise The next node.
*/
RBTree_Node *_RBTree_Next(
const RBTree_Node *node,
RBTree_Direction dir
);
/**
* @brief Sets a red-black tree node as off-tree.
*
* Do not use this function on nodes which are a part of a tree.
*
* @param[in] the_node The node to set off-tree.
*
* @see _RBTree_Is_node_off_tree().
*/
RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node )
{
the_node->parent = NULL;
}
/**
* @brief Returns true, if this red-black tree node is off-tree, and false
* otherwise.
*
* @param[in] the_node The node to test.
*
* @retval true The node is not a part of a tree (off-tree).
* @retval false Otherwise.
*
* @see _RBTree_Set_off_tree().
*/
RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree(
const RBTree_Node *the_node
)
{
return the_node->parent == NULL;
}
/**
* @brief Returns a pointer to root node of the red-black tree.
*
* The root node may change after insert or extract operations.
*
* @param[in] the_rbtree The red-black tree control.
*
* @retval NULL The tree is empty.
* @retval root The root node.
*
* @see _RBTree_Is_root().
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
const RBTree_Control *the_rbtree
)
{
return the_rbtree->root;
}
/**
* @brief Return pointer to RBTree's first node.
*
* This function returns a pointer to the first node on @a the_rbtree,
* where @a dir specifies whether to return the minimum (0) or maximum (1).
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First(
const RBTree_Control *the_rbtree,
RBTree_Direction dir
)
{
return the_rbtree->first[dir];
}
/**
* @brief Returns a pointer to the parent of this node.
*
* The node must have a parent, thus it is invalid to use this function for the
* root node or a node that is not part of a tree. To test for the root node
* compare with _RBTree_Root() or use _RBTree_Is_root().
*
* @param[in] the_node The node of interest.
*
* @retval parent The parent of this node.
* @retval undefined The node is the root node or not part of a tree.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
const RBTree_Node *the_node
)
{
return the_node->parent;
}
/**
* @brief Return pointer to the left of this node.
*
* This function returns a pointer to the left node of this node.
*
* @param[in] the_node is the node to be operated upon.
*
* @return This method returns the left node on the rbtree.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
const RBTree_Node *the_node
)
{
return the_node->child[RBT_LEFT];
}
/**
* @brief Return pointer to the right of this node.
*
* This function returns a pointer to the right node of this node.
*
* @param[in] the_node is the node to be operated upon.
*
* @return This method returns the right node on the rbtree.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
const RBTree_Node *the_node
)
{
return the_node->child[RBT_RIGHT];
}
/**
* @brief Is the RBTree empty.
*
* This function returns true if there are no nodes on @a the_rbtree and
* false otherwise.
*
* @param[in] the_rbtree is the rbtree to be operated upon.
*
* @retval true There are no nodes on @a the_rbtree.
* @retval false There are nodes on @a the_rbtree.
*/
RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
const RBTree_Control *the_rbtree
)
{
return (the_rbtree->root == NULL);
}
/**
* @brief Returns true if this node is the root node of a red-black tree, and
* false otherwise.
*
* The root node may change after insert or extract operations. In case the
* node is not a node of a tree, then this function yields unpredictable
* results.
*
* @param[in] the_node The node of interest.
*
* @retval true The node is the root node.
* @retval false Otherwise.
*
* @see _RBTree_Root().
*/
RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
const RBTree_Node *the_node
)
{
return _RBTree_Parent( _RBTree_Parent( the_node ) ) == NULL;
}
/**
* @brief Finds the red-black tree control given a node in the tree.
*
* In case the node is not a node of a tree, then this function yields
* unpredictable results.
*
* @param[in] the_node The node of interest.
*
* @return The red-black tree control of the node.
*/
RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_control(
const RBTree_Node *the_node
)
{
RBTree_Node *parent = the_node->parent;
RBTree_Control *rbtree;
do {
rbtree = (RBTree_Control *) parent;
parent = parent->parent;
} while ( parent != NULL );
return rbtree;
}
/**
* @brief Initialize this RBTree as empty.
*
* This routine initializes @a the_rbtree to contain zero nodes.
*/
RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
RBTree_Control *the_rbtree
)
{
the_rbtree->permanent_null = NULL;
the_rbtree->root = NULL;
the_rbtree->first[RBT_LEFT] = NULL;
the_rbtree->first[RBT_RIGHT] = NULL;
}
/**
* @brief Returns the minimum node of the red-black tree.
*
* @param[in] the_rbtree The red-black tree control.
*
* @retval NULL The red-black tree is empty.
* @retval node The minimum node.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Minimum(
const RBTree_Control *the_rbtree
)
{
return _RBTree_First( the_rbtree, RBT_LEFT );
}
/**
* @brief Returns the maximum node of the red-black tree.
*
* @param[in] the_rbtree The red-black tree control.
*
* @retval NULL The red-black tree is empty.
* @retval node The maximum node.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Maximum(
const RBTree_Control *the_rbtree
)
{
return _RBTree_First( the_rbtree, RBT_RIGHT );
}
/**
* @brief Returns the predecessor of a node.
*
* @param[in] node is the node.
*
* @retval NULL The predecessor does not exist. Otherwise it returns
* the predecessor node.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
const RBTree_Node *node
)
{
return _RBTree_Next( node, RBT_LEFT );
}
/**
* @brief Returns the successor of a node.
*
* @param[in] node is the node.
*
* @retval NULL The successor does not exist. Otherwise the successor node.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
const RBTree_Node *node
)
{
return _RBTree_Next( node, RBT_RIGHT );
}
/**@}*/
#ifdef __cplusplus
}
#endif
#endif
/* end of include file */
