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, mem, ops, slice};
6
7use crate::vec::{OwnedVecStorage, Vec, VecInner, ViewVecStorage};
8
9mod storage {
10    use crate::vec::{OwnedVecStorage, VecStorage, ViewVecStorage};
11
12    use super::{LinearMapInner, LinearMapView};
13
14    /// Trait defining how data for a [`LinearMap`](super::LinearMap) is stored.
15    ///
16    /// There's two implementations available:
17    ///
18    /// - [`OwnedStorage`]: stores the data in an array whose size is known at compile time.
19    /// - [`ViewStorage`]: stores the data in an unsized slice
20    ///
21    /// This allows [`LinearMap`] to be generic over either sized or unsized storage. The [`linear_map`](super)
22    /// module contains a [`LinearMapInner`] struct that's generic on [`LinearMapStorage`],
23    /// and two type aliases for convenience:
24    ///
25    /// - [`LinearMap<N>`](crate::linear_map::LinearMap) = `LinearMapInner<OwnedStorage<u8, N>>`
26    /// - [`LinearMapView<T>`](crate::linear_map::LinearMapView) = `LinearMapInner<ViewStorage<u8>>`
27    ///
28    /// `LinearMap` can be unsized into `StrinsgView`, either by unsizing coercions such as `&mut LinearMap -> &mut LinearMapView` or
29    /// `Box<LinearMap> -> Box<LinearMapView>`, or explicitly with [`.as_view()`](crate::linear_map::LinearMap::as_view) or [`.as_mut_view()`](crate::linear_map::LinearMap::as_mut_view).
30    ///
31    /// This trait is sealed, so you cannot implement it for your own types. You can only use
32    /// the implementations provided by this crate.
33    ///
34    /// [`LinearMapInner`]: super::LinearMapInner
35    /// [`LinearMap`]: super::LinearMap
36    /// [`OwnedStorage`]: super::OwnedStorage
37    /// [`ViewStorage`]: super::ViewStorage
38    pub trait LinearMapStorage<K, V>: LinearMapStorageSealed<K, V> {}
39    pub trait LinearMapStorageSealed<K, V>: VecStorage<(K, V)> {
40        fn as_linear_map_view(this: &LinearMapInner<K, V, Self>) -> &LinearMapView<K, V>
41        where
42            Self: LinearMapStorage<K, V>;
43        fn as_linear_map_mut_view(
44            this: &mut LinearMapInner<K, V, Self>,
45        ) -> &mut LinearMapView<K, V>
46        where
47            Self: LinearMapStorage<K, V>;
48    }
49
50    impl<K, V, const N: usize> LinearMapStorage<K, V> for OwnedVecStorage<(K, V), N> {}
51    impl<K, V, const N: usize> LinearMapStorageSealed<K, V> for OwnedVecStorage<(K, V), N> {
52        fn as_linear_map_view(this: &LinearMapInner<K, V, Self>) -> &LinearMapView<K, V>
53        where
54            Self: LinearMapStorage<K, V>,
55        {
56            this
57        }
58        fn as_linear_map_mut_view(this: &mut LinearMapInner<K, V, Self>) -> &mut LinearMapView<K, V>
59        where
60            Self: LinearMapStorage<K, V>,
61        {
62            this
63        }
64    }
65
66    impl<K, V> LinearMapStorage<K, V> for ViewVecStorage<(K, V)> {}
67
68    impl<K, V> LinearMapStorageSealed<K, V> for ViewVecStorage<(K, V)> {
69        fn as_linear_map_view(this: &LinearMapInner<K, V, Self>) -> &LinearMapView<K, V>
70        where
71            Self: LinearMapStorage<K, V>,
72        {
73            this
74        }
75        fn as_linear_map_mut_view(this: &mut LinearMapInner<K, V, Self>) -> &mut LinearMapView<K, V>
76        where
77            Self: LinearMapStorage<K, V>,
78        {
79            this
80        }
81    }
82}
83
84pub use storage::LinearMapStorage;
85/// Implementation of [`LinearMapStorage`] that stores the data in an array whose size is known at compile time.
86pub type OwnedStorage<K, V, const N: usize> = OwnedVecStorage<(K, V), N>;
87/// Implementation of [`LinearMapStorage`] that stores the data in an unsized slice.
88pub type ViewStorage<K, V> = ViewVecStorage<(K, V)>;
89
90/// Base struct for [`LinearMap`] and [`LinearMapView`]
91pub struct LinearMapInner<K, V, S: LinearMapStorage<K, V> + ?Sized> {
92    pub(crate) buffer: VecInner<(K, V), usize, S>,
93}
94
95/// A fixed capacity map/dictionary that performs lookups via linear search.
96///
97/// Note that as this map doesn't use hashing so most operations are *O*(n) instead of *O*(1).
98pub type LinearMap<K, V, const N: usize> = LinearMapInner<K, V, OwnedStorage<K, V, N>>;
99
100/// A dynamic capacity map/dictionary that performs lookups via linear search.
101///
102/// Note that as this map doesn't use hashing so most operations are *O*(n) instead of *O*(1).
103pub type LinearMapView<K, V> = LinearMapInner<K, V, ViewStorage<K, V>>;
104
105impl<K, V, const N: usize> LinearMap<K, V, N> {
106    /// Creates an empty `LinearMap`.
107    ///
108    /// # Examples
109    ///
110    /// ```
111    /// use heapless::LinearMap;
112    ///
113    /// // allocate the map on the stack
114    /// let mut map: LinearMap<&str, isize, 8> = LinearMap::new();
115    ///
116    /// // allocate the map in a static variable
117    /// static mut MAP: LinearMap<&str, isize, 8> = LinearMap::new();
118    /// ```
119    pub const fn new() -> Self {
120        Self { buffer: Vec::new() }
121    }
122}
123
124impl<K, V, S: LinearMapStorage<K, V> + ?Sized> LinearMapInner<K, V, S>
125where
126    K: Eq,
127{
128    /// Get a reference to the `LinearMap`, erasing the `N` const-generic.
129    pub fn as_view(&self) -> &LinearMapView<K, V> {
130        S::as_linear_map_view(self)
131    }
132
133    /// Get a mutable reference to the `LinearMap`, erasing the `N` const-generic.
134    pub fn as_mut_view(&mut self) -> &mut LinearMapView<K, V> {
135        S::as_linear_map_mut_view(self)
136    }
137
138    /// Returns the number of elements that the map can hold.
139    ///
140    /// Computes in *O*(1) time.
141    ///
142    /// # Examples
143    ///
144    /// ```
145    /// use heapless::LinearMap;
146    ///
147    /// let map: LinearMap<&str, isize, 8> = LinearMap::new();
148    /// assert_eq!(map.capacity(), 8);
149    /// ```
150    pub fn capacity(&self) -> usize {
151        self.buffer.capacity()
152    }
153
154    /// Clears the map, removing all key-value pairs.
155    ///
156    /// Computes in *O*(1) time.
157    ///
158    /// # Examples
159    ///
160    /// ```
161    /// use heapless::LinearMap;
162    ///
163    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
164    /// map.insert(1, "a").unwrap();
165    /// map.clear();
166    /// assert!(map.is_empty());
167    /// ```
168    pub fn clear(&mut self) {
169        self.buffer.clear();
170    }
171
172    /// Returns true if the map contains a value for the specified key.
173    ///
174    /// Computes in *O*(n) time.
175    ///
176    /// # Examples
177    ///
178    /// ```
179    /// use heapless::LinearMap;
180    ///
181    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
182    /// map.insert(1, "a").unwrap();
183    /// assert_eq!(map.contains_key(&1), true);
184    /// assert_eq!(map.contains_key(&2), false);
185    /// ```
186    pub fn contains_key(&self, key: &K) -> bool {
187        self.get(key).is_some()
188    }
189
190    /// Returns a reference to the value corresponding to the key.
191    ///
192    /// Computes in *O*(n) time.
193    ///
194    /// # Examples
195    ///
196    /// ```
197    /// use heapless::LinearMap;
198    ///
199    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
200    /// map.insert(1, "a").unwrap();
201    /// assert_eq!(map.get(&1), Some(&"a"));
202    /// assert_eq!(map.get(&2), None);
203    /// ```
204    pub fn get<Q>(&self, key: &Q) -> Option<&V>
205    where
206        K: Borrow<Q>,
207        Q: Eq + ?Sized,
208    {
209        self.iter()
210            .find(|&(k, _)| k.borrow() == key)
211            .map(|(_, v)| v)
212    }
213
214    /// Returns a mutable reference to the value corresponding to the key.
215    ///
216    /// Computes in *O*(n) time.
217    ///
218    /// # Examples
219    ///
220    /// ```
221    /// use heapless::LinearMap;
222    ///
223    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
224    /// map.insert(1, "a").unwrap();
225    /// if let Some(x) = map.get_mut(&1) {
226    ///     *x = "b";
227    /// }
228    /// assert_eq!(map[&1], "b");
229    /// ```
230    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
231    where
232        K: Borrow<Q>,
233        Q: Eq + ?Sized,
234    {
235        self.iter_mut()
236            .find(|&(k, _)| k.borrow() == key)
237            .map(|(_, v)| v)
238    }
239
240    /// Returns the number of elements in this map.
241    ///
242    /// Computes in *O*(1) time.
243    ///
244    /// # Examples
245    ///
246    /// ```
247    /// use heapless::LinearMap;
248    ///
249    /// let mut a: LinearMap<_, _, 8> = LinearMap::new();
250    /// assert_eq!(a.len(), 0);
251    /// a.insert(1, "a").unwrap();
252    /// assert_eq!(a.len(), 1);
253    /// ```
254    pub fn len(&self) -> usize {
255        self.buffer.len()
256    }
257
258    /// Inserts a key-value pair into the map.
259    ///
260    /// If the map did not have this key present, `None` is returned.
261    ///
262    /// If the map did have this key present, the value is updated, and the old value is returned.
263    ///
264    /// Computes in *O*(n) time
265    ///
266    /// # Examples
267    ///
268    /// ```
269    /// use heapless::LinearMap;
270    ///
271    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
272    /// assert_eq!(map.insert(37, "a").unwrap(), None);
273    /// assert_eq!(map.is_empty(), false);
274    ///
275    /// map.insert(37, "b").unwrap();
276    /// assert_eq!(map.insert(37, "c").unwrap(), Some("b"));
277    /// assert_eq!(map[&37], "c");
278    /// ```
279    pub fn insert(&mut self, key: K, mut value: V) -> Result<Option<V>, (K, V)> {
280        if let Some((_, v)) = self.iter_mut().find(|&(k, _)| *k == key) {
281            mem::swap(v, &mut value);
282            return Ok(Some(value));
283        }
284
285        self.buffer.push((key, value))?;
286        Ok(None)
287    }
288
289    /// Returns true if the map contains no elements.
290    ///
291    /// Computes in *O*(1) time.
292    ///
293    /// # Examples
294    ///
295    /// ```
296    /// use heapless::LinearMap;
297    ///
298    /// let mut a: LinearMap<_, _, 8> = LinearMap::new();
299    /// assert!(a.is_empty());
300    /// a.insert(1, "a").unwrap();
301    /// assert!(!a.is_empty());
302    /// ```
303    pub fn is_empty(&self) -> bool {
304        self.len() == 0
305    }
306
307    /// Returns true if the map is full.
308    ///
309    /// Computes in *O*(1) time.
310    ///
311    /// # Examples
312    ///
313    /// ```
314    /// use heapless::LinearMap;
315    ///
316    /// let mut a: LinearMap<_, _, 4> = LinearMap::new();
317    /// assert!(!a.is_full());
318    /// a.insert(1, "a").unwrap();
319    /// a.insert(2, "b").unwrap();
320    /// a.insert(3, "c").unwrap();
321    /// a.insert(4, "d").unwrap();
322    /// assert!(a.is_full());
323    /// ```
324    pub fn is_full(&self) -> bool {
325        self.len() == self.capacity()
326    }
327
328    /// An iterator visiting all key-value pairs in arbitrary order.
329    ///
330    /// # Examples
331    ///
332    /// ```
333    /// use heapless::LinearMap;
334    ///
335    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
336    /// map.insert("a", 1).unwrap();
337    /// map.insert("b", 2).unwrap();
338    /// map.insert("c", 3).unwrap();
339    ///
340    /// for (key, val) in map.iter() {
341    ///     println!("key: {} val: {}", key, val);
342    /// }
343    /// ```
344    pub fn iter(&self) -> Iter<'_, K, V> {
345        Iter {
346            iter: self.buffer.as_slice().iter(),
347        }
348    }
349
350    /// An iterator visiting all key-value pairs in arbitrary order,
351    /// with mutable references to the values.
352    ///
353    /// # Examples
354    ///
355    /// ```
356    /// use heapless::LinearMap;
357    ///
358    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
359    /// map.insert("a", 1).unwrap();
360    /// map.insert("b", 2).unwrap();
361    /// map.insert("c", 3).unwrap();
362    ///
363    /// // Update all values
364    /// for (_, val) in map.iter_mut() {
365    ///     *val = 2;
366    /// }
367    ///
368    /// for (key, val) in &map {
369    ///     println!("key: {} val: {}", key, val);
370    /// }
371    /// ```
372    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
373        IterMut {
374            iter: self.buffer.as_mut_slice().iter_mut(),
375        }
376    }
377
378    /// An iterator visiting all keys in arbitrary order.
379    ///
380    /// # Examples
381    ///
382    /// ```
383    /// use heapless::LinearMap;
384    ///
385    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
386    /// map.insert("a", 1).unwrap();
387    /// map.insert("b", 2).unwrap();
388    /// map.insert("c", 3).unwrap();
389    ///
390    /// for key in map.keys() {
391    ///     println!("{}", key);
392    /// }
393    /// ```
394    pub fn keys(&self) -> impl Iterator<Item = &K> {
395        self.iter().map(|(k, _)| k)
396    }
397
398    /// Removes a key from the map, returning the value at
399    /// the key if the key was previously in the map.
400    ///
401    /// Computes in *O*(n) time
402    ///
403    /// # Examples
404    ///
405    /// ```
406    /// use heapless::LinearMap;
407    ///
408    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
409    /// map.insert(1, "a").unwrap();
410    /// assert_eq!(map.remove(&1), Some("a"));
411    /// assert_eq!(map.remove(&1), None);
412    /// ```
413    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
414    where
415        K: Borrow<Q>,
416        Q: Eq + ?Sized,
417    {
418        let idx = self
419            .keys()
420            .enumerate()
421            .find(|&(_, k)| k.borrow() == key)
422            .map(|(idx, _)| idx);
423
424        idx.map(|idx| self.buffer.swap_remove(idx).1)
425    }
426
427    /// An iterator visiting all values in arbitrary order.
428    ///
429    /// # Examples
430    ///
431    /// ```
432    /// use heapless::LinearMap;
433    ///
434    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
435    /// map.insert("a", 1).unwrap();
436    /// map.insert("b", 2).unwrap();
437    /// map.insert("c", 3).unwrap();
438    ///
439    /// for val in map.values() {
440    ///     println!("{}", val);
441    /// }
442    /// ```
443    pub fn values(&self) -> impl Iterator<Item = &V> {
444        self.iter().map(|(_, v)| v)
445    }
446
447    /// An iterator visiting all values mutably in arbitrary order.
448    ///
449    /// # Examples
450    ///
451    /// ```
452    /// use heapless::LinearMap;
453    ///
454    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
455    /// map.insert("a", 1).unwrap();
456    /// map.insert("b", 2).unwrap();
457    /// map.insert("c", 3).unwrap();
458    ///
459    /// for val in map.values_mut() {
460    ///     *val += 10;
461    /// }
462    ///
463    /// for val in map.values() {
464    ///     println!("{}", val);
465    /// }
466    /// ```
467    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
468        self.iter_mut().map(|(_, v)| v)
469    }
470}
471
472impl<K, V, Q, S: LinearMapStorage<K, V> + ?Sized> ops::Index<&'_ Q> for LinearMapInner<K, V, S>
473where
474    K: Borrow<Q> + Eq,
475    Q: Eq + ?Sized,
476{
477    type Output = V;
478
479    fn index(&self, key: &Q) -> &V {
480        self.get(key).expect("no entry found for key")
481    }
482}
483
484impl<K, V, Q, S: LinearMapStorage<K, V> + ?Sized> ops::IndexMut<&'_ Q> for LinearMapInner<K, V, S>
485where
486    K: Borrow<Q> + Eq,
487    Q: Eq + ?Sized,
488{
489    fn index_mut(&mut self, key: &Q) -> &mut V {
490        self.get_mut(key).expect("no entry found for key")
491    }
492}
493
494impl<K, V, const N: usize> Default for LinearMap<K, V, N>
495where
496    K: Eq,
497{
498    fn default() -> Self {
499        Self::new()
500    }
501}
502
503impl<K, V, const N: usize> Clone for LinearMap<K, V, N>
504where
505    K: Eq + Clone,
506    V: Clone,
507{
508    fn clone(&self) -> Self {
509        Self {
510            buffer: self.buffer.clone(),
511        }
512    }
513}
514
515impl<K, V, S: LinearMapStorage<K, V> + ?Sized> fmt::Debug for LinearMapInner<K, V, S>
516where
517    K: Eq + fmt::Debug,
518    V: fmt::Debug,
519{
520    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
521        f.debug_map().entries(self.iter()).finish()
522    }
523}
524
525impl<K, V, const N: usize> FromIterator<(K, V)> for LinearMap<K, V, N>
526where
527    K: Eq,
528{
529    fn from_iter<I>(iter: I) -> Self
530    where
531        I: IntoIterator<Item = (K, V)>,
532    {
533        let mut out = Self::new();
534        out.buffer.extend(iter);
535        out
536    }
537}
538
539/// An iterator that moves out of a [`LinearMap`].
540///
541/// This struct is created by calling the [`into_iter`](LinearMap::into_iter) method on [`LinearMap`].
542pub struct IntoIter<K, V, const N: usize>
543where
544    K: Eq,
545{
546    inner: <Vec<(K, V), N, usize> as IntoIterator>::IntoIter,
547}
548
549impl<K, V, const N: usize> Iterator for IntoIter<K, V, N>
550where
551    K: Eq,
552{
553    type Item = (K, V);
554    fn next(&mut self) -> Option<Self::Item> {
555        self.inner.next()
556    }
557}
558
559impl<K, V, const N: usize> IntoIterator for LinearMap<K, V, N>
560where
561    K: Eq,
562{
563    type Item = (K, V);
564    type IntoIter = IntoIter<K, V, N>;
565
566    fn into_iter(self) -> Self::IntoIter {
567        IntoIter {
568            inner: self.buffer.into_iter(),
569        }
570    }
571}
572
573impl<'a, K, V, S: LinearMapStorage<K, V> + ?Sized> IntoIterator for &'a LinearMapInner<K, V, S>
574where
575    K: Eq,
576{
577    type Item = (&'a K, &'a V);
578    type IntoIter = Iter<'a, K, V>;
579
580    fn into_iter(self) -> Self::IntoIter {
581        self.iter()
582    }
583}
584
585/// An iterator over the items of a [`LinearMap`]
586///
587/// This struct is created by calling the [`iter`](LinearMap::iter) method on [`LinearMap`].
588#[derive(Clone, Debug)]
589pub struct Iter<'a, K, V> {
590    iter: slice::Iter<'a, (K, V)>,
591}
592
593impl<'a, K, V> Iterator for Iter<'a, K, V> {
594    type Item = (&'a K, &'a V);
595
596    fn next(&mut self) -> Option<Self::Item> {
597        self.iter.next().map(|(k, v)| (k, v))
598    }
599}
600
601/// An iterator over the items of a [`LinearMap`] that allows modifying the items
602///
603/// This struct is created by calling the [`iter_mut`](LinearMap::iter_mut) method on [`LinearMap`].
604#[derive(Debug)]
605pub struct IterMut<'a, K, V> {
606    iter: slice::IterMut<'a, (K, V)>,
607}
608
609impl<'a, K, V> Iterator for IterMut<'a, K, V> {
610    type Item = (&'a K, &'a mut V);
611
612    fn next(&mut self) -> Option<Self::Item> {
613        self.iter.next().map(|(k, v)| (k as &K, v))
614    }
615}
616
617impl<K, V1, V2, S1: LinearMapStorage<K, V1> + ?Sized, S2: LinearMapStorage<K, V2> + ?Sized>
618    PartialEq<LinearMapInner<K, V2, S2>> for LinearMapInner<K, V1, S1>
619where
620    K: Eq,
621    V1: PartialEq<V2>,
622{
623    fn eq(&self, other: &LinearMapInner<K, V2, S2>) -> bool {
624        self.len() == other.len()
625            && self
626                .iter()
627                .all(|(key, value)| other.get(key).is_some_and(|v| *value == *v))
628    }
629}
630
631impl<K, V, S: LinearMapStorage<K, V> + ?Sized> Eq for LinearMapInner<K, V, S>
632where
633    K: Eq,
634    V: PartialEq,
635{
636}
637
638#[cfg(test)]
639mod test {
640    use static_assertions::assert_not_impl_any;
641
642    use super::{LinearMap, LinearMapView};
643
644    // Ensure a `LinearMap` containing `!Send` keys stays `!Send` itself.
645    assert_not_impl_any!(LinearMap<*const (), (), 4>: Send);
646    // Ensure a `LinearMap` containing `!Send` values stays `!Send` itself.
647    assert_not_impl_any!(LinearMap<(), *const (), 4>: Send);
648
649    #[test]
650    fn static_new() {
651        static mut _L: LinearMap<i32, i32, 8> = LinearMap::new();
652    }
653
654    #[test]
655    fn borrow() {
656        use crate::String;
657
658        let mut map = LinearMap::<_, _, 8>::new();
659
660        let s = String::<64>::try_from("Hello, world!").unwrap();
661        map.insert(s, 42).unwrap();
662
663        assert_eq!(map.get("Hello, world!").unwrap(), &42);
664    }
665
666    #[test]
667    fn partial_eq() {
668        {
669            let mut a = LinearMap::<_, _, 1>::new();
670            a.insert("k1", "v1").unwrap();
671
672            let mut b = LinearMap::<_, _, 2>::new();
673            b.insert("k1", "v1").unwrap();
674
675            assert!(a == b);
676
677            b.insert("k2", "v2").unwrap();
678
679            assert!(a != b);
680        }
681
682        {
683            let mut a = LinearMap::<_, _, 2>::new();
684            a.insert("k1", "v1").unwrap();
685            a.insert("k2", "v2").unwrap();
686
687            let mut b = LinearMap::<_, _, 2>::new();
688            b.insert("k2", "v2").unwrap();
689            b.insert("k1", "v1").unwrap();
690
691            assert!(a == b);
692        }
693    }
694
695    #[test]
696    fn drop() {
697        droppable!();
698
699        {
700            let mut v: LinearMap<i32, Droppable, 2> = LinearMap::new();
701            v.insert(0, Droppable::new()).ok().unwrap();
702            v.insert(1, Droppable::new()).ok().unwrap();
703            v.remove(&1).unwrap();
704        }
705
706        assert_eq!(Droppable::count(), 0);
707
708        {
709            let mut v: LinearMap<i32, Droppable, 2> = LinearMap::new();
710            v.insert(0, Droppable::new()).ok().unwrap();
711            v.insert(1, Droppable::new()).ok().unwrap();
712        }
713
714        assert_eq!(Droppable::count(), 0);
715    }
716
717    #[test]
718    fn into_iter() {
719        let mut src: LinearMap<_, _, 4> = LinearMap::new();
720        src.insert("k1", "v1").unwrap();
721        src.insert("k2", "v2").unwrap();
722        src.insert("k3", "v3").unwrap();
723        src.insert("k4", "v4").unwrap();
724        let clone = src.clone();
725        for (k, v) in clone.into_iter() {
726            assert_eq!(v, src.remove(k).unwrap());
727        }
728    }
729
730    fn _test_variance_value<'a: 'b, 'b>(
731        x: LinearMap<u32, &'a (), 42>,
732    ) -> LinearMap<u32, &'b (), 42> {
733        x
734    }
735    fn _test_variance_value_view<'a: 'b, 'b, 'c>(
736        x: &'c LinearMapView<u32, &'a ()>,
737    ) -> &'c LinearMapView<u32, &'b ()> {
738        x
739    }
740    fn _test_variance_key<'a: 'b, 'b>(x: LinearMap<&'a (), u32, 42>) -> LinearMap<&'b (), u32, 42> {
741        x
742    }
743    fn _test_variance_key_view<'a: 'b, 'b, 'c>(
744        x: &'c LinearMapView<&'a (), u32>,
745    ) -> &'c LinearMapView<&'b (), u32> {
746        x
747    }
748
749    #[test]
750    fn partial_eq_floats() {
751        // Make sure `PartialEq` is implemented even if `V` doesn't implement `Eq`.
752        let map: LinearMap<usize, f32, 4> = Default::default();
753        assert_eq!(map, map);
754    }
755}
heapless/linear_map.rs

heapless/
linear_map.rs
