Changeset 55faa44 in rtems


Ignore:
Timestamp:
Aug 12, 2016, 9:16:45 AM (3 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
master
Children:
01aa1ba
Parents:
424ffe4d
Message:

score: Improve _RBTree_Insert_inline()

Return if the inserted node is the new minimum node or not.

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • cpukit/score/include/rtems/score/rbtree.h

    r424ffe4d r55faa44  
    452452 * @param less Must return true if the specified key is less than the key of
    453453 *   the node, otherwise false.
    454  */
    455 RTEMS_INLINE_ROUTINE void _RBTree_Insert_inline(
     454 *
     455 * @retval true The inserted node is the new minimum node according to the
     456 *   specified less order function.
     457 * @retval false Otherwise.
     458 */
     459RTEMS_INLINE_ROUTINE bool _RBTree_Insert_inline(
    456460  RBTree_Control *the_rbtree,
    457461  RBTree_Node    *the_node,
     
    462466  RBTree_Node **link;
    463467  RBTree_Node  *parent;
     468  bool          is_new_minimum;
    464469
    465470  link = _RBTree_Root_reference( the_rbtree );
    466471  parent = NULL;
     472  is_new_minimum = true;
    467473
    468474  while ( *link != NULL ) {
     
    473479    } else {
    474480      link = _RBTree_Right_reference( parent );
     481      is_new_minimum = false;
    475482    }
    476483  }
     
    478485  _RBTree_Add_child( the_node, parent, link );
    479486  _RBTree_Insert_color( the_rbtree, the_node );
     487  return is_new_minimum;
    480488}
    481489
  • testsuites/sptests/sprbtree01/init.c

    r424ffe4d r55faa44  
    233233  min_max_extract( &tree, node, min, max );
    234234  rtems_test_assert( rtems_rbtree_is_empty( &tree ) );
     235}
     236
     237static bool test_less(
     238  const void        *left,
     239  const RBTree_Node *right
     240)
     241{
     242  const int       *the_left;
     243  const test_node *the_right;
     244
     245  the_left = left;
     246  the_right = RTEMS_CONTAINER_OF( right, test_node, Node );
     247
     248  return *the_left < the_right->key;
     249}
     250
     251static void test_rbtree_insert_inline( void )
     252{
     253  RBTree_Control tree;
     254  test_node      a;
     255  test_node      b;
     256  test_node      c;
     257  int            key;
     258  bool           is_new_minimum;
     259
     260  puts( "INIT - Verify _RBTree_Insert_inline" );
     261
     262  a.key = 1;
     263  b.key = 2;
     264  c.key = 3;
     265
     266  _RBTree_Initialize_empty( &tree );
     267  _RBTree_Initialize_node( &a.Node );
     268  _RBTree_Initialize_node( &b.Node );
     269  _RBTree_Initialize_node( &c.Node );
     270
     271  key = b.key;
     272  is_new_minimum = _RBTree_Insert_inline(
     273    &tree,
     274    &b.Node,
     275    &key,
     276    test_less
     277  );
     278  rtems_test_assert( is_new_minimum );
     279
     280  key = c.key;
     281  is_new_minimum = _RBTree_Insert_inline(
     282    &tree,
     283    &c.Node,
     284    &key,
     285    test_less
     286  );
     287  rtems_test_assert( !is_new_minimum );
     288
     289  key = a.key;
     290  is_new_minimum = _RBTree_Insert_inline(
     291    &tree,
     292    &a.Node,
     293    &key,
     294    test_less
     295  );
     296  rtems_test_assert( is_new_minimum );
    235297}
    236298
     
    22112273
    22122274  test_rbtree_min_max();
     2275  test_rbtree_insert_inline();
    22132276  test_rbtree_random_ops();
    22142277
  • testsuites/sptests/sprbtree01/sprbtree01.scn

    r424ffe4d r55faa44  
    1919INIT - Verify rtems_rbtree_find
    2020INIT - Verify rtems_rbtree_predecessor/successor
    21 INIT - Verify rtems_rbtree_find_control
    2221INIT - Removing 100 nodes
    2322INIT - Insert 20 random numbers
     
    3332INIT - Removing 100 nodes
    3433INIT - Verify min/max node updates
     34INIT - Verify _RBTree_Insert_inline
    3535INIT - Random operations
    3636*** END OF TEST SPRBTREE 1 ***
Note: See TracChangeset for help on using the changeset viewer.