libevent源码分析-- queue.h中TAILQ_QUEUE的理解

libevent中的例子中使用的是FreeBSD下的queue.h,在linux的/usr/include/sys/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)
....
 #define TAILQ_LAST(head, headname)                  \
     (*(((struct headname *)((head)->tqh_last))->tqh_last))
 /* XXX */
 #define TAILQ_PREV(elm, headname, field)                \
    (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

 

我们就先分析上面的这些定义,先看个应用的例子

#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
分析:
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;  
            (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其存放的是前一个元素的下个元素地址, 也就是前一个元素中tqe_next指针的地址。

对于头节点来说，tqh_first指针是第一个节点的指针；tqh_last是一个二级指针，这个指针指向的是最后一个节点的tqe_next域的地址，其实这个指针是NULL，因为在插入操作时，(item)->entries.tqe_next = NULL; 这句代码将心元素的tqe_next域置为空。然后再取址赋值给tqe_last，觉得没什么意思，但是也不知道为何，也许是理解有误差。
附经过宏替换后的所有代码

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

}

总结：可以看出来，在使用TAILQ_QUEUE的时候，在存储元素是自己定义的，这里只有一个int,为了能将存储的形式表示为链表，需要在存储的节点内添加一个入口entries，这个入口中一个是指向下一个节点的指针，一个是存放下一个节点地址的指针（也就是二级指针），同时再盛情一个头节点，头节点中也有两部分内容，一个是第一个节点的指针，一个是最后一个节点地址的指针（也就是二级指针，这个指针的取值也就是下一个新添加节点的地址），这样就可以将所有的元素链起来。

       如果仔细看那个头文件，还是有一些问题需要深入思考的（对于想我这样的初学者）看下头文件中红色部分，看看觉得是不是很奇怪，为何强制转化为struct headname*,head->tqh_last是struct type**类型，二级指针转化为另一个类型的一级指针。

        分析之前，先说几句预热一下：

           所以指针（不管一级、二级或者指向的类型），它不过就是4字节(32bit CPU)或者8字节(64bit CPU)而已，和名字无关。 比如我有下面两个结构体：

 struct neme1{
struct name1 *first；
struct name1 **last;
} header;

struct name2{
struct name2 *next;
struct name2 **prev;
} type;
        如果我知道了type的next域的地址，我想要获取type的prev元素里面的内容怎么办？ 最直接点的实现就是next域的地址加4再访问就好了，但是在不同平台的机子移植性很差，另一种比较优雅的实现方法就比较好，我使用header和type具有相同的内存分布来做文章， 因为next域指向的元素类型跟type一样，那么我把type类型强制转换为header类型，访问header的last域就可以了。知道type指针next域的地址加4个字节可以访问type的prev域，那么将type转化为header类型，并且知道了last域的值，也就是访问了type类型的prev域。

      下面继续分析上面的问题，如果访问tail_queue中最后一个元素，需要TAILQ_LAST(head,headname)；来访问。分解这个宏

    @1 (head)->tqh_last

    @2 (  (struct headname *) (@1) )

    @3   ( *((@2)->tqh_last) )

     @1是最后一个节点的TAILQ_ENTRY(type)中的struct type* tpe_next域的地址，如果我们知道TAILQ_ENTRY(type)中struct type **tqe_pre的值就能得到该节点（该节点就是最后一个节点）的地址值(为何呢？因为tqe_pre是一个二级指针，这个二级指针是前一个节点（倒数第一个节点）中TAILQ_ENTRY(type)的struct type* tpe_next域的地址，这个struct type* tpe_next指向的是它本身的下一个节点（最后一个节点）的地址，就是最后一个节点的地址)，现在如何获得struct type **tqh_pre是关键所在。仔细观察我们发现TAILQ_ENTRY与TAILQ_HEAD的内存布局实际上是一样的，都是对应两个元素共八个字节，现在有两种方法获得struct type **tqe_pre。   

1.struct type *tqe_next的地址值直接加4

2.将struct type *tqe_next强制转换成head，也就是源代码中的方法

         简单的解析第二种方案就是，将@1强制转化为(struct headname*)，然后再查找tqh_last，这样不就找到了@1中代表的节点的struct type** tpe_prev，但是想下tpe_prev是上一个节点的tpe_next域的地址，上一个节点的tpe_next不就是这个节点的地址么，这样不就得到这个节点的所有信息了么！！！（懂了就没必要看下面的了）

          现在主要分析第二中解决方案，@2是一个head* 指针，通过@3之后我们实际得到的是前一个节点的struct type *tqe_next地址的解引用，就是last节点的地址，这里有点迷惑((@2)->tqh_last)实际对应的是TAILQ_ENTRY节点的struct type **tqe_prev元素，它指向的是前一个节点的struct type *tqe_next地址，这样一来我们便能得到最后一个节点的地址了，TAILQ_PREV使用的方法也是一样的。

       总结： 这里面的双端队列以及链表中节点的next与prev指针，它的设计与我们一般的链表以及linux内核的list完全不一样，因为里面的prev根本不是指向前一个节点，而是指向前一个节点的next元素的地址。也许上面的讲解一时无法理解，但是只要记住一点的就是TAILQ_ENTRY与TAILQ_HEAD的内存布局是一样的，为什么TAILQ_LAST和TAILQ_PREV中不将(head)->tqh_last)转换为TAILQ_HEAD而不是转换为TAILQ_ENTRY是因为TAILQ_ENTRY这个结构体是直接定义在你用户定义的结构体中，无法获取他的类型来进行转换。

    可以尝试着分析一下这个宏：

#define TAILQ_PREV(elm, headname, field)                \
        (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
宏的目的是查找某一个节点的前一个节点：

    首先找到这个节点的TAILQ_ENTRY(type)中的tpe_prev域tpe_prev是前一个节点的tpe_next域的地址，如果知道了前一个节点的tpe_prev指针然后再取值就得到这个节点本身的地址），那么将

(elm)->field.tqe_prev)，

强制转化为（struct headname *）然后再取tph_lase就可以得到前一个节点的tpe_prev的值，然后再加*取值即可





版权声明：本文为yusiguyuan原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。