kernel/list.rs
1// SPDX-License-Identifier: GPL-2.0
2
3// Copyright (C) 2024 Google LLC.
4
5//! A linked list implementation.
6
7use crate::sync::ArcBorrow;
8use crate::types::Opaque;
9use core::iter::{DoubleEndedIterator, FusedIterator};
10use core::marker::PhantomData;
11use core::ptr;
12use pin_init::PinInit;
13
14mod impl_list_item_mod;
15pub use self::impl_list_item_mod::{
16 impl_has_list_links, impl_has_list_links_self_ptr, impl_list_item, HasListLinks, HasSelfPtr,
17};
18
19mod arc;
20pub use self::arc::{impl_list_arc_safe, AtomicTracker, ListArc, ListArcSafe, TryNewListArc};
21
22mod arc_field;
23pub use self::arc_field::{define_list_arc_field_getter, ListArcField};
24
25/// A linked list.
26///
27/// All elements in this linked list will be [`ListArc`] references to the value. Since a value can
28/// only have one `ListArc` (for each pair of prev/next pointers), this ensures that the same
29/// prev/next pointers are not used for several linked lists.
30///
31/// # Invariants
32///
33/// * If the list is empty, then `first` is null. Otherwise, `first` points at the `ListLinks`
34/// field of the first element in the list.
35/// * All prev/next pointers in `ListLinks` fields of items in the list are valid and form a cycle.
36/// * For every item in the list, the list owns the associated [`ListArc`] reference and has
37/// exclusive access to the `ListLinks` field.
38///
39/// # Examples
40///
41/// ```
42/// use kernel::list::*;
43///
44/// #[pin_data]
45/// struct BasicItem {
46/// value: i32,
47/// #[pin]
48/// links: ListLinks,
49/// }
50///
51/// impl BasicItem {
52/// fn new(value: i32) -> Result<ListArc<Self>> {
53/// ListArc::pin_init(try_pin_init!(Self {
54/// value,
55/// links <- ListLinks::new(),
56/// }), GFP_KERNEL)
57/// }
58/// }
59///
60/// impl_list_arc_safe! {
61/// impl ListArcSafe<0> for BasicItem { untracked; }
62/// }
63/// impl_list_item! {
64/// impl ListItem<0> for BasicItem { using ListLinks { self.links }; }
65/// }
66///
67/// // Create a new empty list.
68/// let mut list = List::new();
69/// {
70/// assert!(list.is_empty());
71/// }
72///
73/// // Insert 3 elements using `push_back()`.
74/// list.push_back(BasicItem::new(15)?);
75/// list.push_back(BasicItem::new(10)?);
76/// list.push_back(BasicItem::new(30)?);
77///
78/// // Iterate over the list to verify the nodes were inserted correctly.
79/// // [15, 10, 30]
80/// {
81/// let mut iter = list.iter();
82/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);
83/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 10);
84/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 30);
85/// assert!(iter.next().is_none());
86///
87/// // Verify the length of the list.
88/// assert_eq!(list.iter().count(), 3);
89/// }
90///
91/// // Pop the items from the list using `pop_back()` and verify the content.
92/// {
93/// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 30);
94/// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 10);
95/// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 15);
96/// }
97///
98/// // Insert 3 elements using `push_front()`.
99/// list.push_front(BasicItem::new(15)?);
100/// list.push_front(BasicItem::new(10)?);
101/// list.push_front(BasicItem::new(30)?);
102///
103/// // Iterate over the list to verify the nodes were inserted correctly.
104/// // [30, 10, 15]
105/// {
106/// let mut iter = list.iter();
107/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 30);
108/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 10);
109/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);
110/// assert!(iter.next().is_none());
111///
112/// // Verify the length of the list.
113/// assert_eq!(list.iter().count(), 3);
114/// }
115///
116/// // Pop the items from the list using `pop_front()` and verify the content.
117/// {
118/// assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 30);
119/// assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 10);
120/// }
121///
122/// // Push `list2` to `list` through `push_all_back()`.
123/// // list: [15]
124/// // list2: [25, 35]
125/// {
126/// let mut list2 = List::new();
127/// list2.push_back(BasicItem::new(25)?);
128/// list2.push_back(BasicItem::new(35)?);
129///
130/// list.push_all_back(&mut list2);
131///
132/// // list: [15, 25, 35]
133/// // list2: []
134/// let mut iter = list.iter();
135/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);
136/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 25);
137/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 35);
138/// assert!(iter.next().is_none());
139/// assert!(list2.is_empty());
140/// }
141/// # Result::<(), Error>::Ok(())
142/// ```
143pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
144 first: *mut ListLinksFields,
145 _ty: PhantomData<ListArc<T, ID>>,
146}
147
148// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
149// type of access to the `ListArc<T, ID>` elements.
150unsafe impl<T, const ID: u64> Send for List<T, ID>
151where
152 ListArc<T, ID>: Send,
153 T: ?Sized + ListItem<ID>,
154{
155}
156// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
157// type of access to the `ListArc<T, ID>` elements.
158unsafe impl<T, const ID: u64> Sync for List<T, ID>
159where
160 ListArc<T, ID>: Sync,
161 T: ?Sized + ListItem<ID>,
162{
163}
164
165/// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`].
166///
167/// # Safety
168///
169/// Implementers must ensure that they provide the guarantees documented on methods provided by
170/// this trait.
171///
172/// [`ListArc<Self>`]: ListArc
173pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
174 /// Views the [`ListLinks`] for this value.
175 ///
176 /// # Guarantees
177 ///
178 /// If there is a previous call to `prepare_to_insert` and there is no call to `post_remove`
179 /// since the most recent such call, then this returns the same pointer as the one returned by
180 /// the most recent call to `prepare_to_insert`.
181 ///
182 /// Otherwise, the returned pointer points at a read-only [`ListLinks`] with two null pointers.
183 ///
184 /// # Safety
185 ///
186 /// The provided pointer must point at a valid value. (It need not be in an `Arc`.)
187 unsafe fn view_links(me: *const Self) -> *mut ListLinks<ID>;
188
189 /// View the full value given its [`ListLinks`] field.
190 ///
191 /// Can only be used when the value is in a list.
192 ///
193 /// # Guarantees
194 ///
195 /// * Returns the same pointer as the one passed to the most recent call to `prepare_to_insert`.
196 /// * The returned pointer is valid until the next call to `post_remove`.
197 ///
198 /// # Safety
199 ///
200 /// * The provided pointer must originate from the most recent call to `prepare_to_insert`, or
201 /// from a call to `view_links` that happened after the most recent call to
202 /// `prepare_to_insert`.
203 /// * Since the most recent call to `prepare_to_insert`, the `post_remove` method must not have
204 /// been called.
205 unsafe fn view_value(me: *mut ListLinks<ID>) -> *const Self;
206
207 /// This is called when an item is inserted into a [`List`].
208 ///
209 /// # Guarantees
210 ///
211 /// The caller is granted exclusive access to the returned [`ListLinks`] until `post_remove` is
212 /// called.
213 ///
214 /// # Safety
215 ///
216 /// * The provided pointer must point at a valid value in an [`Arc`].
217 /// * Calls to `prepare_to_insert` and `post_remove` on the same value must alternate.
218 /// * The caller must own the [`ListArc`] for this value.
219 /// * The caller must not give up ownership of the [`ListArc`] unless `post_remove` has been
220 /// called after this call to `prepare_to_insert`.
221 ///
222 /// [`Arc`]: crate::sync::Arc
223 unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<ID>;
224
225 /// This undoes a previous call to `prepare_to_insert`.
226 ///
227 /// # Guarantees
228 ///
229 /// The returned pointer is the pointer that was originally passed to `prepare_to_insert`.
230 ///
231 /// # Safety
232 ///
233 /// The provided pointer must be the pointer returned by the most recent call to
234 /// `prepare_to_insert`.
235 unsafe fn post_remove(me: *mut ListLinks<ID>) -> *const Self;
236}
237
238#[repr(C)]
239#[derive(Copy, Clone)]
240struct ListLinksFields {
241 next: *mut ListLinksFields,
242 prev: *mut ListLinksFields,
243}
244
245/// The prev/next pointers for an item in a linked list.
246///
247/// # Invariants
248///
249/// The fields are null if and only if this item is not in a list.
250#[repr(transparent)]
251pub struct ListLinks<const ID: u64 = 0> {
252 // This type is `!Unpin` for aliasing reasons as the pointers are part of an intrusive linked
253 // list.
254 inner: Opaque<ListLinksFields>,
255}
256
257// SAFETY: The only way to access/modify the pointers inside of `ListLinks<ID>` is via holding the
258// associated `ListArc<T, ID>`. Since that type correctly implements `Send`, it is impossible to
259// move this an instance of this type to a different thread if the pointees are `!Send`.
260unsafe impl<const ID: u64> Send for ListLinks<ID> {}
261// SAFETY: The type is opaque so immutable references to a ListLinks are useless. Therefore, it's
262// okay to have immutable access to a ListLinks from several threads at once.
263unsafe impl<const ID: u64> Sync for ListLinks<ID> {}
264
265impl<const ID: u64> ListLinks<ID> {
266 /// Creates a new initializer for this type.
267 pub fn new() -> impl PinInit<Self> {
268 // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will
269 // not be constructed in an `Arc` that already has a `ListArc`.
270 ListLinks {
271 inner: Opaque::new(ListLinksFields {
272 prev: ptr::null_mut(),
273 next: ptr::null_mut(),
274 }),
275 }
276 }
277
278 /// # Safety
279 ///
280 /// `me` must be dereferenceable.
281 #[inline]
282 unsafe fn fields(me: *mut Self) -> *mut ListLinksFields {
283 // SAFETY: The caller promises that the pointer is valid.
284 unsafe { Opaque::cast_into(ptr::addr_of!((*me).inner)) }
285 }
286
287 /// # Safety
288 ///
289 /// `me` must be dereferenceable.
290 #[inline]
291 unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self {
292 me.cast()
293 }
294}
295
296/// Similar to [`ListLinks`], but also contains a pointer to the full value.
297///
298/// This type can be used instead of [`ListLinks`] to support lists with trait objects.
299#[repr(C)]
300pub struct ListLinksSelfPtr<T: ?Sized, const ID: u64 = 0> {
301 /// The `ListLinks` field inside this value.
302 ///
303 /// This is public so that it can be used with `impl_has_list_links!`.
304 pub inner: ListLinks<ID>,
305 // UnsafeCell is not enough here because we use `Opaque::uninit` as a dummy value, and
306 // `ptr::null()` doesn't work for `T: ?Sized`.
307 self_ptr: Opaque<*const T>,
308}
309
310// SAFETY: The fields of a ListLinksSelfPtr can be moved across thread boundaries.
311unsafe impl<T: ?Sized + Send, const ID: u64> Send for ListLinksSelfPtr<T, ID> {}
312// SAFETY: The type is opaque so immutable references to a ListLinksSelfPtr are useless. Therefore,
313// it's okay to have immutable access to a ListLinks from several threads at once.
314//
315// Note that `inner` being a public field does not prevent this type from being opaque, since
316// `inner` is a opaque type.
317unsafe impl<T: ?Sized + Sync, const ID: u64> Sync for ListLinksSelfPtr<T, ID> {}
318
319impl<T: ?Sized, const ID: u64> ListLinksSelfPtr<T, ID> {
320 /// Creates a new initializer for this type.
321 pub fn new() -> impl PinInit<Self> {
322 // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will
323 // not be constructed in an `Arc` that already has a `ListArc`.
324 Self {
325 inner: ListLinks {
326 inner: Opaque::new(ListLinksFields {
327 prev: ptr::null_mut(),
328 next: ptr::null_mut(),
329 }),
330 },
331 self_ptr: Opaque::uninit(),
332 }
333 }
334
335 /// Returns a pointer to the self pointer.
336 ///
337 /// # Safety
338 ///
339 /// The provided pointer must point at a valid struct of type `Self`.
340 pub unsafe fn raw_get_self_ptr(me: *const Self) -> *const Opaque<*const T> {
341 // SAFETY: The caller promises that the pointer is valid.
342 unsafe { ptr::addr_of!((*me).self_ptr) }
343 }
344}
345
346impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> {
347 /// Creates a new empty list.
348 pub const fn new() -> Self {
349 Self {
350 first: ptr::null_mut(),
351 _ty: PhantomData,
352 }
353 }
354
355 /// Returns whether this list is empty.
356 pub fn is_empty(&self) -> bool {
357 self.first.is_null()
358 }
359
360 /// Inserts `item` before `next` in the cycle.
361 ///
362 /// Returns a pointer to the newly inserted element. Never changes `self.first` unless the list
363 /// is empty.
364 ///
365 /// # Safety
366 ///
367 /// * `next` must be an element in this list or null.
368 /// * if `next` is null, then the list must be empty.
369 unsafe fn insert_inner(
370 &mut self,
371 item: ListArc<T, ID>,
372 next: *mut ListLinksFields,
373 ) -> *mut ListLinksFields {
374 let raw_item = ListArc::into_raw(item);
375 // SAFETY:
376 // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`.
377 // * Since we have ownership of the `ListArc`, `post_remove` must have been called after
378 // the most recent call to `prepare_to_insert`, if any.
379 // * We own the `ListArc`.
380 // * Removing items from this list is always done using `remove_internal_inner`, which
381 // calls `post_remove` before giving up ownership.
382 let list_links = unsafe { T::prepare_to_insert(raw_item) };
383 // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid.
384 let item = unsafe { ListLinks::fields(list_links) };
385
386 // Check if the list is empty.
387 if next.is_null() {
388 // SAFETY: The caller just gave us ownership of these fields.
389 // INVARIANT: A linked list with one item should be cyclic.
390 unsafe {
391 (*item).next = item;
392 (*item).prev = item;
393 }
394 self.first = item;
395 } else {
396 // SAFETY: By the type invariant, this pointer is valid or null. We just checked that
397 // it's not null, so it must be valid.
398 let prev = unsafe { (*next).prev };
399 // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
400 // ownership of the fields on `item`.
401 // INVARIANT: This correctly inserts `item` between `prev` and `next`.
402 unsafe {
403 (*item).next = next;
404 (*item).prev = prev;
405 (*prev).next = item;
406 (*next).prev = item;
407 }
408 }
409
410 item
411 }
412
413 /// Add the provided item to the back of the list.
414 pub fn push_back(&mut self, item: ListArc<T, ID>) {
415 // SAFETY:
416 // * `self.first` is null or in the list.
417 // * `self.first` is only null if the list is empty.
418 unsafe { self.insert_inner(item, self.first) };
419 }
420
421 /// Add the provided item to the front of the list.
422 pub fn push_front(&mut self, item: ListArc<T, ID>) {
423 // SAFETY:
424 // * `self.first` is null or in the list.
425 // * `self.first` is only null if the list is empty.
426 let new_elem = unsafe { self.insert_inner(item, self.first) };
427
428 // INVARIANT: `new_elem` is in the list because we just inserted it.
429 self.first = new_elem;
430 }
431
432 /// Removes the last item from this list.
433 pub fn pop_back(&mut self) -> Option<ListArc<T, ID>> {
434 if self.is_empty() {
435 return None;
436 }
437
438 // SAFETY: We just checked that the list is not empty.
439 let last = unsafe { (*self.first).prev };
440 // SAFETY: The last item of this list is in this list.
441 Some(unsafe { self.remove_internal(last) })
442 }
443
444 /// Removes the first item from this list.
445 pub fn pop_front(&mut self) -> Option<ListArc<T, ID>> {
446 if self.is_empty() {
447 return None;
448 }
449
450 // SAFETY: The first item of this list is in this list.
451 Some(unsafe { self.remove_internal(self.first) })
452 }
453
454 /// Removes the provided item from this list and returns it.
455 ///
456 /// This returns `None` if the item is not in the list. (Note that by the safety requirements,
457 /// this means that the item is not in any list.)
458 ///
459 /// # Safety
460 ///
461 /// `item` must not be in a different linked list (with the same id).
462 pub unsafe fn remove(&mut self, item: &T) -> Option<ListArc<T, ID>> {
463 // SAFETY: TODO.
464 let mut item = unsafe { ListLinks::fields(T::view_links(item)) };
465 // SAFETY: The user provided a reference, and reference are never dangling.
466 //
467 // As for why this is not a data race, there are two cases:
468 //
469 // * If `item` is not in any list, then these fields are read-only and null.
470 // * If `item` is in this list, then we have exclusive access to these fields since we
471 // have a mutable reference to the list.
472 //
473 // In either case, there's no race.
474 let ListLinksFields { next, prev } = unsafe { *item };
475
476 debug_assert_eq!(next.is_null(), prev.is_null());
477 if !next.is_null() {
478 // This is really a no-op, but this ensures that `item` is a raw pointer that was
479 // obtained without going through a pointer->reference->pointer conversion roundtrip.
480 // This ensures that the list is valid under the more restrictive strict provenance
481 // ruleset.
482 //
483 // SAFETY: We just checked that `next` is not null, and it's not dangling by the
484 // list invariants.
485 unsafe {
486 debug_assert_eq!(item, (*next).prev);
487 item = (*next).prev;
488 }
489
490 // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it
491 // is in this list. The pointers are in the right order.
492 Some(unsafe { self.remove_internal_inner(item, next, prev) })
493 } else {
494 None
495 }
496 }
497
498 /// Removes the provided item from the list.
499 ///
500 /// # Safety
501 ///
502 /// `item` must point at an item in this list.
503 unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> ListArc<T, ID> {
504 // SAFETY: The caller promises that this pointer is not dangling, and there's no data race
505 // since we have a mutable reference to the list containing `item`.
506 let ListLinksFields { next, prev } = unsafe { *item };
507 // SAFETY: The pointers are ok and in the right order.
508 unsafe { self.remove_internal_inner(item, next, prev) }
509 }
510
511 /// Removes the provided item from the list.
512 ///
513 /// # Safety
514 ///
515 /// The `item` pointer must point at an item in this list, and we must have `(*item).next ==
516 /// next` and `(*item).prev == prev`.
517 unsafe fn remove_internal_inner(
518 &mut self,
519 item: *mut ListLinksFields,
520 next: *mut ListLinksFields,
521 prev: *mut ListLinksFields,
522 ) -> ListArc<T, ID> {
523 // SAFETY: We have exclusive access to the pointers of items in the list, and the prev/next
524 // pointers are always valid for items in a list.
525 //
526 // INVARIANT: There are three cases:
527 // * If the list has at least three items, then after removing the item, `prev` and `next`
528 // will be next to each other.
529 // * If the list has two items, then the remaining item will point at itself.
530 // * If the list has one item, then `next == prev == item`, so these writes have no
531 // effect. The list remains unchanged and `item` is still in the list for now.
532 unsafe {
533 (*next).prev = prev;
534 (*prev).next = next;
535 }
536 // SAFETY: We have exclusive access to items in the list.
537 // INVARIANT: `item` is being removed, so the pointers should be null.
538 unsafe {
539 (*item).prev = ptr::null_mut();
540 (*item).next = ptr::null_mut();
541 }
542 // INVARIANT: There are three cases:
543 // * If `item` was not the first item, then `self.first` should remain unchanged.
544 // * If `item` was the first item and there is another item, then we just updated
545 // `prev->next` to `next`, which is the new first item, and setting `item->next` to null
546 // did not modify `prev->next`.
547 // * If `item` was the only item in the list, then `prev == item`, and we just set
548 // `item->next` to null, so this correctly sets `first` to null now that the list is
549 // empty.
550 if self.first == item {
551 // SAFETY: The `prev` pointer is the value that `item->prev` had when it was in this
552 // list, so it must be valid. There is no race since `prev` is still in the list and we
553 // still have exclusive access to the list.
554 self.first = unsafe { (*prev).next };
555 }
556
557 // SAFETY: `item` used to be in the list, so it is dereferenceable by the type invariants
558 // of `List`.
559 let list_links = unsafe { ListLinks::from_fields(item) };
560 // SAFETY: Any pointer in the list originates from a `prepare_to_insert` call.
561 let raw_item = unsafe { T::post_remove(list_links) };
562 // SAFETY: The above call to `post_remove` guarantees that we can recreate the `ListArc`.
563 unsafe { ListArc::from_raw(raw_item) }
564 }
565
566 /// Moves all items from `other` into `self`.
567 ///
568 /// The items of `other` are added to the back of `self`, so the last item of `other` becomes
569 /// the last item of `self`.
570 pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
571 // First, we insert the elements into `self`. At the end, we make `other` empty.
572 if self.is_empty() {
573 // INVARIANT: All of the elements in `other` become elements of `self`.
574 self.first = other.first;
575 } else if !other.is_empty() {
576 let other_first = other.first;
577 // SAFETY: The other list is not empty, so this pointer is valid.
578 let other_last = unsafe { (*other_first).prev };
579 let self_first = self.first;
580 // SAFETY: The self list is not empty, so this pointer is valid.
581 let self_last = unsafe { (*self_first).prev };
582
583 // SAFETY: We have exclusive access to both lists, so we can update the pointers.
584 // INVARIANT: This correctly sets the pointers to merge both lists. We do not need to
585 // update `self.first` because the first element of `self` does not change.
586 unsafe {
587 (*self_first).prev = other_last;
588 (*other_last).next = self_first;
589 (*self_last).next = other_first;
590 (*other_first).prev = self_last;
591 }
592 }
593
594 // INVARIANT: The other list is now empty, so update its pointer.
595 other.first = ptr::null_mut();
596 }
597
598 /// Returns a cursor that points before the first element of the list.
599 pub fn cursor_front(&mut self) -> Cursor<'_, T, ID> {
600 // INVARIANT: `self.first` is in this list.
601 Cursor {
602 next: self.first,
603 list: self,
604 }
605 }
606
607 /// Returns a cursor that points after the last element in the list.
608 pub fn cursor_back(&mut self) -> Cursor<'_, T, ID> {
609 // INVARIANT: `next` is allowed to be null.
610 Cursor {
611 next: core::ptr::null_mut(),
612 list: self,
613 }
614 }
615
616 /// Creates an iterator over the list.
617 pub fn iter(&self) -> Iter<'_, T, ID> {
618 // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point
619 // at the first element of the same list.
620 Iter {
621 current: self.first,
622 stop: self.first,
623 _ty: PhantomData,
624 }
625 }
626}
627
628impl<T: ?Sized + ListItem<ID>, const ID: u64> Default for List<T, ID> {
629 fn default() -> Self {
630 List::new()
631 }
632}
633
634impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> {
635 fn drop(&mut self) {
636 while let Some(item) = self.pop_front() {
637 drop(item);
638 }
639 }
640}
641
642/// An iterator over a [`List`].
643///
644/// # Invariants
645///
646/// * There must be a [`List`] that is immutably borrowed for the duration of `'a`.
647/// * The `current` pointer is null or points at a value in that [`List`].
648/// * The `stop` pointer is equal to the `first` field of that [`List`].
649#[derive(Clone)]
650pub struct Iter<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
651 current: *mut ListLinksFields,
652 stop: *mut ListLinksFields,
653 _ty: PhantomData<&'a ListArc<T, ID>>,
654}
655
656impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Iterator for Iter<'a, T, ID> {
657 type Item = ArcBorrow<'a, T>;
658
659 fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
660 if self.current.is_null() {
661 return None;
662 }
663
664 let current = self.current;
665
666 // SAFETY: We just checked that `current` is not null, so it is in a list, and hence not
667 // dangling. There's no race because the iterator holds an immutable borrow to the list.
668 let next = unsafe { (*current).next };
669 // INVARIANT: If `current` was the last element of the list, then this updates it to null.
670 // Otherwise, we update it to the next element.
671 self.current = if next != self.stop {
672 next
673 } else {
674 ptr::null_mut()
675 };
676
677 // SAFETY: The `current` pointer points at a value in the list.
678 let item = unsafe { T::view_value(ListLinks::from_fields(current)) };
679 // SAFETY:
680 // * All values in a list are stored in an `Arc`.
681 // * The value cannot be removed from the list for the duration of the lifetime annotated
682 // on the returned `ArcBorrow`, because removing it from the list would require mutable
683 // access to the list. However, the `ArcBorrow` is annotated with the iterator's
684 // lifetime, and the list is immutably borrowed for that lifetime.
685 // * Values in a list never have a `UniqueArc` reference.
686 Some(unsafe { ArcBorrow::from_raw(item) })
687 }
688}
689
690/// A cursor into a [`List`].
691///
692/// A cursor always rests between two elements in the list. This means that a cursor has a previous
693/// and next element, but no current element. It also means that it's possible to have a cursor
694/// into an empty list.
695///
696/// # Examples
697///
698/// ```
699/// use kernel::prelude::*;
700/// use kernel::list::{List, ListArc, ListLinks};
701///
702/// #[pin_data]
703/// struct ListItem {
704/// value: u32,
705/// #[pin]
706/// links: ListLinks,
707/// }
708///
709/// impl ListItem {
710/// fn new(value: u32) -> Result<ListArc<Self>> {
711/// ListArc::pin_init(try_pin_init!(Self {
712/// value,
713/// links <- ListLinks::new(),
714/// }), GFP_KERNEL)
715/// }
716/// }
717///
718/// kernel::list::impl_list_arc_safe! {
719/// impl ListArcSafe<0> for ListItem { untracked; }
720/// }
721/// kernel::list::impl_list_item! {
722/// impl ListItem<0> for ListItem { using ListLinks { self.links }; }
723/// }
724///
725/// // Use a cursor to remove the first element with the given value.
726/// fn remove_first(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
727/// let mut cursor = list.cursor_front();
728/// while let Some(next) = cursor.peek_next() {
729/// if next.value == value {
730/// return Some(next.remove());
731/// }
732/// cursor.move_next();
733/// }
734/// None
735/// }
736///
737/// // Use a cursor to remove the last element with the given value.
738/// fn remove_last(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
739/// let mut cursor = list.cursor_back();
740/// while let Some(prev) = cursor.peek_prev() {
741/// if prev.value == value {
742/// return Some(prev.remove());
743/// }
744/// cursor.move_prev();
745/// }
746/// None
747/// }
748///
749/// // Use a cursor to remove all elements with the given value. The removed elements are moved to
750/// // a new list.
751/// fn remove_all(list: &mut List<ListItem>, value: u32) -> List<ListItem> {
752/// let mut out = List::new();
753/// let mut cursor = list.cursor_front();
754/// while let Some(next) = cursor.peek_next() {
755/// if next.value == value {
756/// out.push_back(next.remove());
757/// } else {
758/// cursor.move_next();
759/// }
760/// }
761/// out
762/// }
763///
764/// // Use a cursor to insert a value at a specific index. Returns an error if the index is out of
765/// // bounds.
766/// fn insert_at(list: &mut List<ListItem>, new: ListArc<ListItem>, idx: usize) -> Result {
767/// let mut cursor = list.cursor_front();
768/// for _ in 0..idx {
769/// if !cursor.move_next() {
770/// return Err(EINVAL);
771/// }
772/// }
773/// cursor.insert_next(new);
774/// Ok(())
775/// }
776///
777/// // Merge two sorted lists into a single sorted list.
778/// fn merge_sorted(list: &mut List<ListItem>, merge: List<ListItem>) {
779/// let mut cursor = list.cursor_front();
780/// for to_insert in merge {
781/// while let Some(next) = cursor.peek_next() {
782/// if to_insert.value < next.value {
783/// break;
784/// }
785/// cursor.move_next();
786/// }
787/// cursor.insert_prev(to_insert);
788/// }
789/// }
790///
791/// let mut list = List::new();
792/// list.push_back(ListItem::new(14)?);
793/// list.push_back(ListItem::new(12)?);
794/// list.push_back(ListItem::new(10)?);
795/// list.push_back(ListItem::new(12)?);
796/// list.push_back(ListItem::new(15)?);
797/// list.push_back(ListItem::new(14)?);
798/// assert_eq!(remove_all(&mut list, 12).iter().count(), 2);
799/// // [14, 10, 15, 14]
800/// assert!(remove_first(&mut list, 14).is_some());
801/// // [10, 15, 14]
802/// insert_at(&mut list, ListItem::new(12)?, 2)?;
803/// // [10, 15, 12, 14]
804/// assert!(remove_last(&mut list, 15).is_some());
805/// // [10, 12, 14]
806///
807/// let mut list2 = List::new();
808/// list2.push_back(ListItem::new(11)?);
809/// list2.push_back(ListItem::new(13)?);
810/// merge_sorted(&mut list, list2);
811///
812/// let mut items = list.into_iter();
813/// assert_eq!(items.next().ok_or(EINVAL)?.value, 10);
814/// assert_eq!(items.next().ok_or(EINVAL)?.value, 11);
815/// assert_eq!(items.next().ok_or(EINVAL)?.value, 12);
816/// assert_eq!(items.next().ok_or(EINVAL)?.value, 13);
817/// assert_eq!(items.next().ok_or(EINVAL)?.value, 14);
818/// assert!(items.next().is_none());
819/// # Result::<(), Error>::Ok(())
820/// ```
821///
822/// # Invariants
823///
824/// The `next` pointer is null or points a value in `list`.
825pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
826 list: &'a mut List<T, ID>,
827 /// Points at the element after this cursor, or null if the cursor is after the last element.
828 next: *mut ListLinksFields,
829}
830
831impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Cursor<'a, T, ID> {
832 /// Returns a pointer to the element before the cursor.
833 ///
834 /// Returns null if there is no element before the cursor.
835 fn prev_ptr(&self) -> *mut ListLinksFields {
836 let mut next = self.next;
837 let first = self.list.first;
838 if next == first {
839 // We are before the first element.
840 return core::ptr::null_mut();
841 }
842
843 if next.is_null() {
844 // We are after the last element, so we need a pointer to the last element, which is
845 // the same as `(*first).prev`.
846 next = first;
847 }
848
849 // SAFETY: `next` can't be null, because then `first` must also be null, but in that case
850 // we would have exited at the `next == first` check. Thus, `next` is an element in the
851 // list, so we can access its `prev` pointer.
852 unsafe { (*next).prev }
853 }
854
855 /// Access the element after this cursor.
856 pub fn peek_next(&mut self) -> Option<CursorPeek<'_, 'a, T, true, ID>> {
857 if self.next.is_null() {
858 return None;
859 }
860
861 // INVARIANT:
862 // * We just checked that `self.next` is non-null, so it must be in `self.list`.
863 // * `ptr` is equal to `self.next`.
864 Some(CursorPeek {
865 ptr: self.next,
866 cursor: self,
867 })
868 }
869
870 /// Access the element before this cursor.
871 pub fn peek_prev(&mut self) -> Option<CursorPeek<'_, 'a, T, false, ID>> {
872 let prev = self.prev_ptr();
873
874 if prev.is_null() {
875 return None;
876 }
877
878 // INVARIANT:
879 // * We just checked that `prev` is non-null, so it must be in `self.list`.
880 // * `self.prev_ptr()` never returns `self.next`.
881 Some(CursorPeek {
882 ptr: prev,
883 cursor: self,
884 })
885 }
886
887 /// Move the cursor one element forward.
888 ///
889 /// If the cursor is after the last element, then this call does nothing. This call returns
890 /// `true` if the cursor's position was changed.
891 pub fn move_next(&mut self) -> bool {
892 if self.next.is_null() {
893 return false;
894 }
895
896 // SAFETY: `self.next` is an element in the list and we borrow the list mutably, so we can
897 // access the `next` field.
898 let mut next = unsafe { (*self.next).next };
899
900 if next == self.list.first {
901 next = core::ptr::null_mut();
902 }
903
904 // INVARIANT: `next` is either null or the next element after an element in the list.
905 self.next = next;
906 true
907 }
908
909 /// Move the cursor one element backwards.
910 ///
911 /// If the cursor is before the first element, then this call does nothing. This call returns
912 /// `true` if the cursor's position was changed.
913 pub fn move_prev(&mut self) -> bool {
914 if self.next == self.list.first {
915 return false;
916 }
917
918 // INVARIANT: `prev_ptr()` always returns a pointer that is null or in the list.
919 self.next = self.prev_ptr();
920 true
921 }
922
923 /// Inserts an element where the cursor is pointing and get a pointer to the new element.
924 fn insert_inner(&mut self, item: ListArc<T, ID>) -> *mut ListLinksFields {
925 let ptr = if self.next.is_null() {
926 self.list.first
927 } else {
928 self.next
929 };
930 // SAFETY:
931 // * `ptr` is an element in the list or null.
932 // * if `ptr` is null, then `self.list.first` is null so the list is empty.
933 let item = unsafe { self.list.insert_inner(item, ptr) };
934 if self.next == self.list.first {
935 // INVARIANT: We just inserted `item`, so it's a member of list.
936 self.list.first = item;
937 }
938 item
939 }
940
941 /// Insert an element at this cursor's location.
942 pub fn insert(mut self, item: ListArc<T, ID>) {
943 // This is identical to `insert_prev`, but consumes the cursor. This is helpful because it
944 // reduces confusion when the last operation on the cursor is an insertion; in that case,
945 // you just want to insert the element at the cursor, and it is confusing that the call
946 // involves the word prev or next.
947 self.insert_inner(item);
948 }
949
950 /// Inserts an element after this cursor.
951 ///
952 /// After insertion, the new element will be after the cursor.
953 pub fn insert_next(&mut self, item: ListArc<T, ID>) {
954 self.next = self.insert_inner(item);
955 }
956
957 /// Inserts an element before this cursor.
958 ///
959 /// After insertion, the new element will be before the cursor.
960 pub fn insert_prev(&mut self, item: ListArc<T, ID>) {
961 self.insert_inner(item);
962 }
963
964 /// Remove the next element from the list.
965 pub fn remove_next(&mut self) -> Option<ListArc<T, ID>> {
966 self.peek_next().map(|v| v.remove())
967 }
968
969 /// Remove the previous element from the list.
970 pub fn remove_prev(&mut self) -> Option<ListArc<T, ID>> {
971 self.peek_prev().map(|v| v.remove())
972 }
973}
974
975/// References the element in the list next to the cursor.
976///
977/// # Invariants
978///
979/// * `ptr` is an element in `self.cursor.list`.
980/// * `ISNEXT == (self.ptr == self.cursor.next)`.
981pub struct CursorPeek<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> {
982 cursor: &'a mut Cursor<'b, T, ID>,
983 ptr: *mut ListLinksFields,
984}
985
986impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64>
987 CursorPeek<'a, 'b, T, ISNEXT, ID>
988{
989 /// Remove the element from the list.
990 pub fn remove(self) -> ListArc<T, ID> {
991 if ISNEXT {
992 self.cursor.move_next();
993 }
994
995 // INVARIANT: `self.ptr` is not equal to `self.cursor.next` due to the above `move_next`
996 // call.
997 // SAFETY: By the type invariants of `Self`, `next` is not null, so `next` is an element of
998 // `self.cursor.list` by the type invariants of `Cursor`.
999 unsafe { self.cursor.list.remove_internal(self.ptr) }
1000 }
1001
1002 /// Access this value as an [`ArcBorrow`].
1003 pub fn arc(&self) -> ArcBorrow<'_, T> {
1004 // SAFETY: `self.ptr` points at an element in `self.cursor.list`.
1005 let me = unsafe { T::view_value(ListLinks::from_fields(self.ptr)) };
1006 // SAFETY:
1007 // * All values in a list are stored in an `Arc`.
1008 // * The value cannot be removed from the list for the duration of the lifetime annotated
1009 // on the returned `ArcBorrow`, because removing it from the list would require mutable
1010 // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `ArcBorrow` holds
1011 // an immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the
1012 // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable
1013 // access requires first releasing the immutable borrow on the `CursorPeek`.
1014 // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc`
1015 // reference, and `UniqueArc` references must be unique.
1016 unsafe { ArcBorrow::from_raw(me) }
1017 }
1018}
1019
1020impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> core::ops::Deref
1021 for CursorPeek<'a, 'b, T, ISNEXT, ID>
1022{
1023 // If you change the `ptr` field to have type `ArcBorrow<'a, T>`, it might seem like you could
1024 // get rid of the `CursorPeek::arc` method and change the deref target to `ArcBorrow<'a, T>`.
1025 // However, that doesn't work because 'a is too long. You could obtain an `ArcBorrow<'a, T>`
1026 // and then call `CursorPeek::remove` without giving up the `ArcBorrow<'a, T>`, which would be
1027 // unsound.
1028 type Target = T;
1029
1030 fn deref(&self) -> &T {
1031 // SAFETY: `self.ptr` points at an element in `self.cursor.list`.
1032 let me = unsafe { T::view_value(ListLinks::from_fields(self.ptr)) };
1033
1034 // SAFETY: The value cannot be removed from the list for the duration of the lifetime
1035 // annotated on the returned `&T`, because removing it from the list would require mutable
1036 // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `&T` holds an
1037 // immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the
1038 // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable access
1039 // requires first releasing the immutable borrow on the `CursorPeek`.
1040 unsafe { &*me }
1041 }
1042}
1043
1044impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for Iter<'a, T, ID> {}
1045
1046impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for &'a List<T, ID> {
1047 type IntoIter = Iter<'a, T, ID>;
1048 type Item = ArcBorrow<'a, T>;
1049
1050 fn into_iter(self) -> Iter<'a, T, ID> {
1051 self.iter()
1052 }
1053}
1054
1055/// An owning iterator into a [`List`].
1056pub struct IntoIter<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
1057 list: List<T, ID>,
1058}
1059
1060impl<T: ?Sized + ListItem<ID>, const ID: u64> Iterator for IntoIter<T, ID> {
1061 type Item = ListArc<T, ID>;
1062
1063 fn next(&mut self) -> Option<ListArc<T, ID>> {
1064 self.list.pop_front()
1065 }
1066}
1067
1068impl<T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for IntoIter<T, ID> {}
1069
1070impl<T: ?Sized + ListItem<ID>, const ID: u64> DoubleEndedIterator for IntoIter<T, ID> {
1071 fn next_back(&mut self) -> Option<ListArc<T, ID>> {
1072 self.list.pop_back()
1073 }
1074}
1075
1076impl<T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for List<T, ID> {
1077 type IntoIter = IntoIter<T, ID>;
1078 type Item = ListArc<T, ID>;
1079
1080 fn into_iter(self) -> IntoIter<T, ID> {
1081 IntoIter { list: self }
1082 }
1083}