linux内核链表机制

   linux内核开发者建立了一套标准的循环、双向链表的实现。如果需要操作链表，推荐使用这一内核设施。为了使用这个链表机制，驱动程序必须包含头文件。对于用户态的普通程序，若想用这个机制，可把内核中的list.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;
}

 

头文件中声明的一些常用操作链表函数：

 

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在头文件中定义：

#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这个宏，通过查找其定义在文件中。

/**
 * 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，它定义在中，
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

其作用是计算TYPE类型的结构体中成员MEMBER的偏移。