[PATCH] rbtree: Formatting.
Gedare Bloom
gedare at rtems.org
Sun May 13 17:39:56 UTC 2012
Fix formatting in red-black tree code to make it more consistent with
the style of other supercore code.
---
cpukit/score/include/rtems/score/rbtree.h | 74 ++++++------
cpukit/score/inline/rtems/score/rbtree.inl | 176 ++++++++++++----------------
cpukit/score/src/rbtree.c | 26 +---
cpukit/score/src/rbtreeextract.c | 139 +++++++++++------------
cpukit/score/src/rbtreefind.c | 57 ++++++----
cpukit/score/src/rbtreefindheader.c | 34 ++----
cpukit/score/src/rbtreeget.c | 36 ++----
cpukit/score/src/rbtreeinsert.c | 107 +++++++----------
8 files changed, 282 insertions(+), 367 deletions(-)
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index 82bdb6d..271e2fa 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -186,9 +186,16 @@ RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name)
/**
* @brief Initialize a RBTree Header
*
- * This routine initializes @a the_rbtree structure to manage the
+ * This routine initializes a red-black tree to manage the
* contiguous array of @a number_nodes nodes which starts at
- * @a starting_address. Each node is of @a node_size bytes.
+ * @a starting_address. Each node is of @a node_size bytes.
+ *
+ * @param[in] the_rbtree The red-black tree.
+ * @param[in] compare_function Node comparison handler.
+ * @param[in] starting_address Base of array of nodes.
+ * @param[in] number_nodes Count of nodes in array.
+ * @param[in] node_size Size of each node.
+ * @param[in] is_unique True if nodes with the same key are not allowed.
*/
void _RBTree_Initialize(
RBTree_Control *the_rbtree,
@@ -217,12 +224,22 @@ RBTree_Node *_RBTree_Get(
RBTree_Direction dir
);
+/** @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.
+ * If the tree is stable duplicate keys act as FIFO.
+ */
+RBTree_Node *_RBTree_Find_unprotected(
+ RBTree_Control *the_rbtree,
+ RBTree_Node *the_node
+);
+
/**
- * @brief Find the node with given key in the tree
+ * @copydoc _RBTree_Find_unprotected()
*
- * This function returns a pointer to the node with key equal to a key
- * of @a the_node if it exists in the Red-Black Tree @a the_rbtree,
- * and NULL if not.
+ * This function disables interrupts to protect the operation.
*/
RBTree_Node *_RBTree_Find(
RBTree_Control *the_rbtree,
@@ -240,17 +257,15 @@ RBTree_Control *_RBTree_Find_header(
);
/**
- * @brief Insert a Node (unprotected)
+ * @brief Inserts a node into a red-black tree.
*
- * This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
+ * @param[in] the_rbtree The red-black tree.
+ * @param[in] the_node The node to insert.
*
- * @retval 0 Successfully inserted.
- * @retval -1 NULL @a the_node.
- * @retval RBTree_Node* if one with equal value to @a the_node 's key exists
- * in an unique @a the_rbtree.
- *
- * @note It does NOT disable interrupts to ensure the atomicity
- * of the extract operation.
+ * @retval 0 if successfully inserted.
+ * @retval a node that compares equal to @a the_node if it exists and
+ * the_rbtree->is_unique is true
+ * @retval -1 otherwise.
*/
RBTree_Node *_RBTree_Insert_unprotected(
RBTree_Control *the_rbtree,
@@ -258,31 +273,20 @@ RBTree_Node *_RBTree_Insert_unprotected(
);
/**
- * @brief Insert a node on a rbtree
- *
- * This routine inserts @a the_node on the 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 's key exists
- * in an unique @a the_rbtree.
+ * @copydoc _RBTree_Insert_unprotected()
*
- * @note It disables interrupts to ensure the atomicity
- * of the extract operation.
+ * This function disables interrupts to protect the operation.
*/
RBTree_Node *_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.
+ * @brief Extracts (removes) a node from a red-black tree.
*
- * @note It does NOT disable interrupts to ensure the atomicity
- * of the extract operation.
+ * @param[in] the_rbtree The red-black tree.
+ * @param[in] the_node The node to extract.
*/
void _RBTree_Extract_unprotected(
RBTree_Control *the_rbtree,
@@ -290,12 +294,9 @@ void _RBTree_Extract_unprotected(
);
/**
- * @brief Delete a node from the rbtree
- *
- * This routine deletes @a the_node from @a the_rbtree.
+ * @copydoc _RBTree_Extract_unprotected()
*
- * @note It disables interrupts to ensure the atomicity of the
- * append operation.
+ * This function disables interrupts to protect the operation.
*/
void _RBTree_Extract(
RBTree_Control *the_rbtree,
@@ -370,4 +371,3 @@ void _RBTree_Iterate_unprotected(
/**@}*/
#endif
-/* end of include file */
diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl
index c5187a0..a183668 100644
--- a/cpukit/score/inline/rtems/score/rbtree.inl
+++ b/cpukit/score/inline/rtems/score/rbtree.inl
@@ -46,8 +46,8 @@ RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction(
*
*/
RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree(
- RBTree_Node *node
- )
+ RBTree_Node *node
+)
{
node->parent = node->child[RBT_LEFT] = node->child[RBT_RIGHT] = NULL;
}
@@ -58,10 +58,10 @@ RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree(
* 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
- )
+ const RBTree_Node *node
+)
{
- return (node->parent == NULL) && (node->child[RBT_LEFT] == NULL) && (node->child[RBT_RIGHT] == NULL);
+ return !node->parent && !node->child[RBT_LEFT] && !node->child[RBT_RIGHT];
}
/** @brief Are Two Nodes Equal
@@ -70,9 +70,9 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_rbtree(
* and false otherwise.
*/
RTEMS_INLINE_ROUTINE bool _RBTree_Are_nodes_equal(
- const RBTree_Node *left,
- const RBTree_Node *right
- )
+ const RBTree_Node *left,
+ const RBTree_Node *right
+)
{
return left == right;
}
@@ -82,10 +82,10 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Are_nodes_equal(
* 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
- )
+ const RBTree_Control *the_rbtree
+)
{
- return (the_rbtree == NULL);
+ return the_rbtree == NULL;
}
/** @brief Is the RBTree Node Pointer NULL
@@ -93,13 +93,12 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_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
- )
+ const RBTree_Node *the_node
+)
{
- return (the_node == NULL);
+ 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.
@@ -132,7 +131,9 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
const RBTree_Node *the_node
)
{
- if (!the_node->parent->parent) return NULL;
+ if ( !the_node->parent->parent ) {
+ return NULL;
+ }
return the_node->parent;
}
@@ -180,7 +181,7 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
const RBTree_Control *the_rbtree
)
{
- return (the_rbtree->root == NULL);
+ return the_rbtree->root == NULL;
}
/** @brief Is this the First Node on the RBTree
@@ -188,7 +189,6 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
* 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(
const RBTree_Control *the_rbtree,
@@ -196,7 +196,7 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_first(
RBTree_Direction dir
)
{
- return (the_node == _RBTree_First(the_rbtree, dir));
+ return the_node == _RBTree_First(the_rbtree, dir);
}
/** @brief Is this node red?
@@ -204,10 +204,10 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_first(
* 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
- )
+ const RBTree_Node *the_node
+)
{
- return (the_node && the_node->color == RBT_RED);
+ return the_node && the_node->color == RBT_RED;
}
@@ -215,14 +215,16 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_red(
*
* 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
- )
+ 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);
+ RBTree_Node *root = the_rbtree->root;
+ if ( !the_rbtree || !root ) {
+ return false;
+ }
+ return !root->child[RBT_LEFT] && !root->child[RBT_RIGHT];
}
/** @brief Is this Node the RBTree root
@@ -235,7 +237,7 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
const RBTree_Node *the_node
)
{
- return (the_node == _RBTree_Root(the_rbtree));
+ return the_node == _RBTree_Root(the_rbtree);
}
/** @brief Initialize this RBTree as Empty
@@ -243,10 +245,10 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
* This routine initializes @a the_rbtree to contain zero nodes.
*/
RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
- RBTree_Control *the_rbtree,
- RBTree_Compare_function compare_function,
- bool is_unique
- )
+ RBTree_Control *the_rbtree,
+ RBTree_Compare_function compare_function,
+ bool is_unique
+)
{
the_rbtree->permanent_null = NULL;
the_rbtree->root = NULL;
@@ -260,17 +262,15 @@ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
*
* 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
)
{
- 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);
+ RBTree_Node *p, *g;
+ p = _RBTree_Parent( the_node );
+ g = _RBTree_Parent( p );
+ return g;
}
/** @brief Return a pointer to node's sibling
@@ -282,11 +282,12 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling(
const RBTree_Node *the_node
)
{
- if(!the_node) return NULL;
- if(!(the_node->parent)) return NULL;
- if(!(the_node->parent->parent)) return NULL;
+ RBTree_Node *p = _RBTree_Parent( the_node );
+ if ( !p ) {
+ return NULL;
+ }
- if(the_node == the_node->parent->child[RBT_LEFT])
+ if ( the_node == the_node->parent->child[RBT_LEFT] )
return the_node->parent->child[RBT_RIGHT];
else
return the_node->parent->child[RBT_LEFT];
@@ -301,10 +302,9 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling(
const RBTree_Node *the_node
)
{
- if(!the_node) return NULL;
- if(_RBTree_Grandparent(the_node) == NULL) return NULL;
+ RBTree_Node *p = _RBTree_Parent( the_node );
- return _RBTree_Sibling(the_node->parent);
+ return _RBTree_Sibling( p );
}
/** @brief Find the RBTree_Control header given a node in the tree
@@ -313,13 +313,17 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling(
* 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
- )
+ 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;
+ RBTree_Node *p;
+ if ( !the_node ) {
+ return NULL;
+ }
+ while ( ( p = _RBTree_Parent(the_node) ) ) {
+ the_node = p;
+ }
+ return (RBTree_Control*) the_node->parent;
}
RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal( int compare_result )
@@ -327,53 +331,16 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal( int compare_result )
return compare_result == 0;
}
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_greater(
- int compare_result
-)
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_greater( int compare_result )
{
return compare_result > 0;
}
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
- int compare_result
-)
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser( int compare_result )
{
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.
*
@@ -444,12 +411,12 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
* @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_Control *the_rbtree,
+ RBTree_Direction dir
+)
{
RBTree_Node *the_node = the_rbtree->first[dir];
- _RBTree_Extract_unprotected(the_rbtree, the_node);
+ _RBTree_Extract_unprotected( the_rbtree, the_node );
return the_node;
}
@@ -459,19 +426,24 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get_unprotected(
* @a the_node with its child\[@a dir\].
*/
RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
- RBTree_Node *the_node,
- RBTree_Direction dir
- )
+ RBTree_Node *the_node,
+ RBTree_Direction dir
+)
{
RBTree_Node *c;
- if (the_node == NULL) return;
- if (the_node->child[_RBTree_Opposite_direction(dir)] == NULL) return;
+ if ( !the_node ) {
+ return;
+ }
+ if ( !the_node->child[_RBTree_Opposite_direction(dir)] ) {
+ return;
+ }
c = the_node->child[_RBTree_Opposite_direction(dir)];
the_node->child[_RBTree_Opposite_direction(dir)] = c->child[dir];
- if (c->child[dir])
+ if ( c->child[dir] ) {
c->child[dir]->parent = the_node;
+ }
c->child[dir] = the_node;
@@ -487,9 +459,9 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique(
const RBTree_Control *the_rbtree
)
{
- return( the_rbtree && the_rbtree->is_unique );
+ return the_rbtree && the_rbtree->is_unique;
}
+
/**@}*/
#endif
-/* end of include file */
diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c
index 48ea2a0..a953d7d 100644
--- a/cpukit/score/src/rbtree.c
+++ b/cpukit/score/src/rbtree.c
@@ -15,20 +15,6 @@
#include <rtems/score/rbtree.h>
#include <rtems/score/isr.h>
-/*
- * _RBTree_Initialize
- *
- * This kernel routine initializes a Red-Black Tree.
- *
- * Input parameters:
- * the_rbtree - pointer to rbtree header
- * starting_address - starting address of first node
- * number_nodes - number of nodes in rbtree
- * node_size - size of node in bytes
- *
- * Output parameters: NONE
- */
-
void _RBTree_Initialize(
RBTree_Control *the_rbtree,
RBTree_Compare_function compare_function,
@@ -41,17 +27,17 @@ void _RBTree_Initialize(
size_t count;
RBTree_Node *next;
- /* TODO: Error message? */
- if (!the_rbtree) return;
+ if ( !the_rbtree ) {
+ return;
+ }
/* could do sanity checks here */
- _RBTree_Initialize_empty(the_rbtree, compare_function, is_unique);
+ _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique );
count = number_nodes;
next = starting_address;
while ( count-- ) {
- _RBTree_Insert_unprotected(the_rbtree, next);
- next = (RBTree_Node *)
- _Addresses_Add_offset( (void *) next, node_size );
+ _RBTree_Insert_unprotected( the_rbtree, next );
+ next = (RBTree_Node *) _Addresses_Add_offset( (void *) next, node_size );
}
}
diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
index 3079f10..336d3ba 100644
--- a/cpukit/score/src/rbtreeextract.c
+++ b/cpukit/score/src/rbtreeextract.c
@@ -1,5 +1,12 @@
+/**
+ *
+ * @ingroup ScoreRBTree
+ *
+ * @brief _RBTree_Extract_unprotected and _RBTree_Extract
+ */
+
/*
- * Copyright (c) 2010 Gedare Bloom.
+ * Copyright (c) 2010-2012 Gedare Bloom.
*
* The license and distribution terms for this file may be
* found in the file LICENSE in this distribution or at
@@ -10,58 +17,56 @@
#include "config.h"
#endif
-#include <rtems/system.h>
-#include <rtems/score/address.h>
#include <rtems/score/rbtree.h>
#include <rtems/score/isr.h>
-/** @brief Validate and fix-up tree properties after deleting a node
- *
- * This routine is called on a black node, @a the_node, after its deletion.
- * This function maintains the properties of the red-black tree.
+/*
+ * Validate and fix-up tree properties after deleting a node
*
- * @note It does NOT disable interrupts to ensure the atomicity
- * of the extract operation.
+ * This routine is called on a black node, the_node, after its deletion.
+ * This function maintains the properties of the red-black tree.
*/
-static void _RBTree_Extract_validate_unprotected(
- RBTree_Node *the_node
- )
+static void _RBTree_Extract_validate(
+ RBTree_Node *the_node
+)
{
RBTree_Node *parent, *sibling;
RBTree_Direction dir;
parent = the_node->parent;
- if(!parent->parent) return;
+ if( !parent->parent ) {
+ return;
+ }
sibling = _RBTree_Sibling(the_node);
/* continue to correct tree as long as the_node is black and not the root */
- while (!_RBTree_Is_red(the_node) && parent->parent) {
-
+ while ( !_RBTree_Is_red( the_node ) && parent->parent ) {
/* if sibling is red, switch parent (black) and sibling colors,
* then rotate parent left, making the sibling be the_node's grandparent.
* Now the_node has a black sibling and red parent. After rotation,
* update sibling pointer.
*/
- if (_RBTree_Is_red(sibling)) {
+ if ( _RBTree_Is_red( sibling ) ) {
parent->color = RBT_RED;
sibling->color = RBT_BLACK;
dir = the_node != parent->child[0];
- _RBTree_Rotate(parent, dir);
- sibling = parent->child[_RBTree_Opposite_direction(dir)];
+ _RBTree_Rotate( parent, dir );
+ sibling = parent->child[_RBTree_Opposite_direction( dir )];
}
/* sibling is black, see if both of its children are also black. */
- if (!_RBTree_Is_red(sibling->child[RBT_RIGHT]) &&
- !_RBTree_Is_red(sibling->child[RBT_LEFT])) {
+ if ( !_RBTree_Is_red( sibling->child[RBT_RIGHT] )
+ && !_RBTree_Is_red( sibling->child[RBT_LEFT] )
+ ) {
sibling->color = RBT_RED;
- if (_RBTree_Is_red(parent)) {
+ if ( _RBTree_Is_red( parent ) ) {
parent->color = RBT_BLACK;
break;
}
the_node = parent; /* done if parent is red */
parent = the_node->parent;
- sibling = _RBTree_Sibling(the_node);
+ sibling = _RBTree_Sibling( the_node );
} else {
/* at least one of sibling's children is red. we now proceed in two
* cases, either the_node is to the left or the right of the parent.
@@ -70,52 +75,51 @@ static void _RBTree_Extract_validate_unprotected(
* Then switch the sibling and parent colors, and rotate through parent.
*/
dir = the_node != parent->child[0];
- if (!_RBTree_Is_red(sibling->child[_RBTree_Opposite_direction(dir)])) {
+ if (
+ !_RBTree_Is_red( sibling->child[_RBTree_Opposite_direction( dir )] )
+ ) {
sibling->color = RBT_RED;
sibling->child[dir]->color = RBT_BLACK;
- _RBTree_Rotate(sibling, _RBTree_Opposite_direction(dir));
- sibling = parent->child[_RBTree_Opposite_direction(dir)];
+ _RBTree_Rotate( sibling, _RBTree_Opposite_direction( dir ) );
+ sibling = parent->child[_RBTree_Opposite_direction( dir )];
}
sibling->color = parent->color;
parent->color = RBT_BLACK;
- sibling->child[_RBTree_Opposite_direction(dir)]->color = RBT_BLACK;
- _RBTree_Rotate(parent, dir);
+ sibling->child[_RBTree_Opposite_direction( dir )]->color = RBT_BLACK;
+ _RBTree_Rotate( parent, dir );
break; /* done */
}
} /* while */
- if(!the_node->parent->parent) the_node->color = RBT_BLACK;
+ if ( !the_node->parent->parent ) {
+ the_node->color = RBT_BLACK;
+ }
}
-/** @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
- )
+ RBTree_Control *the_rbtree,
+ RBTree_Node *the_node
+)
{
RBTree_Node *leaf, *target;
RBTree_Color victim_color;
RBTree_Direction dir;
- if (!the_node) return;
+ if ( !the_node ) {
+ return;
+ }
/* check if min needs to be updated */
- if (the_node == the_rbtree->first[RBT_LEFT]) {
+ if ( the_node == the_rbtree->first[RBT_LEFT] ) {
RBTree_Node *next;
- next = _RBTree_Successor_unprotected(the_node);
+ next = _RBTree_Successor_unprotected( the_node );
the_rbtree->first[RBT_LEFT] = next;
}
/* Check if max needs to be updated. min=max for 1 element trees so
* do not use else if here. */
- if (the_node == the_rbtree->first[RBT_RIGHT]) {
+ if ( the_node == the_rbtree->first[RBT_RIGHT] ) {
RBTree_Node *previous;
- previous = _RBTree_Predecessor_unprotected(the_node);
+ previous = _RBTree_Predecessor_unprotected( the_node );
the_rbtree->first[RBT_RIGHT] = previous;
}
@@ -125,10 +129,11 @@ void _RBTree_Extract_unprotected(
* and replace the_node with the target node. This maintains the binary
* search tree property, but may violate the red-black properties.
*/
-
- if (the_node->child[RBT_LEFT] && the_node->child[RBT_RIGHT]) {
+ if ( the_node->child[RBT_LEFT] && the_node->child[RBT_RIGHT] ) {
target = the_node->child[RBT_LEFT]; /* find max in node->child[RBT_LEFT] */
- while (target->child[RBT_RIGHT]) target = target->child[RBT_RIGHT];
+ while ( target->child[RBT_RIGHT] ) {
+ target = target->child[RBT_RIGHT];
+ }
/* if the target node has a child, need to move it up the tree into
* target's position (target is the right child of target->parent)
@@ -137,11 +142,11 @@ void _RBTree_Extract_unprotected(
* For now we store the color of the node being deleted in victim_color.
*/
leaf = target->child[RBT_LEFT];
- if(leaf) {
+ if ( leaf ) {
leaf->parent = target->parent;
} else {
/* fix the tree here if the child is a null leaf. */
- _RBTree_Extract_validate_unprotected(target);
+ _RBTree_Extract_validate( target );
}
victim_color = target->color;
dir = target != target->parent->child[0];
@@ -153,16 +158,17 @@ void _RBTree_Extract_unprotected(
/* set target's new children to the original node's children */
target->child[RBT_RIGHT] = the_node->child[RBT_RIGHT];
- if (the_node->child[RBT_RIGHT])
+ if ( the_node->child[RBT_RIGHT] ) {
the_node->child[RBT_RIGHT]->parent = target;
+ }
target->child[RBT_LEFT] = the_node->child[RBT_LEFT];
- if (the_node->child[RBT_LEFT])
+ if ( the_node->child[RBT_LEFT] ) {
the_node->child[RBT_LEFT]->parent = target;
+ }
/* finally, update the parent node and recolor. target has completely
* replaced the_node, and target's child has moved up the tree if needed.
- * the_node is no longer part of the tree, although it has valid pointers
- * still.
+ * the_node is no longer part of the tree, although it has valid pointers.
*/
target->parent = the_node->parent;
target->color = the_node->color;
@@ -178,7 +184,7 @@ void _RBTree_Extract_unprotected(
leaf->parent = the_node->parent;
} else {
/* fix the tree here if the child is a null leaf. */
- _RBTree_Extract_validate_unprotected(the_node);
+ _RBTree_Extract_validate( the_node );
}
victim_color = the_node->color;
@@ -192,34 +198,21 @@ void _RBTree_Extract_unprotected(
* 1. Deleted a red node, its child must be black. Nothing must be done.
* 2. Deleted a black node, its child must be red. Paint child black.
*/
- if (victim_color == RBT_BLACK) { /* eliminate case 1 */
- if (leaf) {
+ if ( victim_color == RBT_BLACK ) { /* eliminate case 1 */
+ if ( leaf ) {
leaf->color = RBT_BLACK; /* case 2 */
}
}
/* Wipe the_node */
- _RBTree_Set_off_rbtree(the_node);
+ _RBTree_Set_off_rbtree( the_node );
/* set root to black, if it exists */
- if (the_rbtree->root) the_rbtree->root->color = RBT_BLACK;
+ if ( the_rbtree->root ) {
+ the_rbtree->root->color = RBT_BLACK;
+ }
}
-
-/*
- * _RBTree_Extract
- *
- * This kernel routine deletes the given node from a rbtree.
- *
- * Input parameters:
- * node - pointer to node in rbtree to be deleted
- *
- * Output parameters: NONE
- *
- * INTERRUPT LATENCY:
- * only case
- */
-
void _RBTree_Extract(
RBTree_Control *the_rbtree,
RBTree_Node *the_node
@@ -228,6 +221,6 @@ void _RBTree_Extract(
ISR_Level level;
_ISR_Disable( level );
- _RBTree_Extract_unprotected( the_rbtree, the_node );
+ _RBTree_Extract_unprotected( the_rbtree, the_node );
_ISR_Enable( level );
}
diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c
index 07cbb3f..643b2ff 100644
--- a/cpukit/score/src/rbtreefind.c
+++ b/cpukit/score/src/rbtreefind.c
@@ -1,5 +1,13 @@
+/**
+ * @file
+ *
+ * @ingroup ScoreRBTree
+ *
+ * @brief _RBTree_Find_unprotected and _RBTree_Find.
+ */
+
/*
- * Copyright (c) 2010 Gedare Bloom.
+ * Copyright (c) 2010-2012 Gedare Bloom.
*
* The license and distribution terms for this file may be
* found in the file LICENSE in this distribution or at
@@ -10,29 +18,33 @@
#include "config.h"
#endif
-#include <rtems/system.h>
-#include <rtems/score/address.h>
#include <rtems/score/rbtree.h>
#include <rtems/score/isr.h>
-/*
- * _RBTree_Find
- *
- * This kernel routine returns a pointer to the rbtree node containing the
- * given key within the given tree, if it exists, or NULL otherwise.
- *
- * Input parameters:
- * the_rbtree - pointer to rbtree control
- * search_node - node with the key to search for
- *
- * Output parameters:
- * return_node - pointer to control header of rbtree
- * NULL - if there is no control header available (the node is not part
- * of a tree)
- *
- * INTERRUPT LATENCY:
- * only case
- */
+RBTree_Node *_RBTree_Find_unprotected(
+ RBTree_Control *the_rbtree,
+ RBTree_Node *the_node
+)
+{
+ RBTree_Node* iter_node = the_rbtree->root;
+ RBTree_Node* found = NULL;
+ RBTree_Direction dir;
+ 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;
+ }
+
+ dir = (RBTree_Direction)_RBTree_Is_greater( compare_result );
+ iter_node = iter_node->child[dir];
+ }
+
+ return found;
+}
RBTree_Node *_RBTree_Find(
RBTree_Control *the_rbtree,
@@ -42,9 +54,8 @@ RBTree_Node *_RBTree_Find(
ISR_Level level;
RBTree_Node *return_node;
- return_node = NULL;
_ISR_Disable( level );
- return_node = _RBTree_Find_unprotected( the_rbtree, search_node );
+ return_node = _RBTree_Find_unprotected( the_rbtree, search_node );
_ISR_Enable( level );
return return_node;
}
diff --git a/cpukit/score/src/rbtreefindheader.c b/cpukit/score/src/rbtreefindheader.c
index 99b0387..4178d6d 100644
--- a/cpukit/score/src/rbtreefindheader.c
+++ b/cpukit/score/src/rbtreefindheader.c
@@ -1,5 +1,12 @@
+/**
+ *
+ * @ingroup ScoreRBTree
+ *
+ * @brief _RBTree_Find_header
+ */
+
/*
- * Copyright (c) 2010 Gedare Bloom.
+ * Copyright (c) 2010-2012 Gedare Bloom.
*
* The license and distribution terms for this file may be
* found in the file LICENSE in this distribution or at
@@ -10,39 +17,18 @@
#include "config.h"
#endif
-#include <rtems/system.h>
-#include <rtems/score/address.h>
#include <rtems/score/rbtree.h>
#include <rtems/score/isr.h>
-/*
- * _RBTree_Find_header
- *
- * This kernel routine returns a pointer to the rbtree header of the tree
- * containing the given node.
- *
- * Input parameters:
- * the_node - pointer to rbtree node
- *
- * Output parameters:
- * return_header - pointer to control header of rbtree
- * NULL - if there is no control header available (the node is not part
- * of a tree)
- *
- * INTERRUPT LATENCY:
- * only case
- */
-
RBTree_Control *_RBTree_Find_header(
RBTree_Node *the_node
)
{
- ISR_Level level;
+ ISR_Level level;
RBTree_Control *return_header;
- return_header = NULL;
_ISR_Disable( level );
- return_header = _RBTree_Find_header_unprotected( the_node );
+ return_header = _RBTree_Find_header_unprotected( the_node );
_ISR_Enable( level );
return return_header;
}
diff --git a/cpukit/score/src/rbtreeget.c b/cpukit/score/src/rbtreeget.c
index 81e9161..47453c2 100644
--- a/cpukit/score/src/rbtreeget.c
+++ b/cpukit/score/src/rbtreeget.c
@@ -1,5 +1,13 @@
+/**
+ * @file
+ *
+ * @ingroup ScoreRBTree
+ *
+ * @brief _RBTree_Get
+ */
+
/*
- * Copyright (c) 2010 Gedare Bloom.
+ * Copyright (c) 2010-2012 Gedare Bloom.
*
* The license and distribution terms for this file may be
* found in the file LICENSE in this distribution or at
@@ -10,41 +18,19 @@
#include "config.h"
#endif
-#include <rtems/system.h>
-#include <rtems/score/address.h>
#include <rtems/score/rbtree.h>
#include <rtems/score/isr.h>
-/*
- * _RBTree_Get
- *
- * This kernel routine returns a pointer to a node taken from the
- * given rbtree.
- *
- * Input parameters:
- * the_rbtree - pointer to rbtree header
- * dir - specifies min (0) or max (1)
- *
- * Output parameters:
- * return_node - pointer to node in rbtree allocated
- * NULL - if no nodes available
- *
- * INTERRUPT LATENCY:
- * only case
- */
-
RBTree_Node *_RBTree_Get(
RBTree_Control *the_rbtree,
RBTree_Direction dir
)
{
- ISR_Level level;
+ ISR_Level level;
RBTree_Node *return_node;
- return_node = NULL;
_ISR_Disable( level );
- return_node = _RBTree_Get_unprotected( the_rbtree, dir );
+ return_node = _RBTree_Get_unprotected( the_rbtree, dir );
_ISR_Enable( level );
return return_node;
}
-
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index 57a36b8..9c889bd 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -1,3 +1,10 @@
+/**
+ *
+ * @ingroup ScoreRBTree
+ *
+ * @brief _RBTree_Insert_unprotected and _RBTree_Insert
+ */
+
/*
* Copyright (c) 2010-2012 Gedare Bloom.
*
@@ -10,34 +17,31 @@
#include "config.h"
#endif
-#include <rtems/system.h>
-#include <rtems/score/address.h>
#include <rtems/score/rbtree.h>
#include <rtems/score/isr.h>
-/** @brief Validate and fix-up tree properties for a new insert/colored node
+/*
+ * Validate and fix-up tree properties for a newly inserted/colored node.
*
- * This routine checks and fixes the Red-Black Tree properties based on
- * @a the_node being just added to the tree.
+ * Checks and fixes the red-black tree properties based on the_node being
+ * just added to the tree as a leaf with the color red.
*
- * @note It does NOT disable interrupts to ensure the atomicity of the
- * append operation.
+ * Note: the insert root case is handled already so no special care is needed.
*/
-static void _RBTree_Validate_insert_unprotected(
- RBTree_Node *the_node
- )
+static void _RBTree_Insert_validate(
+ RBTree_Node *the_node
+)
{
- RBTree_Node *u,*g;
+ RBTree_Node *u, *g;
- /* note: the insert root case is handled already */
/* if the parent is black, nothing needs to be done
* otherwise may need to loop a few times */
- while (_RBTree_Is_red(_RBTree_Parent(the_node))) {
- u = _RBTree_Parent_sibling(the_node);
+ while ( _RBTree_Is_red( _RBTree_Parent( the_node ) ) ) {
+ u = _RBTree_Parent_sibling( the_node );
g = the_node->parent->parent;
/* if uncle is red, repaint uncle/parent black and grandparent red */
- if(_RBTree_Is_red(u)) {
+ if( _RBTree_Is_red( u ) ) {
the_node->parent->color = RBT_BLACK;
u->color = RBT_BLACK;
g->color = RBT_RED;
@@ -47,45 +51,38 @@ static void _RBTree_Validate_insert_unprotected(
RBTree_Direction pdir = the_node->parent != g->child[0];
/* ensure node is on the same branch direction as parent */
- if (dir != pdir) {
- _RBTree_Rotate(the_node->parent, pdir);
+ if ( dir != pdir ) {
+ _RBTree_Rotate( the_node->parent, pdir );
the_node = the_node->child[pdir];
}
the_node->parent->color = RBT_BLACK;
g->color = RBT_RED;
/* now rotate grandparent in the other branch direction (toward uncle) */
- _RBTree_Rotate(g, (1-pdir));
+ _RBTree_Rotate( g, ( _RBTree_Opposite_direction( pdir ) ) );
}
}
- if(!the_node->parent->parent) the_node->color = RBT_BLACK;
-}
-
+ /* if the_node is now the root recolor it black */
+ if ( !the_node->parent->parent ) {
+ the_node->color = RBT_BLACK;
+ }
+}
-/** @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 key to the key of @a the_node exists
- * in an unique @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
- )
+ RBTree_Control *the_rbtree,
+ RBTree_Node *the_node
+)
{
- if(!the_node) return (RBTree_Node*)-1;
+ if ( !the_node ) {
+ return (RBTree_Node*)-1;
+ }
RBTree_Node *iter_node = the_rbtree->root;
int compare_result;
- if (!iter_node) { /* special case: first node inserted */
+ if ( !iter_node ) {
+ /* special case: first node inserted */
the_node->color = RBT_BLACK;
the_rbtree->root = the_node;
the_rbtree->first[0] = the_rbtree->first[1] = the_node;
@@ -93,12 +90,13 @@ RBTree_Node *_RBTree_Insert_unprotected(
the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
} else {
/* typical binary search tree insert, descend tree to leaf and insert */
- while (iter_node) {
- compare_result = the_rbtree->compare_function(the_node, iter_node);
- if ( the_rbtree->is_unique && _RBTree_Is_equal( compare_result ) )
+ while ( iter_node ) {
+ compare_result = the_rbtree->compare_function( the_node, iter_node );
+ if ( the_rbtree->is_unique && _RBTree_Is_equal( compare_result ) ) {
return iter_node;
+ }
RBTree_Direction dir = !_RBTree_Is_lesser( compare_result );
- if (!iter_node->child[dir]) {
+ if ( !iter_node->child[dir] ) {
the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
the_node->color = RBT_RED;
iter_node->child[dir] = the_node;
@@ -106,10 +104,10 @@ RBTree_Node *_RBTree_Insert_unprotected(
/* update min/max */
compare_result = the_rbtree->compare_function(
the_node,
- _RBTree_First(the_rbtree, dir)
+ _RBTree_First( the_rbtree, dir )
);
- if ( (!dir && _RBTree_Is_lesser(compare_result)) ||
- (dir && _RBTree_Is_greater(compare_result)) ) {
+ if ( ( !dir && _RBTree_Is_lesser( compare_result ) ) ||
+ ( dir && _RBTree_Is_greater( compare_result ) ) ) {
the_rbtree->first[dir] = the_node;
}
break;
@@ -120,28 +118,11 @@ RBTree_Node *_RBTree_Insert_unprotected(
} /* while(iter_node) */
/* verify red-black properties */
- _RBTree_Validate_insert_unprotected(the_node);
+ _RBTree_Insert_validate( the_node );
}
return (RBTree_Node*)0;
}
-
-/*
- * _RBTree_Insert
- *
- * This kernel routine inserts a given node after a specified node
- * a requested rbtree.
- *
- * Input parameters:
- * tree - pointer to RBTree Control for tree to insert to
- * node - pointer to node to be inserted
- *
- * Output parameters: NONE
- *
- * INTERRUPT LATENCY:
- * only case
- */
-
RBTree_Node *_RBTree_Insert(
RBTree_Control *tree,
RBTree_Node *node
--
1.7.1
More information about the devel
mailing list