Tail Queue 位于 /usr/include/x86_64-linux-gnu/sys/queue.h，可以include <sys/queue.h> 后直接使用。Queue 的所有源码都是宏定义，因此完全包含于 queue.h 当中，无需编译为库文件。

各种结构示意图

queue.h 包含以下几种数据结构：

单链表（Singly-linked List, SLIST）
单链尾队列（Singly-linked Tail queue, STAILQ）
双链表（List, LIST）
双链尾队列（Tail queue, TAILQ）
简单队列（Simple queue, SQUEUE）
循环队列（Circular queue, CIRCLEQ）

SLIST：单向无尾队列。SLIST 非常适合具有大数据集且很少或没有删除的应用程序，或者用于实现 LIFO 后进先出队列。

STAILQ：单向有尾队列，节点 n 为尾节点。

LIST：双向无尾队列。

TAILQ：双向有尾队列。

CIRCLEQ：双向循环队列。

有尾、无尾的区别：通过这几张图可以发现，有尾（无尾）就是 head 头结构中有（无）指向链表尾节点的指针。

各种结构指向图

单向无尾队列 SLIST

SLIST：单向无尾队列。SLIST 非常适合具有大数据集且很少或没有删除的应用程序，或者用于实现 LIFO 后进先出队列。

扩展后的数据结构

SLIST 数据结构涉及 SLIST_HEAD 和 SLIST_ENTRY 两个宏定义，先给出扩展后的数据结构示例，可以看出两处宏的 type 参数要保持统一（这里都是 entry）。

// 链表节点，不同于新手常写的链表，这里被一个 struct 包裹起来了
struct entry {
    int data;
    struct { // SLIST_ENTRY(entry) entries;
        struct entry* sle_next;
    } entries;
};

// 头节点
struct slisthead { // SLIST_HEAD(slisthead, entry);
    struct entry* slh_first;
};

数据结构宏定义

/*
 * Singly-linked List definitions.
 */
// SLIST 的头节点，这里传入的 type 与 SLIST_ENTRY 宏中的 type 一致
#define SLIST_HEAD(name, type)                      \
    struct name {                                   \
        struct type* slh_first; /* first element */ \
    }

// 初始化 SLIST 的头节点结构体（不是结构体指针）为 NULL
#define SLIST_HEAD_INITIALIZER(head) \
    { NULL }

// SLIST 的节点，这里传入的 type 与 SLIST_HEAD 宏中的 type 一致
#define SLIST_ENTRY(type)                         \
    struct {                                      \
        struct type* sle_next; /* next element */ \
    }
/*
    这里只给出了指向下一个 SLIST 节点的数据结构，没有数据字段，在项目代码使用时，可以这样写：
    struct entry {
        int data;
        SLIST_ENTRY(entry) entries;
    }
*/

操作函数宏定义

/*
 * Singly-linked List functions.
 */
// 初始化 SLIST 头节点结构体指针的 slh_first 成员为 NULL
#define SLIST_INIT(head)          \
    do {                          \
        (head)->slh_first = NULL; \
    } while (/*CONSTCOND*/ 0)

/* 适用于中间节点、尾节点后面插入，不能用于首节点前面插入
    0. field 为 SLIST_ENTRY 成员的成员名
    1. 将新元素 elm 的 sle_next 指向 slistelm 元素的 sle_next
    2. 在元素 slistelm 后面插入新元素 elm
 */
#define SLIST_INSERT_AFTER(slistelm, elm, field)            \
    do {                                                    \
        (elm)->field.sle_next = (slistelm)->field.sle_next; \
        (slistelm)->field.sle_next = (elm);                 \
    } while (/*CONSTCOND*/ 0)

