查看suricata源码时，看到有使用Tail queue作为内存存储配置文件解析内容的结构，这里对Tail queue这个结构及其操作方式做部分记录。
这是一个使用的例子，重点为结构体中的head和next成员。一个ConfNode类型节点有子节点时，使用head成员作为头，连接各个子节点的next成员。1
2
3
4
5
6
7
8
9
10
11
12
13
| typedef struct ConfNode_ {
char *name;
char *val;
int is_seq;
int final;
struct ConfNode_ *parent;
TAILQ_HEAD(, ConfNode_) head;
TAILQ_ENTRY(ConfNode_) next;
} ConfNode;
|
队列数据结构。name为头结点的结构体名，可为空。type为实际的数据节点结构体名，这个结构体将包含队列entry结构。1
2
3
4
5
6
7
8
9
10
11
12
| #define TAILQ_HEAD(name, type) \
struct name { \
struct type *tqh_first; \
struct type **tqh_last; \
}
#define TAILQ_ENTRY(type) \
struct { \
struct type *tqe_next; \
struct type **tqe_prev; \
}
|
队列头初始化代码1
2
3
4
| #define TAILQ_INIT(head) do { \
(head)->tqh_first = NULL; \
(head)->tqh_last = &(head)->tqh_first; \
} while (0)
|
队列操作1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #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 { \
_Q_ASSERT((elm)); \
_Q_ASSERT((head)); \
(elm)->field.tqe_next = NULL; \
(elm)->field.tqe_prev = (head)->tqh_last; \
*(head)->tqh_last = (elm); \
_Q_ASSERT(*(head)->tqh_last); \
(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; \
_Q_ASSERT((head)->tqh_first != (elm)); \
_Q_INVALIDATE((elm)->field.tqe_prev); \
_Q_INVALIDATE((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); \
_Q_INVALIDATE((elm)->field.tqe_prev); \
_Q_INVALIDATE((elm)->field.tqe_next); \
} while (0)
|
队列节点访问操作1
2
3
4
5
6
7
8
9
10
| #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))
#define TAILQ_PREV(elm, headname, field) \
(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
#define TAILQ_EMPTY(head) \
(TAILQ_FIRST(head) == TAILQ_END(head))
|
前三个操作比较容易理解，head为头结点指针，elm为entry所在的结构体指针，field为entry在结构体中的名字。
第四个操作TAILQ_LAST需要结合内存布局理解：
- head为头节点指针，headname为上文定义头节点时的结构体名，如果需要使用TAILQ_LAST操作就必须在定义时设定name。
- head节点中定义tqh_first，tqh_last有顺序要求。
- entry节点中定义tqe_next，tqe_prev有顺序要求。
- ((head)->tqh_last)
- 是一个二级指针，指向最后一个数据节点的tqe_next，既这个二级指针存储了tqe_next的地址，从内存布局可知这个地址也就是entry节点的地址，这个指针也可以看作是指向entry节点的指针。
- ((struct headname *)((head)->tqh_last))
- 将指针做了一次强制类型转换，转换为指向头节点的指针类型，这里仅仅转换了类型，值未发生变化。
- (((struct headname *)((head)->tqh_last))->tqh_last)
- 由于头节点和entry节点内存布局相同，这步操作实际相当于得到了最后一个数据节点的tqe_prev。
- (*(((struct headname *)((head)->tqh_last))->tqh_last))
- 解引用，由于最后一个数据节点的tqe_prev中存储的是倒数第二个数据节点的tqe_next的地址，解引用后得到了倒数第二个数据节点tqe_next的值，也就是最后一个数据节点的地址，也就是最后一个数据节点的指针。
第五个操作TAILQ_PREV同理。
队列遍历操作1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #define TAILQ_FOREACH(var, head, field) \
for((var) = TAILQ_FIRST(head); \
(var) != TAILQ_END(head); \
(var) = TAILQ_NEXT(var, field))
#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
for((var) = TAILQ_FIRST(head), \
(tvar) = TAILQ_FIRST(head) ? TAILQ_NEXT(TAILQ_FIRST(head), field): NULL ; \
(var) != TAILQ_END(head); \
(var = tvar), (tvar) = var ? TAILQ_NEXT(var, field): NULL)
#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
for((var) = TAILQ_LAST(head, headname); \
(var) != TAILQ_END(head); \
(var) = TAILQ_PREV(var, headname, field))
|