From e9fbaa3b48364c821f5fb8ef7d7b7504be957e0e Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Fri, 21 Aug 2015 05:59:49 +0200 Subject: rbtree: Replace implementation Use the BSD 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 b44c09edb5..077f2b181d 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 - -#include +#include +#include #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 ) @@ -200,6 +139,95 @@ RBTree_Node *_RBTree_Insert( bool is_unique ); +/** + * @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 + * + * 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. * @@ -217,20 +245,6 @@ void _RBTree_Extract( RBTree_Node *the_node ); -/** - * @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. * @@ -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 607e7ebf84..9c748eb01c 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 1aaba270e7..4d8a8f8eed 100644 --- a/cpukit/score/src/rbtreeextract.c +++ b/cpukit/score/src/rbtreeextract.c @@ -12,198 +12,14 @@ #include -/** @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 168a108962..f920febd41 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 a7be449420..629fca7795 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 2128ae59bf..7096b4b22f 100644 --- a/cpukit/score/src/rbtreenext.c +++ b/cpukit/score/src/rbtreenext.c @@ -25,39 +25,30 @@ #endif #include -#include +#include -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 0fe72a4e3f..c58c6d56af 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" ); -- cgit v1.2.3