TAILQ linked list has been read many times before and after. Record some points in the learning process.

1. Data structure

#define TAILQ_ENTRY(type)
struct\
{\
    struct type *tqe_next;\
    struct type **tqe_prev;\
}

TAILQ linked list uses a called TAILQ_ The structure of entry, which contains two pointers:
1) Pointer to the next node tqe_next；
2) TQE pointing to the previous node_ Secondary pointer TQE of next pointer address_ prev；
Namely:
node2->tqe_prev = &(node1->tqe_next);

So there are:
*(node2->tqe_prev) = *&(node1->tqe_next) = node1->tqe_next = node2

Define a data node, such as:

struct node
{
    int data;
    TAILQ_ENTRY(node) link;
}

Expand as

struct node
{
    int data;
    struct link
    {
        struct node *tqe_next;
        struct node **tqe_prev;
    }
}

TAILQ linked list has no head node, which abstracts the head node into a data structure TAILQ containing two pointers_ HEAD:

#define TAILQ_HEAD(name, type)\
struct name\
{\
    struct type *tqh_first;\
    struct type **tqh_last;\
}

1)tqh_first points to the first node of the linked list;
2)tqh_last points to the TQE of the last node in the linked list_ next；

2. Linked list initialization

#define TAILQ_INIT(head)\
{\
    (head)->tqh_first = NULL;\
    (head)->tqh_last = &(head)->tqh_first;\
}

Using TAILQ_INIT initializes the linked list in two simple steps:
1)tqh_first points to NULL;
2)tqh_last points to tqh_first；

3. Insert node

3.1 head insertion

3.1.1 insert the first node

#define	TAILQ_INSERT_HEAD(head, elm, field)\
do {\
    if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)\
        TAILQ_FIRST((head))->field.tqe_prev = &TAILQ_NEXT((elm), field);\
	else\
        (head)->tqh_last = &TAILQ_NEXT((elm), field);\
    TAILQ_FIRST((head)) = (elm);\
    (elm)->field.tqe_prev = &TAILQ_FIRST((head));\
} while (0)

code	Illustration
TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))
Is the first node, take the else branch
(head)->tqh_last = &TAILQ_NEXT((elm), field);
TAILQ_FIRST((head)) = (elm);
(elm)->field.tqe_prev = &TAILQ_FIRST((head))

3.1.2 insert non first node

#define	TAILQ_INSERT_HEAD(head, elm, field)\
do {\
    if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)\
        TAILQ_FIRST((head))->field.tqe_prev = &TAILQ_NEXT((elm), field);\
	else\
        (head)->tqh_last = &TAILQ_NEXT((elm), field);\
    TAILQ_FIRST((head)) = (elm);\
    (elm)->field.tqe_prev = &TAILQ_FIRST((head));\
} while (0)

code	Illustration
TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))
Not the first node, take the if branch
TAILQ_FIRST((head))->field.tqe_prev = &TAILQ_NEXT((elm), field);
TAILQ_FIRST((head)) = (elm);
(elm)->field.tqe_prev = &TAILQ_FIRST((head));

3.2 tail insertion

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

code	Illustration
TAILQ_NEXT((elm), field) = NULL;
(elm)->field.tqe_prev = (head)->tqh_last;
*(head)->tqh_last = (elm);
(head)->tqh_last = &TAILQ_NEXT((elm), field);

4. Delete node

4.1 delete the last node

#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)

code	Illustration
if ((TAILQ_NEXT((elm), field)) != NULL)	Delete the last node and take the else branch
(head)->tqh_last = (elm)->field.tqe_prev;
*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);
Remove nodes and recycle resources

4.2 delete non last node

code	Illustration
if ((TAILQ_NEXT((elm), field)) != NULL)	Delete the non last node and take the if branch
TAILQ_NEXT((elm), field)->field.tqe_prev = (elm)->field.tqe_prev;
*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);
Remove nodes and recycle resources

5. TAILQ linked list features

5.1 secondary pointer

TAILQ uses a secondary pointer. If you replace it with a primary pointer, the above figure will be in the following form:

Since TAILQ does not set the header node, the TQE of the first node_ Prev will point to NULL. When deleting a node, you need to distinguish whether it is the first node.

5.2 reverse lookup

tqe_ The prev pointer points to the TQE of the previous node_ Next, how does TAILQ reverse lookup do?

Starting from node 3, in order to get node 2, you need to get the TQE of node 1_ next. However, only TQE of node 2 can be obtained from node 3_ Next, want to get TQE of node 1_ Next, you need to get the TQE of node 2 first_ prev.

Get TQE of node 2_ Prev method:

1. node2->field.tqe_prev
2. &(node2 - > field. Tqe_next) + sizeof (node2 - > field. Tqe_next), i.e. node3 - > field prev + sizeof(node3->field.tqe_next)

First, you need to know node 2 and pass first
The second requires address operation, which will bring additional system overhead

Let's take a look at the operation of TAILQ

#define	TAILQ_PREV(elm, headname, field)\
	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

elm is the current node, headname is the name of the linked list data structure, and field is the linked list entry. TAILQ uses a clever technique here:
Set (ELM) - > field tqe_prev) makes a type conversion to (struct header *), that is, TAILQ_HEAD data structure, due to TAILQ_HEAD and tailq_ The data structure of entry is the same, including a first level pointer and a second level pointer. Therefore, tqh is taken after conversion_ Last offsets the address of a pointer and gets the TQE of node2_ Prev, you get the TQE of node1_ Next, take the value of * to obtain node2.

Why tailq is used_ The reason why head does type conversion is TAILQ_ENTRY is defined inside the node and does not necessarily have struct name. For better code compatibility, tailq with struct name is used_ HEAD.

TAILQ's reverse lookup efficiency is low. In order to reduce the overhead as much as possible, we can do some tricks in the structure design:

struct node
{
    TAILQ_ENTRY(node) link;
    int data;
}

struct node
{
    struct link
    {
        struct node *tqe_next;
        struct node **tqe_prev;
    };
    int data;
}

Tailq_ If entry is the first member of the node structure, then TQE_ The address of the next pointer represents the first memory address of the node. Make a type conversion on the address and get the data through the data member.

5.3, operator

The security provided by TAILQ traverses TAILQ_ FOREACH_ A rare comma operator is used in safe:

(var) && ((tvar) = ((var)->field.tqe_next), 1);\ 

Here, the next node is taken out and saved to tvar in advance. If the next node is NULL, the following statement is false and the current node cannot be processed.

(var) && ((tvar) = ((var)->field.tqe_next));\

After adding the comma operator, the return value of the expression is the value after the comma, i.e. 1. If the expression is true, the next node is taken, and the processing of the current node is guaranteed:

((tvar) = ((var)->field.tqe_next), 1)