Struct TimerWheel 

pub struct TimerWheel<T, const NUM_LEVELS: usize, const NUM_SLOTS: usize> { /* private fields */ }

Hierarchical timer wheel

This is a multi-level timer data structure where each level has lower resolution (is coarser) than the previous. It efficiently handles expiration of many timers by batching them into slots.

Parameters

• T: The context type associated with each timer
• NUM_LEVELS: The number of hierarchical levels (each adds a factor of NUM_SLOTS in range)
• NUM_SLOTS: The number of slots per level

Resolution and Range

• Range per level: Level 0 covers [0, NUM_SLOTS] ticks. Level 1 covers [0, NUM_SLOTS²] ticks at coarser granularity. In general, level L covers [0, NUM_SLOTS^(L+1)] ticks.

• Total range: With NUM_LEVELS levels, the wheel can represent timers up to approximately NUM_SLOTS^NUM_LEVELS ticks in the future (though timers beyond NUM_SLOTS^NUM_LEVELS are still supported, see below).

Handling Timers Far in the Future

When a timer is scheduled with an expiration time far beyond what the wheel’s levels can directly represent (delta ≥ NUM_SLOTS^NUM_LEVELS), it is placed in the last slot of the highest level. As time progresses and cascading occurs, such timers are progressively re-inserted at appropriate finer-resolution slots, eventually cascading down to level 0 for precise expiration. This approach trades initial placement overhead for the ability to handle arbitrarily distant future timers without requiring additional data structures.

Compatibility with VPP C Timer Wheels

The functionality and interface to the timer wheel is intended to be similar to VPP C Timer Wheels, but isn’t binary-compatible with VPP C Timer Wheels, since this would constrain the implementation too much and it’s not envisaged to be likely that timer wheels would be used across API boundaries.

Implementations

impl<T, const NUM_LEVELS: usize, const NUM_SLOTS: usize> TimerWheel<T, NUM_LEVELS, NUM_SLOTS>

pub fn new() -> Self

Create a new timer wheel

pub fn init(uninit_self: &mut MaybeUninit<Self>) -> &mut Self

Initialise a TimerWheel in uninitialized memory.

This can be used to avoid excessive stage usage when uninit_self is located in allocated memory, such as from a Vec, Box or Rc.

pub fn start_timer(&mut self, interval: u64, context: T) -> TimerHandle

Start a timer which expires after the given interval

The timer is one-shot, not periodic.

interval is the interval past the last time timers were expired after which this timer should expire. context is a context to associate with the timer

This has a time complexity of O(1).

pub fn start_timer_absolute( &mut self, expire_time: u64, context: T, ) -> Result<TimerHandle, StartTimerError<T>>

Start a timer which expires at an absolute time

expire_time is the absolute time after which this timer should expire. context is a context to associate with the timer

This has a time complexity of O(1).

pub fn stop_timer(&mut self, handle: TimerHandle) -> Option<T>

Stop a running timer

This has a time complexity of O(1).

pub fn expire_timers(&mut self, ticks: u64) -> Vec<T>

Advance time by multiple ticks, expiring timers

pub fn next_expiration(&self) -> Option<u64>

Get the next expiration time in ticks, or None if no unexpired, started timers

This has worst-case time complexity O(n) where n is NUM_LEVELS * NUM_SLOTS.

Trait Implementations

impl<T: Debug, const NUM_LEVELS: usize, const NUM_SLOTS: usize> Debug for TimerWheel<T, NUM_LEVELS, NUM_SLOTS>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T, const NUM_LEVELS: usize, const NUM_SLOTS: usize> Default for TimerWheel<T, NUM_LEVELS, NUM_SLOTS>

fn default() -> Self

Returns the “default value” for a type.