1 files changed, 256 insertions, 0 deletions
diff --git a/src/ext/timeouts/timeout.h b/src/ext/timeouts/timeout.h
new file mode 100644
index 0000000000..b35874e153
--- /dev/null
+++ b/src/ext/timeouts/timeout.h
@@ -0,0 +1,256 @@
+/* ==========================================================================
+ * 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 "tor_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  "william@25thandClement.com"
+
+#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);
+	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 */
+
+	TOR_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_get_curtime(struct timeouts *);
+/* Return the current tick. */
+
+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 */