免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 1227 | 回复: 11

[内核入门] list.h [复制链接]

论坛徽章:
13
15-16赛季CBA联赛之八一
日期:2016-07-08 21:00:1415-16赛季CBA联赛之同曦
日期:2017-02-15 14:26:1515-16赛季CBA联赛之佛山
日期:2017-02-20 14:19:2615-16赛季CBA联赛之青岛
日期:2017-05-07 16:49:1115-16赛季CBA联赛之广夏
日期:2017-07-30 09:13:1215-16赛季CBA联赛之广东
日期:2018-07-05 22:34:3615-16赛季CBA联赛之江苏
日期:2018-09-03 12:10:2115-16赛季CBA联赛之上海
日期:2018-09-25 03:49:2215-16赛季CBA联赛之广东
日期:2018-09-25 04:09:12
发表于 2016-09-16 11:39 |显示全部楼层
本帖最后由 _nosay 于 2016-09-16 12:13 编辑

  • 传统生成双向链表方法
  1. /* 这段程序用于演示由n_list结构构成一个双向链表的过程 */
  2. #include <stdio.h>
  3. #include <stdlib.h>

  4. struct n_list {
  5.     int n;
  6.     struct n_list *prev;
  7.     struct n_list *next;
  8. } head = { 100, &head, &head };

  9. void n_list_destroy()
  10. {
  11.     while (head.next != &head)
  12.     {
  13.         struct n_list *nl = head.next;
  14.         
  15.         head.next = nl->next;
  16.         free(nl);
  17.     }
  18. }

  19. int n_list_build()
  20. {
  21.     int i = 0;
  22.    
  23.     for (; i < 10; i ++)
  24.     {
  25.         struct n_list *first = &head;
  26.         struct n_list *last  = head.prev;
  27.         struct n_list *nl;
  28.         
  29.         if ((nl = malloc(sizeof(struct n_list))) == NULL) {
  30.             printf("%s(), %d: malloc failed\n", __FUNCTION__, __LINE__);
  31.             goto err;
  32.         }
  33.         
  34.         nl->n = i;
  35.         
  36.         // 将新结点nl加到最后,即last与first之间
  37.         first->prev = nl;
  38.         nl->next = first;
  39.         nl->prev = last;
  40.         last->next = nl;
  41.     }
  42.    
  43.     return 0;
  44. err:
  45.     n_list_destroy();
  46.     return -1;
  47. }

  48. void n_list_print()
  49. {
  50.     struct n_list *nl = &head;
  51.    
  52.     do {
  53.         printf("%d\n", nl->n);
  54.         nl = nl->next;
  55.     } while (nl != &head);
  56. }

  57. int main()
  58. {
  59.     if (n_list_build() < 0)
  60.         return -1;
  61.    
  62.     n_list_print();
  63.     n_list_destroy();
  64.    
  65.     return 0;
  66. }
复制代码

    通过这段代码看,要想将一个结构按照双向链表连接起来,比如“struct { int n; };”,可以先向结构中加入prev、next成员,分别用于指向前、后两个结点,并编写相应链表操作的函数。


  • list.h
    Linux内核中使用的list.h,是将双向链表的结构以及操作都抽象出来了:
    list.png

    另外,将list_for_each(pos, head)宏函数改进一下:
  1. #define list_for_each_safe(pos, n, head) \
  2.     for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)
复制代码

    上述举的例子,就可以写成这样(直接用接口即可,不需要自己再去想各种情况下指针该如何指向):
  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. #include "list.h"

  4. struct n_list {
  5.     int n;
  6.     struct list_head list;  // 添加list_head结构成员
  7. };

  8. struct list_head head = LIST_HEAD_INIT(head);

  9. void n_list_destroy()
  10. {
  11.     struct list_head *pos, *n;
  12.    
  13.     list_for_each(pos, n, &head) {  // 直接使用接口遍历
  14.         struct n_list *nl = container_of(pos, struct n_list, list);
  15.         free(nl);
  16.     }
  17. }

  18. int n_list_build()
  19. {
  20.     int i = 0;
  21.     struct n_list *nl;
  22.    
  23.     for (; i < 10; i ++)
  24.     {
  25.         if ((nl = malloc(sizeof(struct n_list))) == NULL) {
  26.             printf("%s(), %d: malloc failed\n", __FUNCTION__, __LINE__);
  27.             goto err;
  28.         }
  29.         
  30.         nl->n = i;
  31.         list_add_tail(&nl->list, &head);  // 直接使用接口添加
  32.     }
  33.    
  34.     return 0;
  35. err:
  36.     n_list_destroy();
  37.     return -1;
  38. }

  39. void n_list_print()
  40. {
  41.     struct list_head *pos, *n;
  42.    
  43.     list_for_each(pos, n, &head) {        // 直接使用接口遍历
  44.         struct n_list *nl = container_of(pos, struct n_list, list);
  45.         printf("%d\n", nl->n);
  46.     }
  47. }

  48. int main()
  49. {
  50.     if (n_list_build() < 0)
  51.         return -1;
  52.    
  53.     n_list_print();
  54.     n_list_destroy();
  55.    
  56.     return 0;
  57. }