/* 适用于在首节点前插入（同时更新头节点）
    1. 将新元素 elm 的 sle_next 指向头节点的 slh_first
    2. 更新头节点 head 的 slh_first 地址为新元素
*/
#define SLIST_INSERT_HEAD(head, elm, field)        \
    do {                                           \
        (elm)->field.sle_next = (head)->slh_first; \
        (head)->slh_first = (elm);                 \
    } while (/*CONSTCOND*/ 0)

// 更新头节点 head 的 slh_first 地址为下一个节点
#define SLIST_REMOVE_HEAD(head, field)                         \
    do {                                                       \
        (head)->slh_first = (head)->slh_first->field.sle_next; \
    } while (/*CONSTCOND*/ 0)

/* 
    向后遍历头节点 head 指向的 type 类型的链表 curelm，移除（未释放）指定的元素 elm
    1. 如果头节点 head 指向的链表首节点是待移除的元素 elm -> 更新头节点
    2. 否则，循环判断当前节点 curelm 的下一个节点是否是待移除的元素
 */
#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)

// 从头节点 head 指向的链表首节点开始遍历链表，依次将每个节点分配给 var，通过判断 var 是否为 NULL 决定是否遍历完成
#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)

示例代码

示例代码来自：man-pages

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/queue.h>

/* 参见《扩展后的数据结构》 */
struct entry {
    int data;
    SLIST_ENTRY(entry) entries; /* Singly linked list */
};

SLIST_HEAD(slisthead, entry);

int main(void) {
    struct entry *n1, *n2, *n3, *np;
    struct slisthead head; /* Singly linked list head */

    SLIST_INIT(&head); /* Initialize the queue */

    n1 = malloc(sizeof(struct entry)); /* Insert at the head */
    SLIST_INSERT_HEAD(&head, n1, entries);

    n2 = malloc(sizeof(struct entry)); /* Insert after */
    SLIST_INSERT_AFTER(n1, n2, entries);

    SLIST_REMOVE(&head, n2, entry, entries); /* Deletion */
    free(n2);                                // 用户手动释放

    n3 = SLIST_FIRST(&head);
    SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head */
    free(n3);

    for (unsigned int i = 0; i < 5; i++) {
        n1 = malloc(sizeof(struct entry));
        SLIST_INSERT_HEAD(&head, n1, entries);  // 在链表头插入
        n1->data = i;
    }

    /* Forward traversal */
    SLIST_FOREACH(np, &head, entries) {
        printf("%i ", np->data);
    }
    printf("\r\n"); // 4 3 2 1 0

    while (!SLIST_EMPTY(&head)) { /* List deletion */
        n1 = SLIST_FIRST(&head);
        SLIST_REMOVE_HEAD(&head, entries);
        free(n1);
    }
    SLIST_INIT(&head);

    exit(EXIT_SUCCESS);
}

单向有尾队列 STAILQ

STAILQ：单向有尾队列，节点 n 为尾节点。

扩展后的数据结构

STAILQ 数据结构涉及 STAILQ_HEAD 和 STAILQ_ENTRY 两个宏定义，先给出扩展后的数据结构示例，可以看出两处宏的 type 参数要保持统一（这里都是 entry）。

// 单向尾队列的节点
struct entry {
    int data;
    struct { // STAILQ_ENTRY(entry)
        struct entry* stqe_next;
    } entries;
};

// 头节点
struct stailhead { // STAILQ_HEAD(stailhead, entry)
    struct entry* stqh_first;
    struct entry** stqh_last;
};

数据结构宏定义

/*
 * Singly-linked Tail queue declarations.
 */
// STAILQ 的头节点，stqh_last 是一个二级指针，里面存储着一个地址（指向尾节点的 stqe_next 成员地址，而不是尾节点首地址）
#define STAILQ_HEAD(name, type)                                       \
    struct name {                                                     \
        struct type* stqh_first; /* first element */                  \
        struct type** stqh_last; /* addr of last stqe_next element */ \
    }

