list.h头文件分析(2)

2010年8月13日 由 edsionte 留言 »

Last Update:8/27

Last Update:8/15

9.合并链表

既然我们可以切割链表,那么当然也可以合并了。先看最基本的合并函数,就是将list这个链表(不包括头结点)插入到prev和next两结点之间。这个代码阅读起来不困难,基本上是“见码知意”。

 271static inline void __list_splice(const struct list_head *list,
 272                                 struct list_head *prev,
 273                                 struct list_head *next)
 274{
 275        struct list_head *first = list->next;
 276        struct list_head *last = list->prev;
 277
 278        first->prev = prev;
 279        prev->next = first;
 280
 281        last->next = next;
 282        next->prev = last;
 283}

理解了最基本的合并函数,那么将它封装起来,就可以形成下面两个函数了,分别在head链表的首部和尾部合并。这里的调用过程类似增加,删除功能。

 290static inline void list_splice(const struct list_head *list,
 291                                struct list_head *head)
 292{
 293        if (!list_empty(list))
 294                __list_splice(list, head, head->next);
 295}

 302static inline void list_splice_tail(struct list_head *list,
 303                                struct list_head *head)
 304{
 305        if (!list_empty(list))
 306                __list_splice(list, head->prev, head);
 307}

合并两个链表后,list还指向原链表,因此应该初始化。在上述两函数末尾添加初始化语句INIT_LIST_HEAD(list);后,就安全了。

10.遍历

下面我们要分析链表的遍历。虽然涉及到遍历的宏比较多,但是根据我们前面分析的那样,掌握好最基本的宏,其他宏就是进行“封装”。便利中的基本宏是:

381#define __list_for_each(pos, head) \
382        for (pos = (head)->next; pos != (head); pos = pos->next)

head是整个链表的头指针,而pos则不停的往后移动。但是你有没有觉得,这里有些奇怪?因为我们在上篇文章中说过,struct list_head结构经常和其他数据组成新的结构体,那么现在我们只是不停的遍历新结构体中的指针,如何得到其他成员?因此我们需要搞懂list_entry这个宏:

 348#define list_entry(ptr, type, member) \
 349        container_of(ptr, type, member)

这个宏的作用是通过ptr指针获取type结构的地址,也就是指向type的指针。其中ptr是指向member成员的指针。这个list_entry宏貌似很简单的样子,就是再调用container_of宏,可是当你看了container_of宏的定义后……

 443#define container_of(ptr, type, member) ({                      \
 444        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
 445        (type *)( (char *)__mptr - offsetof(type,member) );})

是不是让人有点抓狂?别急,我们一点点来分析。

首先这个宏包含两条语句。第一条:const typeof( ((type *)0)->member ) *__mptr = (ptr);首先将0转化成type类型的指针变量(这个指针变量的地址为0x0),然后再引用member成员(对应就是((type *)0)->member ))。注意这里的typeof(x),是返回x的数据类型,那么 typeof( ((type *)0)->member )其实就是返回member成员的数据类型。那么这条语句整体就是将__mptr强制转换成member成员的数据类型,再将ptr的赋给它(ptr本身就是指向member的指针)。

第二句中,我们先了解offsetof是什么?它也是一个宏被定义在:linux/include/stddef.h中。原型为:

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER);

这个貌似也很抓狂,不过耐心耐心:((TYPE *)0)->MEMBER)这个其实就是提取type类型中的member成员,那么&((TYPE *)0)->MEMBER)得到member成员的地址,再强制转换成size_t类型(unsigned int)。但是这个地址很特别,因为TYPE类型是从0x0开始定义的,那么我们现在得到的这个地址就是member成员在TYPE数据类型中的偏移量。

我们再来看第二条语句, (type *)( (char *)__mptr – offsetof(type,member) )求的就是type的地址,即指向type的指针。不过这里要注意__mptr被强制转换成了(char *),为何要这么做?因为如果member是非char型的变量,比如为int型,并且假设返回值为offset,那么这样直接减去偏移量,实际上__mptr会减去sizeof(int)*offset!这一点和指针加一减一的原理相同。

有了这个指针,那么就可以随意引用其内的成员了。关于此宏的更具体了解,不妨亲自动手测试这里的程序。

好了,现在不用抓狂了,因为了解了list_entry宏,接下来的事情就很简单了。

下面这个宏会得到链表中第一个结点的地址。

 359#define list_first_entry(ptr, type, member) \
 360        list_entry((ptr)->next, type, member)

真正遍历的宏登场了,整个便利过程看起来很简单,可能你对prefetch()陌生,它的作用是预取节点,以提高速度。

 367#define list_for_each(pos, head) \
 368        for (pos = (head)->next; prefetch(pos->next), pos != (head); \
 369                pos = pos->next)

我们再来看一开始我们举例的那个便利宏。注意它和上述便利宏的区别就是没有prefetch(),因为这个宏适合比较少结点的链表。

 381#define __list_for_each(pos, head) \
 382        for (pos = (head)->next; pos != (head); pos = pos->next)

接下来这个遍历宏貌似长相和上面那几个稍有不同,不过理解起来也不困难,倒着(从最后一个结点)开始遍历链表。

389#define list_for_each_prev(pos, head) \
 390        for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
 391                pos = pos->prev)

下面两个宏是上述两个便利宏的安全版,我们看它安全在那里?它多了一个与pos同类型的n,每次将下一个结点的指针暂存起来,防止pos被释放时引起的链表断裂。

