tailq介绍

TAILQ是linux内核对双向队列操作的一种抽象，能实现操作队列需要的各种操作：插入元素，删除元素，遍历队列等，其封装是对应的宏定义，下面详细说明tailq的操作，从定义，初始化，插入，删除和遍历这几个API来介绍，并且提供c++版本的tailq。

tailq的宏定义API

(1)定义：TAILQ_ENTRY(type) 初始化一个type类型的entry

#define TAILQ_ENTRY(type)	\
	struct {			\
		struct type *tqe_next;  /* next element */			\
		struct type **tqe_prev; /* address of previous next element */	\
		TRACEBUF 		\
	}
其中TRACEBUF是一个用来调试的宏
example：
struct node{
	int a, b, c;
	TAILQ_ENTRY(node);
};
展开以后如下：
struct node{
	int a, b, c;
    struct {
		struct node *tqe_next;  /* next element */ 
        sturct node **tqe_prev; /* address of previous next element */
    };
};

(2)定义：TAILQ_HEAD(name, type) 初始化name的结构体，类型为type，初始化头部

#define TAILQ_HEAD(name, type)		\
	struct name {		\
		struct type *tqh_first; /* first element */				\
		struct type **tqh_last; /* addr of last next element */	\
		TRACEBUF 		\
	}
example：
TAILQ_HEAD(head, node) q_head;
展开以后如下：
struct head {
	struct node *tqh_first; /* first element */
	struct node **tqh_last; /* addr of last next element */
} q_head;

(3)初始化：TAILQ_INIT(head) 初始化头部，其中head是上面的TAILQ_HEAD

#define TAILQ_INIT(head) do {                       \
	TAILQ_FIRST((head)) = NULL;                 	\
	(head)->tqh_last = &TAILQ_FIRST((head));		\
	QMD_TRACE_HEAD(head);                       	\
} while (0)
其中QMD_TRACE_HEAD为了debug而设置的

(4)插入：TAILQ_INSERT_TAIL(head, elm, field) head是TAILQ_HEAD的头部，elm是对应需要处理的节点，field就是对应上面的TAILQ_ENTRY

#define TAILQ_INSERT_TAIL(head, elm, field) do {            \
		QMD_TAILQ_CHECK_TAIL(head, field);              	\
		TAILQ_NEXT((elm), field) = NULL;                	\
		(elm)->field.tqe_prev = (head)->tqh_last;           \
		*(head)->tqh_last = (elm);                  		\
		(head)->tqh_last = &TAILQ_NEXT((elm), field);      	\
		QMD_TRACE_HEAD(head);                       		\
		QMD_TRACE_ELEM(&(elm)->field);                  	\
	} while (0)
其中插入方式是通过尾插法，QMD_TAILQ_CHECK_TAIL，QMD_TRACE_HEAD，QMD_TRACE_ELEM对应调试信息

(5)删除：TAILQ_REMOVE(head, elm, field) head是TAILQ_HEAD的头部，elm是对应需要处理的节点，field就是对应上面的TAILQ_ENTRY

#define TAILQ_REMOVE(head, elm, field) do {             \
	if ((TAILQ_NEXT((elm), field)) != NULL)             \
		TAILQ_NEXT((elm), field)->field.tqe_prev =      \
			(elm)->field.tqe_prev;              		\
		else {                              			\
			(head)->tqh_last = (elm)->field.tqe_prev;	\
		}                               				\
		*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);	\
	} while (0)
其中删除的方式是删除头部位置的最近的节点

(6)遍历：TAILQ_FOREACH(var, head, field) var是临时变量，head对应TAILQ_HEAD的定义，field对应TAILQ_ENTRY

#define TAILQ_FOREACH(var, head, field)                 \
		for ((var) = TAILQ_FIRST((head));               \
			(var);                          			\
			(var) = TAILQ_NEXT((var), field))

(7)其他

#define TAILQ_FIRST(head)   ((head)->tqh_first) // 队列的第一个节点
#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) // 当前elm的下一个节点

