687 lines · rust
1// SPDX-License-Identifier: GPL-2.02 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 can28/// only have one `ListArc` (for each pair of prev/next pointers), this ensures that the same29/// prev/next pointers are not used for several linked lists.30///31/// # Invariants32///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 has37/// 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 same44// type of access to the `ListArc<T, ID>` elements.45unsafe impl<T, const ID: u64> Send for List<T, ID>46where47 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 same52// type of access to the `ListArc<T, ID>` elements.53unsafe impl<T, const ID: u64> Sync for List<T, ID>54where55 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/// # Safety63///64/// Implementers must ensure that they provide the guarantees documented on methods provided by65/// this trait.66///67/// [`ListArc<Self>`]: ListArc68pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {69 /// Views the [`ListLinks`] for this value.70 ///71 /// # Guarantees72 ///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 by75 /// 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 /// # Safety80 ///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 /// # Guarantees89 ///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 /// # Safety94 ///95 /// * The provided pointer must originate from the most recent call to `prepare_to_insert`, or96 /// from a call to `view_links` that happened after the most recent call to97 /// `prepare_to_insert`.98 /// * Since the most recent call to `prepare_to_insert`, the `post_remove` method must not have99 /// 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 /// # Guarantees105 ///106 /// The caller is granted exclusive access to the returned [`ListLinks`] until `post_remove` is107 /// called.108 ///109 /// # Safety110 ///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 been115 /// called after this call to `prepare_to_insert`.116 ///117 /// [`Arc`]: crate::sync::Arc118 unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<ID>;119 120 /// This undoes a previous call to `prepare_to_insert`.121 ///122 /// # Guarantees123 ///124 /// The returned pointer is the pointer that was originally passed to `prepare_to_insert`.125 ///126 /// # Safety127 ///128 /// The provided pointer must be the pointer returned by the most recent call to129 /// `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/// # Invariants143///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 linked148 // list.149 inner: Opaque<ListLinksFields>,150}151 152// SAFETY: The only way to access/modify the pointers inside of `ListLinks<ID>` is via holding the153// associated `ListArc<T, ID>`. Since that type correctly implements `Send`, it is impossible to154// 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's157// 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 will164 // 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 /// # Safety174 ///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 /// # Safety183 ///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, and201 // `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, since211// `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 will221 // 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 after254 // 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`, which257 // 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 that273 // 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 us276 // 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`, which297 // 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 us314 // 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 /// # Safety354 ///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 let mut item = unsafe { ListLinks::fields(T::view_links(item)) };358 // SAFETY: The user provided a reference, and reference are never dangling.359 //360 // As for why this is not a data race, there are two cases:361 //362 // * If `item` is not in any list, then these fields are read-only and null.363 // * If `item` is in this list, then we have exclusive access to these fields since we364 // have a mutable reference to the list.365 //366 // In either case, there's no race.367 let ListLinksFields { next, prev } = unsafe { *item };368 369 debug_assert_eq!(next.is_null(), prev.is_null());370 if !next.is_null() {371 // This is really a no-op, but this ensures that `item` is a raw pointer that was372 // obtained without going through a pointer->reference->pointer conversion roundtrip.373 // This ensures that the list is valid under the more restrictive strict provenance374 // ruleset.375 //376 // SAFETY: We just checked that `next` is not null, and it's not dangling by the377 // list invariants.378 unsafe {379 debug_assert_eq!(item, (*next).prev);380 item = (*next).prev;381 }382 383 // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it384 // is in this list. The pointers are in the right order.385 Some(unsafe { self.remove_internal_inner(item, next, prev) })386 } else {387 None388 }389 }390 391 /// Removes the provided item from the list.392 ///393 /// # Safety394 ///395 /// `item` must point at an item in this list.396 unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> ListArc<T, ID> {397 // SAFETY: The caller promises that this pointer is not dangling, and there's no data race398 // since we have a mutable reference to the list containing `item`.399 let ListLinksFields { next, prev } = unsafe { *item };400 // SAFETY: The pointers are ok and in the right order.401 unsafe { self.remove_internal_inner(item, next, prev) }402 }403 404 /// Removes the provided item from the list.405 ///406 /// # Safety407 ///408 /// The `item` pointer must point at an item in this list, and we must have `(*item).next ==409 /// next` and `(*item).prev == prev`.410 unsafe fn remove_internal_inner(411 &mut self,412 item: *mut ListLinksFields,413 next: *mut ListLinksFields,414 prev: *mut ListLinksFields,415 ) -> ListArc<T, ID> {416 // SAFETY: We have exclusive access to the pointers of items in the list, and the prev/next417 // pointers are always valid for items in a list.418 //419 // INVARIANT: There are three cases:420 // * If the list has at least three items, then after removing the item, `prev` and `next`421 // will be next to each other.422 // * If the list has two items, then the remaining item will point at itself.423 // * If the list has one item, then `next == prev == item`, so these writes have no424 // effect. The list remains unchanged and `item` is still in the list for now.425 unsafe {426 (*next).prev = prev;427 (*prev).next = next;428 }429 // SAFETY: We have exclusive access to items in the list.430 // INVARIANT: `item` is being removed, so the pointers should be null.431 unsafe {432 (*item).prev = ptr::null_mut();433 (*item).next = ptr::null_mut();434 }435 // INVARIANT: There are three cases:436 // * If `item` was not the first item, then `self.first` should remain unchanged.437 // * If `item` was the first item and there is another item, then we just updated438 // `prev->next` to `next`, which is the new first item, and setting `item->next` to null439 // did not modify `prev->next`.440 // * If `item` was the only item in the list, then `prev == item`, and we just set441 // `item->next` to null, so this correctly sets `first` to null now that the list is442 // empty.443 if self.first == item {444 // SAFETY: The `prev` pointer is the value that `item->prev` had when it was in this445 // list, so it must be valid. There is no race since `prev` is still in the list and we446 // still have exclusive access to the list.447 self.first = unsafe { (*prev).next };448 }449 450 // SAFETY: `item` used to be in the list, so it is dereferenceable by the type invariants451 // of `List`.452 let list_links = unsafe { ListLinks::from_fields(item) };453 // SAFETY: Any pointer in the list originates from a `prepare_to_insert` call.454 let raw_item = unsafe { T::post_remove(list_links) };455 // SAFETY: The above call to `post_remove` guarantees that we can recreate the `ListArc`.456 unsafe { ListArc::from_raw(raw_item) }457 }458 459 /// Moves all items from `other` into `self`.460 ///461 /// The items of `other` are added to the back of `self`, so the last item of `other` becomes462 /// the last item of `self`.463 pub fn push_all_back(&mut self, other: &mut List<T, ID>) {464 // First, we insert the elements into `self`. At the end, we make `other` empty.465 if self.is_empty() {466 // INVARIANT: All of the elements in `other` become elements of `self`.467 self.first = other.first;468 } else if !other.is_empty() {469 let other_first = other.first;470 // SAFETY: The other list is not empty, so this pointer is valid.471 let other_last = unsafe { (*other_first).prev };472 let self_first = self.first;473 // SAFETY: The self list is not empty, so this pointer is valid.474 let self_last = unsafe { (*self_first).prev };475 476 // SAFETY: We have exclusive access to both lists, so we can update the pointers.477 // INVARIANT: This correctly sets the pointers to merge both lists. We do not need to478 // update `self.first` because the first element of `self` does not change.479 unsafe {480 (*self_first).prev = other_last;481 (*other_last).next = self_first;482 (*self_last).next = other_first;483 (*other_first).prev = self_last;484 }485 }486 487 // INVARIANT: The other list is now empty, so update its pointer.488 other.first = ptr::null_mut();489 }490 491 /// Returns a cursor to the first element of the list.492 ///493 /// If the list is empty, this returns `None`.494 pub fn cursor_front(&mut self) -> Option<Cursor<'_, T, ID>> {495 if self.first.is_null() {496 None497 } else {498 Some(Cursor {499 current: self.first,500 list: self,501 })502 }503 }504 505 /// Creates an iterator over the list.506 pub fn iter(&self) -> Iter<'_, T, ID> {507 // INVARIANT: If the list is empty, both pointers are null. Otherwise, both pointers point508 // at the first element of the same list.509 Iter {510 current: self.first,511 stop: self.first,512 _ty: PhantomData,513 }514 }515}516 517impl<T: ?Sized + ListItem<ID>, const ID: u64> Default for List<T, ID> {518 fn default() -> Self {519 List::new()520 }521}522 523impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> {524 fn drop(&mut self) {525 while let Some(item) = self.pop_front() {526 drop(item);527 }528 }529}530 531/// An iterator over a [`List`].532///533/// # Invariants534///535/// * There must be a [`List`] that is immutably borrowed for the duration of `'a`.536/// * The `current` pointer is null or points at a value in that [`List`].537/// * The `stop` pointer is equal to the `first` field of that [`List`].538#[derive(Clone)]539pub struct Iter<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {540 current: *mut ListLinksFields,541 stop: *mut ListLinksFields,542 _ty: PhantomData<&'a ListArc<T, ID>>,543}544 545impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Iterator for Iter<'a, T, ID> {546 type Item = ArcBorrow<'a, T>;547 548 fn next(&mut self) -> Option<ArcBorrow<'a, T>> {549 if self.current.is_null() {550 return None;551 }552 553 let current = self.current;554 555 // SAFETY: We just checked that `current` is not null, so it is in a list, and hence not556 // dangling. There's no race because the iterator holds an immutable borrow to the list.557 let next = unsafe { (*current).next };558 // INVARIANT: If `current` was the last element of the list, then this updates it to null.559 // Otherwise, we update it to the next element.560 self.current = if next != self.stop {561 next562 } else {563 ptr::null_mut()564 };565 566 // SAFETY: The `current` pointer points at a value in the list.567 let item = unsafe { T::view_value(ListLinks::from_fields(current)) };568 // SAFETY:569 // * All values in a list are stored in an `Arc`.570 // * The value cannot be removed from the list for the duration of the lifetime annotated571 // on the returned `ArcBorrow`, because removing it from the list would require mutable572 // access to the list. However, the `ArcBorrow` is annotated with the iterator's573 // lifetime, and the list is immutably borrowed for that lifetime.574 // * Values in a list never have a `UniqueArc` reference.575 Some(unsafe { ArcBorrow::from_raw(item) })576 }577}578 579/// A cursor into a [`List`].580///581/// # Invariants582///583/// The `current` pointer points a value in `list`.584pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {585 current: *mut ListLinksFields,586 list: &'a mut List<T, ID>,587}588 589impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Cursor<'a, T, ID> {590 /// Access the current element of this cursor.591 pub fn current(&self) -> ArcBorrow<'_, T> {592 // SAFETY: The `current` pointer points a value in the list.593 let me = unsafe { T::view_value(ListLinks::from_fields(self.current)) };594 // SAFETY:595 // * All values in a list are stored in an `Arc`.596 // * The value cannot be removed from the list for the duration of the lifetime annotated597 // on the returned `ArcBorrow`, because removing it from the list would require mutable598 // access to the cursor or the list. However, the `ArcBorrow` holds an immutable borrow599 // on the cursor, which in turn holds a mutable borrow on the list, so any such600 // mutable access requires first releasing the immutable borrow on the cursor.601 // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc`602 // reference, and `UniqueArc` references must be unique.603 unsafe { ArcBorrow::from_raw(me) }604 }605 606 /// Move the cursor to the next element.607 pub fn next(self) -> Option<Cursor<'a, T, ID>> {608 // SAFETY: The `current` field is always in a list.609 let next = unsafe { (*self.current).next };610 611 if next == self.list.first {612 None613 } else {614 // INVARIANT: Since `self.current` is in the `list`, its `next` pointer is also in the615 // `list`.616 Some(Cursor {617 current: next,618 list: self.list,619 })620 }621 }622 623 /// Move the cursor to the previous element.624 pub fn prev(self) -> Option<Cursor<'a, T, ID>> {625 // SAFETY: The `current` field is always in a list.626 let prev = unsafe { (*self.current).prev };627 628 if self.current == self.list.first {629 None630 } else {631 // INVARIANT: Since `self.current` is in the `list`, its `prev` pointer is also in the632 // `list`.633 Some(Cursor {634 current: prev,635 list: self.list,636 })637 }638 }639 640 /// Remove the current element from the list.641 pub fn remove(self) -> ListArc<T, ID> {642 // SAFETY: The `current` pointer always points at a member of the list.643 unsafe { self.list.remove_internal(self.current) }644 }645}646 647impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for Iter<'a, T, ID> {}648 649impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for &'a List<T, ID> {650 type IntoIter = Iter<'a, T, ID>;651 type Item = ArcBorrow<'a, T>;652 653 fn into_iter(self) -> Iter<'a, T, ID> {654 self.iter()655 }656}657 658/// An owning iterator into a [`List`].659pub struct IntoIter<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {660 list: List<T, ID>,661}662 663impl<T: ?Sized + ListItem<ID>, const ID: u64> Iterator for IntoIter<T, ID> {664 type Item = ListArc<T, ID>;665 666 fn next(&mut self) -> Option<ListArc<T, ID>> {667 self.list.pop_front()668 }669}670 671impl<T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for IntoIter<T, ID> {}672 673impl<T: ?Sized + ListItem<ID>, const ID: u64> DoubleEndedIterator for IntoIter<T, ID> {674 fn next_back(&mut self) -> Option<ListArc<T, ID>> {675 self.list.pop_back()676 }677}678 679impl<T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for List<T, ID> {680 type IntoIter = IntoIter<T, ID>;681 type Item = ListArc<T, ID>;682 683 fn into_iter(self) -> IntoIter<T, ID> {684 IntoIter { list: self }685 }686}687