1275970Scy/* 2275970Scy * Copyright (c) 2007-2012 Niels Provos and Nick Mathewson 3275970Scy * 4275970Scy * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com> 5275970Scy * 6275970Scy * Redistribution and use in source and binary forms, with or without 7275970Scy * modification, are permitted provided that the following conditions 8275970Scy * are met: 9275970Scy * 1. Redistributions of source code must retain the above copyright 10275970Scy * notice, this list of conditions and the following disclaimer. 11275970Scy * 2. Redistributions in binary form must reproduce the above copyright 12275970Scy * notice, this list of conditions and the following disclaimer in the 13275970Scy * documentation and/or other materials provided with the distribution. 14275970Scy * 3. The name of the author may not be used to endorse or promote products 15275970Scy * derived from this software without specific prior written permission. 16275970Scy * 17275970Scy * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18275970Scy * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19275970Scy * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20275970Scy * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21275970Scy * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22275970Scy * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23275970Scy * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24275970Scy * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25275970Scy * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26275970Scy * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27275970Scy */ 28275970Scy#ifndef MINHEAP_INTERNAL_H_INCLUDED_ 29275970Scy#define MINHEAP_INTERNAL_H_INCLUDED_ 30275970Scy 31275970Scy#include "event2/event-config.h" 32275970Scy#include "evconfig-private.h" 33275970Scy#include "event2/event.h" 34275970Scy#include "event2/event_struct.h" 35275970Scy#include "event2/util.h" 36275970Scy#include "util-internal.h" 37275970Scy#include "mm-internal.h" 38275970Scy 39275970Scytypedef struct min_heap 40275970Scy{ 41275970Scy struct event** p; 42275970Scy unsigned n, a; 43275970Scy} min_heap_t; 44275970Scy 45275970Scystatic inline void min_heap_ctor_(min_heap_t* s); 46275970Scystatic inline void min_heap_dtor_(min_heap_t* s); 47275970Scystatic inline void min_heap_elem_init_(struct event* e); 48275970Scystatic inline int min_heap_elt_is_top_(const struct event *e); 49275970Scystatic inline int min_heap_empty_(min_heap_t* s); 50275970Scystatic inline unsigned min_heap_size_(min_heap_t* s); 51275970Scystatic inline struct event* min_heap_top_(min_heap_t* s); 52275970Scystatic inline int min_heap_reserve_(min_heap_t* s, unsigned n); 53275970Scystatic inline int min_heap_push_(min_heap_t* s, struct event* e); 54275970Scystatic inline struct event* min_heap_pop_(min_heap_t* s); 55275970Scystatic inline int min_heap_adjust_(min_heap_t *s, struct event* e); 56275970Scystatic inline int min_heap_erase_(min_heap_t* s, struct event* e); 57275970Scystatic inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e); 58275970Scystatic inline void min_heap_shift_up_unconditional_(min_heap_t* s, unsigned hole_index, struct event* e); 59275970Scystatic inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e); 60275970Scy 61275970Scy#define min_heap_elem_greater(a, b) \ 62275970Scy (evutil_timercmp(&(a)->ev_timeout, &(b)->ev_timeout, >)) 63275970Scy 64275970Scyvoid min_heap_ctor_(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; } 65275970Scyvoid min_heap_dtor_(min_heap_t* s) { if (s->p) mm_free(s->p); } 66275970Scyvoid min_heap_elem_init_(struct event* e) { e->ev_timeout_pos.min_heap_idx = -1; } 67275970Scyint min_heap_empty_(min_heap_t* s) { return 0u == s->n; } 68275970Scyunsigned min_heap_size_(min_heap_t* s) { return s->n; } 69275970Scystruct event* min_heap_top_(min_heap_t* s) { return s->n ? *s->p : 0; } 70275970Scy 71275970Scyint min_heap_push_(min_heap_t* s, struct event* e) 72275970Scy{ 73275970Scy if (min_heap_reserve_(s, s->n + 1)) 74275970Scy return -1; 75275970Scy min_heap_shift_up_(s, s->n++, e); 76275970Scy return 0; 77275970Scy} 78275970Scy 79275970Scystruct event* min_heap_pop_(min_heap_t* s) 80275970Scy{ 81275970Scy if (s->n) 82275970Scy { 83275970Scy struct event* e = *s->p; 84275970Scy min_heap_shift_down_(s, 0u, s->p[--s->n]); 85275970Scy e->ev_timeout_pos.min_heap_idx = -1; 86275970Scy return e; 87275970Scy } 88275970Scy return 0; 89275970Scy} 90275970Scy 91275970Scyint min_heap_elt_is_top_(const struct event *e) 92275970Scy{ 93275970Scy return e->ev_timeout_pos.min_heap_idx == 0; 94275970Scy} 95275970Scy 96275970Scyint min_heap_erase_(min_heap_t* s, struct event* e) 97275970Scy{ 98275970Scy if (-1 != e->ev_timeout_pos.min_heap_idx) 99275970Scy { 100275970Scy struct event *last = s->p[--s->n]; 101275970Scy unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2; 102275970Scy /* we replace e with the last element in the heap. We might need to 103275970Scy shift it upward if it is less than its parent, or downward if it is 104275970Scy greater than one or both its children. Since the children are known 105275970Scy to be less than the parent, it can't need to shift both up and 106275970Scy down. */ 107275970Scy if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last)) 108275970Scy min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, last); 109275970Scy else 110275970Scy min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last); 111275970Scy e->ev_timeout_pos.min_heap_idx = -1; 112275970Scy return 0; 113275970Scy } 114275970Scy return -1; 115275970Scy} 116275970Scy 117275970Scyint min_heap_adjust_(min_heap_t *s, struct event *e) 118275970Scy{ 119275970Scy if (-1 == e->ev_timeout_pos.min_heap_idx) { 120275970Scy return min_heap_push_(s, e); 121275970Scy } else { 122275970Scy unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2; 123275970Scy /* The position of e has changed; we shift it up or down 124275970Scy * as needed. We can't need to do both. */ 125275970Scy if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], e)) 126275970Scy min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, e); 127275970Scy else 128275970Scy min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, e); 129275970Scy return 0; 130275970Scy } 131275970Scy} 132275970Scy 133275970Scyint min_heap_reserve_(min_heap_t* s, unsigned n) 134275970Scy{ 135275970Scy if (s->a < n) 136275970Scy { 137275970Scy struct event** p; 138275970Scy unsigned a = s->a ? s->a * 2 : 8; 139275970Scy if (a < n) 140275970Scy a = n; 141275970Scy if (!(p = (struct event**)mm_realloc(s->p, a * sizeof *p))) 142275970Scy return -1; 143275970Scy s->p = p; 144275970Scy s->a = a; 145275970Scy } 146275970Scy return 0; 147275970Scy} 148275970Scy 149275970Scyvoid min_heap_shift_up_unconditional_(min_heap_t* s, unsigned hole_index, struct event* e) 150275970Scy{ 151275970Scy unsigned parent = (hole_index - 1) / 2; 152275970Scy do 153275970Scy { 154275970Scy (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index; 155275970Scy hole_index = parent; 156275970Scy parent = (hole_index - 1) / 2; 157275970Scy } while (hole_index && min_heap_elem_greater(s->p[parent], e)); 158275970Scy (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index; 159275970Scy} 160275970Scy 161275970Scyvoid min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e) 162275970Scy{ 163275970Scy unsigned parent = (hole_index - 1) / 2; 164275970Scy while (hole_index && min_heap_elem_greater(s->p[parent], e)) 165275970Scy { 166275970Scy (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index; 167275970Scy hole_index = parent; 168275970Scy parent = (hole_index - 1) / 2; 169275970Scy } 170275970Scy (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index; 171275970Scy} 172275970Scy 173275970Scyvoid min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e) 174275970Scy{ 175275970Scy unsigned min_child = 2 * (hole_index + 1); 176275970Scy while (min_child <= s->n) 177275970Scy { 178275970Scy min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]); 179275970Scy if (!(min_heap_elem_greater(e, s->p[min_child]))) 180275970Scy break; 181275970Scy (s->p[hole_index] = s->p[min_child])->ev_timeout_pos.min_heap_idx = hole_index; 182275970Scy hole_index = min_child; 183275970Scy min_child = 2 * (hole_index + 1); 184275970Scy } 185275970Scy (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index; 186275970Scy} 187275970Scy 188275970Scy#endif /* MINHEAP_INTERNAL_H_INCLUDED_ */ 189