1 /* $OpenBSD: min_heap.h,v 1.6 2019/04/29 17:11:52 tobias Exp $ */
2
3 /*
4 * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com>
5 * All rights reserved.
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 _MIN_HEAP_H_
30 #define _MIN_HEAP_H_
31
32 #include "event.h"
33
34 typedef struct min_heap {
35 struct event **p;
36 size_t n, a;
37 } min_heap_t;
38
39 static inline void min_heap_ctor(min_heap_t * s);
40 static inline void min_heap_dtor(min_heap_t * s);
41 static inline void min_heap_elem_init(struct event * e);
42 static inline int min_heap_elem_greater(struct event * a, struct event * b);
43 static inline int min_heap_empty(min_heap_t * s);
44 static inline size_t min_heap_size(min_heap_t * s);
45 static inline struct event *min_heap_top(min_heap_t * s);
46 static inline int min_heap_reserve(min_heap_t * s, size_t n);
47 static inline int min_heap_push(min_heap_t * s, struct event * e);
48 static inline struct event *min_heap_pop(min_heap_t * s);
49 static inline int min_heap_erase(min_heap_t * s, struct event * e);
50 static inline void min_heap_shift_up_(min_heap_t * s, size_t hole_index, struct event * e);
51 static inline void min_heap_shift_down_(min_heap_t * s, size_t hole_index, struct event * e);
52
53 int
min_heap_elem_greater(struct event * a,struct event * b)54 min_heap_elem_greater(struct event * a, struct event * b)
55 {
56 return timercmp(&a->ev_timeout, &b->ev_timeout, >);
57 }
58
59 void
min_heap_ctor(min_heap_t * s)60 min_heap_ctor(min_heap_t * s)
61 {
62 s->p = 0;
63 s->n = 0;
64 s->a = 0;
65 }
min_heap_dtor(min_heap_t * s)66 void min_heap_dtor(min_heap_t * s) {
67 if (s->p)
68 free(s->p);
69 }
70 void
min_heap_elem_init(struct event * e)71 min_heap_elem_init(struct event * e)
72 {
73 e->min_heap_idx = SIZE_MAX;
74 }
75 int
min_heap_empty(min_heap_t * s)76 min_heap_empty(min_heap_t * s)
77 {
78 return 0 == s->n;
79 }
80 size_t
min_heap_size(min_heap_t * s)81 min_heap_size(min_heap_t * s)
82 {
83 return s->n;
84 }
85 struct event *
min_heap_top(min_heap_t * s)86 min_heap_top(min_heap_t * s)
87 {
88 return s->n ? *s->p : 0;
89 }
90
91 int
min_heap_push(min_heap_t * s,struct event * e)92 min_heap_push(min_heap_t * s, struct event * e)
93 {
94 if (min_heap_reserve(s, s->n + 1))
95 return -1;
96 min_heap_shift_up_(s, s->n++, e);
97 return 0;
98 }
99
100 struct event *
min_heap_pop(min_heap_t * s)101 min_heap_pop(min_heap_t * s)
102 {
103 if (s->n) {
104 struct event *e = *s->p;
105 min_heap_shift_down_(s, 0, s->p[--s->n]);
106 e->min_heap_idx = SIZE_MAX;
107 return e;
108 }
109 return 0;
110 }
111
112 int
min_heap_erase(min_heap_t * s,struct event * e)113 min_heap_erase(min_heap_t * s, struct event * e)
114 {
115 if (e->min_heap_idx != SIZE_MAX) {
116 struct event *last = s->p[--s->n];
117 size_t parent = (e->min_heap_idx - 1) / 2;
118 /*
119 * we replace e with the last element in the heap. We might
120 * need to shift it upward if it is less than its parent, or
121 * downward if it is greater than one or both its children.
122 * Since the children are known to be less than the parent,
123 * it can't need to shift both up and down.
124 */
125 if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
126 min_heap_shift_up_(s, e->min_heap_idx, last);
127 else
128 min_heap_shift_down_(s, e->min_heap_idx, last);
129 e->min_heap_idx = SIZE_MAX;
130 return 0;
131 }
132 return -1;
133 }
134
135 int
min_heap_reserve(min_heap_t * s,size_t n)136 min_heap_reserve(min_heap_t * s, size_t n)
137 {
138 if (s->a < n) {
139 struct event **p;
140 size_t a = s->a ? s->a * 2 : 8;
141 if (a < n)
142 a = n;
143 if (!(p = recallocarray(s->p, s->a, a, sizeof *p)))
144 return -1;
145 s->p = p;
146 s->a = a;
147 }
148 return 0;
149 }
150
151 void
min_heap_shift_up_(min_heap_t * s,size_t hole_index,struct event * e)152 min_heap_shift_up_(min_heap_t * s, size_t hole_index, struct event * e)
153 {
154 size_t parent = (hole_index - 1) / 2;
155 while (hole_index && min_heap_elem_greater(s->p[parent], e)) {
156 s->p[hole_index] = s->p[parent];
157 s->p[hole_index]->min_heap_idx = hole_index;
158 hole_index = parent;
159 parent = (hole_index - 1) / 2;
160 }
161 e->min_heap_idx = hole_index;
162 s->p[hole_index] = e;
163 }
164
165 void
min_heap_shift_down_(min_heap_t * s,size_t hole_index,struct event * e)166 min_heap_shift_down_(min_heap_t * s, size_t hole_index, struct event * e)
167 {
168 size_t min_child = 2 * (hole_index + 1);
169 while (min_child <= s->n) {
170 if (min_child == s->n ||
171 min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))
172 min_child -= 1;
173 if (!(min_heap_elem_greater(e, s->p[min_child])))
174 break;
175 s->p[hole_index] = s->p[min_child];
176 s->p[hole_index]->min_heap_idx = hole_index;
177 hole_index = min_child;
178 min_child = 2 * (hole_index + 1);
179 }
180 min_heap_shift_up_(s, hole_index, e);
181 }
182 #endif /* _MIN_HEAP_H_ */
183