引子
模块中用到队列，先自己实现了一个：
//队列所要包含的元素类型(简化)
typedef struct packet_s
{
int
data;
struct
packet_s *next; //链表方式链接各个元素结点
} packet_t;
//队列类型
typedef struct
{
struct
packet_s *first; //指向第一个元素结点
struct
packet_s *tail; //指向最后一个元素结点
} packetQueue_t;
//队列定义
packetQueue_t packetQueue;
//队列访问接口，实现都比较简单，修改指针就行。略。
void packetQueue_init(packetQueue_t *pktQueue); //队列初始化
void packetQueue_push(packetQueue_t *pktQueue, packet_t *pkt);
//入队
packet_t packetQueue_pop(packetQueue_t *pktQueue); //出队
上面的队列用起来还顺手，不过，没过多久模块需要加入新功能。新功能需要用到新的元素类型及队列，但由于元素类型不同，上面的队列访问函数代码不能重用。重新针对新元素重复实现队列不是好的软件工程实践。
那么，存在能容纳各种元素类型的队列吗？如果使用C++的话，STL中的queue能做到，因为C++有模版。但对于C语言来说，就需要使用宏的技巧。最
近也在看libevent的源码，刚好发现它里面的队列实现完全采用宏，队列操作代码能够重用。有牛人的代码在，那就好办了。下面就解析下
libevent中队列的接口和实现，记录下来以备项目中使用。
libevent中的队列代码其实用的是OpenBSD内核源码中的queue.h。Linux(/usr/include/sys)也有这个文件，使用man
queue能了解queue.h中接口如何使用。不过相对于libevent中的queue.h，linux下的queue.h有些接口没有，man
queue也就看不到。所以下面简述libevent的queue.h。
接口
先通过样例体会下queue.h中队列的接口的使用，详细的接口参考queue.h文件。在下面的附录也列出了queue.h中关于队列的代码。
#include
#include
#include "queue.h"
//struct element要放入队列，就在其定义中加入
//TAILQ_ENTRY(element) entries;
typedef struct element_s {
int
data;
TAILQ_ENTRY(element_s) entries;
} element_t;
int main()
{
element_t *p = NULL;
element_t *q = NULL;
element_t *curr = NULL;
//定义队列
TAILQ_HEAD(queue_s, element_s) queueHead;
//队列初始化
TAILQ_INIT(&queueHead);
//尾部插入，入队
p =
malloc(sizeof(element_t));
p->data = 1;
TAILQ_INSERT_TAIL(&queueHead, p,
entries);
q =
malloc(sizeof(element_t));
q->data = 2;
TAILQ_INSERT_TAIL(&queueHead, q,
entries);
//遍历队列，输出数据
TAILQ_FOREACH(curr, &queueHead,
entries) {
printf("%d\n",
curr->data);
}
//从头部删除，出队
p =
TAILQ_FIRST(&queueHead);
TAILQ_REMOVE(&queueHead, p,
entries);
//输出队列尾部元素
p =
TAILQ_LAST(&queueHead, queue_s) {
printf("%d\n", p->data);
exit(EXIT_SUCCESS);
}
下面看看上面的宏是如何实现的。
实现
先看加入元素结构体定义中的TAILQ_ENTRY，它的作用是在元素中加入两个指针，链接上前后两个元素。
#define TAILQ_ENTRY(type)
\
struct {
\
struct
type *tqe_next; \
struct
type **tqe_prev; \
}
注意的地方是：第二个元素是指针的指针。这与一般数据结构书中的惯例不同。一般数据结构书中第二个元素是指针，不是指针的指针。使用指针的指针很巧妙，到TAILQ_INSERT_TAIL代码时说明为什么这么设计。
TAILQ_HEAD和TAILQ_INIT的实现比较简单，前者定义了由两个指针组成的结构体（即队列类型），后者初始化。
#define TAILQ_HEAD(name, type)
\
struct name {
\
struct
type *tqh_first;
\
struct
type **tqh_last;
\
}
#define TAILQ_INIT(head) do {
\
(head)->tqh_first= NULL;
\
(head)->tqh_last=
&(head)->tqh_first;\
} while (0)
TAILQ_INSERT_TAIL的作用是在队列的尾部插入元素，其实现代码：
#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)
上面代码没有任何if判断操作，这就体现出TAILQ_ENTRY和TAIL_HEAD中第二个字段使用指针的指针的作用了。假如像一般数据结构书的惯例
一样，都使用指针。因为队列头结点与队列元素结点的类型不同，那么对于队列中第一个元素结点的prev指针就要设为NULL，以及队列类型中的last赋
值为NULL表示空队列。如果这么设计，实现队列尾部插入时就肯定有个if判断操作，也就是类似于如下代码：
#define TAILQ_INSERT_TAIL(head,elm, field) do {
\
(elm)->field.tqe_next= NULL;
\
(elm)->field.tqe_prev=
(head)->tqh_last;
\
if((head)->tqh_last == NULL)
\
(head)->tqh_first = elem;
\
else
\
(head)->tqh_last->next
=elem;
\
} while (0)
对于最基本的数据结构中的最经常用到的尾部插入操作（入队）而言，使用没有if判断的实现代码效率高一些。
可以比较体会下严蔚敏的《数据结构》中的队列的实现，它之中使用了一个多余的元素头结点，也使得入队的操作没有if判断操作。
TAILQ_INSERT_HEAD的作用是在队列的第一个元素前插入新元素，其实现如下，比较简单，无非是指针的操作。
#define TAILQ_INSERT_HEAD(head,elm, field) do {
\
if(((elm)->field.tqe_next =
(head)->tqh_first) != NULL)
\
(head)->tqh_first->field.tqe_prev=
\
&(elm)->field.tqe_next;
\
else
\
(head)->tqh_last=
&(elm)->field.tqe_next;
\
(head)->tqh_first= (elm);
\
(elm)->field.tqe_prev=
&(head)->tqh_first;
\
} while (0)
TAILQ_FOREACH和TAILQ_FIRST的实现代码略。详细的看下面的附录中的代码，比较简单
TAILQ_LAST的作用是计算出队列最后一个元素的地址，它的实现就有点难懂了，用到了TAILQ_ENTRY和TAILQ_HEAD内存布局一样的知识点：
#define TAILQ_LAST(head,headname) \
(*(((struct headname
*)((head)->tqh_last))->tqh_last))
队列中的tqh_last字段的值是队列最后一个元素的tqe_next的地址，不是最后一个元素的地址。怎么计算出最后一个元素的地址呢？
(structheadname
*)(head)->tqh_last获得最后一个元素的tqe_next的地址，并强制转换成队列指针类型，再对其用->tqh_last
就相当于获得了最后一个元素的tqe_prev地址（因为TAILQ_ENTRY和TAILQ_HEAD内存布局一样），然后解引用就得到了最后一个元素
的地址。很巧妙！
其它接口的实现请看queue.h文件，略。有了上面的知识，就很简单了。
总结
开源软件中有很多相当好的代码，特别是一些基本数据结构都有比较高效的实现。有时间要多看和体会，用到自己的代码中，能帮助提高开发效率。
附录
queue.h文件中tailqueue相关代码如下。完整的queue.h代码可以先下载libevent库代码，然后在其compat/sys目录下找到。
#define TAILQ_HEAD(name, type)
\
struct name {
\
structtype *tqh_first;
\
structtype **tqh_last;
\
}
#defineTAILQ_HEAD_INITIALIZER(head)
\
{NULL,
&(head).tqh_first }
#define TAILQ_ENTRY(type)
\
struct {
\
structtype *tqe_next;
\
structtype **tqe_prev;
\
}
#define TAILQ_FIRST(head)
((head)->tqh_first)
#define TAILQ_END(head)
NULL
#define TAILQ_NEXT(elm, field)
((elm)->field.tqe_next)
#define TAILQ_LAST(head,headname)
\
(*(((structheadname
*)((head)->tqh_last))->tqh_last))
#define TAILQ_PREV(elm, headname,field)
\
(*(((structheadname
*)((elm)->field.tqe_prev))->tqh_last))
#define TAILQ_EMPTY(head)
\
(TAILQ_FIRST(head)==
TAILQ_END(head))
#define TAILQ_FOREACH(var, head,field)
\
for((var)= TAILQ_FIRST(head);
\
(var) != TAILQ_END(head);
\
(var) = TAILQ_NEXT(var, field))
#defineTAILQ_FOREACH_REVERSE(var, head, headname, field)
\
for((var)= TAILQ_LAST(head,
headname);
\
(var) != TAILQ_END(head);
\
(var) = TAILQ_PREV(var, headname, field))
#define TAILQ_INIT(head) do {
\
(head)->tqh_first= NULL;
\
(head)->tqh_last=
&(head)->tqh_first;
\
} while (0)
#define TAILQ_INSERT_HEAD(head,elm, field) do {
\
if(((elm)->field.tqe_next =
(head)->tqh_first) != NULL)
\
(head)->tqh_first->field.tqe_prev=
\
&(elm)->field.tqe_next;
\
else
\
(head)->tqh_last=
&(elm)->field.tqe_next;
\
(head)->tqh_first= (elm);
\
(elm)->field.tqe_prev=
&(head)->tqh_first;
\
} while (0)
#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)
#define TAILQ_INSERT_AFTER(head,listelm, elm, field) do {
\
if(((elm)->field.tqe_next =
(listelm)->field.tqe_next) != NULL)\
(elm)->field.tqe_next->field.tqe_prev=
\
&(elm)->field.tqe_next;
\
else
\
(head)->tqh_last=
&(elm)->field.tqe_next;
\
(listelm)->field.tqe_next= (elm);
\
(elm)->field.tqe_prev=
&(listelm)->field.tqe_next;
\
} while (0)
#define TAILQ_INSERT_BEFORE(listelm, elm, field) do {
\
(elm)->field.tqe_prev=
(listelm)->field.tqe_prev;
\
(elm)->field.tqe_next= (listelm);
\
*(listelm)->field.tqe_prev= (elm);
\
(listelm)->field.tqe_prev=
&(elm)->field.tqe_next;
\
} while (0)
#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)
#define TAILQ_REPLACE(head, elm,elm2, field) do {
\
if(((elm2)->field.tqe_next =
(elm)->field.tqe_next) != NULL)
\
(elm2)->field.tqe_next->field.tqe_prev=
\
&(elm2)->field.tqe_next;
\
else
\
(head)->tqh_last=
&(elm2)->field.tqe_next;
\
(elm2)->field.tqe_prev=
(elm)->field.tqe_prev;
\
*(elm2)->field.tqe_prev= (elm2);
\
} while (0)
转载自：http://blog.sina.com.cn/s/blog_603e7371010120ck.html
