heapless/
linear_map.rs

1//! A fixed capacity map/dictionary that performs lookups via linear search.
2//!
3//! Note that as this map doesn't use hashing so most operations are *O*(n) instead of *O*(1).
4
5use core::{borrow::Borrow, fmt, iter::FusedIterator, mem, ops, slice};
6
7#[cfg(feature = "zeroize")]
8use zeroize::Zeroize;
9
10use crate::vec::{OwnedVecStorage, Vec, VecInner, ViewVecStorage};
11
12mod storage {
13    use crate::vec::{OwnedVecStorage, VecStorage, ViewVecStorage};
14
15    use super::{LinearMapInner, LinearMapView};
16
17    /// Trait defining how data for a [`LinearMap`](super::LinearMap) is stored.
18    ///
19    /// There's two implementations available:
20    ///
21    /// - [`OwnedStorage`]: stores the data in an array whose size is known at compile time.
22    /// - [`ViewStorage`]: stores the data in an unsized slice
23    ///
24    /// This allows [`LinearMap`] to be generic over either sized or unsized storage. The
25    /// [`linear_map`](super) module contains a [`LinearMapInner`] struct that's generic on
26    /// [`LinearMapStorage`], and two type aliases for convenience:
27    ///
28    /// - [`LinearMap<N>`](crate::linear_map::LinearMap) = `LinearMapInner<OwnedStorage<u8, N>>`
29    /// - [`LinearMapView<T>`](crate::linear_map::LinearMapView) = `LinearMapInner<ViewStorage<u8>>`
30    ///
31    /// `LinearMap` can be unsized into `StrinsgView`, either by unsizing coercions such as `&mut
32    /// LinearMap -> &mut LinearMapView` or `Box<LinearMap> -> Box<LinearMapView>`, or
33    /// explicitly with [`.as_view()`](crate::linear_map::LinearMap::as_view) or
34    /// [`.as_mut_view()`](crate::linear_map::LinearMap::as_mut_view).
35    ///
36    /// This trait is sealed, so you cannot implement it for your own types. You can only use
37    /// the implementations provided by this crate.
38    ///
39    /// [`LinearMapInner`]: super::LinearMapInner
40    /// [`LinearMap`]: super::LinearMap
41    /// [`OwnedStorage`]: super::OwnedStorage
42    /// [`ViewStorage`]: super::ViewStorage
43    pub trait LinearMapStorage<K, V>: LinearMapStorageSealed<K, V> {}
44    pub trait LinearMapStorageSealed<K, V>: VecStorage<(K, V)> {
45        fn as_linear_map_view(this: &LinearMapInner<K, V, Self>) -> &LinearMapView<K, V>
46        where
47            Self: LinearMapStorage<K, V>;
48        fn as_linear_map_mut_view(
49            this: &mut LinearMapInner<K, V, Self>,
50        ) -> &mut LinearMapView<K, V>
51        where
52            Self: LinearMapStorage<K, V>;
53    }
54
55    impl<K, V, const N: usize> LinearMapStorage<K, V> for OwnedVecStorage<(K, V), N> {}
56    impl<K, V, const N: usize> LinearMapStorageSealed<K, V> for OwnedVecStorage<(K, V), N> {
57        fn as_linear_map_view(this: &LinearMapInner<K, V, Self>) -> &LinearMapView<K, V>
58        where
59            Self: LinearMapStorage<K, V>,
60        {
61            this
62        }
63        fn as_linear_map_mut_view(this: &mut LinearMapInner<K, V, Self>) -> &mut LinearMapView<K, V>
64        where
65            Self: LinearMapStorage<K, V>,
66        {
67            this
68        }
69    }
70
71    impl<K, V> LinearMapStorage<K, V> for ViewVecStorage<(K, V)> {}
72
73    impl<K, V> LinearMapStorageSealed<K, V> for ViewVecStorage<(K, V)> {
74        fn as_linear_map_view(this: &LinearMapInner<K, V, Self>) -> &LinearMapView<K, V>
75        where
76            Self: LinearMapStorage<K, V>,
77        {
78            this
79        }
80        fn as_linear_map_mut_view(this: &mut LinearMapInner<K, V, Self>) -> &mut LinearMapView<K, V>
81        where
82            Self: LinearMapStorage<K, V>,
83        {
84            this
85        }
86    }
87}
88
89pub use storage::LinearMapStorage;
90/// Implementation of [`LinearMapStorage`] that stores the data in an array whose size is known at
91/// compile time.
92pub type OwnedStorage<K, V, const N: usize> = OwnedVecStorage<(K, V), N>;
93/// Implementation of [`LinearMapStorage`] that stores the data in an unsized slice.
94pub type ViewStorage<K, V> = ViewVecStorage<(K, V)>;
95
96/// Base struct for [`LinearMap`] and [`LinearMapView`]
97#[cfg_attr(
98    feature = "zeroize",
99    derive(Zeroize),
100    zeroize(bound = "S: Zeroize, K: Zeroize, V: Zeroize")
101)]
102pub struct LinearMapInner<K, V, S: LinearMapStorage<K, V> + ?Sized> {
103    pub(crate) buffer: VecInner<(K, V), usize, S>,
104}
105
106/// A fixed capacity map/dictionary that performs lookups via linear search.
107///
108/// Note that as this map doesn't use hashing so most operations are *O*(n) instead of *O*(1).
109pub type LinearMap<K, V, const N: usize> = LinearMapInner<K, V, OwnedStorage<K, V, N>>;
110
111/// A dynamic capacity map/dictionary that performs lookups via linear search.
112///
113/// Note that as this map doesn't use hashing so most operations are *O*(n) instead of *O*(1).
114pub type LinearMapView<K, V> = LinearMapInner<K, V, ViewStorage<K, V>>;
115
116impl<K, V, const N: usize> LinearMap<K, V, N> {
117    /// Creates an empty `LinearMap`.
118    ///
119    /// # Examples
120    ///
121    /// ```
122    /// use heapless::LinearMap;
123    ///
124    /// // allocate the map on the stack
125    /// let mut map: LinearMap<&str, isize, 8> = LinearMap::new();
126    ///
127    /// // allocate the map in a static variable
128    /// static mut MAP: LinearMap<&str, isize, 8> = LinearMap::new();
129    /// ```
130    pub const fn new() -> Self {
131        Self { buffer: Vec::new() }
132    }
133}
134
135impl<K, V, S: LinearMapStorage<K, V> + ?Sized> LinearMapInner<K, V, S>
136where
137    K: Eq,
138{
139    /// Get a reference to the `LinearMap`, erasing the `N` const-generic.
140    pub fn as_view(&self) -> &LinearMapView<K, V> {
141        S::as_linear_map_view(self)
142    }
143
144    /// Get a mutable reference to the `LinearMap`, erasing the `N` const-generic.
145    pub fn as_mut_view(&mut self) -> &mut LinearMapView<K, V> {
146        S::as_linear_map_mut_view(self)
147    }
148
149    /// Returns the number of elements that the map can hold.
150    ///
151    /// Computes in *O*(1) time.
152    ///
153    /// # Examples
154    ///
155    /// ```
156    /// use heapless::LinearMap;
157    ///
158    /// let map: LinearMap<&str, isize, 8> = LinearMap::new();
159    /// assert_eq!(map.capacity(), 8);
160    /// ```
161    pub fn capacity(&self) -> usize {
162        self.buffer.capacity()
163    }
164
165    /// Clears the map, removing all key-value pairs.
166    ///
167    /// Computes in *O*(1) time.
168    ///
169    /// # Examples
170    ///
171    /// ```
172    /// use heapless::LinearMap;
173    ///
174    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
175    /// map.insert(1, "a").unwrap();
176    /// map.clear();
177    /// assert!(map.is_empty());
178    /// ```
179    pub fn clear(&mut self) {
180        self.buffer.clear();
181    }
182
183    /// Returns true if the map contains a value for the specified key.
184    ///
185    /// Computes in *O*(n) time.
186    ///
187    /// # Examples
188    ///
189    /// ```
190    /// use heapless::LinearMap;
191    ///
192    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
193    /// map.insert(1, "a").unwrap();
194    /// assert_eq!(map.contains_key(&1), true);
195    /// assert_eq!(map.contains_key(&2), false);
196    /// ```
197    pub fn contains_key(&self, key: &K) -> bool {
198        self.get(key).is_some()
199    }
200
201    /// Returns a reference to the value corresponding to the key.
202    ///
203    /// Computes in *O*(n) time.
204    ///
205    /// # Examples
206    ///
207    /// ```
208    /// use heapless::LinearMap;
209    ///
210    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
211    /// map.insert(1, "a").unwrap();
212    /// assert_eq!(map.get(&1), Some(&"a"));
213    /// assert_eq!(map.get(&2), None);
214    /// ```
215    pub fn get<Q>(&self, key: &Q) -> Option<&V>
216    where
217        K: Borrow<Q>,
218        Q: Eq + ?Sized,
219    {
220        self.iter()
221            .find(|&(k, _)| k.borrow() == key)
222            .map(|(_, v)| v)
223    }
224
225    /// Returns a mutable reference to the value corresponding to the key.
226    ///
227    /// Computes in *O*(n) time.
228    ///
229    /// # Examples
230    ///
231    /// ```
232    /// use heapless::LinearMap;
233    ///
234    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
235    /// map.insert(1, "a").unwrap();
236    /// if let Some(x) = map.get_mut(&1) {
237    ///     *x = "b";
238    /// }
239    /// assert_eq!(map[&1], "b");
240    /// ```
241    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
242    where
243        K: Borrow<Q>,
244        Q: Eq + ?Sized,
245    {
246        self.iter_mut()
247            .find(|&(k, _)| k.borrow() == key)
248            .map(|(_, v)| v)
249    }
250
251    /// Returns the number of elements in this map.
252    ///
253    /// Computes in *O*(1) time.
254    ///
255    /// # Examples
256    ///
257    /// ```
258    /// use heapless::LinearMap;
259    ///
260    /// let mut a: LinearMap<_, _, 8> = LinearMap::new();
261    /// assert_eq!(a.len(), 0);
262    /// a.insert(1, "a").unwrap();
263    /// assert_eq!(a.len(), 1);
264    /// ```
265    pub fn len(&self) -> usize {
266        self.buffer.len()
267    }
268
269    /// Inserts a key-value pair into the map.
270    ///
271    /// If the map did not have this key present, `None` is returned.
272    ///
273    /// If the map did have this key present, the value is updated, and the old value is returned.
274    ///
275    /// Computes in *O*(n) time
276    ///
277    /// # Examples
278    ///
279    /// ```
280    /// use heapless::LinearMap;
281    ///
282    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
283    /// assert_eq!(map.insert(37, "a").unwrap(), None);
284    /// assert_eq!(map.is_empty(), false);
285    ///
286    /// map.insert(37, "b").unwrap();
287    /// assert_eq!(map.insert(37, "c").unwrap(), Some("b"));
288    /// assert_eq!(map[&37], "c");
289    /// ```
290    pub fn insert(&mut self, key: K, mut value: V) -> Result<Option<V>, (K, V)> {
291        if let Some((_, v)) = self.iter_mut().find(|&(k, _)| *k == key) {
292            mem::swap(v, &mut value);
293            return Ok(Some(value));
294        }
295
296        self.buffer.push((key, value))?;
297        Ok(None)
298    }
299
300    /// Returns true if the map contains no elements.
301    ///
302    /// Computes in *O*(1) time.
303    ///
304    /// # Examples
305    ///
306    /// ```
307    /// use heapless::LinearMap;
308    ///
309    /// let mut a: LinearMap<_, _, 8> = LinearMap::new();
310    /// assert!(a.is_empty());
311    /// a.insert(1, "a").unwrap();
312    /// assert!(!a.is_empty());
313    /// ```
314    pub fn is_empty(&self) -> bool {
315        self.len() == 0
316    }
317
318    /// Returns true if the map is full.
319    ///
320    /// Computes in *O*(1) time.
321    ///
322    /// # Examples
323    ///
324    /// ```
325    /// use heapless::LinearMap;
326    ///
327    /// let mut a: LinearMap<_, _, 4> = LinearMap::new();
328    /// assert!(!a.is_full());
329    /// a.insert(1, "a").unwrap();
330    /// a.insert(2, "b").unwrap();
331    /// a.insert(3, "c").unwrap();
332    /// a.insert(4, "d").unwrap();
333    /// assert!(a.is_full());
334    /// ```
335    pub fn is_full(&self) -> bool {
336        self.len() == self.capacity()
337    }
338
339    /// An iterator visiting all key-value pairs in arbitrary order.
340    ///
341    /// # Examples
342    ///
343    /// ```
344    /// use heapless::LinearMap;
345    ///
346    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
347    /// map.insert("a", 1).unwrap();
348    /// map.insert("b", 2).unwrap();
349    /// map.insert("c", 3).unwrap();
350    ///
351    /// for (key, val) in map.iter() {
352    ///     println!("key: {} val: {}", key, val);
353    /// }
354    /// ```
355    pub fn iter(&self) -> Iter<'_, K, V> {
356        Iter {
357            iter: self.buffer.as_slice().iter(),
358        }
359    }
360
361    /// An iterator visiting all key-value pairs in arbitrary order,
362    /// with mutable references to the values.
363    ///
364    /// # Examples
365    ///
366    /// ```
367    /// use heapless::LinearMap;
368    ///
369    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
370    /// map.insert("a", 1).unwrap();
371    /// map.insert("b", 2).unwrap();
372    /// map.insert("c", 3).unwrap();
373    ///
374    /// // Update all values
375    /// for (_, val) in map.iter_mut() {
376    ///     *val = 2;
377    /// }
378    ///
379    /// for (key, val) in &map {
380    ///     println!("key: {} val: {}", key, val);
381    /// }
382    /// ```
383    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
384        IterMut {
385            iter: self.buffer.as_mut_slice().iter_mut(),
386        }
387    }
388
389    /// An iterator visiting all keys in arbitrary order.
390    ///
391    /// # Examples
392    ///
393    /// ```
394    /// use heapless::LinearMap;
395    ///
396    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
397    /// map.insert("a", 1).unwrap();
398    /// map.insert("b", 2).unwrap();
399    /// map.insert("c", 3).unwrap();
400    ///
401    /// for key in map.keys() {
402    ///     println!("{}", key);
403    /// }
404    /// ```
405    pub fn keys(&self) -> impl Iterator<Item = &K> {
406        self.iter().map(|(k, _)| k)
407    }
408
409    /// Removes a key from the map, returning the value at
410    /// the key if the key was previously in the map.
411    ///
412    /// Computes in *O*(n) time
413    ///
414    /// # Examples
415    ///
416    /// ```
417    /// use heapless::LinearMap;
418    ///
419    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
420    /// map.insert(1, "a").unwrap();
421    /// assert_eq!(map.remove(&1), Some("a"));
422    /// assert_eq!(map.remove(&1), None);
423    /// ```
424    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
425    where
426        K: Borrow<Q>,
427        Q: Eq + ?Sized,
428    {
429        let idx = self
430            .keys()
431            .enumerate()
432            .find(|&(_, k)| k.borrow() == key)
433            .map(|(idx, _)| idx);
434
435        idx.map(|idx| self.buffer.swap_remove(idx).1)
436    }
437
438    /// An iterator visiting all values in arbitrary order.
439    ///
440    /// # Examples
441    ///
442    /// ```
443    /// use heapless::LinearMap;
444    ///
445    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
446    /// map.insert("a", 1).unwrap();
447    /// map.insert("b", 2).unwrap();
448    /// map.insert("c", 3).unwrap();
449    ///
450    /// for val in map.values() {
451    ///     println!("{}", val);
452    /// }
453    /// ```
454    pub fn values(&self) -> impl Iterator<Item = &V> {
455        self.iter().map(|(_, v)| v)
456    }
457
458    /// An iterator visiting all values mutably in arbitrary order.
459    ///
460    /// # Examples
461    ///
462    /// ```
463    /// use heapless::LinearMap;
464    ///
465    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
466    /// map.insert("a", 1).unwrap();
467    /// map.insert("b", 2).unwrap();
468    /// map.insert("c", 3).unwrap();
469    ///
470    /// for val in map.values_mut() {
471    ///     *val += 10;
472    /// }
473    ///
474    /// for val in map.values() {
475    ///     println!("{}", val);
476    /// }
477    /// ```
478    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
479        self.iter_mut().map(|(_, v)| v)
480    }
481
482    /// Returns an entry for the corresponding key
483    /// ```
484    /// use heapless::linear_map;
485    /// use heapless::LinearMap;
486    /// let mut map = LinearMap::<_, _, 16>::new();
487    /// if let linear_map::Entry::Vacant(v) = map.entry("a") {
488    ///     v.insert(1).unwrap();
489    /// }
490    /// if let linear_map::Entry::Occupied(mut o) = map.entry("a") {
491    ///     println!("found {}", *o.get()); // Prints 1
492    ///     o.insert(2);
493    /// }
494    /// // Prints 2
495    /// println!("val: {}", *map.get("a").unwrap());
496    /// ```
497    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
498        let idx = self
499            .keys()
500            .enumerate()
501            .find(|&(_, k)| *k.borrow() == key)
502            .map(|(idx, _)| idx);
503
504        match idx {
505            Some(idx) => Entry::Occupied(OccupiedEntry {
506                idx,
507                map: self.as_mut_view(),
508            }),
509            None => Entry::Vacant(VacantEntry {
510                key,
511                map: self.as_mut_view(),
512            }),
513        }
514    }
515
516    /// Retains only the elements specified by the predicate.
517    ///
518    /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`.
519    pub fn retain<F>(&mut self, mut f: F)
520    where
521        F: FnMut(&K, &mut V) -> bool,
522    {
523        self.buffer.retain_mut(|(k, v)| f(k, v));
524    }
525}
526
527impl<K, V, Q, S: LinearMapStorage<K, V> + ?Sized> ops::Index<&'_ Q> for LinearMapInner<K, V, S>
528where
529    K: Borrow<Q> + Eq,
530    Q: Eq + ?Sized,
531{
532    type Output = V;
533
534    fn index(&self, key: &Q) -> &V {
535        self.get(key).expect("no entry found for key")
536    }
537}
538
539impl<K, V, Q, S: LinearMapStorage<K, V> + ?Sized> ops::IndexMut<&'_ Q> for LinearMapInner<K, V, S>
540where
541    K: Borrow<Q> + Eq,
542    Q: Eq + ?Sized,
543{
544    fn index_mut(&mut self, key: &Q) -> &mut V {
545        self.get_mut(key).expect("no entry found for key")
546    }
547}
548
549impl<K, V, const N: usize> Default for LinearMap<K, V, N>
550where
551    K: Eq,
552{
553    fn default() -> Self {
554        Self::new()
555    }
556}
557
558impl<K, V, const N: usize> Clone for LinearMap<K, V, N>
559where
560    K: Eq + Clone,
561    V: Clone,
562{
563    fn clone(&self) -> Self {
564        Self {
565            buffer: self.buffer.clone(),
566        }
567    }
568}
569
570impl<K, V, S: LinearMapStorage<K, V> + ?Sized> fmt::Debug for LinearMapInner<K, V, S>
571where
572    K: Eq + fmt::Debug,
573    V: fmt::Debug,
574{
575    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
576        f.debug_map().entries(self.iter()).finish()
577    }
578}
579
580impl<K, V, const N: usize> FromIterator<(K, V)> for LinearMap<K, V, N>
581where
582    K: Eq,
583{
584    fn from_iter<I>(iter: I) -> Self
585    where
586        I: IntoIterator<Item = (K, V)>,
587    {
588        let mut out = Self::new();
589        out.buffer.extend(iter);
590        out
591    }
592}
593
594/// An iterator that moves out of a [`LinearMap`].
595///
596/// This struct is created by calling the [`into_iter`](LinearMap::into_iter) method on
597/// [`LinearMap`].
598pub struct IntoIter<K, V, const N: usize>
599where
600    K: Eq,
601{
602    inner: <Vec<(K, V), N, usize> as IntoIterator>::IntoIter,
603}
604
605impl<K, V, const N: usize> Iterator for IntoIter<K, V, N>
606where
607    K: Eq,
608{
609    type Item = (K, V);
610    fn next(&mut self) -> Option<Self::Item> {
611        self.inner.next()
612    }
613
614    fn size_hint(&self) -> (usize, Option<usize>) {
615        let len = self.len();
616        (len, Some(len))
617    }
618}
619
620impl<K, V, const N: usize> FusedIterator for IntoIter<K, V, N> where K: Eq {}
621
622impl<K, V, const N: usize> ExactSizeIterator for IntoIter<K, V, N>
623where
624    K: Eq,
625{
626    fn len(&self) -> usize {
627        self.inner.len()
628    }
629}
630
631impl<K, V, const N: usize> IntoIterator for LinearMap<K, V, N>
632where
633    K: Eq,
634{
635    type Item = (K, V);
636    type IntoIter = IntoIter<K, V, N>;
637
638    fn into_iter(self) -> Self::IntoIter {
639        IntoIter {
640            inner: self.buffer.into_iter(),
641        }
642    }
643}
644
645impl<'a, K, V, S: LinearMapStorage<K, V> + ?Sized> IntoIterator for &'a LinearMapInner<K, V, S>
646where
647    K: Eq,
648{
649    type Item = (&'a K, &'a V);
650    type IntoIter = Iter<'a, K, V>;
651
652    fn into_iter(self) -> Self::IntoIter {
653        self.iter()
654    }
655}
656
657/// An iterator over the items of a [`LinearMap`]
658///
659/// This struct is created by calling the [`iter`](LinearMap::iter) method on [`LinearMap`].
660#[derive(Clone, Debug)]
661pub struct Iter<'a, K, V> {
662    iter: slice::Iter<'a, (K, V)>,
663}
664
665impl<'a, K, V> Iterator for Iter<'a, K, V> {
666    type Item = (&'a K, &'a V);
667
668    fn next(&mut self) -> Option<Self::Item> {
669        self.iter.next().map(|(k, v)| (k, v))
670    }
671}
672
673/// An iterator over the items of a [`LinearMap`] that allows modifying the items
674///
675/// This struct is created by calling the [`iter_mut`](LinearMap::iter_mut) method on [`LinearMap`].
676#[derive(Debug)]
677pub struct IterMut<'a, K, V> {
678    iter: slice::IterMut<'a, (K, V)>,
679}
680
681impl<'a, K, V> Iterator for IterMut<'a, K, V> {
682    type Item = (&'a K, &'a mut V);
683
684    fn next(&mut self) -> Option<Self::Item> {
685        self.iter.next().map(|(k, v)| (k as &K, v))
686    }
687}
688
689impl<K, V1, V2, S1: LinearMapStorage<K, V1> + ?Sized, S2: LinearMapStorage<K, V2> + ?Sized>
690    PartialEq<LinearMapInner<K, V2, S2>> for LinearMapInner<K, V1, S1>
691where
692    K: Eq,
693    V1: PartialEq<V2>,
694{
695    fn eq(&self, other: &LinearMapInner<K, V2, S2>) -> bool {
696        self.len() == other.len()
697            && self
698                .iter()
699                .all(|(key, value)| other.get(key).is_some_and(|v| *value == *v))
700    }
701}
702
703impl<K, V, S: LinearMapStorage<K, V> + ?Sized> Eq for LinearMapInner<K, V, S>
704where
705    K: Eq,
706    V: PartialEq,
707{
708}
709
710/// A view into an entry in the map
711pub enum Entry<'a, K, V> {
712    /// The entry corresponding to the key `K` exists in the map
713    Occupied(OccupiedEntry<'a, K, V>),
714    /// The entry corresponding to the key `K` does not exist in the map
715    Vacant(VacantEntry<'a, K, V>),
716}
717
718/// An occupied entry which can be manipulated
719pub struct OccupiedEntry<'a, K, V> {
720    // SAFETY: `idx` must not be modified after construction, and
721    // the size of `map` must not be changed.
722    idx: usize,
723    map: &'a mut LinearMapView<K, V>,
724}
725
726impl<'a, K, V> OccupiedEntry<'a, K, V>
727where
728    K: Eq,
729{
730    /// Gets a reference to the key that this entity corresponds to
731    pub fn key(&self) -> &K {
732        // SAFETY: Valid idx from OccupiedEntry construction
733        let (k, _v) = unsafe { self.map.buffer.get_unchecked(self.idx) };
734        k
735    }
736
737    /// Removes this entry from the map and yields its corresponding key and value
738    pub fn remove_entry(self) -> (K, V) {
739        // SAFETY: Valid idx from OccupiedEntry construction
740        unsafe { self.map.buffer.swap_remove_unchecked(self.idx) }
741    }
742
743    /// Removes this entry from the map and yields its corresponding key and value
744    pub fn remove(self) -> V {
745        self.remove_entry().1
746    }
747
748    /// Gets a reference to the value associated with this entry
749    pub fn get(&self) -> &V {
750        // SAFETY: Valid idx from OccupiedEntry construction
751        let (_k, v) = unsafe { self.map.buffer.get_unchecked(self.idx) };
752        v
753    }
754
755    /// Gets a mutable reference to the value associated with this entry
756    pub fn get_mut(&mut self) -> &mut V {
757        // SAFETY: Valid idx from OccupiedEntry construction
758        let (_k, v) = unsafe { self.map.buffer.get_unchecked_mut(self.idx) };
759        v
760    }
761
762    /// Consumes this entry and yields a reference to the underlying value
763    pub fn into_mut(self) -> &'a mut V {
764        // SAFETY: Valid idx from OccupiedEntry construction
765        let (_k, v) = unsafe { self.map.buffer.get_unchecked_mut(self.idx) };
766        v
767    }
768
769    /// Overwrites the underlying map's value with this entry's value
770    pub fn insert(self, value: V) -> V {
771        // SAFETY: Valid idx from OccupiedEntry construction
772        let (_k, v) = unsafe { self.map.buffer.get_unchecked_mut(self.idx) };
773        mem::replace(v, value)
774    }
775}
776
777/// A view into an empty slot in the underlying map
778pub struct VacantEntry<'a, K, V> {
779    key: K,
780    map: &'a mut LinearMapView<K, V>,
781}
782
783impl<'a, K, V> VacantEntry<'a, K, V>
784where
785    K: Eq,
786{
787    /// Get the key associated with this entry
788    pub fn key(&self) -> &K {
789        &self.key
790    }
791
792    /// Consumes this entry to yield to key associated with it
793    pub fn into_key(self) -> K {
794        self.key
795    }
796
797    /// Inserts this entry into to underlying map, yields a mutable reference to the inserted value.
798    /// If the map is at capacity the value is returned instead.
799    pub fn insert(self, value: V) -> Result<&'a mut V, V> {
800        self.map
801            .buffer
802            .push((self.key, value))
803            .map_err(|(_k, v)| v)?;
804        let idx = self.map.buffer.len() - 1;
805        let r = &mut self.map.buffer[idx];
806        Ok(&mut r.1)
807    }
808}
809
810#[cfg(test)]
811mod test {
812    use static_assertions::assert_not_impl_any;
813
814    use super::{Entry, LinearMap, LinearMapView};
815
816    // Ensure a `LinearMap` containing `!Send` keys stays `!Send` itself.
817    assert_not_impl_any!(LinearMap<*const (), (), 4>: Send);
818    // Ensure a `LinearMap` containing `!Send` values stays `!Send` itself.
819    assert_not_impl_any!(LinearMap<(), *const (), 4>: Send);
820
821    #[test]
822    fn static_new() {
823        static mut _L: LinearMap<i32, i32, 8> = LinearMap::new();
824    }
825
826    #[test]
827    fn borrow() {
828        use crate::String;
829
830        let mut map = LinearMap::<_, _, 8>::new();
831
832        let s = String::<64>::try_from("Hello, world!").unwrap();
833        map.insert(s, 42).unwrap();
834
835        assert_eq!(map.get("Hello, world!").unwrap(), &42);
836    }
837
838    #[test]
839    fn partial_eq() {
840        {
841            let mut a = LinearMap::<_, _, 1>::new();
842            a.insert("k1", "v1").unwrap();
843
844            let mut b = LinearMap::<_, _, 2>::new();
845            b.insert("k1", "v1").unwrap();
846
847            assert!(a == b);
848
849            b.insert("k2", "v2").unwrap();
850
851            assert!(a != b);
852        }
853
854        {
855            let mut a = LinearMap::<_, _, 2>::new();
856            a.insert("k1", "v1").unwrap();
857            a.insert("k2", "v2").unwrap();
858
859            let mut b = LinearMap::<_, _, 2>::new();
860            b.insert("k2", "v2").unwrap();
861            b.insert("k1", "v1").unwrap();
862
863            assert!(a == b);
864        }
865    }
866
867    #[test]
868    fn drop() {
869        droppable!();
870
871        {
872            let mut v: LinearMap<i32, Droppable, 2> = LinearMap::new();
873            v.insert(0, Droppable::new()).ok().unwrap();
874            v.insert(1, Droppable::new()).ok().unwrap();
875            v.remove(&1).unwrap();
876        }
877
878        assert_eq!(Droppable::count(), 0);
879
880        {
881            let mut v: LinearMap<i32, Droppable, 2> = LinearMap::new();
882            v.insert(0, Droppable::new()).ok().unwrap();
883            v.insert(1, Droppable::new()).ok().unwrap();
884        }
885
886        assert_eq!(Droppable::count(), 0);
887    }
888
889    #[test]
890    fn into_iter() {
891        let mut src: LinearMap<_, _, 4> = LinearMap::new();
892        src.insert("k1", "v1").unwrap();
893        src.insert("k2", "v2").unwrap();
894        src.insert("k3", "v3").unwrap();
895        src.insert("k4", "v4").unwrap();
896        let clone = src.clone();
897        for (k, v) in clone.into_iter() {
898            assert_eq!(v, src.remove(k).unwrap());
899        }
900        assert!(src.is_empty());
901    }
902
903    #[test]
904    fn into_iter_len() {
905        let mut src: LinearMap<_, _, 2> = LinearMap::new();
906        src.insert("k1", "v1").unwrap();
907        src.insert("k2", "v2").unwrap();
908        let mut items = src.into_iter();
909        assert_eq!(items.len(), 2);
910        let _ = items.next();
911        assert_eq!(items.len(), 1);
912        let _ = items.next();
913        assert_eq!(items.len(), 0);
914    }
915
916    fn _test_variance_value<'a: 'b, 'b>(
917        x: LinearMap<u32, &'a (), 42>,
918    ) -> LinearMap<u32, &'b (), 42> {
919        x
920    }
921    fn _test_variance_value_view<'a: 'b, 'b, 'c>(
922        x: &'c LinearMapView<u32, &'a ()>,
923    ) -> &'c LinearMapView<u32, &'b ()> {
924        x
925    }
926    fn _test_variance_key<'a: 'b, 'b>(x: LinearMap<&'a (), u32, 42>) -> LinearMap<&'b (), u32, 42> {
927        x
928    }
929    fn _test_variance_key_view<'a: 'b, 'b, 'c>(
930        x: &'c LinearMapView<&'a (), u32>,
931    ) -> &'c LinearMapView<&'b (), u32> {
932        x
933    }
934
935    #[test]
936    fn partial_eq_floats() {
937        // Make sure `PartialEq` is implemented even if `V` doesn't implement `Eq`.
938        let map: LinearMap<usize, f32, 4> = Default::default();
939        assert_eq!(map, map);
940    }
941
942    #[test]
943    #[cfg(feature = "zeroize")]
944    fn test_linear_map_zeroize() {
945        use zeroize::Zeroize;
946
947        let mut map: LinearMap<u8, u8, 8> = LinearMap::new();
948        for i in 1..=8 {
949            map.insert(i, i * 10).unwrap();
950        }
951
952        assert_eq!(map.len(), 8);
953        assert_eq!(map.get(&5), Some(&50));
954
955        // zeroized using Vec's implementation
956        map.zeroize();
957
958        assert_eq!(map.len(), 0);
959        assert!(map.is_empty());
960    }
961
962    // tests that use this constant take too long to run under miri, specially on CI, with a map of
963    // this size so make the map smaller when using miri
964    #[cfg(not(miri))]
965    const MAP_SLOTS: usize = 4096;
966    #[cfg(miri)]
967    const MAP_SLOTS: usize = 64;
968    fn almost_filled_map() -> LinearMap<usize, usize, MAP_SLOTS> {
969        let mut almost_filled = LinearMap::new();
970        for i in 1..MAP_SLOTS {
971            almost_filled.insert(i, i).unwrap();
972        }
973        almost_filled
974    }
975
976    #[test]
977    fn remove() {
978        let mut src = almost_filled_map();
979        // key doesn't exist
980        let k = 0;
981        let r = src.remove(&k);
982        assert!(r.is_none());
983
984        let k = 5;
985        let v = 5;
986        let r = src.remove(&k);
987        assert_eq!(r, Some(v));
988        let r = src.remove(&k);
989        assert!(r.is_none());
990        assert_eq!(src.len(), MAP_SLOTS - 2);
991    }
992
993    #[test]
994    fn replace() {
995        let mut src = almost_filled_map();
996        src.insert(10, 1000).unwrap();
997        let v = src.get(&10).unwrap();
998        assert_eq!(*v, 1000);
999
1000        let mut src = almost_filled_map();
1001        let v = src.get_mut(&10).unwrap();
1002        *v = 500;
1003        let v = src.get(&10).unwrap();
1004        assert_eq!(*v, 500);
1005    }
1006
1007    #[test]
1008    fn retain() {
1009        let mut src = almost_filled_map();
1010        src.retain(|k, _v| k % 2 == 0);
1011        src.retain(|k, _v| k % 3 == 0);
1012
1013        for (k, v) in src.iter() {
1014            assert_eq!(k, v);
1015            assert_eq!(k % 2, 0);
1016            assert_eq!(k % 3, 0);
1017        }
1018
1019        let mut src = almost_filled_map();
1020        src.retain(|_k, _v| false);
1021        assert!(src.is_empty());
1022
1023        let mut src = almost_filled_map();
1024        src.retain(|_k, _v| true);
1025        assert_eq!(src.len(), MAP_SLOTS - 1);
1026        src.insert(0, 0).unwrap();
1027        src.retain(|_k, _v| true);
1028        assert_eq!(src.len(), MAP_SLOTS);
1029    }
1030
1031    #[test]
1032    fn entry_find() {
1033        let key = 0;
1034        let value = 0;
1035        let mut src = almost_filled_map();
1036        let entry = src.entry(key);
1037        match entry {
1038            Entry::Occupied(_) => {
1039                panic!("Found entry without inserting");
1040            }
1041            Entry::Vacant(v) => {
1042                assert_eq!(&key, v.key());
1043                assert_eq!(key, v.into_key());
1044            }
1045        }
1046        src.insert(key, value).unwrap();
1047        let entry = src.entry(key);
1048        match entry {
1049            Entry::Occupied(mut o) => {
1050                assert_eq!(&key, o.key());
1051                assert_eq!(&value, o.get());
1052                assert_eq!(&value, o.get_mut());
1053                assert_eq!(&value, o.into_mut());
1054            }
1055            Entry::Vacant(_) => {
1056                panic!("Entry not found");
1057            }
1058        }
1059    }
1060
1061    #[test]
1062    fn entry_vacant_insert() {
1063        let key = 0;
1064        let value = 0;
1065        let mut src = almost_filled_map();
1066        assert_eq!(MAP_SLOTS - 1, src.len());
1067        let entry = src.entry(key);
1068        match entry {
1069            Entry::Occupied(_) => {
1070                panic!("Entry found when empty");
1071            }
1072            Entry::Vacant(v) => {
1073                assert_eq!(value, *v.insert(value).unwrap());
1074            }
1075        };
1076        assert_eq!(value, *src.get(&key).unwrap());
1077    }
1078
1079    #[test]
1080    fn entry_vacant_full_insert() {
1081        let mut src = almost_filled_map();
1082
1083        // fill the map
1084        let key = MAP_SLOTS * 2;
1085        let value = key;
1086        src.insert(key, value).unwrap();
1087        assert_eq!(MAP_SLOTS, src.len());
1088
1089        let key = 0;
1090        let value = 0;
1091        let entry = src.entry(key);
1092        match entry {
1093            Entry::Occupied(_) => {
1094                panic!("Entry found when missing");
1095            }
1096            Entry::Vacant(v) => {
1097                // Value is returned since the map is full
1098                assert_eq!(value, v.insert(value).unwrap_err());
1099            }
1100        };
1101        assert!(src.get(&key).is_none());
1102    }
1103
1104    #[test]
1105    fn entry_occupied_insert() {
1106        let key = 0;
1107        let value = 0;
1108        let value2 = 5;
1109        let mut src = almost_filled_map();
1110        assert_eq!(MAP_SLOTS - 1, src.len());
1111        src.insert(key, value).unwrap();
1112        let entry = src.entry(key);
1113        match entry {
1114            Entry::Occupied(o) => {
1115                assert_eq!(value, o.insert(value2));
1116            }
1117            Entry::Vacant(_) => {
1118                panic!("Entry not found");
1119            }
1120        };
1121        assert_eq!(value2, *src.get(&key).unwrap());
1122    }
1123
1124    #[test]
1125    fn entry_remove_entry() {
1126        let key = 0;
1127        let value = 0;
1128        let mut src = almost_filled_map();
1129        src.insert(key, value).unwrap();
1130        assert_eq!(MAP_SLOTS, src.len());
1131        let entry = src.entry(key);
1132        match entry {
1133            Entry::Occupied(o) => {
1134                assert_eq!((key, value), o.remove_entry());
1135            }
1136            Entry::Vacant(_) => {
1137                panic!("Entry not found")
1138            }
1139        };
1140        assert_eq!(MAP_SLOTS - 1, src.len());
1141        assert!(!src.contains_key(&key));
1142    }
1143
1144    #[test]
1145    fn entry_remove() {
1146        let key = 0;
1147        let value = 0;
1148        let mut src = almost_filled_map();
1149        src.insert(key, value).unwrap();
1150        assert_eq!(MAP_SLOTS, src.len());
1151        let entry = src.entry(key);
1152        match entry {
1153            Entry::Occupied(o) => {
1154                assert_eq!(value, o.remove());
1155            }
1156            Entry::Vacant(_) => {
1157                panic!("Entry not found");
1158            }
1159        };
1160        assert_eq!(MAP_SLOTS - 1, src.len());
1161    }
1162}
heapless/linear_map.rs

heapless/
linear_map.rs
