diff options
author | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2014-07-21 18:08:07 +0200 |
---|---|---|
committer | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2014-07-22 12:30:53 +0200 |
commit | 6b0a7efc77bd0dec7acdd84b692e266f5183b2b6 (patch) | |
tree | 19d1b30410bc2f17d8c04a06dd9da0cd056981f2 /cpukit/score/src/rbtreeinsert.c | |
parent | doc: Update console driver documentation (diff) | |
download | rtems-6b0a7efc77bd0dec7acdd84b692e266f5183b2b6.tar.bz2 |
rbtree: Format
Diffstat (limited to 'cpukit/score/src/rbtreeinsert.c')
-rw-r--r-- | cpukit/score/src/rbtreeinsert.c | 70 |
1 files changed, 39 insertions, 31 deletions
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c index 7174529ade..c77c5748bf 100644 --- a/cpukit/score/src/rbtreeinsert.c +++ b/cpukit/score/src/rbtreeinsert.c @@ -21,42 +21,43 @@ * @note It does NOT disable interrupts to ensure the atomicity of the * append operation. */ -static void _RBTree_Validate_insert( - RBTree_Node *the_node - ) +static void _RBTree_Validate_insert( RBTree_Node *the_node ) { - RBTree_Node *u,*g; + RBTree_Node *u, *g; /* note: the insert root case is handled already */ /* if the parent is black, nothing needs to be done * otherwise may need to loop a few times */ - while (_RBTree_Is_red(_RBTree_Parent(the_node))) { - u = _RBTree_Parent_sibling(the_node); + while ( _RBTree_Is_red( _RBTree_Parent( the_node ) ) ) { + u = _RBTree_Parent_sibling( the_node ); g = the_node->parent->parent; /* if uncle is red, repaint uncle/parent black and grandparent red */ - if(_RBTree_Is_red(u)) { + if ( _RBTree_Is_red( u ) ) { the_node->parent->color = RBT_BLACK; u->color = RBT_BLACK; g->color = RBT_RED; the_node = g; } else { /* if uncle is black */ - RBTree_Direction dir = the_node != the_node->parent->child[0]; - RBTree_Direction pdir = the_node->parent != g->child[0]; + RBTree_Direction dir = the_node != the_node->parent->child[ 0 ]; + RBTree_Direction pdir = the_node->parent != g->child[ 0 ]; /* ensure node is on the same branch direction as parent */ - if (dir != pdir) { - _RBTree_Rotate(the_node->parent, pdir); - the_node = the_node->child[pdir]; + if ( dir != pdir ) { + _RBTree_Rotate( the_node->parent, pdir ); + the_node = the_node->child[ pdir ]; } + the_node->parent->color = RBT_BLACK; g->color = RBT_RED; /* now rotate grandparent in the other branch direction (toward uncle) */ - _RBTree_Rotate(g, (1-pdir)); + _RBTree_Rotate( g, ( 1 - pdir ) ); } } - if(!the_node->parent->parent) the_node->color = RBT_BLACK; + + if ( !the_node->parent->parent ) + the_node->color = RBT_BLACK; } RBTree_Node *_RBTree_Insert( @@ -66,47 +67,54 @@ RBTree_Node *_RBTree_Insert( bool is_unique ) { - if(!the_node) return (RBTree_Node*)-1; + if ( !the_node ) + return (RBTree_Node *) -1; RBTree_Node *iter_node = the_rbtree->root; - int compare_result; - if (!iter_node) { /* special case: first node inserted */ + if ( !iter_node ) { /* special case: first node inserted */ the_node->color = RBT_BLACK; the_rbtree->root = the_node; - the_rbtree->first[0] = the_rbtree->first[1] = the_node; + 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; + the_node->child[ RBT_LEFT ] = the_node->child[ RBT_RIGHT ] = NULL; } else { /* typical binary search tree insert, descend tree to leaf and insert */ - while (iter_node) { - compare_result = ( *compare )( the_node, iter_node ); + while ( iter_node ) { + int compare_result = ( *compare )( the_node, iter_node ); + if ( is_unique && _RBTree_Is_equal( compare_result ) ) return iter_node; + RBTree_Direction dir = !_RBTree_Is_lesser( compare_result ); - if (!iter_node->child[dir]) { - the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL; + + 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; + 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 ( (!dir && _RBTree_Is_lesser(compare_result)) || - (dir && _RBTree_Is_greater(compare_result)) ) { - the_rbtree->first[dir] = the_node; + + if ( + ( !dir && _RBTree_Is_lesser( compare_result ) ) + || ( dir && _RBTree_Is_greater( compare_result ) ) + ) { + the_rbtree->first[ dir ] = the_node; } + break; } else { - iter_node = iter_node->child[dir]; + iter_node = iter_node->child[ dir ]; } - } /* while(iter_node) */ /* verify red-black properties */ - _RBTree_Validate_insert(the_node); + _RBTree_Validate_insert( the_node ); } - return (RBTree_Node*)0; + + return (RBTree_Node *) 0; } |