structured_asn1/memory/
sort.rs

1//! Iterative sorting with fallible comparisons and pre-admitted moves.
2
3use core::cmp::Ordering;
4
5use super::{MemoryError, Work};
6
7/// A refused sort, preserving the comparator's own error and provenance.
8#[derive(Debug, PartialEq, Eq)]
9pub enum SortError<E> {
10    /// The sort could not admit its own comparison dispatch or value movement.
11    Resource(MemoryError),
12    /// The caller's fallible comparison refused further processing.
13    Comparison(E),
14}
15
16impl From<SortError<MemoryError>> for MemoryError {
17    fn from(error: SortError<MemoryError>) -> Self {
18        match error {
19            SortError::Resource(reason) | SortError::Comparison(reason) => reason,
20        }
21    }
22}
23
24pub(super) fn sort<T, E, W: Work>(
25    values: &mut [T],
26    memory: &W,
27    mut compare: impl FnMut(&T, &T) -> Result<Ordering, E>,
28) -> Result<(), SortError<E>> {
29    for root in (0..values.len() / 2).rev() {
30        sift(values, root, values.len(), memory, &mut compare)?;
31    }
32    for end in (1..values.len()).rev() {
33        exchange(values, 0, end, memory).map_err(SortError::Resource)?;
34        sift(values, 0, end, memory, &mut compare)?;
35    }
36    Ok(())
37}
38
39fn sift<T, E, W: Work>(
40    values: &mut [T],
41    mut root: usize,
42    end: usize,
43    memory: &W,
44    compare: &mut impl FnMut(&T, &T) -> Result<Ordering, E>,
45) -> Result<(), SortError<E>> {
46    while root < end / 2 {
47        // root < end/2 proves both the multiplication and child are in range.
48        let mut child = root * 2 + 1;
49        memory.charge_work(1).map_err(SortError::Resource)?;
50        if child + 1 < end {
51            memory.charge_work(1).map_err(SortError::Resource)?;
52            if compare(&values[child], &values[child + 1]).map_err(SortError::Comparison)?
53                == Ordering::Less
54            {
55                child += 1;
56            }
57        }
58        memory.charge_work(1).map_err(SortError::Resource)?;
59        if compare(&values[root], &values[child]).map_err(SortError::Comparison)? != Ordering::Less
60        {
61            break;
62        }
63        exchange(values, root, child, memory).map_err(SortError::Resource)?;
64        root = child;
65    }
66    Ok(())
67}
68
69fn exchange<T, W: Work>(
70    values: &mut [T],
71    left: usize,
72    right: usize,
73    memory: &W,
74) -> Result<(), MemoryError> {
75    let cost = (core::mem::size_of::<T>() as u64)
76        .checked_mul(2)
77        .and_then(|bytes| bytes.checked_add(1))
78        .ok_or(MemoryError::WorkExceeded)?;
79    memory.charge_work(cost)?;
80    values.swap(left, right);
81    Ok(())
82}
structured_asn1/memory/sort.rs

structured_asn1/memory/
sort.rs
