list-test.cpp

// Experiment: Intrusively linked list, implemented using C++ templates
// 2019, Jens Stimpfle

#include <assert.h>
#include <stddef.h>
#include <stdio.h>

struct ListLink {
        ListLink *next;
        ListLink *prev;
};

void __list_init(struct ListLink *list)
{
    list->next = list;
    list->prev = list;
}

#define __list_get_link(item, offset) ((ListLink *) ((char *) (item) + (offset)))
#define __list_get_container(type, link, offset) ((type *) ((char *) (link) - (offset)))

void __list_insert_between(ListLink *prev, ListLink *next, ListLink *item)
{
        assert(prev->next == next);
        assert(next->prev == prev);
        item->next = next;
        item->prev = prev;
        prev->next = item;
        next->prev = item;
}

void __list_append(struct ListLink *list, struct ListLink *item)
{
        __list_insert_between(list->prev, list, item);
}

void __list_prepend(struct ListLink *list, struct ListLink *item)
{
        __list_insert_between(list, list->next, item);
}


template<typename T, int OFF>
ListLink *GetLink(T *item)
{
    return __list_get_link(item, OFF);
}

template<typename T, int OFF>
T *GetContainer(ListLink *link)
{
    return __list_get_container(T, link, OFF);
}

template<typename T, int OFF>
struct ListIter {
    ListLink *current;
    T& operator*() { return *GetContainer<T, OFF>(current); }
    void operator++() { current = current->next; }
    void operator--() { current = current->next; }
    bool operator==(ListIter<T, OFF>& other) const { return current == other.current; }
    bool operator!=(ListIter<T, OFF>& other) const { return current != other.current; }
};

template<typename T, int OFF>
struct List {
        ListLink head;
        List() { __list_init(&head); }
        void append(T *item) { __list_append(&head, GetLink<T, OFF>(item)); }
        void prepend(T *item) { __list_prepend(&head, GetLink<T, OFF>(item)); }
        ListIter<T, OFF> begin() { return ListIter<T, OFF> { head.next }; }
        ListIter<T, OFF> end() { return ListIter<T, OFF> { &head }; }
};

#define LIST(T, member) List<T, offsetof(T, member)>



struct Foo {
    int x;
    Foo(int x) : x(x) {}
    ListLink link;
};

int main(int argc, const char **argv)
{
    LIST(Foo, link) list;
    Foo foos[] = { Foo(42), Foo(43), Foo(44) };
    for (int i = 0; i < 3; i++)
        list.prepend(&foos[i]);
    for (Foo& foo : list)
        printf("%d\n", foo.x);
    return 0;
}