【C++实现】浅聊定时器的实现,最小堆配合map实现定时器
文章目录
- 前言
- 最小堆配合map实现定时器
- 节点结构
- 向上调整算法,向下调整算法
- 插入操作
- 删除任意元素操作
- 处理过期时间
前言
定时器的使用:nginx,数据库的主从备份,心跳检测,游戏技能,武器的冷却,倒计时等等,其他需要使用超时机制的功能。
定时器主要用于需要使⽤超时机制的功能。
定时器的实现有两种方式:
第⼀种是,⽹络事件和时间事件在⼀个线程当中配合使⽤;例如nginx、redis;
第⼆种是,⽹络事件和时间事件在不同线程当中处理;例如skynet(轻量级的游戏开发框架)。
最小堆配合map实现定时器
这是一种最常见的实现方式。为什么需要map?因为删除堆当中任意一个元素的时间复杂度是O(N),因为删除之间需要查找,需要遍历整个数组查找该元素。而我们添加其他数据结构,如红黑树,哈希表来定位这个要删除的元素,删除操作的时间复杂度就能到O(logN)
- map实现文件描述符到TimerNode的映射,后面简称Node了~
- 最小堆当中存放的是TimerNode,堆内的比较方法是按照过期时间比较
_map.insert(make_pair(id, node));
在不实现任意位置的删除操作,我们实际上不需要idx字段,但是由于心跳检测当中,倘若对方发送正常报文(而非心跳报文),我们依旧需要更新堆内部的过期时间。因为正常报文正常接受也能够说明这条链接依旧存活
。
idx能够在修改任意一个元素的时候O(1)时间获得删除元素的索引。并且删除同理。
修改堆内的对应的节点的场景:
删除堆顶元素的场景:
堆顶的时间超时了,可以认为连接已经无效了,此时堆顶的回调方法可以是 1.删除map当中文件描述符到节点的映射关系,2.删除epoll模型当中对应等待的文件描述符。3.close掉对应的文件描述符。
删除堆内任意元素的场景:
如epoll当中不需要关心该文件描述符了,此时需要堆中元素pop后,依旧是上面回调的三步骤。
增加堆内元素的场景:
如果epoll模型增加要关心的文件描述符,此时也需要将这个元素添加到堆当中,记录过期时间。此时需要push_back这个节点再向上调整,添加map当中文件描述符到节点的映射关系。
节点结构
typedef void (*TimerHandler) (struct TimerNode *node);
struct TimerNode {
int idx = 0; // 元素在heap当中的位置,任意位置删除的时候用得到
int id = 0; //id 是 类的成员比变量,一直++,Count()函数获取。
unsigned int expire = 0; // 过期时间
TimerHandler cb = NULL; // 回调方法,当元素top出来后调用
};
向上调整算法,向下调整算法
以往写的两篇博客有叙述这块。相对简单,不做叙述了。
堆的任意位置的调整
【数据结构入门】从零实现–堆的实现
bool MinHeapTimer::_shiftDown(int pos){
int last = (int)_heap.size()-1;
int idx = pos;
for (;;) {
int left = 2 * idx + 1;
if ((left >= last) || (left < 0)) {
break;
}
int min = left; // left child
int right = left + 1;
if (right < last && !_lessThan(left, right)) {
min = right; // right child
}
if (!_lessThan(min, idx)) {
break;
}
std::swap(_heap[idx], _heap[min]);
_heap[idx]->idx = idx;
_heap[min]->idx = min;
idx = min;
}
return idx > pos;
}
void MinHeapTimer::_shiftUp(int pos)
{
for (;;) {
int parent = (pos - 1) / 2; // parent node
if (parent == pos || !_lessThan(pos, parent)) {
break;
}
std::swap(_heap[parent], _heap[pos]);
_heap[parent]->idx = parent;
_heap[pos]->idx = pos;
pos = parent;
}
}
插入操作
- 堆当中的timeout时间是当前时间 + expire时间
- 也就是尾部进行一次向上调整。
//expire 表示距离现在的过期时间
//cb 是回调方法,只有pop的时候才会调用。
int MinHeapTimer::AddTimer(uint32_t expire, TimerHandler cb) {
int64_t timeout = current_time() + expire;
TimerNode* node = new TimerNode;
int id = Count();
node->id = id;
node->expire = timeout;
node->cb = cb;
node->idx = (int)_heap.size();
_heap.push_back(node);
_shiftUp((int)_heap.size() - 1);
_map.insert(make_pair(id, node));
return id;
}
删除任意元素操作
删除任意一个位置的元素,给定参数id,从map当中找到对应的节点,删除该节点。
bool MinHeapTimer::DelTimer(int id)
{
//id -> Node
auto iter = _map.find(id);
if (iter == _map.end())
return false;
_delNode(iter->second);// 删除Node
return true;
}
void MinHeapTimer::_delNode(TimerNode *node)
{
//节点所在位置为idx, idx的元素与末尾元素交换,再进行一次向上或向下调整即可。
int last = (int)_heap.size() - 1;
int idx = node->idx;
if (idx != last) {
std::swap(_heap[idx], _heap[last]);
_heap[idx]->idx = idx;
if (!_shiftDown(idx)) {
_shiftUp(idx);
}
}
_heap.pop_back();//从堆内删除该元素
_map.erase(node->id);// 从_map删除该映射
delete node;
}
处理过期时间
从堆顶获取元素,检测时间是否过期,过期就删除,直到堆内无数据或者堆顶元素没有超时。这里实际上属于业务上处理,若是心跳检测的程序,那么此时就需要断开与对端的连接。
只有这里会调用已经注册的回调函数。
void MinHeapTimer::ExpireTimer()
{
if (_heap.empty()) return;
uint32_t now = current_time();
do {
TimerNode* node = _heap.front();
if (now < node->expire)//堆顶元素没过期
break;
if (node->cb) {//若有注册回调函数,则调用。
node->cb(node);
}
_delNode(node);
} while(!_heap.empty());//堆内无元素就退出
}