summaryrefslogtreecommitdiff
path: root/minheap-internal.h
diff options
context:
space:
mode:
authorNick Mathewson <nickm@torproject.org>2010-02-18 17:41:15 -0500
committerNick Mathewson <nickm@torproject.org>2010-02-18 17:44:09 -0500
commite5bbd40ad7f66f80170454683342076ec1e92d31 (patch)
tree84a839ef40c6054d982a3799f0408053aa52238a /minheap-internal.h
parent8fdf09c09d2f92d7bc1a333b24a6490f65d5369c (diff)
downloadlibevent-e5bbd40ad7f66f80170454683342076ec1e92d31.tar.gz
Clean up formatting: use tabs, not 8-spaces, to indent.
Diffstat (limited to 'minheap-internal.h')
-rw-r--r--minheap-internal.h130
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);
}