Skip to main content

nexus_timer/
wheel.rs

1//! Timer wheel — the main data structure.
2//!
3//! `TimerWheel<T, S>` is a multi-level, rebalancing timer wheel. Entries are
4//! placed into a level based on how far in the future their deadline is, and
5//! **rebalanced** down to finer levels as their deadline approaches; `poll`
6//! then collects ready timers from the small, exact fine-level slots. Timers
7//! fire at their exact tick, never early, never missed.
8
9use std::cell::Cell;
10use std::marker::PhantomData;
11use std::mem;
12use std::time::{Duration, Instant};
13
14use nexus_slab::{Full, Slot, bounded, unbounded};
15
16use crate::entry::{EntryPtr, WheelEntry, entry_ref};
17use crate::handle::TimerHandle;
18use crate::level::Level;
19use crate::store::{BoundedStore, SlabStore};
20
21/// Error returned by a builder's `build` when the configuration is invalid.
22///
23/// A wheel / queue is configured at construction from your own constants, so an
24/// invalid config is a programmer error — but it is *returned* rather than
25/// panicked, both for consistency with the rest of the workspace and so a caller
26/// that sources configuration from runtime input can handle it. The message
27/// names the constraint that was violated.
28#[derive(Debug, Clone, PartialEq, Eq)]
29pub enum ConfigError {
30    /// A configuration value is out of range; the message names the constraint.
31    Invalid(&'static str),
32}
33
34impl std::fmt::Display for ConfigError {
35    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
36        match self {
37            Self::Invalid(msg) => write!(f, "timer configuration error: {msg}"),
38        }
39    }
40}
41
42impl std::error::Error for ConfigError {}
43
44// =============================================================================
45// WheelBuilder (typestate)
46// =============================================================================
47
48/// Builder for configuring a timer wheel.
49///
50/// Defaults match the Linux kernel timer wheel (1ms tick, 64 slots/level,
51/// 8x multiplier, 7 levels → ~4.7 hour range).
52///
53/// # Examples
54///
55/// ```
56/// use std::time::{Duration, Instant};
57/// use nexus_timer::{Wheel, WheelBuilder};
58///
59/// let now = Instant::now();
60///
61/// // All defaults
62/// let wheel: Wheel<u64> = WheelBuilder::default().unbounded(4096).build(now).unwrap();
63///
64/// // Custom config
65/// let wheel: Wheel<u64> = WheelBuilder::default()
66///     .tick_duration(Duration::from_micros(100))
67///     .slots_per_level(32)
68///     .unbounded(4096)
69///     .build(now)
70///     .unwrap();
71/// ```
72#[derive(Debug, Clone, Copy)]
73pub struct WheelBuilder {
74    tick_duration: Duration,
75    slots_per_level: usize,
76    clk_shift: u32,
77    num_levels: usize,
78    max_rebalances_per_poll: usize,
79}
80
81impl Default for WheelBuilder {
82    fn default() -> Self {
83        WheelBuilder {
84            tick_duration: Duration::from_millis(1),
85            slots_per_level: 64,
86            clk_shift: 3,
87            num_levels: 7,
88            max_rebalances_per_poll: usize::MAX,
89        }
90    }
91}
92
93impl WheelBuilder {
94    /// Creates a new builder with default configuration.
95    pub fn new() -> Self {
96        Self::default()
97    }
98
99    /// Sets the tick duration. Default: 1ms.
100    pub fn tick_duration(mut self, d: Duration) -> Self {
101        self.tick_duration = d;
102        self
103    }
104
105    /// Sets the number of slots per level. Must be a power of 2, at most 64, and
106    /// greater than `2^clk_shift` so a rebalance always moves an entry to a
107    /// strictly finer level (`clk_shift` and `slots_per_level` are validated
108    /// together at [`build`](UnboundedWheelBuilder::build)). Default: 64.
109    pub fn slots_per_level(mut self, n: usize) -> Self {
110        self.slots_per_level = n;
111        self
112    }
113
114    /// Sets the bit shift between levels (multiplier = 2^clk_shift). Must satisfy
115    /// `2^clk_shift < slots_per_level` so a rebalance always moves an entry to a
116    /// strictly finer level (validated at build); with the default 64 slots that
117    /// allows `clk_shift` up to 5. Default: 3 (8x).
118    pub fn clk_shift(mut self, s: u32) -> Self {
119        self.clk_shift = s;
120        self
121    }
122
123    /// Sets the number of levels. Default: 7.
124    pub fn num_levels(mut self, n: usize) -> Self {
125        self.num_levels = n;
126        self
127    }
128
129    /// Sets the maximum number of entries **rebalanced** (moved to a finer
130    /// level) per [`poll_and_rebalance`](TimerWheel::poll_and_rebalance).
131    /// Default: `usize::MAX` (unbounded).
132    ///
133    /// Rebalancing is maintenance: as time advances, a timer scheduled far in
134    /// the future is placed in a coarse level, and when its slot comes due it is
135    /// moved down to a finer level so it is not re-scanned on every future poll.
136    /// Unbounded (the default), one poll rebalances a whole slot at once — least
137    /// total work, but a rare poll can spike. A cap spreads that work across
138    /// several polls: each poll rebalances at most `n` entries and leaves the
139    /// rest in place, trading the rare spike for slightly more total work (the
140    /// leftover entries are walked again on a later poll).
141    ///
142    /// **This bounds only rebalancing, never firing.** Every due timer is still
143    /// collected at its exact deadline regardless of the cap, because a
144    /// not-yet-due entry left un-rebalanced simply fires from whatever level it
145    /// is sitting in when its time comes. The cap can therefore never make a
146    /// timer fire late or be missed; it is purely a latency-smoothing knob for
147    /// the poll hot path.
148    ///
149    /// **Recommended to tune** for latency-sensitive loops: pick `n` large
150    /// enough to keep up with the steady rebalance rate (roughly
151    /// `population * num_levels / average_timeout_in_ticks`) so entries do not
152    /// backlog, yet small enough that no single poll stalls.
153    pub fn max_rebalances_per_poll(mut self, n: usize) -> Self {
154        self.max_rebalances_per_poll = n;
155        self
156    }
157
158    /// Transitions to an unbounded wheel builder.
159    ///
160    /// `chunk_capacity` is the slab chunk size (entries per chunk). The slab
161    /// grows by adding new chunks as needed.
162    pub fn unbounded(self, chunk_capacity: usize) -> UnboundedWheelBuilder {
163        UnboundedWheelBuilder {
164            config: self,
165            chunk_capacity,
166        }
167    }
168
169    /// Transitions to a bounded wheel builder.
170    ///
171    /// `capacity` is the maximum number of concurrent timers.
172    pub fn bounded(self, capacity: usize) -> BoundedWheelBuilder {
173        BoundedWheelBuilder {
174            config: self,
175            capacity,
176        }
177    }
178
179    fn validate(&self) -> Result<(), ConfigError> {
180        if !self.slots_per_level.is_power_of_two() {
181            return Err(ConfigError::Invalid("slots_per_level must be a power of 2"));
182        }
183        if self.slots_per_level > 64 {
184            return Err(ConfigError::Invalid(
185                "slots_per_level must be <= 64 (u64 bitmask)",
186            ));
187        }
188        if self.num_levels == 0 {
189            return Err(ConfigError::Invalid("num_levels must be > 0"));
190        }
191        if self.num_levels > 8 {
192            return Err(ConfigError::Invalid("num_levels must be <= 8 (u8 bitmask)"));
193        }
194        if self.clk_shift == 0 {
195            return Err(ConfigError::Invalid("clk_shift must be > 0"));
196        }
197        if self.tick_duration.is_zero() {
198            return Err(ConfigError::Invalid("tick_duration must be non-zero"));
199        }
200        // tick_ns() narrows as_nanos() (u128) to u64; a duration whose nanos
201        // exceed u64::MAX would truncate — and a nonzero multiple of 2^64 would
202        // truncate to 0, making inv_tick_ns a divide-by-zero. Reject up front so
203        // build() stays panic-free.
204        if self.tick_duration.as_nanos() > u64::MAX as u128 {
205            return Err(ConfigError::Invalid(
206                "tick_duration must fit in u64 nanoseconds",
207            ));
208        }
209        let max_shift = (self.num_levels - 1) as u64 * self.clk_shift as u64;
210        if max_shift >= 64 {
211            return Err(ConfigError::Invalid(
212                "(num_levels - 1) * clk_shift must be < 64",
213            ));
214        }
215        let slots_log2 = self.slots_per_level.trailing_zeros() as u64;
216        if slots_log2 + max_shift >= 64 {
217            return Err(ConfigError::Invalid(
218                "slots_per_level << max_shift would overflow u64",
219            ));
220        }
221        // Rebalance progress guard. When a due slot is polled, a not-yet-due
222        // entry is relocated to a strictly finer level (see `TimerWheel::poll_level`);
223        // that requires 2^clk_shift < slots_per_level (both powers of two, so
224        // `clk_shift < slots_log2`, avoiding a shift that could overflow for
225        // absurd clk_shift). Checked last so a config that also overflows reports
226        // the overflow first.
227        if (self.clk_shift as u64) >= slots_log2 {
228            return Err(ConfigError::Invalid(
229                "2^clk_shift must be < slots_per_level so rebalancing relocates to a strictly finer level",
230            ));
231        }
232        Ok(())
233    }
234
235    fn tick_ns(&self) -> u64 {
236        self.tick_duration.as_nanos() as u64
237    }
238}
239
240/// Terminal builder for an unbounded timer wheel.
241///
242/// Created via [`WheelBuilder::unbounded`]. The only method is `.build()`.
243#[derive(Debug)]
244pub struct UnboundedWheelBuilder {
245    config: WheelBuilder,
246    chunk_capacity: usize,
247}
248
249impl UnboundedWheelBuilder {
250    /// Builds the unbounded timer wheel, validating the configuration.
251    ///
252    /// # Errors
253    ///
254    /// Returns [`ConfigError`] if the configuration is invalid (e.g.
255    /// non-power-of-2 `slots_per_level`, out-of-range `num_levels` / `clk_shift`,
256    /// zero tick duration, or `2^clk_shift >= slots_per_level`).
257    pub fn build<T: 'static>(self, now: Instant) -> Result<Wheel<T>, ConfigError> {
258        self.config.validate()?;
259        // SAFETY: Timer wheel is single-threaded (!Send, !Sync). All slots
260        // are freed via Slot::from_raw() + slab.free() before the wheel drops.
261        // The slab is never shared across threads.
262        let slab = unsafe { unbounded::Slab::with_chunk_capacity(self.chunk_capacity) };
263        let levels = build_levels::<T>(&self.config);
264        let tick_ns = self.config.tick_ns();
265        Ok(TimerWheel {
266            slab,
267            num_levels: self.config.num_levels,
268            levels,
269            current_ticks: 0,
270            tick_ns,
271            inv_tick_ns: (1u128 << 64) / tick_ns as u128,
272            epoch: now,
273            active_levels: 0,
274            len: 0,
275            min_deadline: Cell::new(None),
276            max_rebalances_per_poll: self.config.max_rebalances_per_poll,
277            _marker: PhantomData,
278        })
279    }
280}
281
282/// Terminal builder for a bounded timer wheel.
283///
284/// Created via [`WheelBuilder::bounded`]. The only method is `.build()`.
285#[derive(Debug)]
286pub struct BoundedWheelBuilder {
287    config: WheelBuilder,
288    capacity: usize,
289}
290
291impl BoundedWheelBuilder {
292    /// Builds the bounded timer wheel, validating the configuration.
293    ///
294    /// # Errors
295    ///
296    /// Returns [`ConfigError`] if the configuration is invalid (e.g.
297    /// non-power-of-2 `slots_per_level`, out-of-range `num_levels` / `clk_shift`,
298    /// zero tick duration, or `2^clk_shift >= slots_per_level`).
299    pub fn build<T: 'static>(self, now: Instant) -> Result<BoundedWheel<T>, ConfigError> {
300        self.config.validate()?;
301        // SAFETY: Timer wheel is single-threaded (!Send, !Sync). All slots
302        // are freed via Slot::from_raw() + slab.free() before the wheel drops.
303        // The slab is never shared across threads.
304        let slab = unsafe { bounded::Slab::with_capacity(self.capacity) };
305        let levels = build_levels::<T>(&self.config);
306        let tick_ns = self.config.tick_ns();
307        Ok(TimerWheel {
308            slab,
309            num_levels: self.config.num_levels,
310            levels,
311            current_ticks: 0,
312            tick_ns,
313            inv_tick_ns: (1u128 << 64) / tick_ns as u128,
314            epoch: now,
315            active_levels: 0,
316            len: 0,
317            min_deadline: Cell::new(None),
318            max_rebalances_per_poll: self.config.max_rebalances_per_poll,
319            _marker: PhantomData,
320        })
321    }
322}
323
324// =============================================================================
325// TimerWheel
326// =============================================================================
327
328/// A multi-level, rebalancing timer wheel.
329///
330/// Generic over:
331/// - `T` — the user payload stored with each timer.
332/// - `S` — the slab storage backend. Defaults to `unbounded::Slab`.
333///
334/// # Thread Safety
335///
336/// `Send` but `!Sync`. Can be moved to a thread at setup but must not
337/// be shared. All internal raw pointers point into owned allocations
338/// (slab chunks, level slot arrays) — moving the wheel moves the heap
339/// data with it.
340pub struct TimerWheel<
341    T: 'static,
342    S: SlabStore<Item = WheelEntry<T>> = unbounded::Slab<WheelEntry<T>>,
343> {
344    slab: S,
345    levels: Vec<Level<T>>,
346    num_levels: usize,
347    active_levels: u8,
348    current_ticks: u64,
349    tick_ns: u64,
350    inv_tick_ns: u128,
351    epoch: Instant,
352    len: usize,
353    min_deadline: Cell<Option<u64>>,
354    /// Max entries rebalanced (moved to a finer level) per poll_and_rebalance (see
355    /// [`WheelBuilder::max_rebalances_per_poll`]). `usize::MAX` = unbounded.
356    max_rebalances_per_poll: usize,
357    _marker: PhantomData<*const ()>, // !Send (overridden below), !Sync
358}
359
360// SAFETY: TimerWheel<T, S> exclusively owns all memory behind its raw pointers.
361//
362// Pointer inventory and ownership:
363// - Slot `entry_head`/`entry_tail` — point into slab-owned memory (SlotCell
364//   in a slab chunk). Slab chunks are Vec<SlotCell<T>> heap allocations.
365// - DLL links (`WheelEntry::prev`, `WheelEntry::next`) — point to other
366//   SlotCells in the same slab.
367// - `Level::slots` — `Box<[WheelSlot<T>]>`, owned by the level.
368//
369// All pointed-to memory lives inside owned collections (Vec, Box<[T]>).
370// When TimerWheel is moved, the heap allocations stay at their addresses —
371// the internal pointers remain valid. No thread-local state. No shared
372// ownership.
373//
374// T: Send is required because timer values cross the thread boundary with
375// the wheel.
376//
377// S is NOT required to be Send. Slab types are !Send (raw pointers, Cell)
378// but the wheel exclusively owns its slab — no shared access, no aliasing.
379// Moving the wheel moves the slab; heap allocations stay at their addresses
380// so internal pointers remain valid.
381//
382// Outstanding TimerHandle<T> values are !Send and cannot follow the wheel
383// across threads. They become inert — consuming them requires &mut
384// TimerWheel which the original thread no longer has. The debug_assert in
385// TimerHandle::drop catches this as a programming error. Worst case is a
386// slot leak (refcount stuck at 1), not unsoundness.
387#[allow(clippy::non_send_fields_in_send_ty)]
388unsafe impl<T: Send + 'static, S: SlabStore<Item = WheelEntry<T>>> Send for TimerWheel<T, S> {}
389
390/// A timer wheel backed by a fixed-capacity slab.
391pub type BoundedWheel<T> = TimerWheel<T, bounded::Slab<WheelEntry<T>>>;
392
393/// A timer wheel backed by a growable slab.
394pub type Wheel<T> = TimerWheel<T, unbounded::Slab<WheelEntry<T>>>;
395
396// =============================================================================
397// Construction
398// =============================================================================
399
400impl<T: 'static> Wheel<T> {
401    /// Creates an unbounded timer wheel with default configuration.
402    ///
403    /// `now` fixes the reference epoch — pass one monotone clock source
404    /// (e.g. `Instant::now()`) here and to every `schedule`/`poll`. For custom
405    /// configuration, use [`WheelBuilder`].
406    pub fn unbounded(chunk_capacity: usize, now: Instant) -> Self {
407        WheelBuilder::default()
408            .unbounded(chunk_capacity)
409            .build(now)
410            .expect("default WheelBuilder config is valid")
411    }
412}
413
414impl<T: 'static> BoundedWheel<T> {
415    /// Creates a bounded timer wheel with default configuration.
416    ///
417    /// `now` fixes the reference epoch — pass one monotone clock source
418    /// (e.g. `Instant::now()`) here and to every `schedule`/`poll`. For custom
419    /// configuration, use [`WheelBuilder`].
420    pub fn bounded(capacity: usize, now: Instant) -> Self {
421        WheelBuilder::default()
422            .bounded(capacity)
423            .build(now)
424            .expect("default WheelBuilder config is valid")
425    }
426}
427
428fn build_levels<T: 'static>(config: &WheelBuilder) -> Vec<Level<T>> {
429    (0..config.num_levels)
430        .map(|i| Level::new(config.slots_per_level, i, config.clk_shift))
431        .collect()
432}
433
434// =============================================================================
435// Schedule
436// =============================================================================
437
438impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> TimerWheel<T, S> {
439    /// Schedules a timer and returns a handle for cancellation.
440    ///
441    /// The handle must be consumed via [`cancel`](Self::cancel) or
442    /// [`free`](Self::free). Dropping it is a programming error.
443    ///
444    /// # Panics
445    ///
446    /// Panics if the backing slab is at capacity (bounded slabs only).
447    /// This is a capacity planning error — size your wheel for peak load.
448    pub fn schedule(&mut self, deadline: Instant, value: T) -> TimerHandle<T> {
449        let deadline_ticks = self.instant_to_ticks(deadline);
450        let entry = WheelEntry::new(deadline_ticks, value, 2);
451        let slot = self.slab.alloc(entry);
452        let ptr = slot.into_raw();
453        self.insert_entry(ptr, deadline_ticks);
454        self.len += 1;
455        TimerHandle::new(ptr)
456    }
457
458    /// Schedules a fire-and-forget timer (no handle returned).
459    ///
460    /// The timer will fire during poll and the value will be collected.
461    /// Cannot be cancelled.
462    ///
463    /// # Panics
464    ///
465    /// Panics if the backing slab is at capacity (bounded slabs only).
466    /// This is a capacity planning error — size your wheel for peak load.
467    pub fn schedule_forget(&mut self, deadline: Instant, value: T) {
468        let deadline_ticks = self.instant_to_ticks(deadline);
469        let entry = WheelEntry::new(deadline_ticks, value, 1);
470        let slot = self.slab.alloc(entry);
471        let ptr = slot.into_raw();
472        self.insert_entry(ptr, deadline_ticks);
473        self.len += 1;
474    }
475}
476
477// =============================================================================
478// Schedule — fallible (bounded slabs only)
479// =============================================================================
480
481impl<T: 'static, S: BoundedStore<Item = WheelEntry<T>>> TimerWheel<T, S> {
482    /// Attempts to schedule a timer, returning a handle on success.
483    ///
484    /// Returns `Err(Full(value))` if the slab is at capacity. Use this
485    /// when you need graceful error handling. For the common case where
486    /// capacity exhaustion is fatal, use [`schedule`](Self::schedule).
487    pub fn try_schedule(&mut self, deadline: Instant, value: T) -> Result<TimerHandle<T>, Full<T>> {
488        let deadline_ticks = self.instant_to_ticks(deadline);
489        let entry = WheelEntry::new(deadline_ticks, value, 2);
490        match self.slab.try_alloc(entry) {
491            Ok(slot) => {
492                let ptr = slot.into_raw();
493                self.insert_entry(ptr, deadline_ticks);
494                self.len += 1;
495                Ok(TimerHandle::new(ptr))
496            }
497            Err(full) => {
498                // Extract the user's T from the WheelEntry wrapper
499                let wheel_entry = full.into_inner();
500                // SAFETY: entry was just constructed with Some(value) and never inserted
501                // into the wheel — no other code has accessed it. Single-threaded.
502                let value = unsafe { wheel_entry.take_value() }
503                    .expect("entry was just constructed with Some(value)");
504                Err(Full(value))
505            }
506        }
507    }
508
509    /// Attempts to schedule a fire-and-forget timer.
510    ///
511    /// Returns `Err(Full(value))` if the slab is at capacity. Use this
512    /// when you need graceful error handling. For the common case where
513    /// capacity exhaustion is fatal, use [`schedule_forget`](Self::schedule_forget).
514    pub fn try_schedule_forget(&mut self, deadline: Instant, value: T) -> Result<(), Full<T>> {
515        let deadline_ticks = self.instant_to_ticks(deadline);
516        let entry = WheelEntry::new(deadline_ticks, value, 1);
517        match self.slab.try_alloc(entry) {
518            Ok(slot) => {
519                let ptr = slot.into_raw();
520                self.insert_entry(ptr, deadline_ticks);
521                self.len += 1;
522                Ok(())
523            }
524            Err(full) => {
525                let wheel_entry = full.into_inner();
526                // SAFETY: entry was just constructed with Some(value) and never inserted
527                // into the wheel — no other code has accessed it. Single-threaded.
528                let value = unsafe { wheel_entry.take_value() }
529                    .expect("entry was just constructed with Some(value)");
530                Err(Full(value))
531            }
532        }
533    }
534}
535
536// =============================================================================
537// Cancel / Free / Poll / Query — generic over any store
538// =============================================================================
539
540impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> TimerWheel<T, S> {
541    /// Cancels a timer and returns its value.
542    ///
543    /// - If the timer is still active: unlinks from the wheel, extracts value,
544    ///   frees the slab entry. Returns `Some(T)`.
545    /// - If the timer already fired (zombie handle): frees the slab entry.
546    ///   Returns `None`.
547    ///
548    /// Consumes the handle (no Drop runs).
549    pub fn cancel(&mut self, handle: TimerHandle<T>) -> Option<T> {
550        let ptr = handle.ptr;
551        // Consume handle without running Drop
552        mem::forget(handle);
553
554        // SAFETY: handle guarantees ptr is valid and allocated from our slab.
555        let entry = unsafe { entry_ref(ptr) };
556        let refs = entry.refs();
557
558        if refs == 2 {
559            // Active timer with handle — unlink, extract, free
560            // SAFETY: single-threaded access; entry is still in the wheel (refs==2),
561            // so the value has not been taken by fire_entry.
562            let value = unsafe { entry.take_value() };
563            let cancelled_deadline = entry.deadline_ticks();
564            self.remove_entry(ptr);
565            self.len -= 1;
566            if self.len == 0 {
567                self.min_deadline.set(None);
568            } else if let Some(cur) = self.min_deadline.get()
569                && cancelled_deadline == cur
570            {
571                self.min_deadline.set(None);
572            }
573            // SAFETY: ptr was allocated from our slab via into_raw()
574            self.slab.free(unsafe { Slot::from_raw(ptr) });
575            value
576        } else {
577            // refs == 1 means the wheel already fired this (zombie).
578            // The fire path decremented 2→1 and left the entry for us to free.
579            debug_assert_eq!(refs, 1, "unexpected refcount {refs} in cancel");
580            // SAFETY: ptr was allocated from our slab via into_raw()
581            self.slab.free(unsafe { Slot::from_raw(ptr) });
582            None
583        }
584    }
585
586    /// Releases a timer handle without cancelling.
587    ///
588    /// - If the timer is still active: converts to fire-and-forget (refs 2→1).
589    ///   Timer stays in the wheel and will fire normally during poll.
590    /// - If the timer already fired (zombie): frees the slab entry (refs 1→0).
591    ///
592    /// Consumes the handle (no Drop runs).
593    pub fn free(&mut self, handle: TimerHandle<T>) {
594        let ptr = handle.ptr;
595        mem::forget(handle);
596
597        // SAFETY: handle guarantees ptr is valid
598        let entry = unsafe { entry_ref(ptr) };
599        let new_refs = entry.dec_refs();
600
601        if new_refs == 0 {
602            // Was a zombie (fired already, refs was 1) — free the entry
603            // SAFETY: ptr was allocated from our slab via into_raw()
604            self.slab.free(unsafe { Slot::from_raw(ptr) });
605        }
606        // new_refs == 1: timer is now fire-and-forget, stays in wheel
607    }
608
609    /// Reschedules an active timer to a new deadline.
610    ///
611    /// Moves the entry from its current slot to the correct slot for
612    /// `new_deadline` without extracting or reconstructing the value.
613    ///
614    /// # Panics
615    ///
616    /// Panics if the timer has already fired (zombie handle). Only active
617    /// timers (refs == 2) can be rescheduled.
618    ///
619    /// Consumes and returns a new handle (same entry, new position).
620    pub fn reschedule(&mut self, handle: TimerHandle<T>, new_deadline: Instant) -> TimerHandle<T> {
621        let ptr = handle.ptr;
622        mem::forget(handle);
623
624        // SAFETY: handle guarantees ptr is valid
625        let entry = unsafe { entry_ref(ptr) };
626        assert_eq!(entry.refs(), 2, "cannot reschedule a fired timer");
627
628        let old_deadline = entry.deadline_ticks();
629
630        // Remove from current position
631        self.remove_entry(ptr);
632
633        // Update deadline and reinsert
634        let new_ticks = self.instant_to_ticks(new_deadline);
635        entry.set_deadline_ticks(new_ticks);
636        self.insert_entry(ptr, new_ticks);
637
638        // Cache: if old deadline was the cached min and new is later,
639        // we may have lost the min. insert_entry already handles
640        // new < old (lowers cache), but can't detect old == cached
641        // when moving later.
642        if let Some(cur) = self.min_deadline.get()
643            && old_deadline == cur
644            && new_ticks > cur
645        {
646            self.min_deadline.set(None);
647        }
648
649        TimerHandle::new(ptr)
650    }
651
652    /// Collects all ready (due) timers into `buf`, **without rebalancing**, and
653    /// returns how many were collected.
654    ///
655    /// This is the minimal poll: it hands back the timers whose deadline has
656    /// passed and does no maintenance, so a not-yet-due entry stays in whatever
657    /// level it was placed in. Cheap on any single call — but if you *only* ever
658    /// call `poll`, entries are never moved to finer levels and a busy wheel
659    /// degrades to an O(population) scan per poll. For steady low-latency
660    /// polling, prefer [`poll_and_rebalance`](Self::poll_and_rebalance)
661    /// (collect + maintain in one pass).
662    pub fn poll(&mut self, now: Instant, buf: &mut Vec<T>) -> usize {
663        self.poll_with_limit(now, usize::MAX, buf)
664    }
665
666    /// Collects up to `limit` ready timers into `buf`, without rebalancing.
667    ///
668    /// Resumable: if the limit is hit, the next call continues where this one
669    /// left off (as long as `now` hasn't changed). See [`poll`](Self::poll) for
670    /// the rebalancing tradeoff.
671    ///
672    /// Returns the number collected in this call.
673    pub fn poll_with_limit(&mut self, now: Instant, limit: usize, buf: &mut Vec<T>) -> usize {
674        // Rebalance budget 0 → collect only, never move an entry to a finer level.
675        self.poll_inner(now, limit, 0, buf)
676    }
677
678    /// Collects all ready timers into `buf` **and rebalances** the wheel in the
679    /// same pass — the batteries-included poll. Returns how many were collected.
680    ///
681    /// Collecting is unbounded; **rebalancing** (moving not-yet-due entries to
682    /// finer levels so future polls stay cheap) is capped at
683    /// [`max_rebalances_per_poll`](WheelBuilder::max_rebalances_per_poll)
684    /// (default unbounded). The cap only smooths rebalance work across polls — it
685    /// never delays or drops a fire.
686    pub fn poll_and_rebalance(&mut self, now: Instant, buf: &mut Vec<T>) -> usize {
687        self.poll_and_rebalance_with_limit(now, usize::MAX, buf)
688    }
689
690    /// Collects up to `limit` ready timers into `buf` and rebalances the wheel.
691    ///
692    /// The collect phase is resumable like
693    /// [`poll_with_limit`](Self::poll_with_limit); rebalancing is capped by
694    /// [`max_rebalances_per_poll`](WheelBuilder::max_rebalances_per_poll).
695    /// Returns the number collected in this call.
696    pub fn poll_and_rebalance_with_limit(
697        &mut self,
698        now: Instant,
699        limit: usize,
700        buf: &mut Vec<T>,
701    ) -> usize {
702        self.poll_inner(now, limit, self.max_rebalances_per_poll, buf)
703    }
704
705    /// **Proactively** rebalances the wheel: moves up to `limit` not-yet-due
706    /// entries down to the finest level they now belong in, and returns how many
707    /// moved. Does **not** collect or fire anything.
708    ///
709    /// This is the maintenance half of [`poll_and_rebalance`](Self::poll_and_rebalance),
710    /// exposed on its own so you can move it *off* the collect hot path.
711    ///
712    /// # When to reach for this
713    ///
714    /// Use `poll` + `rebalance` (instead of `poll_and_rebalance`) when you have a
715    /// **large number of outstanding timers and want to cut the poll tail**. The
716    /// cost of a poll that has work is dominated by walking a fat coarse slot to
717    /// find the ready timers; by pulling entries down to exact fine-level slots
718    /// *before* their slot comes due, `rebalance` keeps that walk small, so the
719    /// collect stays cheap and flat. In practice this moves the poll-tail work
720    /// off the hot path onto `rebalance`, roughly quartering the collect's p99.9
721    /// on a busy wheel — at the price of doing the maintenance yourself, when it
722    /// suits you.
723    ///
724    /// # Recommended pattern: opportunistic + bounded
725    ///
726    /// Rebalance only when a poll came back empty — i.e. during genuine slack —
727    /// and bound each call so a high-frequency loop spreads the work instead of
728    /// stalling on one big sweep (`rebalance` is resumable; the next call
729    /// continues):
730    ///
731    /// ```ignore
732    /// let collected = wheel.poll(now, &mut buf);
733    /// if collected == 0 {
734    ///     // nothing to deliver — maintain during the slack, a bounded slice
735    ///     wheel.rebalance(now, REBALANCE_BUDGET);
736    /// }
737    /// ```
738    ///
739    /// This self-tunes to load: busy iterations pay only the cheap collect, and
740    /// the maintenance lands exactly on the idle ones. A fixed cadence (rebalance
741    /// every N iterations) also works — just avoid rebalancing on *every* poll,
742    /// which re-walks the look-ahead window and is pure overhead.
743    ///
744    /// # Safety of skipping it
745    ///
746    /// `rebalance` only visits slots whose earliest entry is already within a
747    /// finer level's reach, and moving nothing is always safe: an un-rebalanced
748    /// entry simply fires from wherever it is sitting when its time comes. If you
749    /// never call it, the wheel still works — it just degrades to walking coarse
750    /// slots on the collect path (which is what [`poll_and_rebalance`] does for
751    /// you in one call).
752    ///
753    /// [`poll_and_rebalance`]: Self::poll_and_rebalance
754    pub fn rebalance(&mut self, now: Instant, limit: usize) -> usize {
755        let now_ticks = self.instant_to_ticks(now);
756        self.current_ticks = now_ticks; // select_level / rebalance_level read this.
757
758        let mut moved = 0;
759        // Level 0 is already the finest — nothing to pull down from it. Ascending
760        // order; select_level places each entry at its correct level directly, so
761        // no entry is touched twice.
762        let mut mask = self.active_levels & !1;
763        while mask != 0 && moved < limit {
764            let lvl_idx = mask.trailing_zeros() as usize;
765            mask &= mask - 1;
766            // An entry at this level belongs at a finer one once it is within the
767            // next-finer level's range; a slot is worth visiting only if its
768            // earliest entry has reached that window.
769            let finer_reach = now_ticks.saturating_add(self.levels[lvl_idx - 1].range());
770            moved += self.rebalance_level(lvl_idx, finer_reach, limit - moved);
771        }
772
773        // Entries moved and per-slot minima changed; refresh the global-min cache.
774        self.min_deadline.set(self.walk_min_deadline());
775        moved
776    }
777
778    /// Shared poll body: collect ready timers (up to `limit`) and rebalance
779    /// not-yet-due entries to finer levels (up to `rebalance_budget`).
780    /// `rebalance_budget == 0` is collect-only.
781    fn poll_inner(
782        &mut self,
783        now: Instant,
784        limit: usize,
785        rebalance_budget: usize,
786        buf: &mut Vec<T>,
787    ) -> usize {
788        let now_ticks = self.instant_to_ticks(now);
789        self.current_ticks = now_ticks; // MUST precede the early return — select_level reads it.
790
791        // Fast path: if the cached global minimum is beyond now, nothing is due,
792        // so skip the level walk entirely — and with nothing due there is nothing
793        // to rebalance either. The cache may be stale-low (a lower bound), so this
794        // is conservative: it can miss the shortcut, never fire late.
795        if let Some(min) = self.min_deadline.get()
796            && min > now_ticks
797        {
798            return 0;
799        }
800
801        let mut fired = 0;
802        // Rebalance budget for this whole poll. Bounds only rebalancing, never
803        // collection — so the level loop below is NOT gated on it; due entries
804        // keep being collected after the budget is spent.
805        let mut rebalances = 0;
806        let mut mask = self.active_levels;
807
808        while mask != 0 && fired < limit {
809            let lvl_idx = mask.trailing_zeros() as usize;
810            mask &= mask - 1; // clear lowest set bit
811            fired += self.poll_level(
812                lvl_idx,
813                now_ticks,
814                limit - fired,
815                rebalance_budget,
816                &mut rebalances,
817                buf,
818            );
819        }
820
821        // Refresh the global-min cache from the (now-healed) per-slot minima.
822        // poll_level heals every slot it walks, so this recomputes an accurate
823        // minimum (> now when nothing is due). Without it the cache can stay
824        // stale-low (<= now) after a cancel or a no-fire poll, permanently
825        // defeating the early-exit above and making next_deadline() report a
826        // past instant. Cheap now — one compare per active slot. (If a limit
827        // truncated the poll, a walked-but-not-drained slot stays stale-low, so
828        // the cache stays <= now and the next poll correctly re-enters.)
829        self.min_deadline.set(self.walk_min_deadline());
830
831        fired
832    }
833
834    /// Returns an `Instant` no later than when the next timer fires, or `None`
835    /// if the wheel is empty.
836    ///
837    /// **Lower bound, not exact.** The per-slot minima are stale-low after a
838    /// cancel/fire (they are not recomputed on removal — see the design), so the
839    /// returned instant may be *earlier* than the true next deadline, never
840    /// later. It is safe as a sleep/wake bound: you may wake early and find
841    /// nothing due, but you can never miss a timer.
842    ///
843    /// O(1) on cache hit; otherwise ~one compare per active slot to recompute.
844    pub fn next_deadline(&self) -> Option<Instant> {
845        if let Some(ticks) = self.min_deadline.get() {
846            return Some(self.ticks_to_instant(ticks));
847        }
848        if self.len == 0 {
849            return None;
850        }
851        let min_ticks = self.walk_min_deadline();
852        self.min_deadline.set(min_ticks);
853        min_ticks.map(|t| self.ticks_to_instant(t))
854    }
855
856    /// Recomputes the wheel's minimum deadline from the per-slot minima —
857    /// ~one compare per active slot, not one per entry.
858    ///
859    /// The per-slot minima may be stale-low (see `WheelSlot::min_deadline`), so
860    /// the result is a **lower bound**: it may be earlier than the true minimum,
861    /// never later. Callers (`next_deadline`, the poll early-exit) treat it
862    /// conservatively — an under-estimate only ever costs extra work.
863    #[cold]
864    fn walk_min_deadline(&self) -> Option<u64> {
865        // `any` (not `min_ticks != u64::MAX`) is the emptiness test: a real
866        // far-future deadline can saturate to exactly u64::MAX in
867        // `instant_to_ticks`, so the sentinel value is a legitimate minimum.
868        let mut min_ticks = u64::MAX;
869        let mut any = false;
870        let mut lvl_mask = self.active_levels;
871        while lvl_mask != 0 {
872            let lvl_idx = lvl_mask.trailing_zeros() as usize;
873            lvl_mask &= lvl_mask - 1;
874            let level = &self.levels[lvl_idx];
875            let mut slot_mask = level.active_slots();
876            while slot_mask != 0 {
877                let slot_idx = slot_mask.trailing_zeros() as usize;
878                slot_mask &= slot_mask - 1;
879                any = true;
880                min_ticks = min_ticks.min(level.slot(slot_idx).min_deadline());
881            }
882        }
883        any.then_some(min_ticks)
884    }
885
886    /// Test-only **exact** minimum deadline via a full entry walk (ignoring the
887    /// per-slot minima) — the ground truth the lower-bound [`next_deadline`] is
888    /// checked against.
889    #[cfg(test)]
890    fn next_deadline_uncached(&self) -> Option<Instant> {
891        let mut min_ticks: Option<u64> = None;
892        let mut lvl_mask = self.active_levels;
893        while lvl_mask != 0 {
894            let lvl_idx = lvl_mask.trailing_zeros() as usize;
895            lvl_mask &= lvl_mask - 1;
896            let level = &self.levels[lvl_idx];
897            let mut slot_mask = level.active_slots();
898            while slot_mask != 0 {
899                let slot_idx = slot_mask.trailing_zeros() as usize;
900                slot_mask &= slot_mask - 1;
901                let slot = level.slot(slot_idx);
902                let mut entry_ptr = slot.entry_head();
903                while !entry_ptr.is_null() {
904                    // SAFETY: entry_ptr is in this slot's DLL
905                    let entry = unsafe { entry_ref(entry_ptr) };
906                    let dt = entry.deadline_ticks();
907                    min_ticks = Some(min_ticks.map_or(dt, |c| c.min(dt)));
908                    entry_ptr = entry.next();
909                }
910            }
911        }
912        min_ticks.map(|t| self.ticks_to_instant(t))
913    }
914
915    /// Returns the number of timers currently in the wheel.
916    #[inline]
917    pub fn len(&self) -> usize {
918        self.len
919    }
920
921    /// Returns true if the wheel contains no timers.
922    #[inline]
923    pub fn is_empty(&self) -> bool {
924        self.len == 0
925    }
926
927    // =========================================================================
928    // Internal: tick conversion
929    // =========================================================================
930
931    #[inline]
932    fn instant_to_ticks(&self, instant: Instant) -> u64 {
933        let dur = instant.saturating_duration_since(self.epoch);
934        let nanos = dur.as_nanos().min(u64::MAX as u128) as u64;
935        ((nanos as u128 * self.inv_tick_ns) >> 64) as u64
936    }
937
938    #[inline]
939    fn ticks_to_instant(&self, ticks: u64) -> Instant {
940        self.epoch + Duration::from_nanos(ticks.saturating_mul(self.tick_ns))
941    }
942
943    // =========================================================================
944    // Internal: level selection
945    // =========================================================================
946
947    /// Selects the appropriate level for a deadline.
948    ///
949    /// Walks levels from finest to coarsest, picking the first level whose
950    /// range can represent the delta. Clamps to the highest level if the
951    /// deadline exceeds the wheel's total range.
952    #[inline]
953    fn select_level(&self, deadline_ticks: u64) -> usize {
954        let delta = deadline_ticks.saturating_sub(self.current_ticks);
955
956        for (i, level) in self.levels.iter().enumerate() {
957            if delta < level.range() {
958                return i;
959            }
960        }
961
962        // Beyond max range — clamp to highest level
963        self.num_levels - 1
964    }
965
966    // =========================================================================
967    // Internal: entry insertion into a level's slot
968    // =========================================================================
969
970    /// Inserts an entry into the appropriate level and slot.
971    ///
972    /// Records the level and slot index on the entry so `remove_entry` can
973    /// find it without recomputing (which would be unsound after time advances).
974    #[inline]
975    #[allow(clippy::needless_pass_by_ref_mut)]
976    fn insert_entry(&mut self, entry_ptr: EntryPtr<T>, deadline_ticks: u64) {
977        let lvl_idx = self.select_level(deadline_ticks);
978        let slot_idx = self.levels[lvl_idx].slot_index(deadline_ticks);
979
980        // Record location on the entry for O(1) lookup at cancel time.
981        // SAFETY: entry_ptr is valid (just allocated)
982        let entry = unsafe { entry_ref(entry_ptr) };
983        entry.set_location(lvl_idx as u8, slot_idx as u16);
984
985        // SAFETY: entry_ptr is valid (just allocated), not in any DLL yet
986        unsafe { self.levels[lvl_idx].slot(slot_idx).push_entry(entry_ptr) };
987
988        // Per-slot min: this entry may lower the slot's minimum. (Maintained here,
989        // not in push_entry, so TimeoutQueue's shared slot pays nothing.)
990        {
991            let slot = self.levels[lvl_idx].slot(slot_idx);
992            slot.set_min_deadline(slot.min_deadline().min(deadline_ticks));
993        }
994
995        // Activate slot and level (idempotent — OR is a no-op if already set)
996        self.levels[lvl_idx].activate_slot(slot_idx);
997        self.active_levels |= 1 << lvl_idx;
998
999        // Cache: new entry may lower the minimum.
1000        // len is incremented by the caller AFTER insert_entry returns,
1001        // so self.len == 0 means the wheel was empty before this insert.
1002        match self.min_deadline.get() {
1003            None if self.len == 0 => {
1004                self.min_deadline.set(Some(deadline_ticks));
1005            }
1006            Some(cur) if deadline_ticks < cur => {
1007                self.min_deadline.set(Some(deadline_ticks));
1008            }
1009            _ => {}
1010        }
1011    }
1012
1013    /// Removes an entry from its level's slot DLL.
1014    ///
1015    /// Reads the stored level and slot index from the entry (set at insertion
1016    /// time). Does NOT recompute from delta — that would be unsound after
1017    /// `current_ticks` advances.
1018    #[inline]
1019    #[allow(clippy::needless_pass_by_ref_mut)]
1020    fn remove_entry(&mut self, entry_ptr: EntryPtr<T>) {
1021        // SAFETY: entry_ptr is valid (caller guarantee)
1022        let entry = unsafe { entry_ref(entry_ptr) };
1023
1024        let lvl_idx = entry.level() as usize;
1025        let slot_idx = entry.slot_idx() as usize;
1026
1027        // SAFETY: entry_ptr is in this slot's DLL (invariant from insert_entry)
1028        unsafe { self.levels[lvl_idx].slot(slot_idx).remove_entry(entry_ptr) };
1029
1030        if self.levels[lvl_idx].slot(slot_idx).is_empty() {
1031            // Drained: reset the slot min so an empty slot never reports a
1032            // stale-low deadline. A non-empty slot is left stale-low on purpose
1033            // (safe — see WheelSlot::min_deadline).
1034            self.levels[lvl_idx]
1035                .slot(slot_idx)
1036                .set_min_deadline(u64::MAX);
1037            self.levels[lvl_idx].deactivate_slot(slot_idx);
1038            if !self.levels[lvl_idx].is_active() {
1039                self.active_levels &= !(1 << lvl_idx);
1040            }
1041        }
1042    }
1043
1044    // =========================================================================
1045    // Internal: fire an entry
1046    // =========================================================================
1047
1048    /// Fires a single entry: extracts value, decrements refcount, possibly frees.
1049    ///
1050    /// Returns `Some(T)` if the value was still present (not already cancelled).
1051    #[inline]
1052    fn fire_entry(&mut self, entry_ptr: EntryPtr<T>) -> Option<T> {
1053        // SAFETY: entry_ptr is valid (we're walking the DLL)
1054        let entry = unsafe { entry_ref(entry_ptr) };
1055
1056        let fired_deadline = entry.deadline_ticks();
1057
1058        // Extract value
1059        // SAFETY: single-threaded
1060        let value = unsafe { entry.take_value() };
1061
1062        let new_refs = entry.dec_refs();
1063        if new_refs == 0 {
1064            // Fire-and-forget (was refs=1) — free the slab entry immediately
1065            // SAFETY: entry_ptr was allocated from our slab via into_raw()
1066            self.slab.free(unsafe { Slot::from_raw(entry_ptr) });
1067        }
1068        // new_refs == 1: handle exists (was refs=2), entry becomes zombie.
1069        // Handle holder will free via cancel() or free().
1070
1071        self.len -= 1;
1072
1073        if self.len == 0 {
1074            self.min_deadline.set(None);
1075        } else if let Some(cur) = self.min_deadline.get()
1076            && fired_deadline == cur
1077        {
1078            self.min_deadline.set(None);
1079        }
1080
1081        value
1082    }
1083
1084    // =========================================================================
1085    // Internal: poll a single level
1086    // =========================================================================
1087
1088    /// Polls a single level for expired entries up to `limit`.
1089    ///
1090    fn poll_level(
1091        &mut self,
1092        lvl_idx: usize,
1093        now_ticks: u64,
1094        limit: usize,
1095        rebalance_budget: usize,
1096        rebalances: &mut usize,
1097        buf: &mut Vec<T>,
1098    ) -> usize {
1099        let mut fired = 0;
1100        let mut mask = self.levels[lvl_idx].active_slots();
1101
1102        while mask != 0 && fired < limit {
1103            let slot_idx = mask.trailing_zeros() as usize;
1104            mask &= mask - 1;
1105
1106            let slot_ptr = self.levels[lvl_idx].slot(slot_idx) as *const crate::level::WheelSlot<T>;
1107            // SAFETY: slot_ptr points into self.levels[lvl_idx].slots
1108            // (Box<[WheelSlot<T>]>), a stable heap allocation never reallocated
1109            // during poll. fire_entry and insert_entry mutate self.slab, self.len,
1110            // self.active_levels, self.min_deadline, and *other* levels' slots —
1111            // rebalancing relocates only to strictly finer levels (< lvl_idx), never
1112            // this slot — so this slot's backing memory is untouched and `slot`
1113            // stays valid across the loop.
1114            let slot = unsafe { &*slot_ptr };
1115
1116            // Slot-skip: if the slot's minimum deadline is beyond now, nothing
1117            // in it is due — do not touch a single entry. Stale-low is safe: it
1118            // only costs an unnecessary walk (handled below), never a skip.
1119            if slot.min_deadline() > now_ticks {
1120                continue;
1121            }
1122
1123            let mut new_min = u64::MAX; // min over entries that stay in this slot
1124            let mut entry_ptr = slot.entry_head();
1125
1126            while !entry_ptr.is_null() && fired < limit {
1127                // SAFETY: entry_ptr is in this slot's DLL
1128                let entry = unsafe { entry_ref(entry_ptr) };
1129                let next_entry = entry.next(); // captured before any unlink below
1130                let dt = entry.deadline_ticks();
1131
1132                if dt <= now_ticks {
1133                    // Due — fire it.
1134                    // SAFETY: entry_ptr is in this slot's DLL (from entry_head,
1135                    // walked via next pointers within the same slot).
1136                    unsafe { slot.remove_entry(entry_ptr) };
1137                    if let Some(value) = self.fire_entry(entry_ptr) {
1138                        buf.push(value);
1139                    }
1140                    fired += 1;
1141                } else if *rebalances < rebalance_budget && self.select_level(dt) < lvl_idx {
1142                    // Not due, it now belongs at a strictly finer level, and we are
1143                    // still under the per-poll rebalance budget: relocate it down
1144                    // instead of re-walking it every poll until this slot's span
1145                    // passes. The target (< lvl_idx) is never this slot, so the walk
1146                    // terminates and the entry is not re-processed this poll (finer
1147                    // levels are polled first). current_ticks == now_ticks (set in
1148                    // poll_inner before this loop), so insert_entry selects the
1149                    // correct finer level.
1150                    // SAFETY: entry_ptr is in this slot's DLL.
1151                    unsafe { slot.remove_entry(entry_ptr) };
1152                    self.insert_entry(entry_ptr, dt);
1153                    *rebalances += 1;
1154                } else {
1155                    // Not due, and left in place — either it still belongs at this
1156                    // level (a far entry sharing the slot via the modular index:
1157                    // deadlines a full level-range apart map to the same slot), or
1158                    // the per-poll rebalance budget is spent. Either way it stays put
1159                    // and fires (or rebalances) on a later poll from wherever it sits;
1160                    // track it as the slot's surviving minimum. A spent budget can
1161                    // never make a timer fire late — poll still fires it the moment
1162                    // dt <= now, regardless of which level it is in.
1163                    new_min = new_min.min(dt);
1164                }
1165
1166                entry_ptr = next_entry;
1167            }
1168
1169            // If we walked the whole slot, its minimum is exactly the min over the
1170            // entries that stayed (u64::MAX — the empty sentinel — when the slot
1171            // drained via fires + rebalances). A limit-truncated walk (entry_ptr
1172            // non-null) leaves the min stale-low; the next poll re-walks and heals.
1173            if entry_ptr.is_null() {
1174                slot.set_min_deadline(new_min);
1175            }
1176
1177            if slot.is_empty() {
1178                self.levels[lvl_idx].deactivate_slot(slot_idx);
1179            }
1180        }
1181
1182        // Deactivate level if all slots drained
1183        if !self.levels[lvl_idx].is_active() {
1184            self.active_levels &= !(1 << lvl_idx);
1185        }
1186
1187        fired
1188    }
1189
1190    /// Proactively pulls not-yet-due entries at `lvl_idx` down to a finer level.
1191    /// Visits only active slots whose earliest entry has reached `finer_reach`
1192    /// (is within the next-finer level's range) and relocates each entry that now
1193    /// belongs at a strictly finer level, up to `limit`. Returns how many moved.
1194    /// Fires nothing.
1195    fn rebalance_level(&mut self, lvl_idx: usize, finer_reach: u64, limit: usize) -> usize {
1196        let mut moved = 0;
1197        let mut mask = self.levels[lvl_idx].active_slots();
1198
1199        while mask != 0 && moved < limit {
1200            let slot_idx = mask.trailing_zeros() as usize;
1201            mask &= mask - 1;
1202
1203            let slot_ptr = self.levels[lvl_idx].slot(slot_idx) as *const crate::level::WheelSlot<T>;
1204            // SAFETY: same argument as poll_level — slot_ptr points into the
1205            // stable Box<[WheelSlot<T>]>; insert_entry only ever relocates to a
1206            // strictly finer level (< lvl_idx), never this slot, so `slot` stays
1207            // valid across the loop.
1208            let slot = unsafe { &*slot_ptr };
1209
1210            // Nothing to pull down yet if the earliest entry hasn't reached the
1211            // finer level's window.
1212            if slot.min_deadline() >= finer_reach {
1213                continue;
1214            }
1215
1216            let mut new_min = u64::MAX;
1217            let mut entry_ptr = slot.entry_head();
1218
1219            while !entry_ptr.is_null() && moved < limit {
1220                // SAFETY: entry_ptr is in this slot's DLL.
1221                let entry = unsafe { entry_ref(entry_ptr) };
1222                let next_entry = entry.next();
1223                let dt = entry.deadline_ticks();
1224
1225                if self.select_level(dt) < lvl_idx {
1226                    // SAFETY: entry_ptr is in this slot's DLL.
1227                    unsafe { slot.remove_entry(entry_ptr) };
1228                    self.insert_entry(entry_ptr, dt);
1229                    moved += 1;
1230                } else {
1231                    // Still belongs at this level (modular-index neighbor a full
1232                    // range away, or budget-truncated). Leave it; track its min.
1233                    new_min = new_min.min(dt);
1234                }
1235
1236                entry_ptr = next_entry;
1237            }
1238
1239            // Fully-walked slot: its min is exactly the min over entries that
1240            // stayed. A limit-truncated walk (entry_ptr non-null) leaves it
1241            // stale-low; the next rebalance/poll re-walks and heals it.
1242            if entry_ptr.is_null() {
1243                slot.set_min_deadline(new_min);
1244            }
1245
1246            if slot.is_empty() {
1247                self.levels[lvl_idx].deactivate_slot(slot_idx);
1248            }
1249        }
1250
1251        moved
1252    }
1253}
1254
1255// =============================================================================
1256// Drop
1257// =============================================================================
1258
1259impl<T: 'static, S: SlabStore<Item = WheelEntry<T>>> Drop for TimerWheel<T, S> {
1260    fn drop(&mut self) {
1261        // Walk active levels and slots via bitmasks, free every entry.
1262        let mut lvl_mask = self.active_levels;
1263        while lvl_mask != 0 {
1264            let lvl_idx = lvl_mask.trailing_zeros() as usize;
1265            lvl_mask &= lvl_mask - 1;
1266
1267            let level = &self.levels[lvl_idx];
1268            let mut slot_mask = level.active_slots();
1269            while slot_mask != 0 {
1270                let slot_idx = slot_mask.trailing_zeros() as usize;
1271                slot_mask &= slot_mask - 1;
1272
1273                let slot = level.slot(slot_idx);
1274                let mut entry_ptr = slot.entry_head();
1275                while !entry_ptr.is_null() {
1276                    // SAFETY: entry_ptr is in this slot's DLL
1277                    let entry = unsafe { entry_ref(entry_ptr) };
1278                    let next_entry = entry.next();
1279
1280                    // SAFETY: entry_ptr was allocated from our slab via into_raw()
1281                    self.slab.free(unsafe { Slot::from_raw(entry_ptr) });
1282
1283                    entry_ptr = next_entry;
1284                }
1285            }
1286        }
1287    }
1288}
1289
1290// =============================================================================
1291// Tests
1292// =============================================================================
1293
1294#[cfg(test)]
1295mod tests {
1296    use super::*;
1297    use std::time::{Duration, Instant};
1298
1299    fn ms(millis: u64) -> Duration {
1300        Duration::from_millis(millis)
1301    }
1302
1303    // -------------------------------------------------------------------------
1304    // Thread safety
1305    // -------------------------------------------------------------------------
1306
1307    fn assert_send<T: Send>() {}
1308
1309    #[test]
1310    fn wheel_is_send() {
1311        assert_send::<Wheel<u64>>();
1312        assert_send::<BoundedWheel<u64>>();
1313    }
1314
1315    // -------------------------------------------------------------------------
1316    // Construction
1317    // -------------------------------------------------------------------------
1318
1319    #[test]
1320    fn default_config() {
1321        let now = Instant::now();
1322        let wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1323        assert!(wheel.is_empty());
1324        assert_eq!(wheel.len(), 0);
1325    }
1326
1327    #[test]
1328    fn bounded_construction() {
1329        let now = Instant::now();
1330        let wheel: BoundedWheel<u64> = BoundedWheel::bounded(128, now);
1331        assert!(wheel.is_empty());
1332    }
1333
1334    #[test]
1335    fn invalid_config_non_power_of_two() {
1336        let now = Instant::now();
1337        let result = WheelBuilder::default()
1338            .slots_per_level(65)
1339            .unbounded(1024)
1340            .build::<u64>(now);
1341        assert_invalid(&result, "power of 2");
1342    }
1343
1344    // -------------------------------------------------------------------------
1345    // Schedule + Cancel
1346    // -------------------------------------------------------------------------
1347
1348    #[test]
1349    fn schedule_and_cancel() {
1350        let now = Instant::now();
1351        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1352
1353        let h = wheel.schedule(now + ms(50), 42);
1354        assert_eq!(wheel.len(), 1);
1355
1356        let val = wheel.cancel(h);
1357        assert_eq!(val, Some(42));
1358        assert_eq!(wheel.len(), 0);
1359    }
1360
1361    #[test]
1362    fn schedule_forget_fires() {
1363        let now = Instant::now();
1364        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1365
1366        wheel.schedule_forget(now + ms(10), 99);
1367        assert_eq!(wheel.len(), 1);
1368
1369        let mut buf = Vec::new();
1370        let fired = wheel.poll(now + ms(20), &mut buf);
1371        assert_eq!(fired, 1);
1372        assert_eq!(buf, vec![99]);
1373        assert_eq!(wheel.len(), 0);
1374    }
1375
1376    #[test]
1377    fn cancel_after_fire_returns_none() {
1378        let now = Instant::now();
1379        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1380
1381        let h = wheel.schedule(now + ms(10), 42);
1382
1383        let mut buf = Vec::new();
1384        wheel.poll(now + ms(20), &mut buf);
1385        assert_eq!(buf, vec![42]);
1386
1387        // Handle is now a zombie
1388        let val = wheel.cancel(h);
1389        assert_eq!(val, None);
1390    }
1391
1392    #[test]
1393    fn free_active_timer_becomes_fire_and_forget() {
1394        let now = Instant::now();
1395        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1396
1397        let h = wheel.schedule(now + ms(10), 42);
1398        wheel.free(h); // releases handle, timer stays
1399        assert_eq!(wheel.len(), 1);
1400
1401        let mut buf = Vec::new();
1402        wheel.poll(now + ms(20), &mut buf);
1403        assert_eq!(buf, vec![42]);
1404        assert_eq!(wheel.len(), 0);
1405    }
1406
1407    #[test]
1408    fn free_zombie_handle() {
1409        let now = Instant::now();
1410        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1411
1412        let h = wheel.schedule(now + ms(10), 42);
1413
1414        let mut buf = Vec::new();
1415        wheel.poll(now + ms(20), &mut buf);
1416
1417        // Handle is zombie, free should clean up
1418        wheel.free(h);
1419    }
1420
1421    // -------------------------------------------------------------------------
1422    // Bounded wheel
1423    // -------------------------------------------------------------------------
1424
1425    #[test]
1426    fn bounded_full() {
1427        let now = Instant::now();
1428        let mut wheel: BoundedWheel<u64> = BoundedWheel::bounded(2, now);
1429
1430        let h1 = wheel.try_schedule(now + ms(10), 1).unwrap();
1431        let h2 = wheel.try_schedule(now + ms(20), 2).unwrap();
1432
1433        let err = wheel.try_schedule(now + ms(30), 3);
1434        assert!(err.is_err());
1435        let recovered = err.unwrap_err().into_inner();
1436        assert_eq!(recovered, 3);
1437
1438        // Cancel one, should have room
1439        wheel.cancel(h1);
1440        let h3 = wheel.try_schedule(now + ms(30), 3).unwrap();
1441
1442        // Clean up handles
1443        wheel.free(h2);
1444        wheel.free(h3);
1445    }
1446
1447    #[test]
1448    fn bounded_schedule_forget_full() {
1449        let now = Instant::now();
1450        let mut wheel: BoundedWheel<u64> = BoundedWheel::bounded(1, now);
1451
1452        wheel.try_schedule_forget(now + ms(10), 1).unwrap();
1453        let err = wheel.try_schedule_forget(now + ms(20), 2);
1454        assert!(err.is_err());
1455    }
1456
1457    // -------------------------------------------------------------------------
1458    // Poll
1459    // -------------------------------------------------------------------------
1460
1461    #[test]
1462    fn poll_respects_deadline() {
1463        let now = Instant::now();
1464        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1465
1466        wheel.schedule_forget(now + ms(10), 1);
1467        wheel.schedule_forget(now + ms(50), 2);
1468        wheel.schedule_forget(now + ms(100), 3);
1469
1470        let mut buf = Vec::new();
1471
1472        // At 20ms: only timer 1 should fire
1473        let fired = wheel.poll(now + ms(20), &mut buf);
1474        assert_eq!(fired, 1);
1475        assert_eq!(buf, vec![1]);
1476        assert_eq!(wheel.len(), 2);
1477
1478        // At 60ms: timer 2 fires
1479        buf.clear();
1480        let fired = wheel.poll(now + ms(60), &mut buf);
1481        assert_eq!(fired, 1);
1482        assert_eq!(buf, vec![2]);
1483
1484        // At 200ms: timer 3 fires
1485        buf.clear();
1486        let fired = wheel.poll(now + ms(200), &mut buf);
1487        assert_eq!(fired, 1);
1488        assert_eq!(buf, vec![3]);
1489
1490        assert!(wheel.is_empty());
1491    }
1492
1493    #[test]
1494    fn poll_with_limit() {
1495        let now = Instant::now();
1496        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1497
1498        for i in 0..10 {
1499            wheel.schedule_forget(now + ms(1), i);
1500        }
1501
1502        let mut buf = Vec::new();
1503
1504        // Fire 3 at a time
1505        let fired = wheel.poll_with_limit(now + ms(5), 3, &mut buf);
1506        assert_eq!(fired, 3);
1507        assert_eq!(wheel.len(), 7);
1508
1509        let fired = wheel.poll_with_limit(now + ms(5), 3, &mut buf);
1510        assert_eq!(fired, 3);
1511        assert_eq!(wheel.len(), 4);
1512
1513        // Fire remaining
1514        let fired = wheel.poll(now + ms(5), &mut buf);
1515        assert_eq!(fired, 4);
1516        assert!(wheel.is_empty());
1517        assert_eq!(buf.len(), 10);
1518    }
1519
1520    // -------------------------------------------------------------------------
1521    // Multi-level
1522    // -------------------------------------------------------------------------
1523
1524    #[test]
1525    fn timers_across_levels() {
1526        let now = Instant::now();
1527        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1528
1529        // Level 0: 0-63ms
1530        wheel.schedule_forget(now + ms(5), 0);
1531        // Level 1: 64-511ms
1532        wheel.schedule_forget(now + ms(200), 1);
1533        // Level 2: 512-4095ms
1534        wheel.schedule_forget(now + ms(1000), 2);
1535
1536        let mut buf = Vec::new();
1537
1538        wheel.poll(now + ms(10), &mut buf);
1539        assert_eq!(buf, vec![0]);
1540
1541        buf.clear();
1542        wheel.poll(now + ms(250), &mut buf);
1543        assert_eq!(buf, vec![1]);
1544
1545        buf.clear();
1546        wheel.poll(now + ms(1500), &mut buf);
1547        assert_eq!(buf, vec![2]);
1548
1549        assert!(wheel.is_empty());
1550    }
1551
1552    // -------------------------------------------------------------------------
1553    // next_deadline
1554    // -------------------------------------------------------------------------
1555
1556    #[test]
1557    fn next_deadline_empty() {
1558        let now = Instant::now();
1559        let wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1560        assert!(wheel.next_deadline().is_none());
1561    }
1562
1563    #[test]
1564    fn next_deadline_returns_earliest() {
1565        let now = Instant::now();
1566        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1567
1568        wheel.schedule_forget(now + ms(100), 1);
1569        wheel.schedule_forget(now + ms(50), 2);
1570        wheel.schedule_forget(now + ms(200), 3);
1571
1572        let next = wheel.next_deadline().unwrap();
1573        // Should be close to now + 50ms (within tick granularity)
1574        let delta = next.duration_since(now);
1575        assert!(delta >= ms(49) && delta <= ms(51));
1576    }
1577
1578    #[test]
1579    fn next_deadline_cache_invalidates_on_cancel() {
1580        let now = Instant::now();
1581        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1582
1583        let h1 = wheel.schedule(now + ms(50), 1);
1584        wheel.schedule_forget(now + ms(100), 2);
1585        wheel.schedule_forget(now + ms(200), 3);
1586
1587        // Cached at 50ms
1588        let d1 = wheel.next_deadline().unwrap();
1589        assert!(d1.duration_since(now) >= ms(49) && d1.duration_since(now) <= ms(51));
1590
1591        // Cancel the earliest — cache invalidated, should return ~100ms
1592        wheel.cancel(h1);
1593        let d2 = wheel.next_deadline().unwrap();
1594        assert!(d2.duration_since(now) >= ms(99) && d2.duration_since(now) <= ms(101));
1595    }
1596
1597    #[test]
1598    fn next_deadline_cache_invalidates_on_fire() {
1599        let now = Instant::now();
1600        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1601
1602        wheel.schedule_forget(now + ms(50), 1);
1603        wheel.schedule_forget(now + ms(100), 2);
1604        wheel.schedule_forget(now + ms(200), 3);
1605
1606        // Prime cache
1607        let _ = wheel.next_deadline();
1608
1609        // Fire earliest via poll
1610        let mut buf = Vec::new();
1611        wheel.poll(now + ms(60), &mut buf);
1612        assert_eq!(buf, vec![1]);
1613
1614        // Cache invalidated, should return ~100ms
1615        let d = wheel.next_deadline().unwrap();
1616        assert!(d.duration_since(now) >= ms(99) && d.duration_since(now) <= ms(101));
1617    }
1618
1619    #[test]
1620    fn next_deadline_cache_updates_on_insert() {
1621        let now = Instant::now();
1622        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1623
1624        wheel.schedule_forget(now + ms(100), 1);
1625        let d1 = wheel.next_deadline().unwrap();
1626        assert!(d1.duration_since(now) >= ms(99) && d1.duration_since(now) <= ms(101));
1627
1628        // Insert an earlier timer — cache should update
1629        wheel.schedule_forget(now + ms(30), 2);
1630        let d2 = wheel.next_deadline().unwrap();
1631        assert!(d2.duration_since(now) >= ms(29) && d2.duration_since(now) <= ms(31));
1632    }
1633
1634    #[test]
1635    fn next_deadline_after_reschedule_later() {
1636        let now = Instant::now();
1637        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1638
1639        let h_a = wheel.schedule(now + ms(50), 1);
1640        wheel.schedule_forget(now + ms(100), 2);
1641
1642        let d1 = wheel.next_deadline().unwrap();
1643        assert!(d1.duration_since(now) >= ms(49) && d1.duration_since(now) <= ms(51));
1644
1645        // Reschedule A later — B becomes earliest
1646        let h_a = wheel.reschedule(h_a, now + ms(200));
1647        let d2 = wheel.next_deadline().unwrap();
1648        assert!(d2.duration_since(now) >= ms(99) && d2.duration_since(now) <= ms(101));
1649        mem::forget(h_a);
1650    }
1651
1652    #[test]
1653    fn next_deadline_after_reschedule_earlier() {
1654        let now = Instant::now();
1655        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1656
1657        let h_a = wheel.schedule(now + ms(100), 1);
1658        wheel.schedule_forget(now + ms(50), 2);
1659
1660        let d1 = wheel.next_deadline().unwrap();
1661        assert!(d1.duration_since(now) >= ms(49) && d1.duration_since(now) <= ms(51));
1662
1663        // Reschedule A earlier — A becomes new earliest
1664        let h_a = wheel.reschedule(h_a, now + ms(25));
1665        let d2 = wheel.next_deadline().unwrap();
1666        assert!(d2.duration_since(now) >= ms(24) && d2.duration_since(now) <= ms(26));
1667        mem::forget(h_a);
1668    }
1669
1670    #[test]
1671    fn next_deadline_repeated_calls_stable() {
1672        let now = Instant::now();
1673        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1674
1675        wheel.schedule_forget(now + ms(50), 1);
1676        wheel.schedule_forget(now + ms(100), 2);
1677        wheel.schedule_forget(now + ms(200), 3);
1678
1679        let d1 = wheel.next_deadline();
1680        let d2 = wheel.next_deadline();
1681        let d3 = wheel.next_deadline();
1682        assert_eq!(d1, d2);
1683        assert_eq!(d2, d3);
1684    }
1685
1686    // -------------------------------------------------------------------------
1687    // Reciprocal precision
1688    // -------------------------------------------------------------------------
1689
1690    #[test]
1691    fn reciprocal_instant_to_ticks_precision() {
1692        // Reciprocal multiply is at most 1 tick low vs true integer division.
1693        // Verify across multiple tick_ns values and multiples.
1694        let now = Instant::now();
1695
1696        for &tick_ns in &[1_000_000u64, 1_000, 100, 999_999, 7_500_000] {
1697            let wheel: Wheel<u64> = WheelBuilder::default()
1698                .tick_duration(Duration::from_nanos(tick_ns))
1699                .unbounded(64)
1700                .build(now)
1701                .unwrap();
1702
1703            for n in 0..500u64 {
1704                let nanos = n * tick_ns;
1705                let instant = now + Duration::from_nanos(nanos);
1706                let got = wheel.instant_to_ticks(instant);
1707                let exact = nanos / tick_ns;
1708                let diff = exact as i64 - got as i64;
1709                assert!(
1710                    diff >= 0 && diff <= 1,
1711                    "tick_ns={tick_ns}, n={n}: exact={exact}, got={got}, diff={diff}",
1712                );
1713            }
1714        }
1715    }
1716
1717    // -------------------------------------------------------------------------
1718    // Deadline in the past
1719    // -------------------------------------------------------------------------
1720
1721    #[test]
1722    fn deadline_in_the_past_fires_immediately() {
1723        let now = Instant::now();
1724        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1725
1726        // Schedule at epoch (which is "now" at construction)
1727        wheel.schedule_forget(now, 42);
1728
1729        let mut buf = Vec::new();
1730        let fired = wheel.poll(now + ms(1), &mut buf);
1731        assert_eq!(fired, 1);
1732        assert_eq!(buf, vec![42]);
1733    }
1734
1735    // -------------------------------------------------------------------------
1736    // Deadline beyond max range — clamped
1737    // -------------------------------------------------------------------------
1738
1739    #[test]
1740    fn deadline_beyond_max_range_clamped() {
1741        let now = Instant::now();
1742        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1743
1744        // Way in the future — should clamp to highest level
1745        let h = wheel.schedule(now + Duration::from_secs(100_000), 99);
1746        assert_eq!(wheel.len(), 1);
1747
1748        // Won't fire at any reasonable time but will fire when enough ticks pass
1749        let mut buf = Vec::new();
1750        wheel.poll(now + Duration::from_secs(100_001), &mut buf);
1751        assert_eq!(buf, vec![99]);
1752
1753        // Note: handle was already consumed by the poll (fire-and-forget path won't
1754        // apply since refs=2). Actually the handle still exists. Let's clean up.
1755        // The timer already fired, so cancel returns None.
1756        // Actually buf got the value, which means it fired. But handle still needs cleanup.
1757        // We already pushed the value so we need to handle the zombie.
1758        // Wait — we used schedule (refs=2), poll fired it (refs 2→1 zombie), handle `h` exists.
1759        // Actually we consumed it with the poll — no we didn't, we still have `h`.
1760
1761        // h is a zombie handle now
1762        let val = wheel.cancel(h);
1763        assert_eq!(val, None);
1764    }
1765
1766    // -------------------------------------------------------------------------
1767    // Drop
1768    // -------------------------------------------------------------------------
1769
1770    #[test]
1771    fn drop_cleans_up_active_entries() {
1772        let now = Instant::now();
1773        let mut wheel: Wheel<String> = Wheel::unbounded(1024, now);
1774
1775        for i in 0..100 {
1776            wheel.schedule_forget(now + ms(i * 10), format!("timer-{i}"));
1777        }
1778
1779        assert_eq!(wheel.len(), 100);
1780        // Drop should free all entries without leaking
1781        drop(wheel);
1782    }
1783
1784    #[test]
1785    fn drop_with_outstanding_handles() {
1786        let now = Instant::now();
1787        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1788
1789        // Schedule but DON'T cancel — just free the handles
1790        let h1 = wheel.schedule(now + ms(10), 1);
1791        let h2 = wheel.schedule(now + ms(20), 2);
1792
1793        // Free the handles (convert to fire-and-forget) so they don't debug_assert
1794        wheel.free(h1);
1795        wheel.free(h2);
1796
1797        // Drop the wheel — should clean up the entries
1798        drop(wheel);
1799    }
1800
1801    // -------------------------------------------------------------------------
1802    // Level selection
1803    // -------------------------------------------------------------------------
1804
1805    #[test]
1806    fn level_selection_boundaries() {
1807        let now = Instant::now();
1808        let wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1809
1810        // Level 0: delta < 64
1811        assert_eq!(wheel.select_level(0), 0);
1812        assert_eq!(wheel.select_level(63), 0);
1813
1814        // Level 1: 64 <= delta < 512
1815        assert_eq!(wheel.select_level(64), 1);
1816        assert_eq!(wheel.select_level(511), 1);
1817
1818        // Level 2: 512 <= delta < 4096
1819        assert_eq!(wheel.select_level(512), 2);
1820    }
1821
1822    // -------------------------------------------------------------------------
1823    // Bug fix validation: cancel after time advance
1824    // -------------------------------------------------------------------------
1825
1826    #[test]
1827    fn cancel_after_time_advance() {
1828        // The critical bug: schedule at T+500ms (level 2, delta=500 ticks),
1829        // poll at T+400ms (no fire, but current_ticks advances to 400),
1830        // cancel at T+400ms. Old code would recompute delta = 500-400 = 100
1831        // → level 1. But the entry is in level 2. Stored location fixes this.
1832        let now = Instant::now();
1833        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1834
1835        let h = wheel.schedule(now + ms(500), 42);
1836        assert_eq!(wheel.len(), 1);
1837
1838        // Advance time — timer doesn't fire (deadline is 500ms)
1839        let mut buf = Vec::new();
1840        let fired = wheel.poll(now + ms(400), &mut buf);
1841        assert_eq!(fired, 0);
1842        assert!(buf.is_empty());
1843
1844        // Cancel after time advance — must find the entry in the correct slot
1845        let val = wheel.cancel(h);
1846        assert_eq!(val, Some(42));
1847        assert_eq!(wheel.len(), 0);
1848    }
1849
1850    // -------------------------------------------------------------------------
1851    // Per-slot min: stale-low safety
1852    // -------------------------------------------------------------------------
1853
1854    #[test]
1855    fn slot_min_stale_low_after_cancel_still_fires() {
1856        // Cancelling the earliest entry in a non-empty slot leaves that slot's
1857        // cached min stale-low (the per-slot minima are not recomputed on
1858        // remove). Poll must still fire the SURVIVORS at the right times — never
1859        // skip a due entry, never fire an early one.
1860        let now = Instant::now();
1861        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1862
1863        // 3000 / 3001 / 3002 ms all land in the same level-2 slot.
1864        let h0 = wheel.schedule(now + ms(3000), 0);
1865        wheel.schedule_forget(now + ms(3001), 1);
1866        wheel.schedule_forget(now + ms(3002), 2);
1867
1868        // Cancel the earliest — the slot min now points at 3000 (gone): stale-low.
1869        assert_eq!(wheel.cancel(h0), Some(0));
1870
1871        let mut buf = Vec::new();
1872        assert_eq!(wheel.poll(now + ms(3000), &mut buf), 0, "nothing due yet");
1873        assert!(buf.is_empty());
1874
1875        let fired = wheel.poll(now + ms(3002), &mut buf);
1876        assert_eq!(fired, 2, "both survivors fire once due");
1877        buf.sort_unstable();
1878        assert_eq!(buf, vec![1, 2]);
1879    }
1880
1881    #[test]
1882    fn slot_min_resets_on_drain_and_reinsert() {
1883        // A drained slot resets its min to u64::MAX; a later insert must set the
1884        // min fresh, not inherit a stale value.
1885        let now = Instant::now();
1886        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1887
1888        wheel.schedule_forget(now + ms(3000), 0);
1889        let mut buf = Vec::new();
1890        assert_eq!(wheel.poll(now + ms(3000), &mut buf), 1);
1891        assert!(wheel.is_empty());
1892        assert!(wheel.next_deadline().is_none());
1893
1894        // Re-insert (likely into the same drained slot).
1895        wheel.schedule_forget(now + ms(3000), 1);
1896        let nd = wheel.next_deadline().expect("non-empty");
1897        assert!(nd <= now + ms(3000)); // lower bound — never later than the true deadline
1898        buf.clear();
1899        assert_eq!(wheel.poll(now + ms(2999), &mut buf), 0);
1900        assert_eq!(wheel.poll(now + ms(3000), &mut buf), 1);
1901    }
1902
1903    #[test]
1904    fn poll_refreshes_stale_low_cache() {
1905        // Cancelling the slot-min entry leaves the slot min — and, once read, the
1906        // global cache — stale-low, pointing at the cancelled deadline. A poll
1907        // that finds nothing due must refresh the cache off that stale value;
1908        // otherwise it stays <= now forever, defeating the early-exit and making
1909        // next_deadline() report a past instant.
1910        let now = Instant::now();
1911        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1912
1913        // 3000 / 3002 ms share a slot. Cancel the earlier one.
1914        let h0 = wheel.schedule(now + ms(3000), 0);
1915        wheel.schedule_forget(now + ms(3002), 1);
1916        assert_eq!(wheel.cancel(h0), Some(0));
1917
1918        // Populate the (now stale-low) cache: it points at the cancelled 3000.
1919        let stale = wheel.next_deadline().expect("non-empty");
1920        assert!(stale <= now + ms(3000));
1921
1922        // Poll past 3000 but before 3002 — nothing fires; the slot heals to 3002
1923        // and the cache is refreshed at the end of the poll.
1924        let mut buf = Vec::new();
1925        assert_eq!(wheel.poll(now + ms(3001), &mut buf), 0);
1926
1927        // Regression: without the poll-end refresh this would still be the
1928        // cancelled ~3000 (in the past). It must now reflect the survivor —
1929        // compared against the captured stale value so tick-rounding is irrelevant.
1930        let refreshed = wheel.next_deadline().expect("non-empty");
1931        assert!(
1932            refreshed > stale,
1933            "cache must refresh past the stale-low value after a no-fire poll",
1934        );
1935    }
1936
1937    // -------------------------------------------------------------------------
1938    // Same-slot entries
1939    // -------------------------------------------------------------------------
1940
1941    #[test]
1942    fn multiple_entries_same_slot() {
1943        let now = Instant::now();
1944        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1945
1946        // All 5 timers at the same deadline → same slot
1947        let mut handles = Vec::new();
1948        for i in 0..5 {
1949            handles.push(wheel.schedule(now + ms(10), i));
1950        }
1951        assert_eq!(wheel.len(), 5);
1952
1953        // Cancel the middle ones
1954        let v2 = wheel.cancel(handles.remove(2));
1955        assert_eq!(v2, Some(2));
1956        let v0 = wheel.cancel(handles.remove(0));
1957        assert_eq!(v0, Some(0));
1958        assert_eq!(wheel.len(), 3);
1959
1960        // Poll — remaining 3 should fire
1961        let mut buf = Vec::new();
1962        let fired = wheel.poll(now + ms(20), &mut buf);
1963        assert_eq!(fired, 3);
1964
1965        // Clean up zombie handles
1966        for h in handles {
1967            let val = wheel.cancel(h);
1968            assert_eq!(val, None); // already fired
1969        }
1970    }
1971
1972    // -------------------------------------------------------------------------
1973    // Level boundary
1974    // -------------------------------------------------------------------------
1975
1976    #[test]
1977    fn entry_at_level_boundary() {
1978        // Default config: level 0 range = 64 ticks (64ms).
1979        // A deadline at exactly tick 64 should go to level 1, not level 0.
1980        let now = Instant::now();
1981        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
1982
1983        let h = wheel.schedule(now + ms(64), 99);
1984        assert_eq!(wheel.len(), 1);
1985
1986        // Should NOT fire at 63ms
1987        let mut buf = Vec::new();
1988        let fired = wheel.poll(now + ms(63), &mut buf);
1989        assert_eq!(fired, 0);
1990
1991        // Should fire at 64ms
1992        let fired = wheel.poll(now + ms(65), &mut buf);
1993        assert_eq!(fired, 1);
1994        assert_eq!(buf, vec![99]);
1995
1996        // Clean up zombie handle
1997        wheel.cancel(h);
1998    }
1999
2000    // -------------------------------------------------------------------------
2001    // Bookmark/resumption with mixed expiry
2002    // -------------------------------------------------------------------------
2003
2004    #[test]
2005    fn poll_with_limit_mixed_expiry() {
2006        let now = Instant::now();
2007        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2008
2009        // 3 expired at poll time, 2 not
2010        wheel.schedule_forget(now + ms(5), 1);
2011        wheel.schedule_forget(now + ms(5), 2);
2012        wheel.schedule_forget(now + ms(5), 3);
2013        wheel.schedule_forget(now + ms(500), 4); // not expired
2014        wheel.schedule_forget(now + ms(500), 5); // not expired
2015        assert_eq!(wheel.len(), 5);
2016
2017        let mut buf = Vec::new();
2018
2019        // Fire 2 of the 3 expired
2020        let fired = wheel.poll_with_limit(now + ms(10), 2, &mut buf);
2021        assert_eq!(fired, 2);
2022        assert_eq!(wheel.len(), 3);
2023
2024        // Fire remaining expired (1 more)
2025        let fired = wheel.poll_with_limit(now + ms(10), 5, &mut buf);
2026        assert_eq!(fired, 1);
2027        assert_eq!(wheel.len(), 2);
2028
2029        // The 2 unexpired should still be there
2030        assert_eq!(buf.len(), 3);
2031    }
2032
2033    // -------------------------------------------------------------------------
2034    // Re-add after drain
2035    // -------------------------------------------------------------------------
2036
2037    #[test]
2038    fn reuse_after_full_drain() {
2039        let now = Instant::now();
2040        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2041
2042        // Round 1: schedule and drain
2043        for i in 0..10 {
2044            wheel.schedule_forget(now + ms(1), i);
2045        }
2046        let mut buf = Vec::new();
2047        wheel.poll(now + ms(5), &mut buf);
2048        assert_eq!(buf.len(), 10);
2049        assert!(wheel.is_empty());
2050
2051        // Round 2: schedule and drain again — wheel must work normally
2052        buf.clear();
2053        for i in 10..20 {
2054            wheel.schedule_forget(now + ms(100), i);
2055        }
2056        assert_eq!(wheel.len(), 10);
2057
2058        wheel.poll(now + ms(200), &mut buf);
2059        assert_eq!(buf.len(), 10);
2060        assert!(wheel.is_empty());
2061    }
2062
2063    // -------------------------------------------------------------------------
2064    // All levels active simultaneously
2065    // -------------------------------------------------------------------------
2066
2067    #[test]
2068    fn all_levels_active() {
2069        let now = Instant::now();
2070        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2071
2072        // Schedule one timer per level with increasing distances.
2073        // Level 0: <64ms, Level 1: 64-511ms, Level 2: 512-4095ms, etc.
2074        let distances = [10, 100, 1000, 5000, 40_000, 300_000, 3_000_000];
2075        let mut handles: Vec<TimerHandle<u64>> = Vec::new();
2076        for (i, &d) in distances.iter().enumerate() {
2077            handles.push(wheel.schedule(now + ms(d), i as u64));
2078        }
2079        assert_eq!(wheel.len(), 7);
2080
2081        // Cancel in a shuffled order: 4, 1, 6, 0, 3, 5, 2
2082        let order = [4, 1, 6, 0, 3, 5, 2];
2083        // Take ownership by swapping with dummies — actually we need to
2084        // cancel by index. Let's use Option to track.
2085        let mut opt_handles: Vec<Option<TimerHandle<u64>>> =
2086            handles.into_iter().map(Some).collect();
2087
2088        for &idx in &order {
2089            let h = opt_handles[idx].take().unwrap();
2090            let val = wheel.cancel(h);
2091            assert_eq!(val, Some(idx as u64));
2092        }
2093        assert!(wheel.is_empty());
2094    }
2095
2096    // -------------------------------------------------------------------------
2097    // Poll values match
2098    // -------------------------------------------------------------------------
2099
2100    #[test]
2101    fn poll_values_match() {
2102        let now = Instant::now();
2103        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2104
2105        let expected: Vec<u64> = (100..110).collect();
2106        for &v in &expected {
2107            wheel.schedule_forget(now + ms(5), v);
2108        }
2109
2110        let mut buf = Vec::new();
2111        wheel.poll(now + ms(10), &mut buf);
2112
2113        buf.sort_unstable();
2114        assert_eq!(buf, expected);
2115    }
2116
2117    // -------------------------------------------------------------------------
2118    // Reschedule
2119    // -------------------------------------------------------------------------
2120
2121    #[test]
2122    fn reschedule_moves_deadline() {
2123        let now = Instant::now();
2124        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2125
2126        let h = wheel.schedule(now + ms(100), 42);
2127        assert_eq!(wheel.len(), 1);
2128
2129        // Reschedule to earlier
2130        let h = wheel.reschedule(h, now + ms(50));
2131        assert_eq!(wheel.len(), 1);
2132
2133        // Should NOT fire at 40ms
2134        let mut buf = Vec::new();
2135        let fired = wheel.poll(now + ms(40), &mut buf);
2136        assert_eq!(fired, 0);
2137
2138        // Should fire at 50ms
2139        let fired = wheel.poll(now + ms(55), &mut buf);
2140        assert_eq!(fired, 1);
2141        assert_eq!(buf, vec![42]);
2142
2143        // Clean up zombie
2144        wheel.cancel(h);
2145    }
2146
2147    #[test]
2148    fn reschedule_to_later() {
2149        let now = Instant::now();
2150        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2151
2152        let h = wheel.schedule(now + ms(50), 7);
2153
2154        // Reschedule to later
2155        let h = wheel.reschedule(h, now + ms(200));
2156
2157        // Should NOT fire at original deadline
2158        let mut buf = Vec::new();
2159        let fired = wheel.poll(now + ms(60), &mut buf);
2160        assert_eq!(fired, 0);
2161
2162        // Should fire at new deadline
2163        let fired = wheel.poll(now + ms(210), &mut buf);
2164        assert_eq!(fired, 1);
2165        assert_eq!(buf, vec![7]);
2166
2167        wheel.cancel(h);
2168    }
2169
2170    #[test]
2171    #[should_panic(expected = "cannot reschedule a fired timer")]
2172    fn reschedule_panics_on_zombie() {
2173        let now = Instant::now();
2174        let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2175
2176        let h = wheel.schedule(now + ms(10), 42);
2177
2178        let mut buf = Vec::new();
2179        wheel.poll(now + ms(20), &mut buf);
2180
2181        // h is now a zombie — reschedule should panic
2182        let _h = wheel.reschedule(h, now + ms(100));
2183    }
2184
2185    // -------------------------------------------------------------------------
2186    // Non-default builder configurations (L13)
2187    // -------------------------------------------------------------------------
2188
2189    #[test]
2190    fn custom_slots_per_level() {
2191        let now = Instant::now();
2192        // 32 slots/level instead of default 64
2193        let mut wheel: Wheel<u64> = WheelBuilder::default()
2194            .slots_per_level(32)
2195            .unbounded(256)
2196            .build(now)
2197            .unwrap();
2198
2199        // Level 0 range = 32 ticks (32ms with 1ms tick)
2200        // Deadline at 20ms should go to level 0
2201        let h1 = wheel.schedule(now + ms(20), 1);
2202        // Deadline at 40ms should go to level 1 (>= 32 ticks)
2203        let h2 = wheel.schedule(now + ms(40), 2);
2204
2205        let mut buf = Vec::new();
2206        wheel.poll(now + ms(25), &mut buf);
2207        assert_eq!(buf, vec![1]);
2208
2209        buf.clear();
2210        wheel.poll(now + ms(50), &mut buf);
2211        assert_eq!(buf, vec![2]);
2212
2213        wheel.cancel(h1);
2214        wheel.cancel(h2);
2215    }
2216
2217    #[test]
2218    fn custom_clk_shift() {
2219        let now = Instant::now();
2220        // clk_shift=2 means 4x multiplier between levels (instead of 8x)
2221        let mut wheel: Wheel<u64> = WheelBuilder::default()
2222            .clk_shift(2)
2223            .unbounded(256)
2224            .build(now)
2225            .unwrap();
2226
2227        // Level 0: 64 slots × 1ms = 64ms range
2228        // Level 1: 64 slots × 4ms = 256ms range (with 4x multiplier)
2229        let h1 = wheel.schedule(now + ms(50), 1); // level 0
2230        let h2 = wheel.schedule(now + ms(100), 2); // level 1 (>= 64 ticks, <256 ticks)
2231
2232        let mut buf = Vec::new();
2233        wheel.poll(now + ms(55), &mut buf);
2234        assert_eq!(buf, vec![1]);
2235
2236        buf.clear();
2237        wheel.poll(now + ms(110), &mut buf);
2238        assert_eq!(buf, vec![2]);
2239
2240        wheel.cancel(h1);
2241        wheel.cancel(h2);
2242    }
2243
2244    #[test]
2245    fn custom_num_levels() {
2246        let now = Instant::now();
2247        // Only 3 levels instead of 7
2248        let mut wheel: Wheel<u64> = WheelBuilder::default()
2249            .num_levels(3)
2250            .unbounded(256)
2251            .build(now)
2252            .unwrap();
2253
2254        // Level 0: 64ms, Level 1: 512ms, Level 2: 4096ms
2255        // Max range is level 2 = 4096ms. Beyond that, clamped.
2256        let h = wheel.schedule(now + ms(3000), 42);
2257        assert_eq!(wheel.len(), 1);
2258
2259        let mut buf = Vec::new();
2260        wheel.poll(now + ms(3100), &mut buf);
2261        assert_eq!(buf, vec![42]);
2262
2263        wheel.cancel(h);
2264    }
2265
2266    #[test]
2267    fn custom_tick_duration() {
2268        let now = Instant::now();
2269        // 100μs ticks instead of 1ms
2270        let mut wheel: Wheel<u64> = WheelBuilder::default()
2271            .tick_duration(Duration::from_micros(100))
2272            .unbounded(256)
2273            .build(now)
2274            .unwrap();
2275
2276        // 1ms = 10 ticks, should be level 0 (< 64 ticks)
2277        wheel.schedule_forget(now + ms(1), 1);
2278        // 10ms = 100 ticks, should be level 1 (>= 64 ticks)
2279        wheel.schedule_forget(now + ms(10), 2);
2280
2281        let mut buf = Vec::new();
2282        wheel.poll(now + ms(2), &mut buf);
2283        assert_eq!(buf, vec![1]);
2284
2285        buf.clear();
2286        wheel.poll(now + ms(15), &mut buf);
2287        assert_eq!(buf, vec![2]);
2288    }
2289
2290    #[test]
2291    fn bounded_custom_config() {
2292        let now = Instant::now();
2293        let mut wheel: BoundedWheel<u64> = WheelBuilder::default()
2294            .slots_per_level(16)
2295            .num_levels(4)
2296            .bounded(8)
2297            .build(now)
2298            .unwrap();
2299
2300        // Fill to capacity
2301        let mut handles = Vec::new();
2302        for i in 0..8 {
2303            handles.push(wheel.try_schedule(now + ms(i * 10 + 10), i).unwrap());
2304        }
2305        assert!(wheel.try_schedule(now + ms(100), 99).is_err());
2306
2307        // Cancel one, schedule another
2308        wheel.cancel(handles.remove(0));
2309        let h = wheel.try_schedule(now + ms(100), 99).unwrap();
2310        handles.push(h);
2311
2312        // Clean up
2313        for h in handles {
2314            wheel.cancel(h);
2315        }
2316    }
2317
2318    // -------------------------------------------------------------------------
2319    // Builder validation (L13)
2320    // -------------------------------------------------------------------------
2321
2322    /// Asserts `result` is `Err(ConfigError::Invalid(_))` whose message contains
2323    /// `expect_substr`. Generic over the Ok type so it needs no `Debug` bound on
2324    /// the built wheel.
2325    #[track_caller]
2326    fn assert_invalid<T>(result: &Result<T, ConfigError>, expect_substr: &str) {
2327        match result {
2328            Err(ConfigError::Invalid(msg)) => assert!(
2329                msg.contains(expect_substr),
2330                "message {msg:?} does not contain {expect_substr:?}"
2331            ),
2332            Ok(_) => panic!("expected ConfigError::Invalid containing {expect_substr:?}, got Ok"),
2333        }
2334    }
2335
2336    #[test]
2337    fn invalid_config_too_many_slots() {
2338        let now = Instant::now();
2339        let result = WheelBuilder::default()
2340            .slots_per_level(128)
2341            .unbounded(1024)
2342            .build::<u64>(now);
2343        assert_invalid(&result, "slots_per_level must be <= 64");
2344    }
2345
2346    #[test]
2347    fn invalid_config_zero_levels() {
2348        let now = Instant::now();
2349        let result = WheelBuilder::default()
2350            .num_levels(0)
2351            .unbounded(1024)
2352            .build::<u64>(now);
2353        assert_invalid(&result, "num_levels must be > 0");
2354    }
2355
2356    #[test]
2357    fn invalid_config_too_many_levels() {
2358        let now = Instant::now();
2359        let result = WheelBuilder::default()
2360            .num_levels(9)
2361            .unbounded(1024)
2362            .build::<u64>(now);
2363        assert_invalid(&result, "num_levels must be <= 8");
2364    }
2365
2366    #[test]
2367    fn invalid_config_zero_shift() {
2368        let now = Instant::now();
2369        let result = WheelBuilder::default()
2370            .clk_shift(0)
2371            .unbounded(1024)
2372            .build::<u64>(now);
2373        assert_invalid(&result, "clk_shift must be > 0");
2374    }
2375
2376    #[test]
2377    fn invalid_config_zero_tick() {
2378        let now = Instant::now();
2379        let result = WheelBuilder::default()
2380            .tick_duration(Duration::ZERO)
2381            .unbounded(1024)
2382            .build::<u64>(now);
2383        assert_invalid(&result, "tick_duration must be non-zero");
2384    }
2385
2386    #[test]
2387    fn invalid_config_tick_too_large() {
2388        let now = Instant::now();
2389        // as_nanos() would exceed u64::MAX (~584 years), which would truncate on
2390        // the cast to u64 — must be rejected, not silently narrowed (a nonzero
2391        // multiple of 2^64 would truncate to 0 → divide-by-zero in build()).
2392        let result = WheelBuilder::default()
2393            .tick_duration(Duration::from_secs(20_000_000_000))
2394            .unbounded(1024)
2395            .build::<u64>(now);
2396        assert_invalid(&result, "tick_duration must fit in u64 nanoseconds");
2397    }
2398
2399    #[test]
2400    fn invalid_config_shift_overflow() {
2401        let now = Instant::now();
2402        // 8 levels × clk_shift=8 = 56 bits shift on level 7
2403        // Plus 64 slots (6 bits) = 62 bits, should be OK
2404        // But 8 levels × clk_shift=9 = 63 + 6 = 69 bits — overflow
2405        let result = WheelBuilder::default()
2406            .num_levels(8)
2407            .clk_shift(9)
2408            .unbounded(1024)
2409            .build::<u64>(now);
2410        assert_invalid(&result, "overflow");
2411    }
2412
2413    #[test]
2414    fn invalid_config_rebalance_progress() {
2415        let now = Instant::now();
2416        // slots_per_level = 4 (2^2), clk_shift = 3 → 2^3 = 8 >= 4, so a not-due
2417        // entry could rebalance to the *same* level and poll would live-lock.
2418        // Must be rejected at build time.
2419        let result = WheelBuilder::default()
2420            .slots_per_level(4)
2421            .clk_shift(3)
2422            .num_levels(2)
2423            .unbounded(64)
2424            .build::<u64>(now);
2425        assert_invalid(&result, "strictly finer level");
2426    }
2427
2428    // -------------------------------------------------------------------------
2429    // Rebalance tests (#668)
2430    // -------------------------------------------------------------------------
2431
2432    #[test]
2433    fn rebalanced_entry_fires_at_its_deadline() {
2434        let now = Instant::now();
2435        let mut wheel: Wheel<u64> = WheelBuilder::default().unbounded(256).build(now).unwrap();
2436
2437        // Both deadlines land in the same level-2 slot (46): 3000>>6 == 3005>>6.
2438        // At now=3000 the slot's min (3000) is due, so the slot is walked: 3000
2439        // is collected, and 3005 (not yet due) is rebalanced to a finer level
2440        // rather than being re-walked. It must still fire at its exact deadline.
2441        wheel.schedule_forget(now + ms(3000), 1);
2442        wheel.schedule_forget(now + ms(3005), 2);
2443
2444        let mut buf = Vec::new();
2445        wheel.poll_and_rebalance(now + ms(3000), &mut buf);
2446        assert_eq!(buf, vec![1], "3000 collected, 3005 rebalanced");
2447
2448        buf.clear();
2449        wheel.poll_and_rebalance(now + ms(3005), &mut buf);
2450        assert_eq!(buf, vec![2], "rebalanced entry fires at its exact deadline");
2451        assert!(wheel.is_empty());
2452    }
2453
2454    #[test]
2455    fn cancel_after_rebalance() {
2456        let now = Instant::now();
2457        let mut wheel: Wheel<u64> = WheelBuilder::default().unbounded(256).build(now).unwrap();
2458
2459        wheel.schedule_forget(now + ms(3000), 1);
2460        let h = wheel.schedule(now + ms(3005), 2); // rebalanced on the 3000 poll
2461
2462        let mut buf = Vec::new();
2463        wheel.poll_and_rebalance(now + ms(3000), &mut buf);
2464        assert_eq!(buf, vec![1]);
2465        assert_eq!(wheel.len(), 1, "rebalanced entry still live");
2466
2467        // cancel must find the entry at its new (finer) location and return it.
2468        assert_eq!(wheel.cancel(h), Some(2));
2469        assert_eq!(wheel.len(), 0);
2470    }
2471
2472    #[test]
2473    fn bounded_rebalance_still_fires_everything_on_time() {
2474        let now = Instant::now();
2475        // Cap = 1 rebalance per poll — a herd of not-yet-due entries in one
2476        // coarse slot drains over many polls instead of all at once, but every
2477        // timer must still fire at its exact deadline.
2478        let mut wheel: Wheel<u64> = WheelBuilder::default()
2479            .max_rebalances_per_poll(1)
2480            .unbounded(256)
2481            .build(now)
2482            .unwrap();
2483
2484        // 20 deadlines spread across one level-2 slot (all map to slot 46).
2485        let mut expected: Vec<u64> = Vec::new();
2486        for i in 0..20u64 {
2487            let d = 2950 + i * 2; // 2950, 2952, ... 2988 — all in level-2 slot 46
2488            wheel.schedule_forget(now + ms(d), d);
2489            expected.push(d);
2490        }
2491
2492        let mut fired: Vec<u64> = Vec::new();
2493        let mut buf = Vec::new();
2494        for t in 0..=3000u64 {
2495            buf.clear();
2496            wheel.poll_and_rebalance(now + ms(t), &mut buf);
2497            for &v in &buf {
2498                assert!(v <= t, "timer {v} fired early at {t}");
2499                fired.push(v);
2500            }
2501        }
2502        fired.sort_unstable();
2503        assert_eq!(fired, expected, "every timer fires exactly once, on time");
2504        assert!(wheel.is_empty());
2505    }
2506
2507    #[test]
2508    fn rebalance_cap_zero_is_collect_only() {
2509        let now = Instant::now();
2510        // Cap = 0: no rebalancing at all — entries never move levels and fire
2511        // from wherever they were placed (pure drip-fire). Must still be correct.
2512        let mut wheel: Wheel<u64> = WheelBuilder::default()
2513            .max_rebalances_per_poll(0)
2514            .unbounded(256)
2515            .build(now)
2516            .unwrap();
2517
2518        wheel.schedule_forget(now + ms(3000), 1);
2519        wheel.schedule_forget(now + ms(3005), 2); // would rebalance if the cap allowed
2520
2521        let mut buf = Vec::new();
2522        wheel.poll_and_rebalance(now + ms(3000), &mut buf);
2523        assert_eq!(buf, vec![1]); // 3000 collected; 3005 left in its coarse slot
2524        buf.clear();
2525        wheel.poll_and_rebalance(now + ms(3005), &mut buf);
2526        assert_eq!(buf, vec![2]); // fires on time from its original slot
2527        assert!(wheel.is_empty());
2528    }
2529
2530    #[test]
2531    fn proactive_rebalance_moves_and_preserves_firing() {
2532        let now = Instant::now();
2533        let mut wheel: Wheel<u64> = WheelBuilder::default().unbounded(256).build(now).unwrap();
2534
2535        // 10 deadlines at level 2 (delta ~3000 ∈ [512, 4096)).
2536        let mut expected = Vec::new();
2537        for i in 0..10u64 {
2538            let d = 3000 + i * 4;
2539            wheel.schedule_forget(now + ms(d), d);
2540            expected.push(d);
2541        }
2542
2543        // Far from the deadlines, nothing is within a finer level's reach.
2544        assert_eq!(
2545            wheel.rebalance(now, usize::MAX),
2546            0,
2547            "nothing to pull down yet"
2548        );
2549
2550        // Drive the timeline with proactive rebalance + collect-only poll. Every
2551        // timer must still fire exactly once, on time — and rebalance must have
2552        // actually pulled entries down as they approached.
2553        let mut fired = Vec::new();
2554        let mut buf = Vec::new();
2555        let mut total_moved = 0;
2556        for t in 0..=3040u64 {
2557            total_moved += wheel.rebalance(now + ms(t), usize::MAX);
2558            buf.clear();
2559            wheel.poll(now + ms(t), &mut buf);
2560            for &v in &buf {
2561                assert!(v <= t, "timer {v} fired early at {t}");
2562                fired.push(v);
2563            }
2564        }
2565        assert!(
2566            total_moved > 0,
2567            "rebalance pulled entries down as they neared"
2568        );
2569        fired.sort_unstable();
2570        assert_eq!(fired, expected, "every timer fires once, on time");
2571        assert!(wheel.is_empty());
2572    }
2573
2574    // -------------------------------------------------------------------------
2575    // Miri-compatible tests (L12)
2576    // -------------------------------------------------------------------------
2577    // These tests exercise the raw pointer paths (DLL operations, entry
2578    // lifecycle, poll) with Drop types to catch UB under Miri.
2579
2580    #[test]
2581    fn miri_schedule_cancel_drop_type() {
2582        let now = Instant::now();
2583        let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2584
2585        let h = wheel.schedule(now + ms(50), "hello".to_string());
2586        let val = wheel.cancel(h);
2587        assert_eq!(val, Some("hello".to_string()));
2588        assert!(wheel.is_empty());
2589    }
2590
2591    #[test]
2592    fn miri_poll_fires_drop_type() {
2593        let now = Instant::now();
2594        let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2595
2596        wheel.schedule_forget(now + ms(10), "a".to_string());
2597        wheel.schedule_forget(now + ms(10), "b".to_string());
2598        wheel.schedule_forget(now + ms(10), "c".to_string());
2599
2600        let mut buf = Vec::new();
2601        let fired = wheel.poll(now + ms(20), &mut buf);
2602        assert_eq!(fired, 3);
2603        assert_eq!(buf.len(), 3);
2604        assert!(wheel.is_empty());
2605    }
2606
2607    #[test]
2608    fn miri_cancel_zombie_drop_type() {
2609        let now = Instant::now();
2610        let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2611
2612        let h = wheel.schedule(now + ms(10), "zombie".to_string());
2613
2614        let mut buf = Vec::new();
2615        wheel.poll(now + ms(20), &mut buf);
2616        assert_eq!(buf, vec!["zombie".to_string()]);
2617
2618        // h is now a zombie — cancel frees the entry
2619        let val = wheel.cancel(h);
2620        assert_eq!(val, None);
2621    }
2622
2623    #[test]
2624    fn miri_free_active_and_zombie() {
2625        let now = Instant::now();
2626        let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2627
2628        // Active → fire-and-forget via free
2629        let h1 = wheel.schedule(now + ms(10), "active".to_string());
2630        wheel.free(h1);
2631
2632        // Poll fires the fire-and-forget entry
2633        let mut buf = Vec::new();
2634        wheel.poll(now + ms(20), &mut buf);
2635        assert_eq!(buf, vec!["active".to_string()]);
2636
2637        // Zombie → free
2638        let h2 = wheel.schedule(now + ms(10), "will-fire".to_string());
2639        buf.clear();
2640        wheel.poll(now + ms(20), &mut buf);
2641        wheel.free(h2); // zombie cleanup
2642    }
2643
2644    #[test]
2645    fn miri_reschedule_drop_type() {
2646        let now = Instant::now();
2647        let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2648
2649        let h = wheel.schedule(now + ms(100), "moveme".to_string());
2650        let h = wheel.reschedule(h, now + ms(50));
2651
2652        let mut buf = Vec::new();
2653        wheel.poll(now + ms(55), &mut buf);
2654        assert_eq!(buf, vec!["moveme".to_string()]);
2655
2656        wheel.cancel(h);
2657    }
2658
2659    #[test]
2660    fn miri_dll_multi_entry_same_slot() {
2661        // Multiple entries in same slot exercises DLL push/remove paths
2662        let now = Instant::now();
2663        let mut wheel: Wheel<Vec<u8>> = Wheel::unbounded(64, now);
2664
2665        let mut handles = Vec::new();
2666        for i in 0..5 {
2667            handles.push(wheel.schedule(now + ms(10), vec![i; 32]));
2668        }
2669
2670        // Cancel middle, then head, then tail
2671        let v2 = wheel.cancel(handles.remove(2));
2672        assert_eq!(v2.unwrap(), vec![2; 32]);
2673
2674        let v0 = wheel.cancel(handles.remove(0));
2675        assert_eq!(v0.unwrap(), vec![0; 32]);
2676
2677        // Poll remaining
2678        let mut buf = Vec::new();
2679        wheel.poll(now + ms(20), &mut buf);
2680        assert_eq!(buf.len(), 3);
2681
2682        // Clean up zombie handles
2683        for h in handles {
2684            wheel.cancel(h);
2685        }
2686    }
2687
2688    #[test]
2689    fn miri_drop_wheel_with_entries() {
2690        let now = Instant::now();
2691        let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2692
2693        // Schedule entries across multiple levels
2694        for i in 0..20 {
2695            wheel.schedule_forget(now + ms(i * 100), format!("entry-{i}"));
2696        }
2697        assert_eq!(wheel.len(), 20);
2698
2699        // Drop with active entries — must not leak or UB
2700        drop(wheel);
2701    }
2702
2703    #[test]
2704    fn miri_bounded_lifecycle() {
2705        let now = Instant::now();
2706        let mut wheel: BoundedWheel<String> = BoundedWheel::bounded(4, now);
2707
2708        let h1 = wheel.try_schedule(now + ms(10), "a".to_string()).unwrap();
2709        let h2 = wheel.try_schedule(now + ms(20), "b".to_string()).unwrap();
2710        let h3 = wheel.try_schedule(now + ms(30), "c".to_string()).unwrap();
2711        let h4 = wheel.try_schedule(now + ms(40), "d".to_string()).unwrap();
2712
2713        // Full
2714        let err = wheel.try_schedule(now + ms(50), "e".to_string());
2715        assert!(err.is_err());
2716
2717        // Cancel and reuse
2718        wheel.cancel(h1);
2719        let h5 = wheel.try_schedule(now + ms(50), "e".to_string()).unwrap();
2720
2721        // Poll fires some
2722        let mut buf = Vec::new();
2723        wheel.poll(now + ms(25), &mut buf);
2724
2725        // Clean up all remaining handles
2726        wheel.cancel(h2);
2727        wheel.free(h3);
2728        wheel.free(h4);
2729        wheel.free(h5);
2730    }
2731
2732    #[test]
2733    fn miri_rebalance_relocate_drop_type() {
2734        // Exercises the rebalance relocate path (insert_entry called while this
2735        // slot's `&WheelSlot` is held) with a Drop type, to catch any aliasing
2736        // UB in that hot-path borrow. Must use poll_and_rebalance — plain poll
2737        // never relocates, so it would not exercise the path.
2738        let now = Instant::now();
2739        let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2740
2741        // Same level-2 slot: 3000>>6 == 3005>>6. At now=3000 the "collected"
2742        // entry fires and the "rebalanced" entry relocates to a finer level.
2743        wheel.schedule_forget(now + ms(3000), "collected".to_string());
2744        wheel.schedule_forget(now + ms(3005), "rebalanced".to_string());
2745
2746        let mut buf = Vec::new();
2747        wheel.poll_and_rebalance(now + ms(3000), &mut buf);
2748        assert_eq!(buf, vec!["collected".to_string()]);
2749
2750        buf.clear();
2751        wheel.poll_and_rebalance(now + ms(3005), &mut buf);
2752        assert_eq!(buf, vec!["rebalanced".to_string()]);
2753        assert!(wheel.is_empty());
2754    }
2755
2756    #[test]
2757    fn miri_rebalance_method_drop_type() {
2758        // Standalone rebalance() uses the same insert_entry-while-slot-borrowed
2759        // pattern as poll_and_rebalance; exercise it with a Drop type.
2760        let now = Instant::now();
2761        let mut wheel: Wheel<String> = Wheel::unbounded(64, now);
2762        wheel.schedule_forget(now + ms(3000), "a".to_string());
2763        wheel.schedule_forget(now + ms(3004), "b".to_string());
2764
2765        // Advance so both are within a finer level's reach, then rebalance.
2766        let moved = wheel.rebalance(now + ms(2960), usize::MAX);
2767        assert!(moved >= 1);
2768
2769        let mut buf = Vec::new();
2770        wheel.poll(now + ms(3004), &mut buf);
2771        buf.sort();
2772        assert_eq!(buf, vec!["a".to_string(), "b".to_string()]);
2773        assert!(wheel.is_empty());
2774    }
2775}
2776
2777#[cfg(test)]
2778mod proptests {
2779    use super::*;
2780    use proptest::prelude::*;
2781    use std::collections::HashSet;
2782    use std::mem;
2783    use std::time::{Duration, Instant};
2784
2785    /// Operation in a schedule/cancel interleaving.
2786    #[derive(Debug, Clone)]
2787    enum Op {
2788        /// Schedule a timer at `deadline_ms` milliseconds from epoch.
2789        Schedule { deadline_ms: u64 },
2790        /// Cancel the timer at the given index (modulo outstanding handles).
2791        Cancel { idx: usize },
2792    }
2793
2794    fn op_strategy() -> impl Strategy<Value = Op> {
2795        prop_oneof![
2796            // Schedule with deadlines from 1ms to 10_000ms
2797            (1u64..10_000).prop_map(|deadline_ms| Op::Schedule { deadline_ms }),
2798            // Cancel at random index
2799            any::<usize>().prop_map(|idx| Op::Cancel { idx }),
2800        ]
2801    }
2802
2803    proptest! {
2804        #![proptest_config(ProptestConfig::with_cases(500))]
2805
2806        /// Fuzz schedule/cancel interleaving.
2807        ///
2808        /// Random sequence of schedule and cancel operations. Invariants:
2809        /// - `len` always matches outstanding active timers
2810        /// - cancel on active handle returns `Some`
2811        /// - poll collects all un-cancelled values
2812        #[test]
2813        fn fuzz_schedule_cancel_interleaving(ops in proptest::collection::vec(op_strategy(), 1..200)) {
2814            let now = Instant::now();
2815            let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2816
2817            let mut handles: Vec<TimerHandle<u64>> = Vec::new();
2818            let mut active_values: HashSet<u64> = HashSet::new();
2819            let mut next_id: u64 = 0;
2820
2821            for op in &ops {
2822                match op {
2823                    Op::Schedule { deadline_ms } => {
2824                        let id = next_id;
2825                        next_id += 1;
2826                        let h = wheel.schedule(now + Duration::from_millis(*deadline_ms), id);
2827                        handles.push(h);
2828                        active_values.insert(id);
2829                    }
2830                    Op::Cancel { idx } => {
2831                        if !handles.is_empty() {
2832                            let i = idx % handles.len();
2833                            let h = handles.swap_remove(i);
2834                            let val = wheel.cancel(h);
2835                            // Value should be Some (all handles are for active timers)
2836                            let v = val.unwrap();
2837                            assert!(active_values.remove(&v));
2838                        }
2839                    }
2840                }
2841                // len must match active values
2842                prop_assert_eq!(wheel.len(), active_values.len());
2843            }
2844
2845            // Poll everything — should collect exactly the remaining active values
2846            let mut buf = Vec::new();
2847            // Use a far-future time to fire everything
2848            wheel.poll(now + Duration::from_secs(100_000), &mut buf);
2849
2850            // Clean up zombie handles (poll fired them, handles still exist)
2851            for h in handles {
2852                mem::forget(h);
2853            }
2854
2855            let fired_set: HashSet<u64> = buf.into_iter().collect();
2856            prop_assert_eq!(fired_set, active_values);
2857            prop_assert!(wheel.is_empty());
2858        }
2859
2860        /// Fuzz poll timing.
2861        ///
2862        /// Schedule N timers with random deadlines. Poll at random increasing
2863        /// times. Assert every timer fires exactly once, fired deadlines are
2864        /// all <= poll time, unfired deadlines are all > poll time.
2865        #[test]
2866        fn fuzz_poll_timing(
2867            deadlines in proptest::collection::vec(1u64..5000, 1..100),
2868            poll_times in proptest::collection::vec(1u64..10_000, 1..20),
2869        ) {
2870            let now = Instant::now();
2871            let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2872
2873            // Schedule all timers (fire-and-forget)
2874            for (i, &d) in deadlines.iter().enumerate() {
2875                wheel.schedule_forget(now + Duration::from_millis(d), i as u64);
2876            }
2877
2878            // Sort poll times to be monotonically increasing
2879            let mut sorted_times: Vec<u64> = poll_times;
2880            sorted_times.sort_unstable();
2881            sorted_times.dedup();
2882
2883            let mut all_fired: Vec<u64> = Vec::new();
2884
2885            for &t in &sorted_times {
2886                let mut buf = Vec::new();
2887                wheel.poll(now + Duration::from_millis(t), &mut buf);
2888
2889                // Every fired entry should have deadline_ms <= t
2890                for &id in &buf {
2891                    let deadline_ms = deadlines[id as usize];
2892                    prop_assert!(deadline_ms <= t,
2893                        "Timer {} with deadline {}ms fired at {}ms", id, deadline_ms, t);
2894                }
2895
2896                all_fired.extend(buf);
2897            }
2898
2899            // Fire everything remaining
2900            let mut final_buf = Vec::new();
2901            wheel.poll(now + Duration::from_secs(100_000), &mut final_buf);
2902            all_fired.extend(final_buf);
2903
2904            // Every timer should have fired exactly once
2905            all_fired.sort_unstable();
2906            let expected: Vec<u64> = (0..deadlines.len() as u64).collect();
2907            prop_assert_eq!(all_fired, expected, "Not all timers fired exactly once");
2908            prop_assert!(wheel.is_empty());
2909        }
2910
2911        /// Fuzz next_deadline cache correctness.
2912        ///
2913        /// Random sequence of schedule, schedule_forget, cancel, reschedule,
2914        /// and poll operations. After each operation, verifies the cached
2915        /// `next_deadline()` matches the uncached full walk.
2916        #[test]
2917        fn fuzz_next_deadline_cache(
2918            ops in proptest::collection::vec(deadline_op_strategy(), 1..300),
2919        ) {
2920            let now = Instant::now();
2921            let mut wheel: Wheel<u64> = Wheel::unbounded(1024, now);
2922            let mut handles: Vec<(TimerHandle<u64>, u64)> = Vec::new();
2923            let mut next_id: u64 = 0;
2924
2925            for op in &ops {
2926                match op {
2927                    DeadlineOp::Schedule { deadline_ms } => {
2928                        let h = wheel.schedule(now + Duration::from_millis(*deadline_ms), next_id);
2929                        handles.push((h, *deadline_ms));
2930                        next_id += 1;
2931                    }
2932                    DeadlineOp::ScheduleForget { deadline_ms } => {
2933                        wheel.schedule_forget(now + Duration::from_millis(*deadline_ms), next_id);
2934                        next_id += 1;
2935                    }
2936                    DeadlineOp::Cancel { idx } => {
2937                        if !handles.is_empty() {
2938                            let i = idx % handles.len();
2939                            let (h, _) = handles.swap_remove(i);
2940                            wheel.cancel(h);
2941                        }
2942                    }
2943                    DeadlineOp::Reschedule { idx, new_deadline_ms } => {
2944                        if !handles.is_empty() {
2945                            let i = idx % handles.len();
2946                            let (h, _) = handles.swap_remove(i);
2947                            let new_h = wheel.reschedule(h, now + Duration::from_millis(*new_deadline_ms));
2948                            handles.push((new_h, *new_deadline_ms));
2949                        }
2950                    }
2951                    DeadlineOp::Poll { at_ms } => {
2952                        let mut buf = Vec::new();
2953                        wheel.poll(now + Duration::from_millis(*at_ms), &mut buf);
2954                        // Free zombie handles whose timers just fired.
2955                        // A handle is a zombie if its deadline_ms <= at_ms.
2956                        let at = *at_ms;
2957                        let mut i = 0;
2958                        while i < handles.len() {
2959                            if handles[i].1 <= at {
2960                                let (h, _) = handles.swap_remove(i);
2961                                wheel.free(h);
2962                            } else {
2963                                i += 1;
2964                            }
2965                        }
2966                    }
2967                }
2968
2969                // Contract: `next_deadline()` is a LOWER BOUND — the per-slot
2970                // minima are stale-low after removal, so it may report earlier
2971                // than the true next fire, never later. Assert it never exceeds
2972                // the exact minimum, and that emptiness agrees.
2973                let cached = wheel.next_deadline();
2974                let exact = wheel.next_deadline_uncached();
2975                prop_assert_eq!(
2976                    cached.is_none(),
2977                    exact.is_none(),
2978                    "emptiness disagrees after {:?}",
2979                    op
2980                );
2981                if let (Some(c), Some(e)) = (cached, exact) {
2982                    prop_assert!(
2983                        c <= e,
2984                        "next_deadline {:?} exceeded exact {:?} after {:?}",
2985                        c,
2986                        e,
2987                        op
2988                    );
2989                }
2990            }
2991
2992            for (h, _) in handles {
2993                mem::forget(h);
2994            }
2995        }
2996    }
2997
2998    #[derive(Debug, Clone)]
2999    enum DeadlineOp {
3000        Schedule { deadline_ms: u64 },
3001        ScheduleForget { deadline_ms: u64 },
3002        Cancel { idx: usize },
3003        Reschedule { idx: usize, new_deadline_ms: u64 },
3004        Poll { at_ms: u64 },
3005    }
3006
3007    fn deadline_op_strategy() -> impl Strategy<Value = DeadlineOp> {
3008        prop_oneof![
3009            (1u64..10_000).prop_map(|deadline_ms| DeadlineOp::Schedule { deadline_ms }),
3010            (1u64..10_000).prop_map(|deadline_ms| DeadlineOp::ScheduleForget { deadline_ms }),
3011            any::<usize>().prop_map(|idx| DeadlineOp::Cancel { idx }),
3012            (any::<usize>(), 1u64..10_000).prop_map(|(idx, new_deadline_ms)| {
3013                DeadlineOp::Reschedule {
3014                    idx,
3015                    new_deadline_ms,
3016                }
3017            }),
3018            (1u64..10_000).prop_map(|at_ms| DeadlineOp::Poll { at_ms }),
3019        ]
3020    }
3021}