良许Linux教程网 干货合集 嵌入式开发中100%会用的几个宏,建议收藏

嵌入式开发中100%会用的几个宏,建议收藏

在编程领域,链表宏是一种广泛应用于众多操作系统内核、嵌入式系统以及各类开源项目中的数据结构实现方式,其简洁高效的特性备受称道。唐代诗人白居易曾言:“水积春塘晚,阴交夏木繁”,不禁让人联想到链表宏在代码世界中的繁荣与生机。

无论是在Linux内核,还是在鸿蒙操作系统的内核设计中,又或者在RTOS(实时操作系统)的构建过程中,链表宏都扮演着不可或缺的角色。其优雅的设计理念使得整个数据结构的实现始终保持在一种高度简洁的状态,常常不超过50行代码长度。更为引人瞩目的是,在诸多开源框架中,如轻量级嵌入式服务器框架shttpd,其底层数据结构往往以链表宏为核心进行构建。

本文旨在深入剖析名为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。目的是完成单个节点的初始化工作,如下图示意了该过程。image-20240507222431762

#define LL_INIT(N) ((N)->next = (N)->prev = (N))

2.2 LL_HEAD(H)

LL_HEAD的定义如下,直接将宏LL_HEAD展开,其意图很明显是定义一个新链表H(H表示为传入宏的参数名),并且将H的两个指针域,都初始化为H地址本身,如下图示意了该过程。![image-20240507222444758x_lazy=1&wx_co=1)

#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之后的结构。image-20240507222448311image-20240507222454902

#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的结果进行对照。image-20240507222500915image-20240507222511330

#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宏** 能还原出该结构体指针,从而达到操作具体结构体的目的。

如下例子虽然不是完整能跑的程序,但是足够说明双向链表宏的关键用法。程序源码如下,现对照代码,描述双向链表宏的大致使用步骤:

  1. 定义一个结构体,结构体中必须包含struct llhead link;双向链表节点,这是后续能通过遍历双向链表节点,还原出该结构体指针的关键;
  2. 通过LL_HEAD(listeners);,创建一个双向链表的头为listeners
  3. 在具体逻辑中,肯定有地方通过LL_TAIL(&listeners, &l->link);或者LL_ADD(H, N),向双向链表的头listeners添加节点;
  4. 在需要操作1.所定义的结构体时,通过LL_FOREACH(&listeners, lp)遍历出节点指针;
  5. 这是最精华的一步,通过4.遍历出来的节点,传入宏LL_ENTRY(lp, struct listener, link);中,还原出节点所在的结构体指针,根据逻辑的需要对结构体进行具体相应的操作;
  6. 通过宏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内核中被推广使用。

如果有同学知道这些宏的原始来源,请后台私信哦,感谢!

以上就是良许教程网为各位朋友分享的Linu系统相关内容。想要了解更多Linux相关知识记得关注公众号“良许Linux”,或扫描下方二维码进行关注,更多干货等着你 !

137e00002230ad9f26e78-265x300
本文由 良许Linux教程网 发布,可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。
良许

作者: 良许

良许,世界500强企业Linux开发工程师,公众号【良许Linux】的作者,全网拥有超30W粉丝。个人标签:创业者,CSDN学院讲师,副业达人,流量玩家,摄影爱好者。
上一篇
下一篇

发表评论

联系我们

联系我们

公众号:良许Linux

在线咨询: QQ交谈

邮箱: yychuyu@163.com

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

关注微博
返回顶部