Note

外观

内核里的链表和队列 ​

内核<sys/queue.h>头文件里有很多用宏实现的链表和队列

名字类型
SLIST单项链表
LIST双向链表
STAILQ单向尾队列
TAILQ双向尾队列
CIRCLEQ双向循环队列

TAILQ ​

tailq

结合源码分析实例 ​

c
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/queue.h>

//定义包含tailq的结构体
struct entry {
     int data;                     //用户数据部分
     TAILQ_ENTRY(entry) entries;   //Tail queue，这个必须要定义
     };

#if 0
//下面是TAILQ_ENTRY宏源码，
#define	TAILQ_ENTRY(type) \
struct {\
	struct type *tqe_next;	/* next element */\
	struct type **tqe_prev;	/* address of previous next element */\
}
//在匿名结果体里，加了两个struct type类型的指针
//展开struct entry就是
struct entry {
     int data;
     struct{
         struct entry *tqe_next;
         struct entry **tqe_prev;
         } entries;
     };
#endif

//定义tailq的头结构体
TAILQ_HEAD(tailhead, entry);
#if 0
//下面是TAILQ_HEAD宏源码，
#define	TAILQ_HEAD(name, type)						\
struct name {								\
	struct type *tqh_first;	/* first element */			\
	struct type **tqh_last;	/* addr of last next element */		\
}
//展开就是
struct tailhead {
     struct entry *tqh_first;
     struct entry **tqh_last;
     };
#endif
int main(void)
{
     struct tailhead head; //定义tailq头部
     struct entry *n1, *n2, *n3, *np; //定义4个节点指针
     int i;

     //初始化头部,这里传进去的是指针
     TAILQ_INIT(&head);
     #if 0
     //TAILQ_INIT宏源码
     #define	TAILQ_INIT(head) do {\
	TAILQ_FIRST((head)) = NULL;\
	(head)->tqh_last = &TAILQ_FIRST((head));\
     } while (0)
     //TAILQ_FIRS源码
     #define	TAILQ_FIRST(head)	((head)->tqh_first)
     //展开后的初始化源码
     do{
          heap->tqh_first = NULL;  //tqh_first值赋值为空
          heap->tqh_last = &heap->tqh_first; //tqh_last值赋值为tqh_first的地址，
                                             //注意是tqh_first这个变量的地址，
                                             //而不是tqh_first指向的节点的地址
     }while()
     //初始化完变量值 __________
     //   tqh_first |NULL      |
     //   tqh_last  |&tqh_first|
     //              ——————————            
     #endif
     n1 = malloc(sizeof(struct entry));      
     TAILQ_INSERT_HEAD(&head, n1, entries);
     #if 0
     //TAILQ_INSERT_HEAD宏源码
     #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)
     //TAILQ_NEXT源码
     #define	TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
     //展开后的源码
     do {
          //将头节点的下一节点作为elm的下一个节点
          elm->entries.tqe_next = head.tqh_first;
          if(elm->entries.tqe_next != NULL) //如果elm的下一节点不为空
	     {
               //将之前的一个节点的prev指向elm的next
		     head->tqh_first->entries.tqe_prev =&elm->entries.tqe_next;				
	     }
          else //elm下一节点为空，即队列就一个节点
          {
		     head->tqh_last = &elm->entries.tqe_next; //尾指针包含elm的tqe_next的地址
          }
	     head->tqh_first = elm; //新节点为头节点之后的第一个节点					
	     elm->entries.tqe_prev = &head->tqh_first; //elm的pre指针包含头节点tqh_first的地址
     } while (0)
     #endif
     n1 = malloc(sizeof(struct entry));    
     TAILQ_INSERT_TAIL(&head, n1, entries);

     n2 = malloc(sizeof(struct entry));      
     TAILQ_INSERT_AFTER(&head, n1, n2, entries);

     n3 = malloc(sizeof(struct entry));      
     TAILQ_INSERT_BEFORE(n2, n3, entries);

     TAILQ_REMOVE(&head, n2, entries);       
     free(n2);
                                                   
     i = 0;
     TAILQ_FOREACH(np, &head, entries)
     np->data = i++;
                                                   
     TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
          printf("%i\n", np->data);

     n1 = TAILQ_FIRST(&head);
     while (n1 != NULL) {
          n2 = TAILQ_NEXT(n1, entries);
          free(n1);
          n1 = n2;
     }
     TAILQ_INIT(&head);

     exit(EXIT_SUCCESS);
}

函数定义 ​

函数名作用
TAILQ_ENTRY(TYPE)定义节点
TAILQ_HEAD(HEADNAME, TYPE)定义头部
TAILQ_HEAD TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head)
void TAILQ_INIT(TAILQ_HEAD *head)初始化头部
int TAILQ_EMPTY(TAILQ_HEAD *head)队列是否为空
void TAILQ_INSERT_HEAD(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME)头部插入
void TAILQ_INSERT_TAIL(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME)尾部插入
void TAILQ_INSERT_BEFORE(struct TYPE *listelm, struct TYPE *elm, TAILQ_ENTRY NAME)litselem前插入elm
void TAILQ_INSERT_AFTER(TAILQ_HEAD *head, struct TYPE *listelm, struct TYPE *elm TAILQ_ENTRY NAME)listelem之后插入elem
struct TYPE *TAILQ_FIRST(TAILQ_HEAD *head)获取第一个节点
struct TYPE *TAILQ_LAST(TAILQ_HEAD *head, HEADNAME)获取最后一个节点
struct TYPE *TAILQ_PREV(struct TYPE *elm, HEADNAME, TAILQ_ENTRY NAME)返回elem前一个节点
struct TYPE *TAILQ_NEXT(struct TYPE *elm, TAILQ_ENTRY NAME)返回elem后一个节点
TAILQ_FOREACH(struct TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME)正序遍历
TAILQ_FOREACH_REVERSE(struct TYPE *var, TAILQ_HEAD *head, HEADNAME, TAILQ_ENTRY NAME)逆序遍历
void TAILQ_REMOVE(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME)移除节点
void TAILQ_CONCAT(TAILQ_HEAD *head1, TAILQ_HEAD *head2, TAILQ_ENTRY NAME)heap2链接到heap1

参考 ​

queue-man7
tailp-man7