linux服务器开发相关视频解析：
5种红黑树的场景，从Linux内核谈到Nginx源码，听完醍醐灌顶
网络程序需要处理的第三类事件是定时事件，比如定期检测一个客户连接的活动状态。服务器程序通常管理着众多定时事件，因此有效组织定时事件，使之能在预期的时间点被触发且不影响服务器的主要逻辑。
将每个定时事件分别封装成定时器，并使用某种容器类数据结构，比如链表、排序链表和时间轮，将所有定时器串联起来，以实现对定时事件的统一管理。
定时
定时是指在一段时间之后触发某段代码的机制。Linux提供了三种定时方法：
- socket选项SO_RCVTIMEO和SO_SNDTIMEO
- SIGALRM信号
- I/O复用系统调用的超时参数
socket选项SO_RCVTIMEO和SO_SNDTIMEO
socket选项SO_RCVTIMEO和SO_SNDTIMEO分别用来设置socket接收数据超时时间和发送数据超时时间。这两个选项仅对与数据接收和发送相关的socket专用系统调用有效，这些系统调用包括send、sendmsg、recv、recvmsg、accept和connect。可以根据系统调用的返回值以及errno来判断超时时间是否已到，进而决定是否开始处理定时任务。
1#include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
#include
#include
//超时连接函数
int timeout_connect(const char* ip, int port, int time);
int main(int argc, char* argv[])
{
if(argc <= 2)
{
printf("usage: %s ip_address port_number\n", basename(argv[0]));
return 1;
}
const char* ip = argv[1];
int port = atoi(argv[2]);
int sockfd = timeout_connect(ip,port,);
if(sockfd < 0)
{
return 1;
}
return 0;
}
int timeout_connect(const char* ip, int port, int time)
{
int ret = 0;
struct sockaddr_in address;
bzero(&address,sizeof(address));
address.sin_family = AF_INET;
inet_pton(AF_INET,ip,&address.sin_addr);
address.sin_port = htons(port);
int sockfd = socket(PF_INET,SOCK_STREAM,0);
assert(sockfd>=0);
//通过选项SO_RCVTIMEO和SO_SNDTIMEO所设置的超时时间的类型是timeval，这和select系统
//调用的超时参数类型相同
struct timeval timeout;
timeout.tv_sec = time;
timeout.tv_usec = 0;
socklen_t len = sizeof(timeout);
ret = setsockopt(sockfd,SOL_SOCKET, SO_SNDTIMEO, &timeout, len);
assert(ret!=-1);
ret = connect(sockfd,(struct sockaddr*)&address, sizeof(address));
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反映了定时的精度。
举例：
基于升序链表的定时器-》简单的定时器实现 添加定时器的时间复杂度是O(n)，删除定时器的时间复杂度是O(1)，执行定时任务的时间复杂度是O(1)
定时器通常至少要包含两个成员：一个超时时间（相对时间或绝对时间）和一个任务回调函数。有时候还可能包含回调函数被执行时需要传入的参数，以及是否重启定时器等信息。
服务器程序通常要定期处理非活动连接：给客户端发一个重连请求，或者关闭该连接，或者其他。Linux在内核中提供了对连接是否处于活动状态的定期检查机制，我们可以通过socket选项KEEPALIVE来激活它。不过使用这种方式将使得应用程序对连接的管理变得复杂。因此，考虑在应用层实现类似于KEEPALIVE的机制，以管理所有长时间处于非活动状态的连接。
利用alarm函数周期性地触发SIGALRM信号，该信号的信号处理函数利用管道通知主循环执行定时器链表上的定时任务-关闭非活动的连接。
timelink.h
1 #ifndef LST_TIMER
2 #define LST_TIMER
3
4 #include
5 #define BUFFER_SIZE
6 class util_timer; //前向声明
7
8 //用户数据结构：客户端socket地址、socket文件描述符、读缓存和定时器
9 struct client_data
{
sockaddr_in address;
int sockfd;
char buf[BUFFER_SIZE];
util_timer* timer;
};
//定时器类
class util_timer
{
public:
util_timer():prev(NULL),next(NULL){}
time_t expire; //任务的超时时间，这里使用绝对时间
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)
{
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);
}
//当某个定时任务发生变化时，调整对应的定时器在链表中的位置
//这个函数只考虑被调整的定时器的超时时间延长的情况
void adjust_timer(util_timer* timer)
{
if(!timer)
{
return;
}
util_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 del_timer(util_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;
}
//SIGALRM信号每次被触发就在其信号处理哈桑农户中执行一次tick函数，以处理链表上到期的> 任务
void tick()
{
if(!head)
{
return;
}
printf("timer tick\n");
time_t cur = time(NULL); //获得系统当前的时间
util_timer* tmp = head;
//从头结点开始依次处理每个定时器，直到遇到一个尚未到期的定时器，这就是定时器
的核心逻辑
while(tmp)
{
//比较定时器的超时值和系统当前时间
if(curexpire)
{
break;
}
//调用定时器的回调函数，以执行定时任务
tmp->cb_func(tmp->user_data);
//执行完定时器中的定时任务后，将它从链表中删除
head = tmp->next;
if(head)
{
head->prev = NULL;
}
delete tmp;
tmp = head;
}
}
private:
//私有重载定时器添加函数，添加到结点lst_head之后的链表中
void add_timer(util_timer* timer, util_timer* lst_head)
{
util_timer* prev = lst_head;
util_timer* tmp = prev->next;
//遍历lst_head节点之后的部分链表，直到找到一个超时时间大于目标定时器的超时时
间的结点，并将目标定时器插入该结点之前
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;
}
//如果遍历完lst_head结点之后的部分链表，仍未找到超时时间大于目标定时器时间的
结点，则将目标定时器插入链表尾部，并把它设置为新的尾结点
if(!tmp)
{
prev->next = timer;
timer->prev = prev;
timer->next = NULL;
tail = timer;
}
}
private:
util_timer* head;
util_timer* tail;
};
#endif 【文章福利】需要C/C++ Linux服务器架构师学习资料加群（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等）
closelink.cpp
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
#include
#include
#include
#include
#include
#include "timelink.h"
#define FD_LIMIT
#define MAX_EVENT_NUMBER
#define TIMESLOT 5
static int pipefd[2];
static sort_timer_lst timer_lst;
static int epollfd = 0;
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;
}
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);
}
//定时处理任务，实际上就是调用tick函数
void timer_handler()
{
timer_lst.tick();
//因为一次alarm调用只会引起一次SIGALRM信号，需要重新定义，以不断触发SIGALRM信号
alarm(TIMESLOT);
}
//定时器回调函数，它删除非活动连接socket上的注册事件，并关闭之
void cb_func(client_data* user_data)
{
assert(user_data);
epoll_ctl(epollfd,EPOLL_CTL_DEL,user_data->sockfd,0);
close(user_data->sockfd);
printf("close fd %d\n",user_data->sockfd);
}
int main(int argc, char* argv[])
{
if( argc <= 2)
{
printf("usage: %s ip_address port_number\n",basename(argv[0]));
return 1;
}
const char* ip = argv[1];
int port = atoi(argv[2]);
int ret = 0;
struct sockaddr_in address;
bzero(&address,sizeof(address));
address.sin_family = AF_INET;
inet_pton(AF_INET, ip, &address.sin_addr);
address.sin_port = htons(port);
int listenfd = socket(PF_INET,SOCK_STREAM,0);
assert(listenfd>=0);
ret = bind(listenfd,(struct sockaddr*)&address,sizeof(address));
assert(ret!=-1);
ret = listen(listenfd,5);
assert(ret!=-1);
epoll_event events[MAX_EVENT_NUMBER];
int epollfd = epoll_create(5);
assert(epollfd!=-1);
addfd(epollfd,listenfd);
ret = socketpair(PF_UNIX,SOCK_STREAM,0,pipefd);
assert(ret!=-1);
setnonblocking(pipefd[1]);
addfd(epollfd,pipefd[0]);
//设置信号处理函数
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))
{
printf("epoll failure\n");
break;
}
for(int i = 0; i < number; i++)
{
int sockfd = events[i].data.fd;
if(sockfd==listenfd)
{
//处理新到的客户连接
struct sockaddr_in client_address;
socklen_t client_addrlength = sizeof(client_address);
int connfd = accept(listenfd,(struct sockaddr*)&client_addre ss,&client_addrlength);
addfd(epollfd,connfd);
users[connfd].address = client_address;
users[connfd].sockfd = connfd;
//创建定时器，设置其回调函数与超时时间，然后绑定定时器与用户数据，最后将定时器添加到链表timer_lst中
util_timer* timer = new util_timer;
timer->user_data = &users[connfd];
timer->cb_func = cb_func;
time_t cur = time(NULL);
timer->expire = cur + 3*TIMESLOT;
users[connfd].timer = timer;
timer_lst.add_timer(timer);
}else if((sockfd==pipefd[0])&&(events[i].events & EPOLLIN)){
//处理信号
int sig;
char signals[];
ret = recv(pipefd[0],signals,sizeof(signals),0);
if(ret==- {
//处理错误
continue;
}else if(ret == {
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(events[i].events & EPOLLIN)
{
//处理客户连接上接收到的数据
memset(users[sockfd].buf, '\0', BUFFER_SIZE);
ret = recv(sockfd,users[sockfd].buf,BUFFER_SIZE-1,0);
util_timer* timer = users[sockfd].timer;
if(ret < { //如果发生读错误，则关闭连接，并移除其对应的定时器
if(errno!=EAGAIN)
{
cb_func(&users[sockfd]);
if(timer)
{
timer_lst.del_timer(timer);
}
}
}else if(ret == { //如果对方关闭连接，则服务器也关闭连接，并移除对应的
定时器
cb_func(&users[sockfd]);
if(timer)
{
timer_lst.del_timer(timer);
}
}else{ //如果某个客户连接上有数据，则要调整该连接对应的定时> 器，以延迟该连接被关闭的时间
printf("get %d bytes of client data %s from %d\n",re t,users[sockfd].buf,sockfd);
if(timer)
{
time_t cur = time(NULL);
timer->expire = cur + 3*TIMESLOT;
printf("adjust timer once\n");
timer_lst.adjust_timer(timer);
}
}
}else{
//others
}
}
//最后处理定时事件，因为I/O事件有更高优先级，这样会导致定时任务不能按照预期> 时间执行
if(timeout)
{
timer_handler();
timeout = false;
}
}
close(listenfd);
close(pipefd[1]);
close(pipefd[0]);
delete[] users;
return 0;
} I/O复用系统调用的超时参数
Linux下的3组I/O复用系统调用都带有超时参数，因此它们不仅能统一处理信号和I/O事件，也能统一处理定时事件。但是由于I/O复用系统调用可能在超时时间到期之前就返回（有I/O事件发生），所以如果要利用它们来定时，就需要不断更新定时参数以反映剩余的时间。
#define TIMEOUT
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_EVENT_NUMBER,timeout);
if((number<0)&&(errno!=EINTR))
{
printf("epoll failure\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)*;
//重新计算后timeout有可能等于0，说明本次epoll_wait调用返回时，不仅有文件描述符就绪，而且其超时时间也刚好到达，此时我们也要处理定时任务，并重置定时时间
if(timeout <= 0)
{
timeout = TIMEOUT;
}
//handle connections
}高性能定时器
时间轮
在时间轮内，（实线）指针指向轮子上的一个槽(slot)，它以恒定的速度顺时针转动，每转动一步就指向下一个槽（虚线指针指向的槽），每次转动称为一个滴答(tick)。一个滴答的时间称为时间轮的槽间隔si(slot interval)，它实际上就是心搏时间。该时间轮共有N个槽，因此它运转一周的时间是Nsi。每个槽指向一条定时器链表，每条链表上的定时器具有相同的特征：它们的定时时间相差Nsi的整数倍。时间轮正是利用这个关系将定时器散列到不同的链表中。假如现在指针指向槽cs，我们要添加一个定时时间为ti的定时器，则该定时器将被插入槽ts(timer slot)对应的链表中：ts=(cs+(ti/si))%N
基于排序链表的定时器使用唯一的一条链表来管理所有定时器，所以插入操作的效率随着定时器数目的增多而降低。而时间轮私用哈希表的思想，将定时器散列到不同的链表上。这样每条链表上的定时器数目都将明显少于原来的排序链表上的定时器数目，插入操作的效率基本不受定时器数目的影响。对于时间轮而言，添加一个定时器的时间复杂度是O(1)，删除一个定时器的时间复杂度也是O(1)，指向一个定时器的时间复杂度是O(n)。但实际上执行一个定时器任务的效率要比O(n)好得多，因为时间轮将所有的定时器散列到了不同的链表上。时间轮的槽越多，等价于散列表的入口越多，从而每条链表上的定时器数量越少。
timeround.h
1 #ifndef TIME_WHEEL_TIMER
2 #define TIME_WHEEL_TIMER
3 #include
4 #include
5 #include
6 #define BUFFER_SIZE
7 class tw_timer;
8 struct client_data
9 {
sockaddr_in address;
int sockfd;
char buf[BUFFER_SIZE];
tw_timer* timer;
};
class tw_timer
{
pubilc:
tw_timer(int rot, int ts):rotation(rot),time_slot(ts),next(NULL),prev(NULL){}
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] = NULL;
}
}
~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 NULL;
}
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,c ur_slot);
slots[ts] = timer;
}else{
//否则将定时器插入第ts个槽中
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]是目标定时器所在槽的头结点
if(timer==slots[ts])
{
slots[ts] = slots[ts]->next;
if(slots[ts])
{
slots[ts]->prev = NULL;
}
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 timer once\n");
//如果定时器的rotation值大于0，则它在这一轮不起作用
if(tmp->rotation> {
tmp->rotation--;
tmp = tmp->next;
}else{
//定时器已经到期，于是执行定时任务，然后删除该定时器
tmp->cb_func(tmp->user_data);
if(tmp==slots[cur_slot])
{
printf("delete header in cur_slot\n");
slots[cur_slot] = tmp->next;
delete tmp;
if(slots[cur_slot])
{
slots[cur_slot]->prev = NULL;
}
tmp = slots[cur_slot];
}else{
tmp->prev->next = tmp->next;
if(tmp->next)
{
tmp->next->prev = tmp->prev;
}
tw_timer* tmp2 = tmp->next;
delete tmp;
tmp = tmp2;
}
}
}
//更新时间轮的当前槽
cur_slot = ++cur_slot % N;
}
private:
static const int N = ; //时间轮上槽的数目
static const int SI = 1; //每1s时间轮转动一次，即槽间隔为1s
tw_timer* slots[N]; //时间轮的槽，其中每个元素指向一个定时器链表，链表无序
int cur_slot; //时间轮的当前槽
};
#endif 时间堆
前面讨论的定时方案都是以固定的频率调用心搏tick，并在其中依次检测到期的定时器，然后执行到期定时器上的回调函数。设计定时器的另外一种思路是：将所有定时器中超时时间最小的一个定时器的超时值作为心搏间隔。这样，一旦心搏tick被调用，超时时间最小的定时器必然到期，我们就可以在tick函数中处理该定时器。然后，再次从剩余的定时器中找出超时时间最小的一个，并将这段最小时间设置为下一次心搏间隔。如此反复，就实现了较为精确的定时。
最小堆是指每个节点的值都小于或等于其子节点的值的完全二叉树。树的基本操作是插入节点和删除节点。为了将一个元素X插入最小堆，我们可以在树的下一个空闲位置创建一个空穴。如果X可以放在空穴中而不破坏堆序，则插入完成。否则就执行上虑操作，即交换空穴和它的父节点上的元素。不断执行上述过程，直到X可以被放入空穴，则插入操作完成。
最小堆的删除操作指的是删除其根节点上的元素，并且不被坏堆序性质。执行删除操作时，我们需要先在根节点处创建一个空穴。由于堆现在少了一个元素，因此我们可以把堆的最后一个元素X移动到该堆的某个地方。如果X可以被放入空穴，则删除操作完成。否则就执行下虑操作，即交换空穴和它的两个儿子节点中的较小者。不断进行上述过程，直到X可以被放入空穴，则删除操作完成。
由于最小堆是一种完全二叉树，所以可以用数组来组织其中的元素。比如第一幅图所示的最小堆可以用下图表示。对于数组中的任意一个位置i上的元素，其左儿子节点在位置2i+1上，其右儿子节点在位置2i+2上，其父节点则在位置[(i-1)/2] (i>0)上。与用链表来表示堆相比，用数组表示堆不仅节省空间，而且更容易实现堆的插入、删除等操作。
假设我们已经有一个包含N个元素的数组，现在要把它初始化为一个最小堆。那么最简单的方法是：初始化一个空堆，然后将数组中的每个元素插入该堆中。不过这样做效率偏低。实际上，我们只需要对数组中的第[(N-1)/2] ~ 0个元素执行下虑操作，即可保证该数组构成一个最小堆。这是因为对包含N个元素的完全二叉树而言，它具有[(N-1)/2]个非叶子节点，这些非叶子节点正是该完全二叉树的第0 ~ [(N-1)/2]个节点。我们只要确保这些非叶子节点构成的子树都具有堆序性质，整个树就具有堆序性质。
timestack.h
1 #ifndef MIN_HEAP
2 #define MIN_HEAP
3 #include
4 #include
5 #include
6 using std::exception;
7 #define BUFFER_SIZE
8
9 class heap_timer;
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; }
time_t expire; //定时器生效的绝对时间
void (*cb_func)(client_data*); //定时器的回调函数
client_data* user_data; //用户数据
};
class time_heap
{
public:
time_heap(int cap) throw(std::exception):capacity(cap),cur_size(0)
{
array = new heap_timer* [capacity];
if(!array)
{
throw std::exception();
}
for(int i = 0; i < capacity; ++i)
{
array[i] = NULL;
}
}
time_heap(heap_timer** init_array, int size, int capacity) throw(std::exception):
capacity(capacity),cur_size(size)
{
if(capacity=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;
}
//添加目标定时器timer
void add_timer(heap_timer* timer) throw(std::exception)
{
if(!timer)
{
return;
}
if(cur_size>=capacity)
{
resize();
}
//新插入一个元素，当前堆大小加1，hole是新建空穴的位置
int hole = cur_size++;
int parent = 0;
//对从空穴到梗节点的路径上的所有节点执行上虑操作
for(;hole>0;hole=parent)
{
parent = (hole-1)/2;
if(array[parent]->expire <= timer->expire)
{
break;
}
array[hole] = array[parent];
}
array[hole] = timer;
}
//删除目标定时器timer
void del_timer(heap_timer* timer)
{
if(!timer)
{
return;
}
//仅将目标定时器的回调函数设置为空，即所谓的延迟销毁
//这节省真正删除该定时器造成的开销，但容易使堆数组膨胀
timer->cb_func = NULL;
}
//获得堆顶部的定时器
heap_timer* top() const
{
if(empty())
{
return NULL;
}
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);
}
//将堆顶元素删除，同时生成新的堆顶定时器
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;
//hole当前节点 hole*2+1左子节点
for(;(hole*2+1)<=(cur_size-1);hole=child)
{
child = hole*2+1;
if((child<(cur_size-1))&&(array[child+1]->expire < array[child]->expire))
{
++child; //找到子节点超时值小的
}
if(array[child]->expire < temp->expire)
{
array[hole] = array[child];
}else{
break;
}
}
array[hole] = temp;
}
//将堆数组容量扩大1倍
void resize() throw(std::exception)
{
heap_timer** temp = new heap_timer* [2*capacity];
if(!temp)
{
throw std::exception();
}
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;
}
heap_timer** array; //堆数组
int capacity; //堆数组的容量
int cur_size; //堆数组当前包含元素的个数
};
#endif 对于时间堆而言，添加一个定时器的时间复杂度是O(lgn)，删除一个定时器的时间复杂度是O(1)，执行一个定时器的时间复杂度是O(1)。