linked_hash_table/
iter.rs

1//! Iterator types produced by [`LinkedHashMap`].
2//!
3//! All iterator structs are returned by methods on [`LinkedHashMap`]; you
4//! rarely need to name them explicitly.
5//!
6//! | Type | Created by | Yields |
7//! |------|-----------|--------|
8//! | [`Iter`] | [`iter`] | `(&K, &V)` |
9//! | [`IterMut`] | [`iter_mut`] | `(&K, &mut V)` |
10//! | [`Keys`] | [`keys`] | `&K` |
11//! | [`Values`] | [`values`] | `&V` |
12//! | [`ValuesMut`] | [`values_mut`] | `&mut V` |
13//! | [`Drain`] | [`drain`] | `(K, V)`: empties the map |
14//! | [`IntoIter`] | [`into_iter`] | `(K, V)`: consumes the map |
15//!
16//! [`LinkedHashMap`]: crate::LinkedHashMap
17//! [`iter`]: crate::LinkedHashMap::iter
18//! [`iter_mut`]: crate::LinkedHashMap::iter_mut
19//! [`keys`]: crate::LinkedHashMap::keys
20//! [`values`]: crate::LinkedHashMap::values
21//! [`values_mut`]: crate::LinkedHashMap::values_mut
22//! [`drain`]: crate::LinkedHashMap::drain
23//! [`into_iter`]: crate::LinkedHashMap::into_iter
24
25use std::marker::PhantomData;
26use std::ptr::NonNull;
27
28use crate::node::Node;
29
30/// Iterator over `(&K, &V)` pairs in insertion order.
31///
32/// Created by [`LinkedHashMap::iter`](crate::LinkedHashMap::iter).
33pub struct Iter<'a, K, V> {
34    pub(crate) front: *const Node<K, V>,
35    pub(crate) back: *const Node<K, V>,
36    pub(crate) len: usize,
37    // The `PhantomData` ensures that the output references are properly
38    // constrained by the lifetime of the `&LinkedHashMap` that created this iterator.
39    pub(crate) _marker: PhantomData<(&'a K, &'a V)>,
40}
41
42impl<'a, K, V> Iterator for Iter<'a, K, V> {
43    type Item = (&'a K, &'a V);
44
45    fn next(&mut self) -> Option<Self::Item> {
46        if self.len == 0 {
47            return None;
48        }
49        // SAFETY: `len > 0` guarantees that `front` is a live, fully-initialised
50        // real node (not the tail sentinel).  The `PhantomData` lifetime ties the
51        // output references to `'a`, which is the lifetime of the `&LinkedHashMap`.
52        unsafe {
53            let node = self.front;
54            self.front = (*node).next;
55            self.len -= 1;
56            Some((Node::key_ref(node), Node::value_ref(node)))
57        }
58    }
59
60    #[inline]
61    fn size_hint(&self) -> (usize, Option<usize>) {
62        (self.len, Some(self.len))
63    }
64}
65
66impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
67    fn next_back(&mut self) -> Option<Self::Item> {
68        if self.len == 0 {
69            return None;
70        }
71        // SAFETY: `len > 0` guarantees that `back` is a live real node (not the
72        // head sentinel).
73        unsafe {
74            let node = self.back;
75            self.back = (*node).prev;
76            self.len -= 1;
77            Some((Node::key_ref(node), Node::value_ref(node)))
78        }
79    }
80}
81
82impl<K, V> ExactSizeIterator for Iter<'_, K, V> {}
83
84/// Iterator over `(&K, &mut V)` pairs in insertion order.
85///
86/// Created by [`LinkedHashMap::iter_mut`](crate::LinkedHashMap::iter_mut).
87pub struct IterMut<'a, K, V> {
88    pub(crate) front: *mut Node<K, V>,
89    pub(crate) back: *mut Node<K, V>,
90    pub(crate) len: usize,
91    pub(crate) _marker: PhantomData<(&'a K, &'a mut V)>,
92}
93
94impl<'a, K, V> Iterator for IterMut<'a, K, V> {
95    type Item = (&'a K, &'a mut V);
96
97    fn next(&mut self) -> Option<Self::Item> {
98        if self.len == 0 {
99            return None;
100        }
101        // SAFETY: The `&mut LinkedHashMap` borrow that created this iterator
102        // guarantees exclusive access.  Each node is yielded exactly once, so
103        // no two outstanding `&mut V` references can alias.
104        unsafe {
105            let node = self.front;
106            self.front = (*node).next;
107            self.len -= 1;
108            Some((Node::key_ref(node), Node::value_mut(node)))
109        }
110    }
111
112    #[inline]
113    fn size_hint(&self) -> (usize, Option<usize>) {
114        (self.len, Some(self.len))
115    }
116}
117
118impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
119    fn next_back(&mut self) -> Option<Self::Item> {
120        if self.len == 0 {
121            return None;
122        }
123        // SAFETY: Same as next(), but traversing from the back.
124        unsafe {
125            let node = self.back;
126            self.back = (*node).prev;
127            self.len -= 1;
128            Some((Node::key_ref(node), Node::value_mut(node)))
129        }
130    }
131}
132
133impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {}
134
135/// Iterator over keys in insertion order.
136///
137/// Created by [`LinkedHashMap::keys`](crate::LinkedHashMap::keys).
138pub struct Keys<'a, K, V> {
139    pub(crate) inner: Iter<'a, K, V>,
140}
141
142impl<'a, K, V> Iterator for Keys<'a, K, V> {
143    type Item = &'a K;
144
145    #[inline]
146    fn next(&mut self) -> Option<&'a K> {
147        self.inner.next().map(|(k, _)| k)
148    }
149
150    #[inline]
151    fn size_hint(&self) -> (usize, Option<usize>) {
152        self.inner.size_hint()
153    }
154}
155
156impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
157    #[inline]
158    fn next_back(&mut self) -> Option<&'a K> {
159        self.inner.next_back().map(|(k, _)| k)
160    }
161}
162
163impl<K, V> ExactSizeIterator for Keys<'_, K, V> {}
164
165/// Iterator over values in insertion order.
166///
167/// Created by [`LinkedHashMap::values`](crate::LinkedHashMap::values).
168pub struct Values<'a, K, V> {
169    pub(crate) inner: Iter<'a, K, V>,
170}
171
172impl<'a, K, V> Iterator for Values<'a, K, V> {
173    type Item = &'a V;
174
175    #[inline]
176    fn next(&mut self) -> Option<&'a V> {
177        self.inner.next().map(|(_, v)| v)
178    }
179
180    #[inline]
181    fn size_hint(&self) -> (usize, Option<usize>) {
182        self.inner.size_hint()
183    }
184}
185
186impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
187    #[inline]
188    fn next_back(&mut self) -> Option<&'a V> {
189        self.inner.next_back().map(|(_, v)| v)
190    }
191}
192
193impl<K, V> ExactSizeIterator for Values<'_, K, V> {}
194
195/// Mutable iterator over values in insertion order.
196///
197/// Created by [`LinkedHashMap::values_mut`](crate::LinkedHashMap::values_mut).
198pub struct ValuesMut<'a, K, V> {
199    pub(crate) inner: IterMut<'a, K, V>,
200}
201
202impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
203    type Item = &'a mut V;
204
205    #[inline]
206    fn next(&mut self) -> Option<&'a mut V> {
207        self.inner.next().map(|(_, v)| v)
208    }
209
210    #[inline]
211    fn size_hint(&self) -> (usize, Option<usize>) {
212        self.inner.size_hint()
213    }
214}
215
216impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {}
217
218/// Draining iterator: removes and yields every `(K, V)` pair in insertion
219/// order, leaving the map empty.
220///
221/// Created by [`LinkedHashMap::drain`](crate::LinkedHashMap::drain).
222/// If the iterator is dropped before it is fully consumed, the remaining
223/// elements are freed and the map's sentinel linkage is restored so the map
224/// can be used again immediately.
225pub struct Drain<'a, K, V> {
226    pub(crate) front: *mut Node<K, V>,
227    pub(crate) tail_ptr: *mut Node<K, V>,
228    pub(crate) head_ptr: *mut Node<K, V>,
229    pub(crate) len: usize,
230    pub(crate) _marker: PhantomData<&'a mut (K, V)>,
231}
232
233impl<K, V> Iterator for Drain<'_, K, V> {
234    type Item = (K, V);
235
236    fn next(&mut self) -> Option<(K, V)> {
237        if self.len == 0 {
238            return None;
239        }
240        // SAFETY: `len > 0` means `front` points to a live real node.  We move
241        // the key/value out with `assume_init_read` (the MaybeUninit slots are
242        // now logically uninitialised) and then free the bare Node allocation.
243        unsafe {
244            let node = self.front;
245            self.front = (*node).next;
246            self.len -= 1;
247            let k = Node::key_read(node);
248            let v = Node::value_read(node);
249            let _ = Box::from_raw(node); // free allocation; fields already moved
250            Some((k, v))
251        }
252    }
253
254    #[inline]
255    fn size_hint(&self) -> (usize, Option<usize>) {
256        (self.len, Some(self.len))
257    }
258}
259
260impl<K, V> Drop for Drain<'_, K, V> {
261    fn drop(&mut self) {
262        // Eagerly drop any nodes that the caller did not consume.
263        // SAFETY: Remaining nodes are live and fully initialised.  The owning
264        // map's HashMap index was cleared before Drain was created, so these
265        // nodes are exclusively owned by this iterator.
266        unsafe {
267            let mut cur = self.front;
268            while cur != self.tail_ptr {
269                let next = (*cur).next;
270                Node::drop_real(cur);
271                cur = next;
272            }
273            // Restore the sentinel linkage so the map is in a valid empty state
274            // the moment Drain is dropped.
275            (*self.head_ptr).next = self.tail_ptr;
276            (*self.tail_ptr).prev = self.head_ptr;
277        }
278    }
279}
280
281impl<K, V> ExactSizeIterator for Drain<'_, K, V> {}
282
283/// Consuming iterator: yields every `(K, V)` pair in insertion order,
284/// consuming the map.
285///
286/// Created by calling `.into_iter()` on a [`LinkedHashMap`](crate::LinkedHashMap).
287pub struct IntoIter<K, V> {
288    pub(crate) front: *mut Node<K, V>,
289    pub(crate) tail: NonNull<Node<K, V>>,
290    pub(crate) head: NonNull<Node<K, V>>,
291    pub(crate) len: usize,
292}
293
294// SAFETY: IntoIter exclusively owns all the nodes it points to (it takes
295// ownership from the map via mem::forget + ptr::read).  No aliasing is
296// possible.
297unsafe impl<K: Send, V: Send> Send for IntoIter<K, V> {}
298unsafe impl<K: Sync, V: Sync> Sync for IntoIter<K, V> {}
299
300impl<K, V> Iterator for IntoIter<K, V> {
301    type Item = (K, V);
302
303    fn next(&mut self) -> Option<(K, V)> {
304        if self.len == 0 {
305            return None;
306        }
307        // SAFETY: `len > 0` guarantees `front` is a live real node.
308        unsafe {
309            let node = self.front;
310            self.front = (*node).next;
311            self.len -= 1;
312            let k = Node::key_read(node);
313            let v = Node::value_read(node);
314            let _ = Box::from_raw(node);
315            Some((k, v))
316        }
317    }
318
319    #[inline]
320    fn size_hint(&self) -> (usize, Option<usize>) {
321        (self.len, Some(self.len))
322    }
323}
324
325impl<K, V> Drop for IntoIter<K, V> {
326    fn drop(&mut self) {
327        // Free un-consumed real nodes.
328        // SAFETY: Remaining nodes are live, real, and exclusively owned by
329        // this iterator.
330        unsafe {
331            let mut cur = self.front;
332            while cur != self.tail.as_ptr() {
333                let next = (*cur).next;
334                Node::drop_real(cur);
335                cur = next;
336            }
337            // Free the two sentinel nodes whose key/value are uninitialised.
338            Node::drop_sentinel(self.head.as_ptr());
339            Node::drop_sentinel(self.tail.as_ptr());
340        }
341    }
342}
343
344impl<K, V> ExactSizeIterator for IntoIter<K, V> {}
345
346// Variance assertions
347//
348// These compile-time checks verify that each iterator type is *covariant*
349// in its lifetime and type parameters: a longer lifetime / more-derived type
350// can be shortened / widened to match a shorter lifetime / less-derived type.
351//
352// The pattern is: write a function that accepts the "longer" type and returns
353// the "shorter" type with only implicit subtyping — if the compiler accepts it,
354// the type is covariant in those parameters.
355
356#[cfg(not(coverage))]
357const _: () = {
358    /// `Iter<'long, K, V>` is covariant in `'a`, `K`, and `V`.
359    fn _check_iter<'long: 'short, 'short, K, V>(x: Iter<'long, K, V>) -> Iter<'short, K, V> {
360        x
361    }
362
363    /// `IterMut<'long, K, V>` is covariant in `'a` and `K`, but NOT in `V`
364    /// (it yields `&'a mut V`).  We only assert covariance in `'a` and `K`.
365    fn _check_iter_mut_lifetime<'long: 'short, 'short, K, V>(
366        x: IterMut<'long, K, V>,
367    ) -> IterMut<'short, K, V> {
368        x
369    }
370
371    /// `Keys<'long, K, V>` is covariant in `'a` and `K`.
372    fn _check_keys<'long: 'short, 'short, K, V>(x: Keys<'long, K, V>) -> Keys<'short, K, V> {
373        x
374    }
375
376    /// `Values<'long, K, V>` is covariant in `'a` and `V`.
377    fn _check_values<'long: 'short, 'short, K, V>(x: Values<'long, K, V>) -> Values<'short, K, V> {
378        x
379    }
380
381    /// `IntoIter<K, V>` is covariant in `K` and `V`.
382    ///
383    /// Since `IntoIter` has no lifetime, we verify this by confirming that the
384    /// struct compiles and the PhantomData annotation is sound.  The owned
385    /// `(K, V)` pairs it yields make covariance safe.
386    fn _check_into_iter<K, V>(_: IntoIter<K, V>) {}
387};
linked_hash_table/iter.rs

linked_hash_table/
iter.rs
