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

[Andrey Semashev]

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;
}

[Andrey Semashev]

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

[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());
            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
      }
   }

[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.

[Andrey Semashev]

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

[anonymous]

Fixed in revision 51971.