Chinaunix首页 | 论坛 | 博客
  • 博客访问: 185027
  • 博文数量: 37
  • 博客积分: 171
  • 博客等级: 入伍新兵
  • 技术积分: 315
  • 用 户 组: 普通用户
  • 注册时间: 2011-01-13 22:54
个人简介

寻找方向程序猿、攻城狮

文章存档

2023年(1)

2022年(4)

2019年(1)

2018年(1)

2017年(1)

2015年(2)

2014年(19)

2013年(2)

2012年(1)

2011年(5)

分类: LINUX

2014-12-16 23:52:07

linux内核中,链表头结构一般不会使用链表元素的类型来定义,如下:
struct example_head
{
    struct list_head list;
    int count;
}
链表元素类型的定义一般如下:
struct example_element
{
    struct list_head list;
    int x;
    char y;
    ......
}

其中,struct list_head结构的定义如下:
struct list_head {
struct list_head *next, *prev;
};

一般来说,由这样的数据结构类型构成的链表要进行遍历的话其实蛮简单直观的,如下:

  1. struct example_element* p = (struct example_element*)head->list.next;

  2. for (;p != &head->list; p = (struct example_element*)p->list.next;)
  3. {
  4. ............
  5. }
但是内核中经常用list_for_each_entry这个宏来实现遍历,搞的比较复杂,可能看个半天还是看不懂。
我自己对这个宏分析了一下。
list_for_each_entry的定义如下:

  1. /**
  2.  * list_for_each_entry    -    iterate over list of given type
  3.  * @pos:    the type * to use as a loop cursor.
  4.  * @head:    the head for your list.
  5.  * @member:    the name of the list_struct within the struct.
  6.  */
  7. #define list_for_each_entry(pos, head, member)                \
  8.     for (pos = list_entry((head)->next, typeof(*pos), member);    \
  9.      prefetch(pos->member.next), &pos->member != (head);     \
  10.      pos = list_entry(pos->member.next, typeof(*pos), member))
注意member的解释,是the struct内部的list_struct的名字,the struct是指example_element,那么example_element中的list_struct就是struct list_head list;了。
for循环中,中间的条件判断理解起来比较简单,就是告诉cpu把下一个结点的内容读取到一级cache,然后判断pos指针是不是已经遍历到头结点了。
关键之处在于list_entry宏了。再看list_entry宏的定义:

  1. /**
  2.  * list_entry - get the struct for this entry
  3.  * @ptr:    the &struct list_head pointer.
  4.  * @type:    the type of the struct this is embedded in.
  5.  * @member:    the name of the list_struct within the struct.
  6.  */
  7. #define list_entry(ptr, type, member) \
  8.     container_of(ptr, type, member)

  1. /**
  2.  * container_of - cast a member of a structure out to the containing structure
  3.  * @ptr:    the pointer to the member.
  4.  * @type:    the type of the container struct this is embedded in.
  5.  * @member:    the name of the member within the struct.
  6.  *
  7.  */
  8. #define container_of(ptr, type, member) ({            \
  9.     const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
  10.     (type *)( (char *)__mptr - offsetof(type,member) );})
注意的是,ptr的类型是struct list_head,而member也是struct list_head,而type的类型是struct example_element的,struct list_head类型的member位于type内部。
container_of宏主要是获得ptr所指向的member成员所在的struct example_element类型的链表元素的指针。
如果member位于struct example_element类型的链表元素的最前面,那么要获取struct example_element类型的元素的指针很简单的,做一个强制转换即可,没必要使用以上的宏定义搞的太过复杂,如下:
(struct example_element*)ptr

但为什么内核代码搞的这么复杂呢,我认为主要原因在于通用性,如果struct example_element的定义如下,list_for_each_entry也一样可以用来遍历,而我最前面所用的方法就不适用了。

  1. struct example_element
  2. {
  3.    int x;
  4.    struct list_head list;
  5.    char b;
  6.    ........
  7. }

以上是我个人见解,请指正。




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