注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Code@Pig Home

喜欢背着一袋Code傻笑的Pig .. 忧美.欢笑.记忆.忘却 .之. 角落

 
 
 

日志

 
 

[libevent] timer 的原理 (min-heap)  

2009-03-21 16:56:39|  分类: net_libevent |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
libevent-1.4.12-stable, libevent-2.0.4-alpha

libevent 中,用最小堆(min-heap)来管理所有 timer。

基础知识
min-heap,就是 child node value 一定小于 parent node value 的 binary-tree。因此,获取 min value,只需要 pop root node 即可。
[libevent] min-heap - kasicass - Co<wbr>de@Pig Home


算法实现 (min_heap.h)
对于 libevent,root node 就是最近即将触发的 timer event。node value 就是 timer 触发的时间(秒)。

// p - (struct event *) array
// n - event array count (point to first empty slot)
// a - event array size
typedef struct min_heap
{
    struct event** p;
    unsigned n, a;
} min_heap_t

对于上面的图,n = 9, a = 12,p[] 中存储的值如下:
index   0   1   2    3    4    5   6    7     8   9  10  11
value   1   2   3  17  19  36   7  25 100   ?   ?    ?
而 child/parent 可以构成 parent_index = (child_index - 1) / 2 的关系。

:-) 基本数据便是如此这般,剩下的代码也就比较简单了。
  评论这张
 
阅读(2844)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017