list.h文件分析

Posted on In 
1
2
3
structlist_head {
       struct list_head *next, *prev; 
};

一上来就放这么一个数据结构，那么，这个到底要做什么呢？没错，就如上面代码所示，本文的主角就是它，由它衍生而来的一些问题。首先自我介绍，它，来自Linux系统中的链表。

就是个链表的头！是不觉得很奇怪？怎么只有两个指针域，没有数据域呢？其实笔者现在也纠结这这个问题着呢！没事，咱们先往下看。说不定什么时候，咱就明白了这是怎么一回事情呢。

1
2
3
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#defineLIST_HEAD(name) \
       struct list_head name = LIST_HEAD_INIT(name)

这俩是宏没错吧！来看看这个俩到底是个什么意思。

先来看看这个LIST_HEAD_INIT(name)，当程序当中出现了这个东西的时候，它立马就会替换成后面的东西，例如出现了：
LIST_HEAD_INIT(headnode)；
它立马就会替换成{&(headnode),&(headnode)}.
假设有这么一段C代码

1
2
struct list_head headnode ;//定义了一个headnode节点
headnode = LIST_HEAD_INIT(headnode);

那么它是不应该再编译阶段就立马的被替换成这样呢？

1
2
struct list_head headnode ;//定义了一个headnode节点
headnode = { &(headnode), &(headnode) };

注意：这里面对标准的C进行了拓展叫：GNU C，这个意思呢就是说，对headnode的两个成员赋值。这赋值之后成了什么样子了呢？看下图：

图一

是不是自己指向了自己？至于为什么可以这么赋值，不是本文讨论的重点，详细的可以Google.

其实这里的LIST_HEAD_INIT(name)宏是用来初始化的；
而LIST_HEAD(name)宏则是用来定义+初始化。你看LIST_HEAD(name)宏是不比LIST_HEAD_INIT(name)宏多了这句 struct list_head name ？

记住：

LIST_HEAD_INIT(name)宏是用来初始化的；

LIST_HEAD(name)宏则是用来定义+初始化。

OK，我们接着往下看：

1
2
3
4
5
static inline void INIT_LIST_HEAD(struct list_head *list)
{
       list->next = list;
       list->prev = list;
}

奇怪这里怎么好像又是在初始化，而且还和上面的功能一样。笔者觉得，他们这样做有如下考虑：

有些人习惯于调用函数进行初始化，而有的人喜欢代码简洁而直接使用宏来进行初始化，但是不论是那种方式，都达到了一样的功能,即初始化。

往下看，有关链表添加的

1
2
3
4
5
6
7
8
9
10
11
#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,  struct list_head *prev,  struct list_head *next);
#endif

注意 __list_add前面可是两个下划线；这个就是说，这个函数是linux内核的东西，使用的时候，就得注意了。一看名字就知道是增加链表节点；其实我们学习双向链表的时候，那么多的指针操作，能把人绕死，而且到最后也搞得不清楚，看看人家linux源代码是咋实现的：是不觉得有差距？

往下看：

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

刚才不说了么，前头俩下划线的让谨慎的使用么，这不？又弄了一个函数，可以调用这个函数来进行链表的添加。

实际上，还是调用的是刚才的那个有两个下划线的函数。这里体现了两个思想：

1、封装，其实这个概念是C++等一类程序设计语言的OOP思想，用在了这里。

2、重用，很多时候，代码其实都是可以不用自己写的，有一些现成的东西你可以去调用，这样可以很好的提高生产效率，而且linux源代码使用的是GPL许可证，没有什么版权啊乱七八糟的东西，有这么好的东西干嘛不用呢？其实下来的这个你会体会的更深：

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

看名字，看看list_add_tail这个名字。是不是“尾插法”？还是调用了前头的那个有两个下划线的函数吧？而且，仅仅只是调换了一下参数的次序。高明吧！

好！再接着往下看：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
       next->prev = prev;
       prev->next = next;
}
 
#ifndef CONFIG_DEBUG_LIST
static inline void list_del(struct list_head *entry)
{
       __list_del(entry->prev, entry->next);
       entry->next = LIST_POISON1;
       entry->prev = LIST_POISON2;
}
#else
extern void list_del(struct list_head *entry);
#endif

