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
Am 12.04.2015 um 21:29 schrieb Thijs
Schreijer:
[
I’m looking for an
efficient timer mechanism in Lua. Does anyone know of any
Lua based timing-wheel implementations? (before I roll my
own)
Thx.
Thijs