网站建设项目补充协议,石墨网站开发,天津平台网站建设方案,英文网站建设公司 杭州1 简介 前面系列文章对libevent源码的主体结构#xff0c;从reactor框架实现#xff0c;到evbuffer和bufferevent实现原理#xff0c;及libevent的例子进行了剖析#xff0c;自此#xff0c;我们便可基于libevent开发app了。 从本文开始#xff0c;主要来介绍下libevent源…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的组织和管理基本都可以用以上基本数据结构来组织小跟堆将另起一文来加以介绍。
