Libevent源码分析(一):最小堆

2024-09-05 12:48
文章标签 分析 源码 最小 libevent

本文主要是介绍Libevent源码分析(一):最小堆,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Libevent中的timeout事件是使用最小堆来管理维护的.代码位于<minheap-internal.h>.

看函数命名和代码风格应该是一个C++程序员,函数名都挺好懂的,只是下面这个结构体变量命名比较坑....

typedef struct min_heap
{struct event** p;unsigned n, a;//n队列元素的多少,a代表队列空间的大小.
} min_heap_t;

注释是我加的,这命名,n啊a啊的,鬼知道啥意思....必须吐槽一下.

 

先来说说什么是最小堆:

1.堆是一个二叉树

2.最小堆:父节点的值总是小于等于子节点

如下图:

上图圆圈旁边的数字代表其在数组中的下标.堆一般是用数组来存储的,也就是说实际存储结构是连续的,只是逻辑上是一棵树的结构.这样做的好处是很容易找到堆顶的元素,对Libevent来说,很容易就可以找到距当前时间最近的timeout事件.

 现在想想看我们要插入一个元素,我们要怎么移动数组中元素的位置,使其逻辑上仍然是一个小堆?结合下图很容易看出来:

1.假设我们要插入的元素为6大于其父节点的值2.则把元素放在数组相应的index上,插入完成.

 

2.假设我们要插入的为2小于其父节点的值3.则交换该节点与其父节点的值.对于下图来说,交换完毕后插入就算完成了.那要是交换完后发现index=2的元素还小于其父节点index=0的呢?就又得在一次交换,如此循环,直到达到根节点或是其不大于父节点.

到了这里我们看看libevent里的实现代码就很清楚了

复制代码
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;
}//分配队列大小.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;  //初始分配8个指针大小空间,否则原空间大小翻倍.if (a < n)a = n;   //翻倍后空间依旧不足,则分配n.if (!(p = (struct event**)mm_realloc(s->p, a * sizeof *p))) //重新分配内存return -1;s->p = p; //重新赋值队列地址及大小.s->a = a; //
    }return 0;
}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;
}
复制代码

 实际上作者写了一个比较通用的函数min_heap_shift_up(),与之相对应的还有min_heap_shift_down()

复制代码
void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
{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])->ev_timeout_pos.min_heap_idx = hole_index;hole_index = min_child;min_child = 2 * (hole_index + 1);}(s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
}
复制代码

这里的hole_index是我们要填入某个值的下标,e是要填入的值.还是画图比较好理解:

当这个值(下标为hole_Index=1)比其父节点1(index = 0)小时,要向上移动调整.

当这个值(下标为hole_Index=1)比其最小子节点6(index = 3)还大时,要向下移动调整.

Libevent里是这么使用他们的:

复制代码
int min_heap_erase(min_heap_t* s, struct event* e)
{if (-1 != e->ev_timeout_pos.min_heap_idx){struct event *last = s->p[--s->n];//把最后一个值作为要填入hole_index的值unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;/* we replace e with the last element in the heap.  We might need toshift it upward if it is less than its parent, or downward if it isgreater than one or both its children. Since the children are knownto be less than the parent, it can't need to shift both up anddown. */if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))min_heap_shift_up_(s, e->ev_timeout_pos.min_heap_idx, last);elsemin_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last);e->ev_timeout_pos.min_heap_idx = -1;return 0;}return -1;
}
复制代码
复制代码
struct event* min_heap_pop(min_heap_t* s)
{if (s->n){struct event* e = *s->p;min_heap_shift_down_(s, 0u, s->p[--s->n]);e->ev_timeout_pos.min_heap_idx = -1;return e;}return 0;
}
复制代码

 

最后总结一下,由于堆这种结构在逻辑上的这种二叉树的关系,其插入也好,删除也好,就是一个与父节点或是子节点比较然后调整位置,这一过程循环往复直到达到边界条件的过程.记住这一点,就不难写出代码了.

二叉树节点i:父节点为(i-1)/2.子节点为2i+1,2(i+1)。

这篇关于Libevent源码分析(一):最小堆的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1139012

相关文章

基于Go语言实现Base62编码的三种方式以及对比分析

《基于Go语言实现Base62编码的三种方式以及对比分析》Base62编码是一种在字符编码中使用62个字符的编码方式,在计算机科学中,,Go语言是一种静态类型、编译型语言,它由Google开发并开源,... 目录一、标准库现状与解决方案1. 标准库对比表2. 解决方案完整实现代码(含边界处理)二、关键实现细

PostgreSQL 序列(Sequence) 与 Oracle 序列对比差异分析

《PostgreSQL序列(Sequence)与Oracle序列对比差异分析》PostgreSQL和Oracle都提供了序列(Sequence)功能,但在实现细节和使用方式上存在一些重要差异,... 目录PostgreSQL 序列(Sequence) 与 oracle 序列对比一 基本语法对比1.1 创建序

Android实现一键录屏功能(附源码)

《Android实现一键录屏功能(附源码)》在Android5.0及以上版本,系统提供了MediaProjectionAPI,允许应用在用户授权下录制屏幕内容并输出到视频文件,所以本文将基于此实现一个... 目录一、项目介绍二、相关技术与原理三、系统权限与用户授权四、项目架构与流程五、环境配置与依赖六、完整

Android实现定时任务的几种方式汇总(附源码)

《Android实现定时任务的几种方式汇总(附源码)》在Android应用中,定时任务(ScheduledTask)的需求几乎无处不在:从定时刷新数据、定时备份、定时推送通知,到夜间静默下载、循环执行... 目录一、项目介绍1. 背景与意义二、相关基础知识与系统约束三、方案一:Handler.postDel

慢sql提前分析预警和动态sql替换-Mybatis-SQL

《慢sql提前分析预警和动态sql替换-Mybatis-SQL》为防止慢SQL问题而开发的MyBatis组件,该组件能够在开发、测试阶段自动分析SQL语句,并在出现慢SQL问题时通过Ducc配置实现动... 目录背景解决思路开源方案调研设计方案详细设计使用方法1、引入依赖jar包2、配置组件XML3、核心配

Java NoClassDefFoundError运行时错误分析解决

《JavaNoClassDefFoundError运行时错误分析解决》在Java开发中,NoClassDefFoundError是一种常见的运行时错误,它通常表明Java虚拟机在尝试加载一个类时未能... 目录前言一、问题分析二、报错原因三、解决思路检查类路径配置检查依赖库检查类文件调试类加载器问题四、常见

Python中的Walrus运算符分析示例详解

《Python中的Walrus运算符分析示例详解》Python中的Walrus运算符(:=)是Python3.8引入的一个新特性,允许在表达式中同时赋值和返回值,它的核心作用是减少重复计算,提升代码简... 目录1. 在循环中避免重复计算2. 在条件判断中同时赋值变量3. 在列表推导式或字典推导式中简化逻辑

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字