TAILQ-队列之一二事 | 乐趣区

TAILQ队列是FreeBSD内核中的一种队列数据结构，在一些著名的开源库中(如DPDK,libevent)有广泛的应用。

`TAILQ`队列的定义

TAILQ队列有HEAD和ENTRY两种基本的数据结构

#define    TAILQ_HEAD(name, type)                        \struct name {                                \    struct type *tqh_first;    /* first element */            \    struct type **tqh_last;    /* addr of last next element */        \}#define TAILQ_ENTRY(type)                                            \struct {                                                             \    struct type *tqe_next;  /* next element */                       \    struct type **tqe_prev;/* addr of previous next element*/        \}

注意：数据结构中的filed都是type类型的指针(或者是二级指针)，这里的type是用户的队列元素类型，，将ENTRY结构内嵌到用户的QUEUE_ITEM结构中：

struct QUEUE_ITEM{      int value;      TAILQ_ENTRY(QUEUE_ITEM) entries;  };  TAILQ_HEAD(headname,QUEUE_ITEM) queue_head;

这和Linux中list的组织方式不一样，后者是单纯地将struct list_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).....

这些接口的实现和更多的操作接口可以参考 FreeBSD queue

`TAILQ`队列中为什么`tqh_prev`和`tqh_last`要使用二级指针

要搞清楚这个问题，我们可以考虑如果不使用二级指针会怎么样？就像定义成下面这样。

#define    FAKE_TAILQ_HEAD(name, type)                        \struct name {                                \    struct type *tqh_first;    /* first element */            \    struct type *tqh_last;    /* last element */        \}#define FAKE_TAILQ_ENTRY(type)                                            \struct {                                                             \    struct type *tqe_next;  /* next element */                       \    struct type *tqe_prev;  /*   previous element*/        \}

对比一下TAILQ_HEAD和FAKE_TAILQ_HEAD (注意其中的红线和绿线的区别)

如果我们想要删除队列的任意一个元素，对FAKE_TAILQ，我们需要特殊处理该元素是第一个元素的情况(第一个元素的tqe_prev指针为空)，而TAILQ就没有这个烦恼！

`TAILQ`队列的遍历性能

Linux中的list只将struct list_head作为用户元素的挂接点，因此在正向遍历链表时，需要使用container_of这类接口才能获取用户的数据，而TAILQ由于tqe_next指针直接指向用户元素的类型，所以理论上，正向遍历TAILQ比list更快.但逆向遍历时,由于TAILQ的取用prev元素的操作比next麻烦的多，因此逆向遍历是比正向慢的：

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

以下是用附件中的代码测试的结果：

遍历TAILQ:

TAILQ traversal time is 31955 usTAILQ reverse traversal time is 38699 us

遍历list

list traversal time is 33062 uslist list traversal time is 35864 us

附录

测试代码 `bsd.c`

#include <stdio.h>#include <stdlib.h> #include <sys/time.h>#define TAILQ_ENTRY(type)                                            \struct {                                                             \    struct type *tqe_next;  /* next element */                       \    struct type **tqe_prev;/* addr of previous next element*/        \}   #define    TAILQ_HEAD(name, type)                        \struct name {                                \    struct type *tqh_first;    /* first element */            \    struct type **tqh_last;    /* addr of last next element */        \}#define    TAILQ_FIRST(head)    ((head)->tqh_first)#define    TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)#define    TAILQ_PREV(elm, headname, field)                \    (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))    #define    TAILQ_LAST(head, headname)                    \    (*(((struct headname *)((head)->tqh_last))->tqh_last))        #define    TAILQ_INIT(head) do {                        \    TAILQ_FIRST((head)) = NULL;                    \    (head)->tqh_last = &TAILQ_FIRST((head));            \} while (0)#define TAILQ_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)#define    TAILQ_INSERT_BEFORE(listelm, elm, field) do {            \    (elm)->field.tqe_prev = (listelm)->field.tqe_prev;        \    TAILQ_NEXT((elm), field) = (listelm);                \    *(listelm)->field.tqe_prev = (elm);                \    (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);        \} while (0)#define    TAILQ_FOREACH(var, head, field)                    \    for ((var) = TAILQ_FIRST((head));                \        (var);                            \        (var) = TAILQ_NEXT((var), field))#define    TAILQ_FOREACH_REVERSE(var, head, headname, field)        \    for ((var) = TAILQ_LAST((head), headname);            \        (var);                            \        (var) = TAILQ_PREV((var), headname, field))        struct QUEUE_ITEM{      int value;      TAILQ_ENTRY(QUEUE_ITEM) entries;  };  TAILQ_HEAD(headname,QUEUE_ITEM) queue_head;  #define ITEM_NUM 5000000#define TRAVERSAL 20int main(int argc,char **argv){      struct QUEUE_ITEM *item;       long long totaltime = 0;    struct timeval start,end;    long long metric[TRAVERSAL];    int i = 0;        TAILQ_INIT(&queue_head);      for(i=1;i<ITEM_NUM;i+=1){          item=malloc(sizeof(struct QUEUE_ITEM));          item->value=i;          TAILQ_INSERT_TAIL(&queue_head, item, entries);      }          for (i = 0; i < TRAVERSAL; i++)    {        gettimeofday(&start,NULL);        TAILQ_FOREACH(item, &queue_head, entries)        {            item->value++;        }           gettimeofday(&end,NULL);        metric[i] = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec); // get the run time by microsecond    }       totaltime = 0;    for (i=0;i<TRAVERSAL;i++)    {        totaltime += metric[i];    }    printf("TAILQ traversal time is %lld us\n", totaltime/TRAVERSAL);    for (i = 0; i < TRAVERSAL; i++)    {        gettimeofday(&start,NULL);        TAILQ_FOREACH_REVERSE(item, &queue_head, headname,entries)        {            item->value++;        }           gettimeofday(&end,NULL);        metric[i] = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec); // get the run time by microsecond    }        totaltime = 0;    for (i=0;i<TRAVERSAL;i++)    {        totaltime += metric[i];    }        printf("TAILQ reverse traversal time is %lld us\n", totaltime/TRAVERSAL);    return 0; }

