libevent中最小堆实现算法解析

2017-12-19 12:02:58来源:cnblogs.com作者:nengm人点击

分享

libevent,一个非常好的c的网络库,最近开始学习并分析下,做个记录。源码选用的1.4版本。因为感觉这版的代码比较精简,也没有太多宏定义,个人感觉适合学习原理。

从哪里开始呢,我选择从一些最简单的基础的东西开始,由简入繁。

今天就带来libevent的最小堆生成,体会下libevent作者如何实现最小堆的。最小堆用在libevent的时间管理上,来计算是否超时。

最小堆:是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于其左子节点和右子节点的值。

1.min_heap_shift_up_   插入元素后向上调整

2.min_heap_shift_down_ 元素向下调整(删除元素)

3.代码注释

  1 /*  2  * Copyright (c) 2006 Maxim Yegorushkin <[email protected]>  3  * All rights reserved.  4  *  5  * Redistribution and use in source and binary forms, with or without  6  * modification, are permitted provided that the following conditions  7  * are met:  8  * 1. Redistributions of source code must retain the above copyright  9  *    notice, this list of conditions and the following disclaimer. 10  * 2. Redistributions in binary form must reproduce the above copyright 11  *    notice, this list of conditions and the following disclaimer in the 12  *    documentation and/or other materials provided with the distribution. 13  * 3. The name of the author may not be used to endorse or promote products 14  *    derived from this software without specific prior written permission. 15  * 16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26  */ 27 #ifndef _MIN_HEAP_H_ 28 #define _MIN_HEAP_H_ 29  30 #include "event.h" 31 #include "evutil.h" 32  33 //最小堆,是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于其左子节点和右子节点的值。 34 typedef struct min_heap 35 { 36     //动态分配内存用来保存指向*event的指针 37     struct event** p; 38     //n为元素个数,a为个数容量 39     unsigned n, a; 40 } min_heap_t; 41  42 static inline void           min_heap_ctor(min_heap_t* s); 43 static inline void           min_heap_dtor(min_heap_t* s); 44 static inline void           min_heap_elem_init(struct event* e); 45 static inline int            min_heap_elem_greater(struct event *a, struct event *b); 46 static inline int            min_heap_empty(min_heap_t* s); 47 static inline unsigned       min_heap_size(min_heap_t* s); 48 static inline struct event*  min_heap_top(min_heap_t* s); 49 static inline int            min_heap_reserve(min_heap_t* s, unsigned n); 50 static inline int            min_heap_push(min_heap_t* s, struct event* e); 51 static inline struct event*  min_heap_pop(min_heap_t* s); 52 static inline int            min_heap_erase(min_heap_t* s, struct event* e); 53 static inline void           min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e); 54 static inline void           min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e); 55  56 int min_heap_elem_greater(struct event *a, struct event *b) 57 { 58     return evutil_timercmp(&a->ev_timeout, &b->ev_timeout, >); 59 } 60  61 void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; } 62 void min_heap_dtor(min_heap_t* s) { if(s->p) free(s->p); } 63 void min_heap_elem_init(struct event* e) { e->min_heap_idx = -1; } 64 int min_heap_empty(min_heap_t* s) { return 0u == s->n; } 65 unsigned min_heap_size(min_heap_t* s) { return s->n; } 66 struct event* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; } 67  68 //插入元素 69 int min_heap_push(min_heap_t* s, struct event* e) 70 { 71     //检查内存 72     if(min_heap_reserve(s, s->n + 1)) 73         return -1; 74  75     //插入元素向上调整 76     min_heap_shift_up_(s, s->n++, e); 77     return 0; 78 } 79  80 //pop头元素 81 struct event* min_heap_pop(min_heap_t* s) 82 { 83     if(s->n) 84     { 85         //->优先级比*高 86         //e指向头元素的指针 87         struct event* e = *s->p; 88         //元素向下调整,0U代表头节点索引,s->p[--s->n]:最下层最右边元素,用于插入后填充空出的位置 89         min_heap_shift_down_(s, 0u, s->p[--s->n]); 90  91         //头元素在堆中索引赋值为-1,出堆 92         e->min_heap_idx = -1; 93         return e; 94     } 95     return 0; 96 } 97  98 //删除堆中等于e的元素 99 int min_heap_erase(min_heap_t* s, struct event* e)100 {101     if(((unsigned int)-1) != e->min_heap_idx)102     {103         struct event *last = s->p[--s->n];104         //父节点索引105         unsigned parent = (e->min_heap_idx - 1) / 2;106     /* we replace e with the last element in the heap.  We might need to107        shift it upward if it is less than its parent, or downward if it is108        greater than one or both its children. Since the children are known109        to be less than the parent, it can't need to shift both up and110        down. */111         //如果e不是根元素,当前e的父节点值大于last,需要进行向上调整112         if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))113              min_heap_shift_up_(s, e->min_heap_idx, last);114         else115         //如果e是根元素或者e的父节点元素值不大于last,元素向下调整,e->min_heap_idx为头节点索引,last:最下层最右边元素116         //,用于插入后填充空出的位置117              min_heap_shift_down_(s, e->min_heap_idx, last);118         //将e元素出堆119         e->min_heap_idx = -1;120         return 0;121     }122     return -1;123 }124 125 //调整分配内存126 int min_heap_reserve(min_heap_t* s, unsigned n)127 {128     //如果元素的容量小于元素个数,需要重新分配内存129     if(s->a < n)130     {131         struct event** p;132         //a原来默认为0就分配为8,如果以前有值(不是第一次调整),就扩大两倍133         unsigned a = s->a ? s->a * 2 : 8;134         //如果a还不够,直接让a等于n,元素个数和容量相同135         if(a < n)136             a = n;137         //重新调整内存,连续分配138         if(!(p = (struct event**)realloc(s->p, a * sizeof *p)))139             return -1;140         //首地址141         s->p = p;142         //容量143         s->a = a;144     }145     return 0;146 }147 148 //插入元素后向上调整149 void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)150 {151     //父节点的索引152     unsigned parent = (hole_index - 1) / 2;153     //如果hole_index不等于0且父节点元素大于所给的元素,继续比较,直到到达hole_index为根元素,154     //或者现在的父元素大于了e,找到插入的位置155     while(hole_index && min_heap_elem_greater(s->p[parent], e))156     {157         //父节点元素值大,将父节点放到现在的hole_index上的位置158         (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;159 160         //hole_index赋值为父节点的索引161         hole_index = parent;162 163         //找到现在的hole_index的父节点索引164         parent = (hole_index - 1) / 2;165     }166 167     //跳出循环找到了要插入的位置,位置的索引就是现在的hole_index168     (s->p[hole_index] = e)->min_heap_idx = hole_index;169 }170 171 //元素向下调整(删除元素)172 void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)173 {174     //右孩子索引175     unsigned min_child = 2 * (hole_index + 1);176     //存在右孩子,如果不存在右子树,直接向下调整,因为最多存在左子树,且值肯定不小于父节点,可以直接向下调整177     while(min_child <= s->n)178     {179         //选择左右孩子值最小的孩子的索引,根据优先级可以加()进行更好的查看180         min_child -= ((min_child == s->n) || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]));181         //如果e元素不大于最小的孩子元素,没有必要再继续,hole_index就是他的位置182         if(!(min_heap_elem_greater(e, s->p[min_child])))183             break;184         //将小的孩子元素放到hole_index位置上185         (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;186         //hole_index保存当前小的孩子索引187         hole_index = min_child;188         //当前小的孩子位置空出,继续下一次循环,比较当前小的孩子的左右孩子189         min_child = 2 * (hole_index + 1);190     }191     //将e元素放到hole_index,然后向上调整。一般e元素是取最下层最右节点。不排除有可能比现在的位置上的父节点下192     //所以需要向上调整193     min_heap_shift_up_(s, hole_index,  e);194 }195 196 #endif /* _MIN_HEAP_H_ */

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台