Struct OrderedPool

pub struct OrderedPool<T: PriorityLevel, const N: usize, const L: usize> {
    pub entries: ArrayVec<T, N>,
    pub sorted: ArrayVec<u16, N>,
}

An owned heapless container with capacity N that maintains order both through properties of its entries and by time of access.

Operations that are supposed to be fast are:

• Finding an element by iteration
• Moving that element to the front of its relevant level

There is no remove an item; instead, the &mut T of Self::lookup can be replaced with a low-priority placeholder value. (In fact, future iterations may require that such a value exists and is Default).

Usage

use coapcore::oluru::{OrderedPool, PriorityLevel};

#[derive(Debug)]
struct MyValue {
    id: u32,
    name: Option<&'static str>,
}

impl PriorityLevel for MyValue {
    fn level(&self) -> usize {
        if self.name.is_some() {
            0
        } else {
            1
        }
    }
}

// A cache with a capacity of three.
type MyCache = OrderedPool<MyValue, 3, 2>;

// Create an empty cache, then insert some items.
let mut cache = MyCache::new();
cache.insert(MyValue { id: 1, name: Some("Mercury") });
cache.insert(MyValue { id: 2, name: Some("Venus") });
cache.insert(MyValue { id: 3, name: None });

let item = cache.lookup(|x| x.id == 1, |x| format!("Found {}", x.name.unwrap_or("unnamed object")));
assert_eq!(item.unwrap().as_str(), "Found Mercury");

// If the cache is full, inserting a new item evicts one item.
//
// While Venus (ID 2) was used least recently, it has higher priority than the no-name planet
// with index 3, so that gets evicted first instead.
let returned = cache.insert(MyValue { id: 4, name: Some("Mars") });
assert!(returned.expect("Pool was full").is_some_and(|item| item.id == 3));

Implementation

Right now, this is implemented as a separate entry vector and an index vector, where the latter is often rotated internally. Future changes may change this to only be a single list, using a doubly linked list, and keeping head indices of each level (which is why the number of levels L is part of the type).

The value list following the style of a Vec means that popping elements from anywhere but the tail is costly, which it should better not be; a slab allocator style would improve that.

Terminology

A “position” is a key to .sorted. An “index” is a key to .entries (and thus a value of .sorted).

Invariants

Before and after any public function, these hold:

• .sorted has the same length as .entries
• .sorted is a permutation of .entries’ (and thus its) index space. Therefore, each of its values is unique, and is an index into .entries.
• If T::level is constant, self.sorted.iter().map(|i| self.entries[i].level()) is sorted.

Fields

entries: ArrayVec<T, N>

Elements without regard for ordering

sorted: ArrayVec<u16, N>

A sorted list of indices into entries: high priority first, ties broken by recentness

Implementations

impl<T: PriorityLevel, const N: usize, const L: usize> OrderedPool<T, N, L>

pub const fn new() -> Self

Create an empty cache.

pub fn lookup<Ftest, Fuse, R>( &mut self, f_test: Ftest, f_use: Fuse, ) -> Option<R>

where Ftest: FnMut(&T) -> bool, Fuse: FnOnce(&mut T) -> R,

Iterate over items from highest priority to lowest, most recently used first.

If the function f_test (which receives a shared reference to the entry) returns Some(r), f_use is called with a mutable reference to the item as well as the first function’s result. That item is regarded as “used” and thus shifted to the front, and the second function’s return value is passed on.

This differs from uluru in two ways:

• There is no find() method: As the level may change through mutation, we can not hand out a &mut T unless we can sure to process any level changes when it is returned. (A linear type drop guard wrapper may afford that, but is not available in Rust at the time of writing)
• The callback is split in a test part and a use part, which ensures that elements that are not looked up do not get mutated; only the selected item is mutated and will then be sorted in correctly.

pub fn insert(&mut self, new: T) -> Result<Option<T>, T>

Inserts an element.

If the new element’s priority is lower than the lowest in the queue, it is returned as an Err. Otherwise, the element is inserted, and any dropped lower priority element is returned in the Ok value.

pub fn force_insert(&mut self, new: T) -> Option<T>

Inserts an element without regard for its level.

The element is inserted unconditionally, and the least priority element is returned by value.

pub fn iter(&self) -> impl Iterator<Item = &T>

Returns an iterator visiting all items in arbitrary order.

Trait Implementations

impl<T: Debug + PriorityLevel, const N: usize, const L: usize> Debug for OrderedPool<T, N, L>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: PriorityLevel, const N: usize, const L: usize> Default for OrderedPool<T, N, L>

fn default() -> Self

Returns the “default value” for a type.