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