Merge branch 'timeout_foreach'

5 files changed, 131 insertions, 2 deletions

diff --git a/bench-wheel.c b/bench-wheel.c
index 3089140..cef80f8 100644
--- a/bench-wheel.c
+++ b/bench-wheel.c
@@ -57,6 +57,11 @@ static int empty(void *T) {
 } /* empty() */
 
 
+static struct timeout *next(void *T, struct timeouts_cursor *cur) {
+	return timeouts_next(T, cur);
+} /* next() */
+
+
 static void destroy(void *T) {
 	timeouts_close(T);
 } /* destroy() */
@@ -70,6 +75,7 @@ const struct benchops benchops = {
 	.update  = &update,
 	.check   = &check,
 	.empty   = &empty,
+	.next    = &next,
 	.destroy = &destroy
 };
 
diff --git a/bench.c b/bench.c
index 05d37ed..341fa2c 100644
--- a/bench.c
+++ b/bench.c
@@ -183,6 +183,39 @@ static int bench_empty(lua_State *L) {
 } /* bench_empty() */
 
 
+static int bench__next(lua_State *L) {
+	struct bench *B = lua_touserdata(L, lua_upvalueindex(1));
+	struct timeouts_cursor *cursor = lua_touserdata(L, lua_upvalueindex(2));
+	struct timeout *to;
+
+	if (!B->ops.next || !(to = B->ops.next(B->state, cursor)))
+		return 0;
+
+	lua_pushinteger(L, luaL_optinteger(L, 2, 0) + 1);
+
+	lua_newtable(L);
+	lua_pushinteger(L, to->expires);
+	lua_setfield(L, -2, "expires");
+
+	return 2;
+} /* bench__next() */
+
+static int bench__pairs(lua_State *L) {
+	struct timeouts_cursor *cursor;
+
+	lua_settop(L, 1);
+
+	cursor = lua_newuserdata(L, sizeof *cursor);
+	TIMEOUTS_CURSOR_INIT(cursor, TIMEOUTS_ALL);
+
+	lua_pushcclosure(L, &bench__next, 2);
+	lua_pushvalue(L, 1);
+	lua_pushinteger(L, 0);
+
+	return 3;
+} /* bench__pairs() */
+
+
 static int bench__gc(lua_State *L) {
 	struct bench *B = lua_touserdata(L, 1);
 
@@ -206,8 +239,9 @@ static const luaL_Reg bench_methods[] = {
 };
 
 static const luaL_Reg bench_metatable[] = {
-	{ "__gc", &bench__gc },
-	{ NULL,   NULL }
+	{ "__pairs", &bench__pairs },
+	{ "__gc",    &bench__gc },
+	{ NULL,      NULL }
 };
 
 static const luaL_Reg bench_globals[] = {
diff --git a/bench.h b/bench.h
index bd29301..aa3ed34 100644
--- a/bench.h
+++ b/bench.h
@@ -6,5 +6,6 @@ struct benchops {
 	void (*update)(void *, timeout_t);
 	void (*check)(void *);
 	int (*empty)(void *);
+	struct timeout *(*next)(void *, struct timeouts_cursor *);
 	void (*destroy)(void *);
 }; /* struct benchops() */
diff --git a/timeout.c b/timeout.c
index 88aaa02..eb72bc1 100644
--- a/timeout.c
+++ b/timeout.c
@@ -79,6 +79,13 @@
 } 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
@@ -612,6 +619,59 @@ TIMEOUT_PUBLIC bool timeouts_check(struct timeouts *T, FILE *fp) {
 } /* timeouts_check() */
 
 
+#define ENTER                                                           \
+	do {                                                            \
+	static const int pc0 = __LINE__;                                \
+	switch (pc0 + cur->pc) {                                        \
+	case __LINE__: (void)0
+
+#define SAVE_AND_DO(do_statement)                                       \
+	do {                                                            \
+		cur->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_cursor *cur) {
+	struct timeout *to;
+
+	ENTER;
+
+	if (cur->flags & TIMEOUTS_EXPIRED) {
+		TAILQ_FOREACH_SAFE(to, &T->expired, tqe, cur->to) {
+			YIELD(to);
+		}
+	}
+
+	if (cur->flags & TIMEOUTS_PENDING) {
+		for (cur->i = 0; cur->i < countof(T->wheel); cur->i++) {
+			for (cur->j = 0; cur->j < countof(T->wheel[cur->i]); cur->j++) {
+				TAILQ_FOREACH_SAFE(to, &T->wheel[cur->i][cur->j], tqe, cur->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
  *
diff --git a/timeout.h b/timeout.h
index ee0180d..5c82753 100644
--- a/timeout.h
+++ b/timeout.h
@@ -189,6 +189,34 @@ TIMEOUT_PUBLIC bool timeouts_expired(struct timeouts *);
 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_CURSOR_INITIALIZER(flags) { (flags) }
+
+#define TIMEOUTS_CURSOR_INIT(cur, _flags) do {                          \
+	(cur)->flags = (_flags);                                        \
+	(cur)->pc = 0;                                                  \
+} while (0)
+
+struct timeouts_cursor {
+	int flags;
+	unsigned pc, i, j;
+	struct timeout *to;
+}; /* struct timeouts_cursor */
+
+TIMEOUT_PUBLIC struct timeout *timeouts_next(struct timeouts *, struct timeouts_cursor *);
+/* 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_cursor _foreach_cursor = TIMEOUTS_CURSOR_INITIALIZER((flags)); \
+	while (((var) = timeouts_next((T), &_foreach_cursor)))
+
 
 /*
  * B O N U S  W H E E L  I N T E R F A C E S