timeout.h 6.51 KB
Newer Older
William Ahern's avatar
start  
William Ahern committed
1
/* ==========================================================================
2
 * timeout.h - Tickless hierarchical timing wheel.
William Ahern's avatar
start  
William Ahern committed
3
 * --------------------------------------------------------------------------
william's avatar
william committed
4
 * Copyright (c) 2013, 2014  William Ahern
William Ahern's avatar
start  
William Ahern committed
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
 *
 * 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.
 * ==========================================================================
 */
26 27
#ifndef TIMEOUT_H
#define TIMEOUT_H
William Ahern's avatar
start  
William Ahern committed
28

29 30 31 32 33 34
#include <stdbool.h>    /* bool */
#include <stdio.h>      /* FILE */

#include <inttypes.h>   /* PRIu64 PRIx64 PRIX64 uint64_t */

#include <sys/queue.h>  /* TAILQ(3) */
William Ahern's avatar
start  
William Ahern committed
35 36


37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
/*
 * 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 0x20140103
#define TIMEOUT_V_ABI 0x20140103
#define TIMEOUT_V_API 0x20140103

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);


William Ahern's avatar
start  
William Ahern committed
64
/*
65
 * I N T E G E R  T Y P E  I N T E R F A C E S
William Ahern's avatar
start  
William Ahern committed
66 67 68
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

69 70 71 72
#define TIMEOUT_C(n) UINT64_C(n)
#define TIMEOUT_PRIu PRIu64
#define TIMEOUT_PRIx PRIx64
#define TIMEOUT_PRIX PRIX64
William Ahern's avatar
William Ahern committed
73

74 75 76
#define TIMEOUT_mHZ TIMEOUT_C(1000)
#define TIMEOUT_uHZ TIMEOUT_C(1000000)
#define TIMEOUT_nHZ TIMEOUT_C(1000000000)
William Ahern's avatar
William Ahern committed
77

78
typedef uint64_t timeout_t;
William Ahern's avatar
William Ahern committed
79

william's avatar
william committed
80 81
#define timeout_error_t int /* for documentation purposes */

William Ahern's avatar
William Ahern committed
82

83 84 85
/*
 * C A L L B A C K  I N T E R F A C E
 *
86 87 88
 * Callback function parameters unspecified to make embedding into existing
 * applications easier.
 *
89
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
William Ahern's avatar
William Ahern committed
90

91
#ifndef TIMEOUT_CB_OVERRIDE
92 93 94 95
struct timeout_cb {
	void (*fn)();
	void *arg;
}; /* struct timeout_cb */
96
#endif
William Ahern's avatar
William Ahern committed
97

98 99 100 101
/*
 * T I M E O U T  I N T E R F A C E S
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
William Ahern's avatar
William Ahern committed
102

103 104
#define TIMEOUT_INT 0x01 /* interval (repeating) timeout */
#define TIMEOUT_ABS 0x02 /* treat timeout values as absolute */
William Ahern's avatar
William Ahern committed
105

106
#define TIMEOUT_INITIALIZER(flags) { (flags) }
William Ahern's avatar
William Ahern committed
107

108 109 110 111
#define timeout_setcb(to, fn, arg) do { \
	(to)->callback.fn = (fn);       \
	(to)->callback.arg = (arg);     \
} while (0)
William Ahern's avatar
William Ahern committed
112

113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
struct timeout {
	int flags;

	timeout_t interval;
	/* timeout interval if periodic */

	timeout_t expires;
	/* absolute expiration time */

	struct timeouts *timeouts;
	/* timeouts collection if member of */

	struct timeout_list *pending;
	/* timeout list if pending on wheel or expiry queue */

128 129 130
	TAILQ_ENTRY(timeout) tqe;
	/* entry member for struct timeout_list lists */

131 132 133
	struct timeout_cb callback;
	/* optional callback information */
}; /* struct timeout */
William Ahern's avatar
William Ahern committed
134 135


136
TIMEOUT_PUBLIC struct timeout *timeout_init(struct timeout *, int);
137
/* initialize timeout structure (same as TIMEOUT_INITIALIZER) */
William Ahern's avatar
start  
William Ahern committed
138

139
TIMEOUT_PUBLIC bool timeout_pending(struct timeout *);
140
/* true if on timing wheel, false otherwise */
William Ahern's avatar
William Ahern committed
141
 
142
TIMEOUT_PUBLIC bool timeout_expired(struct timeout *);
143
/* true if on expired queue, false otherwise */
William Ahern's avatar
start  
William Ahern committed
144

145
TIMEOUT_PUBLIC void timeout_del(struct timeout *);
146 147 148 149 150 151 152 153 154 155
/* remove timeout from any timing wheel (okay if not member of any) */


/*
 * T I M I N G  W H E E L  I N T E R F A C E S
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

struct timeouts;

william's avatar
william committed
156
TIMEOUT_PUBLIC struct timeouts *timeouts_open(timeout_t, timeout_error_t *);
157
/* open a new timing wheel, setting optional HZ (for float conversions) */
158

159
TIMEOUT_PUBLIC void timeouts_close(struct timeouts *);
160 161
/* destroy timing wheel */

162 163 164
TIMEOUT_PUBLIC timeout_t timeouts_hz(struct timeouts *);
/* return HZ setting (for float conversions) */

165
TIMEOUT_PUBLIC void timeouts_update(struct timeouts *, timeout_t);
166 167
/* update timing wheel with current absolute time */

168
TIMEOUT_PUBLIC void timeouts_step(struct timeouts *, timeout_t);
169 170
/* step timing wheel by relative time */

171
TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *);
172 173
/* return interval to next required update */

174
TIMEOUT_PUBLIC void timeouts_add(struct timeouts *, struct timeout *, timeout_t);
175 176
/* add timeout to timing wheel */

177
TIMEOUT_PUBLIC void timeouts_del(struct timeouts *, struct timeout *);
178 179
/* remove timeout from any timing wheel or expired queue (okay if on neither) */

william's avatar
william committed
180 181 182
TIMEOUT_PUBLIC struct timeout *timeouts_get(struct timeouts *);
/* return any expired timeout (caller should loop until NULL-return) */

183
TIMEOUT_PUBLIC bool timeouts_pending(struct timeouts *);
184 185
/* return true if any timeouts pending on timing wheel */

186
TIMEOUT_PUBLIC bool timeouts_expired(struct timeouts *);
187 188
/* return true if any timeouts on expired queue */

189
TIMEOUT_PUBLIC bool timeouts_check(struct timeouts *, FILE *);
190 191 192
/* return true if invariants hold. describes failures to optional file handle. */


william's avatar
william committed
193 194 195 196 197 198 199 200 201 202 203 204 205 206
/*
 * 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) \
207
	((timeout_t)ceil((f) * timeouts_hz((T)))) /* prefer late expiration over early */
william's avatar
william committed
208 209

#define timeouts_i2f(T, i) \
210
	((double)(i) / timeouts_hz((T)))
william's avatar
william committed
211 212 213 214

#define timeouts_addf(T, to, timeout) \
	timeouts_add((T), (to), timeouts_f2i((T), (timeout)))

215
#endif /* TIMEOUT_H */