[rtems commit] rbtree: Replace implementation
Sebastian Huber
sebh at rtems.org
Thu Sep 3 12:00:36 UTC 2015
Module: rtems
Branch: master
Commit: e9fbaa3b48364c821f5fb8ef7d7b7504be957e0e
Changeset: http://git.rtems.org/rtems/commit/?id=e9fbaa3b48364c821f5fb8ef7d7b7504be957e0e
Author: Sebastian Huber <sebastian.huber at embedded-brains.de>
Date: Fri Aug 21 05:59:49 2015 +0200
rbtree: Replace implementation
Use the BSD <sys/tree.h> implementation since it is faster, more
flexible and uses less storage. See https://github.com/sebhub/rb-bench.
---
cpukit/score/include/rtems/score/rbtree.h | 277 +++++----
cpukit/score/include/rtems/score/rbtreeimpl.h | 118 ----
cpukit/score/src/rbtreeextract.c | 190 +-----
cpukit/score/src/rbtreefind.c | 10 +-
cpukit/score/src/rbtreeinsert.c | 128 +---
cpukit/score/src/rbtreenext.c | 57 +-
testsuites/sptests/sprbtree01/init.c | 853 +++++++++++++-------------
7 files changed, 624 insertions(+), 1009 deletions(-)
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index b44c09e..077f2b1 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -18,9 +18,8 @@
#ifndef _RTEMS_SCORE_RBTREE_H
#define _RTEMS_SCORE_RBTREE_H
-#include <stddef.h>
-
-#include <rtems/score/address.h>
+#include <sys/tree.h>
+#include <rtems/score/basedefs.h>
#ifdef __cplusplus
extern "C" {
@@ -40,54 +39,22 @@ extern "C" {
/**@{*/
/**
- * @typedef RBTree_Node
+ * @brief Red-black tree node.
*
- * This type definition promotes the name for the RBTree Node used by
- * all RTEMS code. It is a separate type definition because a forward
- * reference is required to define it. See @ref RBTree_Node_struct for
- * detailed information.
+ * This is used to manage each node (element) which is placed on a red-black
+ * tree.
*/
-typedef struct RBTree_Node_struct RBTree_Node;
+typedef struct RBTree_Node {
+ RB_ENTRY(RBTree_Node) Node;
+} RBTree_Node;
/**
- * This enum type defines the colors available for the RBTree Nodes
- */
-typedef enum {
- RBT_BLACK,
- RBT_RED
-} RBTree_Color;
-
-/**
- * @struct RBTree_Node_struct
- *
- * This is used to manage each element (node) which is placed
- * on a RBT.
- *
- * @note Typically, a more complicated structure will use the
- * rbtree package. The more complicated structure will
- * include a rbtree node as the first element in its
- * control structure. It will then call the rbtree package
- * with a pointer to that node element. The node pointer
- * and the higher level structure start at the same address
- * so the user can cast the pointers back and forth.
+ * @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.
*/
-struct RBTree_Node_struct {
- /** This points to the node's parent */
- RBTree_Node *parent;
- /** child[0] points to the left child, child[1] points to the right child */
- RBTree_Node *child[2];
- /** The color of the node. Either red or black */
- RBTree_Color color;
-};
-
-/**
- * This type indicates the direction.
- */
-typedef enum {
- RBT_LEFT=0,
- RBT_RIGHT=1
-} RBTree_Direction;
+typedef RB_HEAD(RBTree_Control, RBTree_Node) RBTree_Control;
/**
* @brief Integer type for compare results.
@@ -117,41 +84,13 @@ typedef RBTree_Compare_result ( *RBTree_Compare )(
);
/**
- * @struct RBTree_Control
- *
- * This is used to manage a RBT. A rbtree consists of a tree of zero or more
- * nodes.
- *
- * @note This implementation does not require special checks for
- * manipulating the root element of the RBT.
- * To accomplish this the @a RBTree_Control structure can be overlaid
- * with a @ref RBTree_Node structure to act as a "dummy root",
- * which has a NULL parent and its left child is the root.
- */
-
-/* the RBTree_Control is actually part of the RBTree structure as an
- * RBTree_Node. The mapping of fields from RBTree_Control to RBTree_Node are:
- * permanent_null == parent
- * root == left
- * first[0] == right
- */
-typedef struct {
- /** This points to a NULL. Useful for finding the root. */
- RBTree_Node *permanent_null;
- /** This points to the root node of the RBT. */
- RBTree_Node *root;
- /** This points to the min and max nodes of this RBT. */
- RBTree_Node *first[2];
-} RBTree_Control;
-
-/**
- * @brief RBTree initializer for an empty rbtree with designator @a name.
+ * @brief Initializer for an empty red-black tree with designator @a name.
*/
#define RBTREE_INITIALIZER_EMPTY( name ) \
- { NULL, NULL, { NULL, NULL } }
+ RB_INITIALIZER( name )
/**
- * @brief RBTree definition for an empty rbtree with designator @a 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 )
@@ -201,6 +140,95 @@ RBTree_Node *_RBTree_Insert(
);
/**
+ * @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 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
+)
+{
+ 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
@@ -218,20 +246,6 @@ void _RBTree_Extract(
);
/**
- * @brief Returns the in-order next node of a node.
- *
- * @param[in] node The node.
- * @param[in] dir The direction.
- *
- * @retval NULL The in-order next node does not exist.
- * @retval otherwise The next node.
- */
-RBTree_Node *_RBTree_Next(
- const RBTree_Node *node,
- RBTree_Direction dir
-);
-
-/**
* @brief Sets a red-black tree node as off-tree.
*
* Do not use this function on nodes which are a part of a tree.
@@ -242,7 +256,7 @@ RBTree_Node *_RBTree_Next(
*/
RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node )
{
- the_node->parent = NULL;
+ RB_COLOR( the_node, Node ) = -1;
}
/**
@@ -260,7 +274,7 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree(
const RBTree_Node *the_node
)
{
- return the_node->parent == NULL;
+ return RB_COLOR( the_node, Node ) == -1;
}
/**
@@ -279,21 +293,17 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
const RBTree_Control *the_rbtree
)
{
- return the_rbtree->root;
+ return RB_ROOT( the_rbtree );
}
/**
- * @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).
+ * @brief Returns a reference to the root pointer of the red-black tree.
*/
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First(
- const RBTree_Control *the_rbtree,
- RBTree_Direction dir
+RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Root_reference(
+ RBTree_Control *the_rbtree
)
{
- return the_rbtree->first[dir];
+ return &RB_ROOT( the_rbtree );
}
/**
@@ -312,7 +322,7 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
const RBTree_Node *the_node
)
{
- return the_node->parent;
+ return RB_PARENT( the_node, Node );
}
/**
@@ -328,7 +338,18 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
const RBTree_Node *the_node
)
{
- return the_node->child[RBT_LEFT];
+ 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 );
}
/**
@@ -344,7 +365,18 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
const RBTree_Node *the_node
)
{
- return the_node->child[RBT_RIGHT];
+ 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 );
}
/**
@@ -362,7 +394,7 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
const RBTree_Control *the_rbtree
)
{
- return (the_rbtree->root == NULL);
+ return RB_EMPTY( the_rbtree );
}
/**
@@ -384,7 +416,7 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
const RBTree_Node *the_node
)
{
- return _RBTree_Parent( _RBTree_Parent( the_node ) ) == NULL;
+ return _RBTree_Parent( the_node ) == NULL;
}
/**
@@ -396,10 +428,7 @@ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
RBTree_Control *the_rbtree
)
{
- the_rbtree->permanent_null = NULL;
- the_rbtree->root = NULL;
- the_rbtree->first[RBT_LEFT] = NULL;
- the_rbtree->first[RBT_RIGHT] = NULL;
+ RB_INIT( the_rbtree );
}
/**
@@ -410,12 +439,7 @@ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
* @retval NULL The red-black tree is empty.
* @retval node The minimum node.
*/
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Minimum(
- const RBTree_Control *the_rbtree
-)
-{
- return _RBTree_First( the_rbtree, RBT_LEFT );
-}
+RBTree_Node *_RBTree_Minimum( const RBTree_Control *the_rbtree );
/**
* @brief Returns the maximum node of the red-black tree.
@@ -425,12 +449,7 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Minimum(
* @retval NULL The red-black tree is empty.
* @retval node The maximum node.
*/
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Maximum(
- const RBTree_Control *the_rbtree
-)
-{
- return _RBTree_First( the_rbtree, RBT_RIGHT );
-}
+RBTree_Node *_RBTree_Maximum( const RBTree_Control *the_rbtree );
/**
* @brief Returns the predecessor of a node.
@@ -440,12 +459,7 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Maximum(
* @retval NULL The predecessor does not exist. Otherwise it returns
* the predecessor node.
*/
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
- const RBTree_Node *node
-)
-{
- return _RBTree_Next( node, RBT_LEFT );
-}
+RBTree_Node *_RBTree_Predecessor( const RBTree_Node *node );
/**
* @brief Returns the successor of a node.
@@ -454,12 +468,7 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
*
* @retval NULL The successor does not exist. Otherwise the successor node.
*/
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
- const RBTree_Node *node
-)
-{
- return _RBTree_Next( node, RBT_RIGHT );
-}
+RBTree_Node *_RBTree_Successor( const RBTree_Node *node );
/**@}*/
diff --git a/cpukit/score/include/rtems/score/rbtreeimpl.h b/cpukit/score/include/rtems/score/rbtreeimpl.h
index 607e7eb..9c748eb 100644
--- a/cpukit/score/include/rtems/score/rbtreeimpl.h
+++ b/cpukit/score/include/rtems/score/rbtreeimpl.h
@@ -62,66 +62,6 @@ void _RBTree_Iterate(
void *visitor_arg
);
-/**
- * @brief Get the direction opposite to @a the_dir.
- */
-RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction(
- RBTree_Direction the_dir
-)
-{
- return (RBTree_Direction) !((int) the_dir);
-}
-
-/**
- * @brief Returns the direction of the node.
- *
- * @param[in] the_node The node of interest.
- * @param[in] parent The parent of the node. The parent must exist, thus it is
- * invalid to use this function for the root node.
- */
-RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Direction(
- const RBTree_Node *the_node,
- const RBTree_Node *parent
-)
-{
- return (RBTree_Direction) ( the_node != parent->child[ 0 ] );
-}
-
-/**
- * @brief Is this node red.
- *
- * 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
- )
-{
- return (the_node && the_node->color == RBT_RED);
-}
-
-/**
- * @brief Returns the sibling of the node.
- *
- * @param[in] the_node The node of interest.
- * @param[in] parent The parent of the node. The parent must exist, thus it is
- * invalid to use this function for the root node.
- *
- * @retval NULL No sibling exists.
- * @retval sibling The sibling of the node.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling(
- const RBTree_Node *the_node,
- const RBTree_Node *parent
-)
-{
- RBTree_Node *left_child = parent->child[ RBT_LEFT ];
-
- return the_node == left_child ? parent->child[ RBT_RIGHT ] : left_child;
-}
-
RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal(
RBTree_Compare_result compare_result
)
@@ -143,64 +83,6 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
return compare_result < 0;
}
-/**
- * @brief Rotates the node in the specified direction.
- *
- * The node is swapped with its child in the opposite direction if it exists.
- *
- * Sub-tree before rotation:
- * @dot
- * digraph state {
- * parent -> the_node;
- * the_node -> sibling [label="dir"];
- * the_node -> child [label="opp_dir"];
- * child -> grandchild [label="dir"];
- * child -> grandchildsibling [label="opp_dir"];
- * }
- * @enddot
- *
- * Sub-tree after rotation:
- * @dot
- * digraph state {
- * parent -> child;
- * the_node -> sibling [label="dir"];
- * the_node -> grandchild [label="opp_dir"];
- * child -> the_node [label="dir"];
- * child -> grandchildsibling [label="opp_dir"];
- * }
- * @enddot
- *
- * @param[in] the_node The node to rotate.
- * @param[in] dir The rotation direction.
- */
-RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
- RBTree_Node *the_node,
- RBTree_Direction dir
-)
-{
- RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
- RBTree_Node *child = the_node->child[ opp_dir ];
- RBTree_Node *grandchild;
- RBTree_Node *parent;
-
- if ( child == NULL)
- return;
-
- grandchild = child->child[ dir ];
- the_node->child[ opp_dir ] = grandchild;
-
- if ( grandchild != NULL )
- grandchild->parent = the_node;
-
- child->child[ dir ] = the_node;
-
- parent = _RBTree_Parent( the_node );
- parent->child[ _RBTree_Direction( the_node, parent ) ] = child;
-
- child->parent = parent;
- the_node->parent = child;
-}
-
/** @} */
#ifdef __cplusplus
diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
index 1aaba27..4d8a8f8 100644
--- a/cpukit/score/src/rbtreeextract.c
+++ b/cpukit/score/src/rbtreeextract.c
@@ -12,198 +12,14 @@
#include <rtems/score/rbtreeimpl.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.
- *
- * @note It does NOT disable interrupts to ensure the atomicity
- * of the extract operation.
- */
-static void _RBTree_Extract_validate( RBTree_Node *the_node )
-{
- RBTree_Node *parent;
-
- parent = the_node->parent;
-
- if ( !parent->parent )
- return;
-
- /* continue to correct tree as long as the_node is black and not the root */
- while ( !_RBTree_Is_red( the_node ) && parent->parent ) {
- RBTree_Node *sibling = _RBTree_Sibling( the_node, 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 ) ) {
- RBTree_Direction dir = _RBTree_Direction( the_node, parent );
- RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
-
- parent->color = RBT_RED;
- sibling->color = RBT_BLACK;
- _RBTree_Rotate( parent, dir );
- sibling = parent->child[ opp_dir ];
- }
+RB_GENERATE_REMOVE_COLOR( RBTree_Control, RBTree_Node, Node, static )
- /* 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 ] ) ) {
- sibling->color = RBT_RED;
-
- if ( _RBTree_Is_red( parent ) ) {
- parent->color = RBT_BLACK;
- break;
- }
-
- the_node = parent; /* done if parent is red */
- parent = the_node->parent;
- } 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.
- * In both cases, first check if one of sibling's children is black,
- * and if so rotate in the proper direction and update sibling pointer.
- * Then switch the sibling and parent colors, and rotate through parent.
- */
- RBTree_Direction dir = _RBTree_Direction( the_node, parent );
- RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
-
- if (
- !_RBTree_Is_red( sibling->child[ opp_dir ] )
- ) {
- sibling->color = RBT_RED;
- sibling->child[ dir ]->color = RBT_BLACK;
- _RBTree_Rotate( sibling, opp_dir );
- sibling = parent->child[ opp_dir ];
- }
-
- sibling->color = parent->color;
- parent->color = RBT_BLACK;
- sibling->child[ opp_dir ]->color = RBT_BLACK;
- _RBTree_Rotate( parent, dir );
- break; /* done */
- }
- } /* while */
-
- if ( !the_node->parent->parent )
- the_node->color = RBT_BLACK;
-}
+RB_GENERATE_REMOVE( RBTree_Control, RBTree_Node, Node, static )
void _RBTree_Extract(
RBTree_Control *the_rbtree,
RBTree_Node *the_node
)
{
- RBTree_Node *leaf, *target;
- RBTree_Color victim_color;
- RBTree_Direction dir;
-
- /* check if min needs to be updated */
- if ( the_node == the_rbtree->first[ RBT_LEFT ] ) {
- RBTree_Node *next;
- next = _RBTree_Successor( 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 ] ) {
- RBTree_Node *previous;
- previous = _RBTree_Predecessor( the_node );
- the_rbtree->first[ RBT_RIGHT ] = previous;
- }
-
- /* if the_node has at most one non-null child then it is safe to proceed
- * check if both children are non-null, if so then we must find a target node
- * either max in node->child[RBT_LEFT] or min in node->child[RBT_RIGHT],
- * 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 ] ) {
- target = the_node->child[ RBT_LEFT ]; /* find max in node->child[RBT_LEFT] */
-
- 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)
- * when target vacates it. if there is no child, then target->parent
- * should become NULL. This may cause the coloring to be violated.
- * For now we store the color of the node being deleted in victim_color.
- */
- leaf = target->child[ RBT_LEFT ];
-
- if ( leaf ) {
- leaf->parent = target->parent;
- } else {
- /* fix the tree here if the child is a null leaf. */
- _RBTree_Extract_validate( target );
- }
-
- victim_color = target->color;
- dir = target != target->parent->child[ 0 ];
- target->parent->child[ dir ] = leaf;
-
- /* now replace the_node with target */
- dir = the_node != the_node->parent->child[ 0 ];
- the_node->parent->child[ dir ] = target;
-
- /* 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 ] )
- the_node->child[ RBT_RIGHT ]->parent = target;
-
- target->child[ RBT_LEFT ] = 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.
- */
- target->parent = the_node->parent;
- target->color = the_node->color;
- } else {
- /* the_node has at most 1 non-null child. Move the child in to
- * the_node's location in the tree. This may cause the coloring to be
- * violated. We will fix it later.
- * For now we store the color of the node being deleted in victim_color.
- */
- leaf = the_node->child[ RBT_LEFT ] ?
- the_node->child[ RBT_LEFT ] : the_node->child[ RBT_RIGHT ];
-
- if ( leaf ) {
- leaf->parent = the_node->parent;
- } else {
- /* fix the tree here if the child is a null leaf. */
- _RBTree_Extract_validate( the_node );
- }
-
- victim_color = the_node->color;
-
- /* remove the_node from the tree */
- dir = the_node != the_node->parent->child[ 0 ];
- the_node->parent->child[ dir ] = leaf;
- }
-
- /* fix coloring. leaf has moved up the tree. The color of the deleted
- * node is in victim_color. There are two cases:
- * 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 ) {
- leaf->color = RBT_BLACK; /* case 2 */
- }
- }
-
- /* set root to black, if it exists */
- if ( the_rbtree->root )
- the_rbtree->root->color = RBT_BLACK;
+ RB_REMOVE( RBTree_Control, the_rbtree, the_node );
}
diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c
index 168a108..f920feb 100644
--- a/cpukit/score/src/rbtreefind.c
+++ b/cpukit/score/src/rbtreefind.c
@@ -26,12 +26,11 @@ RBTree_Node *_RBTree_Find(
bool is_unique
)
{
- RBTree_Node *iter_node = the_rbtree->root;
+ RBTree_Node *iter_node = _RBTree_Root( the_rbtree );
RBTree_Node *found = NULL;
while ( iter_node != NULL ) {
RBTree_Compare_result compare_result = ( *compare )( the_node, iter_node );
- RBTree_Direction dir;
if ( _RBTree_Is_equal( compare_result ) ) {
found = iter_node;
@@ -40,8 +39,11 @@ RBTree_Node *_RBTree_Find(
break;
}
- dir = (RBTree_Direction) _RBTree_Is_greater( compare_result );
- iter_node = iter_node->child[ dir ];
+ if ( _RBTree_Is_greater( compare_result ) ) {
+ iter_node = _RBTree_Right( iter_node );
+ } else {
+ iter_node = _RBTree_Left( iter_node );
+ }
}
return found;
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index a7be449..629fca7 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -22,68 +22,6 @@ RTEMS_STATIC_ASSERT(
RBTree_Compare_result_int32_t
);
-/** @brief Validate and fix-up tree properties for a new insert/colored node
- *
- * This routine checks and fixes the Red-Black Tree properties based on
- * @a the_node being just added to the tree.
- *
- * @note It does NOT disable interrupts to ensure the atomicity of the
- * append operation.
- */
-static void _RBTree_Validate_insert( RBTree_Node *the_node )
-{
- RBTree_Node *parent = _RBTree_Parent( the_node );
- RBTree_Node *grandparent = _RBTree_Parent( parent );
-
- /* 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 ( parent->color == RBT_RED ) {
- /* The root is black, so the grandparent must exist */
- RBTree_Node *uncle = _RBTree_Sibling( parent, grandparent );
-
- /*
- * If uncle exists and is red, repaint uncle/parent black and grandparent
- * red.
- */
- if ( uncle != NULL && uncle->color == RBT_RED ) {
- parent->color = RBT_BLACK;
- uncle->color = RBT_BLACK;
- grandparent->color = RBT_RED;
- the_node = grandparent;
- parent = _RBTree_Parent( the_node );
- grandparent = _RBTree_Parent( parent );
-
- if ( grandparent == NULL )
- break;
- } else { /* If uncle does not exist or is black */
- RBTree_Direction dir = _RBTree_Direction( the_node, parent );
- RBTree_Direction parentdir = _RBTree_Direction( parent, grandparent );
-
- /* ensure node is on the same branch direction as parent */
- if ( dir != parentdir ) {
- RBTree_Node *oldparent = parent;
-
- parent = the_node;
- the_node = oldparent;
- _RBTree_Rotate( oldparent, parentdir );
- }
-
- parent->color = RBT_BLACK;
- grandparent->color = RBT_RED;
-
- /* now rotate grandparent in the other branch direction (toward uncle) */
- _RBTree_Rotate( grandparent, _RBTree_Opposite_direction( parentdir ) );
-
- grandparent = _RBTree_Parent( parent );
- break;
- }
- }
-
- if ( grandparent == NULL )
- the_node->color = RBT_BLACK;
-}
-
RBTree_Node *_RBTree_Insert(
RBTree_Control *the_rbtree,
RBTree_Node *the_node,
@@ -91,52 +29,38 @@ RBTree_Node *_RBTree_Insert(
bool is_unique
)
{
- RBTree_Node *iter_node = the_rbtree->root;
+ RBTree_Node **which = _RBTree_Root_reference( the_rbtree );
+ RBTree_Node *parent = NULL;
- 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;
- the_node->parent = (RBTree_Node *) the_rbtree;
- 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 ) {
- RBTree_Compare_result compare_result =
- ( *compare )( the_node, iter_node );
+ while ( *which != NULL ) {
+ RBTree_Compare_result compare_result;
- if ( is_unique && _RBTree_Is_equal( compare_result ) )
- return iter_node;
+ parent = *which;
+ compare_result = ( *compare )( the_node, parent );
- RBTree_Direction dir = !_RBTree_Is_lesser( compare_result );
+ if ( is_unique && _RBTree_Is_equal( compare_result ) ) {
+ return parent;
+ }
- 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;
- the_node->parent = iter_node;
- /* update min/max */
- compare_result = ( *compare )(
- the_node,
- _RBTree_First( the_rbtree, dir )
- );
+ if ( _RBTree_Is_lesser( compare_result ) ) {
+ which = _RBTree_Left_reference( parent );
+ } else {
+ which = _RBTree_Right_reference( parent );
+ }
+ }
- if (
- ( dir == RBT_LEFT && _RBTree_Is_lesser( compare_result ) )
- || ( dir == RBT_RIGHT && !_RBTree_Is_lesser( compare_result ) )
- ) {
- the_rbtree->first[ dir ] = the_node;
- }
+ _RBTree_Add_child( the_node, parent, which );
+ _RBTree_Insert_color( the_rbtree, the_node );
- break;
- } else {
- iter_node = iter_node->child[ dir ];
- }
- } /* while(iter_node) */
+ return NULL;
+}
- /* verify red-black properties */
- _RBTree_Validate_insert( the_node );
- }
+RB_GENERATE_INSERT_COLOR( RBTree_Control, RBTree_Node, Node, static )
- return (RBTree_Node *) 0;
+void _RBTree_Insert_color(
+ RBTree_Control *the_rbtree,
+ RBTree_Node *the_node
+)
+{
+ RBTree_Control_RB_INSERT_COLOR( the_rbtree, the_node );
}
diff --git a/cpukit/score/src/rbtreenext.c b/cpukit/score/src/rbtreenext.c
index 2128ae5..7096b4b 100644
--- a/cpukit/score/src/rbtreenext.c
+++ b/cpukit/score/src/rbtreenext.c
@@ -25,39 +25,30 @@
#endif
#include <rtems/score/rbtreeimpl.h>
-#include <rtems/score/isr.h>
+#include <rtems/score/basedefs.h>
-RBTree_Node *_RBTree_Next(
- const RBTree_Node *node,
- RBTree_Direction dir
-)
+RB_GENERATE_MINMAX( RBTree_Control, RBTree_Node, Node, static )
+
+RB_GENERATE_NEXT( RBTree_Control, RBTree_Node, Node, static )
+
+RB_GENERATE_PREV( RBTree_Control, RBTree_Node, Node, static )
+
+RBTree_Node *_RBTree_Minimum( const RBTree_Control *tree )
+{
+ return RB_MIN( RBTree_Control, RTEMS_DECONST( RBTree_Control *, tree ) );
+}
+
+RBTree_Node *_RBTree_Maximum( const RBTree_Control *tree )
+{
+ return RB_MAX( RBTree_Control, RTEMS_DECONST( RBTree_Control *, tree ) );
+}
+
+RBTree_Node *_RBTree_Successor( const RBTree_Node *node )
+{
+ return RB_NEXT( RBTree_Control, NULL, RTEMS_DECONST( RBTree_Node *, node ) );
+}
+
+RBTree_Node *_RBTree_Predecessor( const RBTree_Node *node )
{
- RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
- RBTree_Node *current = node->child[ dir ];
- RBTree_Node *next = NULL;
-
- if ( current != NULL ) {
- next = current;
-
- while ( ( current = current->child[ opp_dir ] ) != NULL ) {
- next = current;
- }
- } else {
- RBTree_Node *parent = node->parent;
-
- if ( parent->parent && node == parent->child[ opp_dir ] ) {
- next = parent;
- } else {
- while ( parent->parent && node == parent->child[ dir ] ) {
- node = parent;
- parent = parent->parent;
- }
-
- if ( parent->parent ) {
- next = parent;
- }
- }
- }
-
- return next;
+ return RB_PREV( RBTree_Control, NULL, RTEMS_DECONST( RBTree_Node *, node ) );
}
diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
index 0fe72a4..c58c6d5 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -35,13 +35,13 @@ typedef struct {
static test_node node_array[100];
-#define RED RBT_RED
+#define RED RB_RED
-#define BLACK RBT_BLACK
+#define BLACK RB_BLACK
static int rb_color( const rtems_rbtree_node *n )
{
- return n->color;
+ return RB_COLOR( n, Node );
}
static rtems_rbtree_compare_result test_compare_function (
@@ -241,7 +241,7 @@ typedef struct {
const rtems_rbtree_node *parent;
const rtems_rbtree_node *left;
const rtems_rbtree_node *right;
- RBTree_Color color;
+ int color;
} test_node_description;
static const test_node_description test_insert_tree_0[] = {
@@ -863,8 +863,8 @@ static const test_node_description random_ops_tree_multiple_3[] = {
};
static const test_node_description random_ops_tree_unique_4[] = {
- { 0, NULL, NULL, TN( 3 ), BLACK },
- { 3, TN( 0 ), NULL, NULL, RED }
+ { 0, TN(3), NULL, NULL, RED },
+ { 3, NULL, TN(0), NULL, BLACK }
};
static const test_node_description random_ops_tree_multiple_4[] = {
@@ -911,10 +911,10 @@ static const test_node_description random_ops_tree_multiple_7[] = {
};
static const test_node_description random_ops_tree_unique_8[] = {
- { 0, TN( 1 ), NULL, NULL, RED },
- { 1, TN( 5 ), TN( 0 ), NULL, BLACK },
- { 5, NULL, TN( 1 ), TN( 6 ), BLACK },
- { 6, TN( 5 ), NULL, NULL, BLACK }
+ { 0, TN(1), NULL, NULL, BLACK },
+ { 1, NULL, TN(0), TN(6), BLACK },
+ { 5, TN(6), NULL, NULL, RED },
+ { 6, TN(1), TN(5), NULL, BLACK }
};
static const test_node_description random_ops_tree_multiple_8[] = {
@@ -1001,36 +1001,36 @@ static const test_node_description random_ops_tree_multiple_12[] = {
};
static const test_node_description random_ops_tree_unique_13[] = {
- { 0, TN( 1 ), NULL, NULL, RED },
- { 1, TN( 3 ), TN( 0 ), NULL, BLACK },
- { 3, NULL, TN( 1 ), TN( 8 ), BLACK },
- { 4, TN( 5 ), NULL, NULL, RED },
- { 5, TN( 8 ), TN( 4 ), TN( 6 ), BLACK },
- { 6, TN( 5 ), NULL, NULL, RED },
- { 8, TN( 3 ), TN( 5 ), TN( 11 ), RED },
- { 10, TN( 11 ), NULL, NULL, RED },
- { 11, TN( 8 ), TN( 10 ), NULL, BLACK }
+ { 0, TN(1), NULL, NULL, RED },
+ { 1, TN(3), TN(0), NULL, BLACK },
+ { 3, TN(8), TN(1), TN(5), RED },
+ { 4, TN(5), NULL, NULL, RED },
+ { 5, TN(3), TN(4), TN(6), BLACK },
+ { 6, TN(5), NULL, NULL, RED },
+ { 8, NULL, TN(3), TN(11), BLACK },
+ { 10, TN(11), NULL, NULL, RED },
+ { 11, TN(8), TN(10), NULL, BLACK }
};
static const test_node_description random_ops_tree_multiple_13[] = {
- { 0, TN( 0 ), NULL, NULL, BLACK },
- { 0, TN( 4 ), TN( 1 ), TN( 3 ), RED },
- { 1, TN( 0 ), NULL, NULL, BLACK },
- { 2, NULL, TN( 0 ), TN( 8 ), BLACK },
- { 2, TN( 6 ), NULL, NULL, RED },
- { 3, TN( 8 ), TN( 5 ), NULL, BLACK },
- { 4, TN( 4 ), TN( 6 ), TN( 11 ), RED },
- { 5, TN( 8 ), NULL, TN( 10 ), BLACK },
- { 5, TN( 11 ), NULL, NULL, RED }
+ { 0, TN(0), NULL, NULL, RED },
+ { 0, TN(3), TN(1), NULL, BLACK },
+ { 1, TN(6), TN(0), TN(4), RED },
+ { 2, TN(3), NULL, TN(5), BLACK },
+ { 2, TN(4), NULL, NULL, RED },
+ { 3, NULL, TN(3), TN(11), BLACK },
+ { 4, TN(11), NULL, NULL, RED },
+ { 5, TN(6), TN(8), TN(10), BLACK },
+ { 5, TN(11), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_unique_14[] = {
- { 3, TN( 6 ), NULL, TN( 5 ), BLACK },
- { 5, TN( 3 ), NULL, NULL, RED },
- { 6, NULL, TN( 3 ), TN( 12 ), BLACK },
- { 8, TN( 12 ), NULL, NULL, BLACK },
- { 12, TN( 6 ), TN( 8 ), TN( 13 ), RED },
- { 13, TN( 12 ), NULL, NULL, BLACK }
+ { 3, TN(5), NULL, NULL, RED },
+ { 5, TN(6), TN(3), NULL, BLACK },
+ { 6, NULL, TN(5), TN(12), BLACK },
+ { 8, TN(12), NULL, NULL, BLACK },
+ { 12, TN(6), TN(8), TN(13), RED },
+ { 13, TN(12), NULL, NULL, BLACK }
};
static const test_node_description random_ops_tree_multiple_14[] = {
@@ -1043,491 +1043,491 @@ static const test_node_description random_ops_tree_multiple_14[] = {
};
static const test_node_description random_ops_tree_unique_15[] = {
- { 0, TN( 2 ), NULL, NULL, BLACK },
- { 2, TN( 9 ), TN( 0 ), TN( 8 ), BLACK },
- { 7, TN( 8 ), NULL, NULL, RED },
- { 8, TN( 2 ), TN( 7 ), NULL, BLACK },
- { 9, NULL, TN( 2 ), TN( 12 ), BLACK },
- { 10, TN( 12 ), NULL, NULL, BLACK },
- { 12, TN( 9 ), TN( 10 ), TN( 13 ), BLACK },
- { 13, TN( 12 ), NULL, TN( 14 ), BLACK },
- { 14, TN( 13 ), NULL, NULL, RED }
+ { 0, TN(2), NULL, NULL, RED },
+ { 2, TN(8), TN(0), TN(7), BLACK },
+ { 7, TN(2), NULL, NULL, RED },
+ { 8, NULL, TN(2), TN(12), BLACK },
+ { 9, TN(12), NULL, TN(10), BLACK },
+ { 10, TN(9), NULL, NULL, RED },
+ { 12, TN(8), TN(9), TN(13), RED },
+ { 13, TN(12), NULL, TN(14), BLACK },
+ { 14, TN(13), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_multiple_15[] = {
- { 0, TN( 2 ), NULL, NULL, RED },
- { 1, TN( 9 ), TN( 0 ), TN( 7 ), BLACK },
- { 3, TN( 2 ), NULL, NULL, RED },
- { 4, NULL, TN( 2 ), TN( 13 ), BLACK },
- { 4, TN( 13 ), NULL, TN( 10 ), BLACK },
- { 5, TN( 8 ), NULL, NULL, RED },
- { 6, TN( 9 ), TN( 8 ), TN( 12 ), RED },
- { 6, TN( 13 ), NULL, TN( 14 ), BLACK },
- { 7, TN( 12 ), NULL, NULL, RED }
+ { 0, TN(2), NULL, NULL, RED },
+ { 1, TN(9), TN(0), TN(7), BLACK },
+ { 3, TN(2), NULL, NULL, RED },
+ { 4, NULL, TN(2), TN(10), BLACK },
+ { 4, TN(10), NULL, NULL, BLACK },
+ { 5, TN(9), TN(8), TN(12), RED },
+ { 6, TN(12), NULL, NULL, RED },
+ { 6, TN(10), TN(13), TN(14), BLACK },
+ { 7, TN(12), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_unique_16[] = {
- { 0, TN( 5 ), NULL, TN( 3 ), BLACK },
- { 3, TN( 0 ), NULL, NULL, RED },
- { 5, NULL, TN( 0 ), TN( 10 ), BLACK },
- { 7, TN( 10 ), NULL, NULL, BLACK },
- { 10, TN( 5 ), TN( 7 ), TN( 12 ), RED },
- { 12, TN( 10 ), NULL, NULL, BLACK }
+ { 0, TN(5), NULL, TN(3), BLACK },
+ { 3, TN(0), NULL, NULL, RED },
+ { 5, TN(10), TN(0), TN(7), RED },
+ { 7, TN(5), NULL, NULL, BLACK },
+ { 10, NULL, TN(5), TN(12), BLACK },
+ { 12, TN(10), NULL, NULL, BLACK }
};
static const test_node_description random_ops_tree_multiple_16[] = {
- { 0, TN( 3 ), NULL, NULL, RED },
- { 1, TN( 7 ), TN( 0 ), TN( 5 ), BLACK },
- { 2, TN( 3 ), NULL, NULL, RED },
- { 3, NULL, TN( 3 ), TN( 12 ), BLACK },
- { 5, TN( 12 ), NULL, NULL, RED },
- { 6, TN( 7 ), TN( 10 ), NULL, BLACK }
+ { 0, TN(5), NULL, TN(3), BLACK },
+ { 1, TN(0), NULL, NULL, RED },
+ { 2, TN(10), TN(0), TN(7), RED },
+ { 3, TN(5), NULL, NULL, BLACK },
+ { 5, NULL, TN(5), TN(12), BLACK },
+ { 6, TN(10), NULL, NULL, BLACK }
};
static const test_node_description random_ops_tree_unique_17[] = {
- { 0, TN( 1 ), NULL, NULL, BLACK },
- { 1, TN( 5 ), TN( 0 ), TN( 3 ), BLACK },
- { 3, TN( 1 ), NULL, TN( 4 ), BLACK },
- { 4, TN( 3 ), NULL, NULL, RED },
- { 5, NULL, TN( 1 ), TN( 9 ), BLACK },
- { 7, TN( 9 ), NULL, TN( 8 ), BLACK },
- { 8, TN( 7 ), NULL, NULL, RED },
- { 9, TN( 5 ), TN( 7 ), TN( 16 ), BLACK },
- { 16, TN( 9 ), NULL, NULL, BLACK }
+ { 0, TN(1), NULL, NULL, RED },
+ { 1, TN(3), TN(0), NULL, BLACK },
+ { 3, TN(7), TN(1), TN(5), RED },
+ { 4, TN(5), NULL, NULL, RED },
+ { 5, TN(3), TN(4), NULL, BLACK },
+ { 7, NULL, TN(3), TN(9), BLACK },
+ { 8, TN(9), NULL, NULL, BLACK },
+ { 9, TN(7), TN(8), TN(16), RED },
+ { 16, TN(9), NULL, NULL, BLACK }
};
static const test_node_description random_ops_tree_multiple_17[] = {
- { 0, TN( 0 ), NULL, NULL, BLACK },
- { 0, TN( 5 ), TN( 1 ), TN( 3 ), BLACK },
- { 1, TN( 0 ), NULL, NULL, BLACK },
- { 2, NULL, TN( 0 ), TN( 9 ), BLACK },
- { 2, TN( 9 ), NULL, TN( 7 ), BLACK },
- { 3, TN( 4 ), NULL, NULL, RED },
- { 4, TN( 5 ), TN( 4 ), TN( 16 ), BLACK },
- { 4, TN( 16 ), NULL, NULL, RED },
- { 8, TN( 9 ), TN( 8 ), NULL, BLACK }
+ { 0, TN(0), NULL, NULL, RED },
+ { 0, TN(3), TN(1), NULL, BLACK },
+ { 1, TN(7), TN(0), TN(5), RED },
+ { 2, TN(3), NULL, TN(4), BLACK },
+ { 2, TN(5), NULL, NULL, RED },
+ { 3, NULL, TN(3), TN(8), BLACK },
+ { 4, TN(8), NULL, NULL, BLACK },
+ { 4, TN(7), TN(9), TN(16), RED },
+ { 8, TN(8), NULL, NULL, BLACK }
};
static const test_node_description random_ops_tree_unique_18[] = {
- { 0, TN( 1 ), NULL, NULL, RED },
- { 1, TN( 3 ), TN( 0 ), TN( 2 ), BLACK },
- { 2, TN( 1 ), NULL, NULL, RED },
- { 3, TN( 6 ), TN( 1 ), TN( 4 ), BLACK },
- { 4, TN( 3 ), NULL, TN( 5 ), BLACK },
- { 5, TN( 4 ), NULL, NULL, RED },
- { 6, NULL, TN( 3 ), TN( 14 ), BLACK },
- { 7, TN( 8 ), NULL, NULL, RED },
- { 8, TN( 10 ), TN( 7 ), TN( 9 ), BLACK },
- { 9, TN( 8 ), NULL, NULL, RED },
- { 10, TN( 14 ), TN( 8 ), TN( 12 ), RED },
- { 12, TN( 10 ), NULL, NULL, BLACK },
- { 14, TN( 6 ), TN( 10 ), TN( 17 ), BLACK },
- { 17, TN( 14 ), NULL, NULL, BLACK }
+ { 0, TN(2), NULL, TN(1), BLACK },
+ { 1, TN(0), NULL, NULL, RED },
+ { 2, TN(4), TN(0), TN(3), BLACK },
+ { 3, TN(2), NULL, NULL, BLACK },
+ { 4, NULL, TN(2), TN(12), BLACK },
+ { 5, TN(6), NULL, NULL, RED },
+ { 6, TN(8), TN(5), TN(7), BLACK },
+ { 7, TN(6), NULL, NULL, RED },
+ { 8, TN(12), TN(6), TN(10), RED },
+ { 9, TN(10), NULL, NULL, RED },
+ { 10, TN(8), TN(9), NULL, BLACK },
+ { 12, TN(4), TN(8), TN(17), BLACK },
+ { 14, TN(17), NULL, NULL, RED },
+ { 17, TN(12), TN(14), NULL, BLACK }
};
static const test_node_description random_ops_tree_multiple_18[] = {
- { 0, TN( 1 ), NULL, NULL, RED },
- { 0, TN( 2 ), TN( 0 ), TN( 3 ), BLACK },
- { 1, TN( 1 ), NULL, NULL, RED },
- { 1, TN( 6 ), TN( 1 ), TN( 4 ), BLACK },
- { 2, TN( 2 ), NULL, TN( 5 ), BLACK },
- { 2, TN( 4 ), NULL, NULL, RED },
- { 3, NULL, TN( 2 ), TN( 12 ), BLACK },
- { 3, TN( 8 ), NULL, NULL, RED },
- { 4, TN( 9 ), TN( 7 ), NULL, BLACK },
- { 4, TN( 12 ), TN( 8 ), TN( 10 ), RED },
- { 5, TN( 9 ), NULL, NULL, BLACK },
- { 6, TN( 6 ), TN( 9 ), TN( 14 ), BLACK },
- { 7, TN( 12 ), NULL, TN( 17 ), BLACK },
- { 8, TN( 14 ), NULL, NULL, RED }
+ { 0, TN(3), NULL, TN(1), BLACK },
+ { 0, TN(0), NULL, NULL, RED },
+ { 1, TN(4), TN(0), TN(2), BLACK },
+ { 1, TN(3), NULL, NULL, BLACK },
+ { 2, NULL, TN(3), TN(12), BLACK },
+ { 2, TN(6), NULL, NULL, RED },
+ { 3, TN(8), TN(5), TN(7), BLACK },
+ { 3, TN(6), NULL, NULL, RED },
+ { 4, TN(12), TN(6), TN(10), RED },
+ { 4, TN(10), NULL, NULL, RED },
+ { 5, TN(8), TN(9), NULL, BLACK },
+ { 6, TN(4), TN(8), TN(14), BLACK },
+ { 7, TN(12), NULL, TN(17), BLACK },
+ { 8, TN(14), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_unique_19[] = {
- { 1, TN( 2 ), NULL, NULL, RED },
- { 2, TN( 6 ), TN( 1 ), NULL, BLACK },
- { 6, TN( 9 ), TN( 2 ), TN( 8 ), BLACK },
- { 8, TN( 6 ), NULL, NULL, BLACK },
- { 9, NULL, TN( 6 ), TN( 12 ), BLACK },
- { 11, TN( 12 ), NULL, NULL, BLACK },
- { 12, TN( 9 ), TN( 11 ), TN( 16 ), BLACK },
- { 14, TN( 16 ), NULL, NULL, RED },
- { 16, TN( 12 ), TN( 14 ), NULL, BLACK }
+ { 1, TN(2), NULL, NULL, RED },
+ { 2, TN(6), TN(1), NULL, BLACK },
+ { 6, TN(11), TN(2), TN(8), BLACK },
+ { 8, TN(6), NULL, TN(9), BLACK },
+ { 9, TN(8), NULL, NULL, RED },
+ { 11, NULL, TN(6), TN(14), BLACK },
+ { 12, TN(14), NULL, NULL, BLACK },
+ { 14, TN(11), TN(12), TN(16), BLACK },
+ { 16, TN(14), NULL, NULL, BLACK }
};
static const test_node_description random_ops_tree_multiple_19[] = {
- { 0, TN( 2 ), NULL, NULL, RED },
- { 1, TN( 6 ), TN( 1 ), NULL, BLACK },
- { 3, TN( 8 ), TN( 2 ), TN( 9 ), BLACK },
- { 4, TN( 6 ), NULL, NULL, BLACK },
- { 4, NULL, TN( 6 ), TN( 12 ), BLACK },
- { 5, TN( 12 ), NULL, NULL, BLACK },
- { 6, TN( 8 ), TN( 11 ), TN( 16 ), BLACK },
- { 7, TN( 16 ), NULL, NULL, RED },
- { 8, TN( 12 ), TN( 14 ), NULL, BLACK }
+ { 0, TN(2), NULL, NULL, RED },
+ { 1, TN(6), TN(1), NULL, BLACK },
+ { 3, TN(11), TN(2), TN(9), BLACK },
+ { 4, TN(6), NULL, TN(8), BLACK },
+ { 4, TN(9), NULL, NULL, RED },
+ { 5, NULL, TN(6), TN(14), BLACK },
+ { 6, TN(14), NULL, NULL, BLACK },
+ { 7, TN(11), TN(12), TN(16), BLACK },
+ { 8, TN(14), NULL, NULL, BLACK }
};
static const test_node_description random_ops_tree_unique_20[] = {
- { 0, TN( 3 ), NULL, TN( 1 ), BLACK },
- { 1, TN( 0 ), NULL, NULL, RED },
- { 3, TN( 9 ), TN( 0 ), TN( 4 ), RED },
- { 4, TN( 3 ), NULL, TN( 7 ), BLACK },
- { 7, TN( 4 ), NULL, NULL, RED },
- { 9, NULL, TN( 3 ), TN( 14 ), BLACK },
- { 10, TN( 14 ), NULL, TN( 12 ), BLACK },
- { 12, TN( 10 ), NULL, NULL, RED },
- { 14, TN( 9 ), TN( 10 ), TN( 18 ), RED },
- { 17, TN( 18 ), NULL, NULL, RED },
- { 18, TN( 14 ), TN( 17 ), TN( 19 ), BLACK },
- { 19, TN( 18 ), NULL, NULL, RED }
+ { 0, TN(3), NULL, TN(1), BLACK },
+ { 1, TN(0), NULL, NULL, RED },
+ { 3, TN(9), TN(0), TN(7), BLACK },
+ { 4, TN(7), NULL, NULL, RED },
+ { 7, TN(3), TN(4), NULL, BLACK },
+ { 9, NULL, TN(3), TN(12), BLACK },
+ { 10, TN(12), NULL, NULL, BLACK },
+ { 12, TN(9), TN(10), TN(17), BLACK },
+ { 14, TN(17), NULL, NULL, BLACK },
+ { 17, TN(12), TN(14), TN(18), RED },
+ { 18, TN(17), NULL, TN(19), BLACK },
+ { 19, TN(18), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_multiple_20[] = {
- { 0, TN( 1 ), NULL, NULL, RED },
- { 0, TN( 4 ), TN( 0 ), TN( 3 ), BLACK },
- { 1, TN( 1 ), NULL, NULL, RED },
- { 2, TN( 9 ), TN( 1 ), TN( 7 ), BLACK },
- { 3, TN( 4 ), NULL, NULL, BLACK },
- { 4, NULL, TN( 4 ), TN( 12 ), BLACK },
- { 5, TN( 12 ), NULL, NULL, BLACK },
- { 6, TN( 9 ), TN( 10 ), TN( 17 ), BLACK },
- { 7, TN( 17 ), NULL, NULL, BLACK },
- { 8, TN( 12 ), TN( 14 ), TN( 18 ), RED },
- { 9, TN( 17 ), NULL, TN( 19 ), BLACK },
- { 9, TN( 18 ), NULL, NULL, RED }
+ { 0, TN(3), NULL, TN(1), BLACK },
+ { 0, TN(0), NULL, NULL, RED },
+ { 1, TN(9), TN(0), TN(7), BLACK },
+ { 2, TN(7), NULL, NULL, RED },
+ { 3, TN(3), TN(4), NULL, BLACK },
+ { 4, NULL, TN(3), TN(14), BLACK },
+ { 5, TN(14), NULL, TN(12), BLACK },
+ { 6, TN(10), NULL, NULL, RED },
+ { 7, TN(9), TN(10), TN(18), BLACK },
+ { 8, TN(18), NULL, NULL, RED },
+ { 9, TN(14), TN(17), TN(19), BLACK },
+ { 9, TN(18), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_unique_21[] = {
- { 0, TN( 1 ), NULL, NULL, BLACK },
- { 1, TN( 8 ), TN( 0 ), TN( 4 ), BLACK },
- { 3, TN( 4 ), NULL, NULL, BLACK },
- { 4, TN( 1 ), TN( 3 ), TN( 5 ), RED },
- { 5, TN( 4 ), NULL, NULL, BLACK },
- { 8, NULL, TN( 1 ), TN( 13 ), BLACK },
- { 11, TN( 13 ), NULL, NULL, BLACK },
- { 13, TN( 8 ), TN( 11 ), TN( 16 ), BLACK },
- { 15, TN( 16 ), NULL, NULL, BLACK },
- { 16, TN( 13 ), TN( 15 ), TN( 17 ), RED },
- { 17, TN( 16 ), NULL, NULL, BLACK }
+ { 0, TN(3), NULL, TN(1), BLACK },
+ { 1, TN(0), NULL, NULL, RED },
+ { 3, TN(11), TN(0), TN(5), BLACK },
+ { 4, TN(5), NULL, NULL, BLACK },
+ { 5, TN(3), TN(4), TN(8), RED },
+ { 8, TN(5), NULL, NULL, BLACK },
+ { 11, NULL, TN(3), TN(15), BLACK },
+ { 13, TN(15), NULL, NULL, BLACK },
+ { 15, TN(11), TN(13), TN(17), BLACK },
+ { 16, TN(17), NULL, NULL, RED },
+ { 17, TN(15), TN(16), NULL, BLACK }
};
static const test_node_description random_ops_tree_multiple_21[] = {
- { 0, TN( 1 ), NULL, NULL, BLACK },
- { 0, TN( 8 ), TN( 0 ), TN( 4 ), BLACK },
- { 1, TN( 4 ), NULL, NULL, BLACK },
- { 2, TN( 1 ), TN( 3 ), TN( 5 ), RED },
- { 2, TN( 4 ), NULL, NULL, BLACK },
- { 4, NULL, TN( 1 ), TN( 13 ), BLACK },
- { 5, TN( 13 ), NULL, NULL, BLACK },
- { 6, TN( 8 ), TN( 11 ), TN( 17 ), BLACK },
- { 7, TN( 17 ), NULL, NULL, BLACK },
- { 8, TN( 13 ), TN( 15 ), TN( 16 ), RED },
- { 8, TN( 17 ), NULL, NULL, BLACK }
+ { 0, TN(3), NULL, TN(1), BLACK },
+ { 0, TN(0), NULL, NULL, RED },
+ { 1, TN(8), TN(0), TN(4), BLACK },
+ { 2, TN(3), NULL, TN(5), BLACK },
+ { 2, TN(4), NULL, NULL, RED },
+ { 4, NULL, TN(3), TN(13), BLACK },
+ { 5, TN(13), NULL, NULL, BLACK },
+ { 6, TN(8), TN(11), TN(17), BLACK },
+ { 7, TN(17), NULL, NULL, BLACK },
+ { 8, TN(13), TN(15), TN(16), RED },
+ { 8, TN(17), NULL, NULL, BLACK }
};
static const test_node_description random_ops_tree_unique_22[] = {
- { 1, TN( 3 ), NULL, TN( 2 ), BLACK },
- { 2, TN( 1 ), NULL, NULL, RED },
- { 3, TN( 8 ), TN( 1 ), TN( 4 ), BLACK },
- { 4, TN( 3 ), NULL, TN( 7 ), BLACK },
- { 7, TN( 4 ), NULL, NULL, RED },
- { 8, NULL, TN( 3 ), TN( 14 ), BLACK },
- { 10, TN( 11 ), NULL, NULL, RED },
- { 11, TN( 14 ), TN( 10 ), NULL, BLACK },
- { 14, TN( 8 ), TN( 11 ), TN( 18 ), BLACK },
- { 15, TN( 18 ), NULL, NULL, BLACK },
- { 18, TN( 14 ), TN( 15 ), TN( 21 ), RED },
- { 21, TN( 18 ), NULL, NULL, BLACK }
+ { 1, TN(3), NULL, TN(2), BLACK },
+ { 2, TN(1), NULL, NULL, RED },
+ { 3, TN(8), TN(1), TN(7), BLACK },
+ { 4, TN(7), NULL, NULL, RED },
+ { 7, TN(3), TN(4), NULL, BLACK },
+ { 8, NULL, TN(3), TN(14), BLACK },
+ { 10, TN(11), NULL, NULL, RED },
+ { 11, TN(14), TN(10), NULL, BLACK },
+ { 14, TN(8), TN(11), TN(18), BLACK },
+ { 15, TN(18), NULL, NULL, BLACK },
+ { 18, TN(14), TN(15), TN(21), RED },
+ { 21, TN(18), NULL, NULL, BLACK }
};
static const test_node_description random_ops_tree_multiple_22[] = {
- { 0, TN( 3 ), NULL, NULL, BLACK },
- { 1, TN( 8 ), TN( 1 ), TN( 4 ), BLACK },
- { 1, TN( 4 ), NULL, NULL, BLACK },
- { 2, TN( 3 ), TN( 2 ), TN( 7 ), RED },
- { 3, TN( 4 ), NULL, NULL, BLACK },
- { 4, NULL, TN( 3 ), TN( 14 ), BLACK },
- { 5, TN( 14 ), NULL, TN( 10 ), BLACK },
- { 5, TN( 11 ), NULL, NULL, RED },
- { 7, TN( 8 ), TN( 11 ), TN( 18 ), BLACK },
- { 7, TN( 18 ), NULL, NULL, BLACK },
- { 9, TN( 14 ), TN( 15 ), TN( 21 ), RED },
- { 10, TN( 18 ), NULL, NULL, BLACK }
+ { 0, TN(3), NULL, NULL, BLACK },
+ { 1, TN(8), TN(1), TN(4), BLACK },
+ { 1, TN(4), NULL, NULL, BLACK },
+ { 2, TN(3), TN(2), TN(7), RED },
+ { 3, TN(4), NULL, NULL, BLACK },
+ { 4, NULL, TN(3), TN(14), BLACK },
+ { 5, TN(14), NULL, TN(10), BLACK },
+ { 5, TN(11), NULL, NULL, RED },
+ { 7, TN(8), TN(11), TN(18), BLACK },
+ { 7, TN(18), NULL, NULL, BLACK },
+ { 9, TN(14), TN(15), TN(21), RED },
+ { 10, TN(18), NULL, NULL, BLACK }
};
static const test_node_description random_ops_tree_unique_23[] = {
- { 0, TN( 2 ), NULL, NULL, BLACK },
- { 2, TN( 8 ), TN( 0 ), TN( 7 ), BLACK },
- { 7, TN( 2 ), NULL, NULL, BLACK },
- { 8, NULL, TN( 2 ), TN( 16 ), BLACK },
- { 11, TN( 12 ), NULL, NULL, BLACK },
- { 12, TN( 16 ), TN( 11 ), TN( 14 ), RED },
- { 13, TN( 14 ), NULL, NULL, RED },
- { 14, TN( 12 ), TN( 13 ), TN( 15 ), BLACK },
- { 15, TN( 14 ), NULL, NULL, RED },
- { 16, TN( 8 ), TN( 12 ), TN( 20 ), BLACK },
- { 17, TN( 20 ), NULL, NULL, RED },
- { 20, TN( 16 ), TN( 17 ), TN( 21 ), BLACK },
- { 21, TN( 20 ), NULL, NULL, RED }
+ { 0, TN(2), NULL, NULL, RED },
+ { 2, TN(8), TN(0), TN(7), BLACK },
+ { 7, TN(2), NULL, NULL, RED },
+ { 8, TN(12), TN(2), TN(11), BLACK },
+ { 11, TN(8), NULL, NULL, BLACK },
+ { 12, NULL, TN(8), TN(17), BLACK },
+ { 13, TN(15), NULL, TN(14), BLACK },
+ { 14, TN(13), NULL, NULL, RED },
+ { 15, TN(17), TN(13), TN(16), RED },
+ { 16, TN(15), NULL, NULL, BLACK },
+ { 17, TN(12), TN(15), TN(20), BLACK },
+ { 20, TN(17), NULL, TN(21), BLACK },
+ { 21, TN(20), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_multiple_23[] = {
- { 0, TN( 2 ), NULL, NULL, BLACK },
- { 1, TN( 8 ), TN( 0 ), TN( 7 ), RED },
- { 3, TN( 2 ), NULL, NULL, BLACK },
- { 4, TN( 12 ), TN( 2 ), TN( 11 ), BLACK },
- { 5, TN( 8 ), NULL, NULL, BLACK },
- { 6, NULL, TN( 8 ), TN( 17 ), BLACK },
- { 6, TN( 15 ), NULL, NULL, BLACK },
- { 7, TN( 17 ), TN( 13 ), TN( 16 ), RED },
- { 7, TN( 16 ), NULL, NULL, RED },
- { 8, TN( 15 ), TN( 14 ), NULL, BLACK },
- { 8, TN( 12 ), TN( 15 ), TN( 20 ), BLACK },
- { 10, TN( 17 ), NULL, TN( 21 ), BLACK },
- { 10, TN( 20 ), NULL, NULL, RED }
+ { 0, TN(2), NULL, NULL, RED },
+ { 1, TN(8), TN(0), TN(7), BLACK },
+ { 3, TN(2), NULL, NULL, RED },
+ { 4, TN(12), TN(2), TN(11), BLACK },
+ { 5, TN(8), NULL, NULL, BLACK },
+ { 6, NULL, TN(8), TN(17), BLACK },
+ { 6, TN(15), NULL, NULL, BLACK },
+ { 7, TN(17), TN(13), TN(16), RED },
+ { 7, TN(16), NULL, NULL, RED },
+ { 8, TN(15), TN(14), NULL, BLACK },
+ { 8, TN(12), TN(15), TN(20), BLACK },
+ { 10, TN(17), NULL, TN(21), BLACK },
+ { 10, TN(20), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_unique_24[] = {
- { 4, TN( 5 ), NULL, NULL, BLACK },
- { 5, TN( 8 ), TN( 4 ), TN( 6 ), RED },
- { 6, TN( 5 ), NULL, NULL, BLACK },
- { 8, TN( 14 ), TN( 5 ), TN( 10 ), BLACK },
- { 10, TN( 8 ), NULL, NULL, BLACK },
- { 14, NULL, TN( 8 ), TN( 20 ), BLACK },
- { 15, TN( 16 ), NULL, NULL, RED },
- { 16, TN( 20 ), TN( 15 ), NULL, BLACK },
- { 20, TN( 14 ), TN( 16 ), TN( 22 ), BLACK },
- { 22, TN( 20 ), NULL, NULL, BLACK }
+ { 4, TN(6), NULL, TN(5), BLACK },
+ { 5, TN(4), NULL, NULL, RED },
+ { 6, TN(14), TN(4), TN(10), BLACK },
+ { 8, TN(10), NULL, NULL, RED },
+ { 10, TN(6), TN(8), NULL, BLACK },
+ { 14, NULL, TN(6), TN(20), BLACK },
+ { 15, TN(16), NULL, NULL, RED },
+ { 16, TN(20), TN(15), NULL, BLACK },
+ { 20, TN(14), TN(16), TN(22), BLACK },
+ { 22, TN(20), NULL, NULL, BLACK }
};
static const test_node_description random_ops_tree_multiple_24[] = {
- { 2, TN( 6 ), NULL, TN( 5 ), BLACK },
- { 2, TN( 4 ), NULL, NULL, RED },
- { 3, TN( 10 ), TN( 4 ), TN( 8 ), BLACK },
- { 4, TN( 6 ), NULL, NULL, BLACK },
- { 5, NULL, TN( 6 ), TN( 16 ), BLACK },
- { 7, TN( 16 ), NULL, TN( 15 ), BLACK },
- { 7, TN( 14 ), NULL, NULL, RED },
- { 8, TN( 10 ), TN( 14 ), TN( 22 ), BLACK },
- { 10, TN( 22 ), NULL, NULL, RED },
- { 11, TN( 16 ), TN( 20 ), NULL, BLACK }
+ { 2, TN(6), NULL, TN(5), BLACK },
+ { 2, TN(4), NULL, NULL, RED },
+ { 3, TN(14), TN(4), TN(10), BLACK },
+ { 4, TN(10), NULL, NULL, RED },
+ { 5, TN(6), TN(8), NULL, BLACK },
+ { 7, NULL, TN(6), TN(20), BLACK },
+ { 7, TN(16), NULL, NULL, RED },
+ { 8, TN(20), TN(15), NULL, BLACK },
+ { 10, TN(14), TN(16), TN(22), BLACK },
+ { 11, TN(20), NULL, NULL, BLACK }
};
static const test_node_description random_ops_tree_unique_25[] = {
- { 0, TN( 1 ), NULL, NULL, BLACK },
- { 1, TN( 13 ), TN( 0 ), TN( 4 ), BLACK },
- { 3, TN( 4 ), NULL, NULL, BLACK },
- { 4, TN( 1 ), TN( 3 ), TN( 6 ), RED },
- { 5, TN( 6 ), NULL, NULL, RED },
- { 6, TN( 4 ), TN( 5 ), TN( 9 ), BLACK },
- { 9, TN( 6 ), NULL, NULL, RED },
- { 13, NULL, TN( 1 ), TN( 19 ), BLACK },
- { 14, TN( 15 ), NULL, NULL, RED },
- { 15, TN( 16 ), TN( 14 ), NULL, BLACK },
- { 16, TN( 19 ), TN( 15 ), TN( 17 ), RED },
- { 17, TN( 16 ), NULL, NULL, BLACK },
- { 19, TN( 13 ), TN( 16 ), TN( 23 ), BLACK },
- { 23, TN( 19 ), NULL, TN( 24 ), BLACK },
- { 24, TN( 23 ), NULL, NULL, RED }
+ { 0, TN(1), NULL, NULL, RED },
+ { 1, TN(3), TN(0), NULL, BLACK },
+ { 3, TN(13), TN(1), TN(5), BLACK },
+ { 4, TN(5), NULL, NULL, BLACK },
+ { 5, TN(3), TN(4), TN(6), RED },
+ { 6, TN(5), NULL, TN(9), BLACK },
+ { 9, TN(6), NULL, NULL, RED },
+ { 13, NULL, TN(3), TN(19), BLACK },
+ { 14, TN(15), NULL, NULL, RED },
+ { 15, TN(16), TN(14), NULL, BLACK },
+ { 16, TN(19), TN(15), TN(17), RED },
+ { 17, TN(16), NULL, NULL, BLACK },
+ { 19, TN(13), TN(16), TN(23), BLACK },
+ { 23, TN(19), NULL, TN(24), BLACK },
+ { 24, TN(23), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_multiple_25[] = {
- { 0, TN( 1 ), NULL, NULL, BLACK },
- { 0, TN( 5 ), TN( 0 ), TN( 3 ), RED },
- { 1, TN( 1 ), NULL, NULL, BLACK },
- { 2, TN( 13 ), TN( 1 ), TN( 6 ), BLACK },
- { 2, TN( 6 ), NULL, NULL, RED },
- { 3, TN( 5 ), TN( 4 ), TN( 9 ), BLACK },
- { 4, TN( 6 ), NULL, NULL, RED },
- { 6, NULL, TN( 5 ), TN( 19 ), BLACK },
- { 7, TN( 17 ), NULL, TN( 14 ), BLACK },
- { 7, TN( 15 ), NULL, NULL, RED },
- { 8, TN( 19 ), TN( 15 ), TN( 16 ), RED },
- { 8, TN( 17 ), NULL, NULL, BLACK },
- { 9, TN( 13 ), TN( 17 ), TN( 23 ), BLACK },
- { 11, TN( 19 ), NULL, TN( 24 ), BLACK },
- { 12, TN( 23 ), NULL, NULL, RED }
+ { 0, TN(3), NULL, TN(1), BLACK },
+ { 0, TN(0), NULL, NULL, RED },
+ { 1, TN(13), TN(0), TN(4), BLACK },
+ { 2, TN(4), NULL, NULL, BLACK },
+ { 2, TN(3), TN(5), TN(6), RED },
+ { 3, TN(4), NULL, TN(9), BLACK },
+ { 4, TN(6), NULL, NULL, RED },
+ { 6, NULL, TN(3), TN(19), BLACK },
+ { 7, TN(17), NULL, TN(14), BLACK },
+ { 7, TN(15), NULL, NULL, RED },
+ { 8, TN(19), TN(15), TN(16), RED },
+ { 8, TN(17), NULL, NULL, BLACK },
+ { 9, TN(13), TN(17), TN(23), BLACK },
+ { 11, TN(19), NULL, TN(24), BLACK },
+ { 12, TN(23), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_unique_26[] = {
- { 0, TN( 1 ), NULL, NULL, RED },
- { 1, TN( 6 ), TN( 0 ), TN( 3 ), BLACK },
- { 3, TN( 1 ), NULL, NULL, RED },
- { 6, TN( 11 ), TN( 1 ), TN( 9 ), BLACK },
- { 9, TN( 6 ), NULL, TN( 10 ), BLACK },
- { 10, TN( 9 ), NULL, NULL, RED },
- { 11, NULL, TN( 6 ), TN( 14 ), BLACK },
- { 12, TN( 14 ), NULL, TN( 13 ), BLACK },
- { 13, TN( 12 ), NULL, NULL, RED },
- { 14, TN( 11 ), TN( 12 ), TN( 20 ), BLACK },
- { 18, TN( 20 ), NULL, NULL, BLACK },
- { 20, TN( 14 ), TN( 18 ), TN( 23 ), RED },
- { 21, TN( 23 ), NULL, NULL, RED },
- { 23, TN( 20 ), TN( 21 ), NULL, BLACK }
+ { 0, TN(1), NULL, NULL, RED },
+ { 1, TN(3), TN(0), NULL, BLACK },
+ { 3, TN(11), TN(1), TN(9), BLACK },
+ { 6, TN(9), NULL, NULL, RED },
+ { 9, TN(3), TN(6), TN(10), BLACK },
+ { 10, TN(9), NULL, NULL, RED },
+ { 11, NULL, TN(3), TN(14), BLACK },
+ { 12, TN(14), NULL, TN(13), BLACK },
+ { 13, TN(12), NULL, NULL, RED },
+ { 14, TN(11), TN(12), TN(20), BLACK },
+ { 18, TN(20), NULL, NULL, BLACK },
+ { 20, TN(14), TN(18), TN(23), RED },
+ { 21, TN(23), NULL, NULL, RED },
+ { 23, TN(20), TN(21), NULL, BLACK }
};
static const test_node_description random_ops_tree_multiple_26[] = {
- { 0, TN( 0 ), NULL, NULL, RED },
- { 0, TN( 6 ), TN( 1 ), TN( 3 ), BLACK },
- { 1, TN( 0 ), NULL, NULL, RED },
- { 3, TN( 12 ), TN( 0 ), TN( 11 ), BLACK },
- { 4, TN( 11 ), NULL, NULL, RED },
- { 5, TN( 6 ), TN( 9 ), TN( 10 ), BLACK },
- { 5, TN( 11 ), NULL, NULL, RED },
- { 6, NULL, TN( 6 ), TN( 18 ), BLACK },
- { 6, TN( 14 ), NULL, NULL, RED },
- { 7, TN( 18 ), TN( 13 ), NULL, BLACK },
- { 9, TN( 12 ), TN( 14 ), TN( 21 ), BLACK },
- { 10, TN( 21 ), NULL, NULL, RED },
- { 10, TN( 18 ), TN( 20 ), TN( 23 ), BLACK },
- { 11, TN( 21 ), NULL, NULL, RED }
+ { 0, TN(3), NULL, TN(0), BLACK },
+ { 0, TN(1), NULL, NULL, RED },
+ { 1, TN(9), TN(1), TN(6), BLACK },
+ { 3, TN(3), NULL, NULL, BLACK },
+ { 4, NULL, TN(3), TN(14), BLACK },
+ { 5, TN(12), NULL, TN(10), BLACK },
+ { 5, TN(11), NULL, NULL, RED },
+ { 6, TN(14), TN(11), TN(13), RED },
+ { 6, TN(12), NULL, NULL, BLACK },
+ { 7, TN(9), TN(12), TN(20), BLACK },
+ { 9, TN(20), NULL, NULL, BLACK },
+ { 10, TN(14), TN(18), TN(23), RED },
+ { 10, TN(23), NULL, NULL, RED },
+ { 11, TN(20), TN(21), NULL, BLACK }
};
static const test_node_description random_ops_tree_unique_27[] = {
- { 3, TN( 8 ), NULL, NULL, BLACK },
- { 8, TN( 19 ), TN( 3 ), TN( 17 ), RED },
- { 12, TN( 17 ), NULL, NULL, RED },
- { 17, TN( 8 ), TN( 12 ), NULL, BLACK },
- { 19, NULL, TN( 8 ), TN( 23 ), BLACK },
- { 20, TN( 23 ), NULL, TN( 21 ), BLACK },
- { 21, TN( 20 ), NULL, NULL, RED },
- { 23, TN( 19 ), TN( 20 ), TN( 25 ), RED },
- { 24, TN( 25 ), NULL, NULL, RED },
- { 25, TN( 23 ), TN( 24 ), TN( 26 ), BLACK },
- { 26, TN( 25 ), NULL, NULL, RED }
+ { 3, TN(8), NULL, NULL, BLACK },
+ { 8, TN(19), TN(3), TN(17), BLACK },
+ { 12, TN(17), NULL, NULL, RED },
+ { 17, TN(8), TN(12), NULL, BLACK },
+ { 19, NULL, TN(8), TN(24), BLACK },
+ { 20, TN(21), NULL, NULL, RED },
+ { 21, TN(24), TN(20), TN(23), BLACK },
+ { 23, TN(21), NULL, NULL, RED },
+ { 24, TN(19), TN(21), TN(25), BLACK },
+ { 25, TN(24), NULL, TN(26), BLACK },
+ { 26, TN(25), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_multiple_27[] = {
- { 1, TN( 8 ), NULL, NULL, BLACK },
- { 4, TN( 19 ), TN( 3 ), TN( 17 ), RED },
- { 6, TN( 17 ), NULL, NULL, RED },
- { 8, TN( 8 ), TN( 12 ), NULL, BLACK },
- { 9, NULL, TN( 8 ), TN( 23 ), BLACK },
- { 10, TN( 23 ), NULL, TN( 21 ), BLACK },
- { 10, TN( 20 ), NULL, NULL, RED },
- { 11, TN( 19 ), TN( 20 ), TN( 24 ), RED },
- { 12, TN( 24 ), NULL, NULL, RED },
- { 12, TN( 23 ), TN( 25 ), TN( 26 ), BLACK },
- { 13, TN( 24 ), NULL, NULL, RED }
+ { 1, TN(8), NULL, NULL, BLACK },
+ { 4, TN(19), TN(3), TN(17), BLACK },
+ { 6, TN(17), NULL, NULL, RED },
+ { 8, TN(8), TN(12), NULL, BLACK },
+ { 9, NULL, TN(8), TN(25), BLACK },
+ { 10, TN(21), NULL, NULL, RED },
+ { 10, TN(25), TN(20), TN(23), BLACK },
+ { 11, TN(21), NULL, NULL, RED },
+ { 12, TN(19), TN(21), TN(24), BLACK },
+ { 12, TN(25), NULL, TN(26), BLACK },
+ { 13, TN(24), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_unique_28[] = {
- { 0, TN( 5 ), NULL, NULL, BLACK },
- { 5, TN( 13 ), TN( 0 ), TN( 7 ), RED },
- { 7, TN( 5 ), NULL, NULL, BLACK },
- { 13, NULL, TN( 5 ), TN( 17 ), BLACK },
- { 15, TN( 17 ), NULL, NULL, BLACK },
- { 17, TN( 13 ), TN( 15 ), TN( 26 ), RED },
- { 21, TN( 26 ), NULL, NULL, RED },
- { 26, TN( 17 ), TN( 21 ), NULL, BLACK }
+ { 0, TN(5), NULL, NULL, BLACK },
+ { 5, TN(13), TN(0), TN(7), RED },
+ { 7, TN(5), NULL, NULL, BLACK },
+ { 13, NULL, TN(5), TN(17), BLACK },
+ { 15, TN(17), NULL, NULL, BLACK },
+ { 17, TN(13), TN(15), TN(26), RED },
+ { 21, TN(26), NULL, NULL, RED },
+ { 26, TN(17), TN(21), NULL, BLACK }
};
static const test_node_description random_ops_tree_multiple_28[] = {
- { 0, TN( 5 ), NULL, NULL, RED },
- { 2, TN( 7 ), TN( 0 ), NULL, BLACK },
- { 3, NULL, TN( 5 ), TN( 15 ), BLACK },
- { 6, TN( 15 ), NULL, NULL, BLACK },
- { 7, TN( 7 ), TN( 13 ), TN( 21 ), RED },
- { 8, TN( 21 ), NULL, NULL, RED },
- { 10, TN( 15 ), TN( 17 ), TN( 26 ), BLACK },
- { 13, TN( 21 ), NULL, NULL, RED }
+ { 0, TN(5), NULL, NULL, BLACK },
+ { 2, TN(13), TN(0), TN(7), RED },
+ { 3, TN(5), NULL, NULL, BLACK },
+ { 6, NULL, TN(5), TN(17), BLACK },
+ { 7, TN(17), NULL, NULL, BLACK },
+ { 8, TN(13), TN(15), TN(26), RED },
+ { 10, TN(26), NULL, NULL, RED },
+ { 13, TN(17), TN(21), NULL, BLACK }
};
static const test_node_description random_ops_tree_unique_29[] = {
- { 0, TN( 1 ), NULL, NULL, RED },
- { 1, TN( 4 ), TN( 0 ), TN( 3 ), BLACK },
- { 3, TN( 1 ), NULL, NULL, RED },
- { 4, TN( 11 ), TN( 1 ), TN( 7 ), BLACK },
- { 6, TN( 7 ), NULL, NULL, RED },
- { 7, TN( 4 ), TN( 6 ), TN( 8 ), BLACK },
- { 8, TN( 7 ), NULL, NULL, RED },
- { 11, NULL, TN( 4 ), TN( 13 ), BLACK },
- { 12, TN( 13 ), NULL, NULL, BLACK },
- { 13, TN( 11 ), TN( 12 ), TN( 22 ), BLACK },
- { 14, TN( 17 ), NULL, NULL, RED },
- { 17, TN( 22 ), TN( 14 ), NULL, BLACK },
- { 22, TN( 13 ), TN( 17 ), TN( 25 ), RED },
- { 25, TN( 22 ), NULL, TN( 27 ), BLACK },
- { 27, TN( 25 ), NULL, NULL, RED }
+ { 0, TN(3), NULL, TN(1), BLACK },
+ { 1, TN(0), NULL, NULL, RED },
+ { 3, TN(12), TN(0), TN(6), BLACK },
+ { 4, TN(6), NULL, NULL, BLACK },
+ { 6, TN(3), TN(4), TN(8), RED },
+ { 7, TN(8), NULL, NULL, RED },
+ { 8, TN(6), TN(7), TN(11), BLACK },
+ { 11, TN(8), NULL, NULL, RED },
+ { 12, NULL, TN(3), TN(17), BLACK },
+ { 13, TN(17), NULL, TN(14), BLACK },
+ { 14, TN(13), NULL, NULL, RED },
+ { 17, TN(12), TN(13), TN(25), BLACK },
+ { 22, TN(25), NULL, NULL, RED },
+ { 25, TN(17), TN(22), TN(27), BLACK },
+ { 27, TN(25), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_multiple_29[] = {
- { 0, TN( 3 ), NULL, TN( 1 ), BLACK },
- { 0, TN( 0 ), NULL, NULL, RED },
- { 1, TN( 11 ), TN( 0 ), TN( 6 ), BLACK },
- { 2, TN( 6 ), NULL, NULL, BLACK },
- { 3, TN( 3 ), TN( 4 ), TN( 7 ), RED },
- { 3, TN( 6 ), NULL, TN( 8 ), BLACK },
- { 4, TN( 7 ), NULL, NULL, RED },
- { 5, NULL, TN( 3 ), TN( 12 ), BLACK },
- { 6, TN( 12 ), NULL, NULL, BLACK },
- { 6, TN( 11 ), TN( 13 ), TN( 22 ), BLACK },
- { 7, TN( 17 ), NULL, NULL, RED },
- { 8, TN( 22 ), TN( 14 ), NULL, BLACK },
- { 11, TN( 12 ), TN( 17 ), TN( 25 ), RED },
- { 12, TN( 22 ), NULL, TN( 27 ), BLACK },
- { 13, TN( 25 ), NULL, NULL, RED }
+ { 0, TN(3), NULL, TN(1), BLACK },
+ { 0, TN(0), NULL, NULL, RED },
+ { 1, TN(11), TN(0), TN(6), BLACK },
+ { 2, TN(6), NULL, NULL, BLACK },
+ { 3, TN(3), TN(4), TN(7), RED },
+ { 3, TN(6), NULL, TN(8), BLACK },
+ { 4, TN(7), NULL, NULL, RED },
+ { 5, NULL, TN(3), TN(22), BLACK },
+ { 6, TN(12), NULL, NULL, BLACK },
+ { 6, TN(22), TN(13), TN(17), RED },
+ { 7, TN(17), NULL, NULL, RED },
+ { 8, TN(12), TN(14), NULL, BLACK },
+ { 11, TN(11), TN(12), TN(25), BLACK },
+ { 12, TN(22), NULL, TN(27), BLACK },
+ { 13, TN(25), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_unique_30[] = {
- { 0, TN( 4 ), NULL, NULL, BLACK },
- { 4, TN( 12 ), TN( 0 ), TN( 8 ), RED },
- { 6, TN( 8 ), NULL, NULL, RED },
- { 8, TN( 4 ), TN( 6 ), TN( 9 ), BLACK },
- { 9, TN( 8 ), NULL, NULL, RED },
- { 12, TN( 14 ), TN( 4 ), TN( 13 ), BLACK },
- { 13, TN( 12 ), NULL, NULL, BLACK },
- { 14, NULL, TN( 12 ), TN( 17 ), BLACK },
- { 16, TN( 17 ), NULL, NULL, BLACK },
- { 17, TN( 14 ), TN( 16 ), TN( 20 ), BLACK },
- { 18, TN( 20 ), NULL, NULL, BLACK },
- { 20, TN( 17 ), TN( 18 ), TN( 28 ), RED },
- { 27, TN( 28 ), NULL, NULL, RED },
- { 28, TN( 20 ), TN( 27 ), NULL, BLACK }
+ { 0, TN(4), NULL, NULL, RED },
+ { 4, TN(6), TN(0), NULL, BLACK },
+ { 6, TN(13), TN(4), TN(9), RED },
+ { 8, TN(9), NULL, NULL, RED },
+ { 9, TN(6), TN(8), TN(12), BLACK },
+ { 12, TN(9), NULL, NULL, RED },
+ { 13, NULL, TN(6), TN(18), BLACK },
+ { 14, TN(16), NULL, NULL, RED },
+ { 16, TN(18), TN(14), TN(17), BLACK },
+ { 17, TN(16), NULL, NULL, RED },
+ { 18, TN(13), TN(16), TN(27), RED },
+ { 20, TN(27), NULL, NULL, RED },
+ { 27, TN(18), TN(20), TN(28), BLACK },
+ { 28, TN(27), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_multiple_30[] = {
- { 0, TN( 4 ), NULL, NULL, RED },
- { 2, TN( 6 ), TN( 0 ), NULL, BLACK },
- { 3, TN( 12 ), TN( 4 ), TN( 8 ), RED },
- { 4, TN( 8 ), NULL, NULL, RED },
- { 4, TN( 6 ), TN( 9 ), TN( 13 ), BLACK },
- { 6, TN( 8 ), NULL, NULL, RED },
- { 6, NULL, TN( 6 ), TN( 18 ), BLACK },
- { 7, TN( 17 ), NULL, NULL, RED },
- { 8, TN( 18 ), TN( 14 ), TN( 16 ), BLACK },
- { 8, TN( 17 ), NULL, NULL, RED },
- { 9, TN( 12 ), TN( 17 ), TN( 27 ), RED },
- { 10, TN( 27 ), NULL, NULL, RED },
- { 13, TN( 18 ), TN( 20 ), TN( 28 ), BLACK },
- { 14, TN( 27 ), NULL, NULL, RED }
+ { 0, TN(4), NULL, NULL, BLACK },
+ { 2, TN(13), TN(0), TN(9), RED },
+ { 3, TN(9), NULL, NULL, RED },
+ { 4, TN(4), TN(6), TN(8), BLACK },
+ { 4, TN(9), NULL, NULL, RED },
+ { 6, TN(14), TN(4), TN(12), BLACK },
+ { 6, TN(13), NULL, NULL, BLACK },
+ { 7, NULL, TN(13), TN(18), BLACK },
+ { 8, TN(18), NULL, TN(16), BLACK },
+ { 8, TN(17), NULL, NULL, RED },
+ { 9, TN(14), TN(17), TN(27), BLACK },
+ { 10, TN(27), NULL, NULL, RED },
+ { 13, TN(18), TN(20), TN(28), BLACK },
+ { 14, TN(27), NULL, NULL, RED }
};
static const test_node_description random_ops_tree_unique_31[] = {
- { 0, TN( 2 ), NULL, NULL, RED },
- { 2, TN( 5 ), TN( 0 ), NULL, BLACK },
- { 5, TN( 14 ), TN( 2 ), TN( 9 ), BLACK },
- { 7, TN( 9 ), NULL, NULL, RED },
- { 9, TN( 5 ), TN( 7 ), TN( 11 ), BLACK },
- { 11, TN( 9 ), NULL, NULL, RED },
- { 14, NULL, TN( 5 ), TN( 21 ), BLACK },
- { 16, TN( 21 ), NULL, TN( 18 ), BLACK },
- { 18, TN( 16 ), NULL, NULL, RED },
- { 21, TN( 14 ), TN( 16 ), TN( 30 ), BLACK },
- { 30, TN( 21 ), NULL, NULL, BLACK }
+ { 0, TN(2), NULL, NULL, RED },
+ { 2, TN(5), TN(0), NULL, BLACK },
+ { 5, TN(11), TN(2), TN(9), BLACK },
+ { 7, TN(9), NULL, NULL, RED },
+ { 9, TN(5), TN(7), NULL, BLACK },
+ { 11, NULL, TN(5), TN(21), BLACK },
+ { 14, TN(16), NULL, NULL, RED },
+ { 16, TN(21), TN(14), TN(18), BLACK },
+ { 18, TN(16), NULL, NULL, RED },
+ { 21, TN(11), TN(16), TN(30), BLACK },
+ { 30, TN(21), NULL, NULL, BLACK }
};
static const test_node_description random_ops_tree_multiple_31[] = {
- { 0, TN( 2 ), NULL, NULL, RED },
- { 1, TN( 5 ), TN( 0 ), NULL, BLACK },
- { 2, TN( 11 ), TN( 2 ), TN( 9 ), BLACK },
- { 3, TN( 9 ), NULL, NULL, RED },
- { 4, TN( 5 ), TN( 7 ), NULL, BLACK },
- { 5, NULL, TN( 5 ), TN( 21 ), BLACK },
- { 7, TN( 16 ), NULL, NULL, RED },
- { 8, TN( 21 ), TN( 14 ), TN( 18 ), BLACK },
- { 9, TN( 16 ), NULL, NULL, RED },
- { 10, TN( 11 ), TN( 16 ), TN( 30 ), BLACK },
- { 15, TN( 21 ), NULL, NULL, BLACK }
+ { 0, TN(2), NULL, NULL, RED },
+ { 1, TN(5), TN(0), NULL, BLACK },
+ { 2, TN(11), TN(2), TN(9), BLACK },
+ { 3, TN(9), NULL, NULL, RED },
+ { 4, TN(5), TN(7), NULL, BLACK },
+ { 5, NULL, TN(5), TN(21), BLACK },
+ { 7, TN(16), NULL, NULL, RED },
+ { 8, TN(21), TN(14), TN(18), BLACK },
+ { 9, TN(16), NULL, NULL, RED },
+ { 10, TN(11), TN(16), TN(30), BLACK },
+ { 15, TN(21), NULL, NULL, BLACK }
};
#define RANDOM_OPS_TREE( i ) \
@@ -1698,13 +1698,6 @@ rtems_task Init( rtems_task_argument ignored )
rtems_test_assert( !rtems_rbtree_is_node_off_tree( &node1.Node ) );
- i = (node1.Node.parent == &node2.Node);
- _RBTree_Rotate( &node1.Node,
- !node1.Node.child[RBT_LEFT] ? RBT_RIGHT : RBT_LEFT
- );
- if ( (node1.Node.parent == &node2.Node) != i )
- puts( "INIT - FAILED FALSE ROTATION" );
-
if (!rb_assert(rtems_rbtree_root(&rbtree1)) )
puts( "INIT - FAILED TREE CHECK" );
@@ -2027,10 +2020,8 @@ rtems_task Init( rtems_task_argument ignored )
rtems_test_exit(0);
}
- if ( _RBTree_Is_red( NULL ) != 0 )
- puts ( "INIT - ERROR ON RBTREE NULL IS RED MISMATCH" );
- if ( _RBTree_Is_red( rbtree1.root ) != 0 )
- puts ( "INIT - ERROR ON RBTREE NULL IS RED MISMATCH" );
+ if ( rb_color( rtems_rbtree_root(&rbtree1) ) != BLACK )
+ puts ( "INIT - ERROR ON RBTREE ROOT IS BLACK MISMATCH" );
puts( "INIT - Removing 100 nodes" );
More information about the vc
mailing list