当前位置:七道奇文章资讯编程技术VC/C++编程
日期:2011-03-22 13:54:00  来源:本站整理

<b>libevent源码浅析(二):libevent的按时器的实现</b>[VC/C++编程]

赞助商链接



  本文“<b>libevent源码浅析(二):libevent的按时器的实现</b>[VC/C++编程]”是由七道奇为您精心收集,来源于网络转载,文章版权归文章作者所有,本站不对其观点以及内容做任何评价,请读者自行判断,以下是其具体内容:

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


  以上是“<b>libevent源码浅析(二):libevent的按时器的实现</b>[VC/C++编程]”的内容,如果你对以上该文章内容感兴趣,你可以看看七道奇为您推荐以下文章:
  • <b>hosts是什么 hosts文件在什么位置 若何改正hosts</b>
  • <b>在 Windows 8 中手动安装语言包</b>
  • <b>五个常见 PHP数据库问题</b>
  • Windows中Alt键的12个高效快速的利用本领介绍
  • <b>MySQL ORDER BY 的实现解析</b>
  • <b>详解MySQL存储历程参数有三种范例(in、out、inout)</b>
  • <b>Win8系统恢复出来经典的开始菜单的办法</b>
  • <b>Win8系统花屏怎么办 Win8系统花屏的办理办法</b>
  • <b>Windows 7系统下无线网卡安装</b>
  • <b>为什么 Linux不需求碎片整理</b>
  • <b>Windows 8中删除账户的几种办法(图)</b>
  • <b>教你如安在win7下配置路由器</b>
  • 本文地址: 与您的QQ/BBS好友分享!
    • 好的评价 如果您觉得此文章好,就请您
        0%(0)
    • 差的评价 如果您觉得此文章差,就请您
        0%(0)

    文章评论评论内容只代表网友观点,与本站立场无关!

       评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论
    Copyright © 2020-2022 www.xiamiku.com. All Rights Reserved .