2023面试高手

这个屌丝很懒，什么也没留下！

热门标签

Linux内核队列queue.h

作者：2023面试高手 | 2024-03-02 17:35:26

踩

Linux内核队列queue.h

文章目录

一、简介
二、SLIST单向无尾链表
三、STAILQ单向有尾链表
四、LIST双向无尾链表
五、TAILQ双向有尾链表
六、CIRCLEQ循环链表
七、queue源码
参考

一、简介

queue.h是一个非常经典的文件，定义了一系列宏的操作，它定义了一系列的宏操作，实现了链表，尾队列和循环链表。
queue.h定义了5个基本的数据类型：

单向无尾链表
单向有尾链表
双向无尾链表
双向有尾链表
循环链表

queue相关链表/队列的使用流程为：

定义自己的结构体
在结构体中使用XXXX_ENTRY定义链表/队列成员变量
使用XXXX_HEAD定义一个链表/队列头
使用XXXX_INIT初始化链表/队列头（也可在定义时初始化）
使用相关的INSERT、REMOVE、FOREACH、REPLACE方法操作队列

几种类型支持的操作：
在这里插入图片描述

二、SLIST单向无尾链表

2.1 介绍

SLIST是Singly-linked List的缩写，意为单向无尾链表。
在这里插入图片描述
SLIST适合数据量非常大并且几乎不需要删除数据的场合，或者当作堆栈使用。
SLIST相关的源码：

/*
 * Singly-linked List definitions.
 */
#define SLIST_HEAD(name, type)                                              \
struct name {                                                               \
    struct type *slh_first; /* first element */                             \
}

#define SLIST_HEAD_INITIALIZER(head)                                        \
    { NULL }

#define SLIST_ENTRY(type)                                                   \
struct {                                                                    \
    struct type *sle_next;  /* next element */                              \
}

/*
 * Singly-linked List functions.
 */
#define SLIST_INIT(head) do {                                               \
    (head)->slh_first = NULL;                                               \
} while (/*CONSTCOND*/0)

#define SLIST_INSERT_AFTER(slistelm, elm, field) do {                       \
    (elm)->field.sle_next = (slistelm)->field.sle_next;                     \
    (slistelm)->field.sle_next = (elm);                                     \
} while (/*CONSTCOND*/0)

#define SLIST_INSERT_HEAD(head, elm, field) do {                            \
    (elm)->field.sle_next = (head)->slh_first;                              \
    (head)->slh_first = (elm);                                              \
} while (/*CONSTCOND*/0)

#define SLIST_REMOVE_HEAD(head, field) do {                                 \
    (head)->slh_first = (head)->slh_first->field.sle_next;                  \
} while (/*CONSTCOND*/0)

#define SLIST_REMOVE(head, elm, type, field) do {                           \
    if ((head)->slh_first == (elm)) {                                       \
        SLIST_REMOVE_HEAD((head), field);                                   \
    }                                                                       \
    else {                                                                  \
        struct type *curelm = (head)->slh_first;                            \
        while(curelm->field.sle_next != (elm))                              \
            curelm = curelm->field.sle_next;                                \
        curelm->field.sle_next =                                            \
            curelm->field.sle_next->field.sle_next;                         \
    }                                                                       \
} while (/*CONSTCOND*/0)

#define SLIST_FOREACH(var, head, field)                                     \
    for ((var) = SLIST_FIRST((head));                                       \
        (var);                                                              \
        (var) = SLIST_NEXT((var), field) )

#define SLIST_FOREACH_PREVPTR(var, varp, head, field)                       \
    for ((varp) = &SLIST_FIRST((head));                                     \
        ((var) = *(varp)) != NULL;                                          \
        (varp) = &SLIST_NEXT((var), field) )

/*
 * Singly-linked List access methods.
 */
#define SLIST_EMPTY(head)       ((head)->slh_first == NULL)
#define SLIST_FIRST(head)       ((head)->slh_first)
#define SLIST_NEXT(elm, field)  ((elm)->field.sle_next)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

2.2 操作

与单向链表相关的宏、方法和函数有：

// definitions
SLIST_HEAD(name, type)
SLIST_HEAD_INITIALIZER(head)
SLIST_ENTRY(type)
// access methods
SLIST_FIRST(head)
SLIST_END(head)
SLIST_EMPTY(head)
SLIST_NEXT(elm, field)
LIST_FOREACH(var, head, field)
SLIST_FOREACH_PREVPTR(var, varp, head, field)
// functions
SLIST_INIT(head)
SLIST_INSERT_AFTER(slistelm, elm, field)
SLIST_INSERT_HEAD(head, elm, field)
SLIST_REMOVE_NEXT(head, elm, field)
SLIST_REMOVE_HEAD(head, field)
SLIST_REMOVE(head, elm, type, field)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

宏定义说明

SLIST_HEAD用于定义一个单向链表数据结构体的头变量，该结构体只有一个指针成员slh_first，指向第一个type类型的数据结构；name可以不用（填写）；
SLIST_HEAD_INITIALIZER用于在定义时初始化SLIST_HEAD定义的数据结构体的头变量；head可以不用填写;
SLIST_ENTRY则用于定义一个（用户）结构体的成员变量，该成员变量只包含一个指向type类型的指针sle_next；

与单向链表相关的访问方法有6个

SLIST_FIRST用于获取单向链表的第一个元素；
SLIST_END定义了尾部的判断标准；
SLIST_EMPTY用于判断单向链表是否为空：空则返回true，否则返回false；
SLIST_NEXT用于获取elm元素的下一个元素，field是前面用SLIST_ENTRY定义的成员变量名；
SLIST_FOREACH用于遍历单向链表，var是临时变量，head是链表头指针（SLIST_HEAD定义的变量），field是SLIST_ENTRY定义的成员变量名；
SLIST_FOREACH_PREVPTR与SLIST_FOREACH类似，用于遍历单向链表，不过提供更多的一个临时指针变量varp，指向var指向元素的地址；

