【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当中文件描述符到节点的映射关系。

节点结构

typedefvoid(*TimerHandler)(structTimerNode*node);structTimerNode{int idx =0;// 元素在heap当中的位置，任意位置删除的时候用得到int id =0;//id 是 类的成员比变量，一直++，Count()函数获取。unsignedint expire =0;// 过期时间
    TimerHandler cb =NULL;// 回调方法，当元素top出来后调用};

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

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

boolMinHeapTimer::_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 childint 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;}voidMinHeapTimer::_shiftUp(int pos){for(;;){int parent =(pos -1)/2;// parent nodeif(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的时候才会调用。intMinHeapTimer::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当中找到对应的节点，删除该节点。

boolMinHeapTimer::DelTimer(int id){//id  -> Nodeauto iter = _map.find(id);if(iter == _map.end())returnfalse;_delNode(iter->second);// 删除Nodereturntrue;}

voidMinHeapTimer::_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;}

处理过期时间

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

voidMinHeapTimer::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());//堆内无元素就退出}