Skip to main content

bombay_timers/
lib.rs

1//! A keyed, generation-safe monotonic timer queue.
2
3use core::cmp::{Ordering, Reverse};
4use core::fmt;
5use core::hash::{Hash, Hasher};
6use rustc_hash::FxHasher;
7use std::collections::BinaryHeap;
8use std::mem;
9use std::sync::Arc;
10
11/// Schedule interval between heap-compaction checks; a power of two.
12const COMPACT_INTERVAL: u64 = 1024;
13
14/// Unforgeable queue identity. One brand is allocated per [`TimerQueue`] and
15/// shared by every token the queue mints; because tokens hold an `Arc` to
16/// their brand, the brand allocation outlives its queue whenever tokens do,
17/// so a later queue can never occupy the same address and alias its
18/// authority. The type is private and the API exposes no way to construct or
19/// compare brands, so a brand cannot be forged.
20struct QueueBrand;
21
22/// Exact authority over one scheduled generation.
23///
24/// Authority is scoped to the issuing queue: a token minted by one
25/// [`TimerQueue`] can never cancel a schedule in another queue, even when key
26/// and generation number coincide.
27#[derive(Clone)]
28pub struct Token<K> {
29    brand: Arc<QueueBrand>,
30    key: K,
31    generation: u64,
32}
33
34#[allow(
35    clippy::missing_fields_in_debug,
36    reason = "the brand is deliberately opaque: it identifies the issuing queue, not the schedule"
37)]
38impl<K: fmt::Debug> fmt::Debug for Token<K> {
39    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
40        f.debug_struct("Token")
41            .field("key", &self.key)
42            .field("generation", &self.generation)
43            .finish()
44    }
45}
46
47impl<K: PartialEq> PartialEq for Token<K> {
48    fn eq(&self, other: &Self) -> bool {
49        Arc::ptr_eq(&self.brand, &other.brand)
50            && self.key == other.key
51            && self.generation == other.generation
52    }
53}
54impl<K: Eq> Eq for Token<K> {}
55
56impl<K> Token<K> {
57    /// Inspect the scheduled key.
58    #[must_use]
59    pub const fn key(&self) -> &K {
60        &self.key
61    }
62}
63
64struct Entry<I, K, V> {
65    at: I,
66    sequence: u64,
67    generation: u64,
68    key: K,
69    value: V,
70}
71
72impl<I: Ord, K, V> PartialEq for Entry<I, K, V> {
73    fn eq(&self, other: &Self) -> bool {
74        self.at == other.at && self.sequence == other.sequence
75    }
76}
77impl<I: Ord, K, V> Eq for Entry<I, K, V> {}
78impl<I: Ord, K, V> PartialOrd for Entry<I, K, V> {
79    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
80        Some(self.cmp(other))
81    }
82}
83impl<I: Ord, K, V> Ord for Entry<I, K, V> {
84    #[inline]
85    fn cmp(&self, other: &Self) -> Ordering {
86        self.at
87            .cmp(&other.at)
88            .then_with(|| self.sequence.cmp(&other.sequence))
89    }
90}
91
92/// An expiration emitted by the queue.
93#[derive(Debug, Clone, PartialEq, Eq)]
94pub struct Expired<I, K, V> {
95    /// Requested deadline.
96    pub at: I,
97    /// Scheduled key.
98    pub key: K,
99    /// Scheduled value.
100    pub value: V,
101}
102
103/// A rejected scheduling request, retaining ownership of its complete input.
104#[derive(Debug, Clone, PartialEq, Eq)]
105pub enum ScheduleError<I, K, V> {
106    /// No further timer generation can be represented.
107    GenerationExhausted { key: K, at: I, value: V },
108    /// No further insertion sequence can be represented.
109    SequenceExhausted { key: K, at: I, value: V },
110}
111
112/// Minimal open-addressing map: key -> generation.
113///
114/// Linear probing with tombstones over power-of-two capacity, `FxHash`. The
115/// scheduler only needs `insert`/`get`/`remove`/`len`/`shrink_to_fit` — never
116/// iteration — so a purpose-built probe table beats a Swiss-table `HashMap` on
117/// the hot path: one state-byte load per probe instead of a 16-byte SIMD
118/// control-group scan, at the same `FxHash` cost.
119struct GenMap<K> {
120    keys: Vec<Option<K>>,
121    gens: Vec<u64>,
122    /// Occupied slots.
123    len: usize,
124    /// `(capacity() * 3) / 4`, cached so the per-insert growth check is a
125    /// compare instead of a multiply.
126    grow_threshold: usize,
127}
128
129impl<K> Default for GenMap<K> {
130    fn default() -> Self {
131        Self::new()
132    }
133}
134
135impl<K> GenMap<K> {
136    fn new() -> Self {
137        Self {
138            keys: Vec::new(),
139            gens: Vec::new(),
140            len: 0,
141            grow_threshold: 0,
142        }
143    }
144
145    fn len(&self) -> usize {
146        self.len
147    }
148
149    fn is_empty(&self) -> bool {
150        self.len == 0
151    }
152
153    fn capacity(&self) -> usize {
154        self.keys.len()
155    }
156
157    fn hash(key: &K) -> u64
158    where
159        K: Hash,
160    {
161        let mut hasher = FxHasher::default();
162        key.hash(&mut hasher);
163        hasher.finish()
164    }
165
166    /// Probe start for `key` under `mask` (capacity minus one, a power of two
167    /// minus one). Truncating the hash to `usize` is deliberate: only the low
168    /// bits select the table slot.
169    #[allow(
170        clippy::cast_possible_truncation,
171        reason = "hash-to-index truncation is inherent to table sizing"
172    )]
173    fn index(key: &K, mask: usize) -> usize
174    where
175        K: Hash,
176    {
177        Self::hash(key) as usize & mask
178    }
179
180    /// Rebuild the table at exactly `capacity` (a power of two, zero allowed),
181    /// reinserting the occupied entries.
182    fn rebuild(&mut self, capacity: usize)
183    where
184        K: Hash,
185    {
186        let mut keys: Vec<Option<K>> = Vec::with_capacity(capacity);
187        keys.resize_with(capacity, || None);
188        let mut gens = vec![0_u64; capacity];
189        for (i, slot) in self.keys.drain(..).enumerate() {
190            if let Some(key) = slot {
191                let mask = capacity - 1;
192                let mut j = Self::index(&key, mask);
193                while keys[j].is_some() {
194                    j = (j + 1) & mask;
195                }
196                keys[j] = Some(key);
197                gens[j] = self.gens[i];
198            }
199        }
200        self.keys = keys;
201        self.gens = gens;
202        self.grow_threshold = (self.capacity() * 3) / 4;
203    }
204
205    fn grow(&mut self)
206    where
207        K: Hash,
208    {
209        let new_cap = if self.capacity() == 0 {
210            4
211        } else {
212            self.capacity() * 2
213        };
214        self.rebuild(new_cap);
215    }
216
217    fn insert(&mut self, key: K, generation: u64) -> Option<u64>
218    where
219        K: Eq + Hash,
220    {
221        if self.len >= self.grow_threshold {
222            self.grow();
223        }
224        let mask = self.capacity() - 1;
225        let mut i = Self::index(&key, mask);
226        loop {
227            match &self.keys[i] {
228                None => {
229                    self.keys[i] = Some(key);
230                    self.gens[i] = generation;
231                    self.len += 1;
232                    return None;
233                }
234                Some(k) if k == &key => {
235                    return Some(mem::replace(&mut self.gens[i], generation));
236                }
237                Some(_) => {}
238            }
239            i = (i + 1) & mask;
240        }
241    }
242
243    fn get(&self, key: &K) -> Option<&u64>
244    where
245        K: Eq + Hash,
246    {
247        if self.capacity() == 0 {
248            return None;
249        }
250        let mask = self.capacity() - 1;
251        let mut i = Self::index(key, mask);
252        loop {
253            match self.keys[i] {
254                None => return None,
255                Some(ref k) if k == key => return Some(&self.gens[i]),
256                Some(_) => {}
257            }
258            i = (i + 1) & mask;
259        }
260    }
261
262    /// Remove the entry at the probed slot `i`, shifting any following entries
263    /// whose probe chain runs through the vacated slot one step back. This
264    /// needs no tombstones: the table only ever holds `Some` (occupied) and
265    /// `None` (empty), so probes always terminate and the load factor counts
266    /// only occupied slots.
267    fn delete_at(&mut self, i: usize, mask: usize)
268    where
269        K: Hash,
270    {
271        let mut i = i;
272        // Walk forward from the gap. An entry at `j` must shift back into the
273        // gap iff its probe chain (from its hash slot `h`) passes through the
274        // gap `i`; otherwise it stays and the walk continues, because entries
275        // further along may still chain through the gap.
276        let mut j = (i + 1) & mask;
277        while let Some(k) = &self.keys[j] {
278            let h = Self::index(k, mask);
279            let passes_gap = if h <= j {
280                h <= i && i <= j
281            } else {
282                // The chain wraps: it covers `h..=mask` and `0..=j`.
283                i >= h || i <= j
284            };
285            if passes_gap {
286                self.keys[i] = self.keys[j].take();
287                self.gens[i] = self.gens[j];
288                i = j;
289            }
290            j = (j + 1) & mask;
291        }
292        self.keys[i] = None;
293    }
294
295    fn remove(&mut self, key: &K) -> Option<u64>
296    where
297        K: Eq + Hash,
298    {
299        if self.capacity() == 0 {
300            return None;
301        }
302        let mask = self.capacity() - 1;
303        let mut i = Self::index(key, mask);
304        loop {
305            match &self.keys[i] {
306                None => return None,
307                Some(k) if k == key => {
308                    let generation = self.gens[i];
309                    self.len -= 1;
310                    self.delete_at(i, mask);
311                    return Some(generation);
312                }
313                Some(_) => {}
314            }
315            i = (i + 1) & mask;
316        }
317    }
318
319    /// Remove `key` iff it maps to exactly `generation`, in a single probe
320    /// (the cancel path would otherwise pay get-then-remove, two probes).
321    fn cancel(&mut self, key: &K, generation: u64) -> bool
322    where
323        K: Eq + Hash,
324    {
325        if self.capacity() == 0 {
326            return false;
327        }
328        let mask = self.capacity() - 1;
329        let mut i = Self::index(key, mask);
330        loop {
331            match &self.keys[i] {
332                None => return false,
333                Some(k) if k == key => {
334                    if self.gens[i] == generation {
335                        self.len -= 1;
336                        self.delete_at(i, mask);
337                        return true;
338                    }
339                    return false;
340                }
341                Some(_) => {}
342            }
343            i = (i + 1) & mask;
344        }
345    }
346
347    fn shrink_to_fit(&mut self) {
348        // The queue only shrinks after a full drain (len == 0), releasing the
349        // whole table.
350        if self.len == 0 {
351            self.keys = Vec::new();
352            self.gens = Vec::new();
353            self.grow_threshold = 0;
354        }
355    }
356}
357
358/// Safe reference scheduler using a binary heap and generation index.
359pub struct TimerQueue<I, K, V> {
360    brand: Arc<QueueBrand>,
361    heap: BinaryHeap<Reverse<Entry<I, K, V>>>,
362    current: GenMap<K>,
363    next_generation: u64,
364    next_sequence: u64,
365    /// Whether the heap may contain stale (superseded) entries. Stale entries
366    /// are created only by replacing or cancelling a live schedule and are
367    /// removed entirely by a compaction rebuild, so the flag tracks exactly
368    /// those transitions. When `false`, `discard_stale` skips its per-pop
369    /// generation lookup entirely.
370    stale_possible: bool,
371}
372
373impl<I, K, V> Default for TimerQueue<I, K, V> {
374    fn default() -> Self {
375        Self::new()
376    }
377}
378
379impl<I, K, V> TimerQueue<I, K, V> {
380    /// Construct an empty timer queue.
381    #[must_use]
382    pub fn new() -> Self {
383        Self {
384            brand: Arc::new(QueueBrand),
385            heap: BinaryHeap::new(),
386            current: GenMap::default(),
387            next_generation: 1,
388            next_sequence: 0,
389            stale_possible: false,
390        }
391    }
392
393    /// Number of current keyed schedules, excluding stale heap entries.
394    #[must_use]
395    pub fn len(&self) -> usize {
396        self.current.len()
397    }
398
399    /// Whether no key is currently scheduled.
400    #[must_use]
401    pub fn is_empty(&self) -> bool {
402        self.current.is_empty()
403    }
404}
405
406impl<I, K, V> TimerQueue<I, K, V>
407where
408    I: Copy + Ord,
409    K: Clone + Eq + Hash,
410{
411    /// Schedule or replace one keyed value.
412    ///
413    /// # Errors
414    ///
415    /// Returns [`ScheduleError::GenerationExhausted`] or
416    /// [`ScheduleError::SequenceExhausted`] with the complete input when the
417    /// corresponding counter has no next value. Rejection leaves the queue
418    /// unchanged.
419    ///
420    #[inline]
421    pub fn schedule(
422        &mut self,
423        key: K,
424        at: I,
425        value: V,
426    ) -> Result<Token<K>, ScheduleError<I, K, V>> {
427        let Some(next_generation) = self.next_generation.checked_add(1) else {
428            return Err(ScheduleError::GenerationExhausted { key, at, value });
429        };
430        let Some(next_sequence) = self.next_sequence.checked_add(1) else {
431            return Err(ScheduleError::SequenceExhausted { key, at, value });
432        };
433
434        let generation = self.next_generation;
435        let sequence = self.next_sequence;
436        self.next_generation = next_generation;
437        self.next_sequence = next_sequence;
438        if self.current.insert(key.clone(), generation).is_some() {
439            // A replacement: the superseded generation stays in the heap.
440            self.stale_possible = true;
441        }
442        self.heap.push(Reverse(Entry {
443            at,
444            sequence,
445            generation,
446            key: key.clone(),
447            value,
448        }));
449        // Bound the heap while the queue is growing: replace-heavy phases
450        // accumulate stale generations that would otherwise peak at the full
451        // schedule count. The check is amortized over `COMPACT_INTERVAL`
452        // schedules so the fresh-key path pays one AND+branch; the peak bound
453        // then slackens by at most `COMPACT_INTERVAL` entries.
454        if self.next_sequence & (COMPACT_INTERVAL - 1) == 0 {
455            self.compact();
456        }
457        Ok(Token {
458            brand: Arc::clone(&self.brand),
459            key,
460            generation,
461        })
462    }
463
464    /// Cancel exactly the generation named by `token`.
465    ///
466    /// Tokens are branded by their issuing queue: a token from another queue
467    /// never cancels here, regardless of key and generation.
468    #[inline]
469    pub fn cancel(&mut self, token: &Token<K>) -> bool {
470        if !Arc::ptr_eq(&self.brand, &token.brand) {
471            return false;
472        }
473        if self.current.cancel(&token.key, token.generation) {
474            // The cancelled entry remains in the heap until it surfaces.
475            self.stale_possible = true;
476            true
477        } else {
478            false
479        }
480    }
481
482    /// Return the earliest current deadline, removing stale heap entries.
483    #[inline]
484    pub fn next_deadline(&mut self) -> Option<I> {
485        self.discard_stale();
486        self.heap.peek().map(|entry| entry.0.at)
487    }
488
489    /// Pop one current timer due at or before `now`.
490    #[inline]
491    pub fn pop_due(&mut self, now: I) -> Option<Expired<I, K, V>> {
492        self.discard_stale();
493        if self.heap.peek().is_none_or(|entry| entry.0.at > now) {
494            return None;
495        }
496        let Reverse(entry) = self.heap.pop()?;
497        self.current.remove(&entry.key);
498        // Drain-release: once every key is popped the buffers still pin the
499        // peak capacity. `compact()` covers the stale path; this covers the
500        // clean path where `discard_stale` returns before calling it.
501        if self.current.is_empty() {
502            self.current.shrink_to_fit();
503            self.heap.shrink_to_fit();
504        }
505        Some(Expired {
506            at: entry.at,
507            key: entry.key,
508            value: entry.value,
509        })
510    }
511
512    /// Remove stale heap entries once they outnumber the live schedules and
513    /// release oversized buffers after a full drain.
514    ///
515    /// Lazy top-of-heap discard bounds nothing: replace-heavy workloads leave
516    /// every superseded generation in the heap until it happens to surface.
517    /// Once the heap exceeds twice the live count, rebuild it from the
518    /// generation index in O(n) and shrink the buffer, bounding memory to
519    /// ~2x live entries. The retained entries are exactly those the discard
520    /// loop would eventually pop, so ordering and firing semantics are
521    /// unchanged.
522    ///
523    /// When every key has been drained or cancelled, both containers still
524    /// pin the peak capacity; release it so a long-lived queue does not
525    /// retain a workload's peak footprint.
526    #[inline]
527    fn compact(&mut self) {
528        // Compaction triggers when stale entries outnumber live ones, i.e.
529        // `heap > 2 * live`. Every live key has exactly one heap entry, so
530        // `checked_sub` cannot underflow; on the impossible underflow path,
531        // skip compaction (the safe direction).
532        let Some(stale) = self.heap.len().checked_sub(self.current.len()) else {
533            return;
534        };
535        if stale > self.current.len() {
536            let mut vec = mem::take(&mut self.heap).into_vec();
537            vec.retain(|Reverse(entry)| self.current.get(&entry.key) == Some(&entry.generation));
538            vec.shrink_to_fit();
539            self.heap = BinaryHeap::from(vec);
540            // The rebuild discarded every stale entry.
541            self.stale_possible = false;
542        }
543        if self.current.is_empty() {
544            self.current.shrink_to_fit();
545            self.heap.shrink_to_fit();
546        }
547    }
548
549    #[inline]
550    fn discard_stale(&mut self) {
551        // `stale_possible` is false only when no stale entry can exist, so the
552        // clean path skips both the compaction arithmetic and the per-pop
553        // generation lookup. A live top does not imply the heap is clean
554        // (stale entries lurk deeper), so the flag clears only when the heap
555        // empties or a rebuild removes them.
556        if !self.stale_possible {
557            return;
558        }
559        self.compact();
560        while self
561            .heap
562            .peek()
563            .is_some_and(|entry| self.current.get(&entry.0.key) != Some(&entry.0.generation))
564        {
565            self.heap.pop();
566        }
567        if self.heap.is_empty() {
568            self.stale_possible = false;
569        }
570    }
571}
572
573#[cfg(test)]
574mod tests {
575    #![allow(
576        clippy::cast_possible_truncation,
577        reason = "tests deliberately truncate u64 RNG outputs to small key/now ranges"
578    )]
579    use super::*;
580    use std::collections::{BTreeMap, BTreeSet};
581
582    /// Deterministic xorshift64* generator.
583    struct Rng(u64);
584
585    impl Rng {
586        fn next(&mut self) -> u64 {
587            let mut x = self.0;
588            x ^= x >> 12;
589            x ^= x << 25;
590            x ^= x >> 27;
591            self.0 = x;
592            x.wrapping_mul(0x2545_F491_4F6C_DD1D)
593        }
594    }
595
596    /// Differential test: the scheduler against a BTreeSet/BTreeMap reference
597    /// model over a seeded stream of schedules, replaces, cancels, and pops.
598    /// The model orders by `(at, generation)`, which is the queue's
599    /// equal-deadline schedule order (generation increases exactly once per
600    /// schedule).
601    #[test]
602    fn differential_against_reference_model() {
603        // Multiple seeds broaden coverage of hash-layout-dependent bugs (the
604        // tombstone load-factor hang was seed-dependent).
605        for seed in [
606            0xDEAD_BEEF_1234_u64,
607            0x00C0_FFEE_0001,
608            0x5EED_5EED_5EED,
609            0x0102_0304_0506,
610        ] {
611            differential_run(seed);
612        }
613    }
614
615    #[allow(
616        clippy::too_many_lines,
617        reason = "the differential test enumerates every op type and phase explicitly"
618    )]
619    fn differential_run(seed: u64) {
620        const KEYS: usize = 64;
621        // Tombstone-sweep parameters (used after the main drain).
622        const STRESS_KEYS: usize = 1024;
623        const STRESS_BASE: u64 = 1_000_000;
624        let mut rng = Rng(seed);
625        let mut queue = TimerQueue::new();
626        let mut tokens: Vec<Option<Token<u64>>> = vec![None; KEYS];
627        // Reference model: per-key live schedule and a set ordered by deadline.
628        let mut live: BTreeMap<u64, (u64, u64, u64)> = BTreeMap::new(); // key -> (at, gen, value)
629        let mut by_deadline: BTreeSet<(u64, u64, u64)> = BTreeSet::new(); // (at, gen, key)
630        let mut modelpopped_gen = 0_u64;
631
632        // Keep the same seeded state machine under Miri, but bound the
633        // interpreter run. Native CI retains the full eight-million-operation
634        // differential plus tombstone sweep.
635        let operations = if cfg!(miri) { 5_000 } else { 50_000 };
636        for _ in 0..operations {
637            let key = (rng.next() % KEYS as u64) as usize;
638            let roll = rng.next() % 10;
639            match roll {
640                0..=5 => {
641                    let at = rng.next() % 100;
642                    let value = rng.next();
643                    let token = queue.schedule(key as u64, at, value).unwrap();
644                    tokens[key] = Some(token);
645                    modelpopped_gen += 1;
646                    if let Some(old) = live.insert(key as u64, (at, modelpopped_gen, value)) {
647                        by_deadline.remove(&(old.0, old.1, key as u64));
648                    }
649                    by_deadline.insert((at, modelpopped_gen, key as u64));
650                }
651                6..=7 => {
652                    if let Some(token) = tokens[key].as_ref() {
653                        let got = queue.cancel(token);
654                        let expected = live
655                            .get(&(key as u64))
656                            .is_some_and(|&(_, g, _)| g == token.generation);
657                        assert_eq!(got, expected, "cancel mismatch for key {key}");
658                        if got {
659                            tokens[key] = None;
660                            if let Some(old) = live.remove(&(key as u64)) {
661                                by_deadline.remove(&(old.0, old.1, key as u64));
662                            }
663                        }
664                    }
665                }
666                8..=9 => {
667                    let now = rng.next() % 100;
668                    let got = queue.pop_due(now);
669                    let expected = by_deadline.first().copied().filter(|&(at, _, _)| at <= now);
670                    match (got, expected) {
671                        (Some(expired), Some((at, popped_gen, k))) => {
672                            let (_, _, v) = live[&k];
673                            assert_eq!((expired.at, expired.key, expired.value), (at, k, v));
674                            by_deadline.remove(&(at, popped_gen, k));
675                            live.remove(&k);
676                        }
677                        (None, None) => {}
678                        (got, expected) => {
679                            panic!("pop_due mismatch: got {got:?}, expected {expected:?}")
680                        }
681                    }
682                    let nd = queue.next_deadline();
683                    assert_eq!(
684                        nd,
685                        by_deadline.first().map(|&(at, _, _)| at),
686                        "next_deadline mismatch after pop at now={now}"
687                    );
688                }
689                _ => unreachable!(),
690            }
691            assert_eq!(queue.len(), live.len(), "live-count mismatch after op");
692        }
693
694        // Final full drain must empty both in the same order.
695        while let Some(expired) = queue.pop_due(u64::MAX) {
696            let (at, _seq_gen, k) = by_deadline.pop_first().expect("model exhausted early");
697            assert_eq!(expired.at, at);
698            assert_eq!(expired.key, k);
699        }
700        assert!(by_deadline.is_empty(), "model should be empty after drain");
701        assert!(queue.is_empty());
702
703        // Tombstone stress: schedule-then-cancel sweeps over a wide key
704        // range. The map's occupied count stays near zero while tombstones
705        // from many distinct keys accumulate; a growth condition that
706        // ignores tombstones lets the probe table fill and the probes spin
707        // forever (caught as a 600x mixed-workload slowdown before the
708        // fix). The queue must stay empty throughout the sweep.
709        let stress_rounds = if cfg!(miri) { 20 } else { 2_000 };
710        let stress_keys = if cfg!(miri) { 64 } else { STRESS_KEYS };
711        for round in 0..stress_rounds {
712            for key in 0..stress_keys {
713                let s_key = STRESS_BASE + u64::try_from(key).expect("key fits u64");
714                let token = queue.schedule(s_key, round % 100, round).unwrap();
715                assert!(queue.cancel(&token), "sweep cancel must succeed");
716            }
717            assert_eq!(
718                queue.len(),
719                0,
720                "sweep must leave nothing live at round {round}"
721            );
722        }
723        assert!(
724            queue.next_deadline().is_none(),
725            "all sweep entries are stale; deadline must be none"
726        );
727    }
728
729    /// `&str` keys exercise the non-integer hash path of the generation map.
730    #[test]
731    fn str_keys_schedule_replace_cancel_pop() {
732        let mut queue = TimerQueue::new();
733        let old = queue.schedule("actor", 10_u64, "old").unwrap();
734        let new = queue.schedule("actor", 20, "new").unwrap();
735        assert!(!queue.cancel(&old));
736        assert_eq!(queue.next_deadline(), Some(20));
737        assert_eq!(queue.pop_due(19), None);
738        assert_eq!(queue.pop_due(20).unwrap().value, "new");
739        assert!(!queue.cancel(&new));
740    }
741
742    #[test]
743    fn generation_exhaustion_returns_input_and_preserves_queue_state() {
744        let mut queue = TimerQueue::new();
745        let existing = queue
746            .schedule(String::from("existing"), 11_u64, String::from("kept"))
747            .unwrap();
748        queue.next_generation = u64::MAX;
749        queue.next_sequence = 17;
750
751        let error = queue
752            .schedule(String::from("actor"), 23_u64, String::from("payload"))
753            .unwrap_err();
754
755        assert_eq!(
756            error,
757            ScheduleError::GenerationExhausted {
758                key: String::from("actor"),
759                at: 23,
760                value: String::from("payload"),
761            }
762        );
763        assert_eq!(queue.next_generation, u64::MAX);
764        assert_eq!(queue.next_sequence, 17);
765        assert_eq!(queue.current.len(), 1);
766        assert_eq!(
767            queue.current.get(existing.key()),
768            Some(&existing.generation)
769        );
770        assert_eq!(queue.heap.len(), 1);
771        assert!(!queue.stale_possible);
772        assert_eq!(
773            queue.pop_due(11),
774            Some(Expired {
775                at: 11,
776                key: String::from("existing"),
777                value: String::from("kept"),
778            })
779        );
780    }
781
782    #[test]
783    fn sequence_exhaustion_returns_input_without_advancing_generation() {
784        let mut queue = TimerQueue::new();
785        queue.next_generation = 41;
786        queue.next_sequence = u64::MAX;
787
788        let error = queue.schedule("actor", 23_u64, "payload").unwrap_err();
789
790        assert_eq!(
791            error,
792            ScheduleError::SequenceExhausted {
793                key: "actor",
794                at: 23,
795                value: "payload",
796            }
797        );
798        assert_eq!(queue.next_generation, 41);
799        assert_eq!(queue.next_sequence, u64::MAX);
800        assert!(queue.current.is_empty());
801        assert!(queue.heap.is_empty());
802        assert!(!queue.stale_possible);
803    }
804
805    #[test]
806    fn failed_replacement_leaves_existing_schedule_current() {
807        let mut queue = TimerQueue::new();
808        let token = queue.schedule("actor", 10_u64, "existing").unwrap();
809        queue.next_sequence = u64::MAX;
810
811        assert_eq!(
812            queue.schedule("actor", 20, "replacement"),
813            Err(ScheduleError::SequenceExhausted {
814                key: "actor",
815                at: 20,
816                value: "replacement",
817            })
818        );
819        assert_eq!(queue.current.get(token.key()), Some(&token.generation));
820        assert_eq!(queue.next_deadline(), Some(10));
821        assert_eq!(
822            queue.pop_due(10),
823            Some(Expired {
824                at: 10,
825                key: "actor",
826                value: "existing",
827            })
828        );
829    }
830
831    #[test]
832    fn successful_schedule_returns_exact_queue_branded_token() {
833        let mut queue = TimerQueue::new();
834
835        let token = queue.schedule("actor", 10_u64, "value").unwrap();
836
837        assert!(Arc::ptr_eq(&token.brand, &queue.brand));
838        assert_eq!(token.key, "actor");
839        assert_eq!(token.generation, 1);
840        assert!(queue.cancel(&token));
841    }
842}