slabmap/
lib.rs

1/*! This crate provides the type [`SlabMap`].
2[`SlabMap`] is HashMap-like collection that automatically determines the key.
3
4# Examples
5
6```
7use slabmap::SlabMap;
8
9let mut s = SlabMap::new();
10let key_a = s.insert("aaa");
11let key_b = s.insert("bbb");
12
13assert_eq!(s[key_a], "aaa");
14assert_eq!(s[key_b], "bbb");
15
16for (key, value) in &s {
17    println!("{} -> {}", key, value);
18}
19
20assert_eq!(s.remove(key_a), Some("aaa"));
21assert_eq!(s.remove(key_a), None);
22```
23*/
24
25use std::{
26    collections::TryReserveError,
27    fmt::Debug,
28    iter::{Enumerate, FusedIterator},
29    mem::replace,
30};
31
32use derive_ex::derive_ex;
33
34#[cfg(test)]
35mod tests;
36
37/**
38A fast HashMap-like collection that automatically determines the key.
39*/
40
41#[derive_ex(Clone(bound(T)))]
42pub struct SlabMap<T> {
43    entries: Vec<Entry<T>>,
44    next_vacant_idx: usize,
45    len: usize,
46    non_optimized_count: usize,
47}
48const INVALID_INDEX: usize = usize::MAX;
49
50#[derive(Clone, Debug)]
51enum Entry<T> {
52    Occupied(T),
53    VacantHead { vacant_body_len: usize },
54    VacantTail { next_vacant_idx: usize },
55}
56
57impl<T> SlabMap<T> {
58    /// Constructs a new, empty `SlabMap<T>`.
59    /// The SlabMap will not allocate until elements are pushed onto it.
60    #[inline]
61    pub const fn new() -> Self {
62        Self {
63            entries: Vec::new(),
64            next_vacant_idx: INVALID_INDEX,
65            len: 0,
66            non_optimized_count: 0,
67        }
68    }
69
70    /// Constructs a new, empty `SlabMap<T>` with the specified capacity.
71    #[inline]
72    pub fn with_capacity(capacity: usize) -> Self {
73        Self {
74            entries: Vec::with_capacity(capacity),
75            next_vacant_idx: INVALID_INDEX,
76            len: 0,
77            non_optimized_count: 0,
78        }
79    }
80
81    /// Constructs as new `SlabMap<T>` from keys and values with at least the specified capacity.
82    pub fn from_iter_with_capacity(
83        iter: impl IntoIterator<Item = (usize, T)>,
84        capacity: usize,
85    ) -> Self {
86        let mut entries = Vec::with_capacity(capacity);
87        for (key, value) in iter {
88            if key >= entries.len() {
89                entries.resize_with(key + 1, || Entry::VacantTail {
90                    next_vacant_idx: INVALID_INDEX,
91                });
92            }
93            entries[key] = Entry::Occupied(value);
94        }
95        let mut this = Self {
96            entries,
97            next_vacant_idx: INVALID_INDEX,
98            len: usize::MAX,
99            non_optimized_count: usize::MAX,
100        };
101        this.force_optimize();
102        this
103    }
104
105    /// Returns the number of elements the SlabMap can hold without reallocating.
106    #[inline]
107    pub fn capacity(&self) -> usize {
108        self.entries.capacity()
109    }
110
111    /// Reserves capacity for at least additional more elements to be inserted in the given `SlabMap<T>`.
112    ///
113    /// # Panics
114    /// Panics if the new capacity overflows usize.    
115    #[inline]
116    pub fn reserve(&mut self, additional: usize) {
117        self.entries.reserve(self.entries_additional(additional));
118    }
119
120    /// Try to reserve capacity for at least additional more elements to be inserted in the given `SlabMap<T>`.
121    #[inline]
122    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
123        self.entries
124            .try_reserve(self.entries_additional(additional))
125    }
126
127    /// Reserves the minimum capacity for exactly additional more elements to be inserted in the given `SlabMap<T>`.
128    ///
129    /// # Panics
130    /// Panics if the new capacity overflows usize.    
131    #[inline]
132    pub fn reserve_exact(&mut self, additional: usize) {
133        self.entries
134            .reserve_exact(self.entries_additional(additional));
135    }
136
137    /// Try to reserve the minimum capacity for exactly additional more elements to be inserted in the given `SlabMap<T>`.
138    #[inline]
139    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
140        self.entries
141            .try_reserve_exact(self.entries_additional(additional))
142    }
143
144    #[inline]
145    fn entries_additional(&self, additional: usize) -> usize {
146        additional.saturating_sub(self.entries.len() - self.len)
147    }
148
149    /// Returns the number of elements in the SlabMap.
150    ///
151    /// # Examples
152    /// ```
153    /// use slabmap::SlabMap;
154    ///
155    /// let mut s = SlabMap::new();
156    /// assert_eq!(s.len(), 0);
157    ///
158    /// let key1 = s.insert(10);
159    /// let key2 = s.insert(15);
160    ///
161    /// assert_eq!(s.len(), 2);
162    ///
163    /// s.remove(key1);
164    /// assert_eq!(s.len(), 1);
165    ///
166    /// s.remove(key2);
167    /// assert_eq!(s.len(), 0);
168    /// ```    
169    #[inline]
170    pub fn len(&self) -> usize {
171        self.len
172    }
173
174    /// Returns true if the SlabMap contains no elements.
175    ///    
176    /// # Examples
177    /// ```
178    /// use slabmap::SlabMap;
179    ///
180    /// let mut s = SlabMap::new();
181    /// assert_eq!(s.is_empty(), true);
182    ///
183    /// let key = s.insert("a");
184    /// assert_eq!(s.is_empty(), false);
185    ///
186    /// s.remove(key);
187    /// assert_eq!(s.is_empty(), true);
188    /// ```
189    #[inline]
190    pub fn is_empty(&self) -> bool {
191        self.len == 0
192    }
193
194    /// Returns a reference to the value corresponding to the key.
195    ///
196    /// # Examples
197    /// ```
198    /// use slabmap::SlabMap;
199    ///
200    /// let mut s = SlabMap::new();
201    /// let key = s.insert(100);
202    ///
203    /// assert_eq!(s.get(key), Some(&100));
204    /// assert_eq!(s.get(key + 1), None);
205    /// ```
206    #[inline]
207    pub fn get(&self, key: usize) -> Option<&T> {
208        if let Entry::Occupied(value) = self.entries.get(key)? {
209            Some(value)
210        } else {
211            None
212        }
213    }
214
215    /// Returns a mutable reference to the value corresponding to the key.
216    #[inline]
217    pub fn get_mut(&mut self, key: usize) -> Option<&mut T> {
218        if let Entry::Occupied(value) = self.entries.get_mut(key)? {
219            Some(value)
220        } else {
221            None
222        }
223    }
224
225    /// Returns true if the SlabMap contains a value for the specified key.
226    ///
227    /// # Examples
228    /// ```
229    /// use slabmap::SlabMap;
230    ///
231    /// let mut s = SlabMap::new();
232    /// let key = s.insert(100);
233    ///
234    /// assert_eq!(s.contains_key(key), true);
235    /// assert_eq!(s.contains_key(key + 1), false);
236    /// ```
237    #[inline]
238    pub fn contains_key(&self, key: usize) -> bool {
239        self.get(key).is_some()
240    }
241
242    /// Inserts a value into the SlabMap.
243    ///
244    /// Returns the key associated with the value.
245    ///
246    /// # Examples
247    /// ```
248    /// use slabmap::SlabMap;
249    ///
250    /// let mut s = SlabMap::new();
251    /// let key_abc = s.insert("abc");
252    /// let key_xyz = s.insert("xyz");
253    ///
254    /// assert_eq!(s[key_abc], "abc");
255    /// assert_eq!(s[key_xyz], "xyz");
256    /// ```
257    pub fn insert(&mut self, value: T) -> usize {
258        self.insert_with_key(|_| value)
259    }
260
261    /// Inserts a value given by `f` into the SlabMap. The key to be associated with the value is passed to `f`.
262    ///
263    /// Returns the key associated with the value.
264    ///
265    /// # Examples
266    /// ```
267    /// use slabmap::SlabMap;
268    ///
269    /// let mut s = SlabMap::new();
270    /// let key = s.insert_with_key(|key| format!("my key is {}", key));
271    ///
272    /// assert_eq!(s[key], format!("my key is {}", key));
273    /// ```
274    #[inline]
275    pub fn insert_with_key(&mut self, f: impl FnOnce(usize) -> T) -> usize {
276        let idx;
277        if self.next_vacant_idx < self.entries.len() {
278            idx = self.next_vacant_idx;
279            self.next_vacant_idx = match self.entries[idx] {
280                Entry::VacantHead { vacant_body_len } => {
281                    if vacant_body_len > 0 {
282                        self.entries[idx + 1] = Entry::VacantHead {
283                            vacant_body_len: vacant_body_len - 1,
284                        };
285                    }
286                    idx + 1
287                }
288                Entry::VacantTail { next_vacant_idx } => next_vacant_idx,
289                Entry::Occupied(_) => unreachable!(),
290            };
291            self.entries[idx] = Entry::Occupied(f(idx));
292            self.non_optimized_count = self.non_optimized_count.saturating_sub(1);
293        } else {
294            idx = self.entries.len();
295            self.entries.push(Entry::Occupied(f(idx)));
296        }
297        self.len += 1;
298        idx
299    }
300
301    /// Removes a key from the SlabMap, returning the value at the key if the key was previously in the SlabMap.
302    ///
303    /// # Examples
304    /// ```
305    /// use slabmap::SlabMap;
306    ///
307    /// let mut s = SlabMap::new();
308    /// let key = s.insert("a");
309    /// assert_eq!(s.remove(key), Some("a"));
310    /// assert_eq!(s.remove(key), None);
311    /// ```
312    pub fn remove(&mut self, key: usize) -> Option<T> {
313        let is_last = key + 1 == self.entries.len();
314        let e = self.entries.get_mut(key)?;
315        if !matches!(e, Entry::Occupied(..)) {
316            return None;
317        }
318        self.len -= 1;
319        let e = if is_last {
320            self.entries.pop().unwrap()
321        } else {
322            let e = replace(
323                e,
324                Entry::VacantTail {
325                    next_vacant_idx: self.next_vacant_idx,
326                },
327            );
328            self.next_vacant_idx = key;
329            self.non_optimized_count += 1;
330            e
331        };
332        if self.is_empty() {
333            self.clear();
334        }
335        if let Entry::Occupied(value) = e {
336            Some(value)
337        } else {
338            unreachable!()
339        }
340    }
341
342    /// Clears the SlabMap, removing all values and optimize free spaces.
343    ///
344    /// # Examples
345    /// ```
346    /// use slabmap::SlabMap;
347    ///
348    /// let mut s = SlabMap::new();
349    /// s.insert(1);
350    /// s.insert(2);
351    ///
352    /// s.clear();
353    ///
354    /// assert_eq!(s.is_empty(), true);
355    /// ```
356    pub fn clear(&mut self) {
357        self.entries.clear();
358        self.len = 0;
359        self.next_vacant_idx = INVALID_INDEX;
360        self.non_optimized_count = 0;
361    }
362
363    /// Clears the SlabMap, returning all values as an iterator and optimize free spaces.
364    ///
365    /// # Examples
366    /// ```
367    /// use slabmap::SlabMap;
368    ///
369    /// let mut s = SlabMap::new();
370    /// let k0 = s.insert(10);
371    /// let k1 = s.insert(20);
372    ///
373    /// let d: Vec<_> = s.drain().collect();
374    /// let mut e = vec![(k0, 10), (k1, 20)];
375    /// e.sort();
376    ///
377    /// assert_eq!(s.is_empty(), true);
378    /// assert_eq!(d, e);
379    /// ```
380    pub fn drain(&mut self) -> Drain<T> {
381        let len = self.len;
382        self.len = 0;
383        self.next_vacant_idx = INVALID_INDEX;
384        self.non_optimized_count = 0;
385        Drain {
386            iter: self.entries.drain(..).enumerate(),
387            len,
388        }
389    }
390
391    /// Retains only the elements specified by the predicate and optimize free spaces.
392    ///
393    /// # Examples
394    /// ```
395    /// use slabmap::SlabMap;
396    ///
397    /// let mut s = SlabMap::new();
398    /// s.insert(10);
399    /// s.insert(15);
400    /// s.insert(20);
401    /// s.insert(25);
402    ///
403    /// s.retain(|_idx, value| *value % 2 == 0);
404    ///
405    /// let value: Vec<_> = s.values().cloned().collect();
406    /// assert_eq!(value, vec![10, 20]);
407    /// ```
408    pub fn retain(&mut self, f: impl FnMut(usize, &mut T) -> bool) {
409        self.merge_vacants(f)
410    }
411    fn merge_vacants(&mut self, mut f: impl FnMut(usize, &mut T) -> bool) {
412        let mut idx = 0;
413        let mut vacant_head_idx = 0;
414        let mut prev_vacant_tail_idx = None;
415        let mut len = 0;
416        self.next_vacant_idx = INVALID_INDEX;
417        while let Some(e) = self.entries.get_mut(idx) {
418            match e {
419                Entry::VacantTail { .. } => {
420                    idx += 1;
421                }
422                Entry::VacantHead { vacant_body_len } => {
423                    idx += *vacant_body_len + 2;
424                }
425                Entry::Occupied(value) => {
426                    if f(idx, value) {
427                        self.set_vacants(vacant_head_idx, idx, &mut prev_vacant_tail_idx);
428                        idx += 1;
429                        len += 1;
430                        vacant_head_idx = idx;
431                    } else {
432                        self.entries[idx] = Entry::VacantTail {
433                            next_vacant_idx: INVALID_INDEX,
434                        };
435                        idx += 1;
436                    }
437                }
438            }
439        }
440        self.entries.truncate(vacant_head_idx);
441        self.non_optimized_count = 0;
442        self.len = len;
443    }
444    fn set_vacants(
445        &mut self,
446        vacant_head_idx: usize,
447        vacant_end_idx: usize,
448        prev_vacant_tail_idx: &mut Option<usize>,
449    ) {
450        if vacant_head_idx >= vacant_end_idx {
451            return;
452        }
453        if self.next_vacant_idx == INVALID_INDEX {
454            self.next_vacant_idx = vacant_head_idx;
455        }
456        if vacant_head_idx + 2 <= vacant_end_idx {
457            self.entries[vacant_head_idx] = Entry::VacantHead {
458                vacant_body_len: vacant_end_idx - (vacant_head_idx + 2),
459            };
460        }
461        self.entries[vacant_end_idx - 1] = Entry::VacantTail {
462            next_vacant_idx: INVALID_INDEX,
463        };
464        if let Some(prev_vacant_tail_idx) = *prev_vacant_tail_idx {
465            self.entries[prev_vacant_tail_idx] = Entry::VacantTail {
466                next_vacant_idx: vacant_head_idx,
467            };
468        }
469        *prev_vacant_tail_idx = Some(vacant_end_idx - 1);
470    }
471
472    /// Optimizing the free space for speeding up iterations.
473    ///
474    /// If the free space has already been optimized, this method does nothing and completes with O(1).
475    ///
476    /// # Examples
477    /// ```
478    /// use slabmap::SlabMap;
479    /// use std::time::Instant;
480    ///
481    /// let mut s = SlabMap::new();
482    /// const COUNT: usize = 1000000;
483    /// for i in 0..COUNT {
484    ///     s.insert(i);
485    /// }
486    /// let keys: Vec<_> = s.keys().take(COUNT - 1).collect();
487    /// for key in keys {
488    ///     s.remove(key);
489    /// }
490    ///
491    /// s.optimize(); // if comment out this line, `s.values().sum()` to be slow.
492    ///
493    /// let begin = Instant::now();
494    /// let sum: usize = s.values().sum();
495    /// println!("sum : {}", sum);
496    /// println!("duration : {} ms", (Instant::now() - begin).as_millis());
497    /// ```
498    pub fn optimize(&mut self) {
499        if !self.is_optimized() {
500            self.force_optimize();
501        }
502    }
503    fn force_optimize(&mut self) {
504        self.merge_vacants(|_, _| true);
505    }
506
507    #[inline]
508    fn is_optimized(&self) -> bool {
509        self.non_optimized_count == 0
510    }
511
512    /// Gets an iterator over the entries of the SlabMap, sorted by key.
513    ///
514    /// If you make a large number of [`remove`](SlabMap::remove) calls, [`optimize`](SlabMap::optimize) should be called before calling this function.
515    #[inline]
516    pub fn iter(&self) -> Iter<T> {
517        Iter {
518            iter: self.entries.iter().enumerate(),
519            len: self.len,
520        }
521    }
522
523    /// Gets a mutable iterator over the entries of the slab, sorted by key.
524    ///
525    /// If you make a large number of [`remove`](SlabMap::remove) calls, [`optimize`](SlabMap::optimize) should be called before calling this function.
526    #[inline]
527    pub fn iter_mut(&mut self) -> IterMut<T> {
528        IterMut {
529            iter: self.entries.iter_mut().enumerate(),
530            len: self.len,
531        }
532    }
533
534    /// Gets an iterator over the keys of the SlabMap, in sorted order.
535    ///
536    /// If you make a large number of [`remove`](SlabMap::remove) calls, [`optimize`](SlabMap::optimize) should be called before calling this function.
537    #[inline]
538    pub fn keys(&self) -> Keys<T> {
539        Keys(self.iter())
540    }
541
542    /// Gets an iterator over the values of the SlabMap.
543    ///
544    /// If you make a large number of [`remove`](SlabMap::remove) calls, [`optimize`](SlabMap::optimize) should be called before calling this function.
545    #[inline]
546    pub fn values(&self) -> Values<T> {
547        Values(self.iter())
548    }
549
550    /// Gets a mutable iterator over the values of the SlabMap.
551    ///
552    /// If you make a large number of [`remove`](SlabMap::remove) calls, [`optimize`](SlabMap::optimize) should be called before calling this function.
553    #[inline]
554    pub fn values_mut(&mut self) -> ValuesMut<T> {
555        ValuesMut(self.iter_mut())
556    }
557}
558impl<T> Default for SlabMap<T> {
559    #[inline]
560    fn default() -> Self {
561        Self::new()
562    }
563}
564impl<T: Debug> Debug for SlabMap<T> {
565    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
566        f.debug_map().entries(self.iter()).finish()
567    }
568}
569
570impl<T> std::ops::Index<usize> for SlabMap<T> {
571    type Output = T;
572
573    #[inline]
574    fn index(&self, index: usize) -> &Self::Output {
575        self.get(index).expect("out of index.")
576    }
577}
578impl<T> std::ops::IndexMut<usize> for SlabMap<T> {
579    #[inline]
580    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
581        self.get_mut(index).expect("out of index.")
582    }
583}
584
585impl<T> FromIterator<(usize, T)> for SlabMap<T> {
586    fn from_iter<I: IntoIterator<Item = (usize, T)>>(iter: I) -> Self {
587        Self::from_iter_with_capacity(iter, 0)
588    }
589}
590
591impl<T> IntoIterator for SlabMap<T> {
592    type Item = (usize, T);
593    type IntoIter = IntoIter<T>;
594
595    #[inline]
596    fn into_iter(self) -> Self::IntoIter {
597        IntoIter {
598            iter: self.entries.into_iter().enumerate(),
599            len: self.len,
600        }
601    }
602}
603
604impl<'a, T> IntoIterator for &'a SlabMap<T> {
605    type Item = (usize, &'a T);
606    type IntoIter = Iter<'a, T>;
607
608    #[inline]
609    fn into_iter(self) -> Self::IntoIter {
610        self.iter()
611    }
612}
613impl<'a, T> IntoIterator for &'a mut SlabMap<T> {
614    type Item = (usize, &'a mut T);
615    type IntoIter = IterMut<'a, T>;
616
617    #[inline]
618    fn into_iter(self) -> Self::IntoIter {
619        self.iter_mut()
620    }
621}
622
623/// An owning iterator over the values of a SlabMap.
624///
625/// This struct is created by the `into_iter` method on [`SlabMap`] (provided by the IntoIterator trait).
626pub struct IntoIter<T> {
627    iter: Enumerate<std::vec::IntoIter<Entry<T>>>,
628    len: usize,
629}
630impl<T> Iterator for IntoIter<T> {
631    type Item = (usize, T);
632    #[inline]
633    fn next(&mut self) -> Option<Self::Item> {
634        let mut e_opt = self.iter.next();
635        while let Some(e) = e_opt {
636            e_opt = match e.1 {
637                Entry::Occupied(value) => {
638                    self.len -= 1;
639                    return Some((e.0, value));
640                }
641                Entry::VacantHead { vacant_body_len } => self.iter.nth(vacant_body_len + 1),
642                Entry::VacantTail { .. } => self.iter.next(),
643            }
644        }
645        None
646    }
647    #[inline]
648    fn size_hint(&self) -> (usize, Option<usize>) {
649        (self.len, Some(self.len))
650    }
651    #[inline]
652    fn count(self) -> usize
653    where
654        Self: Sized,
655    {
656        self.len
657    }
658}
659
660/// A draining iterator for `SlabMap<T>`.
661///
662/// This struct is created by the [`drain`](SlabMap::drain) method on [`SlabMap`].
663pub struct Drain<'a, T> {
664    iter: Enumerate<std::vec::Drain<'a, Entry<T>>>,
665    len: usize,
666}
667impl<'a, T> Iterator for Drain<'a, T> {
668    type Item = (usize, T);
669    #[inline]
670    fn next(&mut self) -> Option<Self::Item> {
671        let mut e_opt = self.iter.next();
672        while let Some(e) = e_opt {
673            e_opt = match e.1 {
674                Entry::Occupied(value) => {
675                    self.len -= 1;
676                    return Some((e.0, value));
677                }
678                Entry::VacantHead { vacant_body_len } => self.iter.nth(vacant_body_len + 1),
679                Entry::VacantTail { .. } => self.iter.next(),
680            }
681        }
682        None
683    }
684    #[inline]
685    fn size_hint(&self) -> (usize, Option<usize>) {
686        (self.len, Some(self.len))
687    }
688    #[inline]
689    fn count(self) -> usize
690    where
691        Self: Sized,
692    {
693        self.len
694    }
695}
696
697/// An iterator over the entries of a SlabMap.
698///
699/// This struct is created by the [`iter`](SlabMap::iter) method on [`SlabMap`].
700pub struct Iter<'a, T> {
701    iter: std::iter::Enumerate<std::slice::Iter<'a, Entry<T>>>,
702    len: usize,
703}
704impl<'a, T> Iterator for Iter<'a, T> {
705    type Item = (usize, &'a T);
706    #[inline]
707    fn next(&mut self) -> Option<Self::Item> {
708        let mut e_opt = self.iter.next();
709        while let Some(e) = e_opt {
710            e_opt = match e {
711                (key, Entry::Occupied(value)) => {
712                    self.len -= 1;
713                    return Some((key, value));
714                }
715                (_, Entry::VacantHead { vacant_body_len }) => self.iter.nth(*vacant_body_len + 1),
716                (_, Entry::VacantTail { .. }) => self.iter.next(),
717            }
718        }
719        None
720    }
721    #[inline]
722    fn size_hint(&self) -> (usize, Option<usize>) {
723        (self.len, Some(self.len))
724    }
725    #[inline]
726    fn count(self) -> usize
727    where
728        Self: Sized,
729    {
730        self.len
731    }
732}
733impl<'a, T> FusedIterator for Iter<'a, T> {}
734impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
735
736/// A mutable iterator over the entries of a SlabMap.
737///
738/// This struct is created by the [`iter_mut`](SlabMap::iter_mut) method on [`SlabMap`].
739pub struct IterMut<'a, T> {
740    iter: std::iter::Enumerate<std::slice::IterMut<'a, Entry<T>>>,
741    len: usize,
742}
743impl<'a, T> Iterator for IterMut<'a, T> {
744    type Item = (usize, &'a mut T);
745    #[inline]
746    fn next(&mut self) -> Option<Self::Item> {
747        let mut e_opt = self.iter.next();
748        while let Some(e) = e_opt {
749            e_opt = match e {
750                (key, Entry::Occupied(value)) => {
751                    self.len -= 1;
752                    return Some((key, value));
753                }
754                (_, Entry::VacantHead { vacant_body_len }) => self.iter.nth(*vacant_body_len + 1),
755                (_, Entry::VacantTail { .. }) => self.iter.next(),
756            }
757        }
758        None
759    }
760    #[inline]
761    fn size_hint(&self) -> (usize, Option<usize>) {
762        (self.len, Some(self.len))
763    }
764    #[inline]
765    fn count(self) -> usize
766    where
767        Self: Sized,
768    {
769        self.len
770    }
771}
772impl<'a, T> FusedIterator for IterMut<'a, T> {}
773impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
774
775/// An iterator over the keys of a SlabMap.
776///
777/// This struct is created by the [`keys`](SlabMap::keys) method on [`SlabMap`].
778pub struct Keys<'a, T>(Iter<'a, T>);
779impl<'a, T> Iterator for Keys<'a, T> {
780    type Item = usize;
781    #[inline]
782    fn next(&mut self) -> Option<Self::Item> {
783        self.0.next().map(|(k, _)| k)
784    }
785    #[inline]
786    fn size_hint(&self) -> (usize, Option<usize>) {
787        self.0.size_hint()
788    }
789    #[inline]
790    fn count(self) -> usize
791    where
792        Self: Sized,
793    {
794        self.0.count()
795    }
796}
797impl<'a, T> FusedIterator for Keys<'a, T> {}
798impl<'a, T> ExactSizeIterator for Keys<'a, T> {}
799
800/// An iterator over the values of a SlabMap.
801///
802/// This struct is created by the [`values`](SlabMap::values) method on [`SlabMap`].
803pub struct Values<'a, T>(Iter<'a, T>);
804impl<'a, T> Iterator for Values<'a, T> {
805    type Item = &'a T;
806    #[inline]
807    fn next(&mut self) -> Option<Self::Item> {
808        self.0.next().map(|(_, v)| v)
809    }
810    #[inline]
811    fn size_hint(&self) -> (usize, Option<usize>) {
812        self.0.size_hint()
813    }
814    #[inline]
815    fn count(self) -> usize
816    where
817        Self: Sized,
818    {
819        self.0.count()
820    }
821}
822impl<'a, T> FusedIterator for Values<'a, T> {}
823impl<'a, T> ExactSizeIterator for Values<'a, T> {}
824
825/// A mutable iterator over the values of a SlabMap.
826///
827/// This struct is created by the [`values_mut`](SlabMap::values_mut) method on [`SlabMap`].
828pub struct ValuesMut<'a, T>(IterMut<'a, T>);
829impl<'a, T> Iterator for ValuesMut<'a, T> {
830    type Item = &'a mut T;
831    #[inline]
832    fn next(&mut self) -> Option<Self::Item> {
833        self.0.next().map(|(_, v)| v)
834    }
835    #[inline]
836    fn size_hint(&self) -> (usize, Option<usize>) {
837        self.0.size_hint()
838    }
839    #[inline]
840    fn count(self) -> usize
841    where
842        Self: Sized,
843    {
844        self.0.count()
845    }
846}
847impl<'a, T> FusedIterator for ValuesMut<'a, T> {}
848impl<'a, T> ExactSizeIterator for ValuesMut<'a, T> {}
slabmap/lib.rs

slabmap/
lib.rs
