libevent源码分析--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 <stdio.h>
#include <stdlib.h>
#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 

 struct QUEUE_ITEM{
	int value;
        struct {			
            struct QUEUE_ITEM *tqe_next;	
	    struct QUEUE_ITEM **tqe_prev;
        }entries;
};

struct {                  
    struct QUEUE_ITEM *tqh_first;     
    struct QUEUE_ITEM **tqh_last;     
}queue_head; 

do {  
    (&queue_head)->tqh_first = NULL;               
    (&queue_head)->tqh_last = &(&queue_head)->tqh_first;        
} while (0);

    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);  

    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;  
            (item)->entries.tqe_prev = (&queue_head)->tqh_last;  
            //首次执行相当于(&queue_head)->tqh_first=item  
            //以后执行相当于是(前一个item)->entries.tqe_next=当前item  
            *(&queue_head)->tqh_last = (item);  
            (&queue_head)->tqh_last = &(item)->entries.tqe_next;  
        } while (0);  
    }  

最终建立的链表结构如图,下面看一下insert操作,经过宏替换后代码如下  
  
struct QUEUE_ITEM *ins_item;  
ins_item=malloc(sizeof(ins_item));  
ins_item->value=100;  
  
do {  
    (ins_item)->entries.tqe_prev = (item)->entries.tqe_prev;  
    (ins_item)->entries.tqe_next = (item);  
    //这句话体现了TAILQ的特色,tqe_prev是前一个元素的下个元素地址,  
    //所以正好应该是当前插入item的地址  
    *(item)->entries.tqe_prev = (ins_item);  
    (item)->entries.tqe_prev = &(ins_item)->entries.tqe_next;  
} while (0);

总结:TAILQ的最大特点就是每个entry的二级指针tqe_prev其存放的是前一个元素的下个元素地址,呵呵,听起来都很拗口
我现在就是不知道为什么linux的queue.h只有建立tailq的宏定义而缺少所有的access method,初涉linux c编程,请大家指教

附经过宏替换后的所有代码

#include "stdio.h"
#include "stdlib.h"
struct QUEUE_ITEM{
	int value;
	struct {
		struct QUEUE_ITEM *tqe_next;
		struct QUEUE_ITEM **tqe_prev;
	}entries;
};
struct {
	struct QUEUE_ITEM *tqh_first;
	struct QUEUE_ITEM **tqh_last;
}queue_head;

int main(int argc,char **argv){
	struct QUEUE_ITEM *item;
	struct QUEUE_ITEM *tmp_item;

	do {
		(&queue_head)->tqh_first = NULL;
		(&queue_head)->tqh_last = &(&queue_head)->tqh_first;
	} while (0);

	int i=0;
	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;
			(item)->entries.tqe_prev = (&queue_head)->tqh_last;
			//首次执行相当于(&queue_head)->tqh_first=item
			//以后执行相当于是(前一个item)->entries.tqe_next=当前item
			*(&queue_head)->tqh_last = (item);
			(&queue_head)->tqh_last = &(item)->entries.tqe_next;
		} while (0);
	}

	struct QUEUE_ITEM *ins_item;
	ins_item=malloc(sizeof(ins_item));

	ins_item->value=100;
	do {
		(ins_item)->entries.tqe_prev = (item)->entries.tqe_prev;
		(ins_item)->entries.tqe_next = (item);
		*(item)->entries.tqe_prev = (ins_item);
		(item)->entries.tqe_prev = &(ins_item)->entries.tqe_next;
	} while (0);

	tmp_item=((&queue_head)->tqh_first);
	printf("first element is %d\n",tmp_item->value);

	tmp_item=((tmp_item)->entries.tqe_next);
	printf("next element is %d\n",tmp_item->value);

	tmp_item=((tmp_item)->entries.tqe_next);
	printf("next element is %d\n",tmp_item->value);

	tmp_item=((tmp_item)->entries.tqe_next);
	printf("next element is %d\n",tmp_item->value);

}

libevent源码分析--QUEUE的使用（基本的数据结构）

原文：http://blog.csdn.net/yusiguyuan/article/details/19629659