TAILQ-双向有尾队列

简介

TAILQ(双向有尾队列)是 FreeBSD/linux 内核对双向队列操作的一种抽象，在/usr/include/sys/queue.h 文件中实现各种定义。

尾队列能实现操作队列需要的各种操作：插入元素，删除元素，遍历队列等。优点是插入元素很快。

在一些著名的开源库中(如DPDK,libevent)有广泛的应用

定义

双向有尾队列有一个表头和表尾，表头指向节点 1 和尾节点

TAILQ队列有HEAD和ENTRY两种基本的数据结构：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// 队列元素
#define TAILQ_ENTRY(type)         \
struct {                          \
    struct type *tqe_next;        \
    struct type **tqe_prev;       \
}

//
struct tailq_entry {
　　int val;
　　TAILQ_ENTRY(int_node);
};

// 队列头
#define  TAILQ_HEAD(name, type)        \
struct name {                          \
    struct type *tqh_first;     /*队列第一个元素的地址*/       \
    struct type **tqh_last;     /**/       \
}
STAILQ_HEAD(my_tailq,  tailq_entry) queue_head;

注意：数据结构中的filed都是type类型的指针(或者是二级指针)，这里的type是用户的队列元素类型，

将ENTRY结构内嵌到用户的QUEUE_ITEM结构中：

1
2
struct QUEUE_ITEM{
    int value;

和 linux list 区别

和Linux中list的组织方式不一样，后者是单纯地将struct list_head作为链表的一个挂接点，并没有用户的信息，具体差别可以看下图：

TAILQ 队列的操作

TAILQ提供了多种操作队列的API,比如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
TAILQ_HEAD(name, type)
TAILQ_ENTRY(type)
TAILQ_EMPTY(head)
TAILQ_FIRST(head)
TAILQ_FOREACH(var, head, field)
TAILQ_INIT(head)
TAILQ_INSERT_AFTER(head, listelm, elm, field)
TAILQ_INSERT_BEFORE(listelm, elm, field)
TAILQ_INSERT_TAIL(head, elm, field)
.....

TAILQ队列中为什么tqh_prev和tqh_last要使用二级指针

要搞清楚这个问题，我们可以考虑如果不使用二级指针会怎么样？就像定义成下面这样。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#define    FAKE_TAILQ_HEAD(name, type)                        \
struct name {                                \
    struct type *tqh_first;    /* first element */            \
    struct type *tqh_last;    /* last element */        \
}

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

如果我们想要删除队列的任意一个元素，对FAKE_TAILQ，我们需要特殊处理该元素是第一个元素的情况(第一个元素的tqe_prev指针为空)，而TAILQ就没有这个烦恼！

**TAILQ队列的遍历性能**

Linux中的list只将struct list_head作为用户元素的挂接点，因此在正向遍历链表时，需要使用container_of这类接口才能获取用户的数据，而TAILQ由于tqe_next指针直接指向用户元素的类型，所以理论上，正向遍历TAILQ比list更快.但逆向遍历时,由于TAILQ的取用prev元素的操作比next麻烦的多，因此逆向遍历是比正向慢的：

1
2
#define    TAILQ_PREV(elm, headname, field)                \
    (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

TAILQ-双向有尾队列

TAILQ-双向有尾队列

简介

定义

和 linux list 区别

TAILQ 队列的操作

**TAILQ队列中为什么tqh_prev和tqh_last要使用二级指针**

参考

相关文章：

TAILQ队列中为什么tqh_prev和tqh_last要使用二级指针