基于时间堆的定时器

#ifndef MIN_HEAP
#define MIN_HEAP

#include <iostream>
#include <netinet/in.h>
#include <time.h>
using std::exception;

#define BUFFER_SIZE 64

class heap_timer;
struct client_data {
    sockaddr_in address;
    int sockfd;
    char buf[BUFFER_SIZE];
    heap_timer* timer;
};

class heap_timer {
    public:
        heap_timer(int delay) {
            expire = timer(NULL) + delay;
        }

        time_t expire;
        void (*cb_func)(client_data*);
        client_data* user_data;
};

class time_heap {
    public:
        time_heap(int cap) throw (std::exception) : capacity(cap), cur_size(0) {
            array = new heap_timer* [capacity];
            if (!array) {
                throw std:exception();
            }
            for (int i = 0; i < capacity; ++i) {
                array[i] = NULL;
            }
        }

        time_heap(heap_timer** init_array, int size, int capacity) throw (std::exception) : cur_size(size), capacity(capacity) {
            if (capacity < size) {
                throw std::exception();
            }
            array = new heap_timer* [capacity];
            if (!array) {
                throw std::exception();
            }
            for (int i = 0; i < capacity; ++i) {
                array[i] = NULL;
            }
            if (size != 0) {
                for (int i = 0; i < size; ++i) {
                    array[i] = init_array[i];
                }
                for (int i = (cur_size - 1) / 2; i >= 0; --i) {
                    percolate_down(i);
                }
            }
        }

        ~time_heap() {
            for (int i = 0; i < cur_size; ++i) {
                delete array[i];
            }
            delete[] array;
        }

        void add_timer(heap_timer* timer) throw (std::exception) {
            if (!timer) {
                return;
            }
            if (cur_size >= capacity) {
                resize();
            }
            int hole = cur_size++;
            int parent = 0;
            for (; hole > 0; hole = parent) { // 上滤
                parent = (hole - 1) / 2;
                if (array[parent]->expire <= timer->expire) {
                    break;
                }
                array[hole] = array[parent];
            }
            array[hole] = timer;
        }

        void del_timer(heap_timer* timer) {
            if (!timer) {
                return;
            }
            timer->cb_func = NULL; // 所谓的延迟销毁，节省真正删除该定时器造成的开销，缺点是容易使数组膨胀
        }

        heap_timer* top() const {
            if (empty()) {
                return NULL;
            }
            return array[0];
        }

        void pop_timer() {
            if (empty()) {
                return;
            }
            if (array[0]) {
                delete array[0];
                array[0] = array[--cur_size];
                percolate_down(0);
            }
        }

        void tick() { // 把所有到期的事件都处理掉
            heap_timer* tmp = array[0];
            time_t cur = timer(NULL);
            while (!empty()) {
                if (!tmp) {
                    break;
                }
                if (tmp->expire > cur) {
                    break;
                }
                if (array[0]->cb_func) {
                    array[0]->cb_func(array[0]->user_data);
                }
                pop_timer();
                tmp = array[0];
            }
        }

        bool empty() const {
            return cur_size == 0;
        }

    private:
        void percolate_down(int hole) {
            heap_timer* temp = array[hole];
            int child = 0;
            for (; ((hole * 2 + 1) <= (cur_size - 1)); hole = child) {
                child = hole * 2 + 1;
                if ((child < (cur_size - 1)) && (array[child + 1]->expire < array[child]->expire)) { // 右孩子比左孩子小，换右孩子
                    ++child;
                }
                if (array[child]->expire < temp->expire) { // 交换操作
                    array[hole] = array[child];
                } else {
                    break;
                }
            }
            array[hole] = temp;
        }

        void resize() throw (std::exception) {
            heap_timer** temp = new heap_timer* [2 * capacity];
            for (int i = 0; i < 2 * capacity; ++i) {
                temp[i] = NULL;
            }
            if (!temp) {
                throw std::exception();
            }
            capacity = 2 * capacity;
            for (int i = 0; i < cur_size; ++i) {
                temp[i] = array[i];
            }
            delete[] array;
            array = temp;
        }

        heap_timer** array;
        int capacity;
        int cur_size;
}

#endif

堆是一种高效的数据结构，不熟悉堆的同学先学习下堆。



上图来自Linux高性能服务器编程——游双$P_{211}$

添加一个定时器的时间复杂度为$O(log_2n)$，删除定时器复杂度为$O(1)$，执行一个定时器时间复杂度为$O(1)$。

---

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