segfaults in ordered_index

[christoph.kluge@…]

Hi,

we are suffering segfaults in ordered_index_node_impl::increment line 254

static void increment(pointer& x) {

if(x->right()!=pointer(0)){

x=x->right(); while(x->left()!=pointer(0))x=x->left(); XXX

} else{

pointer y=x->parent(); while(x==y->right()){

x=y; y=y->parent();

} if(x->right()!=y)x=y;

}

}

What, if x->left() becomes 0? Well, it does, over here! Shouldn't this read

while(x!=pointer(0)&&x->left()!=pointer(0))x=x->left();

? What is this line of code supposed to do anyway, other than uselessly consuming CPU time? Why not write

x = 0;

instead, if this was meant? ordered_index_node_impl_base::left and ordered_index_node_impl_base::right do not have any side-effects.

By the way, for the classes ordered_index_node_std_base and ordered_index_node_compressed_base, I don't see any of the POD data members getting initialized. A user-provided constructor is not defined. From the C++ Standard, IIRC, POD data members are not initialized by the implicitly-generated constructor and therefore have indeterminate values.

This also applies to recent versions of boost, the trunk included. The code doesn't appear to have changed here.

To me this looks like this is working only by chance. Has anyone ever bothered to review this code?

Cheers,

Christoph

[Joaquín M López Muñoz]

What, if x->left() becomes 0?

If x->left() is 0, then x=x->left() is not executed and x retains a non-null value (specifically, x points to a node whose left child is 0).

Well, it does, over here!

Can you provide a complete test program showing the effect? Without any other info, my bet is the internal rb-tree has been corrupted by some bug in your program.

Shouldn't this read

while(x!=pointer(0)&&x->left()!=pointer(0))x=x->left();

No; note that just before the while loop we have

if(x->right()!=pointer(0)){

x=x->right(); ...

So x can't be null and the extra check inside the loop is redundant.

What is this line of code supposed to do anyway, other than uselessly consuming CPU time? Why not write

x = 0;

As explained above, x won't be null after executing the while loop.

ordered_index_node_impl_base::left and ordered_index_node_impl_base::right do not have any side-effects.

This is supposedly not related to your problem, but: what's the problem with those member functions not having side effects?

By the way, for the classes ordered_index_node_std_base and ordered_index_node_compressed_base, I don't see any of the POD data members getting initialized. A user-provided constructor is not defined. From the C++ Standard, IIRC, POD data members are not initialized by the implicitly-generated constructor and therefore have indeterminate values.

This is correct. Initialization takes place at points in time other than construction, for instance in ordered_index::empty_initialize() and ordered_index_node_impl::link(). It is not an error to let POD values be uninitialized as long as they are actually initialized before being read.

To me this looks like this is working only by chance. Has anyone ever bothered to review this code?

This is slightly offensive but, as it does not contain either info on your problem or any other useful suggestion, I'll just ignore it.

I'm closing this as "invalid" (i.e. no bug detected). If you can come up with a test program where the crash happens please reopen the ticket and attach the relevant info. Thank you!