定时器（linux）
网络程序需要处理定时事件，比如定期检测一个客户连接的活动状态。服务器通常管理着众多定时事件，因此有效的组织这些定时事件，使之能在预期的时间点被触发且不影响服务器的主要逻辑，对于服务器性能有着至关重要的影响。为此我们要将每个定时事件分别封装成定时器，并使用某种容器类数据结构，比如链表、排序链表和时间轮，将所有定时器串联起来，以实现对定时事件的统一管理。
LINUX提供了三种定时方法
- socket选项SO_RCVTIMEO和SO_SNDTIMEO
由表可见，我们可以根据系统调用send,recv,accept,connect的返回值和errno来判断超时时间是否已到，进而决定是否开始处理定时任务。下列代码以connect为例，说明程序如何使用SO_SNDTIMEO选项来定时
/*设置超时时间*/
#ifndef _HEAD_H
#define _HEAD_H
#include<iostream>
#include<sys/types.h>
#include<fcntl.h>
#include<sys/socket.h>
#include<netinet/in.h>
#include<arpa/inet.h>
#include<assert.h>
#include<unistd.h>
#include<string.h>
#include<netdb.h>
#include<sys/epoll.h>
#include<pthread.h>
void my_err(std::string str, int line)
{
fprintf(stderr, "line: %d\n", line);
std::cerr << str << std::endl;
exit(0);
}
#endif
#include"head.hpp"
#include<errno.h>
/*超时连接函数*/
int timeout_connect(const char *ip, int port, int time)
{
int ret = 0;
struct sockaddr_in serv;
memset(&serv, 0, sizeof(serv));
serv.sin_family = AF_INET;
serv.sin_port = htons(port);
inet_pton(AF_INET, ip, &serv.sin_addr);
int sockfd = socket(AF_INET, SOCK_STREAM, 0);
struct timeval timeout;
timeout.tv_sec = time;
timeout.tv_usec = 0;
socklen_t len = sizeof(timeout);
/*通过选项SO_RCVTIMEO和SO_SNDTIMEO所设置的超时时间的类型是timeval, 这和select系统调用的超时参数类型相同*/
ret = setsockopt(sockfd, SOL_SOCKET, SO_SNDTIMEO, &timeout, len);
ret = connect(sockfd, (struct sockaddr*)&serv, sizeof(serv));
if(ret == -1)
{
/*超时对应的错误号是EINPROGRESS。下面这个条件如果成立，我们就可以处理定时任务了*/
if(errno == EINPROGRESS)
{
printf("connecting timeout, process timeout logic\n");
return -1;
}
printf("error occur when connecting to server\n");
return -1;
}
return sockfd;
}
- SIGALRM
我们由alarm和setitimer函数设置的定时闹钟一旦超时，将触发SIGALRM信号。因此，我们可以利用该信号的信号处理函数来处理定时任务。但是，如果要处理多个定时任务，我们就需要不断的触发SIGALRM信号，并在其信号处理函数中执行到期的任务。一般而言，SIGALRM信号按照固定的频率生成，既由alarm和setitimer函数设置的定时周期T保持不变。如果某个定时任务的超时时间不是T的整数倍，那么它实际被执行的事件和预期的时间略有偏差。因此定时周期T反映了定时的精度。
我们将实现一个简单地定时器——基于升序链表的定时器。
基于升序链表的定时器
定时器通常包含两个成员：一个超时时间（相对时间或者绝对时间）和一个任务回调函数。
下面是代码的实现linux环境下
#ifndef LST_TIMER
#define LST_TIMER
#include"head.hpp"
#include<time.h>
#define BUFFER_SIZE 64
class util_timer;
/*用户数据结构： 客户端socket地址 文件描述符 读缓存和定时器*/
struct client_data
{
struct sockaddr_in address;
int sockfd;
char buf[BUFFER_SIZE];
util_timer* timer;
};
/*定时器类*/
class util_timer
{
public:
util_timer() : prev(NULL), next(NULL) {}
public:
time_t expier; //任务的超时时间，这里使用绝对时间
void (*cb_func)(client_data*); //任务回调函数
client_data *user_data;
util_timer* prev; //指向前一个定时器
util_timer* next; //指向后一个定时器
};
/*定时器链表。 它是一个升序，双向链表且带有头结点和尾节点*/
class sort_timer_lst
{
public:
sort_timer_lst() : head(NULL), tail(NULL) {}
/*链表被销毁时，删除其中所有的定时器*/
~sort_timer_lst()
{
util_timer* tmp = head;
while(tmp)
{
head = tmp->next;
delete tmp;
tmp = head;
}
}
/*将目标定时器timer添加到链表中*/
void add_timer(util_timer* timer);
/*当某个定时器的任务发生变化时，调整对应的定时器在链表中的位置。*/
void adjust_timer(util_timer* timer);
/*将目标定时器timer从链表中移除*/
void del_timer(util_timer* timer);
/*SIGALRM信号每次被触发就在其信号处理函数（如果使用统一事件源，则是主函数）中执行一次tick函数，以处理链表上到期的任务*/
void tick();
/*重载的add_timer函数，它被公有的add_timer函数和adjust_timer的函数调用。
该函数表示将目标定时器timer添加到节点lst_head之后的节点lst_head之后的部分链表中*/
void add_timer(util_timer* timer, util_timer* lst_head);
public:
util_timer* head;
util_timer* tail;
};
/*将目标定时器timer添加到链表中*/
void sort_timer_lst::add_timer(util_timer* timer)
{
if(!timer)
{
return;
}
if(!head) //如果链表中无节点
{
head = tail = timer;
return;
}
/*如果目标定时器的超时时间小于当前链表中所有定时器的超时时间，则把该节点插入到链表头节点。
否则就需要调用重载函数add_timer(util_timer* timer, util_timer* lst_head), 把它插入链表中合适的位置，以保证链表的升序特性*/
if(timer->expier < head->expier)
{
timer->next = head;
head = timer;
head = timer;
return;
}
add_timer(timer, head);
}
/*当某个定时器的任务发生变化时，调整对应的定时器在链表中的位置。*/
void sort_timer_lst::adjust_timer(util_timer* timer)
{
if(!timer)
return;
/*当需要调整时，我们只需将此节点从链表中取出，然后重新插入*/
// util_timer* prev = timer->prev;
// util_timer* next = timer->next;
timer->prev->next = timer->next;
timer->next->prev = timer->prev;
timer->prev = timer->next = NULL;
add_timer(timer);
}
/*将目标定时器timer从链表中移除*/
void sort_timer_lst::del_timer(util_timer* timer)
{
if(!timer)
return;
/*下面这个条件成立表示链表只有一个定时器，既目标定时器*/
if( (timer == head) && (timer == tail) )
{
delete timer;
head = tail = nullptr;
return;
}
/*如果目标至少存在两个定时器，且目标定时器是链表的头结点，则将链表的头结点重置为原头结点的下一个节点，然后删除目标定时器*/
if(timer == head)
{
head = timer->next;
head->prev = nullptr;
delete timer;
return;
}
/*如果目标至少存在两个定时器，且目标定时器是链表的尾结点，则将链表的尾结点重置为原尾结点的上一个节点，然后删除目标定时器*/
if(timer == tail)
{
tail = tail->prev;
tail->next = nullptr;
delete timer;
return;
}
/*如果目标定时器位于链表的中间，则把它前后的定时器串联起来，然后删除目标定时器*/
timer->prev->next = timer->next;
timer->next->prev = timer->prev;
delete timer;
return;
}
/*SIGALRM信号每次被触发就在其信号处理函数（如果使用统一事件源，则是主函数）中执行一次tick函数，以处理链表上到期的任务*/
void sort_timer_lst::tick()
{
if(!head)
return;
printf("timer tick\n");
time_t cur = time(NULL); //获得系统的当前时间
util_timer* tmp = head;
/*从头结点开始依次处理每个定时器，直到遇到一个尚未到期的定时器，这就是定时器的核心逻辑*/
while(tmp)
{
/*因为每个定时器都使用绝对时间作为超时值，所以我们可以把定时器的超时值和系统当前时间比较以判断定时器是否到期*/
if(cur < tmp->expier)
return;
/*调用定时器的回调函数，以执行定时任务*/
tmp->cb_func(tmp->user_data);
/*执行完定时器中的定时任务之后，就将它从链表中删除，并重置头结点*/
head = tmp->next;
if(head)
head->prev = nullptr;
delete tmp;
tmp = head;
}
}
/*重载的add_time函数*/
void sort_timer_lst::add_timer(util_timer* timer, util_timer* lst_head)
{
util_timer* prev = lst_head;
util_timer* tmp = lst_head->next;
/*遍历lst_head节点之后的部分链表，直到找到一个超时时间大于目标定时器的超时时间的节点，并将目标定时器插入到该节点之前*/
while(tmp)
{
if(timer->expier < tmp->expier)
{
timer->next =tmp;
prev->next = timer;
timer->prev = prev;
tmp->prev = timer;
break;
}
prev =tmp;
tmp = tmp->next;
}
/*如果遍历完都没有插入，则将其插入到尾节点*/
tmp = timer;
prev->next = tmp;
tmp->prev = prev;
tmp->next = nullptr;
tail = tmp;
}
#endif
/*处理非活动连接*/
#include"head.hpp"
#include"lst_timer.hpp"
#include<signal.h>
#define FD_LIMIT 65535
#define MAX_EVENT_NUMBER 1024
#define TIMESLOT 5
/*统一事件源处理信号 创建管道加入到epoll中*/
static int pipefd[2];
static sort_timer_lst timer_lst;
static int epollfd = 0;
/*将socket设置为非阻塞的*/
int setnonblocking(int fd)
{
int old_option = fcntl(fd, F_GETFL);
int new_option = old_option | O_NONBLOCK;
fcntl(fd, F_SETFL, new_option);
return old_option;
}
/*设置epoll参数*/
void addfd(int epollfd, int fd)
{
epoll_event event;
event.data.fd = fd;
event.events = EPOLLIN | EPOLLET;
epoll_ctl(epollfd, EPOLL_CTL_ADD, fd, &event);
setnonblocking(fd);
}
void sig_handler(int sig)
{
int save_errno = errno;
int msg = sig;
send(pipefd[1], (char *)&msg, 1, 0);
errno = save_errno;
}
void addsig(int sig)
{
struct sigaction sa;
memset(&sa, '\0', sizeof(sa));
sa.sa_handler = sig_handler;
sa.sa_flags |= SA_RESTART;
sigfillset(&sa.sa_mask);
assert(sigaction(sig, &sa, NULL) != -1);
}
void timer_handler()
{
/*定时处理任务，实际上就是调用tick函数*/
timer_lst.tick();
/*因为一次alarm调用只会引起一次SIGALRM信号，所以我们重新定时，以不断触发SIGALRM信号*/
alarm(TIMESLOT);
}
/*定时器回调函数，它删除非活动连接socket上的注册事件，并关闭之*/
void cb_func(client_data* user_data)
{
epoll_ctl(epollfd, EPOLL_CTL_DEL, user_data->sockfd, 0);
assert(user_data);
close(user_data->sockfd);
printf("close fd %d\n", user_data->sockfd);
}
int main(int argc, char* argv[])
{
if(argc <= 2)
my_err("command list", __LINE__);
const char* ip = argv[1];
int port = atoi(argv[2]);
int ret = 0;
struct sockaddr_in address;
memset(&address, 0, sizeof(address));
address.sin_family = AF_INET;
address.sin_port = htonl(port);
inet_pton(AF_INET, ip, &address.sin_addr);
int listenfd = socket(AF_INET, SOCK_STREAM, 0);
if(listenfd < 0)
my_err("socket", __LINE__);
ret = bind(listenfd, (struct sockaddr*)&address, sizeof(address));
if(ret < 0)
my_err("bind", __LINE__);
ret = listen(listenfd, 5);
if(ret < 0)
my_err("listen", __LINE__);
epoll_event events[MAX_EVENT_NUMBER];
epollfd = epoll_create(5);
addfd(epollfd, listenfd);
/*设置信号处理函数*/
addsig(SIGALRM);
addsig(SIGTERM);
bool stop_server = false;
client_data* users = new client_data[FD_LIMIT];
bool timeout = false;
alarm(TIMESLOT); //定时
while(!stop_server)
{
int number = epoll_wait(epollfd, events, MAX_EVENT_NUMBER, -1); //阻塞
if( (number < 0) && (errno != EINTR) )
my_err("epoll_wait", __LINE__);
for(int i = 0; i < number; ++i)
{
int sockfd = events[i].data.fd;
/*处理新到客户连接 */
if(sockfd == listenfd)
{
struct sockaddr_in client;
memset(&client, 0, sizeof(client));
socklen_t client_len = sizeof(client);
int connfd = accept(listenfd, (struct sockaddr*)&client, &client_len);
//将新的连接加入到epoll事件集中
addfd(epollfd, connfd);
users[connfd].address = client;
users[connfd].sockfd = connfd;
/*创建定时器，设置其回调函数与超时时间，然后绑定定时器与用户数据，最后将定时器添加到链表lst中*/
util_timer* timer = new util_timer;
timer->user_data = &users[connfd];
timer->cb_func = cb_func;
time_t cur = time(NULL);
timer->expier = cur + 3 * TIMESLOT;
users[connfd].timer = timer;
timer_lst.add_timer(timer);
}
/*处理信号*/
else if( (sockfd == pipefd[0]) && (sockfd & EPOLLIN))
{
int sig;
char signals[1024];
ret = recv(sockfd, signals, sizeof(signals), 0);
if(ret == -1)
{
continue;
}
else if(ret == 0)
continue;
else
{
for(int i = 0; i < ret; ++i)
{
switch(signals[i])
{
case SIGALRM:
{
/*用timeout变量标记有定时任务需要处理，但不立即处理定时任务。
这是因为定时任务的优先级不是很高，我们优先处理其它更重要的任务*/
timeout = true;
break;
}
case SIGTERM:
{
stop_server = true;
}
}
}
}
}
/*处理客户连接上收到的数据*/
else if(sockfd & EPOLLIN)
{
memset(users[sockfd].buf, '\0', BUFFER_SIZE);
ret = recv(sockfd, users[sockfd].buf, BUFFER_SIZE - 1, 0);
printf("get %d bytes of client data %s from %d\n", ret, users[sockfd].buf, sockfd);
util_timer* timer = users[sockfd].timer;
if(ret < 0)
{
/*如果发生读错误，则关闭连接，并移除其对应的定时器*/
if(errno != EAGAIN)
{
cb_func(&users[sockfd]);
if(timer)
timer_lst.del_timer(timer);
}
}
else if(ret == 0)
{
/*如果对方已经关闭连接，则我们也关闭连接，并移除对应的定时器*/
cb_func(&users[sockfd]);
if(timer)
timer_lst.del_timer(timer);
}
else
{
/*如果某个客户连接上有数据可读，则我们要调整该连接对应的定时器，以延迟该连接被关闭时间*/
if(timer)
{
time_t cur = time(NULL);
timer->expier = cur + 3 * TIMESLOT;
printf("adjust time once\n");
timer_lst.adjust_timer(timer);
}
}
}
}
/*最后处理定时事件，因为I/O事件有更高的优先级。当然，这样做将导致定时任务不能精确地按照预期的时间执行*/
if(timeout)
{
timer_handler();
timeout = false;
}
}
close(listenfd);
close(pipefd[0]);
close(pipefd[1]);
delete []users;
return 0;
}
上述代码的核心函数tick()相当于一个心搏函数，它每隔一段固定的时间就执行一次，以检测并处理到期的任务。判断定时任务到期的依据是定时器的expire值小于当前系统的时间。从执行效率来看，添加定时器的时间复杂度是O(n),删除定时器的时间复杂度是O(1),执行定时任务的时间复杂度是O(1)。
- I/O复用系统调用的超时参数
LINUX下的三组I/O复用都有超时参数，因此它们不仅能统一处理信号和I/O事件，也能统一处理定时事件。但是由于I/O复用系统调用可能在超时时间到期之前就返回（有I/O事件发生），所以如果我们要利用它们来定时，就需要不断更新参数以反映剩余的时间。
#define TIMEOUT = 5000;
int timeout = TIMEOUT;
time_t start = time(NULL); //获取当前系统时间
time_t end = time(NULL);
while(1)
{
printf("the timeout is now %d mil-seconds \n", timeout);
start = time(NULL);
int number = epoll_wait(epollfd, events, MAX_EVENTS_NUMBER, timeout);
if(number < 0)
{
printf("epoll failuer\n");
break;
}
/*如果epoll_wait成功返回0，则说明超时时间到，此时便可处理定时任务，并重置时间*/
if(number == 0)
{
timeout = TIMEOUT;
continue;
}
end = time(NULL);
/*如果epoll_wait的返回值大于0，则本次epoll_wait调用持续的时间是 (end-start)*1000ms, 我们需要将定时时间timeout减去这段时间，以获得下次epoll_wait调用的超时参数*/
timeout -= (end - start)*1000;
/*重新计算后的timeout值可能等于0，说明本次epoll_wait中有定时任务，我们处理它，并重置定时时间*/
if(timeout < 0)
timeout = TIMEOUT;
}
高性能定时器
前文提到，基于排序链表的定时器存在一个问题，添加定时器的效率偏低。下面我们来实现定时轮。
看着上图是不和hash表中拉链法很像，时间轮确实用到了该原理。
时间轮种，指针以恒定的速度转动，每转动一步就是下一个槽，每次转动称为一个滴答(tick)。一个滴答的时间称为时间轮的间隔槽si(slot interval)，它实际上就是心搏时间。时间轮中公有N个槽，每转动一周的时间为Nsi。每个槽指向一条定时器链表，每条链表上的定时器具有相同的特征：它们的定时时间相差Nsi的整数倍。时间轮正是利用此关系将定时器散列到不同的链表中。假设现在指针指向槽cs，我们要将添加一个定时时间为ti的定时器，则该定时器将被插入槽ts(timer slot)对应的链表中：
ts = (cs + (ti / si) ) % N; //好好理解这里的算法
链表会随着定时器的数目增多效率降低，而散列有多条链表，数目增多对该散列影响很小。
在学习散列知识后，再看时间轮，我们发现，要提高时间精度就要将si的值尽可能的小，要提高执行效率就要N值族够大。
本次我们只实现一个轮子的定时轮，各位可以尝试多个轮子。
//时间轮定时器
#ifndef TIME_WHEEL_TIMER
#define TIME_WHEEL_TIMER
#include"head.hpp"
#include<time.h>
#define BUFFER_SIZE 64
class tw_timer;
/*绑定socket和定时器*/
struct client_data
{
struct sockaddr_in address;
int sockfd;
char buf[BUFFER_SIZE];
tw_timer* timer;
};
/*定时器类*/
class tw_timer
{
public:
tw_timer(int rot, int ts) : next(nullptr), prev(nullptr), rotation(rot), time_slot(ts) {}
public:
int rotation; //记录定时器在时间轮转多少圈生效
int time_slot; // 记录定时器属于时间轮上哪个槽（对应的链表）
void (*cb_func)(client_data*); //定时器回调函数
client_data* user_data; //客户数据
tw_timer* next;
tw_timer* prev;
};
class time_wheel
{
public:
time_wheel() : cur_slot(0)
{
for(int i = 0; i < N; ++i)
slots[i] = nullptr; //初始化每个槽的头结点
}
~time_wheel()
{
/*遍历每个槽，并销毁其中的定时器*/
for(int i = 0; i < N; ++i)
{
tw_timer* tmp = slots[i];
while(tmp)
{
slots[i] = tmp->next;
delete tmp;
tmp = slots[i];
}
}
}
/*根据定时值timeout创建一个定时器，并把它插入合适的槽中*/
tw_timer* add_timer(int timeout)
{
if(timeout < 0)
return nullptr;
int ticks = 0;
/*下面根据待插入定时器的超时值计算它将在时间轮转动多少个滴答后被触发，
并将该滴答数存储于变量ticks中。如果待插入定时器的超时值小于时间轮槽间隔SI,
则将ticks向上折合为1，否则就将ticks向下折合为timeout/SI */
if(timeout < SI)
ticks = 1;
else
{
ticks = timeout / SI;
}
//计算待插入的定时器在时间轮转动多少圈后被触发
int rotation = ticks / N;
/*计算待插入的定时器应该被插入哪个槽中*/
int ts = (cur_slot + (ticks % N) ) % N;
//创建新的定时器，它在时间轮转动rotation圈后被触发，且位于第ts个槽上
tw_timer* timer = new tw_timer(rotation, ts);
/*如果第ts个槽上尚无任何定时器，则把新建的定时器插入其中，并将定时器设置为该槽的头结点*/
if(!slots[ts])
{
printf("add timer, rotation is %d, ts is %d, cur_slot is %d\n", rotation, ts, cur_slot);
slots[ts] = timer;
}
//否则将定时器插入第ts个槽中
else
{
timer->next = slots[ts];
slots[ts]->prev = timer;
slots[ts] = timer;
}
return timer;
}
/*删除目标定时器timer*/
void del_timer(tw_timer* timer)
{
if(!timer)
return;
int ts = timer->time_slot;
/*slots[ts]是目标定时器所在的槽的头结点。如果目标定时器就是该头结点，则需要重置第ts个槽的头结点*/
if(timer == slots[ts])
{
slots[ts] = slots[ts]->next;
if(slots[ts])
slots[ts]->prev = nullptr;
delete timer;
}
else
{
timer->prev->next = timer->next;
if(timer->next)
timer->next->prev = timer->prev;
delete timer;
}
}
/*SI时间到后，调用该函数，时间轮向前滚动一个槽的间隔*/
void tick()
{
tw_timer* tmp = slots[cur_slot]; //取得时间轮上当前槽的头结点
printf("current slot is %d\n", cur_slot);
while(tmp)
{
printf("tick the time once\n");
//如果定时器的rotation值大于0， 则它在这一轮不起作用
if(tmp->rotation > 0)
{
tmp->rotation--;
tmp = tmp->next;
}
//否则，说明定时器已经到期，于是执行定期任务，然后删除该定时器
else
{
tmp->cb_func(tmp->user_data);
if(tmp == slots[cur_slot])
{
printf("delete header cur_slot\n");
slots[cur_slot] = tmp->next;
delete tmp;
if(slots[cur_slot])
slots[cur_slot]->prev = nullptr;
tmp = slots[cur_slot];
}
else
{
tmp->prev->next = tmp->next;
if(tmp->next)
tmp->next->prev = tmp->prev;
tw_timer* tmp2 = tmp;
delete tmp;
tmp = tmp2;
}
}
}
cur_slot = ++cur_slot % N; //更新时间轮的当前槽，以反映时间轮的转动
}
private:
/*时间轮上槽的数目*/
static const int N = 60;
/*每1s时间轮转动一次，既槽间隔为1s*/
static const int SI = 1;
/*时间轮的槽，其中每个元素指向一个定时器链表，链表无序*/
tw_timer* slots[N];
int cur_slot; //时间轮的当前槽
};
#endif
时间堆
前面讨论的定时器都是以固定的频率调用心搏函数tick，并在其中依次检测到期的定时器，然后执行到期定时器上的回调函数。设计定时器的另外一种思路是：将所有定时器中超时时间最小的一个定时器的超时值作为心搏间隔。这样，一旦心搏函数tick被调用，超时时间最小的定时器必然到期，我们就可以在tick函数中处理该定时器。然后，再次从剩余的定时器中找出超时时间最小的一个，并将这段最小时间设置为下一次心搏间隔。如此反复，就实现了较为准确的定时。
在数据结构中，最小堆最适合这种定时方案。(大家需要自行去学习堆的知识)
最小堆的堆顶是最小的元素，我们就将它的定时时间作为间隔，当堆顶元素被处理之后，就将堆顶元素删除，然后用堆的操作将子节点中最小的放到堆顶，如此反复我们就可以较为准确的定时
下面就是时间堆结构的实现
#ifndef HEAP_TIME
#define HEAP_TIME
#include"head.hpp"
#include<time.h>
using std::exception;
const int BUFFER_SIZE = 64;
class heap_timer; //前向声明
//绑定socket和定时器
struct client_data
{
sockaddr_in address;
int sockfd;
char buf[BUFFER_SIZE];
heap_timer* timer;
};
//定时器类
class heap_timer
{
public:
heap_timer(int delay)
{
expire = time(NULL) + delay;
}
public:
time_t expire; //定时器生效的绝对时间
void (*cb_func)(client_data*); //定时器的回调函数
client_data* user_data; //用户数据
};
//时间堆类
class time_heap
{
public:
/*构造函数之一，初始化一个大小为cap的空对*/
time_heap(int cap) : capacity(cap), cur_size(0)
{
array = new heap_timer* [capacity]; //创建堆数组
if(!array)
throw std::exception();
for(int i = 0; i < capacity; ++i)
array[i] = nullptr;
}
/*构造函数之二， 用已有数组来初始化堆*/
time_heap(heap_timer** init_array, int size, int cap) : cur_size(size), capacity(cap)
{
if(capacity < size)
throw std::exception();
array = new heap_timer*[capacity]; //创建堆数组
if(!array)
throw std::exception();
if(size)
{
for(int i = 0; i < capacity; ++i)
array[i] = init_array[i];
for(int i = (cur_size -1) / 2; i >=0; --i)
//对数组中的第[(cur_size - 1) /2 ] ~ 0个元素执行下滤操作
percolate_down(i);
}
}
//销毁时间堆
~time_heap()
{
for(int i = 0; i < cur_size; ++i)
{
delete array[i];
}
delete []array;
}
public:
//添加目标定时器timer
void add_timer(heap_timer* timer)
{
if(!timer)
return;
if(cur_size >= capacity) //如果数组容量不够，则将其扩大一倍
resize();
//新插入一个元素，当前堆大小加1，hole是新建空穴的位置
int hole = cur_size++;
int parent = 0;
//对从空穴到根节点的路径上的所有节点执行上滤操作
for(; hole > 0; --hole)
{
parent = (hole -1) / 2;
if(array[parent]->expire > timer->expire)
{
array[hole]->expire = array[parent]->expire;
continue;
}
array[hole]->expire = timer->expire;
break;
}
}
//删除目标定时器
void del_timer(heap_timer* timer)
{
if(!timer)
return;
/*
仅将目标定时器的回调函数设置为空，既所谓的延迟销毁，
这将节省真正删除定时器造成的开销，但这样做容易使得堆数组膨胀
*/
timer->cb_func = nullptr;
}
//获得堆顶部的定时器
heap_timer* top() const
{
if(empty())
return nullptr;
return array[0];
}
//删除堆顶部的定时器
void pop_timer()
{
if(empty())
return;
if(array[0])
{
delete array[0];
//将原来的堆顶元素替换为堆数组中最后一个元素
array[0] = array[--cur_size];
percolate_down(0); //堆新的堆顶元素执行下滤操作
}
}
//心搏函数
void tick()
{
heap_timer* tmp = array[0];
time_t cur = time(NULL);
while(!empty())
{
if(!tmp)
break;
//如果堆顶定时器没到期，则退出循环
if(tmp->expire > cur)
break;
//否则就执行堆顶定时器的任务
if(array[0]->cb_func)
array[0]->cb_func(array[0]->user_data);
//将堆顶元素删除，同时生成新的定时器(array[0])
pop_timer();
tmp = array[0];
}
}
//堆数组是否为空
bool empty() const {return cur_size == 0;}
private:
//最小堆的下滤操作，它确保数组中以第hole个节点为根的子树拥有最小堆性质
void percolate_down(int hole)
{
heap_timer* temp = array[hole];
int child = 0;
for(; ((hole * 2 + 1) <= (cur_size -1) ); hole = child)
{
child = hole * 2 + 1;
if(child < cur_size -1 && array[child]->expire > array[child + 1]->expire)
++child;
if(temp->expire < array[child]->expire)
break;
array[hole]->expire = array[child]->expire;
}
array[hole]->expire = temp->expire;
}
//将堆数组容量扩大一倍
void resize()
{
heap_timer** temp = new heap_timer* [capacity *2]; //扩容
for(int i = 0; i < 2*capacity; ++i)
temp[i] = nullptr;
capacity = 2 *capacity;
for(int i =0; i < capacity; ++i)
temp[i] = array[i];
delete []array;
array = temp;
}
private:
heap_timer** array; //堆数组
int capacity; //堆数组容量
int cur_size; //堆数组当前包含元素的个数
};
#endif
对时间堆而言，添加一个定时器的时间复杂度为O(logn), 删除一个定时器的时间复杂度为O(1), 执行一个定时器的时间复杂度为O(1), 因此，时间堆效率非常高。