XGuru's Blog

2.1 event_base核心事件基類數(shù)據(jù)結(jié)構(gòu)

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

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

      已注冊隊列對應(yīng)事件基中的eventqueue，活躍事件隊列對應(yīng)的是事件基中的activequeues[ev->ev_pri]結(jié)構(gòu)體數(shù)組。其中的ev_pri代表的是事件的優(yōu)先級，數(shù)值越小代表越高的優(yōu)先級別。

      可以通過調(diào)用event_priority_set()函數(shù)對其優(yōu)先級進行設(shè)置，默認(rèn)插入中等優(yōu)先級(nactivequeues/2 ,即活躍隊列總數(shù)除以2)。

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

      在這里處理超時機制中使用了一個經(jīng)典的數(shù)據(jù)結(jié)構(gòu)min-Heap，源碼位于Min_heap.h

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

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

1.它是一種完全二叉樹

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

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

libevent實現(xiàn)的min-Heap變量名有點猥瑣。

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

p可以理解成存儲事件指針的數(shù)組，n表示的是容量，a表示的是當(dāng)前數(shù)。

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

這個min-heap作者應(yīng)該是OOP陣營的，其中出現(xiàn)有對應(yīng)構(gòu)造函數(shù)的min_heap_ctor()，和對應(yīng)析構(gòu)函數(shù)min_heap_dtor()。

2.3事件隊列（雙向鏈表）

libevent中的活躍事件隊列和已注冊隊列采用的數(shù)據(jù)結(jié)構(gòu)都是用宏來實現(xiàn)的，原在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