从零开始实现 C++ TinyWebServer 小根堆定时器 HeapTimer详解

文章目录

  • TimerNode 结构体
  • HeapTimer 类
  • 堆操作函数
    • 实现 SwapNode() 函数
    • 实现 SiftUp() 函数
    • 实现 SiftDown() 函数
    • 实现 Delete() 函数
  • 实现 Add() 函数
  • 实现 Adjust() 函数
  • 实现 DoWork() 函数
  • 实现 Tick() 函数
  • 实现 GetNextTick() 函数
  • 实现 Pop() 函数
  • 实现 Clear() 函数
  • HeapTimer 代码
  • HeapTimer 测试

从零开始实现 C++ TinyWebServer 项目总览
项目源码

TimerNode 结构体

struct TimerNode {int id;TimeStamp expires;  // 超时时间点TimeoutCallBack cb; //  回调函数TimerNode(int id_, TimeStamp expires_, TimeoutCallBack cb_) : id(id_), expires(expires_), cb(cb_) {}bool operator<(const TimerNode& t) {return expires < t.expires;}bool operator>(const TimerNode& t) {return expires > t.expires;}
};
  • id：定时器的唯一标识符。
  • expires：定时器的超时时间点。
  • cb：定时器到期时要执行的回调函数。
  • 重载了 < 和 > 运算符，用于比较两个定时器节点的超时时间，用于后续建堆。

HeapTimer 类

HeapTimer类是基于小根堆的定时器，用于管理多个定时任务。在 webserver 中，定时器是一种重要的工具，常用于处理连接超时、定时任务等场景。使用最小堆来管理定时器的好处是可以高效地插入、删除和获取最近到期的定时器。

class HeapTimer {
public:HeapTimer() { heap_.reserve(64); }~HeapTimer() { Clear(); }void Add(int id, int timeout, const TimeoutCallBack& cb);void Adjust(int id, int timeout);void DoWork(int id);void Tick();int GetNextTick();void Pop();void Clear();size_t Size() { return heap_.size(); }private:void SwapNode(size_t i, size_t j);void SiftUp(size_t child);bool SiftDown(size_t parent, size_t n);void Delete(size_t i);std::vector<TimerNode> heap_;// id 对应的在 heap_ 中的下标std::unordered_map<int, size_t> ref_;
};

堆操作函数

实现 SwapNode() 函数

void HeapTimer::SwapNode(size_t i, size_t j) {assert(i < heap_.size());assert(j < heap_.size());std::swap(heap_[i], heap_[j]);ref_[heap_[i].id] = i;ref_[heap_[j].id] = j;
}

实现 SiftUp() 函数

// 向上调整算法
void HeapTimer::SiftUp(size_t child) {assert(child < heap_.size());size_t parent = (child - 1) / 2;while (parent > 0) {if (heap_[parent] > heap_[child]) {SwapNode(child, parent);child = parent;parent = (child - 1) / 2;} else {break;}}
}

实现 SiftDown() 函数

// 向下调整算法
// 返回：是否调整
bool HeapTimer::SiftDown(size_t parent, size_t n) {assert(parent < heap_.size());assert(n <= heap_.size());size_t child = 2 * parent + 1; // 左孩子size_t pos = parent;while (child < n) {if (child + 1 < n && heap_[child + 1] < heap_[child])++child; // 右孩子if (heap_[parent] > heap_[child]) {SwapNode(child, parent);parent = child;child = 2 * parent + 1;} else {break;}}return pos < parent;
}

实现 Delete() 函数

  • 将该节点与堆的最后一个节点交换位置。
  • 调用 SiftDown 函数，如果未进行向下调整，再调用 SiftUp 函数调整堆。
