1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
// SPDX-License-Identifier: GPL-2.0

//! Intrusive circular doubly-linked lists.
//!
//! Copied from linux/rust/kernel/unsafe_list.rs.
//!
//! We don't use the C version for two main reasons:
//! - Next/prev pointers do not support `?Sized` types, so wouldn't be able to have a list of, for
//!   example, `dyn Trait`.
//! - It would require the list head to be pinned (in addition to the list entries).

use core::{cell::UnsafeCell, iter, marker::PhantomPinned, mem::MaybeUninit, ptr::NonNull};

/// An intrusive circular doubly-linked list.
///
/// Membership of elements of the list must be tracked by the owner of the list.
///
/// While elements of the list must remain pinned while in the list, the list itself does not
/// require pinning. In other words, users are allowed to move instances of [`List`].
///
/// # Invariants
///
/// The links of an entry are wrapped in [`UnsafeCell`] and they are acessible when the list itself
/// is. For example, when a thread has a mutable reference to a list, it may also safely get
/// mutable references to the links of the elements in the list.
///
/// The links of an entry are also wrapped in [`MaybeUninit`] and they are initialised when they
/// are present in a list. Otherwise they are uninitialised.
///
/// # Examples
///
/// ```
/// # use linked_list::unsafe_list::{Adapter, Links, List};
///
/// struct Example {
///     v: usize,
///     links: Links<Example>,
/// }
///
/// // SAFETY: This adapter is the only one that uses `Example::links`.
/// unsafe impl Adapter for Example {
///     type EntryType = Self;
///     fn to_links(obj: &Self) -> &Links<Self> {
///         &obj.links
///     }
/// }
///
/// let a = Example {
///     v: 0,
///     links: Links::new(),
/// };
/// let b = Example {
///     v: 1,
///     links: Links::new(),
/// };
///
/// let mut list = List::<Example>::new();
/// assert!(list.is_empty());
///
/// // SAFETY: `a` was declared above, it's not in any lists yet, is never moved, and outlives the
/// // list.
/// unsafe { list.push_back(&a) };
///
/// // SAFETY: `b` was declared above, it's not in any lists yet, is never moved, and outlives the
/// // list.
/// unsafe { list.push_back(&b) };
///
/// assert!(core::ptr::eq(&a, list.front().unwrap().as_ptr()));
/// assert!(core::ptr::eq(&b, list.back().unwrap().as_ptr()));
///
/// for (i, e) in list.iter().enumerate() {
///     assert_eq!(i, e.v);
/// }
///
/// for e in &list {
///     println!("{}", e.v);
/// }
///
/// // SAFETY: `b` was added to the list above and wasn't removed yet.
/// unsafe { list.remove(&b) };
///
/// assert!(core::ptr::eq(&a, list.front().unwrap().as_ptr()));
/// assert!(core::ptr::eq(&a, list.back().unwrap().as_ptr()));
/// ```
pub struct List<A: Adapter + ?Sized> {
    first: Option<NonNull<A::EntryType>>,
}

// SAFETY: The list is itself can be safely sent to other threads but we restrict it to being `Send`
// only when its entries are also `Send`.
unsafe impl<A: Adapter + ?Sized> Send for List<A> where A::EntryType: Send {}

// SAFETY: The list is itself usable from other threads via references but we restrict it to being
// `Sync` only when its entries are also `Sync`.
unsafe impl<A: Adapter + ?Sized> Sync for List<A> where A::EntryType: Sync {}

impl<A: Adapter + ?Sized> List<A> {
    /// Constructs a new empty list.
    pub const fn new() -> Self {
        Self { first: None }
    }

    /// Determines if the list is empty.
    pub const fn is_empty(&self) -> bool {
        self.first.is_none()
    }