// 初始化 STAILQ 的头节点（不是结构体指针）的 stqh_first 为 NULL，stqh_last 为 stqh_first 的地址
#define STAILQ_HEAD_INITIALIZER(head) \
    { NULL, &(head).stqh_first }

// STAILQ 的节点，这里传入的 type 与 STAILQ_HEAD 宏中的 type 一致
#define STAILQ_ENTRY(type)                         \
    struct {                                       \
        struct type* stqe_next; /* next element */ \
    }
/*
    这里只给出了指向下一个 STAILQ 节点的数据结构，没有数据字段，在项目代码使用时，可以这样写：
    struct entry {
        int data;
        STAILQ_ENTRY(entry) entries;
    }
*/

操作函数宏定义

/*
 * Singly-linked Tail queue functions.
 */
// 初始化 STAILQ 头节点结构体指针的成员
#define STAILQ_INIT(head)                        \
    do {                                         \
        (head)->stqh_first = NULL;               \
        (head)->stqh_last = &(head)->stqh_first; \
    } while (/*CONSTCOND*/ 0)

// 在 STAILQ 的头节点 head 前插入新元素 elm，并重新将头节点 head 指向新元素 elm
#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)

// 在 STAILQ 尾节点（通过头节点 head 获取）后面插入新元素 elm
#define STAILQ_INSERT_TAIL(head, elm, field)         \
    do {                                             \
        (elm)->field.stqe_next = NULL;               \
        *(head)->stqh_last = (elm); /* 原尾节点的 stqe_next 指向新元素 */ \
        (head)->stqh_last = &(elm)->field.stqe_next; \
    } while (/*CONSTCOND*/ 0)

// 在中间节点、尾节点 listelm 后面插入新元素 elm。如果是尾节点后插入，则需要更新头节点的 stqh_last
#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)

// 头节点指向首节点的下一个节点。如果移动后只剩一个节点，则需要更新头节点的 stqh_last
#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)

// 通过 head 遍历 STAILQ，移除指定的元素 elm。如果移除的元素 elm 是尾节点，则需要更新头节点的 stqh_last
#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)

// 从头节点 head 指向的首节点开始遍历队列，依次将每个节点分配给 var，通过判断 var 是否为 NULL 决定是否遍历完成
#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)

示例代码

示例代码来自：man-pages

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/queue.h>

struct entry {
    int data;
    STAILQ_ENTRY(entry) entries; /* Singly linked tail queue */
};

STAILQ_HEAD(stailhead, entry);

int main(void) {
    struct entry *n1, *n2, *n3, *np;
    struct stailhead head; /* Singly linked tail queue head */

    STAILQ_INIT(&head); /* Initialize the queue */

    n1 = malloc(sizeof(struct entry)); /* Insert at the head */
    STAILQ_INSERT_HEAD(&head, n1, entries);

    n1 = malloc(sizeof(struct entry)); /* Insert at the tail */
    STAILQ_INSERT_TAIL(&head, n1, entries);

    n2 = malloc(sizeof(struct entry)); /* Insert after */
    STAILQ_INSERT_AFTER(&head, n1, n2, entries);

    STAILQ_REMOVE(&head, n2, entry, entries); /* Deletion */
    free(n2);

    n3 = STAILQ_FIRST(&head);
    STAILQ_REMOVE_HEAD(&head, entries); /* Deletion from the head */
    free(n3);

    n1 = STAILQ_FIRST(&head);
    n1->data = 0;
    for (unsigned int i = 1; i < 5; i++) {
        n1 = malloc(sizeof(struct entry));
        STAILQ_INSERT_HEAD(&head, n1, entries);
        n1->data = i;
    }
    /* Forward traversal */
    STAILQ_FOREACH(np, &head, entries) {
        printf("%i ", np->data);
    }
    printf("\r\n"); // 4 3 2 1 0

    /* TailQ deletion */
    n1 = STAILQ_FIRST(&head);
    while (n1 != NULL) {
        n2 = STAILQ_NEXT(n1, entries);
        free(n1);
        n1 = n2;
    }
    STAILQ_INIT(&head);

    exit(EXIT_SUCCESS);
}

