这两天想看看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 queue的定义

  1. #define TAILQ_HEAD(name, type)              \
  2. struct name {                       \
  3. struct type *tqh_first; /* first element */ \
  4. struct type **tqh_last; /* addr of last next element */\
  5. }
  6. #define TAILQ_ENTRY(type)                   \
  7. struct {                            \
  8. struct type *tqe_next;  /* next element */      \
  9. struct type **tqe_prev;/* addr of previous next element*/ \
  10. }
  11. #define TAILQ_INIT(head) do {               \
  12. (head)->tqh_first = NULL;                \
  13. (head)->tqh_last = &(head)->tqh_first;        \
  14. } while (0)
  15. #define TAILQ_INSERT_TAIL(head, elm, field) do {        \
  16. (elm)->field.tqe_next = NULL;            \
  17. (elm)->field.tqe_prev = (head)->tqh_last;     \
  18. *(head)->tqh_last = (elm);               \
  19. (head)->tqh_last = &(elm)->field.tqe_next;        \
  20. } while (0)
  21. #define TAILQ_INSERT_BEFORE(listelm, elm, field) do {       \
  22. (elm)->field.tqe_prev = (listelm)->field.tqe_prev;    \
  23. (elm)->field.tqe_next = (listelm);           \
  24. *(listelm)->field.tqe_prev = (elm);          \
  25. (listelm)->field.tqe_prev = &(elm)->field.tqe_next;   \
  26. } while (0)
  27. #define TAILQ_FIRST(head)       ((head)->tqh_first)
  28. #define TAILQ_NEXT(elm, field)      ((elm)->field.tqe_next)
  29. ....

我们就先分析上面的这些定义,先看个应用的例子

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "queue.h"
  4. struct QUEUE_ITEM{
  5. int value;
  6. TAILQ_ENTRY(QUEUE_ITEM) entries;
  7. };
  8. TAILQ_HEAD(,QUEUE_ITEM) queue_head;
  9. int main(int argc,char **argv){
  10. struct QUEUE_ITEM *item;
  11. struct QUEUE_ITEM *tmp_item;
  12. TAILQ_INIT(&queue_head);
  13. int i=0;
  14. for(i=5;i<10;i+=2){
  15. item=malloc(sizeof(item));
  16. item->value=i;
  17. TAILQ_INSERT_TAIL(&queue_head, item, entries);
  18. }
  19. struct QUEUE_ITEM *ins_item;
  20. ins_item=malloc(sizeof(ins_item));
  21. ins_item->value=100;
  22. TAILQ_INSERT_BEFORE(item,ins_item,entries);
  23. tmp_item=TAILQ_FIRST(&queue_head);
  24. printf("first element is %d\n",tmp_item->value);
  25. tmp_item=TAILQ_NEXT(tmp_item,entries);
  26. printf("next element is %d\n",tmp_item->value);
  27. tmp_item=TAILQ_NEXT(tmp_item,entries);
  28. printf("next element is %d\n",tmp_item->value);
  29. tmp_item=TAILQ_NEXT(tmp_item,entries);
  30. printf("next element is %d\n",tmp_item->value);
  31. }

结果:

  1. first element is 5
  2. next element is 7
  3. next element is 100
  4. next element is 9

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

  1. struct QUEUE_ITEM{
  2. int value;
  3. struct {
  4. struct QUEUE_ITEM *tqe_next;
  5. struct QUEUE_ITEM **tqe_prev;
  6. }entries;
  7. };

TAILQ_HEAD(,QUEUE_ITEM) queue_head; 实际是

  1. struct {
  2. struct QUEUE_ITEM *tqh_first;
  3. struct QUEUE_ITEM **tqh_last;
  4. }queue_head;

接着我们定义了QUEUE_ITEM的两个指针变量item和tmp_item

TAILQ_INIT(&queue_head); 相当于是

  1. do {
  2. (&queue_head)->tqh_first = NULL;
  3. (&queue_head)->tqh_last = &(&queue_head)->tqh_first;
  4. } while (0);

head的初始化如 下图1

接着我们通过循环分配了几个元素,并赋值

  1. TAILQ_INSERT_TAIL(&queue_head, item, entries); 相当于执行
  2. do {
  3. (item)->entries.tqe_next = NULL;
  4. (item)->entries.tqe_prev = (&queue_head)->tqh_last;
  5. *(&queue_head)->tqh_last = (item);
  6. (&queue_head)->tqh_last = &(item)->entries.tqe_next;
  7. } while (0);

也就是我们的循环执行下面代码段,结果分析见图2,3

  1. for(i=5;i<10;i+=2){
  2. item=malloc(sizeof(item));
  3. item->value=i;
  4. do {
  5. (item)->entries.tqe_next = NULL;
  6. //首次执行相当于item->entries.tqe_prev=&(&queue_head)->tqh_first
  7. //以后执行相当于是(item)->entries.tqe_prev=&(前一个item)->entries.tqe_next;
  8. (item)->entries.tqe_prev = (&queue_head)->tqh_last;
  9. //首次执行相当于(&queue_head)->tqh_first=item
  10. //以后执行相当于是(前一个item)->entries.tqe_next=当前item
  11. *(&queue_head)->tqh_last = (item);
  12. (&queue_head)->tqh_last = &(item)->entries.tqe_next;
  13. } while (0);
  14. }
  1. 最终建立的链表结构如图,下面看一下insert操作,经过宏替换后代码如下
  2. struct QUEUE_ITEM *ins_item;
  3. ins_item=malloc(sizeof(ins_item));
  4. ins_item->value=100;
  5. do {
  6. (ins_item)->entries.tqe_prev = (item)->entries.tqe_prev;
  7. (ins_item)->entries.tqe_next = (item);
  8. //这句话体现了TAILQ的特色,tqe_prev是前一个元素的下个元素地址,
  9. //所以正好应该是当前插入item的地址
  10. *(item)->entries.tqe_prev = (ins_item);
  11. (item)->entries.tqe_prev = &(ins_item)->entries.tqe_next;
  12. } while (0);

