Linux- struct list_head简介

struct list_head简介

在Linux内核中，提供了一个用来创建双向循环链表的结构 list_head。虽然linux内核是用C语言写的，但是list_head的引入，使得内核数据结构也可以拥有面向对象的特性，通过使用操作list_head 的通用接口很容易实现代码的重用。

Linux内核中的链表方式与众不同，他不是将数据结构塞入链表，而是将链表结点塞入数据结构。链表代码在<linux/list.h>中声明。

首先找到list_head结构体定义，include/linux/list.h 如下：

struct list_head {
	struct list_head *next, *prev;
};
1
2
3

next指向下一个链表结点，prev指向前一个链表结点。list_head本身并没有意义，他需要嵌入到你自己的数据结构中才有效。

需要注意的一点是，头结点head是不使用的，这点需要注意。

使用list_head组织的链表的结构如下图所示：

然后就开始围绕这个结构开始构建链表，然后插入、删除节点 ，遍历整个链表等等，其实内核已经提供好了现成的接口，接下来就让我们进入 kernel/include/linux/list.h中：

定义一个链表

这里我们随便创建一个例子：

struct qingmu
{
    unsigned int age;
    unsigned int weight;
    struct list_head list;
};
1
2
3
4
5
6

初始化链表
内核提供了下面的这些接口来初始化链表：

//静态初始化
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12

动态初始化：

struct qingmu  *mu;
mu = kmalloc(sizeof(struct *qingmu), GPL_KERNEL);
mu->age = 18;
mu->weight = 60;
INIT_LIST_HEAD(&mu->list);
1
2
3
4
5

如果一个结构在编译期静态创建，那么：

struct  qingmu mu{
	.age = 18
    .weight = 60;
	.list = LIST_HEAD_INIT(mu.list); 
};
1
2
3
4
5

将上述分解开来如下：

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

#define LIST_HEAD_INIT(mu.list) { &(mu.list), &(mu.list) }
            
mu.list.prev=&mu.list;
mu.list.next=&mu.list;

1
2
3
4
5
6
7

上述两种方式都可以把现有的数据结构改造成链表。

链表头

在上述的链表中我们假如有很多的qingmu结点，每一个节都都包涵有一个list_head指针，于是我们就可以从任何一个结点气遍历链表，直到我们看到所有的结点。不过有的时候，我们需要一个特殊的指针所引导整个链表，而不是从一个链表结点出发。那么就有了头结点的说法，也就是一个常规的list_head：

#define LIST_HEAD(name) \    //链表头
	struct list_head name = LIST_HEAD_INIT(name)
1
2

例如：

structlist_head myhead; 
LIST_HEAD(myhead)/INIT_LIST_HEAD(&myhead);
直接定义并初始化链表。
1
2
3

这样我们的链表就初始化完毕，链表头的myhead就prev 和 next指针分别指向myhead自己了，如下图：

添加结点

list_add

给链表增加一个结点：

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

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

从上面的函数可以看出，把新结点(new)插入到head结点后面。

和上面的例子相结合，此时我们已经创建了mu结点并初始化完成，我们需要在mu结点后面加一个结点：

struct qingmu mu1;
mu1.age = 19;
mu1.weight = 61;
list_add(&mu1,&mu->list);
1
2
3
4

这样我们就可以把mu1这个结点插入到mu结点的链表中去了。

list_add_tail

void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

从上面的函数可以看出，把新结点(new)插入到head结点前面。

例：

struct qingmu mu2;
mu2.age = 20;
mu2.weight = 62;
list_add(&mu2,&mu->list);
1
2
3
4

从链表中删除一个结点

list_del

从列表中删除一个结点：

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

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}
1
2
3
4
5
6
7
8
9
10
11
12

链表删除函数，传入参数是要删除的节点，调用__list_del函数，完成删除，删除后的节点的指针赋值为LIST_POISON1和LIST_POISON2宏，完成删除。LIST_POISON1和LIST_POISON2定义在 include/linux/list.h文件

#define LIST_POISON1  ((void *) 0x00100100)
#define LIST_POISON2  ((void *) 0x00200200)
1
2

