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;
///这里可以看到当需要扩大行列的空间时，每次都是以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的算法实现有些丑恶而已。。