本文主要研究libevent中用来存储事件的两个结构体。
尾队列
具体定义位于queue.h中。
#define TAILQ_HEAD(name, type) \ struct name { \ struct type *tqh_first; /* first element */ \ struct type **tqh_last; /* addr of last next element */ \ } #define TAILQ_ENTRY(type) \ struct { \ struct type *tqe_next; /* next element */ \ struct type **tqe_prev; /* address of previous next element */ \ } #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) #define TAILQ_FIRST(head) ((head)->tqh_first) #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) #define TAILQ_INIT(head) do { \ TAILQ_FIRST((head)) = NULL; \ (head)->tqh_last = &TAILQ_FIRST((head)); \ } while (0) #define TAILQ_INSERT_TAIL(head, elm, field) do { \ TAILQ_NEXT((elm), field) = NULL; \ (elm)->field.tqe_prev = (head)->tqh_last; \ *(head)->tqh_last = (elm); \ (head)->tqh_last = &TAILQ_NEXT((elm), field); \ } while (0) #define TAILQ_INSERT_HEAD(head, elm, field) do { \ if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ TAILQ_FIRST((head))->field.tqe_prev = \ &TAILQ_NEXT((elm), field); \ else \ (head)->tqh_last = &TAILQ_NEXT((elm), field); \ TAILQ_FIRST((head)) = (elm); \ (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ } while (0) #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ TAILQ_NEXT((elm), field)->field.tqe_prev = \ &TAILQ_NEXT((elm), field); \ else { \ (head)->tqh_last = &TAILQ_NEXT((elm), field); \ } \ TAILQ_NEXT((listelm), field) = (elm); \ (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ } while (0) #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ TAILQ_NEXT((elm), field) = (listelm); \ *(listelm)->field.tqe_prev = (elm); \ (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ } while (0) #define TAILQ_REMOVE(head, elm, field) do { \ if ((TAILQ_NEXT((elm), field)) != NULL) \ TAILQ_NEXT((elm), field)->field.tqe_prev = \ (elm)->field.tqe_prev; \ else { \ (head)->tqh_last = (elm)->field.tqe_prev; \ } \ *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ } while (0)
从定义可以看出，尾队列是一个双向链表，具体表现为：
一个小DEMO:
#include <stdio.h> #include <stdlib.h> #include <sys/queue.h> #define LIST_SIZE 5 // 声明头结点 TAILQ_HEAD(event_list, event); // 声明元素结点 struct event { int value; TAILQ_ENTRY(event) field; }; int main(int argc, char **argv) { event_list *list = (event_list*)malloc(sizeof(event_list)); TAILQ_INIT(list); event *item; for (int i = 0; i < LIST_SIZE; i++) { item = (event*)malloc(sizeof(event)); item->value = i; item->field.tqe_next = NULL; item->field.tqe_prev = NULL; TAILQ_INSERT_TAIL(list, item, field); } printf("当前list: "); for (item = list->tqh_first; item; item = item->field.tqe_next) { printf("%d ", item->value); } printf("\n"); event **test = list->tqh_first->field.tqe_prev; if (test == &list->tqh_first) { printf("guess right\n"); } printf("尾部插入结点: 10\n"); item = (event*)malloc(sizeof(event)); item->value = 10; item->field.tqe_next = NULL; item->field.tqe_prev = NULL; TAILQ_INSERT_TAIL(list, item, field); printf("当前list: "); for (item = list->tqh_first; item; item = item->field.tqe_next) { printf("%d ", item->value); } printf("\n"); printf("头部插入结点: 20\n"); item = (event*)malloc(sizeof(event)); item->value = 20; item->field.tqe_next = NULL; item->field.tqe_prev = NULL; TAILQ_INSERT_HEAD(list, item, field); printf("当前list: "); for (item = list->tqh_first; item; item = item->field.tqe_next) { printf("%d ", item->value); } printf("\n"); printf("在值为3的结点之后插入结点: 30\n"); for (item = list->tqh_first; item; item = item->field.tqe_next) { if (item->value == 3) { event *new_item = (event*)malloc(sizeof(event)); new_item->value = 30; new_item->field.tqe_next = NULL; new_item->field.tqe_prev = NULL; TAILQ_INSERT_AFTER(list, item, new_item, field); } } printf("当前list: "); for (item = list->tqh_first; item; item = item->field.tqe_next) { printf("%d ", item->value); } printf("\n"); printf("在值为1的结点之前插入结点: 40\n"); for (item = list->tqh_first; item; item = item->field.tqe_next) { if (item->value == 1) { event *new_item = (event*)malloc(sizeof(event)); new_item->value = 40; new_item->field.tqe_next = NULL; new_item->field.tqe_prev = NULL; TAILQ_INSERT_BEFORE(item, new_item, field); } } printf("当前list: "); for (item = list->tqh_first; item; item = item->field.tqe_next) { printf("%d ", item->value); } printf("\n"); printf("删除值为3的结点\n"); for (item = list->tqh_first; item; item = item->field.tqe_next) { if (item->value == 3) { TAILQ_REMOVE(list, item, field); } } printf("当前list: "); for (item = list->tqh_first; item; item = item->field.tqe_next) { printf("%d ", item->value); } printf("\n"); printf("Done\n"); }
最小堆
typedef struct min_heap { struct event** p; // 指向event*指针数组 unsigned n, a; // a表示堆的大小，n表示堆中元素个数 } min_heap_t;
void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; } void min_heap_elem_init(struct event* e) { e->ev_timeout_pos.min_heap_idx = -1; } unsigned min_heap_size(min_heap_t* s) { return s->n; }
参考资料: