micromap_rawl/
map.rs

1use crate::{Drain, Entry, Map, OccupiedEntry, VacantEntry};
2use core::borrow::Borrow;
3
4mod internal {
5    use crate::Map;
6
7    impl<K: PartialEq, V, const N: usize> Map<K, V, N> {
8        /// Internal function to get access via reference to the element in the internal array.
9        #[inline]
10        pub(crate) const fn item_ref(
11            &self,
12            i: usize,
13        ) -> &(K, V) {
14            unsafe { self.pairs[i].assume_init_ref() }
15        }
16
17        /// Internal function to get mutable access via reference to the element in the internal array.
18        #[inline]
19        pub(crate) fn item_mut(
20            &mut self,
21            i: usize,
22        ) -> &mut V {
23            &mut unsafe { self.pairs[i].assume_init_mut() }.1
24        }
25
26        /// Internal function to get access to the element in the internal array.
27        #[inline]
28        pub(crate) fn item_read(
29            &mut self,
30            i: usize,
31        ) -> (K, V) {
32            unsafe { self.pairs[i].assume_init_read() }
33        }
34
35        /// Internal function to get access to the element in the internal array.
36        #[inline]
37        pub(crate) fn item_drop(
38            &mut self,
39            i: usize,
40        ) {
41            unsafe { self.pairs[i].assume_init_drop() };
42        }
43
44        /// Internal function to get access to the element in the internal array.
45        #[inline]
46        pub(crate) fn item_write(
47            &mut self,
48            i: usize,
49            val: (K, V),
50        ) {
51            self.pairs[i].write(val);
52        }
53
54        /// Remove an index (by swapping the last one here and reducing the length)
55        #[inline]
56        pub(crate) fn remove_index_drop(
57            &mut self,
58            i: usize,
59        ) {
60            self.item_drop(i);
61
62            self.len -= 1;
63            if i != self.len {
64                let value = self.item_read(self.len);
65                self.item_write(i, value);
66            }
67        }
68
69        /// Remove an index (by swapping the last one here and reducing the length)
70        #[inline]
71        pub(crate) fn remove_index_read(
72            &mut self,
73            i: usize,
74        ) -> (K, V) {
75            let result = self.item_read(i);
76
77            self.len -= 1;
78            if i != self.len {
79                let value = self.item_read(self.len);
80                self.item_write(i, value);
81            }
82
83            result
84        }
85    }
86}
87
88impl<K: PartialEq, V, const N: usize> Map<K, V, N> {
89    /// Get its total capacity.
90    #[inline]
91    #[must_use]
92    pub const fn capacity(&self) -> usize {
93        N
94    }
95
96    /// Is it empty?
97    #[inline]
98    #[must_use]
99    pub const fn is_empty(&self) -> bool {
100        self.len() == 0
101    }
102
103    /// Return the total number of pairs inside.
104    #[inline]
105    #[must_use]
106    pub const fn len(&self) -> usize {
107        self.len
108    }
109
110    /// Clears the map, returning all key-value pairs as an iterator. Keeps the allocated memory for reuse.
111    ///
112    /// If the returned iterator is dropped before being fully consumed, it drops the remaining key-value pairs. The returned iterator keeps a mutable borrow on the map to optimize its implementation.
113    pub fn drain(&mut self) -> Drain<'_, K, V> {
114        let drain = Drain {
115            iter: self.pairs[0..self.len].iter_mut(),
116        };
117        self.len = 0;
118        drain
119    }
120
121    /// Does the map contain this key?
122    #[inline]
123    #[must_use]
124    pub fn contains_key<Q: PartialEq + ?Sized>(
125        &self,
126        k: &Q,
127    ) -> bool
128    where
129        K: Borrow<Q>,
130    {
131        for i in 0..self.len {
132            let p = self.item_ref(i);
133            if p.0.borrow() == k {
134                return true;
135            }
136        }
137        false
138    }
139
140    /// Remove by key.
141    #[inline]
142    pub fn remove<Q: PartialEq + ?Sized>(
143        &mut self,
144        k: &Q,
145    ) -> Option<V>
146    where
147        K: Borrow<Q>,
148    {
149        for i in 0..self.len {
150            let p = self.item_ref(i);
151            if p.0.borrow() == k {
152                return Some(self.remove_index_read(i).1);
153            }
154        }
155        None
156    }
157
158    /// Insert a single pair into the map.
159    ///
160    /// # Panics
161    ///
162    /// It may panic if there are too many pairs in the map already. Pay attention,
163    /// it panics only in the "debug" mode. In the "release" mode, you are going to get
164    /// undefined behavior. This is done for the sake of performance, in order to
165    /// avoid a repetitive check for the boundary condition on every `insert()`.
166    #[inline]
167    pub fn insert(
168        &mut self,
169        k: K,
170        v: V,
171    ) -> Option<V> {
172        let (_, existing_value) = self.insert_i(k, v);
173        existing_value
174    }
175
176    #[inline]
177    pub(crate) fn insert_i(
178        &mut self,
179        k: K,
180        v: V,
181    ) -> (usize, Option<V>) {
182        let mut target = self.len;
183        let mut i = 0;
184        let mut existing_value = None;
185        loop {
186            if i == self.len {
187                break;
188            }
189            let p = self.item_ref(i);
190            if p.0 == k {
191                target = i;
192                existing_value = Some(self.item_read(i).1);
193                break;
194            }
195            i += 1;
196        }
197        self.item_write(target, (k, v));
198        if target == self.len {
199            self.len += 1;
200        }
201
202        (target, existing_value)
203    }
204
205    /// Get a reference to a single value.
206    #[inline]
207    #[must_use]
208    pub fn get<Q: PartialEq + ?Sized>(
209        &self,
210        k: &Q,
211    ) -> Option<&V>
212    where
213        K: Borrow<Q>,
214    {
215        for i in 0..self.len {
216            let p = self.item_ref(i);
217            if p.0.borrow() == k {
218                return Some(&p.1);
219            }
220        }
221        None
222    }
223
224    /// Get a mutable reference to a single value.
225    ///
226    /// # Panics
227    ///
228    /// If can't turn it into a mutable state.
229    #[inline]
230    #[must_use]
231    pub fn get_mut<Q: PartialEq + ?Sized>(
232        &mut self,
233        k: &Q,
234    ) -> Option<&mut V>
235    where
236        K: Borrow<Q>,
237    {
238        for i in 0..self.len {
239            let p = self.item_ref(i);
240            if p.0.borrow() == k {
241                return Some(self.item_mut(i));
242            }
243        }
244        None
245    }
246
247    /// Remove all pairs from it, but keep the space intact for future use.
248    #[inline]
249    pub fn clear(&mut self) {
250        for i in 0..self.len {
251            self.item_drop(i);
252        }
253        self.len = 0;
254    }
255
256    /// Retains only the elements specified by the predicate.
257    #[inline]
258    pub fn retain<F: Fn(&K, &V) -> bool>(
259        &mut self,
260        f: F,
261    ) {
262        let mut i = 0;
263        while i < self.len {
264            let p = self.item_ref(i);
265            if f(&p.0, &p.1) {
266                // do not remove -> next index
267                i += 1;
268            } else {
269                self.remove_index_drop(i);
270                // recheck the same index
271            }
272        }
273    }
274
275    /// Returns the key-value pair corresponding to the supplied key.
276    #[inline]
277    pub fn get_key_value<Q: PartialEq + ?Sized>(
278        &self,
279        k: &Q,
280    ) -> Option<(&K, &V)>
281    where
282        K: Borrow<Q>,
283    {
284        for i in 0..self.len {
285            let p = self.item_ref(i);
286            if p.0.borrow() == k {
287                return Some((&p.0, &p.1));
288            }
289        }
290        None
291    }
292
293    /// Removes a key from the map, returning the stored key and value if the
294    /// key was previously in the map.
295    #[inline]
296    pub fn remove_entry<Q: PartialEq + ?Sized>(
297        &mut self,
298        k: &Q,
299    ) -> Option<(K, V)>
300    where
301        K: Borrow<Q>,
302    {
303        for i in 0..self.len {
304            let p = self.item_ref(i);
305            if p.0.borrow() == k {
306                return Some(self.remove_index_read(i));
307            }
308        }
309        None
310    }
311
312    pub fn entry(
313        &mut self,
314        k: K,
315    ) -> Entry<'_, K, V, N> {
316        for i in 0..self.len {
317            let p = self.item_ref(i);
318            if p.0 == k {
319                return Entry::Occupied(OccupiedEntry {
320                    index: i,
321                    table: self,
322                });
323            }
324        }
325        Entry::Vacant(VacantEntry {
326            key: k,
327            table: self,
328        })
329    }
330}
331
332#[cfg(test)]
333mod test {
334    use super::*;
335
336    #[test]
337    fn insert_and_check_length() {
338        let mut m: Map<String, i32, 10> = Map::new();
339        assert_eq!(m.insert("first".to_string(), 42), None);
340        assert_eq!(1, m.len());
341        assert_eq!(m.insert("second".to_string(), 16), None);
342        assert_eq!(2, m.len());
343        assert_eq!(m.insert("first".to_string(), 16), Some(42));
344        assert_eq!(2, m.len());
345    }
346
347    #[test]
348    fn overwrites_keys() {
349        let mut m: Map<i32, i32, 1> = Map::new();
350        assert_eq!(m.insert(1, 42), None);
351        assert_eq!(m.insert(1, 42), Some(42));
352        assert_eq!(1, m.len());
353    }
354
355    #[test]
356    #[should_panic]
357    #[cfg(debug_assertions)]
358    fn cant_write_into_empty_map() {
359        let mut m: Map<i32, i32, 0> = Map::new();
360        assert_eq!(m.insert(1, 42), None);
361    }
362
363    #[test]
364    fn empty_length() {
365        let m: Map<u32, u32, 10> = Map::new();
366        assert_eq!(0, m.len());
367    }
368
369    #[test]
370    fn is_empty_check() {
371        let mut m: Map<u32, u32, 10> = Map::new();
372        assert!(m.is_empty());
373        assert_eq!(m.insert(42, 42), None);
374        assert!(!m.is_empty());
375    }
376
377    #[test]
378    fn insert_and_gets() {
379        let mut m: Map<String, i32, 10> = Map::new();
380        assert_eq!(m.insert("one".to_string(), 42), None);
381        assert_eq!(m.insert("two".to_string(), 16), None);
382        assert_eq!(16, *m.get("two").unwrap());
383    }
384
385    #[test]
386    fn insert_and_gets_mut() {
387        let mut m: Map<i32, [i32; 3], 10> = Map::new();
388        assert_eq!(m.insert(42, [1, 2, 3]), None);
389        let a = m.get_mut(&42).unwrap();
390        a[0] = 500;
391        assert_eq!(500, m.get(&42).unwrap()[0]);
392    }
393
394    #[test]
395    fn checks_key() {
396        let mut m: Map<String, i32, 10> = Map::new();
397        assert_eq!(m.insert("one".to_string(), 42), None);
398        assert!(m.contains_key("one"));
399        assert!(!m.contains_key("another"));
400    }
401
402    #[test]
403    fn gets_missing_key() {
404        let mut m: Map<String, i32, 10> = Map::new();
405        assert_eq!(m.insert("one".to_string(), 42), None);
406        assert!(m.get("two").is_none());
407    }
408
409    #[test]
410    fn mut_gets_missing_key() {
411        let mut m: Map<String, i32, 10> = Map::new();
412        assert_eq!(m.insert("one".to_string(), 42), None);
413        assert!(m.get_mut("two").is_none());
414    }
415
416    #[test]
417    fn removes_simple_pair() {
418        let mut m: Map<String, i32, 10> = Map::new();
419        assert_eq!(m.insert("one".to_string(), 42), None);
420        assert_eq!(m.remove("one"), Some(42));
421        assert_eq!(m.remove("another"), None);
422        assert!(m.get("one").is_none());
423    }
424
425    #[cfg(test)]
426    #[derive(Clone, PartialEq, Debug)]
427    struct Foo {
428        v: [u32; 3],
429    }
430
431    #[test]
432    fn insert_struct() {
433        let mut m: Map<u8, Foo, 8> = Map::new();
434        let foo = Foo { v: [1, 2, 100] };
435        assert_eq!(m.insert(1, foo), None);
436        assert_eq!(100, m.into_iter().next().unwrap().1.v[2]);
437    }
438
439    #[cfg(test)]
440    #[derive(Clone, PartialEq, Debug)]
441    struct Composite {
442        r: Map<u8, u8, 1>,
443    }
444
445    #[test]
446    fn insert_composite() {
447        let mut m: Map<u8, Composite, 8> = Map::new();
448        let c = Composite { r: Map::new() };
449        assert_eq!(m.insert(1, c), None);
450        assert_eq!(0, m.into_iter().next().unwrap().1.r.len());
451    }
452
453    #[test]
454    fn large_map_in_heap() {
455        let m: Box<Map<u64, [u64; 10], 10>> = Box::new(Map::new());
456        assert_eq!(0, m.len());
457    }
458
459    #[test]
460    fn clears_it_up() {
461        let mut m: Map<String, i32, 10> = Map::new();
462        assert_eq!(m.insert("one".to_string(), 42), None);
463        m.clear();
464        assert_eq!(0, m.len());
465    }
466
467    #[test]
468    fn retain_test() {
469        let vec: Vec<(i32, i32)> = (0..8).map(|x| (x, x * 10)).collect();
470        let mut m: Map<i32, i32, 10> = Map::from_iter(vec);
471        assert_eq!(m.len(), 8);
472        m.retain(|&k, _| k < 6);
473        assert_eq!(m.len(), 6);
474        m.retain(|_, &v| v > 30);
475        assert_eq!(m.len(), 2);
476    }
477
478    #[test]
479    fn insert_many_and_remove() {
480        let mut m: Map<usize, u64, 4> = Map::new();
481        for _ in 0..2 {
482            let cap = m.capacity();
483            for i in 0..cap {
484                assert_eq!(m.insert(i, 256), None);
485                assert_eq!(m.remove(&i), Some(256));
486            }
487        }
488    }
489
490    #[test]
491    fn get_key_value() {
492        let mut m: Map<String, i32, 10> = Map::new();
493        let k = "key".to_string();
494        assert_eq!(m.insert(k.clone(), 42), None);
495        assert_eq!(m.get_key_value(&k), Some((&k, &42)));
496        assert!(m.contains_key(&k));
497    }
498
499    #[test]
500    fn get_absent_key_value() {
501        let mut m: Map<String, i32, 10> = Map::new();
502        assert_eq!(m.insert("one".to_string(), 42), None);
503        assert_eq!(m.get_key_value("two"), None);
504    }
505
506    #[test]
507    fn remove_entry_present() {
508        let mut m: Map<String, i32, 10> = Map::new();
509        let k = "key".to_string();
510        assert_eq!(m.insert(k.clone(), 42), None);
511        assert_eq!(m.remove_entry(&k), Some((k.clone(), 42)));
512        assert!(!m.contains_key(&k));
513    }
514
515    #[test]
516    fn remove_entry_absent() {
517        let mut m: Map<String, i32, 10> = Map::new();
518        assert_eq!(m.insert("one".to_string(), 42), None);
519        assert_eq!(m.remove_entry("two"), None);
520    }
521
522    #[test]
523    fn drop_removed_entry() {
524        use std::rc::Rc;
525        let mut m: Map<(), Rc<()>, 8> = Map::new();
526        let v = Rc::new(());
527        assert_eq!(m.insert((), Rc::clone(&v)), None);
528        assert_eq!(Rc::strong_count(&v), 2);
529        assert_eq!(m.remove_entry(&()), Some(((), Rc::clone(&v))));
530        assert_eq!(Rc::strong_count(&v), 1);
531    }
532
533    #[test]
534    fn insert_after_remove() {
535        let mut m: Map<_, _, 1> = Map::new();
536        assert_eq!(m.insert(1, 2), None);
537        assert_eq!(m.remove(&1), Some(2));
538        assert_eq!(m.insert(1, 3), None);
539    }
540
541    #[test]
542    fn insert_drop_duplicate() {
543        use std::rc::Rc;
544        let mut m: Map<_, _, 1> = Map::new();
545        let v = Rc::new(());
546        assert_eq!(m.insert((), Rc::clone(&v)), None);
547        assert_eq!(Rc::strong_count(&v), 2);
548        assert_eq!(m.insert((), Rc::clone(&v)), Some(Rc::clone(&v)));
549        assert_eq!(Rc::strong_count(&v), 2);
550    }
551
552    #[test]
553    fn insert_duplicate_after_remove() {
554        let mut m: Map<_, _, 2> = Map::new();
555        assert_eq!(m.insert(1, 1), None);
556        assert_eq!(m.insert(2, 2), None);
557        assert_eq!(m.remove(&1), Some(1));
558        assert_eq!(m.insert(2, 3), Some(2));
559        assert_eq!(1, m.len());
560        assert_eq!(3, m[&2]);
561    }
562}
micromap_rawl/map.rs

micromap_rawl/
map.rs
