libevent源码剖析-evconnlistener-CSDN博客

libevent源码剖析-event_libevent 任务周期调度-CSDN博客

libevent源码剖析-开篇-CSDN博客

libevent源码剖析之http-CSDN博客

libevent源码剖析之bufferevent_libevent 发送数据-CSDN博客

libevent源码剖析之evbuffer-CSDN博客

libevent源码剖析之reactor-CSDN博客

libevent源码剖析之iocp_iocp 源码-CSDN博客

libevent源码剖析之epoll_libevent中 epoll 处理过程-CSDN博客

libevent源码剖析之poll-CSDN博客

libevent源码剖析之select-CSDN博客

    前面系列文章对libevent源码的主体结构，从reactor框架实现，到evbuffer和bufferevent实现原理，及libevent的例子进行了剖析，自此，我们便可基于libevent开发app了。

    从本文开始，主要来介绍下libevent源码的枝叶部分，包括基本数据结构、C开发技巧、工具函数等。

    单链表相关操作都在libevent源码根目录compat/sys/queue.h文件下。这里简要介绍下单链表原理及其操作。

    单链表是一种链式存储的数据结构，每个节点包含数据域和指向下一个节点的指针。下面是单链表的主要优缺点：

优点

• 动态内存分配：单链表的节点可以在需要时动态分配和释放，不需要提前分配固定大小的内存，适合需要频繁插入和删除的情况。

• 插入和删除操作效率高：在已知位置进行插入和删除操作只需更改指针即可，时间复杂度为 O(1)。相比数组无需移动其他元素，因此适合频繁插入、删除操作的场景。

• 节省内存：单链表只需存储数据和一个指向下个节点的指针，比双向链表节省内存开销，适用于内存敏感的应用。

• 便于扩展：由于链表不需要连续的内存空间，所以扩展链表时只需增加节点，不会涉及整体内存的重新分配和复制操作。

缺点

• 随机访问性能差：单链表不支持随机访问，要访问某个特定位置的节点，必须从头开始逐个遍历，时间复杂度为 O(n)，在访问频繁的场景性能较低。

• 额外的存储开销：每个节点需要存储一个指针用于链接下一个节点，若数据较小或节点较多，指针的额外存储开销会显得较大。

• 不便于反向遍历：单链表只能从头到尾顺序遍历，无法反向遍；如果需要反向遍历的功能，需要转换成双向链表或借助栈等辅助数据结构。

• 链表操作的指针复杂性：在操作链表（如插入、删除）时，指针的使用容易导致错误，例如指针丢失、空指针访问等，增加了开发和调试的难度。

    单链表适合数据量动态变化、需要频繁插入和删除、但不要求随机访问的场景。

单链表结构图 

2.1.1 定义

    C单链表结构定义如下：

2.1.2 访问方法

    libevent通过宏定义来访问单链表的数据成员及遍历：

2.1.3 操作函数 

    libevent实现的单链表操作主要有：初始化、中间插入、头部插入、尾部插入、头部移除：

    以上是SLIST单链表所有源码实现，相对简单，不赘述。

    在libevent中，LIS链表是一种双向链表结构，其每个节点包含一个指向前后节点的指针。和单向链表不同，双向链表一般是用来表示事件的多重组织方式，即不同事件类型和优先级的事件链。下面是双向链表的优缺点：

优点

• 层级化的事件管理：双向链表可以将事件按优先级、事件类型等不同维度进行分层组织，方便事件循环时按需分配处理，尤其在多优先级事件的场景中非常有效。

• 便于按优先级调度：通过将高优先级事件和低优先级事件划分到不同链表层级中，处理事件时可以优先处理高优先级链表上的事件，便于实现调度控制，保证关键事件的及时性。

• 插入、删除操作简便：双向链表特性使得在任意位置插入或删除节点非常高效，只需调整前后指针，时间复杂度为 O(1)，适合频繁操作。

• 事件遍历灵活：可以在多层链表中进行迭代，适合多种情况下的事件遍历、优先级切换等。对于复杂事件处理逻辑，可以快速遍历特定层级事件，提升事件处理效率。

缺点

• 内存消耗较大：每个节点需要存储两个指针（指向前后节点），如果链表层级很多且节点较多，内存开销会明显增大。

• 操作复杂性增加：双向链表的多层级设计，尤其是在事件分层组织、删除和调整优先级时，对开发者理解和调试的要求较高，可能导致复杂的指针操作错误。

• 访问深层节点效率降低：如果事件在较低优先级的层级，处理时需要逐层遍历链表才能访问到这些事件，效率相对较低，适合优先级较为集中的场景。

• 对随机访问支持差：链表结构本身不支持随机访问，查找特定事件或位置的节点时需要顺序遍历，在大规模节点的情况下效率较低。

双向链表结构图 