void HeapTimer::Delete(size_t i) {assert(!heap_.empty() && i < heap_.size());size_t n = heap_.size() - 1;if (i < n - 1) { // 跳过nSwapNode(i, n);if (!SiftDown(i, n))SiftUp(i);}ref_.erase(heap_.back().id);heap_.pop_back();
}

实现 Add() 函数

void HeapTimer::Add(int id, int timeout, const TimeoutCallBack& cb) {if (ref_.count(id)) {Adjust(id, timeout);heap_[ref_[id]].cb = cb;} else {size_t n = heap_.size();ref_[id] = n;heap_.emplace_back(id, Clock::now() + MS(timeout), cb);SiftUp(n);}
}

实现 Adjust() 函数

void HeapTimer::Adjust(int id, int timeout) {assert(ref_.count(id));heap_[ref_[id]].expires = Clock::now() + MS(timeout);if (!SiftDown(ref_[id], heap_.size()))SiftUp(ref_[id]);
}

实现 DoWork() 函数

void HeapTimer::DoWork(int id) {if (heap_.empty() || ref_.count(id))return;size_t i = ref_[id];heap_[i].cb();Delete(i);
}

实现 Tick() 函数

void HeapTimer::Tick() {if (heap_.empty())return;while (!heap_.empty()) {TimerNode node = heap_.front();if (std::chrono::duration_cast<MS>(node.expires - Clock::now()).count() > 0)break;node.cb();Pop();}
}

实现 GetNextTick() 函数

int HeapTimer::GetNextTick() {Tick();int res = -1;if (!heap_.empty()) {res = std::chrono::duration_cast<MS>(heap_.front().expires - Clock::now()).count();if (res < 0) res = 0;   }return res;
}

实现 Pop() 函数

void HeapTimer::Pop() {assert(!heap_.empty());Delete(0);
}

实现 Clear() 函数

void HeapTimer::Clear() {heap_.clear();ref_.clear();
}

HeapTimer 代码

heap_timer.h

#ifndef HEAP_TIMER_H
#define HEAP_TIMER_H#include <cassert>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <chrono>
#include <functional>typedef std::function<void()> TimeoutCallBack;
typedef std::chrono::high_resolution_clock Clock;
typedef std::chrono::milliseconds MS;
typedef std::chrono::high_resolution_clock::time_point TimeStamp;// 定时器节点
struct TimerNode {int id;TimeStamp expires;  // 超时时间点TimeoutCallBack cb; //  回调函数TimerNode(int id_, TimeStamp expires_, TimeoutCallBack cb_) : id(id_), expires(expires_), cb(cb_) {}bool operator<(const TimerNode& t) {return expires < t.expires;}bool operator>(const TimerNode& t) {return expires > t.expires;}
};class HeapTimer {
public:HeapTimer() { heap_.reserve(64); }~HeapTimer() { Clear(); }void Add(int id, int timeout, const TimeoutCallBack& cb);void Adjust(int id, int timeout);void DoWork(int id);void Tick();int GetNextTick();void Pop();void Clear();size_t Size() { return heap_.size(); }private:void SwapNode(size_t i, size_t j);void SiftUp(size_t child);bool SiftDown(size_t parent, size_t n);void Delete(size_t i);std::vector<TimerNode> heap_;// id 对应的在 heap_ 中的下标std::unordered_map<int, size_t> ref_;
};#endif // HEAP_TIMER_H

heap_timer.cc

#include "heap_timer.h"void HeapTimer::Add(int id, int timeout, const TimeoutCallBack& cb) {if (ref_.count(id)) {Adjust(id, timeout);heap_[ref_[id]].cb = cb;} else {size_t n = heap_.size();ref_[id] = n;heap_.emplace_back(id, Clock::now() + MS(timeout), cb);SiftUp(n);}
}void HeapTimer::Adjust(int id, int timeout) {assert(ref_.count(id));heap_[ref_[id]].expires = Clock::now() + MS(timeout);if (!SiftDown(ref_[id], heap_.size()))SiftUp(ref_[id]);
}// 触发回调函数，并删除id
void HeapTimer::DoWork(int id) {if (heap_.empty() || ref_.count(id))return;size_t i = ref_[id];heap_[i].cb();Delete(i);
}void HeapTimer::Tick() {if (heap_.empty())return;while (!heap_.empty()) {TimerNode node = heap_.front();if (std::chrono::duration_cast<MS>(node.expires - Clock::now()).count() > 0)break;node.cb();Pop();}
}int HeapTimer::GetNextTick() {Tick();int res = -1;if (!heap_.empty()) {res = std::chrono::duration_cast<MS>(heap_.front().expires - Clock::now()).count();if (res < 0) res = 0;   }return res;
}void HeapTimer::Pop() {assert(!heap_.empty());Delete(0);
}void HeapTimer::Clear() {heap_.clear();ref_.clear();
}void HeapTimer::SwapNode(size_t i, size_t j) {assert(i < heap_.size());assert(j < heap_.size());std::swap(heap_[i], heap_[j]);ref_[heap_[i].id] = i;ref_[heap_[j].id] = j;
}// 向上调整算法
void HeapTimer::SiftUp(size_t child) {assert(child < heap_.size());size_t parent = (child - 1) / 2;while (parent > 0) {if (heap_[parent] > heap_[child]) {SwapNode(child, parent);child = parent;parent = (child - 1) / 2;} else {break;}}
}// 向下调整算法
// 返回：是否调整
bool HeapTimer::SiftDown(size_t parent, size_t n) {assert(parent < heap_.size());assert(n <= heap_.size());size_t child = 2 * parent + 1; // 左孩子size_t pos = parent;while (child < n) {if (child + 1 < n && heap_[child + 1] < heap_[child])++child; // 右孩子if (heap_[parent] > heap_[child]) {SwapNode(child, parent);parent = child;child = 2 * parent + 1;} else {break;}}return pos < parent;
}void HeapTimer::Delete(size_t i) {assert(!heap_.empty() && i < heap_.size());size_t n = heap_.size() - 1;if (i < n - 1) { // 跳过nSwapNode(i, n);if (!SiftDown(i, n))SiftUp(i);}ref_.erase(heap_.back().id);heap_.pop_back();
}

HeapTimer 测试

测试 HeapTimer 的Add，Tick，GetNextTick函数。

#include "../code/heap_timer/heap_timer.h"
#include "../code/log/log.h"
#include <cassert>void CallbackFunction() {LOG_DEBUG("Callback function is called!")
}// 测试 add 函数
void TestAdd() {HeapTimer timer;int id = 1;int timeout = 1000;  // 超时时间为 1000 毫秒timer.Add(id, timeout, CallbackFunction);assert(timer.Size() == 1);
}// 测试 tick 函数
void TestTick() {HeapTimer timer;int id = 1;int timeout = 100;  // 超时时间为 100 毫秒timer.Add(id, timeout, CallbackFunction);// 等待一段时间，确保定时器超时std::this_thread::sleep_for(std::chrono::milliseconds(200));timer.Tick();assert(timer.Size() == 0);
}// 测试 GetNextTick 函数
void TestGetNextTick() {HeapTimer timer;int id = 1;int timeout = 10000;  // 超时时间为 10000 毫秒timer.Add(id, timeout, CallbackFunction);int next_tick = timer.GetNextTick();assert(next_tick >= 0);
}int main() {Log* logger = Log::GetInstance();logger->Init(0, "./logs/", ".log", 1024);TestAdd();TestTick();TestGetNextTick();return 0;
}

