Chinaunix首页 | 论坛 | 博客

hjun119620的CU博客

首页　| 　博文目录　| 　关于我

hjun119620

  • 博客访问： 96007
  • 博文数量： 31
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 380
  • 用 户 组： 普通用户
  • 注册时间： 2014-02-24 22:04
文章分类

全部博文（31）

文章存档

2014年（31）

我的朋友
最近访客
推荐博文
相关博文
queue.h(Circular queue 循环队列)

分类： C/C++

2014-05-28 16:50:01



Circular queue图例：




点击(此处)折叠或打开

  1. /*
  2.  * Circular queue definitions.
  3.  */
  4. #define CIRCLEQ_HEAD(name, type)                    \
  5. struct name {                                \
  6.     struct type *cqh_first;        /* first element */        \
  7.     struct type *cqh_last;        /* last element */        \
  8. }
展开CIRCLEQ_HEAD(eventlist,event)
struct eventlist{
    struct event * cqh_first;
    struct event * cqu_last;
}



点击(此处)折叠或打开

  1. #define CIRCLEQ_HEAD_INITIALIZER(head)                    \    //这里的head是头节点，而不是指向头节点的指针
  2.     { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
展开CIRCLEQ_HEAD_INITIALIZER(sEventBase)   { CIRCLEQ_END(&sEventBase), CIRCLEQ_END(&sEventBase) }
继续展开  {  (void *) (&sEventBase),  (void *)（&sEventBase)  }


点击(此处)折叠或打开

  1. #define CIRCLEQ_ENTRY(type)                        \
  2. struct {                                \
  3.     struct type *cqe_next;        /* next element */        \
  4.     struct type *cqe_prev;        /* previous element */        \
  5. }

展开CRICLE_ENTRY(event)
strcut  {
    struct event * cqe_next;
    struct event *cqe_prev;
}


点击(此处)折叠或打开

  1. /*
  2.  * Circular queue access methods
  3.  */
  4. #define    CIRCLEQ_FIRST(head)        ((head)->cqh_first)    //得到第一个节点的指针
展开CIRCLE_FIRST(pEventBase)  ((pEventBase)->cqh_first)



点击(此处)折叠或打开

  1. #define    CIRCLEQ_LAST(head)        ((head)->cqh_last)
展开CIRCLEQ_LAST(pEventBase)   ((pEventBase)->cqh_last)


点击(此处)折叠或打开

  1. #define    CIRCLEQ_END(head)        ((void *)(head))
展开CIRCLEQ_END(pEventBase)   ((void *)(pEventBase))


点击(此处)折叠或打开

  1. #define    CIRCLEQ_NEXT(elm, field)    ((elm)->field.cqe_next)
展开CIRCLEQ_NEXT(elm,event_next)   ((elm)->event_next.cqe_next)


点击(此处)折叠或打开

  1. #define    CIRCLEQ_PREV(elm, field)    ((elm)->field.cqe_prev)
展开CIRCLEQ(elm,event_next)  ((elm)->event_next.cqe_prev)


