search

rust-embedded / heapless

Heapless, `static` friendly data structures
Apache License 2.0
1.47k stars 178 forks source link

Add const-erased versions of the various containers #371

Open sosthene-nitrokey opened 1 year ago

sosthene-nitrokey commented 1 year ago

Making code flexible around heapless structures can be a bit verbose because it requires being generic over the capacity of each collection. This could be helped by providing versions of the structures with the const erased. This would allow removing the generics in some cases.

For example, heapless::Vec currently is :

pub struct Vec<T, const N: usize> {
    len: usize,
    buffer: [MaybeUninit<T>; N],
}

It should be possible to provide a struct that goes hand in hand with it:

pub struct VecView<'a, T> {
    len: &'a mut len,
    buffer: &mut [MaybeUninit<T>],
}

impl<T, const N: usize> Vec<T, N> {
    fn as_view(&mut self) -> VecView<'_, T> {
        VecView { len: &mut self.len, buffer: &mut self.buffer }
    }
}

With VecView implementing most of the API that Vec currently implements. This would allow for example methods that write data to an outbuffer of type &mut Vec<T, N> to instead take a parameter VecView<'_, T>.

Something like:

fn do_something<const N: usize>(response_buffer: &mut Vec<u8, N>)

could become 

fn do_something(response_buffer: VecView<'_, u8>)

In a trait for example this would also have the advantage of making it object-safe.

I believe this pattern:

  1. Improve ergonomics
  2. Might reduce compilation time and binary size because of monomorphisation (unverified)
sosthene-nitrokey commented 1 month ago

Types:

IndexMap and IndexSet

IndexSet depends on the View type for IndexMap being available.

IndexMap is currently implemented with a CoreMaptype that looks like:

struct CoreMap<K, V, const N: usize> {
    entries: Vec<Bucket<K, V>, N>,
    indices: [Option<Pos>; N],
}

It is not possible to construct a View for this type like for Vec since the N would have to be erased twice.

We could solve that issue by "inlining" the indices into the entries:

struct CoreMap<K, V, const N: usize> {
    entries_indices: [(MaybeUninit<Bucket<K, V>>, Option<Pos>); N],
    len: usize,
}

Then only one N needs to be erased, and this can be implemented. However this requires changing the implementation significantly.

It might even be possible to get rid of the len field (I think an entry is initialized if and only if a index points to it, and only one index can point to it at a given time?).

sosthene-nitrokey commented 1 month ago

There are cases where some adjacent structures have the const generic that could be removed thanks to this implementation. Would it be worth making breaking changes to remove this const generic?