    /// Inserts the only entry to a list.
    ///
    /// This must only be called when the list is empty.
    pub fn insert_only_entry(&mut self, obj: &A::EntryType) {
        let obj_ptr = NonNull::from(obj);

        // SAFETY: We have mutable access to the list, so we also have access to the entry
        // we're about to insert (and it's not in any other lists per the function safety
        // requirements).
        let obj_inner = unsafe { &mut *A::to_links(obj).0.get() };

        // INVARIANTS: All fields of the links of the newly-inserted object are initialised
        // below.
        obj_inner.write(LinksInner {
            next: obj_ptr,
            prev: obj_ptr,
            _pin: PhantomPinned,
        });
        self.first = Some(obj_ptr);
    }

    /// Adds the given object to the end of the list.
    ///
    /// # Safety
    ///
    /// Callers must ensure that:
    /// - The object is not currently in any lists.
    /// - The object remains alive until it is removed from the list.
    /// - The object is not moved until it is removed from the list.
    pub unsafe fn push_back(&mut self, obj: &A::EntryType) {
        if let Some(first) = self.first {
            // SAFETY: The previous entry to the first one is necessarily present in the list (it
            // may in fact be the first entry itself as this is a circular list). The safety
            // requirements of this function regarding `obj` satisfy those of `insert_after`.
            unsafe { self.insert_after(self.inner_ref(first).prev, obj) };
        } else {
            self.insert_only_entry(obj);
        }
    }

    /// Adds the given object to the beginning of the list.
    ///
    /// # Safety
    ///
    /// Callers must ensure that:
    /// - The object is not currently in any lists.
    /// - The object remains alive until it is removed from the list.
    /// - The object is not moved until it is removed from the list.
    pub unsafe fn push_front(&mut self, obj: &A::EntryType) {
        if let Some(first) = self.first {
            // SAFETY: The safety requirements of this function regarding `obj` satisfy those of
            // `insert_before`. Additionally, `first` is in the list.
            unsafe { self.insert_before(first, obj) };
        } else {
            self.insert_only_entry(obj);
        }
    }

    /// Removes the given object from the list.
    ///
    /// # Safety
    ///
    /// The object must be in the list. In other words, the object must have previously been
    /// inserted into this list and not removed yet.
    pub unsafe fn remove(&mut self, entry: &A::EntryType) {
        // SAFETY: Per the function safety requirements, `entry` is in the list.
        let inner = unsafe { self.inner_ref(NonNull::from(entry)) };
        let next = inner.next;
        let prev = inner.prev;

        // SAFETY: We have mutable access to the list, so we also have access to the entry we're
        // about to remove (which we know is in the list per the function safety requirements).
        let inner = unsafe { &mut *A::to_links(entry).0.get() };

        // SAFETY: Since the entry was in the list, it was initialised.
        unsafe { inner.assume_init_drop() };

        if core::ptr::eq(next.as_ptr(), entry) {
            // Removing the only element.
            self.first = None;
        } else {
            // SAFETY: `prev` is in the list because it is pointed at by the entry being removed.
            unsafe { self.inner(prev).next = next };
            // SAFETY: `next` is in the list because it is pointed at by the entry being removed.
            unsafe { self.inner(next).prev = prev };

            if core::ptr::eq(self.first.unwrap().as_ptr(), entry) {
                // Update the pointer to the first element as we're removing it.
                self.first = Some(next);
            }
        }
    }

    /// Adds the given object after another object already in the list.
    ///
    /// # Safety
    ///
    /// Callers must ensure that:
    /// - The existing object is currently in the list.
    /// - The new object is not currently in any lists.
    /// - The new object remains alive until it is removed from the list.
    /// - The new object is not moved until it is removed from the list.
    pub unsafe fn insert_after(&mut self, existing: NonNull<A::EntryType>, new: &A::EntryType) {
        // SAFETY: We have mutable access to the list, so we also have access to the entry we're
        // about to insert (and it's not in any other lists per the function safety requirements).
        let new_inner = unsafe { &mut *A::to_links(new).0.get() };

        // SAFETY: Per the function safety requirements, `existing` is in the list.
        let existing_inner = unsafe { self.inner(existing) };
        let next = existing_inner.next;

        // INVARIANTS: All fields of the links of the newly-inserted object are initialised below.
        new_inner.write(LinksInner {
            next,
            prev: existing,
            _pin: PhantomPinned,
        });

        existing_inner.next = NonNull::from(new);

        // SAFETY: `next` is in the list because it's pointed at by the existing entry.
        unsafe { self.inner(next).prev = NonNull::from(new) };
    }

