尾队列TAILQ

尾队列TAILQ是FreeBSD/linux内核对双向队列操作的一种抽象，在/usr/include/sys/queue.h文件中实现各种定义。
尾队列能实现操作队列需要的各种操作：插入元素，删除元素，遍历队列等。优点是插入元素很快。
DPDK中使用了大量的尾队列。

1、定义尾队列元素TAILQ_ENTRY

代码中使用TAILQ_ENTRY定义尾队列中的一个元素：

展开后即：

这是TAILQ对两个指向前后两个元素指针的抽象，抽象为TAILQ_ENTRY结构体：
tqe_next是指向下一个元素的指针，
tqe_prev是一个二级指针，指针变量的地址，是前一个元素的tqe_next的地址，解引用(*tqe_prev)之后就是前一个元素指向的下一个元素的内存地址

例如，我们声明一个结构体，这个结构体只有一个int型整数，以及指向前一个元素和后一个元素的指针。

宏展开之后就变成：

如图：

但还需要其它手段才能实现数据的存储。

2、创建队列头TAILQ_HEAD

创建队列头的宏TAILQ_HEAD定义如下：

展开后为：

创建一个名为name的结构体，作为尾队列的头结点。
这个宏实际上使用的时候，会展开成为一个结构体，
tqh_first是一个一级指针，指向队列中的第一个元素。
tqh_last是一个二级指针，它指向最后一个元素中的tqe_next（参考上面的TAILQ_ENTRY）变量的地址，指针的地址就是二级指针。
例如：

展开后为：

就创建了一个名为qhead的队列头，队列内容指向的结构体类型为struct int_node。

或者将其用在其它结构体中:

展开后为：

3、初始化队列头TAILQ_INIT

将头指针tqh->first初始化为NULL，尾指针tqh_last(指向指针的指针)指向头指针tqh_first的地址。
如下图

仍以struct int_node为例：

展开后即：

创建了一个名为queue_head的队列头，并对其初始化。
队列指向的结构体为struct int_node。

4、在创建时初始化一个队列头TAILQ_HEAD_INITIALIZER

仍以struct int_node为例：

展开后即为：

5、插入尾队列尾部TAILQ_INSERT_TAIL

插入元素用TAILQ_INSERT_TAIL宏，由于TAILQ中有一个tqh_last的二级指针，所以插入元素直接插到队尾，仅用O(1)时间。

宏定义中第一个元素为队列的头结点，如上文的&queue_head，
第二个元素为要插入的结点，如上文的item，
第三个元素为结点中用TAILQ_ENTRY宏定义的域。

举例说明：
（1）定义

展开后：

（2）初始化

即：

（3）分配一个结点并插入

插入操作展开后即：

通过图形遂句解析插入操作：
第一句， item->next.tqe_next = NULL;
将新元素（数据部分值为2）的tqe_next指向NULL；

第二句， item->next.tqe_prev = (&queue_head)->tqh_last;
将新元素的tqe_prev的值赋值为(& queue_head)->tqh_last，即原来队列中最后一个元素的tqe_next变量的地址，即当前队列头指向的tqh_first的地址：

第三句， *(&queue_head)->tqh_last = item;

将头结点的tqh_last的值，即原队列最后一个元素的tqe_next指向item；

如果原队列为空，则由于当前为向队列中插入第一个结点，
而此时*(&queue_head)->tqh_last的值就是tqh_first的地址，所以这一句也就等价于：
(&queue_head)->tqh_first = item;
也就是将(&queue_head)->tqh_first指向item。

而如果原队列不为空，则(&queue_head)->tqh_last的值为原队列最后一个结点的tqe_next的地址，
这时就变成了该结点的tqe_next指向新插入的结点，
相当于把新结点插入到原队列尾结点的后面。

第四句： (&queue_head)->tqh_last = &(item)->next.tqe_next;
将新元素的tqe_next的地址赋值给头结点的tqh_last指针（指向指针的指针，二级指针）：

6、向队列头部插入新元素TAILQ_INSERT_HEAD

向队列头部插入元素用TAILQ_INSERT_HEAD宏，定义如下：

首先将原队列头部指针赋值给新元素的tqe_next，并判断如果此时指向为空，
如果不为空，说明队列中已经包含其他元素，该原队列中的第一个元素的tqe_prev保存新元素的tqe_next变量的地址；
如果为空， 说明新元素是要插入的第一个元素，则直接将新元素tqe_next变量的地址赋值给头结点的tqh_first；
然后，将队列头部指向新元素，
之后，用新元素的tqe_prev保存队列头部tqh_first的地址。

7、删除队列中的指定元素TAILQ_REMOVE

宏定义中的第一个元素是队列的头结点，如前文的&queue_head，
第二个元素是要删除的结点，如前文的item，
第三个元素是创建的TAILQ_ENTYR宏定义的域。
假设没有删除之前的队列如下所示：

假设要删除队列中的第一个元素，即值为2的元素。
宏定义的第一行首先判断当前元素的tqe_next是否为空，
如果不为空，说明当前元素不是队列中的最后一个元素，
就将当前元素的tqe_prev的值赋值给下一个元素的tqe_prev，让其指向自己的上一个元素；
如果为空，说明当前元素是队列中的最后一个元素，
就将队列头的tqh_last的值保存为当前元素的tqe_prev，
也就是将队列头的尾指针指向当前元素的前一个元素。
结果如图如示：

之后，将当前元素的*tqe_prev的值保存为当前元素的tqe_next的地址，
而当前元素的*tqe_prev的值是前一个元素的tqe_next的值，该值保存的是当前元素的tqe_next的地址，
所以这一语句就是将*tqe_prev的值保存为当前元素的下一个元素的tqe_next的地址：

至此，虽然值为2的元素还连在队列中（只有它连接另的元素，别的元素不指向这个要删除的元素），但如果这时遍历队列的话，已经不会遍历该元素了。
释放该结点之后：

8、其他常用宏

8.1 队列的第一个元素TAILQ_FIRST

8.2 当前元素的下一个元素TAILQ_NEXT

8.3 判断队列是否为空TAILQ_EMPTY

8.4 遍历列表中的每个元素TAILQ_FOREACH

就是利用临时变量var来遍历队列中的每个元素。

参考：http://blog.csdn.net/hunanchenxingyu/article/details/8648794

————————————————————