深入理解TAILQ队列
Notice this artical mostly from :http://blog.csdn.net/hunanchenxingyu/article/details/8648794
I just add some personal understanding and modified some mistakes made by blogger hunanchenxingyu
队列，又稱為佇列（英文queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。
FreeBSD中的TAILQ把整个队列头抽象为一个单独的数据结构，我们先看看FreeBSD中的TAILQ相关宏，然后再举例子理解这些宏。 这里用最简单的一个结构体来理解TAILQ，这个结构体中有一个int型整数，还有两个分别指向前方和后方的指针。
1.描述前一个和下一个元素的结构体
458 #define TAILQ_ENTRY(type) \
459 struct { \
460 struct type *tqe_next; /* next element */ \
461 struct type **tqe_prev; /* address of previous next element */ \
462 TRACEBUF \
463 }
这是TAILQ对两个指向前后两个元素指针的抽象，抽象为TAILQ_ENTRY结构体：tqe_next是指向下一个元素的指针，tqe_prev是一个二级指针，指针变量的地址，是前一个元素的tqe_next的地址，解引用(*tqe_prev)之后就是本元素的内存地址；TRACEBUF是一个调试相关的宏，我们先不管它。举例： 我们声明一个结构体，这个结构体只有一个int 型数据，读者可以改动这个structure成员来实现自己的tail queue，还有前驱和后继指针由TAILQ_ENTRY来实现。
typedef struct ElemType {
int data;
} TqElemType;
struct tailq_node{ TqElemType elem; TAILQ_ENTRY(tailq_node) TQueueField;
};
宏展开之后就变成：
struct int_node{ TqElemType elem; struct {
struct int_node *tqe_next; /* next element */
sturct int_node **tqe_prev; /* address of previous next element */
} TQueueField;
};
例如：结构体成员赋值 2.
2.队列头
TAILQ把整个队列头单独抽象为一个结构体TAILQ_HEAD，如下：
445 /*
446 * Tail queue declarations.
447 */
448 #define TAILQ_HEAD(name, type) \
449 struct name { \
450 struct type *tqh_first; /* first element */ \
451 struct type **tqh_last; /* addr of last next element */ \
452 TRACEBUF \
453 }
这个宏实际上使用的时候，会展开成为一个结构体，tqh_first是一个一级指针，指向队列中的第一个元素；tqh_last是一个二级指针，它指向最后一个元素中的tqe_next（请参考上面的TAILQ_ENTRY），也就是最后一个元素的tqe_next的地址，指针的地址就是二级指针；TRACEBUF是一个用来调试的宏，不用管它。举例： 声明一个叫做queue_head的队列头：
TAILQ_HEAD(my_tailq_head, tailq_node) queue_head;
宏展开之后就会变成（不管TRACEBUF宏）：
struct my_tailq_head {
struct tailq_node *tqh_first; /* first element */
struct tailq_node **tqh_last; /* addr of last next element */
} queue_head;
如图：
用下面的宏初始化这个队列头（TAILQ_FIRST下文'5.'有说明）：
534 #define TAILQ_INIT(head) do { \
535 TAILQ_FIRST((head)) = NULL; \
536 (head)->tqh_last = &TAILQ_FIRST((head)); \
537 QMD_TRACE_HEAD(head); \
538 } while (0)
变成：
3.插入元素
插入元素用TAILQ_INSERT_TAIL宏，由于TAILQ中有一个tqh_last的二级指针，所以插入元素直接插到队尾，仅用O(1)时间。
578 #define TAILQ_INSERT_TAIL(head, elm, field) do { \
579 QMD_TAILQ_CHECK_TAIL(head, field); \
580 TAILQ_NEXT((elm), field) = NULL; \
581 (elm)->field.tqe_prev = (head)->tqh_last; \
582 *(head)->tqh_last = (elm); \
583 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
584 QMD_TRACE_HEAD(head); \
585 QMD_TRACE_ELEM(&(elm)->field); \
586 } while (0)
QMD_TAILQ_CHECK_TAIL，QMD_TRACE_HEAD，QMD_TRACE_ELEM这三个宏和调试信息相关和做一些必要的检查，我们可以先不管,TAILQ_NEXT下文‘6.’有说明；这个宏就是在调整相关的指针指向。我们向一个空队列插入两个元素2来理解这个宏： 3.1 580行让新元素的tqe_next指向空，执行完第580行：
3.2 581行让新元素的tqe_prev赋值为tqh_last，也就是指向队列头中的tqh_first的地址，执行完第581行：
3.3 582行让二级指针tqh_last中的内容指向新元素，也就是tqh_first指向新元素，执行完第582行：
3.4 583行，队列头的tqh_last赋值为新元素的tqe_next的地址（指针的地址，二级指针），执行完第583行：
这就是插入2后的整个链表。
插入元素（续）
插入元素2 后的变形图 如下图 1
（以下图，展示了插入4个tailq_node 的详细过程...）
图 tail queue (please take attention PIC tail queue for next browse)
4.删除元素
删除元素用TAILQ_REMOVE宏
596 #define TAILQ_REMOVE(head, elm, field) do { \
597 QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \
598 QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \
599 QMD_TAILQ_CHECK_NEXT(elm, field); \
600 QMD_TAILQ_CHECK_PREV(elm, field); \
601 if ((TAILQ_NEXT((elm), field)) != NULL) \
602 TAILQ_NEXT((elm), field)->field.tqe_prev = \
603 (elm)->field.tqe_prev; \
604 else { \
605 (head)->tqh_last = (elm)->field.tqe_prev; \
606 QMD_TRACE_HEAD(head); \
607 } \
608 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
609 TRASHIT(*oldnext); \
610 TRASHIT(*oldprev); \
611 QMD_TRACE_ELEM(&(elm)->field); \
612 } while (0)
QMD_SAVELINK，QMD_TAILQ_CHECK_NEXT，QMD_TAILQ_CHECK_PREV，TRASHIT，同样先不管这几个宏。我们从队列中删除一个元素来理解这个宏： 4.1 假设经过上节插入元素2之后，我们用TAILQ_INSERT_TAIL再插入一个元素1，没有删除之前的链表如下图：
现在假设我们删除队列中的第一个元素2 4.2 602和603在调整当前元素的下一个元素的tqe_prev指针，执行完第602行和603行之后：
4.3 608调整当前元素tqe_prev中的内容，执行完第608行之后：
4.4 释放结点2的空间之后，最后的链表：
attention!
we again use 图 tail queue to explain how to remove a tailQueue node (or element) in a tailQueue.
example 1 : choose to delete first tailQueue node in tailQueue
Abviously, NULL != TAILQ_NEXT((elm), field))
Please keep in mind : Do not forget to free the removed tailQueue node (free(elm))
example 2: choose to delete tailQueue node among tailQueue (not last or first tailQueue node in tailQueue)
Abviously, NULL != TAILQ_NEXT((elm), field))
Please keep in mind : Do not forget to free the removed tailQueue node (free(elm);)
example 3: choose to delete last tailQueue node in tailQueue)
Attention here! NULL == TAILQ_NEXT((elm), field))
Please keep in mind : Do not forget to free the removed tailQueue node (free(elm);)
5.队列中的第一个元素
512 #define TAILQ_FIRST(head) ((head)->tqh_first)
6.当前元素的下一个元素
591 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
这个宏比较简单。
7.遍历链表中的每一个元素
用宏TAILQ_FOREACH
514 #define TAILQ_FOREACH(var, head, field) \
515 for ((var) = TAILQ_FIRST((head)); \
516 (var)!= TAILQ_END(head); \
517 (var) = TAILQ_NEXT((var), field))
here simply define TAILQ_END(head) NULL
这个宏就比较简单了，用临时变量var来遍历链表中的每一个元素。 这些宏就是几个操作TAILQ经常使用的宏，还有一些诸如TAILQ_INSERT_HEAD等宏，类似，请自行看代码，这里就不一一叙述了。这篇文章主要是理解相关的宏和插入删除过程，完整的应用例子请看下面的参考文献。
Example 1:
#include
#include
typedef struct ElemType {
int data;
} TqElemType;
#define TRACEBUF /*a debug related MACRO */
/*queue head pointer needed*/
/*TAILQ_FIRST(TAILQ_HEAD *head);*/
#define TAILQ_FIRST(head) ((head)->tqh_first)
/* TAILQ_NEXT(TYPE *elm, TAILQ_ENTRY NAME);*/
#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
#define TAILQ_END(head) NULL
/*1. A structure describe previous and next element */
#define TAILQ_ENTRY(type) \
struct {\
struct type *tqe_next; /*next element*/ \
struct type **tqe_prev; /*address of previous next element*/ \
TRACEBUF \
}
/*
*unfold tailq_node
* struct tailq_node {
* TqElemType elem;
* struct {
* struct tailq_node *tqe_next; //next element
* struct tailq_node **tqe_prev; //address of previous next element
* } TQueueField;
* };
* */
typedef struct tailq_node {
TqElemType elem;
TAILQ_ENTRY(taiq_node) TQueueField;
} TqNode;
/*2. Tailq header*/
/*
* Tail queue declarations.
* */
#define TAILQ_HEAD(name, type) \
struct name { \
struct type *tqh_first; /*first element*/ \
struct type **tqh_last; /*addr of last next element*/ \
TRACEBUF \
}
/*unflod TAILQ_HEAD(my_tailq_head, tailq_node)
* struct my_tailq_head {
* struct tailq_node *tqh_first; //first element
* struct tailq_node **tqh_last; //addr of last next element
* } queue_head;
*
* */
TAILQ_HEAD(my_tailq_head, tailq_node) queue_head;
/*use below MACRO to initalize queue_head*/
#define TAILQ_INIT(head) do { \
TAILQ_FIRST((head)) = NULL; \
(head)->tqh_last = &TAILQ_FIRST((head)); \
/*QMD_TRACE_HEAD(head);*/ \
} while (0)
/*3. Insert element*/
/*Using TAILQ_INSET_TAIL macro to insert element, for TAILQ have a tqh_last pointer to pointer reason, element insert to queue tail directly, O(1) time consumption*/
/*
*'head' here need a pointer that head define by TAILQ_HEAD
*'elm' here need a pointer that elm define by the Data node you need (here is struct tailq_node)
*'field' here is the name defined by TAILQ_ENTRY'
* */
#define TAILQ_INSERT_TAIL(head, elm, field) do { \
/*QMD_TAILQ_CHECK_TAIL(head, field);*/ \
TAILQ_NEXT((elm), field) = NULL; \
(elm)->field.tqe_prev = (head)->tqh_last; \
*(head)->tqh_last = (elm); \
(head)->tqh_last = &TAILQ_NEXT((elm), field); \
/*QMD_TRACE_HEAD(head);*/ \
/*QMD_TRACE_ELEM(&(elm)->field);*/ \
} while(0)
/*4. Remove element(tailq node)*/
/*
*'head' here need a pointer that head define by TAILQ_HEAD
*'elm' here is an already known pointer that define by the Data node you need (here is struct tailq_node)
*'field' here is the name defined by TAILQ_ENTRY'
* */
TqNode *remove_tmp;
#define TAILQ_REMOVE(head, elm, field) do { \
/*QMD_SAVELINK(oldnext, (elm)->field.tqe_next);*/ \
/*QMD_SAVELINK(oldprev, (elm)->field.tqe_prev);*/ \
/*QMD_TAILQ_CHECK_NEXT(elm, field); */ \
/*QMD_TAILQ_CHECK_PREV(elm, field); */ \
if ((TAILQ_NEXT((elm), field)) != NULL) { \
/*TAILQ_NEXT((elm), field)->field.tqe_prev =*/ \
/*error: dereferencing pointer to incomplete type*/ \
remove_tmp = TAILQ_NEXT((elm), field); \
remove_tmp->field.tqe_prev = \
(elm)->field.tqe_prev; \
} \
else { \
(head)->tqh_last = (elm)->field.tqe_prev; \
/*QMD_TRACE_HEAD(head);*/ \
} \
*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
/*TRASHIT(*oldnext); */ \
/*TRASHIT(*oldprev); */ \
/*QMD_TRACE_ELEM(&(elm)->field); */ \
} while(0)
/*5. Get last items*/
/*The maLEAR
*
* tail queue is empty the return value is NULL.*/
/*prototype: TAILQ_LAST(TAILQ_HEAD *head, HEADNAME)*/
#define TAILQ_LAST(head, headname) \
(*(((struct headname *)((head)->tqh_last))->tqh_last))
/*7. traverse every element in tail queue node*/
/*
* 'var' here need a pointer of 'struct tailq_node' which is the Data node that can be defined by yourself.
* 'head' here need a pointer of 'struct my_tailq_head' which the head structure of the queue.
* 'field here is the name defined by TAILQ_ENTRY'
* */
#define TAILQ_FOREACH(var, head, field) \
for ((var) = TAILQ_FIRST((head)); \
(var) != TAILQ_END(head); \
(var) = TAILQ_NEXT((var), field))
int main(int argc, char **argv)
{
printf("/*----------------------------------------------------------*/\n");
printf(" create tailq that referenced by freeBSD/Linux/tailq \n");
printf("/*----------------------------------------------------------*/\n");
printf("Initializing tail queue head ... \n");
TAILQ_INIT(&queue_head);
if (queue_head.tqh_first == *(queue_head.tqh_last)) {
if (NULL == queue_head.tqh_first)
printf("initialize queue head successful!\n");
}
else {
printf("Initialize queue head failed!\n");
}
printf("Inserting 10 Tail queue Node to tail queue ...\n");
int i;
TqNode *tailqNode;
for (i=0; i<10; i++) {
tailqNode = (TqNode *)malloc(sizeof(struct tailq_node));
tailqNode->elem.data = i;
TAILQ_INSERT_TAIL(&queue_head, tailqNode, TQueueField);
}
printf("10 Tail queue Node inserted successful!\n");
printf("Traversing tail queue ...\n");
TAILQ_FOREACH(tailqNode, &queue_head, TQueueField) {
printf("elem->data: %d \n",tailqNode->elem.data);
}
printf("Traversing end!\n");
printf("Removing first tailQueue Node ...\n");
tailqNode = queue_head.tqh_first;
TAILQ_REMOVE(&queue_head, tailqNode, TQueueField);
printf("Traversing tail queue ...\n");
TAILQ_FOREACH(tailqNode, &queue_head, TQueueField) {
printf("elem->data: %d \n",tailqNode->elem.data);
}
printf("Traversing end!\n");
printf("Removing second tailQueue Node ...\n");
tailqNode = TAILQ_FIRST(&queue_head)->TQueueField.tqe_next;
TAILQ_REMOVE(&queue_head, tailqNode, TQueueField);
printf("Traversing tailQueue ...\n");
TAILQ_FOREACH(tailqNode, &queue_head, TQueueField) {
printf("elem->data: %d \n", tailqNode->elem.data);
}
printf("Traversing end!\n");
printf("Print last data in tailQueue ...\n");
tailqNode = TAILQ_LAST(&queue_head, my_tailq_head);
printf("last item: %d\n", tailqNode->elem.data);
printf("Removing last tailQueue Node ...\n");
TAILQ_REMOVE(&queue_head, tailqNode, TQueueField);
printf("Traversing tailQueue ...\n");
TAILQ_FOREACH(tailqNode, &queue_head, TQueueField) {
printf("elem->data: %d\n", tailqNode->elem.data);
}
printf("Traversing end!\n");
return 0;
}
参考资料：
1.FreeBSD官方网站 这里的代码示例是FreeBSD 7.0版本，上面这个链接教你如何获得FreeBSD的代码。
上面这个链接是FreeBSD的tag信息。
2.graphviz画图软件
这里优美的图是用AT&T强大的开源画图工具graphviz生成的。为什么不用visio，dia，diagram designer等拖拉拽的画图工具？因为很难画成心中想要的那种图形，虽然还需要点学习时间，但是掌握之后画拓扑图就是传说中的所想即所得。关于如何用graphviz画出图示中的双向队列，请看我的另一篇博文：
3.其他TAILQ参考资料3.1 来自iteye的一篇很好的文章，举了一个应用TAILQ的例子http://bachmozart.iteye.com/blog/292836/ ，不过个人感觉里面的那个图对二级指针的描述还是不够好。
3.2 这里也提供了一个TAILQ应用的例子 http://blog.linuxphp.org/archives/1485/
3.3 来自FreeBSDchina论坛的讲解
http://blog.csdn.net/jiayp004/article/details/13023027
http://blog.chinaunix.net/uid-17240700-id-3084728.html
