XGuru's Blog

2.1 event_base核心事件基類數據結構

      可以看出event_base是整個libevent的核心部分，它由三種結構構成：一個時間堆 (對應EVLIST_TIMEOUT),一個已注冊隊列(對應EVLIST_INSERTE)，一個活躍事件隊列(對應EVLIST_ACTIVE)。

      時間堆采用的是min-Heap最小二叉堆，已注冊隊列和活躍事件隊列采用的都是雙向鏈表。

      已注冊隊列對應事件基中的eventqueue，活躍事件隊列對應的是事件基中的activequeues[ev->ev_pri]結構體數組。其中的ev_pri代表的是事件的優先級，數值越小代表越高的優先級別。

      可以通過調用event_priority_set()函數對其優先級進行設置，默認插入中等優先級(nactivequeues/2 ,即活躍隊列總數除以2)。

2.2 超時隊列（min-Heap最小二叉堆）

      在這里處理超時機制中使用了一個經典的數據結構min-Heap，源碼位于Min_heap.h

libevent從1.4版本之后就開始采用min-Heap來代替RB-Tree。

min-Heap（最小二叉堆）遵循的原則:

1.它是一種完全二叉樹

2.它最小的元素在頂端每個元素都比它的父節點大(或相等)。

插入元素時間復雜度為O(log n)，找出最小值的復雜度僅為O(1)。

libevent實現的min-Heap變量名有點猥瑣。

1typedef struct min_heap
2{
3    struct event** p;
4    unsigned n, a;
5} min_heap_t;
6

p可以理解成存儲事件指針的數組，n表示的是容量，a表示的是當前數。

堆的操作函數里一般e代表事件，s代表被操縱的min-Heap。

這個min-heap作者應該是OOP陣營的，其中出現有對應構造函數的min_heap_ctor()，和對應析構函數min_heap_dtor()。

2.3事件隊列（雙向鏈表）

libevent中的活躍事件隊列和已注冊隊列采用的數據結構都是用宏來實現的，原在freeBSD的<sys/queue.h>中已有定義，為了對Linux跨平臺支持考慮，libevent將部分代碼集中到event_internal.h里。

1#define TAILQ_ENTRY(type)                        \
2struct {                                         \
3    struct type *tqe_next;    /**//* 下一個元素 */         \
4    struct type **tqe_prev;    /**//*上一個元素的地址*/      \
5}
6

libevent用到的宏操作

TAILQ_INIT