diff options
author | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2015-08-21 05:59:49 +0200 |
---|---|---|
committer | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2015-09-03 13:58:16 +0200 |
commit | e9fbaa3b48364c821f5fb8ef7d7b7504be957e0e (patch) | |
tree | b8401a96b7daec44038359d66dfa02876621dfc1 /cpukit/score/src/rbtreeinsert.c | |
parent | score: Optimize thread queue first operation (diff) | |
download | rtems-e9fbaa3b48364c821f5fb8ef7d7b7504be957e0e.tar.bz2 |
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.
Diffstat (limited to '')
-rw-r--r-- | cpukit/score/src/rbtreeinsert.c | 128 |
1 files changed, 26 insertions, 102 deletions
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 ); } |