首页 > 代码库 > 服务器开发之定时器
服务器开发之定时器
写这篇文章前搜了下网上类似的文章,有很多,所以笔者的这篇文章就不对定时器的常见实现方法加以说明,也不进行性能比较,直接上代码。
基于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或建议也请联系我。
服务器开发之定时器
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。