Linuxqueueh之TAILQ队列分析

1、这两天想看看memcached的实现,所以先学习了libevent,使用起来还是比较简单的,其实是对select/poll/kqueue等的封装,学习libevent过程中又遇到了linux下队列的使用,简单分析如下,权当做记录: libevent中的例子中使用的是FreeBSD下的queue.h,在linux的/usr/include/sys/queue.h也有该头文件,但是是一个缩减版本,而且没有看到queue 的access method,不知道是不是跟我们的linux服务器版本有关,没办法google了一下,找到了FreeBSD 下queue.h的定义,我们看一下tail q

2、ueue的定义 C代码  1. #define TAILQ_HEAD(name, type)                2. struct name                   

3、       3.     struct type *tqh_first; /* first element */   4.     struct type *tqh_last; /* addr of last next element */  5.

4、   6.   7. #define TAILQ_ENTRY(type)                     8. struct                 &#

5、160;             9.     struct type *tqe_next;  /* next element */        10.     struct type *tqe_prev;/*

6、0;addr of previous next element*/   11.                                      

7、60;                            12.   13. #define TAILQ_INIT(head) do            

8、      14.     (head)->tqh_first = NULL;                  15.     (head)->tqh_last = &(head)->tqh_first;

9、0;         16.  while (0)  17.   18. #define TAILQ_INSERT_TAIL(head, elm, field) do           19.     (elm)->field.tqe_next

10、0;= NULL;              20.     (elm)->field.tqe_prev = (head)->tqh_last;       21.     *(head)->tqh_last = (elm); &#

11、160;/将elm赋给最后一个元素               22.     (head)->tqh_last = &(elm)->field.tqe_next;          23.  while (0)  24.

12、60; 25. #define TAILQ_INSERT_BEFORE(listelm, elm, field) do          26.     (elm)->field.tqe_prev = (listelm)->field.tqe_prev;      27.    

13、0;(elm)->field.tqe_next = (listelm);             28.     *(listelm)->field.tqe_prev = (elm);            29.    

14、60;(listelm)->field.tqe_prev = &(elm)->field.tqe_next;     30.  while (0)  31. #define TAILQ_FIRST(head)       (head)->tqh_first)  32.   33. #define TAILQ_NEXT(elm,

15、60;field)      (elm)->field.tqe_next)  34. .  我们就先分析上面的这些定义,先看个应用的例子 C代码  1. #include <stdio.h>  2. #include <stdlib.h>  3. #include "queue.h"  4.   5. str

16、uct QUEUE_ITEM  6.     int value;  7.     TAILQ_ENTRY(QUEUE_ITEM) entries;  8. ;  9. TAILQ_HEAD(,QUEUE_ITEM) queue_head;  10. int main(int argc,char *argv)  11. 

17、0;   struct QUEUE_ITEM *item;  12.     struct QUEUE_ITEM *tmp_item;  13.   14. ccc    TAILQ_INIT(&queue_head);  15.     int i=0;  16.   