    /// Adds the given object before another object already in the list.
    ///
    /// # Safety
    ///
    /// Callers must ensure that:
    /// - The existing object is currently in the list.
    /// - The new object is not currently in any lists.
    /// - The new object remains alive until it is removed from the list.
    /// - The new object is not moved until it is removed from the list.
    pub unsafe fn insert_before(&mut self, existing: NonNull<A::EntryType>, new: &A::EntryType) {
        // SAFETY: The safety requirements of this function satisfy those of `insert_after`.
        unsafe { self.insert_after(self.inner_ref(existing).prev, new) };

        if self.first.unwrap() == existing {
            // Update the pointer to the first element as we're inserting before it.
            self.first = Some(NonNull::from(new));
        }
    }

    /// Returns the first element of the list, if one exists.
    pub fn front(&self) -> Option<NonNull<A::EntryType>> {
        self.first
    }

    /// Returns the last element of the list, if one exists.
    pub fn back(&self) -> Option<NonNull<A::EntryType>> {
        // SAFETY: Having a pointer to it guarantees that the object is in the list.
        self.first.map(|f| unsafe { self.inner_ref(f).prev })
    }

    /// Returns an iterator for the list starting at the first entry.
    pub fn iter(&self) -> Iterator<'_, A> {
        Iterator::new(self.cursor_front())
    }

    /// Returns an iterator for the list starting at the last entry.
    pub fn iter_back(&self) -> impl iter::DoubleEndedIterator<Item = &'_ A::EntryType> {
        Iterator::new(self.cursor_back())
    }

    /// Returns a cursor starting on the first (front) element of the list.
    pub fn cursor_front(&self) -> Cursor<'_, A> {
        // SAFETY: `front` is in the list (or is `None`) because we've read it from the list head
        // and the list cannot have changed because we hold a shared reference to it.
        unsafe { Cursor::new(self, self.front()) }
    }

    /// Returns a cursor starting on the last (back) element of the list.
    pub fn cursor_back(&self) -> Cursor<'_, A> {
        // SAFETY: `back` is in the list (or is `None`) because we've read it from the list head
        // and the list cannot have changed because we hold a shared reference to it.
        unsafe { Cursor::new(self, self.back()) }
    }

    /// Returns a mutable reference to the links of a given object.
    ///
    /// # Safety
    ///
    /// Callers must ensure that the element is in the list.
    unsafe fn inner(&mut self, ptr: NonNull<A::EntryType>) -> &mut LinksInner<A::EntryType> {
        // SAFETY: The safety requirements guarantee that we the links are initialised because
        // that's part of the type invariants. Additionally, the type invariants also guarantee
        // that having a mutable reference to the list guarantees that the links are mutably
        // accessible as well.
        unsafe { (*A::to_links(ptr.as_ref()).0.get()).assume_init_mut() }
    }

    /// Returns a shared reference to the links of a given object.
    ///
    /// # Safety
    ///
    /// Callers must ensure that the element is in the list.
    unsafe fn inner_ref(&self, ptr: NonNull<A::EntryType>) -> &LinksInner<A::EntryType> {
        // SAFETY: The safety requirements guarantee that we the links are initialised because
        // that's part of the type invariants. Additionally, the type invariants also guarantee
        // that having a shared reference to the list guarantees that the links are accessible in
        // shared mode as well.
        unsafe { (*A::to_links(ptr.as_ref()).0.get()).assume_init_ref() }
    }
}

