Linux内核有一些基本的数据结构，这些数据结构是Linux实现的基础，对于链表相信大家都不陌生，但是Linux内核中的链表与平常平常我们所使用的链表略有不同，第一次遇到或许会感到困惑。
先来看一个链表的节点，对于一个节点，分为两部分，一部分是数据，另一部分是串联数据的指针。Linux链表节点的定义如下(以下代码皆为3.5版本)：
// include/linux/types.h
struct list_head {
struct list_head *next, *prev;
};
这里的定义有些奇怪，因为仅有前后节点的指针，并没有数据，就像一串链子，只有线没有线上的珠子，肯定是无法使用，那Linux内核如何把这些“珠子”附着到线上的呢？
来看一个简单的例子：
struce simple {
int data;
struct list_head list;
};
simple结构体的list成员指向下一个或者上一个simple的list，这样便把节点串联起来了，data作为“珠子”附着在list线上，但这样仍然有一个问题，list成员仅仅指向下一个simple的list成员，那从list成员如何得到simple节点的地址呢？
答案是根据list成员的地址以及list成员在simple的位置便可以计算出simple对象的地址，这样有些繁琐，Linux提供了一个宏，可以简化这个过程：
// include/linux/list.h
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
// include/linux/kernel.h
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif
#endif /* __KERNEL__ */
可以看到，list_entry直接调用了container_of，container_of分为两句，((type *)0)->member可以获得member在结构体type中的偏移，假设有一个结构体在地址0的位置，那么成员的地址便是成员对结构体的偏移，typeof是gcc的扩展，用于获取变量的类型，offsetof(type,member) 获取member成员在type中的偏移，然后使用member成员的指针ptr（复制成__mptr）减去偏移，即是结构体的地址。在我们的例子中，从list成员的地址获取simple结构的地址如下：
simple * p = list_entry(ptr, struct simple, list);
这样便解决了从list_head上获取附着的数据的问题。接下来需要解决对链表的增删改查的问题：
一、初始化链表：
初始化链表有两种方法，LIST_HEAD_INIT和LIST_HEAD
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
创建一个指向自身的节点。
二、插入：
在节点后插入新节点list_add_tail，和在节点前插入新节点list_add：
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
/**
* list_add_tail - add a new entry
* @new: new entry to be added
* @head: list head to add it before
*
* Insert a new entry before the specified head.
* This is useful for implementing queues.
*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
其中 __list_add 只是普通的链表操作，并无特别之处，可参见Linux源码查看实现。
三、删除节点：
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
__list_del 把entry从链表中删除，之后把entry链表指针复制成非空指针（如果使用会出现段错误）
四、检查是否空链表
判断一个链表是否为空，只需要看头节点是否指向自己便可：
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
五、遍历
遍历是这几种操作中最为复杂的，有四个函数：
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); pos = pos->prev)
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.prev, typeof(*pos), member))
list_for_each 和 list_for_each_prev 较为简单，一个向后遍历，另一个向前遍历，list_for_each_entry和list_for_each_entry_reverse功能相似，不过不是对list_head操作，而是直接对结构体操作，如我们这里的simple结构。根据之前的叙述也不难理解函数实现，只是在list_head上调用了list_entry获取了完整结构。
六、实例
千言万语不如一个例子来的直观，我们通过一个简单的例子说明一下如何使用内核链表：
#include <linux/list.h>
#include <linux/kernel.h>
#include <stdio.h>
struct simple {
int data;
struct list_head list;
};
int main()
{
int i = 0;
struct simple * p;
struct list_head * pos;
LIST_HEAD(head);
for (i = 0; i < 10; i++) {
p = (struct simple*)malloc(sizeof(struct simple));
p->data = i * 10;
list_add_tail(&p->list, &head);
}
list_for_each_entry(p, &head, list) {
printf("for %d\n", p->data);
}
while (!list_empty(&head)) {
pos = head.next;
p = (struct simple*)list_entry(pos,
struct simple, list);
list_del(pos);
printf("del %d\n", p->data);
free(p);
}
return 0;
}
编译参数为
gcc -D__KERNEL__ -I/usr/src/linux-headers-3.2.0-27-generic/include/ -I/usr/src/linux-headers-3.2.0-27-generic/arch/ia64/include/ simple.c
其中头文件中都是内核函数，需要宏__KERNEL__，否则大部分定义会被忽略。
转载自：http://tech.fancymore.com/page/143.html#more-143