精华内容
下载资源
问答
  • 基于STL的小根堆定时器实现(C++)

    千次阅读 2019-12-17 11:39:20
    基于STL的小根堆定时器实现(C++) 详细内容参见:《Linux高性能服务器编程》第11章 定时器。 该书我已上传到CSND:https://download.csdn.net/download/qq_34039018/12035959 下面谈的是个人理解,观点不一定对。 ...

    基于STL的小根堆定时器实现(C++)

    详细内容参见:《Linux高性能服务器编程》第11章 定时器。
    下面谈的是个人理解,观点不一定对。
      小根堆定时器的优点如下:
      1. 添加时间复杂度为O(1);
      2. 删除时间复杂度为O(1);
      3.执行一个定时器的时间复杂度为O(1);
      4.比起传统的按照固定时间间隔执行tick函数的链表/时间轮定时器,小根堆定时器可以动态地将所有定时器时间的最小的一个定时器的超时值作为心博时间。这样,一旦心博函数tick()被调用,则超时时间最小的定时器一定到期,执行相关处理。然后将下一个最小值定时器作为下一次的超时时间。这样,减少了调用tick()的次数。
      由此可见,最小堆定时器相比链表定时器和时间轮定时器的效率会更好些。
      网上大多是关于时间堆/最小堆定时器的实现都是手写实现堆的增删改等操作,比较麻烦。因为C++的内部已经有优先队列,直接调用相关函数就可以构建堆、增加、修改等操作,函数如下:

    #include<algorithm>
    using namespace std;
    
    make_heap(array.begin(), array.end());	//构建堆
    push_heap(array.begin(), array.end());		// 插入元素
    pop_heap(array.begin(), array.end());		// 弹出元素
    sort_heap(array.begin(), array.end());		// 排序
    

      因此我没有再把堆的操作那一套函数自己手动实现了,直接使用algorithm的内置函数实现小根堆定时器。原书中是手动实现了一个堆。

    代码

    • heap_timer.h
    //
    // Created by yongpu on 2019/12/16.
    //
    
    #ifndef HEAP_TIMER_HEAP_TIMER_H
    #define HEAP_TIMER_HEAP_TIMER_H
    
    #include <iostream>
    #include <netinet/in.h>
    #include <time.h>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    #define BUFFER_SIZE 64
    
    struct client_data;
    
    
    /* 定时器类 */
    class heap_timer_node {
    public:
        heap_timer_node(int delay) {
    //        expire = time(NULL) + delay;
            expire = delay;
            validFlag = true;
        }
    
    public:
        time_t expire;                      /* 定时器生效的绝对时间 */
        void (*cb_func)(client_data *);     /* 定时器的回调函数 */
        client_data *user_data;             /* 用户数据 */
        bool validFlag;                    /* 有效标志 */
    };
    
    /* 构建堆时的比较函数 */
    bool cmp_heap_timer_node(heap_timer_node *node1, heap_timer_node *node2);
    
    /* 时间堆类 */
    class timer_heap {
    public:
        timer_heap(int cap);
    
        void add_timer(heap_timer_node *timer); /* 添加目标定时器timer */
        void del_timer(heap_timer_node *timer); /* 删除目标定时器timer */
        heap_timer_node *get_top();             /* 获得堆顶部的定时器 */
        void del_top();                         /* 删除堆顶部的定时器 */
        void tick();                            /* 心博函数 */
        void disPlay();                         /* 输出堆中所有定时器 */
        bool is_empty();                        /* 堆是否为空 */
    
        ~timer_heap();                          /* 销毁时间堆 */
    private:
        void resize();                          /* 将当前容量扩大一倍 */
    
    private:
        vector<heap_timer_node *> array;        /* 堆数组 */
        int capacity;                           /* 堆数组的容量 */
        int cur_size;                           /* 堆数组中当前的元素个数 */
        int deleteNum;                          /* 已删除的定时器数量 */
    };
    
    
    /* 绑定socket和定时器 */
    struct client_data {
        sockaddr_in address;
        int sockfd;
        char buf[BUFFER_SIZE];
        heap_timer_node *timer;
    
    };
    
    
    #endif //HEAP_TIMER_HEAP_TIMER_H
    
    
    • heap_timer.cpp
    //
    // Created by yongpu on 2019/12/16.
    //
    
    #include "heap_timer.h"
    
    /* 用于构造堆 */
    bool cmp_heap_timer_node(heap_timer_node *node1, heap_timer_node *node2) {
        return node1->expire > node2->expire;
    }
    
    /* 构造函数 */
    timer_heap::timer_heap(int cap) {
        this->capacity = cap;
        this->array.resize(cap);
        this->cur_size = 0;
        this->deleteNum = 0;
        for (int i = 0; i < cap; i++) {
            this->array[i] = nullptr;
        }
        make_heap(array.begin(), array.begin() + cur_size, cmp_heap_timer_node);
    }
    
    /* 添加一个定时器 */
    void timer_heap::add_timer(heap_timer_node *timer) {
        if (timer == nullptr) {
            return;
        }
        if (cur_size >= capacity) {     /* 无空间,则将array扩大一倍 */
            resize();
        }
    
        /* 插入新元素 */
        array[cur_size] = timer;
        cur_size++;
    
        /* 调整堆 */
        push_heap(array.begin(), array.begin() + cur_size, cmp_heap_timer_node);
    }
    
    /* 删除一个定时器 */
    void timer_heap::del_timer(heap_timer_node *timer) {
        if (timer == nullptr) {
            return;
        }
        /* 仅仅将目标定时器的回调函数设置为空,即所谓的延迟销毁,
         * 将节省真正删除该定时器造成的开销,但这样做容易造成堆数组膨胀 */
        timer->cb_func = nullptr;
        timer->validFlag = false;   /* 将定时器标记为无效 */
        deleteNum++;
        /* 判断删除数是否达到当前容量的一半,达到了则删除并重新建堆 */
        if (deleteNum >= cur_size / 2) {
            int vaildIndex = 0;
            for (int i = 0; i < cur_size; i++) {
                if (array[i]->validFlag) {
                    array[vaildIndex] = array[i];
                    vaildIndex++;
                    array[i] = nullptr;
                } else {
                    delete array[i];
                    array[i] = nullptr;
                }
            }
            cur_size = vaildIndex;
            make_heap(array.begin(), array.begin() + cur_size, cmp_heap_timer_node);
        }
    }
    
    /* 获取堆顶定时器 */
    heap_timer_node *timer_heap::get_top() {
        if (is_empty()) {
            return nullptr;
        } else {
            return array.front();
        }
    }
    
    /* 删除堆顶定时器 */
    void timer_heap::del_top() {
        /* pop_heap 将堆顶元素移至当前堆的最末尾位置,及array[array.begin() + cur_size-1]处*/
        pop_heap(array.begin(), array.begin() + cur_size, cmp_heap_timer_node);
        /* 删除该定时器 */
        delete array[cur_size - 1];
        array[cur_size - 1] = nullptr;
        cur_size--;
    }
    
    /* 心博函数 */
    void timer_heap::tick() {
        heap_timer_node *topTimer = get_top();
        time_t cur = time(nullptr);
        while (!is_empty()) {
            if (topTimer == nullptr) {
                break;
            }
            /* 如果对顶元素还没有到期,则退出循环 */
            if (topTimer->expire > cur) {
                break;
            }
            /* 否则执行堆顶定时器中的任务 */
            if (topTimer->validFlag && topTimer->cb_func != nullptr) {
                topTimer->cb_func(topTimer->user_data);
            }
            /* 删除堆顶元素 */
            del_top();
            topTimer = get_top();
        }
    }
    
    /* 将array的容量扩大一倍 */
    void timer_heap::resize() {
        array.resize(capacity * 2);
        capacity = capacity * 2;
    }
    
    void timer_heap::disPlay() {
        cout << "disPlay: ";
        for (int i = 0; i < capacity; i++) {
            if (array[i] == nullptr) {
                break;
            }
            cout << array[i]->expire << " ";
        }
        cout << endl;
    }
    
    /* 判断堆是否为空 */
    bool timer_heap::is_empty() {
        return cur_size == 0;
    }
    
    /* 析构函数,销毁堆 */
    timer_heap::~timer_heap() {
        for (int i = 0; i < cur_size; i++) {
            delete array[i];
            array[i] = nullptr;
        }
    }
    
    • main.cpp
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include "heap_timer.h"
    
    using namespace std;
    
    int main() {
        heap_timer_node *node1 = new heap_timer_node(6);
        heap_timer_node *node2 = new heap_timer_node(2);
        heap_timer_node *node3 = new heap_timer_node(4);
        heap_timer_node *node4 = new heap_timer_node(11);
        heap_timer_node *node5 = new heap_timer_node(5);
    
        timer_heap heaps(10);
        heaps.add_timer(node1);
        heaps.add_timer(node2);
        heaps.add_timer(node3);
        heaps.add_timer(node4);
        heaps.add_timer(node5);
    
        heaps.get_top();
    
        heaps.disPlay();
        heaps.del_timer(node1);
    
        heaps.del_timer(node2);
    
        heaps.del_timer(node3);
        heaps.disPlay();
    
    
        return 0;
    }
    
    
    • 运行
      在这里插入图片描述
    展开全文
  • 在libevent中定时器实现是通过基于最小的优先级队列来实现的,对于这两个数据结构比较陌生的可以去翻算法导论的6.5节中,主要的源码都在min_heap.c中,下面是C++的实现。 数据结构 typedef struct min_...

    在libevent中定时器的实现是通过基于最小堆的优先级队列来实现的,对于这两个数据结构比较陌生的可以去翻算法导论的6.5节中,主要的源码都在min_heap.c中,下面是C++的实现。

    数据结构

    typedef struct min_heap
    {
      struct event** p;
      unsigned n, a;
    } min_heap_t;
    在这个数据结构中 p也就是整个优先级队列,而这个优先级队列的每个节点都是一个struct *event.n表示这个队列的元素个数。a表示这个队列的大小。

    #ifndef VOS_TIMER_H_  
    #define VOS_TIMER_H_  
      
    #define RELATIVE_TIMER 1  
    #define ABSOLUTE_TIMER 2  
      
    namespace vos  
    {  
      
    struct event;  
    typedef struct min_heap  
    {  
        struct event** p;  
        unsigned n, a;  
    } min_heap_t;  
      
    class Timer  
    {  
    public:  
        Timer();  
        virtual ~Timer();  
        /************************************** 
         * input: interval: 每次执行的时间隔间, 单位是毫秒。 
         *        fun arg : 回调函数以及参数。 
         *        flag    : 绝对定时器还是相对定时器,如果是相对定时器 
         *        exe_num : 只有在相对定时器才有效,表示执行的次数。最少为1次 
         * return: 生成定时器的ID 
         **************************************/  
        unsigned int timer_add(int interval, void (*fun)(void*), void *arg,  int flag = ABSOLUTE_TIMER,  
                int exe_num = 0);  
        /*************************************** 
         * description: 
         * 去掉已经加入的定时器,比如产生定时器的母体已经消亡了,在消亡之间要将其删除。 
         * 相对定时器在任务完成后会Timer会自己释放掉。 
         ***************************************/  
        bool timer_remove(unsigned int timer_id);  
        /*************************************** 
         * description: Timer属于被动对象,没有自己的执行线程,属于被调用者。这样主要是为了避免产生线程同步。 
         * 定时器的循环处理函数,由定时器的拥有者进行循环调用。它的最小时间间隔决定了定时器的精度。 
         ***************************************/  
        int timer_process();  
      
    private:  
        struct min_heap _min_heap;  
        unsigned int _timer_id;  
    };  
      
    } /* namespace vos */  
    #endif /* VOS_TIMER_H_ */

    #include "vos_timer.h"  
      
    #ifndef __WINDOWS  
    #include <sys/time.h>  
    #else  
    #include <windows.h>  
    #endif  
      
    #include <time.h>  
    #include <stdio.h>  
    #include <stdlib.h>  
      
    #define evutil_timercmp(tvp, uvp, cmp)                          \  
        (((tvp)->tv_sec == (uvp)->tv_sec) ?                           \  
        ((tvp)->tv_usec cmp (uvp)->tv_usec) :                     \  
        ((tvp)->tv_sec cmp (uvp)->tv_sec))  
      
    #define evutil_timersub(tvp, uvp, vvp)                      \  
        do {                                                    \  
        (vvp)->tv_sec = (tvp)->tv_sec - (uvp)->tv_sec;     \  
        (vvp)->tv_usec = (tvp)->tv_usec - (uvp)->tv_usec;  \  
        if ((vvp)->tv_usec < 0) {                         \  
        (vvp)->tv_sec--;                             \  
        (vvp)->tv_usec += 1000000;                       \  
        }                                                   \  
        } while (0)  
      
    #define evutil_timeradd(tvp, uvp, vvp)                          \  
        do {                                                        \  
        (vvp)->tv_sec = (tvp)->tv_sec + (uvp)->tv_sec;         \  
        (vvp)->tv_usec = (tvp)->tv_usec + (uvp)->tv_usec;       \  
        if ((vvp)->tv_usec >= 1000000) {                      \  
        (vvp)->tv_sec++;                                 \  
        (vvp)->tv_usec -= 1000000;                           \  
        }                                                       \  
        } while (0)  
      
    #ifdef __WINDOWS  
    int gettimeofday(struct timeval* tv, void * attr)  
    {  
        union  
        {  
            long long ns100;  
            FILETIME ft;  
        }now;  
      
        GetSystemTimeAsFileTime (&now.ft);  
        tv->tv_usec = (long) ((now.ns100 / 10LL) % 1000000LL);  
        tv->tv_sec = (long) ((now.ns100 - 116444736000000000LL) / 10000000LL);  
        return (0);  
    }  
    #endif  
      
    namespace vos  
    {  
    struct event  
    {  
        unsigned int min_heap_idx; /* for managing timeouts */  
        unsigned int timer_id;  
        struct timeval ev_interval;  
        struct timeval ev_timeout;  
        int ev_exe_num;  
      
        void (*ev_callback)(void *arg);  
        void *ev_arg;  
      
        int ev_res; /* result passed to event callback */  
        int ev_flags;  
    };  
      
    /***构造函数  ***************/  
    static inline void min_heap_ctor(min_heap_t* s);  
    /***析构函数  ***************/  
    static inline void min_heap_dtor(min_heap_t* s);  
    /***初始化函数  ***************/  
    static inline void min_heap_elem_init(struct event* e);  
    /****比较函数***************/  
    static inline int min_heap_elem_greater(struct event *a, struct event *b);  
      
    static inline int min_heap_empty(min_heap_t* s);  
      
    static inline unsigned min_heap_size(min_heap_t* s);  
    /****返回栈顶元素************/  
    static inline struct event* min_heap_top(min_heap_t* s);  
    /****调整定时器的大小*********/  
    static inline int min_heap_reserve(min_heap_t* s, unsigned n);  
    /****放入数据*************/  
    static inline int min_heap_push(min_heap_t* s, struct event* e);  
    /****取得最后上面的数据******/  
    static inline struct event* min_heap_pop(min_heap_t* s);  
    /****消除一个定时器元素*******/  
    static inline int min_heap_erase(min_heap_t* s, struct event* e);  
    /****向上调整 ************/  
    static inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e);  
    /****向下调整************/  
    static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e);  
      
    static inline void gettime(struct timeval *tm);  
      
    Timer::Timer() :  
            _timer_id(0)  
    {  
        min_heap_ctor(&_min_heap);  
    }  
      
    Timer::~Timer()  
    {  
        for (int i = 0; i < _min_heap.n; i++)  
        {  
            free(_min_heap.p[i]);  
        }  
        min_heap_dtor(&_min_heap);  
    }  
      
    unsigned int Timer::timer_add(int interval, void(*fun)(void*), void *arg,  
            int flag /* = ABSOLUTE_TIMER */, int exe_num /* =  0 */)  
    {  
        struct event * ev = (struct event*) malloc(sizeof(struct event));  
        min_heap_elem_init(ev);  
        if (NULL == ev)  
            return NULL;  
        struct timeval now;  
        gettime(&now);  
        ev->ev_interval.tv_sec = interval / 1000;  
        ev->ev_interval.tv_usec = (interval % 1000) * 1000;  
        evutil_timeradd(&now, &(ev->ev_interval), &(ev->ev_timeout));  
        ev->ev_flags = flag;  
        ev->ev_callback = fun;  
        ev->ev_arg = arg;  
        ev->ev_exe_num = exe_num;  
        ev->timer_id = _timer_id++;  
      
        min_heap_push(&_min_heap, ev);  
      
        return ev->timer_id;  
    }  
      
    bool Timer::timer_remove(unsigned int timer_id)  
    {  
        for (int i = 0; i < _min_heap.n; i++)  
        {  
            if (timer_id == _min_heap.p[i]->timer_id)  
            {  
                struct event * e = _min_heap.p[i];  
                min_heap_erase(&_min_heap, _min_heap.p[i]);  
                free(e);  
                return true;  
            }  
        }  
        return false;  
    }  
      
    int Timer::timer_process()  
    {  
        struct event *event;  
        struct timeval now;  
        while ((event = min_heap_top(&_min_heap)) != NULL)  
        {  
            gettime(&now);  
            if (evutil_timercmp(&now, &(event->ev_timeout), < ))  
                break;  
            min_heap_pop(&_min_heap);  
            event->ev_callback(event->ev_arg);  
            if (event->ev_flags == ABSOLUTE_TIMER  
                    || (event->ev_flags == RELATIVE_TIMER && --event->ev_exe_num > 0))  
            {  
                evutil_timeradd(&(event->ev_timeout), &(event->ev_interval), &(event->ev_timeout));  
                min_heap_push(&_min_heap, event);  
            }  
            else  
            {  
                free(event);  
            }  
        }  
      
        return 0;  
    }  
      
    void gettime(struct timeval *tm)  
    {  
        gettimeofday(tm, NULL);  
    }  
      
    int min_heap_elem_greater(struct event *a, struct event *b)  
    {  
        return evutil_timercmp(&a->ev_timeout, &b->ev_timeout, >);  
    }  
      
    void min_heap_ctor(min_heap_t* s)  
    {  
        s->p = 0;  
        s->n = 0;  
        s->a = 0;  
    }  
      
    void min_heap_dtor(min_heap_t* s)  
    {  
        if (s->p)  
            free(s->p);  
    }  
      
    void min_heap_elem_init(struct event* e)  
    {  
        e->min_heap_idx = -1;  
    }  
      
    int min_heap_empty(min_heap_t* s)  
    {  
        return 0u == s->n;  
    }  
      
    unsigned min_heap_size(min_heap_t* s)  
    {  
        return s->n;  
    }  
      
    struct event* min_heap_top(min_heap_t* s)  
    {  
        return s->n ? *s->p : 0;  
    }  
      
    int min_heap_push(min_heap_t* s, struct event* e)  
    {  
        if (min_heap_reserve(s, s->n + 1))  
            return -1;  
        min_heap_shift_up_(s, s->n++, e);  
        return 0;  
    }  
      
    struct event* min_heap_pop(min_heap_t* s)  
    {  
        if (s->n)  
        {  
            struct event* e = *s->p;  
            min_heap_shift_down_(s, 0u, s->p[--s->n]);  
            e->min_heap_idx = -1;  
            return e;  
        }  
        return 0;  
    }  
      
    int min_heap_erase(min_heap_t* s, struct event* e)  
    {  
        if (((unsigned int) -1) != e->min_heap_idx)  
        {  
            struct event *last = s->p[--s->n];  
            unsigned parent = (e->min_heap_idx - 1) / 2;  
            /* we replace e with the last element in the heap.  We might need to 
             shift it upward if it is less than its parent, or downward if it is 
             greater than one or both its children. Since the children are known 
             to be less than the parent, it can't need to shift both up and 
             down. */  
            if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))  
                min_heap_shift_up_(s, e->min_heap_idx, last);  
            else  
                min_heap_shift_down_(s, e->min_heap_idx, last);  
            e->min_heap_idx = -1;  
            return 0;  
        }  
        return -1;  
    }  
      
    int min_heap_reserve(min_heap_t* s, unsigned n)  
    {  
        if (s->a < n)  
        {  
            struct event** p;  
            unsigned a = s->a ? s->a * 2 : 8;  
            if (a < n)  
                a = n;  
            if (!(p = (struct event**) realloc(s->p, a * sizeof *p)))  
                return -1;  
            s->p = p;  
            s->a = a;  
        }  
        return 0;  
    }  
      
    void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)  
    {  
        unsigned parent = (hole_index - 1) / 2;  
        while (hole_index && min_heap_elem_greater(s->p[parent], e))  
        {  
            (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;  
            hole_index = parent;  
            parent = (hole_index - 1) / 2;  
        }  
        (s->p[hole_index] = e)->min_heap_idx = hole_index;  
    }  
      
    void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)  
    {  
        unsigned min_child = 2 * (hole_index + 1);  
        while (min_child <= s->n)  
        {  
            min_child -= min_child == s->n  
                    || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);  
            if (!(min_heap_elem_greater(e, s->p[min_child])))  
                break;  
            (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;  
            hole_index = min_child;  
            min_child = 2 * (hole_index + 1);  
        }  
        min_heap_shift_up_(s, hole_index, e);  
    }  
    } /* namespace vos */  




    展开全文
  • 所有的数据结构书中都有关于堆的详细介绍,向堆中插入、删除元素时间复杂度都是O(lgN),N为堆中元素的个数,而获取最小key值(小根堆)的复杂度为O(1)。堆是一个完全二叉树,基本存储方式是一个数组。 看函数名都...

     Libevent 源码下载可以去官网  github

     

    Libevent使用堆来管理Timer事件,其key值就是事件的超时时间,源代码位于文件minheap-internal.h中。

    所有的数据结构书中都有关于堆的详细介绍,向堆中插入、删除元素时间复杂度都是O(lgN),N为堆中元素的个数,而获取最小key值(小根堆)的复杂度为O(1)。堆是一个完全二叉树,基本存储方式是一个数组。

    看函数名都挺好懂的,只是下面这个结构体变量命名比较坑....

    typedef struct min_heap
    {
    	struct event** p; // 堆的数组
    	size_t n, a;      // 堆元素个数, 堆分配内存大小
    } min_heap_t;

          Libevent实现的堆还是比较轻巧的,轻巧到什么地方呢,就以插入元素为例,来对比说明,下面伪代码中的size表示当前堆的元素个数:

    典型的代码逻辑如下:

    Heap[size++] = new; // 先放到数组末尾,元素个数+1  
    // 下面就是shift_up()的代码逻辑,不断的将new向上调整  
    _child = size;  
    while(_child>0) // 循环  
    {  
       _parent = (_child-1)/2; // 计算parent  
       if(Heap[_parent].key < Heap[_child].key)  
          break; // 调整结束,跳出循环  
       swap(_parent, _child); // 交换parent和child  
    }  

            而libevent的heap代码对这一过程做了优化,在插入新元素时,只是为新元素预留了一个位置hole(初始时hole位于数组尾部),但并不立刻 将新元素插入到hole上,而是不断向上调整hole的值,将父节点向下调整,最后确认hole就是新元素的所在位置时,才会真正的将新元素插入到 hole上,因此在调整过程中就比上面的代码少了一次赋值的操作, 下面就是min_heap_shift_up_()的源代码逻辑,不断的将新的“预留位置”向上调整:

    void min_heap_shift_up_(min_heap_t* s, size_t hole_index, struct event* e)
    {
        size_t parent = (hole_index - 1) / 2;
    	//如果hole_index不等于0且父节点元素大于所给的元素,继续比较,直到到达hole_index为根元素,
        //或者现在的父元素大于了e,找到插入的位置
        while (hole_index && min_heap_elem_greater(s->p[parent], e))
        {
            //父节点元素值大,将父节点放到现在的hole_index上的位置
    	(s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index;
    		
    	//hole_index赋值为父节点的索引
    	hole_index = parent;
    		
    	//找到现在的hole_index的父节点索引
    	parent = (hole_index - 1) / 2;
        }
    	
    	//跳出循环找到了要插入的位置,位置的索引就是现在的hole_index
        (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
    }

            由于每次调整都少做一次赋值操作,在调整路径比较长时,调整效率会比第一种有所提高。libevent中的min_heap_shift_up_()函数就是上面逻辑的具体实现,对应的向下调整函数是min_heap_shift_down_()。

    void min_heap_shift_down_(min_heap_t* s, size_t hole_index, struct event* e)
    {
        size_t min_child = 2 * (hole_index + 1);  //右孩子索引
    	
    	//存在右孩子,如果不存在右子树,直接向下调整,因为最多存在左子树,且值肯定不小于父节点,可以直接向下调整
        while (min_child <= s->n)
        {
    	//选择左右孩子值最小的孩子的索引,根据优先级可以加()进行更好的查看
    	min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
    	//如果e元素不大于最小的孩子元素,没有必要再继续,hole_index就是他的位置
    	if (!(min_heap_elem_greater(e, s->p[min_child])))
    	    break;
    	//将小的孩子元素放到hole_index位置上
    	(s->p[hole_index] = s->p[min_child])->ev_timeout_pos.min_heap_idx = hole_index;
    	 //hole_index保存当前小的孩子索引
    	hole_index = min_child;
    	//当前小的孩子位置空出,继续下一次循环,比较当前小的孩子的左右孩子
    	min_child = 2 * (hole_index + 1);
        }
    	
    	
        (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
    }

     

    展开全文
  • 最小堆定时器实现

    千次阅读 2013-08-26 22:15:07
    最小堆定时器实现  上一篇博文实现了升序定时器链表,但是存在一个问题:添加定时器的效率偏低。后来产生了两种定时器实现方案:时间轮和时间。下面来实现最小堆定时器。  c++实现的最小堆定时器代码...
    最小堆定时器的实现

         上一篇博文实现了升序定时器链表,但是存在一个问题:添加定时器的效率偏低。后来产生了两种定时器实现方案:时间轮和时间堆。下面来实现最小堆定时器。
         c++实现的最小堆定时器代码如下:
         
    #ifndef intIME_HEAP
    #define intIME_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 = time( NULL ) + delay;
        }
    
    public:
       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; 
        }
    
    public:
        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;
            }
            // lazy delelte
            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 = time( 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;
        }
    
    private:
        heap_timer** array;//堆数组
        int capacity; //堆数组的容量
        int cur_size; //堆数组当前包含元素的个数
    };
    
    #endif
    

    展开全文
  • 最小堆定时器

    2021-03-23 19:52:18
    基于最小堆实现的网络定时器 头文件 // // Created by wenfan on 2021/3/21. // #ifndef MIN_HEAP_H #define MIN_HEAP_H #include <iostream> #include <netinet/in.h> #include <ctime> ...
  • 在不同框架中,这两种事件有不同的实现⽅式; 第⼀种,⽹络事件和时间事件在⼀个线程当中配合使⽤;例如nginx、redis; // 第⼀种 伪代码 while (!quit) { int now = get_now_time();// 单位:ms int timeout = ...
  • 时间堆定时器实现

    2020-09-13 18:43:21
    或者每个父结点的值都小于或等于其左右孩子结点的值,称为顶堆。 大小如下图: 我们将这种逻辑结构映射到数组中,如下图: 我们通过两组简单的公式描述一下上述两种的特性: 大顶堆:arr[i] >= arr[2i+1]...
  • 最小 最小的定义 ...从定义可知,节点是树中的最小值, 最小一般用链表存储,父子节点的关系,用纯数学的关系表示为:假设当前节点的在链表中的索引为n,左子节点为2n+1 ,右子节点为2n+2 ...
  • 基于升序链表的定时器和时间轮都是以固定的频率来调用心搏函数,并在其中依次检测到期的定时器,然后执行到期定时器上的回调函数,这样的定时并不准确,因为可能已有定时器到期了,但是因为心搏函数此时还未调用而...
  • 高性能定时器1——时间 ​ 在网络程序中我们通常要处理三种事件,网络I/O事件、信号以及定时事件,我们可以使用I/O复用系统调用(select、poll、epoll)将这三类事件进行统一处理。我们通常使用定时器来检测一个...
  • 为了更好的使用多核的性能,我们将在每个核上设置一个全局的变量,然后使用散列方式将排队的定时器分发到响应的容器中。 /*我们使用一个宏来控制个数,这样很容易通过编译来控制数量*/ struct ev_loop ev_loops...
  • 时间堆定时器

    2021-06-04 16:49:16
    前面讨论的定时方案都是以固定的频率调用心搏函数tick,并在其中依次检测到期的定时器,然后执行...如此反复,就实现了较为精确的定时。 最小很适合处理这种定时方案。 由于最小是一种完全二叉树,所以我们可以用数
  • 优先队列实现定时器

    2017-02-01 11:19:00
    http://www.cnblogs.com/lewiskyo/p/6359789.html上文介绍了使用数组实现定时器,但因为插入和删除定时器的效率太低,所以这里改用优先队列实现一次。 实现代码如下: 1 #include <iostream> 2 #...
  • 定时器实现

    2021-04-11 20:53:54
    2.4、最小堆实现定时器 2.5、时间轮实现定时器 2.5.1、单层级时间轮 2.5.2、多层级时间轮 1、定时器概述 对于服务端来说,驱动服务端逻辑的事件主要有两个,⼀个是⽹络事件,另⼀个是时间事件; 在不同框架中...
  • 网络编程定时器三:使用最小

    千次阅读 2017-02-06 21:59:58
    前面讨论的定时方案都是以固定频率调用心搏函数tick,并在其中一次检测到期的定时器,然后执行到期定时器上的回调函数。设计定时器的另一中思路是,将所有定器超时时间最小的一个定时器...最小适合这种解决方案,下面
  • 文章来源:点击打开链接跟上一篇,这里写一下时间:时间轮的滴答是固定以指定的槽间隔触发,而时间是以定时器堆中的最小到期时间做定时,也就是alarm(minTimeout),一旦定时器被触发,那么就删除此定时器,更新...
  • 高性能网络编程6--reactor反应定时器管理

    万次阅读 多人点赞 2013-12-20 19:37:23
    在大数据和云计算时代,我们对服务器的处理能力要求...此时就必须用到epoll这样的IO复用,但直接基于它编程在软件工程层面效率是非常差的,我们需要一个网络模型、设计模式,来简化应用编码,反应就是这么一个东东。
  • Libev中在管理定时器时,使用了这种结构,而且除了常见的最小2叉之外,它还实现了更高效的4叉。 之所以要实现4叉,是因为普通2叉的缓存效率较低,所谓缓存效率低,也就是说对CPU缓存的利用率比较低,...
  • 就是说,有N多个定时器,如何来实现高效到点执行定时函数的问题。 在开发Linux网络程序时,通常需要维护多个定时器,如维护客户端心跳时间、检查多个数据包的超时重传等。 定时器的结构有多钟比如链表式,最小,...
  • 2. 最小实现 3. 性质 4. 代码 二、时间 1. 概念简述 2. 实现细节 3. 代码 一、 1. 概念 是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于(或不小于)其左子节点和右...
  • 反应开发模型被绝大多数高性能服务器所选择,上一篇所介绍的IO多路复用是它的实现基础。定时触发功能通常是服务器必备组件,反应模型往往还不得不将定时器的管理囊括在内。本篇将介绍反应模型的特点和用法。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,753
精华内容 1,901
关键字:

小根堆实现定时器