CMakeList.txt

cmake_minimum_required(VERSION 3.10)
project(tests)# 设置 C++ 标准和编译器选项
set(CMAKE_BUILD_TYPE Debug)
set(CMAKE_CXX_STANDARD 14)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wall -Wextra")set(COMMON ../code/buffer/buffer.cc ../code/log/log.cc)
set(HEAP_TIMER ../code/heap_timer/heap_timer.cc)add_executable(heap_timer_test heap_timer_test.cc ${COMMON} ${HEAP_TIMER})

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/41328.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

音视频 二 看书的笔记 MediaPlayer

音视频 二 看书的笔记 MediaPlayer

此类是用于播放声音和视频的主要 API 对方不想多说向你丢了一个链接 MediaPlayer Idle 空闲状态Initialized 初始化状态 调用 setDataSource() 时会进入此状态 setDataSource必须在Idle 状态下调用&#xff0c;否则就抛出异常了了了了了。Prepared 准备状态 回调监听setOnPrep…
阅读更多...
Linux笔记---动静态库（使用篇）

Linux笔记---动静态库（使用篇）

目录 1. 库的概念 2. 静态库&#xff08;Static Libraries&#xff09; 2.1 静态库的制作 2.2 静态库的使用 2.2.1 显式指定库文件及头文件路径 2.2.2 将库文件安装到系统目录 2.2.3 将头文件安装到系统目录 3. 动态库 3.1 动态库的制作 3.2 动态库的使用 3.2.1 显式…
阅读更多...
CAS（Compare And Swap）

CAS（Compare And Swap）