impl<'a, A: Adapter + ?Sized> iter::IntoIterator for &'a List<A> {
    type Item = &'a A::EntryType;
    type IntoIter = Iterator<'a, A>;
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

/// An iterator for the linked list.
pub struct Iterator<'a, A: Adapter + ?Sized> {
    cursor: Cursor<'a, A>,
}

impl<'a, A: Adapter + ?Sized> Iterator<'a, A> {
    fn new(cursor: Cursor<'a, A>) -> Self {
        Self { cursor }
    }
}

impl<'a, A: Adapter + ?Sized> iter::Iterator for Iterator<'a, A> {
    type Item = &'a A::EntryType;

    fn next(&mut self) -> Option<Self::Item> {
        let ret = self.cursor.current()?;
        self.cursor.move_next();
        Some(ret)
    }
}

impl<A: Adapter + ?Sized> iter::DoubleEndedIterator for Iterator<'_, A> {
    fn next_back(&mut self) -> Option<Self::Item> {
        let ret = self.cursor.current()?;
        self.cursor.move_prev();
        Some(ret)
    }
}

/// A linked-list adapter.
///
/// It is a separate type (as opposed to implemented by the type of the elements of the list)
/// so that a given type can be inserted into multiple lists at the same time; in such cases, each
/// list needs its own adapter that returns a different pointer to links.
///
/// It may, however, be implemented by the type itself to be inserted into lists, which makes it
/// more readable.
///
/// # Safety
///
/// Implementers must ensure that the links returned by [`Adapter::to_links`] are unique to the
/// adapter. That is, different adapters must return different links for a given object.
///
/// The reason for this requirement is to avoid confusion that may lead to UB. In particular, if
/// two adapters were to use the same links, a user may have two lists (one for each adapter) and
/// try to insert the same object into both at the same time; although this clearly violates the
/// list safety requirements (e.g., those in [`List::push_back`]), for users to notice it, they'd
/// have to dig into the details of the two adapters.
///
/// By imposing the requirement on the adapter, we make it easier for users to check compliance
/// with the requirements when using the list.
///
/// # Examples
///
/// ```
/// # use linked_list::unsafe_list::{Adapter, Links, List};
///
/// struct Example {
///     a: u32,
///     b: u32,
///     links1: Links<Example>,
///     links2: Links<Example>,
/// }
///
/// // SAFETY: This adapter is the only one that uses `Example::links1`.
/// unsafe impl Adapter for Example {
///     type EntryType = Self;
///     fn to_links(obj: &Self) -> &Links<Self> {
///         &obj.links1
///     }
/// }
///
/// struct ExampleAdapter;
///
/// // SAFETY: This adapter is the only one that uses `Example::links2`.
/// unsafe impl Adapter for ExampleAdapter {
///     type EntryType = Example;
///     fn to_links(obj: &Example) -> &Links<Example> {
///         &obj.links2
///     }
/// }
///
/// static LIST1: List<Example> = List::new();
/// static LIST2: List<ExampleAdapter> = List::new();
/// ```
pub unsafe trait Adapter {
    /// The type of the enties in the list.
    type EntryType: ?Sized;

    /// Retrieves the linked list links for the given object.
    fn to_links(obj: &Self::EntryType) -> &Links<Self::EntryType>;
}

struct LinksInner<T: ?Sized> {
    next: NonNull<T>,
    prev: NonNull<T>,
    _pin: PhantomPinned,
}

/// Links of a linked list.
///
/// List entries need one of these per concurrent list.
pub struct Links<T: ?Sized>(UnsafeCell<MaybeUninit<LinksInner<T>>>);

// SAFETY: `Links` can be safely sent to other threads but we restrict it to being `Send` only when
// the list entries it points to are also `Send`.
unsafe impl<T: ?Sized> Send for Links<T> {}

// SAFETY: `Links` is usable from other threads via references but we restrict it to being `Sync`
// only when the list entries it points to are also `Sync`.
unsafe impl<T: ?Sized> Sync for Links<T> {}