双向无尾队列 LIST

LIST：双向无尾队列。

扩展后的数据结构

LIST 数据结构涉及 LIST_HEAD 和 LIST_ENTRY 两个宏定义，先给出扩展后的数据结构示例，可以看出两处宏的 type 参数要保持统一（这里都是 entry）。

// LIST 节点
struct entry {
    int data;
    struct { // LIST_ENTRY(entry) entries;
        struct entry* le_next;
        struct entry** le_prev;
    } entries;
};

// LIST 头节点
struct listhead { // LIST_HEAD(listhead, entry);
    struct entry* lh_first;
}

数据结构宏定义

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

// LIST 头节点结构体（非结构体指针）初始化为 NULL
#define LIST_HEAD_INITIALIZER(head) \
    { NULL }

// LIST 节点，le_prev 是一个二级指针，里面存储着一个地址（指向前一个节点的 le_next 成员地址）
#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)

/* 在 listelm 节点后面插入新节点 elm
    1. 将新节点 elm 指向 listelm 节点的原有的下一个节点前面
    2. listelm 节点的原有的下一个节点的 le_prev，更新为指向新节点 elm 的 le_next 成员地址
    3. 更新 listelm 节点的下一个节点为新节点 elm
    4. 新节点的 le_prev，更新为指向 listelm 节点的 le_next 成员地址
 */
#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)

/* 在 listelm 节点前面插入新节点 elm
    1. 新节点 elm 的 le_prev 更新为 listelm 节点的 le_prev
    2. 新节点 elm 的 le_next 指向 listelm 节点
    3. 让 listelm 节点的原有前一个节点指向新节点 elm
    4. listelm 节点的 le_prev 指向前一个新节点 elm 的 le_next 成员地址
 */
#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)

/* 在 head 头节点前插入一个节点 elm，并更新头
    1. 将新节点链接在头节点指向的首节点的前面
    2. 更新头节点指向的首节点的 le_prev 为新节点 elm 的 le_next 成员地址
    3. 更新头节点 lh_first 为新节点 elm 的首地址
    4. 更新新首节点 elm 的 le_prev 的地址为头节点的 lh_first 成员地址
 */
#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)

/* 移除指定的节点
    1. 将移除节点的下一个节点的 le_prev 更新为移除元素的 le_prev（如果移除节点不是尾节点）
    2. 通过解引用移除节点的 le_prev 获取前一个节点指向的下一个节点，将其重新指向移除元素的下一个节点
 */
#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)

// 从头节点 head 指向的首节点开始遍历队列，依次将每个节点分配给 var，通过判断 var 是否为 NULL 决定是否遍历完成
#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)

示例代码

示例代码来自：man-pages

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/queue.h>

struct entry {
    int data;
    LIST_ENTRY(entry) entries; /* List */
};

LIST_HEAD(listhead, entry);

int main(void) {
    struct entry *n1, *n2, *n3, *np;
    struct listhead head; /* List head */
    int i;

    LIST_INIT(&head); /* Initialize the list */

    n1 = malloc(sizeof(struct entry));     /* Insert at the head */
    LIST_INSERT_HEAD(&head, n1, entries);  // head <-> n1

    n2 = malloc(sizeof(struct entry));   /* Insert after */
    LIST_INSERT_AFTER(n1, n2, entries);  // head <-> n1 <-> n2

    n3 = malloc(sizeof(struct entry));    /* Insert before */
    LIST_INSERT_BEFORE(n2, n3, entries);  // head <-> n1 <-> n3 <-> n2

    i = 0; /* Forward traversal */
    LIST_FOREACH(np, &head, entries) {
        np->data = i++;  // n1(0) n3(1) n2(2)
    }

    LIST_REMOVE(n2, entries); /* Deletion, head <-> n1 <-> n3 */
    free(n2);
    /* Forward traversal */
    LIST_FOREACH(np, &head, entries) {
        printf("%i ", np->data);
    }
    printf("\r\n");  // 0 1

    /* List deletion */
    n1 = LIST_FIRST(&head);
    while (n1 != NULL) {
        n2 = LIST_NEXT(n1, entries);
        free(n1);
        n1 = n2;
    }
    LIST_INIT(&head);

    exit(EXIT_SUCCESS);
}

