基于时间轮的定时器

#ifndef TIME_WHEEL_TIMER
#define TIME_WHEEL_TIMER

#include <time.h>
#include <netinet/in.h>
#include <stdio.h>

#define BUFFER_SIZE 64
class tw_timer;
struct client_data {
    sockaddr_in address;
    int sockfd;
    char buf[BUFFER_SIZE];
    tw_timer* timer;
};

class tw_timer {
    public:
        tw_timer(int rot, int ts) : next(NULL), prev(NULL), rotation(rot), time_slot(ts) {}

        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) {
                while(tmp) {
                    slots[i] = tmp->next;
                    delete tmp;
                    tmp = slots[i];
                }
            }
        }

        tw_timer* add_timer(int timeout) {
            if (timeout < 0) {
                return NULL;
            }
            int ticks = 0;
            // 根据待插入定时器的超时值计算他在时间轮转动多少滴答后触发，并将该滴答数存储变量tics中。若待插入定时器超时值小于槽间隔SI，将tics向上折合为1.否则向下折合为timeout/SI
            if (timeout < SI) {
                ticks = 1;
            } else {
                ticks = timeout / SI;
            }
            int rotation = ticks / N; // 计算待插入的定时器转动多少圈后触发
            int ts = (cur_slot + (ticks % N)) % N; // 定时器应该被插入哪个槽
            tw_timer* timer = new tw_timer(rotation, ts);

            if (!slots[ts]) { // 没有定时器，把新建的定时器插入，并设置为头节点
                printf("add timer, rotation is %d, ts is %d, cur_slot is %d\n", rotation, ts, cur_slot);
                slots[ts] = timer;
            } else { // 将定时器插入第ts个槽中
                timer->next = slots[ts];
                slots[ts]->prev = timer;
                slots[ts] = timer;
            }
            return timer;
        }

        void del_timer(tw_timer* timer) {
            if (!timer) {
                return;
            }
            int ts = timer->time_slot;
            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;
            }
        }

        void tick() {
            tw_timer* tmp = slots[cur_slot];
            printf("current slot is %d\n", cur_slot);
            while (tmp) {
                printf("tick the timer once\n");
                if (tmp->rotation > 0) { // ratation大于0，这一轮不起作用
                    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 = 60; // 时间轮上槽的数目
        static const int SI = 1; // 每1s时间轮转动一次，槽间隔为1s
        tw_timer* slots[N]; // 每个元素指向一个定时器链表，无序
        int cur_slot;
}

#endif

结构如图所示：
图片来自高性能服务器编程——游双
$time\ slot = (current\ slot + (time\ interval / slot\ interval)) \ \%\ N$
其中，$time\ slot$为需要添加到的时间槽，$current\ slot$为现在时间轮所处的时间槽，$time\ interval$为从现在开始计时，需要多久触发执行任务的时间，$slot\ interval$为每个时间槽所代表的时间。$N$为时间槽总数。
想要提高定时精度，使$slot\ interval$值变小。提高执行效率，增大$N$。

添加定时器时间复杂度$O(1)$，执行定时器时间复杂度$O(N)$，实际上效率比$O(N)$快，因为不同定时器被散列到不同的链表上了。当用多个时间轮时，该时间复杂度近似为$O(1)$。

---

reference：高性能linux服务器编程——游双