Linux学习------分析list.h 之 函数部分
分类： Linux C 2010-08-31 09:57 1073人阅读 评论(3) 收藏 举报
在Linux中，最常见也是最经典的数据结构就是其中的双向链表，而对双向链表的各种操作都存储在list.h头文件中，最近仔细看了一下这个头文件，把我对它的理解记录下来，算是一个学习笔记吧。我看的是2.6.35.4版本的内核源代码，list.h在include/linux下存放，相对于一些其他的内核原文件来说，list.h算是比较小的了，而且只有700多行，主要是因为这个文件算是一个纯C文件，就是它是单纯的用C语言来对双向链表进行操作，看起来也比较容易。
在list.h中，定义了如下一个数据结构：
1. struct list_head {
2. struct list_head *next, *prev;
3. };
struct list_head {struct list_head *next, *prev;}; 这是一个双向链表，但是不存储数据，只是做一个相互连接的作用，定义了一个指向后一元素的指针和指向前一元素的指针。定义这样一个没有存储数据的数据结构，我觉得好处是可以广泛嵌套使用，把它当做一座桥，只是连接，然后再配合上其他变量来存储数据，一起形成一个结构体，这样后面对其操作就可以通用了，不必换一种数据就换一堆操作了。 对于双向链表的初始化，list.h中给出了两个方法，一个是宏定义的方法，另一个是函数的方法： 1. #define LIST_HEAD_INIT(name) { &(name), &(name) } 2. #define LIST_HEAD(name) / 3. struct list_head name = LIST_HEAD_INIT(name) 4. static inline void INIT_LIST_HEAD(struct list_head *list)
5. { 6. list->next = list; 7. list->prev = list; 8. } #define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) /struct list_head name = LIST_HEAD_INIT(namestatic inline void INIT_LIST_HEAD(struct list_head *list{list->next = list;list->prev = list;} 前两个宏定义要结合起来看，第二个宏定义是一个结构体的赋初值，再看第一个宏定义，就是说把name这个list_head类型的结构体的第一个元素赋值为name的地址，第二个元素也赋值为name的地址，再结合上面的结构体的定义，就是说把name->next和name->prev都赋值为name自己，也就是指向自身，这样就是初始化好了一个双向链表的结点。而第二种用函数的方法就是直接把我上面的分析转换成代码的形式了，意思和功能是一样的。 对于链表的操作不过是“增删改查”几种，双向链表也不例外。
一、在进行增加操作时，list.h中的代码如下：
1. static inline void __list_add(struct list_head *new,
2. struct list_head *prev,
3. struct list_head *next)
4. {
5. next->prev = new;
6. new->next = next;
7. new->prev = prev;
8. prev->next = new;
9. }
10. static inline void list_add(struct list_head *new, struct list_head *head)
11. {
12. __list_add(new, head, head->next);
13. } 14. static inline void list_add_tail(struct list_head *new, struct list_head *head) 15. { 16. __list_add(new, head->prev, head); 17. } { 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_add(new, head, head->next);}static inline void list_add_tail(struct list_head *new, st{__list_add(new, head->prev, head);} 总共定义了三个函数，大致一看，后两个是调用了第一个函数。对于第一个函数，首先分析它的参数是什么，第一个参数new，是一个类型为list_head的指针，指向要增加的结点，而prev和next也都是list_head类型的指针，顾名思义，就是指向增加的位置的前面和后面的结点，在函数内部，首先是把要增加位置的后面的结点的prev元素赋值为new，再把new的next元素指向后面结点，意思是先把后面的结点与新增结点相连；然后是把new的prev元素指向前面结点，再把前面结点的next赋值为new，意思是把前
面的结点与新增结点相连。对于第二个函数，分析其调用__list_add()是的实参，第二个为head，第三个为head->next，也就是说要把新增结点加到head之后，head->next之前，也就是增加一个结点到头结点后，类似于单链表的头插法。对于第三个函数，它调用__list_add()时，第二个参数为head->prev，第三个为head，就是要把新增结点加到head->prev之后，head之前，对于双向链表来说，head->prev正是链表的最后一个结点，所以这个函数的功能就是在链表的最后增加新结点，类似于单链表的尾插法。
二、对于删除操作，list.h的代码如下：
1. static inline void __list_del(struct list_head * prev, struct list_head * next)
2. {
3. next->prev = prev;
4. prev->next = next;
5. }
6. static inline void list_del(struct list_head *entry)
7. {
8. __list_del(entry->prev, entry->next);
9. entry->next = LIST_POISON1;
10. entry->prev = LIST_POISON2; 11. } 12. static inline void list_del_init(struct list_head *entry) 13. { 14. __list_del(entry->prev, entry->next); 15. INIT_LIST_HEAD(entry); 16. } static inline void __list_del(struct list_head * prev, stru{next->prev = prev;prev->next = next;}static inline void list_del(struct list_head *entry){__list_del(entry->prev, entry->next);entry->next = LIST_POISON1;entry->prev = LIST_POISON2;}static inline void list_del_init(struct list_head *entry){__list_del(entry->prev, entry->next);INIT_LIST_HEAD(entry); 同样也是定义了三个函数，而后两个函数也是调用了第一个函数。先看第一个函数，简单地说一下，就是把要删除的这个结点后面的结点的prev指向要删除结点的前面的结点，在把要删除的这个结点的前面的结点的next指向要删除的后面的那个结点，说的比较复杂，
但是理解起来应该不难，简而言之，就是把要删除的这个的前后相连，就把它自己分离出来了。但是光把前后结点相连还没有彻底完成删除，还要对待删除结点进行一些操作，后面的两个函数的不同点就是处理这个待删除节点的操作时不一样的。先解释第三个函数的操作，INIT_LIST_HEAD（entry），就是前面说到过的那个初始化函数，作用是把entry的prev和next都指向它自身，就不会让它们乱指，也是一种安全的删除方式。再看看第二个函数它是分别将next和prev赋值为LIST_POISON1和LIST_POISON2，这两个是宏定义的常量，在include/linux/poison.h中定义的，源代码如下：
1. /*
2. * These are non-NULL pointers that will result in page faults
3. * under normal circumstances, used to verify that nobody uses
4. * non-initialized list entries.
5. */
6. #define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
7. #define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
/* * These are non-NULL pointers that will result in page * under normal circumstances, used to verify that nob * non-initialized list entries. */#define LIST_POISON1 ((void *) 0x00100100 + POISON#define LIST_POISON2 ((void *) 0x00200200 + POISON 大概意思就是一个常人基本不能用的一个地址，就相当于把prev和next屏蔽掉，不能通过它在切入到链表中，但是它属于不安全的方式。 三、对于修改操作，在list.h中是用替换的方式来的，源代码如下： 1. static inline void list_replace(struct list_head *old, 2. struct list_head *new) 3. { 4. new->next = old->next; 5. new->next->prev = new; 6. new->prev = old->prev;
7. new->prev->next = new; 8. } 9. static inline void list_replace_init(struct list_head *old, 10. struct list_head *new) 11. { 12. list_replace(old, new); 13. INIT_LIST_HEAD(old); 14. } 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;}static inline void list_replace_init(struct list_head *old,struct list_head *n{list_replace(old, new);INIT_LIST_HEAD(old);} 修改比较简单，就是把要修改的那个结点的prev和next赋值给新的结点，然后把原
来前后的结点对应的next和prev再指向新结点，这就是第一个函数的作用，就是用来修改指向的，而对于修改过的那个结点要做类似于删除的操作，在第二个函数中体现，与上文提到的删除一样，使用INIT_LIST_HEAD（）函数，把原来的结点的prev和next都指向自己，安全删除。
四、对于移动操作，在list.h中的定义如下：
1. static inline void list_move(struct list_head *list, struct list_head *head)
2. {
3. __list_del(list->prev, list->next);
4. list_add(list, head);
5. }
6. static inline void list_move_tail(struct list_head *list,
7. struct list_head *head)
8. {
9. __list_del(list->prev, list->next);
10. list_add_tail(list, head);
11. } static inline void list_move(struct list_head *list, struct{__list_del(list->prev, list->next);list_add(list, head);}static inline void list_move_tail(struct list_head *list, struct list_head *head){__list_del(list->prev, list->next);list_add_tail(list, head);} 定义了两个函数，但是函数体中的东西都是很眼熟的，我就不多说了，宏观上说一下，第一个函数是把一个结点移动到头结点之后，使用的方法就是把待移动结点从原来位置分离出来（使用__list_del函数），然后在把它增加到头结点后（使用list_add函数）；第二个函数是把一个结点移动到最后，使用的方法也是先把待移动结点从原来位置分离出来（使用__list_del函数），然后在把它增加到最后（使用list_add_tail函数）。这个地方就体现出函数功能的独立化的好处了，当然这只是一部分。 五、状态检测。类似于用栈的时候的判栈空栈满，当然，在链表中是不会判断满的。list.h的源代码如下： 1. static inline int list_is_last(const struct list_head *list, 2. const struct list_head *head) 3. {
4. return list->next == head;
5. }
6. static inline int list_empty(const struct list_head *head)
7. {
8. return head->next == head;
9. }
10. static inline int list_empty_careful(const struct list_head *head)
11. {
12. struct list_head *next = head->next;
13. return (next == head) && (next == head->prev);
14. }
15. static inline int list_is_singular(const struct list_head *head)
16. {
17. return !list_empty(head) && (head->next == head->prev); 18. } static inline int list_is_last(const struct list_head *list,const struct list_head *he{return list->next == head;}static inline int list_empty(const struct list_head *head{return head->next == head;}static inline int list_empty_careful(const struct list_hea{struct list_head *next = head->next;return (next == head) && (next == head->prev);}static inline int list_is_singular(const struct list_head * 看名字就基本可以知道了，第一个函数是判断是否为链表尾部，使用的方法是判断当前结点的next是否指向头结点，因为是双向链表，很容易理解。第二个函数是判断链表是否为空，使用的方法同样容易理解，就是判断头结点的next是否是指向自身的。而第三个函数比第二个函数多一个“careful”，就是因为它还要检测prev是否也是指向自身。最后一个是判断链表是否为单个结点，方法是判断头结点的next和prev是否指向同一个地方，当然它还不能是指向自己，也就是不为空。 六、旋转操作，不知道用来干嘛，但是通过注释可以知道是把list向左转一下，源代码如下： 1. static inline void list_rotate_left(struct list_head *head) 2. {
3. struct list_head *first; 4. if (!list_empty(head)) { 5. first = head->next; 6. list_move_tail(first, head); 7. } 8. } static inline void list_rotate_left(struct list_head *head){struct list_head *first;if (!list_empty(head)) {first = head->next;list_move_tail(first, head);}} 就是一个非空链表的头结点的next移到它的前面，也就是链表的最后，使用了list_move_tail函数，就像一个钟，把固定指针的那个点想象成头结点，这个函数就是把指针从指向3的地方，逆时针（也可以是顺时针）转动，指向了9的地方。 七、切分链表，就是从规定的地方把链表一分为二，在list.h中对应的源代码如下：
1. static inline void __list_cut_position(struct list_head *list,
2. struct list_head *head, struct list_head *entry)
3. {
4. struct list_head *new_first = entry->next;
5. list->next = head->next;
6. list->next->prev = list;
7. list->prev = entry;
8. entry->next = list;
9. head->next = new_first;
10. new_first->prev = head;
11. }
12. static inline void list_cut_position(struct list_head *list,
13. struct list_head *head, struct list_head *entry)
14. {
15. if (list_empty(head))
16. return;
17. if (list_is_singular(head) &&
18. (head->next != entry && head != entry))
19. return;
20. if (entry == head)
21. INIT_LIST_HEAD(list);
22. else
23. __list_cut_position(list, head, entry);
24. }
static inline void __list_cut_position(struct list_head *lstruct list_head *head, struct list_head *{struct list_head *new_first = entry->next;list->next = head->next;list->next->prev = list;list->prev = entry;entry->next = list;head->next = new_first;new_first->prev = head;}static inline void list_cut_position(struct list_head *liststruct list_head *head, struct list_head *{if (list_empty(head)) 和上文一样，还是着重分析第一个函数，先从参数下手，list和head分别为切分链表后形成的两个双向链表的头结点，而entry是指要切分的位置，再看函数体，细节我就不做过多说明了，对链表的操作只要细心就好了，大概就是先找到要切分的位置就是entry，把这个位置记录下来，然后把它之前包括它的一段作为一个双向链表，这个双向链表的头结点为list，把它们首尾相连（首为list，尾为entry）；再把head当做后面的一段链表的头结点，与entry后的第一个结点相连，这个节点就作为后面这段链表的第二个结点，因为此时的head还是与最开始的整体链表的尾部是连接好的，所以不用在做首尾相连的工作了，这也是为什么要用head当后半部分链表的头结点了，就是因为会少做一步操作了。对于第二个函数，就是加上了一些切分链表的条件，首先不能为空，而且如果是单个结点，还需要保证切分点不是头结点也不是头结点后的结点，排除以上情况，如果切分点就是头结点，那么就是说产生两个链表，前面的链表是一个以list为头结点的空链表，而后面的是以head为头结点的整条链表，其实就是相当于初始化定义一个list头结点就可以了。剩下的就是可以正常切分的切分操作了，就可以使用第一个函数了。 八、合并链表操作，就是把一个双向链表插到另一个双向链表中，在list.h中的源代码如下：
1. static inline void __list_splice(const struct list_head *list,
2. struct list_head *prev,
3. struct list_head *next)
4. {
5. struct list_head *first = list->next;
6. struct list_head *last = list->prev;
7. first->prev = prev;
8. prev->next = first;
9. last->next = next;
10. next->prev = last;
11. }
static inline void __list_splice(const struct list_head *l 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;} 首先列举出来的这段代码和上面的每一个功能的第一个函数一样，都是被后面的函数调用的。先看它的参数，list是一个头结点，就是要把它后面的那一串链表插入到其他链表中，prev和next就是链表要插入的位置的前后结点，在函数体中，先用first和last记录这串要插入的链表的头和尾，把first和要插入位置的前面prev相连，把last和要插入位置的后面next相连，就像插入一个大结点一样把链表插入到规定位置。 后面调用这个函数的代码如下： 1. static inline void list_splice(const struct list_head *list, 2. struct list_head *head) 3. { 4. if (!list_empty(list)) 5. __list_splice(list, head, head->next);
6. } 7. static inline void list_splice_tail(struct list_head *list, 8. struct list_head *head) 9. { 10. if (!list_empty(list)) 11. __list_splice(list, head->prev, head); 12. } static inline void list_splice(const struct list_head *liststruct list_head *head){if (!list_empty(list))__list_splice(list, head, head->next);}static inline void list_splice_tail(struct list_head *list,struct list_head *head){if (!list_empty(list))__list_splice(list, head->prev, head);} 可以观察两个函数体中调用上一函数的参数，第一个函数是把链表插入到head之后head->next之前，就是说把链表插到头结点后，类似于头插法，第二个函数是把链表插入到head->prev之后，head之前，就是说把链表插到链表的最后，类似于尾插法。当
然，在插入链表之前，要保证待插的那个链表不是空链表。
这时就会衍生出一个问题，对于把新链表“带来”的那个list头结点该怎么办，源代码作了如下操作：
1. static inline void list_splice_init(struct list_head *list,
2. struct list_head *head)
3. {
4. if (!list_empty(list)) {
5. __list_splice(list, head, head->next);
6. INIT_LIST_HEAD(list);
7. }
8. }
9. static inline void list_splice_tail_init(struct list_head *list,
10. struct list_head *head)
11. {
12. if (!list_empty(list)) { 13. __list_splice(list, head->prev, head); 14. INIT_LIST_HEAD(list); 15. } 16. } static inline void list_splice_init(struct list_head *list, struct list_head *head){if (!list_empty(list)) {__list_splice(list, head, head->next);INIT_LIST_HEAD(list);}}static inline void list_splice_tail_init(struct list_head *l struct list_head *{if (!list_empty(list)) {__list_splice(list, head->prev, head);INIT_LIST_HEAD(list);} 看函数名就知道了，就是多了一步init，就是利用INIT_LIST_HEAD函数，把list“释放”了。 至此，前半部分的通过函数定义的方式定义出了一些对链表的操作已经介绍完了，后面还有相当一部分是通过宏定义的方式定义的，堪称短小精干。当然（好像说了好多“当然”），通过分析前面的这部分，也能深深体会到内核程序的巧妙之处，每个函数都有自己独立的分工，达到很高的可移植性，对于类似的操作，可以通过调用已经定义好的函数来
实现，这是我们应该努力去学习的毕竟源代码也是人写的，不会难到一个字不懂得，只要静下心来，慢慢看，慢慢体会，就会了解其中奥妙，再加之自己的实践和分析，变成自己的东西，就会有很多的收获。
结束语还是老话，我也是刚开始学习Linux内核的，以上都是自己通过查资料阅读源代码得到的理论，可能有一些会与事实不符，有不同的见解大家可以提出来，不要喷就好了。。。
因篇幅问题不能全部显示，请点此查看更多更全内容