tree 531cf756b6bb7ca55f5033c69abe9ee4135e9c4e
parent f74db0b33d491a3189df7f909d382f93f9152c30
author Pablo Neira Ayuso <pablo@gnumonks.org> 1317030303 +0200
committer Harald Welte <laforge@gnumonks.org> 1318850729 +0200

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.