diff options
Diffstat (limited to 'cpukit/score/inline/rtems/score/rbtree.inl')
| -rw-r--r-- | cpukit/score/inline/rtems/score/rbtree.inl | 266 |
1 files changed, 139 insertions, 127 deletions
diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl index 439b40a0ba..8b4234de57 100644 --- a/cpukit/score/inline/rtems/score/rbtree.inl +++ b/cpukit/score/inline/rtems/score/rbtree.inl @@ -1,12 +1,14 @@ /** - * @file rtems/score/rbtree.inl + * @file * - * This include file contains the bodies of the routines which are - * associated with Red-Black Trees and inlined. + * @brief Inlined Routines Associated with Red-Black Trees * - * @note The routines in this file are ordered from simple - * to complex. No other RBTree Handler routine is referenced - * unless it has already been defined. + * This include file contains the bodies of the routines which are + * associated with Red-Black Trees and inlined. + * + * @note The routines in this file are ordered from simple + * to complex. No other RBTree Handler routine is referenced + * unless it has already been defined. */ /* @@ -25,12 +27,12 @@ #define _RTEMS_SCORE_RBTREE_INL /** - * @addtogroup ScoreRBTree - * @{ + * @addtogroup ScoreRBTree */ +/**@{**/ /** - * @brief Get the direction opposite to @a the_dir + * @brief Get the direction opposite to @a the_dir. */ RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction( RBTree_Direction the_dir @@ -39,10 +41,11 @@ RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction( return (RBTree_Direction) !((int) the_dir); } -/** @brief Set off rbtree +/** + * @brief Set off RBtree. * - * This function sets the parent and child fields of the @a node to NULL - * indicating the @a node is not part of a rbtree. + * This function sets the parent and child fields of the @a node to NULL + * indicating the @a node is not part of a rbtree. * */ RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree( @@ -52,22 +55,29 @@ RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree( node->parent = node->child[RBT_LEFT] = node->child[RBT_RIGHT] = NULL; } -/** @brief Is the Node off RBTree +/** + * @brief Is the node off RBTree. * - * This function returns true if the @a node is not on a rbtree. A @a node is - * off rbtree if the parent and child fields are set to NULL. + * This function returns true if the @a node is not on a rbtree. A @a node is + * off rbtree if the parent and child fields are set to NULL. */ RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_rbtree( const RBTree_Node *node ) { - return (node->parent == NULL) && (node->child[RBT_LEFT] == NULL) && (node->child[RBT_RIGHT] == NULL); + return (node->parent == NULL) && + (node->child[RBT_LEFT] == NULL) && + (node->child[RBT_RIGHT] == NULL); } -/** @brief Are Two Nodes Equal +/** + * @brief Are two Nodes equal. + * + * This function returns true if @a left and @a right are equal, + * and false otherwise. * - * This function returns true if @a left and @a right are equal, - * and false otherwise. + * @retval true @a left and @a right are equal. + * @retval false @a left and @a right are not equal. */ RTEMS_INLINE_ROUTINE bool _RBTree_Are_nodes_equal( const RBTree_Node *left, @@ -77,9 +87,13 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Are_nodes_equal( return left == right; } -/** @brief Is this RBTree Control Pointer Null +/** + * @brief Is this RBTree control pointer NULL. * - * This function returns true if @a the_rbtree is NULL and false otherwise. + * This function returns true if @a the_rbtree is NULL and false otherwise. + * + * @retval true @a the_rbtree is @c NULL. + * @retval false @a the_rbtree is not @c NULL. */ RTEMS_INLINE_ROUTINE bool _RBTree_Is_null( const RBTree_Control *the_rbtree @@ -88,9 +102,13 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_null( return (the_rbtree == NULL); } -/** @brief Is the RBTree Node Pointer NULL +/** + * @brief Is the RBTree node pointer NUL. + * + * This function returns true if @a the_node is NULL and false otherwise. * - * This function returns true if @a the_node is NULL and false otherwise. + * @retval true @a the_node is @c NULL. + * @retval false @a the_node is not @c NULL. */ RTEMS_INLINE_ROUTINE bool _RBTree_Is_null_node( const RBTree_Node *the_node @@ -100,9 +118,10 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_null_node( } -/** @brief Return pointer to RBTree's root node +/** + * @brief Return pointer to RBTree's root node. * - * This function returns a pointer to the root node of @a the_rbtree. + * This function returns a pointer to the root node of @a the_rbtree. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root( const RBTree_Control *the_rbtree @@ -111,10 +130,11 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root( return the_rbtree->root; } -/** @brief Return pointer to RBTree's First node +/** + * @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). + * 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, @@ -124,9 +144,10 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First( return the_rbtree->first[dir]; } -/** @brief Return pointer to the parent of this node +/** + * @brief Return pointer to the parent of this node. * - * This function returns a pointer to the parent node of @a the_node. + * This function returns a pointer to the parent node of @a the_node. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent( const RBTree_Node *the_node @@ -136,13 +157,14 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent( return the_node->parent; } -/** @brief Return pointer to the left of this node +/** + * @brief Return pointer to the left of this node. * - * This function returns a pointer to the left node 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. + * @param[in] the_node is the node to be operated upon. * - * @return This method returns the left node on the rbtree. + * @return This method returns the left node on the rbtree. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left( const RBTree_Node *the_node @@ -151,13 +173,14 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left( return the_node->child[RBT_LEFT]; } -/** @brief Return pointer to the right of this node +/** + * @brief Return pointer to the right of this node. * - * This function returns a pointer to the right node 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. + * @param[in] the_node is the node to be operated upon. * - * @return This method returns the right node on the rbtree. + * @return This method returns the right node on the rbtree. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right( const RBTree_Node *the_node @@ -166,15 +189,16 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right( return the_node->child[RBT_RIGHT]; } -/** @brief Is the RBTree Empty +/** + * @brief Is the RBTree empty. * - * This function returns true if there are no nodes on @a the_rbtree and - * false otherwise. + * 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. + * @param[in] the_rbtree is the rbtree to be operated upon. * - * @return This function returns true if there are no nodes on - * @a the_rbtree and false otherwise. + * @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 @@ -183,11 +207,15 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty( return (the_rbtree->root == NULL); } -/** @brief Is this the First Node on the RBTree +/** + * @brief Is this the first node on the RBTree. * - * This function returns true if @a the_node is the first node on - * @a the_rbtree and false otherwise. @a dir specifies whether first means - * minimum (0) or maximum (1). + * This function returns true if @a the_node is the first node on + * @a the_rbtree and false otherwise. @a dir specifies whether first means + * minimum (0) or maximum (1). + * + * @retval true @a the_node is the first node on @a the_rbtree. + * @retval false @a the_node is not the first node on @a the_rbtree. * */ RTEMS_INLINE_ROUTINE bool _RBTree_Is_first( @@ -199,9 +227,13 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_first( return (the_node == _RBTree_First(the_rbtree, dir)); } -/** @brief Is this node red? +/** + * @brief Is this node red. + * + * This function returns true if @a the_node is red and false otherwise. * - * This function returns true if @a the_node is red and false otherwise. + * @retval true @a the_node is red. + * @retval false @a the_node in not red. */ RTEMS_INLINE_ROUTINE bool _RBTree_Is_red( const RBTree_Node *the_node @@ -211,24 +243,32 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_red( } -/** @brief Does this RBTree have only One Node +/** + * @brief Does this RBTree have only one node. * - * This function returns true if there is only one node on @a the_rbtree and - * false otherwise. + * This function returns true if there is only one node on @a the_rbtree and + * false otherwise. * + * @retval true @a the_rbtree has only one node. + * @retval false @a the_rbtree has more than one nodes. */ RTEMS_INLINE_ROUTINE bool _RBTree_Has_only_one_node( const RBTree_Control *the_rbtree ) { if(!the_rbtree) return false; /* TODO: expected behavior? */ - return (the_rbtree->root->child[RBT_LEFT] == NULL && the_rbtree->root->child[RBT_RIGHT] == NULL); + return (the_rbtree->root->child[RBT_LEFT] == NULL && + the_rbtree->root->child[RBT_RIGHT] == NULL); } -/** @brief Is this Node the RBTree root +/** + * @brief Is this node the RBTree root. * - * This function returns true if @a the_node is the root of @a the_rbtree and - * false otherwise. + * This function returns true if @a the_node is the root of @a the_rbtree and + * false otherwise. + * + * @retval true @a the_node is the root of @a the_rbtree. + * @retval false @a the_node is not the root of @a the_rbtree. */ RTEMS_INLINE_ROUTINE bool _RBTree_Is_root( const RBTree_Control *the_rbtree, @@ -238,9 +278,10 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_root( return (the_node == _RBTree_Root(the_rbtree)); } -/** @brief Initialize this RBTree as Empty +/** + * @brief Initialize this RBTree as empty. * - * This routine initializes @a the_rbtree to contain zero nodes. + * This routine initializes @a the_rbtree to contain zero nodes. */ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty( RBTree_Control *the_rbtree, @@ -256,11 +297,11 @@ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty( the_rbtree->is_unique = is_unique; } -/** @brief Return a pointer to node's grandparent +/** + * @brief Return a pointer to node's grandparent. * - * This function returns a pointer to the grandparent of @a the_node if it - * exists, and NULL if not. - * + * This function returns a pointer to the grandparent of @a the_node if it + * exists, and NULL if not. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Grandparent( const RBTree_Node *the_node @@ -273,10 +314,11 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Grandparent( return(the_node->parent->parent); } -/** @brief Return a pointer to node's sibling +/** + * @brief Return a pointer to node's sibling. * - * This function returns a pointer to the sibling of @a the_node if it - * exists, and NULL if not. + * This function returns a pointer to the sibling of @a the_node if it + * exists, and NULL if not. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling( const RBTree_Node *the_node @@ -292,10 +334,11 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling( return the_node->parent->child[RBT_LEFT]; } -/** @brief Return a pointer to node's parent's sibling +/** + * @brief Return a pointer to node's parent's sibling. * - * This function returns a pointer to the sibling of the parent of - * @a the_node if it exists, and NULL if not. + * This function returns a pointer to the sibling of the parent of + * @a the_node if it exists, and NULL if not. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling( const RBTree_Node *the_node @@ -307,10 +350,11 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling( return _RBTree_Sibling(the_node->parent); } -/** @brief Find the RBTree_Control header given a node in the tree +/** + * @brief Find the RBTree_Control header given a node in the tree. * - * This function returns a pointer to the header of the Red Black - * Tree containing @a the_node if it exists, and NULL if not. + * This function returns a pointer to the header of the Red Black + * Tree containing @a the_node if it exists, and NULL if not. */ RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header_unprotected( RBTree_Node *the_node @@ -341,47 +385,13 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser( return compare_result < 0; } -/** @brief Find the node with given key in the tree - * - * This function returns a pointer to the node in @a the_rbtree - * having key equal to key of @a the_node if it exists, - * and NULL if not. @a the_node has to be made up before a search. - * - * @note If the tree is not unique and contains duplicate keys, the set - * of duplicate keys acts as FIFO. - */ -RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected( - RBTree_Control *the_rbtree, - RBTree_Node *the_node - ) -{ - RBTree_Node* iter_node = the_rbtree->root; - RBTree_Node* found = NULL; - int compare_result; - while (iter_node) { - compare_result = the_rbtree->compare_function(the_node, iter_node); - if ( _RBTree_Is_equal( compare_result ) ) { - found = iter_node; - if ( the_rbtree->is_unique ) - break; - } - - RBTree_Direction dir = - (RBTree_Direction) _RBTree_Is_greater( compare_result ); - iter_node = iter_node->child[dir]; - } /* while(iter_node) */ - - return found; -} - /** * @brief Returns the predecessor of a node. * - * @param[in] rbtree The red-black tree. - * @param[in] node The node. + * @param[in] node is the node. * - * @retval NULL The predecessor does not exist. - * @retval otherwise The predecessor node. + * @retval NULL The predecessor does not exist. Otherwise it returns + * the predecessor node. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor_unprotected( const RBTree_Node *node @@ -405,11 +415,9 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor( /** * @brief Returns the successor of a node. * - * @param[in] rbtree The red-black tree. - * @param[in] node The node. + * @param[in] node is the node. * - * @retval NULL The successor does not exist. - * @retval otherwise The successor node. + * @retval NULL The successor does not exist. Otherwise the successor node. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor_unprotected( const RBTree_Node *node @@ -430,18 +438,19 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor( return _RBTree_Next( node, RBT_RIGHT ); } -/** @brief Get the First Node (unprotected) +/** + * @brief Get the first node (unprotected). * - * This function removes the minimum or maximum node from the_rbtree and - * returns a pointer to that node. It does NOT disable interrupts to ensure - * the atomicity of the get operation. + * This function removes the minimum or maximum node from the_rbtree and + * returns a pointer to that node. It does NOT disable interrupts to ensure + * the atomicity of the get operation. * - * @param[in] the_rbtree is the rbtree to attempt to get the min node from. - * @param[in] dir specifies whether to get minimum (0) or maximum (1) + * @param[in] the_rbtree is the rbtree to attempt to get the min node from. + * @param[in] dir specifies whether to get minimum (0) or maximum (1) * - * @return This method returns the min or max node on the rbtree, or NULL. + * @return This method returns the min or max node on the rbtree, or NULL. * - * @note This routine may return NULL if the RBTree is empty. + * @note This routine may return NULL if the RBTree is empty. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get_unprotected( RBTree_Control *the_rbtree, @@ -453,10 +462,11 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get_unprotected( return the_node; } -/** @brief Rotate the_node in the direction passed as second argument - * - * This routine rotates @a the_node to the direction @a dir, swapping - * @a the_node with its child\[@a dir\]. +/** + * @brief Rotate the_node in the direction passed as second argument. + * + * This routine rotates @a the_node to the direction @a dir, swapping + * @a the_node with its child\[@a dir\]. */ RTEMS_INLINE_ROUTINE void _RBTree_Rotate( RBTree_Node *the_node, @@ -481,7 +491,8 @@ RTEMS_INLINE_ROUTINE void _RBTree_Rotate( the_node->parent = c; } -/** @brief Determines whether the tree is unique +/** + * @brief Determines whether the tree is unique. */ RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique( const RBTree_Control *the_rbtree @@ -489,7 +500,8 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique( { return( the_rbtree && the_rbtree->is_unique ); } -/**@}*/ + +/** @} */ #endif /* end of include file */ |