数据结构之线性表(bsd, sys/queue.h)

数据结构之线性表

Author:Once Day Date:2023年5月27日

参考文档:

Linux内嵌链表（sys/queue.h）详解_tissar的博客-CSDN博客
嵌入式大杂烩周记第 3 期：sys/queue.h - 知乎 (zhihu.com)
queue(7) - Linux manual page (man7.org)
queue(3) - OpenBSD manual pages
list(3) - Linux manual page (man7.org)
slist(3) - Linux manual page (man7.org)
stailq(3) - Linux manual page (man7.org)
tailq(3) - Linux manual page (man7.org)
circleq(3) - Linux manual page (man7.org)

文章目录

- 数据结构之线性表

1.概述

线性表（linear list）存在唯一的头部数据和尾部数据，而且中间的每个数据都有一个前驱元素和后驱元素。
线性表是有限个元素的序列，如一维数组和链表。
每个数据元素可由若干个数据项构成。

数学表达可如下：
( a 1 , a 2 , . . . . , a n − 1 , a n ) (a_1,a_2,....,a_{n-1},a_n) (a1,a2,....,an−1,an)
**数据元素n即为线性表的长度。**也可以看到每个元素都有个确切的位置，并且长度也可根据需要增长和缩短。

本文介绍的线性表以linux自带的sys/queue.h为例子，该列表来自于FreeBSD中的一个头文件。一般由glibc中携带。源码查看链接如下:

queue.h « sys « sys - src - FreeBSD source tree

头文件queue.h为C语言中的链表提供了更加标准规范的编程接口。如今的版本多为伯克利加州大学1994年8月的8.5版本。

1.1 不同队列的功能介绍

单链表(SLIST)的头是一个正向指针。元素是单链接的，以最小的空间和指针操作开销为代价，对任意元素进行O(n)移除。新元素可以添加到现有元素之后，也可以添加到列表的头部。从列表头部删除的元素应该使用显式宏来实现此目的，以获得最佳效率。单链表只能在正向上遍历。单链表适用于具有大数据集且很少或没有删除的应用程序，或实现后进先出队列。

单链尾队列(STAILQ)由一对指针引导，一个指向列表的头部，另一个指向列表的尾部。元素是单链接的，以最小的空间和指针操作开销为代价，对任意元素进行O(n)移除。可以将新元素添加到列表中，在现有元素之后，在列表的头部，或在列表的末尾。要从尾部队列的头部删除的元素应该为此目的使用显式宏，以获得最佳效率。单链尾队列只能在正向上遍历。单链接尾部队列非常适合具有大数据集和很少或没有删除或实现FIFO队列的应用程序。

一些bsd提供SIMPLEQ而不是STAILQ。它们是相同的，但由于历史原因，它们在不同的bsd上命名不同。STAILQ起源于FreeBSD，而SIMPLEQ起源于NetBSD。出于兼容性的考虑，有些系统提供两组宏。Glibc提供了STAILQ和SIMPLEQ，除了缺少一个相当于STAILQ_CONCAT()的SIMPLEQ之外，它们是相同的。

列表(LIST)的头由单个前向指针(或哈希表头的前向指针数组)组成。元素是双向链接的，因此可以删除任意元素而无需遍历列表。新元素可以添加到列表中，在现有元素之前或之后，也可以添加到列表的头部。列表可以在任意一个方向上遍历。

尾队列(TAILQ)由一对指针引导，一个指向列表的头部，另一个指向列表的尾部。元素是双向链接的，因此可以删除任意元素而无需遍历列表。可以将新元素添加到列表中，在现有元素之前或之后，在列表的开头或结尾。尾队列可以在任何一个方向上遍历。

最后还有一个CIRCLEQ的循环队列，一般用不着，上述的四个队列已经足够使用了。

总共有五种类型的数据结构:单链表、列表、单链尾队列和尾队列。所有五个结构都支持以下功能:

在列表的头部插入一个新条目。
在列表中的任何元素之后插入一个新条目。
从列表的头部删除一个条目。
向前遍历列表。

所有双重链接类型的数据结构(列表和尾队列)还允许:

在列表中的任何元素之前插入一个新条目。
删除列表中的任何条目。

然而:

每个元素需要两个指针而不是一个。
操作的代码大小和执行时间(移除除外)大约是单链接数据结构的两倍。
列表是最简单的双链数据结构，在单链表上只支持上述功能。

尾部队列增加了以下功能:

可以在列表末尾添加条目。
它们可以反向遍历，这是有代价的。

