最近在看乐鑫ESP-ADF框架，发现该框架用到TAILQ 双向链表，于是我网上找了大量资料，总结这一篇东西。

 

定义：

TAILQ 是链表结构，使用大量宏定义去代表链表结构处理，源码在#include <sys/queue.h>

 

常用API

TAILQ_HEAD	定义队列头
TAILQ_ENTRY	队列实体定义
TAILQ_INIT	初始化队列
TAILQ_FOREACH	对队列进行遍历操作
TAILQ_INSERT_BEFORE	在指定元素之前插入元素
TAILQ_INSERT_TAIL	在队列尾部插入元素
TAILQ_EMPTY	检查队列是否为空
TAILQ_REMOVE	从队列中移除元素

 

 

 

 

源码分析

为了更好分析，以下我们定义一个demo

1.首先定义一个结构体为

typedef struct Node{
    char c;
    TAILQ_ENTRY(Node) link;
}Node;

首先先看TAILQ_ENTRY源码

#define	_TAILQ_ENTRY(type, qual)					\
struct {								\
	qual type *tqe_next;		/* next element */		\
	qual type *qual *tqe_prev;	/* address of previous next element */\
}
#define TAILQ_ENTRY(type)	_TAILQ_ENTRY(struct type,)

TAILQ_ENTRY是宏定义，我们把该宏定义展开，即可变为

typedef struct Node{
    char c;
    struct {
	    qual type *tqe_next;	
	    qual type **tqe_prev;
    } link;
}Node;

在link结构体包含两个元素，分别是tqe_enxt,tqe_prev,tqe_next指向下一个Node节点，但是tqe_pre不是指向前一个Node节点，而是指向前一个Node->tqe_next属性，注意，tqe_prev是一个二级指针。

结果如下图所示

2.创建好链表结构列表后，需要创建一个链表队列头方便对队列进行操作，创建代码如下.

TAILQ_HEAD代表定义表头

TAILQ_HEAD(head,Node) head;

/*
 * Tail queue definitions.
 */
#define	_TAILQ_HEAD(name, type, qual)					\
struct name {								\
	qual type *tqh_first;		/* first element */		\
	qual type *qual *tqh_last;	/* addr of last next element */	\
}
#define TAILQ_HEAD(name, type)	_TAILQ_HEAD(name, struct type,)

展开宏定义，可得到

struct head{
    Node *tqh_first;
    Node **tqh_last;
}head

该头也有两个属性，第一个元素tqh_first指向元素第一个元素，第二个元素tqh_last是一个二级指针，注意，不是指向最后一个结构体地址，而是指向最后一个结构体Node->tqe_next属性。如下图所示：

 

3.准备好队列头的结点结构体后，可以开始初始化一个链表队列，初始化链表队列如下

TAILQ_HEAD(name, type)

查看TAILQ_HEAD()源码如下：

#define	_TAILQ_HEAD(name, type, qual)					\
struct name {								\
	qual type *tqh_first;		/* first element */		\
	qual type *qual *tqh_last;	/* addr of last next element */	\
}
#define TAILQ_HEAD(name, type)	_TAILQ_HEAD(name, struct type,)

上面代码比较接单，对队列头两个属性赋予初始值。

队列初始化

#define	STAILQ_INIT(head) do {						\
	(head)->stqh_first = NULL;					\
	(head)->stqh_last = &(head)->stqh_first;				\
} while (/*CONSTCOND*/0)

4.队尾添加节点 TAIL_INSERT_TAIL

(1)在链表队列尾部插入元素代码如下，动态分配一个Node节点 node1,并将其插入到队列尾部。

Node *node1 = (Node *)malloc(sizeof(Node));
TAILQ_INSERT_TAIL(head,node1,link);

查看TAILQ_INSERT_TAIL源码如下

#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 (/*CONSTCOND*/0)

展开宏定义代码结果如下

do{
    (node1)->link.tqe_next = ((void *)0); 
	(node1)->link.tqe_prev = (head)->tqh_last; 
	*(head)->tqh_last = (node1); 
	(head)->tqh_last = &(node1)->link.tqe_next; 
}while(0);

假设原来有三个节点，现在要增加一个节点，过程如下图所示：
 

 

那么如果在队列头加入一个新的节点呢？此时使用TAILQ_INSERT_HEAD在队列头加入节点

#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 (/*CONSTCOND*/0)

展开宏定义，可以得到

do {			\
	if (((Node)->link.tqe_next = (head)->tqh_first) != NULL)	\
		(head)->tqh_first->link.tqe_prev =			\
		    &(Node)->link.tqe_next;				\
	else								\
		(head)->tqh_last = &(Node)->link.tqe_next;		\
	(head)->tqh_first = (Node);					\
	(Node)->link.tqe_prev = &(head)->tqh_first;			\
} while (/*CONSTCOND*/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 (/*CONSTCOND*/0)

同理同下图所示：

 

下面请看demo代码，目标是创建3个node节点并且读出打印。

#include <stdio.h>
#include <stdlib.h>
#include <sys/queue.h>
struct node{
    char c;
    TAILQ_ENTRY(node) next;
};
TAILQ_HEAD(head_s,node);
int main(){
    struct head_s my_node;
    TAILQ_INIT(&my_node);
    const char *p="que";
    while(*p){
        struct node *e=(struct node *)malloc(sizeof(struct node));
        e->c=*p;
        TAILQ_INSERT_TAIL(&my_node,e,next);
        printf("push %p %c\r\n",e,e->c);
        p++;
    }
    while(!TAILQ_EMPTY(&my_node)){
        struct node *first = TAILQ_FIRST(&my_node);
        printf("pop %p %c\r\n",first,first->c);
        TAILQ_REMOVE(&my_node,first,next);
        free(first);
    }

}

执行以上程序，得出以下结果。

push 0x560ee44292a0 q
push 0x560ee44296d0 u
push 0x560ee44296f0 e
pop 0x560ee44292a0 q
pop 0x560ee44296d0 u
pop 0x560ee44296f0 e