libevent中的例子中使用的是FreeBSD下的queue.h,在linux的/usr/include/sys/queue.h也有该头文件,但是是一个缩减版本,而且没有看到queue 的access method,不知道是不是跟我们的linux服务器版本有关,没办法google了一下,找到了FreeBSD 下queue.h的定义,我们看一下tail queue的定义
#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*/ \
}
#define TAILQ_INIT(head) do { \
(head)->tqh_first = NULL; \
(head)->tqh_last = &(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_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_FIRST(head) ((head)->tqh_first)
#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
....
我们就先分析上面的这些定义,先看个应用的例子
#include
#include
#include "queue.h" struct QUEUE_ITEM{ int value; TAILQ_ENTRY(QUEUE_ITEM) entries; }; TAILQ_HEAD(,QUEUE_ITEM) queue_head; int main(int argc,char **argv){ struct QUEUE_ITEM *item; struct QUEUE_ITEM *tmp_item; TAILQ_INIT(&queue_head); int i=0; for(i=5;i<10;i+=2){ item=malloc(sizeof(item)); item->value=i; TAILQ_INSERT_TAIL(&queue_head, item, entries); } struct QUEUE_ITEM *ins_item; ins_item=malloc(sizeof(ins_item)); ins_item->value=100; TAILQ_INSERT_BEFORE(item,ins_item,entries); tmp_item=TAILQ_FIRST(&queue_head); printf("first element is %d\n",tmp_item->value); tmp_item=TAILQ_NEXT(tmp_item,entries); printf("next element is %d\n",tmp_item->value); tmp_item=TAILQ_NEXT(tmp_item,entries); printf("next element is %d\n",tmp_item->value); tmp_item=TAILQ_NEXT(tmp_item,entries); printf("next element is %d\n",tmp_item->value); }
first element is 5
next element is 7
next element is 100
next element is 9
分析:
QUEUE_ITEM 是我们定义的存放在队列里的东东,简单起见只包括一个int值
TAILQ_ENTRY(QUEUE_ITEM) entries 主要是存放下一个对象和前一个对象的指针,具体见 header
根据头文件进行宏替换后,实际我们声明的是这样的结构:
struct QUEUE_ITEM{
int value;
struct {
struct QUEUE_ITEM *tqe_next;
struct QUEUE_ITEM **tqe_prev;
}entries;
};
TAILQ_HEAD(,QUEUE_ITEM) queue_head; 实际是
struct {
struct QUEUE_ITEM *tqh_first;
struct QUEUE_ITEM **tqh_last;
}queue_head;
接着我们定义了QUEUE_ITEM的两个指针变量item和tmp_item
TAILQ_INIT(&queue_head); 相当于是
do {
(&queue_head)->tqh_first = NULL;
(&queue_head)->tqh_last = &(&queue_head)->tqh_first;
} while (0);
head的初始化如 下图1
接着我们通过循环分配了几个元素,并赋值
TAILQ_INSERT_TAIL(&queue_head, item, entries); 相当于执行
do {
(item)->entries.tqe_next = NULL;
(item)->entries.tqe_prev = (&queue_head)->tqh_last;
*(&queue_head)->tqh_last = (item);
(&queue_head)->tqh_last = &(item)->entries.tqe_next;
} while (0);
也就是我们的循环执行下面代码段,结果分析见图2,3
for(i=5;i<10;i+=2){
item=malloc(sizeof(item));
item->value=i;
do {
(item)->entries.tqe_next = NULL;
//首次执行相当于item->entries.tqe_prev=&(&queue_head)->tqh_first
//以后执行相当于是(item)->entries.tqe_prev=&(前一个item)->entries.tqe_next;
(ite