Non-Intrusive Linked List

Non-Intrusive Linked List
Long time back I have seen some interesting implementation of linked list.
Recently I saw some discussion on hackernews, got again intested to understand that list implementation.
Similar implementation is used by Linux kernel linked list

Normally when a developer defines a linked list, he/she will add data part as member of linked list node
say you want to create linked list of Integers then one would have struct as follows

struct intList {
   int data;
   struct intList *prev;
   struct intList *next;
}

– Now this list is attached to data-type integer.
– You cannot have same node part of two different list.
– This is called as Intrusive Linked List.
– You have to do lot of careful surgery of list, need to check pointers is null or not.

Non-Intrusive Linked list is amazing way of getting rid of these restrictions.

Let us define a new Non-Intrusive linked list which will work with any POD in C language.

struct llhead {
  struct llhead *prev, *next;
};

Note that there is no mention of the type it is storing. This seems strange at first.
Intrusive linked lists flip the memory layout inside out. Instead of the list node providing memory for
a POD, POD provides memory for a list node. The ‘intrusive’ part of the name comes from the fact that
we store the list node inside the type POD.

Let us define some operation on this list

#define LL_INIT(N)      ((N)->next = (N)->prev = (N))
#define LL_HEAD(H)      struct llhead H = { &H, &H }
#define LL_ENTRY(P,T,N) ((T *)((char *)(P) - offsetof(T, N)))
#define LL_TAIL(H, N)                   \
  do {                                  \
    ((H)->prev)->next = (N);            \
    (N)->prev = ((H)->prev);            \
    (N)->next = (H);                    \
    (H)->prev = (N);                    \
  } while (0)
#define LL_DEL(N)                       \
  do {                                  \
    ((N)->next)->prev = ((N)->prev);    \
    ((N)->prev)->next = ((N)->next);    \
    LL_INIT(N);                         \
  } while (0)
#define LL_FOREACH(H,N) for (N = (H)->next; N != (H); N = (N)->next)
#define LL_FOREACH_SAFE(H,N,T)         \
  for (N = (H)->next, T = (N)->next; N != (H);     \
      N = (T), T = (N)->next)

Remember this is actually Circular doubly linked list.

Now I want to create a list of integers, this is how I will be writing my POD

struct integerList {
  struct llhead link;
  int data;
};

Initialize the head of the list.

LL_HEAD(mylist);

Here is the complete working example.

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include "ilist.h"


struct llhead {
  struct llhead *prev, *next;
};

#define LL_INIT(N)      ((N)->next = (N)->prev = (N))
#define LL_HEAD(H)      struct llhead H = { &H, &H }
#define LL_ENTRY(P,T,N) ((T *)((char *)(P) - offsetof(T, N)))
#define LL_TAIL(H, N)                   \
  do {                                  \
    ((H)->prev)->next = (N);            \
    (N)->prev = ((H)->prev);            \
    (N)->next = (H);                    \
    (H)->prev = (N);                    \
  } while (0)
#define LL_DEL(N)                       \
  do {                                  \
    ((N)->next)->prev = ((N)->prev);    \
    ((N)->prev)->next = ((N)->next);    \
    LL_INIT(N);                         \
  } while (0)
#define LL_FOREACH(H,N) for (N = (H)->next; N != (H); N = (N)->next)
#define LL_FOREACH_SAFE(H,N,T)         \
  for (N = (H)->next, T = (N)->next; N != (H);     \
      N = (T), T = (N)->next)


struct integerList {
  struct llhead link;
  int data;
};

int main(int argc, char **argv) {
  int k = 0; 
  struct llhead *head;
  static LL_HEAD(mylist);

  for ( k = 0; k < 10; k++) {
    struct integerList *elem = 
          (struct integerList *)malloc(sizeof(struct integerList));
    elem->data = k;
    LL_TAIL(&mylist, &elem->link);
  }

  LL_FOREACH(&mylist, head) {
    struct integerList *elem = LL_ENTRY(head, struct integerList, link);
    printf("%d\n", elem->data );
  }

  return 0;
}
Advertisements