复制代码
   将双向链表从具体的结构中抽象出来,可以说非常精妙,可以对比这两段使用list_head前后的程序,最好动手写一些程序验证一下list.h里面的各个接口的功能,Linux内核中大量使用了list_head,所以把list.h搞熟悉,看内核代码也会轻松很多。


  • list_entry() ??
  1. #define list_entry(ptr, type, member) \
  2.     ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
复制代码

    这个宏函数比较让人震惊,所以解释一下。在上述的例子中,可以看到调用过一次container_of(pos, struct n_list, list),其实这个宏函数内部封装的就是list_entry(),经过宏替换后,变成这样:    ((struct n_list *)((char *)(pos)-(unsigned long)(&((struct n_list *)0)->list)))

    还是好复杂,所以一部分一部分的看:
    ((struct n_list *)((char *)(pos)-(unsigned long)(&((struct n_list *)0)->list)))
   list entry.png
    将0地址看作n_list结构所在的位置,list成员所在地址&((struct n_list *)0)->list,则为list相对于结构开始位置的偏移量。但奇怪的是,为什么这里访问空指针,不会出错?其实这里并没有访问list,只是取了list的地址(比如“nl->n”,先是取n地址“&nl->n”,然后再访问n内容“*(&nl->n)”),所以并不会段错误。

    最后,由于pos是list_head结构的真实地址,往前减掉与结构起始位置的距离,于是就通过list成员的位置,得到了整个结构的位置,并将类型也转换成结构的类型,就OK了。


  • Linux内核关于C语言的其它说明
    Linux内核使用的是GNU C,相对于ANSI C,多了一些扩展特性,等读代码遇到时再说明,但要注意的是GNU C一直在扩展,所以新版本内核,可能出现用老版本gcc编译不过的情况,那就需要升级gcc再编译。
    另外还有一些“do {} while(0)”等技巧,没有什么理解难度,所以也不一一列举。



评分

参与人数 1可用积分 +2 收起 理由
Godbach + 2 赞一个!

查看全部评分

论坛徽章:
5
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:53:172015亚冠之水原三星
日期:2015-06-02 16:34:202015年亚冠纪念徽章
日期:2015-10-19 18:13:37程序设计版块每日发帖之星
日期:2015-11-08 06:20:00
发表于 2016-09-16 13:58 |显示全部楼层
彩色代码图片那个,编辑器是什么

论坛徽章:
13
15-16赛季CBA联赛之八一
日期:2016-07-08 21:00:1415-16赛季CBA联赛之同曦
日期:2017-02-15 14:26:1515-16赛季CBA联赛之佛山
日期:2017-02-20 14:19:2615-16赛季CBA联赛之青岛
日期:2017-05-07 16:49:1115-16赛季CBA联赛之广夏
日期:2017-07-30 09:13:1215-16赛季CBA联赛之广东
日期:2018-07-05 22:34:3615-16赛季CBA联赛之江苏
日期:2018-09-03 12:10:2115-16赛季CBA联赛之上海
日期:2018-09-25 03:49:2215-16赛季CBA联赛之广东
日期:2018-09-25 04:09:12
发表于 2016-09-16 14:52 |显示全部楼层
回复 2# xinglp

source insight

论坛徽章:
0
发表于 2016-10-03 20:54 |显示全部楼层
回复 1# _nosay

最近也在研究内核的通用链表的源码,有一个问题不太懂:假设我在定义
  1. struct n_list {
  2.     int n;
  3.     struct list_head *list;  // 添加list_head结构成员
  4. };
复制代码
注意,我把结构体里的list定义成指针变量了,主要问题在于list_entry函数,它要调用container_of(pos,type,member),因此我将container_of的定义适当改了下
  1. #define container_of(ptr, type, member) ({const typeof(((type *)0)->member) __mptr = (ptr); \
  2.                                          (type *)((char *)__mptr - offsetof(type,member));})
复制代码
这里我把__mptr定义成变量了,因为typeof调用后肯定知道此时struct n_list的list成员是指针变量,那么此时我觉得container_of应该可以正确获取宿主的类型,但实际上我调用list_entry进行遍历操作时,就会段错误。但我想不通哪里有问题(可以通过编译)


