首页 > 代码库 > 【内核数据结构】 内核链表分析

【内核数据结构】 内核链表分析

一、简介:


        Linux中的链表使用两个指针,可以方便的构成双向链表,实际上,通常它都组织成双向循环链表,不同于数据结构书上的链表,这里的节点只有链表指针,没有链表的数据,下边我将对内核中使用的 include/linux/list.h 进行函数说明和生动的图形解释。


二、函数:



我们先来看看

1. 链表数据结构 list_head 的定义:


[cpp] view plain copy
 print?技术分享技术分享
  1. struct list_head {  
  2.     struct list_head *next, *prev;  
  3. };  
【1】只有前后节点指针,没有数据

2. 声明和初始化:有两种方法


①声明的时候初始化一个链表 LIST_HEAD 宏

[cpp] view plain copy
 print?技术分享技术分享
  1. #define LIST_HEAD_INIT(name) { &(name), &(name) } // 链表的pre和next指针都指向了节点自己的首地址  
  2.   
  3. #define LIST_HEAD(name) \  
  4.     struct list_head name = LIST_HEAD_INIT(name)  
②运行时初始化链表 INIT_LIST_HEAD 函数

[cpp] view plain copy
 print?技术分享技术分享
  1. static inline void INIT_LIST_HEAD(struct list_head *list)  
  2. {  
  3.     list->next = list;  
  4.     list->prev = list;  
  5. }  

注意:

此处说的声明的时候简单的理解为不在函数内部,而运行时指的就是在函数内部了

图形:

技术分享


3. 插入/删除/合并


a) 插入


对链表的插入操作有两种:

在表头插入 list_add函数 和

在表尾插入 list_add_tail函数

[cpp] view plain copy
 print?技术分享技术分享
  1. static inline void list_add(struct list_head *newstruct list_head *head) // new:要添加的新的链表的首地址,head:链表的中的位置  
  2. {  
  3.     __list_add(new, head, head->next);  
  4. }  
  5. static inline void list_add_tail(struct list_head *newstruct list_head *head)  
  6. {  
  7.     __list_add(new, head->prev, head);  
  8. }  
可以看到他们调用了相同的 __list_add 函数:

[cpp] view plain copy
 print?技术分享技术分享
  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. }  
【1】对于这个函数,他是将list_add和list_add_tail的共性的部分抽离了出来,给我们分析很大的障碍,我们只分析 list_add 和 list_add_tail 函数


图形:

  • list_add 部分:

技术分享

技术分享

网络上的一张图更全面的展示了在使用中的链表的结构:

技术分享


  • list_add_tail 部分:

技术分享

技术分享

画图总结:

【1】上边图形的画法中,要前两步划在外边沿

【2】对list链表的头和尾的快速记忆的方法,我们可以看待内核中的链表为 向右行驶的贪吃蛇


b) 删除


对链表的删除操作函数有两种:

list_del函数

list_del_init函数

[cpp] view plain copy
 print?技术分享技术分享
  1. static inline void list_del(struct list_head *entry) // entry:要删除的链表的首地址  
  2. {  
  3.     __list_del(entry->prev, entry->next); // 这不就是 __list_del_entry(entry) 吗!!  
  4.     entry->next = LIST_POISON1;  
  5.     entry->prev = LIST_POISON2;  
  6. }  
  7. static inline void list_del_init(struct list_head *entry)  
  8. {  
  9.     __list_del_entry(entry);  
  10.     INIT_LIST_HEAD(entry); // 运行中初始化链表节点  
  11. }  
  12. static inline void __list_del_entry(struct list_head *entry)  
  13. {  
  14.     __list_del(entry->prev, entry->next);  
  15. }  
【1】list_del函数中entry的next和prev指针指向了LIST_POISON1和LIST_POISON2位置,对他们进行访问都将引起页故障,保护不在链表中的节点项不可访问

他们调用了相同的 __list_del 函数:

[cpp] view plain copy
 print?技术分享技术分享
  1. static inline void __list_del(struct list_head * prev, struct list_head * next)  
  2. {  
  3.     next->prev = prev;  
  4.     prev->next = next;  
  5. }  