CAS核心原理 操作流程 CAS 包含三个参数&#xff1a;内存值&#xff08;V&#xff09;、预期值&#xff08;E&#xff09;和新值&#xff08;N&#xff09;。执行步骤如下&#xff1a; 比较&#xff1a;检查当前内存值 V 是否等于预期值 E。 交换&#xff1a;如果相等&#…
阅读更多...
宝塔面板安装docker flarum失败，请先安装依赖应用: [‘mysql‘]:5/8

宝塔面板安装docker flarum失败，请先安装依赖应用: [‘mysql‘]:5/8

安装失败的解决方案 提示错误请先安装依赖应用: [mysql]:5/8 解决方案&#xff1a;不要使用最新的docker mysql&#xff0c;使用5.7.44版本docker mysql&#xff0c;等安装完毕再安装docker flarum就不会报错了。 如果安装完成你不知道默认的账号密码可以看这里 宝塔docker f…
阅读更多...
c#的.Net Framework 的console 项目找不到System.Window.Forms 引用

c#的.Net Framework 的console 项目找不到System.Window.Forms 引用

首先确保是建立的.Net Framework 的console 项目,然后天健reference 应用找不到System.Windows.Forms 引用 打开对应的csproj 文件 在第一个PropertyGroup下添加 <UseWindowsForms>true</UseWindowsForms> 然后在第一个ItemGroup 下添加 <Reference Incl…
阅读更多...
基于 mxgraph 实现流程图

基于 mxgraph 实现流程图

mxgraph 可以实现复杂的流程图绘制。mxGraph里的Graph指的是图论(Graph Theory)里的图而不是柱状图、饼图和甘特图等图(chart)&#xff0c;因此想找这些图的读者可以结束阅读了。 作为图论的图&#xff0c;它包含点和边&#xff0c;如下图所示。 交通图 横道图 架构图 mxGrap…
阅读更多...
21.Excel自动化：如何使用 xlwings 进行编程

21.Excel自动化：如何使用 xlwings 进行编程

一 将Excel用作数据查看器 使用 xlwings 中的 view 函数。 1.导包 import datetime as dt import xlwings as xw import pandas as pd import numpy as np 2.view 函数 创建一个基于伪随机数的DataFrame&#xff0c;它有足够多的行&#xff0c;使得只有首尾几行会被显示。 df …
阅读更多...
STL之空间配置器

STL之空间配置器

1. 什么是空间配置器 空间配置器&#xff0c;顾名思义就是为各个容器高效的管理空间(空间的申请与回收)的&#xff0c;在默默地工作。虽然在常规使用STL时&#xff0c;可能用不到它&#xff0c;但站在学习研究的角度&#xff0c;学习它的实现原理对我们有很大的帮助。 2. 为什…
阅读更多...
Axure项目实战：智慧城市APP（三）教育查询（显示与隐藏交互）

Axure项目实战：智慧城市APP（三）教育查询（显示与隐藏交互）

亲爱的小伙伴&#xff0c;在您浏览之前&#xff0c;烦请关注一下&#xff0c;在此深表感谢&#xff01; 课程主题&#xff1a;教育查询 主要内容&#xff1a;教育公告信息&#xff0c;小升初、初升高、高考成绩查询&#xff1b;教育公告信息为传统的信息页面&#xff0c;小升…
阅读更多...
最大字段和问题 C++(穷举、分治法、动态规划)

最大字段和问题 C++(穷举、分治法、动态规划)

问题描述 给定由n个整数&#xff08;包含负整数&#xff09;组成的序列a1,a2,…,an&#xff0c;求该序列子段和的最大值。规定当所有整数均为负值时定义其最大子段和为0 穷举法 最简单的方法就是穷举法&#xff0c;用一个变量指示求和的开始位置&#xff0c;一个变量指示结束…
阅读更多...
【数据转换】- Halcon＜-＞Mat

【数据转换】- Halcon＜-＞Mat

背景介绍 最近在写C#联合Haclon调用C的.dll文件进行联合编程。大致需求就是C#设计界面&#xff0c;然后调用Haclon的图像处理库&#xff0c;C把目标检测的模型进行TensorRT部署生成动态链接库&#xff0c;之后界面操作加载模型、对图像进行检测等功能。 设计界面如下&#xf…
阅读更多...
MFC中如何判断一个窗口当前状态是显示还是隐藏

MFC中如何判断一个窗口当前状态是显示还是隐藏

