Re: efficient timers

[Nagaev Boris <bnagaev@...>]

On Mon, Apr 13, 2015 at 8:17 AM, Oliver Kroth <oliver.kroth@nec-i.de> wrote:
> Hi Thijs,
>
> not sure if someone else referred to a solution like mine:
> I used in one of my projects a so called binary heap as "queue". New events
> are inserted at the end and bubbled up. Deleted timers leave a hole that is
> filled by inserting the last element and resort the heap. Checking whether
> the first (earliest) event is due can be done in O(1) by looking on the
> heap's root. Inserting and deleting events can be done in O(log n). The
> funny thing is that the heap does not use pointers but is stored in a
> contiguous array using the event's index to calculate the parent's and
> children's indexes.
>
> May not be the most efficient solution but had the smallest overhead on
> checking the due events, and has reasonable effort on queue management.
> The Lua implementations is about 100 LOC.
>
> If someone is interested, I may post it.
>
> --
> Oliver Kroth
>

I am interested. Could you post it, please?

Best regards,
Boris Nagaev