Loading...
Note: File does not exist in v3.5.6.
1// SPDX-License-Identifier: GPL-2.0
2
3// Copyright (C) 2024 Google LLC.
4
5//! A linked list implementation.
6
7use crate::init::PinInit;
8use crate::sync::ArcBorrow;
9use crate::types::Opaque;
10use core::iter::{DoubleEndedIterator, FusedIterator};
11use core::marker::PhantomData;
12use core::ptr;
13
14mod impl_list_item_mod;
15pub use self::impl_list_item_mod::{
16 impl_has_list_links, impl_has_list_links_self_ptr, impl_list_item, HasListLinks, HasSelfPtr,
17};
18
19mod arc;
20pub use self::arc::{impl_list_arc_safe, AtomicTracker, ListArc, ListArcSafe, TryNewListArc};
21
22mod arc_field;
23pub use self::arc_field::{define_list_arc_field_getter, ListArcField};
24
25/// A linked list.
26///
27/// All elements in this linked list will be [`ListArc`] references to the value. Since a value can
28/// only have one `ListArc` (for each pair of prev/next pointers), this ensures that the same
29/// prev/next pointers are not used for several linked lists.
30///
31/// # Invariants
32///
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
37/// exclusive access to the `ListLinks` field.
38pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
39 first: *mut ListLinksFields,
40 _ty: PhantomData<ListArc<T, ID>>,
41}
42
43// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
44// type of access to the `ListArc<T, ID>` elements.
45unsafe impl<T, const ID: u64> Send for List<T, ID>
46where
47 ListArc<T, ID>: Send,
48 T: ?Sized + ListItem<ID>,
49{
50}
51// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
52// type of access to the `ListArc<T, ID>` elements.
53unsafe impl<T, const ID: u64> Sync for List<T, ID>
54where
55 ListArc<T, ID>: Sync,
56 T: ?Sized + ListItem<ID>,
57{
58}
59
60/// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`].
61///
62/// # Safety
63///
64/// Implementers must ensure that they provide the guarantees documented on methods provided by
65/// this trait.
66///
67/// [`ListArc<Self>`]: ListArc
68pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
69 /// Views the [`ListLinks`] for this value.
70 ///
71 /// # Guarantees
72 ///
73 /// If there is a previous call to `prepare_to_insert` and there is no call to `post_remove`
74 /// since the most recent such call, then this returns the same pointer as the one returned by
75 /// the most recent call to `prepare_to_insert`.
76 ///
77 /// Otherwise, the returned pointer points at a read-only [`ListLinks`] with two null pointers.
78 ///
79 /// # Safety
80 ///
81 /// The provided pointer must point at a valid value. (It need not be in an `Arc`.)
82 unsafe fn view_links(me: *const Self) -> *mut ListLinks<ID>;
83
84 /// View the full value given its [`ListLinks`] field.
85 ///
86 /// Can only be used when the value is in a list.
87 ///
88 /// # Guarantees
89 ///
90 /// * Returns the same pointer as the one passed to the most recent call to `prepare_to_insert`.
91 /// * The returned pointer is valid until the next call to `post_remove`.
92 ///
93 /// # Safety
94 ///
95 /// * The provided pointer must originate from the most recent call to `prepare_to_insert`, or
96 /// from a call to `view_links` that happened after the most recent call to
97 /// `prepare_to_insert`.
98 /// * Since the most recent call to `prepare_to_insert`, the `post_remove` method must not have
99 /// been called.
100 unsafe fn view_value(me: *mut ListLinks<ID>) -> *const Self;
101
102 /// This is called when an item is inserted into a [`List`].
103 ///
104 /// # Guarantees
105 ///
106 /// The caller is granted exclusive access to the returned [`ListLinks`] until `post_remove` is
107 /// called.
108 ///
109 /// # Safety
110 ///
111 /// * The provided pointer must point at a valid value in an [`Arc`].
112 /// * Calls to `prepare_to_insert` and `post_remove` on the same value must alternate.
113 /// * The caller must own the [`ListArc`] for this value.
114 /// * The caller must not give up ownership of the [`ListArc`] unless `post_remove` has been
115 /// called after this call to `prepare_to_insert`.
116 ///
117 /// [`Arc`]: crate::sync::Arc
118 unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<ID>;
119
120 /// This undoes a previous call to `prepare_to_insert`.
121 ///
122 /// # Guarantees
123 ///
124 /// The returned pointer is the pointer that was originally passed to `prepare_to_insert`.
125 ///
126 /// # Safety
127 ///
128 /// The provided pointer must be the pointer returned by the most recent call to
129 /// `prepare_to_insert`.
130 unsafe fn post_remove(me: *mut ListLinks<ID>) -> *const Self;
131}
132
133#[repr(C)]
134#[derive(Copy, Clone)]
135struct ListLinksFields {
136 next: *mut ListLinksFields,
137 prev: *mut ListLinksFields,
138}
139
140/// The prev/next pointers for an item in a linked list.
141///
142/// # Invariants
143///
144/// The fields are null if and only if this item is not in a list.
145#[repr(transparent)]
146pub struct ListLinks<const ID: u64 = 0> {
147 // This type is `!Unpin` for aliasing reasons as the pointers are part of an intrusive linked
148 // list.
149 inner: Opaque<ListLinksFields>,
150}
151
152// SAFETY: The only way to access/modify the pointers inside of `ListLinks<ID>` is via holding the
153// associated `ListArc<T, ID>`. Since that type correctly implements `Send`, it is impossible to
154// move this an instance of this type to a different thread if the pointees are `!Send`.
155unsafe impl<const ID: u64> Send for ListLinks<ID> {}
156// SAFETY: The type is opaque so immutable references to a ListLinks are useless. Therefore, it's
157// okay to have immutable access to a ListLinks from several threads at once.
158unsafe impl<const ID: u64> Sync for ListLinks<ID> {}
159
160impl<const ID: u64> ListLinks<ID> {
161 /// Creates a new initializer for this type.
162 pub fn new() -> impl PinInit<Self> {
163 // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will
164 // not be constructed in an `Arc` that already has a `ListArc`.
165 ListLinks {
166 inner: Opaque::new(ListLinksFields {
167 prev: ptr::null_mut(),
168 next: ptr::null_mut(),
169 }),
170 }
171 }
172
173 /// # Safety
174 ///
175 /// `me` must be dereferenceable.
176 #[inline]
177 unsafe fn fields(me: *mut Self) -> *mut ListLinksFields {
178 // SAFETY: The caller promises that the pointer is valid.
179 unsafe { Opaque::raw_get(ptr::addr_of!((*me).inner)) }
180 }
181
182 /// # Safety
183 ///
184 /// `me` must be dereferenceable.
185 #[inline]
186 unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self {
187 me.cast()
188 }
189}
190
191/// Similar to [`ListLinks`], but also contains a pointer to the full value.
192///
193/// This type can be used instead of [`ListLinks`] to support lists with trait objects.
194#[repr(C)]
195pub struct ListLinksSelfPtr<T: ?Sized, const ID: u64 = 0> {
196 /// The `ListLinks` field inside this value.
197 ///
198 /// This is public so that it can be used with `impl_has_list_links!`.
199 pub inner: ListLinks<ID>,
200 // UnsafeCell is not enough here because we use `Opaque::uninit` as a dummy value, and
201 // `ptr::null()` doesn't work for `T: ?Sized`.
202 self_ptr: Opaque<*const T>,
203}
204
205// SAFETY: The fields of a ListLinksSelfPtr can be moved across thread boundaries.
206unsafe impl<T: ?Sized + Send, const ID: u64> Send for ListLinksSelfPtr<T, ID> {}
207// SAFETY: The type is opaque so immutable references to a ListLinksSelfPtr are useless. Therefore,
208// it's okay to have immutable access to a ListLinks from several threads at once.
209//
210// Note that `inner` being a public field does not prevent this type from being opaque, since
211// `inner` is a opaque type.
212unsafe impl<T: ?Sized + Sync, const ID: u64> Sync for ListLinksSelfPtr<T, ID> {}
213
214impl<T: ?Sized, const ID: u64> ListLinksSelfPtr<T, ID> {
215 /// The offset from the [`ListLinks`] to the self pointer field.
216 pub const LIST_LINKS_SELF_PTR_OFFSET: usize = core::mem::offset_of!(Self, self_ptr);
217
218 /// Creates a new initializer for this type.
219 pub fn new() -> impl PinInit<Self> {
220 // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will
221 // not be constructed in an `Arc` that already has a `ListArc`.
222 Self {
223 inner: ListLinks {
224 inner: Opaque::new(ListLinksFields {
225 prev: ptr::null_mut(),
226 next: ptr::null_mut(),
227 }),
228 },
229 self_ptr: Opaque::uninit(),
230 }
231 }
232}
233
234impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> {
235 /// Creates a new empty list.
236 pub const fn new() -> Self {
237 Self {
238 first: ptr::null_mut(),
239 _ty: PhantomData,
240 }
241 }
242
243 /// Returns whether this list is empty.
244 pub fn is_empty(&self) -> bool {
245 self.first.is_null()
246 }
247
248 /// Add the provided item to the back of the list.
249 pub fn push_back(&mut self, item: ListArc<T, ID>) {
250 let raw_item = ListArc::into_raw(item);
251 // SAFETY:
252 // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`.
253 // * Since we have ownership of the `ListArc`, `post_remove` must have been called after
254 // the most recent call to `prepare_to_insert`, if any.
255 // * We own the `ListArc`.
256 // * Removing items from this list is always done using `remove_internal_inner`, which
257 // calls `post_remove` before giving up ownership.
258 let list_links = unsafe { T::prepare_to_insert(raw_item) };
259 // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid.
260 let item = unsafe { ListLinks::fields(list_links) };
261
262 if self.first.is_null() {
263 self.first = item;
264 // SAFETY: The caller just gave us ownership of these fields.
265 // INVARIANT: A linked list with one item should be cyclic.
266 unsafe {
267 (*item).next = item;
268 (*item).prev = item;
269 }
270 } else {
271 let next = self.first;
272 // SAFETY: By the type invariant, this pointer is valid or null. We just checked that
273 // it's not null, so it must be valid.
274 let prev = unsafe { (*next).prev };
275 // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
276 // ownership of the fields on `item`.
277 // INVARIANT: This correctly inserts `item` between `prev` and `next`.
278 unsafe {
279 (*item).next = next;
280 (*item).prev = prev;
281 (*prev).next = item;
282 (*next).prev = item;
283 }
284 }
285 }
286
287 /// Add the provided item to the front of the list.
288 pub fn push_front(&mut self, item: ListArc<T, ID>) {
289 let raw_item = ListArc::into_raw(item);
290 // SAFETY:
291 // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`.
292 // * If this requirement is violated, then the previous caller of `prepare_to_insert`
293 // violated the safety requirement that they can't give up ownership of the `ListArc`
294 // until they call `post_remove`.
295 // * We own the `ListArc`.
296 // * Removing items] from this list is always done using `remove_internal_inner`, which
297 // calls `post_remove` before giving up ownership.
298 let list_links = unsafe { T::prepare_to_insert(raw_item) };
299 // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid.
300 let item = unsafe { ListLinks::fields(list_links) };
301
302 if self.first.is_null() {
303 // SAFETY: The caller just gave us ownership of these fields.
304 // INVARIANT: A linked list with one item should be cyclic.
305 unsafe {
306 (*item).next = item;
307 (*item).prev = item;
308 }
309 } else {
310 let next = self.first;
311 // SAFETY: We just checked that `next` is non-null.
312 let prev = unsafe { (*next).prev };
313 // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
314 // ownership of the fields on `item`.
315 // INVARIANT: This correctly inserts `item` between `prev` and `next`.
316 unsafe {
317 (*item).next = next;
318 (*item).prev = prev;
319 (*prev).next = item;
320 (*next).prev = item;
321 }
322 }
323 self.first = item;
324 }
325
326 /// Removes the last item from this list.
327 pub fn pop_back(&mut self) -> Option<ListArc<T, ID>> {
328 if self.first.is_null() {
329 return None;
330 }
331
332 // SAFETY: We just checked that the list is not empty.
333 let last = unsafe { (*self.first).prev };
334 // SAFETY: The last item of this list is in this list.
335 Some(unsafe { self.remove_internal(last) })
336 }
337
338 /// Removes the first item from this list.
339 pub fn pop_front(&mut self) -> Option<ListArc<T, ID>> {
340 if self.first.is_null() {
341 return None;
342 }
343
344 // SAFETY: The first item of this list is in this list.
345 Some(unsafe { self.remove_internal(self.first) })
346 }
347
348 /// Removes the provided item from this list and returns it.
349 ///
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.)
352 ///
353 /// # Safety
354 ///
355 /// `item` must not be in a different linked list (with the same id).
356 pub unsafe fn remove(&mut self, item: &T) -> Option<ListArc<T, ID>> {
357 // SAFETY: TODO.
358 let mut item = unsafe { ListLinks::fields(T::view_links(item)) };
359 // SAFETY: The user provided a reference, and reference are never dangling.
360 //
361 // As for why this is not a data race, there are two cases:
362 //
363 // * If `item` is not in any list, then these fields are read-only and null.
364 // * If `item` is in this list, then we have exclusive access to these fields since we
365 // have a mutable reference to the list.
366 //
367 // In either case, there's no race.
368 let ListLinksFields { next, prev } = unsafe { *item };
369
370 debug_assert_eq!(next.is_null(), prev.is_null());
371 if !next.is_null() {
372 // This is really a no-op, but this ensures that `item` is a raw pointer that was
373 // obtained without going through a pointer->reference->pointer conversion roundtrip.
374 // This ensures that the list is valid under the more restrictive strict provenance
375 // ruleset.
376 //
377 // SAFETY: We just checked that `next` is not null, and it's not dangling by the
378 // list invariants.
379 unsafe {
380 debug_assert_eq!(item, (*next).prev);
381 item = (*next).prev;
382 }
383
384 // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it
385 // is in this list. The pointers are in the right order.
386 Some(unsafe { self.remove_internal_inner(item, next, prev) })
387 } else {
388 None
389 }
390 }
391
392 /// Removes the provided item from the list.
393 ///
394 /// # Safety
395 ///
396 /// `item` must point at an item in this list.
397 unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> ListArc<T, ID> {
398 // SAFETY: The caller promises that this pointer is not dangling, and there's no data race
399 // since we have a mutable reference to the list containing `item`.
400 let ListLinksFields { next, prev } = unsafe { *item };
401 // SAFETY: The pointers are ok and in the right order.
402 unsafe { self.remove_internal_inner(item, next, prev) }
403 }
404
405 /// Removes the provided item from the list.
406 ///
407 /// # Safety
408 ///
409 /// The `item` pointer must point at an item in this list, and we must have `(*item).next ==
410 /// next` and `(*item).prev == prev`.
411 unsafe fn remove_internal_inner(
412 &mut self,
413 item: *mut ListLinksFields,
414 next: *mut ListLinksFields,
415 prev: *mut ListLinksFields,
416 ) -> ListArc<T, ID> {
417 // SAFETY: We have exclusive access to the pointers of items in the list, and the prev/next
418 // pointers are always valid for items in a list.
419 //
420 // INVARIANT: There are three cases:
421 // * If the list has at least three items, then after removing the item, `prev` and `next`
422 // will be next to each other.
423 // * If the list has two items, then the remaining item will point at itself.
424 // * If the list has one item, then `next == prev == item`, so these writes have no
425 // effect. The list remains unchanged and `item` is still in the list for now.
426 unsafe {
427 (*next).prev = prev;
428 (*prev).next = next;
429 }
430 // SAFETY: We have exclusive access to items in the list.
431 // INVARIANT: `item` is being removed, so the pointers should be null.
432 unsafe {
433 (*item).prev = ptr::null_mut();
434 (*item).next = ptr::null_mut();
435 }
436 // INVARIANT: There are three cases:
437 // * If `item` was not the first item, then `self.first` should remain unchanged.
438 // * If `item` was the first item and there is another item, then we just updated
439 // `prev->next` to `next`, which is the new first item, and setting `item->next` to null
440 // did not modify `prev->next`.
441 // * If `item` was the only item in the list, then `prev == item`, and we just set
442 // `item->next` to null, so this correctly sets `first` to null now that the list is
443 // empty.
444 if self.first == item {
445 // SAFETY: The `prev` pointer is the value that `item->prev` had when it was in this
446 // list, so it must be valid. There is no race since `prev` is still in the list and we
447 // still have exclusive access to the list.
448 self.first = unsafe { (*prev).next };
449 }
450
451 // SAFETY: `item` used to be in the list, so it is dereferenceable by the type invariants
452 // of `List`.
453 let list_links = unsafe { ListLinks::from_fields(item) };
454 // SAFETY: Any pointer in the list originates from a `prepare_to_insert` call.
455 let raw_item = unsafe { T::post_remove(list_links) };
456 // SAFETY: The above call to `post_remove` guarantees that we can recreate the `ListArc`.
457 unsafe { ListArc::from_raw(raw_item) }
458 }
459
460 /// Moves all items from `other` into `self`.
461 ///
462 /// The items of `other` are added to the back of `self`, so the last item of `other` becomes
463 /// the last item of `self`.
464 pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
465 // First, we insert the elements into `self`. At the end, we make `other` empty.
466 if self.is_empty() {
467 // INVARIANT: All of the elements in `other` become elements of `self`.
468 self.first = other.first;
469 } else if !other.is_empty() {
470 let other_first = other.first;
471 // SAFETY: The other list is not empty, so this pointer is valid.
472 let other_last = unsafe { (*other_first).prev };
473 let self_first = self.first;
474 // SAFETY: The self list is not empty, so this pointer is valid.
475 let self_last = unsafe { (*self_first).prev };
476
477 // SAFETY: We have exclusive access to both lists, so we can update the pointers.
478 // INVARIANT: This correctly sets the pointers to merge both lists. We do not need to
479 // update `self.first` because the first element of `self` does not change.
480 unsafe {
481 (*self_first).prev = other_last;
482 (*other_last).next = self_first;
483 (*self_last).next = other_first;
484 (*other_first).prev = self_last;
485 }
486 }
487
488 // INVARIANT: The other list is now empty, so update its pointer.
489 other.first = ptr::null_mut();
490 }
491
492 /// Returns a cursor to the first element of the list.
493 ///
494 /// If the list is empty, this returns `None`.
495 pub fn cursor_front(&mut self) -> Option<Cursor<'_, T, ID>> {
496 if self.first.is_null() {
497 None
498 } else {
499 Some(Cursor {
500 current: self.first,
501 list: self,
502 })
503 }
504 }
505
506 /// Creates an iterator over the list.
507 pub fn iter(&self) -> Iter<'_, T, ID> {
508 // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point
509 // at the first element of the same list.
510 Iter {
511 current: self.first,
512 stop: self.first,
513 _ty: PhantomData,
514 }
515 }
516}
517
518impl<T: ?Sized + ListItem<ID>, const ID: u64> Default for List<T, ID> {
519 fn default() -> Self {
520 List::new()
521 }
522}
523
524impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> {
525 fn drop(&mut self) {
526 while let Some(item) = self.pop_front() {
527 drop(item);
528 }
529 }
530}
531
532/// An iterator over a [`List`].
533///
534/// # Invariants
535///
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`].
539#[derive(Clone)]
540pub struct Iter<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
541 current: *mut ListLinksFields,
542 stop: *mut ListLinksFields,
543 _ty: PhantomData<&'a ListArc<T, ID>>,
544}
545
546impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Iterator for Iter<'a, T, ID> {
547 type Item = ArcBorrow<'a, T>;
548
549 fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
550 if self.current.is_null() {
551 return None;
552 }
553
554 let current = self.current;
555
556 // SAFETY: We just checked that `current` is not null, so it is in a list, and hence not
557 // dangling. There's no race because the iterator holds an immutable borrow to the list.
558 let next = unsafe { (*current).next };
559 // INVARIANT: If `current` was the last element of the list, then this updates it to null.
560 // Otherwise, we update it to the next element.
561 self.current = if next != self.stop {
562 next
563 } else {
564 ptr::null_mut()
565 };
566
567 // SAFETY: The `current` pointer points at a value in the list.
568 let item = unsafe { T::view_value(ListLinks::from_fields(current)) };
569 // SAFETY:
570 // * All values in a list are stored in an `Arc`.
571 // * The value cannot be removed from the list for the duration of the lifetime annotated
572 // on the returned `ArcBorrow`, because removing it from the list would require mutable
573 // access to the list. However, the `ArcBorrow` is annotated with the iterator's
574 // lifetime, and the list is immutably borrowed for that lifetime.
575 // * Values in a list never have a `UniqueArc` reference.
576 Some(unsafe { ArcBorrow::from_raw(item) })
577 }
578}
579
580/// A cursor into a [`List`].
581///
582/// # Invariants
583///
584/// The `current` pointer points a value in `list`.
585pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
586 current: *mut ListLinksFields,
587 list: &'a mut List<T, ID>,
588}
589
590impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Cursor<'a, T, ID> {
591 /// Access the current element of this cursor.
592 pub fn current(&self) -> ArcBorrow<'_, T> {
593 // SAFETY: The `current` pointer points a value in the list.
594 let me = unsafe { T::view_value(ListLinks::from_fields(self.current)) };
595 // SAFETY:
596 // * All values in a list are stored in an `Arc`.
597 // * The value cannot be removed from the list for the duration of the lifetime annotated
598 // on the returned `ArcBorrow`, because removing it from the list would require mutable
599 // access to the cursor or the list. However, the `ArcBorrow` holds an immutable borrow
600 // on the cursor, which in turn holds a mutable borrow on the list, so any such
601 // mutable access requires first releasing the immutable borrow on the cursor.
602 // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc`
603 // reference, and `UniqueArc` references must be unique.
604 unsafe { ArcBorrow::from_raw(me) }
605 }
606
607 /// Move the cursor to the next element.
608 pub fn next(self) -> Option<Cursor<'a, T, ID>> {
609 // SAFETY: The `current` field is always in a list.
610 let next = unsafe { (*self.current).next };
611
612 if next == self.list.first {
613 None
614 } else {
615 // INVARIANT: Since `self.current` is in the `list`, its `next` pointer is also in the
616 // `list`.
617 Some(Cursor {
618 current: next,
619 list: self.list,
620 })
621 }
622 }
623
624 /// Move the cursor to the previous element.
625 pub fn prev(self) -> Option<Cursor<'a, T, ID>> {
626 // SAFETY: The `current` field is always in a list.
627 let prev = unsafe { (*self.current).prev };
628
629 if self.current == self.list.first {
630 None
631 } else {
632 // INVARIANT: Since `self.current` is in the `list`, its `prev` pointer is also in the
633 // `list`.
634 Some(Cursor {
635 current: prev,
636 list: self.list,
637 })
638 }
639 }
640
641 /// Remove the current element from the list.
642 pub fn remove(self) -> ListArc<T, ID> {
643 // SAFETY: The `current` pointer always points at a member of the list.
644 unsafe { self.list.remove_internal(self.current) }
645 }
646}
647
648impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for Iter<'a, T, ID> {}
649
650impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for &'a List<T, ID> {
651 type IntoIter = Iter<'a, T, ID>;
652 type Item = ArcBorrow<'a, T>;
653
654 fn into_iter(self) -> Iter<'a, T, ID> {
655 self.iter()
656 }
657}
658
659/// An owning iterator into a [`List`].
660pub struct IntoIter<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
661 list: List<T, ID>,
662}
663
664impl<T: ?Sized + ListItem<ID>, const ID: u64> Iterator for IntoIter<T, ID> {
665 type Item = ListArc<T, ID>;
666
667 fn next(&mut self) -> Option<ListArc<T, ID>> {
668 self.list.pop_front()
669 }
670}
671
672impl<T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for IntoIter<T, ID> {}
673
674impl<T: ?Sized + ListItem<ID>, const ID: u64> DoubleEndedIterator for IntoIter<T, ID> {
675 fn next_back(&mut self) -> Option<ListArc<T, ID>> {
676 self.list.pop_back()
677 }
678}
679
680impl<T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for List<T, ID> {
681 type IntoIter = IntoIter<T, ID>;
682 type Item = ListArc<T, ID>;
683
684 fn into_iter(self) -> IntoIter<T, ID> {
685 IntoIter { list: self }
686 }
687}