c++ 时间轮定时器实现

前言

之所以写这篇文章，是在一篇博客中看到了时间轮定时器这个东西，感觉很是惊艳，https://www.cnblogs.com/zhongwencool/p/timing_wheel.html。在以前写windows 程序的时候，windows API 自己就实现了SetTimer 这个调用，在超时后会触发OnTimer的回调，然后通过timer_id 调用我们自己事件处理函数，但是在后台开发中，一般都需要自己实现，这里根据博客实现了自己的定时器。

实现

头文件定义TimeWheel.h

/************************************************************************/
/* TimeWheel实现了一个毫秒级别的定时器，最大支持到分钟级别                                                                     */
/************************************************************************/

#pragma once
#include<functional>
#include<list>
#include<thread>
#include<mutex>

typedef struct TimePos_
{
	int ms_pos;
	int s_pos;
	int min_pos;
}TimePos;

typedef struct EventInfo_
{
	int interval;
	std::function<void(void)> call_back;
	TimePos time_pos;
	int timer_id;

}EventInfo;

class TimeWheel
{
public:
	TimeWheel();
	~TimeWheel();
public:
	/*step 以毫秒为单位，表示定时器最小时间粒度
	 *max_timer 表示定时器所能接受的分钟时间间隔
	 */
	int InitTimerWheel(int step,int max_min);
	int AddTimer(int interval, std::function<void(void)>& call_back);
	int DeleteTimer(int timer_id);

private:
	int DoLoop();
	int GenerateTimerID();
	int InsertTimer(int diff_ms,EventInfo& einfo);
	int GetNextTrigerPos(int interval,TimePos& time_pos);
	int GetMS(TimePos time_pos);
	int DealTimeWheeling(std::list<EventInfo> leinfo);
private:
	std::list<EventInfo> *_pCallbackList = nullptr;
	std::mutex _mutex;

	TimePos _time_pos;

	int _lowCount = 0;
	int _midCount = 0;
	int _highCount = 0;

	int _step_ms = 0;

	int _timer_count = 0;

};

源文件实现TimerWheel.cpp

#include "TimeWheel.h"
#include <iostream>
#include <windows.h>
using namespace std;

TimeWheel::TimeWheel()
{
	memset(&_time_pos, 0, sizeof(_time_pos));
	
}


TimeWheel::~TimeWheel()
{
}
int TimeWheel::InitTimerWheel(int step_ms, int max_min)
{
	if (1000 % step_ms != 0)
	{
		cout << "step is not property, should be devided by 1000" << endl;
		return -1;
	}
	int msNeedCount = 1000 / step_ms;
	int sNeedCount = 60;
	int minNeedCount = max_min;

	_pCallbackList = new std::list<EventInfo>[msNeedCount + sNeedCount + minNeedCount];
	_step_ms = step_ms;

	_lowCount = msNeedCount;
	_midCount = sNeedCount;
	_highCount = minNeedCount;

	std::thread th([&]{
		this->DoLoop();
	});

	th.detach();
	return 0;
}
int TimeWheel::AddTimer(int interval, std::function<void(void)>& call_back)
{
	if (interval < _step_ms || interval % _step_ms != 0 || interval >= _step_ms * _lowCount * _midCount * _highCount)
	{
		cout << "time interval is invalid" << endl;
		return -1;
	}

	std::unique_lock<std::mutex> lock(_mutex);

	EventInfo einfo = {0};
	einfo.interval = interval;
	einfo.call_back = call_back;
	einfo.time_pos.ms_pos = _time_pos.ms_pos;
	einfo.time_pos.s_pos = _time_pos.s_pos;
	einfo.time_pos.min_pos = _time_pos.min_pos;
	einfo.timer_id = GenerateTimerID();
	 
	InsertTimer(einfo.interval,einfo);

	_timer_count++;

	cout << "insert timer success time_id: " << einfo.timer_id << endl;
	return einfo.timer_id;
}
int TimeWheel::DeleteTimer(int time_id)
{
	std::unique_lock<std::mutex> lock(_mutex);
	int i = 0;
	int nCount = _lowCount + _midCount + _highCount;
	for (i = 0; i < nCount; i++)
	{
		std::list<EventInfo>& leinfo = _pCallbackList[i];
		for (auto item = leinfo.begin(); item != leinfo.end();item++)
		{
			if (item->timer_id == time_id)
			{
				item = leinfo.erase(item);
				return 0;
			}
		}
	}

	if (i == nCount)
	{
		cout << "timer not found" << endl;
		return -1;
	}

	return 0;
}
int TimeWheel::DoLoop()
{
	cout << "........starting loop........" << endl;
	static int nCount = 0;
	while (true)
	{
		this_thread::sleep_for(chrono::milliseconds(_step_ms));
		std::unique_lock<std::mutex> lock(_mutex);
		cout << ".........this is " << ++nCount <<"  loop........."<< endl;
		TimePos pos = {0};
		TimePos last_pos = _time_pos;
		GetNextTrigerPos(_step_ms, pos);
		_time_pos = pos;

		if (pos.min_pos != last_pos.min_pos)
		{
			list<EventInfo>& leinfo = _pCallbackList[_time_pos.min_pos + _midCount + _lowCount];
			DealTimeWheeling(leinfo);
			leinfo.clear();
		}
		else if (pos.s_pos != last_pos.s_pos)
		{
			list<EventInfo>& leinfo = _pCallbackList[_time_pos.s_pos + _lowCount];
			DealTimeWheeling(leinfo);
			leinfo.clear();
		}
		else if (pos.ms_pos != last_pos.ms_pos)
		{
			list<EventInfo>& leinfo = _pCallbackList[_time_pos.ms_pos];
			DealTimeWheeling(leinfo);
			leinfo.clear();
		}
		else
		{
			cout << "error time not change" << endl;
			return -1;
		}
		lock.unlock();
	}
	return 0;
}
int TimeWheel::GenerateTimerID()
{
	int x = rand() % 0xffffffff;
	int cur_time = time(nullptr);
	return x | cur_time | _timer_count;
}

