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; }
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?
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.
Hi Paolo, Yes, you are right, I forgot the NULL value. Sorry for disturbing.
Ok. No problem.