`
simohayha
  • 浏览: 1400076 次
  • 性别: Icon_minigender_1
  • 来自: 火星
社区版块
存档分类
最新评论

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;
        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的算法实现有些丑陋罢了。。
3
1
分享到:
评论
2 楼 simohayha 2010-03-12  
huxk 写道
///这里可以看到当需要扩大队列的空间时,每次都是以8的倍数进行扩展

這句註釋錯得太離譜了

  ,谢谢了,当时看得不太仔细。。
1 楼 huxk 2010-03-07  
///这里可以看到当需要扩大队列的空间时,每次都是以8的倍数进行扩展

這句註釋錯得太離譜了

相关推荐

    libevent源码深度剖析pdf

    为方便阅读,把blog上的libevent源码深度剖析系列文章整合成一个pdf。

    libevent源码分析

    本文将对libevent源码进行分析,深入理解其实现原理以及关键的数据结构和函数接口。我们首先从libevent源码的整体架构开始,然后详细介绍一些重要的组件和它们的实现方式。 1. 开篇 在分析libevent源码之前,有必要...

    Libevent源码分析 pdf文档 带目录

    在深入Libevent源码分析之前,需要了解它的核心概念,主要包括事件循环、事件处理器、IO事件、定时器事件、信号事件等。事件循环是Libevent的中枢,它在后台运行,检测事件源的变化,并触发相应的事件处理器。事件...

    libevent源码深度剖析 + libevent参考手册(中文版)

    libevent库,文字版,很清晰,附带libevent参考手册(中文版) libevent源码深度剖析,根据libevent开源代码框架进行剖析,很不错值得学习借鉴,还有libevent中C语言的功底值得学习揣摩!

    Libevent源码解析.pdf

    Libevent 源码解析 Libevent 是一个高性能的事件驱动库,广泛应用于网络编程和高性能服务器开发中。下面是对 Libevent 源码的深入剖析,涵盖了其架构设计、事件处理机制、Reactor 模式、事件循环、IO multiplexing...

    libevent源码深度剖析

    libevent源码深度剖析

    libevent参考手册(中文版)+libevent源码深度剖析

    《libevent参考手册(中文版)》和《libevent源码深度剖析》是两本针对libevent库的重要参考资料。libevent是一个开源的事件通知库,它使得开发者能够编写高性能、可扩展的网络服务器或者客户端应用。这个库的核心...

    libevent源码深度剖析.zip_libevent 原理_libevent原理_libevent源码_libevent编程_

    《libevent源码深度剖析》 libevent是一个高度优化的事件通知库,广泛应用于网络编程,尤其是服务器端的高性能设计。它提供了一种抽象层,允许程序员以一致的方式处理各种类型的事件,包括文件描述符(如套接字)的...

    libevent 参考手册中文版及源码解析

    标题"libevent 参考手册中文版及源码解析"表明了本次学习的主题,重点是libevent库,包含了中文参考手册和源码的深度解析。libevent是一个开源的事件通知库,它使开发者能够方便地处理各种网络事件,如TCP、UDP、...

    libevent源码

    **libevent库源码详解** libevent是一个高度可移植、事件驱动的网络库,它能够帮助程序员处理大量的并发连接,并且有效地利用系统资源。在2.1.8stable版本中,libevent提供了丰富的功能和优化,使其成为开发高性能...

    最新jm源码、最新libevent源码

    标题中的“jm源码”和“libevent源码”指的是两个知名的开源项目,分别是JM(可能是Java Microservices的简称)和Libevent。这两个组件在IT领域,尤其是网络编程和服务器开发中扮演着重要角色。 首先,让我们深入...

    libevent 源码深度剖析.pdf

    libevent 源码深度剖析.pdf libevent 源码 深度 剖析 pdf

    Libevent源码和资料合集

    这个“Libevent源码和资料合集”包含了Libevent的核心源代码以及相关的学习资源,对于深入理解和使用Libevent至关重要。 Libevent 的主要功能是通过事件驱动模型来管理非阻塞I/O。它支持多种事件模型,包括epoll...

    libevent源码分析1

    《libevent源码分析1》 在深入探讨libevent的源码之前,我们先来了解一下这个库的基本情况。libevent是一个高度可扩展的事件通知库,它用于编写高性能、高并发的网络服务器。它的核心功能是提供了一种高效的方式来...

    libevent源码及库文件

    **二、libevent 的工作原理** `libevent` 的核心是事件循环,它负责监听注册的事件源并处理发生的事件。当事件发生时,对应的回调函数会被调用,用户可以在这些回调函数中执行相应的处理逻辑。 **三、libevent 的...

Global site tag (gtag.js) - Google Analytics