XGuru's Blog

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

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

      時(shí)間堆采用的是min-Heap最小二叉堆，已注冊(cè)隊(duì)列和活躍事件隊(duì)列采用的都是雙向鏈表。

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

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

2.2 超時(shí)隊(duì)列（min-Heap最小二叉堆）

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

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

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

1.它是一種完全二叉樹

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

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

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

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

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

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

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

2.3事件隊(duì)列（雙向鏈表）

libevent中的活躍事件隊(duì)列和已注冊(cè)隊(duì)列采用的數(shù)據(jù)結(jié)構(gòu)都是用宏來(lái)實(shí)現(xiàn)的，原在freeBSD的<sys/queue.h>中已有定義，為了對(duì)Linux跨平臺(tái)支持考慮，libevent將部分代碼集中到event_internal.h里。

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

libevent用到的宏操作

TAILQ_INIT