[数据结构与算法]web服务器升序链表定时器

#ifndef LST_TIMER
#define LST_TIMER

#include <unistd.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/epoll.h>
#include <fcntl.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <assert.h>
#include <sys/stat.h>
#include <string.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <stdarg.h>
#include <errno.h>
#include <sys/wait.h>
#include <sys/uio.h>
#include <time.h>

#define BUFFER_SIZE 64
class util_timer; //声明

//定义用户数据结构体
struct client_data
{
    sockaddr_in address;
    int sockfd;
    char buf[BUFFER_SIZE];
    util_timer *timer;
};

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

public:
    time_t expire;
    void (*cb_func)(client_data *);
    client_data *user_data;
    util_timer *pre;
    util_timer *next;
};

//定时器链表
class sort_timer_lst
{

private:
    util_timer *head;
    util_timer *tail;

public:
    sort_timer_lst() : head(nullptr), tail(nullptr) {}
    //链表被销毁时，删除所有定时器
    ~sort_timer_lst()
    {
        util_timer *tmp = head;
        while (tmp)
        {
            head = tmp->next;
            delete tmp;
            tmp = head;
        }
    }

    //将目标表定时器添加到链表中
    void add_timer(util_timer *timer)
    {
        if (timer == nullptr)
        {
            return;
        }
        //head头结点为空
        if (head == nullptr)
        {
            head = tail = timer;
            return;
        }
        //如果目标定时器的超时时间小于所有升序链表
        //添加到head节点
        if (timer->expire < head->expire)
        {
            timer->next = head;
            timer->pre = nullptr;
            head->pre = timer;
            head = timer;
            return;
        }
        //否则就进行添加到中间
        add_timer(timer, head);
    }

    //当某个定时事件发生变化时，调整对应的的定时器在链表中的位置
    //只考虑超时时间延长的情况，即往后面移动
    void adjust_timer(util_timer *timer)
    {
        if (timer == nullptr)
        {
            return;
        }
        util_timer *tmp = timer->next;
        //被调整的定时器在尾部
        //或者该定时器的超时值仍然小于下一个
        if (tmp == nullptr || timer->expire < tmp->expire)
        {
            return;
        }

        //如果目标定时器是头结点,则将该定时器取出，再重新插入
        if (timer == head)
        {
            head = head->next;
            head->pre = nullptr;
            timer->next = nullptr;
            //取出，重新插入
            add_timer(timer, head);
        }
        //如果不是头尾节点，在中间
        else
        {
            timer->pre->next = tmp;
            tmp->pre = timer->pre;
            add_timer(timer, timer->next);
        }
    }

    //删除目标定时器
    void del_timer(util_timer *timer)
    {
        if (timer == nullptr)
        {
            return;
        }
        //当链表中只有一个定时器时
        if (timer == head && timer == tail)
        {
            delete timer;
            head = nullptr;
            tail = nullptr;
            return;
        }

        //有多个定时器,并且定时器是链表的尾节点
        //重置尾节点
        if (timer == tail)
        {
            tail = tail->pre;
            tail->next = nullptr;
            delete timer;
            return;
        }

        //是头结点
        if (timer == head)
        {
            head = head->next;
            head->pre = nullptr;
            delete timer;
            return;
        }

        //在中间
        timer->pre->next = timer->next;
        timer->next->pre = timer->pre;
        delete timer;
    }

    //sigalrm信号每次触发就执行一次tick函数
    void tick()
    {
        if (head == nullptr)
        {
            return;
        }
        //获得当前时间
        time_t cur = time(NULL);
        util_timer *tmp = head;
        //从头结点开始依次处理每个定时器，直到遇到一个尚未到期的定时器
        while (tmp)
        {
            //当前时间小于超时时间时
            if (cur < tmp->expire)
            {
                break;
            }

            //否则调用定时器的回调函数,执行任务
            //作用是关闭套接字，从epoll中剔除
            tmp->cb_func(tmp->user_data);
            //执行完定时器中的定时任务后，就将它从链表中剔除，并重置链表头结点
            head = tmp->next;
            //判断此时头结点是否为空
            if (head)
            {
                head->pre = nullptr;
            }
            delete tmp;
            tmp = head;
        }
    }

private:
    //重载辅助函数，设为私有的
    //添加定时器到中间
    void add_timer(util_timer *timer, util_timer *lst_head)
    {
        //双指针方式
        util_timer *prev = lst_head;
        util_timer *tmp = prev->next;
        while (tmp)
        {
            if (timer->expire < tmp->expire)
            {
                prev->next = timer;
                timer->pre = prev;
                timer->next = tmp;
                tmp->pre = timer;
                break;
            }
            prev = tmp;
            tmp = tmp->next;
        }
        //遍历完都没有找到，则说明是最大的
        //将它插到尾部，并设置成tail
        if (tmp == nullptr)
        {
            prev->next = timer;
            timer->pre = prev;
            timer->next = nullptr;
            tail = timer;
        }
    }
};

#endif