Linux内核双向链表

对于每个链表，必须实现一组操作集： 初始化链表，插入和删除一个元素,遍历链表

kernel定义了list_head数据结构

include/linux/list.h 定义了list_head数据结构:

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

字段next和prev分别表示通用链表向前和向后的指针元素, listhead的next和prev存的是另一个listhead的地址: 只要自己定义的结构体包含了struct list_head成员，就可以通过内核定义的一系列的宏来构造一个我们自己的链表.

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

LISTHEAD定义了一个struct listhead类型的变量，并使next, prev指向这个变量本身.

static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}

list_add是list.h的内部函数，将新的节点new插入到prev和next之间 static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); } 将new插入到head后面, 可以用list_add实现栈 static inline void list_add_tail(struct list_head *new, struct list_head *head) { __list_add(new, head->prev, head); } 将new插入到head前面，也就是链表的尾部, 可以用listaddtail实现队列 ## 从链表中删除节点 list_del static inline void __list_del(struct list_head * prev, struct list_head * next) { next->prev = prev; prev->next = next; } list_del是list.h的内部函数, 删除next和preb之间的节点

static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}

listdel将节点entry从链表中删除, 并使next和prev指向无效的地址 LISTPOSITION1, LISTPOSITION2 LISTPOSITION1和LIST_POISON2是一个无效的地址,引用这个地址会导致页错误

将head指针作为listempty的参数 static inline int list_empty(const struct list_head *head) { return head->next == head; } ## 遍历链表 listfor_each

#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

遍历链表,通过pos返回指向链表元素list_head结构的指针

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

ptr: 指向链表中的节点struct listhead type: 自定义结构体类型，例如struct testdata member:listhead类型的成员在自定义结构体中的名称，在testdata中是list

container_of是内核中常见的一个宏，通过成员地址获取结构体地址，实际上就是通过偏移量来计算的

定义如下：

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

例如自定义结构体如下:

struct test_data
{
    struct list_head list;

    int id;
    int intdata[128];
    void* pri_data;
};

LIST_HEAD(test_head);

int i;
struct test_data* pdata;
struct list_head* pnode;

for (i = 0; i < 10; i++)
{
    pdata = (struct test_data*)malloc(sizeof(struct test_data));
    pdata->id = i;
    list_add_tail(&pdata->list, &test_head); 
}

list_for_each(pnode, &test_head)
{
    pdata = list_entry(pnode, struct test_data, list);
    printf("list id: %d\n", pdata->id);
}

list是testdata中的一个成员, 如已经知道链表中的一个节点的地址，则可以通道listentry获取对应的test_data结构体的地址

与listforeach类似，但listforeachentry返回的是包含listhead的数据结构的地址,而不是list_head结构本身的地址

#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))