论坛徽章:
20
程序设计版块每日发帖之星
日期:2015-08-17 06:20:00程序设计版块每日发帖之星
日期:2016-07-16 06:20:00程序设计版块每日发帖之星
日期:2016-07-18 06:20:00每日论坛发贴之星
日期:2016-07-18 06:20:00黑曼巴
日期:2016-12-26 16:00:3215-16赛季CBA联赛之江苏
日期:2017-06-26 11:05:5615-16赛季CBA联赛之上海
日期:2017-07-21 18:12:5015-16赛季CBA联赛之青岛
日期:2017-09-04 17:32:0515-16赛季CBA联赛之吉林
日期:2018-03-26 10:02:16程序设计版块每日发帖之星
日期:2016-07-15 06:20:0015-16赛季CBA联赛之江苏
日期:2016-07-07 18:37:512015亚冠之萨济拖拉机
日期:2015-08-17 12:21:08
发表于 2016-10-04 19:07 |显示全部楼层
内嵌的list_head不能是指针。

论坛徽章:
13
15-16赛季CBA联赛之八一
日期:2016-07-08 21:00:1415-16赛季CBA联赛之同曦
日期:2017-02-15 14:26:1515-16赛季CBA联赛之佛山
日期:2017-02-20 14:19:2615-16赛季CBA联赛之青岛
日期:2017-05-07 16:49:1115-16赛季CBA联赛之广夏
日期:2017-07-30 09:13:1215-16赛季CBA联赛之广东
日期:2018-07-05 22:34:3615-16赛季CBA联赛之江苏
日期:2018-09-03 12:10:2115-16赛季CBA联赛之上海
日期:2018-09-25 03:49:2215-16赛季CBA联赛之广东
日期:2018-09-25 04:09:12
发表于 2016-10-07 07:27 |显示全部楼层
回复 4# 进无止进

const typeof(((type *)0)->member) __mptr = (ptr);
ptr应该传n_list结构中list成员的地址,如果传的是list指向的值就不对了,比如struct n_list nl,container_of(nl.list, struct n_list, list)是不对的,改成&nl.list试试。

论坛徽章:
13
15-16赛季CBA联赛之八一
日期:2016-07-08 21:00:1415-16赛季CBA联赛之同曦
日期:2017-02-15 14:26:1515-16赛季CBA联赛之佛山
日期:2017-02-20 14:19:2615-16赛季CBA联赛之青岛
日期:2017-05-07 16:49:1115-16赛季CBA联赛之广夏
日期:2017-07-30 09:13:1215-16赛季CBA联赛之广东
日期:2018-07-05 22:34:3615-16赛季CBA联赛之江苏
日期:2018-09-03 12:10:2115-16赛季CBA联赛之上海
日期:2018-09-25 03:49:2215-16赛季CBA联赛之广东
日期:2018-09-25 04:09:12
发表于 2016-10-07 07:43 |显示全部楼层
回复 4# 进无止进

不是指针的话,就是直接把list_head“附”在结构里,否则只是list_head指针“附”在结构里,而list_head本身在malloc(struct list_head)的地方

论坛徽章:
0
发表于 2016-10-07 23:58 |显示全部楼层
回复 7# _nosay 不好意思,你说的我不是很懂,能不能再科普一下,还有一点请教:
假如我还是把内嵌的定义成指针,然后把container_of改成这样
  1. #define container_of(ptr, type, member) ({const typeof(((type *)0)->member)  *__mptr =& (ptr); \
  2.                                          (type *)((char *)__mptr - offsetof(type,member));})
复制代码

也就是取ptr得地址,这样前后都是二重指针,我觉得应该也可以完成container_of的作用啊


论坛徽章:
13
15-16赛季CBA联赛之八一
日期:2016-07-08 21:00:1415-16赛季CBA联赛之同曦
日期:2017-02-15 14:26:1515-16赛季CBA联赛之佛山
日期:2017-02-20 14:19:2615-16赛季CBA联赛之青岛
日期:2017-05-07 16:49:1115-16赛季CBA联赛之广夏
日期:2017-07-30 09:13:1215-16赛季CBA联赛之广东
日期:2018-07-05 22:34:3615-16赛季CBA联赛之江苏
日期:2018-09-03 12:10:2115-16赛季CBA联赛之上海
日期:2018-09-25 03:49:2215-16赛季CBA联赛之广东
日期:2018-09-25 04:09:12
发表于 2016-10-08 04:14 |显示全部楼层
回复 8# 进无止进

你把代码发来,[size=25.6822px]container_of()一般用在list_for_each(){}里面,第一个传的是局部变量,取地址已经不是你结构里面那个list的地址了。

论坛徽章:
0
发表于 2016-10-12 14:01 |显示全部楼层
回复 8# 进无止进

改成指针是毫无意义的,我以前就尝试过。因为contianer_of是基于相对偏移。如果改成指针的话,那么你的ptr必须是这个指针的二维指针,也就是这个指针变量本身的地址,而不是它所指向的地址
我们一般使用指针都是关注它所指向的地址。


您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会

【架构革新 高效可控】2020年12月21日-23日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP