[Boost-bugs] [Boost C++ Libraries] #6978: Crash in rbtree_algorithms::rebalance_after_erasure, new in 1.49

Subject: [Boost-bugs] [Boost C++ Libraries] #6978: Crash in rbtree_algorithms::rebalance_after_erasure, new in 1.49
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2012-06-10 23:09:24

#6978: Crash in rbtree_algorithms::rebalance_after_erasure, new in 1.49
----------------------------------------------+-----------------------------
 Reporter:  jeff-boosttrac@…                  |       Owner:  igaztanaga
     Type:  Bugs                              |      Status:  new       
Milestone:  To Be Determined                  |   Component:  intrusive 
  Version:  Boost 1.49.0                      |    Severity:  Regression
 Keywords:                                    |  
----------------------------------------------+-----------------------------
 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;
 }

 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/6978>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.