测试代码 `list.c`

#include <stdio.h>#include <stdlib.h>#include <stddef.h>    /* for offsetof */#include <sys/time.h>#define container_of(ptr, type, member) ({            \    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \    (type *)( (char *)__mptr - offsetof(type,member) );})#define list_entry(ptr, type, member) \    container_of(ptr, type, member)#define list_first_entry(ptr, type, member) \    list_entry((ptr)->next, type, member)#define list_last_entry(ptr, type, member) \    list_entry((ptr)->prev, type, member)#define list_next_entry(pos, member) \    list_entry((pos)->member.next, typeof(*(pos)), member)#define list_prev_entry(pos, member) \    list_entry((pos)->member.prev, typeof(*(pos)), member)    #define list_for_each_entry(pos, head, member)                \    for (pos = list_first_entry(head, typeof(*pos), member);    \         &pos->member != (head);                    \         pos = list_next_entry(pos, member))#define list_for_each_entry_reverse(pos, head, member)            \    for (pos = list_last_entry(head, typeof(*pos), member);        \         &pos->member != (head);                     \         pos = list_prev_entry(pos, member))         #define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \    struct list_head name = LIST_HEAD_INIT(name)struct list_head {    struct list_head *next, *prev;};static inline void INIT_LIST_HEAD(struct list_head *list){    list->next = list;    list->prev = list;}static inline void __list_add(struct list_head *new,                  struct list_head *prev,                  struct list_head *next){    next->prev = new;    new->next = next;    new->prev = prev;    prev->next = new;}static inline void list_add(struct list_head *new, struct list_head *head){    __list_add(new, head, head->next);}struct QUEUE_ITEM{    int value;    struct list_head node;};LIST_HEAD(queue_head);#define ITEM_NUM 5000000#define TRAVERSAL 20int main(){    int i = 0;    struct QUEUE_ITEM *item;    long long totaltime = 0;    struct timeval start,end;    long long metric[TRAVERSAL];        for(i=1;i<ITEM_NUM;i+=1){        item=malloc(sizeof(struct QUEUE_ITEM));        item->value = i;        INIT_LIST_HEAD(&item->node);        list_add(&item->node, &queue_head);    }        for (i = 0; i < TRAVERSAL; i++)    {        gettimeofday(&start,NULL);        list_for_each_entry_reverse(item, &queue_head, node)        {            item->value++;        }           gettimeofday(&end,NULL);        metric[i] = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec); // get the run time by microsecond    }       totaltime = 0;    for (i=0;i<TRAVERSAL;i++)    {        totaltime += metric[i];    }    printf("list traversal time is %lld us\n", totaltime/TRAVERSAL);        for (i = 0; i < TRAVERSAL; i++)    {        gettimeofday(&start,NULL);        list_for_each_entry(item, &queue_head, node)        {            item->value++;        }           gettimeofday(&end,NULL);        metric[i] = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec); // get the run time by microsecond    }       totaltime = 0;    for (i=0;i<TRAVERSAL;i++)    {        totaltime += metric[i];    }    printf("list list traversal time is %lld us\n", totaltime/TRAVERSAL);    return 0;}

TAILQ队列的定义

TAILQ队列的操作

TAILQ队列中为什么tqh_prev和tqh_last要使用二级指针

TAILQ队列的遍历性能

附录

测试代码 bsd.c

测试代码 list.c