在libevent中定時器的實現是通過基於最小堆的優先級隊列來實現的。
對於這兩個數據結構比較陌生的可以去翻算法導論的6.5節。
主要的源碼都在min_heap.c中。
我們先來看主要的數據結構：
typedef struct min_heap
{
struct event** p;
unsigned n, a;
} min_heap_t;
在這個數據結構中 p也就是整個優先級隊列，而這個優先級隊列的每個節點都是一個struct *event.n表示這個隊列的元素個數。a表示這個隊列的大小.
接下來來看幾個主要的方法：
min_heap_reserve調整隊列的大小。
int min_heap_reserve(min_heap_t* s, unsigned n)
{
if(s->a < n)
{
struct event** p;
///這裡可以看到當需要擴大隊列的空間時，每次都是以8的倍數進行擴展
unsigned a = s->a ? s->a * 2 : 8;
if(a < n)
a = n;
///擴大隊列的空間
if(!(p = (struct event**)realloc(s->p, a * sizeof *p)))
return -1;
s->p = p;
s->a = a;
}
return 0;
}
min_heap_shift_up_ 插入一個定時器到當前隊列：
void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
{
///首先計算當前插入點的元素的父節點。
unsigned parent = (hole_index - 1) / 2;
///循環處理定時器的位置,首先比較當前的定時器與他的父節點的定時器，如果大於父節點的定時器，則直接跳過循環然後將定時器加入隊列。如果大與父節點的定時器則交換兩個節點的值,然後這裡還有個需要注意的地方就是min_heap_idx這個數據，它表示當前event對象也就是定時器對象在定時器隊列的索引值。
while(hole_index && min_heap_elem_greater(s->p[parent], e))
{
(s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
hole_index = parent;
parent = (hole_index - 1) / 2;
}
///得到定時器應插入的位置hole_index.
(s->p[hole_index] = e)->min_heap_idx = hole_index;
}
min_heap_shift_down_ 取出當前的最短時間的定時器，其實也就是root節點，然後平衡此最小堆。
void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
{
///得到當前節點的右孩子。每次取出root節點之後，傳遞最後一個元素到root節點，然後平衡此最小堆。
unsigned min_child = 2 * (hole_index + 1);
while(min_child <= s->n)
{
min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
if(!(min_heap_elem_greater(e, s->p[min_child])))
break;
(s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
hole_index = min_child;
min_child = 2 * (hole_index + 1);
}
min_heap_shift_up_(s, hole_index, e);
}
PS:其實只要對最小堆和優先級隊列了解的話，這個定時器的實現很簡單的說。。不過libevent的算法實現有些丑陋罷了。。
