list_head结构的使用

时间：2010-12-08 来源：wushuan10141

在Linux内核中，提供了一个用来创建双向循环链表的结构list_head。使用list_head提供的相应接口，链表操作将变得相当简单。

下面就是kernel中的list_head结构定义：
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }

需要注意的一点是，头结点head是不使用的，这一点我在最初使用list_head的时候，经常忘记，直接把head当作第一个节点拿来使用，结果出错了，呵呵。记住！链表的第一个节点是head的下一个节点，呵呵。

下面简单介绍一下这个结构的几个常用接口：

LIST_HEAD() -- 生成一个名为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_entry()

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

根据指针ptr(该指针指向数据结构type中数据域member)，返回其所在代表的整个数据结构(type)的指针
#define container_of(ptr, type, member)                     \
({                                                            \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);\
        (type *)( (char *)__mptr - offsetof(type,member) ); \
})

计算数据域MEMBER在数据结构TYPE中的偏移量
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

list_entry是个相当有用的接口，用多了你就会渐渐看出它的好了。因为list_head通常是作为某个struct的一个成员的，而不是单独拿来使用的，因此就经常需要用到list_entry了。

实例:
--------------------------------------------------
(1) ptr是一个page结构内部的成分lru的地址，而我们所需要的却是那个page结构本身的地址，所以要从地址ptr减去一个位移量，即成分lru内部的位移量，才能达到要求。那么，这位移量到底是多少呢?
&((type *)0)->member
&((struct page *)0)->lru 表示当结构体page正好在地址0上时其成分lru的地址，这就是位偏移量

(2) 根据给定的进程task，获取链表中的下一个进程(task->tasks.next指向下一个进程task_struct的tasks域，返回的数据结构为task_struct):
list_entry(task->tasks.next, struct task_struct, tasks)

task_struct {

        struct list_head tasks;
        ... ...

}

双向链表的插入操作 -- list_add()

将new所代表的结构体插入head所管理的双向链表的头节点head之后: （即插入表头）

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

new -->|---------------|
       |list_head *next|
       |list_head *prev|
       |---------------|

                                      （new 结点）
head-->|---------------|     |---------------|
       |list_head *next|---->|list_head *next|
       |list_head *prev|<----|list_head *prev|
       |---------------|     |---------------|

static inline void __list_add( struct list_head *new,
                                   struct list_head *prev,
                                   struct list_head *next)
{
       next->prev = new;         //(1)
       new->next = next;         //(2)
       new->prev = prev;         //(3)
        prev->next = new;         //(4)
}

__list_add()参数初始状态
-------------------------------------------------------
new ----->|---------------|
              |list_head *next|
              |list_head *prev|
              |---------------|

prev--+                   next--+
          |                         |
head--+-->|---------------| |       |---------------|
              |list_head *next|-+-->|list_head *next|
              |list_head *prev|<----|list_head *prev|
              |---------------|         |---------------|


__list_add()运行后的链表状态 (将新节点new插入到头节点head之后)
---------------------------------------------------------
prev--+                    next---+
          |                           |
head--+-->|---------------|<-+|        |---------------|
              |list_head *next|-+|+--->|list_head *next|
              |list_head *prev| ||+----|list_head *prev|
              |---------------| ||| +->|---------------|
       +------------------------+|| |
       |            (3)                  || |
       |--+----------------------+| |
       |--|                        (1)| |
new|--|-->|---------------|<--+ |
       |--|       |list_head *next|-----+(2)
       |--|---|list_head *prev|
       +----->|---------------|
         (4)

如果是要插入链表末尾，可以使用list_add_tail(new, head);

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

list_del(entry) 把entry从list中删除

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;
}

list_empty() -- 判断链表是否为空

如果双向链表head为空则返回真，否则为假
----------------------------------------------------
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}

遍历双向链表，list_head提供了两个很有用的宏定义：

遍历双向链表 -- list_for_each()

遍历head(struct list_head)索引的双向链表，每找到一个节点就将该节点赋给pos(struct list_head)

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

                       pos ---+
                              |
head -->|---------------| | -|---------------|        |---------------|
            |list_head *next|-+->|list_head *next|--->|list_head *next|
            |list_head *prev|<---|list_head *prev|<---|list_head *prev|
            |---------------|        |---------------|        |---------------|

如果只是遍历读取list的话，直接使用list_for_each()即可。可是如果你在遍历过程中还要对list进行操作的话（特别是delete操作），应使用另一个安全版本list_for_each_safe()。

list_for_each_safe()

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

它在遍历之前，会先保存pos的next域到n中，这样对pos节点删除后，下一个节点就不会断开了。