/** * @file rtems/score/rbtree.h * * 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.com/license/LICENSE. * * $Id$ */ #ifndef _RTEMS_SCORE_RBTREE_H #define _RTEMS_SCORE_RBTREE_H /** * @defgroup ScoreRBTree Red-Black Tree Handler * * 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. */ /**@{*/ #ifdef __cplusplus extern "C" { #endif #include /** * @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]; /** This is the integer value stored by this node, used for sorting */ unsigned int value; /** The color of the node. Either red or black */ RBTree_Color color; }; /** * @brief macro to return the structure containing the @a node. * * This macro returns a pointer of type @a container_type that points * to the structure containing @a node, where @a node_field_name is the * field name of the RBTree_Node structure in @a container_type. * */ #define _RBTree_Container_of(node,container_type, node_field_name) \ ((container_type*) \ ((size_t)node - ((size_t)(&((container_type *)0)->node_field_name)))) typedef enum { RBT_LEFT=0, RBT_RIGHT=1 } RBTree_Direction; /** * @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) \ { \ .permanent_null = NULL, \ .root = NULL, \ .first[0] = NULL, \ .first[1] = 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) \ { \ .parent = NULL, \ .child[0] = NULL, \ .child[1] = NULL, \ .value = -1, \ 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 Initialize a RBTree Header * * This routine initializes @a the_rbtree structure to manage the * contiguous array of @a number_nodes nodes which starts at * @a starting_address. Each node is of @a node_size bytes. */ void _RBTree_Initialize( RBTree_Control *the_rbtree, void *starting_address, size_t number_nodes, size_t node_size ); /** * @brief Obtain the min or max node of a rbtree * * This function removes the min or max node from @a the_rbtree and returns * a pointer to that node. If @a the_rbtree is empty, then NULL is returned. * @a dir specifies whether to return the min (0) or max (1). * * @return This method returns a pointer to a node. If a node was removed, * then a pointer to that node is returned. If @a the_rbtree was * empty, then NULL is returned. * * @note It disables interrupts to ensure the atomicity of the get operation. */ RBTree_Node *_RBTree_Get( RBTree_Control *the_rbtree, RBTree_Direction dir ); /** * @brief Check the min or max node on a rbtree * * This function returns a pointer to the min or max node of @a the_rbtree. * If @a the_rbtree is empty, then NULL is returned. @a dir specifies * whether to return the min (0) or max (1). * * @return This method returns a pointer to a node. * If @a the_rbtree was empty, then NULL is returned. * * @note It disables interrupts to ensure the atomicity of the get operation. */ RBTree_Node *_RBTree_Peek( RBTree_Control *the_rbtree, RBTree_Direction dir ); /** @brief Find the node with given value in the tree * * This function returns a pointer to the node with value equal to @a value * if it exists in the Red-Black Tree @a the_rbtree, and NULL if not. */ RBTree_Node *_RBTree_Find( RBTree_Control *the_rbtree, unsigned int value ); /** @brief Find the control structure of the tree containing the given node * * This function returns a pointer to the control structure of the tree * containing @a the_node, if it exists, and NULL if not. */ RBTree_Control *_RBTree_Find_header( RBTree_Node *the_node ); /** @brief Insert a Node (unprotected) * * This routine inserts @a the_node on the Red-Black Tree @a the_rbtree. * * @retval 0 Successfully inserted. * @retval -1 NULL @a the_node. * @retval RBTree_Node* if one with equal value to @a the_node->value exists * in @a the_rbtree. * * @note It does NOT disable interrupts to ensure the atomicity * of the extract operation. */ RBTree_Node *_RBTree_Insert_unprotected( RBTree_Control *the_rbtree, RBTree_Node *the_node ); /** * @brief Insert a node on a rbtree * * This routine inserts @a the_node on the tree @a the_rbtree. * * @note It disables interrupts to ensure the atomicity * of the extract operation. */ void _RBTree_Insert( RBTree_Control *the_rbtree, RBTree_Node *the_node ); /** @brief Extract a Node (unprotected) * * This routine extracts (removes) @a the_node from @a the_rbtree. * * @note It does NOT disable interrupts to ensure the atomicity * of the extract operation. */ void _RBTree_Extract_unprotected( RBTree_Control *the_rbtree, RBTree_Node *the_node ); /** * @brief Delete a node from the rbtree * * This routine deletes @a the_node from @a the_rbtree. * * @note It disables interrupts to ensure the atomicity of the * append operation. */ void _RBTree_Extract( RBTree_Control *the_rbtree, RBTree_Node *the_node ); #ifndef __RTEMS_APPLICATION__ #include #endif #ifdef __cplusplus } #endif /**@}*/ #endif /* end of include file */