18、  for(i=5;i<10;i+=2)  17.         item=malloc(sizeof(item);  18.         item->value=i;  19.         TAILQ_INSERT_TAIL(&queue_head

19、, item, entries);  20.       21.       22.     struct QUEUE_ITEM *ins_item;  23.     ins_item=malloc(sizeof(ins_item);  24.   25.  

20、0;  ins_item->value=100;  26.     TAILQ_INSERT_BEFORE(item,ins_item,entries);  27.   28.   29.     tmp_item=TAILQ_FIRST(&queue_head);  30.     printf("first elemen

21、t is %dn",tmp_item->value);  31.   32.     tmp_item=TAILQ_NEXT(tmp_item,entries);  33.     printf("next element is %dn",tmp_item->value);  34.   35.   

22、60; tmp_item=TAILQ_NEXT(tmp_item,entries);  36.     printf("next element is %dn",tmp_item->value);  37.   38.     tmp_item=TAILQ_NEXT(tmp_item,entries);  39.     print

23、f("next element is %dn",tmp_item->value);  40.   41.   结果: Java代码  1. first element is 5  2. next element is 7  3. next element is 100  4. next ele

24、ment is 9  分析: QUEUE_ITEM 是我们定义的存放在队列里的东东,简单起见只包括一个int值 TAILQ_ENTRY(QUEUE_ITEM) entries 主要是存放下一个对象和前一个对象的指针,具体见 header   根据头文件进行宏替换后,实际我们声明的是这样的结构: C代码  1.  struct QUEUE_ITEM  2.     int value;&#

25、160; 3.         struct               4.             struct QUEUE_ITEM *tqe_next;     

26、 5.         struct QUEUE_ITEM *tqe_prev;  6.         entries;  7. ;  8.    TAILQ_HEAD(,QUEUE_ITEM) queue_head; 实际是 C代码  1. struct  

27、0;                2.     struct QUEUE_ITEM *tqh_first;     3.     struct QUEUE_ITEM *tqh_last;     4. queue_he

28、ad;  接着我们定义了QUEUE_ITEM的两个指针变量item和tmp_item TAILQ_INIT(&queue_head); 相当于是 C代码  1. do   2.     (&queue_head)->tqh_first = NULL;               

29、;3.     (&queue_head)->tqh_last = &(&queue_head)->tqh_first;        4.  while (0);  head的初始化如 下图1 接着我们通过循环分配了几个元素,并赋值 C代码  1. TAILQ_INSERT_TAIL(&queue_head, item,&

30、#160;entries); 相当于执行    2. do   3.     (item)->entries.tqe_next = NULL;   4.     (item)->entries.tqe_prev = (&queue_head)->tqh_last;      

31、0;      5.     *(&queue_head)->tqh_last = (item);                     6.     (&queue_head)->tqh_last&

32、#160;= &(item)->entries.tqe_next;            7.  while (0);  Int a =1;Int*pa=&a;Int b =2;Int*pb=&b;Int *p =&pa;*p=pb;也就是我们的循环执行下面代码段,结果分析见图2,3 C代码  1. for(i=5;i<10;i+=2) 

33、60;2.     item=malloc(sizeof(item);  3.     item->value=i;  4.     do   5.         (item)->entries.tqe_next = NULL;  6.    &

34、#160;    /首次执行相当于item->entries.tqe_prev=&(&queue_head)->tqh_first  7.         /以后执行相当于是(item)->entries.tqe_prev=&(前一个item)->entries.tqe_next;  8.         (i

35、tem)->entries.tqe_prev = (&queue_head)->tqh_last;  9.         /首次执行相当于(&queue_head)->tqh_first=item  10.         /以后执行相当于是(前一个item)->entries.tqe_next=当前item  11

36、.         *(&queue_head)->tqh_last = (item);  /填充内容12.         (&queue_head)->tqh_last = &(item)->entries.tqe_next;  /占位置，占个地13.      

37、while (0);  14.   C代码  1. 最终建立的链表结构如图,下面看一下insert操作,经过宏替换后代码如下  2.   3. struct QUEUE_ITEM *ins_item;  4. ins_item=malloc(sizeof(ins_item);  5. ins_item->value=100;  6.   7. do   

38、;8.     (ins_item)->entries.tqe_prev = (item)->entries.tqe_prev;  9.     (ins_item)->entries.tqe_next = (item);  10.     /这句话体现了TAILQ的特色,tqe_prev是前一个元素的下个元素地址,  11.   

39、0; /所以正好应该是当前插入item的地址  12.     *(item)->entries.tqe_prev = (ins_item);  13.     (item)->entries.tqe_prev = &(ins_item)->entries.tqe_next;  14.  while (0);   总结:TAILQ的

40、最大特点就是每个entry的二级指针tqe_prev其存放的是前一个元素的下个元素地址,呵呵,听起来都很拗口 现在就是不知道为什么linux的queue.h只有建立tailq的宏定义而缺少所有的access method,初涉linux c编程,请大家指教 附经过宏替换后的所有代码 C代码  1. #include "stdio.h"  2. #include "stdlib.h"  3. struct QUEUE_ITEM 

41、 4.     int value;  5.     struct   6.         struct QUEUE_ITEM *tqe_next;  7.         struct QUEUE_ITEM *tqe_prev

42、;  8.     entries;  9. ;  10. struct   11.     struct QUEUE_ITEM *tqh_first;  12.     struct QUEUE_ITEM *tqh_last;  13. queue_head;  14.  &#

43、160;15. int main(int argc,char *argv)  16.     struct QUEUE_ITEM *item;  17.     struct QUEUE_ITEM *tmp_item;  18.   19.     do   20.   

44、0;     (&queue_head)->tqh_first = NULL;  21.         (&queue_head)->tqh_last = &(&queue_head)->tqh_first;  22.      while (0);  23

45、.   24.     int i=0;  25.     for(i=5;i<10;i+=2)  26.         item=malloc(sizeof(item);  27.         item->value=i;  28

46、.         do   29.             (item)->entries.tqe_next = NULL;  30.             /首次执行相当于item->entr

47、ies.tqe_prev=&(&queue_head)->tqh_first  31.             /以后执行相当于是(item)->entries.tqe_prev=&(前一个item)->entries.tqe_next;  32.             (i

48、tem)->entries.tqe_prev = (&queue_head)->tqh_last;  33.             /首次执行相当于(&queue_head)->tqh_first=item  34.             /以后执行相当于是(前

49、一个item)->entries.tqe_next=当前item  35.             *(&queue_head)->tqh_last = (item);  36.             (&queue_head)->tqh_last =&

50、#160;&(item)->entries.tqe_next;  37.          while (0);  38.       39.   40.     struct QUEUE_ITEM *ins_item;  41.     ins

51、_item=malloc(sizeof(ins_item);  42.   43.     ins_item->value=100;  44.     do   45.         (ins_item)->entries.tqe_prev = (item)->entries.tqe_prev;  46.         (ins_item)->entries.tqe_next = (item);