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

全部博文(31)

文章存档

2014年(31)

我的朋友

分类: C/C++

2014-05-23 11:35:02




LIST图例:



点击(此处)折叠或打开

  1. /*
  2.  * List definitions.
  3.  */
  4. #define LIST_HEAD(name, type)                        \    //链表头定义
  5. struct name {                                \
  6.     struct type *lh_first;    /* first element */            \
  7. }
展开SLIST_HEAD (event_list, event) 
struct event_list { 
struct event *slh_first; /* first element */ \
}
这样就定义了event_list结构,该结构具有一个访问event结构的指针slh_first



点击(此处)折叠或打开

  1. #define LIST_HEAD_INITIALIZER(head)                    \  //链表头初始化
  2.     { NULL }
展开SLIST_HEAD_INITIALIZER(&pEventbase->eventqueue)  { NULL }
eventqueue是event_list结构对象,该宏是把eventqueue中的slh_first赋值为NULL


点击(此处)折叠或打开

  1. #define LIST_ENTRY(type)                        \    //链表结点定义
  2. struct {                                \
  3.     struct type *le_next;    /* next element */            \
  4.     struct type **le_prev;    /* address of previous next element */    \
  5. }
展开LIST_ENTRY(event)
struct{
    struct event *le_next;    
    struct event **le_prev;    
}


ENTRY结构被用在event结构中
struct event{
    TAILQ_ENTRY(event) ev_next;   //这里可以把TAILQ_ENTRY理解成LIST_ENTRY
    ...
}展开为
struct event{
    struct{
        struct event *le_next;    //指向下一个event结构的节点,实际上存放的是下一个event节点的地址
        struct event **le_prev;    //指向上一个event结构的节点,,实际上存放的是上一个event结构中event_next结构中le_next指针的地址
    } ev_next;
    ...
}



点击(此处)折叠或打开

  1. /*
  2.  * List access methods
  3.  */
  4. #define    LIST_FIRST(head)        ((head)->lh_first)     //返回指向第一个节点的指针
展开LIST_FIRST(&pEventBase->eventqueue)    ((&pEventBase->eventqueue)->lh_first)



点击(此处)折叠或打开

  1. #define    LIST_END(head)            NULL    //链表尾部
展开LIST_END(&pEventBase->eventqueue)  NULL


点击(此处)折叠或打开

  1. #define    LIST_EMPTY(head)        (LIST_FIRST(head) == LIST_END(head))    //判断链表是否为空
展开LIST_EMPTY(&pEventBase->eventqueue)    (  ((&pEventBase->eventqueue)->lh_first)  == NULL )



点击(此处)折叠或打开

  1. #define    LIST_NEXT(elm, field)        ((elm)->field.le_next)    //获取elm指针所指的元素的下个元素的指针
展开LIST_NEXT(pEvent,event_next)   ( (pEvent)->event_next.le_next)


点击(此处)折叠或打开

  1. #define LIST_FOREACH(var, head, field)                    \    //遍历链表
  2.     for((var) = LIST_FIRST(head);                    \
  3.      (var)!= LIST_END(head);                    \
  4.      (var) = LIST_NEXT(var, field))
展开LIST_FOREACH(pTmp, &pEventBase->eventqueue, event_next)
    for((pTmp) = LIST_FIRST(&pEventBase->eventqueue);
        (pTmp) != LIST_END(&pEventBase->eventqueue);
        (pTmp) =LIST_NEXT(pTmp,event_next) )继续展开
   for((pTmp) =  ((&pEventBase->eventqueue)->lh_first) ;
        (pTmp) !=NULL;
        (pTmp) = ( (pEvent)->event_next.le_next) )


点击(此处)折叠或打开

  1. /*
  2.  * List functions.
  3.  */
  4. #define    LIST_INIT(head) do {                        \    //链表初始化
  5.     LIST_FIRST(head) = LIST_END(head);                \
  6. } while (0)
展开LIST_INIT(&pEventBase->eventqueue)
do{
      ((&pEventBase->eventqueue)->lh_first)  = NULL;
}while(0)


点击(此处)折叠或打开

  1. #define LIST_INSERT_AFTER(listelm, elm, field) do {            \     //在listelm所指元素后插入elm所指元素
  2.     if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)    \
  3.         (listelm)->field.le_next->field.le_prev =        \
  4.          &(elm)->field.le_next;                \
  5.     (listelm)->field.le_next = (elm);                \
  6.     (elm)->field.le_prev = &(listelm)->field.le_next;        \
  7. } while (0)
初始状态:


执行LIST_INSERT_AFTER后:


图中的1,2,3,4分别对应
1.  (elm)->field.le_next = (listelm)->field.le_next                      //让elm的next指针指向listelm的next指针所指元素(也就是listelm的下一个节点)
2. (listelm)->field.le_next->field.le_prev = &(elm)->field.le_next;     //让listelm的下一个节点的prev指针指向elm的next指针
3. (listelm)->field.le_next = (elm);                                    //让listelm的next指针指向elm所指对象     
4.  (elm)->field.le_prev = &(listelm)->field.le_next;                   //  让elm的prev指针指向listelm的next指针

