Changeset f53aa8d in rtems


Ignore:
Timestamp:
May 3, 2012, 4:43:29 PM (7 years ago)
Author:
Gedare Bloom <gedare@…>
Branches:
4.11, master
Children:
c100ba1
Parents:
a41950dd
git-author:
Gedare Bloom <gedare@…> (05/03/12 16:43:29)
git-committer:
Gedare Bloom <gedare@…> (05/08/12 22:40:44)
Message:

rbtree: API changes. Remove rbtree control node from RBTree_Next.

The implementation of RBTree_Next was using an awkward construction to detect
and avoid accessing the false root of the red-black tree. To deal with the
false root, RBTree_Next was comparing node parents with the control node.
Instead the false root can be detected by checking if the grandparent of a
node exists; the grandparent of the tree's true root is NULL by definition
so the root of the tree is found while walking up the tree by checking for
the non-existence of a grandparent.

This change propagates into the predecessor/successor and iterate functions.

Files:
8 edited

Legend:

Unmodified
Added
Removed
  • cpukit/sapi/inline/rtems/rbtree.inl

    ra41950dd rf53aa8d  
    284284 */
    285285RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor_unprotected(
    286   const rtems_rbtree_control *rbtree,
    287286  const rtems_rbtree_node *node
    288287)
    289288{
    290   return _RBTree_Predecessor_unprotected( rbtree, node );
     289  return _RBTree_Predecessor_unprotected( node );
    291290}
    292291
     
    295294 */
    296295RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor(
    297   const rtems_rbtree_control *rbtree,
    298296  const rtems_rbtree_node *node
    299297)
    300298{
    301   return _RBTree_Predecessor( rbtree, node );
     299  return _RBTree_Predecessor( node );
    302300}
    303301
     
    306304 */
    307305RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor_unprotected(
    308   const rtems_rbtree_control *rbtree,
    309306  const rtems_rbtree_node *node
    310307)
    311308{
    312   return _RBTree_Successor_unprotected( rbtree, node );
     309  return _RBTree_Successor_unprotected( node );
    313310}
    314311
     
    317314 */
    318315RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor(
    319   const rtems_rbtree_control *rbtree,
    320316  const rtems_rbtree_node *node
    321317)
    322318{
    323   return _RBTree_Successor( rbtree, node );
     319  return _RBTree_Successor( node );
    324320}
    325321
  • cpukit/sapi/src/rbheap.c

    ra41950dd rf53aa8d  
    204204
    205205static rtems_rbheap_chunk *get_next(
    206   const rtems_rbtree_control *chunk_tree,
    207206  const rtems_rbheap_chunk *chunk,
    208207  RBTree_Direction dir
     
    210209{
    211210  return rtems_rbheap_chunk_of_node(
    212     _RBTree_Next_unprotected(chunk_tree, &chunk->tree_node, dir)
     211    _RBTree_Next_unprotected(&chunk->tree_node, dir)
    213212  );
    214213}
     
    247246    if (chunk != NULL_PAGE) {
    248247      if (!rtems_rbheap_is_chunk_free(chunk)) {
    249         rtems_rbheap_chunk *pred = get_next(chunk_tree, chunk, RBT_LEFT);
    250         rtems_rbheap_chunk *succ = get_next(chunk_tree, chunk, RBT_RIGHT);
     248        rtems_rbheap_chunk *pred = get_next(chunk, RBT_LEFT);
     249        rtems_rbheap_chunk *succ = get_next(chunk, RBT_RIGHT);
    251250
    252251        check_and_merge(free_chain, chunk_tree, chunk, succ);
  • cpukit/score/include/rtems/score/rbtree.h

    ra41950dd rf53aa8d  
    308308 * @brief Returns the in-order next node of a node.
    309309 *
    310  * @param[in] rbtree The red-black tree.
    311310 * @param[in] node The node.
    312311 * @param[in] dir The direction.
     
    316315 */
    317316RBTree_Node *_RBTree_Next_unprotected(
    318   const RBTree_Control *rbtree,
    319317  const RBTree_Node *node,
    320318  RBTree_Direction dir
     
    327325 */
    328326RBTree_Node *_RBTree_Next(
    329   const RBTree_Control *rbtree,
    330327  const RBTree_Node *node,
    331328  RBTree_Direction dir
  • cpukit/score/inline/rtems/score/rbtree.inl

    ra41950dd rf53aa8d  
    385385 */
    386386RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor_unprotected(
    387   const RBTree_Control *rbtree,
    388387  const RBTree_Node *node
    389388)
    390389{
    391   return _RBTree_Next_unprotected( rbtree, node, RBT_LEFT );
     390  return _RBTree_Next_unprotected( node, RBT_LEFT );
    392391}
    393392
     
    398397 */
    399398RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
    400   const RBTree_Control *rbtree,
    401399  const RBTree_Node *node
    402400)
    403401{
    404   return _RBTree_Next( rbtree, node, RBT_LEFT );
     402  return _RBTree_Next( node, RBT_LEFT );
    405403}
    406404
     
    415413 */
    416414RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor_unprotected(
    417   const RBTree_Control *rbtree,
    418415  const RBTree_Node *node
    419416)
    420417{
    421   return _RBTree_Next_unprotected( rbtree, node, RBT_RIGHT );
     418  return _RBTree_Next_unprotected( node, RBT_RIGHT );
    422419}
    423420
     
    428425 */
    429426RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
    430   const RBTree_Control *rbtree,
    431427  const RBTree_Node *node
    432428)
    433429{
    434   return _RBTree_Next( rbtree, node, RBT_RIGHT );
     430  return _RBTree_Next( node, RBT_RIGHT );
    435431}
    436432
  • cpukit/score/src/rbtreeextract.c

    ra41950dd rf53aa8d  
    110110  if (the_node == the_rbtree->first[RBT_LEFT]) {
    111111    RBTree_Node *next;
    112     next = _RBTree_Successor_unprotected(the_rbtree, the_node);
     112    next = _RBTree_Successor_unprotected(the_node);
    113113    the_rbtree->first[RBT_LEFT] = next;
    114114  }
     
    118118  if (the_node == the_rbtree->first[RBT_RIGHT]) {
    119119    RBTree_Node *previous;
    120     previous = _RBTree_Predecessor_unprotected(the_rbtree, the_node);
     120    previous = _RBTree_Predecessor_unprotected(the_node);
    121121    the_rbtree->first[RBT_RIGHT] = previous;
    122122  }
  • cpukit/score/src/rbtreeiterate.c

    ra41950dd rf53aa8d  
    4141    stop = (*visitor)( current, dir, visitor_arg );
    4242
    43     current = _RBTree_Next_unprotected( rbtree, current, dir );
     43    current = _RBTree_Next_unprotected( current, dir );
    4444  }
    4545}
  • cpukit/score/src/rbtreenext.c

    ra41950dd rf53aa8d  
    2929
    3030RBTree_Node *_RBTree_Next_unprotected(
    31   const RBTree_Control *rbtree,
    3231  const RBTree_Node *node,
    3332  RBTree_Direction dir
     
    4443    }
    4544  } else {
    46     const RBTree_Node *null = (const RBTree_Node *) rbtree;
    4745    RBTree_Node *parent = node->parent;
    4846
    49     if ( parent != null && node == parent->child [opp_dir] ) {
     47    if ( parent->parent && node == parent->child [opp_dir] ) {
    5048      next = parent;
    5149    } else {
    52       while ( parent != null && node == parent->child [dir] ) {
     50      while ( parent->parent && node == parent->child [dir] ) {
    5351        node = parent;
    54         parent = node->parent;
     52        parent = parent->parent;
    5553      }
    5654
    57       if ( parent != null ) {
     55      if ( parent->parent ) {
    5856        next = parent;
    5957      }
     
    6563
    6664RBTree_Node *_RBTree_Next(
    67   const RBTree_Control *rbtree,
    6865  const RBTree_Node *node,
    6966  RBTree_Direction dir
     
    7471
    7572  _ISR_Disable( level );
    76   next = _RBTree_Next_unprotected( rbtree,  node, dir );
     73  next = _RBTree_Next_unprotected( node, dir );
    7774  _ISR_Enable( level );
    7875
  • testsuites/sptests/sprbtree01/init.c

    ra41950dd rf53aa8d  
    440440
    441441  puts( "INIT - Verify rtems_rbtree_predecessor/successor");
    442   p = rtems_rbtree_predecessor(&rbtree1, p);
     442  p = rtems_rbtree_predecessor(p);
    443443  if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 29) {
    444444    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
     
    446446  }
    447447  p = rtems_rbtree_find(&rbtree1, &search_node.Node);
    448   p = rtems_rbtree_successor(&rbtree1, p);
     448  p = rtems_rbtree_successor(p);
    449449  if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 31) {
    450450    puts ("INIT - ERROR ON RBTREE ID MISMATCH");
Note: See TracChangeset for help on using the changeset viewer.