基于时间轮的定时器

之前实现的基于升序链表的定时器虽然能实现定时的功能，但是存在一个很明显的缺点：当定时器数量多时，插入一个定时器的时间复杂度时O(n)，因为需要保持链表升序。而删除一个定时器的时间复杂度是O(1)（链表是双向的）。于是出现了基于时间轮的定时器，

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

// 绑定socket和定时器
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(nullptr), prev(nullptr), rotation(rot), time_slot(ts) {}

public:
    int rotation; /* 记录该定时器在时间轮转多少圈后生效 */
    int time_slot; /* 记录该定时器属于时间轮上哪个槽对应的链表 */
    void (*cb_func)(client_data *); /* 回调函数 */
    client_data *user_data; /* 用户数据 */
    tw_timer *next; /* 指向下一个定时器 */
    tw_timer *prev; /* 指向前一个定时器 */
};

/* 时间轮 */
class time_whell {
public:
    time_whell() : cur_slot(0) {
        for (int i = 0; i < N; ++i) {
            slots[i] = nullptr;
        }
    }
    ~time_whell() {
        /* 遍历每个槽，并销毁其中的定时器 */
        for (int i = 0; i < N; ++i) {
            tw_timer *temp = slots[i];
            while (temp) {
                slots[i] = temp->next;
                delete temp;
                temp = slots[i];
            }
        }
    }

    /* 根据定时器timeout创建一个定时器，并把它插入合适的槽中 */
    tw_timer *add_timer(int timeout) {
        if (timeout < 0) {
            return nullptr;
        }
        int ticks = 0;
        /**下面根据待插入定时器的超时值计算它将在时间轮转动多少个嘀嗒(也就是SI)后被触发，并将该嘀嗒数存储于变量ticks中，
         * 如果待插入定时器的超时值小于时间槽的槽间隔SI，则将ticks向上折合为1，否则就将ticks向下折合为 timeout/SI */
        if (timeout < SI) {
            ticks = 1;
        } else {
            ticks = timeout / SI;
        }
        /* 计算待插入的定时器在时间轮转动多少圈后触发 */
        int rotation = ticks / N;
        /* 计算待插入的定时器应该被插入到哪个槽中 */
        int ts = (cur_slot + (ticks % N)) % N; // 该式子应该等同于： (cur_slot + ticks) % N
        /* 创建新的定时器，它在时间轮转动rotation圈之后被触发，且位于第ts个槽上 */
        tw_timer *timer = new tw_timer(rotation, ts);
        /* 如果第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;
        }
        // 否则将定时器插入第ts个槽中
        else {
            timer->next = slots[ts];
            slots[ts]->prev = timer;
            slots[ts] = timer;
        }
        return timer;
    }

    /* 删除目标定时器timer */
    void del_timer(tw_timer *timer) {
        if (!timer) {
            return;
        }
        int ts = timer->time_slot;
        /* slots[ts]是目标定时器timer所在槽的头结点。
         * 如果目标定时器就是该头结点。则需要重置第ts个槽的头结点 */
        if (timer == slots[ts]) {
            slots[ts] = slots[ts]->next;
            if (slots[ts]) {
                slots[ts]->prev = nullptr;
            }
            delete timer;
        } else {
            timer->prev->next = timer->next;
            if (timer->next) {
                timer->next->prev = timer->prev;
            }
            delete timer;
        }
    }

    /* SI时间到后，调用该函数，时间轮向前滚动一个槽的间隔 */
    void tick() {
        tw_timer *temp = slots[cur_slot]; /* 取得时间轮当前槽的头结点 */
        printf("current slot is %d\n", cur_slot);
        while (temp) {
            printf("tick the timer once\n");
            /* 如果定时器的rotation值大于0, 则它在这一轮不起作用 */
            if (temp->rotation > 0) {
                temp->rotation--;
                temp = temp->next;
            }
            /* 否则，说明计时器已经到期，于是执行定时任务，然后删除该定时器 */
            else {
                temp->cb_func(temp->user_data); // 执行定时任务
                /* 删除该定时器 */
                if (temp == slots[cur_slot]) {
                    printf("delete header in cur_slot\n");
                    slots[cur_slot] = temp->next;
                    delete temp;
                    if (slots[cur_slot]) {
                        slots[cur_slot]->prev = nullptr;
                    }
                    temp = slots[cur_slot];
                } else {
                    temp->prev->next = temp->next;
                    if (temp->next) {
                        temp->next->prev = temp->prev;
                    }
                    tw_timer *temp2 = temp->next;
                    delete temp;
                    temp = temp2;
                }
            }
        }
        cur_slot = ++cur_slot % N; /* 更新时间轮的当前轮，以反映时间轮的转动 */
    }

private:
    static const int N = 60; /* 时间轮上槽的数目 */
    static const int SI = 1; /* 每1s转动一次 */
    tw_timer *slots[N]; /* 时间轮的槽，每个元素指向一个定时器链表，链表是无序的 */
    int cur_slot; /* 时间轮当前转动到哪个槽 */
};

#endif