libevent 源碼淺析 (二)：定時器實現——最小堆優先級隊列完整解析

定時器核心資料結構：min_heap

libevent 使用最小堆實現定時器優先級隊列，確保取出最早超時事件為 O(1)，插入/刪除為 O(log n)。核心結構定義於 min_heap.c：

typedef struct min_heap {
    struct event **p;   // 動態陣列，堆節點指標
    unsigned n;         // 當前元素數量
    unsigned a;         // 陣列配置容量
} min_heap_t;

每個 event 結構包含 min_heap_idx 記錄在堆中的索引，支援 O(1) 定位與刪除。

關鍵操作原始碼解析

1. 容量擴充：min_heap_reserve()

int min_heap_reserve(min_heap_t* s, unsigned n) {
    if (s->a < n) {
        unsigned a = s->a ? s->a * 2 : 8;  // 指數增長，初始 8
        if (a < n) a = n;
        struct event **p = (struct event**)realloc(s->p, a * sizeof *p);
        if (!p) return -1;
        s->p = p;
        s->a = a;
    }
    return 0;
}

採用倍增策略 (×2) 減少重新配置次數，平衡記憶體與效能。

2. 插入定時器：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;
    // 向上調整：若父節點超時時間較大，則下移父節點
    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;
    }
    (s->p[hole_index] = e)->min_heap_idx = hole_index;
}

新元素置於陣列末尾，向上比較父節點 (索引 (i-1)/2)，維持最小堆性質：父節點超時時間 ≤ 子節點。min_heap_elem_greater 比較 ev_timeout。

3. 取出/刪除最小元素：min_heap_shift_down_()

void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e) {
    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);  // 最後微調
}

取出根節點 (最早超時) 後，將最後一個元素移至根節點，向下比較兩子節點較小者，維持堆性質。最後呼叫 shift_up 確保精確定位。

定時器完整生命週期

1. event_add()：檢測 tv != NULL 且未在定時器隊列，呼叫 min_heap_reserve 確保容量，計算絕對超時時間 ev_timeout = now + tv，呼叫 event_queue_insert(base, ev, EVLIST_TIMEOUT) → min_heap_push → shift_up。
2. event_base_loop()：呼叫 timeout_next 取堆頂元素計算剩餘時間傳給 dispatch。
3. timeout_process()：dispatch 返回後遍歷堆頂，若 ev_timeout <= now 則 event_del(ev) (含 min_heap_erase → shift_down) 並 event_active(ev, EV_TIMEOUT, 1) 加入活躍隊列。
4. event_del()：若事件在定時器隊列 (EVLIST_TIMEOUT)，呼叫 min_heap_erase 從堆移除。

設計評析

• 優點：演算法標準、複雜度最優、程式碼緊湊、支援動態增刪、單執行緒無鎖。
• 缺點：min_heap_shift_down_ 邏輯較繁瑣 (手動計算子節點索引)、缺乏封裝、realloc 可能導致指標失效 (但 libevent 單執行緒且不持有外部指標)、程式碼風格較老舊 (C89 風格、巨集多)。
• 適用場景：中小規模定時器 (數萬以內)、單執行緒事件循環、需精確超時控制的網路伺服器。

若需更高效能或支援取消任意定時器、批次操作，可考慮 Timer Wheel (時間輪) 或 Hierarchical Timer Wheel (分層時間輪) 結構，但最小堆在通用場景下表現優異且實作簡單。