与单向链表相关的函数有6个

SLIST_INIT用于初始化SLIST_HEAD定义的头指针变量；当然也可以在使用SLIST_HEAD定义头指针变量时同时使用SLIST_HEAD_INITIALIZER进行初始化；
SLIST_INSERT_AFTER用于将元素elm插入到当前链表元素slistelm的后面；
SLIST_INSERT_HEAD用于将元素elm插入到当前链表head的头部；head是SLIST_HEAD定义的链表头指针；
SLIST_REMOVE_NEXT用于将elm后面的元素删除，head未使用；注意删除时判断elm后面是否还有元素，否则会崩溃;
SLIST_REMOVE_HEAD用于删除第一个元素；注意删除时判断head是否为空，否则会崩溃;
SLIST_REMOVE用于从head链表中删除elm元素；注意首先判断elm元素是否在head链表中，否则会崩溃；

2.3 例子

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

struct SLIST_ITEM {
    int value;
    SLIST_ENTRY(SLIST_ITEM) entry;
};
int main(void) {
    int i;
    SLIST_HEAD(,SLIST_ITEM) slist_head;
    SLIST_INIT(&slist_head);
    if (SLIST_EMPTY(&slist_head))
        printf("single list is empty\n");
    struct SLIST_ITEM *item;
    struct SLIST_ITEM *item_temp;
    for( i = 0; i < 10; i += 1)
    {
            item = (struct SLIST_ITEM *)malloc(sizeof(struct SLIST_ITEM));
            item->value = i;
            item->entry.sle_next = NULL;
            SLIST_INSERT_HEAD(&slist_head, item, entry);
    }
    printf("after insert 10 item to single list:\n");
    SLIST_FOREACH(item, &slist_head, entry)
            printf("item value = %d\n", item->value);
    

    while( SLIST_EMPTY(&slist_head) == 0 ){
            item_temp = (&slist_head)->slh_first;
            SLIST_REMOVE(&slist_head,(&slist_head)->slh_first,SLIST_ITEM,entry);
            free(item_temp);
    }

    printf("here");
    if ( SLIST_EMPTY(&slist_head) )
            printf("single list is empty\n");        
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

在这里插入图片描述

SLIST_INSERT_HEAD(&slist_head, item, entry)
从头部插入元素，第一个参数为头节点，第一个参数为要插入的元素，第三个参数为自定义结构体中，自定义的SLIST_ENTRY(SLIST_ITEM)结构体变量名称。
SLIST_REMOVE(&slist_head,(&slist_head)->slh_first,SLIST_ITEM,entry)
删除对应元素( 内部仅是指针指向的改变，没有真正释放空间 )

三、STAILQ单向有尾链表

STAILQ 是 Singly-linked Tail queue 的缩写，意为单向有尾链表。有尾链表可作队列使用。
在这里插入图片描述
STAILQ相关的源码

/*
 * Singly-linked Tail queue declarations.
 */
#define STAILQ_HEAD(name, type)                                             \
struct name {                                                               \
    struct type *stqh_first;    /* first element */                         \
    struct type **stqh_last;    /* addr of last next element */             \
}

#define STAILQ_HEAD_INITIALIZER(head)                                       \
    { NULL, &(head).stqh_first }

#define STAILQ_ENTRY(type)                                                  \
struct {                                                                    \
    struct type *stqe_next; /* next element */                              \
}

/*
 * Singly-linked Tail queue functions.
 */
#define STAILQ_INIT(head) do {                                              \
    (head)->stqh_first = NULL;                                              \
    (head)->stqh_last = &(head)->stqh_first;                                \
} while (/*CONSTCOND*/0)

#define STAILQ_INSERT_HEAD(head, elm, field) do {                           \
    if (((elm)->field.stqe_next = (head)->stqh_first) == NULL)              \
        (head)->stqh_last = &(elm)->field.stqe_next;                        \
    (head)->stqh_first = (elm);                                             \
} while (/*CONSTCOND*/0)

#define STAILQ_INSERT_TAIL(head, elm, field) do {                           \
    (elm)->field.stqe_next = NULL;                                          \
    *(head)->stqh_last = (elm);                                             \
    (head)->stqh_last = &(elm)->field.stqe_next;                            \
} while (/*CONSTCOND*/0)

#define STAILQ_INSERT_AFTER(head, listelm, elm, field) do {                 \
    if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)      \
        (head)->stqh_last = &(elm)->field.stqe_next;                        \
    (listelm)->field.stqe_next = (elm);                                     \
} while (/*CONSTCOND*/0)

#define STAILQ_REMOVE_HEAD(head, field) do {                                \
    if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \
        (head)->stqh_last = &(head)->stqh_first;                            \
} while (/*CONSTCOND*/0)

#define STAILQ_REMOVE(head, elm, type, field) do {                          \
    if ((head)->stqh_first == (elm)) {                                      \
        STAILQ_REMOVE_HEAD((head), field);                                  \
    } else {                                                                \
        struct type *curelm = (head)->stqh_first;                           \
        while (curelm->field.stqe_next != (elm))                            \
            curelm = curelm->field.stqe_next;                               \
        if ((curelm->field.stqe_next =                                      \
            curelm->field.stqe_next->field.stqe_next) == NULL)              \
                (head)->stqh_last = &(curelm)->field.stqe_next;             \
    }                                                                       \
} while (/*CONSTCOND*/0)

#define STAILQ_FOREACH(var, head, field)                                    \
    for ((var) = ((head)->stqh_first);                                      \
        (var);                                                              \
        (var) = ((var)->field.stqe_next))