2.2.1 定义

 2.2.2 访问方法 

     2.2.3 操作函数

    libevent中的简单队列是一个由单链表来实现的。simple queue 是一种简单的队列数据结构，它通常用于按顺序存储和访问元素。队列是一种先进先出（FIFO, First In First Out）结构，元素总是从队尾插入，从队首删除。下面是 simple queue 的特点、基本操作和优缺点。

特点

• FIFO（先进先出）：最先进入队列的元素会最先被处理。
• 单向操作：通常只允许在队尾插入元素、在队首删除元素，保持队列有序性。
• 动态增长：可以在需要时动态添加元素，内存使用通常灵活。

优点

• 操作简单：只需操作队尾和队首，插入和删除的复杂度为 O(1)。
• 内存效率：链表实现的队列可以根据需要动态调整大小，适合存储不确定数量的数据。
• 无锁并发：在一些并发场景中，可以通过特定设计使队列支持无锁操作，提高并发访问的效率。

缺点

• 随机访问效率低：只能按顺序访问元素，无法高效地进行随机访问。
• 可能有内存开销：链表实现的队列会在每个节点上存储额外的指针信息，在大量节点时会增加内存使用。
• 阻塞问题：在生产者-消费者场景中，如果生产或消费速度不匹配，可能会导致队列过长或过短，需额外处理队列满或空的情况。 

 简单队列结构图

    2.3.1定义

    2.3.2 访问方法

    2.3.3 操作函数

    TAILQ 是一种双向链表队列，广泛用于 BSD 系统和 libevent 库中。它支持从队列头部或尾部高效地插入、删除和访问元素，便于实现先进先出（FIFO）队列、双端队列等多种数据结构。TAILQ 的设计特点主要在于它使用双向链表维护队列顺序，尾部始终指向最后一个元素，因此插入和删除操作效率较高。

    相关操作在include/event2/event_struct.h文件下，如果对应平台有此<sys/queue.h>文件相应实现，则可直接用。

优点

• 双端操作高效：TAILQ 支持头部和尾部的高效插入和删除操作，时间复杂度均为 O(1)。
• 灵活性高：支持在任意位置插入和删除，适合实现各种类型的队列、链表、双端队列等。
• 结构简洁：TAILQ 数据结构相对简单，内存开销较低，适合内核、系统编程等低资源场景。

缺点

• 访问性能差：TAILQ 不支持随机访问，访问特定位置需要顺序遍历，效率较低。
• 指针操作复杂：TAILQ 的双向指针结构在操作中容易出现指针悬挂、泄漏等错误，增加开发难度。

 尾队列结构图

    2.4.1 定义

    2.4.2 方法访问

    2.4.3 操作函数

    Circular Queue（循环队列）是一种队列数据结构，它将队列逻辑上视为“环形结构”，通过在固定大小的数组中实现循环，来避免普通线性队列出现的“假溢出”问题。循环队列在系统编程和实时系统中常用，如 CPU 调度、任务管理等。

优点

• 内存效率高：循环队列的最大优势在于通过循环重用数组空间，避免了普通线性队列“假溢出”的问题。
• 固定大小：在实时和嵌入式系统中，循环队列的固定数组大小有助于内存管理。

缺点

• 容量限制：固定数组大小的循环队列有容量上限，超出限制会导致队列溢出。
• 指针计算复杂：由于指针的循环移动，操作比单纯的线性队列复杂，可能会产生边界问题。

 环形队列结构图

2.4.1 定义

 2.4.2 访问方法

2.4.3 操作函数

优点

• 高效查询和插入：哈希表的设计使其查询和插入的平均时间复杂度接近 O(1)，在管理大量事件（如定时器事件）时非常高效。

• 动态扩展：libevent 的哈希表可以根据负载因子动态扩展，降低碰撞率并保持性能。

• 空间利用率高：哈希表通过散列函数分布元素，避免了链表或树结构的空间浪费，适合事件数量较多的场景。

缺点

• 内存占用波动：在动态扩展过程中，哈希表需要重新分配内存，这可能导致内存使用不稳定。

• 碰撞处理开销：尽管有较低的碰撞概率，但在高负载情况下，链表长度可能增加，导致操作复杂度退化为 O(n)。

• 线程不安全：libevent 中的哈希表设计在多线程环境下不安全，使用时需要额外的锁机制来避免竞争。

    libevent在对IO事件和signal事件进行组织管理的时候，采用的哈希表，以IO事件为例，fd为哈希表的桶，哈希槽为evmap_io的双向链表，详见下图：

IO事件哈希表 

libevent在对signal事件的组织管理方式，与IO事件基本是一样的，以signal为桶，哈希槽为evmap_signal的双向链表，详见下图：

signal事件结构图 

• 本文主要对libevent的基本数据结构进行介绍，包括单链表、双向链表、简单队列、尾队列、圆形队列以及哈希表的实现原理；
• 除了timer事件使用了小跟堆以外，libevent对event的组织和管理基本都可以用以上基本数据结构来组织，小根堆将另起一文来加以介绍。