m)->entries.tqe_prev = (&queue_head)->tqh_last;
//首次执行相当于(&queue_head)->tqh_first=item
//以后执行相当于是(前一个item)->entries.tqe_next=当前item
*(&queue_head)->tqh_last = (item);
(&queue_head)->tqh_last = &(item)->entries.tqe_next;
} while (0);
}
最终建立的链表结构如图,下面看一下insert操作,经过宏替换后代码如下
struct QUEUE_ITEM *ins_item;
ins_item=malloc(sizeof(ins_item));
ins_item->value=100;
do {
(ins_item)->entries.tqe_prev = (item)->entries.tqe_prev;
(ins_item)->entries.tqe_next = (item);
//这句话体现了TAILQ的特色,tqe_prev是前一个元素的下个元素地址,
//所以正好应该是当前插入item的地址
*(item)->entries.tqe_prev = (ins_item);
(item)->entries.tqe_prev = &(ins_item)->entries.tqe_next;
} while (0);
总结:TAILQ的最大特点就是每个entry的二级指针tqe_prev其存放的是前一个元素的下个元素地址,呵呵,听起来都很拗口
我现在就是不知道为什么linux的queue.h只有建立tailq的宏定义而缺少所有的access method,初涉linux c编程,请大家指教
附经过宏替换后的所有代码
#include "stdio.h"
#include "stdlib.h"
struct QUEUE_ITEM{
int value;
struct {
struct QUEUE_ITEM *tqe_next;
struct QUEUE_ITEM **tqe_prev;
}entries;
};
struct {
struct QUEUE_ITEM *tqh_first;
struct QUEUE_ITEM **tqh_last;
}queue_head;
int main(int argc,char **argv){
struct QUEUE_ITEM *item;
struct QUEUE_ITEM *tmp_item;
do {
(&queue_head)->tqh_first = NULL;
(&queue_head)->tqh_last = &(&queue_head)->tqh_first;
} while (0);
int i=0;
for(i=5;i<10;i+=2){
item=malloc(sizeof(item));
item->value=i;
do {
(item)->entries.tqe_next = NULL;
//首次执行相当于item->entries.tqe_prev=&(&queue_head)->tqh_first
//以后执行相当于是(item)->entries.tqe_prev=&(前一个item)->entries.tqe_next;
(item)->entries.tqe_prev = (&queue_head)->tqh_last;
//首次执行相当于(&queue_head)->tqh_first=item
//以后执行相当于是(前一个item)->entries.tqe_next=当前item
*(&queue_head)->tqh_last = (item);
(&queue_head)->tqh_last = &(item)->entries.tqe_next;
} while (0);
}
struct QUEUE_ITEM *ins_item;
ins_item=malloc(sizeof(ins_item));
ins_item->value=100;
do {
(ins_item)->entries.tqe_prev = (item)->entries.tqe_prev;
(ins_item)->entries.tqe_next = (item);
*(item)->entries.tqe_prev = (ins_item);
(item)->entries.tqe_prev = &(ins_item)->entries.tqe_next;
} while (0);
tmp_item=((&queue_head)->tqh_first);
printf("first element is %d\n",tmp_item->value);
tmp_item=((tmp_item)->entries.tqe_next);
printf("next element is %d\n",tmp_item->value);
tmp_item=((tmp_item)->entries.tqe_next);
printf("next element is %d\n",tmp_item->value);
tmp_item=((tmp_item)->entries.tqe_next);
printf("next element is %d\n",tmp_item->value);
}