??queue.h最早來源于FreeBSD逢享，出自某遠(yuǎn)古大神之手，里面定義了5種隊(duì)列，singly-linked lists, lists, simple queues, tail queues, and circular queues。今天我們重點(diǎn)看下里面的tail queues闸衫。
/* $OpenBSD: queue.h,v 1.16 2000/09/07 19:47:59 art Exp $ */
/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */
?? 我們來看下代碼結(jié)構(gòu)：
/*
* Tail queue definitions.
*/
#define TAILQ_HEAD(name, type) \
struct name { \
struct type *tqh_first; /* first element */ \
struct type **tqh_last; /* addr of last next element */ \
}
#define TAILQ_HEAD_INITIALIZER(head) \
{ NULL, &(head).tqh_first }
#define TAILQ_ENTRY(type) \
struct { \
struct type *tqe_next; /* next element */ \
struct type **tqe_prev; /* address of previous next element */ \
}
/*
* tail queue access methods
*/
#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) \
(*(((struct headname *)((head)->tqh_last))->tqh_last))
/* XXX */
#define TAILQ_PREV(elm, headname, field) \
(*(((struct headname *)((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))
#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
for((var) = TAILQ_LAST(head, headname); \
(var) != TAILQ_END(head); \
(var) = TAILQ_PREV(var, headname, field))
/*
* Tail queue functions.
*/
#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)
??我們?cè)倏磦€(gè)例子：
#include <stdio.h>
#include <stdlib.h>
struct QUEUE_ITEM {
int value;
TAILQ_ENTRY(QUEUE_ITEM) entries;
};
TAILQ_HEAD(TAIL_QUEUE, 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 = (struct QUEUE_ITEM*)malloc(sizeof(QUEUE_ITEM));
item->value = i;
TAILQ_INSERT_TAIL(&queue_head, item, entries);
}
struct QUEUE_ITEM *ins_item;
ins_item = (struct QUEUE_ITEM*)malloc(sizeof(QUEUE_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);
getchar();
}
??內(nèi)存分布如圖：
??我們先看TAILQ_HEAD：
tqh_first為隊(duì)列第一個(gè)元素的地址献丑；
tqh_last為最后一個(gè)元素tqe_next的地址末捣；
tqh_last指向的指針為0；
??再看TAILQ_ENTRY：
tqe_next為隊(duì)列下一個(gè)元素的地址创橄；
tqe_prev為隊(duì)列上一個(gè)元素tqe_next的地址塔粒；
tqe_prev指向的指針為當(dāng)前元素的地址；
??于是筐摘，我們?cè)谀X子里形成了對(duì)這個(gè)隊(duì)列的大致結(jié)構(gòu)卒茬。
??下面我們逐一深度分析隊(duì)列的操作。
#define TAILQ_HEAD_INITIALIZER(head) { NULL, &(head).tqh_first }
#define TAILQ_INIT(head) do { \
(head)->tqh_first = NULL; \
(head)->tqh_last = &(head)->tqh_first; \
} while (0)
??這兩個(gè)宏代表了隊(duì)列的初始化咖熟，將tqh_first賦值為NULL圃酵，再將tqh_last 賦值為tqh_first的地址，如此做馍管，當(dāng)?shù)谝淮翁砑釉貢r(shí)郭赐，對(duì)tqh_last 指向的元素操作既是對(duì)tqh_first操作。
#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) \
(*(((struct headname *)((head)->tqh_last))->tqh_last))
/* XXX */
#define TAILQ_PREV(elm, headname, field) \
(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
??TAILQ_LAST确沸，TAILQ_PREV這兩個(gè)宏可能比較難理解捌锭。
??先看TAILQ_LAST，我們思考下罗捎，如何獲取最后一個(gè)元素的地址观谦，從圖上看，最后一個(gè)元素的tqe_prev指向的值即是最后一個(gè)元素的地址桨菜，由文章前面可知豁状，最后一個(gè)元素的tqe_next值為(head)->tqh_last，如何從tqe_next獲取到tqe_prev指向的值倒得，因?yàn)門AILQ_ENTRY與TAILQ_HEAD的內(nèi)存布局是一樣的泻红，稍加思考，于是就有了這個(gè)宏表達(dá)式霞掺。TAILQ_PREV類似谊路。
??這里要注意，TAILQ_ENTRY與TAILQ_HEAD的內(nèi)存布局是一樣的菩彬，為什么TAILQ_LAST和TAILQ_PREV中不將(head)->tqh_last)轉(zhuǎn)換為TAILQ_HEAD而不是轉(zhuǎn)換為TAILQ_ENTRY是因?yàn)門AILQ_ENTRY這個(gè)結(jié)構(gòu)體是直接定義在你用戶定義的結(jié)構(gòu)體中缠劝，無(wú)法獲取他的類型來進(jìn)行轉(zhuǎn)換。
??其他的宏都比較簡(jiǎn)單挤巡，直來直去剩彬，比較好理解酷麦，這里就不詳述了矿卑。以后有問題再作記錄。