点击(此处)折叠或打开

  1. #define    LIST_INSERT_BEFORE(listelm, elm, field) do {            \    //在listelm所指元素前插入elm所指元素
  2.     (elm)->field.le_prev = (listelm)->field.le_prev;        \
  3.     (elm)->field.le_next = (listelm);                \
  4.     *(listelm)->field.le_prev = (elm);                \
  5.     (listelm)->field.le_prev = &(elm)->field.le_next;        \
  6. } while (0)
初始状态:


执行LIST_INSERT_BEFORE(listelm, elm, field) 


图中的1,2,3,4分别对应
1.  (elm)->field.le_prev = (listelm)->field.le_prev;                    //让elm的prev指针指向listelm的prev指针所指对象       
2.  (elm)->field.le_next = (listelm);                                   //让elm的next指针指向listelm指针所指对象
3.   *(listelm)->field.le_prev = (elm);                                 //让listelm的上一个节点的next指针指向elm所指对象   *(listelm)->field.le_prev结构获取listelm上一个节点的next指针     
4.   (listelm)->field.le_prev = &(elm)->field.le_next;                  //让listelm指针的prev指针指向elm的next指针





点击(此处)折叠或打开

  1. #define LIST_INSERT_HEAD(head, elm, field) do {                \     //在head所指元素后插入elm所指元素,也就是在第一个元素前插入elm
  2.     if (((elm)->field.le_next = (head)->lh_first) != NULL)        \
  3.         (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
  4.     (head)->lh_first = (elm);                    \
  5.     (elm)->field.le_prev = &(head)->lh_first;            \
  6. } while (0)
初始状态:

执行 LIST_INSERT_HEAD(head, elm, field) 后




图中的1,2,3,4分别对应
1. (elm)->field.le_next = (head)->lh_first                            //让elm的next指针指向head的lh_first所指元素,也就是第一个元素
2.  (head)->lh_first->field.le_prev = &(elm)->field.le_next;       //让第一个元素的prev指针指向elm的next指针
3.  (head)->lh_first = (elm);                                     //让head的lh_first指针指向elm所指元素
4.   (elm)->field.le_prev = &(head)->lh_first;                    // 让elm的prev指向head的lh_first指针   



点击(此处)折叠或打开

  1. #define LIST_REMOVE(elm, field) do {                    \    //移除elm所指元素
  2.     if ((elm)->field.le_next != NULL)                \
  3.         (elm)->field.le_next->field.le_prev =            \
  4.          (elm)->field.le_prev;                \
  5.     *(elm)->field.le_prev = (elm)->field.le_next;            \
  6. } while (0)
初始状态:

执行 LIST_REMOVE(elm, field)后




图中的1,2分别对应
1. (elm)->field.le_next->field.le_prev = (elm)->field.le_prev;    //让elm下一个元素的prev指针指向elm的prev指针所指元素(让elm的下一个元素的prev指针指向elm的上一个元素的next指针)
2.  *(elm)->field.le_prev = (elm)->field.le_next;                 //让elm的上一个元素的next指针指向elm的next指针所指元素


执行LIST_REMOVE(elm, field)后,elm的next指针与prev指针依然指向链表的节点,只不过链表中的节点不会再指向elm了

点击(此处)折叠或打开

  1. #define LIST_REPLACE(elm, elm2, field) do {                \     //用elm2所指元素替换elm所指元素
  2.     if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)    \
  3.         (elm2)->field.le_next->field.le_prev =            \
  4.          &(elm2)->field.le_next;                \
  5.     (elm2)->field.le_prev = (elm)->field.le_prev;            \
  6.     *(elm2)->field.le_prev = (elm2);                \
  7. } while (0)
初始状态:

执行LIST_REPLACE(elm, elm2, field)后





图中的1,2,3,4分别对应
1. (elm2)->field.le_next = (elm)->field.le_next                                //让elm2的next指针指向elm的next指针所指元素(即elm的下一个元素)
2.  (elm2)->field.le_next->field.le_prev = &(elm2)->field.le_next;             //让elm2的下一个元素的prev指针指向elm2的next指针
3.  (elm2)->field.le_prev = (elm)->field.le_prev;                              //让elm2的prev指针指向elm的prev指针所指元素(即elm的上一个元素的next指针)
4.   *(elm2)->field.le_prev = (elm2);                                          //让elm2的上一个节点的next指针指向elm2所指元素( *(elm2)->field.le_prev  表示elm2的上一个元素的next指针)

执行LIST_REPLACE(elm, elm2, field)后,elm的next指针与prev指针依然指向链表中的节点,不过链表中的节点不再指向elm




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

上一篇:queue.h(slist)

下一篇:queue.h(SimpleQ)

给主人留下些什么吧!~~