Lines Matching +full:send +full:- +full:not +full:- +full:empty

1 // SPDX-License-Identifier: GPL-2.0
7 // May not be needed in Rust 1.87.0 (pending beta backport).
32 /// prev/next pointers are not used for several linked lists.
36 /// * If the list is empty, then `first` is null. Otherwise, `first` points at the `ListLinks`
48 unsafe impl<T, const ID: u64> Send for List<T, ID>
50 ListArc<T, ID>: Send,
80 /// Otherwise, the returned pointer points at a read-only [`ListLinks`] with two null pointers.
84 /// The provided pointer must point at a valid value. (It need not be in an `Arc`.)
85 unsafe fn view_links(me: *const Self) -> *mut ListLinks<ID>; in view_links()
101 /// * Since the most recent call to `prepare_to_insert`, the `post_remove` method must not have
103 unsafe fn view_value(me: *mut ListLinks<ID>) -> *const Self; in view_value()
117 /// * The caller must not give up ownership of the [`ListArc`] unless `post_remove` has been
121 unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<ID>; in prepare_to_insert()
133 unsafe fn post_remove(me: *mut ListLinks<ID>) -> *const Self; in post_remove()
147 /// The fields are null if and only if this item is not in a list.
156 // associated `ListArc<T, ID>`. Since that type correctly implements `Send`, it is impossible to
157 // move this an instance of this type to a different thread if the pointees are `!Send`.
158 unsafe impl<const ID: u64> Send for ListLinks<ID> {}
165 pub fn new() -> impl PinInit<Self> { in new()
166 // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will in new()
167 // not be constructed in an `Arc` that already has a `ListArc`. in new()
180 unsafe fn fields(me: *mut Self) -> *mut ListLinksFields { in fields()
189 unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { in from_fields()
203 // UnsafeCell is not enough here because we use `Opaque::uninit` as a dummy value, and
209 unsafe impl<T: ?Sized + Send, const ID: u64> Send for ListLinksSelfPtr<T, ID> {}
213 // Note that `inner` being a public field does not prevent this type from being opaque, since
222 pub fn new() -> impl PinInit<Self> { in new()
223 // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will in new()
224 // not be constructed in an `Arc` that already has a `ListArc`. in new()
238 /// Creates a new empty list.
239 pub const fn new() -> Self { in new()
246 /// Returns whether this list is empty.
247 pub fn is_empty(&self) -> bool { in is_empty()
254 /// is empty.
259 /// * if `next` is null, then the list must be empty.
264 ) -> *mut ListLinksFields { in insert_inner()
274 // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid. in insert_inner()
277 // Check if the list is empty. in insert_inner()
288 // it's not null, so it must be valid. in insert_inner()
308 // * `self.first` is only null if the list is empty. in push_back()
316 // * `self.first` is only null if the list is empty. in push_front()
324 pub fn pop_back(&mut self) -> Option<ListArc<T, ID>> { in pop_back()
329 // SAFETY: We just checked that the list is not empty. in pop_back()
336 pub fn pop_front(&mut self) -> Option<ListArc<T, ID>> { in pop_front()
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).
353 pub unsafe fn remove(&mut self, item: &T) -> Option<ListArc<T, ID>> { in remove()
358 // As for why this is not a data race, there are two cases: in remove()
360 // * If `item` is not in any list, then these fields are read-only and null. in remove()
369 // This is really a no-op, but this ensures that `item` is a raw pointer that was in remove()
370 // obtained without going through a pointer->reference->pointer conversion roundtrip. in remove()
374 // SAFETY: We just checked that `next` is not null, and it's not dangling by the in remove()
394 unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> ListArc<T, ID> { in remove_internal()
395 // SAFETY: The caller promises that this pointer is not dangling, and there's no data race in remove_internal()
413 ) -> ListArc<T, ID> { in remove_internal_inner()
434 // * If `item` was not the first item, then `self.first` should remain unchanged. in remove_internal_inner()
436 // `prev->next` to `next`, which is the new first item, and setting `item->next` to null in remove_internal_inner()
437 // did not modify `prev->next`. 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()
440 // empty. in remove_internal_inner()
442 // SAFETY: The `prev` pointer is the value that `item->prev` had when it was in this in remove_internal_inner()
462 // First, we insert the elements into `self`. At the end, we make `other` empty. 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()
475 // INVARIANT: This correctly sets the pointers to merge both lists. We do not need to in push_all_back()
476 // update `self.first` because the first element of `self` does not change. in push_all_back()
485 // INVARIANT: The other list is now empty, so update its pointer. in push_all_back()
490 pub fn cursor_front(&mut self) -> Cursor<'_, T, ID> { in cursor_front()
499 pub fn cursor_back(&mut self) -> Cursor<'_, T, ID> { in cursor_back()
508 pub fn iter(&self) -> Iter<'_, T, ID> { in iter()
509 // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point in iter()
520 fn default() -> Self { in default()
550 fn next(&mut self) -> Option<ArcBorrow<'a, T>> { in next()
557 // SAFETY: We just checked that `current` is not null, so it is in a list, and hence not in next()
585 /// into an empty list.
601 /// fn new(value: u32) -> Result<ListArc<Self>> {
604 /// links <- ListLinks::new(),
620 /// fn remove_first(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
632 /// fn remove_last(list: &mut List<ListItem>, value: u32) -> Option<ListArc<ListItem>> {
645 /// fn remove_all(list: &mut List<ListItem>, value: u32) -> List<ListItem> {
660 /// fn insert_at(list: &mut List<ListItem>, new: ListArc<ListItem>, idx: usize) -> Result {
729 fn prev_ptr(&self) -> *mut ListLinksFields { in prev_ptr()
750 pub fn peek_next(&mut self) -> Option<CursorPeek<'_, 'a, T, true, ID>> { in peek_next()
756 // * We just checked that `self.next` is non-null, so it must be in `self.list`. in peek_next()
765 pub fn peek_prev(&mut self) -> Option<CursorPeek<'_, 'a, T, false, ID>> { in peek_prev()
773 // * We just checked that `prev` is non-null, so it must be in `self.list`. in peek_prev()
785 pub fn move_next(&mut self) -> bool { in move_next()
807 pub fn move_prev(&mut self) -> bool { in move_prev()
818 fn insert_inner(&mut self, item: ListArc<T, ID>) -> *mut ListLinksFields { in insert_inner()
826 // * if `ptr` is null, then `self.list.first` is null so the list is empty. in insert_inner()
859 pub fn remove_next(&mut self) -> Option<ListArc<T, ID>> { in remove_next()
864 pub fn remove_prev(&mut self) -> Option<ListArc<T, ID>> { in remove_prev()
884 pub fn remove(self) -> ListArc<T, ID> { in remove()
889 // INVARIANT: `self.ptr` is not equal to `self.cursor.next` due to the above `move_next` in remove()
891 // SAFETY: By the type invariants of `Self`, `next` is not null, so `next` is an element of in remove()
897 pub fn arc(&self) -> ArcBorrow<'_, T> { in arc()
924 fn deref(&self) -> &T { in deref()
944 fn into_iter(self) -> Iter<'a, T, ID> { in into_iter()
957 fn next(&mut self) -> Option<ListArc<T, ID>> { in next()
965 fn next_back(&mut self) -> Option<ListArc<T, ID>> { in next_back()
974 fn into_iter(self) -> IntoIter<T, ID> { in into_iter()