基于 stl map 的定时器(C++)

2021-04-08

项目要添加 session,每个 session 需要设置过期时间,所以需要定时器。

定时器实现逻辑:对每个定时器事件到期时间进行排序,对有序数据进行顺序检查处理,需要支持查找。

比较了多种方案后,决定通过参考 C++11实现的定时器 ,基于 stl 的字典(map)造个简单点的轮子。


1. 实现

方案选择 std::map 实现。原因:

  • std::map 内部是一颗红黑树,读写时间复杂度 O(logN)。
  • std::map 迭代器默认是根据 key 索引的中序排列。
  • 支持查询。

实现源码:timers.h, timers.cpp

测试源码:test_timers.cpp


1.1. 定时器事件

事件组合 id(TimerGrpID)设计,主要为了方便 std::map 内部排序,还有去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 定时器事件组合 id。
 * 第一个参数是事件到期时间,方便 std::map 排序。
 * 第二个参数是定时器事件 id。*/
typedef std::pair<int64_t, int> TimerGrpID;

/* 定时器事件回调函数。
 * 第一个参数:定时器 id。
 * 第二个参数:是否循环定时器。
 * 第三个参数:创建定时器时传入的用户参数。*/
typedef std::function<void(int, bool, void*)> TimerEvent;

/* 定时器事件。 */
class Timer {
    ...
    int m_id = 0;               /* timer's id. */
    uint64_t m_after_time = 0;  /* timeout in `after` milliseconds. */
    uint64_t m_repeat_time = 0; /* repeat milliseconds. */
    void* m_privdata = nullptr; /* user's data. */
    TimerEvent m_callback_fn;   /* callback function. */
};

1.2. 定时器事件管理

主要通过两个数据结构进行维护:std::mapstd::unordered_map,前者方便定时器事件的排序和数据存储,后者方便查询定时事件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Timers {
    ...
   public:
    /* 删除定时器事件。 */
    bool del_timer(int id);
    /* 添加定时器事件。 */
    int add_timer(const TimerEvent& fn, uint64_t after, uint64_t repeat = 0, void* privdata = nullptr);

   public:
    /* 外部定时刷新,检查事件是否过期. */
    virtual void on_repeat_timer() override;
    ...
   protected:
    int m_last_timer_id = 0;
    std::map<TimerGrpID, Timer*> m_timers;
    std::unordered_map<int, TimerGrpID> m_ids; /* 通过哈希表方便对 std::map 的组合 id 进行查询,删除. */
};

1.3. 核心逻辑

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
39
40
41
42
43
44
45
46
47
48
int Timers::add_timer(const TimerEvent& fn, uint64_t after, uint64_t repeat, void* privdata) {
    int id = new_tid();
    TimerGrpID gid = {mstime() + after, id};

    m_ids[id] = gid;
    m_timers[gid] = (new Timer(id, fn, after, repeat, privdata));

    LOG_DEBUG("add timer done! id: %d", id);
    return id;
}

void Timers::on_repeat_timer() {
    uint64_t now = mstime();

    /* 遍历 std::map 节点,检查节点上的时间是否到期了。*/
    while (!m_timers.empty() && (m_timers.begin()->first.first < now)) {
        auto it = m_timers.begin();
        auto gid = it->first;
        auto timer = it->second;
        auto fn = timer->callback_fn();

        /* 到期了,先从 std::map 上移除对应的定时器事件:timer 与 std::map 解除关系。*/
        m_timers.erase(it);

        /* 到期了,就调用对应定时事件的回调函数。*/
        if (fn) {
            fn(timer->id(), timer->repeat_time() != 0, timer->privdata());
        }

        /* 如果定时事件需要重复触发,那么就更新定时事件的到期时间,重新插入 std::map。*/
        if (timer->repeat_time() != 0) {
            LOG_TRACE("repeat timer hit, timer id: %d, timeout: %llu, now: %llu",
                      gid.second, gid.first, now);
            TimerGrpID new_gid = {mstime() + timer->repeat_time(), gid.second};
            m_timers[new_gid] = timer;
            m_ids[gid.second] = new_gid;
        } else {
            LOG_TRACE("timer hit, delete timer, id: %d", gid.second);
            /* 如果定时器事件不需要重复触发,那么释放掉定时器事件。*/
            SAFE_DELETE(timer);
            auto itr = m_ids.find(gid.first);
            if (itr != m_ids.end()) {
                m_ids.erase(itr);
            }
        }
    }
    ...
}

2. 参考