libevent-1.4.12-stable, libevent-2.0.4-alpha
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 的关系。
:-) 基本数据便是如此这般,剩下的代码也就比较简单了。
评论