理解linux内核数据结构尾队列（Tail queue）

理解linux内核数据结构尾队列（Tail queue）

Tail queue位于/usr/include/x86_64-linux-gnu/sys/queue.h

queue.h包含以下几种数据结构：

1. 双链表（List）
2. 单链表（Singly-linked List）
3. 单链尾队列（Singly-linked Tail queue）
4. 简单队列（Simple queue）
5. 双链尾队列（Tail queue）
6. 循环队列（Circular queue）

Tail queue几个参数含义

HEADNAME

链表头结点的名字，用TAILQ_HEAD(HEADNAME, TYPE);定义

TYPE elm

用户定义结构体，该结构体必须用TAILQ_ENTRY(TYPE);定义一个变量field

head

头结点指针，即HEADNAME*

field

用TAILQ_ENTRY声明的变量名

对于上面demo，

HEADNAME是tailhead

TYPE elm是entry

head是tailhead*

field是entries

Tail queue代码

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

#define	TAILQ_HEAD_INITIALIZER(head)					
	{ NULL, &(head).tqh_first }

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


#define	TAILQ_EMPTY(head)	((head)->tqh_first == NULL)

#define	TAILQ_FIRST(head)	((head)->tqh_first)

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

#define	TAILQ_FOREACH_REVERSe(var, head, headname, field)		
	for ((var) = TAILQ_LAST((head), headname);			
	    (var);							
	    (var) = TAILQ_PREV((var), headname, field))

#define	TAILQ_INIT(head) do {						
	TAILQ_FIRST((head)) = NULL;					
	(head)->tqh_last = &TAILQ_FIRST((head));			
} while (0)

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

#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			
	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		
	TAILQ_NEXT((elm), field) = (listelm);				
	*(listelm)->field.tqe_prev = (elm);				
	(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);		
} while (0)

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

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

#define	TAILQ_LAST(head, headname)					
	(*(((struct headname *)((head)->tqh_last))->tqh_last))

#define	TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)

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

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

其中TAILQ_HEAD是头结点，TAILQ_ENTRY是非头结点

代码实现中比较难理解的是TAILQ_LAST和TAILQ_PREV。二级指针为啥要转一级指针，它又是如何得到尾元素和上一个元素的。

接下来通过一个demo来打印出Tail queue各个结点的地址和值。

#include 
#include 
#include 
#include 

#define ITEM_NUM 4

// #pragma pack(1)
// 由于字节对齐，一共占用24字节
typedef struct _QUEUE_ITEM {
    int value;
    TAILQ_ENTRY(_QUEUE_ITEM) entries;
}QUEUE_ITEM;
// #pragma pack()

TAILQ_HEAD(TAIL_QUEUE, _QUEUE_ITEM) queue_head;

int main(int argc, char **argv) {
    QUEUE_ITEM *item[ITEM_NUM];
    TAILQ_INIT(&queue_head);

    int i = 0;
    for (i = 0; i < ITEM_NUM; ++i) {
        item[i] = (QUEUE_ITEM*)malloc(sizeof(QUEUE_ITEM));
        item[i]->value = i;
        TAILQ_INSERT_TAIL(&queue_head, item[i], entries);
    }
    
    printf("queue_head:%p, first:%p, last:%pn", (void*)&queue_head, (void*)queue_head.tqh_first, (void*)queue_head.tqh_last);

    for(i = 0; i < ITEM_NUM; ++i)
    {
        printf("item[%d]: item:%p, next:%p, &next:%p, prev:%p, *prev:%pn",
        i, (void*)item[i], (void*)item[i]->entries.tqe_next, 
        (void*)&(item[i]->entries.tqe_next), (void*)item[i]->entries.tqe_prev, (void*)(*item[i]->entries.tqe_prev));
    }

    printf("last item:%pn", TAILQ_LAST(&queue_head, TAIL_QUEUE));
    printf("sizeof(QUEUE_ITEM): %lun", sizeof(QUEUE_ITEM));

    return 0;
}

运行输出：

  通过上面输出可以得到Tail queue的内存布局如下：

粉红色的是域的地址，绿色是域值，0 1 2 3是data

 现在再来看TAILQ_LAST

#define	TAILQ_LAST(head, headname)					
	(*(((struct headname *)((head)->tqh_last))->tqh_last))

((head)->tqh_last)指向尾元素的tqe_next域，即获取到尾元素的tqe_next域的地址0x1f35078

((struct headname *)((head)->tqh_last))将0x1f35078强转为头结点指针。为什么能强转呢？因为头结点和非头结点的内存布局是一样的（都是两个指针）。

(((struct headname *)((head)->tqh_last))->tqh_last)的意思是获取尾元素tqe_prev域的值0x1f35058，可以理解为0x1f35078+8后解引用。0x1f35058即倒数第二个结点的tqe_next域的地址。

 (*(((struct headname *)((head)->tqh_last))->tqh_last)) 最后对0x1f35058解引用，得到0x1f35070，即尾元素的首地址，此时拿到尾元素指针。

理解了TAILQ_LAST再看TAILQ_PREV就比较简单

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

假设当前节点是节点2

((elm)->field.tqe_prev)拿到节点1的next域的地址0x1f35038

(((struct headname *)((elm)->field.tqe_prev))->tqh_last)拿到结点0的next域的地址0x1f35018

(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))对0x1f35018解引用得到节点1的首地址0x1f35030，即指向节点1的指针。