本文主要是介绍高性能定时器 --- 时间堆,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
时间堆时间轮给我们的感觉依旧不够精细,因为它是按照时间间隔来执行定时器的。
时间堆的设计思路是:
将所有定时器中超时时间最小的定时器的超时值作为心博间隔。一旦心博函数被调用,超时时间最小的定时器必然到期,我们就可以准确的处理它。然后,再从剩余的定时器中找出超时时间最小的那个,作为下一次心博时间,这样,就显得较为精准了。
这里我们采用最小堆处理这个问题。
#ifndef MIN_HEAP_TIMER
#define MIN_HEAP_TIMER#include <stdio.h>
#include <netinet/in.h>
#include <time.h>#define BUF_SIZE 64struct client_date
{struct sockaddr_in cd_address;int cd_sockfd;char cd_buf[BUFF_SIZE];mh_timer* cd_timer; //每个连接都拥有的一个定时器
};class heap_timer
{
public:time_t expire;client_date *user_data;time_heap(int delay){expire = time(NULL)+delay;}void (*cb_func)(client_date*);
};class time_heap
{
private:heap_timer **array; //一个指针数组int capacity;int cur_size;public://第一种构造函数//初始化一个给定大小的空堆time_heap(int cap):capacity(cap),cur_size(0){array = new heap_timer*[cap];if(NULL == array)exit(1);for(int i=0; i<cap; i++)array[i] = NULL;}//第二种构造函数//用已有数组来构造堆time_heap(heap_timer **init_array, int cap, int size):capacity(cap),cur_size(size){if(NULL == init_array || size<cap)exit(1);array = new heap_timer*[cap];if(NULL == array)exit(1);for(int i=0; i<cap; i++)array[i] = NULL; if(size != 0){for(int i=0; i<size; i++)array[i] = init_array[i];for(int i=(cur_size-1)/2; i>=0; i--) //对整个堆进行调整(调整的对象是拥有子节点的所有节点)adjust_down(i);}}//析构函数~time_heap(){for(int i=0; i<cur_size; i++)delete array[i];delete[] array;}//添加目标定时器void add_timer(heap_timer *timer){if(NULL == timer)return;if(cur_size >= capacity)resize();cur_size ++;int s = cur_size;int parent;for(; s>0; s=parent){parent = (s-1)/2;//因为是添加进来的,之前部分是排好的。所以只要跟parent比比,一直往上不断比就可以了if(array[parent]->expire > array[s])array[s] = array[parent];elsebreak; }array[s] = timer;}//删除目标定时器void void del_timer(heap_timer *timer){if(NULL == timer)return;//这是书上的方法,简单,但是容易导致膨胀(不过这种数据结构一般不会突然删某个,而是删顶部元素的)timer->cb_func = NULL;//复杂点的话就是先得知这个节点下标是哪个,然后让最后一个顶替它,对这个节点进行 adjust_down() 操作}//获取顶部定时器heap_timer *top(){if(!empty())return array[0];return NULL;}//删除顶部定时器void del_top(){if(empty())return;if(array[0]){delete array[0];array[0] = array[--cur_size];adjust_down(array[0]);}}//心搏函数void tick(){heap_timer* tmp = array[0];time_t cur = time(NULL);while(!empty()){if(!tmp)break;if(tmp->expire > cur)break;if(tmp->cb_func)tmp->cb_func(tmp->user_data);del_top();tmp = array[0];}}bool empty(){return cur_size==0;}//调整函数(向下)void adjust_down(int s){heap_timer *tmp = array[s];int child;//for循环的条件是: 至少s的左子节点存在(比如s为0,至少孩子节点1要存在,才需要调整,否则没有子节点是不需要调整的)for(; s*2+1<=cur_size-1; ){child = s*2+1;//第一个条件满足说明s的右子节点也存在//第二个条件说明s的右子节点小于左子节点,从而代替左子节点和s节点进行比较if((child<cur_size-1) && (array[child+1]->expire < array[child]->expire))child++;//如果s节点果真大于子节点,那么s节点的位置就要由该子节点来代替//因为有tmp变量指向原s节点,所以这里可以直接覆盖,且接下来要调整的对象就是原s节点现在所处的环境if(tmp->expire > array[child]->expire){array[s] = array[child];s = child;}elsebreak;}array[s] = tmp;}//扩大堆数组的容量void resize(){heap_timer *temp = new heap_timer*[2*capacity];if(NULL == temp)exit(1);for(int i=0; i<2*capacity; i++)temp[i] = NULL;capacity = 2*capacity;for(int i=0; i<cur_size; i++)temp[i] = array[i];delete[] array;array = temp;}
};
这篇关于高性能定时器 --- 时间堆的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!