id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
6978,"Crash in rbtree_algorithms::rebalance_after_erasure, new in 1.49",jeff-boosttrac@…,Ion Gaztañaga,"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;
}

}}}",Bugs,closed,To Be Determined,intrusive,Boost 1.49.0,Regression,fixed,,