DLIST hack (cont.)

Last blog was about a doubly circular linked list, as well as some common definitions. This article is going to talk about why a generic doubly circular linked list is useful. The main reason to use the DLIST structure mentioned in the previous article is because it is very generic. Otherwise you will have next/prev self-referential structure pointers. In this case, we made a struct whose sole members were self-referential structure pointers. Therefore, if any struct has this structure as a member, then it can link to any other struct that also has this same structure as a member.

This is a little bit odd, but useful. The oddity is the reason why it's a _hack_. To see why this would be useful is easy. You can chain multiple different types of structures. This is quite amazing actually, and there is a way to get the original structure that holds this DLIST object within it.

Before giving an example, I will describe a way, in which we can get the original structure whose DLIST member is being chained within the doubly cirucluar linked list. There is another post, in which I described the list-head problem. Whereby, if you have an element within a structure, you can go to the top of the structure if you know how many bytes the top of the structure is in regards to the actual element of the structure. All you need to do is subtract the bytes from the starting address of the element within the structure and the offset position of the element within the structure definition.

Let's see some code:

typedef struct dlist {
        struct dlist * next;
        struct dlist * prev;
} dlist_t;

typedef struct A {
        int c;
        dlist_t list;
        int a;
} A_t;

#define DLIST_INIT(dlistp) \
{ \
        (dlistp)->prev = (dlistp)->next = (dlistp); \
}
#define DLIST_ADD2HEAD(dlistp, newp) \
{ \
        dlist_t *oldfirstp; \
        oldfirstp = (dlistp)->next; \
        oldfirstp->prev = (dlistp)->prev; \
        (newp)->next = oldfirstp; \
        (newp)->prev = (dlistp); \
        (dlistp)->next = (newp); \
}
#define DLIST_ADD2TAIL(dlistp, newp) \
{ \
        dlist_t *oldlastp; \
        oldlastp = (dlistp)->prev; \
        (dlistp)->prev = (newp); \
        (newp)->next = (dlistp); \
        (newp)->prev = oldlastp; \
        oldlastp->next = (newp); \
}
#define DLIST_GET_ELEMENT(ptr, type, element_of_type) \
        ((type *)((char *)(ptr) - (size_t)offsetof(type, element_of_type)))

int main() {

        A_t a1, b1, c1;
        a1.a = 3, b1.a = 4, c1.a = 5;

        DLIST_INIT(&a1.list)
        DLIST_INIT(&b1.list)
        DLIST_INIT(&c1.list)

        DLIST_ADD2TAIL(&a1.list, &b1.list)
        DLIST_ADD2TAIL(&a1.list, &c1.list)

        printf("%d\n", DLIST_GET_ELEMENT(&a1.list, struct A, list)->a);
        printf("%d\n", DLIST_GET_ELEMENT(a1.list.next, A_t, list)->a);
        printf("%d\n", DLIST_GET_ELEMENT(a1.list.prev, A_t, list)->a);
        printf("%d\n", (unsigned)(&((A_t *)0)->list));

        return 0;
}

This allows us to chain any structure that has a DLIST member somewhere located within the structure.