1/* $NetBSD: minheap-internal.h,v 1.4 2021/04/07 03:36:48 christos Exp $ */ 2/* 3 * Copyright (c) 2007-2012 Niels Provos and Nick Mathewson 4 * 5 * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com> 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. The name of the author may not be used to endorse or promote products 16 * derived from this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29#ifndef MINHEAP_INTERNAL_H_INCLUDED_ 30#define MINHEAP_INTERNAL_H_INCLUDED_ 31 32#include "event2/event-config.h" 33#include "evconfig-private.h" 34#include "event2/event.h" 35#include "event2/event_struct.h" 36#include "event2/util.h" 37#include "util-internal.h" 38#include "mm-internal.h" 39 40typedef struct min_heap 41{ 42 struct event** p; 43 unsigned n, a; 44} min_heap_t; 45 46static inline void min_heap_ctor_(min_heap_t* s); 47static inline void min_heap_dtor_(min_heap_t* s); 48static inline void min_heap_elem_init_(struct event* e); 49static inline int min_heap_elt_is_top_(const struct event *e); 50static inline int min_heap_empty_(min_heap_t* s); 51static inline unsigned min_heap_size_(min_heap_t* s); 52static inline struct event* min_heap_top_(min_heap_t* s); 53static inline int min_heap_reserve_(min_heap_t* s, unsigned n); 54static inline int min_heap_push_(min_heap_t* s, struct event* e); 55static inline struct event* min_heap_pop_(min_heap_t* s); 56static inline int min_heap_adjust_(min_heap_t *s, struct event* e); 57static inline int min_heap_erase_(min_heap_t* s, struct event* e); 58static inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e); 59static inline void min_heap_shift_up_unconditional_(min_heap_t* s, unsigned hole_index, struct event* e); 60static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e); 61 62#define min_heap_elem_greater(a, b) \ 63 (evutil_timercmp(&(a)->ev_timeout, &(b)->ev_timeout, >)) 64 65void min_heap_ctor_(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; } 66void min_heap_dtor_(min_heap_t* s) { if (s->p) mm_free(s->p); } 67void min_heap_elem_init_(struct event* e) { e->ev_timeout_pos.min_heap_idx = -1; } 68int min_heap_empty_(min_heap_t* s) { return 0u == s->n; } 69unsigned min_heap_size_(min_heap_t* s) { return s->n; } 70struct event* min_heap_top_(min_heap_t* s) { return s->n ? *s->p : 0; } 71 72int min_heap_push_(min_heap_t* s, struct event* e) 73{ 74 if (s->n == UINT32_MAX || min_heap_reserve_(s, s->n + 1)) 75 return -1; 76 min_heap_shift_up_(s, s->n++, e); 77 return 0; 78} 79 80struct event* min_heap_pop_(min_heap_t* s) 81{ 82 if (s->n) 83 { 84 struct event* e = *s->p; 85 min_heap_shift_down_(s, 0u, s->p[--s->n]); 86 e->ev_timeout_pos.min_heap_idx = -1; 87 return e; 88 } 89 return 0; 90} 91 92int min_heap_elt_is_top_(const struct event *e) 93{ 94 return e->ev_timeout_pos.min_heap_idx == 0; 95} 96 97int min_heap_erase_(min_heap_t* s, struct event* e) 98{ 99 if (-1 != e->ev_timeout_pos.min_heap_idx) 100 { 101 struct event *last = s->p[--s->n]; 102 unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2; 103 /* we replace e with the last element in the heap. We might need to 104 shift it upward if it is less than its parent, or downward if it is 105 greater than one or both its children. Since the children are known 106 to be less than the parent, it can't need to shift both up and 107 down. */ 108 if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last)) 109 min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, last); 110 else 111 min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last); 112 e->ev_timeout_pos.min_heap_idx = -1; 113 return 0; 114 } 115 return -1; 116} 117 118int min_heap_adjust_(min_heap_t *s, struct event *e) 119{ 120 if (-1 == e->ev_timeout_pos.min_heap_idx) { 121 return min_heap_push_(s, e); 122 } else { 123 unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2; 124 /* The position of e has changed; we shift it up or down 125 * as needed. We can't need to do both. */ 126 if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], e)) 127 min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, e); 128 else 129 min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, e); 130 return 0; 131 } 132} 133 134int min_heap_reserve_(min_heap_t* s, unsigned n) 135{ 136 if (s->a < n) 137 { 138 struct event** p; 139 unsigned a = s->a ? s->a * 2 : 8; 140 if (a < n) 141 a = n; 142#if (SIZE_MAX == UINT32_MAX) 143 if (a > SIZE_MAX / sizeof *p) 144 return -1; 145#endif 146 if (!(p = (struct event**)mm_realloc(s->p, a * sizeof *p))) 147 return -1; 148 s->p = p; 149 s->a = a; 150 } 151 return 0; 152} 153 154void min_heap_shift_up_unconditional_(min_heap_t* s, unsigned hole_index, struct event* e) 155{ 156 unsigned parent = (hole_index - 1) / 2; 157 do 158 { 159 (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index; 160 hole_index = parent; 161 parent = (hole_index - 1) / 2; 162 } while (hole_index && min_heap_elem_greater(s->p[parent], e)); 163 (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index; 164} 165 166void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e) 167{ 168 unsigned parent = (hole_index - 1) / 2; 169 while (hole_index && min_heap_elem_greater(s->p[parent], e)) 170 { 171 (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index; 172 hole_index = parent; 173 parent = (hole_index - 1) / 2; 174 } 175 (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index; 176} 177 178static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e) 179{ 180 unsigned min_child = 2 * (hole_index + 1); 181 while (min_child <= s->n) 182 { 183 min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]); 184 if (!(min_heap_elem_greater(e, s->p[min_child]))) 185 break; 186 (s->p[hole_index] = s->p[min_child])->ev_timeout_pos.min_heap_idx = hole_index; 187 hole_index = min_child; 188 min_child = 2 * (hole_index + 1); 189 } 190 (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index; 191} 192 193#endif /* MINHEAP_INTERNAL_H_INCLUDED_ */ 194