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`]: LinkedHashMap::iter
16///
17/// # Examples
18///
19/// ```
20/// use tether_map::LinkedHashMap;
21///
22/// let mut map = LinkedHashMap::new();
23/// map.insert("a", 1);
24/// map.insert("b", 2);
25///
26/// for (key, value) in map.iter() {
27///     println!("{}: {}", key, value);
28/// }
29/// ```
30pub struct Iter<'a, K, T> {
31    pub(crate) forward_ptr: Option<ActiveSlotRef<K, T>>,
32    pub(crate) reverse_ptr: Option<ActiveSlotRef<K, T>>,
33    pub(crate) nodes: &'a Arena<K, T>,
34}
35
36impl<'a, K, T> Iterator for Iter<'a, K, T> {
37    type Item = (&'a K, &'a T);
38
39    fn next(&mut self) -> Option<Self::Item> {
40        let ptr = self.forward_ptr?;
41        if self.forward_ptr == self.reverse_ptr {
42            self.forward_ptr = None;
43            self.reverse_ptr = None;
44        } else {
45            self.forward_ptr = Some(ptr.next(self.nodes));
46        }
47
48        let data = ptr.data(self.nodes);
49
50        Some((&data.key, &data.value))
51    }
52}
53
54impl<'a, K, T> DoubleEndedIterator for Iter<'a, K, T> {
55    fn next_back(&mut self) -> Option<Self::Item> {
56        let ptr = self.reverse_ptr?;
57        if self.reverse_ptr == self.forward_ptr {
58            self.reverse_ptr = None;
59            self.forward_ptr = None;
60        } else {
61            self.reverse_ptr = Some(ptr.prev(self.nodes));
62        }
63
64        let data = ptr.data(self.nodes);
65
66        Some((&data.key, &data.value))
67    }
68}
69
70#[derive(Debug)]
71/// An owning iterator over the entries of a `LinkedHashMap`.
72///
73/// This struct is created by the [`into_iter`] method on [`LinkedHashMap`]
74/// (provided by the [`IntoIterator`] trait). See its documentation for more.
75///
76/// [`into_iter`]: IntoIterator::into_iter
77/// [`IntoIterator`]: core::iter::IntoIterator
78///
79/// # Examples
80///
81/// ```
82/// use tether_map::LinkedHashMap;
83///
84/// let mut map = LinkedHashMap::new();
85/// map.insert("a", 1);
86/// map.insert("b", 2);
87///
88/// for (key, value) in map {
89///     println!("{}: {}", key, value);
90/// }
91/// ```
92pub struct IntoIter<K, T> {
93    pub(crate) nodes: ArenaContainer<K, T>,
94    pub(crate) forward_ptr: Option<ActiveSlotRef<K, T>>,
95    pub(crate) reverse_ptr: Option<ActiveSlotRef<K, T>>,
96}
97
98impl<K, T> Iterator for IntoIter<K, T> {
99    type Item = (K, T);
100
101    fn next(&mut self) -> Option<Self::Item> {
102        let ptr = self.forward_ptr?;
103        if self.forward_ptr == self.reverse_ptr {
104            self.forward_ptr = None;
105            self.reverse_ptr = None;
106        } else {
107            self.forward_ptr = Some(ptr.next(&self.nodes));
108        }
109
110        // SAFETY: We do not access the pointer after this call.
111        let data = unsafe { self.nodes.free_and_unlink(ptr).data };
112        Some((data.key, data.value))
113    }
114}
115
116impl<K, T> DoubleEndedIterator for IntoIter<K, T> {
117    fn next_back(&mut self) -> Option<Self::Item> {
118        let ptr = self.reverse_ptr?;
119        if self.reverse_ptr == self.forward_ptr {
120            self.reverse_ptr = None;
121            self.forward_ptr = None;
122        } else {
123            self.reverse_ptr = Some(ptr.prev(&self.nodes));
124        }
125
126        // SAFETY: We do not access the pointer after this call.
127        let data = unsafe { self.nodes.free_and_unlink(ptr).data };
128        Some((data.key, data.value))
129    }
130}
131
132#[derive(Debug)]
133/// A mutable iterator over the entries of a `LinkedHashMap`.
134///
135/// This struct is created by the [`iter_mut`] method on [`LinkedHashMap`]. See
136/// its documentation for more.
137///
138/// [`iter_mut`]: LinkedHashMap::iter_mut
139///
140/// # Examples
141///
142/// ```
143/// use tether_map::LinkedHashMap;
144///
145/// let mut map = LinkedHashMap::new();
146/// map.insert("a", 1);
147/// map.insert("b", 2);
148///
149/// for (key, value) in map.iter_mut() {
150///     *value *= 2;
151/// }
152///
153/// assert_eq!(map.get(&"a"), Some(&2));
154/// assert_eq!(map.get(&"b"), Some(&4));
155/// ```
156pub struct IterMut<'a, K, T> {
157    pub(crate) forward_ptr: Option<ActiveSlotRef<K, T>>,
158    pub(crate) reverse_ptr: Option<ActiveSlotRef<K, T>>,
159    pub(crate) _nodes: PhantomData<&'a mut Arena<K, T>>,
160}
161
162#[derive(Debug)]
163/// A mutable iterator over the values of a `LinkedHashMap`.
164///
165/// This iterator yields `&mut T` values in the order they were inserted into
166/// the map. It is created by the [`values_mut`] method on `LinkedHashMap`.
167///
168/// [`values_mut`]: LinkedHashMap::values_mut
169///
170/// # Examples
171///
172/// ```
173/// use tether_map::LinkedHashMap;
174///
175/// let mut map = LinkedHashMap::new();
176/// map.insert("a", 1);
177/// map.insert("b", 2);
178///
179/// for value in map.values_mut() {
180///     *value *= 10;
181/// }
182///
183/// assert_eq!(map.get(&"a"), Some(&10));
184/// assert_eq!(map.get(&"b"), Some(&20));
185/// ```
186pub struct ValuesMut<'a, K, T> {
187    pub(crate) iter: IterMut<'a, K, T>,
188}
189
190impl<'a, K, T> Iterator for IterMut<'a, K, T> {
191    type Item = (&'a K, &'a mut T);
192
193    fn next(&mut self) -> Option<Self::Item> {
194        // SAFETY: We yield exactly one item per ptr. Our ptrs are unique. We trust the
195        // pointers we are iterating over came from our arena. We tie the lifetime to
196        // our mutable borrow of the arena.
197        let node_mut = unsafe { self.forward_ptr?.as_ptr().as_mut() };
198        if self.forward_ptr == self.reverse_ptr {
199            self.forward_ptr = None;
200            self.reverse_ptr = None;
201        } else {
202            // SAFETY: We are iterating over our own pointers which we know are valid.
203            self.forward_ptr = unsafe {
204                Some(match node_mut.links {
205                    Links::Occupied { next, .. } => next,
206                    Links::Vacant { .. } => unreachable_unchecked(),
207                })
208            };
209        }
210
211        // SAFETY: See above.
212        unsafe {
213            let data = node_mut.data.assume_init_mut();
214            Some((&data.key, &mut data.value))
215        }
216    }
217}
218
219impl<'a, K, T> DoubleEndedIterator for IterMut<'a, K, T> {
220    fn next_back(&mut self) -> Option<Self::Item> {
221        // SAFETY: We yield exactly one item per ptr. Our ptrs are unique. We trust the
222        // pointers we are iterating over came from our arena. We tie the lifetime to
223        // our mutable borrow of the arena.
224        let node_mut = unsafe { self.reverse_ptr?.as_ptr().as_mut() };
225        if self.reverse_ptr == self.forward_ptr {
226            self.reverse_ptr = None;
227            self.forward_ptr = None;
228        } else {
229            // SAFETY: We are iterating over our own pointers which we know are valid.
230            self.reverse_ptr = unsafe {
231                Some(match node_mut.links {
232                    Links::Occupied { prev, .. } => prev,
233                    Links::Vacant { .. } => unreachable_unchecked(),
234                })
235            };
236        }
237
238        // SAFETY: See above.
239        unsafe {
240            let data = node_mut.data.assume_init_mut();
241            Some((&data.key, &mut data.value))
242        }
243    }
244}
245
246impl<'a, K, T> Iterator for ValuesMut<'a, K, T> {
247    type Item = &'a mut T;
248
249    fn next(&mut self) -> Option<Self::Item> {
250        self.iter.next().map(|(_, v)| v)
251    }
252
253    fn size_hint(&self) -> (usize, Option<usize>) {
254        self.iter.size_hint()
255    }
256}
257
258impl<'a, K, T> DoubleEndedIterator for ValuesMut<'a, K, T> {
259    fn next_back(&mut self) -> Option<Self::Item> {
260        self.iter.next_back().map(|(_, v)| v)
261    }
262}
tether_map/linked_hash_map/iter.rs

tether_map/linked_hash_map/
iter.rs
