tether_map/linked_hash_map/
iter.rs

1use core::hint::unreachable_unchecked;
2use core::marker::PhantomData;
3
4use crate::arena::ActiveSlotRef;
5use crate::arena::Arena;
6use crate::arena::ArenaContainer;
7use crate::arena::Links;
8
9#[derive(Debug, Clone, Copy)]
10/// An iterator over the entries of a `LinkedHashMap`.
11///
12/// This struct is created by the [`iter`] method on [`LinkedHashMap`]. See its
13/// documentation for more.
14///
15/// [`iter`]: crate::LinkedHashMap::iter
16/// [`LinkedHashMap`]: crate::LinkedHashMap
17///
18/// # Examples
19///
20/// ```
21/// use tether_map::LinkedHashMap;
22///
23/// let mut map = LinkedHashMap::new();
24/// map.insert("a", 1);
25/// map.insert("b", 2);
26///
27/// for (key, value) in map.iter() {
28///     println!("{}: {}", key, value);
29/// }
30/// ```
31pub struct Iter<'a, K, T> {
32    pub(crate) forward_ptr: Option<ActiveSlotRef<K, T>>,
33    pub(crate) reverse_ptr: Option<ActiveSlotRef<K, T>>,
34    pub(crate) nodes: &'a Arena<K, T>,
35}
36
37impl<'a, K, T> Iterator for Iter<'a, K, T> {
38    type Item = (&'a K, &'a T);
39
40    #[inline]
41    fn next(&mut self) -> Option<Self::Item> {
42        let ptr = self.forward_ptr?;
43        if self.forward_ptr == self.reverse_ptr {
44            self.forward_ptr = None;
45            self.reverse_ptr = None;
46        } else {
47            self.forward_ptr = Some(ptr.next(self.nodes));
48        }
49
50        let data = ptr.data(self.nodes);
51
52        Some((&data.key, &data.value))
53    }
54}
55
56impl<'a, K, T> DoubleEndedIterator for Iter<'a, K, T> {
57    #[inline]
58    fn next_back(&mut self) -> Option<Self::Item> {
59        let ptr = self.reverse_ptr?;
60        if self.reverse_ptr == self.forward_ptr {
61            self.reverse_ptr = None;
62            self.forward_ptr = None;
63        } else {
64            self.reverse_ptr = Some(ptr.prev(self.nodes));
65        }
66
67        let data = ptr.data(self.nodes);
68
69        Some((&data.key, &data.value))
70    }
71}
72
73#[derive(Debug)]
74/// An owning iterator over the entries of a `LinkedHashMap`.
75///
76/// This struct is created by the [`into_iter`] method on [`LinkedHashMap`]
77/// (provided by the [`IntoIterator`] trait). See its documentation for more.
78///
79/// [`into_iter`]: IntoIterator::into_iter
80/// [`IntoIterator`]: core::iter::IntoIterator
81/// [`LinkedHashMap`]: crate::LinkedHashMap
82///
83/// # Examples
84///
85/// ```
86/// use tether_map::LinkedHashMap;
87///
88/// let mut map = LinkedHashMap::new();
89/// map.insert("a", 1);
90/// map.insert("b", 2);
91///
92/// for (key, value) in map {
93///     println!("{}: {}", key, value);
94/// }
95/// ```
96pub struct IntoIter<K, T> {
97    pub(crate) nodes: ArenaContainer<K, T>,
98    pub(crate) forward_ptr: Option<ActiveSlotRef<K, T>>,
99    pub(crate) reverse_ptr: Option<ActiveSlotRef<K, T>>,
100}
101
102impl<K, T> Iterator for IntoIter<K, T> {
103    type Item = (K, T);
104
105    #[inline]
106    fn next(&mut self) -> Option<Self::Item> {
107        let ptr = self.forward_ptr?;
108        if self.forward_ptr == self.reverse_ptr {
109            self.forward_ptr = None;
110            self.reverse_ptr = None;
111        } else {
112            self.forward_ptr = Some(ptr.next(&self.nodes));
113        }
114
115        // SAFETY: We do not access the pointer after this call.
116        let data = unsafe { self.nodes.free_and_unlink(ptr).data };
117        Some((data.key, data.value))
118    }
119}
120
121impl<K, T> DoubleEndedIterator for IntoIter<K, T> {
122    #[inline]
123    fn next_back(&mut self) -> Option<Self::Item> {
124        let ptr = self.reverse_ptr?;
125        if self.reverse_ptr == self.forward_ptr {
126            self.reverse_ptr = None;
127            self.forward_ptr = None;
128        } else {
129            self.reverse_ptr = Some(ptr.prev(&self.nodes));
130        }
131
132        // SAFETY: We do not access the pointer after this call.
133        let data = unsafe { self.nodes.free_and_unlink(ptr).data };
134        Some((data.key, data.value))
135    }
136}
137
138#[derive(Debug)]
139/// A mutable iterator over the entries of a `LinkedHashMap`.
140///
141/// This struct is created by the [`iter_mut`] method on [`LinkedHashMap`]. See
142/// its documentation for more.
143///
144/// [`iter_mut`]: crate::LinkedHashMap::iter_mut
145/// [`LinkedHashMap`]: crate::LinkedHashMap
146///
147/// # Examples
148///
149/// ```
150/// use tether_map::LinkedHashMap;
151///
152/// let mut map = LinkedHashMap::new();
153/// map.insert("a", 1);
154/// map.insert("b", 2);
155///
156/// for (key, value) in map.iter_mut() {
157///     *value *= 2;
158/// }
159///
160/// assert_eq!(map.get(&"a"), Some(&2));
161/// assert_eq!(map.get(&"b"), Some(&4));
162/// ```
163pub struct IterMut<'a, K, T> {
164    pub(crate) forward_ptr: Option<ActiveSlotRef<K, T>>,
165    pub(crate) reverse_ptr: Option<ActiveSlotRef<K, T>>,
166    pub(crate) _nodes: PhantomData<&'a mut Arena<K, T>>,
167}
168
169#[derive(Debug)]
170/// A mutable iterator over the values of a `LinkedHashMap`.
171///
172/// This iterator yields `&mut T` values in the order they were inserted into
173/// the map. It is created by the [`values_mut`] method on [`LinkedHashMap`].
174///
175/// [`values_mut`]: crate::LinkedHashMap::values_mut
176/// [`LinkedHashMap`]: crate::LinkedHashMap
177///
178/// # Examples
179///
180/// ```
181/// use tether_map::LinkedHashMap;
182///
183/// let mut map = LinkedHashMap::new();
184/// map.insert("a", 1);
185/// map.insert("b", 2);
186///
187/// for value in map.values_mut() {
188///     *value *= 10;
189/// }
190///
191/// assert_eq!(map.get(&"a"), Some(&10));
192/// assert_eq!(map.get(&"b"), Some(&20));
193/// ```
194pub struct ValuesMut<'a, K, T> {
195    pub(crate) iter: IterMut<'a, K, T>,
196}
197
198impl<'a, K, T> Iterator for IterMut<'a, K, T> {
199    type Item = (&'a K, &'a mut T);
200
201    #[inline]
202    fn next(&mut self) -> Option<Self::Item> {
203        // SAFETY: We yield exactly one item per ptr. Our ptrs are unique. We trust the
204        // pointers we are iterating over came from our arena. We tie the lifetime to
205        // our mutable borrow of the arena.
206        let node_mut = unsafe { self.forward_ptr?.as_ptr().as_mut() };
207        if self.forward_ptr == self.reverse_ptr {
208            self.forward_ptr = None;
209            self.reverse_ptr = None;
210        } else {
211            // SAFETY: We are iterating over our own pointers which we know are valid.
212            self.forward_ptr = unsafe {
213                Some(match node_mut.links {
214                    Links::Occupied { next, .. } => next,
215                    Links::Vacant { .. } => unreachable_unchecked(),
216                })
217            };
218        }
219
220        // SAFETY: See above.
221        unsafe {
222            let data = node_mut.data.assume_init_mut();
223            Some((&data.key, &mut data.value))
224        }
225    }
226}
227
228impl<'a, K, T> DoubleEndedIterator for IterMut<'a, K, T> {
229    #[inline]
230    fn next_back(&mut self) -> Option<Self::Item> {
231        // SAFETY: We yield exactly one item per ptr. Our ptrs are unique. We trust the
232        // pointers we are iterating over came from our arena. We tie the lifetime to
233        // our mutable borrow of the arena.
234        let node_mut = unsafe { self.reverse_ptr?.as_ptr().as_mut() };
235        if self.reverse_ptr == self.forward_ptr {
236            self.reverse_ptr = None;
237            self.forward_ptr = None;
238        } else {
239            // SAFETY: We are iterating over our own pointers which we know are valid.
240            self.reverse_ptr = unsafe {
241                Some(match node_mut.links {
242                    Links::Occupied { prev, .. } => prev,
243                    Links::Vacant { .. } => unreachable_unchecked(),
244                })
245            };
246        }
247
248        // SAFETY: See above.
249        unsafe {
250            let data = node_mut.data.assume_init_mut();
251            Some((&data.key, &mut data.value))
252        }
253    }
254}
255
256impl<'a, K, T> Iterator for ValuesMut<'a, K, T> {
257    type Item = &'a mut T;
258
259    #[inline]
260    fn next(&mut self) -> Option<Self::Item> {
261        self.iter.next().map(|(_, v)| v)
262    }
263
264    #[inline]
265    fn size_hint(&self) -> (usize, Option<usize>) {
266        self.iter.size_hint()
267    }
268}
269
270impl<'a, K, T> DoubleEndedIterator for ValuesMut<'a, K, T> {
271    #[inline]
272    fn next_back(&mut self) -> Option<Self::Item> {
273        self.iter.next_back().map(|(_, v)| v)
274    }
275}
276
277#[cfg(test)]
278mod tests {
279    use alloc::vec;
280    use alloc::vec::Vec;
281
282    use crate::LinkedHashMap;
283
284    #[test]
285    fn test_iter_empty() {
286        let map: LinkedHashMap<i32, &str> = LinkedHashMap::new();
287        let mut iter = map.iter();
288        assert_eq!(iter.next(), None);
289        assert_eq!(iter.next_back(), None);
290    }
291
292    #[test]
293    fn test_iter_single_element() {
294        let mut map = LinkedHashMap::new();
295        map.insert(1, "one");
296
297        let mut iter = map.iter();
298        assert_eq!(iter.next(), Some((&1, &"one")));
299        assert_eq!(iter.next(), None);
300        assert_eq!(iter.next_back(), None);
301    }
302
303    #[test]
304    fn test_iter_multiple_elements_forward() {
305        let mut map = LinkedHashMap::new();
306        map.insert(1, "one");
307        map.insert(2, "two");
308        map.insert(3, "three");
309
310        let mut iter = map.iter();
311        assert_eq!(iter.next(), Some((&1, &"one")));
312        assert_eq!(iter.next(), Some((&2, &"two")));
313        assert_eq!(iter.next(), Some((&3, &"three")));
314        assert_eq!(iter.next(), None);
315    }
316
317    #[test]
318    fn test_iter_multiple_elements_backward() {
319        let mut map = LinkedHashMap::new();
320        map.insert(1, "one");
321        map.insert(2, "two");
322        map.insert(3, "three");
323
324        let mut iter = map.iter();
325        assert_eq!(iter.next_back(), Some((&3, &"three")));
326        assert_eq!(iter.next_back(), Some((&2, &"two")));
327        assert_eq!(iter.next_back(), Some((&1, &"one")));
328        assert_eq!(iter.next_back(), None);
329    }
330
331    #[test]
332    fn test_iter_bidirectional() {
333        let mut map = LinkedHashMap::new();
334        map.insert(1, "one");
335        map.insert(2, "two");
336        map.insert(3, "three");
337        map.insert(4, "four");
338
339        let mut iter = map.iter();
340        assert_eq!(iter.next(), Some((&1, &"one")));
341        assert_eq!(iter.next_back(), Some((&4, &"four")));
342        assert_eq!(iter.next(), Some((&2, &"two")));
343        assert_eq!(iter.next_back(), Some((&3, &"three")));
344        assert_eq!(iter.next(), None);
345        assert_eq!(iter.next_back(), None);
346    }
347
348    #[test]
349    fn test_iter_meet_in_middle() {
350        let mut map = LinkedHashMap::new();
351        map.insert(1, "one");
352        map.insert(2, "two");
353        map.insert(3, "three");
354
355        let mut iter = map.iter();
356        assert_eq!(iter.next(), Some((&1, &"one")));
357        assert_eq!(iter.next_back(), Some((&3, &"three")));
358        assert_eq!(iter.next(), Some((&2, &"two")));
359        assert_eq!(iter.next(), None);
360        assert_eq!(iter.next_back(), None);
361    }
362
363    #[test]
364    fn test_iter_collect() {
365        let mut map = LinkedHashMap::new();
366        map.insert("a", 1);
367        map.insert("b", 2);
368        map.insert("c", 3);
369
370        let collected: Vec<_> = map.iter().collect();
371        assert_eq!(collected, vec![(&"a", &1), (&"b", &2), (&"c", &3)]);
372
373        let collected_rev: Vec<_> = map.iter().rev().collect();
374        assert_eq!(collected_rev, vec![(&"c", &3), (&"b", &2), (&"a", &1)]);
375    }
376
377    #[test]
378    fn test_into_iter_empty() {
379        let map: LinkedHashMap<i32, &str> = LinkedHashMap::new();
380        let mut iter = map.into_iter();
381        assert_eq!(iter.next(), None);
382        assert_eq!(iter.next_back(), None);
383    }
384
385    #[test]
386    fn test_into_iter_single_element() {
387        let mut map = LinkedHashMap::new();
388        map.insert(1, "one");
389
390        let mut iter = map.into_iter();
391        assert_eq!(iter.next(), Some((1, "one")));
392        assert_eq!(iter.next(), None);
393        assert_eq!(iter.next_back(), None);
394    }
395
396    #[test]
397    fn test_into_iter_multiple_elements_forward() {
398        let mut map = LinkedHashMap::new();
399        map.insert(1, "one");
400        map.insert(2, "two");
401        map.insert(3, "three");
402
403        let mut iter = map.into_iter();
404        assert_eq!(iter.next(), Some((1, "one")));
405        assert_eq!(iter.next(), Some((2, "two")));
406        assert_eq!(iter.next(), Some((3, "three")));
407        assert_eq!(iter.next(), None);
408    }
409
410    #[test]
411    fn test_into_iter_multiple_elements_backward() {
412        let mut map = LinkedHashMap::new();
413        map.insert(1, "one");
414        map.insert(2, "two");
415        map.insert(3, "three");
416
417        let mut iter = map.into_iter();
418        assert_eq!(iter.next_back(), Some((3, "three")));
419        assert_eq!(iter.next_back(), Some((2, "two")));
420        assert_eq!(iter.next_back(), Some((1, "one")));
421        assert_eq!(iter.next_back(), None);
422    }
423
424    #[test]
425    fn test_into_iter_bidirectional() {
426        let mut map = LinkedHashMap::new();
427        map.insert(1, "one");
428        map.insert(2, "two");
429        map.insert(3, "three");
430        map.insert(4, "four");
431
432        let mut iter = map.into_iter();
433        assert_eq!(iter.next(), Some((1, "one")));
434        assert_eq!(iter.next_back(), Some((4, "four")));
435        assert_eq!(iter.next(), Some((2, "two")));
436        assert_eq!(iter.next_back(), Some((3, "three")));
437        assert_eq!(iter.next(), None);
438        assert_eq!(iter.next_back(), None);
439    }
440
441    #[test]
442    fn test_into_iter_collect() {
443        let mut map = LinkedHashMap::new();
444        map.insert("a", 1);
445        map.insert("b", 2);
446        map.insert("c", 3);
447
448        let collected: Vec<_> = map.into_iter().collect();
449        assert_eq!(collected, vec![("a", 1), ("b", 2), ("c", 3)]);
450    }
451
452    #[test]
453    fn test_iter_mut_empty() {
454        let mut map: LinkedHashMap<i32, &str> = LinkedHashMap::new();
455        let mut iter = map.iter_mut();
456        assert_eq!(iter.next(), None);
457        assert_eq!(iter.next_back(), None);
458    }
459
460    #[test]
461    fn test_iter_mut_single_element() {
462        let mut map = LinkedHashMap::new();
463        map.insert(1, 100);
464
465        {
466            let mut iter = map.iter_mut();
467            if let Some((key, value)) = iter.next() {
468                assert_eq!(key, &1);
469                *value *= 2;
470            }
471            assert_eq!(iter.next(), None);
472        }
473
474        assert_eq!(map.get(&1), Some(&200));
475    }
476
477    #[test]
478    fn test_iter_mut_multiple_elements_forward() {
479        let mut map = LinkedHashMap::new();
480        map.insert(1, 10);
481        map.insert(2, 20);
482        map.insert(3, 30);
483
484        {
485            let iter = map.iter_mut();
486            for (_, value) in iter {
487                *value *= 2;
488            }
489        }
490
491        assert_eq!(map.get(&1), Some(&20));
492        assert_eq!(map.get(&2), Some(&40));
493        assert_eq!(map.get(&3), Some(&60));
494    }
495
496    #[test]
497    fn test_iter_mut_multiple_elements_backward() {
498        let mut map = LinkedHashMap::new();
499        map.insert(1, 10);
500        map.insert(2, 20);
501        map.insert(3, 30);
502
503        {
504            let mut iter = map.iter_mut();
505            while let Some((_, value)) = iter.next_back() {
506                *value += 1;
507            }
508        }
509
510        assert_eq!(map.get(&1), Some(&11));
511        assert_eq!(map.get(&2), Some(&21));
512        assert_eq!(map.get(&3), Some(&31));
513    }
514
515    #[test]
516    fn test_iter_mut_bidirectional() {
517        let mut map = LinkedHashMap::new();
518        map.insert(1, 10);
519        map.insert(2, 20);
520        map.insert(3, 30);
521        map.insert(4, 40);
522
523        {
524            let mut iter = map.iter_mut();
525            if let Some((_, value)) = iter.next() {
526                *value = 100;
527            }
528            if let Some((_, value)) = iter.next_back() {
529                *value = 400;
530            }
531            if let Some((_, value)) = iter.next() {
532                *value = 200;
533            }
534            if let Some((_, value)) = iter.next_back() {
535                *value = 300;
536            }
537        }
538
539        assert_eq!(map.get(&1), Some(&100));
540        assert_eq!(map.get(&2), Some(&200));
541        assert_eq!(map.get(&3), Some(&300));
542        assert_eq!(map.get(&4), Some(&400));
543    }
544
545    #[test]
546    fn test_values_mut_empty() {
547        let mut map: LinkedHashMap<i32, &str> = LinkedHashMap::new();
548        let mut iter = map.values_mut();
549        assert_eq!(iter.next(), None);
550        assert_eq!(iter.next_back(), None);
551    }
552
553    #[test]
554    fn test_values_mut_single_element() {
555        let mut map = LinkedHashMap::new();
556        map.insert("key", 42);
557
558        {
559            let mut iter = map.values_mut();
560            if let Some(value) = iter.next() {
561                *value = 99;
562            }
563            assert_eq!(iter.next(), None);
564        }
565
566        assert_eq!(map.get(&"key"), Some(&99));
567    }
568
569    #[test]
570    fn test_values_mut_multiple_elements_forward() {
571        let mut map = LinkedHashMap::new();
572        map.insert("a", 1);
573        map.insert("b", 2);
574        map.insert("c", 3);
575
576        {
577            for value in map.values_mut() {
578                *value *= 10;
579            }
580        }
581
582        assert_eq!(map.get(&"a"), Some(&10));
583        assert_eq!(map.get(&"b"), Some(&20));
584        assert_eq!(map.get(&"c"), Some(&30));
585    }
586
587    #[test]
588    fn test_values_mut_multiple_elements_backward() {
589        let mut map = LinkedHashMap::new();
590        map.insert("a", 1);
591        map.insert("b", 2);
592        map.insert("c", 3);
593
594        {
595            let mut iter = map.values_mut();
596            while let Some(value) = iter.next_back() {
597                *value += 100;
598            }
599        }
600
601        assert_eq!(map.get(&"a"), Some(&101));
602        assert_eq!(map.get(&"b"), Some(&102));
603        assert_eq!(map.get(&"c"), Some(&103));
604    }
605
606    #[test]
607    fn test_values_mut_bidirectional() {
608        let mut map = LinkedHashMap::new();
609        map.insert(1, 10);
610        map.insert(2, 20);
611        map.insert(3, 30);
612        map.insert(4, 40);
613
614        {
615            let mut iter = map.values_mut();
616            if let Some(value) = iter.next() {
617                *value = 1000;
618            }
619            if let Some(value) = iter.next_back() {
620                *value = 4000;
621            }
622            if let Some(value) = iter.next() {
623                *value = 2000;
624            }
625            if let Some(value) = iter.next_back() {
626                *value = 3000;
627            }
628        }
629
630        assert_eq!(map.get(&1), Some(&1000));
631        assert_eq!(map.get(&2), Some(&2000));
632        assert_eq!(map.get(&3), Some(&3000));
633        assert_eq!(map.get(&4), Some(&4000));
634    }
635
636    #[test]
637    fn test_values_mut_collect() {
638        let mut map = LinkedHashMap::new();
639        map.insert("x", 1);
640        map.insert("y", 2);
641        map.insert("z", 3);
642
643        let original_values: Vec<_> = map.values_mut().map(|v| *v).collect();
644        assert_eq!(original_values, vec![1, 2, 3]);
645
646        for value in map.values_mut() {
647            *value *= 5;
648        }
649
650        let modified_values: Vec<_> = map.values_mut().map(|v| *v).collect();
651        assert_eq!(modified_values, vec![5, 10, 15]);
652    }
653
654    #[test]
655    fn test_iterator_size_hints() {
656        let mut map = LinkedHashMap::new();
657        map.insert(1, "a");
658        map.insert(2, "b");
659        map.insert(3, "c");
660
661        let iter = map.iter();
662        assert_eq!(iter.size_hint(), (0, None));
663
664        let values_iter = map.values_mut();
665        assert_eq!(values_iter.size_hint(), (0, None));
666    }
667
668    #[test]
669    fn test_iterator_preservation_after_modification() {
670        let mut map = LinkedHashMap::new();
671        map.insert(1, 10);
672        map.insert(2, 20);
673        map.insert(3, 30);
674
675        let collected_before: Vec<_> = map.iter().map(|(k, v)| (*k, *v)).collect();
676
677        map.insert(4, 40);
678
679        let collected_after: Vec<_> = map.iter().map(|(k, v)| (*k, *v)).collect();
680
681        assert_eq!(collected_before, vec![(1, 10), (2, 20), (3, 30)]);
682        assert_eq!(collected_after, vec![(1, 10), (2, 20), (3, 30), (4, 40)]);
683    }
684}
tether_map/linked_hash_map/iter.rs

tether_map/linked_hash_map/
iter.rs
