1 /* $OpenBSD: min_heap.h,v 1.2 2010/07/12 18:03:38 nicm 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 #include "evutil.h"
34
35 typedef struct min_heap
36 {
37 struct event** p;
38 unsigned n, a;
39 } min_heap_t;
40
41 static inline void min_heap_ctor(min_heap_t* s);
42 static inline void min_heap_dtor(min_heap_t* s);
43 static inline void min_heap_elem_init(struct event* e);
44 static inline int min_heap_elem_greater(struct event *a, struct event *b);
45 static inline int min_heap_empty(min_heap_t* s);
46 static inline unsigned min_heap_size(min_heap_t* s);
47 static inline struct event* min_heap_top(min_heap_t* s);
48 static inline int min_heap_reserve(min_heap_t* s, unsigned n);
49 static inline int min_heap_push(min_heap_t* s, struct event* e);
50 static inline struct event* min_heap_pop(min_heap_t* s);
51 static inline int min_heap_erase(min_heap_t* s, struct event* e);
52 static inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e);
53 static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e);
54
min_heap_elem_greater(struct event * a,struct event * b)55 int min_heap_elem_greater(struct event *a, struct event *b)
56 {
57 return evutil_timercmp(&a->ev_timeout, &b->ev_timeout, >);
58 }
59
min_heap_ctor(min_heap_t * s)60 void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
min_heap_dtor(min_heap_t * s)61 void min_heap_dtor(min_heap_t* s) { if(s->p) free(s->p); }
min_heap_elem_init(struct event * e)62 void min_heap_elem_init(struct event* e) { e->min_heap_idx = -1; }
min_heap_empty(min_heap_t * s)63 int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
min_heap_size(min_heap_t * s)64 unsigned min_heap_size(min_heap_t* s) { return s->n; }
min_heap_top(min_heap_t * s)65 struct event* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; }
66
min_heap_push(min_heap_t * s,struct event * e)67 int min_heap_push(min_heap_t* s, struct event* e)
68 {
69 if(min_heap_reserve(s, s->n + 1))
70 return -1;
71 min_heap_shift_up_(s, s->n++, e);
72 return 0;
73 }
74
min_heap_pop(min_heap_t * s)75 struct event* min_heap_pop(min_heap_t* s)
76 {
77 if(s->n)
78 {
79 struct event* e = *s->p;
80 min_heap_shift_down_(s, 0u, s->p[--s->n]);
81 e->min_heap_idx = -1;
82 return e;
83 }
84 return 0;
85 }
86
min_heap_erase(min_heap_t * s,struct event * e)87 int min_heap_erase(min_heap_t* s, struct event* e)
88 {
89 if(((unsigned int)-1) != e->min_heap_idx)
90 {
91 struct event *last = s->p[--s->n];
92 unsigned parent = (e->min_heap_idx - 1) / 2;
93 /* we replace e with the last element in the heap. We might need to
94 shift it upward if it is less than its parent, or downward if it is
95 greater than one or both its children. Since the children are known
96 to be less than the parent, it can't need to shift both up and
97 down. */
98 if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
99 min_heap_shift_up_(s, e->min_heap_idx, last);
100 else
101 min_heap_shift_down_(s, e->min_heap_idx, last);
102 e->min_heap_idx = -1;
103 return 0;
104 }
105 return -1;
106 }
107
min_heap_reserve(min_heap_t * s,unsigned n)108 int min_heap_reserve(min_heap_t* s, unsigned n)
109 {
110 if(s->a < n)
111 {
112 struct event** p;
113 unsigned a = s->a ? s->a * 2 : 8;
114 if(a < n)
115 a = n;
116 if(!(p = (struct event**)realloc(s->p, a * sizeof *p)))
117 return -1;
118 s->p = p;
119 s->a = a;
120 }
121 return 0;
122 }
123
min_heap_shift_up_(min_heap_t * s,unsigned hole_index,struct event * e)124 void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
125 {
126 unsigned parent = (hole_index - 1) / 2;
127 while(hole_index && min_heap_elem_greater(s->p[parent], e))
128 {
129 (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
130 hole_index = parent;
131 parent = (hole_index - 1) / 2;
132 }
133 (s->p[hole_index] = e)->min_heap_idx = hole_index;
134 }
135
min_heap_shift_down_(min_heap_t * s,unsigned hole_index,struct event * e)136 void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
137 {
138 unsigned min_child = 2 * (hole_index + 1);
139 while(min_child <= s->n)
140 {
141 min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
142 if(!(min_heap_elem_greater(e, s->p[min_child])))
143 break;
144 (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
145 hole_index = min_child;
146 min_child = 2 * (hole_index + 1);
147 }
148 min_heap_shift_up_(s, hole_index, e);
149 }
150
151 #endif /* _MIN_HEAP_H_ */
152