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