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