Changeset 64939bc in rtems


Ignore:
Timestamp:
07/12/14 19:22:22 (9 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
4.11, 5, master
Children:
ed7a028
Parents:
7e119990
git-author:
Sebastian Huber <sebastian.huber@…> (07/12/14 19:22:22)
git-committer:
Joel Sherrill <joel.sherrill@…> (07/15/14 15:03:48)
Message:

rbtree: Reduce RBTree_Control size

Remove compare function and is unique indicator from the control
structure. Rename RBTree_Compare_function to RBTree_Compare. Rename
rtems_rbtree_compare_function to rtems_rbtree_compare. Provide C++
compatible initializers. Add compare function and is unique indicator
to _RBTree_Find(), _RBTree_Insert(), rtems_rbtree_find() and
rtems_rbtree_insert(). Remove _RBTree_Is_unique() and
rtems_rbtree_is_unique(). Remove compare function and is unique
indicator from _RBTree_Initialize_empty() and
rtems_rbtree_initialize_empty().

Files:
16 edited

Legend:

Unmodified
Added
Removed

  • cpukit/posix/include/rtems/posix/keyimpl.h

    r7e119990 r64939bc  
    4343 * @brief The rbtree control block used to manage all key values
    4444 */
    45 POSIX_EXTERN RBTree_Control _POSIX_Keys_Key_value_lookup_tree;
     45extern RBTree_Control _POSIX_Keys_Key_value_lookup_tree;
    4646
    4747/**
    … …  
    6262 * This routine compares the rbtree node
    6363 */
    64 int _POSIX_Keys_Key_value_lookup_tree_compare_function(
     64int _POSIX_Keys_Key_value_compare(
    6565  const RBTree_Node *node1,
    6666  const RBTree_Node *node2
    … …  
    166166}
    167167
     168RTEMS_INLINE_ROUTINE RBTree_Node *_POSIX_Keys_Find(
     169  pthread_key_t              key,
     170  Objects_Id                 thread_id,
     171  POSIX_Keys_Key_value_pair *search_node
     172)
     173{
     174  search_node->key = key;
     175  search_node->thread_id = thread_id;
     176
     177  return _RBTree_Find(
     178    &_POSIX_Keys_Key_value_lookup_tree,
     179    &search_node->Key_value_lookup_node,
     180    _POSIX_Keys_Key_value_compare,
     181    true
     182  );
     183}
     184
    168185/** @} */
    169186

  • cpukit/posix/src/key.c

    r7e119990 r64939bc  
    2727#include <rtems/score/wkspace.h>
    2828
     29RBTREE_DEFINE_EMPTY( _POSIX_Keys_Key_value_lookup_tree );
     30
    2931/**
    3032 * @brief This routine compares the rbtree node by comparing POSIX key first
    … …  
    4345 */
    4446
    45 int _POSIX_Keys_Key_value_lookup_tree_compare_function(
     47int _POSIX_Keys_Key_value_compare(
    4648  const RBTree_Node *node1,
    4749  const RBTree_Node *node2
    … …  
    154156  );
    155157
    156   _RBTree_Initialize_empty(
    157       &_POSIX_Keys_Key_value_lookup_tree,
    158       _POSIX_Keys_Key_value_lookup_tree_compare_function,
    159       true
    160   );
    161 
    162158  _POSIX_Keys_Initialize_keypool();
    163159}

  • cpukit/posix/src/keyfreememory.c

    r7e119990 r64939bc  
    3333
    3434  key_id = the_key->Object.id;
    35   search_node.key = key_id;
    36   search_node.thread_id = 0;
    37   iter = _RBTree_Find( &_POSIX_Keys_Key_value_lookup_tree, &search_node.Key_value_lookup_node );
     35  iter = _POSIX_Keys_Find( key_id, 0, &search_node );
    3836  if ( !iter )
    3937    return;

  • cpukit/posix/src/keygetspecific.c

    r7e119990 r64939bc  
    5050
    5151    case OBJECTS_LOCAL:
    52       search_node.key = key;
    53       search_node.thread_id = _Thread_Executing->Object.id;
    54       p = _RBTree_Find( &_POSIX_Keys_Key_value_lookup_tree,
    55                                     &search_node.Key_value_lookup_node );
    56       key_data = NULL;
    57       if ( p ) {
     52      p = _POSIX_Keys_Find( key, _Thread_Executing->Object.id, &search_node );
     53      if ( p != NULL ) {
    5854        value_pair_p = _RBTree_Container_of( p,
    5955                                          POSIX_Keys_Key_value_pair,
    6056                                          Key_value_lookup_node );
    61         /* key_data = _RBTree_Container_of( p, */
    62         /*                                  POSIX_Keys_Key_value_pair, */
    63         /*                                  Key_value_lookup_node )->value; */
    6457        key_data = value_pair_p->value;
     58      } else {
     59        key_data = NULL;
    6560      }
    6661

  • cpukit/posix/src/keysetspecific.c

    r7e119990 r64939bc  
    4545
    4646    case OBJECTS_LOCAL:
    47       search_node.key = key;
    48       search_node.thread_id = _Thread_Executing->Object.id;
    49       p = _RBTree_Find( &_POSIX_Keys_Key_value_lookup_tree,
    50                                     &search_node.Key_value_lookup_node );
    51 
    52       if ( p ) {
     47      p = _POSIX_Keys_Find( key, _Thread_Executing->Object.id, &search_node );
     48      if ( p != NULL ) {
    5349        value_pair_ptr = _RBTree_Container_of( p,
    5450                                          POSIX_Keys_Key_value_pair,
    … …  
    7066        /* The insert can only go wrong if the same node is already in a unique
    7167         * tree. This has been already checked with the _RBTree_Find() */
    72         (void) _RBTree_Insert( &_POSIX_Keys_Key_value_lookup_tree,
    73                              &(value_pair_ptr->Key_value_lookup_node) );
     68        _RBTree_Insert(
     69          &_POSIX_Keys_Key_value_lookup_tree,
     70          &value_pair_ptr->Key_value_lookup_node,
     71          _POSIX_Keys_Key_value_compare,
     72          true
     73        );
    7474
    7575        /** append rb_node to the thread API extension's chain */

  • cpukit/sapi/include/rtems/rbtree.h

    r7e119990 r64939bc  
    5656
    5757/**
    58  * @typedef rtems_rbtree_compare_function
    59  *
    6058 * This type defines function pointers for user-provided comparison
    6159 * function. The function compares two nodes in order to determine
    6260 * the order in a red-black tree.
    6361 */
    64 typedef RBTree_Compare_function rtems_rbtree_compare_function;
     62typedef RBTree_Compare rtems_rbtree_compare;
    6563
    6664/**
    … …  
    9492 */
    9593RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
    96   rtems_rbtree_control          *the_rbtree,
    97   rtems_rbtree_compare_function  compare_function,
    98   void                          *starting_address,
    99   size_t                         number_nodes,
    100   size_t                         node_size,
    101   bool                           is_unique
    102 )
    103 {
    104   _RBTree_Initialize( the_rbtree, compare_function, starting_address,
     94  rtems_rbtree_control *the_rbtree,
     95  rtems_rbtree_compare  compare,
     96  void                 *starting_address,
     97  size_t                number_nodes,
     98  size_t                node_size,
     99  bool                  is_unique
     100)
     101{
     102  _RBTree_Initialize( the_rbtree, compare, starting_address,
    105103    number_nodes, node_size, is_unique);
    106104}
    … …  
    112110 */
    113111RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(
    114   rtems_rbtree_control          *the_rbtree,
    115   rtems_rbtree_compare_function  compare_function,
    116   bool                           is_unique
    117 )
    118 {
    119   _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique );
     112  rtems_rbtree_control *the_rbtree
     113)
     114{
     115  _RBTree_Initialize_empty( the_rbtree );
    120116}
    121117
    … …  
    278274RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
    279275  const rtems_rbtree_control *the_rbtree,
    280   const rtems_rbtree_node *the_node
    281 )
    282 {
    283   return _RBTree_Find( the_rbtree, the_node );
     276  const rtems_rbtree_node    *the_node,
     277  rtems_rbtree_compare        compare,
     278  bool                        is_unique
     279)
     280{
     281  return _RBTree_Find( the_rbtree, the_node, compare, is_unique );
    284282}
    285283
    … …  
    386384RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
    387385  rtems_rbtree_control *the_rbtree,
    388   rtems_rbtree_node *the_node
    389 )
    390 {
    391   return _RBTree_Insert( the_rbtree, the_node );
    392 }
    393 
    394 /**
    395  * @brief Determines whether the tree is unique.
    396  */
    397 RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_unique(
    398   const rtems_rbtree_control *the_rbtree
    399 )
    400 {
    401   return _RBTree_Is_unique(the_rbtree);
     386  rtems_rbtree_node    *the_node,
     387  rtems_rbtree_compare  compare,
     388  bool                  is_unique
     389)
     390{
     391  return _RBTree_Insert( the_rbtree, the_node, compare, is_unique );
    402392}
    403393

  • cpukit/sapi/src/rbheap.c

    r7e119990 r64939bc  
    8181)
    8282{
    83   _RBTree_Insert(tree, &chunk->tree_node);
     83  rtems_rbtree_insert(tree, &chunk->tree_node, chunk_compare, true);
    8484}
    8585
    … …  
    108108      rtems_chain_initialize_empty(free_chain);
    109109      rtems_chain_initialize_empty(&control->spare_descriptor_chain);
    110       rtems_rbtree_initialize_empty(chunk_tree, chunk_compare, true);
     110      rtems_rbtree_initialize_empty(chunk_tree);
    111111      control->alignment = alignment;
    112112      control->handler_arg = handler_arg;
    … …  
    199199
    200200  return rtems_rbheap_chunk_of_node(
    201     _RBTree_Find(chunk_tree, &chunk.tree_node)
     201    rtems_rbtree_find(chunk_tree, &chunk.tree_node, chunk_compare, true)
    202202  );
    203203}
    … …  
    231231    rtems_chain_extract_unprotected(&b->chain_node);
    232232    add_to_chain(free_chain, b);
    233     _RBTree_Extract(chunk_tree, &b->tree_node);
     233    rtems_rbtree_extract(chunk_tree, &b->tree_node);
    234234  }
    235235}

  • cpukit/score/include/rtems/score/rbtree.h

    r7e119990 r64939bc  
    105105
    106106/**
    107  * This type defines function pointers for user-provided comparison
    108  * function. The function compares two nodes in order to determine
    109  * the order in a red-black tree.
    110  */
    111 typedef int (*RBTree_Compare_function)(
    112   const RBTree_Node *node1,
    113   const RBTree_Node *node2
     107 * @brief Compares two red-black tree nodes.
     108 *
     109 * @param[in] first The first node.
     110 * @param[in] second The second node.
     111 *
     112 * @retval positive The key value of the first node is greater than the one of
     113 *   the second node.
     114 * @retval 0 The key value of the first node is equal to the one of the second
     115 *   node.
     116 * @retval negative The key value of the first node is less than the one of the
     117 *   second node.
     118 */
     119typedef int ( *RBTree_Compare )(
     120  const RBTree_Node *first,
     121  const RBTree_Node *second
    114122);
    115123
    … …  
    140148  /** This points to the min and max nodes of this RBT. */
    141149  RBTree_Node *first[2];
    142   /**
    143    * Comparison function pointer. Keys to compare have to be found
    144    * inside to maintain generality. It has to return 1 if first node
    145    * has higher key than second, -1 if lower, 0 if equal.
    146    */
    147   RBTree_Compare_function compare_function;
    148   /** Determines whether the tree accepts duplicate keys. */
    149   bool is_unique;
    150150} RBTree_Control;
    151151
    … …  
    153153 *  @brief RBTree initializer for an empty rbtree with designator @a name.
    154154 */
    155 #define RBTREE_INITIALIZER_EMPTY(name) \
    156 { \
    157   .permanent_null = NULL, \
    158   .root = NULL, \
    159   .first[0] = NULL, \
    160   .first[1] = NULL, \
    161   .compare_function = NULL, \
    162   .is_unique = 0 \
    163 }
     155#define RBTREE_INITIALIZER_EMPTY( name ) \
     156  { NULL, NULL, { NULL, NULL } }
    164157
    165158/**
    166159 *  @brief RBTree definition for an empty rbtree with designator @a name.
    167160 */
    168 #define RBTREE_DEFINE_EMPTY(name) \
    169 RBTree_Control name = RBTREE_INITIALIZER_EMPTY(name)
     161#define RBTREE_DEFINE_EMPTY( name ) \
     162  RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )
    170163
    171164/**
    172165 *  @brief RBTree_Node initializer for an empty node with designator @a name.
    173166 */
    174 #define RBTREE_NODE_INITIALIZER_EMPTY(name) \
    175 { \
    176   .parent = NULL, \
    177   .child[0] = NULL, \
    178   .child[1] = NULL, \
    179   RBT_RED \
    180 }
     167#define RBTREE_NODE_INITIALIZER_EMPTY( name ) \
     168  { NULL, { NULL, NULL }, RBT_RED }
    181169
    182170/**
    183171 *  @brief RBTree definition for an empty rbtree with designator @a name.
    184172 */
    185 #define RBTREE_NODE_DEFINE_EMPTY(name) \
    186 RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name)
     173#define RBTREE_NODE_DEFINE_EMPTY( name ) \
     174  RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY( name )
    187175
    188176/**
    … …  
    194182 *
    195183 *  @param[in] the_rbtree is the pointer to rbtree header
     184 *  @param[in] compare The node compare function.
    196185 *  @param[in] starting_address is the starting address of first node
    197186 *  @param[in] number_nodes is the number of nodes in rbtree
    198187 *  @param[in] node_size is the size of node in bytes
     188 *  @param[in] is_unique If true, then reject nodes with a duplicate key, else
     189 *    otherwise.
    199190 */
    200191void _RBTree_Initialize(
    201   RBTree_Control          *the_rbtree,
    202   RBTree_Compare_function  compare_function,
    203   void                    *starting_address,
    204   size_t                   number_nodes,
    205   size_t                   node_size,
    206   bool                     is_unique
     192  RBTree_Control *the_rbtree,
     193  RBTree_Compare  compare,
     194  void           *starting_address,
     195  size_t          number_nodes,
     196  size_t          node_size,
     197  bool            is_unique
    207198);
    208199
    … …  
    212203 * @param[in] the_rbtree The red-black tree control.
    213204 * @param[in] the_node A node specifying the key.
     205 * @param[in] compare The node compare function.
     206 * @param[in] is_unique If true, then return the first node with a key equal to
     207 *   the one of the node specified if it exits, else return the last node if it
     208 *   exists.
    214209 *
    215210 * @retval node A node corresponding to the key.  If the tree is not unique
    … …  
    219214RBTree_Node *_RBTree_Find(
    220215  const RBTree_Control *the_rbtree,
    221   const RBTree_Node *the_node
     216  const RBTree_Node    *the_node,
     217  RBTree_Compare        compare,
     218  bool                  is_unique
    222219);
    223220
    … …  
    226223 *
    227224 *  This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
     225 *
     226 * @param[in] the_rbtree The red-black tree control.
     227 * @param[in] the_node The node to insert.
     228 * @param[in] compare The node compare function.
     229 * @param[in] is_unique If true, then reject nodes with a duplicate key, else
     230 *   otherwise.
    228231 *
    229232 *  @retval 0 Successfully inserted.
    … …  
    234237RBTree_Node *_RBTree_Insert(
    235238  RBTree_Control *the_rbtree,
    236   RBTree_Node *the_node
     239  RBTree_Node    *the_node,
     240  RBTree_Compare  compare,
     241  bool            is_unique
    237242);
    238243
    … …  
    438443 */
    439444RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
    440     RBTree_Control          *the_rbtree,
    441     RBTree_Compare_function  compare_function,
    442     bool                     is_unique
    443     )
     445  RBTree_Control *the_rbtree
     446)
    444447{
    445448  the_rbtree->permanent_null   = NULL;
    446449  the_rbtree->root             = NULL;
    447   the_rbtree->first[0]         = NULL;
    448   the_rbtree->first[1]         = NULL;
    449   the_rbtree->compare_function = compare_function;
    450   the_rbtree->is_unique        = is_unique;
     450  the_rbtree->first[RBT_LEFT]  = NULL;
     451  the_rbtree->first[RBT_RIGHT] = NULL;
    451452}
    452453
    … …  
    503504}
    504505
    505 /**
    506  * @brief Determines whether the tree is unique.
    507  */
    508 RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique(
    509   const RBTree_Control *the_rbtree
    510 )
    511 {
    512   return( the_rbtree && the_rbtree->is_unique );
    513 }
    514 
    515506/**@}*/
    516507

  • cpukit/score/include/rtems/score/scheduleredfimpl.h

    r7e119990 r64939bc  
    4545}
    4646
     47int _Scheduler_EDF_Compare(
     48  const RBTree_Node* n1,
     49  const RBTree_Node* n2
     50);
     51
    4752RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Enqueue(
    4853  const Scheduler_Control *scheduler,
    … …  
    5459  Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
    5560
    56   _RBTree_Insert( &context->Ready, &node->Node );
     61  _RBTree_Insert(
     62    &context->Ready,
     63    &node->Node,
     64    _Scheduler_EDF_Compare,
     65    false
     66  );
    5767  node->queue_state = SCHEDULER_EDF_QUEUE_STATE_YES;
    5868}

  • cpukit/score/src/rbtree.c

    r7e119990 r64939bc  
    2424
    2525void _RBTree_Initialize(
    26   RBTree_Control          *the_rbtree,
    27   RBTree_Compare_function  compare_function,
    28   void                    *starting_address,
    29   size_t                   number_nodes,
    30   size_t                   node_size,
    31   bool                     is_unique
     26  RBTree_Control *the_rbtree,
     27  RBTree_Compare  compare,
     28  void           *starting_address,
     29  size_t          number_nodes,
     30  size_t          node_size,
     31  bool            is_unique
    3232)
    3333{
    … …  
    3939
    4040  /* could do sanity checks here */
    41   _RBTree_Initialize_empty(the_rbtree, compare_function, is_unique);
     41  _RBTree_Initialize_empty( the_rbtree );
    4242
    4343  count = number_nodes;
    4444  next  = starting_address;
    4545  while ( count-- ) {
    46     _RBTree_Insert(the_rbtree, next);
    47     next           = (RBTree_Node *)
    48                         _Addresses_Add_offset( (void *) next, node_size );
     46    _RBTree_Insert( the_rbtree, next, compare, is_unique );
     47    next = (RBTree_Node *) _Addresses_Add_offset( next, node_size );
    4948  }
    5049}

  • cpukit/score/src/rbtreefind.c

    r7e119990 r64939bc  
    1919
    2020#include <rtems/score/rbtreeimpl.h>
    21 #include <rtems/score/isr.h>
    2221
    2322RBTree_Node *_RBTree_Find(
    2423  const RBTree_Control *the_rbtree,
    25   const RBTree_Node *the_node
     24  const RBTree_Node    *the_node,
     25  RBTree_Compare        compare,
     26  bool                  is_unique
    2627)
    2728{
    2829  RBTree_Node* iter_node = the_rbtree->root;
    2930  RBTree_Node* found = NULL;
    30   int compare_result;
    31   while (iter_node) {
    32     compare_result = the_rbtree->compare_function(the_node, iter_node);
     31
     32  while ( iter_node != NULL ) {
     33    int compare_result = ( *compare )( the_node, iter_node );
     34    RBTree_Direction dir;
     35
    3336    if ( _RBTree_Is_equal( compare_result ) ) {
    3437      found = iter_node;
    35       if ( the_rbtree->is_unique )
     38      if ( is_unique )
    3639        break;
    3740    }
    3841
    39     RBTree_Direction dir =
    40       (RBTree_Direction) _RBTree_Is_greater( compare_result );
    41     iter_node = iter_node->child[dir];
    42   } /* while(iter_node) */
     42    dir = (RBTree_Direction) _RBTree_Is_greater( compare_result );
     43    iter_node = iter_node->child[ dir ];
     44  }
    4345
    4446  return found;

  • cpukit/score/src/rbtreeinsert.c

    r7e119990 r64939bc  
    6060}
    6161
    62 
    63 
    64 /** @brief Insert a Node (unprotected)
    65  *
    66  *  This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
    67  *
    68  *  @retval 0 Successfully inserted.
    69  *  @retval -1 NULL @a the_node.
    70  *  @retval RBTree_Node* if one with equal key to the key of @a the_node exists
    71  *          in an unique @a the_rbtree.
    72  *
    73  *  @note It does NOT disable interrupts to ensure the atomicity
    74  *        of the extract operation.
    75  */
    7662RBTree_Node *_RBTree_Insert(
    77     RBTree_Control *the_rbtree,
    78     RBTree_Node *the_node
    79     )
     63  RBTree_Control *the_rbtree,
     64  RBTree_Node    *the_node,
     65  RBTree_Compare  compare,
     66  bool            is_unique
     67)
    8068{
    8169  if(!the_node) return (RBTree_Node*)-1;
    … …  
    9381    /* typical binary search tree insert, descend tree to leaf and insert */
    9482    while (iter_node) {
    95       compare_result = the_rbtree->compare_function(the_node, iter_node);
    96       if ( the_rbtree->is_unique && _RBTree_Is_equal( compare_result ) )
     83      compare_result = ( *compare )( the_node, iter_node );
     84      if ( is_unique && _RBTree_Is_equal( compare_result ) )
    9785        return iter_node;
    9886      RBTree_Direction dir = !_RBTree_Is_lesser( compare_result );
    … …  
    10391        the_node->parent = iter_node;
    10492        /* update min/max */
    105         compare_result = the_rbtree->compare_function(
    106             the_node,
    107             _RBTree_First(the_rbtree, dir)
     93        compare_result = ( *compare )(
     94          the_node,
     95          _RBTree_First( the_rbtree, dir )
    10896        );
    10997        if ( (!dir && _RBTree_Is_lesser(compare_result)) ||

  • cpukit/score/src/scheduleredf.c

    r7e119990 r64939bc  
    2121#include <rtems/score/scheduleredfimpl.h>
    2222
    23 static int _Scheduler_EDF_RBTree_compare_function
    24 (
     23int _Scheduler_EDF_Compare(
    2524  const RBTree_Node* n1,
    2625  const RBTree_Node* n2
    … …  
    4443    _Scheduler_EDF_Get_context( scheduler );
    4544
    46   _RBTree_Initialize_empty(
    47     &context->Ready,
    48     _Scheduler_EDF_RBTree_compare_function,
    49     0
    50   );
     45  _RBTree_Initialize_empty( &context->Ready );
    5146}

  • cpukit/score/src/scheduleredfchangepriority.c

    r7e119990 r64939bc  
    3333
    3434  _RBTree_Extract( &context->Ready, &node->Node );
    35   _RBTree_Insert( &context->Ready, &node->Node );
     35  _RBTree_Insert(
     36    &context->Ready,
     37    &node->Node,
     38    _Scheduler_EDF_Compare,
     39    false
     40  );
    3641
    3742  SCHEDULER_RETURN_VOID_OR_NULL;

  • cpukit/score/src/scheduleredfyield.c

    r7e119990 r64939bc  
    3636   */
    3737  _RBTree_Extract( &context->Ready, &node->Node );
    38   _RBTree_Insert( &context->Ready, &node->Node );
     38  _RBTree_Insert(
     39    &context->Ready,
     40    &node->Node,
     41    _Scheduler_EDF_Compare,
     42    false
     43  );
    3944
    4045  _Scheduler_EDF_Schedule_body( scheduler, the_thread, false );

  • testsuites/sptests/sprbtree01/init.c

    r7e119990 r64939bc  
    4343}
    4444
    45 /*
    46  * recursively checks tree. if the tree is built properly it should only
    47  * be a depth of 7 function calls for 100 entries in the tree.
     45static rtems_rbtree_node *rb_insert_unique(
     46  rtems_rbtree_control *rbtree,
     47  rtems_rbtree_node    *node
     48)
     49{
     50  return rtems_rbtree_insert( rbtree, node, test_compare_function, true );
     51}
     52
     53static rtems_rbtree_node *rb_insert_multi(
     54  rtems_rbtree_control *rbtree,
     55  rtems_rbtree_node    *node
     56)
     57{
     58  return rtems_rbtree_insert( rbtree, node, test_compare_function, false );
     59}
     60
     61static rtems_rbtree_node *rb_find_unique(
     62  rtems_rbtree_control *rbtree,
     63  rtems_rbtree_node    *node
     64)
     65{
     66  return rtems_rbtree_find( rbtree, node, test_compare_function, true );
     67}
     68
     69static rtems_rbtree_node *rb_find_multi(
     70  rtems_rbtree_control *rbtree,
     71  rtems_rbtree_node    *node
     72)
     73{
     74  return rtems_rbtree_find( rbtree, node, test_compare_function, false );
     75}
     76
     77/*
     78 * recursively checks tree. if the tree is built properly it should only
     79 * be a depth of 7 function calls for 100 entries in the tree.
    4880 */
    4981static int rb_assert ( rtems_rbtree_node *root )
    … …  
    107139
    108140  puts( "Init - Initialize rbtree empty" );
    109   rtems_rbtree_initialize_empty( &rbtree1, &test_compare_function, true );
    110 
    111   if ( !rtems_rbtree_is_unique( &rbtree1 ) )
    112     puts( "INIT - FAILED IS UNIQUE CHECK" );
    113   if ( rtems_rbtree_is_unique( NULL ) )
    114     puts( "INIT - FAILED IS UNIQUE CHECK" );
     141  rtems_rbtree_initialize_empty( &rbtree1 );
    115142
    116143  /* verify that the rbtree insert work */
    … …  
    120147  node2.id = 2;
    121148  node2.key = 2;
    122   rtems_rbtree_insert( &rbtree1, &node1.Node );
    123   rtems_rbtree_insert( &rbtree1, &node2.Node );
    124 
    125   p = rtems_rbtree_insert( &rbtree1, NULL );
     149  rb_insert_unique( &rbtree1, &node1.Node );
     150  rb_insert_unique( &rbtree1, &node2.Node );
     151
     152  p = rb_insert_unique( &rbtree1, NULL );
    126153  if (p != (void *)(-1))
    127154    puts( "INIT - FAILED NULL NODE INSERT" );
    … …  
    160187  puts("INIT - Verify rtems_rbtree_insert with the same value twice");
    161188  node2.key = node1.key;
    162   rtems_rbtree_insert(&rbtree1, &node1.Node);
    163   p = rtems_rbtree_insert(&rbtree1, &node2.Node);
     189  rb_insert_unique(&rbtree1, &node1.Node);
     190  p = rb_insert_unique(&rbtree1, &node2.Node);
    164191
    165192  if (p != &node1.Node)
    … …  
    219246  node2.id = 1;
    220247  node2.key = 1;
    221   rtems_rbtree_insert( &rbtree1, &node1.Node );
    222   rtems_rbtree_insert( &rbtree1, &node2.Node );
     248  rb_insert_unique( &rbtree1, &node1.Node );
     249  rb_insert_unique( &rbtree1, &node2.Node );
    223250
    224251  puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" );
    … …  
    238265    rtems_test_exit(0);
    239266  }
    240   rtems_rbtree_insert(&rbtree1, p);
     267  rb_insert_unique(&rbtree1, p);
    241268
    242269  for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
    … …  
    257284    node_array[i].id = i;
    258285    node_array[i].key = i;
    259     rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
     286    rb_insert_unique( &rbtree1, &node_array[i].Node );
    260287
    261288    if (!rb_assert(rbtree1.root) )
    … …  
    290317    node_array[i].id = 99-i;
    291318    node_array[i].key = 99-i;
    292     rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
     319    rb_insert_unique( &rbtree1, &node_array[i].Node );
    293320
    294321    if (!rb_assert(rbtree1.root) )
    … …  
    325352    node_array[i].id = i;
    326353    node_array[i].key = i;
    327     rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
     354    rb_insert_unique( &rbtree1, &node_array[i].Node );
    328355
    329356    if (!rb_assert(rbtree1.root) )
    … …  
    377404    node_array[i].key = i;
    378405  }
    379   rtems_rbtree_insert( &rbtree1, &node_array[3].Node );
    380   rtems_rbtree_insert( &rbtree1, &node_array[1].Node );
    381   rtems_rbtree_insert( &rbtree1, &node_array[5].Node );
    382   rtems_rbtree_insert( &rbtree1, &node_array[0].Node );
    383   rtems_rbtree_insert( &rbtree1, &node_array[2].Node );
    384   rtems_rbtree_insert( &rbtree1, &node_array[4].Node );
    385   rtems_rbtree_insert( &rbtree1, &node_array[6].Node );
     406  rb_insert_unique( &rbtree1, &node_array[3].Node );
     407  rb_insert_unique( &rbtree1, &node_array[1].Node );
     408  rb_insert_unique( &rbtree1, &node_array[5].Node );
     409  rb_insert_unique( &rbtree1, &node_array[0].Node );
     410  rb_insert_unique( &rbtree1, &node_array[2].Node );
     411  rb_insert_unique( &rbtree1, &node_array[4].Node );
     412  rb_insert_unique( &rbtree1, &node_array[6].Node );
    386413  rtems_rbtree_extract( &rbtree1, &node_array[2].Node );
    387414  /* node_array[1] has now only a left child. */
    … …  
    396423    node_array[i].id = 99-i;
    397424    node_array[i].key = 99-i;
    398     rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
     425    rb_insert_unique( &rbtree1, &node_array[i].Node );
    399426
    400427    if (!rb_assert(rbtree1.root) )
    … …  
    429456    node_array[i].id = i;
    430457    node_array[i].key = i;
    431     rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
     458    rb_insert_unique( &rbtree1, &node_array[i].Node );
    432459
    433460    if (!rb_assert(rbtree1.root) )
    … …  
    437464  puts( "INIT - Verify rtems_rbtree_find" );
    438465  search_node.key = 30;
    439   p = rtems_rbtree_find(&rbtree1, &search_node.Node);
     466  p = rb_find_unique(&rbtree1, &search_node.Node);
    440467  if(rtems_rbtree_container_of(p,test_node,Node)->id != 30) {
    441468    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
    … …  
    449476    rtems_test_exit(0);
    450477  }
    451   p = rtems_rbtree_find(&rbtree1, &search_node.Node);
     478  p = rb_find_unique(&rbtree1, &search_node.Node);
    452479  p = rtems_rbtree_successor(p);
    453480  if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 31) {
    … …  
    456483  }
    457484
    458   p = rtems_rbtree_find(&rbtree1, &search_node.Node);
     485  p = rb_find_unique(&rbtree1, &search_node.Node);
    459486  puts( "INIT - Verify rtems_rbtree_find_header" );
    460487  if (rtems_rbtree_find_header(p) != &rbtree1) {
    … …  
    510537    node_array[i].id = numbers[i];
    511538    node_array[i].key = numbers[i];
    512     rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
     539    rb_insert_unique( &rbtree1, &node_array[i].Node );
    513540
    514541    if (!rb_assert(rbtree1.root) )
    … …  
    574601  /* Initialize the tree for duplicate keys */
    575602  puts( "Init - Initialize duplicate rbtree empty" );
    576   rtems_rbtree_initialize_empty( &rbtree1, &test_compare_function, false );
    577 
    578   if ( rtems_rbtree_is_unique( &rbtree1 ) )
    579     puts( "INIT - FAILED IS UNIQUE CHECK" );
    580   if ( rtems_rbtree_is_unique( NULL ) )
    581     puts( "INIT - FAILED IS UNIQUE CHECK" );
     603  rtems_rbtree_initialize_empty( &rbtree1 );
    582604
    583605  puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
    … …  
    585607    node_array[i].id = i;
    586608    node_array[i].key = i%5;
    587     rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
     609    rb_insert_multi( &rbtree1, &node_array[i].Node );
    588610
    589611    if (!rb_assert(rbtree1.root) )
    … …  
    593615  puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
    594616  search_node.key = 2;
    595   p = rtems_rbtree_find(&rbtree1, &search_node.Node);
     617  p = rb_find_multi(&rbtree1, &search_node.Node);
    596618  if(rtems_rbtree_container_of(p,test_node,Node)->id != 2) {
    597619    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
    … …  
    626648    node_array[i].id = 99-i;
    627649    node_array[i].key = (99-i)%5;
    628     rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
     650    rb_insert_multi( &rbtree1, &node_array[i].Node );
    629651
    630652    if (!rb_assert(rbtree1.root) )
    … …  
    634656  puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" );
    635657  search_node.key = 2;
    636   p = rtems_rbtree_find(&rbtree1, &search_node.Node);
     658  p = rb_find_multi(&rbtree1, &search_node.Node);
    637659  if(rtems_rbtree_container_of(p,test_node,Node)->id != 97) {
    638660    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
Note: See TracChangeset for help on using the changeset viewer.