Linux Kernel Doubly Linked circular list

                                                              In this blog post I am introducing  the most beautiful linked list I have ever seen . This linked list is taken from linux kernel. Linux kernels linked list is entirely written in a single file . To see how it is implemented you can take a look at your kernel source ,it is located in /include/linux/list.h most of the linked list operations and data structures for the linked list is written  in that file. The code is documented well . The list written there is a doubly linked circular list. You can see the structure of node linked in linked list which is defined in the file /include/linux/types.h as 

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

almost all of the work in the linked list is done by a prepossessing macro

 #define list_entry(ptr, type, member) \
         container_of(ptr, type, member)

and if you look for what this container is doing you can see it as

#define container_of(ptr, type, member) ({                      \
         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
         (type *)( (char *)__mptr - offsetof(type,member) );})

  

I have implemented a small linked list code as a kernel module using the operations which are defined inside the list.h file.

#include<linux/module.h>
#include<linux/kernel.h>
#include<linux/list.h>
#include<linux/slab.h>

struct node {
 int data;
 struct list_head ptr;
};

#define list_t struct list_head
static struct list_head head = {&(head),&(head)};

static void print_dll(void)
{
 list_t *q = &head;
 struct node *temp;
 while(q->next != &head) {
  temp = list_entry(q->next,struct node,ptr);
  printk("data = %d\n",temp->data);
  q = q->next;
 }
}

struct node *new(int data)
{
 struct node *temp;
 temp = (struct node *) kmalloc(sizeof(struct node),GFP_KERNEL);
 temp->data = data;
 return temp;
}

static void dll_add(int data)
{
 list_add_tail(&(new(data)->ptr),&head);
}

static void make_dll(void)
{ 
 int i;
 for(i = 0; i < 10; i++) {
  dll_add(i);
 }
}

static void dll_delete(int data) 
{
 list_t *q;
 struct node *temp;
 for(q=&head;q->next != &head; q=q->next) {
  temp =  list_entry(q->next,struct node,ptr);
  if(temp->data == data) {
   list_del(&temp->ptr);
  }
 }
}

int init_module(void)
{
 printk("inserted linked list test module\n");
 make_dll();
 print_dll();
 printk("trying to deleat the node with data %d\n",5);
 dll_delete(5);
 print_dll();
 printk("the last element of the dll is %d\n",
   list_entry((&head)->prev,struct node,ptr)->data);
 return 0;
}

void cleanup_module(void)
{
 printk("cleaned module \n");
}
 

Screen short of output