1290001Sglebius/* 2290001Sglebius * Copyright (c) 2007-2012 Niels Provos and Nick Mathewson 3290001Sglebius * 4290001Sglebius * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com> 5290001Sglebius * 6290001Sglebius * Redistribution and use in source and binary forms, with or without 7290001Sglebius * modification, are permitted provided that the following conditions 8290001Sglebius * are met: 9290001Sglebius * 1. Redistributions of source code must retain the above copyright 10290001Sglebius * notice, this list of conditions and the following disclaimer. 11290001Sglebius * 2. Redistributions in binary form must reproduce the above copyright 12290001Sglebius * notice, this list of conditions and the following disclaimer in the 13290001Sglebius * documentation and/or other materials provided with the distribution. 14290001Sglebius * 3. The name of the author may not be used to endorse or promote products 15290001Sglebius * derived from this software without specific prior written permission. 16290001Sglebius * 17290001Sglebius * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18290001Sglebius * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19290001Sglebius * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20290001Sglebius * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21290001Sglebius * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22290001Sglebius * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23290001Sglebius * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24290001Sglebius * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25290001Sglebius * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26290001Sglebius * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27290001Sglebius */ 28290001Sglebius#ifndef MINHEAP_INTERNAL_H_INCLUDED_ 29290001Sglebius#define MINHEAP_INTERNAL_H_INCLUDED_ 30290001Sglebius 31290001Sglebius#include "event2/event-config.h" 32290001Sglebius#include "evconfig-private.h" 33290001Sglebius#include "event2/event.h" 34290001Sglebius#include "event2/event_struct.h" 35290001Sglebius#include "event2/util.h" 36290001Sglebius#include "util-internal.h" 37290001Sglebius#include "mm-internal.h" 38290001Sglebius 39290001Sglebiustypedef struct min_heap 40290001Sglebius{ 41290001Sglebius struct event** p; 42290001Sglebius unsigned n, a; 43290001Sglebius} min_heap_t; 44290001Sglebius 45290001Sglebiusstatic inline void min_heap_ctor_(min_heap_t* s); 46290001Sglebiusstatic inline void min_heap_dtor_(min_heap_t* s); 47290001Sglebiusstatic inline void min_heap_elem_init_(struct event* e); 48290001Sglebiusstatic inline int min_heap_elt_is_top_(const struct event *e); 49290001Sglebiusstatic inline int min_heap_empty_(min_heap_t* s); 50290001Sglebiusstatic inline unsigned min_heap_size_(min_heap_t* s); 51290001Sglebiusstatic inline struct event* min_heap_top_(min_heap_t* s); 52290001Sglebiusstatic inline int min_heap_reserve_(min_heap_t* s, unsigned n); 53290001Sglebiusstatic inline int min_heap_push_(min_heap_t* s, struct event* e); 54290001Sglebiusstatic inline struct event* min_heap_pop_(min_heap_t* s); 55290001Sglebiusstatic inline int min_heap_adjust_(min_heap_t *s, struct event* e); 56290001Sglebiusstatic inline int min_heap_erase_(min_heap_t* s, struct event* e); 57290001Sglebiusstatic inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e); 58290001Sglebiusstatic inline void min_heap_shift_up_unconditional_(min_heap_t* s, unsigned hole_index, struct event* e); 59290001Sglebiusstatic inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e); 60290001Sglebius 61290001Sglebius#define min_heap_elem_greater(a, b) \ 62290001Sglebius (evutil_timercmp(&(a)->ev_timeout, &(b)->ev_timeout, >)) 63290001Sglebius 64290001Sglebiusvoid min_heap_ctor_(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; } 65290001Sglebiusvoid min_heap_dtor_(min_heap_t* s) { if (s->p) mm_free(s->p); } 66290001Sglebiusvoid min_heap_elem_init_(struct event* e) { e->ev_timeout_pos.min_heap_idx = -1; } 67290001Sglebiusint min_heap_empty_(min_heap_t* s) { return 0u == s->n; } 68290001Sglebiusunsigned min_heap_size_(min_heap_t* s) { return s->n; } 69290001Sglebiusstruct event* min_heap_top_(min_heap_t* s) { return s->n ? *s->p : 0; } 70290001Sglebius 71290001Sglebiusint min_heap_push_(min_heap_t* s, struct event* e) 72290001Sglebius{ 73290001Sglebius if (min_heap_reserve_(s, s->n + 1)) 74290001Sglebius return -1; 75290001Sglebius min_heap_shift_up_(s, s->n++, e); 76290001Sglebius return 0; 77290001Sglebius} 78290001Sglebius 79290001Sglebiusstruct event* min_heap_pop_(min_heap_t* s) 80290001Sglebius{ 81290001Sglebius if (s->n) 82290001Sglebius { 83290001Sglebius struct event* e = *s->p; 84290001Sglebius min_heap_shift_down_(s, 0u, s->p[--s->n]); 85290001Sglebius e->ev_timeout_pos.min_heap_idx = -1; 86290001Sglebius return e; 87290001Sglebius } 88290001Sglebius return 0; 89290001Sglebius} 90290001Sglebius 91290001Sglebiusint min_heap_elt_is_top_(const struct event *e) 92290001Sglebius{ 93290001Sglebius return e->ev_timeout_pos.min_heap_idx == 0; 94290001Sglebius} 95290001Sglebius 96290001Sglebiusint min_heap_erase_(min_heap_t* s, struct event* e) 97290001Sglebius{ 98290001Sglebius if (-1 != e->ev_timeout_pos.min_heap_idx) 99290001Sglebius { 100290001Sglebius struct event *last = s->p[--s->n]; 101290001Sglebius unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2; 102290001Sglebius /* we replace e with the last element in the heap. We might need to 103290001Sglebius shift it upward if it is less than its parent, or downward if it is 104290001Sglebius greater than one or both its children. Since the children are known 105290001Sglebius to be less than the parent, it can't need to shift both up and 106290001Sglebius down. */ 107290001Sglebius if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last)) 108290001Sglebius min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, last); 109290001Sglebius else 110290001Sglebius min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last); 111290001Sglebius e->ev_timeout_pos.min_heap_idx = -1; 112290001Sglebius return 0; 113290001Sglebius } 114290001Sglebius return -1; 115290001Sglebius} 116290001Sglebius 117290001Sglebiusint min_heap_adjust_(min_heap_t *s, struct event *e) 118290001Sglebius{ 119290001Sglebius if (-1 == e->ev_timeout_pos.min_heap_idx) { 120290001Sglebius return min_heap_push_(s, e); 121290001Sglebius } else { 122290001Sglebius unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2; 123290001Sglebius /* The position of e has changed; we shift it up or down 124290001Sglebius * as needed. We can't need to do both. */ 125290001Sglebius if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], e)) 126290001Sglebius min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, e); 127290001Sglebius else 128290001Sglebius min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, e); 129290001Sglebius return 0; 130290001Sglebius } 131290001Sglebius} 132290001Sglebius 133290001Sglebiusint min_heap_reserve_(min_heap_t* s, unsigned n) 134290001Sglebius{ 135290001Sglebius if (s->a < n) 136290001Sglebius { 137290001Sglebius struct event** p; 138290001Sglebius unsigned a = s->a ? s->a * 2 : 8; 139290001Sglebius if (a < n) 140290001Sglebius a = n; 141290001Sglebius if (!(p = (struct event**)mm_realloc(s->p, a * sizeof *p))) 142290001Sglebius return -1; 143290001Sglebius s->p = p; 144290001Sglebius s->a = a; 145290001Sglebius } 146290001Sglebius return 0; 147290001Sglebius} 148290001Sglebius 149290001Sglebiusvoid min_heap_shift_up_unconditional_(min_heap_t* s, unsigned hole_index, struct event* e) 150290001Sglebius{ 151290001Sglebius unsigned parent = (hole_index - 1) / 2; 152290001Sglebius do 153290001Sglebius { 154290001Sglebius (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index; 155290001Sglebius hole_index = parent; 156290001Sglebius parent = (hole_index - 1) / 2; 157290001Sglebius } while (hole_index && min_heap_elem_greater(s->p[parent], e)); 158290001Sglebius (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index; 159290001Sglebius} 160290001Sglebius 161290001Sglebiusvoid min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e) 162290001Sglebius{ 163290001Sglebius unsigned parent = (hole_index - 1) / 2; 164290001Sglebius while (hole_index && min_heap_elem_greater(s->p[parent], e)) 165290001Sglebius { 166290001Sglebius (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index; 167290001Sglebius hole_index = parent; 168290001Sglebius parent = (hole_index - 1) / 2; 169290001Sglebius } 170290001Sglebius (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index; 171290001Sglebius} 172290001Sglebius 173290001Sglebiusvoid min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e) 174290001Sglebius{ 175290001Sglebius unsigned min_child = 2 * (hole_index + 1); 176290001Sglebius while (min_child <= s->n) 177290001Sglebius { 178290001Sglebius min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]); 179290001Sglebius if (!(min_heap_elem_greater(e, s->p[min_child]))) 180290001Sglebius break; 181290001Sglebius (s->p[hole_index] = s->p[min_child])->ev_timeout_pos.min_heap_idx = hole_index; 182290001Sglebius hole_index = min_child; 183290001Sglebius min_child = 2 * (hole_index + 1); 184290001Sglebius } 185290001Sglebius (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index; 186290001Sglebius} 187290001Sglebius 188290001Sglebius#endif /* MINHEAP_INTERNAL_H_INCLUDED_ */ 189