#define STAILQ_CONCAT(head1, head2) do {                                    \
    if (!STAILQ_EMPTY((head2))) {                                           \
        *(head1)->stqh_last = (head2)->stqh_first;                          \
        (head1)->stqh_last = (head2)->stqh_last;                            \
        STAILQ_INIT((head2));                                               \
    }                                                                       \
} while (/*CONSTCOND*/0)

/*
 * Singly-linked Tail queue access methods.
 */
#define STAILQ_EMPTY(head)          ((head)->stqh_first == NULL)
#define STAILQ_FIRST(head)          ((head)->stqh_first)
#define STAILQ_NEXT(elm, field)     ((elm)->field.stqe_next)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

四、LIST双向无尾链表

双向链表有前向的指针，因此可以执行一些前向操作，而且无需遍历链表便可以删除一些节点。
在这里插入图片描述
LIST相关的源码

/*
 * List definitions.
 */
#define LIST_HEAD(name, type)                                               \
struct name {                                                               \
    struct type *lh_first;  /* first element */                             \
}

#define LIST_HEAD_INITIALIZER(head)                                         \
    { NULL }

#define LIST_ENTRY(type)                                                    \
struct {                                                                    \
    struct type *le_next;   /* next element */                              \
    struct type **le_prev;  /* address of previous next element */          \
}

/*
 * List functions.
 */
#define LIST_INIT(head) do {                                                \
    (head)->lh_first = NULL;                                                \
} while (/*CONSTCOND*/0)

#define LIST_INSERT_AFTER(listelm, elm, field) do {                         \
    if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)          \
        (listelm)->field.le_next->field.le_prev =                           \
            &(elm)->field.le_next;                                          \
    (listelm)->field.le_next = (elm);                                       \
    (elm)->field.le_prev = &(listelm)->field.le_next;                       \
} while (/*CONSTCOND*/0)

#define LIST_INSERT_BEFORE(listelm, elm, field) do {                        \
    (elm)->field.le_prev = (listelm)->field.le_prev;                        \
    (elm)->field.le_next = (listelm);                                       \
    *(listelm)->field.le_prev = (elm);                                      \
    (listelm)->field.le_prev = &(elm)->field.le_next;                       \
} while (/*CONSTCOND*/0)

#define LIST_INSERT_HEAD(head, elm, field) do {                             \
    if (((elm)->field.le_next = (head)->lh_first) != NULL)                  \
        (head)->lh_first->field.le_prev = &(elm)->field.le_next;            \
    (head)->lh_first = (elm);                                               \
    (elm)->field.le_prev = &(head)->lh_first;                               \
} while (/*CONSTCOND*/0)

#define LIST_REMOVE(elm, field) do {                                        \
    if ((elm)->field.le_next != NULL)                                       \
        (elm)->field.le_next->field.le_prev =                               \
            (elm)->field.le_prev;                                           \
    *(elm)->field.le_prev = (elm)->field.le_next;                           \
} while (/*CONSTCOND*/0)

#define LIST_FOREACH(var, head, field)                                      \
    for ((var) = ((head)->lh_first);                                        \
        (var);                                                              \
        (var) = ((var)->field.le_next))

/*
 * List access methods.
 */
#define LIST_EMPTY(head)        ((head)->lh_first == NULL)
#define LIST_FIRST(head)        ((head)->lh_first)
#define LIST_NEXT(elm, field)   ((elm)->field.le_next)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

五、TAILQ双向有尾链表

TAILQ 是 Tail queue 的缩写，意为双向有尾链表。
有尾链表可作队列使用。
双向有尾链表兼具了双向链表和有尾链表的特点。
在这里插入图片描述
TAILQ相关的源码

/*
 * Tail queue definitions.
 */
#define TAILQ_HEAD(name, type)                                              \
struct name {                                                               \
    struct type *tqh_first;     /* first element */                         \
    struct type **tqh_last;     /* addr of last next element */             \
}

#define TAILQ_HEAD_INITIALIZER(head)                                        \
    { NULL, &(head).tqh_first }

#define TAILQ_ENTRY(type)                                                   \
struct {                                                                    \
    struct type *tqe_next;      /* next element */                          \
    struct type **tqe_prev;     /* address of previous next element */      \
}

/*
 * Tail queue functions.
 */
#define TAILQ_INIT(head) do {                                               \
    (head)->tqh_first = NULL;                                               \
    (head)->tqh_last = &(head)->tqh_first;                                  \
} while (/*CONSTCOND*/0)

#define TAILQ_INSERT_HEAD(head, elm, field) do {                            \
    if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)                \
        (head)->tqh_first->field.tqe_prev = &(elm)->field.tqe_next;         \
    else                                                                    \
        (head)->tqh_last = &(elm)->field.tqe_next;                          \
    (head)->tqh_first = (elm);                                              \
    (elm)->field.tqe_prev = &(head)->tqh_first;                             \
} while (/*CONSTCOND*/0)

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

#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {                  \
    if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)        \
        (elm)->field.tqe_next->field.tqe_prev = &(elm)->field.tqe_next;     \
    else                                                                    \
        (head)->tqh_last = &(elm)->field.tqe_next;                          \
    (listelm)->field.tqe_next = (elm);                                      \
    (elm)->field.tqe_prev = &(listelm)->field.tqe_next;                     \
} while (/*CONSTCOND*/0)

#define TAILQ_INSERT_BEFORE(listelm, elm, field) do {                       \
    (elm)->field.tqe_prev = (listelm)->field.tqe_prev;                      \
    (elm)->field.tqe_next = (listelm);                                      \
    *(listelm)->field.tqe_prev = (elm);                                     \
    (listelm)->field.tqe_prev = &(elm)->field.tqe_next;                     \
} while (/*CONSTCOND*/0)

