Lines Matching full:list
5 //! A linked list implementation.
28 /// A linked list.
30 /// All elements in this linked list will be [`ListArc`] references to the value. Since a value can
36 /// * If the list is empty, then `first` is null. Otherwise, `first` points at the `ListLinks`
37 /// field of the first element in the list.
38 /// * All prev/next pointers in `ListLinks` fields of items in the list are valid and form a cycle.
39 /// * For every item in the list, the list owns the associated [`ListArc`] reference and has
41 pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> { struct
48 unsafe impl<T, const ID: u64> Send for List<T, ID> implementation
56 unsafe impl<T, const ID: u64> Sync for List<T, ID> implementation
63 /// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`].
89 /// Can only be used when the value is in a list.
105 /// This is called when an item is inserted into a [`List`].
143 /// The prev/next pointers for an item in a linked list.
147 /// The fields are null if and only if this item is not in a list.
151 // list.
237 impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> { implementation
238 /// Creates a new empty list.
246 /// Returns whether this list is empty.
253 /// Returns a pointer to the newly inserted element. Never changes `self.first` unless the list
258 /// * `next` must be an element in this list or null.
259 /// * if `next` is null, then the list must be empty.
271 // * Removing items from this list is always done using `remove_internal_inner`, which in insert_inner()
277 // Check if the list is empty. in insert_inner()
280 // INVARIANT: A linked list with one item should be cyclic. in insert_inner()
290 // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us in insert_inner()
304 /// Add the provided item to the back of the list.
307 // * `self.first` is null or in the list. in push_back()
308 // * `self.first` is only null if the list is empty. in push_back()
312 /// Add the provided item to the front of the list.
315 // * `self.first` is null or in the list. in push_front()
316 // * `self.first` is only null if the list is empty. in push_front()
319 // INVARIANT: `new_elem` is in the list because we just inserted it. in push_front()
323 /// Removes the last item from this list.
329 // SAFETY: We just checked that the list is not empty. in pop_back()
331 // SAFETY: The last item of this list is in this list. in pop_back()
335 /// Removes the first item from this list.
341 // SAFETY: The first item of this list is in this list. in pop_front()
345 /// Removes the provided item from this list and returns it.
347 /// This returns `None` if the item is not in the list. (Note that by the safety requirements,
348 /// this means that the item is not in any list.)
352 /// `item` must not be in a different linked list (with the same id).
360 // * If `item` is not in any list, then these fields are read-only and null. in remove()
361 // * If `item` is in this list, then we have exclusive access to these fields since we in remove()
362 // have a mutable reference to the list. in remove()
371 // This ensures that the list is valid under the more restrictive strict provenance in remove()
375 // list invariants. in remove()
381 // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it in remove()
382 // is in this list. The pointers are in the right order. in remove()
389 /// Removes the provided item from the list.
393 /// `item` must point at an item in this list.
396 // since we have a mutable reference to the list containing `item`. in remove_internal()
402 /// Removes the provided item from the list.
406 /// The `item` pointer must point at an item in this list, and we must have `(*item).next ==
414 // SAFETY: We have exclusive access to the pointers of items in the list, and the prev/next in remove_internal_inner()
415 // pointers are always valid for items in a list. in remove_internal_inner()
418 // * If the list has at least three items, then after removing the item, `prev` and `next` in remove_internal_inner()
420 // * If the list has two items, then the remaining item will point at itself. in remove_internal_inner()
421 // * If the list has one item, then `next == prev == item`, so these writes have no in remove_internal_inner()
422 // effect. The list remains unchanged and `item` is still in the list for now. in remove_internal_inner()
427 // SAFETY: We have exclusive access to items in the list. in remove_internal_inner()
438 // * If `item` was the only item in the list, then `prev == item`, and we just set in remove_internal_inner()
439 // `item->next` to null, so this correctly sets `first` to null now that the list is in remove_internal_inner()
443 // list, so it must be valid. There is no race since `prev` is still in the list and we in remove_internal_inner()
444 // still have exclusive access to the list. in remove_internal_inner()
448 // SAFETY: `item` used to be in the list, so it is dereferenceable by the type invariants in remove_internal_inner()
449 // of `List`. in remove_internal_inner()
451 // SAFETY: Any pointer in the list originates from a `prepare_to_insert` call. in remove_internal_inner()
461 pub fn push_all_back(&mut self, other: &mut List<T, ID>) { in push_all_back()
468 // SAFETY: The other list is not empty, so this pointer is valid. in push_all_back()
471 // SAFETY: The self list is not empty, so this pointer is valid. in push_all_back()
485 // INVARIANT: The other list is now empty, so update its pointer. in push_all_back()
489 /// Returns a cursor that points before the first element of the list.
491 // INVARIANT: `self.first` is in this list. in cursor_front()
494 list: self, in cursor_front()
498 /// Returns a cursor that points after the last element in the list.
503 list: self, in cursor_back()
507 /// Creates an iterator over the list.
509 // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point in iter()
510 // at the first element of the same list. in iter()
519 impl<T: ?Sized + ListItem<ID>, const ID: u64> Default for List<T, ID> { implementation
521 List::new() in default()
525 impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> { implementation
533 /// An iterator over a [`List`].
537 /// * There must be a [`List`] that is immutably borrowed for the duration of `'a`.
538 /// * The `current` pointer is null or points at a value in that [`List`].
539 /// * The `stop` pointer is equal to the `first` field of that [`List`].
557 // SAFETY: We just checked that `current` is not null, so it is in a list, and hence not in next()
558 // dangling. There's no race because the iterator holds an immutable borrow to the list. in next()
560 // INVARIANT: If `current` was the last element of the list, then this updates it to null. in next()
568 // SAFETY: The `current` pointer points at a value in the list. in next()
571 // * All values in a list are stored in an `Arc`. in next()
572 // * The value cannot be removed from the list for the duration of the lifetime annotated in next()
573 // on the returned `ArcBorrow`, because removing it from the list would require mutable in next()
574 // access to the list. However, the `ArcBorrow` is annotated with the iterator's in next()
575 // lifetime, and the list is immutably borrowed for that lifetime. in next()
576 // * Values in a list never have a `UniqueArc` reference. in next()
581 /// A cursor into a [`List`].
583 /// A cursor always rests between two elements in the list. This means that a cursor has a previous
585 /// into an empty list.
591 /// use kernel::list::{List, ListArc, ListLinks};
609 /// kernel::list::impl_has_list_links! {
612 /// kernel::list::impl_list_arc_safe! {
615 /// kernel::list::impl_list_item! {
620 /// fn remove_first(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
621 /// let mut cursor = list.cursor_front();
632 /// fn remove_last(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
633 /// let mut cursor = list.cursor_back();
644 /// // a new list.
645 /// fn remove_all(list: &mut List<ListItem>, value: u32) -> List<ListItem> {
646 /// let mut out = List::new();
647 /// let mut cursor = list.cursor_front();
660 /// fn insert_at(list: &mut List<ListItem>, new: ListArc<ListItem>, idx: usize) -> Result {
661 /// let mut cursor = list.cursor_front();
671 /// // Merge two sorted lists into a single sorted list.
672 /// fn merge_sorted(list: &mut List<ListItem>, merge: List<ListItem>) {
673 /// let mut cursor = list.cursor_front();
685 /// let mut list = List::new();
686 /// list.push_back(ListItem::new(14)?);
687 /// list.push_back(ListItem::new(12)?);
688 /// list.push_back(ListItem::new(10)?);
689 /// list.push_back(ListItem::new(12)?);
690 /// list.push_back(ListItem::new(15)?);
691 /// list.push_back(ListItem::new(14)?);
692 /// assert_eq!(remove_all(&mut list, 12).iter().count(), 2);
694 /// assert!(remove_first(&mut list, 14).is_some());
696 /// insert_at(&mut list, ListItem::new(12)?, 2)?;
698 /// assert!(remove_last(&mut list, 15).is_some());
701 /// let mut list2 = List::new();
704 /// merge_sorted(&mut list, list2);
706 /// let mut items = list.into_iter();
718 /// The `next` pointer is null or points a value in `list`.
720 list: &'a mut List<T, ID>, field
731 let first = self.list.first; in prev_ptr()
745 // list, so we can access its `prev` pointer. in prev_ptr()
756 // * We just checked that `self.next` is non-null, so it must be in `self.list`. in peek_next()
773 // * We just checked that `prev` is non-null, so it must be in `self.list`. in peek_prev()
790 // SAFETY: `self.next` is an element in the list and we borrow the list mutably, so we can in move_next()
794 if next == self.list.first { in move_next()
798 // INVARIANT: `next` is either null or the next element after an element in the list. in move_next()
808 if self.next == self.list.first { in move_prev()
812 // INVARIANT: `prev_ptr()` always returns a pointer that is null or in the list. in move_prev()
820 self.list.first in insert_inner()
825 // * `ptr` is an element in the list or null. in insert_inner()
826 // * if `ptr` is null, then `self.list.first` is null so the list is empty. in insert_inner()
827 let item = unsafe { self.list.insert_inner(item, ptr) }; in insert_inner()
828 if self.next == self.list.first { in insert_inner()
829 // INVARIANT: We just inserted `item`, so it's a member of list. in insert_inner()
830 self.list.first = item; in insert_inner()
858 /// Remove the next element from the list.
863 /// Remove the previous element from the list.
869 /// References the element in the list next to the cursor.
873 /// * `ptr` is an element in `self.cursor.list`.
883 /// Remove the element from the list.
892 // `self.cursor.list` by the type invariants of `Cursor`. in remove()
893 unsafe { self.cursor.list.remove_internal(self.ptr) } in remove()
898 // SAFETY: `self.ptr` points at an element in `self.cursor.list`. in arc()
901 // * All values in a list are stored in an `Arc`. in arc()
902 // * The value cannot be removed from the list for the duration of the lifetime annotated in arc()
903 // on the returned `ArcBorrow`, because removing it from the list would require mutable in arc()
904 // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `ArcBorrow` holds in arc()
906 // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable in arc()
908 // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc` in arc()
925 // SAFETY: `self.ptr` points at an element in `self.cursor.list`. in deref()
928 // SAFETY: The value cannot be removed from the list for the duration of the lifetime in deref()
929 // annotated on the returned `&T`, because removing it from the list would require mutable in deref()
930 // access to the `CursorPeek`, the `Cursor` or the `List`. However, the `&T` holds an in deref()
932 // `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable access in deref()
940 impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for &'a List<T, ID> { implementation
949 /// An owning iterator into a [`List`].
951 list: List<T, ID>, field
958 self.list.pop_front() in next()
966 self.list.pop_back() in next_back()
970 impl<T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for List<T, ID> { implementation
975 IntoIter { list: self } in into_iter()