双向有尾队列 TAILQ

TAILQ：双向有尾队列。

扩展后的数据结构

TAILQ 数据结构涉及 TAILQ_HEAD 和 TAILQ_ENTRY 两个宏定义，先给出扩展后的数据结构示例，可以看出两处宏的 type 参数要保持统一（这里都是 entry）。

struct entry {
    int data;
    struct {  // TAILQ_ENTRY(entry)
        struct entry* tqe_next;
        struct entry** tqe_prev;
    } entries;
};

struct tailhead {  // TAILQ_HEAD(tailhead, entry)
    struct entry* tqh_first;
    struct entry** tqh_last;
};

tqe_prev和 tqh_last 为什么是二级指针，换成一级指针行不行？

肯定不行，如果它的前面是头节点怎么办，头节点的定义里面没有 struct entry 结构体类型啊！再仔细看看，不管是头节点还是普通节点，都有 struct entry* 结构体指针类型，那就定义一个类型为 struct entry** 的变量好了。这样前插的时候就可以统一处理了，例子见 TAILQ_INSERT_BEFORE。

数据结构宏定义

/*
 * Tail queue definitions.
 */
// TAILQ 头节点，其中 qual=qualifier，用于修饰限定 type，如 qual=const
#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 }

// TAILQ 节点，qual 用于修饰限定 type 和二级指针
#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.
 */
// TAILQ 头节点初始化，初始化时头节点中的二级指针 tqh_last 指向 tqh_first 成员变量的地址 
#define TAILQ_INIT(head)                       \
    do {                                       \
        (head)->tqh_first = NULL;              \
        (head)->tqh_last = &(head)->tqh_first; \
    } while (/*CONSTCOND*/ 0)

/* 在头节点 head 前插入新节点 elm，并更新头节点
    1. 将新节点的 tqe_next 指向头节点的 tqh_first 指向的首节点
    2. 如果首节点非空，则将原首节点的 tqe_prev 指向新节点 elm 的 tqe_next 成员变量的地址
    3. 否则（首节点为空），则【更新尾指针 tqh_last 指向新节点 elm 的 tqe_next 成员变量的地址】
    4. 更新头节点的 tqh_first 指向新节点 elm
    5. 更新新节点 elm 的 tqe_prev 指向头节点的 tqh_first 成员变量的地址
 */
#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)

/* 在尾节点（通过 head 获取尾节点的 tqe_next 地址）后插入新节点 elm
    1. 将作为尾节点的新节点 elm 的 tqe_next 置 NULL
    2. 将作为尾节点的新节点 elm 的 tqe_prev 指向原尾节点的 tqe_next 成员的地址（通过(head)->tqh_last 获取）
    3. 将原尾节点作为新尾节点 elm 的前一个节点（将原尾节点指向新尾节点 elm）
    4. 更新头节点中指向尾节点的 tqe_next 成员地址的二级指针 tqh_last
 */
#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)

/* 在节点 listelm 后插入新节点 elm，如果是在尾节点后插入，则更新头节点的 tqh_last 成员地址
    1. 更新新节点 elm 的 tqe_next 为节点 listelm 的 tqe_next，即插入
    2. 如果更新后新节点 elm 的 tqe_next 不为空：
        则不是在尾节点后插入，更新节点 listelm 的原下一个节点的 tqe_prev 成员值为新节点 elm 的 tqe_next 成员地址
        否则，是在尾节点后插入，则更新头节点的 tqh_last 成员地址为新节点 elm(尾节点) 的 tqe_next 成员地址
    3. 将节点 listelm 指向新节点 elm
    4. 将新节点的 tqe_prev 成员值指向节点 listelm 的 tqe_next 成员地址
 */