#define TAILQ_REMOVE(head, elm, field) do {                                 \
    if (((elm)->field.tqe_next) != NULL)                                    \
        (elm)->field.tqe_next->field.tqe_prev = (elm)->field.tqe_prev;      \
    else                                                                    \
        (head)->tqh_last = (elm)->field.tqe_prev;                           \
    *(elm)->field.tqe_prev = (elm)->field.tqe_next;                         \
} while (/*CONSTCOND*/0)

#define TAILQ_FOREACH(var, head, field)                                     \
    for ((var) = ((head)->tqh_first);                                       \
        (var);                                                              \
        (var) = ((var)->field.tqe_next))

#define TAILQ_FOREACH_REVERSE(var, head, headname, field)                   \
    for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));    \
        (var);                                                              \
        (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))

#define TAILQ_CONCAT(head1, head2, field) do {                              \
    if (!TAILQ_EMPTY(head2)) {                                              \
        *(head1)->tqh_last = (head2)->tqh_first;                            \
        (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;             \
        (head1)->tqh_last = (head2)->tqh_last;                              \
        TAILQ_INIT((head2));                                                \
    }                                                                       \
} while (/*CONSTCOND*/0)

/*
 * Tail queue access methods.
 */
#define TAILQ_EMPTY(head)       ((head)->tqh_first == NULL)
#define TAILQ_FIRST(head)       ((head)->tqh_first)
#define TAILQ_NEXT(elm, field)  ((elm)->field.tqe_next)

#define TAILQ_LAST(head, headname)                                          \
    (*(((struct headname *)((head)->tqh_last))->tqh_last))

#define TAILQ_PREV(elm, headname, field)                                    \
    (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

六、CIRCLEQ循环链表

CIRCLEQ 是 Circular queue 的缩写，意为循环链表。
在这里插入图片描述
CIRCLEQ相关的源码

/*
 * Circular queue definitions.
 */
#define CIRCLEQ_HEAD(name, type)                                            \
struct name {                                                               \
    struct type *cqh_first;     /* first element */                         \
    struct type *cqh_last;      /* last element */                          \
}

#define CIRCLEQ_HEAD_INITIALIZER(head)                                      \
    { (void *)&head, (void *)&head }

#define CIRCLEQ_ENTRY(type)                                                 \
struct {                                                                    \
    struct type *cqe_next;      /* next element */                          \
    struct type *cqe_prev;      /* previous element */                      \
}

/*
 * Circular queue functions.
 */
#define CIRCLEQ_INIT(head) do {                                             \
    (head)->cqh_first = (void *)(head);                                     \
    (head)->cqh_last = (void *)(head);                                      \
} while (/*CONSTCOND*/0)

#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {                \
    (elm)->field.cqe_next = (listelm)->field.cqe_next;                      \
    (elm)->field.cqe_prev = (listelm);                                      \
    if ((listelm)->field.cqe_next == (void *)(head))                        \
        (head)->cqh_last = (elm);                                           \
    else                                                                    \
        (listelm)->field.cqe_next->field.cqe_prev = (elm);                  \
    (listelm)->field.cqe_next = (elm);                                      \
} while (/*CONSTCOND*/0)

#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {               \
    (elm)->field.cqe_next = (listelm);                                      \
    (elm)->field.cqe_prev = (listelm)->field.cqe_prev;                      \
    if ((listelm)->field.cqe_prev == (void *)(head))                        \
        (head)->cqh_first = (elm);                                          \
    else                                                                    \
        (listelm)->field.cqe_prev->field.cqe_next = (elm);                  \
    (listelm)->field.cqe_prev = (elm);                                      \
} while (/*CONSTCOND*/0)

#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {                          \
    (elm)->field.cqe_next = (head)->cqh_first;                              \
    (elm)->field.cqe_prev = (void *)(head);                                 \
    if ((head)->cqh_last == (void *)(head))                                 \
        (head)->cqh_last = (elm);                                           \
    else                                                                    \
        (head)->cqh_first->field.cqe_prev = (elm);                          \
    (head)->cqh_first = (elm);                                              \
} while (/*CONSTCOND*/0)

#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {                          \
    (elm)->field.cqe_next = (void *)(head);                                 \
    (elm)->field.cqe_prev = (head)->cqh_last;                               \
    if ((head)->cqh_first == (void *)(head))                                \
        (head)->cqh_first = (elm);                                          \
    else                                                                    \
        (head)->cqh_last->field.cqe_next = (elm);                           \
    (head)->cqh_last = (elm);                                               \
} while (/*CONSTCOND*/0)

#define CIRCLEQ_REMOVE(head, elm, field) do {                               \
    if ((elm)->field.cqe_next == (void *)(head))                            \
        (head)->cqh_last = (elm)->field.cqe_prev;                           \
    else                                                                    \
        (elm)->field.cqe_next->field.cqe_prev = (elm)->field.cqe_prev;      \
    if ((elm)->field.cqe_prev == (void *)(head))                            \
        (head)->cqh_first = (elm)->field.cqe_next;                          \
    else                                                                    \
        (elm)->field.cqe_prev->field.cqe_next = (elm)->field.cqe_next;      \
} while (/*CONSTCOND*/0)

#define CIRCLEQ_FOREACH(var, head, field)                                   \
    for ((var) = ((head)->cqh_first);                                       \
        (var) != (const void *)(head);                                      \
        (var) = ((var)->field.cqe_next))

#define CIRCLEQ_FOREACH_REVERSE(var, head, field)                           \
    for ((var) = ((head)->cqh_last);                                        \
        (var) != (const void *)(head);                                      \
        (var) = ((var)->field.cqe_prev))

/*
 * Circular queue access methods.
 */
#define CIRCLEQ_EMPTY(head)         ((head)->cqh_first == (void *)(head))
#define CIRCLEQ_FIRST(head)         ((head)->cqh_first)
#define CIRCLEQ_LAST(head)          ((head)->cqh_last)
#define CIRCLEQ_NEXT(elm, field)    ((elm)->field.cqe_next)
#define CIRCLEQ_PREV(elm, field)    ((elm)->field.cqe_prev)

