<b>libevent源码浅析(二):libevent的按时器的实现</b>[VC/C++编程]
本文“<b>libevent源码浅析(二):libevent的按时器的实现</b>[VC/C++编程]”是由七道奇为您精心收集,来源于网络转载,文章版权归文章作者所有,本站不对其观点以及内容做任何评价,请读者自行判断,以下是其具体内容:
在libevent中按时器的实现是通过基于最小堆的优先级行列来实现的.
关于这两个数据构造对比陌生的可以去翻算法导论的6.5节.
主要的源码都在min_heap.c中.
我们先来看主要的数据构造:
typedef struct min_heap
{
struct event** p;
unsigned n, a;
} min_heap_t;
在这个数据构造中 p也就是整个优先级行列,而这个优先级行列的每个节点都是一个struct *event.n表示这个行列的元素个数.a表示这个行列的大小.
接下来来看几个主要的办法:
min_heap_reserve调整行列的大小.
int min_heap_reserve(min_heap_t* s, unsigned n)
{
if(s->a < n)
{
struct event** p;
///这里可以看到当需求扩大行列的空间时,每次都是以8的倍数举行扩大
unsigned a = s->a ? s->a * 2 : 8;
if(a < n)
a = n;
///扩大行列的空间
if(!(p = (struct event**)realloc(s->p, a * sizeof *p)))
return -1;
s->p = p;
s->a = a;
}
return 0;
}
min_heap_shift_up_ 插入一个按时器到当前行列:
void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
{
///首先计算当前插入点的元素的父节点.
unsigned parent = (hole_index - 1) / 2;
///循环处理按时器的位置,首先对比当前的按时器与他的父节点的按时器,假如大于父节点的按时器,则直接跳过循环然后将按时器加入行列.假如大与父节点的按时器则交换两个节点的值,然后这里还有个需求注意的地方就是min_heap_idx这个数据,它表示当前event对象也就是按时器对象在按时器行列的索引值.
while(hole_index && min_heap_elem_greater(s->p[parent], e))
{
(s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
hole_index = parent;
parent = (hole_index - 1) / 2;
}
///得到按时器应插入的位置hole_index.
(s->p[hole_index] = e)->min_heap_idx = hole_index;
}
min_heap_shift_down_ 取出当前的最短时间的按时器,其实也就是root节点,然后均衡此最小堆.
void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
{
///得到当前节点的右孩子.每次取出root节点之后,传送最后一个元素到root节点,然后均衡此最小堆.
unsigned min_child = 2 * (hole_index + 1);
while(min_child <= s->n)
{
min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
if(!(min_heap_elem_greater(e, s->p[min_child])))
break;
(s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
hole_index = min_child;
min_child = 2 * (hole_index + 1);
}
min_heap_shift_up_(s, hole_index, e);
}
PS:其实只要对最小堆和优先级行列理解的话,这个按时器的实现很简单的说..不过libevent的算法实现有些丑陋罢了..
以上是“<b>libevent源码浅析(二):libevent的按时器的实现</b>[VC/C++编程]”的内容,如果你对以上该文章内容感兴趣,你可以看看七道奇为您推荐以下文章:
本文地址: | 与您的QQ/BBS好友分享! |