array_map/
lib.rs

1#![cfg_attr(not(test), deny(warnings, clippy::all, clippy::pedantic, clippy::cargo, missing_docs))]
2#![deny(unsafe_code)]
3#![cfg_attr(not(any(test, feature = "std")), no_std)]
4#![allow(clippy::module_name_repetitions, clippy::inline_always)]
5
6//! `no_std` compatible Map and Set backed by arrays.
7//! This crate will evolve as more const-generic features become available.
8//!
9//! Features:
10//! * `derive`: Includes the [`Indexable`](array_map_derive::Indexable) derive macro
11//! * `serde`: Includes serde impls for [`ArrayMap`] and [`ArraySet`]
12//! * `std`: Includes [`From`](core::convert::From) implementations between [`ArrayMap<K, AtomicBool, M>`](ArrayMap) and [`ArraySet<K, S>`](ArraySet)
13//!
14//! This is especially useful if you have a bare enum where you want to treat each key as a field. This
15//! also has the benefit that adding a new enum variant forces you to update your code.
16//! ```
17//! use array_map::*;
18//! # use array_map_derive::Indexable;
19//! #[repr(u8)]
20//! #[derive(Indexable)]
21//! enum DetectionType {
22//!   Person,
23//!   Vehicle,
24//!   Bicycle,
25//! }
26//!
27//! let thresholds = ArrayMap::<DetectionType, f32, {DetectionType::count()}>::from_closure(|dt| match dt {
28//!     DetectionType::Person => 0.8,
29//!     DetectionType::Vehicle => 0.9,
30//!     DetectionType::Bicycle => 0.7,
31//!   });
32//!
33//! let person_threshold = thresholds[DetectionType::Person];
34//!
35//! ```
36//!
37//! This can also be used to memoize some common computations
38//! (this is 2x as fast as doing the computation on aarch64)
39//! ```
40//! use array_map::*;
41//! let u8_to_f32_cache = ArrayMap::<u8, f32, {u8::SIZE}>::from_closure(|u|f32::from(*u) / 255.0);
42//! # let bytes = vec![0_u8; 1024];
43//! // take some bytes and convert them to f32
44//! let floats = bytes.iter().copied().map(|b|u8_to_f32_cache[b]).collect::<Vec<_>>();
45//! ```
46
47mod map;
48#[cfg(feature = "serde")]
49mod serde;
50mod set;
51mod three_tuple;
52mod two_tuple;
53
54#[cfg(feature = "array_map_derive")]
55pub use array_map_derive::Indexable;
56use core::convert::TryInto;
57pub use map::*;
58pub use set::*;
59pub use three_tuple::*;
60pub use two_tuple::*;
61
62/// Allows mapping from a type to an index
63///
64/// # Safety
65///
66/// This trait is unsafe because there are a few other requirements that need to be met:
67/// * The indexes of self need to be contiguous and need to be returned in order from `iter()`
68/// * Iter needs to return exactly N items (this is checked in debug mode)
69#[allow(unsafe_code)]
70pub unsafe trait Indexable {
71  /// The number of items or variants that this type can have.
72  const SIZE: usize;
73  /// The number of bytes it will take to represent this type in a set.
74  /// # Safety
75  /// This must equal `set_size(Self::SIZE)`
76  const SET_SIZE: usize;
77  /// The type of Iterator that will be returned by [`Self::iter()`]
78  type Iter: Iterator<Item = Self>;
79  /// Maps self to usize to know which value in the underling array to use
80  /// # Safety
81  /// This value can never be greater than [`Self::SIZE`]
82  ///
83  /// All values in `0..SIZE` must be returned by some variant of self.
84  fn index(self) -> usize;
85  /// An Iterator over all valid values of `self`
86  /// # Safety
87  /// This iterator must yield exactly [`Self::SIZE`] items
88  fn iter() -> Self::Iter;
89}
90
91#[inline(always)]
92fn assert_indexable_safe<I: Indexable>() {
93  #[cfg(debug_assertions)]
94  {
95    for (i, k) in I::iter().enumerate().take(I::SIZE + 1) {
96      let index = k.index();
97      assert_eq!(index, i);
98      assert!(index < I::SIZE);
99    }
100  }
101}
102
103/// Allows mapping from an index to a type
104///
105/// # Safety
106///
107/// This is trait is unsafe because it needs to uphold the property that it is reflexive.
108/// For example:
109/// ```
110/// use array_map::*;
111/// let index = 42_u8.index();
112/// let u = u8::from_index(index);
113/// assert_eq!(u, 42);
114/// ```
115///
116/// If a value greater than or equal to [`Self::SIZE`](Indexable::SIZE) is provided, then this function can panic.
117/// This library will never pass in an invalid usize value.
118#[allow(unsafe_code)]
119pub unsafe trait ReverseIndexable: Indexable {
120  /// Converts from a usize to `Self`
121  fn from_index(u: usize) -> Self;
122}
123
124#[allow(unsafe_code)]
125unsafe impl<T: Indexable> Indexable for Option<T> {
126  const SIZE: usize = T::SIZE + 1;
127  const SET_SIZE: usize = set_size(T::SIZE + 1);
128  #[allow(clippy::type_complexity)]
129  type Iter = core::iter::Chain<core::iter::Map<T::Iter, fn(T) -> Option<T>>, core::iter::Once<Option<T>>>;
130
131  fn index(self) -> usize {
132    match self {
133      Some(x) => x.index(),
134      None => T::SIZE,
135    }
136  }
137
138  fn iter() -> Self::Iter {
139    T::iter().map(Some as fn(T) -> Option<T>).chain(core::iter::once(None))
140  }
141}
142
143#[allow(unsafe_code)]
144unsafe impl<T: ReverseIndexable> ReverseIndexable for Option<T> {
145  fn from_index(u: usize) -> Self {
146    if u == T::SIZE {
147      None
148    } else {
149      Some(T::from_index(u))
150    }
151  }
152}
153
154#[allow(unsafe_code)]
155unsafe impl Indexable for bool {
156  const SIZE: usize = 2;
157  const SET_SIZE: usize = set_size(2);
158  type Iter = core::array::IntoIter<bool, 2>;
159  #[inline(always)]
160  fn index(self) -> usize {
161    usize::from(self)
162  }
163  #[inline(always)]
164  fn iter() -> Self::Iter {
165    [false, true].into_iter()
166  }
167}
168
169#[allow(unsafe_code)]
170unsafe impl ReverseIndexable for bool {
171  fn from_index(u: usize) -> Self {
172    [false, true][u]
173  }
174}
175
176#[allow(unsafe_code)]
177unsafe impl Indexable for u8 {
178  const SIZE: usize = u8::MAX as usize + 1;
179  const SET_SIZE: usize = set_size(u8::MAX as usize + 1);
180  type Iter = core::ops::RangeInclusive<Self>;
181  #[inline(always)]
182  fn index(self) -> usize {
183    self as usize
184  }
185  #[inline(always)]
186  fn iter() -> Self::Iter {
187    Self::MIN..=Self::MAX
188  }
189}
190
191#[allow(unsafe_code)]
192unsafe impl ReverseIndexable for u8 {
193  fn from_index(u: usize) -> Self {
194    u.try_into().unwrap_or_else(|_| panic!("Invalid u8 index provided {}", u))
195  }
196}
197
198#[allow(unsafe_code)]
199unsafe impl Indexable for u16 {
200  const SIZE: usize = u16::MAX as usize + 1;
201  const SET_SIZE: usize = set_size(u16::MAX as usize + 1);
202  type Iter = core::ops::RangeInclusive<Self>;
203  #[inline(always)]
204  fn index(self) -> usize {
205    self as usize
206  }
207  #[inline(always)]
208  fn iter() -> Self::Iter {
209    Self::MIN..=Self::MAX
210  }
211}
212
213#[allow(unsafe_code)]
214unsafe impl ReverseIndexable for u16 {
215  fn from_index(u: usize) -> Self {
216    u.try_into().unwrap_or_else(|_| panic!("Invalid u16 index provided {}", u))
217  }
218}
219
220/// This struct implements [`Indexable`] and allows all values in `0..N`
221#[derive(Copy, Clone, Default, Debug, PartialEq, Eq, PartialOrd, Ord)]
222#[cfg_attr(feature = "serde", derive(::serde::Serialize, ::serde::Deserialize))]
223#[cfg_attr(feature = "serde", serde(transparent))]
224#[repr(transparent)]
225#[must_use]
226pub struct IndexU8<const N: u8>(u8);
227
228impl<const N: u8> IndexU8<N> {
229  /// Returns a new `IndexU8` if it is in a valid range
230  #[inline]
231  #[must_use]
232  pub const fn new(u: u8) -> Option<Self> {
233    if u < N {
234      Some(Self(u))
235    } else {
236      None
237    }
238  }
239  /// Returns the underlying u8
240  #[inline(always)]
241  #[must_use]
242  pub const fn get(self) -> u8 {
243    self.0
244  }
245}
246
247#[allow(unsafe_code)]
248unsafe impl<const N: u8> Indexable for IndexU8<N> {
249  const SIZE: usize = N as usize;
250  const SET_SIZE: usize = set_size(N as usize);
251  type Iter = core::iter::Map<core::ops::Range<u8>, fn(u8) -> Self>;
252
253  fn index(self) -> usize {
254    self.0 as usize
255  }
256
257  fn iter() -> Self::Iter {
258    (0..N).map(Self)
259  }
260}
261
262#[allow(unsafe_code)]
263unsafe impl<const N: u8> ReverseIndexable for IndexU8<N> {
264  fn from_index(u: usize) -> Self {
265    let u: u8 = u.try_into().unwrap_or_else(|_| panic!("Invalid IndexU8 index provided {}", u));
266    Self::new(u).unwrap_or_else(|| panic!("Invalid IndexU8 index provided {}", u))
267  }
268}
269
270impl<const N: u8> core::fmt::Display for IndexU8<N> {
271  fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
272    self.0.fmt(f)
273  }
274}
275
276/// This struct implements [`Indexable`] and allows all values in `0..N`
277#[derive(Copy, Clone, Default, Debug, PartialEq, Eq, PartialOrd, Ord)]
278#[cfg_attr(feature = "serde", derive(::serde::Serialize, ::serde::Deserialize))]
279#[cfg_attr(feature = "serde", serde(transparent))]
280#[repr(transparent)]
281#[must_use]
282pub struct IndexU16<const N: u16>(u16);
283
284impl<const N: u16> IndexU16<N> {
285  /// Returns a new `IndexU8` if it is in a valid range
286  #[inline]
287  #[must_use]
288  pub const fn new(u: u16) -> Option<Self> {
289    if u < N {
290      Some(Self(u))
291    } else {
292      None
293    }
294  }
295  /// Returns the underlying u8
296  #[inline(always)]
297  #[must_use]
298  pub const fn get(self) -> u16 {
299    self.0
300  }
301}
302
303#[allow(unsafe_code)]
304unsafe impl<const N: u16> Indexable for IndexU16<N> {
305  const SIZE: usize = N as usize;
306  const SET_SIZE: usize = set_size(N as usize);
307  type Iter = core::iter::Map<core::ops::Range<u16>, fn(u16) -> Self>;
308
309  fn index(self) -> usize {
310    self.0 as usize
311  }
312
313  fn iter() -> Self::Iter {
314    (0..N).map(Self)
315  }
316}
317
318#[allow(unsafe_code)]
319unsafe impl<const N: u16> ReverseIndexable for IndexU16<N> {
320  fn from_index(u: usize) -> Self {
321    let u: u16 = u.try_into().unwrap_or_else(|_| panic!("Invalid IndexU8 index provided {}", u));
322    Self::new(u).unwrap_or_else(|| panic!("Invalid IndexU8 index provided {}", u))
323  }
324}
325
326impl<const N: u16> core::fmt::Display for IndexU16<N> {
327  fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
328    self.0.fmt(f)
329  }
330}
331
332#[cfg(test)]
333mod test {
334
335  #[derive(Copy, Clone, PartialEq, Eq, Ord, PartialOrd, Debug, ::serde::Serialize, ::serde::Deserialize)]
336  #[serde(transparent)]
337  pub struct Lowercase(pub(crate) char);
338  #[allow(unsafe_code)]
339  unsafe impl crate::Indexable for Lowercase {
340    const SIZE: usize = 26;
341    const SET_SIZE: usize = crate::set_size(26);
342    type Iter = core::iter::Map<core::ops::RangeInclusive<char>, fn(char) -> Lowercase>;
343
344    fn index(self) -> usize {
345      self.0 as usize - 'a' as usize
346    }
347
348    fn iter() -> Self::Iter {
349      ('a'..='z').map(Lowercase)
350    }
351  }
352}
array_map/lib.rs

array_map/
lib.rs
