XGuru's Blog

技术,是一种态度。关注:高性能后端技术/服务器架构/C++/C/LAMP

   :: 首页 :: 联系 :: 聚合  :: 管理
  20 Posts :: 0 Stories :: 93 Comments :: 0 Trackbacks

公告





twitter / xoXGuru

feedsky
抓虾
google reader
鲜果
QQ邮箱
九点

常用链接

留言簿(8)

搜索

  •  

最新评论

阅读排行榜

 

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

初始化队列

TAILQ_FOREACH

对队列进行遍历操作

TAILQ_INSERT_BEFORE

在指定元素之前插入元素

TAILQ_INSERT_TAIL

在队列尾部插入元素

TAILQ_EMPTY

检查队列是否为空

TAILQ_REMOVE

从队列中移除元素

posted on 2010-06-24 00:23 XGuru 阅读(1596) 评论(1)  编辑 收藏 引用

Feedback

# re: [原创]Libevent学习笔记(2)-基本数据结构 2012-06-13 11:29 Filipe
Please translate this to english! thank you  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理