libevent源代码之最小堆的实现
libevent 中通过结构体min_heap_t实现最小堆，该结构体的声明如下：
typedef struct min_heap
{
struct event** p;
unsigned n, a;
} min_heap_t;
其中p是指向指针的指针，p指向了一个数组，该数组存储了event指针。N是申请数组的大小，a是当前数组中有几个元素。数组的大小在初始值设定为8，在添加元素时，数组内存不够时，重新申请一个2*n的数组，并把原数组中的内容拷贝到新申请的数组中。具体代码如下：
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**)mm_realloc(s->p, a * sizeof *p)))
return -1;
s->p = p;
s->a = a;
}
return 0;
}
和string的内存管理实现方式类似。
元素的入栈
int min_heap_push(min_heap_t* s, struct event* e)
{
if (min_heap_reserve(s, s->n + 1))
return -1;
min_heap_shift_up_(s, s->n++, e);
return 0;
}
min_heap_reserve不再介绍，min_heap_shift_up中并不是简单的把e放在堆的尾部，然后进行最小堆的调整。min_heap_shift_up中认为数组的尾部是一个hole，如果parent大于e，则可直接赋值到尾部，减少了元素之间的赋值交换。直到找到e适合的hole，然后直接赋值。
代码如下：
void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
{
unsigned parent = (hole_index - 1) / 2;
while (hole_index && min_heap_elem_greater(s->p[parent], e))
{
(s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index;
hole_index = parent;
parent = (hole_index - 1) / 2;
}
(s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
}
元素的出栈
和入栈类似，也是用一个hole来移动元素，避免元素的反复赋值交换