#define CIRCLEQ_LOOP_NEXT(head, elm, field)                                 \
    (((elm)->field.cqe_next == (void *)(head))                              \
        ? ((head)->cqh_first)                                               \
        : (elm->field.cqe_next))

#define CIRCLEQ_LOOP_PREV(head, elm, field)                                 \
    (((elm)->field.cqe_prev == (void *)(head))                              \
        ? ((head)->cqh_last)                                                \
        : (elm->field.cqe_prev))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

七、queue源码

在Linux系统中的路径为：/usr/include/sys/queue.h
也可以通过如下网址查看：https://codebrowser.dev/glibc/glibc/misc/sys/queue.h.html
queue.h

/*
 * Copyright (c) 1991, 1993
 *        The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *        @(#)queue.h        8.5 (Berkeley) 8/20/94
 */
#ifndef        _QUEUE_H_
#define        _QUEUE_H_
/*
 * This file defines five types of data structures: singly-linked lists,
 * lists, simple queues, tail queues, and circular queues.
 *
 * A singly-linked list is headed by a single forward pointer. The
 * elements are singly linked for minimum space and pointer manipulation
 * overhead at the expense of O(n) removal for arbitrary elements. New
 * elements can be added to the list after an existing element or at the
 * head of the list.  Elements being removed from the head of the list
 * should use the explicit macro for this purpose for optimum
 * efficiency. A singly-linked list may only be traversed in the forward
 * direction.  Singly-linked lists are ideal for applications with large
 * datasets and few or no removals or for implementing a LIFO queue.
 *
 * A list is headed by a single forward pointer (or an array of forward
 * pointers for a hash table header). The elements are doubly linked
 * so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before
 * or after an existing element or at the head of the list. A list
 * may only be traversed in the forward direction.
 *
 * A simple queue is headed by a pair of pointers, one the head of the
 * list and the other to the tail of the list. The elements are singly
 * linked to save space, so elements can only be removed from the
 * head of the list. New elements can be added to the list after
 * an existing element, at the head of the list, or at the end of the
 * list. A simple queue may only be traversed in the forward direction.
 *
 * A tail queue is headed by a pair of pointers, one to the head of the
 * list and the other to the tail of the list. The elements are doubly
 * linked so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before or
 * after an existing element, at the head of the list, or at the end of
 * the list. A tail queue may be traversed in either direction.
 *
 * A circle queue is headed by a pair of pointers, one to the head of the
 * list and the other to the tail of the list. The elements are doubly
 * linked so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before or after
 * an existing element, at the head of the list, or at the end of the list.
 * A circle queue may be traversed in either direction, but has a more
 * complex end of list detection.
 *
 * For details on the use of these macros, see the queue(3) manual page.
 */
/*
 * List definitions.
 */
#define        LIST_HEAD(name, type)                                                \
struct name {                                                                \
        struct type *lh_first;        /* first element */                        \
}
#define        LIST_HEAD_INITIALIZER(head)                                        \
        { NULL }
#define        LIST_ENTRY(type)                                                \
struct {                                                                \
        struct type *le_next;        /* next element */                        \
        struct type **le_prev;        /* address of previous next element */        \
}
/*
 * List functions.
 */
#define        LIST_INIT(head) do {                                                \
        (head)->lh_first = NULL;                                        \
} while (/*CONSTCOND*/0)
#define        LIST_INSERT_AFTER(listelm, elm, field) do {                        \
        if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)        \
                (listelm)->field.le_next->field.le_prev =                \
                    &(elm)->field.le_next;                                \
        (listelm)->field.le_next = (elm);                                \
        (elm)->field.le_prev = &(listelm)->field.le_next;                \
} while (/*CONSTCOND*/0)
#define        LIST_INSERT_BEFORE(listelm, elm, field) do {                        \
        (elm)->field.le_prev = (listelm)->field.le_prev;                \
        (elm)->field.le_next = (listelm);                                \
        *(listelm)->field.le_prev = (elm);                                \
        (listelm)->field.le_prev = &(elm)->field.le_next;                \
} while (/*CONSTCOND*/0)
#define        LIST_INSERT_HEAD(head, elm, field) do {                                \
        if (((elm)->field.le_next = (head)->lh_first) != NULL)                \
                (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
        (head)->lh_first = (elm);                                        \
        (elm)->field.le_prev = &(head)->lh_first;                        \
} while (/*CONSTCOND*/0)
#define        LIST_REMOVE(elm, field) do {                                        \
        if ((elm)->field.le_next != NULL)                                \
                (elm)->field.le_next->field.le_prev =                         \
                    (elm)->field.le_prev;                                \
        *(elm)->field.le_prev = (elm)->field.le_next;                        \
} while (/*CONSTCOND*/0)
#define        LIST_FOREACH(var, head, field)                                        \
        for ((var) = ((head)->lh_first);                                \
                (var);                                                        \
                (var) = ((var)->field.le_next))
/*
 * List access methods.
 */
#define        LIST_EMPTY(head)                ((head)->lh_first == NULL)
#define        LIST_FIRST(head)                ((head)->lh_first)
#define        LIST_NEXT(elm, field)                ((elm)->field.le_next)
/*
 * Singly-linked List definitions.
 */
#define        SLIST_HEAD(name, type)                                                \
struct name {                                                                \
        struct type *slh_first;        /* first element */                        \
}
#define        SLIST_HEAD_INITIALIZER(head)                                        \
        { NULL }
#define        SLIST_ENTRY(type)                                                \
struct {                                                                \
        struct type *sle_next;        /* next element */                        \
}
/*
 * Singly-linked List functions.
 */