图形:

我们来删除有3个元素的链表的中间的一个:list_del(&new)

技术分享

list_del_init 函数不再画图,唯一的不同是把删除下来的图的next和prev指针指向了自己的首地址


c) 替换


对链表的替换操作有两个:

list_replace函数

list_replace_init函数

[cpp] view plain copy
 print?技术分享技术分享
  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.   
  10. static inline void list_replace_init(struct list_head *old,  
  11.                     struct list_head *new)  
  12. {  
  13.     list_replace(old, new);  
  14.     INIT_LIST_HEAD(old);  
  15. }  
图形:

技术分享

list_replace_init函数的图形此处也不再画


d) 搬移


搬移的含义是将原本属于一个链表的节点移动到另一个链表的操作,有两个函数:

list_move函数

list_move_tail函数

[cpp] view plain copy
 print?技术分享技术分享
  1. /** 
  2.  * list_move - 把从一个链表上删除的节点添加到另外的一个链表的头部 
  3.  * @list: 我们要移动的节点 
  4.  * @head: 要移动到的另外的一个链表头 
  5.  */  
  6. static inline void list_move(struct list_head *list, struct list_head *head)  
  7. {  
  8.     __list_del_entry(list);  
  9.     list_add(list, head);  
  10. }  
  11.   
  12. /** 
  13.  * list_move_tail - 添加到另外的一个链表的尾部 
  14.  * @list: the entry to move 
  15.  * @head: the head that will follow our entry 
  16.  */  
  17. static inline void list_move_tail(struct list_head *list,  
  18.                   struct list_head *head)  
  19. {  
  20.     __list_del_entry(list);  
  21.     list_add_tail(list, head);  
  22. }  

图形:


技术分享


e) 合并


合并在这里的意思就是合并了,是将两个独立的链表合并成为一个链表,合并的时候根据合并的位置的不同可以分为:

合并到头部的 list_splice函数

合并到尾部的 list_splice_tail函数:(这两个函数有推荐使用的函数)

[cpp] view plain copy
 print?技术分享技术分享
  1. /** 
  2.  * list_splice - join two lists, this is designed for stacks 
  3.  * @list: the new list to add. 
  4.  * @head: the place to add it in the first list. 
  5.  */  
  6. static inline void list_splice(const struct list_head *list,  
  7.                 struct list_head *head)  
  8. {  
  9.     if (!list_empty(list))  
  10.         __list_splice(list, head, head->next);  
  11. }  
  12. /** 
  13.  * list_splice_tail - join two lists, each list being a queue 
  14.  * @list: the new list to add. 
  15.  * @head: the place to add it in the first list. 
  16.  */  
  17. static inline void list_splice_tail(struct list_head *list,  
  18.                 struct list_head *head)  
  19. {  
  20.     if (!list_empty(list))  
  21.         __list_splice(list, head->prev, head);  
  22. }  
  23. static inline void list_splice_init(struct list_head *list, // 推荐使用,防止混乱  
  24.                     struct list_head *head)  
  25. {  
  26.     if (!list_empty(list)) {  
  27.         __list_splice(list, head, head->next);  
  28.         INIT_LIST_HEAD(list);                   <--- 跟list_splice唯一的不同  
  29.     }  
  30. }  
  31. static inline void list_splice_tail_init(struct list_head *list, // 推荐使用,防止混乱  
  32.                      struct list_head *head)  
  33. {  
  34.     if (!list_empty(list)) {  
  35.         __list_splice(list, head->prev, head);  
  36.         INIT_LIST_HEAD(list);                   <--- 跟list_splice_tail_init唯一的不同  
  37.     }  
  38. }  
  39. static inline void __list_splice(const struct list_head *list,  
  40.                  struct list_head *prev,  
  41.                  struct list_head *next)  
  42. {  
  43.     struct list_head *first = list->next;  
  44.     struct list_head *last = list->prev;  
  45.   
  46.     first->prev = prev;  
  47.     prev->next = first;  
  48.   
  49.     last->next = next;  
  50.     next->prev = last;  
  51. }  

