Chinaunix首页 | 论坛 | 博客
  • 博客访问: 298947
  • 博文数量: 76
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 715
  • 用 户 组: 普通用户
  • 注册时间: 2015-05-20 20:38
文章分类
文章存档

2016年(20)

2015年(56)

分类: 嵌入式

2016-02-28 20:12:18


  1. linux内核中链表代码分析---list.h头文件分析(二)
  2. 16年2月28日16:59:55

  3. 分析完container_of()宏以后,继续分析list.h文件:
  4. (1)list_entry
  5. 它就是一个container_of宏,都是得到ptr所指地址的这个结构体的首地址
  6. #define list_entry(ptr, type, member) \
  7.     container_of(ptr, type, member)

  8. (2) list_first_entry
  9. #define list_first_entry(ptr, type, member) \
  10.     list_entry((ptr)->next, type, member)
  11. 这里的ptr是一个链表的头节点,这个宏就是取得这个链表第一元素的所指结构体的首地址。

  12. (3) list_for_each
  13. #define list_for_each(pos, head) \
  14.     for (pos = (head)->next; pos != (head); pos = pos->next)
  15. 它实际上就是一个for循环,从头到尾遍历链表,但是看代码发现,遍历链表需要一个head参数即可,这个pos参数好像没什么用啊。。。
  16. 然后就在内核中grep了一番,稍微总结出来一点:
  17. 这是一个for循环,我们通过这个for循环总得做点什么事情吧,以下面这个为例,
  18. 源文件在/driver/input/serio/hil_mlc.c中:
  19. static LIST_HEAD(hil_mlcs);
  20. static void hil_mlcs_process(unsigned long unused)
  21. {
  22.     struct list_head *tmp;

  23.     read_lock(&hil_mlcs_lock);
  24.     list_for_each(tmp, &hil_mlcs) {
  25.         struct hil_mlc *mlc = list_entry(tmp, hil_mlc, list);
  26.         ....
  27. }
  28. 可以看到,它通过这个list_for_each函数,将hil_mlcs链表中的每一个成员地址一一赋给了tmp变量,这样,在后面的语句中,就可以通过list_entry这个宏根据tmp变量和list链表头来找到包含他们的整个结构体hil_mlc的首地址,然后就可以对这个结构体里面其他的成员变量进行操作了~~~
  29. 这一块涉及到linux中,比如对于每一个子设备,都建立一个结构体,然后将这些子设备通过一个链表链接起来,操作的时候需要遍历链表中的每一项进行操作,所以就是这个函数存在的意义。
  30. 后面那个 __list_for_each和list_for_each相同,以前这两个函数是不同的,它有一个prefetch预取的操作,我们不再考虑。

  31. (4)list_for_each_prev
  32. #define list_for_each_prev(pos, head) \
  33.     for (pos = (head)->prev; pos != (head); pos = pos->prev)
  34. 与list_for_each相似,只是它是从尾到头遍历链表,将链表中的每一项都取出来操作。

  35. (5)list_for_each_safe
  36. #define list_for_each_safe(pos, n, head) \
  37.     for (pos = (head)->next, n = pos->next; pos != (head); \
  38.         pos = n, n = pos->next)
  39. 这个实际上就是一个for循环,从头到尾遍历链表。这里使用了n来记录pos的下一个,这样处理完一 个流程之后再赋给pos,避免了删除pos结点造成的问题。这个函数是 专门为删除结点是准备的。
  40. :list_for_each(pos, head)和list_for_each_safe(pos, n, head)都是从头至尾遍历链表的,但是对于前者 来说当操作中没有删除结点的时候使用,但是如果操作中有删除结点的操作的时候就使用后者,对于后面带safe的一般都是这个目的。

  41. (6) list_for_each_prev_safe
  42. #define list_for_each_prev_safe(pos, n, head) \
  43.     for (pos = (head)->prev, n = pos->prev; \
  44.      pos != (head); \
  45.      pos = n, n = pos->prev)
  46. 同理,这个函数与 list_for_each_prev相似。

  47. /* 注意上面的几个函数,他们的行参里面有pos与下面函数行参里面的pos不同,上面函数的操作都是pos = (head)->next等等的操作,所以pos是list_head类型的,下面函数的操作是pos = list_entry()等等的操作,所以他们是list_head结构体所嵌入的结构体的指针形式的,我们称之为宿主结构体。 */

  48. (7) list_for_each_entry
  49. #define list_for_each_entry(pos, head, member)                \
  50.     for (pos = list_entry((head)->next, typeof(*pos), member);    \
  51.      &pos->member != (head);     \
  52.      pos = list_entry(pos->member.next, typeof(*pos), member))
  53. 第一个参数为传入的遍历指针,指向宿主数据结构,第二个参数为链表头,为list_head结构,第三 个参数为list_head结构在宿主结构中的成员名。
  54. 这个函数是根据member成员遍历head链表(member成员一般都嵌入在宿主结构体中),并且将每个结构体的首地址赋值给pos,这样的话,我们就 可以在循环体里面通过pos来访问该宿主结构体变量的其他成员了。 下面用最近分析的V4L2里面的一段代码来举例说明,代码位于v4l2-device.c中:
  55. int v4l2_device_register_subdev_nodes(struct v4l2_device *v4l2_dev)
  56. {
  57.     struct video_device *vdev;
  58.     struct v4l2_subdev *sd;

  59.     list_for_each_entry(sd, &v4l2_dev->subdevs, list) {
  60.         if (!(sd->flags & V4L2_SUBDEV_FL_HAS_DEVNODE))
  61.             continue;
  62.     。。。。
  63. }
  64. 可以分析出来, v4l2_device结构体里面含有这个 subdevs链表头,sd是指向v4l2_subdev结构体的指针,list是一个list_head结构,在之前的代码中,肯定有操作已经将各个子设备结构体v4l2_subdev全部链接进 v4l2_device结构体里面的 subdevs链表里面,这时候需要做的就是从这个v4l2_device结构体里面的 subdevs链表里一一取出各个子设备结构体v4l2_subdev,然后操作它的各个成员变量。上述代码就是完成这个工作。

  65. (8) list_for_each_entry_reverse
  66. #define list_for_each_entry_reverse(pos, head, member)            \
  67.     for (pos = list_entry((head)->prev, typeof(*pos), member);    \
  68.      &pos->member != (head);     \
  69.      pos = list_entry(pos->member.prev, typeof(*pos), member))
  70. 与上面那个函数类似,反向遍历链表。

  71. (9) list_prepare_entry
  72. #define list_prepare_entry(pos, head, member) \
  73.     ((pos) ? : list_entry(head, typeof(*pos), member))
  74. 第一个参数为传入的遍历指针,指向宿主数据结构,第二个参数为链表头,为list_head结构,第三 个参数为list_head结构在宿主结构中的成员名。
  75. 这个函数的功能就是如果pos非空,那么pos的值就为其本身,如果pos为空,那么就从链表头强制扩展一
  76. 个虚pos指针,这个宏定义是为了在list_for_each_entry_continue()中使用做准备的。

  77. (10)list_for_each_entry_continue
  78. #define list_for_each_entry_continue(pos, head, member)         \
  79.     for (pos = list_entry(pos->member.next, typeof(*pos), member);    \
  80.      &pos->member != (head);    \
  81.      pos = list_entry(pos->member.next, typeof(*pos), member))
  82. 这个函数与list_for_each_entry很相似,但是肯定是不同的,它是从pos所在的宿主结构体的下一个开始遍历链表,并不是从链表的头部开始遍历,从它的名字可以看出来。主要的区别就是我标红的位置。

  83. (11)list_for_each_entry_continue_reverse
  84. #define list_for_each_entry_continue_reverse(pos, head, member)        \
  85.     for (pos = list_entry(pos->member.prev, typeof(*pos), member);    \
  86.      &pos->member != (head);    \
  87.      pos = list_entry(pos->member.prev, typeof(*pos), member))
  88. 与上一个函数类似,从pos位于的宿主结构体的上一个开始反向变量链表。

  89. (12)list_for_each_entry_from
  90. #define list_for_each_entry_from(pos, head, member)             \
  91.     for (; &pos->member != (head);    \
  92.      pos = list_entry(pos->member.next, typeof(*pos), member))
  93. 从当前pos所位于的宿主结构体开始遍历链表。

  94. (13)后面的几个函数带safe的函数,他们与上面讲的函数都很相似,只是保存了pos的下一个宿主结构体,这些函数是专门为删除结点是准备的。就不分析他们了。

  95. 至此,对于普通链表的操作我们就分析完了,这个list.h中后面的代码主要是为了哈西表设计的,就暂时先不分析,等到学了哈西表再分析他们^o^~


  1. linux内核中链表代码分析---list.h头文件分析(二)
  2. 16年2月28日16:59:55

  3. 分析完container_of()宏以后,继续分析list.h文件:
  4. (1)list_entry
  5. 它就是一个container_of宏,都是得到ptr所指地址的这个结构体的首地址
  6. #define list_entry(ptr, type, member) \
  7.     container_of(ptr, type, member)

  8. (2) list_first_entry
  9. #define list_first_entry(ptr, type, member) \
  10.     list_entry((ptr)->next, type, member)
  11. 这里的ptr是一个链表的头节点,这个宏就是取得这个链表第一元素的所指结构体的首地址。

  12. (3) list_for_each
  13. #define list_for_each(pos, head) \
  14.     for (pos = (head)->next; pos != (head); pos = pos->next)
  15. 它实际上就是一个for循环,从头到尾遍历链表,但是看代码发现,遍历链表需要一个head参数即可,这个pos参数好像没什么用啊。。。
  16. 然后就在内核中grep了一番,稍微总结出来一点:
  17. 这是一个for循环,我们通过这个for循环总得做点什么事情吧,以下面这个为例,
  18. 源文件在/driver/input/serio/hil_mlc.c中:
  19. static LIST_HEAD(hil_mlcs);
  20. static void hil_mlcs_process(unsigned long unused)
  21. {
  22.     struct list_head *tmp;

  23.     read_lock(&hil_mlcs_lock);
  24.     list_for_each(tmp, &hil_mlcs) {
  25.         struct hil_mlc *mlc = list_entry(tmp, hil_mlc, list);
  26.         ....
  27. }
  28. 可以看到,它通过这个list_for_each函数,将hil_mlcs链表中的每一个成员地址一一赋给了tmp变量,这样,在后面的语句中,就可以通过list_entry这个宏根据tmp变量和list链表头来找到包含他们的整个结构体hil_mlc的首地址,然后就可以对这个结构体里面其他的成员变量进行操作了~~~
  29. 这一块涉及到linux中,比如对于每一个子设备,都建立一个结构体,然后将这些子设备通过一个链表链接起来,操作的时候需要遍历链表中的每一项进行操作,所以就是这个函数存在的意义。
  30. 后面那个 __list_for_each和list_for_each相同,以前这两个函数是不同的,它有一个prefetch预取的操作,我们不再考虑。

  31. (4)list_for_each_prev
  32. #define list_for_each_prev(pos, head) \
  33.     for (pos = (head)->prev; pos != (head); pos = pos->prev)
  34. 与list_for_each相似,只是它是从尾到头遍历链表,将链表中的每一项都取出来操作。

  35. (5)list_for_each_safe
  36. #define list_for_each_safe(pos, n, head) \
  37.     for (pos = (head)->next, n = pos->next; pos != (head); \
  38.         pos = n, n = pos->next)
  39. 这个实际上就是一个for循环,从头到尾遍历链表。这里使用了n来记录pos的下一个,这样处理完一 个流程之后再赋给pos,避免了删除pos结点造成的问题。这个函数是 专门为删除结点是准备的。
  40. :list_for_each(pos, head)和list_for_each_safe(pos, n, head)都是从头至尾遍历链表的,但是对于前者 来说当操作中没有删除结点的时候使用,但是如果操作中有删除结点的操作的时候就使用后者,对于后面带safe的一般都是这个目的。

  41. (6) list_for_each_prev_safe
  42. #define list_for_each_prev_safe(pos, n, head) \
  43.     for (pos = (head)->prev, n = pos->prev; \
  44.      pos != (head); \
  45.      pos = n, n = pos->prev)
  46. 同理,这个函数与 list_for_each_prev相似。

  47. /* 注意上面的几个函数,他们的行参里面有pos与下面函数行参里面的pos不同,上面函数的操作都是pos = (head)->next等等的操作,所以pos是list_head类型的,下面函数的操作是pos = list_entry()等等的操作,所以他们是list_head结构体所嵌入的结构体的指针形式的,我们称之为宿主结构体。 */

  48. (7) list_for_each_entry
  49. #define list_for_each_entry(pos, head, member)                \
  50.     for (pos = list_entry((head)->next, typeof(*pos), member);    \
  51.      &pos->member != (head);     \
  52.      pos = list_entry(pos->member.next, typeof(*pos), member))
  53. 第一个参数为传入的遍历指针,指向宿主数据结构,第二个参数为链表头,为list_head结构,第三 个参数为list_head结构在宿主结构中的成员名。
  54. 这个函数是根据member成员遍历head链表(member成员一般都嵌入在宿主结构体中),并且将每个结构体的首地址赋值给pos,这样的话,我们就 可以在循环体里面通过pos来访问该宿主结构体变量的其他成员了。 下面用最近分析的V4L2里面的一段代码来举例说明,代码位于v4l2-device.c中:
  55. int v4l2_device_register_subdev_nodes(struct v4l2_device *v4l2_dev)
  56. {
  57.     struct video_device *vdev;
  58.     struct v4l2_subdev *sd;

  59.     list_for_each_entry(sd, &v4l2_dev->subdevs, list) {
  60.         if (!(sd->flags & V4L2_SUBDEV_FL_HAS_DEVNODE))
  61.             continue;
  62.     。。。。
  63. }
  64. 可以分析出来, v4l2_device结构体里面含有这个 subdevs链表头,sd是指向v4l2_subdev结构体的指针,list是一个list_head结构,在之前的代码中,肯定有操作已经将各个子设备结构体v4l2_subdev全部链接进 v4l2_device结构体里面的 subdevs链表里面,这时候需要做的就是从这个v4l2_device结构体里面的 subdevs链表里一一取出各个子设备结构体v4l2_subdev,然后操作它的各个成员变量。上述代码就是完成这个工作。

  65. (8) list_for_each_entry_reverse
  66. #define list_for_each_entry_reverse(pos, head, member)            \
  67.     for (pos = list_entry((head)->prev, typeof(*pos), member);    \
  68.      &pos->member != (head);     \
  69.      pos = list_entry(pos->member.prev, typeof(*pos), member))
  70. 与上面那个函数类似,反向遍历链表。

  71. (9) list_prepare_entry
  72. #define list_prepare_entry(pos, head, member) \
  73.     ((pos) ? : list_entry(head, typeof(*pos), member))
  74. 第一个参数为传入的遍历指针,指向宿主数据结构,第二个参数为链表头,为list_head结构,第三 个参数为list_head结构在宿主结构中的成员名。
  75. 这个函数的功能就是如果pos非空,那么pos的值就为其本身,如果pos为空,那么就从链表头强制扩展一
  76. 个虚pos指针,这个宏定义是为了在list_for_each_entry_continue()中使用做准备的。

  77. (10)list_for_each_entry_continue
  78. #define list_for_each_entry_continue(pos, head, member)         \
  79.     for (pos = list_entry(pos->member.next, typeof(*pos), member);    \
  80.      &pos->member != (head);    \
  81.      pos = list_entry(pos->member.next, typeof(*pos), member))
  82. 这个函数与list_for_each_entry很相似,但是肯定是不同的,它是从pos所在的宿主结构体的下一个开始遍历链表,并不是从链表的头部开始遍历,从它的名字可以看出来。主要的区别就是我标红的位置。

  83. (11)list_for_each_entry_continue_reverse
  84. #define list_for_each_entry_continue_reverse(pos, head, member)        \
  85.     for (pos = list_entry(pos->member.prev, typeof(*pos), member);    \
  86.      &pos->member != (head);    \
  87.      pos = list_entry(pos->member.prev, typeof(*pos), member))
  88. 与上一个函数类似,从pos位于的宿主结构体的上一个开始反向变量链表。

  89. (12)list_for_each_entry_from
  90. #define list_for_each_entry_from(pos, head, member)             \
  91.     for (; &pos->member != (head);    \
  92.      pos = list_entry(pos->member.next, typeof(*pos), member))
  93. 从当前pos所位于的宿主结构体开始遍历链表。

  94. (13)后面的几个函数带safe的函数,他们与上面讲的函数都很相似,只是保存了pos的下一个宿主结构体,这些函数是专门为删除结点是准备的。就不分析他们了。

  95. 至此,对于普通链表的操作我们就分析完了,这个list.h中后面的代码主要是为了哈西表设计的,就暂时先不分析,等到学了哈西表再分析他们^o^~

阅读(2662) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~