双向循环链表struct list_head

ningxinleng

双向循环链表
tdhlshx@yahoo.com.cn, 2008-4-30
内核中很多地方使用双向循环链表来维护一些信息，比如任务队列。
双向循环链表定义于include/linux/list.h，只有两个成员next与prev分别指向后继与前趋结点。一般内嵌到别的结构体内使用。避免了每个需要双向循环链表的数据结构都自己维护指针并编写链表操作函数。
struct list_head {
    struct list_head *next, *prev;      
};
一些常用的相关宏和函数如下：
INIT_LIST_HEAD(ptr)  初始化ptr节点为表头，将前趋与后继都指向自己。
LIST_HEAD(name) 声明并初始化双向循环链表name。
static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
向链表中在prev与next之间插入元素new
static inline void list_add(struct list_head *new, struct list_head *head)
在链表中头节点后插入元素new，调用__list_add()实现。
static inline void list_add_tail(struct list_head *new, struct list_head *head)
在链表末尾插入元素new，调用__list_add()实现。
static inline void __list_del(struct list_head * prev, struct list_head * next)
删除链表中prev与next之间的元素。
static inline void list_del(struct list_head *entry)
删除链表中的元素entry。
static inline void list_del_init(struct list_head *entry)
从链表中删除元素entry,并将其初始化为新的链表。
static inline void list_move(struct list_head *list, struct list_head *head)
从链表中删除list元素，并将其加入head链表。
static inline void list_move_tail(struct list_head *list, struct list_head *head)
把list移动到链表末尾。
static inline int list_empty(const struct list_head *head)
测试链表是否为空。
static inline void __list_splice(struct list_head *list, struct list_head *head)
将链表list与head合并。
static inline void list_splice(struct list_head *list, struct list_head *head)
在list不为空的情况下，调用__list_splice()实现list与head的合并。
static inline void list_splice_init(struct list_head *list, struct list_head *head)
将两链表合并，并将list初始化。
list_entry(ptr, type, member)
list_entry的定义是怎么回事？
a. list_entry的定义在内核源文件include/linux/list.h中：
#define list_entry(ptr, type, member)
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
b. 其功能是根据list_head型指针ptr换算成其宿主结构的起始地址，该宿主结构是type型的，而ptr在其宿主结构中定义为member成员。如下图：
req-->|type型对象起始地址
|
|... ...
ptr-->|ptr指针所指的member成员地址
|
|... ...
ptr指向图中所示的位置，通过(unsigned long)(&((type*)0)->member)得到ptr
和req之间的差值，ptr减去这个差值就得到了type型宿主结构的指针req，返回
类型为(type*)。（这个技巧很绝啊！头结构与宿主结构的member成员的地址差正好是这个宿主结构的地址，即相对于0地址。）
把((char *)(ptr)-(换成unsigned long *就不对了， 因为“偏移”这个东西，其单位是字节； 在指针的加减运算中，只有（unsigned）char *型的指针，其运算单位是字节…
list_for_each(pos, head)，__list_for_each(pos, head)
列出链表head中的每一项，前者有调用prefetch进行预取而后者没有。。
list_for_each_prev(pos, head)
反向列出链表head中的每一项，有预取。
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/85268/showart_2182236.html