图形:

技术分享

这张图虽然画出来了,比起看程序,虽然好点,但是理解起来还是有很大的问题,此处就借鉴别人的一张图来说明这个list_splice函数实现了什么:


        链表合并list_splice(&list1,&list2) (此图片引自:http://www.ibm.com/developerworks/cn/linux/kernel/l-chain/)

技术分享

对于这张图的说明如下:

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


4. 找到链表中的数据


        前边提到的函数都是操作的链表节点的入口,但是对于我们真正有意义的是节点上的数据,链表的头上没有数据,其他的节点上都是带有数据的。如何从一个链表节点的入口得到节点的数据呢?要用到以下的函数:

list_entry函数

[cpp] view plain copy
 print?技术分享技术分享
  1. /** 
  2.  * list_entry - 获得含链表入口的结构体首地址 
  3.  * @ptr:    member的首地址 
  4.  * @type:   容器的类型 
  5.  * @member: 要得到他的容器的某个成员 
  6.  */  
  7. #define list_entry(ptr, type, member) \  
  8.     container_of(ptr, type, member)  
  9.   
  10. #define container_of(ptr, type, member) ({          \  
  11.     const typeof( ((type *)0)->member ) *__mptr = (ptr); \  
  12.     (type *)( (char *)__mptr - offsetof(type,member) );})  
  13.   
  14. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) // 将数据结构体放到0地址处,天然的结构体中成员的首地址就是成员在结构体中的偏移量  

一个简单的例子:

main.c

[cpp] view plain copy
 print?技术分享技术分享
  1. #include <stdio.h>  
  2. #include "list.h"  
  3.   
  4. LIST_HEAD(device_list);  
  5.   
  6. typedef struct device_struct  
  7. {  
  8.     unsigned char *devname;  
  9.     struct list_head entry;  
  10. } device_struct_s;  
  11.   
  12. int main(int argc, const char *argv[])  
  13. {  
  14.     device_struct_s led;  
  15.     device_struct_s *led2;  
  16.   
  17.     led.devname = "led";  
  18.   
  19.     /* 添加到链表的前边 */  
  20.     list_add(&led.entry, &device_list);  
  21.   
  22.     /* 得到含有链表节点的数据结构体的首地址 */  
  23.     led2 = list_entry(device_list.next, device_struct_s, entry);  
  24.   
  25.     printf("led2.devname = %s\n", led2->devname);  
  26.       
  27.     return 0;  
  28. }  
【1】list.h 你需要复制linux内核中的list.h头文件,并且把list_head的定义和其他需要包含进来的结构体或者宏包含进来,编译后执行的结果如下:

led2.devname = led


5. 遍历链表


对linux内核的遍历可以分为遍历链表和遍历链表中的结构体:

从头开始遍历链表,list_for_each宏,

从头开始遍历链表中的结构体,list_for_each_entry宏:

[cpp] view plain copy
 print?技术分享技术分享
  1. /** 
  2.  * list_for_each - 迭代/遍历 链表 
  3.  * @pos:    the &struct list_head to use as a loop cursor. 
  4.  * @head:   要遍历的链表头 
  5.  */  
  6. #define list_for_each(pos, head) \  
  7.     for (pos = (head)->next; pos != (head); pos = pos->next)  
  8.   
  9.   
  10. /** 
  11.  * list_for_each_entry  - 遍历含链表节点入口的结构体 
  12.  * @pos:    the type * to use as a loop cursor. 
  13.  * @head:   要遍历的链表头 
  14.  * @member: 结构体中链表入口的名字 
  15.  */  
  16. #define list_for_each_entry(pos, head, member)              \  
  17.     for (pos = list_entry((head)->next, typeof(*pos), member);   \  
  18.          &pos->member != (head);     \  
  19.          pos = list_entry(pos->member.next, typeof(*pos), member))  

一个简单的例子:

[cpp] view plain copy
 print?技术分享技术分享
  1. #include <stdio.h>  
  2. #include "list.h"  
  3.   
  4. LIST_HEAD(device_list);  
  5.   
  6. typedef struct device_struct  
  7. {  
  8.     unsigned char *devname;  
  9.     struct list_head entry;  
  10. } device_struct_s;  
  11.   
  12. int main(int argc, const char *argv[])  
  13. {  
  14.     device_struct_s led, gpio, beep, *tmp;  
  15.   
  16.     led.devname = "led";  
  17.     gpio.devname = "gpio";  
  18.     beep.devname = "beep";  
  19.   
  20.     /* 一个一个往链表的前边添加 */  
  21.     list_add(&led.entry, &device_list);  
  22.     list_add(&gpio.entry, &device_list);  
  23.     list_add(&beep.entry, &device_list);  
  24.   
  25.     /* 1. 遍历链表的入口的首地值 */  
  26.     struct list_head *i;  
  27.     list_for_each(i, &device_list)  
  28.     {  
  29.         tmp = list_entry(i, device_struct_s, entry);  
  30.         printf("tmp.devname = %s\n", tmp->devname);  
  31.     }  
  32.   
  33.     /* 2. 遍历含链表的入口的结构体的首地值 */  
  34.     device_struct_s *j;  
  35.     list_for_each_entry(j, &device_list, entry)  
  36.     {  
  37.         printf("j.devname = %s\n", j->devname);  
  38.     }  
  39.   
  40.     return 0;  
  41. }  
【1】list.h 你需要复制linux内核中的list.h头文件,并且把list_head的定义和其他需要包含进来的结构体或者宏包含进来,编译后执行的结果如下:

tmp.devname = beep
tmp.devname = gpio
tmp.devname = led
j.devname = beep
j.devname = gpio
j.devname = led


另外:

  1. linux内核的链表中提供了反向遍历链表的宏list_for_each_prev和list_for_each_entry_reverse,他们分别是list_for_each和list_for_each_entry的反方向的实现,使用方法完全一样。
  2. 如果遍历不是从链表头开始,而是从已知的某个节点pos开始,则要使用list_for_each_entry_continue宏(使用方法同list_for_each_entry宏)。
  3. 如果想实现如果pos有值则从pos开始遍历,如果没有则从链表的头开始遍历,为此,Linux专门提供了一个list_prepare_entry(pos,head,member)宏,将它的返回值作为list_for_each_entry_continue()的pos参数,就可以满足这一要求。

我们将list_for_each_prev和list_for_each_entry_reverse的代码和执行结果也写下来:

[cpp] view plain copy
 print?技术分享技术分享
  1. printf("list_for_each_prev()\n");  
  2. /* 3. 反向遍历链表的入口的首地值 */  
  3. struct list_head *k;  
  4. list_for_each_prev(k, &device_list)  
  5. {  
  6.     tmp = list_entry(k, device_struct_s, entry);  
  7.     printf("tmp.devname = %s\n", tmp->devname);  
  8. }  
  9.   
  10. printf("list_for_each_reverse()\n");  
  11. /* 4. 反向遍历含链表的入口的结构体的首地值 */  
  12. device_struct_s *g;  
  13. list_for_each_entry_reverse(g, &device_list, entry)  
  14. {  
  15.     printf("g.devname = %s\n", g->devname);  
  16. }  

【1】此部分是在上边的main.c中实现的

【2】结合上边代码整个的执行结果如下:

list_for_each()
tmp.devname =beep
tmp.devname =gpio
tmp.devname =led
list_for_each_entry()
j.devname = beep
j.devname = gpio
j.devname = led
list_for_each_prev()   <--- 可以看到遍历结果是从尾部遍历到头部
tmp.devname = led
tmp.devname = gpio
tmp.devname = beep
list_for_each_reverse()   <--- 可以看到遍历结果是从尾部遍历到头部
g.devname = led
g.devname = gpio
g.devname = beep


6. 安全性


只讲一点判断链表是不是为空:

list_empty宏

[cpp] view plain copy
 print?技术分享技术分享
  1. static inline int list_empty(const struct list_head *head)  
  2. {  
  3.     return head->next == head;  
  4. }  

【内核数据结构】 内核链表分析