Comparison with Owning Containers

Traditionally, containers "own" the elements which they reference. For instance, di::Vector<T> internally allocates memory to store each element in the vector. As a consequence, there it is inconvient to store the same value of type T in multiple containers.

Intrusive containers allow the container itself to use the space inside of an element T as part of the storage. This scheme allows data structures like linked-lists and trees to be efficently implemented without allocation. Storing nodes on the stack is useful in cases where the a thread needs to store add itself to a linked list, and then block. Also, in multi-threaded applications, an intrusive container protected by a lock can be used without needing to access the global allocator. This is criticial in kernelspace, because allocation is fallible and requires synchronization. By using intrusive containers, kernel code doesn't need to handle insertion failures, and doesn't hold locks to containers while performing the actual allocation.

Main Concern with Intrusive Containers

The main issue with intrusive containers is that they do not have owner-ship semantics. In particular, there is no way to enforce that the nodes being referenced are valid. Sometimes this is by design, when allocating on the stack before blocking. In other cases, code must make use of reference-counting to ensure object validity.

Another important point is that, from an implementation perspective, it would be nice to implement owning containers in terms of intrusive containers. This ensures that the 2 containers will have feature parity. But to do so, we need to introduce some customization points for intrusive containers.

Intrusive Container Customizations

The intrusive container implementation has 6 customization points.

Operation	Description
Tag::node_type(`di::InPlaceType<T>`) -> Tag::Node	Get the correct node type for a given T.
Tag::down_cast(`di::InPlaceType<T>`, Tag::Node& node) -> T&	Cast from a node type to the underlying T value.
Tag::is_sized(`di::InPlaceType<T>`) -> bool	Determines whether the container offers an O(1) size function.
Tag::always_store_tail(`di::InPlaceType<T>`) -> bool	Determines whether a ForwardList offers O(1) back() and push_back().
Tag::did_insert(IntrusiveContainer&, Tag::Node& node)	Hook which intrusive container calls just after inserting the node.
Tag::did_remove(IntrusiveContainer&, Tag::Node& node)	Hook which intrusive container calls just after removing the node.

Notice, there are 2 hooks which are called when inserting and removing elements, respectively. This is used so that reference-counted objects can take a reference on insertion and drop a reference on removal. The did_remove hook will be used by the owning containers to delete the object directly. As an implementation note, the last template parameter of the intrusive containers is the IntrusiveContainer type to pass the hooks. This allows user code to have the hook called with their own subclass and node type.

The down_cast method is used to convert from an internal node to a value of type T. This is needed so that the container's iterator will function correctly.

Additionally, each Tag passed to the container has an associated Node type, which is required to conform to the container's requirements. This means that the Node type must either be the container's node base class, or the Node type must publically inherit from it. Internally, intrusive containers will downcast their internal pointers to the Node type before calling these customizations.

The Tag also can customize whether or not the intrusive container stores a size. By standard C++, the owning list type should store the list's size. However, there is no need to store the size unless it is specifically needed.

In addition, the Tag can custommize whether or a ForwardList will store a pointer to the tail. This allows providing a .back() and .push_back() functions, which makes the container usable with the di::Queue adapter. This is enabled by default for normal intrusive containers, but by standard C++, the owning variant will not provide this functionality.

Using the IntrusiveList class

Types which want to be added to an IntrusiveList can use the following snippet.

class MyType : public di::IntrusiveListElement<> {};

static void test() {
    auto my_list = di::IntrusiveList<MyType> {};
    auto x = MyType {};
    my_list.push_back(x);
}

To create a custom type, declare it like so and then inherit from the correct list element helper.

struct MyTag : di::IntrusiveListTag<MyTag> {};
 
class MyType : public di::IntrusiveListNode<MyTag> {};

static void test() {
    auto my_list = di::IntrusiveList<MyType, MyTag> {};
    auto x = MyType {};
    my_list.push_back(x);
}

As another example, to create a Type which needs shared ownership, a custom Tag can be used. In the future, there could even be a helper tag-type to implement this pattern. Also, under this approach, there needs to be some action which drops the last reference to MyType, since its initial reference count is 1.

struct MyTag;
 
class MyType
    : public di::IntrusiveListNode<MyTag>
    , di::IntrusiveRefCount<MyType> {};
 
struct MyTag : di::IntrusiveListTag<MyTag> {
    using Node = di::IntrusiveListTag<MyTag>::Node;
 
    constexpr static void did_insert(di::InPlaceType<MyType> t, Node& node) {
        auto& value = MyTag::down_cast(t, node);
        auto to_leak = di::Arc<MyType>(node, di::adopt_object);
        (void) to_leak.release();
    }
 
    constexpr static void did_remove(di::InPlaceType<MyType> t, Node& node) {
        auto& value = MyTag::down_cast(t, node);
        auto to_drop = di::Arc<MyType>(node, di::retain_object);
    }
};