水积春塘晚,阴交夏木繁 ——唐·白居易
链表宏 在linux内核 、鸿蒙内核 、rtos 和一些开源代码 中用的非常多。链表宏是双向链表的经典实现方式,总代码不超过50行,相当精炼。在一些开源框架中,它的数据结构,就是以链表宏 为基础进行搭建(如shttpd,一个开源的轻量级、嵌入式服务器框架)。本篇文章将对llist.h
文件中的链表宏进行逐个讲解。
1 源码(llist.h) llist.h
文件的全部源码如下:
#ifndef LLIST_HEADER_INCLUDED #define LLIST_HEADER_INCLUDED /* * Linked list macros. */ struct llhead { struct llhead *prev ; struct llhead *next ; };#define LL_INIT(N) ((N)->next = (N)->prev = (N)) #define LL_HEAD(H) struct llhead H = { &H, &H } #define LL_ENTRY(P,T,N) ((T *)((char *)(P) - offsetof(T, N))) #define LL_ADD(H, N) \ do { \ ((H)->next)->prev = (N); \ (N)->next = ((H)->next); \ (N)->prev = (H); \ (H)->next = (N); \ } while (0) #define LL_TAIL(H, N) \ do { \ ((H)->prev)->next = (N); \ (N)->prev = ((H)->prev); \ (N)->next = (H); \ (H)->prev = (N); \ } while (0) #define LL_DEL(N) \ do { \ ((N)->next)->prev = ((N)->prev); \ ((N)->prev)->next = ((N)->next); \ LL_INIT(N); \ } while (0) #define LL_EMPTY(N) ((N)->next == (N)) #define LL_FOREACH(H,N) for (N = (H)->next; N != (H); N = (N)->next) #define LL_FOREACH_SAFE(H,N,T) \ for (N = (H)->next, T = (N)->next; N != (H); \ N = (T), T = (N)->next) #endif /* LLIST_HEADER_INCLUDED */
2 注解 在llist.h
中,所用到的链表是双向链表,其节点结构定义如下。在此节点结构中,其只包含了两个指针域,一个指向直接前驱,一个指向直接后继,没有定义数据域。
struct llhead { struct llhead *prev ; struct llhead *next ; };
2.1 LL_INIT(N) 宏LL_INIT
的定义如下,其作用是将所传入指针N
的两个指针域(N)->next
和(N)->prev
都指向N
。目的是完成单个节点的初始化工作,如下图示意了该过程。
#define LL_INIT(N) ((N)->next = (N)->prev = (N))
2.2 LL_HEAD(H) 宏LL_HEAD
的定义如下,直接将宏LL_HEAD
展开,其意图很明显是定义一个新链表H
(H表示为传入宏的参数名),并且将H
的两个指针域,都初始化为H
地址本身,如下图示意了该过程。
#define LL_HEAD(H) struct llhead H = { &H, &H }
2.3 LL_ENTRY(P,T,N) 宏LL_ENTRY
的定义如下,其依赖于宏offsetof
。下面先对宏offsetof
进行详细描述,其功能描述为:
C语言的offsetof()宏,是定义在stddef.h。用于求出一个struct或union数据类型的给定成员的size_t类型的字节偏移值(相对于struct或union数据类型的开头)。offsetof()宏有两个参数,分别是结构名与结构内的成员名。——维基百科
#define LL_ENTRY(P,T,N) ((T *)((char *)(P) - offsetof(T, N))) #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
为了更好的理解宏offsetof
,下面按照宏的定义来进行拆解说明。
((TYPE *)0):取整数零并将其强转换为指向TYPE的指针。 ((TYPE *)0)->MEMBER):引用指向结构成员MEMBER。 &((TYPE *)0)->MEMBER):取出MEMBER的地址。 ((size_t) &((TYPE *)0)->MEMBER):将结果转换为适当的数据类型。 由于该结构体是以0地址开头,所以最后该宏返回的结果就是该成员相对于结构体开头的偏移量。有了对宏offsetof
的理解,再来看宏LL_ENTRY
就比较好理解了。宏LL_ENTRY
的功能是,根据结构体变量(T)中的域成员变量(N)的指针(P)来获取指向整个结构体变量的指针 ,下面来做拆解说明:
offsetof(T, N):计算成员N相对于其结构体T开头的偏移量。 ((char *)(P):将指针P强转为字符指针类型,保证其做+/-运算时是以字节为单位。 (char *)(P) - offsetof(T, N)):P为成员N的指针,减去偏移量,指针到了结构体开头位置。 ((T *)((char *)(P)- offsetof(T, N))):将指针强转,得到了整个结构体指针。 宏LL_ENTRY
的作用和linux
中的宏container_of
作用基本一样,该宏定义如下:
#define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );})
2.4 LL_ADD(H, N) 宏LL_ADD
的定义如下,其作用是向双向链表H的头部添加节点N。根据LL_ADD
定义的语句顺序,对照着图片分析,会更加清晰。如下图,上面这张图片展示了添加节点N之前的结构,下图展示了添加节点N之后的结构。
#define LL_ADD(H, N) \ do { \ ((H)->next)->prev = (N); \ (N)->next = ((H)->next); \ (N)->prev = (H); \ (H)->next = (N); \ } while (0)
2.5 LL_TAIL(H, N) 宏LL_TAIL
的定义如下,其作用是将节点N添加到双向链表H的尾部。宏LL_TAIL
的定义如下,其作用是向双向链表H的头部添加节点N。根据LL_TAIL
定义的语句顺序,对照着图片分析,会更加清晰。如下图,上面这张图片展示了添加节点N之前的结构,下图展示了添加节点N之后的结构,可以和LL_ADD
的结果进行对照。
#define LL_TAIL(H, N) \ do { \ ((H)->prev)->next = (N); \ (N)->prev = ((H)->prev); \ (N)->next = (H); \ (H)->prev = (N); \ } while (0)
2.6 LL_DEL(N) 宏LL_DEL
的定义如下,其作用是将节点N从双向链表中删除,并且节点N回到初始状态(其指针仅指向自身,不再指向其它地方)。
#define LL_DEL(N) \ do { \ ((N)->next)->prev = ((N)->prev); \ ((N)->prev)->next = ((N)->next); \ LL_INIT(N); \ } while (0)
2.7 LL_EMPTY(N) 宏LL_EMPTY
的定义如下,其作用是判断链表N是否为空链表,返回布尔值false/true
。如果节点的直接后继next
指向其自身,就认为其为空节点。
#define LL_EMPTY(N) ((N)->next == (N))
2.8 LL_FOREACH(H,N) 宏LL_FOREACH
的定义如下,其作用是在双向链表H中,循环遍历出节点。
#define LL_FOREACH(H,N) for (N = (H)->next; N != (H); N = (N)->next)
2.9 LL_FOREACH_SAFE(H,N,T) 宏LL_FOREACH_SAFE
的定义如下,其作用是在双向链表H中,循环遍历出节点N,因为其有提前存储N的下一个节点T。即使N节点被清理掉,也不影响其下一个节点的遍历,所以该宏一般用来做循环清除双向链表中节点的操作,而宏LL_FOREACH
仅用来遍历双向链表。
#define LL_FOREACH_SAFE(H,N,T) \ for (N = (H)->next, T = (N)->next; N != (H); \ N = (T), T = (N)->next)
3 使用案例 有人可能会有疑惑,这个双向链表定义如此简单,只有前驱和后继两个指针,甚至连数据域都没有,那实际该如何使用呢?这个可能就是这组双向链表宏的精妙之处。其在使用过程中并不需要数据域,而是通过指针将结构体串联成双向链表,并且通过该指针借助 LL_ENTRY宏 能还原出该结构体指针,从而达到操作具体结构体的目的。 如下例子虽然不是完整能跑的程序,但是足够说明双向链表宏的关键用法。程序源码如下,现对照代码,描述双向链表宏的大致使用步骤:
定义一个结构体,结构体中必须包含struct llhead link;
双向链表节点,这是后续能通过遍历双向链表节点,还原出该结构体指针的关键; 通过LL_HEAD(listeners);
,创建一个双向链表的头为listeners
; 在具体逻辑中,肯定有地方通过LL_TAIL(&listeners, &l->link);
或者LL_ADD(H, N)
,向双向链表的头listeners
添加节点; 在需要操作1.所定义的结构体时,通过LL_FOREACH(&listeners, lp)
遍历出节点指针; 这是最精华的一步,通过4.遍历出来的节点,传入宏LL_ENTRY(lp, struct listener, link);
中,还原出节点所在的结构体指针 ,根据逻辑的需要对结构体进行具体相应的操作; 通过宏LL_FOREACH_SAFE
来遍历双向链表,LL_DEL
来删除遍历出来的节点,达到清空链表的作用。 struct llhead { struct llhead *prev ; struct llhead *next ; };struct listener { struct llhead link ; struct shttpd_ctx *ctx ; /* Context that socket belongs */ int sock; /* Listening socket */ int is_ssl; /* Should be SSL-ed */ };static LL_HEAD (listeners) ; /* List of listening sockets */ struct listener *l ; LL_TAIL(&listeners, &l->link);struct llhead *lp ; LL_FOREACH(&listeners, lp) { l = LL_ENTRY(lp, struct listener, link); FD_SET(l->sock, &read_set); if (l->sock > max_fd) max_fd = l->sock; DBG(('FD_SET(%d) (listening)' , l->sock)); }struct llhead *lp , *tmp ; LL_FOREACH_SAFE(&listeners, lp, tmp) { l = LL_ENTRY(lp, struct listener, link); (void ) closesocket(l->sock); LL_DEL(&l->link); free (l); }
4 总结 LL_ENTRY(P,T,N)
宏是这一组宏的核心,其在具体使用中的功能可以概括为,通过传入链表节点P,还原出节点所在结构体的指针,进而能对结构体进行相应操作 ;这些宏最初是极客写出的,后来在Linux内核中被推广使用。 如果有同学知道这些宏的原始来源,请后台私信哦,感谢!