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
No comments:
Post a Comment