impl<T: ?Sized> Links<T> {
    /// Constructs a new instance of the linked-list links.
    pub const fn new() -> Self {
        Self(UnsafeCell::new(MaybeUninit::uninit()))
    }
}

pub(crate) struct CommonCursor<A: Adapter + ?Sized> {
    pub(crate) cur: Option<NonNull<A::EntryType>>,
}

impl<A: Adapter + ?Sized> CommonCursor<A> {
    pub(crate) fn new(cur: Option<NonNull<A::EntryType>>) -> Self {
        Self { cur }
    }

    /// Moves the cursor to the next entry of the list.
    ///
    /// # Safety
    ///
    /// Callers must ensure that the cursor is either [`None`] or points to an entry that is in
    /// `list`.
    pub(crate) unsafe fn move_next(&mut self, list: &List<A>) {
        match self.cur.take() {
            None => self.cur = list.first,
            Some(cur) => {
                if let Some(head) = list.first {
                    // SAFETY: Per the function safety requirements, `cur` is in the list.
                    let links = unsafe { list.inner_ref(cur) };
                    if links.next != head {
                        self.cur = Some(links.next);
                    }
                }
            }
        }
    }

    /// Moves the cursor to the previous entry of the list.
    ///
    /// # Safety
    ///
    /// Callers must ensure that the cursor is either [`None`] or points to an entry that is in
    /// `list`.
    pub(crate) unsafe fn move_prev(&mut self, list: &List<A>) {
        match list.first {
            None => self.cur = None,
            Some(head) => {
                let next = match self.cur.take() {
                    None => head,
                    Some(cur) => {
                        if cur == head {
                            return;
                        }
                        cur
                    }
                };
                // SAFETY: `next` is either `head` or `cur`. The former is in the list because it's
                // its head; the latter is in the list per the function safety requirements.
                self.cur = Some(unsafe { list.inner_ref(next) }.prev);
            }
        }
    }
}

/// A list cursor that allows traversing a linked list and inspecting elements.
pub struct Cursor<'a, A: Adapter + ?Sized> {
    cursor: CommonCursor<A>,
    list: &'a List<A>,
}

impl<'a, A: Adapter + ?Sized> Cursor<'a, A> {
    /// Creates a new cursor.
    ///
    /// # Safety
    ///
    /// Callers must ensure that `cur` is either [`None`] or points to an entry in `list`.
    pub(crate) unsafe fn new(list: &'a List<A>, cur: Option<NonNull<A::EntryType>>) -> Self {
        Self {
            list,
            cursor: CommonCursor::new(cur),
        }
    }

    /// Returns the element the cursor is currently positioned on.
    pub fn current(&self) -> Option<&'a A::EntryType> {
        let cur = self.cursor.cur?;
        // SAFETY: `cursor` starts off in the list and only changes within the list. Additionally,
        // the list cannot change because we hold a shared reference to it, so the cursor is always
        // within the list.
        Some(unsafe { cur.as_ref() })
    }

    /// Moves the cursor to the next element.
    pub fn move_next(&mut self) {
        // SAFETY: `cursor` starts off in the list and only changes within the list. Additionally,
        // the list cannot change because we hold a shared reference to it, so the cursor is always
        // within the list.
        unsafe { self.cursor.move_next(self.list) };
    }

    /// Moves the cursor to the previous element.
    pub fn move_prev(&mut self) {
        // SAFETY: `cursor` starts off in the list and only changes within the list. Additionally,
        // the list cannot change because we hold a shared reference to it, so the cursor is always
        // within the list.
        unsafe { self.cursor.move_prev(self.list) };
    }
}

#[cfg(test)]
mod tests {
    extern crate alloc;
    use alloc::{boxed::Box, vec::Vec};
    use core::ptr::NonNull;

    struct Example {
        links: super::Links<Self>,
    }

