1 tailq队列介绍 TAILQ队列是FreeBSD内核中的一种队列数据结构,主要是把队列头抽象成一个单独的结构体。它实现在Linux queue中。
1.1 queue 简介
可以include <sys/queue.h>后直接使用。queue 分为 SLIST、LIST、STAILQ、TAILQ、CIRCLEQ 。queue 的所有源码都是宏定义,因此完全包含于queue.h当中,无需编译为库文件。
可以从toolchains或者系统路径/usr/include/x86_64-linux-gnu/sys/queue.h找到实现。
1.2 SLIST SLIST 是Singly-linked List 的缩写,意为单向无尾链表。
1.3 STAILQ 单向有尾链表,节点n为尾节点。
1.4 LIST 双向无尾链表。
1.5 TAILQ 双向有尾链表。
1.6 CIRCLEQ 双向循环链表。
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; \ struct type **tqe_prev; \ } 如: struct item{ int val; TAILQ_ENTRY(item) entries; };
2.2 队列头 1 2 3 4 5 6 #define TAILQ_HEAD(name, type) \ struct name { \ struct type *tqh_first; \ struct type **tqh_last; \ } STAILQ_HEAD(my_tailq, tailq_entry) queue_head;
先看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 初始化
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个元素
将要插入的node加入到尾部:
1 2 (elm)->field.tqe_next = NULL; (elm)->field.tqe_prev = (head)->tqh_last;
更新头节点:
1 2 *(head)->tqh_last = (elm); (head)->tqh_last = &(elm)->field.tqe_next;
2.4.2 同理插入多个元素 同理多个元素时尾插。
将要插入的node加入到尾部:
更新头节点:
1 2 *(head)->tqh_last = (elm); (head)->tqh_last = &(elm)->field.tqe_next;
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句执行完后:
然后free掉该elm,
同理再删除val=2的elm:
然后free掉该elm,
最后如果要把val=4的elm删除:
elm中的tqe_next为空,表示elm是尾节点。那么,
1 2 (head)->tqh_last = (elm)->field.tqe_prev; *(elm)->field.tqe_prev = (elm)->field.tqe_next;
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)); }
打印结果如下:
可以用图形来描述:
TAILQ_LAST(&queue_head, TAIL_QUEUE);
这句话展开:(*(((struct TAIL_QUEUE*)((&queue_head)->tqh_last))->tqh_last))
((struct TAIL_QUEUE*)((&queue_head)->tqh_last))
这句话,我们把地址0x601060代入进去得0x602098,即为:
然后(((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代入进去得: 然后对*(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)))
当看懂之前的最后一个元素 原理时,倒遍历的实现是不是超级简单。