网页版千图网东莞seo建站排名
1 简介
前面系列文章对libevent源码的主体结构,从reactor框架实现,到evbuffer和bufferevent实现原理,及libevent的例子进行了剖析,自此,我们便可基于libevent开发app了。
从本文开始,主要来介绍下libevent源码的枝叶部分,包括基本数据结构、C开发技巧、工具函数等。
2 基本数据结构
2.1 单链表
单链表相关操作都在libevent源码根目录compat/sys/queue.h文件下。这里简要介绍下单链表原理及其操作。
单链表是一种链式存储的数据结构,每个节点包含数据域和指向下一个节点的指针。下面是单链表的主要优缺点:
优点
动态内存分配:单链表的节点可以在需要时动态分配和释放,不需要提前分配固定大小的内存,适合需要频繁插入和删除的情况。
插入和删除操作效率高:在已知位置进行插入和删除操作只需更改指针即可,时间复杂度为 O(1)。相比数组无需移动其他元素,因此适合频繁插入、删除操作的场景。
节省内存:单链表只需存储数据和一个指向下个节点的指针,比双向链表节省内存开销,适用于内存敏感的应用。
便于扩展:由于链表不需要连续的内存空间,所以扩展链表时只需增加节点,不会涉及整体内存的重新分配和复制操作。
缺点
随机访问性能差:单链表不支持随机访问,要访问某个特定位置的节点,必须从头开始逐个遍历,时间复杂度为 O(n),在访问频繁的场景性能较低。
额外的存储开销:每个节点需要存储一个指针用于链接下一个节点,若数据较小或节点较多,指针的额外存储开销会显得较大。
不便于反向遍历:单链表只能从头到尾顺序遍历,无法反向遍;如果需要反向遍历的功能,需要转换成双向链表或借助栈等辅助数据结构。
链表操作的指针复杂性:在操作链表(如插入、删除)时,指针的使用容易导致错误,例如指针丢失、空指针访问等,增加了开发和调试的难度。
单链表适合数据量动态变化、需要频繁插入和删除、但不要求随机访问的场景。
单链表结构图
2.1.1 定义
C单链表结构定义如下:
/** Singly-linked List definitions.*/
#define SLIST_HEAD(name, type) \
struct name { \struct type *slh_first; /* first element */ \
}#define SLIST_HEAD_INITIALIZER(head) \{ NULL }#ifndef _WIN32
#define SLIST_ENTRY(type) \
struct { \struct type *sle_next; /* next element */ \
}
#endif
2.1.2 访问方法
libevent通过宏定义来访问单链表的数据成员及遍历:
/** Singly-linked List access methods.*/
#define SLIST_FIRST(head) ((head)->slh_first)
#define SLIST_END(head) NULL
#define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)#define SLIST_FOREACH(var, head, field) \for((var) = SLIST_FIRST(head); \(var) != SLIST_END(head); \(var) = SLIST_NEXT(var, field))
2.1.3 操作函数
libevent实现的单链表操作主要有:初始化、中间插入、头部插入、尾部插入、头部移除:
/** Singly-linked List functions.*/
#define SLIST_INIT(head) { \SLIST_FIRST(head) = SLIST_END(head); \
}#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \(elm)->field.sle_next = (slistelm)->field.sle_next; \(slistelm)->field.sle_next = (elm); \
} while (0)#define SLIST_INSERT_HEAD(head, elm, field) do { \(elm)->field.sle_next = (head)->slh_first; \(head)->slh_first = (elm); \
} while (0)#define SLIST_REMOVE_HEAD(head, field) do { \(head)->slh_first = (head)->slh_first->field.sle_next; \
} while (0)
以上是SLIST单链表所有源码实现,相对简单,不赘述。
2.2 双向链表
在libevent中,LIS链表是一种双向链表结构,其每个节点包含一个指向前后节点的指针。和单向链表不同,双向链表一般是用来表示事件的多重组织方式,即不同事件类型和优先级的事件链。下面是双向链表的优缺点:
优点
层级化的事件管理:双向链表可以将事件按优先级、事件类型等不同维度进行分层组织,方便事件循环时按需分配处理,尤其在多优先级事件的场景中非常有效。
便于按优先级调度:通过将高优先级事件和低优先级事件划分到不同链表层级中,处理事件时可以优先处理高优先级链表上的事件,便于实现调度控制,保证关键事件的及时性。
插入、删除操作简便:双向链表特性使得在任意位置插入或删除节点非常高效,只需调整前后指针,时间复杂度为 O(1),适合频繁操作。
事件遍历灵活:可以在多层链表中进行迭代,适合多种情况下的事件遍历、优先级切换等。对于复杂事件处理逻辑,可以快速遍历特定层级事件,提升事件处理效率。
缺点
内存消耗较大:每个节点需要存储两个指针(指向前后节点),如果链表层级很多且节点较多,内存开销会明显增大。
操作复杂性增加:双向链表的多层级设计,尤其是在事件分层组织、删除和调整优先级时,对开发者理解和调试的要求较高,可能导致复杂的指针操作错误。
访问深层节点效率降低:如果事件在较低优先级的层级,处理时需要逐层遍历链表才能访问到这些事件,效率相对较低,适合优先级较为集中的场景。
对随机访问支持差:链表结构本身不支持随机访问,查找特定事件或位置的节点时需要顺序遍历,在大规模节点的情况下效率较低。
双向链表结构图
2.2.1 定义
/** List definitions.*/
#define LIST_HEAD(name, type) \
struct name { \struct type *lh_first; /* first element */ \
}#define LIST_HEAD_INITIALIZER(head) \{ NULL }#define LIST_ENTRY(type) \
struct { \struct type *le_next; /* next element */ \struct type **le_prev; /* address of previous next element */ \
}
2.2.2 访问方法
/** List access methods*/
#define LIST_FIRST(head) ((head)->lh_first)
#define LIST_END(head) NULL
#define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
#define LIST_NEXT(elm, field) ((elm)->field.le_next)#define LIST_FOREACH(var, head, field) \for((var) = LIST_FIRST(head); \(var)!= LIST_END(head); \(var) = LIST_NEXT(var, field))
2.2.3 操作函数
/** List functions.*/
#define LIST_INIT(head) do { \LIST_FIRST(head) = LIST_END(head); \
} while (0)#define LIST_INSERT_AFTER(listelm, elm, field) do { \if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \(listelm)->field.le_next->field.le_prev = \&(elm)->field.le_next; \(listelm)->field.le_next = (elm); \(elm)->field.le_prev = &(listelm)->field.le_next; \
} while (0)#define LIST_INSERT_BEFORE(listelm, elm, field) do { \(elm)->field.le_prev = (listelm)->field.le_prev; \(elm)->field.le_next = (listelm); \*(listelm)->field.le_prev = (elm); \(listelm)->field.le_prev = &(elm)->field.le_next; \
} while (0)#define LIST_INSERT_HEAD(head, elm, field) do { \if (((elm)->field.le_next = (head)->lh_first) != NULL) \(head)->lh_first->field.le_prev = &(elm)->field.le_next;\(head)->lh_first = (elm); \(elm)->field.le_prev = &(head)->lh_first; \
} while (0)#define LIST_REMOVE(elm, field) do { \if ((elm)->field.le_next != NULL) \(elm)->field.le_next->field.le_prev = \(elm)->field.le_prev; \*(elm)->field.le_prev = (elm)->field.le_next; \
} while (0)#define LIST_REPLACE(elm, elm2, field) do { \if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \(elm2)->field.le_next->field.le_prev = \&(elm2)->field.le_next; \(elm2)->field.le_prev = (elm)->field.le_prev; \*(elm2)->field.le_prev = (elm2); \
} while (0)
2.3 简单队列
libevent中的简单队列是一个由单链表来实现的。simple queue 是一种简单的队列数据结构,它通常用于按顺序存储和访问元素。队列是一种先进先出(FIFO, First In First Out)结构,元素总是从队尾插入,从队首删除。下面是 simple queue 的特点、基本操作和优缺点。
特点
- FIFO(先进先出):最先进入队列的元素会最先被处理。
- 单向操作:通常只允许在队尾插入元素、在队首删除元素,保持队列有序性。
- 动态增长:可以在需要时动态添加元素,内存使用通常灵活。
优点
- 操作简单:只需操作队尾和队首,插入和删除的复杂度为 O(1)。
- 内存效率:链表实现的队列可以根据需要动态调整大小,适合存储不确定数量的数据。
- 无锁并发:在一些并发场景中,可以通过特定设计使队列支持无锁操作,提高并发访问的效率。
缺点
- 随机访问效率低:只能按顺序访问元素,无法高效地进行随机访问。
- 可能有内存开销:链表实现的队列会在每个节点上存储额外的指针信息,在大量节点时会增加内存使用。
- 阻塞问题:在生产者-消费者场景中,如果生产或消费速度不匹配,可能会导致队列过长或过短,需额外处理队列满或空的情况。
简单队列结构图
2.3.1定义
/** Simple queue definitions.*/
#define SIMPLEQ_HEAD(name, type) \
struct name { \struct type *sqh_first; /* first element */ \struct type **sqh_last; /* addr of last next element */ \
}#define SIMPLEQ_HEAD_INITIALIZER(head) \{ NULL, &(head).sqh_first }#define SIMPLEQ_ENTRY(type) \
struct { \struct type *sqe_next; /* next element */ \
}
2.3.2 访问方法
/** Simple queue access methods.*/
#define SIMPLEQ_FIRST(head) ((head)->sqh_first)
#define SIMPLEQ_END(head) NULL
#define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)#define SIMPLEQ_FOREACH(var, head, field) \for((var) = SIMPLEQ_FIRST(head); \(var) != SIMPLEQ_END(head); \(var) = SIMPLEQ_NEXT(var, field))
2.3.3 操作函数
/** Simple queue functions.*/
#define SIMPLEQ_INIT(head) do { \(head)->sqh_first = NULL; \(head)->sqh_last = &(head)->sqh_first; \
} while (0)#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \(head)->sqh_last = &(elm)->field.sqe_next; \(head)->sqh_first = (elm); \
} while (0)#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \(elm)->field.sqe_next = NULL; \*(head)->sqh_last = (elm); \(head)->sqh_last = &(elm)->field.sqe_next; \
} while (0)#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\(head)->sqh_last = &(elm)->field.sqe_next; \(listelm)->field.sqe_next = (elm); \
} while (0)#define SIMPLEQ_REMOVE_HEAD(head, elm, field) do { \if (((head)->sqh_first = (elm)->field.sqe_next) == NULL) \(head)->sqh_last = &(head)->sqh_first; \
} while (0)
2.4 尾队列
TAILQ 是一种双向链表队列,广泛用于 BSD 系统和 libevent 库中。它支持从队列头部或尾部高效地插入、删除和访问元素,便于实现先进先出(FIFO)队列、双端队列等多种数据结构。TAILQ 的设计特点主要在于它使用双向链表维护队列顺序,尾部始终指向最后一个元素,因此插入和删除操作效率较高。
相关操作在include/event2/event_struct.h文件下,如果对应平台有此<sys/queue.h>文件相应实现,则可直接用。
优点
- 双端操作高效:TAILQ 支持头部和尾部的高效插入和删除操作,时间复杂度均为 O(1)。
- 灵活性高:支持在任意位置插入和删除,适合实现各种类型的队列、链表、双端队列等。
- 结构简洁:TAILQ 数据结构相对简单,内存开销较低,适合内核、系统编程等低资源场景。
缺点
- 访问性能差:TAILQ 不支持随机访问,访问特定位置需要顺序遍历,效率较低。
- 指针操作复杂:TAILQ 的双向指针结构在操作中容易出现指针悬挂、泄漏等错误,增加开发难度。
尾队列结构图
2.4.1 定义
/** Tail queue definitions.*/
#define TAILQ_HEAD(name, type) \
struct name { \struct type *tqh_first; /* first element */ \struct type **tqh_last; /* addr of last next element */ \
}#define TAILQ_HEAD_INITIALIZER(head) \{ NULL, &(head).tqh_first }#define TAILQ_ENTRY(type) \
struct { \struct type *tqe_next; /* next element */ \struct type **tqe_prev; /* address of previous next element */ \
}
2.4.2 方法访问
/** tail queue access methods*/
#define TAILQ_FIRST(head) ((head)->tqh_first)
#define TAILQ_END(head) NULL
#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
#define TAILQ_LAST(head, headname) \(*(((struct headname *)((head)->tqh_last))->tqh_last))
/* XXX */
#define TAILQ_PREV(elm, headname, field) \(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
#define TAILQ_EMPTY(head) \(TAILQ_FIRST(head) == TAILQ_END(head))#define TAILQ_FOREACH(var, head, field) \for((var) = TAILQ_FIRST(head); \(var) != TAILQ_END(head); \(var) = TAILQ_NEXT(var, field))#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \for((var) = TAILQ_LAST(head, headname); \(var) != TAILQ_END(head); \(var) = TAILQ_PREV(var, headname, field))
2.4.3 操作函数
/** Tail queue functions.*/
#define TAILQ_INIT(head) do { \(head)->tqh_first = NULL; \(head)->tqh_last = &(head)->tqh_first; \
} while (0)#define TAILQ_INSERT_HEAD(head, elm, field) do { \if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \(head)->tqh_first->field.tqe_prev = \&(elm)->field.tqe_next; \else \(head)->tqh_last = &(elm)->field.tqe_next; \(head)->tqh_first = (elm); \(elm)->field.tqe_prev = &(head)->tqh_first; \
} while (0)#define TAILQ_INSERT_TAIL(head, elm, field) do { \(elm)->field.tqe_next = NULL; \(elm)->field.tqe_prev = (head)->tqh_last; \*(head)->tqh_last = (elm); \(head)->tqh_last = &(elm)->field.tqe_next; \
} while (0)#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\(elm)->field.tqe_next->field.tqe_prev = \&(elm)->field.tqe_next; \else \(head)->tqh_last = &(elm)->field.tqe_next; \(listelm)->field.tqe_next = (elm); \(elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
} while (0)#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \(elm)->field.tqe_prev = (listelm)->field.tqe_prev; \(elm)->field.tqe_next = (listelm); \*(listelm)->field.tqe_prev = (elm); \(listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
} while (0)#define TAILQ_REMOVE(head, elm, field) do { \if (((elm)->field.tqe_next) != NULL) \(elm)->field.tqe_next->field.tqe_prev = \(elm)->field.tqe_prev; \else \(head)->tqh_last = (elm)->field.tqe_prev; \*(elm)->field.tqe_prev = (elm)->field.tqe_next; \
} while (0)#define TAILQ_REPLACE(head, elm, elm2, field) do { \if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \(elm2)->field.tqe_next->field.tqe_prev = \&(elm2)->field.tqe_next; \else \(head)->tqh_last = &(elm2)->field.tqe_next; \(elm2)->field.tqe_prev = (elm)->field.tqe_prev; \*(elm2)->field.tqe_prev = (elm2); \
} while (0)
2.4 圆形队列
Circular Queue(循环队列)是一种队列数据结构,它将队列逻辑上视为“环形结构”,通过在固定大小的数组中实现循环,来避免普通线性队列出现的“假溢出”问题。循环队列在系统编程和实时系统中常用,如 CPU 调度、任务管理等。
优点
- 内存效率高:循环队列的最大优势在于通过循环重用数组空间,避免了普通线性队列“假溢出”的问题。
- 固定大小:在实时和嵌入式系统中,循环队列的固定数组大小有助于内存管理。
缺点
- 容量限制:固定数组大小的循环队列有容量上限,超出限制会导致队列溢出。
- 指针计算复杂:由于指针的循环移动,操作比单纯的线性队列复杂,可能会产生边界问题。
环形队列结构图
2.4.1 定义
/** Circular queue definitions.*/
#define CIRCLEQ_HEAD(name, type) \
struct name { \struct type *cqh_first; /* first element */ \struct type *cqh_last; /* last element */ \
}#define CIRCLEQ_HEAD_INITIALIZER(head) \{ CIRCLEQ_END(&head), CIRCLEQ_END(&head) }#define CIRCLEQ_ENTRY(type) \
struct { \struct type *cqe_next; /* next element */ \struct type *cqe_prev; /* previous element */ \
}
2.4.2 访问方法
/** Circular queue access methods*/
#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
#define CIRCLEQ_LAST(head) ((head)->cqh_last)
#define CIRCLEQ_END(head) ((void *)(head))
#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
#define CIRCLEQ_EMPTY(head) \(CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))#define CIRCLEQ_FOREACH(var, head, field) \for((var) = CIRCLEQ_FIRST(head); \(var) != CIRCLEQ_END(head); \(var) = CIRCLEQ_NEXT(var, field))#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \for((var) = CIRCLEQ_LAST(head); \(var) != CIRCLEQ_END(head); \(var) = CIRCLEQ_PREV(var, fie
2.4.3 操作函数
/** Circular queue functions.*/
#define CIRCLEQ_INIT(head) do { \(head)->cqh_first = CIRCLEQ_END(head); \(head)->cqh_last = CIRCLEQ_END(head); \
} while (0)#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \(elm)->field.cqe_next = (listelm)->field.cqe_next; \(elm)->field.cqe_prev = (listelm); \if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \(head)->cqh_last = (elm); \else \(listelm)->field.cqe_next->field.cqe_prev = (elm); \(listelm)->field.cqe_next = (elm); \
} while (0)#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \(elm)->field.cqe_next = (listelm); \(elm)->field.cqe_prev = (listelm)->field.cqe_prev; \if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \(head)->cqh_first = (elm); \else \(listelm)->field.cqe_prev->field.cqe_next = (elm); \(listelm)->field.cqe_prev = (elm); \
} while (0)#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \(elm)->field.cqe_next = (head)->cqh_first; \(elm)->field.cqe_prev = CIRCLEQ_END(head); \if ((head)->cqh_last == CIRCLEQ_END(head)) \(head)->cqh_last = (elm); \else \(head)->cqh_first->field.cqe_prev = (elm); \(head)->cqh_first = (elm); \
} while (0)#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \(elm)->field.cqe_next = CIRCLEQ_END(head); \(elm)->field.cqe_prev = (head)->cqh_last; \if ((head)->cqh_first == CIRCLEQ_END(head)) \(head)->cqh_first = (elm); \else \(head)->cqh_last->field.cqe_next = (elm); \(head)->cqh_last = (elm); \
} while (0)#define CIRCLEQ_REMOVE(head, elm, field) do { \if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \(head)->cqh_last = (elm)->field.cqe_prev; \else \(elm)->field.cqe_next->field.cqe_prev = \(elm)->field.cqe_prev; \if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \(head)->cqh_first = (elm)->field.cqe_next; \else \(elm)->field.cqe_prev->field.cqe_next = \(elm)->field.cqe_next; \
} while (0)#define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \CIRCLEQ_END(head)) \(head).cqh_last = (elm2); \else \(elm2)->field.cqe_next->field.cqe_prev = (elm2); \if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \CIRCLEQ_END(head)) \(head).cqh_first = (elm2); \else \(elm2)->field.cqe_prev->field.cqe_next = (elm2); \
} while (0)
2.5 哈希表
优点
高效查询和插入:哈希表的设计使其查询和插入的平均时间复杂度接近 O(1),在管理大量事件(如定时器事件)时非常高效。
动态扩展:libevent 的哈希表可以根据负载因子动态扩展,降低碰撞率并保持性能。
空间利用率高:哈希表通过散列函数分布元素,避免了链表或树结构的空间浪费,适合事件数量较多的场景。
缺点
内存占用波动:在动态扩展过程中,哈希表需要重新分配内存,这可能导致内存使用不稳定。
碰撞处理开销:尽管有较低的碰撞概率,但在高负载情况下,链表长度可能增加,导致操作复杂度退化为 O(n)。
线程不安全:libevent 中的哈希表设计在多线程环境下不安全,使用时需要额外的锁机制来避免竞争。
libevent在对IO事件和signal事件进行组织管理的时候,采用的哈希表,以IO事件为例,fd为哈希表的桶,哈希槽为evmap_io的双向链表,详见下图:
IO事件哈希表
libevent在对signal事件的组织管理方式,与IO事件基本是一样的,以signal为桶,哈希槽为evmap_signal的双向链表,详见下图:
signal事件结构图
3 小结
- 本文主要对libevent的基本数据结构进行介绍,包括单链表、双向链表、简单队列、尾队列、圆形队列以及哈希表的实现原理;
- 除了timer事件使用了小跟堆以外,libevent对event的组织和管理基本都可以用以上基本数据结构来组织,小跟堆将另起一文来加以介绍。