tailq队列

1 tailq队列介绍#

TAILQ队列是FreeBSD内核中的一种队列数据结构，主要是把队列头抽象成一个单独的结构体。它实现在Linux queue中。

1.1 queue 简介#

img

可以include <sys/queue.h>后直接使用。queue 分为 SLIST、LIST、STAILQ、TAILQ、CIRCLEQ 。queue 的所有源码都是宏定义，因此完全包含于queue.h当中，无需编译为库文件。

可以从toolchains或者系统路径/usr/include/x86_64-linux-gnu/sys/queue.h找到实现。

img

1.2 SLIST#

SLIST 是Singly-linked List 的缩写，意为单向无尾链表。

img

1.3 STAILQ#

单向有尾链表，节点n为尾节点。

img

1.4 LIST#

双向无尾链表。

img

1.5 TAILQ#

双向有尾链表。

img

1.6 CIRCLEQ#

双向循环链表。

img

2 TAILQ实现原理图解#

双向有尾链表,也就是有一个表头和表尾，表头指向节点1和尾节点。

2.1 描述前一个和下一个元素的结构#

1
2
3
4
5
6
7
8
9
10
11
12
13
#define TAILQ_ENTRY(type)                                                   \
struct {                                                                    \
    struct type *tqe_next;      /* next element */                          \
    struct type **tqe_prev;     /* address of previous next element */      \
}

/*tqe_next是指向下一个元素的指针，tqe_prev是指向前一个元素的tqe_next地址，对它解引用后
（*tqe_priv）指向当前元素的地址。*/
如：
struct item{
　　int val;
　　TAILQ_ENTRY(item) entries;
};

img

2.2 队列头#

1
2
3
4
5
6
#define    TAILQ_HEAD(name, type)                        \
struct name {                                \
    struct type *tqh_first;    /* first element */            \
    struct type **tqh_last;    /* addr of last next element */        \
}
STAILQ_HEAD(my_tailq,  tailq_entry) queue_head;

img

先看TAILQ_HEAD:

1
2
3
tqh_first为队列第一个元素的地址；
tqh_last为最后一个元素tqe_next的地址；
tqh_last指向的指针为0；

再看TAILQ_ENTRY:

1
2
3
tqe_next为队列下一个元素的地址；
tqe_prev为队列上一个元素tqe_next的地址；
tqe_prev指向的指针为当前元素的地址；

2.3 初始化#

img

1
2
3
4
#define TAILQ_INIT(head) do {                                               \
    (head)->tqh_first = NULL;                                               \
    (head)->tqh_last = &(head)->tqh_first;                                  \
} while (0)

2.4 插入元素#

1
2
3
4
5
6
#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 (0)

2.4.1 插入1个元素#

  1. 将要插入的node加入到尾部：

    img

1
2
(elm)->field.tqe_next = NULL;                         
(elm)->field.tqe_prev = (head)->tqh_last;//将要插入的节点prev指向最后一个node

  1. 更新头节点:

    img

1
2
*(head)->tqh_last = (elm);          
(head)->tqh_last = &(elm)->field.tqe_next;

2.4.2 同理插入多个元素#

同理多个元素时尾插。

  1. 将要插入的node加入到尾部:

    img

  2. 更新头节点:

img

1
2
*(head)->tqh_last = (elm);           //尾节点指向新的尾巴
(head)->tqh_last = &(elm)->field.tqe_next; //head的last指向新的尾巴

2.5 删除元素#

1
2
3
4
5
6
7
#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 (0)

我们现在要把val=3的elm删除：
elm中的tqe_next不为空，表示elm不是尾节点。那么

1
2
(elm)->field.tqe_next->field.tqe_prev = (elm)->field.tqe_prev;
*(elm)->field.tqe_prev = (elm)->field.tqe_next;

这2句执行完后:

img

然后free掉该elm,

img

同理再删除val=2的elm：

img

然后free掉该elm，

img

最后如果要把val=4的elm删除：

elm中的tqe_next为空，表示elm是尾节点。那么，

1
2
(head)->tqh_last = (elm)->field.tqe_prev;               //让head的last指向新的尾巴        
*(elm)->field.tqe_prev = (elm)->field.tqe_next;    //让elm的前一个node的next指向该elm的后一个node

img

2.6 第一个元素#

1
#define        TAILQ_FIRST(head)                ((head)->tqh_first)

2.7 最后一个元素#

1
2
#define        TAILQ_LAST(head, headname) \
(*(((struct headname *)((head)->tqh_last))->tqh_last))

这个实现看起来有点绕，我们先做一个实验:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef struct _QUEUE_ITEM {
    int value;
    TAILQ_ENTRY(QUEUE_ITEM) entries;
}QUEUE_ITEM;

TAILQ_HEAD(TAIL_QUEUE, QUEUE_ITEM) queue_head;

int main(int argc, char **argv) {
    QUEUE_ITEM *item[5];
    TAILQ_INIT(&queue_head);

    int i = 0;
    for (i = 0; i < 5; i += 1) {
        item[i] = (struct QUEUE_ITEM*)malloc(sizeof(QUEUE_ITEM));
        item[i]->value = i;
        TAILQ_INSERT_TAIL(&queue_head, item[i], entries);
    }

    for(i = 0; i < 5; i += 1) {
            printf("item[%d]: item:%#x, next:%#x,&next:%#x, prev:%#x, *prev:%#x\n",
　　　　　　　　i, item[i], item[i]->entries.tqe_next, &(item[i]->entries.tqe_next), item[i]->entries.tqe_prev, *(item[i]->entries.tqe_prev));
    }

    printf("queue_head:%#x, first:%#x, last:%#x\n", &queue_head, queue_head.tqh_first, queue_head.tqh_last);
    printf("last item:%p\n", TAILQ_LAST(&queue_head, TAIL_QUEUE));
}

打印结果如下:
img

可以用图形来描述:
img

TAILQ_LAST(&queue_head, TAIL_QUEUE);这句话展开:
(*(((struct TAIL_QUEUE*)((&queue_head)->tqh_last))->tqh_last))

((struct TAIL_QUEUE*)((&queue_head)->tqh_last))这句话,我们把地址0x601060代入进去得0x602098，即为：

img

然后(((struct TAIL_QUEUE*)((&queue_head)->tqh_last))->tqh_last)得到0x602078,
认真的同学此时已经发现，此时对应倒数第二元素的next地址，

最后取(*(((struct TAIL_QUEUE*)((&queue_head)->tqh_last))->tqh_last))得到0x602090,这就是最后一个元素的地址。

总结：这里核心其实就是把最后一个元素的entries成员当成head指针来使用。因为本质上最后一个节点的TAILQ_ENTRY域和TAILQ_HEAD是同样的结构。

2.8 下一个元素#

1
#define        TAILQ_NEXT(elm, field)                ((elm)->field.tqe_next)

2.9 前一个元素#

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

这里和TAILQ_LAST原理一样，将0x602090代入进去得:
img
然后对*(0x602058)得0x602070,即得到了前一个node的地址。

2.10 判空#

1
#define        TAILQ_EMPTY(head)                ((head)->tqh_first == NULL)

2.11 判满#

1
#define        TAILQ_FIRST(head)                ((head)->tqh_first)

2.12 遍历#

1
2
3
4
#define        TAILQ_FOREACH(var, head, field)                                        \
for ((var) = ((head)->tqh_first);                                \
(var);                                                        \
(var) = ((var)->field.tqe_next))

2.13 倒遍历#

1
2
3
4
#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)))

当看懂之前的最后一个元素原理时，倒遍历的实现是不是超级简单。