lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

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)