# Linux内核双向链表

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

kernel定义了list_head数据结构

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

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


## 初始化链表 LIST_HEAD

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

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

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


## 向链表添加新的节点 list_add

```
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前面，也就是链表的尾部, 可以用list_add_tail实现队列


## 从链表中删除节点 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;
}
```

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


## 判断链表是否为空 list_empty

将head指针作为list_empty的参数
```
static inline int list_empty(const struct list_head *head)
{
	return head->next == head;
}
```


## 遍历链表 list_for_each

```
#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)
```
遍历链表,通过pos返回指向链表元素list_head结构的指针


## 获取自定义结构体的地址 list_entry

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

ptr:   指向链表中的节点struct list_head
type:  自定义结构体类型，例如struct test_data
member:list_head类型的成员在自定义结构体中的名称，在test_data中是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是test_data中的一个成员, 如已经知道链表中的一个节点的地址，则可以通道list_entry获取对应的test_data结构体的地址


## 遍历链表，并获取自定义结构体的地址 list_for_each_entry

与list_for_each类似，但list_for_each_entry返回的是包含list_head的数据结构的地址,而不是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))
```