1.概述
定时器是一种用于在指定时间后执行特定任务或操作的机制。在计算机科学和编程中，定时器通常用于实现延时操作、周期性任务调度等功能。
对于定时器的实现，核心分为两大块，分别是容器和触发方式，容器就是组织定时器中定时任务的数据结构，触发方式描述了我们以什么方式检测任务是否到期。今天的重点是定时器系列的开篇，能组织定时器的数据结构都要有一个基本的要求，就是能保证数据在数据结构内是有序的，通常的数据结构又最小堆、红黑树、时间轮等，本文将使用最小堆来组织定时器。
2.最小堆
最小堆（Min-Heap）是一种特殊的完全二叉树，其中每个节点的值都小于或等于其子节点的值。这种特性使得最小堆的根节点总是存储着最小的元素。最小堆常用于实现需要快速访问最小元素的应用场景。
最小堆是一棵完全二叉树，这意味着除了最后一层外，其他所有层都是满的，并且最后一层的节点尽可能靠左排列。最小堆通常使用数组表示，其堆序性质：对于任意节点 ( i )，其子节点 ( 2i+1 ) 和 ( 2i+2 ) 满足以下条件：
- heap[i] > heap[2i + 1]及父节点大于左子节点
- heap[i] < heap[2i + 2]及父节点小于右子节点
3.代码实现
定义以下结构：
struct timer_entry {
uint64_t time; // 时间戳，用来表示定时任务的过期时间
uint32_t min_heap_idx; // 当前节点在堆(数组)中的索引
};
struct min_heap {
timer_entry** p;
uint32_t n; // n 为实际元素个数
uint32_t a; // a 为容量
};实现其核心调整算法：
#define min_heap_elem_greater(a, b) \
((a)->time > (b)->time)
static void min_heap_shift_up_(min_heap* s, uint32_t hole_index, timer_entry* e) {
//计算父节点索引
uint32_t parent = (hole_index - 1) / 2;
//当前插入位置的索引不为0，并且插入位置的父节点的值比当前插入的值大，则交换位置知道这个条件不满足就把插入的元素插入到当前位置
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;
}
(s->p[hole_index] = e)->min_heap_idx = hole_index;
}
static void min_heap_shift_down_(min_heap* s, uint32_t hole_index, timer_entry* e)
{
// 计算右子节点的索引
uint32_t 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);
}
(s->p[hole_index] = e)->min_heap_idx = hole_index;
}最后对最小堆的一些行为进行封装实现，下面是完整代码：
//minheap.h
#pragma once
#include <cstdint>
struct timer_entry {
uint64_t time; // 时间戳，用来表示定时任务的过期时间
uint32_t min_heap_idx; // 当前节点在堆(数组)中的索引
};
struct min_heap {
timer_entry** p;
uint32_t n; // n 为实际元素个数
uint32_t a; // a 为容量
};
//初始化最小堆
int min_heap_init(min_heap** h, uint32_t a);
//销毁最小堆
int min_heap_free(min_heap* h);
//往最小堆中插入元素
int min_heap_push(min_heap* h, timer_entry* x);
//往最小堆中拿出最小元素
int min_heap_pop(min_heap* h, timer_entry** x);
//获取堆顶元素（不会从堆中删除）
int min_heap_top(min_heap* h, timer_entry** x);// minheap.cpp
#include "minheap.h"
#include <cstdlib>
#define min_heap_elem_greater(a, b) \
((a)->time > (b)->time)
static void min_heap_shift_up_(min_heap* s, uint32_t hole_index, timer_entry* e) {
//计算父节点索引
uint32_t parent = (hole_index - 1) / 2;
//当前插入位置的索引不为0，并且插入位置的父节点的值比当前插入的值大，则交换位置知道这个条件不满足就把插入的元素插入到当前位置
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;
}
(s->p[hole_index] = e)->min_heap_idx = hole_index;
}
static void min_heap_shift_down_(min_heap* s, uint32_t hole_index, timer_entry* e)
{
// 计算右子节点的索引
uint32_t 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);
}
(s->p[hole_index] = e)->min_heap_idx = hole_index;
}
// 堆大小动态增长
static int min_heap_reserve(min_heap* s, uint32_t n) {
if (s->a < n)
{
timer_entry** p;
unsigned a = s->a ? s->a * 2 : 8;
if (a < n)
a = n;
if (!(p = (timer_entry**)realloc(s->p, a * sizeof(*p)))) {
return -1;
}
s->p = p;
s->a = a;
}
return 0;
}
int min_heap_init(min_heap** h, uint32_t a) {
*h = (min_heap*)malloc(sizeof(min_heap));
if(!*h) {
return -1;
}
(*h)->p = (timer_entry**)malloc(a * sizeof(*((*h)->p)));
if(!(*h)->p) {
return -1;
}
(*h)->a = a;
(*h)->n = 0;
return 0;
}
int min_heap_free(min_heap* h) {
if(h) {
return -1;
}
if(h->p) {
free(h->p);
}
free(h);
return 0;
}
int min_heap_push(min_heap* h, timer_entry* x) {
if(min_heap_reserve(h, h->n + 1)) {
return -1;
}
min_heap_shift_up_(h, h->n++, x);
return 0;
}
int min_heap_pop(min_heap* h, timer_entry** x) {
if (h->n)
{
timer_entry* e = *(h->p);
min_heap_shift_down_(h, 0, h->p[--h->n]);
e->min_heap_idx = -1;
*x = e;
return 0;
}
return -1;
}
int min_heap_top(min_heap* h, timer_entry** x) {
if (h->n)
{
timer_entry* e = *(h->p);
*x = e;
return 0;
}
return -1;
}4.封装测试
细心的同学可能注意到，上述最小堆里没有任何业务相关的东西，貌似就是一个什么都不做的最小堆，但看过linux内核的同学应该都知道我要怎么做了，话不多说上代码：
//main.cpp
#include "minheap.h"
#include <cstdint>
#include <iostream>
#include <functional>
#include <chrono>
#include <ctime>
#include <thread>
extern "C"{
#define offsetofs(s,m) (size_t)(&reinterpret_cast<const volatile char&>((((s*)0)->m)))
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetofs(type, member) );})
}
using CallBack = std::function<void(void)>;
struct TimeNode {
timer_entry env;
CallBack cb;
};
class Timer {
public:
Timer(uint32_t size);
Timer() = delete;
~Timer();
int addTimer(uint64_t time, CallBack cb);
void run();
void stop();
private:
uint64_t GetNowTime();
private:
min_heap* _heap;
bool _close;
};
Timer::Timer(uint32_t size) {
min_heap_init(&_heap, size);
_close = false;
}
Timer::~Timer() {
min_heap_free(_heap);
}
int Timer::addTimer(uint64_t time, CallBack cb) {
TimeNode* node = new TimeNode();
node->env.time = GetNowTime() + time;
node->cb = cb;
min_heap_push(_heap, &node->env);
return 0;
}
uint64_t Timer::GetNowTime() {
auto now = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(now.time_since_epoch());
uint64_t timestamp_ms = duration.count();
return timestamp_ms;
}
void Timer::run() {
while(!_close) {
uint64_t now = GetNowTime();
timer_entry* entry = nullptr;
if(!min_heap_top(_heap, &entry)) {
if(entry->time <= now) {
if(!min_heap_pop(_heap, &entry)) {
TimeNode* node = container_of(entry, TimeNode, env);
if(node) {
node->cb();
}
delete node;
}
} else {
std::this_thread::sleep_for(std::chrono::milliseconds(entry->time - now));
}
}
std::this_thread::sleep_for(std::chrono::milliseconds(50));
}
}
void Timer::stop() {
_close = true;
}
int main(int, char**){
Timer timer(10);
auto now = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(now.time_since_epoch());
uint64_t timestamp_ms = duration.count();
std::cout << "Start, now time :" << timestamp_ms << std::endl;
timer.addTimer(1000, [&](void){
auto now = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(now.time_since_epoch());
uint64_t timestamp_ms = duration.count();
std::cout << "timer 1, now time :" << timestamp_ms << std::endl;
});
timer.addTimer(2000, [&](void){
auto now = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(now.time_since_epoch());
uint64_t timestamp_ms = duration.count();
std::cout << "timer 2, now time :" << timestamp_ms << std::endl;
});
std::thread t([&](){
timer.run();
});
std::this_thread::sleep_for(std::chrono::milliseconds(3000));
timer.stop();
t.join();
return 0;
}
我的目标是实现一个通用定时器，里面包含所有定时器的实现方便选择，所以我使用了cmake加clangd加vscode来管理我的工程，目前我的目录结构如下：
ok，现在编译运行看结果
学习参考：0voice · GitHub
标签：index,定时器,min,实现,最小,timer,heap,entry,hole From： https://blog.csdn.net/weixin_55951019/article/details/144171720