首页 > 代码库 > 服务器开发之定时器

服务器开发之定时器

写这篇文章前搜了下网上类似的文章,有很多,所以笔者的这篇文章就不对定时器的常见实现方法加以说明,也不进行性能比较,直接上代码。

基于multimap实现的比较简单,这里略过。

1 最小堆实现

// head file //////////////////////////////////////////////////////////////////#pragma once#include <vector>#include <boost/function.hpp>class TimerManager;class Timer{public:	enum TimerType { ONCE, CIRCLE };	Timer(TimerManager& manager);	~Timer();	template<typename Fun>	void Start(Fun fun, unsigned interval, TimerType timeType = CIRCLE);	void Stop();private:	void OnTimer(unsigned long long now);private:	friend class TimerManager;	TimerManager& manager_;	TimerType timerType_;	boost::function<void(void)> timerFun_;	unsigned interval_;	unsigned long long expires_;	size_t heapIndex_;};class TimerManager{public:	static unsigned long long GetCurrentMillisecs();private:	friend class Timer;    void AddTimer(Timer* timer);    void RemoveTimer(Timer* timer);    void DetectTimers();    void UpHeap(size_t index);    void DownHeap(size_t index);    void SwapHeap(size_t, size_t index2);private:    struct HeapEntry    {        unsigned long long time;        Timer* timer;    };    std::vector<HeapEntry> heap_;};template<typename Fun>inline void Timer::Start(Fun fun, unsigned interval, TimerType timeType){	Stop();	interval_ = interval;	timerFun_ = fun;	timerType_ = timeType;	timer->expires_ = timer->interval_ + TimerManager::GetCurrentMillisecs();	manager_.AddTimer(this);}// cpp file //////////////////////////////////////////////////////////////////#define _CRT_SECURE_NO_WARNINGS#include "config.h"#include "timer.h"#ifdef _MSC_VER # include <sys/timeb.h>#else# include <sys/time.h>#endif//////////////////////////////////////////////////////////////////////////// TimerTimer::Timer(TimerManager& manager)	: manager_(manager)	, heapIndex_(-1){}Timer::~Timer(){	Stop();}void Timer::Stop(){	if (heapIndex_ != -1)	{		manager_.RemoveTimer(this);		heapIndex_ = -1;	}}void Timer::OnTimer(unsigned long long now){	if (timerType_ == Timer::CIRCLE)	{		expires_ = interval_ + now;		manager_.AddTimer(this);	}	else	{		heapIndex_ = -1;	}	timerFun_();}//////////////////////////////////////////////////////////////////////////// TimerManagervoid TimerManager::AddTimer(Timer* timer){    timer->heapIndex_ = heap_.size();    HeapEntry entry = { timer->expires_, timer };    heap_.push_back(entry);    UpHeap(heap_.size() - 1);}void TimerManager::RemoveTimer(Timer* timer){    size_t index = timer->heapIndex_;    if (!heap_.empty() && index < heap_.size())    {        if (index == heap_.size() - 1)        {            heap_.pop_back();        }        else        {            SwapHeap(index, heap_.size() - 1);            heap_.pop_back();            size_t parent = (index - 1) / 2;            if (index > 0 && heap_[index].time < heap_[parent].time)                UpHeap(index);            else                DownHeap(index);        }    }}void TimerManager::DetectTimers(){    unsigned long long now = GetCurrentMillisecs();    while (!heap_.empty() && heap_[0].time <= now)    {        Timer* timer = heap_[0].timer;        RemoveTimer(timer);        timer->OnTimer(now);    }}void TimerManager::UpHeap(size_t index){    size_t parent = (index - 1) / 2;    while (index > 0 && heap_[index].time < heap_[parent].time)    {        SwapHeap(index, parent);        index = parent;        parent = (index - 1) / 2;    }}void TimerManager::DownHeap(size_t index){    size_t child = index * 2 + 1;    while (child < heap_.size())    {        size_t minChild = (child + 1 == heap_.size() || heap_[child].time < heap_[child + 1].time)            ? child : child + 1;        if (heap_[index].time < heap_[minChild].time)            break;        SwapHeap(index, minChild);        index = minChild;        child = index * 2 + 1;    }}void TimerManager::SwapHeap(size_t index1, size_t index2){    HeapEntry tmp = heap_[index1];    heap_[index1] = heap_[index2];    heap_[index2] = tmp;    heap_[index1].timer->heapIndex_ = index1;    heap_[index2].timer->heapIndex_ = index2;}unsigned long long TimerManager::GetCurrentMillisecs(){#ifdef _MSC_VER 	_timeb timebuffer;	_ftime(&timebuffer);	unsigned long long ret = timebuffer.time;	ret = ret * 1000 + timebuffer.millitm;	return ret;#else	timeval tv;          	::gettimeofday(&tv, 0);	unsigned long long ret = tv.tv_sec;	ret = ret * 1000 + tv.tv_usec / 1000;#endif}

 

2 时间轮实现

