diff options
author | Nick Mathewson <nickm@torproject.org> | 2010-02-18 17:41:15 -0500 |
---|---|---|
committer | Nick Mathewson <nickm@torproject.org> | 2010-02-18 17:44:09 -0500 |
commit | e5bbd40ad7f66f80170454683342076ec1e92d31 (patch) | |
tree | 84a839ef40c6054d982a3799f0408053aa52238a /minheap-internal.h | |
parent | 8fdf09c09d2f92d7bc1a333b24a6490f65d5369c (diff) | |
download | libevent-e5bbd40ad7f66f80170454683342076ec1e92d31.tar.gz |
Clean up formatting: use tabs, not 8-spaces, to indent.
Diffstat (limited to 'minheap-internal.h')
-rw-r--r-- | minheap-internal.h | 130 |
1 files changed, 65 insertions, 65 deletions
diff --git a/minheap-internal.h b/minheap-internal.h index ba557166..747f635a 100644 --- a/minheap-internal.h +++ b/minheap-internal.h @@ -36,28 +36,28 @@ typedef struct min_heap { - struct event** p; - unsigned n, a; + struct event** p; + unsigned 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_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 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); -static inline int min_heap_reserve(min_heap_t* s, unsigned n); -static inline int min_heap_push(min_heap_t* s, struct event* e); +static inline int min_heap_reserve(min_heap_t* s, unsigned 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, unsigned hole_index, struct event* e); -static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, 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_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, >); + return 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; } @@ -69,22 +69,22 @@ 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; + 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, 0u, s->p[--s->n]); - e->ev_timeout_pos.min_heap_idx = -1; - return e; - } - return 0; + if (s->n) + { + struct event* e = *s->p; + min_heap_shift_down_(s, 0u, s->p[--s->n]); + e->ev_timeout_pos.min_heap_idx = -1; + return e; + } + return 0; } int min_heap_elt_is_top(const struct event *e) @@ -94,39 +94,39 @@ int min_heap_elt_is_top(const struct event *e) int min_heap_erase(min_heap_t* s, struct event* e) { - if(((unsigned int)-1) != e->ev_timeout_pos.min_heap_idx) - { - struct event *last = s->p[--s->n]; - unsigned parent = (e->ev_timeout_pos.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->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); - else - min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last); - e->ev_timeout_pos.min_heap_idx = -1; - return 0; - } - return -1; + if (((unsigned int)-1) != e->ev_timeout_pos.min_heap_idx) + { + struct event *last = s->p[--s->n]; + unsigned parent = (e->ev_timeout_pos.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->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); + else + min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last); + e->ev_timeout_pos.min_heap_idx = -1; + return 0; + } + return -1; } int min_heap_reserve(min_heap_t* s, unsigned n) { - if(s->a < n) - { - struct event** p; - unsigned a = s->a ? s->a * 2 : 8; - if(a < n) - a = n; - if(!(p = (struct event**)realloc(s->p, a * sizeof *p))) - return -1; - s->p = p; - s->a = a; - } - return 0; + if(s->a < n) + { + struct event** p; + unsigned a = s->a ? s->a * 2 : 8; + if(a < n) + a = n; + if(!(p = (struct event**)realloc(s->p, a * sizeof *p))) + return -1; + s->p = p; + s->a = a; + } + return 0; } void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e) @@ -134,9 +134,9 @@ void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e) unsigned parent = (hole_index - 1) / 2; while(hole_index && min_heap_elem_greater(s->p[parent], e)) { - (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index; - hole_index = parent; - parent = (hole_index - 1) / 2; + (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index; + hole_index = parent; + parent = (hole_index - 1) / 2; } (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index; } @@ -146,12 +146,12 @@ void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e) unsigned min_child = 2 * (hole_index + 1); while(min_child <= s->n) { - min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]); - if(!(min_heap_elem_greater(e, s->p[min_child]))) - break; - (s->p[hole_index] = s->p[min_child])->ev_timeout_pos.min_heap_idx = hole_index; - hole_index = min_child; - min_child = 2 * (hole_index + 1); + min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]); + if(!(min_heap_elem_greater(e, s->p[min_child]))) + break; + (s->p[hole_index] = s->p[min_child])->ev_timeout_pos.min_heap_idx = hole_index; + hole_index = min_child; + min_child = 2 * (hole_index + 1); } min_heap_shift_up_(s, hole_index, e); } |