然而:

所有的列表插入和删除都必须指定列表的头。
每个头条目需要两个指针而不是一个。
代码大小比单链表大15%，操作运行速度比单链表慢20%。

另一种类型的数据结构——循环队列——违反了C语言的混叠规则，导致编译错误。所有使用它们的代码都应转换为另一种结构;尾队列通常是最容易转换的。

1.2 功能对比表

下面是一些功能标记：

+ 意味着这个宏是可用的。

- 意味着这个宏不可用。

s 意味着这个宏可用但是速率较低(o(n)复杂度)

2.具体说明

2.1 SLIST单向列表详细介绍

BSD queue.h中的SLIST是一种单向链表，它提供了一种简单而高效的数据结构，适用于许多常见的程序场景。下面是从效率、安全性和使用方式三个方面对SLIST的总结：

效率：SLIST的效率非常高，因为它是一个非常简单的数据结构，它的插入、删除和遍历操作都可以在常数时间内完成。这使得SLIST非常适合于需要高效率的程序场景，如操作系统内核、网络服务器等。
安全性：在多线程环境下，对于同一个SLIST链表的并发访问，通常需要进行同步和互斥，以确保数据的完整性和正确性。因此，在多线程环境下使用SLIST时，确实需要进行上锁保护。
使用方式：使用SLIST非常简单，只需要包含头文件<sys/queue.h>即可。SLIST提供了一系列宏，可以用来操作链表，例如SLIST_INIT、SLIST_INSERT_HEAD、SLIST_REMOVE等。这些宏可以在代码中直接使用，非常方便。此外，SLIST还提供了一些辅助宏，例如SLIST_EMPTY和SLIST_NEXT等，可以用来查询链表的状态和访问链表元素。

总的来说，BSD queue.h中的SLIST是一种非常高效、可靠、易用的数据结构，适用于许多常见的程序场景。在程序开发过程中，程序员可以使用SLIST来提高程序的效率和安全性，同时减少开发时间和代码复杂度。

单链表的头是由SLIST_HEAD()宏定义的结构。该结构包含一个指向列表第一个元素的指针。元素是单链接的，以最小的空间和指针操作开销为代价，对任意元素进行O(n)移除。新元素可以添加到现有元素之后，也可以添加到列表的头部。SLIST_HEAD结构体的声明如下:

#define SLIST_HEAD(name, type)                      \
    struct name {                                   \
        struct type *slh_first; /* first element */ \
    }

SLIST_HEAD(HEADNAME, TYPE) head;

其中HEADNAME是要定义的结构的名称，struct TYPE是要链接到列表中的元素的类型。指向列表头的指针稍后可以声明为:

struct HEADNAME *headp;

HEADNAME功能通常不使用，导致以下奇怪的代码(使用匿名结构体):

SLIST_HEAD(, TYPE) head, *headp;

下面是配套其他操作函数:

SLIST_ENTRY()宏声明了一个连接列表中的元素的结构。
SLIST_INIT()宏初始化由head引用的列表。
列表也可以通过使用SLIST_HEAD_INITIALIZER()宏静态初始化，如下所示:
```
SLIST_HEAD(HEADNAME, TYPE) head = SLIST_HEAD_INITIALIZER(head);
```
SLIST_INSERT_HEAD()宏将新元素elm插入到列表的头部。
SLIST_INSERT_AFTER()宏将新元素elm插入到元素listelm之后。
SLIST_REMOVE_HEAD()宏删除由head指向的列表的第一个元素。
SLIST_REMOVE_AFTER()宏删除elm之后的列表元素。
SLIST_REMOVE()宏删除由head指向的列表中的元素elm。

SLIST_FIRST()和SLIST_NEXT()宏可以用来遍历列表:

for (np = SLIST_FIRST(&head); np != NULL; np = SLIST_NEXT(np, FIELDNAME))

或者，为了简单起见，可以使用SLIST_FOREACH()宏:

SLIST_FOREACH(np, head, FIELDNAME)

宏SLIST_FOREACH_SAFE()向前遍历由head引用的列表，将每个元素依次赋值给var。然而，与SLIST_FOREACH()不同的是，SLIST_FOREACH_SAFE()允许删除var并在循环中安全地释放它，而不会干扰遍历。

应该使用SLIST_EMPTY()宏来检查简单列表是否为空。

SLIST_FOREACH()不允许在循环中删除或释放var，因为它会干扰遍历。SLIST_FOREACH_SAFE()存在于bsd中，但不存在于glibc中，它通过允许var安全地从列表中删除并从循环中释放而不干扰遍历来修复此限制。