#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)

/* 在节点 listelm 前插入新节点 elm，不涉及更新头节点的成员信息
    1. 更新新节点的 tqe_prev 为节点 listelm 的 tqe_prev
    2. 将新节点的 tqe_next 指向节点 listelm
    3. 将节点 listelm 的前一个节点指向新节点 elm：
        a) 解引用 *(listelm)->field.tqe_prev，即节点 listelm 的前一个节点的 tqe_next 地址，指向新节点 elm
        b) 如果节点 listelm 是首节点呢? 解引用获取到的就是头节点 head 的 tqh_first 地址，其指向新节点 elm
    4. 更新节点 listelm 的 tqe_prev 成员值为新插入节点 elm 的 tqe_next 成员地址
 */
#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)

/* 移除节点 elm，如果移除的是首 / 尾节点，则需要更新头节点的 tqh_first/tqh_last 地址
    1. 判断待移除的节点 elm 的 tqe_next 是否为空：
        不为空，则不是尾节点：更新节点 elm 的下一个节点的 tqe_prev 值为节点 elm 的 tqe_prev 值
        为空，则是尾结点：更新头节点的 tqh_last 值为节点 elm 的 tqe_prev 值
    2. 通过解引用修改待移除节点 elm 的前一个节点的值，从而将其指向待移除节点 elm 的下一个节点
        解引用前的前一个节点的地址：可能是前一个普通节点的 tqe_next 地址，也可能是头节点的 tqh_first 地址；
        通过解引用修改变量地址下的值，从而将其指向正确的节点（待移除节点 elm 的下一个节点）
 */
#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)

// 正向遍历，从头节点 head 指向的首节点开始遍历队列，依次将每个节点分配给 var，通过判断 var 是否为 NULL 决定是否遍历完成
#define TAILQ_FOREACH(var, head, field) for ((var) = ((head)->tqh_first); (var); (var) = ((var)->field.tqe_next))

// 反向遍历，参考 TAILQ_LAST 和 TAILQ_PREV
#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))

TAILQ_LAST

TAILQ_LAST 可以获取尾节点的结构体首地址（不是尾节点的 tqe_next 成员地址），它是如何获取到的？

(head)->tqh_last 是最后一个节点的 entries.tqe_next 成员的地址，可是这个地址不是用户想要的，用户要的是节点的地址（结构体的首地址），所以只好曲线救国，请看《各种结构指向图》小节的 TAILQ，从 1 到 2 再到 3。

从 entries.tqe_next 的地址怎么得到 entries.tqe_prev 的值呢（目的是为了得到倒数第二个节点的 entries.tqe_next）？

其实也不难，虽然 struct entry 里面 entries 这个结构体变量没有标签，但是 它的元素构成和 struct headname 完全一样，都是一个 struct entry* 和一个 struct entry**，所以可以把 entries.tqe_next 的地址强制转换为 (struct headname *) 类型：

(struct headname *)((head)->tqh_last)

然后访问它的 tqh_last 成员（也就是图中尾节点的 tqe_prev）：

((struct headname *)((head)->tqh_last))->tqh_last

这样就得到了前一个节点的 entries.tqe_next 的地址，再对它解引用：

*(((struct headname *)((head)->tqh_last))->tqh_last)

就得到了 entries.tqe_next 变量，这恰好是大结构体（ struct entry ）的首地址。

TAILQ_PREV

我们再看 TAILQ_PREV 这个宏，道理类似。请看《各种结构指向图》小节的 TAILQ，从 a 到 b 再到 c。

