Changeset 74f1c73e in rtems


Ignore:
Timestamp:
Aug 21, 2011, 8:07:11 PM (9 years ago)
Author:
Joel Sherrill <joel.sherrill@…>
Branches:
4.11, 5, master
Children:
611909e
Parents:
08ef1631
Message:

2011-08-21 Petr Benes <benesp16@…>

PR 1886/cpukit

  • sapi/include/rtems/rbtree.h, sapi/inline/rtems/rbtree.inl, score/include/rtems/score/rbtree.h, score/inline/rtems/score/rbtree.inl, score/src/rbtree.c, score/src/rbtreeinsert.c: This patch enables inserting duplicate keys into rbtree. It is possible to turn on this feature when initializing the tree.
Location:
cpukit
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • cpukit/ChangeLog

    r08ef1631 r74f1c73e  
     12011-08-21      Petr Benes <benesp16@fel.cvut.cz>
     2
     3        PR 1886/cpukit
     4        * sapi/include/rtems/rbtree.h, sapi/inline/rtems/rbtree.inl,
     5        score/include/rtems/score/rbtree.h,
     6        score/inline/rtems/score/rbtree.inl, score/src/rbtree.c,
     7        score/src/rbtreeinsert.c: This patch enables inserting duplicate keys
     8        into rbtree. It is possible to turn on this feature when initializing
     9        the tree.
     10
    1112011-08-21      Joel Sherrill <joel.sherrilL@OARcorp.com>
    212
  • cpukit/sapi/include/rtems/rbtree.h

    r08ef1631 r74f1c73e  
    4444
    4545/**
     46 * @typedef rtems_rbtree_compare_function
     47 *
     48 * This type defines function pointers for user-provided comparison
     49 * function. The function compares two nodes in order to determine
     50 * the order in a red-black tree.
     51 */
     52typedef RBTree_Compare_function rtems_rbtree_compare_function;
     53
     54/**
     55 * @typedef rtems_rbtree_unique
     56 *
     57 * This enum type defines whether the tree can contain nodes with
     58 * duplicate keys.
     59 */
     60typedef enum {
     61  /** The tree is not unique, insertion of duplicate keys is performed
     62   *  in a FIFO manner. */
     63  RTEMS_RBTREE_DUPLICATE = false,
     64  /** The tree is unique, insertion of duplicate key is refused. */
     65  RTEMS_RBTREE_UNIQUE    = true
     66} rtems_rbtree_unique;
     67
     68/**
    4669 *  @brief RBTree initializer for an empty rbtree with designator @a name.
    4770 */
  • cpukit/sapi/inline/rtems/rbtree.inl

    r08ef1631 r74f1c73e  
    3636 */
    3737RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
    38   rtems_rbtree_control *the_rbtree,
    39   void                 *compare_function,
    40   void                 *starting_address,
    41   size_t                number_nodes,
    42   size_t                node_size
     38  rtems_rbtree_control          *the_rbtree,
     39  rtems_rbtree_compare_function  compare_function,
     40  void                          *starting_address,
     41  size_t                         number_nodes,
     42  size_t                         node_size,
     43  rtems_rbtree_unique            is_unique
    4344)
    4445{
    4546  _RBTree_Initialize( the_rbtree, compare_function, starting_address,
    46     number_nodes, node_size);
     47    number_nodes, node_size, is_unique);
    4748}
    4849
     
    5354 */
    5455RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(
    55   rtems_rbtree_control *the_rbtree,
    56   void                 *compare_function
    57 )
    58 {
    59   _RBTree_Initialize_empty( the_rbtree, compare_function );
     56  rtems_rbtree_control          *the_rbtree,
     57  rtems_rbtree_compare_function  compare_function,
     58  rtems_rbtree_unique            is_unique
     59)
     60{
     61  _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique );
    6062}
    6163
     
    258260 *  of @a the_node if it exists within @a the_rbtree, and NULL if not.
    259261 *  @a the_node has to be made up before a search.
     262 *
     263 *  @note If the tree is not unique and contains duplicate keys, the set
     264 *        of duplicate keys acts as FIFO.
    260265 */
    261266RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
     
    383388 *  This routine inserts @a the_node on @a the_rbtree.
    384389 *  It disables interrupts to ensure the atomicity of the insert operation.
    385  */
    386 RTEMS_INLINE_ROUTINE void rtems_rbtree_insert(
     390 *
     391 *  @retval 0 Successfully inserted.
     392 *  @retval -1 NULL @a the_node.
     393 *  @retval RBTree_Node* if one with equal key to the key of @a the_node exists
     394 *          in an unique @a the_rbtree.
     395 */
     396RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
    387397  rtems_rbtree_control *the_rbtree,
    388398  rtems_rbtree_node *the_node
    389399)
    390400{
    391   _RBTree_Insert( the_rbtree, the_node );
     401  return _RBTree_Insert( the_rbtree, the_node );
     402}
     403
     404/** @brief Determines whether the tree is unique
     405 */
     406RTEMS_INLINE_ROUTINE rtems_rbtree_unique rtems_rbtree_is_unique(
     407    rtems_rbtree_control *the_rbtree
     408)
     409{
     410  return( _RBTree_Is_unique(the_rbtree) );
    392411}
    393412
  • cpukit/score/include/rtems/score/rbtree.h

    r08ef1631 r74f1c73e  
    101101
    102102/**
     103 * This type defines function pointers for user-provided comparison
     104 * function. The function compares two nodes in order to determine
     105 * the order in a red-black tree.
     106 */
     107typedef int (*RBTree_Compare_function)(
     108    RBTree_Node *node1,
     109    RBTree_Node *node2
     110);
     111
     112/**
    103113 *  @struct RBTree_Control
    104114 *
     
    127137  RBTree_Node *first[2];
    128138  /**
    129    * Comparison function pointer. Keys to compare has to be found
     139   * Comparison function pointer. Keys to compare have to be found
    130140   * inside to maintain generality. It has to return 1 if first node
    131141   * has higher key than second, -1 if lower, 0 if equal.
    132142   */
    133   int (*compare_function) (RBTree_Node*, RBTree_Node*);
     143  RBTree_Compare_function compare_function;
     144  /** Determines whether the tree accepts duplicate keys. */
     145  bool is_unique;
    134146} RBTree_Control;
    135147
     
    143155  .first[0] = NULL, \
    144156  .first[1] = NULL, \
    145   .compare_function = NULL \
     157  .compare_function = NULL, \
     158  .is_unique = 0 \
    146159}
    147160
     
    177190 */
    178191void _RBTree_Initialize(
    179   RBTree_Control *the_rbtree,
    180   void           *compare_function,
    181   void           *starting_address,
    182   size_t          number_nodes,
    183   size_t          node_size
     192  RBTree_Control          *the_rbtree,
     193  RBTree_Compare_function  compare_function,
     194  void                    *starting_address,
     195  size_t                   number_nodes,
     196  size_t                   node_size,
     197  bool                     is_unique
    184198);
    185199
     
    248262 *  @retval 0 Successfully inserted.
    249263 *  @retval -1 NULL @a the_node.
    250  *  @retval RBTree_Node* if one with equal value to @a the_node->value exists
    251  *          in @a the_rbtree.
     264 *  @retval RBTree_Node* if one with equal value to @a the_node 's key exists
     265 *          in an unique @a the_rbtree.
    252266 *
    253267 *  @note It does NOT disable interrupts to ensure the atomicity
     
    264278 *  This routine inserts @a the_node on the tree @a the_rbtree.
    265279 *
     280 *  @retval 0 Successfully inserted.
     281 *  @retval -1 NULL @a the_node.
     282 *  @retval RBTree_Node* if one with equal value to @a the_node 's key exists
     283 *          in an unique @a the_rbtree.
     284 *
    266285 *  @note It disables interrupts to ensure the atomicity
    267286 *  of the extract operation.
    268287 */
    269 void _RBTree_Insert(
     288RBTree_Node *_RBTree_Insert(
    270289  RBTree_Control *the_rbtree,
    271290  RBTree_Node *the_node
  • cpukit/score/inline/rtems/score/rbtree.inl

    r08ef1631 r74f1c73e  
    236236 */
    237237RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
    238     RBTree_Control *the_rbtree,
    239     void           *compare_function
     238    RBTree_Control          *the_rbtree,
     239    RBTree_Compare_function  compare_function,
     240    bool                     is_unique
    240241    )
    241242{
     
    245246  the_rbtree->first[1]         = NULL;
    246247  the_rbtree->compare_function = compare_function;
     248  the_rbtree->is_unique        = is_unique;
    247249}
    248250
     
    318320 *  having key equal to key of  @a the_node if it exists,
    319321 *  and NULL if not. @a the_node has to be made up before a search.
     322 *
     323 *  @note If the tree is not unique and contains duplicate keys, the set
     324 *        of duplicate keys acts as FIFO.
    320325 */
    321326RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected(
     
    325330{
    326331  RBTree_Node* iter_node = the_rbtree->root;
     332  RBTree_Node* found = NULL;
    327333  int compare_result;
    328334  while (iter_node) {
    329335    compare_result = the_rbtree->compare_function(the_node, iter_node);
    330336    if (compare_result == 0) {
    331         return(iter_node);
     337      found = iter_node;
     338      if ( the_rbtree->is_unique )
     339        break;
    332340    }
    333341
    334     RBTree_Direction dir = (compare_result != -1);
     342    RBTree_Direction dir = (compare_result == 1);
    335343    iter_node = iter_node->child[dir];
    336344  } /* while(iter_node) */
    337345
    338   return 0;
     346  return found;
    339347}
    340348
     
    429437  if (the_node == NULL) return;
    430438  if (the_node->child[(1-dir)] == NULL) return;
    431  
    432439
    433440  c = the_node->child[(1-dir)];
     
    444451  the_node->parent = c;
    445452}
     453
     454/** @brief Determines whether the tree is unique
     455 */
     456RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique(
     457    RBTree_Control *the_rbtree
     458)
     459{
     460  return( the_rbtree && the_rbtree->is_unique );
     461}
    446462/**@}*/
    447463
  • cpukit/score/src/rbtree.c

    r08ef1631 r74f1c73e  
    3333
    3434void _RBTree_Initialize(
    35   RBTree_Control *the_rbtree,
    36   void           *compare_function,
    37   void           *starting_address,
    38   size_t         number_nodes,
    39   size_t         node_size
     35  RBTree_Control          *the_rbtree,
     36  RBTree_Compare_function  compare_function,
     37  void                    *starting_address,
     38  size_t                   number_nodes,
     39  size_t                   node_size,
     40  bool                     is_unique
    4041)
    4142{
     
    4748
    4849  /* could do sanity checks here */
    49   _RBTree_Initialize_empty(the_rbtree, compare_function);
     50  _RBTree_Initialize_empty(the_rbtree, compare_function, is_unique);
    5051
    5152  count = number_nodes;
  • cpukit/score/src/rbtreeinsert.c

    r08ef1631 r74f1c73e  
    7373 *  @retval -1 NULL @a the_node.
    7474 *  @retval RBTree_Node* if one with equal key to the key of @a the_node exists
    75  *          in @a the_rbtree.
     75 *          in an unique @a the_rbtree.
    7676 *
    7777 *  @note It does NOT disable interrupts to ensure the atomicity
     
    9898    while (iter_node) {
    9999      compare_result = the_rbtree->compare_function(the_node, iter_node);
    100       if ( !compare_result ) return iter_node;
     100      if ( the_rbtree->is_unique && !compare_result )
     101        return iter_node;
    101102      RBTree_Direction dir = (compare_result != -1);
    102103      if (!iter_node->child[dir]) {
     
    139140 */
    140141
    141 void _RBTree_Insert(
     142RBTree_Node *_RBTree_Insert(
    142143  RBTree_Control *tree,
    143144  RBTree_Node *node
     
    147148
    148149  _ISR_Disable( level );
    149     _RBTree_Insert_unprotected( tree, node );
     150    return _RBTree_Insert_unprotected( tree, node );
    150151  _ISR_Enable( level );
    151152}
Note: See TracChangeset for help on using the changeset viewer.