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

全部博文(31)

文章存档

2014年(31)

我的朋友

分类: C/C++

2014-05-28 09:55:14



TQILQ的队列图例:




点击(此处)折叠或打开

  1. /*
  2.  * Tail queue definitions.
  3.  */
  4. #define TAILQ_HEAD(name, type)                        \ //定义一TAILQ链表的头节点,name名字,type链表对象
  5. struct name {                                \
  6.     struct type *tqh_first;    /* first element */            \
  7.     struct type **tqh_last;    /* addr of last next element */        \
  8. }
展开TAILQ_HEAD(eventlist,event)
struct eventlist{
    struct event *tqh_first;
    struct event  **tqh_last;      //指向最后一个元素的next指针(保存的是最后一个元素的next指针地址)
}




点击(此处)折叠或打开

  1. #define TAILQ_HEAD_INITIALIZER(head)                    \
  2.     { NULL, &(head).tqh_first }
展开TAILQ_HEAD_INITIALIZER(pEventBase->eventqueue)  {NULL, &(pEvent->eventBase).tqh_first}



点击(此处)折叠或打开

  1. #define TAILQ_ENTRY(type)                        \
  2. struct {                                \
  3.     struct type *tqe_next;    /* next element */            \
  4.     struct type **tqe_prev;    /* address of previous next element */    \
  5. }
展开TAILQ_ENTRY(event)
struct {
    struct event *tqe_next;
    struct event **tqe_prev;
}


点击(此处)折叠或打开

  1. /*
  2.  * tail queue access methods
  3.  */
  4. #define    TAILQ_FIRST(head)        ((head)->tqh_first)
展开TAILQ_FIRST(&pEventBase->queue)   ( ( &pEventBase->queue)->tqh_first)


点击(此处)折叠或打开

  1. #define    TAILQ_END(head)            NULL
展开TAIL_END(&pEventBase->eventqueue)  NULL


点击(此处)折叠或打开

  1. #define    TAILQ_NEXT(elm, field)        ((elm)->field.tqe_next)
展开TAILQ_NEXT(pEvent, event_next)   ( ( pEvent)->event_next.tqe_next)


点击(此处)折叠或打开

  1. #define TAILQ_LAST(head, headname)                    \ //获取queue的最后一个节点,首先获取指向最后一个节点的last的指针,将该指针强制转换成struct headname *,这样做的目的是方便获取prev指针,
  2.     (*(((struct headname *)((head)->tqh_last))->tqh_last)) //获取prev后,实际上得到了上一个节点的next指针的地址,取*号,得到next指针指的对象,也就是最后一个元素
展开TAILQ_LAST(&pEventBase->eventqueue, eventlist)
( * ( ( ( struct eventlist *) ( ( &pEventBase->eventqueue)->tqh_last )) -> tqh_last))


( &pEventBase->eventqueue)    //得到指向头节点的指针(得到头节点的地址)
(&pEventBase->eventqueue)->tqh_last    //得到指向最后一个节点的next指针的指针  (得到最后一个节点的next指针的地址)
( struct eventlist *) ( ( &pEventBase->eventqueue)->tqh_last ))    //强制转换成eventlist *    (将next指针的地址强制转换成eventlist *)
( ( struct eventlist *) ( ( &pEventBase->eventqueue)->tqh_last )) -> tqh_last    //得到指向最后一个节点的上一个节点的next指针的指针(最后一个节点的上一个节点的next指针的地址 
* ( ( ( struct eventlist *) ( ( &pEventBase->eventqueue)->tqh_last )) -> tqh_last)    //得到指向最后一个元素的指针  (得到最后一个元素的地址)



点击(此处)折叠或打开

  1. #define TAILQ_PREV(elm, headname, field)                \ //获取elm元素的上一个元素,
  2.     (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
展开TAILQ_PREV(pEvent, eventlist, event_next)
( *( ( ( struct  eventlist * )( (pEvent)->event_next.tqe_prev))->tqh_last ) ) 


(pEvent)->event_next.tqe_prev)  //得到上一个元素的next指针
( struct  eventlist * )( (pEvent)->event_next.tqe_prev))   //把上一个元素的next指针强制转换成eventlist指针
( ( struct  eventlist * )( (pEvent)->event_next.tqe_prev))->tqh_last    //得到强制转换后的tqh_last指针,该指针指向上一个元素的上一个元素的next指针
*( ( ( struct  eventlist * )( (pEvent)->event_next.tqe_prev))->tqh_last )    //对prev进行解析,得到指向上一个元素的指针



