use alloc::{collections::BinaryHeap, vec::Vec};
use core::{mem, num::NonZeroUsize};
use crate::{Deadline, Moment, Retained, RetainedBytes};
use super::scheduled::Scheduled;
use super::{
Timer, TimerDrain, TimerId, TimerLimits, TimerOwnerId, TimerQueueSnapshot, TimerScheduleError,
TimerScheduleFailure, TimerToken,
};
#[derive(Debug)]
pub struct TimerQueue<T> {
owner: TimerOwnerId,
limits: TimerLimits,
measure: fn(&T) -> RetainedBytes,
pub(super) timers: BinaryHeap<Scheduled<T>>,
next_id: Option<TimerId>,
retained: RetainedBytes,
}
impl<T: Retained> TimerQueue<T> {
pub fn new(owner: TimerOwnerId, limits: TimerLimits) -> Self {
Self::with_measure(owner, limits, T::retained_bytes)
}
pub fn starting_at(owner: TimerOwnerId, limits: TimerLimits, first_id: TimerId) -> Self {
Self::starting_at_with_measure(owner, limits, first_id, T::retained_bytes)
}
}
impl<T> TimerQueue<T> {
pub fn with_measure(
owner: TimerOwnerId,
limits: TimerLimits,
measure: fn(&T) -> RetainedBytes,
) -> Self {
Self::starting_at_with_measure(owner, limits, TimerId::ZERO, measure)
}
pub fn starting_at_with_measure(
owner: TimerOwnerId,
limits: TimerLimits,
first_id: TimerId,
measure: fn(&T) -> RetainedBytes,
) -> Self {
Self {
owner,
limits,
measure,
timers: BinaryHeap::with_capacity(limits.timers().get()),
next_id: Some(first_id),
retained: RetainedBytes::ZERO,
}
}
pub const fn owner(&self) -> TimerOwnerId {
self.owner
}
pub const fn limits(&self) -> TimerLimits {
self.limits
}
pub fn is_empty(&self) -> bool {
self.timers.is_empty()
}
pub fn len(&self) -> usize {
self.timers.len()
}
pub fn next_deadline(&self) -> Option<Deadline> {
self.timers
.peek()
.map(|scheduled| scheduled.timer.deadline())
}
pub fn schedule(
&mut self,
deadline: Deadline,
value: T,
) -> Result<TimerToken, TimerScheduleError<T>> {
if self.timers.len() >= self.limits.timers().get() {
return Err(TimerScheduleError::new(
deadline,
value,
TimerScheduleFailure::TimerCapacity {
limit: self.limits.timers(),
},
));
}
let retained = (self.measure)(&value);
let next_retained = self.check_retained(deadline, value, retained)?;
let Some(id) = self.next_id else {
return Err(TimerScheduleError::new(
deadline,
next_retained.value,
TimerScheduleFailure::TimerIdsExhausted,
));
};
let token = TimerToken::new(self.owner, id, deadline);
self.next_id = id.checked_next();
self.timers.push(Scheduled {
timer: Timer::new(token, next_retained.value, retained),
});
self.retained = next_retained.total;
Ok(token)
}
pub fn cancel(&mut self, token: TimerToken) -> Option<Timer<T>> {
if token.owner() != self.owner {
return None;
}
let mut timers = mem::take(&mut self.timers).into_vec();
let Some(index) = timers
.iter()
.position(|scheduled| scheduled.timer.token() == token)
else {
self.timers = BinaryHeap::from(timers);
return None;
};
let scheduled = timers.swap_remove(index);
self.timers = BinaryHeap::from(timers);
self.subtract_retained(scheduled.timer.measured_retained_bytes());
Some(scheduled.timer)
}
pub fn pop_due(&mut self, now: Moment) -> Option<Timer<T>> {
if !self
.next_deadline()
.is_some_and(|deadline| deadline.is_elapsed_at(now))
{
return None;
}
let scheduled = self.timers.pop()?;
self.subtract_retained(scheduled.timer.measured_retained_bytes());
Some(scheduled.timer)
}
pub fn drain_due_into(
&mut self,
now: Moment,
destination: &mut Vec<Timer<T>>,
budget: NonZeroUsize,
) -> TimerDrain {
let mut fired = 0;
while fired < budget.get() {
let Some(timer) = self.pop_due(now) else {
break;
};
destination.push(timer);
fired += 1;
}
TimerDrain::new(
fired,
self.next_deadline()
.is_some_and(|deadline| deadline.is_elapsed_at(now)),
)
}
pub fn snapshot(&self) -> TimerQueueSnapshot {
TimerQueueSnapshot::new(
self.owner,
self.limits,
self.timers.len(),
self.retained,
self.next_deadline(),
self.next_id,
)
}
fn check_retained(
&self,
deadline: Deadline,
value: T,
retained: RetainedBytes,
) -> Result<Checked<T>, TimerScheduleError<T>> {
let Some(total) = self.retained.checked_add(retained) else {
return Err(TimerScheduleError::new(
deadline,
value,
TimerScheduleFailure::RetainedByteOverflow {
current: self.retained,
timer: retained,
},
));
};
if total.get() > self.limits.retained_bytes().get() {
return Err(TimerScheduleError::new(
deadline,
value,
TimerScheduleFailure::RetainedByteCapacity {
limit: self.limits.retained_bytes(),
current: self.retained,
timer: retained,
},
));
}
Ok(Checked { value, total })
}
fn subtract_retained(&mut self, removed: RetainedBytes) {
self.retained = self
.retained
.checked_sub(removed)
.unwrap_or_else(|| panic!("timer retained-byte accounting invariant violated"));
}
}
#[derive(Debug)]
struct Checked<T> {
value: T,
total: RetainedBytes,
}