下面是具体的宏函数定义类型展示:

#include <sys/queue.h>

SLIST_ENTRY(TYPE);

SLIST_HEAD(HEADNAME, TYPE);
SLIST_HEAD SLIST_HEAD_INITIALIZER(SLIST_HEAD head);
void SLIST_INIT(SLIST_HEAD *head);

int SLIST_EMPTY(SLIST_HEAD *head);

void SLIST_INSERT_HEAD(SLIST_HEAD *head,
                       struct TYPE *elm, SLIST_ENTRY NAME);
void SLIST_INSERT_AFTER(struct TYPE *listelm,
                       struct TYPE *elm, SLIST_ENTRY NAME);

struct TYPE *SLIST_FIRST(SLIST_HEAD *head);
struct TYPE *SLIST_NEXT(struct TYPE *elm, SLIST_ENTRY NAME);

SLIST_FOREACH(struct TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);

void SLIST_REMOVE(SLIST_HEAD *head, struct TYPE *elm,
                       SLIST_ENTRY NAME);
void SLIST_REMOVE_HEAD(SLIST_HEAD *head,
                       SLIST_ENTRY NAME);

2.2 SLIST单向列表使用实例

BSD queue.h中的SLIST是一种单向链表的实现，用于在C语言中管理数据结构。使用SLIST需要进行以下步骤：

定义一个结构体，该结构体应该包含一个SLIST_ENTRY成员，以便将结构体连接到链表中。
使用SLIST_ENTRY宏定义一个结构体成员，以便将结构体链接到链表中。
使用SLIST_HEAD宏定义一个链表头，该链表头包含一个SLIST_ENTRY成员。
使用SLIST_INIT宏将链表头初始化为一个空链表。
使用SLIST_INSERT_HEAD、SLIST_INSERT_AFTER、SLIST_REMOVE等宏来操作链表中的元素。

SLIST与LIST的主要区别在于SLIST是单向链表，只能从头部插入和删除元素，而LIST是双向链表，可以从头部和尾部插入和删除元素。在使用BSD queue.h中的SLIST时，需要注意以下事项：

不支持双向遍历：SLIST是单向链表，只能从头部开始遍历，无法反向遍历。
不支持随机访问：SLIST只能从头部插入和删除元素，因此无法通过索引或指针直接访问链表中的元素。
不安全：SLIST没有进行越界检查，因此存在指针越界问题，需要注意安全性。
不支持动态内存分配：SLIST不支持在运行时动态地分配内存，因此需要在编译时确定链表的大小。
适用性限制：SLIST只适用于单向链表的数据结构，因此不适用于其他类型的数据结构。

总的来说，BSD queue.h中的SLIST是一种简单、高效的单向链表实现。在使用时需要注意其适用性限制和安全性问题。

下面是一个使用示例:

SLIST_HEAD(listhead, entry) head;
struct entry {
	...
	SLIST_ENTRY(entry) entries;	/* Simple list. */
	...
} *n1, *n2, *np;

SLIST_INIT(&head);			/* Initialize simple list. */

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_FOREACH(np, &head, entries)	/* Forward traversal. */
	np-> ...

while (!SLIST_EMPTY(&head)) {	 	/* Delete. */
	n1 = SLIST_FIRST(&head);
	SLIST_REMOVE_HEAD(&head, entries);
	free(n1);
}

2.3 LIST双向列表详细介绍

列表的头是由LIST_HEAD()宏定义的结构。该结构包含一个指向列表第一个元素的指针。元素是双向链接的，因此可以在不遍历列表的情况下删除任意元素。可以将新元素添加到列表中，在现有元素之后，在现有元素之前，或者在列表的头部。LIST_HEAD结构体的声明如下:

LIST_HEAD(HEADNAME, TYPE) head;

其中HEADNAME是要定义的结构的名称，struct TYPE是要链接到列表中的元素的类型。指向列表头的指针稍后可以声明为:

struct HEADNAME *headp; # (名称head和headp是用户可选择的。)

HEADNAME功能通常不使用，导致以下奇怪的代码:

LIST_HEAD(， TYPE) head， *head;

具有下面的操作:

LIST_ENTRY()宏声明了一个连接列表中的元素的结构。
LIST_INIT()宏初始化由head引用的列表。
列表也可以通过使用LIST_HEAD_INITIALIZER()宏静态初始化，如下所示:
```
LIST_HEAD(HEADNAME, TYPE) head = LIST_HEAD_INITIALIZER(head);
```
LIST_INSERT_HEAD()宏将新元素elm插入到列表的头部。
LIST_INSERT_AFTER()宏将新元素elm插入到元素listelm之后。
LIST_INSERT_BEFORE()宏将新元素elm插入到元素listelm之前。
LIST_REMOVE()宏从列表中删除元素elm。
LIST_REPLACE()宏将列表元素elm替换为新元素elm2。

LIST_FIRST()和LIST_NEXT()宏可以用来遍历列表:

for (np = LIST_FIRST(&head);np != NULL;np = LIST_NEXT(np, FIELDNAME))

或者，为了简单起见，可以使用LIST_FOREACH()宏:

LIST_FOREACH(np, head, FIELDNAME)

宏LIST_FOREACH_SAFE()向前遍历由head引用的列表，将每个元素依次赋值给var。然而，与LIST_FOREACH()不同的是，它允许删除var并将其安全地从循环中释放出来，而不会干扰遍历。

应该使用LIST_EMPTY()宏来检查列表是否为空。

双向列表的使用与单向列表没有多少区别，下面是宏函数定义原型:

#include <sys/queue.h>

LIST_ENTRY(TYPE);

LIST_HEAD(HEADNAME, TYPE);
LIST_HEAD LIST_HEAD_INITIALIZER(LIST_HEAD head);
void LIST_INIT(LIST_HEAD *head);

int LIST_EMPTY(LIST_HEAD *head);

void LIST_INSERT_HEAD(LIST_HEAD *head,
                       struct TYPE *elm, LIST_ENTRY NAME);
void LIST_INSERT_BEFORE(struct TYPE *listelm,
                       struct TYPE *elm, LIST_ENTRY NAME);
void LIST_INSERT_AFTER(struct TYPE *listelm,
                       struct TYPE *elm, LIST_ENTRY NAME);

struct TYPE *LIST_FIRST(LIST_HEAD *head);
struct TYPE *LIST_NEXT(struct TYPE *elm, LIST_ENTRY NAME);

LIST_FOREACH(struct TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME);

void LIST_REMOVE(struct TYPE *elm, LIST_ENTRY NAME);

下面是使用实例:

LIST_HEAD(listhead, entry) head;
struct entry {
	...
	LIST_ENTRY(entry) entries;	/* List. */
	...
} *n1, *n2, *np;

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

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

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

n2 = malloc(sizeof(struct entry));	/* Insert before. */
LIST_INSERT_BEFORE(n1, n2, entries);
					/* Forward traversal. */
LIST_FOREACH(np, &head, entries)
	np-> ...

while (!LIST_EMPTY(&head)) {		/* Delete. */
	n1 = LIST_FIRST(&head);
	LIST_REMOVE(n1, entries);
	free(n1);
}

2.4 STAILQ单向尾队列详细介绍

单链接的尾部队列由STAILQ_HEAD()宏定义的结构作为头部。该结构包含一对指针，一个指向尾队列中的第一个元素，另一个指向尾队列中的最后一个元素。元素是单链接的，以最小的空间和指针操作开销为代价，对任意元素进行O(n)移除。新元素可以添加到尾队列，在现有元素之后，在尾队列的头部或尾队列的末端。STAILQ_HEAD结构声明如下:

STAILQ_HEAD(HEADNAME, TYPE) head;

其中HEADNAME是要定义的结构的名称，struct TYPE是要链接到尾队列的元素的类型。指向尾部队列头部的指针稍后可以声明为:

struct HEADNAME *headp;		# (名称head和headp是用户可选择的。)

下面是一些常见的操作:

STAILQ_ENTRY()宏声明了一个连接尾队列中的元素的结构。
STAILQ_INIT()宏初始化由head引用的尾部队列。
尾部队列也可以通过使用STAILQ_HEAD_INITIALIZER()宏静态初始化。
STAILQ_INSERT_AFTER()宏将新元素elm插入到元素listelm之后。
STAILQ_INSERT_HEAD()宏将新元素elm插入到尾部队列的头部。
STAILQ_INSERT_TAIL()宏将新元素elm插入到尾部队列的末尾。
STAILQ_REMOVE_AFTER()宏删除紧跟在elm后面的队列元素。与STAILQ_REMOVE不同，这个宏不会遍历整个尾部队列。
STAILQ_REMOVE_HEAD()宏从尾部队列中删除第一个元素。为了获得最佳效率，从尾部队列头部删除的元素应该显式地使用这个宏，而不是通用的STAILQ_REMOVE宏。
STAILQ_REMOVE()宏从尾部队列中删除元素elm。应该避免使用这个宏，因为它遍历整个列表。如果在高使用率的代码路径中需要这个宏，或者在长尾队列上操作，那么应该使用双链接的尾队列。
STAILQ_CONCAT()宏将由head2引用的尾部队列的所有元素连接到由head1引用的尾部队列的末尾，在进程中清空head2。这比删除和插入单个元素更有效，因为它实际上不遍历head2。