    // SAFETY: This is the only adapter that uses `Example::links`.
    unsafe impl super::Adapter for Example {
        type EntryType = Self;
        fn to_links(obj: &Self) -> &super::Links<Self> {
            &obj.links
        }
    }

    fn build_vector(size: usize) -> Vec<Box<Example>> {
        let mut v = Vec::new();
        v.reserve(size);
        for _ in 0..size {
            v.push(Box::new(Example {
                links: super::Links::new(),
            }));
        }
        v
    }

    #[track_caller]
    fn assert_list_contents(v: &[Box<Example>], list: &super::List<Example>) {
        let n = v.len();

        // Assert that the list is ok going forward.
        let mut count = 0;
        for (i, e) in list.iter().enumerate() {
            assert!(core::ptr::eq(e, &*v[i]));
            count += 1;
        }
        assert_eq!(count, n);

        // Assert that the list is ok going backwards.
        let mut count = 0;
        for (i, e) in list.iter_back().rev().enumerate() {
            assert!(core::ptr::eq(e, &*v[n - 1 - i]));
            count += 1;
        }
        assert_eq!(count, n);
    }

    #[track_caller]
    fn test_each_element(
        min_len: usize,
        max_len: usize,
        test: impl Fn(&mut Vec<Box<Example>>, &mut super::List<Example>, usize, Box<Example>),
    ) {
        for n in min_len..=max_len {
            for i in 0..n {
                let extra = Box::new(Example {
                    links: super::Links::new(),
                });
                let mut v = build_vector(n);
                let mut list = super::List::<Example>::new();

                // Build list.
                for j in 0..n {
                    // SAFETY: The entry was allocated above, it's not in any lists yet, is never
                    // moved, and outlives the list.
                    unsafe { list.push_back(&v[j]) };
                }

                // Call the test case.
                test(&mut v, &mut list, i, extra);

                // Check that the list is ok.
                assert_list_contents(&v, &list);
            }
        }
    }

    #[test]
    fn test_push_back() {
        const MAX: usize = 10;
        let v = build_vector(MAX);
        let mut list = super::List::<Example>::new();

        for n in 1..=MAX {
            // SAFETY: The entry was allocated above, it's not in any lists yet, is never moved,
            // and outlives the list.
            unsafe { list.push_back(&v[n - 1]) };
            assert_list_contents(&v[..n], &list);
        }
    }

    #[test]
    fn test_push_front() {
        const MAX: usize = 10;
        let v = build_vector(MAX);
        let mut list = super::List::<Example>::new();

        for n in 1..=MAX {
            // SAFETY: The entry was allocated above, it's not in any lists yet, is never moved,
            // and outlives the list.
            unsafe { list.push_front(&v[MAX - n]) };
            assert_list_contents(&v[MAX - n..], &list);
        }
    }

    #[test]
    fn test_one_removal() {
        test_each_element(1, 10, |v, list, i, _| {
            // Remove the i-th element.
            // SAFETY: The i-th element was added to the list above, and wasn't removed yet.
            unsafe { list.remove(&v[i]) };
            v.remove(i);
        });
    }

    #[test]
    fn test_one_insert_after() {
        test_each_element(1, 10, |v, list, i, extra| {
            // Insert after the i-th element.
            // SAFETY: The i-th element was added to the list above, and wasn't removed yet.
            // Additionally, the new element isn't in any list yet, isn't moved, and outlives
            // the list.
            unsafe { list.insert_after(NonNull::from(&*v[i]), &*extra) };
            v.insert(i + 1, extra);
        });
    }

    #[test]
    fn test_one_insert_before() {
        test_each_element(1, 10, |v, list, i, extra| {
            // Insert before the i-th element.
            // SAFETY: The i-th element was added to the list above, and wasn't removed yet.
            // Additionally, the new element isn't in any list yet, isn't moved, and outlives
            // the list.
            unsafe { list.insert_before(NonNull::from(&*v[i]), &*extra) };
            v.insert(i, extra);
        });
    }
}