文章目录 一、核心方法&#xff1a;使用 CWnd::IsWindowVisible函数原型示例代码 二、注意事项1. 父窗口的影响2. 窗口最小化/最大化状态3. 窗口尚未创建 三、扩展&#xff1a;通过窗口样式直接判断四、完整示例代码五、总结 在MFC中&#xff0c;判断窗口当前是显示还是隐藏状态…
阅读更多...
Java 大视界 -- 基于 Java 的大数据分布式系统的监控与运维实践（155）

Java 大视界 -- 基于 Java 的大数据分布式系统的监控与运维实践（155）

&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎来到 青云交的博客&#xff01;能与诸位在此相逢&#xff0c;我倍感荣幸。在这飞速更迭的时代&#xff0c;我们都渴望一方心灵净土&#xff0c;而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识&#xff0c;也…
阅读更多...
消息队列性能比拼: Kafka vs RabbitMQ

消息队列性能比拼: Kafka vs RabbitMQ

本内容是对知名性能评测博主 Anton Putra Kafka vs RabbitMQ Performance 内容的翻译与整理, 有适当删减, 相关数据和结论以原作结论为准。 简介 在本视频中&#xff0c;我们将首先比较 Apache Kafka 和传统的 RabbitMQ。然后&#xff0c;在第二轮测试中&#xff0c;会将 Kaf…
阅读更多...
[ComfyUI] SDXL Prompt Styler 自定义节点的作用解析

[ComfyUI] SDXL Prompt Styler 自定义节点的作用解析

1. SDXL Prompt Styler 的位置与基本功能 在 ComfyUI 的 “新建节点” → “实用工具” 下，可以找到 Style 节点（SDXL Prompt Styler）。该节点的主要作用是对输入的描述进行结构化处理，并在转换为 Stable Diffusion XL (SDXL) 提示词时，自动补充风格相关的内容，使提示词…
阅读更多...
【JavaScript】金丹期功法

【JavaScript】金丹期功法

目录 数组声明数组数组的基本使用遍历数组案例&#xff1a;求数组中的最值数组操作查询数据修改数据新增数据案例&#xff1a;数组筛选删除数据 案例&#xff1a;渲染柱形图 数组 数组&#xff08;Array&#xff09;是一种可以按顺序保存数据的数据类型 场景&#xff1a;如果…
阅读更多...
学习本地部署DeepSeek的过程（基于LM Studio）

学习本地部署DeepSeek的过程（基于LM Studio）

除了使用Ollama部署DeepSeek&#xff0c;还可以使用LM Studio部署DeepSeek&#xff0c;后者是一款允许用户在本地计算机上运行大型语言模型&#xff08;LLMs&#xff09;的桌面应用程序&#xff0c;旨在简化本地模型的使用&#xff0c;无需云端连接或复杂配置即可体验 AI 功能。…
阅读更多...
AOA与TOA混合定位，MATLAB例程，自适应基站数量，三维空间下的运动轨迹，滤波使用EKF

AOA与TOA混合定位，MATLAB例程，自适应基站数量，三维空间下的运动轨迹，滤波使用EKF

本代码实现了一个基于 到达角（AOA） 和 到达时间（TOA） 的混合定位算法，结合 扩展卡尔曼滤波（EKF） 对三维运动目标的轨迹进行滤波优化。代码通过模拟动态目标与基站网络，展示了从信号测量、定位解算到轨迹滤波的全流程，适用于城市峡谷、室内等复杂环境下的定位研究。 文…
阅读更多...
C++：函数（通识版）

C++：函数（通识版）

一、函数的基础 1.什么是函数&#xff1f;&#xff08;独立的功能单位&#xff09; 函数是C中封装代码逻辑的基本单元&#xff0c;用于执行特定任务。 作用&#xff1a;代码复用、模块化、提高可读性。 2、函数的基本结构 返回类型 函数名(参数列表) {// 函数体return 返回值…
阅读更多...
STL之map和set

STL之map和set

1. 关联式容器 vector、list、deque、 forward_list(C11)等&#xff0c;这些容器统称为序列式容器&#xff0c;因为其底层为线性序列的数据结构&#xff0c;里面存储的是元素本身。 关联式容器也是用来存储数据的&#xff0c;与序列式容器不同的是&#xff0c;其里面存储的是结…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023