diff options
author | Joel Sherrill <joel.sherrill@OARcorp.com> | 2011-04-04 18:44:16 +0000 |
---|---|---|
committer | Joel Sherrill <joel.sherrill@OARcorp.com> | 2011-04-04 18:44:16 +0000 |
commit | bd9baa8184e8ff78b6644e8d88817a3ac8ec67fe (patch) | |
tree | 626eb6aa1a8779330e88e16987c6f25c226507f6 /cpukit/score/inline/rtems/score/rbtree.inl | |
parent | 2011-04-04 Sebastien Bourdeauducq <sebastien.bourdeauducq@gmail.com> (diff) | |
download | rtems-bd9baa8184e8ff78b6644e8d88817a3ac8ec67fe.tar.bz2 |
2010-07-28 Gedare Bloom <giddyup44@yahoo.com>
PR 1641/cpukit
* sapi/Makefile.am, sapi/preinstall.am, score/Makefile.am,
score/preinstall.am: Add Red Black Tree data structure to score.
* sapi/include/rtems/rbtree.h, sapi/inline/rtems/rbtree.inl,
score/include/rtems/score/rbtree.h, score/inline/rtems/score/rbtree.inl,
score/src/rbtree.c, score/src/rbtreeextract.c,
score/src/rbtreefind.c, score/src/rbtreefindheader.c,
score/src/rbtreeget.c, score/src/rbtreeinsert.c,
score/src/rbtreepeek.c: New files.
Diffstat (limited to 'cpukit/score/inline/rtems/score/rbtree.inl')
-rw-r--r-- | cpukit/score/inline/rtems/score/rbtree.inl | 442 |
1 files changed, 442 insertions, 0 deletions
diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl new file mode 100644 index 0000000000..097cede027 --- /dev/null +++ b/cpukit/score/inline/rtems/score/rbtree.inl @@ -0,0 +1,442 @@ +/** + * @file rtems/score/rbtree.inl + * + * 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. + */ + +/* + * 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 +# error "Never use <rtems/score/rbtree.inl> directly; include <rtems/score/rbtree.h> instead." +#endif + +#ifndef _RTEMS_SCORE_RBTREE_INL +#define _RTEMS_SCORE_RBTREE_INL + +/** + * @addtogroup ScoreRBTree + * @{ + */ + +/** @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. + * + */ +RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree( + RBTree_Node *node + ) +{ + node->parent = node->child[RBT_LEFT] = node->child[RBT_RIGHT] = NULL; +} + +/** @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. + */ +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); +} + +/** @brief Are Two Nodes Equal + * + * This function returns true if @a left and @a right are equal, + * and false otherwise. + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Are_nodes_equal( + const RBTree_Node *left, + const RBTree_Node *right + ) +{ + return left == right; +} + +/** @brief Is this RBTree Control Pointer Null + * + * This function returns true if @a the_rbtree is NULL and false otherwise. + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_null( + const RBTree_Control *the_rbtree + ) +{ + return (the_rbtree == NULL); +} + +/** @brief Is the RBTree Node Pointer NULL + * + * This function returns true if @a the_node is NULL and false otherwise. + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_null_node( + const RBTree_Node *the_node + ) +{ + return (the_node == NULL); +} + + +/** @brief Return pointer to RBTree's root node + * + * This function returns a pointer to the root node of @a the_rbtree. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root( + 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( + RBTree_Control *the_rbtree, + RBTree_Direction dir + ) +{ + return the_rbtree->first[dir]; +} + +/** @brief Return pointer to the parent of this node + * + * This function returns a pointer to the parent node of @a the_node. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent( + RBTree_Node *the_node + ) +{ + if (!the_node->parent->parent) return NULL; + 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( + 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( + 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. + * + * @return This function returns true if there are no nodes on + * @a the_rbtree and false otherwise. + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty( + RBTree_Control *the_rbtree + ) +{ + return (the_rbtree->root == NULL); +} + +/** @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). + * + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_first( + RBTree_Control *the_rbtree, + const RBTree_Node *the_node, + RBTree_Direction dir + ) +{ + return (the_node == _RBTree_First(the_rbtree, dir)); +} + +/** @brief Is this node red? + * + * This function returns true if @a the_node is red and false otherwise. + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_red( + const RBTree_Node *the_node + ) +{ + return (the_node && the_node->color == RBT_RED); +} + + +/** @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. + * + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Has_only_one_node( + const RBTree_Control *the_rbtree + ) +{ + if(!the_rbtree) return NULL; /* TODO: expected behavior? */ + return (the_rbtree->root->child[RBT_LEFT] == NULL && the_rbtree->root->child[RBT_RIGHT] == NULL); +} + +/** @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. + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_root( + RBTree_Control *the_rbtree, + const RBTree_Node *the_node + ) +{ + return (the_node == _RBTree_Root(the_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[0] = NULL; + the_rbtree->first[1] = NULL; +} + +/** @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. + * + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Grandparent( + RBTree_Node *the_node + ) +{ + if(!the_node) return NULL; + if(!(the_node->parent)) return NULL; + if(!(the_node->parent->parent)) return NULL; + if(!(the_node->parent->parent->parent)) return NULL; + return(the_node->parent->parent); +} + +/** @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. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling( + RBTree_Node *the_node + ) +{ + if(!the_node) return NULL; + if(!(the_node->parent)) return NULL; + if(!(the_node->parent->parent)) return NULL; + + if(the_node == the_node->parent->child[RBT_LEFT]) + return the_node->parent->child[RBT_RIGHT]; + else + return the_node->parent->child[RBT_LEFT]; +} + +/** @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. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling( + RBTree_Node *the_node + ) +{ + if(!the_node) return NULL; + if(_RBTree_Grandparent(the_node) == NULL) return NULL; + + return _RBTree_Sibling(the_node->parent); +} + +/** @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. + */ +RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header_unprotected( + RBTree_Node *the_node + ) +{ + if(!the_node) return NULL; + if(!(the_node->parent)) return NULL; + while(the_node->parent) the_node = the_node->parent; + return (RBTree_Control*)the_node; +} + +/** @brief Find the node with given value in the tree + * + * This function returns a pointer to the node in @a the_rbtree + * having value equal to @a the_value if it exists, and NULL if not. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected( + RBTree_Control *the_rbtree, + unsigned int the_value + ) +{ + RBTree_Node* iter_node = the_rbtree->root; + while (iter_node) { + if (the_value == iter_node->value) return(iter_node); + + RBTree_Direction dir = the_value > iter_node->value; + iter_node = iter_node->child[dir]; + } /* while(iter_node) */ + + return 0; +} + +/** @brief Find the nodes in-order predecessor + * + * This function returns a pointer to the in-order predecessor + * of @a the_node if it exists, and NULL if not. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor( + RBTree_Node *the_node + ) +{ + RBTree_Node* iter_node; + if (!the_node) return NULL; + iter_node = the_node->child[RBT_LEFT]; + if (!iter_node) return NULL; + while (iter_node->child[RBT_RIGHT]) { + iter_node = iter_node->child[RBT_RIGHT]; + } + return iter_node; +} + +/** @brief Find the nodes in-order successor + * + * This function returns a pointer to the in-order successor + * of @a the_node if it exists, and NULL if not. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor( + RBTree_Node *the_node + ) +{ + RBTree_Node* iter_node; + if (!the_node) return NULL; + iter_node = the_node->child[RBT_RIGHT]; + if (!iter_node) return NULL; + while (iter_node->child[RBT_LEFT]) { + iter_node = iter_node->child[RBT_LEFT]; + } + return iter_node; +} + +/** @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. + * + * @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. + * + * @note This routine may return NULL if the RBTree is empty. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get_unprotected( + RBTree_Control *the_rbtree, + RBTree_Direction dir + ) +{ + RBTree_Node *the_node = the_rbtree->first[dir]; + _RBTree_Extract_unprotected(the_rbtree, the_node); + return the_node; +} + +/** @brief Peek at the First Node (unprotected) + * + * This function returns a pointer to the first node, minimum if @a dir is 0 + * or maximum if @a dir is 1, from @a the_rbtree without extracting it. + * It does NOT disable interrupts to ensure the atomicity of the peek. + * + * @retval NULL if @a the_rbtree is empty. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Peek_unprotected( + RBTree_Control *the_rbtree, + RBTree_Direction dir + ) +{ + return(the_rbtree->first[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, + RBTree_Direction dir + ) +{ + RBTree_Node *c; + if (the_node == NULL) return; + if (the_node->child[(1-dir)] == NULL) return; + + + c = the_node->child[(1-dir)]; + the_node->child[(1-dir)] = c->child[dir]; + + if (c->child[dir]) + c->child[dir]->parent = the_node; + + c->child[dir] = the_node; + + the_node->parent->child[the_node != the_node->parent->child[0]] = c; + + c->parent = the_node->parent; + the_node->parent = c; +} +/**@}*/ + +#endif +/* end of include file */ |