399#define list_for_each_safe(pos, n, head) \
 400        for (pos = (head)->next, n = pos->next; pos != (head); \
 401                pos = n, n = pos->next)

 409#define list_for_each_prev_safe(pos, n, head) \
 410        for (pos = (head)->prev, n = pos->prev; \
 411             prefetch(pos->prev), pos != (head); \
 412             pos = n, n = pos->prev)

前面我们说过,用在list_for_each宏进行遍历的时候,我们很容易得到pos,我们都知道pos存储的是当前结点前后两个结点的地址。而通过list_entry宏可以获得当前结点的地址,进而得到这个结点中其他的成员变量。而下面两个宏则可以直接获得每个结点的地址,我们接下来看它是如何实现的。为了方便说明以及便于理解,我们用上文中的结构struct stu来举例。pos是指向struct stu结构的指针;list是一个双链表,同时也是这个结构中的成员,head便指向这个双链表;member其实就是这个结构体中的list成员。

在for循环中,首先通过list_entry来获得第一个结点的地址;&pos->member != (head)其实就是&pos->list!=(head);它是用来检测当前list链表是否到头了;最后在利用list_entry宏来获得下一个结点的地址。这样整个for循环就可以依次获得每个结点的地址,进而再去获得其他成员。理解了list_for_each_entry宏,那么list_for_each_entry_reverse宏就显而易见了。

 420#define list_for_each_entry(pos, head, member)                          \
 421        for (pos = list_entry((head)->next, typeof(*pos), member);      \
 422             prefetch(pos->member.next), &pos->member != (head);        \
 423             pos = list_entry(pos->member.next, typeof(*pos), member))

 431#define list_for_each_entry_reverse(pos, head, member)                  \
 432        for (pos = list_entry((head)->prev, typeof(*pos), member);      \
 433             prefetch(pos->member.prev), &pos->member != (head);        \
 434             pos = list_entry(pos->member.prev, typeof(*pos), member))

下面这两个宏是从当前结点的下一个结点开始继续(或反向)遍历。

 456#define list_for_each_entry_continue(pos, head, member)                 \
 457        for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
 458             prefetch(pos->member.next), &pos->member != (head);        \
 459             pos = list_entry(pos->member.next, typeof(*pos), member))

 470#define list_for_each_entry_continue_reverse(pos, head, member)         \
 471        for (pos = list_entry(pos->member.prev, typeof(*pos), member);  \
 472             prefetch(pos->member.prev), &pos->member != (head);        \
 473             pos = list_entry(pos->member.prev, typeof(*pos), member))

与上述宏不同的是,这个宏是从当前pos结点开始遍历。

 483#define list_for_each_entry_from(pos, head, member)                     \
 484        for (; prefetch(pos->member.next), &pos->member != (head);      \
 485             pos = list_entry(pos->member.next, typeof(*pos), member))

接下来几个宏又分别是上述几个宏的安全版。安全原因上面已经说过,在此不再赘述。

list_for_each_entry_safe(pos, n, head, member)
list_for_each_entry_safe_continue(pos, n, head, member)
list_for_each_entry_safe_from(pos, n, head, member)
list_for_each_entry_safe_reverse(pos, n, head, member)

以上即是list.h头文件中的大部分内容分析。关于hash表部分在此暂不分析。

广告位

8 条评论

  1. yangli说道:

    在哪里可以看到typeof的源代码?求解,谢谢!

    [回复一下]

    edsionte 回复:

    @yangli, 你好,typeof是GCC内置的一个宏,因此是看不到它的定义的。不过你可以通过GCC手册来查看typeof更多的解释。我将GCC手册上关于它的解释发到了你的邮箱清查收

    [回复一下]

  2. Den说道:

    问个问题..
    /include/ linux/ kernel.h
    里面
    #define container_of(ptr, type, member) ({ \
    const typeof( ((type *)0)->member ) *__mptr = (ptr); \
    (type *)( (char *)__mptr – offsetof(type,member) );})
    中间那段
    const typeof( ((type *)0)->member ) *__mptr = (ptr);
    不是没必要的么 ? 直接
    #define container_of(ptr, type, member) ({ \
    (type *)( (char *)ptr – offsetof(type,member) );
    也可以得到想要的效果

    [回复一下]

  3. cjok说道:

    顶一个,写的不错哦!

    [回复一下]

  4. gabriel说道:

    问一个比较愚昧的问题

    const typeof( ((type *)0)->member ) *__mptr = (ptr);

    如果这里直接const typeof( member ) *__mptr = (ptr)
    会出现什么样的错误呢?

    [回复一下]

    edsionte 回复:

    @gabriel, 本身不会产生错误,但是加上这句可以对指针类型进行一次检查。

    [回复一下]

发表回复

windows 7 ultimate product key

windows 7 ultimate product key

winrar download free

winrar download free

winzip registration code

winzip registration code

winzip free download

winzip free download

winzip activation code

winzip activation code

windows 7 key generator

windows 7 key generator

winzip freeware

winzip freeware

winzip free download full version

winzip free download full version

free winrar download

free winrar download

free winrar

free winrar

windows 7 crack

windows 7 crack

windows xp product key

windows xp product key

windows 7 activation crack

windows7 activation crack

free winzip

free winzip

winrar free download

winrar free download

winrar free

winrar free

download winrar free

download winrar free

windows 7 product key

windows 7 product key