Opened 9 years ago

Closed 9 years ago

#2862 closed Bugs (fixed)

slist::swap is broken when cache_last< true > is used

Reported by: Andrey Semashev Owned by: Ion Gaztañaga
Milestone: Boost 1.39.0 Component: intrusive
Version: Boost 1.38.0 Severity: Showstopper
Keywords: slist swap Cc:


Swapping two slists with the cache_last option yields an invalid slist. The following code snippet demonstrates the problem:

#include <iostream>
#include <boost/checked_delete.hpp>
#include <boost/intrusive/options.hpp>
#include <boost/intrusive/slist.hpp>
#include <boost/intrusive/slist_hook.hpp>

namespace bi = boost::intrusive;

typedef bi::slist_base_hook<
    bi::link_mode< bi::safe_link >
> BaseHook_t;

struct MyData :
    public BaseHook_t
    int m_Data;

    explicit MyData(int d) : m_Data(d) {}

int main(int, char*[])
    typedef bi::slist<
        bi::base_hook< BaseHook_t >,
        bi::constant_time_size< true >,
        bi::cache_last< true >
    > List_t;

    List_t l1;

    MyData* p = 0;
    p = new MyData(1); l1.push_back(*p);
    p = new MyData(2); l1.push_back(*p);
    p = new MyData(3); l1.push_back(*p);
    p = new MyData(4); l1.push_back(*p);

    std::cout << "l1.front() = " << &l1.front() << std::endl;

    List_t l2;


    std::cout << "l2.front() = " << &l2.front() << std::endl; // should be the same as l1.front() above

    l2.clear_and_dispose(boost::checked_deleter< MyData >()); // this line crashes

    return 0;

Attachments (0)

Change History (5)

comment:1 Changed 9 years ago by Andrey Semashev

An addition: looks like the problem occurs only when one of the lists is empty.

comment:2 Changed 9 years ago by Andrey Semashev

The following version of the priv_swap_cache_last method fixes the problem for me, although I'm not sure it's acceptable:

   void priv_swap_cache_last(slist_impl &other)
      int choice = static_cast< int >(this->empty()) * 2 + static_cast< int >(other.empty());
      switch (choice)
      case 0: // both lists are not empty
            node_ptr other_last(other.get_last_node());
            node_ptr this_last(this->get_last_node());
            node_ptr other_bfirst(other.get_root_node());
            node_ptr this_bfirst(this->get_root_node());

            node_algorithms::transfer_after(this_bfirst, other_bfirst, other_last);
            node_algorithms::transfer_after(other_bfirst, other_last != other_bfirst? other_last : this_bfirst, this_last);
            node_ptr tmp(this->get_last_node());

      case 1: // other.empty() == true
         other.splice_after(other.before_begin(), *this);

      case 2: // this->empty() == true
         this->splice_after(this->before_begin(), other);

      default:; // both lists are empty

comment:3 Changed 9 years ago by Andrey Semashev

Oh, just noticed, there's no need for the "other_last != other_bfirst" comparison as it always yields true in the proposed priv_swap_cache_last version.

comment:4 Changed 9 years ago by Andrey Semashev

On the second thought, ignore it. The splice_after breaks the constatnt_time_size behavior.

comment:5 Changed 9 years ago by anonymous

Resolution: fixed
Status: newclosed

Fixed in revision 51971.

Modify Ticket

Change Properties
Set your email in Preferences
as closed The owner will remain Ion Gaztañaga.
The resolution will be deleted.

Add Comment

E-mail address and name can be saved in the Preferences.

Note: See TracTickets for help on using tickets.