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.

1 files changed, 3 insertions, 3 deletions

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 <sys/time.h>
 
 #include <osmocom/core/linuxlist.h>
+#include <osmocom/core/linuxrbtree.h>
 
 /**
  * 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 */