Add deps timeout

5 files changed, 1250 insertions, 0 deletions

diff --git a/deps/CMakeLists.txt b/deps/CMakeLists.txt
new file mode 100644
index 0000000..0a29ecf
--- /dev/null
+++ b/deps/CMakeLists.txt
@@ -0,0 +1 @@
+add_subdirectory(timeout)
\ No newline at end of file
diff --git a/deps/timeout/CMakeLists.txt b/deps/timeout/CMakeLists.txt
new file mode 100644
index 0000000..e000160
--- /dev/null
+++ b/deps/timeout/CMakeLists.txt
@@ -0,0 +1,3 @@
+set(CMAKE_C_FLAGS "-std=c99")
+add_definitions(-fPIC)
+add_library(timeout STATIC timeout.c timeout-bitops.c)
\ No newline at end of file
diff --git a/deps/timeout/timeout-bitops.c b/deps/timeout/timeout-bitops.c
new file mode 100644
index 0000000..d8325db
--- /dev/null
+++ b/deps/timeout/timeout-bitops.c
@@ -0,0 +1,249 @@
+#include <stdint.h>
+#ifdef _MSC_VER
+#include <intrin.h>     /* _BitScanForward, _BitScanReverse */
+#endif
+
+/* First define ctz and clz functions; these are compiler-dependent if
+ * you want them to be fast. */
+#if defined(__GNUC__) && !defined(TIMEOUT_DISABLE_GNUC_BITOPS)
+
+/* On GCC and clang and some others, we can use __builtin functions. They
+ * are not defined for n==0, but timeout.s never calls them with n==0. */
+
+#define ctz64(n) __builtin_ctzll(n)
+#define clz64(n) __builtin_clzll(n)
+#if LONG_BITS == 32
+#define ctz32(n) __builtin_ctzl(n)
+#define clz32(n) __builtin_clzl(n)
+#else
+#define ctz32(n) __builtin_ctz(n)
+#define clz32(n) __builtin_clz(n)
+#endif
+
+#elif defined(_MSC_VER) && !defined(TIMEOUT_DISABLE_MSVC_BITOPS)
+
+/* On MSVC, we have these handy functions. We can ignore their return
+ * values, since we will never supply val == 0. */
+
+static __inline int ctz32(unsigned long val)
+{
+	DWORD zeros = 0;
+	_BitScanForward(&zeros, val);
+	return zeros;
+}
+static __inline int clz32(unsigned long val)
+{
+	DWORD zeros = 0;
+	_BitScanReverse(&zeros, val);
+	return zeros;
+}
+#ifdef _WIN64
+/* According to the documentation, these only exist on Win64. */
+static __inline int ctz64(uint64_t val)
+{
+	DWORD zeros = 0;
+	_BitScanForward64(&zeros, val);
+	return zeros;
+}
+static __inline int clz64(uint64_t val)
+{
+	DWORD zeros = 0;
+	_BitScanReverse64(&zeros, val);
+	return zeros;
+}
+#else
+static __inline int ctz64(uint64_t val)
+{
+	uint32_t lo = (uint32_t) val;
+	uint32_t hi = (uint32_t) (val >> 32);
+	return lo ? ctz32(lo) : 32 + ctz32(hi);
+}
+static __inline int clz64(uint64_t val)
+{
+	uint32_t lo = (uint32_t) val;
+	uint32_t hi = (uint32_t) (val >> 32);
+	return hi ? clz32(hi) : 32 + clz32(lo);
+}
+#endif
+
+/* End of MSVC case. */
+
+#else
+
+/* TODO: There are more clever ways to do this in the generic case. */
+
+
+#define process_(one, cz_bits, bits)					\
+	if (x < ( one << (cz_bits - bits))) { rv += bits; x <<= bits; }
+
+#define process64(bits) process_((UINT64_C(1)), 64, (bits))
+static inline int clz64(uint64_t x)
+{
+	int rv = 0;
+
+	process64(32);
+	process64(16);
+	process64(8);
+	process64(4);
+	process64(2);
+	process64(1);
+	return rv;
+}
+#define process32(bits) process_((UINT32_C(1)), 32, (bits))
+static inline int clz32(uint32_t x)
+{
+	int rv = 0;
+
+	process32(16);
+	process32(8);
+	process32(4);
+	process32(2);
+	process32(1);
+	return rv;
+}
+
+#undef process_
+#undef process32
+#undef process64
+#define process_(one, bits)						\
+	if ((x & ((one << (bits))-1)) == 0) { rv += bits; x >>= bits; }
+
+#define process64(bits) process_((UINT64_C(1)), bits)
+static inline int ctz64(uint64_t x)
+{
+	int rv = 0;
+
+	process64(32);
+	process64(16);
+	process64(8);
+	process64(4);
+	process64(2);
+	process64(1);
+	return rv;
+}
+
+#define process32(bits) process_((UINT32_C(1)), bits)
+static inline int ctz32(uint32_t x)
+{
+	int rv = 0;
+
+	process32(16);
+	process32(8);
+	process32(4);
+	process32(2);
+	process32(1);
+	return rv;
+}
+
+#undef process32
+#undef process64
+#undef process_
+
+/* End of generic case */
+
+#endif /* End of defining ctz */
+
+#ifdef TEST_BITOPS
+#include <stdio.h>
+#include <stdlib.h>
+
+static uint64_t testcases[] = {
+	13371337 * 10,
+	100,
+	385789752,
+	82574,
+	(((uint64_t)1)<<63) + (((uint64_t)1)<<31) + 10101
+};
+
+static int
+naive_clz(int bits, uint64_t v)
+{
+	int r = 0;
+	uint64_t bit = ((uint64_t)1) << (bits-1);
+	while (bit && 0 == (v & bit)) {
+		r++;
+		bit >>= 1;
+	}
+	/* printf("clz(%d,%lx) -> %d\n", bits, v, r); */
+	return r;
+}
+
+static int
+naive_ctz(int bits, uint64_t v)
+{
+	int r = 0;
+	uint64_t bit = 1;
+	while (bit && 0 == (v & bit)) {
+		r++;
+		bit <<= 1;
+		if (r == bits)
+			break;
+	}
+	/* printf("ctz(%d,%lx) -> %d\n", bits, v, r); */
+	return r;
+}
+
+static int
+check(uint64_t vv)
+{
+	uint32_t v32 = (uint32_t) vv;
+
+	if (vv == 0)
+		return 1; /* c[tl]z64(0) is undefined. */
+
+	if (ctz64(vv) != naive_ctz(64, vv)) {
+		printf("mismatch with ctz64: %d\n", ctz64(vv));
+				exit(1);
+		return 0;
+	}
+	if (clz64(vv) != naive_clz(64, vv)) {
+		printf("mismatch with clz64: %d\n", clz64(vv));
+				exit(1);
+		return 0;
+	}
+
+	if (v32 == 0)
+		return 1; /* c[lt]z(0) is undefined. */
+
+	if (ctz32(v32) != naive_ctz(32, v32)) {
+		printf("mismatch with ctz32: %d\n", ctz32(v32));
+		exit(1);
+		return 0;
+	}
+	if (clz32(v32) != naive_clz(32, v32)) {
+		printf("mismatch with clz32: %d\n", clz32(v32));
+				exit(1);
+		return 0;
+	}
+	return 1;
+}
+
+int
+main(int c, char **v)
+{
+	unsigned int i;
+	const unsigned int n = sizeof(testcases)/sizeof(testcases[0]);
+	int result = 0;
+
+	for (i = 0; i <= 63; ++i) {
+		uint64_t x = 1 << i;
+		if (!check(x))
+			result = 1;
+		--x;
+		if (!check(x))
+			result = 1;
+	}
+
+	for (i = 0; i < n; ++i) {
+		if (! check(testcases[i]))
+			result = 1;
+	}
+	if (result) {
+		puts("FAIL");
+	} else {
+		puts("OK");
+	}
+	return result;
+}
+#endif
+
diff --git a/deps/timeout/timeout.c b/deps/timeout/timeout.c
new file mode 100644
index 0000000..e78f57d
--- /dev/null
+++ b/deps/timeout/timeout.c
@@ -0,0 +1,744 @@
+/* ==========================================================================
+ * timeout.c - Tickless hierarchical timing wheel.
+ * --------------------------------------------------------------------------
+ * Copyright (c) 2013, 2014  William Ahern
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to permit
+ * persons to whom the Software is furnished to do so, subject to the
+ * following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
+ * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+ * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
+ * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
+ * USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * ==========================================================================
+ */
+#include <limits.h>    /* CHAR_BIT */
+
+#include <stddef.h>    /* NULL */
+#include <stdlib.h>    /* malloc(3) free(3) */
+#include <stdio.h>     /* FILE fprintf(3) */
+
+#include <inttypes.h>  /* UINT64_C uint64_t */
+
+#include <string.h>    /* memset(3) */
+
+#include <errno.h>     /* errno */
+
+#include <sys/queue.h> /* TAILQ(3) */
+
+#include "timeout.h"
+
+#if TIMEOUT_DEBUG - 0
+#include "timeout-debug.h"
+#endif
+
+#ifdef TIMEOUT_DISABLE_RELATIVE_ACCESS
+#define TO_SET_TIMEOUTS(to, T) ((void)0)
+#else
+#define TO_SET_TIMEOUTS(to, T) ((to)->timeouts = (T))
+#endif
+
+/*
+ * A N C I L L A R Y  R O U T I N E S
+ *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#define abstime_t timeout_t /* for documentation purposes */
+#define reltime_t timeout_t /* "" */
+
+#if !defined countof
+#define countof(a) (sizeof (a) / sizeof *(a))
+#endif
+
+#if !defined endof
+#define endof(a) (&(a)[countof(a)])
+#endif
+
+#if !defined MIN
+#define MIN(a, b) (((a) < (b))? (a) : (b))
+#endif
+
+#if !defined MAX
+#define MAX(a, b) (((a) > (b))? (a) : (b))
+#endif
+
+#if !defined TAILQ_CONCAT
+#define TAILQ_CONCAT(head1, head2, field) do {                          \
+	if (!TAILQ_EMPTY(head2)) {                                      \
+		*(head1)->tqh_last = (head2)->tqh_first;                \
+		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
+		(head1)->tqh_last = (head2)->tqh_last;                  \
+		TAILQ_INIT((head2));                                    \
+	}                                                               \
+} while (0)
+#endif
+
+#if !defined TAILQ_FOREACH_SAFE
+#define TAILQ_FOREACH_SAFE(var, head, field, tvar)                      \
+	for ((var) = TAILQ_FIRST(head);                                 \
+	    (var) && ((tvar) = TAILQ_NEXT(var, field), 1);              \
+	    (var) = (tvar))
+#endif
+
+
+/*
+ * B I T  M A N I P U L A T I O N  R O U T I N E S
+ *
+ * The macros and routines below implement wheel parameterization. The
+ * inputs are:
+ *
+ *   WHEEL_BIT - The number of value bits mapped in each wheel. The
+ *               lowest-order WHEEL_BIT bits index the lowest-order (highest
+ *               resolution) wheel, the next group of WHEEL_BIT bits the
+ *               higher wheel, etc.
+ *
+ *   WHEEL_NUM - The number of wheels. WHEEL_BIT * WHEEL_NUM = the number of
+ *               value bits used by all the wheels. For the default of 6 and
+ *               4, only the low 24 bits are processed. Any timeout value
+ *               larger than this will cycle through again.
+ *
+ * The implementation uses bit fields to remember which slot in each wheel
+ * is populated, and to generate masks of expiring slots according to the
+ * current update interval (i.e. the "tickless" aspect). The slots to
+ * process in a wheel are (populated-set & interval-mask).
+ *
+ * WHEEL_BIT cannot be larger than 6 bits because 2^6 -> 64 is the largest
+ * number of slots which can be tracked in a uint64_t integer bit field.
+ * WHEEL_BIT cannot be smaller than 3 bits because of our rotr and rotl
+ * routines, which only operate on all the value bits in an integer, and
+ * there's no integer smaller than uint8_t.
+ *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#if !defined WHEEL_BIT
+#define WHEEL_BIT 6
+#endif
+
+#if !defined WHEEL_NUM
+#define WHEEL_NUM 4
+#endif
+
+#define WHEEL_LEN (1U << WHEEL_BIT)
+#define WHEEL_MAX (WHEEL_LEN - 1)
+#define WHEEL_MASK (WHEEL_LEN - 1)
+#define TIMEOUT_MAX ((TIMEOUT_C(1) << (WHEEL_BIT * WHEEL_NUM)) - 1)
+
+#include "timeout-bitops.c"
+
+#if WHEEL_BIT == 6
+#define ctz(n) ctz64(n)
+#define clz(n) clz64(n)
+#define fls(n) ((int)(64 - clz64(n)))
+#else
+#define ctz(n) ctz32(n)
+#define clz(n) clz32(n)
+#define fls(n) ((int)(32 - clz32(n)))
+#endif
+
+#if WHEEL_BIT == 6
+#define WHEEL_C(n) UINT64_C(n)
+#define WHEEL_PRIu PRIu64
+#define WHEEL_PRIx PRIx64
+
+typedef uint64_t wheel_t;
+
+#elif WHEEL_BIT == 5
+
+#define WHEEL_C(n) UINT32_C(n)
+#define WHEEL_PRIu PRIu32
+#define WHEEL_PRIx PRIx32
+
+typedef uint32_t wheel_t;
+
+#elif WHEEL_BIT == 4
+
+#define WHEEL_C(n) UINT16_C(n)
+#define WHEEL_PRIu PRIu16
+#define WHEEL_PRIx PRIx16
+
+typedef uint16_t wheel_t;
+
+#elif WHEEL_BIT == 3
+
+#define WHEEL_C(n) UINT8_C(n)
+#define WHEEL_PRIu PRIu8
+#define WHEEL_PRIx PRIx8
+
+typedef uint8_t wheel_t;
+
+#else
+#error invalid WHEEL_BIT value
+#endif
+
+
+static inline wheel_t rotl(const wheel_t v, int c) {
+	if (!(c &= (sizeof v * CHAR_BIT - 1)))
+		return v;
+
+	return (v << c) | (v >> (sizeof v * CHAR_BIT - c));
+} /* rotl() */
+
+
+static inline wheel_t rotr(const wheel_t v, int c) {
+	if (!(c &= (sizeof v * CHAR_BIT - 1)))
+		return v;
+
+	return (v >> c) | (v << (sizeof v * CHAR_BIT - c));
+} /* rotr() */
+
+
+/*
+ * T I M E R  R O U T I N E S
+ *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+TAILQ_HEAD(timeout_list, timeout);
+
+struct timeouts {
+	struct timeout_list wheel[WHEEL_NUM][WHEEL_LEN], expired;
+
+	wheel_t pending[WHEEL_NUM];
+
+	timeout_t curtime;
+	timeout_t hertz;
+}; /* struct timeouts */
+
+
+static struct timeouts *timeouts_init(struct timeouts *T, timeout_t hz) {
+	unsigned i, j;
+
+	for (i = 0; i < countof(T->wheel); i++) {
+		for (j = 0; j < countof(T->wheel[i]); j++) {
+			TAILQ_INIT(&T->wheel[i][j]);
+		}
+	}
+
+	TAILQ_INIT(&T->expired);
+
+	for (i = 0; i < countof(T->pending); i++) {
+		T->pending[i] = 0;
+	}
+
+	T->curtime = 0;
+	T->hertz = (hz)? hz : TIMEOUT_mHZ;
+
+	return T;
+} /* timeouts_init() */
+
+
+TIMEOUT_PUBLIC struct timeouts *timeouts_open(timeout_t hz, int *error) {
+	struct timeouts *T;
+
+	if ((T = malloc(sizeof *T)))
+		return timeouts_init(T, hz);
+
+	*error = errno;
+
+	return NULL;
+} /* timeouts_open() */
+
+
+static void timeouts_reset(struct timeouts *T) {
+	struct timeout_list reset;
+	struct timeout *to;
+	unsigned i, j;
+
+	TAILQ_INIT(&reset);
+
+	for (i = 0; i < countof(T->wheel); i++) {
+		for (j = 0; j < countof(T->wheel[i]); j++) {
+			TAILQ_CONCAT(&reset, &T->wheel[i][j], tqe);
+		}
+	}
+
+	TAILQ_CONCAT(&reset, &T->expired, tqe);
+
+	TAILQ_FOREACH(to, &reset, tqe) {
+		to->pending = NULL;
+		TO_SET_TIMEOUTS(to, NULL);
+	}
+} /* timeouts_reset() */
+
+
+TIMEOUT_PUBLIC void timeouts_close(struct timeouts *T) {
+	/*
+	 * NOTE: Delete installed timeouts so timeout_pending() and
+	 * timeout_expired() worked as expected.
+	 */
+	timeouts_reset(T);
+
+	free(T);
+} /* timeouts_close() */
+
+
+TIMEOUT_PUBLIC timeout_t timeouts_hz(struct timeouts *T) {
+	return T->hertz;
+} /* timeouts_hz() */
+
+
+TIMEOUT_PUBLIC void timeouts_del(struct timeouts *T, struct timeout *to) {
+	if (to->pending) {
+		TAILQ_REMOVE(to->pending, to, tqe);
+
+		if (to->pending != &T->expired && TAILQ_EMPTY(to->pending)) {
+			ptrdiff_t index = to->pending - &T->wheel[0][0];
+			int wheel = index / WHEEL_LEN;
+			int slot = index % WHEEL_LEN;
+
+			T->pending[wheel] &= ~(WHEEL_C(1) << slot);
+		}
+
+		to->pending = NULL;
+		TO_SET_TIMEOUTS(to, NULL);
+	}
+} /* timeouts_del() */
+
+
+static inline reltime_t timeout_rem(struct timeouts *T, struct timeout *to) {
+	return to->expires - T->curtime;
+} /* timeout_rem() */
+
+
+static inline int timeout_wheel(timeout_t timeout) {
+	/* must be called with timeout != 0, so fls input is nonzero */
+	return (fls(MIN(timeout, TIMEOUT_MAX)) - 1) / WHEEL_BIT;
+} /* timeout_wheel() */
+
+
+static inline int timeout_slot(int wheel, timeout_t expires) {
+	return WHEEL_MASK & ((expires >> (wheel * WHEEL_BIT)) - !!wheel);
+} /* timeout_slot() */
+
+
+static void timeouts_sched(struct timeouts *T, struct timeout *to, timeout_t expires) {
+	timeout_t rem;
+	int wheel, slot;
+
+	timeouts_del(T, to);
+
+	to->expires = expires;
+
+	TO_SET_TIMEOUTS(to, T);
+
+	if (expires > T->curtime) {
+		rem = timeout_rem(T, to);
+
+		/* rem is nonzero since:
+		 *   rem == timeout_rem(T,to),
+		 *       == to->expires - T->curtime
+		 *   and above we have expires > T->curtime.
+		 */
+		wheel = timeout_wheel(rem);
+		slot = timeout_slot(wheel, to->expires);
+
+		to->pending = &T->wheel[wheel][slot];
+		TAILQ_INSERT_TAIL(to->pending, to, tqe);
+
+		T->pending[wheel] |= WHEEL_C(1) << slot;
+	} else {
+		to->pending = &T->expired;
+		TAILQ_INSERT_TAIL(to->pending, to, tqe);
+	}
+} /* timeouts_sched() */
+
+
+#ifndef TIMEOUT_DISABLE_INTERVALS
+static void timeouts_readd(struct timeouts *T, struct timeout *to) {
+	to->expires += to->interval;
+
+	if (to->expires <= T->curtime) {
+		/* If we've missed the next firing of this timeout, reschedule
+		 * it to occur at the next multiple of its interval after
+		 * the last time that it fired.
+		 */
+		timeout_t n = T->curtime - to->expires;
+		timeout_t r = n % to->interval;
+		to->expires = T->curtime + (to->interval - r);
+	}
+
+	timeouts_sched(T, to, to->expires);
+} /* timeouts_readd() */
+#endif
+
+
+TIMEOUT_PUBLIC void timeouts_add(struct timeouts *T, struct timeout *to, timeout_t timeout) {
+#ifndef TIMEOUT_DISABLE_INTERVALS
+	if (to->flags & TIMEOUT_INT)
+		to->interval = MAX(1, timeout);
+#endif
+
+	if (to->flags & TIMEOUT_ABS)
+		timeouts_sched(T, to, timeout);
+	else
+		timeouts_sched(T, to, T->curtime + timeout);
+} /* timeouts_add() */
+
+
+TIMEOUT_PUBLIC void timeouts_update(struct timeouts *T, abstime_t curtime) {
+	timeout_t elapsed = curtime - T->curtime;
+	struct timeout_list todo;
+	int wheel;
+
+	TAILQ_INIT(&todo);
+
+	/*
+	 * There's no avoiding looping over every wheel. It's best to keep
+	 * WHEEL_NUM smallish.
+	 */
+	for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
+		wheel_t pending;
+
+		/*
+		 * Calculate the slots expiring in this wheel
+		 *
+		 * If the elapsed time is greater than the maximum period of
+		 * the wheel, mark every position as expiring.
+		 *
+		 * Otherwise, to determine the expired slots fill in all the
+		 * bits between the last slot processed and the current
+		 * slot, inclusive of the last slot. We'll bitwise-AND this
+		 * with our pending set below.
+		 *
+		 * If a wheel rolls over, force a tick of the next higher
+		 * wheel.
+		 */
+		if ((elapsed >> (wheel * WHEEL_BIT)) > WHEEL_MAX) {
+			pending = (wheel_t)~WHEEL_C(0);
+		} else {
+			wheel_t _elapsed = WHEEL_MASK & (elapsed >> (wheel * WHEEL_BIT));
+			int oslot, nslot;
+
+			/*
+			 * TODO: It's likely that at least one of the
+			 * following three bit fill operations is redundant
+			 * or can be replaced with a simpler operation.
+			 */
+			oslot = WHEEL_MASK & (T->curtime >> (wheel * WHEEL_BIT));
+			pending = rotl(((UINT64_C(1) << _elapsed) - 1), oslot);
+
+			nslot = WHEEL_MASK & (curtime >> (wheel * WHEEL_BIT));
+			pending |= rotr(rotl(((WHEEL_C(1) << _elapsed) - 1), nslot), _elapsed);
+			pending |= WHEEL_C(1) << nslot;
+		}
+
+		while (pending & T->pending[wheel]) {
+			/* ctz input cannot be zero: loop condition. */
+			int slot = ctz(pending & T->pending[wheel]);
+			TAILQ_CONCAT(&todo, &T->wheel[wheel][slot], tqe);
+			T->pending[wheel] &= ~(UINT64_C(1) << slot);
+		}
+
+		if (!(0x1 & pending))
+			break; /* break if we didn't wrap around end of wheel */
+
+		/* if we're continuing, the next wheel must tick at least once */
+		elapsed = MAX(elapsed, (WHEEL_LEN << (wheel * WHEEL_BIT)));
+	}
+
+	T->curtime = curtime;
+
+	while (!TAILQ_EMPTY(&todo)) {
+		struct timeout *to = TAILQ_FIRST(&todo);
+
+		TAILQ_REMOVE(&todo, to, tqe);
+		to->pending = NULL;
+
+		timeouts_sched(T, to, to->expires);
+	}
+
+	return;
+} /* timeouts_update() */
+
+
+TIMEOUT_PUBLIC void timeouts_step(struct timeouts *T, reltime_t elapsed) {
+	timeouts_update(T, T->curtime + elapsed);
+} /* timeouts_step() */
+
+
+TIMEOUT_PUBLIC bool timeouts_pending(struct timeouts *T) {
+	wheel_t pending = 0;
+	int wheel;
+
+	for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
+		pending |= T->pending[wheel];
+	}
+
+	return !!pending;
+} /* timeouts_pending() */
+
+
+TIMEOUT_PUBLIC bool timeouts_expired(struct timeouts *T) {
+	return !TAILQ_EMPTY(&T->expired);
+} /* timeouts_expired() */
+
+
+/*
+ * Calculate the interval before needing to process any timeouts pending on
+ * any wheel.
+ *
+ * (This is separated from the public API routine so we can evaluate our
+ * wheel invariant assertions irrespective of the expired queue.)
+ *
+ * This might return a timeout value sooner than any installed timeout if
+ * only higher-order wheels have timeouts pending. We can only know when to
+ * process a wheel, not precisely when a timeout is scheduled. Our timeout
+ * accuracy could be off by 2^(N*M)-1 units where N is the wheel number and
+ * M is WHEEL_BIT. Only timeouts which have fallen through to wheel 0 can be
+ * known exactly.
+ *
+ * We should never return a timeout larger than the lowest actual timeout.
+ */
+static timeout_t timeouts_int(struct timeouts *T) {
+	timeout_t timeout = ~TIMEOUT_C(0), _timeout;
+	timeout_t relmask;
+	int wheel, slot;
+
+	relmask = 0;
+
+	for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
+		if (T->pending[wheel]) {
+			slot = WHEEL_MASK & (T->curtime >> (wheel * WHEEL_BIT));
+
+			/* ctz input cannot be zero: T->pending[wheel] is
+			 * nonzero, so rotr() is nonzero. */
+			_timeout = (ctz(rotr(T->pending[wheel], slot)) + !!wheel) << (wheel * WHEEL_BIT);
+			/* +1 to higher order wheels as those timeouts are one rotation in the future (otherwise they'd be on a lower wheel or expired) */
+
+			_timeout -= relmask & T->curtime;
+			/* reduce by how much lower wheels have progressed */
+
+			timeout = MIN(_timeout, timeout);
+		}
+
+		relmask <<= WHEEL_BIT; 
+		relmask |= WHEEL_MASK;
+	}
+
+	return timeout;
+} /* timeouts_int() */
+
+
+/*
+ * Calculate the interval our caller can wait before needing to process
+ * events.
+ */
+TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *T) {
+	if (!TAILQ_EMPTY(&T->expired))
+		return 0;
+
+	return timeouts_int(T);
+} /* timeouts_timeout() */
+
+
+TIMEOUT_PUBLIC struct timeout *timeouts_get(struct timeouts *T) {
+	if (!TAILQ_EMPTY(&T->expired)) {
+		struct timeout *to = TAILQ_FIRST(&T->expired);
+
+		TAILQ_REMOVE(&T->expired, to, tqe);
+		to->pending = NULL;
+		TO_SET_TIMEOUTS(to, NULL);
+
+#ifndef TIMEOUT_DISABLE_INTERVALS
+		if ((to->flags & TIMEOUT_INT) && to->interval > 0)
+			timeouts_readd(T, to);
+#endif
+
+		return to;
+	} else {
+		return 0;
+	}
+} /* timeouts_get() */
+
+
+/*
+ * Use dumb looping to locate the earliest timeout pending on the wheel so
+ * our invariant assertions can check the result of our optimized code.
+ */
+static struct timeout *timeouts_min(struct timeouts *T) {
+	struct timeout *to, *min = NULL;
+	unsigned i, j;
+
+	for (i = 0; i < countof(T->wheel); i++) {
+		for (j = 0; j < countof(T->wheel[i]); j++) {
+			TAILQ_FOREACH(to, &T->wheel[i][j], tqe) {
+				if (!min || to->expires < min->expires)
+					min = to;
+			}
+		}
+	}
+
+	return min;
+} /* timeouts_min() */
+
+
+/*
+ * Check some basic algorithm invariants. If these invariants fail then
+ * something is definitely broken.
+ */
+#define report(...) do { \
+	if ((fp)) \
+		fprintf(fp, __VA_ARGS__); \
+} while (0)
+
+#define check(expr, ...) do { \
+	if (!(expr)) { \
+		report(__VA_ARGS__); \
+		return 0; \
+	} \
+} while (0)
+
+TIMEOUT_PUBLIC bool timeouts_check(struct timeouts *T, FILE *fp) {
+	timeout_t timeout;
+	struct timeout *to;
+
+	if ((to = timeouts_min(T))) {
+		check(to->expires > T->curtime, "missed timeout (expires:%" TIMEOUT_PRIu " <= curtime:%" TIMEOUT_PRIu ")\n", to->expires, T->curtime);
+
+		timeout = timeouts_int(T);
+		check(timeout <= to->expires - T->curtime, "wrong soft timeout (soft:%" TIMEOUT_PRIu " > hard:%" TIMEOUT_PRIu ") (expires:%" TIMEOUT_PRIu "; curtime:%" TIMEOUT_PRIu ")\n", timeout, (to->expires - T->curtime), to->expires, T->curtime);
+
+		timeout = timeouts_timeout(T);
+		check(timeout <= to->expires - T->curtime, "wrong soft timeout (soft:%" TIMEOUT_PRIu " > hard:%" TIMEOUT_PRIu ") (expires:%" TIMEOUT_PRIu "; curtime:%" TIMEOUT_PRIu ")\n", timeout, (to->expires - T->curtime), to->expires, T->curtime);
+	} else {
+		timeout = timeouts_timeout(T);
+
+		if (!TAILQ_EMPTY(&T->expired))
+			check(timeout == 0, "wrong soft timeout (soft:%" TIMEOUT_PRIu " != hard:%" TIMEOUT_PRIu ")\n", timeout, TIMEOUT_C(0));
+		else
+			check(timeout == ~TIMEOUT_C(0), "wrong soft timeout (soft:%" TIMEOUT_PRIu " != hard:%" TIMEOUT_PRIu ")\n", timeout, ~TIMEOUT_C(0));
+	}
+
+	return 1;
+} /* timeouts_check() */
+
+
+#define ENTER                                                           \
+	do {                                                            \
+	static const int pc0 = __LINE__;                                \
+	switch (pc0 + it->pc) {                                         \
+	case __LINE__: (void)0
+
+#define SAVE_AND_DO(do_statement)                                       \
+	do {                                                            \
+		it->pc = __LINE__ - pc0;                                \
+		do_statement;                                           \
+		case __LINE__: (void)0;                                 \
+	} while (0)
+
+#define YIELD(rv)                                                       \
+	SAVE_AND_DO(return (rv))
+
+#define LEAVE                                                           \
+	SAVE_AND_DO(break);                                             \
+	}                                                               \
+	} while (0)
+
+TIMEOUT_PUBLIC struct timeout *timeouts_next(struct timeouts *T, struct timeouts_it *it) {
+	struct timeout *to;
+
+	ENTER;
+
+	if (it->flags & TIMEOUTS_EXPIRED) {
+		if (it->flags & TIMEOUTS_CLEAR) {
+			while ((to = timeouts_get(T))) {
+				YIELD(to);
+			}
+		} else {
+			TAILQ_FOREACH_SAFE(to, &T->expired, tqe, it->to) {
+				YIELD(to);
+			}
+		}
+	}
+
+	if (it->flags & TIMEOUTS_PENDING) {
+		for (it->i = 0; it->i < countof(T->wheel); it->i++) {
+			for (it->j = 0; it->j < countof(T->wheel[it->i]); it->j++) {
+				TAILQ_FOREACH_SAFE(to, &T->wheel[it->i][it->j], tqe, it->to) {
+					YIELD(to);
+				}
+			}
+		}
+	}
+
+	LEAVE;
+
+	return NULL;
+} /* timeouts_next */
+
+#undef LEAVE
+#undef YIELD
+#undef SAVE_AND_DO
+#undef ENTER
+
+
+/*
+ * T I M E O U T  R O U T I N E S
+ *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+TIMEOUT_PUBLIC struct timeout *timeout_init(struct timeout *to, int flags) {
+	memset(to, 0, sizeof *to);
+
+	to->flags = flags;
+
+	return to;
+} /* timeout_init() */
+
+
+#ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS
+TIMEOUT_PUBLIC bool timeout_pending(struct timeout *to) {
+	return to->pending && to->pending != &to->timeouts->expired;
+} /* timeout_pending() */
+
+
+TIMEOUT_PUBLIC bool timeout_expired(struct timeout *to) {
+	return to->pending && to->pending == &to->timeouts->expired;
+} /* timeout_expired() */
+
+
+TIMEOUT_PUBLIC void timeout_del(struct timeout *to) {
+	timeouts_del(to->timeouts, to);
+} /* timeout_del() */
+#endif
+
+
+/*
+ * V E R S I O N  I N T E R F A C E S
+ *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+TIMEOUT_PUBLIC int timeout_version(void) {
+	return TIMEOUT_VERSION;
+} /* timeout_version() */
+
+
+TIMEOUT_PUBLIC const char *timeout_vendor(void) {
+	return TIMEOUT_VENDOR;
+} /* timeout_version() */
+
+
+TIMEOUT_PUBLIC int timeout_v_rel(void) {
+	return TIMEOUT_V_REL;
+} /* timeout_version() */
+
+
+TIMEOUT_PUBLIC int timeout_v_abi(void) {
+	return TIMEOUT_V_ABI;
+} /* timeout_version() */
+
+
+TIMEOUT_PUBLIC int timeout_v_api(void) {
+	return TIMEOUT_V_API;
+} /* timeout_version() */
+
diff --git a/deps/timeout/timeout.h b/deps/timeout/timeout.h
new file mode 100644
index 0000000..3ef76e9
--- /dev/null
+++ b/deps/timeout/timeout.h
@@ -0,0 +1,253 @@
+/* ==========================================================================
+ * timeout.h - Tickless hierarchical timing wheel.
+ * --------------------------------------------------------------------------
+ * Copyright (c) 2013, 2014  William Ahern
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to permit
+ * persons to whom the Software is furnished to do so, subject to the
+ * following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
+ * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+ * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
+ * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
+ * USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * ==========================================================================
+ */
+#ifndef TIMEOUT_H
+#define TIMEOUT_H
+
+#include <stdbool.h>    /* bool */
+#include <stdio.h>      /* FILE */
+
+#include <inttypes.h>   /* PRIu64 PRIx64 PRIX64 uint64_t */
+
+#include <sys/queue.h>  /* TAILQ(3) */
+
+
+/*
+ * V E R S I O N  I N T E R F A C E S
+ *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#if !defined TIMEOUT_PUBLIC
+#define TIMEOUT_PUBLIC
+#endif
+
+#define TIMEOUT_VERSION TIMEOUT_V_REL
+#define TIMEOUT_VENDOR  "[email protected]"
+
+#define TIMEOUT_V_REL 0x20160226
+#define TIMEOUT_V_ABI 0x20160224
+#define TIMEOUT_V_API 0x20160226
+
+TIMEOUT_PUBLIC int timeout_version(void);
+
+TIMEOUT_PUBLIC const char *timeout_vendor(void);
+
+TIMEOUT_PUBLIC int timeout_v_rel(void);
+
+TIMEOUT_PUBLIC int timeout_v_abi(void);
+
+TIMEOUT_PUBLIC int timeout_v_api(void);
+
+
+/*
+ * I N T E G E R  T Y P E  I N T E R F A C E S
+ *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#define TIMEOUT_C(n) UINT64_C(n)
+#define TIMEOUT_PRIu PRIu64
+#define TIMEOUT_PRIx PRIx64
+#define TIMEOUT_PRIX PRIX64
+
+#define TIMEOUT_mHZ TIMEOUT_C(1000)
+#define TIMEOUT_uHZ TIMEOUT_C(1000000)
+#define TIMEOUT_nHZ TIMEOUT_C(1000000000)
+
+typedef uint64_t timeout_t;
+
+#define timeout_error_t int /* for documentation purposes */
+
+
+/*
+ * C A L L B A C K  I N T E R F A C E
+ *
+ * Callback function parameters unspecified to make embedding into existing
+ * applications easier.
+ *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#ifndef TIMEOUT_CB_OVERRIDE
+struct timeout_cb {
+	void (*fn)();
+	void *arg;
+}; /* struct timeout_cb */
+#endif
+
+/*
+ * T I M E O U T  I N T E R F A C E S
+ *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#ifndef TIMEOUT_DISABLE_INTERVALS
+#define TIMEOUT_INT 0x01 /* interval (repeating) timeout */
+#endif
+#define TIMEOUT_ABS 0x02 /* treat timeout values as absolute */
+
+#define TIMEOUT_INITIALIZER(flags) { (flags) }
+
+#define timeout_setcb(to, fn, arg) do { \
+	(to)->callback.fn = (fn);       \
+	(to)->callback.arg = (arg);     \
+} while (0)
+
+struct timeout {
+	int flags;
+
+	timeout_t expires;
+	/* absolute expiration time */
+
+	struct timeout_list *pending;
+	/* timeout list if pending on wheel or expiry queue */
+
+	TAILQ_ENTRY(timeout) tqe;
+	/* entry member for struct timeout_list lists */
+
+#ifndef TIMEOUT_DISABLE_CALLBACKS
+	struct timeout_cb callback;
+	/* optional callback information */
+#endif
+
+#ifndef TIMEOUT_DISABLE_INTERVALS
+	timeout_t interval;
+	/* timeout interval if periodic */
+#endif
+
+#ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS
+	struct timeouts *timeouts;
+	/* timeouts collection if member of */
+#endif
+}; /* struct timeout */
+
+
+TIMEOUT_PUBLIC struct timeout *timeout_init(struct timeout *, int);
+/* initialize timeout structure (same as TIMEOUT_INITIALIZER) */
+
+#ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS
+TIMEOUT_PUBLIC bool timeout_pending(struct timeout *);
+/* true if on timing wheel, false otherwise */
+ 
+TIMEOUT_PUBLIC bool timeout_expired(struct timeout *);
+/* true if on expired queue, false otherwise */
+
+TIMEOUT_PUBLIC void timeout_del(struct timeout *);
+/* remove timeout from any timing wheel (okay if not member of any) */
+#endif
+
+/*
+ * T I M I N G  W H E E L  I N T E R F A C E S
+ *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+struct timeouts;
+
+TIMEOUT_PUBLIC struct timeouts *timeouts_open(timeout_t, timeout_error_t *);
+/* open a new timing wheel, setting optional HZ (for float conversions) */
+
+TIMEOUT_PUBLIC void timeouts_close(struct timeouts *);
+/* destroy timing wheel */
+
+TIMEOUT_PUBLIC timeout_t timeouts_hz(struct timeouts *);
+/* return HZ setting (for float conversions) */
+
+TIMEOUT_PUBLIC void timeouts_update(struct timeouts *, timeout_t);
+/* update timing wheel with current absolute time */
+
+TIMEOUT_PUBLIC void timeouts_step(struct timeouts *, timeout_t);
+/* step timing wheel by relative time */
+
+TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *);
+/* return interval to next required update */
+
+TIMEOUT_PUBLIC void timeouts_add(struct timeouts *, struct timeout *, timeout_t);
+/* add timeout to timing wheel */
+
+TIMEOUT_PUBLIC void timeouts_del(struct timeouts *, struct timeout *);
+/* remove timeout from any timing wheel or expired queue (okay if on neither) */
+
+TIMEOUT_PUBLIC struct timeout *timeouts_get(struct timeouts *);
+/* return any expired timeout (caller should loop until NULL-return) */
+
+TIMEOUT_PUBLIC bool timeouts_pending(struct timeouts *);
+/* return true if any timeouts pending on timing wheel */
+
+TIMEOUT_PUBLIC bool timeouts_expired(struct timeouts *);
+/* return true if any timeouts on expired queue */
+
+TIMEOUT_PUBLIC bool timeouts_check(struct timeouts *, FILE *);
+/* return true if invariants hold. describes failures to optional file handle. */
+
+#define TIMEOUTS_PENDING 0x10
+#define TIMEOUTS_EXPIRED 0x20
+#define TIMEOUTS_ALL     (TIMEOUTS_PENDING|TIMEOUTS_EXPIRED)
+#define TIMEOUTS_CLEAR   0x40
+
+#define TIMEOUTS_IT_INITIALIZER(flags) { (flags), 0, 0, 0, 0 }
+
+#define TIMEOUTS_IT_INIT(cur, _flags) do {                              \
+	(cur)->flags = (_flags);                                        \
+	(cur)->pc = 0;                                                  \
+} while (0)
+
+struct timeouts_it {
+	int flags;
+	unsigned pc, i, j;
+	struct timeout *to;
+}; /* struct timeouts_it */
+
+TIMEOUT_PUBLIC struct timeout *timeouts_next(struct timeouts *, struct timeouts_it *);
+/* return next timeout in pending wheel or expired queue. caller can delete
+ * the returned timeout, but should not otherwise manipulate the timing
+ * wheel. in particular, caller SHOULD NOT delete any other timeout as that
+ * could invalidate cursor state and trigger a use-after-free.
+ */
+
+#define TIMEOUTS_FOREACH(var, T, flags)                                 \
+	struct timeouts_it _it = TIMEOUTS_IT_INITIALIZER((flags));      \
+	while (((var) = timeouts_next((T), &_it)))
+
+
+/*
+ * B O N U S  W H E E L  I N T E R F A C E S
+ *
+ * I usually use floating point timeouts in all my code, but it's cleaner to
+ * separate it to keep the core algorithmic code simple.
+ *
+ * Using macros instead of static inline routines where <math.h> routines
+ * might be used to keep -lm linking optional.
+ *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#include <math.h> /* ceil(3) */
+
+#define timeouts_f2i(T, f) \
+	((timeout_t)ceil((f) * timeouts_hz((T)))) /* prefer late expiration over early */
+
+#define timeouts_i2f(T, i) \
+	((double)(i) / timeouts_hz((T)))
+
+#define timeouts_addf(T, to, timeout) \
+	timeouts_add((T), (to), timeouts_f2i((T), (timeout)))
+
+#endif /* TIMEOUT_H */