基础数据结构

Libevent 的高效不仅源于 epoll，更源于其精心优化的基础数据结构。为了追求极致性能和零依赖，Libevent 并没有使用 C++ STL，而是自己实现（或借用）了一套 C 语言的数据结构。

1. 尾队列 (TAILQ)

在 Libevent 源码中，你会到处看到 TAILQ_ENTRY, TAILQ_HEAD 等宏。这些宏来自 BSD 系统的 sys/queue.h。

1.1. 为什么不用标准链表？

C 语言没有标准链表库。sys/queue.h 通过宏定义，允许将链表节点直接嵌入到用户结构体中，避免了额外的内存分配（相比于 std::list 每个节点都要 malloc）。

1.2. 宏解析

#define TAILQ_ENTRY(type)                                               \
struct {                                                                \
    struct type *tqe_next;  /* next element */                          \
    struct type **tqe_prev; /* address of previous next element */      \
}

struct event {
    // ...
    TAILQ_ENTRY(event) ev_active_next; // 嵌入到 event 结构体中
    // ...
};

这是一个双向链表。tqe_prev 指向的是“前一个节点的 next 指针的地址”，这种设计使得删除节点时无需检查是否是头节点，非常优雅。

2. 哈希表 (Hash Table)

Libevent 在 ht-internal.h 中实现了一个通用的哈希表，主要用于 event_io_map（在不支持 epoll 的系统上，如 Windows select，将 fd 映射到 event）。

2.1. 实现特点

链地址法 (Chaining): 解决哈希冲突。
负载因子控制: 当元素数量超过桶数量的 0.5 倍时，自动扩容。
素数扩容: 桶的数量总是保持为素数，减少冲突概率。

3. 最小堆 (Min-Heap)

定时器的管理是 Reactor 的核心功能之一。Libevent 使用最小堆 (min_heap-internal.h) 来管理所有超时事件。

3.1. 为什么是最小堆？

需求: 我们总是需要快速找到“最近要触发”的那个定时器（计算 epoll_wait 的超时时间）。
复杂度:
- 查找最小值: O(1)。
- 插入/删除: O(log N)。
对比: 红黑树也是 O(log N)，但最小堆基于数组实现，缓存局部性（Cache Locality）更好，且实现更简单。

3.2. 数组实现

Libevent 的最小堆是一个动态数组（struct event**）。 * p[0] 是堆顶（最小值）。 * 节点 i 的左子节点是 2*i + 1，右子节点是 2*i + 2。 * struct event 中有一个 min_heap_idx 字段，记录了该事件在堆数组中的索引，使得删除操作也能达到 O(log N)（无需遍历查找）。

4. 总结

Libevent 的数据结构选择体现了典型的 C 语言工程哲学： 1. 侵入式设计 (Intrusive): 将链表节点、堆索引直接嵌入业务结构体，减少内存碎片和分配开销。 2. 宏编程: 利用宏实现泛型（在 C++ 模板出现之前的主流做法）。 3. 特定优化: 针对定时器场景选择最小堆，针对 fd 映射选择哈希表。

这些底层细节的打磨，共同铸就了 Libevent 的高性能。

上一篇: 02-data/bufferevent.md - Bufferevent 原理与实战 下一篇: 03-events/timer.md - 定时器管理

返回 Libevent 专题索引

目录