出處:? http://blog.csdn.net/luotuo44/article/details/38374009

? ? ? ??Libevent源碼中有一個queue.h文件，位于compat/sys目錄下。該文件里面定義了5個數據結構，其中TAILQ_QUEUE是使得最廣泛的。本文就說一下這個數據結構。

隊列結構體：

? ? ? ??TAILQ_QUEUE由下面兩個結構體一起配合工作。

#define TAILQ_HEAD(name, type) \ struct name { \struct type *tqh_first; /* first element */ \struct type **tqh_last; /* addr of last next element */ \ }//和前面的TAILQ_HEAD不同，這里的結構體并沒有name.即沒有結構體名。 //所以該結構體只能作為一個匿名結構體。所以，它一般都是另外一個結構體 //或者共用體的成員 #define TAILQ_ENTRY(type) \ struct { \struct type *tqe_next; /* next element */ \struct type **tqe_prev; /* address of previous next element */ \ } ? ? ? ??由這兩個結構體配合構造出來的隊列一般如下圖所示：

? ? ? ??

? ? ? ? 圖中，一級指針指向的是queue_entry_t這個結構體，即存儲queue_entry_t這個結構體的地址值。二級指針存儲的是一級地址變量的地址值。所以二級指針指向的是圖中的一級指針，而非結構體。圖中的1,2, 3為隊列元素保存的一些值。

隊列操作宏函數以及使用例子：

? ? ? ??除了這兩個結構體，在queue.h文件中，還為TAILQ_QUEUE定義了一系列的訪問和操作函數。很不幸，它們是一些宏定義。這里就簡單貼幾個函數（準確來說，不是函數）的代碼。

#define TAILQ_FIRST(head) ((head)->tqh_first)#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)#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_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)

? ? ? ??這些宏是很難看的，也沒必要直接去看這些宏。下面來看一個使用例子。有例子更容易理解。

//隊列中的元素結構體。它有一個值，并且有前向指針和后向指針 //通過前后像指針，把隊列中的節點(元素)連接起來 struct queue_entry_t {int value;//從TAILQ_ENTRY的定義可知，它只能是結構體或者共用體的成員變量TAILQ_ENTRY(queue_entry_t)entry; };//定義一個結構體，結構體名為queue_head_t，成員變量類型為queue_entry_t //就像有頭節點的鏈表那樣，這個是隊列頭。它有兩個指針，分別指向隊列的頭和尾 TAILQ_HEAD(queue_head_t, queue_entry_t);int main(int argc, char **argv) {struct queue_head_t queue_head;struct queue_entry_t *q, *p, *s, *new_item;int i;TAILQ_INIT(&queue_head);for(i = 0; i < 3; ++i){p = (struct queue_entry_t*)malloc(sizeof(struct queue_entry_t));p->value = i;//第三個參數entry的寫法很怪，居然是一個成員變量名(field)TAILQ_INSERT_TAIL(&queue_head, p, entry);//在隊尾插入數據}q = (struct queue_entry_t*)malloc(sizeof(struct queue_entry_t));q->value = 10;TAILQ_INSERT_HEAD(&queue_head, q, entry);//在隊頭插入數據//現在q指向隊頭元素、p指向隊尾元素s = (struct queue_entry_t*)malloc(sizeof(struct queue_entry_t));s->value = 20;//在隊頭元素q的后面插入元素TAILQ_INSERT_AFTER(&queue_head, q, s, entry);s = (struct queue_entry_t*)malloc(sizeof(struct queue_entry_t));s->value = 30;//在隊尾元素p的前面插入元素TAILQ_INSERT_BEFORE(p, s, entry);//現在進行輸出//獲取第一個元素s = TAILQ_FIRST(&queue_head);printf("the first entry is %d\n", s->value);//獲取下一個元素s = TAILQ_NEXT(s, entry);printf("the second entry is %d\n\n", s->value);//刪除第二個元素, 但并沒有釋放s指向元素的內存TAILQ_REMOVE(&queue_head, s, entry);free(s);new_item = (struct queue_entry_t*)malloc(sizeof(struct queue_entry_t));new_item->value = 100;s = TAILQ_FIRST(&queue_head);//用new_iten替換第一個元素TAILQ_REPLACE(&queue_head, s, new_item, entry);printf("now, print again\n");i = 0;TAILQ_FOREACH(p, &queue_head, entry)//用foreach遍歷所有元素{printf("the %dth entry is %d\n", i, p->value);}p = TAILQ_LAST(&queue_head, queue_head_t);printf("last is %d\n", p->value);p = TAILQ_PREV(p, queue_head_t, entry);printf("the entry before last is %d\n", p->value); }

