Linux内核链表实现过程

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 服务器相关›Shell 编程范例

原作者: [db:作者] 来自: [db:来源] 收藏邀请

关于双链表实现，一般教科书上定义一个双向链表节点的方法如下：

struct list_node{
stuct list_node *pre;
stuct list_node *next;
ElemType data; 
}

即一个链表节点包含：一个指向前向节点的指针、一个指向后续节点的指针，以及数据域共三部分。
但查看linux内核代码中的list实现时，会发现其与教科书上的方法有很大的差别。
来看看linux是如何实现双链表。
双链表节点定义

复制代码代码如下:

struct list_head {
 struct list_head *next, *prev;
};

发现链表节点中根本就没有数据域，这样的链表有什么用？linux内核中定义这样的链表原因何在？
这是因为linux中是通过独立定义一个链表结构，并在结构体中内嵌一个链表节点来实现链表结构的。这样有一个好处就是能达到链表与结构体分离的目的。如此一来，我们构建好一个链表后，其结构示意图如下：

链表的定义及初始化宏定义：

复制代码代码如下:

#define LIST_HEAD_INIT(name){&(name),&(name)}  
#define LIST_HEAD(name) \
      struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \ 
      (ptr)->next = (ptr); (ptr)->prev = (ptr);\
      } while (0) 

LIST_HEAD(name)宏用来定义一个链表头，并使他的两个指针都指向自己。我们可以在程序的变量声明处，直接调用LIST_HEAD(name)宏，来定义并初始化一个名为name的链表。也可以先声明一个链表，然后再使用INIT_LIST_HEAD来初始化这个链表。
也即：

复制代码代码如下:

 LIST_HEAD(mylist);
 与
 struct list_head mylist;
 INIT_LIST_HEAD(&mylist);

是等价的。

插入操作

复制代码代码如下:

/*仅供内部调用
　　* Insert a new entry between two known consecutive entries.
　　* This is only for internal list manipulation where we know
　　* the prev/next entries already!
　　*/
static inline 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;
}
 

复制代码代码如下:

//在头节点后面插入一个节点
static inline void list_add(struct list_head *new, struct list_head *head)
{
 __list_add(new, head, head->next);
}
//在尾节点后插入一个节点
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
 __list_add(new, head->prev, head);
}

删除操作

复制代码代码如下:

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
 next->prev = prev;
 prev->next = next;
}
static inline void list_del(struct list_head *entry)
{
 __list_del(entry->prev, entry->next);
}

删除链表节点的操作很简单，是通过将要删除的节点的前一个节点与后一个节点链接到一起。
链表节点替换操作

复制代码代码如下:

static inline void list_replace(struct list_head *old,
    struct list_head *new)
{
 new->next = old->next;
 new->next->prev = new;
 new->prev = old->prev;
 new->prev->next = new;
}
 

链表遍历操作（重点在这里）
首先来看一个如何根据链表节点地址得到其所在结构体的地址。

复制代码代码如下:

#define list_entry(ptr, type, member) container_of(ptr, type, member)
//container_of宏的定义如下：
#define container_of(ptr, type, member)({\
        const typeof(((type *)0)->member ) *__mptr = (ptr);\
        (type *)( (char *)__mptr - offsetof(type,member) );})
//offsetof的宏定义如下：
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
将上述简化一下成为下面这样：
#define list_entry(ptr, type, member) \
  ((type *)((char *)(ptr)-(size_t)(&((type *)0)->member)))

是一个带3个参数的宏，该宏的作用是获取链表节点(ptr)所在结构体的起始地址。有了这个宏，我们只要知道某一个链表节点指针，就可以通过该链表节点得到其所在结构体的指针，从而，我们遍历链表，也便可以达到遍历我们自己定义的结构体。第一个参数为一个地址，他是结构体链表节点元素的地址，第二个参数是结构体类型，第三个参数是链表节点元素在结构体中的名字。
来仔细分析一下这个宏：
最外面的一层括号可以去掉，这是为了防止宏扩展的，去掉如下：
(type *) ((char *)(ptr)-(size_t)(&((type *)0)->member))
现在就比较清楚了，首先(type *)是C强制转换操作，就是将后面的的数据转化成type结构的指针。而后面的操作可以再分解
(char *)(ptr) - (size_t)(&((type *)0)->member)
这样就是一个减法的操作，前面是一个指针，我们传过去的结构体链表节点元素的指针，这里被转化成指向字符的。而后面是一个整形，可以再分解
(size_t) (&((type *)0)->member)
显然这个整形是一个指针转化的，而这个指针又可以再分解，
&((type *)0)->member
     可以看出这个指针是一个变量取地址得到的，这个变量又是什么呢
