diff options
Diffstat (limited to 'cpukit/score/include/rtems/score/rbtree.h')
| -rw-r--r-- | cpukit/score/include/rtems/score/rbtree.h | 568 |
1 files changed, 0 insertions, 568 deletions
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h deleted file mode 100644 index 15a3bc8913..0000000000 --- a/cpukit/score/include/rtems/score/rbtree.h +++ /dev/null @@ -1,568 +0,0 @@ -/** - * @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 <sys/tree.h> -#include <rtems/score/basedefs.h> -#include <rtems/score/assert.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. - */ -/**@{*/ - -struct RBTree_Control; - -/** - * @brief Red-black tree node. - * - * This is used to manage each node (element) which is placed on a red-black - * tree. - */ -typedef struct RBTree_Node { - RB_ENTRY(RBTree_Node) Node; -} RBTree_Node; - -/** - * @brief Red-black tree control. - * - * This is used to manage a red-black tree. A red-black tree consists of a - * tree of zero or more nodes. - */ -typedef RB_HEAD(RBTree_Control, RBTree_Node) RBTree_Control; - -/** - * @brief Initializer for an empty red-black tree with designator @a name. - */ -#define RBTREE_INITIALIZER_EMPTY( name ) \ - RB_INITIALIZER( name ) - -/** - * @brief Definition for an empty red-black tree with designator @a name. - */ -#define RBTREE_DEFINE_EMPTY( name ) \ - RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name ) - -/** - * @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 ) -{ - RB_COLOR( the_node, Node ) = -1; -} - -/** - * @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 RB_COLOR( the_node, Node ) == -1; -} - -/** - * @brief Rebalances the red-black tree after insertion of the node. - * - * @param[in] the_rbtree The red-black tree control. - * @param[in] the_node The most recently inserted node. - */ -void _RBTree_Insert_color( - RBTree_Control *the_rbtree, - RBTree_Node *the_node -); - -/** - * @brief Initializes a red-black tree node. - * - * In debug configurations, the node is set off tree. In all other - * configurations, this function does nothing. - * - * @param[in] the_node The red-black tree node to initialize. - */ -RTEMS_INLINE_ROUTINE void _RBTree_Initialize_node( RBTree_Node *the_node ) -{ -#if defined(RTEMS_DEBUG) - _RBTree_Set_off_tree( the_node ); -#else - (void) the_node; -#endif -} - -/** - * @brief Adds a child node to a parent node. - * - * @param[in] child The child node. - * @param[in] parent The parent node. - * @param[in] link The child node link of the parent node. - */ -RTEMS_INLINE_ROUTINE void _RBTree_Add_child( - RBTree_Node *child, - RBTree_Node *parent, - RBTree_Node **link -) -{ - _Assert( _RBTree_Is_node_off_tree( child ) ); - RB_SET( child, parent, Node ); - *link = child; -} - -/** - * @brief Inserts the node into the red-black tree using the specified parent - * node and link. - * - * @param[in] the_rbtree The red-black tree control. - * @param[in] the_node The node to insert. - * @param[in] parent The parent node. - * @param[in] link The child node link of the parent node. - * - * @code - * #include <rtems/score/rbtree.h> - * - * typedef struct { - * int value; - * RBTree_Node Node; - * } Some_Node; - * - * bool _Some_Less( - * const RBTree_Node *a, - * const RBTree_Node *b - * ) - * { - * const Some_Node *aa = RTEMS_CONTAINER_OF( a, Some_Node, Node ); - * const Some_Node *bb = RTEMS_CONTAINER_OF( b, Some_Node, Node ); - * - * return aa->value < bb->value; - * } - * - * void _Some_Insert( - * RBTree_Control *the_rbtree, - * Some_Node *the_node - * ) - * { - * RBTree_Node **link = _RBTree_Root_reference( the_rbtree ); - * RBTree_Node *parent = NULL; - * - * while ( *link != NULL ) { - * parent = *link; - * - * if ( _Some_Less( &the_node->Node, parent ) ) { - * link = _RBTree_Left_reference( parent ); - * } else { - * link = _RBTree_Right_reference( parent ); - * } - * } - * - * _RBTree_Insert_with_parent( the_rbtree, &the_node->Node, parent, link ); - * } - * @endcode - */ -RTEMS_INLINE_ROUTINE void _RBTree_Insert_with_parent( - RBTree_Control *the_rbtree, - RBTree_Node *the_node, - RBTree_Node *parent, - RBTree_Node **link -) -{ - _RBTree_Add_child( the_node, parent, link ); - _RBTree_Insert_color( the_rbtree, the_node ); -} - -/** - * @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 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 RB_ROOT( the_rbtree ); -} - -/** - * @brief Returns a reference to the root pointer of the red-black tree. - */ -RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Root_reference( - RBTree_Control *the_rbtree -) -{ - return &RB_ROOT( the_rbtree ); -} - -/** - * @brief Returns a constant reference to the root pointer of the red-black tree. - */ -RTEMS_INLINE_ROUTINE RBTree_Node * const *_RBTree_Root_const_reference( - const RBTree_Control *the_rbtree -) -{ - return &RB_ROOT( the_rbtree ); -} - -/** - * @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 RB_PARENT( the_node, Node ); -} - -/** - * @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 RB_LEFT( the_node, Node ); -} - -/** - * @brief Returns a reference to the left child pointer of the red-black tree - * node. - */ -RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Left_reference( - RBTree_Node *the_node -) -{ - return &RB_LEFT( the_node, Node ); -} - -/** - * @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 RB_RIGHT( the_node, Node ); -} - -/** - * @brief Returns a reference to the right child pointer of the red-black tree - * node. - */ -RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Right_reference( - RBTree_Node *the_node -) -{ - return &RB_RIGHT( the_node, Node ); -} - -/** - * @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 RB_EMPTY( the_rbtree ); -} - -/** - * @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( the_node ) == NULL; -} - -/** - * @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 -) -{ - RB_INIT( the_rbtree ); -} - -/** - * @brief Initializes this red-black tree to contain exactly the specified - * node. - * - * @param[in] the_rbtree The red-black tree control. - * @param[in] the_node The one and only node. - */ -RTEMS_INLINE_ROUTINE void _RBTree_Initialize_one( - RBTree_Control *the_rbtree, - RBTree_Node *the_node -) -{ - _Assert( _RBTree_Is_node_off_tree( the_node ) ); - RB_ROOT( the_rbtree ) = the_node; - RB_PARENT( the_node, Node ) = NULL; - RB_LEFT( the_node, Node ) = NULL; - RB_RIGHT( the_node, Node ) = NULL; - RB_COLOR( the_node, Node ) = RB_BLACK; -} - -/** - * @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. - */ -RBTree_Node *_RBTree_Minimum( const RBTree_Control *the_rbtree ); - -/** - * @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. - */ -RBTree_Node *_RBTree_Maximum( const RBTree_Control *the_rbtree ); - -/** - * @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. - */ -RBTree_Node *_RBTree_Predecessor( const RBTree_Node *node ); - -/** - * @brief Returns the successor of a node. - * - * @param[in] node is the node. - * - * @retval NULL The successor does not exist. Otherwise the successor node. - */ -RBTree_Node *_RBTree_Successor( const RBTree_Node *node ); - -/** - * @brief Replaces a node in the red-black tree without a rebalance. - * - * @param[in] the_rbtree The red-black tree control. - * @param[in] victim The victim node. - * @param[in] replacement The replacement node. - */ -void _RBTree_Replace_node( - RBTree_Control *the_rbtree, - RBTree_Node *victim, - RBTree_Node *replacement -); - -/** - * @brief Inserts the node into the red-black tree. - * - * @param the_rbtree The red-black tree control. - * @param the_node The node to insert. - * @param key The key of the node to insert. This key must be equal to the key - * stored in the node to insert. The separate key parameter is provided for - * two reasons. Firstly, it allows to share the less operator with - * _RBTree_Find_inline(). Secondly, the compiler may generate better code if - * the key is stored in a local variable. - * @param less Must return true if the specified key is less than the key of - * the node, otherwise false. - * - * @retval true The inserted node is the new minimum node according to the - * specified less order function. - * @retval false Otherwise. - */ -RTEMS_INLINE_ROUTINE bool _RBTree_Insert_inline( - RBTree_Control *the_rbtree, - RBTree_Node *the_node, - const void *key, - bool ( *less )( const void *, const RBTree_Node * ) -) -{ - RBTree_Node **link; - RBTree_Node *parent; - bool is_new_minimum; - - link = _RBTree_Root_reference( the_rbtree ); - parent = NULL; - is_new_minimum = true; - - while ( *link != NULL ) { - parent = *link; - - if ( ( *less )( key, parent ) ) { - link = _RBTree_Left_reference( parent ); - } else { - link = _RBTree_Right_reference( parent ); - is_new_minimum = false; - } - } - - _RBTree_Add_child( the_node, parent, link ); - _RBTree_Insert_color( the_rbtree, the_node ); - return is_new_minimum; -} - -/** - * @brief Finds an object in the red-black tree with the specified key. - * - * @param the_rbtree The red-black tree control. - * @param key The key to look after. - * @param equal Must return true if the specified key equals the key of the - * node, otherwise false. - * @param less Must return true if the specified key is less than the key of - * the node, otherwise false. - * @param map In case a node with the specified key is found, then this - * function is called to map the node to the object returned. Usually it - * performs some offset operation via RTEMS_CONTAINER_OF() to map the node to - * its containing object. Thus, the return type is a void pointer and not a - * red-black tree node. - * - * @retval object An object with the specified key. - * @retval NULL No object with the specified key exists in the red-black tree. - */ -RTEMS_INLINE_ROUTINE void *_RBTree_Find_inline( - const RBTree_Control *the_rbtree, - const void *key, - bool ( *equal )( const void *, const RBTree_Node * ), - bool ( *less )( const void *, const RBTree_Node * ), - void *( *map )( RBTree_Node * ) -) -{ - RBTree_Node * const *link; - RBTree_Node *parent; - - link = _RBTree_Root_const_reference( the_rbtree ); - parent = NULL; - - while ( *link != NULL ) { - parent = *link; - - if ( ( *equal )( key, parent ) ) { - return ( *map )( parent ); - } else if ( ( *less )( key, parent ) ) { - link = _RBTree_Left_reference( parent ); - } else { - link = _RBTree_Right_reference( parent ); - } - } - - return NULL; -} - -/**@}*/ - -#ifdef __cplusplus -} -#endif - -#endif -/* end of include file */ |