点击(此处)折叠或打开

  1. #define    CIRCLEQ_EMPTY(head)                        \
  2.     (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
展开CIRCLEQ_FIRST(pEventBase)    (     ((pEventBase)->cqh_first)   ==  ((void *)(pEventBase))  )  


点击(此处)折叠或打开

  1. #define CIRCLEQ_FOREACH(var, head, field)                \
  2.     for((var) = CIRCLEQ_FIRST(head);                \
  3.      (var) != CIRCLEQ_END(head);                    \
  4.      (var) = CIRCLEQ_NEXT(var, field))
展开CIRCLEQ_FOREACH(pTmp, pEventBase, event_next)  
for ( (pTmp) = CIRCLEQ_FIRST(pEvent) ;
    (pTmp) != CIRCLEQ_END(pEventBase);
    (pTmp) = CIRCLEQ_NEXT(pTmp,event_next) )
继续展开
for ( (pTmp) = ((pEventBase)->cqh_first);
    (pTmp) != ((void *)(pEventBase));
    (pTmp) = ((pTmp)->event_next.cqe_next) )



 

点击(此处)折叠或打开

  1. #define CIRCLEQ_FOREACH_REVERSE(var, head, field)            \
  2.     for((var) = CIRCLEQ_LAST(head);                    \
  3.      (var) != CIRCLEQ_END(head);                    \
  4.      (var) = CIRCLEQ_PREV(var, field))
展开CIRCLEQ_FOREACH_REVERSE(pTmp, pEventBase, event_next)
for( ( pTmp) = CIRCLEQ_LAST(pEventBase);
    (pTmp) != CIRCLEQ_END(pEventBase);
    (pTmp) = CIRCLEQ_PREV(pTmp,event_next))
继续展开
for( (pTmp0 = ((pEventBase)->cqe_last);
    (pTmp) != ((void *) (pEventBase);
    (pTmp) = ((pTmp)->event_next.cqe.prev) )



点击(此处)折叠或打开

  1. /*
  2.  * Circular queue functions.
  3.  */
  4. #define    CIRCLEQ_INIT(head) do {                        \   //初始化头节点，让头节点的first指针指向head，让头节点的second指针指向head
  5.     (head)->cqh_first = CIRCLEQ_END(head);                \
  6.     (head)->cqh_last = CIRCLEQ_END(head);                \
  7. } while (0)
展开CIRCLEQ_INIT(pEventBase) 
do{
    (pEventBase)->cqh_first = ((void *)(pEventBase));
    (pEventBase)->cqh_second=((void *)(pEventBase));
}while(0)



点击(此处)折叠或打开

  1. #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {        \    //在listelm前插入elm所指元素
  2.     (elm)->field.cqe_next = (listelm)->field.cqe_next;        \
  3.     (elm)->field.cqe_prev = (listelm);                \
  4.     if ((listelm)->field.cqe_next == CIRCLEQ_END(head))        \
  5.         (head)->cqh_last = (elm);                \
  6.     else                                \
  7.         (listelm)->field.cqe_next->field.cqe_prev = (elm);    \
  8.     (listelm)->field.cqe_next = (elm);                \
  9. } while (0)


  1. (elm)->field.cqe_next = (listelm)->field.cqe_next;        \    //让elm的next指针指向listelm的下一个元素
  2.     (elm)->field.cqe_prev = (listelm);                \    //让elm的prev指针指向listelm
  3.     if ((listelm)->field.cqe_next == CIRCLEQ_END(head))        \    //若listelm的next指向头节点，
  4.         (head)->cqh_last = (elm);                \    //让head的last指针指向elm所指元素
  5.     else                                \
  6.         (listelm)->field.cqe_next->field.cqe_prev = (elm);    \    //让listelm的下一个元素的prev指针指向elm所指元素
  7.     (listelm)->field.cqe_next = (elm);           //让listelm的next指针指向elm所指元素


点击(此处)折叠或打开

  1. #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {        \在listelm后插入elm所指元素
  2.     (elm)->field.cqe_next = (listelm);                \
  3.     (elm)->field.cqe_prev = (listelm)->field.cqe_prev;        \
  4.     if ((listelm)->field.cqe_prev == CIRCLEQ_END(head))        \
  5.         (head)->cqh_first = (elm);                \
  6.     else                                \
  7.         (listelm)->field.cqe_prev->field.cqe_next = (elm);    \
  8.     (listelm)->field.cqe_prev = (elm);                \
  9. } while (0)


  (elm)->field.cqe_next = (listelm);                \    //让elm的next指针指向listelm所指元素
  1.     (elm)->field.cqe_prev = (listelm)->field.cqe_prev;        \    //让elm的prev指针指向listelm的上一个元素
  2.     if ((listelm)->field.cqe_prev == CIRCLEQ_END(head))        \    //如果listelm的prev指向head
  3.         (head)->cqh_first = (elm);                \    //让head的first指针指向elm所指元素
  4.     else                                \
  5.         (listelm)->field.cqe_prev->field.cqe_next = (elm);    \    //让listelm的上一个元素的next指针指向elm所指元素
  6.     (listelm)->field.cqe_prev = (elm);                    //让listelm的prev指针指向elm所指元素


点击(此处)折叠或打开

  1. #define CIRCLEQ_INSERT_HEAD(head, elm, field) do {            \    //在队列头部插入节点
  2.     (elm)->field.cqe_next = (head)->cqh_first;            \
  3.     (elm)->field.cqe_prev = CIRCLEQ_END(head);            \
  4.     if ((head)->cqh_last == CIRCLEQ_END(head))            \
  5.         (head)->cqh_last = (elm);                \
  6.     else                                \
  7.         (head)->cqh_first->field.cqe_prev = (elm);        \
  8.     (head)->cqh_first = (elm);                    \
  9. } while (0)


  1.     (elm)->field.cqe_next = (head)->cqh_first;            \    //让elm的next指针指向head的first指针所指元素（就是第一个元素）
  2.     (elm)->field.cqe_prev = CIRCLEQ_END(head);            \    //让elm的prev指针指向head指针所指元素（就是头节点）
  3.     if ((head)->cqh_last == CIRCLEQ_END(head))            \    //如果head的last指针指向头节点
  4.         (head)->cqh_last = (elm);                \    //让head的last指针指向elm
  5.     else                                \
  6.         (head)->cqh_first->field.cqe_prev = (elm);        \    //让head的first指针所指元素(就是第一个元素）的prev指针指向elm所指对象
  7.     (head)->cqh_first = (elm);                    \    //让head的first指针指向elm所指对象




