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
44 /// use kernel::list::*;
69 /// // Create a new empty list.
70 /// let mut list = List::new();
72 /// assert!(list.is_empty());
76 /// list.push_back(BasicItem::new(15)?);
77 /// list.push_back(BasicItem::new(10)?);
78 /// list.push_back(BasicItem::new(30)?);
80 /// // Iterate over the list to verify the nodes were inserted correctly.
83 /// let mut iter = list.iter();
89 /// // Verify the length of the list.
90 /// assert_eq!(list.iter().count(), 3);
93 /// // Pop the items from the list using `pop_back()` and verify the content.
95 /// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 30);
96 /// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 10);
97 /// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 15);
101 /// list.push_front(BasicItem::new(15)?);
102 /// list.push_front(BasicItem::new(10)?);
103 /// list.push_front(BasicItem::new(30)?);
105 /// // Iterate over the list to verify the nodes were inserted correctly.
108 /// let mut iter = list.iter();
114 /// // Verify the length of the list.
115 /// assert_eq!(list.iter().count(), 3);
118 /// // Pop the items from the list using `pop_front()` and verify the content.
120 /// assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 30);
121 /// assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 10);
124 /// // Push `list2` to `list` through `push_all_back()`.
125 /// // list: [15]
128 /// let mut list2 = List::new();
132 /// list.push_all_back(&mut list2);
134 /// // list: [15, 25, 35]
136 /// let mut iter = list.iter();
146 /// Use [`ListLinksSelfPtr`] as the type of the intrusive field. This allows a list of trait object
150 /// use kernel::list::*;
179 /// // Create a new empty list.
180 /// let mut list = List::<DTWrap<dyn Foo>>::new();
182 /// assert!(list.is_empty());
194 /// list.push_back(DTWrap::new(A(15))?);
195 /// list.push_back(DTWrap::new(A(32))?);
196 /// list.push_back(DTWrap::new(B)?);
198 /// // Iterate over the list to verify the nodes were inserted correctly.
201 /// let mut iter = list.iter();
207 /// // Verify the length of the list.
208 /// assert_eq!(list.iter().count(), 3);
211 /// // Pop the items from the list using `pop_back()` and verify the content.
213 /// assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("b", 42));
214 /// assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 32));
215 /// assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 15));
219 /// list.push_front(DTWrap::new(A(15))?);
220 /// list.push_front(DTWrap::new(A(32))?);
221 /// list.push_front(DTWrap::new(B)?);
223 /// // Iterate over the list to verify the nodes were inserted correctly.
226 /// let mut iter = list.iter();
232 /// // Verify the length of the list.
233 /// assert_eq!(list.iter().count(), 3);
236 /// // Pop the items from the list using `pop_front()` and verify the content.
238 /// assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 15));
239 /// assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 32));
242 /// // Push `list2` to `list` through `push_all_back()`.
243 /// // list: [B]
246 /// let mut list2 = List::<DTWrap<dyn Foo>>::new();
250 /// list.push_all_back(&mut list2);
252 /// // list: [B, B, A(25)]
254 /// let mut iter = list.iter();
263 pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> { struct
270 unsafe impl<T, const ID: u64> Send for List<T, ID> implementation
278 unsafe impl<T, const ID: u64> Sync for List<T, ID> implementation
285 /// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`].
311 /// Can only be used when the value is in a list.
327 /// This is called when an item is inserted into a [`List`].
365 /// The prev/next pointers for an item in a linked list.
369 /// The fields are null if and only if this item is not in a list.
373 // list.
466 impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> { implementation
467 /// Creates a new empty list.
475 /// Returns whether this list is empty.
482 /// Returns a pointer to the newly inserted element. Never changes `self.first` unless the list
487 /// * `next` must be an element in this list or null.
488 /// * if `next` is null, then the list must be empty.
500 // * Removing items from this list is always done using `remove_internal_inner`, which in insert_inner()
506 // Check if the list is empty. in insert_inner()
509 // INVARIANT: A linked list with one item should be cyclic. in insert_inner()
519 // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us in insert_inner()
533 /// Add the provided item to the back of the list.
536 // * `self.first` is null or in the list. in push_back()
537 // * `self.first` is only null if the list is empty. in push_back()
541 /// Add the provided item to the front of the list.
544 // * `self.first` is null or in the list. in push_front()
545 // * `self.first` is only null if the list is empty. in push_front()
548 // INVARIANT: `new_elem` is in the list because we just inserted it. in push_front()
552 /// Removes the last item from this list.
558 // SAFETY: We just checked that the list is not empty. in pop_back()
560 // SAFETY: The last item of this list is in this list. in pop_back()
564 /// Removes the first item from this list.
570 // SAFETY: The first item of this list is in this list. in pop_front()
574 /// Removes the provided item from this list and returns it.
576 /// This returns `None` if the item is not in the list. (Note that by the safety requirements,
577 /// this means that the item is not in any list.)
579 /// When using this method, be careful with using `mem::take` on the same list as that may
584 /// `item` must not be in a different linked list (with the same id).
592 // * If `item` is not in any list, then these fields are read-only and null. in remove()
593 // * If `item` is in this list, then we have exclusive access to these fields since we in remove()
594 // have a mutable reference to the list. in remove()
603 // This ensures that the list is valid under the more restrictive strict provenance in remove()
607 // list invariants. in remove()
613 // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it in remove()
614 // is in this list. The pointers are in the right order. in remove()
621 /// Removes the provided item from the list.
625 /// `item` must point at an item in this list.
628 // since we have a mutable reference to the list containing `item`. in remove_internal()
634 /// Removes the provided item from the list.
638 /// The `item` pointer must point at an item in this list, and we must have `(*item).next ==
646 // SAFETY: We have exclusive access to the pointers of items in the list, and the prev/next in remove_internal_inner()
647 // pointers are always valid for items in a list. in remove_internal_inner()
650 // * If the list has at least three items, then after removing the item, `prev` and `next` in remove_internal_inner()
652 // * If the list has two items, then the remaining item will point at itself. in remove_internal_inner()
653 // * If the list has one item, then `next == prev == item`, so these writes have no in remove_internal_inner()
654 // effect. The list remains unchanged and `item` is still in the list for now. in remove_internal_inner()
659 // SAFETY: We have exclusive access to items in the list. in remove_internal_inner()
670 // * If `item` was the only item in the list, then `prev == item`, and we just set in remove_internal_inner()
671 // `item->next` to null, so this correctly sets `first` to null now that the list is in remove_internal_inner()
675 // list, so it must be valid. There is no race since `prev` is still in the list and we in remove_internal_inner()
676 // still have exclusive access to the list. in remove_internal_inner()
680 // SAFETY: `item` used to be in the list, so it is dereferenceable by the type invariants in remove_internal_inner()
681 // of `List`. in remove_internal_inner()
683 // SAFETY: Any pointer in the list originates from a `prepare_to_insert` call. in remove_internal_inner()
693 pub fn push_all_back(&mut self, other: &mut List<T, ID>) { in push_all_back()
700 // SAFETY: The other list is not empty, so this pointer is valid. in push_all_back()
703 // SAFETY: The self list is not empty, so this pointer is valid. in push_all_back()
717 // INVARIANT: The other list is now empty, so update its pointer. in push_all_back()
721 /// Returns a cursor that points before the first element of the list.
723 // INVARIANT: `self.first` is in this list. in cursor_front()
726 list: self, in cursor_front()
730 /// Returns a cursor that points after the last element in the list.
735 list: self, in cursor_back()
739 /// Creates an iterator over the list.
741 // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point in iter()
742 // at the first element of the same list. in iter()
751 impl<T: ?Sized + ListItem<ID>, const ID: u64> Default for List<T, ID> { implementation
753 List::new() in default()
757 impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> { implementation
765 /// An iterator over a [`List`].
769 /// * There must be a [`List`] that is immutably borrowed for the duration of `'a`.
770 /// * The `current` pointer is null or points at a value in that [`List`].
771 /// * The `stop` pointer is equal to the `first` field of that [`List`].
789 // SAFETY: We just checked that `current` is not null, so it is in a list, and hence not in next()
790 // dangling. There's no race because the iterator holds an immutable borrow to the list. in next()
792 // INVARIANT: If `current` was the last element of the list, then this updates it to null. in next()
800 // SAFETY: The `current` pointer points at a value in the list. in next()
803 // * All values in a list are stored in an `Arc`. in next()
804 // * The value cannot be removed from the list for the duration of the lifetime annotated in next()
805 // on the returned `ArcBorrow`, because removing it from the list would require mutable in next()
806 // access to the list. However, the `ArcBorrow` is annotated with the iterator's in next()
807 // lifetime, and the list is immutably borrowed for that lifetime. in next()
808 // * Values in a list never have a `UniqueArc` reference. in next()
813 /// A cursor into a [`List`].
815 /// A cursor always rests between two elements in the list. This means that a cursor has a previous
817 /// into an empty list.
823 /// use kernel::list::{List, ListArc, ListLinks};
841 /// kernel::list::impl_list_arc_safe! {
844 /// kernel::list::impl_list_item! {
849 /// fn remove_first(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
850 /// let mut cursor = list.cursor_front();
861 /// fn remove_last(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
862 /// let mut cursor = list.cursor_back();
873 /// // a new list.
874 /// fn remove_all(list: &mut List<ListItem>, value: u32) -> List<ListItem> {
875 /// let mut out = List::new();
876 /// let mut cursor = list.cursor_front();
889 /// fn insert_at(list: &mut List<ListItem>, new: ListArc<ListItem>, idx: usize) -> Result {
890 /// let mut cursor = list.cursor_front();
900 /// // Merge two sorted lists into a single sorted list.
901 /// fn merge_sorted(list: &mut List<ListItem>, merge: List<ListItem>) {
902 /// let mut cursor = list.cursor_front();
914 /// let mut list = List::new();
915 /// list.push_back(ListItem::new(14)?);
916 /// list.push_back(ListItem::new(12)?);
917 /// list.push_back(ListItem::new(10)?);
918 /// list.push_back(ListItem::new(12)?);
919 /// list.push_back(ListItem::new(15)?);
920 /// list.push_back(ListItem::new(14)?);
921 /// assert_eq!(remove_all(&mut list, 12).iter().count(), 2);
923 /// assert!(remove_first(&mut list, 14).is_some());
925 /// insert_at(&mut list, ListItem::new(12)?, 2)?;
927 /// assert!(remove_last(&mut list, 15).is_some());
930 /// let mut list2 = List::new();
933 /// merge_sorted(&mut list, list2);
935 /// let mut items = list.into_iter();
947 /// The `next` pointer is null or points a value in `list`.
949 list: &'a mut List<T, ID>, field
960 let first = self.list.first; in prev_ptr()
974 // list, so we can access its `prev` pointer. in prev_ptr()
985 // * We just checked that `self.next` is non-null, so it must be in `self.list`. in peek_next()
1002 // * We just checked that `prev` is non-null, so it must be in `self.list`. in peek_prev()
1019 // SAFETY: `self.next` is an element in the list and we borrow the list mutably, so we can in move_next()
1023 if next == self.list.first { in move_next()
1027 // INVARIANT: `next` is either null or the next element after an element in the list. in move_next()
1037 if self.next == self.list.first { in move_prev()
1041 // INVARIANT: `prev_ptr()` always returns a pointer that is null or in the list. in move_prev()
1049 self.list.first in insert_inner()
1054 // * `ptr` is an element in the list or null. in insert_inner()
1055 // * if `ptr` is null, then `self.list.first` is null so the list is empty. in insert_inner()
1056 let item = unsafe { self.list.insert_inner(item, ptr) }; in insert_inner()
1057 if self.next == self.list.first { in insert_inner()
1058 // INVARIANT: We just inserted `item`, so it's a member of list. in insert_inner()
1059 self.list.first = item; in insert_inner()
1087 /// Remove the next element from the list.
1092 /// Remove the previous element from the list.
1098 /// References the element in the list next to the cursor.
1102 /// * `ptr` is an element in `self.cursor.list`.
1112 /// Remove the element from the list.
1121 // `self.cursor.list` by the type invariants of `Cursor`. in remove()
1122 unsafe { self.cursor.list.remove_internal(self.ptr) } in remove()
1127 // SAFETY: `self.ptr` points at an element in `self.cursor.list`. in arc()
1130 // * All values in a list are stored in an `Arc`. in arc()
1131 // * The value cannot be removed from the list for the duration of the lifetime annotated in arc()
1132 // on the returned `ArcBorrow`, because removing it from the list would require mutable in arc()
1133 // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `ArcBorrow` holds in arc()
1135 // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable in arc()
1137 // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc` in arc()
1154 // SAFETY: `self.ptr` points at an element in `self.cursor.list`. in deref()
1157 // SAFETY: The value cannot be removed from the list for the duration of the lifetime in deref()
1158 // annotated on the returned `&T`, because removing it from the list would require mutable in deref()
1159 // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `&T` holds an in deref()
1161 // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable access in deref()
1169 impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for &'a List<T, ID> { implementation
1178 /// An owning iterator into a [`List`].
1180 list: List<T, ID>, field
1187 self.list.pop_front() in next()
1195 self.list.pop_back() in next_back()
1199 impl<T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for List<T, ID> { implementation
1204 IntoIter { list: self } in into_iter()