2.1 event_base核心事件基类数据结构
![](http://www.cppblog.com/images/cppblog_com/xguru/libevent1.jpg)
可以看出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
![](http://www.cppblog.com/images/cppblog_com/xguru/libevent2.jpg)
libevent从1.4版本之后就开始采用min-Heap来代替RB-Tree。
min-Heap(最小二叉堆)遵循的原则:
1.它是一种完全二叉树
2.它最小的元素在顶端每个元素都比它的父节点大(或相等)。
插入元素时间复杂度为O(log n),找出最小值的复杂度仅为O(1)。
libevent实现的min-Heap变量名有点猥琐。
1
typedef struct min_heap
2![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
3
struct event** p;
4
unsigned n, a;
5
} min_heap_t;
6![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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里。
![](http://www.cppblog.com/images/cppblog_com/xguru/libevent3.jpg)
1
#define TAILQ_ENTRY(type) \
2![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct
{ \
3![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
struct type *tqe_next; /**//* 下一个元素 */ \
4![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
struct type **tqe_prev; /**//*上一个元素的地址*/ \
5
}
6![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
libevent用到的宏操作
宏名称
|
操作
|
TAILQ_INIT
|
初始化队列
|
TAILQ_FOREACH
|
对队列进行遍历操作
|
TAILQ_INSERT_BEFORE
|
在指定元素之前插入元素
|
TAILQ_INSERT_TAIL
|
在队列尾部插入元素
|
TAILQ_EMPTY
|
检查队列是否为空
|
TAILQ_REMOVE
|
从队列中移除元素
|