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)))

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