libevent timer 的原理 (min-heap)

libevent 中，用最小堆(min-heap)来管理所有 timer。

基础知识
min-heap，就是 child node value 一定小于 parent node value 的 binary-tree。因此，获取 min value，只需要 pop root node 即可。

算法实现 (min_heap.h)
对于 libevent，root node 就是最近即将触发的 timer event。node value 就是 timer 触发的时间(秒)。

// p - (struct event *) array
// n - event array count (point to first empty slot)
// a - event array size
typedef struct min_heap
{
struct event** p;
unsigned n, a;
} min_heap_t

对于上面的图，n = 9, a = 12，p[] 中存储的值如下：
index 0 1 2 3 4 5 6 7 8 9 10 11
value 1 2 3 17 19 36 7 25 100 ? ? ?
而 child/parent 可以构成 parent_index = (child_index - 1) / 2 的关系。

:-) 基本数据便是如此这般，剩下的代码也就比较简单了。

举个例子，向一个小根堆3, 5, 8, 7, 12中插入新元素2，使用第一中典型的代码逻辑，其调整过程如下图所示：
heap insert

使用libevent中的堆调整逻辑，调整过程如下图所示：

对于删除和元素修改操作，也遵从相同的逻辑，就不再罗嗦了。

libevent timer 的原理 (min-heap)

浏览过的版块