((type *)0)->member
     看起来有点奇怪，不过这个操作是整个宏中最精妙的，他将地址0转化成type类型，接下来又取得这个结构的member元素，member就是我们传进来的参数：元素在结构体中的命名。其实((type *)0)->member取的变量是内容是什么一点都不重要，重要的我们要取这个变量的地址。取完这个地址将它转换成size_t类型，这样这个数据就是((type *)0)->member相对与地址0的偏移。回到上面的那个减法，将结构体中链表节点元素的地址与他与结构体首地址的偏移相减，不就得到了结构体的地址了吗。)(&((type *)0)->member)))
    最外面的一层括号可以去掉，这是为了防止宏扩展的，去掉如下：
(type *) ((char *)(ptr)-(size_t)(&((type *)0)->member))
     现在就比较清楚了，首先(type *)是C强制转换操作，就是将后面的数据转化成type结构的指针。而后面的操作可以再分解
(char *)(ptr) - (size_t)(&((type *)0)->member)
     这样就是一个减法的操作，前面是一个指针，我们传过去的结构体元素的指针，这里被转化成指向字符的。而后面是一个长整形，可以再分解
(size_t) (&((type *)0)->member)
     显然这个长整形是一个指针转化的，而这个指针又可以再分解，
&((type *)0)->member
     可以看出这个指针是一个变量取地址得到的，这个变量又是什么呢?
((type *)0)->member
     起来有点奇怪，不过这个操作是整个宏中最精妙的，他将地址0转化成type类型，接下来又取得这个结构的member元素，member就是我们传进来的参数：元素在结构体中的命名。其实((type *)0)->member取的变量是内容是什么一点都不重要，重要的我们要取这个变量的地址。取完这个地址将它转换成size_t类型，这样这个数据就是((type *)0)->member相对与地址0的偏移。回到上面的那个减法，将结构体中元素的地址与他与结构体首地址的偏移相减，便得到了结构体的地址了。
链表的遍历操作时通过一个宏来实现的：

复制代码代码如下:

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

其中prefetch是用于性能优化，暂时不用去管它。
从上述链表遍历宏可以看出，其只是一次获得了链表节点指针，在实际应用中，我们都需要获取链表节点所在结构体的数据项，因此，通常将list_for_each和list_entry一起使用。为此，linux的list实现提供了另外一个接口如下：

复制代码代码如下:

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

有了这个接口，我们就可以通过链表结构来遍历我们实际的结构体数据域了。
例如，我们定义了一个结构体如下：

复制代码代码如下:

struct mystruct{
ElemType1 data1;
ElemType2 data2;
strcut list_head anchor;//通常我们称结构体内的链表节点为链表锚，因为它有定位的作用。
}

那么我们遍历链表的代码如下：

复制代码代码如下:

struct mystruct  *pos;
list_for_each_entry(pos,head,anchor){
mystruct *pStruct=pos;
//do something with pStruct.....
}

此外Linux链表还提供了两个对应于基本遍历操作的"_safe"接口：list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos, n, head, member)，它们要求调用者另外提供一个与pos同类型的指针n，在for循环中暂存pos下一个节点的地址，避免因pos节点被释放而造成的断链。
当然，linux链表不止提供上述接口，还有

复制代码代码如下:

list_for_each_prev(pos, head)
list_for_each_prev_safe(pos, n, head)
list_for_each_entry_reverse(pos, head, member)
list_prepare_entry(pos, head, member)
static inline int list_empty_careful(const struct list_head *head)
static inline void list_del_init(struct list_head *entry)
static inline void list_move(struct list_head *list, struct list_head *head)
static inline void list_move_tail(struct list_head *list,
struct list_head *head)
static inline int list_empty(const struct list_head *head)