1 // SPDX-License-Identifier: GPL-2.0 2 3 // Copyright (C) 2024 Google LLC. 4 5 //! A linked list implementation. 6 7 use crate::init::PinInit; 8 use crate::sync::ArcBorrow; 9 use crate::types::Opaque; 10 use core::iter::{DoubleEndedIterator, FusedIterator}; 11 use core::marker::PhantomData; 12 use core::ptr; 13 14 mod impl_list_item_mod; 15 pub use self::impl_list_item_mod::{ 16 impl_has_list_links, impl_has_list_links_self_ptr, impl_list_item, HasListLinks, HasSelfPtr, 17 }; 18 19 mod arc; 20 pub use self::arc::{impl_list_arc_safe, AtomicTracker, ListArc, ListArcSafe, TryNewListArc}; 21 22 mod arc_field; 23 pub 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. 38 pub 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. 45 unsafe impl<T, const ID: u64> Send for List<T, ID> 46 where 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. 53 unsafe impl<T, const ID: u64> Sync for List<T, ID> 54 where 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 68 pub 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)] 135 struct 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)] 146 pub 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`. 155 unsafe 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. 158 unsafe impl<const ID: u64> Sync for ListLinks<ID> {} 159 160 impl<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)] 195 pub 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. 206 unsafe 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. 212 unsafe impl<T: ?Sized + Sync, const ID: u64> Sync for ListLinksSelfPtr<T, ID> {} 213 214 impl<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 234 impl<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 518 impl<T: ?Sized + ListItem<ID>, const ID: u64> Default for List<T, ID> { 519 fn default() -> Self { 520 List::new() 521 } 522 } 523 524 impl<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)] 540 pub 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 546 impl<'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`. 585 pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> { 586 current: *mut ListLinksFields, 587 list: &'a mut List<T, ID>, 588 } 589 590 impl<'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 648 impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for Iter<'a, T, ID> {} 649 650 impl<'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`]. 660 pub struct IntoIter<T: ?Sized + ListItem<ID>, const ID: u64 = 0> { 661 list: List<T, ID>, 662 } 663 664 impl<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 672 impl<T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for IntoIter<T, ID> {} 673 674 impl<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 680 impl<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 } 688