On Thu, Oct 24, 2002 at 02:21:55PM +0000, Charles M. Hannum wrote:
> 
> This amuses me a bit.  If you look back in the archives, you'll find
> that I actually implemented this once myself, but nobody seemed to be
> interested in it at the time.

LOL...
 
> A few things:
> 
> 1) You should note that the execution time of a callout is O(log t)
>    with this structure.

No - it is still O(time) because I don't have an indefinite number
of wheels.  OTOH one check per hour is unlikely to be the limiting
factor!

> 2) The list reversal only occurs because you (gratuitously) switched
>    from TAILQs to LISTs.  This is silly, as the savings in both memory
>    and execution overhead is very small.  Also, this may lead to
>    unexpected behavior, such as TCP retransmissions swapping order
>    each time.

The change from TAILQ to LIST isn't completely gratuitous.  It actually
saves you having to worry about exactly which list a callout is in
when you want to delete it. [1]
In any case you can't (completely) maintain the order for callouts that
are moved between layers.
 
> 3) The logic actually gets a bit simpler (in particular, you don't
>    have to do any distance tests when pulling entries up to a closer
>    bucket) if you have the bucket hierarchy extend to the end of time
>    (which is, IIRC, INT_MAX, because that's the maximum value hzto()
>    will return).

I erred on the side of simplicity when deciding which layer of the
hierarchy to link a callout onto.  I suspect it is possible to only
ever need to move an item in one layer, but the sums get hard!
3 layers gives almost all the advantage of 'n' layers without
additional complexity.

hzto() is a little problematic! For 'wall clock' timers I would
use a longer structure and include the wall clock time and recheck
much nearer the expiry time (and if the system clock leaps more than
a few usecs).  Also useful for repetetive timers.

	David

[1] I've been runing this code for several months with a different
list structure that allowed INSERT_TAIL and had a REMOVE that
didn't need the list head.  I sort of convinced myself that
the order wasn't that important (and that reversing the lists,
if necessary, is cheap!)

-- 
David Laight: david@l8s.co.uk