Messages in this thread Patch in this message | | | Date | Tue, 02 Apr 2024 12:17:03 +0000 | Subject | [PATCH 6/9] rust: list: add iterators | From | Alice Ryhl <> |
| |
Rust Binder has lists containing stuff such as all contexts or all processes, and sometimes need to iterate over them. This patch enables Rust Binder to do that using a normal for loop.
The iterator returns the ArcBorrow type, so it is possible to grab a refcount to values while iterating.
Signed-off-by: Alice Ryhl <aliceryhl@google.com> --- rust/kernel/list.rs | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 102 insertions(+)
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 7e9ed802b26b..892705dd0571 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -5,7 +5,9 @@ //! A linked list implementation. use crate::init::PinInit; +use crate::sync::ArcBorrow; use crate::types::Opaque; +use core::iter::{DoubleEndedIterator, FusedIterator}; use core::marker::PhantomData; use core::ptr; @@ -405,6 +407,17 @@ pub fn push_all_back(&mut self, other: &mut List<T, ID>) { // INVARIANT: The other list is now empty, so update its pointer. other.first = ptr::null_mut(); } + + /// Creates an iterator over the list. + pub fn iter(&self) -> Iter<'_, T, ID> { + // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point + // at the first element of the same list. + Iter { + current: self.first, + stop: self.first, + _ty: PhantomData, + } + } } impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> { @@ -414,3 +427,92 @@ fn drop(&mut self) { } } } + +/// An iterator into a [`List`]. +/// +/// # Invariants +/// +/// The `current` pointer points at a value in a list, or it is null if the iterator has reached +/// the end of the list. The `stop` pointer points at the first value in the same list, or it is +/// null if the list is empty. +#[derive(Clone)] +pub struct Iter<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> { + current: *mut ListLinksFields, + stop: *mut ListLinksFields, + _ty: PhantomData<&'a ListArc<T, ID>>, +} + +impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Iterator for Iter<'a, T, ID> { + type Item = ArcBorrow<'a, T>; + + fn next(&mut self) -> Option<ArcBorrow<'a, T>> { + if self.current.is_null() { + return None; + } + + let current = self.current; + + // SAFETY: We just checked that `current` is not null, so it is in a list, and hence not + // dangling. There's no race because the iterator holds an immutable borrow to the list. + let next = unsafe { (*current).next }; + // INVARIANT: If `current` was the last element of the list, then this updates it to null. + // Otherwise, we update it to the next element. + self.current = if next != self.stop { + next + } else { + ptr::null_mut() + }; + + // SAFETY: The `current` pointer points a value in the list. + let item = unsafe { T::view_value(ListLinks::from_fields(current)) }; + // SAFETY: + // * All values in a list are stored in an `Arc`. + // * The value cannot be removed from the list for the duration of the lifetime annotated + // on the returned `ArcBorrow`, because removing it from the list would require mutable + // access to the list. However, the `ArcBorrow` is annotated with the iterator's + // lifetime, and the list is immutably borrowed for that lifetime. + // * Values in a list never have a `UniqueArc` reference. + Some(unsafe { ArcBorrow::from_raw(item) }) + } +} + +impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for Iter<'a, T, ID> {} + +impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for &'a List<T, ID> { + type IntoIter = Iter<'a, T, ID>; + type Item = ArcBorrow<'a, T>; + + fn into_iter(self) -> Iter<'a, T, ID> { + self.iter() + } +} + +/// An owning iterator into a [`List`]. +pub struct IntoIter<T: ?Sized + ListItem<ID>, const ID: u64 = 0> { + list: List<T, ID>, +} + +impl<T: ?Sized + ListItem<ID>, const ID: u64> Iterator for IntoIter<T, ID> { + type Item = ListArc<T, ID>; + + fn next(&mut self) -> Option<ListArc<T, ID>> { + self.list.pop_front() + } +} + +impl<T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for IntoIter<T, ID> {} + +impl<T: ?Sized + ListItem<ID>, const ID: u64> DoubleEndedIterator for IntoIter<T, ID> { + fn next_back(&mut self) -> Option<ListArc<T, ID>> { + self.list.pop_back() + } +} + +impl<T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for List<T, ID> { + type IntoIter = IntoIter<T, ID>; + type Item = ListArc<T, ID>; + + fn into_iter(self) -> IntoIter<T, ID> { + IntoIter { list: self } + } +} -- 2.44.0.478.gd926399ef9-goog
| |