Auto-unlink hooks

What's an auto-unlink hook?

Boost.Intrusive offers additional hooks with unique features:

When the destructor of the hook is called, the hook checks if the node is inserted in a container. If so, the hook removes the node from the container.
The hook has a member function called unlink() that can be used to unlink the node from the container at any time, without having any reference to the container, if the user wants to do so.

These hooks have exactly the same size overhead as their analog non auto-unlinking hooks, but they have a restriction: they can only be used with non-constant time containers. There is a reason for this:

Auto-unlink hooks don't store any reference to the container where they are inserted.
Only containers with non constant-time size() allow removing an object from the container without referring to the container.

This auto-unlink feature is useful in certain applications but it must be used very carefully:

If several threads are using the same container the destructor of the auto-unlink hook will be called without any thread synchronization so removing the object is thread-unsafe.
Container contents change silently without modifying the container directly. This can lead to surprising effects.

These auto-unlink hooks have also safe-mode properties:

Hooks' constructors put the hook in a well-known default state.
Every time an object is inserted in the intrusive container, the container checks if the hook is in the well-known default state. If not, an assertion is raised.
Every time an object is erased from an intrusive container, the container puts the erased object in the well-known default state.

Auto-unlink hook example

Let's see an example of an auto-unlink hook:

#include <boost/intrusive/list.hpp>
#include <cassert>

using namespace boost::intrusive;

typedef list_base_hook<link_mode<auto_unlink> > auto_unlink_hook;

class MyClass : public auto_unlink_hook
               //This hook removes the node in the destructor
{
   int int_;

   public:
   MyClass(int i = 0)   :  int_(i)  {}
   void unlink()     {  auto_unlink_hook::unlink();  }
   bool is_linked()  {  return auto_unlink_hook::is_linked();  }
};

//Define a list that will store values using the base hook
//The list can't have constant-time size!
typedef list< MyClass, constant_time_size<false> > List;

int main()
{
   //Create the list
   List l;
   {
      //Create myclass and check it's linked
      MyClass myclass;
      assert(myclass.is_linked() == false);

      //Insert the object
      l.push_back(myclass);

      //Check that we have inserted the object
      assert(l.empty() == false);
      assert(&l.front() == &myclass);
      assert(myclass.is_linked() == true);

      //Now myclass' destructor will unlink it
      //automatically
   }

   //Check auto-unlink has been executed
   assert(l.empty() == true);

   {
      //Now test the unlink() function

      //Create myclass and check it's linked
      MyClass myclass;
      assert(myclass.is_linked() == false);

      //Insert the object
      l.push_back(myclass);

      //Check that we have inserted the object
      assert(l.empty() == false);
      assert(&l.front() == &myclass);
      assert(myclass.is_linked() == true);

      //Now unlink the node
      myclass.unlink();

      //Check auto-unlink has been executed
      assert(l.empty() == true);
   }
   return 0;
}

Auto-unlink hooks and containers with constant-time `size()`

As explained, Boost.Intrusive auto-unlink hooks are incompatible with containers that have constant-time size(), so if you try to define such container with an auto-unlink hook's value_traits, you will get a static assertion:

#include <boost/intrusive/list.hpp>

using boost::intrusive;

struct MyTag;

class MyClass : public list_base_hook< link_mode<auto_unlink> >
{/**/};

list <MyClass, constant_time_size<true> > bad_list;

int main()
{
   bad_list list;
   return 0;
}

leads to an error similar to:

error : use of undefined type 'boost::STATIC_ASSERTION_FAILURE<false>'

Pointing to code like this:

//Constant-time size is incompatible with auto-unlink hooks!
BOOST_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink)));

This way, there is no way to compile a program if you try to use auto-unlink hooks in constant-time size containers.

Boost C++ Libraries

Auto-unlink hooks

What's an auto-unlink hook?

Auto-unlink hook example

Auto-unlink hooks and containers with constant-time size()

Auto-unlink hooks and containers with constant-time `size()`