#define        SLIST_INIT(head) do {                                                \
        (head)->slh_first = NULL;                                        \
} while (/*CONSTCOND*/0)
#define        SLIST_INSERT_AFTER(slistelm, elm, field) do {                        \
        (elm)->field.sle_next = (slistelm)->field.sle_next;                \
        (slistelm)->field.sle_next = (elm);                                \
} while (/*CONSTCOND*/0)
#define        SLIST_INSERT_HEAD(head, elm, field) do {                        \
        (elm)->field.sle_next = (head)->slh_first;                        \
        (head)->slh_first = (elm);                                        \
} while (/*CONSTCOND*/0)
#define        SLIST_REMOVE_HEAD(head, field) do {                                \
        (head)->slh_first = (head)->slh_first->field.sle_next;                \
} while (/*CONSTCOND*/0)
#define        SLIST_REMOVE(head, elm, type, field) do {                        \
        if ((head)->slh_first == (elm)) {                                \
                SLIST_REMOVE_HEAD((head), field);                        \
        }                                                                \
        else {                                                                \
                struct type *curelm = (head)->slh_first;                \
                while(curelm->field.sle_next != (elm))                        \
                        curelm = curelm->field.sle_next;                \
                curelm->field.sle_next =                                \
                    curelm->field.sle_next->field.sle_next;                \
        }                                                                \
} while (/*CONSTCOND*/0)
#define        SLIST_FOREACH(var, head, field)                                        \
        for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
/*
 * Singly-linked List access methods.
 */
#define        SLIST_EMPTY(head)        ((head)->slh_first == NULL)
#define        SLIST_FIRST(head)        ((head)->slh_first)
#define        SLIST_NEXT(elm, field)        ((elm)->field.sle_next)
/*
 * Singly-linked Tail queue declarations.
 */
#define        STAILQ_HEAD(name, type)                                        \
struct name {                                                                \
        struct type *stqh_first;        /* first element */                        \
        struct type **stqh_last;        /* addr of last next element */                \
}
#define        STAILQ_HEAD_INITIALIZER(head)                                        \
        { NULL, &(head).stqh_first }
#define        STAILQ_ENTRY(type)                                                \
struct {                                                                \
        struct type *stqe_next;        /* next element */                        \
}
/*
 * Singly-linked Tail queue functions.
 */
#define        STAILQ_INIT(head) do {                                                \
        (head)->stqh_first = NULL;                                        \
        (head)->stqh_last = &(head)->stqh_first;                                \
} while (/*CONSTCOND*/0)
#define        STAILQ_INSERT_HEAD(head, elm, field) do {                        \
        if (((elm)->field.stqe_next = (head)->stqh_first) == NULL)        \
                (head)->stqh_last = &(elm)->field.stqe_next;                \
        (head)->stqh_first = (elm);                                        \
} while (/*CONSTCOND*/0)
#define        STAILQ_INSERT_TAIL(head, elm, field) do {                        \
        (elm)->field.stqe_next = NULL;                                        \
        *(head)->stqh_last = (elm);                                        \
        (head)->stqh_last = &(elm)->field.stqe_next;                        \
} while (/*CONSTCOND*/0)
#define        STAILQ_INSERT_AFTER(head, listelm, elm, field) do {                \
        if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\
                (head)->stqh_last = &(elm)->field.stqe_next;                \
        (listelm)->field.stqe_next = (elm);                                \
} while (/*CONSTCOND*/0)
#define        STAILQ_REMOVE_HEAD(head, field) do {                                \
        if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \
                (head)->stqh_last = &(head)->stqh_first;                        \
} while (/*CONSTCOND*/0)
#define        STAILQ_REMOVE(head, elm, type, field) do {                        \
        if ((head)->stqh_first == (elm)) {                                \
                STAILQ_REMOVE_HEAD((head), field);                        \
        } else {                                                        \
                struct type *curelm = (head)->stqh_first;                \
                while (curelm->field.stqe_next != (elm))                        \
                        curelm = curelm->field.stqe_next;                \
                if ((curelm->field.stqe_next =                                \
                        curelm->field.stqe_next->field.stqe_next) == NULL) \
                            (head)->stqh_last = &(curelm)->field.stqe_next; \
        }                                                                \
} while (/*CONSTCOND*/0)
#define        STAILQ_FOREACH(var, head, field)                                \
        for ((var) = ((head)->stqh_first);                                \
                (var);                                                        \
                (var) = ((var)->field.stqe_next))
#define        STAILQ_CONCAT(head1, head2) do {                                \
        if (!STAILQ_EMPTY((head2))) {                                        \
                *(head1)->stqh_last = (head2)->stqh_first;                \
                (head1)->stqh_last = (head2)->stqh_last;                \
                STAILQ_INIT((head2));                                        \
        }                                                                \
} while (/*CONSTCOND*/0)
/*
 * Singly-linked Tail queue access methods.
 */
#define        STAILQ_EMPTY(head)        ((head)->stqh_first == NULL)
#define        STAILQ_FIRST(head)        ((head)->stqh_first)
#define        STAILQ_NEXT(elm, field)        ((elm)->field.stqe_next)
/*
 * Simple queue definitions.
 */
#define        SIMPLEQ_HEAD(name, type)                                        \
struct name {                                                                \
        struct type *sqh_first;        /* first element */                        \
        struct type **sqh_last;        /* addr of last next element */                \
}
#define        SIMPLEQ_HEAD_INITIALIZER(head)                                        \
        { NULL, &(head).sqh_first }
#define        SIMPLEQ_ENTRY(type)                                                \
struct {                                                                \
        struct type *sqe_next;        /* next element */                        \
}
/*
 * Simple queue functions.
 */
