1use 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
11const COMPACT_INTERVAL: u64 = 1024;
13
14struct QueueBrand;
21
22#[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 #[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#[derive(Debug, Clone, PartialEq, Eq)]
94pub struct Expired<I, K, V> {
95 pub at: I,
97 pub key: K,
99 pub value: V,
101}
102
103#[derive(Debug, Clone, PartialEq, Eq)]
105pub enum ScheduleError<I, K, V> {
106 GenerationExhausted { key: K, at: I, value: V },
108 SequenceExhausted { key: K, at: I, value: V },
110}
111
112struct GenMap<K> {
120 keys: Vec<Option<K>>,
121 gens: Vec<u64>,
122 len: usize,
124 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 #[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 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 fn delete_at(&mut self, i: usize, mask: usize)
268 where
269 K: Hash,
270 {
271 let mut i = i;
272 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 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 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 if self.len == 0 {
351 self.keys = Vec::new();
352 self.gens = Vec::new();
353 self.grow_threshold = 0;
354 }
355 }
356}
357
358pub 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 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 #[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 #[must_use]
395 pub fn len(&self) -> usize {
396 self.current.len()
397 }
398
399 #[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 #[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 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 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 #[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 self.stale_possible = true;
476 true
477 } else {
478 false
479 }
480 }
481
482 #[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 #[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 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 #[inline]
527 fn compact(&mut self) {
528 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 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 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 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 #[test]
602 fn differential_against_reference_model() {
603 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 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 let mut live: BTreeMap<u64, (u64, u64, u64)> = BTreeMap::new(); let mut by_deadline: BTreeSet<(u64, u64, u64)> = BTreeSet::new(); let mut modelpopped_gen = 0_u64;
631
632 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 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 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 #[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}