Adding upstream version 9.1.upstream/9.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 134 insertions, 0 deletions

diff --git a/lib/wheel.c b/lib/wheel.c
new file mode 100644
index 0000000..2520e81
--- /dev/null
+++ b/lib/wheel.c
@@ -0,0 +1,134 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Timer Wheel
+ * Copyright (C) 2016 Cumulus Networks, Inc.
+ * Donald Sharp
+ */
+#include "zebra.h"
+#include "linklist.h"
+#include "frrevent.h"
+#include "memory.h"
+#include "wheel.h"
+#include "log.h"
+
+DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL, "Timer Wheel");
+DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL_LIST, "Timer Wheel Slot List");
+
+static int debug_timer_wheel = 0;
+
+static void wheel_timer_thread(struct event *t);
+
+static void wheel_timer_thread_helper(struct event *t)
+{
+	struct listnode *node, *nextnode;
+	unsigned long long curr_slot;
+	unsigned int slots_to_skip = 1;
+	struct timer_wheel *wheel;
+	void *data;
+
+	wheel = EVENT_ARG(t);
+
+	wheel->curr_slot += wheel->slots_to_skip;
+
+	curr_slot = wheel->curr_slot % wheel->slots;
+
+	if (debug_timer_wheel)
+		zlog_debug("%s: Wheel Slot: %lld(%lld) count: %d", __func__,
+			   wheel->curr_slot, curr_slot,
+			   listcount(wheel->wheel_slot_lists[curr_slot]));
+
+	for (ALL_LIST_ELEMENTS(wheel->wheel_slot_lists[curr_slot], node,
+			       nextnode, data))
+		(*wheel->slot_run)(data);
+
+	while (list_isempty(wheel->wheel_slot_lists[(curr_slot + slots_to_skip)
+						    % wheel->slots])
+	       && (curr_slot + slots_to_skip) % wheel->slots != curr_slot)
+		slots_to_skip++;
+
+	wheel->slots_to_skip = slots_to_skip;
+	event_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
+			     wheel->nexttime * slots_to_skip, &wheel->timer);
+}
+
+static void wheel_timer_thread(struct event *t)
+{
+	struct timer_wheel *wheel;
+
+	wheel = EVENT_ARG(t);
+
+	event_execute(wheel->master, wheel_timer_thread_helper, wheel, 0, NULL);
+}
+
+struct timer_wheel *wheel_init(struct event_loop *master, int period,
+			       size_t slots,
+			       unsigned int (*slot_key)(const void *),
+			       void (*slot_run)(void *), const char *run_name)
+{
+	struct timer_wheel *wheel;
+	size_t i;
+
+	wheel = XCALLOC(MTYPE_TIMER_WHEEL, sizeof(struct timer_wheel));
+
+	wheel->name = XSTRDUP(MTYPE_TIMER_WHEEL, run_name);
+	wheel->slot_key = slot_key;
+	wheel->slot_run = slot_run;
+
+	wheel->period = period;
+	wheel->slots = slots;
+	wheel->curr_slot = 0;
+	wheel->master = master;
+	wheel->nexttime = period / slots;
+
+	wheel->wheel_slot_lists = XCALLOC(MTYPE_TIMER_WHEEL_LIST,
+					  slots * sizeof(struct list *));
+	for (i = 0; i < slots; i++)
+		wheel->wheel_slot_lists[i] = list_new();
+
+	event_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
+			     wheel->nexttime, &wheel->timer);
+
+	return wheel;
+}
+
+void wheel_delete(struct timer_wheel *wheel)
+{
+	int i;
+
+	for (i = 0; i < wheel->slots; i++) {
+		list_delete(&wheel->wheel_slot_lists[i]);
+	}
+
+	EVENT_OFF(wheel->timer);
+	XFREE(MTYPE_TIMER_WHEEL_LIST, wheel->wheel_slot_lists);
+	XFREE(MTYPE_TIMER_WHEEL, wheel->name);
+	XFREE(MTYPE_TIMER_WHEEL, wheel);
+}
+
+int wheel_add_item(struct timer_wheel *wheel, void *item)
+{
+	long long slot;
+
+	slot = (*wheel->slot_key)(item);
+
+	if (debug_timer_wheel)
+		zlog_debug("%s: Inserting %p: %lld %lld", __func__, item, slot,
+			   slot % wheel->slots);
+	listnode_add(wheel->wheel_slot_lists[slot % wheel->slots], item);
+
+	return 0;
+}
+
+int wheel_remove_item(struct timer_wheel *wheel, void *item)
+{
+	long long slot;
+
+	slot = (*wheel->slot_key)(item);
+
+	if (debug_timer_wheel)
+		zlog_debug("%s: Removing %p: %lld %lld", __func__, item, slot,
+			   slot % wheel->slots);
+	listnode_delete(wheel->wheel_slot_lists[slot % wheel->slots], item);
+
+	return 0;
+}