STAILQ_FOREACH()宏用于队列遍历:

STAILQ_FOREACH()宏用于队列遍历，宏STAILQ_FOREACH_SAFE()向前遍历由head引用的队列，将每个元素依次赋值给var。然而，与STAILQ_FOREACH()不同的是，它允许删除var并在循环中安全地释放它，而不会干扰遍历。

可以使用STAILQ_FIRST()、STAILQ_NEXT()和STAILQ_LAST()宏手动遍历尾队列或尾队列的任意部分。应该使用STAILQ_EMPTY()宏来检查尾队列是否为空。

下面是这些函数的宏函数原型定义:

#include <sys/queue.h>

STAILQ_ENTRY(TYPE);

STAILQ_HEAD(HEADNAME, TYPE);
STAILQ_HEAD STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head);
void STAILQ_INIT(STAILQ_HEAD *head);

int STAILQ_EMPTY(STAILQ_HEAD *head);

void STAILQ_INSERT_HEAD(STAILQ_HEAD *head,
                        struct TYPE *elm, STAILQ_ENTRY NAME);
void STAILQ_INSERT_TAIL(STAILQ_HEAD *head,
                        struct TYPE *elm, STAILQ_ENTRY NAME);
void STAILQ_INSERT_AFTER(STAILQ_HEAD *head, struct TYPE *listelm,
                        struct TYPE *elm, STAILQ_ENTRY NAME);

struct TYPE *STAILQ_FIRST(STAILQ_HEAD *head);
struct TYPE *STAILQ_NEXT(struct TYPE *elm, STAILQ_ENTRY NAME);

STAILQ_FOREACH(struct TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);

void STAILQ_REMOVE(STAILQ_HEAD *head, struct TYPE *elm, TYPE,
                        STAILQ_ENTRY NAME);
void STAILQ_REMOVE_HEAD(STAILQ_HEAD *head,
                        STAILQ_ENTRY NAME);

void STAILQ_CONCAT(STAILQ_HEAD *head1, STAILQ_HEAD *head2);

下面是使用示例:

STAILQ_HEAD(listhead, entry) head = STAILQ_HEAD_INITIALIZER(head);
struct entry {
	...
	STAILQ_ENTRY(entry) entries;	/* Singly-linked tail queue. */
	...
} *n1, *n2, *np;

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

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

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

					/* Deletion. */
STAILQ_REMOVE(&head, n2, entry, entries);
free(n2);
					/* Deletion from the head. */
n3 = STAILQ_FIRST(&head);
STAILQ_REMOVE_HEAD(&head, entries);
free(n3);
					/* Forward traversal. */
STAILQ_FOREACH(np, &head, entries)
	np-> ...
					/* Safe forward traversal. */
STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
	np-> ...
	STAILQ_REMOVE(&head, np, entry, entries);
	free(np);
}
					/* Delete. */
while (!STAILQ_EMPTY(&head)) {
	n1 = STAILQ_FIRST(&head);
	STAILQ_REMOVE_HEAD(&head, entries);
	free(n1);
}

2.5 TAILQ双向尾队列详细介绍

尾队列的头部由TAILQ_HEAD()宏定义的结构组成。该结构包含一对指针，一个指向尾队列中的第一个元素，另一个指向尾队列中的最后一个元素。元素是双重链接的，因此可以在不遍历尾队列的情况下删除任意元素。新元素可以添加到队列中，在现有元素之后，在现有元素之前，在队列的头部，或在队列的末尾。一个TAILQ_HEAD结构体声明如下:

TAILQ_HEAD(HEADNAME, TYPE) head;

其中HEADNAME是要定义的结构的名称，struct TYPE是要链接到尾队列的元素的类型。指向尾部队列头部的指针稍后可以声明为:

struct HEADNAME *headp; // (名称head和headp是用户可选择的。)

下面是一些操作:

