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