use super::queued_request::QueuedRequest;
use crate::common::log::log_def::LogType;
use std::collections::HashMap;
use tokio_util::sync::CancellationToken;
pub(super) struct IndexedHeap {
items: Vec<QueuedRequest>,
positions: HashMap<CancellationToken, usize>,
#[cfg(test)]
work: usize,
#[cfg(test)]
reserve_capacity_overflow: bool,
}
impl IndexedHeap {
pub(super) fn new() -> Self {
Self {
items: Vec::new(),
positions: HashMap::new(),
#[cfg(test)]
work: 0,
#[cfg(test)]
reserve_capacity_overflow: false,
}
}
pub(super) fn len(&self) -> usize {
self.items.len()
}
pub(super) fn contains(&self, token: &CancellationToken) -> bool {
self.positions.contains_key(token)
}
#[allow(clippy::result_large_err)]
pub(super) fn push(&mut self, request: QueuedRequest) -> Result<(), QueuedRequest> {
let additional = 1;
#[cfg(test)]
let additional = if std::mem::take(&mut self.reserve_capacity_overflow) {
usize::MAX
} else {
additional
};
if self.contains(&request.dispatch_cancel)
|| self.items.try_reserve(additional).is_err()
|| self.positions.try_reserve(additional).is_err()
{
crate::log_e!(LogType::WSC; "ws.indexed_heap.push", "arg_request_bytes|arg_request_attempt|arg_request_sequence|error", request.message.len(), request.attempt, request.sequence, "duplicate_dispatch_or_allocation_failed");
return Err(request);
}
let index = self.items.len();
self.positions
.insert(request.dispatch_cancel.clone(), index);
self.items.push(request);
self.sift_up(index);
Ok(())
}
pub(super) fn remove(&mut self, token: &CancellationToken) -> Option<QueuedRequest> {
let index = *self.positions.get(token)?;
if !self
.items
.get(index)
.is_some_and(|item| item.dispatch_cancel == *token)
{
crate::log_e!(LogType::WSC; "ws.indexed_heap.remove", "arg_token_present|error", true, "invalid_dispatch_index");
return None;
}
let last_index = self.items.len().checked_sub(1)?;
let last = self.items.pop()?;
if index == last_index {
self.positions.remove(token);
return Some(last);
}
let Some(slot) = self.items.get_mut(index) else {
self.items.push(last);
crate::log_e!(LogType::WSC; "ws.indexed_heap.remove", "arg_token_present|error", true, "missing_replacement_slot");
return None;
};
let removed = std::mem::replace(slot, last);
self.positions.remove(token);
if let Some(position) = self.positions.get_mut(&slot.dispatch_cancel) {
*position = index;
} else {
self.positions.insert(slot.dispatch_cancel.clone(), index);
crate::log_e!(LogType::WSC; "ws.indexed_heap.remove", "arg_token_present|error", true, "replacement_index_recovered");
}
if index
.checked_sub(1)
.is_some_and(|parent| self.greater(index, parent / 2))
{
self.sift_up(index);
} else {
self.sift_down(index);
}
Some(removed)
}
pub(super) fn pop(&mut self) -> Option<QueuedRequest> {
let token = self.items.first()?.dispatch_cancel.clone();
self.remove(&token)
}
pub(super) fn drain(&mut self) -> Vec<QueuedRequest> {
self.positions.clear();
std::mem::take(&mut self.items)
}
fn greater(&mut self, left: usize, right: usize) -> bool {
#[cfg(test)]
{
self.work = self.work.saturating_add(1);
}
match (self.items.get(left), self.items.get(right)) {
(Some(left), Some(right)) => left > right,
_ => {
crate::log_e!(LogType::WSC; "ws.indexed_heap.greater", "left|right|error", left, right, "invalid_node_index");
false
}
}
}
fn swap(&mut self, left: usize, right: usize) -> bool {
if left == right {
return true;
}
let Ok([left_item, right_item]) = self.items.get_disjoint_mut([left, right]) else {
crate::log_e!(LogType::WSC; "ws.indexed_heap.swap", "left|right|error", left, right, "invalid_swap_indices");
return false;
};
std::mem::swap(left_item, right_item);
if let Some(position) = self.positions.get_mut(&left_item.dispatch_cancel) {
*position = left;
}
if let Some(position) = self.positions.get_mut(&right_item.dispatch_cancel) {
*position = right;
}
#[cfg(test)]
{
self.work = self.work.saturating_add(1);
}
true
}
fn sift_up(&mut self, mut index: usize) {
while let Some(parent) = index.checked_sub(1).map(|value| value / 2) {
if !self.greater(index, parent) || !self.swap(index, parent) {
break;
}
index = parent;
}
}
fn sift_down(&mut self, mut index: usize) {
while let Some(left) = index.checked_mul(2).and_then(|value| value.checked_add(1)) {
if self.items.get(left).is_none() {
break;
}
let larger = match left.checked_add(1) {
Some(right) if self.items.get(right).is_some() && self.greater(right, left) => {
right
}
_ => left,
};
if !self.greater(larger, index) || !self.swap(index, larger) {
break;
}
index = larger;
}
}
#[cfg(test)]
pub(super) fn work(&self) -> usize {
self.work
}
#[cfg(test)]
pub(super) fn reject_next_reservation(&mut self) {
self.reserve_capacity_overflow = true;
}
#[cfg(test)]
pub(super) fn valid(&self) -> bool {
self.items.len() == self.positions.len()
&& self.items.iter().enumerate().all(|(index, item)| {
self.positions.get(&item.dispatch_cancel) == Some(&index)
&& match index
.checked_sub(1)
.and_then(|value| self.items.get(value / 2))
{
Some(parent) => parent >= item,
None => index == 0,
}
})
}
}