#define        SIMPLEQ_INIT(head) do {                                                \
        (head)->sqh_first = NULL;                                        \
        (head)->sqh_last = &(head)->sqh_first;                                \
} while (/*CONSTCOND*/0)
#define        SIMPLEQ_INSERT_HEAD(head, elm, field) do {                        \
        if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)        \
                (head)->sqh_last = &(elm)->field.sqe_next;                \
        (head)->sqh_first = (elm);                                        \
} while (/*CONSTCOND*/0)
#define        SIMPLEQ_INSERT_TAIL(head, elm, field) do {                        \
        (elm)->field.sqe_next = NULL;                                        \
        *(head)->sqh_last = (elm);                                        \
        (head)->sqh_last = &(elm)->field.sqe_next;                        \
} while (/*CONSTCOND*/0)
#define        SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {                \
        if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
                (head)->sqh_last = &(elm)->field.sqe_next;                \
        (listelm)->field.sqe_next = (elm);                                \
} while (/*CONSTCOND*/0)
#define        SIMPLEQ_REMOVE_HEAD(head, field) do {                                \
        if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
                (head)->sqh_last = &(head)->sqh_first;                        \
} while (/*CONSTCOND*/0)
#define        SIMPLEQ_REMOVE(head, elm, type, field) do {                        \
        if ((head)->sqh_first == (elm)) {                                \
                SIMPLEQ_REMOVE_HEAD((head), field);                        \
        } else {                                                        \
                struct type *curelm = (head)->sqh_first;                \
                while (curelm->field.sqe_next != (elm))                        \
                        curelm = curelm->field.sqe_next;                \
                if ((curelm->field.sqe_next =                                \
                        curelm->field.sqe_next->field.sqe_next) == NULL) \
                            (head)->sqh_last = &(curelm)->field.sqe_next; \
        }                                                                \
} while (/*CONSTCOND*/0)
#define        SIMPLEQ_FOREACH(var, head, field)                                \
        for ((var) = ((head)->sqh_first);                                \
                (var);                                                        \
                (var) = ((var)->field.sqe_next))
/*
 * Simple queue access methods.
 */
#define        SIMPLEQ_EMPTY(head)                ((head)->sqh_first == NULL)
#define        SIMPLEQ_FIRST(head)                ((head)->sqh_first)
#define        SIMPLEQ_NEXT(elm, field)        ((elm)->field.sqe_next)
/*
 * Tail queue definitions.
 */
#define        _TAILQ_HEAD(name, type, qual)                                        \
struct name {                                                                \
        qual type *tqh_first;                /* first element */                \
        qual type *qual *tqh_last;        /* addr of last next element */        \
}
#define TAILQ_HEAD(name, type)        _TAILQ_HEAD(name, struct type,)
#define        TAILQ_HEAD_INITIALIZER(head)                                        \
        { NULL, &(head).tqh_first }
#define        _TAILQ_ENTRY(type, qual)                                        \
struct {                                                                \
        qual type *tqe_next;                /* next element */                \
        qual type *qual *tqe_prev;        /* address of previous next element */\
}
#define TAILQ_ENTRY(type)        _TAILQ_ENTRY(struct type,)
/*
 * Tail queue functions.
 */
#define        TAILQ_INIT(head) do {                                                \
        (head)->tqh_first = NULL;                                        \
        (head)->tqh_last = &(head)->tqh_first;                                \
} while (/*CONSTCOND*/0)
#define        TAILQ_INSERT_HEAD(head, elm, field) do {                        \
        if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)        \
                (head)->tqh_first->field.tqe_prev =                        \
                    &(elm)->field.tqe_next;                                \
        else                                                                \
                (head)->tqh_last = &(elm)->field.tqe_next;                \
        (head)->tqh_first = (elm);                                        \
        (elm)->field.tqe_prev = &(head)->tqh_first;                        \
} while (/*CONSTCOND*/0)
#define        TAILQ_INSERT_TAIL(head, elm, field) do {                        \
        (elm)->field.tqe_next = NULL;                                        \
        (elm)->field.tqe_prev = (head)->tqh_last;                        \
        *(head)->tqh_last = (elm);                                        \
        (head)->tqh_last = &(elm)->field.tqe_next;                        \
} while (/*CONSTCOND*/0)
#define        TAILQ_INSERT_AFTER(head, listelm, elm, field) do {                \
        if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
                (elm)->field.tqe_next->field.tqe_prev =                 \
                    &(elm)->field.tqe_next;                                \
        else                                                                \
                (head)->tqh_last = &(elm)->field.tqe_next;                \
        (listelm)->field.tqe_next = (elm);                                \
        (elm)->field.tqe_prev = &(listelm)->field.tqe_next;                \
} while (/*CONSTCOND*/0)
#define        TAILQ_INSERT_BEFORE(listelm, elm, field) do {                        \
        (elm)->field.tqe_prev = (listelm)->field.tqe_prev;                \
        (elm)->field.tqe_next = (listelm);                                \
        *(listelm)->field.tqe_prev = (elm);                                \
        (listelm)->field.tqe_prev = &(elm)->field.tqe_next;                \
} while (/*CONSTCOND*/0)
#define        TAILQ_REMOVE(head, elm, field) do {                                \
        if (((elm)->field.tqe_next) != NULL)                                \
                (elm)->field.tqe_next->field.tqe_prev =                 \
                    (elm)->field.tqe_prev;                                \
        else                                                                \
                (head)->tqh_last = (elm)->field.tqe_prev;                \
        *(elm)->field.tqe_prev = (elm)->field.tqe_next;                        \
} while (/*CONSTCOND*/0)
#define        TAILQ_FOREACH(var, head, field)                                        \
        for ((var) = ((head)->tqh_first);                                \
                (var);                                                        \
                (var) = ((var)->field.tqe_next))
