commit cc44e26db4154e11a027442878e1e34bc521e58e
from: Omar Polo <op@omarpolo.com>
date: Mon Feb 19 15:39:31 2024 UTC

ev: simplify heap management

make ev_timer always use the ``reserve'' space and heapify at the
start of the event loop tick.  Bonus points for using the better
algorithm and remove the unused bubbleup.

commit - c7ef47709b71c178743625c10feca9f7cf373b80
commit + cc44e26db4154e11a027442878e1e34bc521e58e
blob - 0a0da1ce783c7d63c80448fd571d7dff5200b3a0
blob + cfe557178e73374aed6b61e63f62cb4cfa113824
--- ev.c
+++ ev.c
@@ -221,50 +221,20 @@ ev_signal(int sig, void (*cb)(int, int, void *), void 
 	return 0;
 }
 
-static inline void
-bubbleup(size_t i)
-{
-	struct evtimer	 tmp;
-	size_t		 p;
-
-	for (;;) {
-		if (i == 0)
-			return;
-
-		p = (i - 1) / 2;
-		if (timercmp(&base->timers[p].tv, &base->timers[i].tv, <))
-		    	return;
-
-		/* swap */
-		memcpy(&tmp, &base->timers[p], sizeof(tmp));
-		memcpy(&base->timers[p], &base->timers[i], sizeof(tmp));
-		memcpy(&base->timers[i], &tmp, sizeof(tmp));
-		i = p;
-	}
-}
-
 unsigned int
 ev_timer(const struct timeval *tv, void (*cb)(int, int, void*), void *udata)
 {
 	struct evtimer	*evt;
 	void		*t;
-	size_t		 tot, newcap, n;
+	size_t		 newcap;
 	unsigned int	 nextid;
-	int		 use_reserve;
 
 	if (tv == NULL) {
 		errno = EINVAL;
 		return 0;
-	}
-
-	use_reserve = 0;
-	tot = base->ntimers;
-	if (base->reserve_from != 0) {
-		use_reserve = 1;
-		tot = base->reserve_till;
 	}
 
-	if (tot == base->timerscap) {
+	if (base->reserve_till == base->timerscap) {
 		newcap = base->timerscap + 8;
 		t = recallocarray(base->timers, base->timerscap, newcap,
 		    sizeof(*base->timers));
@@ -277,23 +247,13 @@ ev_timer(const struct timeval *tv, void (*cb)(int, int
 	if ((nextid = ++base->tid) == 0)
 		nextid = ++base->tid;
 
-	n = base->ntimers;
-	if (use_reserve)
-		n = base->reserve_till;
-
-	evt = &base->timers[n];
+	evt = &base->timers[base->reserve_till];
 	evt->id = nextid;
 	memcpy(&evt->tv, tv, sizeof(*tv));
 	evt->cb.cb = cb;
 	evt->cb.udata = udata;
 
-	if (use_reserve)
-		base->reserve_till++;
-	else {
-		bubbleup(base->ntimers);
-		base->ntimers++;
-	}
-
+	base->reserve_till++;
 	return (nextid);
 }
 
@@ -415,6 +375,38 @@ ev_del(int fd)
 	return 0;
 }
 
+static void
+timerheapify(void)
+{
+	size_t		 i, reserve, gap;
+
+	reserve = base->reserve_till - base->reserve_from;
+	if (reserve == 0)
+		return;
+
+	gap = base->reserve_from - base->ntimers;
+	if (gap != 0) {
+		memmove(&base->timers[base->ntimers],
+		    &base->timers[base->reserve_from],
+		    reserve * sizeof(*base->timers));
+		base->reserve_from -= gap;
+		base->reserve_till -= gap;
+	}
+
+	base->ntimers = base->reserve_till;
+
+	if (base->ntimers < 2)
+		return;
+
+	i = base->ntimers / 2 - 1;
+	for (;;) {
+		bubbledown(i);
+		if (i == 0)
+			break;
+		i--;
+	}
+}
+
 static inline int
 poll2ev(int ev)
 {
@@ -434,9 +426,13 @@ ev_loop(void)
 	struct timespec	 elapsed, beg, end, min, *wait;
 	struct timeval	 tv, sub;
 	int		 n;
-	size_t		 i, gap;
+	size_t		 i;
 
 	while (!ev_stop) {
+		timerheapify();
+		base->reserve_from = base->ntimers;
+		base->reserve_till = base->ntimers;
+
 		wait = NULL;
 		if (base->ntimers) {
 			TIMEVAL_TO_TIMESPEC(&base->timers[0].tv, &min);
@@ -458,9 +454,6 @@ ev_loop(void)
 
 		TIMESPEC_TO_TIMEVAL(&tv, &elapsed);
 
-		base->reserve_from = base->ntimers;
-		base->reserve_till = base->ntimers;
-
 		for (i = 0; i < base->ntimers && !ev_stop; /* nop */) {
 			timersub(&base->timers[i].tv, &tv, &sub);
 			if (sub.tv_sec <= 0) {
@@ -484,24 +477,6 @@ ev_loop(void)
 				    base->cbs[i].udata);
 			}
 		}
-
-		if (base->reserve_from == base->reserve_till)
-			continue;
-
-		/* integrate the new timers in the heap */
-		gap = base->reserve_from - base->ntimers;
-		if (gap != 0) {
-			memmove(&base->timers[base->ntimers],
-			    &base->timers[base->reserve_from],
-			    gap * sizeof(*base->timers));
-			base->reserve_from -= gap;
-			base->reserve_till -= gap;
-		}
-
-		for (i = base->ntimers; i < base->reserve_till; ++i) {
-			base->ntimers++;
-			bubbleup(i);
-		}
 	}
 
 	return 0;