libevent中的基本数据结构---queue.h

时间:2022-05-01 06:26:16
 1 /*
 2 * List definitions.
 3 * 双链表结构
 4 */
 5 #define LIST_HEAD(name, type)                        \
 6 struct name {                                \
 7     struct type *lh_first;    /* first element */            \
 8 }
 9 
10 #define LIST_HEAD_INITIALIZER(head)                    \
11                 { NULL }
12 //链表的入口元素 le_next 指向下一个节点  le_prev 指向上一个节点的next指针元素的地址
13 //这样做好处在于删除,插入时只需操作本节点就可以了 即使是头节点    
14 
15 #define LIST_ENTRY(type)                        \
16 struct {                                \
17     struct type *le_next;    /* next element */            \
18     struct type **le_prev;    /* address of previous next element */    \
19 }
20 
21 /*
22 * List access methods
23 */
24 #define    LIST_FIRST(head)        ((head)->lh_first)
25 #define    LIST_END(head)            NULL
26 #define    LIST_EMPTY(head)        (LIST_FIRST(head) == LIST_END(head))
27 #define    LIST_NEXT(elm, field)        ((elm)->field.le_next)
28 
29 #define LIST_FOREACH(var, head, field)                    \
30     for((var) = LIST_FIRST(head);                    \
31         (var)!= LIST_END(head);                    \
32         (var) = LIST_NEXT(var, field))
33 
34 /*
35 * List functions.
36 */
37 #define    LIST_INIT(head) do {                        \
38     LIST_FIRST(head) = LIST_END(head);                \
39         } while (0)
40 
41 #define LIST_INSERT_AFTER(listelm, elm, field) do {            \
42     if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)    \
43         (listelm)->field.le_next->field.le_prev =        \
44             &(elm)->field.le_next;                \
45     (listelm)->field.le_next = (elm);                \
46     (elm)->field.le_prev = &(listelm)->field.le_next;        \
47 } while (0)
48 
49 //上一个节点的next元素的位置不变 只是next的内容改变 变为要插入元素的地址
50 #define    LIST_INSERT_BEFORE(listelm, elm, field) do {            \
51     (elm)->field.le_prev = (listelm)->field.le_prev;        \
52     (elm)->field.le_next = (listelm);                \
53     *(listelm)->field.le_prev = (elm);                \
54     (listelm)->field.le_prev = &(elm)->field.le_next;        \
55 } while (0)
56 
57 #define LIST_INSERT_HEAD(head, elm, field) do {                \
58     if (((elm)->field.le_next = (head)->lh_first) != NULL)        \
59         (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
60     (head)->lh_first = (elm);                    \
61     (elm)->field.le_prev = &(head)->lh_first;            \
62 } while (0)
63 
64 #define LIST_REMOVE(elm, field) do {                    \
65     if ((elm)->field.le_next != NULL)                \
66         (elm)->field.le_next->field.le_prev =            \
67             (elm)->field.le_prev;                \
68     *(elm)->field.le_prev = (elm)->field.le_next;            \
69 } while (0)
70 
71 #define LIST_REPLACE(elm, elm2, field) do {                \
72     if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)    \
73         (elm2)->field.le_next->field.le_prev =            \
74             &(elm2)->field.le_next;                \
75     (elm2)->field.le_prev = (elm)->field.le_prev;            \
76     *(elm2)->field.le_prev = (elm2);                \
77 } while (0)

 

  1 /*
  2 * Tail queue definitions.
  3 */
  4 // LIST 与SIMPLEQ结合
  5 //双链表结构的尾队列   tqh_last 尾节点的next元素的地址
  6 #define TAILQ_HEAD(name, type)                        \
  7 struct name {                                \
  8     struct type *tqh_first;    /* first element */            \
  9     struct type **tqh_last;    /* addr of last next element */        \
 10 }
 11 
 12 #define TAILQ_HEAD_INITIALIZER(head)                    \
 13                 { NULL, &(head).tqh_first }
 14 
 15 // tqe_prev上一个元素的next元素的地址
 16 #define TAILQ_ENTRY(type)                        \
 17 struct {                                \
 18     struct type *tqe_next;    /* next element */            \
 19     struct type **tqe_prev;    /* address of previous next element */    \
 20 }
 21 
 22 /*
 23 * tail queue access methods
 24 */
 25 #define    TAILQ_FIRST(head)        ((head)->tqh_first)
 26 #define    TAILQ_END(head)            NULL
 27 #define    TAILQ_NEXT(elm, field)        ((elm)->field.tqe_next)
 28 #define TAILQ_LAST(head, headname)                    \
 29     (*(((struct headname *)((head)->tqh_last))->tqh_last))
 30 /* XXX */
 31 #define TAILQ_PREV(elm, headname, field)                \
 32     (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
 33 #define    TAILQ_EMPTY(head)                        \
 34     (TAILQ_FIRST(head) == TAILQ_END(head))
 35 
 36 #define TAILQ_FOREACH(var, head, field)                    \
 37     for((var) = TAILQ_FIRST(head);                    \
 38         (var) != TAILQ_END(head);                    \
 39         (var) = TAILQ_NEXT(var, field))
 40 
 41 #define TAILQ_FOREACH_REVERSE(var, head, headname, field)        \
 42     for((var) = TAILQ_LAST(head, headname);                \
 43         (var) != TAILQ_END(head);                    \
 44         (var) = TAILQ_PREV(var, headname, field))
 45 
 46 /*
 47 * Tail queue functions.
 48 */
 49 #define    TAILQ_INIT(head) do {                        \
 50     (head)->tqh_first = NULL;                    \
 51     (head)->tqh_last = &(head)->tqh_first;                \
 52         } while (0)
 53 
 54 #define TAILQ_INSERT_HEAD(head, elm, field) do {            \
 55     if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)    \
 56         (head)->tqh_first->field.tqe_prev =            \
 57             &(elm)->field.tqe_next;                \
 58                 else                                \
 59         (head)->tqh_last = &(elm)->field.tqe_next;        \
 60     (head)->tqh_first = (elm);                    \
 61     (elm)->field.tqe_prev = &(head)->tqh_first;            \
 62 } while (0)
 63 
 64 #define TAILQ_INSERT_TAIL(head, elm, field) do {            \
 65     (elm)->field.tqe_next = NULL;                    \
 66     (elm)->field.tqe_prev = (head)->tqh_last;            \
 67     *(head)->tqh_last = (elm);                    \
 68     (head)->tqh_last = &(elm)->field.tqe_next;            \
 69 } while (0)
 70 
 71 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {        \
 72     if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
 73         (elm)->field.tqe_next->field.tqe_prev =            \
 74             &(elm)->field.tqe_next;                \
 75                 else                                \
 76         (head)->tqh_last = &(elm)->field.tqe_next;        \
 77     (listelm)->field.tqe_next = (elm);                \
 78     (elm)->field.tqe_prev = &(listelm)->field.tqe_next;        \
 79 } while (0)
 80 
 81 #define    TAILQ_INSERT_BEFORE(listelm, elm, field) do {            \
 82     (elm)->field.tqe_prev = (listelm)->field.tqe_prev;        \
 83     (elm)->field.tqe_next = (listelm);                \
 84     *(listelm)->field.tqe_prev = (elm);                \
 85     (listelm)->field.tqe_prev = &(elm)->field.tqe_next;        \
 86 } while (0)
 87 
 88 #define TAILQ_REMOVE(head, elm, field) do {                \
 89     if (((elm)->field.tqe_next) != NULL)                \
 90         (elm)->field.tqe_next->field.tqe_prev =            \
 91             (elm)->field.tqe_prev;                \
 92                 else                                \
 93         (head)->tqh_last = (elm)->field.tqe_prev;        \
 94     *(elm)->field.tqe_prev = (elm)->field.tqe_next;            \
 95 } while (0)
 96 
 97 #define TAILQ_REPLACE(head, elm, elm2, field) do {            \
 98     if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)    \
 99         (elm2)->field.tqe_next->field.tqe_prev =        \