? ? ? ??例子并不難看懂。這里就不多講了。

展開宏函數：

? ? ? ??下面把這些宏翻譯一下(即展開)，顯示出它們的本來面貌。這當然不是用人工方式去翻譯。而是用gcc 的-E選項。

? ? ? ??閱讀代碼時要注意，tqe_prev和tqh_last都是二級指針，行為會有點難理解。平常我們接觸到的雙向鏈表，next和prev成員都是一級指針。對于像鏈表A->B->C（把它們想象成雙向鏈表），通常B的prev指向A這個結構體本身。此時，B->prev->next指向了本身。但隊列Libevent的TAILQ_QUEUE，B的prev是一個二級指向，它指向的是A結構體的next成員。此時，*B->prev就指向了本身。當然，這并不能說用二級指針就方便。我覺得用二級指針理解起來更難，編寫代碼更容易出錯。

//隊列中的元素結構體。它有一個值，并且有前向指針和后向指針 //通過前后像指針，把隊列中的節點連接起來 struct queue_entry_t {int value;struct{struct queue_entry_t *tqe_next;struct queue_entry_t **tqe_prev;}entry; };//就像有頭節點的鏈表那樣，這個是隊列頭。它有兩個指針，分別指向隊列的頭和尾 struct queue_head_t {struct queue_entry_t *tqh_first;struct queue_entry_t **tqh_last; };int main(int argc, char **argv) {struct queue_head_t queue_head;struct queue_entry_t *q, *p, *s, *new_item;int i;//TAILQ_INIT(&queue_head);do{(&queue_head)->tqh_first = 0;//tqh_last是二級指針，這里指向一級指針(&queue_head)->tqh_last = &(&queue_head)->tqh_first;}while(0);for(i = 0; i < 3; ++i){p = (struct queue_entry_t*)malloc(sizeof(struct queue_entry_t));p->value = i;//TAILQ_INSERT_TAIL(&queue_head, p, entry);在隊尾插入數據do{(p)->entry.tqe_next = 0;//tqh_last存儲的是最后一個元素(隊列節點)tqe_next成員//的地址。所以，tqe_prev指向了tqe_next。(p)->entry.tqe_prev = (&queue_head)->tqh_last;//tqh_last存儲的是最后一個元素(隊列節點)tqe_next成員//的地址，所以*(&queue_head)->tqh_last修改的是最后一個//元素的tqe_next成員的值，使得tqe_next指向*p(新的隊列//節點)。*(&queue_head)->tqh_last = (p);//隊頭結構體（queue_head）的tqh_last成員保存新隊列節點的//tqe_next成員的地址值。即讓tqh_last指向tqe_next。(&queue_head)->tqh_last = &(p)->entry.tqe_next;}while(0);}q = (struct queue_entry_t*)malloc(sizeof(struct queue_entry_t));q->value = 10;//TAILQ_INSERT_HEAD(&queue_head, q, entry);在隊頭插入數據do {//queue_head隊列中已經有節點(元素了)。要對第一個元素進行修改if(((q)->entry.tqe_next = (&queue_head)->tqh_first) != 0)(&queue_head)->tqh_first->entry.tqe_prev = &(q)->entry.tqe_next;else//queue_head隊列目前是空的，還沒有任何節點（元素）。修改queue_head即可(&queue_head)->tqh_last = &(q)->entry.tqe_next;//queue_head的first指針指向要插入的節點*q(&queue_head)->tqh_first = (q);(q)->entry.tqe_prev = &(&queue_head)->tqh_first;}while(0);//現在q指向隊頭元素、p指向隊尾元素s = (struct queue_entry_t*)malloc(sizeof(struct queue_entry_t));s->value = 20;//TAILQ_INSERT_AFTER(&queue_head, q, s, entry);在隊頭元素q的后面插入元素do{//q不是最后隊列中最后一個節點。要對q后面的元素進行修改if (((s)->entry.tqe_next = (q)->entry.tqe_next) != 0)(s)->entry.tqe_next->entry.tqe_prev = &(s)->entry.tqe_next;else//q是最后一個元素。對queue_head修改即可(&queue_head)->tqh_last = &(s)->entry.tqe_next;(q)->entry.tqe_next = (s);(s)->entry.tqe_prev = &(q)->entry.tqe_next;}while(0);s = (struct queue_entry_t*)malloc(sizeof(struct queue_entry_t));s->value = 30;//TAILQ_INSERT_BEFORE(p, s, entry); 在隊尾元素p的前面插入元素do{//無需判斷節點p前面是否還有元素。因為即使沒有元素，queue_head的兩個//指針從功能上也相當于一個元素。這點是采用二級指針的一大好處。(s)->entry.tqe_prev = (p)->entry.tqe_prev;(s)->entry.tqe_next = (p);*(p)->entry.tqe_prev = (s);(p)->entry.tqe_prev = &(s)->entry.tqe_next;}while(0);//現在進行輸出// s = TAILQ_FIRST(&queue_head);s = ((&queue_head)->tqh_first);printf("the first entry is %d\n", s->value);// s = TAILQ_NEXT(s, entry);s = ((s)->entry.tqe_next);printf("the second entry is %d\n\n", s->value);//刪除第二個元素, 但并沒有釋放s指向元素的內存//TAILQ_REMOVE(&queue_head, s, entry);do{if (((s)->entry.tqe_next) != 0)(s)->entry.tqe_next->entry.tqe_prev = (s)->entry.tqe_prev;else (&queue_head)->tqh_last = (s)->entry.tqe_prev;*(s)->entry.tqe_prev = (s)->entry.tqe_next;}while(0);free(s);new_item = (struct queue_entry_t*)malloc(sizeof(struct queue_entry_t));new_item->value = 100;//s = TAILQ_FIRST(&queue_head);s = ((&queue_head)->tqh_first);//用new_iten替換第一個元素//TAILQ_REPLACE(&queue_head, s, new_item, entry);do{if (((new_item)->entry.tqe_next = (s)->entry.tqe_next) != 0)(new_item)->entry.tqe_next->entry.tqe_prev = &(new_item)->entry.tqe_next;else(&queue_head)->tqh_last = &(new_item)->entry.tqe_next;(new_item)->entry.tqe_prev = (s)->entry.tqe_prev;*(new_item)->entry.tqe_prev = (new_item);}while(0);printf("now, print again\n");i = 0;//TAILQ_FOREACH(p, &queue_head, entry)//用foreach遍歷所有元素for((p) = ((&queue_head)->tqh_first); (p) != 0;(p) = ((p)->entry.tqe_next)){printf("the %dth entry is %d\n", i, p->value);}//p = TAILQ_LAST(&queue_head, queue_head_t);p = (*(((struct queue_head_t *)((&queue_head)->tqh_last))->tqh_last));printf("last is %d\n", p->value);//p = TAILQ_PREV(p, queue_head_t, entry);p = (*(((struct queue_head_t *)((p)->entry.tqe_prev))->tqh_last));printf("the entry before last is %d\n", p->value); }

