【C++实现】浅聊定时器的实现，最小堆配合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出来后调用
};
1
2
3
4
5
6
7
8

向上调整算法，向下调整算法

---

以往写的两篇博客有叙述这块。相对简单，不做叙述了。
堆的任意位置的调整
【数据结构入门】从零实现–堆的实现

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;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

插入操作

---

• 堆当中的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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

删除任意元素操作

---

删除任意一个位置的元素，给定参数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;
}
1
2
3
4
5
6
7
8
9

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

处理过期时间

---

从堆顶获取元素，检测时间是否过期，过期就删除，直到堆内无数据或者堆顶元素没有超时。这里实际上属于业务上处理，若是心跳检测的程序，那么此时就需要断开与对端的连接。
只有这里会调用已经注册的回调函数。

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());//堆内无元素就退出
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14