int TimeWheel::InsertTimer(int diff_ms,EventInfo &einfo)
{
	TimePos time_pos = {0};

	GetNextTrigerPos(diff_ms, time_pos);

	if (time_pos.min_pos != _time_pos.min_pos)
		_pCallbackList[_lowCount + _midCount + time_pos.min_pos].push_back(einfo);
	else if (time_pos.s_pos != _time_pos.s_pos)
		_pCallbackList[_lowCount + time_pos.s_pos].push_back(einfo);
	else if (time_pos.ms_pos != _time_pos.ms_pos)
		_pCallbackList[time_pos.ms_pos].push_back(einfo);

	return 0;
}

int TimeWheel::GetNextTrigerPos(int interval, TimePos& time_pos)
{
	int cur_ms = GetMS(_time_pos);
	int future_ms = cur_ms + interval;

	time_pos.min_pos = (future_ms / 1000 / 60) % _highCount;
	time_pos.s_pos = (future_ms % (1000 * 60)) / 1000;
	time_pos.ms_pos = (future_ms % 1000) / _step_ms;

	return 0;
}

int TimeWheel::GetMS(TimePos time_pos)
{
	return _step_ms * time_pos.ms_pos + time_pos.s_pos * 1000 + time_pos.min_pos * 60 * 1000;
}

int TimeWheel::DealTimeWheeling(std::list<EventInfo> leinfo)
{
	for (auto item = leinfo.begin(); item != leinfo.end(); item++)
	{
		int cur_ms = GetMS(_time_pos);
		int last_ms = GetMS(item->time_pos);
		int diff_ms = (cur_ms - last_ms + (_highCount + 1) * 60 * 1000) % ((_highCount + 1) * 60 * 1000);
		if (diff_ms == item->interval)
		{
			item->call_back();

			item->time_pos = _time_pos;
			InsertTimer(item->interval, *item);
		}
		else
		{
			InsertTimer(item->interval - diff_ms, *item);
		}
	}
	return 0;
}

这里实现的是一个毫秒到分钟级别的三成时间轮定时器。InitTimerWheel 中有两个参数，第一个表示支持的最小时间粒度单位毫秒，第二个参数是支持的最大分钟级别。

时钟原理说明：

1.1. 初始化一个三层时间轮:毫秒刻盘：1000/step_ms 个MSList, 秒刻盘：60个SList, 时刻盘：max_min个MinList;

1.2. MSTick由外界推动,每跳一轮(1000/step_ms格),MSTick复位至0,同时STick跳1格;

1.3. 同理STick每跳一轮(60格),STick复位至0,同时MinTick跳1格;

1.4. 最高层：MinTick跳一轮(max_min格）,MinTick复位至0，一个时间轮完整周期完成.

2.事件原理说明：

2.1. 设置时间为TimeOut的事件时,根据TimeOut算出发生此事件时刻的指针位置{TriggerMin,TriggerS,TriggerMS};

2.2. 用{TriggerMin,TriggerS,TriggerMS}与当前指针{NowMin,NowS,NowMS}对比得出事件存放在哪一个指针(Tick);

2.3. 所有层的指针每跳到下一格(Tick01)都会触发格子的事件列表,处理每一个事件Event01：

2.3.1 根据事件Event01的剩余TimeOut算出Event01应该存在上一层(跳得更快)层的位置Pos;

2.3.2 把事件更新到新的Pos(更新TimeOut);

2.3.3 重复处理完Tick01里面所有的事件;

2.3.4 清空Tick01的事件;

2.3.5 最底层(跳最快)层所有的事件遇到指针Tick都会立即执行;

需要指出的是，这里和我所贴的博客中的实现是有点不同的，它所叙述的是一个时分秒级别的定时器，但是我们这里进行了降级，实现的是一个 毫秒，秒，分钟级别的定时器。因为个人感觉，这种级别的定时器使用的概率会更大一些

测试

time_wheel.cpp

#include <iostream>
#include <functional>
#include "TimeWheel.h"
using namespace std;

void fun100()
{
	cout << "func 100" << endl;
}
void fun200()
{
	cout << "func 200" << endl;
}
void fun500()
{
	cout << "func 500" << endl;
}

void fun1500()
{
	cout << "func 1500" << endl;
}

void main()
{	
	std::function<void(void)> f100 = std::bind(&fun100);
	std::function<void(void)> f200 = std::bind(&fun200);
	std::function<void(void)> f500 = std::bind(&fun500);
	std::function<void(void)> f1500 = std::bind(&fun1500);

	TimeWheel time_wheel;
	time_wheel.InitTimerWheel(100, 5);
	int timer1 = time_wheel.AddTimer(100, f100);
	int timer2 = time_wheel.AddTimer(200, f200);
	int timer3 = time_wheel.AddTimer(500, f500);
//	time_wheel.AddTimer(1500, f1500);

	bool b = true;
	int nLoop = 0;
	while (1)
	{
		nLoop++;
		this_thread::sleep_for(chrono::milliseconds(300));
		if (b)
		{
			time_wheel.AddTimer(1500, f1500);
			b = false;
		}
		if (nLoop == 3)
			time_wheel.DeleteTimer(timer1);
	}
}

结语