tailq的c++实现

// 使用c++封装的linux的TAILQ_ENTRY
template<class T>
class CPP_TAILQ_ENTRY 
{
public:
    T *tqe_next;  // next element
    T **tqe_prev; // address of previous next element
};
template<class T>
class CPP_TAILQ_HEAD
{
public:
    T *tqh_first; // first element
    T **tqh_last; // addr of last next element
};
#define CPP_TAILQ_FIRST(head)       ((head)->tqh_first)
#define CPP_TAILQ_NEXT(elm, field)  ((elm)->field.tqe_next)
#define CPP_TAILQ_EMPTY(head)       ((head)->tqh_first == NULL) // 判断队列是否为空
#define CPP_TAILQ_INIT(head) do {                   \
    CPP_TAILQ_FIRST((head)) = NULL;                 \
    (head)->tqh_last = &CPP_TAILQ_FIRST((head));    \
} while (0)

#define CPP_TAILQ_FOREACH(var, head, field)         \
    for ((var) = CPP_TAILQ_FIRST((head));           \
        (var);                                      \
        (var) = CPP_TAILQ_NEXT((var), field))

#define CPP_TAILQ_FOREACH_SAFE(var, head, field, tvar)              \ 
         for ((var) = CPP_TAILQ_FIRST((head));                      \ 
             (var) && ((tvar) = CPP_TAILQ_NEXT((var), field), 1);   \ 
             (var) = (tvar)) 

#define CPP_TAILQ_REMOVE(head, elm, field) do {             \
    if ((CPP_TAILQ_NEXT((elm), field)) != NULL)             \
        CPP_TAILQ_NEXT((elm), field)->field.tqe_prev =      \
            (elm)->field.tqe_prev;                          \
    else {                                                  \
        (head)->tqh_last = (elm)->field.tqe_prev;           \
    }                                                       \
    *(elm)->field.tqe_prev = CPP_TAILQ_NEXT((elm), field);  \
} while (0)

#define CPP_TAILQ_INSERT_TAIL(head, elm, field) do {        \
    CPP_TAILQ_NEXT((elm), field) = NULL;                    \
    (elm)->field.tqe_prev = (head)->tqh_last;               \
    *(head)->tqh_last = (elm);                              \
    (head)->tqh_last = &CPP_TAILQ_NEXT((elm), field);       \
} while (0)

#define CPP_TAILQ_CONCAT(head1, head2, field) do {          \
    if (!CPP_TAILQ_EMPTY(head2)) {                          \
        *(head1)->tqh_last = (head2)->tqh_first;            \
        (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;     \
        (head1)->tqh_last = (head2)->tqh_last;                      \
        CPP_TAILQ_INIT((head2));                                    \
    }                                                               \
} while (0)

使用gtest写的部分的测试用例如下：
class TestInt;
typedef CPP_TAILQ_HEAD<TestInt> TestIntList;
class TestInt 
{
public:
    TestInt(int _d) : d_(_d)
    { }
public:
    CPP_TAILQ_ENTRY<TestInt> entry_;
    int d_;
};

// 插入的测试用例
TEST(TAILQTest, INSERT_TAIL) 
{
    int arr[10] = {1, 2, 3, 4, 5};
    TestIntList tset;
    CPP_TAILQ_INIT(&tset);
    TestInt* ti1 = NULL;
    int idx = 0;
    for (; idx < sizeof(arr)/sizeof(arr[0]); idx++)
    {
        ti1 = new TestInt(arr[idx]);
        CPP_TAILQ_INSERT_TAIL(&tset, ti1, entry_);
    }

    idx = 0;
    TestInt* ti2 = NULL;
    CPP_TAILQ_FOREACH(ti2, &tset, entry_)
    {
        //LOG_TRACE("ti2 value : %d", ti2->d_);
        EXPECT_EQ(arr[idx++], ti2->d_);
    }
}

....