// header file //////////////////////////////////#pragma once#include <list>#include <vector>#include <boost/function.hpp>class TimerManager;class Timer{public:	enum TimerType {ONCE, CIRCLE};	Timer(TimerManager& manager);	~Timer();	template<typename Fun>	void Start(Fun fun, unsigned interval, TimerType timeType = CIRCLE);	void Stop();private:	void OnTimer(unsigned long long now);private:	friend class TimerManager;	TimerManager& manager_;	TimerType timerType_;	boost::function<void(void)> timerFun_;	unsigned interval_;	unsigned long long expires_;	int vecIndex_;	std::list<Timer*>::iterator itr_;};class TimerManager{public:	TimerManager();	static unsigned long long GetCurrentMillisecs();private:	friend class Timer;	void AddTimer(Timer* timer);	void RemoveTimer(Timer* timer);	void DetectTimers();	int Cascade(int offset, int index);private:	typedef std::list<Timer*> TimeList;	std::vector<TimeList> tvec_;	unsigned long long checkTime_;};template<typename Fun>inline void Timer::Start(Fun fun, unsigned interval, TimerType timeType){	Stop();	interval_ = interval;	timerFun_ = fun;	timerType_ = timeType;	expires_ = interval_ + TimerManager::GetCurrentMillisecs();	manager_.AddTimer(this);}// cpp file //////////////////////////////////////////////////#define _CRT_SECURE_NO_WARNINGS#include "config.h"#include "timer2.h"#ifdef _MSC_VER # include <sys/timeb.h>#else# include <sys/time.h>#endif#define TVN_BITS 6#define TVR_BITS 8#define TVN_SIZE (1 << TVN_BITS)#define TVR_SIZE (1 << TVR_BITS)#define TVN_MASK (TVN_SIZE - 1)#define TVR_MASK (TVR_SIZE - 1)#define OFFSET(N) (TVR_SIZE + (N) *TVN_SIZE)#define INDEX(V, N) ((V >> (TVR_BITS + (N) *TVN_BITS)) & TVN_MASK)//////////////////////////////////////////////////////////////////////////// TimerTimer::Timer(TimerManager& manager)	: manager_(manager)	, vecIndex_(-1){}Timer::~Timer(){	Stop();}void Timer::Stop(){	if (vecIndex_ != -1)	{		manager_.RemoveTimer(this);		vecIndex_ = -1;	}}void Timer::OnTimer(unsigned long long now){	if (timerType_ == Timer::CIRCLE)	{		expires_ = interval_ + now;		manager_.AddTimer(this);	}	else	{		vecIndex_ = -1;	}	timerFun_();}//////////////////////////////////////////////////////////////////////////// TimerManagerTimerManager::TimerManager(){	tvec_.resize(TVR_SIZE + 4 * TVN_SIZE);	checkTime_ = GetCurrentMillisecs();}void TimerManager::AddTimer(Timer* timer){	unsigned long long expires = timer->expires_;    unsigned long long idx = expires - checkTime_;      if (idx < TVR_SIZE)	{		timer->vecIndex_ = expires & TVR_MASK;    }	else if (idx < 1 << (TVR_BITS + TVN_BITS))	{        timer->vecIndex_ = OFFSET(0) + INDEX(expires, 0);    }	else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS))	{        timer->vecIndex_ = OFFSET(1) + INDEX(expires, 1);    }	else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS))	{		timer->vecIndex_ = OFFSET(2) + INDEX(expires, 2);    }	else if ((long long) idx < 0)	{		timer->vecIndex_ = checkTime_ & TVR_MASK;    }	else	{            if (idx > 0xffffffffUL)		{            idx = 0xffffffffUL;            expires = idx + checkTime_;        }		timer->vecIndex_ = OFFSET(3) + INDEX(expires, 3);    }	TimeList& tlist = tvec_[timer->vecIndex_];	tlist.push_back(timer);	timer->itr_ = tlist.end();	--timer->itr_;}void TimerManager::RemoveTimer(Timer* timer){	TimeList& tlist = tvec_[timer->vecIndex_];	tlist.erase(timer->itr_);}void TimerManager::DetectTimers(){	unsigned long long now = GetCurrentMillisecs();	while (checkTime_ <= now)	{		int index = checkTime_ & TVR_MASK;		if (!index &&			!Cascade(OFFSET(0), INDEX(checkTime_, 0)) &&			!Cascade(OFFSET(1), INDEX(checkTime_, 1)) &&			!Cascade(OFFSET(2), INDEX(checkTime_, 2)))		{			Cascade(OFFSET(3), INDEX(checkTime_, 3));		}		++checkTime_;		TimeList& tlist = tvec_[index];		TimeList temp;		temp.splice(temp.end(), tlist);		for (TimeList::iterator itr = temp.begin(); itr != temp.end(); ++itr)		{			(*itr)->OnTimer(now);		}	}}int TimerManager::Cascade(int offset, int index){	TimeList& tlist = tvec_[offset + index];	TimeList temp;	temp.splice(temp.end(), tlist);	for (TimeList::iterator itr = temp.begin(); itr != temp.end(); ++itr)	{		AddTimer(*itr);	}	return index;}unsigned long long TimerManager::GetCurrentMillisecs(){#ifdef _MSC_VER 	_timeb timebuffer;	_ftime(&timebuffer);	unsigned long long ret = timebuffer.time;	ret = ret * 1000 + timebuffer.millitm;	return ret;#else	timeval tv;          	::gettimeofday(&tv, 0);	unsigned long long ret = tv.tv_sec;	ret = ret * 1000 + tv.tv_usec / 1000;#endif}

 

结束语

在曾经的很多项目中,定时器的实现都是使用map,也许效率不是太高,却从来没有成为性能的瓶颈。但是程序员通常是追求完美的,既然有更好解决方案,且其实现又不那么复杂,那就完全可以去尝试。

 

申明

笔者自称从来不创造代码,只是代码的搬运工,例如上面最小堆是从boost中搬过来的,时间轮是从linux内核定时器中搬过来的,既然如此如果您愿意,这里代码也可以随意使用(笔者其它博客里的代码也一样),不需要笔者知晓或同意,如果您发现有什么bug或建议也请联系我。

服务器开发之定时器