libevent源码浅析(二)

我们来看下libevent的定时器的实现

在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;
        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的算法实现有些丑陋罢了。。

评论

2 楼 simohayha 2010-03-12  

huxk 写道

///这里可以看到当需要扩大队列的空间时，每次都是以8的倍数进行扩展

這句註釋錯得太離譜了

  ，谢谢了，当时看得不太仔细。。

1 楼 huxk 2010-03-07  

///这里可以看到当需要扩大队列的空间时，每次都是以8的倍数进行扩展

這句註釋錯得太離譜了