diff options
Diffstat (limited to 'minheap-internal.h')
| -rw-r--r-- | minheap-internal.h | 24 |
1 files changed, 17 insertions, 7 deletions
diff --git a/minheap-internal.h b/minheap-internal.h index 39e3946a..53b88886 100644 --- a/minheap-internal.h +++ b/minheap-internal.h @@ -46,7 +46,6 @@ 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_elt_is_top(const 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 unsigned min_heap_size(min_heap_t* s); static inline struct event* min_heap_top(min_heap_t* s); @@ -56,12 +55,11 @@ static inline struct event* min_heap_pop(min_heap_t* s); static inline int min_heap_adjust(min_heap_t *s, struct event* e); static inline int min_heap_erase(min_heap_t* s, struct event* e); static inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e); +static inline void min_heap_shift_up_unconditional_(min_heap_t* s, unsigned hole_index, struct event* e); static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e); -int min_heap_elem_greater(struct event *a, struct event *b) -{ - return evutil_timercmp(&a->ev_timeout, &b->ev_timeout, >); -} +#define min_heap_elem_greater(a, b) \ + (evutil_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) mm_free(s->p); } @@ -107,7 +105,7 @@ int min_heap_erase(min_heap_t* s, struct event* e) to be less than the parent, it can't need to shift both up and down. */ if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last)) - min_heap_shift_up_(s, e->ev_timeout_pos.min_heap_idx, last); + min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, last); else min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last); e->ev_timeout_pos.min_heap_idx = -1; @@ -125,7 +123,7 @@ int min_heap_adjust(min_heap_t *s, struct event *e) /* The position of e has changed; we shift it up or down * as needed. We can't need to do both. */ if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], e)) - min_heap_shift_up_(s, e->ev_timeout_pos.min_heap_idx, e); + min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, e); else min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, e); return 0; @@ -149,6 +147,18 @@ int min_heap_reserve(min_heap_t* s, unsigned n) return 0; } +void min_heap_shift_up_unconditional_(min_heap_t* s, unsigned hole_index, struct event* e) +{ + unsigned parent = (hole_index - 1) / 2; + do + { + (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index; + hole_index = parent; + parent = (hole_index - 1) / 2; + } while (hole_index && min_heap_elem_greater(s->p[parent], e)); + (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index; +} + void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e) { unsigned parent = (hole_index - 1) / 2; |