李邦柱
helpylee@126.com
1. 定时器简介
定时器通常包含至少两个成员：一个超时时间（通常采用相对时间或者超时时间）和一个超时时间到达后的一个回调函数。有时候还可能包含回调函数被执行时需要传入的参数，以及是否重新启动定时器，更改定时器的超时时间等。如果使用链表作为容器来串联所有的定时器，则每个定时器还要包含指向下一个定时器的指针成员。进一步，如果链表是双向的，则每个定时器还需要包含指向前一个定时器的指针成员。
2. 升序定时器链表的实现
#ifndef LST_TIMER
#define LST_TIMER
#include<time.h>
#define BUFFER_SIZE 64
class Timer;/*向前声明*/*/
/*用户数据结构，包含ip,端口，文件描述符，读缓存，以及定时器*/
struct client_data
{
char ip[BUFFER_SIZE];
int port;
int sockfd;
char buf[BUFFER_SIZE];
Timer *timer;
};
/*定时器类*/
class Timer
{
public:
Timer():prev(NULL),next(NULL){}
public:
time_t expire;/*任务的超时时间，此处使用绝对时间*/
client_data* user_data;
void (*cb_func)(client_data*);/*任务回调函数*/
Timer* prev;/*指向前一个定时器*/
Timer* next;/*指向后一个定时器*/
void* arg; /*可根据需要进行扩展使用*/
};
/*定时器链表，它是一个升序，双向链表，且带有头节点和尾节点*/
class sort_timer_lst
{
public:
sort_timer_lst():head(NULL),tail(NULL){}
~sort_timer_lst()/*链表被销毁的时候，删除所有的定时器*/
{
Timer* tmp =head;
while(tmp)
{
head=tmp->next;
delete tmp;
tmp =head;
}
}
void add_timer(Timer* timer);/*将目标定时器添加到链表中*/
bool find_timer(Timer* timer);/*查找目标定时器*/
void del_timer(Timer* timer);/*删除目标定时器*/
void adjust_timer(Timer* timer);/*当某个定时任务发生变化时，调整对应的定时器在链表的位置，此函数之考的向后调整*/
void tick();
private:
void add_timer(Timer* timer,Timer* head);
private:
Timer* head;
Timer* tail;
};
#endif
lst_timer.cpp
#include"lst_timer.h"
void sort_timer_lst::add_timer(Timer* timer)
{
if(!timer) return;
if(!head)
{
head= tail =timer;
return ;
}
if(timer->expire < head->expire)
{
timer->next = head;
head ->prev = timer;
head = timer;
return ;
}
add_timer(timer,head);
}
bool sort_timer_lst:: find_timer(Timer* timer)
{
Timer* tmp = head;
while(tmp)
{
if(strcmp(tmp->user_data->stb_id , timer->user_data->stb_id)==0)
{
return true;
}
tmp = tmp->next;
}
if(!tmp)
return false;
}
void sort_timer_lst::adjust_timer(Timer*timer)
{
if(!timer)
return;
Timer*tmp = timer->next;
if(!tmp||timer->expire<tmp->expire)
return;
if(timer==head)
{
head = head->next;
head->prev =NULL;
timer->next = NULL;
add_timer(timer,head);
}
else
{
timer ->prev->next = timer ->next;
timer ->next->prev = timer->prev;
add_timer(timer,timer->next);
}
}
void sort_timer_lst::del_timer(Timer* timer)
{
if(!timer)
return;
/*下面条件成立，表示只有一个定时器，即目标定时器*/
if((timer ==head)&&(timer ==tail))
{
delete timer;
head = NULL;
tail = NULL;
return ;
}
/*如果链表至少有两个定时器，且目标定时器恰好是头结点*/
if(timer == head)
{
head =head->next;
head->prev=NULL;
delete timer;
return;
}
/*如果链表至少有两个定时器，目标定时器恰好是尾节点*/
if(timer ==tail)
{
tail = tail ->prev;
tail ->next =NULL;
delete timer;
return;
}
/*目标定时器如果位于链表头尾之间，则把它前后的定时器串联起来，然后删除目标定时器*/
timer->prev ->next =timer ->next;
timer->next->prev = timer ->prev ;
delete timer;
}
/*主要通过此函数不断检测时候有定时器超时*/
void sort_timer_lst::tick()
{
if(!head ) return;
time_t cur = time(NULL);
Timer* tmp = head;
while(tmp)
{
if(cur<tmp->expire)
break;
tmp->cb_func(tmp->user_data);/*执行定时器回调函数*/
head=tmp->next;
if(head)
head->prev = NULL;
delete tmp;
tmp = head;
}
}
void sort_timer_lst:: add_timer(Timer* timer,Timer* head)
{
Timer* prev = head;
Timer* tmp = prev->next;
while(tmp)
{
if(timer->expire<tmp->expire)
{
prev->next =timer ;
timer->next = tmp;
tmp ->prev = timer;
timer ->prev = prev;
break;
}
prev = tmp;
tmp =tmp->next;
}
if(!tmp)
{
prev->next = timer;
timer->prev = prev;
timer->next =NULL;
tail = timer;
}
}
3. 性能分析
Sort_timer_lst是一个升序链表，其核心函数是tick,相当于一个脉搏，让它每隔一段时间就执行一次，以检测并处理到期的任务。判定定时任务到期的依据是定时的expire值小于或者等于当前时间。从执行效率上看添加定时器的任务的时间复杂度为O(n),删除定时器的时间复杂度为O(1),执行任务的时间复杂度是O(1).
4. 其他高性能定时器
基于排序链表的定时器存在一个效率的问题，添加定时器的效率偏低，因此可以使用时间轮或者时间堆来解决这个问题。有兴趣的朋友可以学习下时间轮和时间堆。
5. 更多内容，请前往个人文库
http://wenku.baidu.com/p/helpylee
