_timing_wheel.pony

use "collections"

class _TimingWheel
"""
A timing wheel in a hierarchical set of timing wheels. Each wheel covers 6
bits of precision.
"""
let _shift: U64
var _pending: U64 = 0
embed _list: Array[List[Timer]]

new create(index: USize) =>
"""
Create a timing wheel at the given hierarchical level.
"""
_shift = (index * _bits()).u64()
_adjust = if index > 0 then 1 else 0 end
_list = Array[List[Timer]](_max())

for i in Range(0, _max()) do
_list.push(List[Timer])
end

fun ref schedule(timer: Timer) =>
"""
Schedule a timer on this wheel. Mark the bit indicating that the given slot
has timers in its list.
"""
let slot = ((timer._next() >> _shift) - _adjust) and _mask()

try
let list = _list(slot.usize())?
_list(slot.usize())?.append_node(timer._get_node())
_pending = _pending or (1 << slot)
end

fun ref advance(list: List[Timer], current: U64, elapsed: U64): Bool =>
"""
Remove pending timers from this timing wheel and put them on the pending
list supplied. Needs the current time and the elapsed time since the
previous advance. Returns true if the next timing wheel in the hierarchy
"""
let time = (elapsed >> _shift).max(1)
let pending =
if time <= _mask() then
let slot = time and _mask()
let slots = (1 << slot) - 1
let old_slot = _slot(current - elapsed)
let new_slot = _slot(current)

slots.rotl(old_slot) or
slots.rotl(new_slot).rotr(slot) or
(1 << new_slot)
else
-1
end

while (pending and _pending) != 0 do
let slot = (pending and _pending).ctz()
try list.append_list(_list(slot.usize())?) end
_pending = _pending and not (1 << slot)
end

(pending and 1) != 0

fun next(current: U64): U64 =>
"""
Given a current time, return the next time at which this timing wheel
should be advanced. Returns -1 if no timers are on this timing wheel.
"""
if _pending != 0 then
let slot = _slot(current)
let mask = (1 << _shift) - 1
((_pending.rotr(slot).ctz() + _adjust).u64() << _shift.u64()) -
else
-1
end

fun ref clear() =>
"""
Cancels all pending timers.
"""
for list in _list.values() do
for timer in list.values() do
timer._cancel()
end
end

fun _slot(time: U64): U64 =>
"""
Return the slot for a given time.
"""
(time >> _shift) and _mask()

fun tag _bits(): USize => 6
fun tag _max(): USize => 1 << _bits()
fun tag _mask(): U64 => (_max() - 1).u64()