From 066c912fd3b4554d4475ae0837c1d62ef6c872d1 Mon Sep 17 00:00:00 2001 From: Pablo Neira Ayuso Date: Mon, 26 Sep 2011 11:45:03 +0200 Subject: timer: add scalable RB-tree based timer infrastructure This patch adds RB-tree based timers which scales better than the previous list-based implementation. It does not require any API changes. It breaks ABI because the osmo_timer_list structure has changed though (to avoid this in the future, we can put internal data in some private structure). The following table summarizes the worst-case computational complexity of this new implementation versus the previous one: rb-tree list-based ------- ---------- calculate next timer to expire O(1) O(n) insertion of new timer O(log n) O(n) deletion of timer O(log n) O(1) timer-fired scheduler O(log n) O(3n) The most repeated cases are: * the calculation of the next timer to expire, that happens in every loop of our select function. * the timer-fired scheduler execution. This new implementation only loses in the deletion of timer scenario, this happens because we may need to rebalance the tree after the removal. So I think there is some real gain if we have some situation in which we have to handle lots of timers. --- include/osmocom/core/timer.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'include/osmocom/core') diff --git a/include/osmocom/core/timer.h b/include/osmocom/core/timer.h index 8f8c826d..30f558b4 100644 --- a/include/osmocom/core/timer.h +++ b/include/osmocom/core/timer.h @@ -32,6 +32,7 @@ #include #include +#include /** * Timer management: @@ -51,11 +52,10 @@ */ /*! \brief A structure representing a single instance of a timer */ struct osmo_timer_list { - struct llist_head entry; /*!< \brief linked list header */ + struct rb_node node; /*!< \brief rb-tree node header */ + struct llist_head list; /*!< \brief internal list header */ struct timeval timeout; /*!< \brief expiration time */ unsigned int active : 1; /*!< \brief is it active? */ - unsigned int handled : 1; /*!< \brief did we already handle it */ - unsigned int in_list : 1; /*!< \brief is it in the global list? */ void (*cb)(void*); /*!< \brief call-back called at timeout */ void *data; /*!< \brief user data for callback */ -- cgit v1.2.3