这里是删除一节点，这里再一次的体现了封装和重用的思想。不过这里注意：

在将entry这个节点删除之后你得将它指向一个正确的错误区域！什么意思呢，就是说，你的将它放在一个大家公认的错误的地方，因为所有的人都不会去碰那个错误的地方，所以，你这个entry就不会引起各种不必要的麻烦。其实这里有一个问题：你free了某个节点之后，其实，我们还是可以使用这个节点的，这个在一篇博文里讲述的很清楚：
http://blog.sina.com.cn/s/blog_6e9342530100yaef.html

其实这里，LIST_POISON1= 0x00100100. LIST_POISON2=0x00200200。为什么，笔者不知道。

下来接着看这个替换函数。将链表当中某个节点用新的节点替换掉。

1
2
3
4
5
6
7
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;
}

下面在给出图例：

图二

大家可以根据图例来理解。

下来这个函数就是将某个链表里头的节点删除，然后添加到另外一个链表当中。你会发现代码很简单

1
2
3
4
5
static inline void list_move(struct list_head *list, struct list_head *head)
{
       __list_del(list->prev, list->next);
       list_add(list, head);
}

下面这两个函数，一个用来判断是否为链表的最后一个节点，一个用来判断该链表是否为空。

1
2
3
4
5
6
7
8
9
static inline int list_is_last(const struct list_head *list, const struct list_head *head)
{
       return list->next == head;
}
 
static inline int list_empty(const struct list_head *head)
{
       return head->next == head;
}

详细情况如下图：

图三

然而实际上，我们用这种方式来判断链表是否为空是不太精确的。它同时判断头指针的next和prev，仅当两者都指向自己时才返回真。这主要是为了应付另一个cpu正在处理同一个链表而造成next、prev不一致的情况。但代码注释也承认，这一安全保障能力有限：除非其他cpu的链表操作只有list_del_init()，否则仍然不能保证安全，也就是说，还是需要加锁保护。

两个链表合并：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static inline void __list_splice(const struct list_head *list, struct list_head *prev,  struct list_head *next)
{
       struct list_head *first = list->next;
       struct list_head *last = list->prev;
 
       first->prev = prev;
       prev->next = first;
 
       last->next = next;
       next->prev = last;
}
 
static inline void list_splice(const struct list_head *list, struct list_head *head)
{
       if (!list_empty(list))
              __list_splice(list, head, head->next);
}

假设当前有两个链表，表头分别是list1和list2（都是struct list_head变量），当调用list_splice(&list1,&list2)时，只要list1非空，list1链表的内容将被挂接在list2链表上，位于list2和list2.next（原list2表的第一个节点）之间。新list2链表将以原list1表的第一个节点为首节点，而尾节点不变。如图（虚箭头为next指针）：

图四

由于篇幅限制，当中其实，还有一些很有用的函数：比如切割啊，判断是否为单链表啊等等，其实当你再了解了这些函数之后，后面的都是大同小异。可以自己在做研究，下面将重点放在list.h当中的几个很重要的宏当中。
还是顺着list.h往下看，你会看到第一宏：

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

看到上面的那英文注释：获得结构体入口！

ptr：这个参数是指向list_head 类型的指针（注意这里，很容易再代码当中用错）。

type：看到那英文解释了么？这个type可不是list_head！他是list_head嵌入的那个结构体类型。详细会给出一断源代码，帮助大家理解。

member：这个看到名字就知道这个是结构体的一个成员。

list_entry(ptr,type,member)这个宏到底是干嘛的，是不应该看container_of这个宏是干嘛的呢？用Sorce Insight 查看，会发现它在很多文件里头都存在，它们都是一样的，这里选取/include/linux/kernel.h当中的container_of宏来说明。

1
2
3
#define container_of(ptr, type, member) ({        \
   const typeof( ((type *)0)->member ) *__mptr = (ptr); \
   (type *)( (char *)__mptr - offsetof(type,member) );})

