- 论坛徽章:
- 13
|
本帖最后由 _nosay 于 2016-09-16 12:13 编辑
- /* 这段程序用于演示由n_list结构构成一个双向链表的过程 */
- #include <stdio.h>
- #include <stdlib.h>
- struct n_list {
- int n;
- struct n_list *prev;
- struct n_list *next;
- } head = { 100, &head, &head };
- void n_list_destroy()
- {
- while (head.next != &head)
- {
- struct n_list *nl = head.next;
-
- head.next = nl->next;
- free(nl);
- }
- }
- int n_list_build()
- {
- int i = 0;
-
- for (; i < 10; i ++)
- {
- struct n_list *first = &head;
- struct n_list *last = head.prev;
- struct n_list *nl;
-
- if ((nl = malloc(sizeof(struct n_list))) == NULL) {
- printf("%s(), %d: malloc failed\n", __FUNCTION__, __LINE__);
- goto err;
- }
-
- nl->n = i;
-
- // 将新结点nl加到最后,即last与first之间
- first->prev = nl;
- nl->next = first;
- nl->prev = last;
- last->next = nl;
- }
-
- return 0;
- err:
- n_list_destroy();
- return -1;
- }
- void n_list_print()
- {
- struct n_list *nl = &head;
-
- do {
- printf("%d\n", nl->n);
- nl = nl->next;
- } while (nl != &head);
- }
- int main()
- {
- if (n_list_build() < 0)
- return -1;
-
- n_list_print();
- n_list_destroy();
-
- return 0;
- }
复制代码
通过这段代码看,要想将一个结构按照双向链表连接起来,比如“struct { int n; };”,可以先向结构中加入prev、next成员,分别用于指向前、后两个结点,并编写相应链表操作的函数。
Linux内核中使用的list.h,是将双向链表的结构以及操作都抽象出来了:
另外,将list_for_each(pos, head)宏函数改进一下:
- #define list_for_each_safe(pos, n, head) \
- for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)
复制代码
上述举的例子,就可以写成这样(直接用接口即可,不需要自己再去想各种情况下指针该如何指向):- #include <stdio.h>
- #include <stdlib.h>
- #include "list.h"
- struct n_list {
- int n;
- struct list_head list; // 添加list_head结构成员
- };
- struct list_head head = LIST_HEAD_INIT(head);
- void n_list_destroy()
- {
- struct list_head *pos, *n;
-
- list_for_each(pos, n, &head) { // 直接使用接口遍历
- struct n_list *nl = container_of(pos, struct n_list, list);
- free(nl);
- }
- }
- int n_list_build()
- {
- int i = 0;
- struct n_list *nl;
-
- for (; i < 10; i ++)
- {
- if ((nl = malloc(sizeof(struct n_list))) == NULL) {
- printf("%s(), %d: malloc failed\n", __FUNCTION__, __LINE__);
- goto err;
- }
-
- nl->n = i;
- list_add_tail(&nl->list, &head); // 直接使用接口添加
- }
-
- return 0;
- err:
- n_list_destroy();
- return -1;
- }
- void n_list_print()
- {
- struct list_head *pos, *n;
-
- list_for_each(pos, n, &head) { // 直接使用接口遍历
- struct n_list *nl = container_of(pos, struct n_list, list);
- printf("%d\n", nl->n);
- }
- }
- int main()
- {
- if (n_list_build() < 0)
- return -1;
-
- n_list_print();
- n_list_destroy();
-
- return 0;
- }
复制代码 将双向链表从具体的结构中抽象出来,可以说非常精妙,可以对比这两段使用list_head前后的程序,最好动手写一些程序验证一下list.h里面的各个接口的功能,Linux内核中大量使用了list_head,所以把list.h搞熟悉,看内核代码也会轻松很多。
- #define list_entry(ptr, type, member) \
- ((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)))
将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内核使用的是GNU C,相对于ANSI C,多了一些扩展特性,等读代码遇到时再说明,但要注意的是GNU C一直在扩展,所以新版本内核,可能出现用老版本gcc编译不过的情况,那就需要升级gcc再编译。
另外还有一些“do {} while(0)”等技巧,没有什么理解难度,所以也不一一列举。
|
评分
-
查看全部评分
|