总结:TAILQ的最大特点就是每个entry的二级指针tqe_prev其存放的是前一个元素的下个元素地址,呵呵,听起来都很拗口 
我现在就是不知道为什么linux的queue.h只有建立tailq的宏定义而缺少所有的access method,初涉linux c编程,请大家指教

附经过宏替换后的所有代码

  1. #include "stdio.h"
  2. #include "stdlib.h"
  3. struct QUEUE_ITEM{
  4. int value;
  5. struct {
  6. struct QUEUE_ITEM *tqe_next;
  7. struct QUEUE_ITEM **tqe_prev;
  8. }entries;
  9. };
  10. struct {
  11. struct QUEUE_ITEM *tqh_first;
  12. struct QUEUE_ITEM **tqh_last;
  13. }queue_head;
  14. int main(int argc,char **argv){
  15. struct QUEUE_ITEM *item;
  16. struct QUEUE_ITEM *tmp_item;
  17. do {
  18. (&queue_head)->tqh_first = NULL;
  19. (&queue_head)->tqh_last = &(&queue_head)->tqh_first;
  20. } while (0);
  21. int i=0;
  22. for(i=5;i<10;i+=2){
  23. item=malloc(sizeof(item));
  24. item->value=i;
  25. do {
  26. (item)->entries.tqe_next = NULL;
  27. //首次执行相当于item->entries.tqe_prev=&(&queue_head)->tqh_first
  28. //以后执行相当于是(item)->entries.tqe_prev=&(前一个item)->entries.tqe_next;
  29. (item)->entries.tqe_prev = (&queue_head)->tqh_last;
  30. //首次执行相当于(&queue_head)->tqh_first=item
  31. //以后执行相当于是(前一个item)->entries.tqe_next=当前item
  32. *(&queue_head)->tqh_last = (item);
  33. (&queue_head)->tqh_last = &(item)->entries.tqe_next;
  34. } while (0);
  35. }
  36. struct QUEUE_ITEM *ins_item;
  37. ins_item=malloc(sizeof(ins_item));
  38. ins_item->value=100;
  39. do {
  40. (ins_item)->entries.tqe_prev = (item)->entries.tqe_prev;
  41. (ins_item)->entries.tqe_next = (item);
  42. *(item)->entries.tqe_prev = (ins_item);
  43. (item)->entries.tqe_prev = &(ins_item)->entries.tqe_next;
  44. } while (0);
  45. tmp_item=((&queue_head)->tqh_first);
  46. printf("first element is %d\n",tmp_item->value);
  47. tmp_item=((tmp_item)->entries.tqe_next);
  48. printf("next element is %d\n",tmp_item->value);
  49. tmp_item=((tmp_item)->entries.tqe_next);
  50. printf("next element is %d\n",tmp_item->value);
  51. tmp_item=((tmp_item)->entries.tqe_next);
  52. printf("next element is %d\n",tmp_item->value);
  53. }

最新文章

  1. 【Win 10 应用开发】手写识别
  2. webserver几个例子
  3. [课程设计]Scrum 1.3 多鱼点餐系统开发进度
  4. C#与js的各种交互
  5. 建立一个node.js服务器(使用express搭建第一个Web环境)
  6. 怎样去掉FireFox的导入向导
  7. How Tomcat Works（五）
  8. HDU 1672 Cuckoo Hashing
  9. UVa 11174 (乘法逆元) Stand in a Line
  10. js中的if判断十分优美的简洁写法
  11. spring Mvc json返回json的日期格式问题
  12. POJ - 3903 Stock Exchange（LIS最长上升子序列问题）
  13. HBase 1、HBase介绍和工作原理
  14. Maven 项目 @Override must override a superclass method` 问题
  15. java课程设计-猜数游戏
  16. NOIP初赛 之 哈夫曼树
  17. 【转】NOR Flash擦写和原理分析
  18. SAP中的读访问日志Read Access Logging（RAL）
  19. nginx基本配置参数说明
  20. Nginx 阻塞与非阻塞

热门文章

  1. HDU 5119 Happy Matt Friends (背包DP + 滚动数组)
  2. Codeforces 1176B - Merge it!
  3. FreeBSD_11-系统管理——{Part_a-bhyve}
  4. SPOE网络供电
  5. jQuery validate验证隐藏表单(hidden)域
  6. Bootstrap入门及其常用内置实现
  7. js button禁用/启用
  8. TRUNCATE - 清空一个表
  9. Linux 守护进程创建
  10. linux常用命令-2网络相关命令