删除后，该选节点已不在链表当中，因此不会再使用。LIST_POISON1/2是两个不会存在于内核空间的地址，如果使用，就会报错。因此，设置指针，是强制禁用该节点。

利用list_del(struct list_head *entry) 接口就可以删除链表中的任意节点了，但需注意，前提条件是这个节点是已知的，既在链表中真实存在，切prev，next指针都不为NULL。
例：

list_del(&mu2.list);
1

判断链表是否为空

static inline int list_empty(const struct list_head *head)
{
	return head->next == head;
}
1
2
3
4

通过判断传入结点的 下一个结点是否是自己来判断链表是否为空。

遍历链表

正向遍历：

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

#define prefetch(x) __builtin_prefetch(x)
1
2
3
4
5

一个简单的for循环。
循环的初始化工作：pos指向链表头的下一项。
循环的条件：pos不是链表头。
每次循环要做的事情：pos指向链表中的下一项

反向遍历：

#define list_for_each_prev(pos, head) \
	for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
        	pos = pos->prev)
1
2
3

例：

list_for_each(p,list_head)
  {
    	......
  }
1
2
3
4

例

list.h

#ifndef LIST_H
#define LIST_H

#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) );})
#define prefetch(x) __builtin_prefetch(x)

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

typedef struct qingmu
{
    unsigned int age;
    unsigned int weight;
    struct list_head list;
}Qingmu_t;

//静态初始化
#define LIST_HEAD_INIT(name) { &(name), &(name) }
//链表头
#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

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

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

#define list_for_each_entry(pos, head, member)				\
	for (pos = list_entry((head)->next, typeof(*pos), member);	\
	     prefetch(pos->member.next), &pos->member != (head); 	\
	     pos = list_entry(pos->member.next, typeof(*pos), member))


void INIT_LIST_HEAD(struct list_head *list);
void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next);
void list_add_tail(struct list_head *new, struct list_head *head);
void list_add(struct list_head *new, struct list_head *head);
void __list_del(struct list_head * prev, struct list_head * next);
void list_del(struct list_head *entry);
int list_empty(const struct list_head *head);

#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

list.c

#include<stdio.h>
#include <sched.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>
#include "list.h"
//动态初始化
void INIT_LIST_HEAD(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}
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;
}
void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}
void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}
void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}
void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
//	entry->next = LIST_POISON1;
//	entry->prev = LIST_POISON2;
}

int list_empty(const struct list_head *head)
{
	return head->next == head;
}

void display_list(struct list_head *list_head)
{
  int i=0;
  struct list_head *p;
  struct qingmu *entry;
  printf("-------list---------\n");
  list_for_each(p,list_head)
  {
    printf("node[%d]\n",i++);
    entry=list_entry(p,struct qingmu,list);
    printf("\tage: %d\n",entry->age);
    printf("\tweight: %d\n",entry->weight);
  }
  printf("-------end----------\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

example

#include "list.h"
#include<stdio.h>
#include <sched.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>


struct list_head myhead;

int main()
{
    int ret =0,i=0;
 //   struct list_head *p,*q;
//    Qingmu_t *entry;

    INIT_LIST_HEAD(&myhead);  //初始化链表
    ret = list_empty(&myhead);
    if(ret)
    {
        printf("list is empty\n");
    }
    struct qingmu  mu;
    mu.age = 18;
    mu.weight = 60;

    struct qingmu  mu1;
    mu1.age = 19;
    mu1.weight = 61;

    struct qingmu  mu2;
    mu2.age = 20;
    mu2.weight = 62;
    
    list_add(&mu.list,&myhead);
    list_add(&mu1.list,&myhead);
    list_add(&mu2.list,&myhead);

    ret = list_empty(&myhead);
    if(ret)
    {
        printf("list is empty\n");
    }else
    {
        printf("list is not empty\n");
    }

    display_list(&myhead);
	return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

执行结果如下：

后续链表中还可以实现不同的数据结构的嵌套。而且还有很多API都可以在include/linux/list.h中找到。