• Linux内核中的一个list实现的理解

    一 C中宏的应用

    如果我们写个排序方法， 用c语言实现的话，由于没有通用的类型，也没有c++的模板，没有java的泛化，这样不同的数据类型，我们就要实现多个排序方法，比如实现个int的排序方法，实现double类型的排序方法，但是这样重复的代码很多，其实可以用宏来实现。

    同样有个需求要我们写个list，如果里面保存的数据类型不同，就要实现多个，这种实现方法会有太多代码重复，用宏实现是个不错的思路，用宏来实现相关函数还可以提升性能， 当然宏也有明显的缺点，比如不利于调试，写不好也容易在展开的时候出错。

    二 内核中的一个list的实现

    这个list 可以看作是双向链表，具体的实现如下：

    1. #ifndef B4EDBD16_2948_4595_9135_6BBBAF9B6341
    2. #define B4EDBD16_2948_4595_9135_6BBBAF9B6341
    3. /*
    4.  * Tail queue definitions.
    5.  */
    6. #define _TAILQ_HEAD(name, type, qual)                   \
    7. struct name {                               \
    8.     qual type *tqh_first;       /* first element */     \
    9.     qual type *qual *tqh_last;  /* addr of last next element */ \
    10. }
    11. #define TAILQ_HEAD(name, type)  _TAILQ_HEAD(name, struct type,)
    12.  
    13. #define TAILQ_HEAD_INITIALIZER(head)                    \
    14.     { NULL, &(head).tqh_first }
    15.  
    16. #define _TAILQ_ENTRY(type, qual)                    \
    17. struct {                                \
    18.     qual type *tqe_next;        /* next element */      \
    19.     qual type *qual *tqe_prev;  /* address of previous next element */\
    20. }
    21. #define TAILQ_ENTRY(type)   _TAILQ_ENTRY(struct type,)
    22. #define TAILQ_END(head)         NULL
    23. #define TAILQ_FOREACH_SAFE(var, head, field, tvar)                  \
    24.     for((var) = TAILQ_FIRST(head), \
    25.         (tvar) = TAILQ_FIRST(head) ? TAILQ_NEXT(TAILQ_FIRST(head), field): NULL ; \
    26.         (var) != TAILQ_END(head);                   \
    27.         (var = tvar), (tvar) = var ? TAILQ_NEXT(var, field): NULL)
    28. /*
    29.  * Tail queue functions.
    30.  */
    31. #define TAILQ_INIT(head) do {                       \
    32.     (head)->tqh_first = NULL;                   \
    33.     (head)->tqh_last = &(head)->tqh_first;              \
    34. } while (/*CONSTCOND*/0)
    35.  
    36. #define TAILQ_INSERT_HEAD(head, elm, field) do {            \
    37.     if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)    \
    38.         (head)->tqh_first->field.tqe_prev =         \
    39.             &(elm)->field.tqe_next;             \
    40.     else                                \
    41.         (head)->tqh_last = &(elm)->field.tqe_next;      \
    42.     (head)->tqh_first = (elm);                  \
    43.     (elm)->field.tqe_prev = &(head)->tqh_first;         \
    44. } while (/*CONSTCOND*/0)
    45.  
    46. #define TAILQ_INSERT_TAIL(head, elm, field) do {            \
    47.     (elm)->field.tqe_next = NULL;                   \
    48.     (elm)->field.tqe_prev = (head)->tqh_last;           \
    49.     *(head)->tqh_last = (elm);                  \
    50.     (head)->tqh_last = &(elm)->field.tqe_next;          \
    51. } while (/*CONSTCOND*/0)
    52.  
    53. #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {      \
    54.     if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
    55.         (elm)->field.tqe_next->field.tqe_prev =         \
    56.             &(elm)->field.tqe_next;             \
    57.     else                                \
    58.         (head)->tqh_last = &(elm)->field.tqe_next;      \
    59.     (listelm)->field.tqe_next = (elm);              \
    60.     (elm)->field.tqe_prev = &(listelm)->field.tqe_next;     \
    61. } while (/*CONSTCOND*/0)
    62.  
    63. #define TAILQ_INSERT_BEFORE(listelm, elm, field) do {           \
    64.     (elm)->field.tqe_prev = (listelm)->field.tqe_prev;      \
    65.     (elm)->field.tqe_next = (listelm);              \
    66.     *(listelm)->field.tqe_prev = (elm);             \
    67.     (listelm)->field.tqe_prev = &(elm)->field.tqe_next;     \
    68. } while (/*CONSTCOND*/0)
    69.  
    70. #define TAILQ_REMOVE(head, elm, field) do {             \
    71.     if (((elm)->field.tqe_next) != NULL)                \
    72.         (elm)->field.tqe_next->field.tqe_prev =         \
    73.             (elm)->field.tqe_prev;              \
    74.     else                                \
    75.         (head)->tqh_last = (elm)->field.tqe_prev;       \
    76.     *(elm)->field.tqe_prev = (elm)->field.tqe_next;         \
    77. } while (/*CONSTCOND*/0)
    78. #define TAILQ_REPLACE(head, elm, elm2, field) do {          \
    79.     if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)   \
    80.         (elm2)->field.tqe_next->field.tqe_prev =        \
    81.             &(elm2)->field.tqe_next;                \
    82.     else                                \
    83.         (head)->tqh_last = &(elm2)->field.tqe_next;     \
    84.     (elm2)->field.tqe_prev = (elm)->field.tqe_prev;         \
    85.     *(elm2)->field.tqe_prev = (elm2);               \
    86.     _Q_INVALIDATE((elm)->field.tqe_prev);               \
    87.     _Q_INVALIDATE((elm)->field.tqe_next);               \
    88. } while (0)
    89. #define TAILQ_FOREACH(var, head, field)                 \
    90.     for ((var) = ((head)->tqh_first);               \
    91.         (var);                          \
    92.         (var) = ((var)->field.tqe_next))
    93.  
    94. #define TAILQ_FOREACH_REVERSE(var, head, headname, field)       \
    95.     for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));    \
    96.         (var);                          \
    97.         (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
    98.  
    99. #define TAILQ_CONCAT(head1, head2, field) do {              \
    100.     if (!TAILQ_EMPTY(head2)) {                  \
    101.         *(head1)->tqh_last = (head2)->tqh_first;        \
    102.         (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
    103.         (head1)->tqh_last = (head2)->tqh_last;          \
    104.         TAILQ_INIT((head2));                    \
    105.     }                               \
    106. } while (/*CONSTCOND*/0)
    107.  
    108. /*
    109.  * Tail queue access methods.
    110.  */
    111. #define TAILQ_EMPTY(head)       ((head)->tqh_first == NULL)
    112. #define TAILQ_FIRST(head)       ((head)->tqh_first)
    113. #define TAILQ_NEXT(elm, field)      ((elm)->field.tqe_next)
    114.  
    115. #define TAILQ_LAST(head, headname) \
    116.     (*(((struct headname *)((head)->tqh_last))->tqh_last))
    117. #define TAILQ_PREV(elm, headname, field) \
    118.     (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
    119. #endif /* B4EDBD16_2948_4595_9135_6BBBAF9B6341 */

    利用这个宏实现的小例子：

    1. typedef struct _stu {
    2.  char name[54];
    3.  int age;
    4.         // 在链表成员中的使用
    5.  TAILQ_ENTRY(_stu) next;
    6. } stu;
    7.  
    8. typedef struct _sch {
    9.         // 链表
    10.  TAILQ_HEAD(_stu_head, _stu) stu_list;
    11. } sch;
    12.  
    13.  
    14. int main(int argc, char **argv)
    15. {
    16.  sch *psch = (sch *)calloc(1, sizeof(sch));
    17.          // 链表初始化
    18.  TAILQ_INIT(& (psch->stu_list));
    19.  
    20.  stu s1 = {.name = "s1", .age = 1};
    21.  stu s2 = {.name = "s2", .age = 2};
    22.  stu s3 = {.name = "s3", .age = 3};
    23.  stu s4 = {.name = "s4", .age = 4};
    24.  stu s5 = {.name = "s5", .age = 5};
    25.  stu s6 = {.name = "s6", .age = 6};
    26.  
    27.          // 在list前面插入
    28.  TAILQ_INSERT_HEAD(&(psch->stu_list), &s1, next);
    29.  TAILQ_INSERT_HEAD(&(psch->stu_list), &s2, next);
    30.  
    31.         // 在list的队尾插入
    32.  TAILQ_INSERT_TAIL(&(psch->stu_list), &s3, next);
    33.  TAILQ_INSERT_TAIL(&(psch->stu_list), &s5, next);
    34.  
    35.         // 在特定元素前面插入
    36.  TAILQ_INSERT_BEFORE(&s5, &s4, next);
    37.  TAILQ_INSERT_TAIL(&(psch->stu_list), &s6, next);
    38.   printf("queue_head:%p, first:%p, last:%p\n", (void*)&(psch->stu_list), (void*)(psch->stu_list).tqh_first, (void*)(psch->stu_list).tqh_last);
    39.  
    40.  stu *p = NULL;
    41.          // 正向遍历
    42.  TAILQ_FOREACH(p, &(psch->stu_list), next) {
    43.     printf("item:%p, next:%p, &next:%p, prev:%p, *prev:%p\n", p,p->next.tqe_next, &p->next.tqe_next,p->next.tqe_prev,& p->next.tqe_prev);
    44.   printf("name:%s\t age:%d\n", p->name, p->age);
    45.  }
    46.  printf("---------------------------------\n");
    47.  
    48.        // 反向遍历
    49.  TAILQ_FOREACH_REVERSE(p, &(psch->stu_list), _stu_head, next) {
    50.   printf("name:%s\t age:%d\n", p->name, p->age);
    51.  } 
    52.         free(psch);
    53.  return 0;
    54. }

    三 示意图说明

    3.1 获取链表的最后一个元素

    上述链表的示意图如下：f858d1607a8734b495834fabe8b0160b.png

    注意这个链表和我们一般自己在初学c语言的链表不一样，这个里面的tqe_prev指向的不是前一个元素，而是指向前一个元素的tqe_next, 注意这个tqe_next是在stu里面的next的成员里面的。

    这个宏有个比较难以理解的地方，就是得到最后一个元素和得到前一个元素：

    1. #define TAILQ_LAST(head, headname) \
    2.     (*(((struct headname *)((head)->tqh_last))->tqh_last))
    3. #define TAILQ_PREV(elm, headname, field) \
    4.     (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

    我们拿一个来解释TAILQ_LAST，如下图展示： 假如有如下的list：e8d0056196b709fb2ae0bb55e83eb562.png获取最后一个元素的示意图如下：0e18772023272d1a8f92190100aa5ec1.png

    TAILQ_LAST分为两步：

    1. 1. 获取tqh_last 指针，即指到最后一个元素的tqe_next;
    2. 2. 通过最后一个元素的tqe_next 获取到指向最后一个元素即绿色的stu的地址。

    第一步很容易理解，通过(head)->tqh_last 获取到最后一个元素的tqe_next. 第二步很难理解，因为它把这个地址强制转成队列，成员怎么转成队列那，那是因为两个都是指针，指针的大小都是一样的，而且都是两个指针变量，所以可以互转，转了之后可以看到如上图的对应关系,tqe_next 变成了队列的tqh_first 了、同样tqe_prev也就变成了tqh_last,而tqh_last 即tqe_prev指向黄色元素的tqe_next了，然后通过* 取值即变成了绿色的stu的地址，即最后一个元素的地址了。

    3.2 插入元素

    1. #define TAILQ_INSERT_TAIL(head, elm, field) do {            \
    2.     (elm)->field.tqe_next = NULL;                   \
    3.     (elm)->field.tqe_prev = (head)->tqh_last;           \
    4.     *(head)->tqh_last = (elm);                  \
    5.     (head)->tqh_last = &(elm)->field.tqe_next;          \
    6. } while (/*CONSTCOND*/0)

    再画个插入的示意图：1f9c12d29b1628bf6ec23ad9a4ba538a.png

    插入一个元素：1c65cda56e6844697ef7ae5efeb06703.png线条上的数字即插入的顺序。

    再次插入一个元素：fb4c4742ce146aabff499d38ec14f49a.png

    最终形成的链表：672d1c1fb776800827eed67a2312f5a6.png

    3.3 宏调试相关

    宏在调试之前，我们可以先通过gcc命令进行展开,可以获取到展开宏的源码。

    gcc -E -P main.c > main.expand.c

    在gdb调试的时候，可以通过：

    gdb) macro expand 宏

    gcc编译的时候、添加-g3 便于调试宏

    gcc -g3

    四 参考

    1. https://www.361shipin.com/blog/1534986025145729024
    2. https://www.getdami.com/questions/wei-dui-lie-dai-ma-zhong-de-tailq_lastzen-yao-li-jie-89811/
  • 相关阅读:
    知识点滴 - 什么是AIoT
    （附源码）python方块新闻网站 毕业设计 091600
    NPM 常用命令（一）
    genius-storage使用文档，一个浏览器缓存工具
    JavaString类中的常用方法
    混合整数规划（Mixed Integer Programming）
    Linux：多线程概念 | Windows的线程 | 线程的优缺点 | 进程与线程 | 线程控制 | 线程创建 | 线程终止 | 线程等待 | 分离线程
    MyBatisPlus之基础CRUD（增删改查操作）
    【HarmonyOS学习笔记】Slider组件实现图形可调旋转
    JVMの内存泄漏&内存溢出案例分析
  • 原文地址：https://blog.csdn.net/mseaspring/article/details/127131021