use alloc::collections::{BTreeMap, BTreeSet};
use core::time::Duration;
#[derive(Clone, Debug)]
pub struct Pending<T> {
next: u64,
capacity: usize,
entries: BTreeMap<u64, Slot<T>>,
deadlines: BTreeSet<(Duration, u64)>,
}
#[derive(Clone, Debug)]
struct Slot<T> {
deadline: Option<Duration>,
value: T,
}
impl<T> Pending<T> {
#[must_use]
pub fn new(capacity: usize) -> Self {
Self {
next: 1,
capacity: capacity.max(1),
entries: BTreeMap::new(),
deadlines: BTreeSet::new(),
}
}
#[inline]
#[must_use]
pub const fn capacity(&self) -> usize {
self.capacity
}
#[inline]
#[must_use]
pub fn len(&self) -> usize {
self.entries.len()
}
#[inline]
#[must_use]
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
#[inline]
#[must_use]
pub fn contains(&self, id: u64) -> bool {
self.entries.contains_key(&id)
}
#[must_use]
pub fn get(&self, id: u64) -> Option<&T> {
self.entries.get(&id).map(|slot| &slot.value)
}
pub fn issue(&mut self, value: T, deadline: Option<Duration>) -> (u64, Option<(u64, T)>) {
let evicted = if self.entries.len() >= self.capacity {
self.entries.pop_first().map(|(id, slot)| {
self.forget_deadline(id, slot.deadline);
(id, slot.value)
})
} else {
None
};
let mut id = self.next;
while id == 0 || self.entries.contains_key(&id) {
id = id.wrapping_add(1);
}
self.next = id.wrapping_add(1);
if let Some(at) = deadline {
let _fresh = self.deadlines.insert((at, id));
}
let _vacant = self.entries.insert(id, Slot { deadline, value });
(id, evicted)
}
pub fn settle(&mut self, id: u64) -> Option<T> {
let slot = self.entries.remove(&id)?;
self.forget_deadline(id, slot.deadline);
Some(slot.value)
}
pub fn pop_expired(&mut self, now: Duration) -> Option<(u64, T)> {
let &(at, id) = self.deadlines.first()?;
if at > now {
return None;
}
let _removed = self.deadlines.pop_first();
self.entries.remove(&id).map(|slot| (id, slot.value))
}
#[must_use]
pub fn next_deadline(&self) -> Option<Duration> {
self.deadlines.first().map(|&(at, _)| at)
}
pub fn drain(&mut self) -> impl Iterator<Item = (u64, T)> + use<T> {
self.deadlines.clear();
core::mem::take(&mut self.entries)
.into_iter()
.map(|(id, slot)| (id, slot.value))
}
fn forget_deadline(&mut self, id: u64, deadline: Option<Duration>) {
if let Some(at) = deadline {
let _was_there = self.deadlines.remove(&(at, id));
}
}
}
#[cfg(test)]
#[allow(clippy::panic)]
mod tests {
use alloc::vec::Vec;
use proptest::prelude::*;
use super::*;
#[derive(Default)]
struct Model {
next: u64,
entries: Vec<(u64, Option<Duration>, u32)>,
}
#[derive(Clone, Debug)]
enum Op {
Issue(u32, Option<u8>),
Settle(u8),
Expire(u8),
}
fn op() -> impl Strategy<Value = Op> {
prop_oneof![
(any::<u32>(), proptest::option::of(any::<u8>())).prop_map(|(v, d)| Op::Issue(v, d)),
any::<u8>().prop_map(Op::Settle),
any::<u8>().prop_map(Op::Expire),
]
}
proptest! {
#[test]
fn prop_matches_reference(capacity in 1usize..8, ops in proptest::collection::vec(op(), 0..200)) {
let mut real = Pending::new(capacity);
let mut model = Model { next: 1, ..Model::default() };
for op in ops {
match op {
Op::Issue(value, deadline) => {
let deadline = deadline.map(|d| Duration::from_millis(u64::from(d)));
let expected_evicted = (model.entries.len() >= capacity).then(|| {
let (id, _, v) = model.entries.remove(0);
(id, v)
});
let id = model.next;
model.next += 1;
model.entries.push((id, deadline, value));
prop_assert_eq!(real.issue(value, deadline), (id, expected_evicted));
}
Op::Settle(back) => {
let id = model.next.saturating_sub(u64::from(back % 10));
let expected = model.entries.iter().position(|e| e.0 == id).map(|i| model.entries.remove(i).2);
prop_assert_eq!(real.settle(id), expected);
}
Op::Expire(now) => {
let now = Duration::from_millis(u64::from(now));
let due = model
.entries
.iter()
.enumerate()
.filter_map(|(i, e)| e.1.filter(|&d| d <= now).map(|d| (d, e.0, i)))
.min();
let expected = due.map(|(_, _, i)| {
let e = model.entries.remove(i);
(e.0, e.2)
});
prop_assert_eq!(real.pop_expired(now), expected);
}
}
prop_assert_eq!(real.len(), model.entries.len());
prop_assert!(real.len() <= capacity);
let next_deadline = model.entries.iter().filter_map(|e| e.1).min();
prop_assert_eq!(real.next_deadline(), next_deadline);
}
}
}
#[test]
fn test_scale_settle_out_of_order_is_log_time() {
const N: u64 = 200_000;
let mut p = Pending::new(N as usize);
for i in 0..N {
let _issued = p.issue(i, Some(Duration::from_nanos(i * 7 % 1000)));
}
let mut settled = 0u64;
for k in 0..N {
let id = (k * 7919) % N + 1; if p.settle(id).is_some() {
settled += 1;
}
}
assert_eq!(settled, N);
assert!(p.is_empty());
assert_eq!(p.next_deadline(), None);
}
#[test]
fn test_scale_eviction_keeps_capacity() {
let mut p = Pending::new(1000);
let mut evicted = 0;
for i in 0..150_000u32 {
if p.issue(i, None).1.is_some() {
evicted += 1;
}
}
assert_eq!(p.len(), 1000);
assert_eq!(evicted, 149_000);
}
}