lib: Add generic hierarchical timing wheel

Introduce a generic 3-level / 256-slot deadline-ordered callback queue
(1 ms / 16 ms / 256 ms per-slot resolution at levels 0/1/2). Will
replace the existing timerwheel.c.

Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks>
Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>

2 files changed, 83 insertions, 0 deletions

diff --git a/include/ouroboros/time.h b/include/ouroboros/time.h
index 3d037a3c..a4136e8e 100644
--- a/include/ouroboros/time.h
+++ b/include/ouroboros/time.h
@@ -46,6 +46,12 @@
 #define TS_TO_UINT64(ts)                                                \
         ((uint64_t)(ts).tv_sec * BILLION + (uint64_t)(ts).tv_nsec)
 
+#define UINT64_TO_TS(ns, ts)                                            \
+        do {                                                            \
+                (ts)->tv_sec  = (time_t)((ns) / BILLION);               \
+                (ts)->tv_nsec = (long)((ns) % BILLION);                 \
+        } while (0)
+
 #define TIMEVAL_INIT_S(s)   {(s), 0}
 #define TIMEVAL_INIT_MS(ms) {(ms) / 1000, ((ms) % 1000) * 1000}
 #define TIMEVAL_INIT_US(us) {(us) / MILLION, ((us) % MILLION)}
diff --git a/include/ouroboros/tw.h b/include/ouroboros/tw.h
new file mode 100644
index 00000000..156f99db
--- /dev/null
+++ b/include/ouroboros/tw.h
@@ -0,0 +1,77 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2026
+ *
+ * Generic deadline-ordered callback queue (timing wheel)
+ *
+ *    Dimitri Staessens <dimitri@ouroboros.rocks>
+ *    Sander Vrijders   <sander@ouroboros.rocks>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * version 2.1 as published by the Free Software Foundation.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., http://www.fsf.org/about/contact/.
+ */
+
+#ifndef OUROBOROS_TW_H
+#define OUROBOROS_TW_H
+
+#include <ouroboros/cdefs.h>
+#include <ouroboros/list.h>
+
+#include <stddef.h>
+#include <stdint.h>
+#include <time.h>
+
+typedef void (*tw_fire_fn_t)(void * arg);
+
+struct tw_entry {
+        struct list_head next;
+        uint64_t         deadline_ns;
+        tw_fire_fn_t     fire;
+        void *           arg;
+        size_t           lvl;
+};
+
+__BEGIN_DECLS
+
+int  tw_init(void);
+
+void tw_fini(void);
+
+void tw_init_entry(struct tw_entry * e);
+
+/*
+ * Schedule e to fire at deadline_ns. If e is already posted,
+ * the previous schedule is cancelled and replaced.
+ */
+void tw_post(struct tw_entry * e,
+             uint64_t          deadline_ns,
+             tw_fire_fn_t      fire,
+             void *            arg);
+
+void tw_cancel(struct tw_entry * e);
+
+/*
+ * Advance the wheel and fire due callbacks. Callbacks run with the wheel
+ * unlocked and may call tw_post / tw_cancel on any entry, including the one
+ * currently firing. Concurrent tw_move from a second thread is a no-op.
+ */
+void tw_move(void);
+
+/*
+ * Write the absolute deadline of the earliest pending entry to *out.
+ * Empty wheel is signalled by out->tv_nsec == -1.
+ */
+void tw_next_expiry(struct timespec * out);
+
+__END_DECLS
+
+#endif /* OUROBOROS_TW_H */