Lines Matching full:list
5 //! A linked list implementation.
25 /// A linked list.
27 /// All elements in this linked list will be [`ListArc`] references to the value. Since a value can
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
42 /// use kernel::list::*;
70 /// // Create a new empty list.
71 /// let mut list = List::new();
73 /// assert!(list.is_empty());
77 /// list.push_back(BasicItem::new(15)?);
78 /// list.push_back(BasicItem::new(10)?);
79 /// list.push_back(BasicItem::new(30)?);
81 /// // Iterate over the list to verify the nodes were inserted correctly.
84 /// let mut iter = list.iter();
90 /// // Verify the length of the list.
91 /// assert_eq!(list.iter().count(), 3);
94 /// // Pop the items from the list using `pop_back()` and verify the content.
96 /// assert_eq!(list.pop_back().unwrap().value, 30);
97 /// assert_eq!(list.pop_back().unwrap().value, 10);
98 /// assert_eq!(list.pop_back().unwrap().value, 15);
102 /// list.push_front(BasicItem::new(15)?);
103 /// list.push_front(BasicItem::new(10)?);
104 /// list.push_front(BasicItem::new(30)?);
106 /// // Iterate over the list to verify the nodes were inserted correctly.
109 /// let mut iter = list.iter();
115 /// // Verify the length of the list.
116 /// assert_eq!(list.iter().count(), 3);
119 /// // Pop the items from the list using `pop_front()` and verify the content.
121 /// assert_eq!(list.pop_front().unwrap().value, 30);
122 /// assert_eq!(list.pop_front().unwrap().value, 10);
125 /// // Push `list2` to `list` through `push_all_back()`.
126 /// // list: [15]
129 /// let mut list2 = List::new();
133 /// list.push_all_back(&mut list2);
135 /// // list: [15, 25, 35]
137 /// let mut iter = list.iter();
146 pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> { struct
153 unsafe impl<T, const ID: u64> Send for List<T, ID> implementation
161 unsafe impl<T, const ID: u64> Sync for List<T, ID> implementation
168 /// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`].
194 /// Can only be used when the value is in a list.
210 /// This is called when an item is inserted into a [`List`].
248 /// The prev/next pointers for an item in a linked list.
252 /// The fields are null if and only if this item is not in a list.
256 // list.
342 impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> { implementation
343 /// Creates a new empty list.
351 /// Returns whether this list is empty.
358 /// Returns a pointer to the newly inserted element. Never changes `self.first` unless the list
363 /// * `next` must be an element in this list or null.
364 /// * if `next` is null, then the list must be empty.
376 // * Removing items from this list is always done using `remove_internal_inner`, which in insert_inner()
382 // Check if the list is empty. in insert_inner()
385 // INVARIANT: A linked list with one item should be cyclic. in insert_inner()
395 // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us in insert_inner()
409 /// Add the provided item to the back of the list.
412 // * `self.first` is null or in the list. in push_back()
413 // * `self.first` is only null if the list is empty. in push_back()
417 /// Add the provided item to the front of the list.
420 // * `self.first` is null or in the list. in push_front()
421 // * `self.first` is only null if the list is empty. in push_front()
424 // INVARIANT: `new_elem` is in the list because we just inserted it. in push_front()
428 /// Removes the last item from this list.
434 // SAFETY: We just checked that the list is not empty. in pop_back()
436 // SAFETY: The last item of this list is in this list. in pop_back()
440 /// Removes the first item from this list.
446 // SAFETY: The first item of this list is in this list. in pop_front()
450 /// Removes the provided item from this list and returns it.
452 /// This returns `None` if the item is not in the list. (Note that by the safety requirements,
453 /// this means that the item is not in any list.)
457 /// `item` must not be in a different linked list (with the same id).
465 // * If `item` is not in any list, then these fields are read-only and null. in remove()
466 // * If `item` is in this list, then we have exclusive access to these fields since we in remove()
467 // have a mutable reference to the list. in remove()
476 // This ensures that the list is valid under the more restrictive strict provenance in remove()
480 // list invariants. in remove()
486 // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it in remove()
487 // is in this list. The pointers are in the right order. in remove()
494 /// Removes the provided item from the list.
498 /// `item` must point at an item in this list.
501 // since we have a mutable reference to the list containing `item`. in remove_internal()
507 /// Removes the provided item from the list.
511 /// The `item` pointer must point at an item in this list, and we must have `(*item).next ==
519 // SAFETY: We have exclusive access to the pointers of items in the list, and the prev/next in remove_internal_inner()
520 // pointers are always valid for items in a list. in remove_internal_inner()
523 // * If the list has at least three items, then after removing the item, `prev` and `next` in remove_internal_inner()
525 // * If the list has two items, then the remaining item will point at itself. in remove_internal_inner()
526 // * If the list has one item, then `next == prev == item`, so these writes have no in remove_internal_inner()
527 // effect. The list remains unchanged and `item` is still in the list for now. in remove_internal_inner()
532 // SAFETY: We have exclusive access to items in the list. in remove_internal_inner()
543 // * If `item` was the only item in the list, then `prev == item`, and we just set in remove_internal_inner()
544 // `item->next` to null, so this correctly sets `first` to null now that the list is in remove_internal_inner()
548 // list, so it must be valid. There is no race since `prev` is still in the list and we in remove_internal_inner()
549 // still have exclusive access to the list. in remove_internal_inner()
553 // SAFETY: `item` used to be in the list, so it is dereferenceable by the type invariants in remove_internal_inner()
554 // of `List`. in remove_internal_inner()
556 // SAFETY: Any pointer in the list originates from a `prepare_to_insert` call. in remove_internal_inner()
566 pub fn push_all_back(&mut self, other: &mut List<T, ID>) { in push_all_back()
573 // SAFETY: The other list is not empty, so this pointer is valid. in push_all_back()
576 // SAFETY: The self list is not empty, so this pointer is valid. in push_all_back()
590 // INVARIANT: The other list is now empty, so update its pointer. in push_all_back()
594 /// Returns a cursor that points before the first element of the list.
596 // INVARIANT: `self.first` is in this list. in cursor_front()
599 list: self, in cursor_front()
603 /// Returns a cursor that points after the last element in the list.
608 list: self, in cursor_back()
612 /// Creates an iterator over the list.
614 // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point in iter()
615 // at the first element of the same list. in iter()
624 impl<T: ?Sized + ListItem<ID>, const ID: u64> Default for List<T, ID> { implementation
626 List::new() in default()
630 impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> { implementation
638 /// An iterator over a [`List`].
642 /// * There must be a [`List`] that is immutably borrowed for the duration of `'a`.
643 /// * The `current` pointer is null or points at a value in that [`List`].
644 /// * The `stop` pointer is equal to the `first` field of that [`List`].
662 // SAFETY: We just checked that `current` is not null, so it is in a list, and hence not in next()
663 // dangling. There's no race because the iterator holds an immutable borrow to the list. in next()
665 // INVARIANT: If `current` was the last element of the list, then this updates it to null. in next()
673 // SAFETY: The `current` pointer points at a value in the list. in next()
676 // * All values in a list are stored in an `Arc`. in next()
677 // * The value cannot be removed from the list for the duration of the lifetime annotated in next()
678 // on the returned `ArcBorrow`, because removing it from the list would require mutable in next()
679 // access to the list. However, the `ArcBorrow` is annotated with the iterator's in next()
680 // lifetime, and the list is immutably borrowed for that lifetime. in next()
681 // * Values in a list never have a `UniqueArc` reference. in next()
686 /// A cursor into a [`List`].
688 /// A cursor always rests between two elements in the list. This means that a cursor has a previous
690 /// into an empty list.
696 /// use kernel::list::{List, ListArc, ListLinks};
714 /// kernel::list::impl_has_list_links! {
717 /// kernel::list::impl_list_arc_safe! {
720 /// kernel::list::impl_list_item! {
725 /// fn remove_first(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
726 /// let mut cursor = list.cursor_front();
737 /// fn remove_last(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
738 /// let mut cursor = list.cursor_back();
749 /// // a new list.
750 /// fn remove_all(list: &mut List<ListItem>, value: u32) -> List<ListItem> {
751 /// let mut out = List::new();
752 /// let mut cursor = list.cursor_front();
765 /// fn insert_at(list: &mut List<ListItem>, new: ListArc<ListItem>, idx: usize) -> Result {
766 /// let mut cursor = list.cursor_front();
776 /// // Merge two sorted lists into a single sorted list.
777 /// fn merge_sorted(list: &mut List<ListItem>, merge: List<ListItem>) {
778 /// let mut cursor = list.cursor_front();
790 /// let mut list = List::new();
791 /// list.push_back(ListItem::new(14)?);
792 /// list.push_back(ListItem::new(12)?);
793 /// list.push_back(ListItem::new(10)?);
794 /// list.push_back(ListItem::new(12)?);
795 /// list.push_back(ListItem::new(15)?);
796 /// list.push_back(ListItem::new(14)?);
797 /// assert_eq!(remove_all(&mut list, 12).iter().count(), 2);
799 /// assert!(remove_first(&mut list, 14).is_some());
801 /// insert_at(&mut list, ListItem::new(12)?, 2)?;
803 /// assert!(remove_last(&mut list, 15).is_some());
806 /// let mut list2 = List::new();
809 /// merge_sorted(&mut list, list2);
811 /// let mut items = list.into_iter();
823 /// The `next` pointer is null or points a value in `list`.
825 list: &'a mut List<T, ID>, field
836 let first = self.list.first; in prev_ptr()
850 // list, so we can access its `prev` pointer. in prev_ptr()
861 // * We just checked that `self.next` is non-null, so it must be in `self.list`. in peek_next()
878 // * We just checked that `prev` is non-null, so it must be in `self.list`. in peek_prev()
895 // SAFETY: `self.next` is an element in the list and we borrow the list mutably, so we can in move_next()
899 if next == self.list.first { in move_next()
903 // INVARIANT: `next` is either null or the next element after an element in the list. in move_next()
913 if self.next == self.list.first { in move_prev()
917 // INVARIANT: `prev_ptr()` always returns a pointer that is null or in the list. in move_prev()
925 self.list.first in insert_inner()
930 // * `ptr` is an element in the list or null. in insert_inner()
931 // * if `ptr` is null, then `self.list.first` is null so the list is empty. in insert_inner()
932 let item = unsafe { self.list.insert_inner(item, ptr) }; in insert_inner()
933 if self.next == self.list.first { in insert_inner()
934 // INVARIANT: We just inserted `item`, so it's a member of list. in insert_inner()
935 self.list.first = item; in insert_inner()
963 /// Remove the next element from the list.
968 /// Remove the previous element from the list.
974 /// References the element in the list next to the cursor.
978 /// * `ptr` is an element in `self.cursor.list`.
988 /// Remove the element from the list.
997 // `self.cursor.list` by the type invariants of `Cursor`. in remove()
998 unsafe { self.cursor.list.remove_internal(self.ptr) } in remove()
1003 // SAFETY: `self.ptr` points at an element in `self.cursor.list`. in arc()
1006 // * All values in a list are stored in an `Arc`. in arc()
1007 // * The value cannot be removed from the list for the duration of the lifetime annotated in arc()
1008 // on the returned `ArcBorrow`, because removing it from the list would require mutable in arc()
1009 // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `ArcBorrow` holds in arc()
1011 // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable in arc()
1013 // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc` in arc()
1030 // SAFETY: `self.ptr` points at an element in `self.cursor.list`. in deref()
1033 // SAFETY: The value cannot be removed from the list for the duration of the lifetime in deref()
1034 // annotated on the returned `&T`, because removing it from the list would require mutable in deref()
1035 // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `&T` holds an in deref()
1037 // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable access in deref()
1045 impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for &'a List<T, ID> { implementation
1054 /// An owning iterator into a [`List`].
1056 list: List<T, ID>, field
1063 self.list.pop_front() in next()
1071 self.list.pop_back() in next_back()
1075 impl<T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for List<T, ID> { implementation
1080 IntoIter { list: self } in into_iter()