35 #define min_heap_idx interval
37 typedef timeout_t min_heap_idx_t;
39 typedef struct min_heap
46 static inline void min_heap_ctor(
min_heap_t* s);
47 static inline void min_heap_dtor(
min_heap_t* s);
48 static inline void min_heap_elem_init(
struct timeout* e);
49 static inline int min_heap_elem_greater(
struct timeout *a,
struct timeout *b);
50 static inline int min_heap_empty(
min_heap_t* s);
51 static inline unsigned min_heap_size(
min_heap_t* s);
53 static inline int min_heap_reserve(
min_heap_t* s,
unsigned n);
57 static inline void min_heap_shift_up_(
min_heap_t* s,
unsigned hole_index,
struct timeout* e);
58 static inline void min_heap_shift_down_(
min_heap_t* s,
unsigned hole_index,
struct timeout* e);
62 return a->expires > b->expires;
65 void min_heap_ctor(
min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
66 void min_heap_dtor(
min_heap_t* s) {
if(s->p) free(s->p); }
67 void min_heap_elem_init(
struct timeout* e) { e->min_heap_idx = -1; }
68 int min_heap_empty(
min_heap_t* s) {
return 0u == s->n; }
69 unsigned min_heap_size(
min_heap_t* s) {
return s->n; }
74 if(min_heap_reserve(s, s->n + 1))
76 min_heap_shift_up_(s, s->n++, e);
85 min_heap_shift_down_(s, 0u, s->p[--s->n]);
94 if(((min_heap_idx_t)-1) != e->min_heap_idx)
96 struct timeout *last = s->p[--s->n];
97 unsigned parent = (e->min_heap_idx - 1) / 2;
103 if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
104 min_heap_shift_up_(s, e->min_heap_idx, last);
106 min_heap_shift_down_(s, e->min_heap_idx, last);
107 e->min_heap_idx = -1;
113 int min_heap_reserve(
min_heap_t* s,
unsigned n)
118 unsigned a = s->a ? s->a * 2 : 8;
121 if(!(p = (
struct timeout**)realloc(s->p, a *
sizeof *p)))
131 unsigned parent = (hole_index - 1) / 2;
132 while(hole_index && min_heap_elem_greater(s->p[parent], e))
134 (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
136 parent = (hole_index - 1) / 2;
138 (s->p[hole_index] = e)->min_heap_idx = hole_index;
143 unsigned min_child = 2 * (hole_index + 1);
144 while(min_child <= s->n)
146 min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
147 if(!(min_heap_elem_greater(e, s->p[min_child])))
149 (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
150 hole_index = min_child;
151 min_child = 2 * (hole_index + 1);
153 min_heap_shift_up_(s, hole_index, e);
159 static void *init(
struct timeout *
timeout,
size_t count,
int verbose) {
163 H = calloc(1,
sizeof *H);
166 if (0 != min_heap_reserve(H, count))
169 for (i = 0; i < count; i++) {
170 min_heap_elem_init(&
timeout[i]);
177 static void add(
void *ctx,
struct timeout *to, timeout_t expires) {
179 min_heap_erase(H, to);
180 to->expires = H->curtime + expires;
181 if (0 != min_heap_push(H, to))
186 static void del(
void *ctx,
struct timeout *to) {
187 min_heap_erase(ctx, to);
191 static struct timeout *get(
void *ctx) {
195 if ((to = min_heap_top(H)) && to->expires <= H->curtime)
196 return min_heap_pop(H);
202 static void update(
void *ctx, timeout_t ts) {
208 static void check(
void *ctx) {
213 static int empty(
void *ctx) {
216 return (NULL == min_heap_top(H));
220 static void destroy(
void *H) {