31 #include "event2/event-config.h"
35 #include "util-internal.h"
36 #include "mm-internal.h"
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);
52 static inline int min_heap_reserve(
min_heap_t* s,
unsigned n);
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);
59 int min_heap_elem_greater(
struct event *a,
struct event *b)
64 void min_heap_ctor(
min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
65 void min_heap_dtor(
min_heap_t* s) {
if (s->p) mm_free(s->p); }
66 void min_heap_elem_init(
struct event* e) { e->ev_timeout_pos.min_heap_idx = -1; }
67 int min_heap_empty(
min_heap_t* s) {
return 0u == s->n; }
68 unsigned min_heap_size(
min_heap_t* s) {
return s->n; }
73 if (min_heap_reserve(s, s->n + 1))
75 min_heap_shift_up_(s, s->n++, e);
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;
91 int min_heap_elt_is_top(
const struct event *e)
93 return e->ev_timeout_pos.min_heap_idx == 0;
98 if (-1 != e->ev_timeout_pos.min_heap_idx)
100 struct event *last = s->p[--s->n];
101 unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;
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);
110 min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last);
111 e->ev_timeout_pos.min_heap_idx = -1;
117 int min_heap_reserve(
min_heap_t* s,
unsigned n)
122 unsigned a = s->a ? s->a * 2 : 8;
125 if (!(p = (
struct event**)mm_realloc(s->p, a *
sizeof *p)))
133 void min_heap_shift_up_(
min_heap_t* s,
unsigned hole_index,
struct event* e)
135 unsigned parent = (hole_index - 1) / 2;
136 while (hole_index && min_heap_elem_greater(s->p[parent], e))
138 (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index;
140 parent = (hole_index - 1) / 2;
142 (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
145 void min_heap_shift_down_(
min_heap_t* s,
unsigned hole_index,
struct event* e)
147 unsigned min_child = 2 * (hole_index + 1);
148 while (min_child <= s->n)
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])))
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);
157 (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
Structure to represent a single event.
Definition: event_struct.h:87
Core functions for waiting for and receiving events, and using event bases.
Structures used by event.h.
Common convenience functions for cross-platform portability and related socket manipulations.
#define evutil_timercmp(tvp, uvp, cmp)
Return true iff the tvp is related to uvp according to the relational operator cmp.
Definition: util.h:415
Definition: minheap-internal.h:38