diff options
Diffstat (limited to 'cpukit/score/inline/rtems/score/rbtree.inl')
| -rw-r--r-- | cpukit/score/inline/rtems/score/rbtree.inl | 222 |
1 files changed, 134 insertions, 88 deletions
diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl index e25e3df289..dfa8c265fa 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,13 @@ #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 +42,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,10 +56,11 @@ 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 @@ -64,10 +69,14 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_rbtree( 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 +86,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 +101,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 +117,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 +129,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 +143,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 +156,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 +172,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 +188,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 +206,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 +226,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,11 +242,14 @@ 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 @@ -225,10 +259,14 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Has_only_one_node( 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 +276,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 +295,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 +312,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 +332,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 +348,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 @@ -344,8 +386,8 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser( /** * @brief Returns the predecessor of a node. * - * @param[in] rbtree The red-black tree. - * @param[in] node The node. + * @param[in] rbtree is the red-black tree. + * @param[in] node is the node. * * @retval NULL The predecessor does not exist. * @retval otherwise The predecessor node. @@ -372,8 +414,8 @@ 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] rbtree is the red-black tree. + * @param[in] node is the node. * * @retval NULL The successor does not exist. * @retval otherwise The successor node. @@ -397,18 +439,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, @@ -420,10 +463,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, @@ -448,7 +492,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 @@ -456,7 +501,8 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique( { return( the_rbtree && the_rbtree->is_unique ); } -/**@}*/ + +/** @} */ #endif /* end of include file */ |