bug in any_xxx_node_traits, returning by reference

[apkulikov@…]

bstree_algo::rotate_left has parameter p_parent passed by const ref (invoked by rebalance_after_insertion).

With set hook this is ref to temporary variable (default_rbtree_node_traits_impl::get_parent returns value).

With any hook this is ref to node's variable (any_rbtree_node_traits::get_parent returns reference).

This variable is used after node changed. Use local var?

PS: are other rotate_XXX functions OK?

[anonymous]

After fixing this I still have infinite loops and crashes in intrusive sets. Rolled back to 1.55 where everything is stable for me...

[Ion Gaztañaga]

I can't see any problem with the code, the temporary is valid until the function ends. Any chance to have a test program that reproduces your crash?

[anonymous]

Yes, memory block is valid. But this is not temporary, this is any hook's member. In case of non-any hook (normal set_base_hook) this IS actually a temporary.

Program above can be fixed by making parameter p_parent not ref but value. But there are more bugs and I currently not able to find out, ma application still crashing or has infinite loops but only after some time.

[anonymous]

To be even more specific: &p_parent == &p.node_ptr_1 in case of any_hook. So when rotate_left calls rotate_left_no_parent_fix(p,...) &p_parent starts p_right, while with set_base_hook it remains the same.

[Ion Gaztañaga]

Ok, I see. The problem is in the any hook member, it should not return by reference. This was changed in all other node_traits and it seems I forgot to do the same with any_xxx_node_traits classes.

Fixed in:

​https://github.com/boostorg/intrusive/commit/b9aa032d981ad65fce5ea99179e22c25e35f03e8

Thanks for the report.

[anonymous]

Happy to help!

PS: TBH strange function argument requirement to be temporary, at least static assertion in rbtree_algorithms could verify that hook trait returns value.