基于升序链表的定时器

定时器通常至少包含两个成员：

• 超时时间（相对时间或者绝对时间）
• 任务回调函数

有些时候还可能包含回调函数被执行时需要传入的参数，以及是否重启定时器等信息

下面是一个简单的升序链表定时器实现

#ifndef LST_TIMER
#define LST_TIMER

#include <cstdio>
#include <arpa/inet.h>
#include <time.h>
#define BUFFER_SIZE 64

class util_timer; /* 前向声明 */

/* 用户数据结构 */
struct client_data {
    sockaddr_in address; // 客户端socket地址
    int sockfd; // sock文件描述符
    char buf[BUFFER_SIZE]; // 读缓存
    util_timer *timer; // 定时器
};

/* 定时器类 */
class util_timer {
public:
    util_timer() : prev(nullptr), next(nullptr) {}

public:
    time_t expire; /* 任务的超时时间，这里使用绝对时间 */
    void (*cb_func)(client_data *); /* 任务回调函数 */
    /* 回调函数处理的客户数据，由定时器的执行者传递给回调函数 */
    client_data *user_data;
    util_timer *prev; /* 指向上一个定时器 */
    util_timer *next; /* 指向下一个定时器 */
};

/* 定时器链表。它是一个升序双向链表，且带有头结点和尾结点 */
class sort_time_list {
public:
    sort_time_list() {}
    ~sort_time_list() {
        // 链表被销毁时，删除其中所有的定时器
        util_timer *temp = head;
        while (temp) {
            head = temp->next;
            delete temp;
            temp = head;
        }
    }

    void add_timer(util_timer *timer) {
        if (!timer) {
            return;
        }
        if (!head) {
            // timer是第一个插入的定时器
            head = tail = timer;
            return;
        }
        /**
         * 如果目标定时器的超时时间小于当前链表中所有定时器的超时时间，则把该定时器插入链表头部。
         * 否则就需要调用重载函数 add_timer(util_timer* timer, util_timer* list_head)
         * 把它插入链表中合适的位置，以保证链表的升序特性
         */
        if (timer->expire < head->expire) {
            timer->next = head;
            head->prev = timer;
            head = timer;
            return;
        }
        add_timer(timer, head);
    }

    /**
     * @brief 当某个定时任务发生变化时，调整对应的定时器在链表中的位置。
     * 这个函数只考虑被调整的定时器的超时时间延长的情况，即该定时器需要往链表的尾部移动
     * @param
     */
    void adjust_timer(util_timer *timer) {
        if (!timer) {
            return;
        }
        util_timer *temp = timer->next;
        /**
         * 如果被调整的目标定时器在链表尾部，
         * 或者该定时器新的超时值仍然小于下一个定时器的超时值
         * 则不用调整
         */
        if (!temp || (timer->expire < temp->expire)) {
            return;
        }
        /**
         * 如果目标定时器是链表的头节点，则将该定时器从链表中取出并重新插入链表
         */
        if (timer == this->head) {
            head = head->next;
            head->prev = nullptr;
            timer->next = nullptr;
            add_timer(timer, head);
        }
        /**
         * 如果目标定时器不是链表的头节点，则将定时器从链表中取出，
         * 然后插入其原来 所在部分之后 的链表中（因为该函数只考虑超时时间延长的情况）
         */
        else {
            timer->prev->next = timer->next;
            timer->next->prev = timer->prev;
            add_timer(timer, timer->next);
        }
    }

    void del_timer(util_timer *timer) {
        if (!timer) {
            return;
        }
        // 链表中只有一个结点
        if ((timer == this->head && (timer == this->tail))) {
            delete timer;
            this->head = nullptr;
            this->tail = nullptr;
            return;
        }
        // 链表中至少两个结点, 并且timer是头结点
        if (timer == this->head) {
            head = head->next;
            head->prev = nullptr;
            delete timer;
            return;
        }
        // 链表中至少两个结点, 并且timer是尾结点
        if (timer == this->tail) {
            tail = tail->prev;
            tail->next = nullptr;
            delete timer;
            return;
        }
        // timer位于链表中间
        timer->prev->next = timer->next;
        timer->next->prev = timer->prev;
        delete timer;
    }

    /**
     * @brief 在SIGALRM信号的信号处理函数(如果使用统一事件源,就是主函数)中执行的函数
     */
    void tick() {
        if (!this->head) {
            return;
        }
        printf("timer tick \n");
        time_t cur = time(nullptr); /* 获得系统当前时间 */
        util_timer *temp = head;
        /**
         * 从头结点开始依次处理每个定时器，直到遇到一个尚未到期的定时器，这就是定时器的核心逻辑
         */
        while (temp) {
            /**
             * 因为每个定时器都使用绝对时间作为超时值，
             * 所以我们可以把定时器的超时值和系统当前时间进行比较，以判断定时器是否到期
             */
            if (cur < temp->expire) {
                // 因为是升序链表，左翼temp满足该条件时，temp后面的结点一定也满足
                break;
            }
            /* 调用定时器的回调函数，以执行定时任务 */
            temp->cb_func(temp->user_data);
            /* 执行完定时器的定时任务之后，就将它从链表中删除，并重置链表头结点 */
            head = temp->next;
            if (head) {
                head->prev = nullptr;
            }
            delete temp;
            temp = head;
        }
    }

private:
    /**
     * @brief 将定时器timer插入到链表lst_head中。并且保证插入位置一定在头结点之后
     */
    void add_timer(util_timer *timer, util_timer *list_head) {
        util_timer *prev = list_head;
        util_timer *temp = prev->next;
        /**
         * 遍历lst_head节点
         */
        while (temp) {
            if (timer->expire < temp->expire) {
                // 将timer插入到temp之前
                prev->next = timer;
                timer->next = temp;
                temp->prev = timer;
                timer->prev = prev;
                break;
            }
            prev = temp;
            temp = temp->next;
        }
        /**
         * 如果遍历完lst_head节点之后的部分链表，仍未找到超时时间 > 目标定时器timer的超时时间的节点，
         * 则将目标定时器timer插入到链表尾部，并把它设置为新的链表尾结点
         */
        if (!temp) {
            prev->next = timer;
            timer->prev = prev;
            timer->next = nullptr;
            tail = timer;
        }
    }

private:
    util_timer *head;
    util_timer *tail;
};

#endif