subms_timer_wheel/
lib.rs

1//! Single-level hashed timer wheel. O(1) schedule and cancel.
2//!
3//! The wheel has `N` buckets. A scheduled timer at `delay` ticks goes into
4//! bucket `(now + delay) % N` with a `rounds` counter of `delay / N`.
5//! On `tick()`, the hand walks one bucket forward: timers with `rounds == 0`
6//! fire (their callbacks are returned); the rest have `rounds` decremented.
7//! Cancel sets a flag; the entry is dropped lazily on the next visit.
8//!
9//! Tradeoff vs the hierarchical wheel: with a single level, a long delay
10//! causes many no-op revolutions. For workloads with delays bounded by
11//! `N` ticks, the single level is optimal.
12//!
13//! ```
14//! use subms_timer_wheel::TimerWheel;
15//! let mut w: TimerWheel<&'static str> = TimerWheel::new(256);
16//! let id = w.schedule(5, "hello");
17//! for _ in 0..4 { assert!(w.tick().is_empty()); }
18//! assert_eq!(w.tick(), vec!["hello"]);
19//! let _ = id; // returned id can be used to cancel before firing
20//! ```
21
22use std::collections::HashMap;
23
24pub struct TimerWheel<V> {
25    slots: Vec<Slot<V>>,
26    mask: usize,
27    hand: usize,
28    next_id: u64,
29    /// Auxiliary index for O(1) cancellation: id -> (slot, position-in-vec).
30    /// Position can shift when entries fire; we re-index on tick to keep it tight.
31    id_to_slot: HashMap<u64, usize>,
32}
33
34struct Slot<V> {
35    entries: Vec<Entry<V>>,
36}
37
38struct Entry<V> {
39    id: u64,
40    rounds: u32,
41    value: V,
42    cancelled: bool,
43}
44
45impl<V> TimerWheel<V> {
46    /// `num_slots` rounded up to a power of two.
47    pub fn new(num_slots: usize) -> Self {
48        let n = num_slots.max(2).next_power_of_two();
49        let mut slots = Vec::with_capacity(n);
50        for _ in 0..n {
51            slots.push(Slot {
52                entries: Vec::new(),
53            });
54        }
55        Self {
56            slots,
57            mask: n - 1,
58            hand: 0,
59            next_id: 1,
60            id_to_slot: HashMap::new(),
61        }
62    }
63
64    pub fn num_slots(&self) -> usize {
65        self.slots.len()
66    }
67
68    /// Schedule `value` to fire in `delay_ticks`. Returns an id for cancel.
69    pub fn schedule(&mut self, delay_ticks: usize, value: V) -> u64 {
70        let target = self.hand.wrapping_add(delay_ticks);
71        let slot = target & self.mask;
72        let rounds = (delay_ticks / self.slots.len()) as u32;
73        let id = self.next_id;
74        self.next_id += 1;
75        self.slots[slot].entries.push(Entry {
76            id,
77            rounds,
78            value,
79            cancelled: false,
80        });
81        self.id_to_slot.insert(id, slot);
82        id
83    }
84
85    /// Mark a scheduled timer cancelled. Returns `true` if it was pending.
86    pub fn cancel(&mut self, id: u64) -> bool {
87        let Some(&slot) = self.id_to_slot.get(&id) else {
88            return false;
89        };
90        // Walk the slot's vec linearly; lazy-flag the entry. Cancellation in
91        // O(1) amortised; the actual sweep is on the next tick of this slot.
92        for e in &mut self.slots[slot].entries {
93            if e.id == id && !e.cancelled {
94                e.cancelled = true;
95                return true;
96            }
97        }
98        false
99    }
100
101    /// Advance the hand one tick. Returns the values of all timers that
102    /// fired (rounds was 0 and not cancelled). Cancelled timers are dropped
103    /// silently. Other timers have their `rounds` decremented.
104    pub fn tick(&mut self) -> Vec<V> {
105        self.hand = (self.hand + 1) & self.mask;
106        let slot = self.hand;
107        let mut fired = Vec::new();
108        let entries = std::mem::take(&mut self.slots[slot].entries);
109        let mut survivors = Vec::new();
110        for mut e in entries {
111            if e.cancelled {
112                self.id_to_slot.remove(&e.id);
113                continue;
114            }
115            if e.rounds == 0 {
116                self.id_to_slot.remove(&e.id);
117                fired.push(e.value);
118            } else {
119                e.rounds -= 1;
120                survivors.push(e);
121            }
122        }
123        self.slots[slot].entries = survivors;
124        fired
125    }
126}
127
128#[cfg(feature = "harness")]
129pub mod recipe;
130
131// Opt-in feature modules. Each is independent of the base wheel and
132// gated by its own Cargo feature; `cargo add subms-timer-wheel` alone
133// keeps the base zero-dep + std-only shape.
134#[cfg(any(
135    feature = "hierarchical",
136    feature = "concurrent",
137    feature = "deadline-scheduler",
138    feature = "cron",
139    feature = "metrics",
140))]
141pub mod features;
142
143#[cfg(feature = "concurrent")]
144pub use features::concurrent::ConcurrentTimerWheel;
145#[cfg(feature = "cron")]
146pub use features::cron::{CronError, CronSchedule, CronScheduler};
147#[cfg(feature = "deadline-scheduler")]
148pub use features::deadline_scheduler::{Clock, DeadlineScheduler, MonotonicClock, TestClock};
149#[cfg(feature = "hierarchical")]
150pub use features::hierarchical::HierarchicalTimerWheel;
151#[cfg(feature = "metrics")]
152pub use features::metrics::{MeteredTimerWheel, TimerMetrics};
subms_timer_wheel/lib.rs

subms_timer_wheel/
lib.rs
