Auto-unlink hooks

| Home | Libraries | People | FAQ | More

## 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 moment, without having any reference to the container, if the user want to do so.

These hooks have exactly the same size overhead as their analogue 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 using any reference to the container.

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

- 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 being inserted in the intrusive container, the container checks if the hook is the well-known default state. If not, an assertion is raised.
- Every time an object is being erased from the 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 an 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.