这个宏的作用是：计算结构体成员member再结构体当中的相对位置（相对地址）。
现在想想，开头的时候，是不是看到了这个链表的结构体定义只有指针域而没有数据域？现在就是要计算出嵌入了list_head结构的结构体的数据域的地址。

1
2
3
4
struct stu{
   int id；
   struct list_head *next，*prev；
}；

就是要根据list_head类型的结构体计算出struct stu结构体当中成员id的地址。

现在假设有如下定义:

1
2
3
struct stu *p；
struct list_head *r;
r = p->next;

现在我们肯定是可以直接通过p来访问struct stu结构体当中的id的。但是这样做旧失去了其通用性，要知道内核当中链表的组织形式可是list_head。现在要如何才能够通过r访问的id呢？

我们将宏container_of分开成两部分来看。

1
const typeof( ((type *)0)->member ) *__mptr = (ptr);

这里的typeof也是GNU C所拓展的。Typeof(x) 就是返回x的数据类型。我们先从最里面的括号开始看起吧，

(type *)0先将0转化成type 类型的指针，此时地址为0x0。然后再引用member成员，即就是:((type *)0)->member 然后再加上typeof() 不就是返回member的数据类型么。再加上前面的const 后面的 * __mptr 。这是个什么意思？

我们来个一个假设。假设member返回的数据类型是int。那么是不是就成了const int * __mptr = (ptr)?现在是不是明白了？typeof( ((type *)0)->member ) 这个东西，就是为了要得到member的数据类型。

总结一下：这个就是为了定义一个member类型的指针，并且指向ptr(list_head类型)

1
(type *)( (char *)__mptr - offsetof(type,member) );

（char *）__mptr 将__mptr强制转化成char *类型，为什么转化成char* ，就是要获得__mptr指针的地址。而不是其他的类型呢？先来看offsetof这个宏吧。它被定义在/include/linux/stddef.h当中。

1
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

不着急，还是先从最里面的括号开始看起。(TYPE *)0)->MEMBER 这不是为了获取member么。在加个& 获得他的地址、在加上(size_t) 强制转化成size_t 类型(其实也就是 unsigned int)。现在该注意了。刚才是不是说得到了type类型的指针的地址是0x0 ？ 你这里又得到了type类型指针成员member的地址。这个就是member的偏移地址吧！

再将这两个合并起来看。将获得的__mptr指针的地址 ，减去member成员在其中的偏移量。就是member的地址了吧！！O(∩_∩)O~

还有一个重要的问题？就是为什么要转化成char*，而不是其他的*？char类型的数据不论在什么类型的机器上，存储方式应该只是占了一个字节？因为它的实质是ascii码。这样的话，就好理解了，对char*减一 那就是实实在在的减一个字节；但是你要是对int*减一会实实在在的减多少？是不是4？（32位机器下）。这样一来，你怎么知道他的真实地址？
可以根据下图来理解：

图五

下面再来看看和这个宏很类似的宏

1
2
#define list_first_entry(ptr, type, member) \
   list_entry((ptr)->next, type, member)

和刚才唯一的区别就是ptr所代表的意思不同了，list_entry这个宏是用来获得链表的入口的。但是这里却是为了得到链表的第一个元素。详细的不再赘述。

下来看看这个遍历宏：

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

这里prefetch其实还是一个宏，其作用是预取。作用是使得的便利更加快速、高效、安全，我们这里基本上可以不用考虑这些问题，故，使用的时候可以将该宏去掉。

再来看看向前遍历的宏：

1
2
3
#define list_for_each_prev(pos, head) \
   for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
          pos = pos->prev)

跟上面遍历宏一样，其本质还是for循环，结束条件是遍历到了头！

具体的双向循环链表就分析到这里，后面的还有一大堆的遍历宏，只不过也就是上面这几种宏的组合使用罢了；更有甚者，考虑了很多的安全性问题；比如：多线程、并发访问一链表等等，这些应该说在用户级别的程序不大会出现这类问题，我们大可不必注意；但是考虑到在OS当中，有很多是用到了链表；比如：在进程调度的时候，就绪队列、等等。在这个时候就不仅仅需要考虑链表的实现问题了，而且还得考虑安全问题。