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
38 pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {  struct
45 unsafe impl<T, const ID: u64> Send for List<T, ID>  implementation
53 unsafe impl<T, const ID: u64> Sync for List<T, ID>  implementation
60 /// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`].
86     /// Can only be used when the value is in a list.
102     /// This is called when an item is inserted into a [`List`].
140 /// The prev/next pointers for an item in a linked list.
144 /// The fields are null if and only if this item is not in a list.
148     // list.
234 impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> {  implementation
235     /// Creates a new empty list.
243     /// Returns whether this list is empty.
248     /// Add the provided item to the back of the list.
256         // * Removing items from this list is always done using `remove_internal_inner`, which  in push_back()
265             // INVARIANT: A linked list with one item should be cyclic.  in push_back()
275             // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us  in push_back()
287     /// Add the provided item to the front of the list.
296         // * Removing items] from this list is always done using `remove_internal_inner`, which  in push_front()
304             // INVARIANT: A linked list with one item should be cyclic.  in push_front()
313             // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us  in push_front()
326     /// Removes the last item from this list.
332         // SAFETY: We just checked that the list is not empty.  in pop_back()
334         // SAFETY: The last item of this list is in this list.  in pop_back()
338     /// Removes the first item from this list.
344         // SAFETY: The first item of this list is in this list.  in pop_front()
348     /// Removes the provided item from this list and returns it.
350     /// This returns `None` if the item is not in the list. (Note that by the safety requirements,
351     /// this means that the item is not in any list.)
355     /// `item` must not be in a different linked list (with the same id).
363         //  * If `item` is not in any list, then these fields are read-only and null.  in remove()
364         //  * If `item` is in this list, then we have exclusive access to these fields since we  in remove()
365         //    have a mutable reference to the list.  in remove()
374             // This ensures that the list is valid under the more restrictive strict provenance  in remove()
378             // list invariants.  in remove()
384             // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it  in remove()
385             // is in this list. The pointers are in the right order.  in remove()
392     /// Removes the provided item from the list.
396     /// `item` must point at an item in this list.
399         // since we have a mutable reference to the list containing `item`.  in remove_internal()
405     /// Removes the provided item from the list.
409     /// The `item` pointer must point at an item in this list, and we must have `(*item).next ==
417         // SAFETY: We have exclusive access to the pointers of items in the list, and the prev/next  in remove_internal_inner()
418         // pointers are always valid for items in a list.  in remove_internal_inner()
421         //  * If the list has at least three items, then after removing the item, `prev` and `next`  in remove_internal_inner()
423         //  * If the list has two items, then the remaining item will point at itself.  in remove_internal_inner()
424         //  * If the list has one item, then `next == prev == item`, so these writes have no  in remove_internal_inner()
425         //    effect. The list remains unchanged and `item` is still in the list for now.  in remove_internal_inner()
430         // SAFETY: We have exclusive access to items in the list.  in remove_internal_inner()
441         //  * If `item` was the only item in the list, then `prev == item`, and we just set  in remove_internal_inner()
442         //    `item->next` to null, so this correctly sets `first` to null now that the list is  in remove_internal_inner()
446             // list, so it must be valid. There is no race since `prev` is still in the list and we  in remove_internal_inner()
447             // still have exclusive access to the list.  in remove_internal_inner()
451         // SAFETY: `item` used to be in the list, so it is dereferenceable by the type invariants  in remove_internal_inner()
452         // of `List`.  in remove_internal_inner()
454         // SAFETY: Any pointer in the list originates from a `prepare_to_insert` call.  in remove_internal_inner()
464     pub fn push_all_back(&mut self, other: &mut List<T, ID>) {  in push_all_back()
471             // SAFETY: The other list is not empty, so this pointer is valid.  in push_all_back()
474             // SAFETY: The self list is not empty, so this pointer is valid.  in push_all_back()
488         // INVARIANT: The other list is now empty, so update its pointer.  in push_all_back()
492     /// Returns a cursor to the first element of the list.
494     /// If the list is empty, this returns `None`.
501                 list: self,  in cursor_front()
506     /// Creates an iterator over the list.
508         // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point  in iter()
509         // at the first element of the same list.  in iter()
518 impl<T: ?Sized + ListItem<ID>, const ID: u64> Default for List<T, ID> {  implementation
520         List::new()  in default()
524 impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> {  implementation
532 /// An iterator over a [`List`].
536 /// * There must be a [`List`] that is immutably borrowed for the duration of `'a`.
537 /// * The `current` pointer is null or points at a value in that [`List`].
538 /// * The `stop` pointer is equal to the `first` field of that [`List`].
556         // SAFETY: We just checked that `current` is not null, so it is in a list, and hence not  in next()
557         // dangling. There's no race because the iterator holds an immutable borrow to the list.  in next()
559         // INVARIANT: If `current` was the last element of the list, then this updates it to null.  in next()
567         // SAFETY: The `current` pointer points at a value in the list.  in next()
570         // * All values in a list are stored in an `Arc`.  in next()
571         // * The value cannot be removed from the list for the duration of the lifetime annotated  in next()
572         //   on the returned `ArcBorrow`, because removing it from the list would require mutable  in next()
573         //   access to the list. However, the `ArcBorrow` is annotated with the iterator's  in next()
574         //   lifetime, and the list is immutably borrowed for that lifetime.  in next()
575         // * Values in a list never have a `UniqueArc` reference.  in next()
580 /// A cursor into a [`List`].
584 /// The `current` pointer points a value in `list`.
587     list: &'a mut List<T, ID>,  field
593         // SAFETY: The `current` pointer points a value in the list.  in current()
596         // * All values in a list are stored in an `Arc`.  in current()
597         // * The value cannot be removed from the list for the duration of the lifetime annotated  in current()
598         //   on the returned `ArcBorrow`, because removing it from the list would require mutable  in current()
599         //   access to the cursor or the list. However, the `ArcBorrow` holds an immutable borrow  in current()
600         //   on the cursor, which in turn holds a mutable borrow on the list, so any such  in current()
602         // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc`  in current()
609         // SAFETY: The `current` field is always in a list.  in next()
612         if next == self.list.first {  in next()
615             // INVARIANT: Since `self.current` is in the `list`, its `next` pointer is also in the  in next()
616             // `list`.  in next()
619                 list: self.list,  in next()
626         // SAFETY: The `current` field is always in a list.  in prev()
629         if self.current == self.list.first {  in prev()
632             // INVARIANT: Since `self.current` is in the `list`, its `prev` pointer is also in the  in prev()
633             // `list`.  in prev()
636                 list: self.list,  in prev()
641     /// Remove the current element from the list.
643         // SAFETY: The `current` pointer always points at a member of the list.  in remove()
644         unsafe { self.list.remove_internal(self.current) }  in remove()
650 impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for &'a List<T, ID> {  implementation
659 /// An owning iterator into a [`List`].
661     list: List<T, ID>,  field
668         self.list.pop_front()  in next()
676         self.list.pop_back()  in next_back()
680 impl<T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for List<T, ID> {  implementation
685         IntoIter { list: self }  in into_iter()