100             &(elm2)->field.tqe_next;                \
101                 else                                \
102         (head)->tqh_last = &(elm2)->field.tqe_next;        \
103     (elm2)->field.tqe_prev = (elm)->field.tqe_prev;            \
104     *(elm2)->field.tqe_prev = (elm2);                \
105 } while (0)

 使用例子如下:

libevent中的基本数据结构---queue.hlibevent中的基本数据结构---queue.h
  1 #include "list.h"
  2 #include <stdlib.h>
  3 #include <stdio.h>
  4 
  5 struct Person{
  6     int age;
  7     double length;
  8     SLIST_ENTRY(Person) next;
  9 };
 10 
 11 struct A{
 12     int a;
 13     LIST_ENTRY(A) point;
 14 };
 15 
 16 struct B{
 17     int b;
 18     SIMPLEQ_ENTRY(B) next;
 19 };
 20 
 21 struct C{
 22     int c;
 23     TAILQ_ENTRY(C) entry;
 24 };
 25 
 26 struct D{
 27     int d;
 28     CIRCLEQ_ENTRY(D) entry;
 29 };
 30 
 31 static void slist_test()
 32 {
 33     SLIST_HEAD(slHead, Person) head;
 34     SLIST_INIT(&head);
 35     struct Person ace = { 27, 23.34, { NULL } };
 36     struct Person ice = { 24, 23.123, { NULL } };
 37     struct Person e = { 21, 23.3, { NULL } };
 38     struct Person i = { 28, 43.123, { NULL } };
 39     SLIST_INSERT_HEAD(&head, &ace, next);
 40     SLIST_INSERT_AFTER(&ace, &ice, next);
 41     SLIST_INSERT_AFTER(&ace, &e, next);
 42     SLIST_INSERT_AFTER(&ace, &i, next);
 43     if (!SLIST_EMPTY(&head))
 44     {
 45         struct Person *var = NULL;
 46         SLIST_FOREACH(var, &head, next)
 47         {
 48             printf(">>>>%d, %lf\n", var->age, var->length);
 49         }
 50     }
 51 }
 52 
 53 static void list_test()
 54 {
 55     LIST_HEAD(HEAD, A) head;
 56     LIST_INIT(&head);
 57     struct A a = { 12, {0} };
 58     struct A b = { 123, {0} };
 59     struct A c = { 1234, {0} };
 60     struct A d = { 12345, {0} };
 61     LIST_INSERT_HEAD(&head, &a, point);
 62     printf("%p, %p, %p, %p\n", &head, &a, a.point.le_prev , *a.point.le_prev);
 63     LIST_INSERT_BEFORE(&a, &b, point);
 64     printf("%p, %p", a.point.le_prev, *a.point.le_prev);
 65     LIST_INSERT_BEFORE(&a, &c, point);
 66     LIST_INSERT_BEFORE(&a, &d, point);
 67     struct A *var;
 68     if (!LIST_EMPTY(&head))
 69     {
 70         LIST_FOREACH(var, &head, point)
 71         {
 72             printf("----->%d\n", var->a);
 73         }
 74     }
 75 }
 76 
 77 static void simpleq_test()
 78 {
 79     SIMPLEQ_HEAD(Head, B) head;
 80     SIMPLEQ_INIT(&head);
 81     struct B a = { 1, {NULL} };
 82     struct B b = { 11, { NULL } };
 83     struct B c = { 111, { NULL } };
 84     struct B d = { 1111, { NULL } };
 85     SIMPLEQ_INSERT_HEAD(&head, &a, next);
 86     SIMPLEQ_INSERT_TAIL(&head, &b, next);
 87     SIMPLEQ_INSERT_TAIL(&head, &c, next);
 88     SIMPLEQ_INSERT_TAIL(&head, &d, next);
 89     printf("%p, %p, %p, %p, %p\n", &d, d.next, &d.next, head.sqh_last, *head.sqh_last);
 90     struct B *var;
 91     if (!SIMPLEQ_EMPTY(&head))
 92     {
 93         SIMPLEQ_FOREACH(var, &head, next)
 94         {
 95             printf("----->%d\n", var->b);
 96         }
 97     }
 98 }
 99 
100 static void tailq_test()
101 {
102     TAILQ_HEAD(HEAD, C) head;
103     TAILQ_INIT(&head);
104     struct C a = { 1, {0} };
105     struct C b = { 2, {0} };
106     struct C c = { 3, {0} };
107     struct C d = { 4, {0} };
108     TAILQ_INSERT_HEAD(&head, &a, entry);
109     TAILQ_INSERT_AFTER(&head, &a, &b, entry);
110     TAILQ_INSERT_BEFORE(&b, &c, entry);
111     TAILQ_INSERT_BEFORE(&b, &d, entry);
112     struct C * cp;
113     if (!TAILQ_EMPTY(&head))
114     {
115         TAILQ_FOREACH(cp, &head, entry)
116         {
117             printf(">>>>%d\n", cp->c);
118         }
119         TAILQ_FOREACH_REVERSE(cp, &head, HEAD, entry)
120         {
121             printf(">>>>%d\n", cp->c);
122         }
123     }
124 }
125 
126 int main()
127 {
128     //list_test();
129     //simpleq_test();
130     tailq_test();
131     return 0;
132 }
View Code

 

libevent使用: http://www.cppblog.com/mysileng/archive/2013/02/04/197720.html