Modify

Opened 8 years ago

Closed 8 years ago

#2862 closed Bugs (fixed)

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

Reported by: andysem Owned by: igaztanaga
Milestone: Boost 1.39.0 Component: intrusive
Version: Boost 1.38.0 Severity: Showstopper
Keywords: slist swap Cc:

Description

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<
        MyData,
        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;

    l2.swap(l1);

    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 8 years ago by andysem

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

comment:2 Changed 8 years ago by andysem

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());
            this->set_last_node(other.get_last_node());
            other.set_last_node(tmp);
         }
         break;

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

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

      default:; // both lists are empty
      }
   }

comment:3 Changed 8 years ago by andysem

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 8 years ago by andysem

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

comment:5 Changed 8 years ago by anonymous

  • Resolution set to fixed
  • Status changed from new to closed

Fixed in revision 51971.

Add Comment

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain igaztanaga.
The resolution will be deleted. Next status will be 'reopened'.
Author


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

 
Note: See TracTickets for help on using tickets.