? ? ? ??代碼中有一些注釋，不懂的可以看看。其實對于鏈表操作，別人用文字說再多都對自己理解幫助不大。只有自己動手一步步把鏈表操作都畫出來，這樣才能完全理解。

?

特殊指針操作：

? ? ? ??最后那兩個操作宏函數有點難理解，現在來講一下。在講之前，先看一個關于C語言指針的例子。
#include<stdio.h>struct item_t {int a;int b;int c; };struct entry_t {int a;int b; };int main() {struct item_t item = { 1, 2, 3};entry_t *p = (entry_t*)(&item.b);printf("a = %d, b = %d\n", p->a, p->b);return 0; } ? ? ? ??代碼輸出的結果是：a = 2, b = 3

? ? ? ??對于entry_t *p， 指針p指向的內存地址為&item.b。此時對于編譯器來說，它認為從&item.b這個地址開始，是一個entry_t結構體的內存區域。并且把前4個字節當作entry_t成員變量a的值，后4個字節當作entry_t成員變量b的值。所以就有了a = 2, b = 3這個輸出。

? ? ? ??好了，現在開始講解那兩個難看懂的宏。先看一張圖。

? ? ? ??

? ? ? ??雖然本文最前面的圖布局更好看一點，但這張圖才更能反映文中這兩個結構體的內存布局。不錯，tqe_next是在tqe_prev的前面。這使得tqe_next、tqe_prev于tqh_first、tqh_last的內存布局一樣。一級指針在前，二級指針在后。

? ? ? ??現在來解析代碼中最后兩個宏函數。

隊尾節點：

//p = TAILQ_LAST(&queue_head, queue_head_t); p = (*(((struct queue_head_t *)((&queue_head)->tqh_last))->tqh_last));