TAILQ_LAST宏与TAILQ_PREV宏比较难理解,需要对指针、地址两者之间的转换与联系有很强的理解。


点击(此处)折叠或打开

  1. #define    TAILQ_EMPTY(head)                        \
  2.     (TAILQ_FIRST(head) == TAILQ_END(head))
展开TAILQ_EMPTY(&pEventBase)  (  ( ( &pEventBase->queue)->tqh_first) == NULL )


点击(此处)折叠或打开

  1. #define TAILQ_FOREACH(var, head, field)                    \
  2.     for((var) = TAILQ_FIRST(head);                    \
  3.      (var) != TAILQ_END(head);                    \
  4.      (var) = TAILQ_NEXT(var, field))
展开TAILQ_FOREACH(pTmp, &pEventBase->eventqueue, event_next)
    for((pTmp) = TAILQ_FIRST( &pEventBase->eventqueue);                    
      (pTmp) != TAILQ_END( &pEventBase->eventqueue);                    
     
(pTmp) = TAILQ_NEXT(pTmp,  event_next))


点击(此处)折叠或打开

  1. #define TAILQ_FOREACH_REVERSE(var, head, field, headname)        \  //反向遍历
  2.     for((var) = TAILQ_LAST(head, headname);                \
  3.      (var) != TAILQ_END(head);                    \
  4.      (var) = TAILQ_PREV(var, headname, field))
展开 TAILQ_FOREACH_REVERSE(pTmp, &pEventBase->eventqueue, event_next, eventlist)
for((pTmp) = TAILQ_LAST(&pEventBase->eventqueue, headname);                \
      
(pTmp) != TAILQ_END(&pEventBase->eventqueue);                    \
      (pTmp) = TAILQ_PREV(pTmp, eventlist, event_next))




点击(此处)折叠或打开

  1. /*
  2.  * Tail queue functions.
  3.  */
  4. #define    TAILQ_INIT(head) do {                        \ //初始化链表的头节点
  5.     (head)->tqh_first = NULL;                    \
  6.     (head)->tqh_last = &(head)->tqh_first;                \
  7. } while (0)
展开TAILQ_INIT(&pEventBase->eventqueue)
do{   
     (&pEventBase->eventqueue)->tqh_first = NULL;                    \
      (&pEventBase->eventqueue)->tqh_last = &(&pEventBase->eventqueue)->tqh_first;                
while (0)



点击(此处)折叠或打开

  1. #define TAILQ_INSERT_HEAD(head, elm, field) do {            \    //从头部插入一个节点
  2.     if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)    \
  3.         (head)->tqh_first->field.tqe_prev =            \
  4.          &(elm)->field.tqe_next;                \
  5.     else                                \
  6.         (head)->tqh_last = &(elm)->field.tqe_next;        \
  7.     (head)->tqh_first = (elm);                    \
  8.     (elm)->field.tqe_prev = &(head)->tqh_first;            \
  9. } while (0)
  1. if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)    \    //让elm的next指针指向head的first指针所指对象(也就是第一个节点)
  2.         (head)->tqh_first->field.tqe_prev =            \    //让第一个节点的prev指向elm的next指针
  3.          &(elm)->field.tqe_next;                \
  4.     else                                \
  5.         (head)->tqh_last = &(elm)->field.tqe_next;        \    //让head的last指针指向elm的next指针
  6.     (head)->tqh_first = (elm);                    \    //让head的first指针指向elm所指对象
  7.     (elm)->field.tqe_prev = &(head)->tqh_first;            \    //让elm的prev指针指向head的first指针



