loop_in_codes

低调做技术__欢迎移步我的独立博客 codemaro.com 微博 kevinlynx

libevent 源码分析:min_heap带来的超时机制

author : Kevin Lynx

什么是min heap ?

    首先看什么是heap,heap是这样一种数据结构:1.它首先是一棵完成二叉树;2.父亲节点始终大于(或其他逻辑关系
)其孩子节点。根据父亲节点与孩子节点的这种逻辑关系,我们将heap分类,如果父亲节点小于孩子节点,那么这个heap
就是min heap。
    就我目前所看到的实现代码来看,heap基本上都是用数组(或者其他的连续存储空间)作为其存储结构的。这可以保证
数组第一个元素就是heap的根节点。这是一个非常重要的特性,它可以保证我们在取heap的最小元素时,其算法复杂度为
O(1)。
    原谅我的教科书式说教,文章后我会提供我所查阅的比较有用的关于heap有用的资料。

What Can It Do?
    libevent中的min_heap其实不算做真正的MIN heap。它的节点值其实是一个时间值。libevent总是保证时间最晚的节
点为根节点。
    libevent用这个数据结构来实现IO事件的超时控制。当某个事件(libevent中的struct event)被添加时(event_add),
libevent将此事件按照其超时时间(由用户设置)保存在min_heap里。然后libevent会定期地去检查这个min_heap,从而实现
了超时机制。

实现

    min_heap相关源码主要集中在min_heap.h以及超时相关的event.c中。
    首先看下min_heap的结构体定义:

typedef struct min_heap
{
    
struct event** p;
    unsigned n, a;
}
 min_heap_t;


    p指向了一个动态分配的数组(随便你怎么说,反正它是一个由realloc分配的连续内存空间),数组元素为event*,这也是
heap中的节点类型。这里libevent使用连续空间去保存heap,也就是保存一棵树。因为heap是完成树,所以可以保证其元素在
数组中是连续的。n表示目前保存了多少个元素,a表示p指向的内存的尺寸。
    struct event这个结构体定义了很多东西,但是我们只关注两个成员:min_heap_idx:表示该event保存在min_heap数组中
的索引,初始为-1;ev_timeout:该event的超时时间,将被用于heap操作中的节点值比较。

    接下来看几个与堆操作不大相关的函数:
    min_heap_elem_greater:比较两个event的超时值大小。
    min_heap_size:返回heap元素值数量。
    min_heap_reserve:调整内存空间大小,也就是调整p指向的内存区域大小。凡是涉及到内存大小调整的,都有一个策略问
题,这里采用的是初始大小为8,每次增大空间时以2倍的速度增加。
    看几个核心的:真正涉及到heap数据结构操作的函数:往堆里插入元素、从堆里取出元素:
    相关函数为:min_heap_push、min_heap_pop、min_heap_erase、min_heap_shift_up_、min_heap_shift_down_。

heap的核心操作:

- 往堆里插入元素:
    往堆里插入元素相对而言比较简单,如图所示,每一次插入时都从树的最右最下(也就是叶子节点)开始。然后比较即将插入
的节点值与该节点的父亲节点的值,如果小于父亲节点的话(不用在意这里的比较规则,上下文一致即可),那么交换两个节点,
将新的父亲节点与其新的父亲节点继续比较。重复这个过程,直到比较到根节点。

  heap_add
    libevent实现这个过程的函数主要是min_heap_shift_up_。每一次min_heap_push时,首先检查存储空间是否足够,然后直接
调用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;
    
/* 只要父节点还大于子节点就循环 */
    
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;
    }

    (s
->p[hole_index] = e)->min_heap_idx = hole_index;



- 从堆里取元素:

    大部分时候,从堆里取元素只局限于取根节点,因为这个节点是最有用的。对于数组存储结构而言,数组第一个元素即为根
节点。取完元素后,我们还需要重新调整整棵树以使其依然为一个heap。
    这需要保证两点:1.依然是完成树;2.父亲节点依然小于孩子节点。
    在具体实现heap的取元素操作时,具体到代码层次,方法都是有那么点微小差别的。libvent里的操作过程大致如图所示(实际上libevent中父节点的时间值小于子节点的时间值,时间值的比较通过evutil_timercmp实现):

heap_remove
    主要过程分为两步:
    1.比较左右孩子节点,选择最大的节点,移到父亲节点上;按照这种方式处理被选择的孩子节点,直到没有孩子节点为止。例如,
    当移除了100这个节点后,我们在100的孩子节点19和36两个节点里选择较大节点,即36,将36放置到100处;然后选择原来的36的
左右孩子25和1,选25放置于原来的36处;
    2.按照以上方式处理后,树会出现一个空缺,例如原先的25节点,因为被移动到原先的36处,25处就空缺了。因此,为了保证完
成性,就将最右最下的叶子节点(也就是连续存储结构中最后一个元素),例如这里的7,移动到空缺处,然后按照插入元素的方式处理
新插入的节点7。
    完成整个过程。

    libevent完成这个过程的函数主要是min_heap_shift_down_:

/* hole_index 为取出的元素的位置,e为最右最下的元素值 */
void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
{
    
/* 取得hole_index的右孩子节点索引 */
    unsigned min_child 
= 2 * (hole_index + 1);
    
while(min_child <= s->n)
    
{
        
/* 有点恶心的一个表达式,目的就是取两个孩子节点中较大的那个孩子索引 */
        min_child 
-= min_child == s->|| 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);
}
 


STL中的heap

值得一提的是,STL中提供了heap的相关操作算法,借助于模板的泛化特性,其适用范围非常广泛。相关函数为:
make_heap, pop_heap, sort_heap, is_heap, sort 。其实现原理同以上算法差不多,相关代码在algorithm里。SGI的
STL在stl_heap.h里。

参考资料:

What is a heap?

Heap_(data_structure)

Heap Remove

posted on 2008-07-18 15:56 Kevin Lynx 阅读(6550) 评论(6)  编辑 收藏 引用 所属分类: 通用编程network

评论

# re: libevent 源码分析:min_heap带来的超时机制 2008-07-21 12:07 foxtail

向高手致敬 哈哈  回复  更多评论   

# re: libevent 源码分析:min_heap带来的超时机制[未登录] 2008-07-23 20:06 happyday

插入元素和取元素的程序似乎是一样的???  回复  更多评论   

# re: libevent 源码分析:min_heap带来的超时机制 2008-07-23 23:12 Kevin Lynx

@happyday
取元素只是从树根取,取了后需要对整棵树进行调整。
插入元素插入到最下最右的节点,插入后需要进行微小的调整。
总之元素的增加/减少,都需要重新调整整棵树使其依然为一个堆。  回复  更多评论   

# re: libevent 源码分析:min_heap带来的超时机制[未登录] 2009-03-30 13:43 无名

哥们,libevent的最小堆根元素是最小的,父节点总比子节点值要小,

与你这里画得图不符,拜托能认真点吗?  回复  更多评论   

# re: libevent 源码分析:min_heap带来的超时机制 2009-03-31 16:24 Kevin Lynx

@happyday
代码确实粘贴错误,谢谢提醒。

@无名
图确实存在问题,谢谢提醒。

文章已做过微小修改。
  回复  更多评论   

# re: libevent 源码分析:min_heap带来的超时机制 2012-03-10 16:44 Color

其实是左节点,从0开始•••  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理