TAILQ_ENTRY()宏声明了一个连接尾队列中的元素的结构。
TAILQ_INIT()宏初始化由head引用的尾部队列。
尾队列也可以通过使用TAILQ_HEAD_INITIALIZER()宏进行静态初始化。
TAILQ_INSERT_HEAD()宏将新元素elm插入到尾队列的头部。
TAILQ_INSERT_TAIL()宏将新元素elm插入到尾队列的末尾。
TAILQ_INSERT_AFTER()宏将新元素elm插入到元素listelm之后。
TAILQ_INSERT_BEFORE()宏将新元素elm插入到元素listelm之前。
TAILQ_REMOVE()宏从尾部队列中删除元素elm。
TAILQ_REPLACE()宏将列表元素elm替换为新元素elm2。
TAILQ_CONCAT()宏将由head2引用的尾部队列的所有元素连接到由head1引用的尾部队列的末尾，在进程中清空head2。这比删除和插入单个元素更有效，因为它实际上不遍历head2。
TAILQ_FOREACH()和TAILQ_FOREACH_REVERSE()用于遍历尾部队列。TAILQ_FOREACH()从第一个元素开始，一直到最后一个元素。TAILQ_FOREACH_REVERSE()从最后一个元素开始，向第一个元素前进。

宏TAILQ_FOREACH_SAFE()和TAILQ_FOREACH_REVERSE_SAFE()分别沿正向或反向遍历由head引用的列表，依次将每个元素赋值给var。然而，与它们不安全的对应项不同，它们既允许删除var，也允许在循环中安全地释放它，而不会干扰遍历。

可以使用TAILQ_FIRST()、TAILQ_NEXT()、TAILQ_LAST()和TAILQ_PREV()宏手动遍历尾队列或尾队列的任意部分。

应该使用TAILQ_EMPTY()宏来检查尾队列是否为空

下面是函数原型:

#include <sys/queue.h>

TAILQ_ENTRY(TYPE);

TAILQ_HEAD(HEADNAME, TYPE);
TAILQ_HEAD TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head);
void TAILQ_INIT(TAILQ_HEAD *head);

int TAILQ_EMPTY(TAILQ_HEAD *head);

void TAILQ_INSERT_HEAD(TAILQ_HEAD *head,
                        struct TYPE *elm, TAILQ_ENTRY NAME);
void TAILQ_INSERT_TAIL(TAILQ_HEAD *head,
                        struct TYPE *elm, TAILQ_ENTRY NAME);
void TAILQ_INSERT_BEFORE(struct TYPE *listelm,
                        struct TYPE *elm, TAILQ_ENTRY NAME);
void TAILQ_INSERT_AFTER(TAILQ_HEAD *head, struct TYPE *listelm,
                        struct TYPE *elm, TAILQ_ENTRY NAME);

struct TYPE *TAILQ_FIRST(TAILQ_HEAD *head);
struct TYPE *TAILQ_LAST(TAILQ_HEAD *head, HEADNAME);
struct TYPE *TAILQ_PREV(struct TYPE *elm, HEADNAME, TAILQ_ENTRY NAME);
struct TYPE *TAILQ_NEXT(struct TYPE *elm, TAILQ_ENTRY NAME);

TAILQ_FOREACH(struct TYPE *var, TAILQ_HEAD *head,
                        TAILQ_ENTRY NAME);
TAILQ_FOREACH_REVERSE(struct TYPE *var, TAILQ_HEAD *head, HEADNAME,
                        TAILQ_ENTRY NAME);

void TAILQ_REMOVE(TAILQ_HEAD *head, struct TYPE *elm,
                        TAILQ_ENTRY NAME);

void TAILQ_CONCAT(TAILQ_HEAD *head1, TAILQ_HEAD *head2,
                        TAILQ_ENTRY NAME);

下面是实际示例:

TAILQ_HEAD(tailhead, entry) head;
struct entry {
	...
	TAILQ_ENTRY(entry) entries;	/* Tail queue. */
	...
} *n1, *n2, *np;

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

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

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

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

n2 = malloc(sizeof(struct entry));	/* Insert before. */
TAILQ_INSERT_BEFORE(n1, n2, entries);
					/* Forward traversal. */
TAILQ_FOREACH(np, &head, entries)
	np-> ...
					/* Manual forward traversal. */
for (np = n2; np != NULL; np = TAILQ_NEXT(np, entries))
	np-> ...
					/* Delete. */
while ((np = TAILQ_FIRST(&head))) {
	TAILQ_REMOVE(&head, np, entries);
	free(np);
}

Once_day