LINUX基础-list链表

linux-链表

在看linux内核或者由linux提供的一些代码中，经常会遇到LIST_HEAD、INIT_LIST_HEAD等宏定义，以及一些如list_for_each、list_entry等函数。下面我介绍下常用的几个宏定义以及函数的意义。

 

1.struct list_head

在linux中用的是双向循环链表，定义的结构如下：

struct list_head

{

    struct list_head *next, *prev;

}

注意定义的这个链表节点中是没有数据域的，在linux内核中不是链表结构中包含数据域，而是在数据结构中内嵌链表节点。这个和linux内核中的KObjet等数据结构一样都是内嵌的。

 

2.初始化linux链表

初始化一个链表就是声明一个节点，让这个节点的prev域和next域都指向它自身。有两种方法：

(1):LIST_HEAD(name);

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)

 

声明一个节点name ，让这个节点的prev域和next域都指向它自身的地址。

 

(2):INIT_LIST_HEAD(ptr);

 

#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

 

以上两个没有区别，就是在使用INIT_LIST_HEAD之前要先申明一个list_head变量ptr。

 

2.遍历一个链表

(1)list_for_each;

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

 

#define __list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
list_for_each()有prefetch()prefetch() prefetch()用于预取以提高遍历速度，而__list_for_each()无prefetch()用于简单的表的遍历.

(2)list_for_each_safe

for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
这个主要是在遍历的过程中，要删除这个节点是用到。如果在list_for_each中调用list_del(pos)(将pos的前后指针指向undefined state)panic，list_del_init(pos)(将pos前后指针指向自身)导致死循环。

 

注意list_for_each和list_for_each_safe就是一个for循环，使用的时候注意如果在循环体里面有删除节点是用list_for_each_safe，没有得时候就用list_for_each.

 

3.list_entry()函数

list_entry函数用于根据链表指针找到包含这个链表指针的数据结构体。

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

 

container_of见文章 《LINUX基础-container_of》

 

4.list_for_each_entry

一般来讲用list_for_each循环遍历以后，就要调用list_entry来获得数据结构体。list_for_each_entry就是上面两个的综合。

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