设当前节点的地址是 elm（图中用最后这个节点来示意），(elm)->field.tqe_prev，表示顺着 a，得到它前面那个节点的 tqe_next 成员的地址，对这个地址强制转换为 struct headname *，即

(struct headname *)((elm)->field.tqe_prev)

再通过访问 tqh_last（等效于访问 tqe_prev），也就是顺着 b，得到了 elm 前面的前面的节点的 tqe_next 地址，即

((struct headname *)((elm)->field.tqe_prev))->tqh_last

对它解引用，就得到 elm 前面的前面的节点的 tqe_next，它刚好是 c 指向的 elm前面的结构体的首地址。

*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)

示例代码

示例代码来自：man-pages

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/queue.h>

struct entry {
    int data;
    TAILQ_ENTRY(entry) entries; /* Tail queue */
};

TAILQ_HEAD(tailhead, entry);

int main(void) {
    struct entry *n1, *n2, *n3, *np;
    struct tailhead head; /* Tail queue head */
    int i;

    TAILQ_INIT(&head); /* Initialize the queue */

    n1 = malloc(sizeof(struct entry)); /* Insert at the head */
    n1->data = 20;
    TAILQ_INSERT_HEAD(&head, n1, entries);  // 20

    n1 = malloc(sizeof(struct entry)); /* Insert at the tail */
    n1->data = 30;
    TAILQ_INSERT_TAIL(&head, n1, entries);  // 20 30

    n2 = malloc(sizeof(struct entry)); /* Insert after */
    n2->data = 40;
    TAILQ_INSERT_AFTER(&head, n1, n2, entries);  // 20 30 40

    n3 = malloc(sizeof(struct entry)); /* Insert before */
    n3->data = 50;
    TAILQ_INSERT_BEFORE(n2, n3, entries);  // 20 30 50 40

    TAILQ_REMOVE(&head, n2, entries); /* Deletion */
    free(n2);
    /* Forward traversal */
    i = 0;
    TAILQ_FOREACH(np, &head, entries) {
        np->data = np->data + (i++);
    }  // 20 31 52
    /* Reverse traversal */
    TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries) {
        printf("%i ", np->data);
    }
    printf("\r\n");  // 52 31 20
    /* TailQ deletion */
    n1 = TAILQ_FIRST(&head);
    while (n1 != NULL) {
        n2 = TAILQ_NEXT(n1, entries);
        free(n1);
        n1 = n2;
    }
    TAILQ_INIT(&head);

    exit(EXIT_SUCCESS);
}

参考资料

https://www.cnblogs.com/fuzidage/p/14482501.html

https://blog.csdn.net/ET_Endeavoring/article/details/121609082

SLIT: https://blog.csdn.net/longintchar/article/details/122907350

STAILQ: https://blog.csdn.net/longintchar/article/details/122907478

TAILQ: https://blog.csdn.net/longintchar/article/details/122907708

aha

2024-07-02

数据结构 #Linux #数据结构 #队列

基础知识

C 语言

Golang 语言

数据结构

数据结构算法

数据库

计算机网络

操作系统

系统与网络编程

工具与命令

开源项目

Docker

LeetCode 刷题

链表相关

设计

贪心算法

哈希表

树的遍历

深度优先搜索（递归）

图或路径问题

其它

各种结构示意图

各种结构指向图

单向无尾队列 SLIST

扩展后的数据结构

数据结构宏定义

操作函数宏定义

访问宏定义

示例代码

单向有尾队列 STAILQ

扩展后的数据结构

数据结构宏定义

操作函数宏定义

访问宏定义

示例代码

双向无尾队列 LIST

扩展后的数据结构

数据结构宏定义

操作函数宏定义

访问宏定义

示例代码

双向有尾队列 TAILQ

扩展后的数据结构

数据结构宏定义

操作函数宏定义

访问宏定义

TAILQ_LAST

TAILQ_PREV

示例代码