Changeset aaaf9610 in rtems


Ignore:
Timestamp:
Aug 8, 2016, 6:44:51 AM (3 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
master
Children:
e5fd901
Parents:
2cb9b86e
git-author:
Sebastian Huber <sebastian.huber@…> (08/08/16 06:44:51)
git-committer:
Sebastian Huber <sebastian.huber@…> (08/08/16 07:34:29)
Message:

score: Add debug support to red-black trees

This helps to detect double insert and extract errors.

Files:
12 edited

Legend:

Unmodified
Added
Removed
  • cpukit/libfs/src/jffs2/include/linux/rbtree.h

    r2cb9b86e raaaf9610  
    118118)
    119119{
     120  _RBTree_Initialize_node( (RBTree_Node *) node );
    120121  _RBTree_Add_child(
    121122    (RBTree_Node *) node,
  • cpukit/posix/src/keysetspecific.c

    r2cb9b86e raaaf9610  
    5757      key_value_pair->thread = executing;
    5858      key_value_pair->value = RTEMS_DECONST( void *, value );
     59
     60      _RBTree_Initialize_node( &key_value_pair->Lookup_node );
    5961
    6062      _Chain_Initialize_node( &key_value_pair->Key_node );
  • cpukit/sapi/src/rbtreeinsert.c

    r2cb9b86e raaaf9610  
    5151  }
    5252
     53  _RBTree_Initialize_node( the_node );
    5354  _RBTree_Add_child( the_node, parent, which );
    5455  _RBTree_Insert_color( the_rbtree, the_node );
  • cpukit/score/include/rtems/score/rbtree.h

    r2cb9b86e raaaf9610  
    2121#include <sys/tree.h>
    2222#include <rtems/score/basedefs.h>
     23#include <rtems/score/assert.h>
    2324
    2425#ifdef __cplusplus
     
    7071
    7172/**
     73 * @brief Sets a red-black tree node as off-tree.
     74 *
     75 * Do not use this function on nodes which are a part of a tree.
     76 *
     77 * @param[in] the_node The node to set off-tree.
     78 *
     79 * @see _RBTree_Is_node_off_tree().
     80 */
     81RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node )
     82{
     83  RB_COLOR( the_node, Node ) = -1;
     84}
     85
     86/**
     87 * @brief Returns true, if this red-black tree node is off-tree, and false
     88 * otherwise.
     89 *
     90 * @param[in] the_node The node to test.
     91 *
     92 * @retval true The node is not a part of a tree (off-tree).
     93 * @retval false Otherwise.
     94 *
     95 * @see _RBTree_Set_off_tree().
     96 */
     97RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree(
     98  const RBTree_Node *the_node
     99)
     100{
     101  return RB_COLOR( the_node, Node ) == -1;
     102}
     103
     104/**
    72105 * @brief Rebalances the red-black tree after insertion of the node.
    73106 *
     
    81114
    82115/**
     116 * @brief Initializes a red-black tree node.
     117 *
     118 * In debug configurations, the node is set off tree.  In all other
     119 * configurations, this function does nothing.
     120 *
     121 * @param[in] the_node The red-black tree node to initialize.
     122 */
     123RTEMS_INLINE_ROUTINE void _RBTree_Initialize_node( RBTree_Node *the_node )
     124{
     125#if defined(RTEMS_DEBUG)
     126  _RBTree_Set_off_tree( the_node );
     127#endif
     128}
     129
     130/**
    83131 * @brief Adds a child node to a parent node.
    84132 *
     
    93141)
    94142{
     143  _Assert( _RBTree_Is_node_off_tree( child ) );
    95144  RB_SET( child, parent, Node );
    96145  *link = child;
     
    174223  RBTree_Node *the_node
    175224);
    176 
    177 /**
    178  * @brief Sets a red-black tree node as off-tree.
    179  *
    180  * Do not use this function on nodes which are a part of a tree.
    181  *
    182  * @param[in] the_node The node to set off-tree.
    183  *
    184  * @see _RBTree_Is_node_off_tree().
    185  */
    186 RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node )
    187 {
    188   RB_COLOR( the_node, Node ) = -1;
    189 }
    190 
    191 /**
    192  * @brief Returns true, if this red-black tree node is off-tree, and false
    193  * otherwise.
    194  *
    195  * @param[in] the_node The node to test.
    196  *
    197  * @retval true The node is not a part of a tree (off-tree).
    198  * @retval false Otherwise.
    199  *
    200  * @see _RBTree_Set_off_tree().
    201  */
    202 RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree(
    203   const RBTree_Node *the_node
    204 )
    205 {
    206   return RB_COLOR( the_node, Node ) == -1;
    207 }
    208225
    209226/**
  • cpukit/score/src/rbtreeextract.c

    r2cb9b86e raaaf9610  
    2323{
    2424  RB_REMOVE( RBTree_Control, the_rbtree, the_node );
     25#if defined(RTEMS_DEBUG)
     26  _RBTree_Set_off_tree( the_node );
     27#endif
    2528}
  • cpukit/score/src/scheduleredfnodeinit.c

    r2cb9b86e raaaf9610  
    3636  the_node = _Scheduler_EDF_Node_downcast( node );
    3737  the_node->thread = the_thread;
     38  _RBTree_Initialize_node( &the_node->Node );
    3839}
  • cpukit/score/src/threadinitialize.c

    r2cb9b86e raaaf9610  
    188188  );
    189189  _Thread_queue_Gate_open( &the_thread->Wait.Lock.Tranquilizer );
     190  _RBTree_Initialize_node( &the_thread->Wait.Link.Registry_node );
    190191  _SMP_lock_Stats_initialize( &the_thread->Potpourri_stats, "Thread Potpourri" );
    191192#endif
  • cpukit/score/src/threadmp.c

    r2cb9b86e raaaf9610  
    7373
    7474    _Thread_Timer_initialize( &proxy->Timer, _Per_CPU_Get_by_index( 0 ) );
     75    _RBTree_Initialize_node( &proxy->Active );
    7576
    7677    proxy->Wait.spare_heads = &proxy->Thread_queue_heads[ 0 ];
  • cpukit/score/src/threadqenqueue.c

    r2cb9b86e raaaf9610  
    252252  }
    253253
     254  _RBTree_Initialize_node( &path->Start.Registry_node );
    254255  _Chain_Initialize_node( &path->Start.Path_node );
    255256  _Thread_queue_Context_initialize( &path->Start.Queue_context );
  • cpukit/score/src/threadqops.c

    r2cb9b86e raaaf9610  
    243243
    244244  current_priority = the_thread->current_priority;
     245  _RBTree_Initialize_node( &the_thread->Wait.Node.RBTree );
    245246  _RBTree_Insert_inline(
    246247    &priority_queue->Queue,
  • cpukit/score/src/watchdoginsert.c

    r2cb9b86e raaaf9610  
    6161
    6262  header->first = new_first;
     63  _RBTree_Initialize_node( &the_watchdog->Node.RBTree );
    6364  _RBTree_Add_child( &the_watchdog->Node.RBTree, parent, link );
    6465  _RBTree_Insert_color( &header->Watchdogs, &the_watchdog->Node.RBTree );
  • testsuites/sptests/sprbtree01/init.c

    r2cb9b86e raaaf9610  
    18021802    rtems_test_exit(0);
    18031803  }
    1804   rtems_test_assert( !rtems_rbtree_is_node_off_tree( p ) );
    18051804  rb_insert_unique(&rbtree1, p);
    18061805
Note: See TracChangeset for help on using the changeset viewer.