Bug 43525 - Useless condition: "if (__x->_M_right != __y)"
Summary: Useless condition: "if (__x->_M_right != __y)"
Status: RESOLVED INVALID
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: unknown
: P3 enhancement
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2010-03-25 19:26 UTC by double
Modified: 2010-03-25 21:38 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description double 2010-03-25 19:26:07 UTC
The variable "__y" in _Rb_tree_increment (src/tree.cc) is always equal to "__x->_M_parent. Therefore the condition means (which is alwys true):

if (__x->_M_right != __x->_M_parent)

The source:

  _Rb_tree_node_base*
  _Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
  {
    if (__x->_M_right != 0) 
      {
        __x = __x->_M_right;
        while (__x->_M_left != 0)
          __x = __x->_M_left;
      }
    else 
      {
        _Rb_tree_node_base* __y = __x->_M_parent;      // y == x->parent
        while (__x == __y->_M_right) 
          {
            __x = __y;
            __y = __y->_M_parent;                 // y == x->parent
          }
        if (__x->_M_right != __y)    // if( x->right != x->parent )
          __x = __y;
      }
    return __x;
  }
Comment 1 Paolo Carlini 2010-03-25 20:44:17 UTC
Makes sense. I'm still a bit reluctant to change this for 4.5.0. The last time we improved a bit the RB tree implementation we compared it to the one used in the Linux kernel, can you do it and confirm?
Comment 2 Paolo Carlini 2010-03-25 21:04:52 UTC
Evidently, the condition isn't always true: if I replace it with a call to __builtin_abort() when __x->_M_right == __y then 21_strings/basic_string/requirements/exception/generation_prohibited.cc aborts. I don't have the time to investigate now in detail what's going on but the PR is certainly invalid.
Comment 3 double 2010-03-25 21:30:52 UTC
Hi Paolo,
Yes, you are right, I forgot the NULL value.
Sorry for disturbing.

Comment 4 Paolo Carlini 2010-03-25 21:38:08 UTC
Ok. No problem.