tailq介绍
TAILQ是linux内核对双向队列操作的一种抽象，能实现操作队列需要的各种操作：插入元素，删除元素，遍历队列等，其封装是对应的宏定义，下面详细说明tailq的操作，从定义，初始化，插入，删除和遍历这几个API来介绍，并且提供c 版本的tailq。
tailq的宏定义API
（1）定义：TAILQ_ENTRY(type) 初始化一个type类型的entry
代码语言：javascript复制#define TAILQ_ENTRY(type)
struct {
struct type *tqe_next;
struct type **tqe_prev;
TRACEBUF
}其中TRACEBUF是一个用来调试的宏：
代码语言：javascript复制struct node{
int a, b, c;
TAILQ_ENTRY(node);
};展开如下：
代码语言：javascript复制struct node{
int a, b, c;
struct {
struct node *tqe_next;
sturct node **tqe_prev;
};
};（2）定义：TAILQ_HEAD(name, type) 初始化name的结构体，类型为type，初始化头部
代码语言：javascript复制#define TAILQ_HEAD(name, type)
struct name {
struct type **tqh_last;
TRACEBUF
}展开如下：
代码语言：javascript复制struct head {
struct node *tqh_first;
struct node **tqh_last;
} q_head;（3）初始化：TAILQ_INIT(head) 初始化头部，其中head是上面的TAILQ_HEAD
代码语言：javascript复制#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
代码语言：javascript复制#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
代码语言：javascript复制#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
代码语言：javascript复制#define TAILQ_FOREACH(var, head, field)
for ((var) = TAILQ_FIRST((head));
(var);
(var) = TAILQ_NEXT((var), field))（7）其他操作宏
代码语言：javascript复制#define TAILQ_FIRST(head)
((head)->tqh_first) // 队列的第一个节点
#define TAILQ_NEXT(elm, field)
((elm)->field.tqe_next) // 当前elm的下一个节点tailq的c 实现
代码语言：javascript复制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写的部分的测试用例如下：
代码语言：javascript复制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_);
}
}
