尾队列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

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

原创文章,转载请注明: 转载自孙希栋的博客

本文链接地址: 《尾队列TAILQ》

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Scroll Up