Crash in rbtree_algorithms::rebalance_after_erasure, new in 1.49

[jeff-boosttrac@…]

The code below crashes with boost 1.49.

This is because of a change in 1.49 to return references from node_traits::get* and take references as parameters to all tree algorithms.

The code gets a reference to header.left with node_traits::get_left(header), and passes that reference into rbtree_algorithms::erase.

tree_algorithms::erase does a node_traits::set_left(header, ...) at some point, and since z is a reference to header.left, the z pointer changes halfway through tree_algorithms::erase, and passing the wrong z pointer to rebalance_after_erasure after that causes the crash.

#include <iostream>
#include "boost/intrusive/options.hpp"
#include "boost/intrusive/rbtree_algorithms.hpp"
#include "boost/intrusive/rbtree.hpp"

struct my_type : public boost::intrusive::set_base_hook<>
{
    my_type(int i) : i_(i) {}
    int i_;
};

typedef boost::intrusive::rbtree<my_type>::node_traits my_traits;

struct Compare
{
    bool operator()(my_traits::const_node_ptr a, my_traits::const_node_ptr b) { return static_cast<const my_type*>(a)->i_ < static_cast<const my_type*>(b)->i_; }
};

int main()
{
    std::cout << "if i wrap the pointer ref... " << std::endl;
    {
        my_traits::node header;
        boost::intrusive::rbtree_algorithms<my_traits>::init_header(&header);
        for (int i = 0; i < 20; ++i)
            boost::intrusive::rbtree_algorithms<my_traits>::insert_equal(&header, &header, new my_type(i), Compare());
        for (int i = 0; i < 20; ++i)
            boost::intrusive::rbtree_algorithms<my_traits>::erase(&header, my_traits::node_ptr(my_traits::get_right(&header)));
    }
    std::cout << " OK!" << std::endl;
    std::cout << "if i don't wrap the pointer ref... " << std::endl;
    {
        my_traits::node header;
        boost::intrusive::rbtree_algorithms<my_traits>::init_header(&header);
        for (int i = 100; i < 120; ++i)
            boost::intrusive::rbtree_algorithms<my_traits>::insert_equal(&header, &header, new my_type(i), Compare());
        for (int i = 0; i < 20; ++i)
            boost::intrusive::rbtree_algorithms<my_traits>::insert_equal(&header, &header, new my_type(i), Compare());
        for (int i = 0; i < 20; ++i)
            boost::intrusive::rbtree_algorithms<my_traits>::erase(&header, my_traits::get_left(&header));
    }
    std::cout << " OK!" << std::endl; // not really OK, it'll crash before it gets here
    return 0;
}

[jeff-boosttrac@…]

fixed by r80512; broken again by r80575.

[jeff-boosttrac@…]

Replying to jeff-boosttrac@…:

fixed by r80512; broken again by r80575.

Sorry - I must've got confused about what I was testing, r80575 does not re-break it. Current trunk passes the test above, since r80512

[Ion Gaztañaga]

Thanks for the report. Closing the issue as it's fixed in Boost 1.52