点击(此处)折叠或打开

  1. #define CIRCLEQ_INSERT_TAIL(head, elm, field) do {            \    //在队列尾部插入节点
  2.     (elm)->field.cqe_next = CIRCLEQ_END(head);            \
  3.     (elm)->field.cqe_prev = (head)->cqh_last;            \
  4.     if ((head)->cqh_first == CIRCLEQ_END(head))            \
  5.         (head)->cqh_first = (elm);                \
  6.     else                                \
  7.         (head)->cqh_last->field.cqe_next = (elm);        \
  8.     (head)->cqh_last = (elm);                    \
  9. } while (0)


  1.  (elm)->field.cqe_next = CIRCLEQ_END(head);            \    //让elm的next指针指向head指针所指元素（就是头元素）
  2.     (elm)->field.cqe_prev = (head)->cqh_last;            \    //让elm的prev指针指向head的last指针所指元素（就是最后一个元素）
  3.     if ((head)->cqh_first == CIRCLEQ_END(head))            \    //如果head的first指针指向头元素
  4.         (head)->cqh_first = (elm);                \    //让head的first指针指向elm所指元素
  5.     else                                \
  6.         (head)->cqh_last->field.cqe_next = (elm);        \    //让最后一个元素的next指针指向elm
  7.     (head)->cqh_last = (elm);                    \    //让head的last指针指向elm所指对象



点击(此处)折叠或打开

  1. #define    CIRCLEQ_REMOVE(head, elm, field) do {                \   //移除elm所指元素
  2.     if ((elm)->field.cqe_next == CIRCLEQ_END(head))            \
  3.         (head)->cqh_last = (elm)->field.cqe_prev;        \
  4.     else                                \
  5.         (elm)->field.cqe_next->field.cqe_prev =            \
  6.          (elm)->field.cqe_prev;                \
  7.     if ((elm)->field.cqe_prev == CIRCLEQ_END(head))            \
  8.         (head)->cqh_first = (elm)->field.cqe_next;        \
  9.     else                                \
  10.         (elm)->field.cqe_prev->field.cqe_next =            \
  11.          (elm)->field.cqe_next;                \
  12. } while (0)


  1.  if ((elm)->field.cqe_next == CIRCLEQ_END(head))            \    //如果elm的next指针指向head（就是头节点）
  2.         (head)->cqh_last = (elm)->field.cqe_prev;        \    //让head的的last元素指向elm的上一个元素
  3.     else                                \
  4.         (elm)->field.cqe_next->field.cqe_prev =            \    //让elm下一个元素的prev指针指向elm的上一个元素
  5.          (elm)->field.cqe_prev;                \
  6.     if ((elm)->field.cqe_prev == CIRCLEQ_END(head))            \    //如果elm的prev指针指向头节点
  7.         (head)->cqh_first = (elm)->field.cqe_next;        \    //让head的first指针指向elm的下一个元素
  8.     else                                \
  9.         (elm)->field.cqe_prev->field.cqe_next =            \   //让elm的上一给元素的next指针指向elm的下一个元素
  10.          (elm)->field.cqe_next;                \



点击(此处)折叠或打开

  1. #define CIRCLEQ_REPLACE(head, elm, elm2, field) do {            \    //用elm2所指对象替换elm所指对象     这里的head是head对象，而不是指向head的指针
  2.     if (((elm2)->field.cqe_next = (elm)->field.cqe_next) ==        \    
  3.      CIRCLEQ_END(head))                        \
  4.         (head).cqh_last = (elm2);                \    
  5.     else                                \
  6.         (elm2)->field.cqe_next->field.cqe_prev = (elm2);    \
  7.     if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) ==        \
  8.      CIRCLEQ_END(head))                        \
  9.         (head).cqh_first = (elm2);                \
  10.     else                                \
  11.         (elm2)->field.cqe_prev->field.cqe_next = (elm2);    \
  12. } while (0)



  1. if (((elm2)->field.cqe_next = (elm)->field.cqe_next) ==        \    //让elm2的next指针指向elm的next指针所指元素，且elm的next指针所指元素不是head
  2.      CIRCLEQ_END(head))                        \
  3.         (head).cqh_last = (elm2);                \    //让head的last指针指向elm2
  4.  else                                \
  5.         (elm2)->field.cqe_next->field.cqe_prev = (elm2);    \    //让elm2下一个元素的prev指针指向elm2
  6.   if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) ==        \    //让elm2的prev指针指向elm的上一个元素，且elm的上一个元素不是head
  7.      CIRCLEQ_END(head))                        \
  8.         (head).cqh_first = (elm2);                \    //让head的first指针指向elm2
  9.     else                                \
  10.         (elm2)->field.cqe_prev->field.cqe_next = (elm2);    \    //让elm2的上一个元素的next指针指向elm2






阅读(1843) | 评论(0) | 转发(0) |
0

上一篇：queue.h(Tail queue)

下一篇：event_internal.h中的主要数据结构

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6