点击(此处)折叠或打开

  1. #define TAILQ_INSERT_TAIL(head, elm, field) do {            \    //从尾部插入一个节点
  2.     (elm)->field.tqe_next = NULL;                    \
  3.     (elm)->field.tqe_prev = (head)->tqh_last;            \
  4.     *(head)->tqh_last = (elm);                    \
  5.     (head)->tqh_last = &(elm)->field.tqe_next;            \
  6. } while (0)
  1.  (elm)->field.tqe_next = NULL;                    \    //让elm的next指针指向null
  2.  (elm)->field.tqe_prev = (head)->tqh_last;            \    //让elm的prev指针指向head的last指针所指对象(也就是最后一个元素的next指针)
  3.  *(head)->tqh_last = (elm);                    \    //让最后一个元素的next指针指向elm所指元素
  4.  (head)->tqh_last = &(elm)->field.tqe_next;            \    //让head的last指针指向elm的next指针






点击(此处)折叠或打开

  1. #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {        \    //在listelm后插入elm
  2.     if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\   
  3.         (elm)->field.tqe_next->field.tqe_prev =            \
  4.          &(elm)->field.tqe_next;                \
  5.     else                                \
  6.         (head)->tqh_last = &(elm)->field.tqe_next;        \
  7.     (listelm)->field.tqe_next = (elm);                \
  8.     (elm)->field.tqe_prev = &(listelm)->field.tqe_next;        \
  9. } while (0)

  1.  if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\   //让elm的next指针指向listelm的next指针所指元素(也就是listelm的下一个元素)
  2.         (elm)->field.tqe_next->field.tqe_prev =            \    //让elm的next指针所指元素(listelm的下一个元素)的prev指针指向elm的next指针
  3.          &(elm)->field.tqe_next;                \
  4.     else                                \
  5.         (head)->tqh_last = &(elm)->field.tqe_next;        \    //让head的last指针指向elm的next指针
  6.     (listelm)->field.tqe_next = (elm);                \    //让listelm的next指针指向elm所指元素
  7.     (elm)->field.tqe_prev = &(listelm)->field.tqe_next;        \    //让elm的prev指向listelm的next指针




点击(此处)折叠或打开

  1. #define    TAILQ_INSERT_BEFORE(listelm, elm, field) do {            \    //在listelm前插入elm
  2.     (elm)->field.tqe_prev = (listelm)->field.tqe_prev;        \
  3.     (elm)->field.tqe_next = (listelm);                \
  4.     *(listelm)->field.tqe_prev = (elm);                \
  5.     (listelm)->field.tqe_prev = &(elm)->field.tqe_next;        \
  6. } while (0)

  1.     (elm)->field.tqe_prev = (listelm)->field.tqe_prev;        \    //让elm的prev指针指向listelm的prev所指元素(也就是listelm上一个元素的next指针)
  2.     (elm)->field.tqe_next = (listelm);                \    //让elm的next指针指向listelm所指元素
  3.     *(listelm)->field.tqe_prev = (elm);                \    //让listelm的上一个元素的next指针指向elm所指元素
  4.     (listelm)->field.tqe_prev = &(elm)->field.tqe_next;        \    //让listelm的prev指针指向elm的next指针




点击(此处)折叠或打开

  1. #define TAILQ_REMOVE(head, elm, field) do {                \   //移除elm
  2.     if (((elm)->field.tqe_next) != NULL)                \
  3.         (elm)->field.tqe_next->field.tqe_prev =            \
  4.          (elm)->field.tqe_prev;                \
  5.     else                                \
  6.         (head)->tqh_last = (elm)->field.tqe_prev;        \
  7.     *(elm)->field.tqe_prev = (elm)->field.tqe_next;            \
  8. } while (0)
  1.  if (((elm)->field.tqe_next) != NULL)                \   //如果elm的next不是指向NULL
  2.         (elm)->field.tqe_next->field.tqe_prev =            \    //让elm下一个元素的prev指针指向elm上一个元素的next指针
  3.          (elm)->field.tqe_prev;                \
  4.     else                                \    //如果elm的next指针指向NULL
  5.         (head)->tqh_last = (elm)->field.tqe_prev;        \    //让head的last指针指向elm的上一个元素的next指针
  6.     *(elm)->field.tqe_prev = (elm)->field.tqe_next;            \    //让elm的上一个元素的next指针指向elm的next指针所指元素(如果elm是最后一个元素,则是NULL)






阅读(836) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~