#define        TAILQ_FOREACH_REVERSE(var, head, headname, field)                \
        for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));        \
                (var);                                                        \
                (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
#define        TAILQ_CONCAT(head1, head2, field) do {                                \
        if (!TAILQ_EMPTY(head2)) {                                        \
                *(head1)->tqh_last = (head2)->tqh_first;                \
                (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;        \
                (head1)->tqh_last = (head2)->tqh_last;                        \
                TAILQ_INIT((head2));                                        \
        }                                                                \
} while (/*CONSTCOND*/0)
/*
 * Tail queue access methods.
 */
#define        TAILQ_EMPTY(head)                ((head)->tqh_first == NULL)
#define        TAILQ_FIRST(head)                ((head)->tqh_first)
#define        TAILQ_NEXT(elm, field)                ((elm)->field.tqe_next)
#define        TAILQ_LAST(head, headname) \
        (*(((struct headname *)((head)->tqh_last))->tqh_last))
#define        TAILQ_PREV(elm, headname, field) \
        (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
/*
 * Circular queue definitions.
 */
#define        CIRCLEQ_HEAD(name, type)                                        \
struct name {                                                                \
        struct type *cqh_first;                /* first element */                \
        struct type *cqh_last;                /* last element */                \
}
#define        CIRCLEQ_HEAD_INITIALIZER(head)                                        \
        { (void *)&head, (void *)&head }
#define        CIRCLEQ_ENTRY(type)                                                \
struct {                                                                \
        struct type *cqe_next;                /* next element */                \
        struct type *cqe_prev;                /* previous element */                \
}
/*
 * Circular queue functions.
 */
#define        CIRCLEQ_INIT(head) do {                                                \
        (head)->cqh_first = (void *)(head);                                \
        (head)->cqh_last = (void *)(head);                                \
} while (/*CONSTCOND*/0)
#define        CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {                \
        (elm)->field.cqe_next = (listelm)->field.cqe_next;                \
        (elm)->field.cqe_prev = (listelm);                                \
        if ((listelm)->field.cqe_next == (void *)(head))                \
                (head)->cqh_last = (elm);                                \
        else                                                                \
                (listelm)->field.cqe_next->field.cqe_prev = (elm);        \
        (listelm)->field.cqe_next = (elm);                                \
} while (/*CONSTCOND*/0)
#define        CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {                \
        (elm)->field.cqe_next = (listelm);                                \
        (elm)->field.cqe_prev = (listelm)->field.cqe_prev;                \
        if ((listelm)->field.cqe_prev == (void *)(head))                \
                (head)->cqh_first = (elm);                                \
        else                                                                \
                (listelm)->field.cqe_prev->field.cqe_next = (elm);        \
        (listelm)->field.cqe_prev = (elm);                                \
} while (/*CONSTCOND*/0)
#define        CIRCLEQ_INSERT_HEAD(head, elm, field) do {                        \
        (elm)->field.cqe_next = (head)->cqh_first;                        \
        (elm)->field.cqe_prev = (void *)(head);                                \
        if ((head)->cqh_last == (void *)(head))                                \
                (head)->cqh_last = (elm);                                \
        else                                                                \
                (head)->cqh_first->field.cqe_prev = (elm);                \
        (head)->cqh_first = (elm);                                        \
} while (/*CONSTCOND*/0)
#define        CIRCLEQ_INSERT_TAIL(head, elm, field) do {                        \
        (elm)->field.cqe_next = (void *)(head);                                \
        (elm)->field.cqe_prev = (head)->cqh_last;                        \
        if ((head)->cqh_first == (void *)(head))                        \
                (head)->cqh_first = (elm);                                \
        else                                                                \
                (head)->cqh_last->field.cqe_next = (elm);                \
        (head)->cqh_last = (elm);                                        \
} while (/*CONSTCOND*/0)
#define        CIRCLEQ_REMOVE(head, elm, field) do {                                \
        if ((elm)->field.cqe_next == (void *)(head))                        \
                (head)->cqh_last = (elm)->field.cqe_prev;                \
        else                                                                \
                (elm)->field.cqe_next->field.cqe_prev =                        \
                    (elm)->field.cqe_prev;                                \
        if ((elm)->field.cqe_prev == (void *)(head))                        \
                (head)->cqh_first = (elm)->field.cqe_next;                \
        else                                                                \
                (elm)->field.cqe_prev->field.cqe_next =                        \
                    (elm)->field.cqe_next;                                \
} while (/*CONSTCOND*/0)
#define        CIRCLEQ_FOREACH(var, head, field)                                \
        for ((var) = ((head)->cqh_first);                                \
                (var) != (const void *)(head);                                \
                (var) = ((var)->field.cqe_next))
#define        CIRCLEQ_FOREACH_REVERSE(var, head, field)                        \
        for ((var) = ((head)->cqh_last);                                \
                (var) != (const void *)(head);                                \
                (var) = ((var)->field.cqe_prev))
/*
 * Circular queue access methods.
 */
#define        CIRCLEQ_EMPTY(head)                ((head)->cqh_first == (void *)(head))
#define        CIRCLEQ_FIRST(head)                ((head)->cqh_first)
#define        CIRCLEQ_LAST(head)                ((head)->cqh_last)
#define        CIRCLEQ_NEXT(elm, field)        ((elm)->field.cqe_next)
#define        CIRCLEQ_PREV(elm, field)        ((elm)->field.cqe_prev)
#define CIRCLEQ_LOOP_NEXT(head, elm, field)                                \
        (((elm)->field.cqe_next == (void *)(head))                        \
            ? ((head)->cqh_first)                                        \
            : (elm->field.cqe_next))
#define CIRCLEQ_LOOP_PREV(head, elm, field)                                \
        (((elm)->field.cqe_prev == (void *)(head))                        \
            ? ((head)->cqh_last)                                        \
            : (elm->field.cqe_prev))
#endif        /* sys/queue.h */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496

参考

https://www.codeleading.com/article/52881355491/
https://blog.csdn.net/tissar/article/details/86978743

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/181592