首页 > 代码库 > 基于升序定时器的时间链表

基于升序定时器的时间链表

                                   李邦柱

                                                       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