linux内核链表机制

时间：2010-12-28 来源：shenhailuanma

   linux内核开发者建立了一套标准的循环、双向链表的实现。如果需要操作链表，推荐使用这一内核设施。为了使用这个链表机制，驱动程序必须包含头文件<linux/list.h>。对于用户态的普通程序，若想用这个机制，可把内核中的list.h文件中的所需内容拷贝到自己的头文件中。    在头文件<linux/types.h>中，定义了该链表机制所需的list_head类型的结构体。      struct list_head {
     struct list_head *next, *prev;
     };
   用于实际代码的的链表几乎总是由某种结构类型构成，为了在代码中使用linux链表机制，只需在构成链表的机构里嵌入一个list_head。    链表头通常是一个独立的list_head结构。下图显示了简单的struct list_head是如何用来维护一个数据结构链表的。    在使用之前，必须用INIT_LIST_HEAD宏来初始化链表头。可如下声明并初始化一个实际的链表头： struct list_head todo_list; INIT_LIST_HEAD(&todo_list);    另外，可以在编译时像下面这样初始化链表： LIST_HEAD(todo_list);    为了加深理解及在用户空间使用，下面为上述内容的相关源代码： #define LIST_HEAD_INIT(name) { &(name), &(name) } #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name) void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
头文件<linux/list.h>中声明的一些常用操作链表函数： 1. void list_add(struct list_head *new,struct list_head *prev,struct list_head *next);     在链表头后面添加新项（通常实在链表的头部）。这样，它可以被用来建立栈。但需要注意的是，head并不一定非得是链表名义上的头；如果传递了一个恰巧位于链表中间某处的list_head结构体，新项会紧跟在它的后面。因为linux链表是循环式的，链表头通常与其他的项没有本质上的区别。所以可以利用这个特点可是使添加新项的位置变得灵活了许多。源码如下： 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(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
2.void list_del(struct list_head *entry); 删除链表中的指定项。
源码如下： 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;
} 其中LIST_POISON1，LIST_POISON2在头文件<linux/poison>中定义： #define POISON_POINTER_DELTA 0 /*
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
#define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
   由于从链表删除的单元在物理上还存在，为了防止出错，使next及prev指向特定的地址。在实际应用中，对于没用的动态分配产生的链表单元，不要忘了free掉。
3.list_entry(struct list_head *ptr, type_of_struct, field_name);    首先说明一下，list_entry是一个宏，定义在list.h中。因为调用程序通常对被嵌入list_head结构而组成链表的大结构更有兴趣。因此，可以利用list_entry宏将返回指向包含它的大结构的指针。其源码如下所示： /**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
很尴尬，在list.h中没有定义container_of这个宏，通过查找其定义在<linux/kernel.h>文件中。 /**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({   \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
   在上述头文件的定义中，ptr是指向结构体一成员，type是包含ptr指向成员的结构体，member是str指向成员的名字。    对于typeof的说明请参考http://blog.chinaunix.net/u3/119286/showart.php?id=2453376    对于宏offsetof，它定义在<linux/stddef.h>中，
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) 其作用是计算TYPE类型的结构体中成员MEMBER的偏移。