Ignore:
Timestamp:
Jul 12, 2014, 7:22:22 PM (5 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
4.11, 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().

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.