knf, ok bluhm

1 files changed, 125 insertions, 98 deletions

diff --git a/lib/libevent/min_heap.h b/lib/libevent/min_heap.h
index 181473e09cb..34a74e51131 100644
--- a/lib/libevent/min_heap.h
+++ b/lib/libevent/min_heap.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: min_heap.h,v 1.4 2019/04/18 23:44:21 tedu Exp $	*/
+/*	$OpenBSD: min_heap.h,v 1.5 2019/04/20 23:22:28 tedu Exp $	*/
 
 /*
  * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com>
@@ -31,125 +31,152 @@
 
 #include "event.h"
 
-typedef struct min_heap
-{
-    struct event** p;
-    unsigned n, a;
+typedef struct min_heap {
+	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_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 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 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_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 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);
 
-int min_heap_elem_greater(struct event *a, struct event *b)
+int 
+min_heap_elem_greater(struct event * a, struct event * b)
 {
-    return timercmp(&a->ev_timeout, &b->ev_timeout, >);
+	return 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) free(s->p); }
-void min_heap_elem_init(struct event* e) { e->min_heap_idx = -1; }
-int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
-unsigned min_heap_size(min_heap_t* s) { return s->n; }
-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)
+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)
+		free(s->p);
+}
+void 
+min_heap_elem_init(struct event * e)
+{
+	e->min_heap_idx = -1;
+}
+int 
+min_heap_empty(min_heap_t * s)
+{
+	return 0u == s->n;
+}
+unsigned 
+min_heap_size(min_heap_t * s)
 {
-    if(min_heap_reserve(s, s->n + 1))
-        return -1;
-    min_heap_shift_up_(s, s->n++, e);
-    return 0;
+	return s->n;
+}
+struct event *
+min_heap_top(min_heap_t * s)
+{
+	return s->n ? *s->p : 0;
 }
 
-struct event* min_heap_pop(min_heap_t* s)
+int 
+min_heap_push(min_heap_t * s, struct event * e)
 {
-    if(s->n)
-    {
-        struct event* e = *s->p;
-        min_heap_shift_down_(s, 0u, s->p[--s->n]);
-        e->min_heap_idx = -1;
-        return e;
-    }
-    return 0;
+	if (min_heap_reserve(s, s->n + 1))
+		return -1;
+	min_heap_shift_up_(s, s->n++, e);
+	return 0;
 }
 
-int min_heap_erase(min_heap_t* s, struct event* e)
+struct event *
+min_heap_pop(min_heap_t * s)
 {
-    if(((unsigned int)-1) != e->min_heap_idx)
-    {
-        struct event *last = s->p[--s->n];
-        unsigned parent = (e->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->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
-             min_heap_shift_up_(s, e->min_heap_idx, last);
-        else
-             min_heap_shift_down_(s, e->min_heap_idx, last);
-        e->min_heap_idx = -1;
-        return 0;
-    }
-    return -1;
+	if (s->n) {
+		struct event *e = *s->p;
+		min_heap_shift_down_(s, 0u, s->p[--s->n]);
+		e->min_heap_idx = -1;
+		return e;
+	}
+	return 0;
 }
 
-int min_heap_reserve(min_heap_t* s, unsigned n)
+int 
+min_heap_erase(min_heap_t * s, struct event * e)
 {
-    if(s->a < n)
-    {
-        struct event** p;
-        unsigned a = s->a ? s->a * 2 : 8;
-        if(a < n)
-            a = n;
-        if(!(p = realloc(s->p, a * sizeof *p)))
-            return -1;
-        s->p = p;
-        s->a = a;
-    }
-    return 0;
+	if (((unsigned int)-1) != e->min_heap_idx) {
+		struct event *last = s->p[--s->n];
+		unsigned parent = (e->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->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
+			min_heap_shift_up_(s, e->min_heap_idx, last);
+		else
+			min_heap_shift_down_(s, e->min_heap_idx, last);
+		e->min_heap_idx = -1;
+		return 0;
+	}
+	return -1;
 }
 
-void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
+int 
+min_heap_reserve(min_heap_t * s, unsigned n)
 {
-    unsigned parent = (hole_index - 1) / 2;
-    while(hole_index && min_heap_elem_greater(s->p[parent], e))
-    {
-        s->p[hole_index] = s->p[parent];
-        s->p[hole_index]->min_heap_idx = hole_index;
-        hole_index = parent;
-        parent = (hole_index - 1) / 2;
-    }
-    e->min_heap_idx = hole_index;
-    s->p[hole_index] = e;
+	if (s->a < n) {
+		struct event **p;
+		unsigned a = s->a ? s->a * 2 : 8;
+		if (a < n)
+			a = n;
+		if (!(p = realloc(s->p, a * sizeof *p)))
+			return -1;
+		s->p = p;
+		s->a = a;
+	}
+	return 0;
 }
 
-void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
+void 
+min_heap_shift_up_(min_heap_t * s, unsigned hole_index, struct event * e)
 {
-    unsigned min_child = 2 * (hole_index + 1);
-    while(min_child <= s->n)
-	{
-	if (min_child == s->n ||
-	    min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))
-        	min_child -= 1;
-        if(!(min_heap_elem_greater(e, s->p[min_child])))
-            break;
-        s->p[hole_index] = s->p[min_child];
-        s->p[hole_index]->min_heap_idx = hole_index;
-        hole_index = min_child;
-        min_child = 2 * (hole_index + 1);
+	unsigned parent = (hole_index - 1) / 2;
+	while (hole_index && min_heap_elem_greater(s->p[parent], e)) {
+		s->p[hole_index] = s->p[parent];
+		s->p[hole_index]->min_heap_idx = hole_index;
+		hole_index = parent;
+		parent = (hole_index - 1) / 2;
 	}
-    min_heap_shift_up_(s, hole_index,  e);
+	e->min_heap_idx = hole_index;
+	s->p[hole_index] = e;
 }
 
-#endif /* _MIN_HEAP_H_ */
+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) {
+		if (min_child == s->n ||
+		    min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))
+			min_child -= 1;
+		if (!(min_heap_elem_greater(e, s->p[min_child])))
+			break;
+		s->p[hole_index] = s->p[min_child];
+		s->p[hole_index]->min_heap_idx = hole_index;
+		hole_index = min_child;
+		min_child = 2 * (hole_index + 1);
+	}
+	min_heap_shift_up_(s, hole_index, e);
+}
+#endif				/* _MIN_HEAP_H_ */