Lines Matching refs: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::*;
67 /// // Create a new empty list.
68 /// let mut list = List::new();
70 /// assert!(list.is_empty());
74 /// list.push_back(BasicItem::new(15)?);
75 /// list.push_back(BasicItem::new(10)?);
76 /// list.push_back(BasicItem::new(30)?);
78 /// // Iterate over the list to verify the nodes were inserted correctly.
81 /// let mut iter = list.iter();
87 /// // Verify the length of the list.
88 /// assert_eq!(list.iter().count(), 3);
91 /// // Pop the items from the list using `pop_back()` and verify the content.
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);
99 /// list.push_front(BasicItem::new(15)?);
100 /// list.push_front(BasicItem::new(10)?);
101 /// list.push_front(BasicItem::new(30)?);
103 /// // Iterate over the list to verify the nodes were inserted correctly.
106 /// let mut iter = list.iter();
112 /// // Verify the length of the list.
113 /// assert_eq!(list.iter().count(), 3);
116 /// // Pop the items from the list using `pop_front()` and verify the content.
118 /// assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 30);
119 /// assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 10);
122 /// // Push `list2` to `list` through `push_all_back()`.
123 /// // list: [15]
130 /// list.push_all_back(&mut list2);
132 /// // list: [15, 25, 35]
134 /// let mut iter = list.iter();
191 /// Can only be used when the value is in a list.
245 /// The prev/next pointers for an item in a linked list.
249 /// The fields are null if and only if this item is not in a list.
253 // list.
347 /// Creates a new empty list.
355 /// Returns whether this list is empty.
362 /// Returns a pointer to the newly inserted element. Never changes `self.first` unless the list
367 /// * `next` must be an element in this list or null.
368 /// * if `next` is null, then the list must be empty.
380 // * Removing items from this list is always done using `remove_internal_inner`, which
386 // Check if the list is empty.
389 // INVARIANT: A linked list with one item should be cyclic.
399 // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
413 /// Add the provided item to the back of the list.
416 // * `self.first` is null or in the list.
417 // * `self.first` is only null if the list is empty.
421 /// Add the provided item to the front of the list.
424 // * `self.first` is null or in the list.
425 // * `self.first` is only null if the list is empty.
428 // INVARIANT: `new_elem` is in the list because we just inserted it.
432 /// Removes the last item from this list.
438 // SAFETY: We just checked that the list is not empty.
440 // SAFETY: The last item of this list is in this list.
444 /// Removes the first item from this list.
450 // SAFETY: The first item of this list is in this list.
454 /// Removes the provided item from this list and returns it.
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.)
461 /// `item` must not be in a different linked list (with the same id).
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.
480 // This ensures that the list is valid under the more restrictive strict provenance
484 // list invariants.
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.
498 /// Removes the provided item from the list.
502 /// `item` must point at an item in this list.
505 // since we have a mutable reference to the list containing `item`.
511 /// Removes the provided item from the list.
515 /// The `item` pointer must point at an item in this list, and we must have `(*item).next ==
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.
527 // * If the list has at least three items, then after removing the item, `prev` and `next`
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.
536 // SAFETY: We have exclusive access to items in the list.
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
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.
557 // SAFETY: `item` used to be in the list, so it is dereferenceable by the type invariants
560 // SAFETY: Any pointer in the list originates from a `prepare_to_insert` call.
577 // SAFETY: The other list is not empty, so this pointer is valid.
580 // SAFETY: The self list is not empty, so this pointer is valid.
594 // INVARIANT: The other list is now empty, so update its pointer.
598 /// Returns a cursor that points before the first element of the list.
600 // INVARIANT: `self.first` is in this list.
603 list: self,
607 /// Returns a cursor that points after the last element in the list.
612 list: self,
616 /// Creates an iterator over the list.
618 // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point
619 // at the first element of the same list.
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.
669 // INVARIANT: If `current` was the last element of the list, then this updates it to null.
677 // SAFETY: The `current` pointer points at a value in the list.
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.
692 /// A cursor always rests between two elements in the list. This means that a cursor has a previous
694 /// into an empty list.
700 /// use kernel::list::{List, ListArc, ListLinks};
718 /// kernel::list::impl_list_arc_safe! {
721 /// kernel::list::impl_list_item! {
726 /// fn remove_first(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
727 /// let mut cursor = list.cursor_front();
738 /// fn remove_last(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
739 /// let mut cursor = list.cursor_back();
750 /// // a new list.
751 /// fn remove_all(list: &mut List<ListItem>, value: u32) -> List<ListItem> {
753 /// let mut cursor = list.cursor_front();
766 /// fn insert_at(list: &mut List<ListItem>, new: ListArc<ListItem>, idx: usize) -> Result {
767 /// let mut cursor = list.cursor_front();
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();
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);
800 /// assert!(remove_first(&mut list, 14).is_some());
802 /// insert_at(&mut list, ListItem::new(12)?, 2)?;
804 /// assert!(remove_last(&mut list, 15).is_some());
810 /// merge_sorted(&mut list, list2);
812 /// let mut items = list.into_iter();
824 /// The `next` pointer is null or points a value in `list`.
826 list: &'a mut List<T, ID>,
837 let first = self.list.first;
851 // list, so we can access its `prev` pointer.
862 // * We just checked that `self.next` is non-null, so it must be in `self.list`.
879 // * We just checked that `prev` is non-null, so it must be in `self.list`.
896 // SAFETY: `self.next` is an element in the list and we borrow the list mutably, so we can
900 if next == self.list.first {
904 // INVARIANT: `next` is either null or the next element after an element in the list.
914 if self.next == self.list.first {
918 // INVARIANT: `prev_ptr()` always returns a pointer that is null or in the list.
926 self.list.first
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;
964 /// Remove the next element from the list.
969 /// Remove the previous element from the list.
975 /// References the element in the list next to the cursor.
979 /// * `ptr` is an element in `self.cursor.list`.
989 /// Remove the element from the list.
998 // `self.cursor.list` by the type invariants of `Cursor`.
999 unsafe { self.cursor.list.remove_internal(self.ptr) }
1004 // SAFETY: `self.ptr` points at an element in `self.cursor.list`.
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
1014 // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc`
1031 // SAFETY: `self.ptr` points at an element in `self.cursor.list`.
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
1057 list: List<T, ID>,
1064 self.list.pop_front()
1072 self.list.pop_back()
1081 IntoIter { list: self }