? ? ? ??首先是(&queue_head)->tqh_last，它的值是最后一個元素的tqe_next這個成員變量的地址。然后把這個值強制轉換成struct queue_head_t *指針。此時，相當于有一個匿名的struct queue_head_t類型指針q。它指向的地址為隊列的最后一個節點的tqe_next成員變量的地址。無論一級還是二級指針，其都是指向另外一個地址。只是二級指針只能指向一個一級指針的地址。

? ? ? ??此時，在編譯器看來，從tqe_next這個變量的地址開始，是一個struct queue_head_t結構體的內存區域。并且可以將代碼簡寫成：
p = (*(q->tqh_last));

? ? ? ??

? ? ? ??回想一下剛才的那個例子。q->tqh_last的值就是上圖中最后一個節點的tqe_prev成員變量的值。所以*(q->tqh_last))就相當于*tqe_prev。注意，變量tqe_prev是一個二級指針，它指向倒數第二個節點的tqe_next成員。所以*tqe_prev獲取了倒數第二個節點的tqe_next成員的值。它的值就是最后一個節點的地址。最后，將這個地址賦值給p，此時p指向最后一個節點。完成了任務。好復雜的過程。

前一個節點：

? ? ? ??現在來看一下最后那個宏函數，代碼如下：

//p = TAILQ_PREV(p, queue_head_t, entry); p = (*(((struct queue_head_t *)((p)->entry.tqe_prev))->tqh_last)); ? ? ? ??注意，右邊的p此時是指向最后一個節點(元素)的。所以(p)->entry.tqe_prev就是倒數第二個節點tqe_next成員的地址。然后又強制轉換成struct queue_head_t指針。同樣，假設一個匿名的struct queue_head_t *q;此時，宏函數可以轉換成:

p = (*((q)->tqh_last));

? ? ? ??同樣，在編譯器看來，從倒數第二個參數節點tqe_next的地址開始，是一個structqueue_head_t結構體的內存區域。所以tqh_last實際值是tqe_prev變量上的值，即tqe_prev指向的地址。*((q)->tqh_last)就是*tqe_prev，即獲取tqe_prev指向的倒數第三個節點的tqe_next的值。而該值正是倒數第二個節點的地址。將這個地址賦值給p，此時，p就指向了倒數第二個節點。完成了TAILQ_PREV函數名的功能。

?

? ? ? ??這個過程確實有點復雜。而且還涉及到強制類型轉換。

? ? ? ??其實，在TAILQ_LAST(&queue_head, queue_head_t);中，既然都可以獲取最后一個節點的tqe_next的地址值，那么直接將該值 + 4就可以得到tqe_precv的地址值了（假設為pp）。有了該地址值pp，那么直接**pp就可以得到最后一個節點的地址了。代碼如下：
struct queue_entry_t **pp = (&queue_head)->tqh_last; pp += 1; //加1個指針的偏移量，在32位的系統中，就等于+4//因為這里得到的是二級指針的地址值，所以按理來說，得到的是一個 //三級指針。故要用強制轉換成三級指針。 struct queue_entry_t ***ppp = (struct queue_entry_t ***)pp;s = **ppp; printf("the last is %d\n", s->value);

? ? ? ??該代碼雖然能得到正確的結果，但總感覺直接加上一個偏移量的方式太粗暴了。

? ? ? ??有一點要提出，+1那里并不會因為在64位的系統就不能運行，一樣能正確運行的。因為1不是表示一個字節，而是一個指針的偏移量。在64位的系統上一個指針的偏移量為8字節。這種”指針 + 數值”，實際其增加的值為:數值 + sizeof(*指針)。不信的話，可以試一下char指針、int指針、結構體指針(結構體要有多個成員)。

?

?

? ? ? ??好了，還是回到最開始的問題上吧。這個TAILQ_QUEUE隊列是由兩部分組成：隊列頭和隊列節點。在Libevent中，隊列頭一般是event_base結構體的一個成員變量，而隊列節點則是event結構體。比如event_base結構體里面有一個struct event_list eventqueue;其中，結構體struct event_list如下定義：
//event_struct.h TAILQ_HEAD (event_list, event);//所以event_list的定義展開后如下： struct event_list {struct event *tqh_first;struct event **tqh_last; }; ? ? ? ??在event結構體中，則有幾個TAILQ_ENTRY(event)類型的成員變量。這是因為根據不同的條件，采用不同的隊列把這些event結構體連在一起，放到一條隊列中。

總結

以上是生活随笔為你收集整理的Libevent源码分析-----TAILQ_QUEUE队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。