heapless/
linear_map.rs

1use crate::Vec;
2use core::{borrow::Borrow, fmt, iter::FromIterator, mem, ops, slice};
3
4/// A fixed capacity map / dictionary that performs lookups via linear search
5///
6/// Note that as this map doesn't use hashing so most operations are **O(N)** instead of O(1)
7
8pub struct LinearMap<K, V, const N: usize> {
9    pub(crate) buffer: Vec<(K, V), N>,
10}
11
12impl<K, V, const N: usize> LinearMap<K, V, N> {
13    /// Creates an empty `LinearMap`
14    ///
15    /// # Examples
16    ///
17    /// ```
18    /// use heapless::LinearMap;
19    ///
20    /// // allocate the map on the stack
21    /// let mut map: LinearMap<&str, isize, 8> = LinearMap::new();
22    ///
23    /// // allocate the map in a static variable
24    /// static mut MAP: LinearMap<&str, isize, 8> = LinearMap::new();
25    /// ```
26    pub const fn new() -> Self {
27        Self { buffer: Vec::new() }
28    }
29}
30
31impl<K, V, const N: usize> LinearMap<K, V, N>
32where
33    K: Eq,
34{
35    /// Returns the number of elements that the map can hold
36    ///
37    /// Computes in **O(1)** time
38    ///
39    /// # Examples
40    ///
41    /// ```
42    /// use heapless::LinearMap;
43    ///
44    /// let map: LinearMap<&str, isize, 8> = LinearMap::new();
45    /// assert_eq!(map.capacity(), 8);
46    /// ```
47    pub fn capacity(&self) -> usize {
48        N
49    }
50
51    /// Clears the map, removing all key-value pairs
52    ///
53    /// Computes in **O(1)** time
54    ///
55    /// # Examples
56    ///
57    /// ```
58    /// use heapless::LinearMap;
59    ///
60    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
61    /// map.insert(1, "a").unwrap();
62    /// map.clear();
63    /// assert!(map.is_empty());
64    /// ```
65    pub fn clear(&mut self) {
66        self.buffer.clear()
67    }
68
69    /// Returns true if the map contains a value for the specified key.
70    ///
71    /// Computes in **O(N)** time
72    ///
73    /// # Examples
74    ///
75    /// ```
76    /// use heapless::LinearMap;
77    ///
78    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
79    /// map.insert(1, "a").unwrap();
80    /// assert_eq!(map.contains_key(&1), true);
81    /// assert_eq!(map.contains_key(&2), false);
82    /// ```
83    pub fn contains_key(&self, key: &K) -> bool {
84        self.get(key).is_some()
85    }
86
87    /// Returns a reference to the value corresponding to the key
88    ///
89    /// Computes in **O(N)** time
90    ///
91    /// # Examples
92    ///
93    /// ```
94    /// use heapless::LinearMap;
95    ///
96    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
97    /// map.insert(1, "a").unwrap();
98    /// assert_eq!(map.get(&1), Some(&"a"));
99    /// assert_eq!(map.get(&2), None);
100    /// ```
101    pub fn get<Q>(&self, key: &Q) -> Option<&V>
102    where
103        K: Borrow<Q>,
104        Q: Eq + ?Sized,
105    {
106        self.iter()
107            .find(|&(k, _)| k.borrow() == key)
108            .map(|(_, v)| v)
109    }
110
111    /// Returns a mutable reference to the value corresponding to the key
112    ///
113    /// Computes in **O(N)** time
114    ///
115    /// # Examples
116    ///
117    /// ```
118    /// use heapless::LinearMap;
119    ///
120    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
121    /// map.insert(1, "a").unwrap();
122    /// if let Some(x) = map.get_mut(&1) {
123    ///     *x = "b";
124    /// }
125    /// assert_eq!(map[&1], "b");
126    /// ```
127    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
128    where
129        K: Borrow<Q>,
130        Q: Eq + ?Sized,
131    {
132        self.iter_mut()
133            .find(|&(k, _)| k.borrow() == key)
134            .map(|(_, v)| v)
135    }
136
137    /// Returns the number of elements in this map
138    ///
139    /// Computes in **O(1)** time
140    ///
141    /// # Examples
142    ///
143    /// ```
144    /// use heapless::LinearMap;
145    ///
146    /// let mut a: LinearMap<_, _, 8> = LinearMap::new();
147    /// assert_eq!(a.len(), 0);
148    /// a.insert(1, "a").unwrap();
149    /// assert_eq!(a.len(), 1);
150    /// ```
151    pub fn len(&self) -> usize {
152        self.buffer.len()
153    }
154
155    /// Inserts a key-value pair into the map.
156    ///
157    /// If the map did not have this key present, `None` is returned.
158    ///
159    /// If the map did have this key present, the value is updated, and the old value is returned.
160    ///
161    /// Computes in **O(N)** time
162    ///
163    /// # Examples
164    ///
165    /// ```
166    /// use heapless::LinearMap;
167    ///
168    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
169    /// assert_eq!(map.insert(37, "a").unwrap(), None);
170    /// assert_eq!(map.is_empty(), false);
171    ///
172    /// map.insert(37, "b").unwrap();
173    /// assert_eq!(map.insert(37, "c").unwrap(), Some("b"));
174    /// assert_eq!(map[&37], "c");
175    /// ```
176    pub fn insert(&mut self, key: K, mut value: V) -> Result<Option<V>, (K, V)> {
177        if let Some((_, v)) = self.iter_mut().find(|&(k, _)| *k == key) {
178            mem::swap(v, &mut value);
179            return Ok(Some(value));
180        }
181
182        self.buffer.push((key, value))?;
183        Ok(None)
184    }
185
186    /// Returns true if the map contains no elements
187    ///
188    /// Computes in **O(1)** time
189    ///
190    /// # Examples
191    ///
192    /// ```
193    /// use heapless::LinearMap;
194    ///
195    /// let mut a: LinearMap<_, _, 8> = LinearMap::new();
196    /// assert!(a.is_empty());
197    /// a.insert(1, "a").unwrap();
198    /// assert!(!a.is_empty());
199    /// ```
200    pub fn is_empty(&self) -> bool {
201        self.len() == 0
202    }
203
204    /// An iterator visiting all key-value pairs in arbitrary order.
205    ///
206    /// # Examples
207    ///
208    /// ```
209    /// use heapless::LinearMap;
210    ///
211    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
212    /// map.insert("a", 1).unwrap();
213    /// map.insert("b", 2).unwrap();
214    /// map.insert("c", 3).unwrap();
215    ///
216    /// for (key, val) in map.iter() {
217    ///     println!("key: {} val: {}", key, val);
218    /// }
219    /// ```
220    pub fn iter(&self) -> Iter<'_, K, V> {
221        Iter {
222            iter: self.buffer.as_slice().iter(),
223        }
224    }
225
226    /// An iterator visiting all key-value pairs in arbitrary order, with mutable references to the
227    /// values
228    ///
229    /// # Examples
230    ///
231    /// ```
232    /// use heapless::LinearMap;
233    ///
234    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
235    /// map.insert("a", 1).unwrap();
236    /// map.insert("b", 2).unwrap();
237    /// map.insert("c", 3).unwrap();
238    ///
239    /// // Update all values
240    /// for (_, val) in map.iter_mut() {
241    ///     *val = 2;
242    /// }
243    ///
244    /// for (key, val) in &map {
245    ///     println!("key: {} val: {}", key, val);
246    /// }
247    /// ```
248    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
249        IterMut {
250            iter: self.buffer.as_mut_slice().iter_mut(),
251        }
252    }
253
254    /// An iterator visiting all keys in arbitrary order
255    ///
256    /// # Examples
257    ///
258    /// ```
259    /// use heapless::LinearMap;
260    ///
261    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
262    /// map.insert("a", 1).unwrap();
263    /// map.insert("b", 2).unwrap();
264    /// map.insert("c", 3).unwrap();
265    ///
266    /// for key in map.keys() {
267    ///     println!("{}", key);
268    /// }
269    /// ```
270    pub fn keys(&self) -> impl Iterator<Item = &K> {
271        self.iter().map(|(k, _)| k)
272    }
273
274    /// Removes a key from the map, returning the value at the key if the key was previously in the
275    /// map
276    ///
277    /// Computes in **O(N)** time
278    ///
279    /// # Examples
280    ///
281    /// ```
282    /// use heapless::LinearMap;
283    ///
284    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
285    /// map.insert(1, "a").unwrap();
286    /// assert_eq!(map.remove(&1), Some("a"));
287    /// assert_eq!(map.remove(&1), None);
288    /// ```
289    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
290    where
291        K: Borrow<Q>,
292        Q: Eq + ?Sized,
293    {
294        let idx = self
295            .keys()
296            .enumerate()
297            .find(|&(_, k)| k.borrow() == key)
298            .map(|(idx, _)| idx);
299
300        idx.map(|idx| self.buffer.swap_remove(idx).1)
301    }
302
303    /// An iterator visiting all values in arbitrary order
304    ///
305    /// # Examples
306    ///
307    /// ```
308    /// use heapless::LinearMap;
309    ///
310    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
311    /// map.insert("a", 1).unwrap();
312    /// map.insert("b", 2).unwrap();
313    /// map.insert("c", 3).unwrap();
314    ///
315    /// for val in map.values() {
316    ///     println!("{}", val);
317    /// }
318    /// ```
319    pub fn values(&self) -> impl Iterator<Item = &V> {
320        self.iter().map(|(_, v)| v)
321    }
322
323    /// An iterator visiting all values mutably in arbitrary order
324    ///
325    /// # Examples
326    ///
327    /// ```
328    /// use heapless::LinearMap;
329    ///
330    /// let mut map: LinearMap<_, _, 8> = LinearMap::new();
331    /// map.insert("a", 1).unwrap();
332    /// map.insert("b", 2).unwrap();
333    /// map.insert("c", 3).unwrap();
334    ///
335    /// for val in map.values_mut() {
336    ///     *val += 10;
337    /// }
338    ///
339    /// for val in map.values() {
340    ///     println!("{}", val);
341    /// }
342    /// ```
343    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
344        self.iter_mut().map(|(_, v)| v)
345    }
346}
347
348impl<'a, K, V, Q, const N: usize> ops::Index<&'a Q> for LinearMap<K, V, N>
349where
350    K: Borrow<Q> + Eq,
351    Q: Eq + ?Sized,
352{
353    type Output = V;
354
355    fn index(&self, key: &Q) -> &V {
356        self.get(key).expect("no entry found for key")
357    }
358}
359
360impl<'a, K, V, Q, const N: usize> ops::IndexMut<&'a Q> for LinearMap<K, V, N>
361where
362    K: Borrow<Q> + Eq,
363    Q: Eq + ?Sized,
364{
365    fn index_mut(&mut self, key: &Q) -> &mut V {
366        self.get_mut(key).expect("no entry found for key")
367    }
368}
369
370impl<K, V, const N: usize> Default for LinearMap<K, V, N>
371where
372    K: Eq,
373{
374    fn default() -> Self {
375        Self::new()
376    }
377}
378
379impl<K, V, const N: usize> Clone for LinearMap<K, V, N>
380where
381    K: Eq + Clone,
382    V: Clone,
383{
384    fn clone(&self) -> Self {
385        Self {
386            buffer: self.buffer.clone(),
387        }
388    }
389}
390
391impl<K, V, const N: usize> fmt::Debug for LinearMap<K, V, N>
392where
393    K: Eq + fmt::Debug,
394    V: fmt::Debug,
395{
396    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
397        f.debug_map().entries(self.iter()).finish()
398    }
399}
400
401impl<K, V, const N: usize> FromIterator<(K, V)> for LinearMap<K, V, N>
402where
403    K: Eq,
404{
405    fn from_iter<I>(iter: I) -> Self
406    where
407        I: IntoIterator<Item = (K, V)>,
408    {
409        let mut out = Self::new();
410        out.buffer.extend(iter);
411        out
412    }
413}
414
415pub struct IntoIter<K, V, const N: usize>
416where
417    K: Eq,
418{
419    inner: <Vec<(K, V), N> as IntoIterator>::IntoIter,
420}
421
422impl<K, V, const N: usize> Iterator for IntoIter<K, V, N>
423where
424    K: Eq,
425{
426    type Item = (K, V);
427    fn next(&mut self) -> Option<Self::Item> {
428        self.inner.next()
429    }
430}
431
432impl<'a, K, V, const N: usize> IntoIterator for &'a LinearMap<K, V, N>
433where
434    K: Eq,
435{
436    type Item = (&'a K, &'a V);
437    type IntoIter = Iter<'a, K, V>;
438
439    fn into_iter(self) -> Self::IntoIter {
440        self.iter()
441    }
442}
443
444pub struct Iter<'a, K, V> {
445    iter: slice::Iter<'a, (K, V)>,
446}
447
448impl<'a, K, V> Iterator for Iter<'a, K, V> {
449    type Item = (&'a K, &'a V);
450
451    fn next(&mut self) -> Option<Self::Item> {
452        self.iter.next().map(|&(ref k, ref v)| (k, v))
453    }
454}
455
456impl<'a, K, V> Clone for Iter<'a, K, V> {
457    fn clone(&self) -> Self {
458        Self {
459            iter: self.iter.clone(),
460        }
461    }
462}
463
464pub struct IterMut<'a, K, V> {
465    iter: slice::IterMut<'a, (K, V)>,
466}
467
468impl<'a, K, V> Iterator for IterMut<'a, K, V> {
469    type Item = (&'a K, &'a mut V);
470
471    fn next(&mut self) -> Option<Self::Item> {
472        self.iter.next().map(|&mut (ref k, ref mut v)| (k, v))
473    }
474}
475
476impl<K, V, const N: usize, const N2: usize> PartialEq<LinearMap<K, V, N2>> for LinearMap<K, V, N>
477where
478    K: Eq,
479    V: PartialEq,
480{
481    fn eq(&self, other: &LinearMap<K, V, N2>) -> bool {
482        self.len() == other.len()
483            && self
484                .iter()
485                .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
486    }
487}
488
489impl<K, V, const N: usize> Eq for LinearMap<K, V, N>
490where
491    K: Eq,
492    V: PartialEq,
493{
494}
495
496#[cfg(test)]
497mod test {
498    use crate::LinearMap;
499
500    #[test]
501    fn static_new() {
502        static mut _L: LinearMap<i32, i32, 8> = LinearMap::new();
503    }
504
505    #[test]
506    fn partial_eq() {
507        {
508            let mut a = LinearMap::<_, _, 1>::new();
509            a.insert("k1", "v1").unwrap();
510
511            let mut b = LinearMap::<_, _, 2>::new();
512            b.insert("k1", "v1").unwrap();
513
514            assert!(a == b);
515
516            b.insert("k2", "v2").unwrap();
517
518            assert!(a != b);
519        }
520
521        {
522            let mut a = LinearMap::<_, _, 2>::new();
523            a.insert("k1", "v1").unwrap();
524            a.insert("k2", "v2").unwrap();
525
526            let mut b = LinearMap::<_, _, 2>::new();
527            b.insert("k2", "v2").unwrap();
528            b.insert("k1", "v1").unwrap();
529
530            assert!(a == b);
531        }
532    }
533
534    #[test]
535    fn drop() {
536        droppable!();
537
538        {
539            let mut v: LinearMap<i32, Droppable, 2> = LinearMap::new();
540            v.insert(0, Droppable::new()).ok().unwrap();
541            v.insert(1, Droppable::new()).ok().unwrap();
542            v.remove(&1).unwrap();
543        }
544
545        assert_eq!(Droppable::count(), 0);
546
547        {
548            let mut v: LinearMap<i32, Droppable, 2> = LinearMap::new();
549            v.insert(0, Droppable::new()).ok().unwrap();
550            v.insert(1, Droppable::new()).ok().unwrap();
551        }
552
553        assert_eq!(Droppable::count(), 0);
554    }
555}
heapless/linear_map.rs

heapless/
linear_map.rs
