TAILQqueue是FreeBSD内核中的一种队列数据结构，在一些著名的开源库（如DPDK、libevent）中广泛使用。TAILQ队列的定义TAILQ队列有两个基本数据结构，HEAD和ENTRY#defineTAILQ_HEAD(name,type)\structname{\structtype*tqh_first;/*第一个元素*/\结构类型**tqh_last;/*最后一个下一个元素的地址*/\}#defineTAILQ_ENTRY(type)\struct{\structtype*tqe_next;/*下一个元素*/\structtype**tqe_prev;/*前一个下一个元素的addr*/\}注：data结构中的字段是type类型的指针（或二级指针），其中type是用户的队列元素类型，并将ENTRY结构嵌入到用户的QUEUE_ITEM结构中：structQUEUE_ITEM{intvalue;TAILQ_ENTRY(QUEUE_ITEM)个条目；};TAILQ_HEAD(headname,QUEUE_ITEM)queue_head;这与Linux中list的组织方式不同。后者只是简单的使用structlist_head作为链表的挂载点，没有用户信息。具体区别见下图：TAILQ队列操作TAILQ提供了多种操作队列的API，如：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)....这些接口的实现和更多的操作接口你可以参考为什么tqh_prev和tqh_last在FreeBSDqueueTAILQ队列中使用二级指针。为了弄清楚这个问题，我们可以考虑如果不使用二级指针会怎样？定义如下#defineFAKE_TAILQ_HEAD(name,type)\structname{\structtype*tqh_first;/*第一个元素*/\结构类型*tqh_last;/*最后一个元素*/\}#defineFAKE_TAILQ_ENTRY(type)\struct{\structtype*tqe_next;/*下一个元素*/\结构类型*tqe_prev;/*previouselement*/\}比较TAILQ_HEAD和FAKE_TAILQ_HEAD（注意红线和绿线的区别）如果我们要删除队列中的任何一个元素，对于FAKE_TAILQ，我们需要特殊处理元素是第一个元素（第一个元素的tqe_prev指针为空），而TAILQ就没有这个烦恼！TAILQ队列的遍历性能。Linux中的列表仅使用structlist_head作为用户元素的附着点。因此，在正向遍历链表时，需要使用container_of等接口获取用户的数据，因为TAILQ的tqe_next指针直接指向用户元素。类型，所以理论上TAILQ的前向遍历比list快。但是在反向遍历时，由于TAILQ取prev元素的操作比next麻烦，所以反向遍历比正向慢：#defineTAILQ_PREV(elm,headname,field)\(*(((structheadname*)((elm)->field.tqe_prev))->tqh_last))以下是附件中代码的测试结果：遍历TAILQ：TAILQ遍历时间为31955usTAILQ反向遍历时间为38699us遍历listlist遍历时间为33062uslistlist遍历时间为35864us附录测试代码bsd.c#include#include#include#defineTAILQ_ENTRY(type)\struct{\structtype*tqe_next;/*下一个元素*/\structtype**tqe_prev;/*前一个下一个元素的地址*/\}#defineTAILQ_HEAD(name,type)\structname{\structtype*tqh_first;/*第一个元素*/\结构类型**tqh_last;/*最后一个元素的地址*/\}#defineTAILQ_FIRST(head)((head)->tqh_first)#defineTAILQ_NEXT(elm,field)((elm)->field.tqe_next)#defineTAILQ_PREV(elm,headname，场地）\(*(((structheadname*)((elm)->field.tqe_prev))->tqh_last))#defineTAILQ_LAST(head,headname)\(*(((structheadname*)((head)->tqh_last))->tqh_last))#defineTAILQ_INIT(head)do{\TAILQ_FIRST((head))=NULL;\(head)->tqh_last=&TAILQ_FIRST((head));\}while(0)#defineTAILQ_INSERT_TAIL(head,elm,field)do{\TAILQ_NEXT((elm),field)=NULL;\(elm)->field.tqe_prev=(head)->tqh_last;\*(head)->tqh_last=(elm);\(head)->tqh_last=&TAILQ_NEXT((elm),field);\}while(0)#defineTAILQ_INSERT_BEFORE(listelm,elm,field)do{\(elm)->field.tqe_prev=(listelm)->field.tqe_prev;\TAILQ_NEXT((elm),字段)=(listelm);\*(listelm)->field.tqe_prev=(elm);\（李stelm)->field.tqe_prev=&TAILQ_NEXT((elm),field);\}while(0)#defineTAILQ_FOREACH(var,head,field)\for((var)=TAILQ_FIRST((head));\(var);\(var)=TAILQ_NEXT((var),field))#定义TAILQ_FOREACH_REVERSE(var,head,headname,field)\for((var)=TAILQ_LAST((head),headname);\(var);\(var)=TAILQ_PREV((var),headname,field))structQUEUE_ITEM{整数值；TAILQ_ENTRY(QUEUE_ITEM)个条目；};TAILQ_HEAD(headname,QUEUE_ITEM)queue_head;#defineITEM_NUM5000000#defineTRAVERSAL20intmain(intargc,char**argv){structQUEUE_ITEM*item;很长的总时间=0；结构时间开始，结束；长长度量[TRAVERSAL]；诠释我=0;TAILQ_INIT(&queue_head);for(i=1;i价值=我；TAILQ_INSERT_TAIL(&queue_head,item,entries);}for(i=0;ivalue++;}gettimeofday(&end,NULL);metric[i]=(end.tv_sec-start.tv_sec)*1000000+(end.tv_usec-start.tv_usec);//以微秒为单位获取运行时间}totaltime=0;对于(i=0;ivalue++;}gettimeofday(&end,NULL);metric[i]=(end.tv_sec-start.tv_sec)*1000000+(end.tv_usec-start.tv_usec);//获取运行ti我微秒}totaltime=0;对于(i=0;i#include#include/*foroffsetof*/#include#definecontainer_of(ptr,type,member)({\consttypeof(((type*)0)->member)*__mptr=(ptr);\(type*)((char*)__mptr-offsetof(type,member));})#definelist_entry(ptr,type,member)\container_of(ptr,type,member)#definelist_first_entry(ptr,type,member)\list_entry((ptr)->next,type,member)#definelist_last_entry(ptr,type,member))\list_entry((ptr)->prev,type,member)#definelist_next_entry(pos,member)\list_entry((pos)->member.next,typeof(*(pos)),member)#definelist_prev_entry(pos,member)\list_entry((pos)->member.prev,typeof(*(pos)),member)#definelist_for_each_entry(pos,head,member)\for(pos=list_first_entry(head,typeof(*pos),member);\&pos->成员!=(head);\pos=list_next_entry(pos,成员))#definelist_for_each_entry_reverse(pos,head,member)\for(pos=list_last_entry(head,typeof(*pos),member);\&pos->member!=(head);\pos=list_prev_entry(pos,成员))#defineLIST_HEAD_INIT(name){&(name),&(name)}#defineLIST_HEAD(name)\structlist_headname=LIST_HEAD_INIT(name)structlist_head{structlist_head*next,*prev;};staticinlinevoidINIT_LIST_HEAD(structlist_head*list){list->next=list;list->prev=list;}staticinlinevoid__list_add(structlist_head*new,structlist_head*prev,structlist_head*next){next->prev=new;新的-＆GT；下一个=下一个；新->上一个=上一个；prev->next=new;}staticinlinevoidlist_add(structlist_head*new,structlist_head*head){__list_add(new,head,head->next);}structQUEUE_ITEM{intvalue;structlist_headnode;};LIST_HEAD(queue_head);#defineITEM_NUM5000000#defineTRAVERSAL20intmain(){inti=0;结构QUEUE_ITEM*项目;很长的总时间=0；结构时间开始，结束；长长度量[TRAVERSAL]；for(i=1;i价值=我；INIT_LIST_HEAD(&item->node);list_add(&item->node,&queue_head);}for(i=0;ivalue++;}gettimeofday(&end,NULL);指标[i]=(end.tv_sec-start.tv_sec)*1000000+(end.tv_usec-开始.tv_usec);//以微秒为单位获取运行时间}totaltime=0;对于(i=0;ivalue++;}gettimeofday(&end,NULL);metric[i]=(end.tv_sec-start.tv_sec)*1000000+(end.tv_usec-start.tv_usec);//以微秒为单位获取运行时间}totaltime=0;对于(i=0;i
