use super::Linked;
use crate::util::FmtOption;
use core::{
cell::UnsafeCell,
fmt, iter,
marker::PhantomPinned,
mem,
pin::Pin,
ptr::{self, NonNull},
};
#[cfg(test)]
#[cfg(not(loom))]
mod tests;
mod cursor;
pub use self::cursor::{Cursor, CursorMut};
pub struct List<T: Linked<Links<T>> + ?Sized> {
head: Link<T>,
tail: Link<T>,
len: usize,
}
pub struct Links<T: ?Sized> {
inner: UnsafeCell<LinksInner<T>>,
}
pub struct Iter<'list, T: Linked<Links<T>> + ?Sized> {
_list: &'list List<T>,
curr: Link<T>,
curr_back: Link<T>,
len: usize,
}
pub struct IterMut<'list, T: Linked<Links<T>> + ?Sized> {
_list: &'list mut List<T>,
curr: Link<T>,
curr_back: Link<T>,
len: usize,
}
pub struct IntoIter<T: Linked<Links<T>> + ?Sized> {
list: List<T>,
}
pub struct DrainFilter<'list, T, F>
where
F: FnMut(&T) -> bool,
T: Linked<Links<T>> + ?Sized,
{
cursor: CursorMut<'list, T>,
pred: F,
}
type Link<T> = Option<NonNull<T>>;
#[repr(C)]
struct LinksInner<T: ?Sized> {
next: Link<T>,
prev: Link<T>,
_unpin: PhantomPinned,
}
impl<T: Linked<Links<T>> + ?Sized> List<T> {
#[must_use]
pub const fn new() -> List<T> {
List {
head: None,
tail: None,
len: 0,
}
}
pub fn append(&mut self, other: &mut Self) {
let tail = match self.tail {
None => {
debug_assert!(self.is_empty());
mem::swap(self, other);
return;
}
Some(tail) => tail,
};
if let Some((other_head, other_tail, other_len)) = other.take_all() {
unsafe {
T::links(tail).as_mut().set_next(Some(other_head));
T::links(other_head).as_mut().set_prev(Some(tail));
}
self.tail = Some(other_tail);
self.len += other_len;
}
}
pub fn try_split_off(&mut self, at: usize) -> Option<Self> {
let len = self.len();
let split_idx = match at {
at if at == 0 => return Some(mem::replace(self, Self::new())),
at if at == len => return Some(Self::new()),
at if at > len => return None,
at => at - 1,
};
let mut iter = self.iter();
let dist_from_tail = len - 1 - split_idx;
let split_node = if split_idx <= dist_from_tail {
for _ in 0..split_idx {
iter.next();
}
iter.curr
} else {
for _ in 0..dist_from_tail {
iter.next_back();
}
iter.curr_back
};
Some(unsafe { self.split_after_node(split_node, at) })
}
#[track_caller]
#[must_use]
pub fn split_off(&mut self, at: usize) -> Self {
match self.try_split_off(at) {
Some(new_list) => new_list,
None => panic!(
"Cannot split off at a nonexistent index (the index was {} but the len was {})",
at,
self.len()
),
}
}
#[inline]
pub fn is_empty(&self) -> bool {
if self.head.is_none() {
debug_assert!(
self.tail.is_none(),
"inconsistent state: a list had a tail but no head!"
);
debug_assert_eq!(
self.len, 0,
"inconsistent state: a list was empty, but its length was not zero"
);
return true;
}
debug_assert_ne!(
self.len, 0,
"inconsistent state: a list was not empty, but its length was zero"
);
false
}
#[inline]
pub fn len(&self) -> usize {
self.len
}
#[track_caller]
pub fn assert_valid(&self) {
self.assert_valid_named("")
}
#[track_caller]
pub(crate) fn assert_valid_named(&self, name: &str) {
let head = match self.head {
Some(head) => head,
None => {
assert!(
self.tail.is_none(),
"{name}if the linked list's head is null, the tail must also be null"
);
assert_eq!(
self.len, 0,
"{name}if a linked list's head is null, its length must be 0"
);
return;
}
};
assert_ne!(
self.len, 0,
"{name}if a linked list's head is not null, its length must be greater than 0"
);
assert_ne!(
self.tail, None,
"{name}if the linked list has a head, it must also have a tail"
);
let tail = self.tail.unwrap();
let head_links = unsafe { T::links(head) };
let tail_links = unsafe { T::links(tail) };
let head_links = unsafe { head_links.as_ref() };
let tail_links = unsafe { tail_links.as_ref() };
if head == tail {
assert_eq!(
head_links, tail_links,
"{name}if the head and tail nodes are the same, their links must be the same"
);
assert_eq!(
head_links.next(),
None,
"{name}if the linked list has only one node, it must not be linked"
);
assert_eq!(
head_links.prev(),
None,
"{name}if the linked list has only one node, it must not be linked"
);
return;
}
let mut curr = Some(head);
let mut actual_len = 0;
while let Some(node) = curr {
let links = unsafe { T::links(node) };
let links = unsafe { links.as_ref() };
links.assert_valid(head_links, tail_links);
curr = links.next();
actual_len += 1;
}
assert_eq!(
self.len, actual_len,
"{name}linked list's actual length did not match its `len` variable"
);
}
pub fn pop_back(&mut self) -> Option<T::Handle> {
let tail = self.tail?;
self.len -= 1;
unsafe {
let mut tail_links = T::links(tail);
self.tail = tail_links.as_ref().prev();
debug_assert_eq!(
tail_links.as_ref().next(),
None,
"the tail node must not have a next link"
);
if let Some(prev) = tail_links.as_mut().prev() {
T::links(prev).as_mut().set_next(None);
} else {
self.head = None;
}
tail_links.as_mut().unlink();
Some(T::from_ptr(tail))
}
}
pub fn pop_front(&mut self) -> Option<T::Handle> {
let head = self.head?;
self.len -= 1;
unsafe {
let mut head_links = T::links(head);
self.head = head_links.as_ref().next();
if let Some(next) = head_links.as_mut().next() {
T::links(next).as_mut().set_prev(None);
} else {
self.tail = None;
}
head_links.as_mut().unlink();
Some(T::from_ptr(head))
}
}
pub fn push_back(&mut self, item: T::Handle) {
let ptr = T::into_ptr(item);
assert_ne!(self.tail, Some(ptr));
unsafe {
T::links(ptr).as_mut().set_next(None);
T::links(ptr).as_mut().set_prev(self.tail);
if let Some(tail) = self.tail {
T::links(tail).as_mut().set_next(Some(ptr));
}
}
self.tail = Some(ptr);
if self.head.is_none() {
self.head = Some(ptr);
}
self.len += 1;
}
pub fn push_front(&mut self, item: T::Handle) {
let ptr = T::into_ptr(item);
assert_ne!(self.head, Some(ptr));
unsafe {
T::links(ptr).as_mut().set_next(self.head);
T::links(ptr).as_mut().set_prev(None);
if let Some(head) = self.head {
T::links(head).as_mut().set_prev(Some(ptr));
}
}
self.head = Some(ptr);
if self.tail.is_none() {
self.tail = Some(ptr);
}
self.len += 1;
}
#[must_use]
pub fn front(&self) -> Option<Pin<&T>> {
let head = self.head?;
let pin = unsafe {
Pin::new_unchecked(head.as_ref())
};
Some(pin)
}
#[must_use]
pub fn front_mut(&mut self) -> Option<Pin<&mut T>> {
let mut node = self.head?;
let pin = unsafe {
Pin::new_unchecked(node.as_mut())
};
Some(pin)
}
#[must_use]
pub fn back(&self) -> Option<Pin<&T>> {
let node = self.tail?;
let pin = unsafe {
Pin::new_unchecked(node.as_ref())
};
Some(pin)
}
#[must_use]
pub fn back_mut(&mut self) -> Option<Pin<&mut T>> {
let mut node = self.tail?;
let pin = unsafe {
Pin::new_unchecked(node.as_mut())
};
Some(pin)
}
pub unsafe fn remove(&mut self, item: NonNull<T>) -> Option<T::Handle> {
let mut links = T::links(item);
let links = links.as_mut();
debug_assert!(
!self.is_empty() || !links.is_linked(),
"tried to remove an item from an empty list, but the item is linked!\n\
is the item linked to a different list?\n \
item: {item:p}\n links: {links:?}\n list: {self:?}\n"
);
let prev = links.set_prev(None);
let next = links.set_next(None);
if let Some(prev) = prev {
T::links(prev).as_mut().set_next(next);
} else if self.head != Some(item) {
return None;
} else {
debug_assert_ne!(Some(item), next, "node must not be linked to itself");
self.head = next;
}
if let Some(next) = next {
T::links(next).as_mut().set_prev(prev);
} else if self.tail != Some(item) {
return None;
} else {
debug_assert_ne!(Some(item), prev, "node must not be linked to itself");
self.tail = prev;
}
self.len -= 1;
Some(T::from_ptr(item))
}
#[must_use]
pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T> {
CursorMut::new(self, self.head, 0)
}
#[must_use]
pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T> {
let index = self.len().saturating_sub(1);
CursorMut::new(self, self.tail, index)
}
#[must_use]
pub fn cursor_front(&self) -> Cursor<'_, T> {
Cursor::new(self, self.head, 0)
}
#[must_use]
pub fn cursor_back(&self) -> Cursor<'_, T> {
let index = self.len().saturating_sub(1);
Cursor::new(self, self.tail, index)
}
#[must_use]
pub fn iter(&self) -> Iter<'_, T> {
Iter {
_list: self,
curr: self.head,
curr_back: self.tail,
len: self.len(),
}
}
#[must_use]
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
let curr = self.head;
let curr_back = self.tail;
let len = self.len();
IterMut {
_list: self,
curr,
curr_back,
len,
}
}
#[must_use]
pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, T, F>
where
F: FnMut(&T) -> bool,
{
let cursor = self.cursor_front_mut();
DrainFilter { cursor, pred }
}
#[inline]
unsafe fn insert_nodes_between(
&mut self,
prev: Link<T>,
next: Link<T>,
splice_start: NonNull<T>,
splice_end: NonNull<T>,
spliced_length: usize,
) {
debug_assert!(
(prev.is_none() && next.is_none()) || prev != next,
"cannot insert between a node and itself!\n \
prev: {prev:?}\n next: {next:?}",
);
if let Some(prev) = prev {
let links = T::links(prev).as_mut();
debug_assert_eq!(links.next(), next);
links.set_next(Some(splice_start));
} else {
self.head = Some(splice_start);
}
if let Some(next) = next {
let links = T::links(next).as_mut();
debug_assert_eq!(links.prev(), prev);
links.set_prev(Some(splice_end));
} else {
self.tail = Some(splice_end);
}
let start_links = T::links(splice_start).as_mut();
let end_links = T::links(splice_end).as_mut();
debug_assert!(
splice_start == splice_end
|| (start_links.next().is_some() && end_links.prev().is_some()),
"splice_start must be ahead of splice_end!\n \
splice_start: {splice_start:?}\n \
splice_end: {splice_end:?}\n \
start_links: {start_links:?}\n \
end_links: {end_links:?}",
);
start_links.set_prev(prev);
end_links.set_next(next);
self.len += spliced_length;
}
#[inline]
unsafe fn split_after_node(&mut self, split_node: Link<T>, idx: usize) -> Self {
let split_node = match split_node {
Some(node) => node,
None => return mem::replace(self, Self::new()),
};
let head = unsafe { T::links(split_node).as_mut().set_next(None) };
let tail = if let Some(head) = head {
let _prev = unsafe { T::links(head).as_mut().set_prev(None) };
debug_assert_eq!(_prev, Some(split_node));
self.tail.replace(split_node)
} else {
None
};
let split = Self {
head,
tail,
len: self.len - idx,
};
self.len = idx;
split
}
#[inline]
fn take_all(&mut self) -> Option<(NonNull<T>, NonNull<T>, usize)> {
let head = self.head.take()?;
let tail = self.tail.take();
debug_assert!(
tail.is_some(),
"if a list's `head` is `Some`, its tail must also be `Some`"
);
let tail = tail?;
let len = mem::replace(&mut self.len, 0);
debug_assert_ne!(
len, 0,
"if a list is non-empty, its `len` must be greater than 0"
);
Some((head, tail, len))
}
}
impl<T> iter::Extend<T::Handle> for List<T>
where
T: Linked<Links<T>> + ?Sized,
{
fn extend<I: IntoIterator<Item = T::Handle>>(&mut self, iter: I) {
for item in iter {
self.push_back(item);
}
}
}
impl<T> iter::FromIterator<T::Handle> for List<T>
where
T: Linked<Links<T>> + ?Sized,
{
fn from_iter<I: IntoIterator<Item = T::Handle>>(iter: I) -> Self {
let mut list = Self::new();
list.extend(iter);
list
}
}
unsafe impl<T: Linked<Links<T>> + ?Sized> Send for List<T> where T: Send {}
unsafe impl<T: Linked<Links<T>> + ?Sized> Sync for List<T> where T: Sync {}
impl<T: Linked<Links<T>> + ?Sized> fmt::Debug for List<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("List")
.field("head", &FmtOption::new(&self.head))
.field("tail", &FmtOption::new(&self.tail))
.field("len", &self.len())
.finish()
}
}
impl<'list, T: Linked<Links<T>> + ?Sized> IntoIterator for &'list List<T> {
type Item = &'list T;
type IntoIter = Iter<'list, T>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'list, T: Linked<Links<T>> + ?Sized> IntoIterator for &'list mut List<T> {
type Item = Pin<&'list mut T>;
type IntoIter = IterMut<'list, T>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
impl<T: Linked<Links<T>> + ?Sized> IntoIterator for List<T> {
type Item = T::Handle;
type IntoIter = IntoIter<T>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
IntoIter { list: self }
}
}
impl<T: Linked<Links<T>> + ?Sized> Drop for List<T> {
fn drop(&mut self) {
while let Some(node) = self.pop_front() {
drop(node);
}
debug_assert!(self.is_empty());
}
}
impl<T: ?Sized> Links<T> {
#[must_use]
pub const fn new() -> Self {
Self {
inner: UnsafeCell::new(LinksInner {
next: None,
prev: None,
_unpin: PhantomPinned,
}),
}
}
pub fn is_linked(&self) -> bool {
self.next().is_some() || self.prev().is_some()
}
fn unlink(&mut self) {
self.inner.get_mut().next = None;
self.inner.get_mut().prev = None;
}
#[inline]
fn next(&self) -> Link<T> {
unsafe { (*self.inner.get()).next }
}
#[inline]
fn prev(&self) -> Link<T> {
unsafe { (*self.inner.get()).prev }
}
#[inline]
fn set_next(&mut self, next: Link<T>) -> Link<T> {
mem::replace(&mut self.inner.get_mut().next, next)
}
#[inline]
fn set_prev(&mut self, prev: Link<T>) -> Link<T> {
mem::replace(&mut self.inner.get_mut().prev, prev)
}
fn assert_valid(&self, head: &Self, tail: &Self)
where
T: Linked<Self>,
{
if ptr::eq(self, head) {
assert_eq!(
self.prev(),
None,
"head node must not have a prev link; node={:#?}",
self
);
}
if ptr::eq(self, tail) {
assert_eq!(
self.next(),
None,
"tail node must not have a next link; node={:#?}",
self
);
}
assert_ne!(
self.next(),
self.prev(),
"node cannot be linked in a loop; node={:#?}",
self
);
if let Some(next) = self.next() {
assert_ne!(
unsafe { T::links(next) },
NonNull::from(self),
"node's next link cannot be to itself; node={:#?}",
self
);
}
if let Some(prev) = self.prev() {
assert_ne!(
unsafe { T::links(prev) },
NonNull::from(self),
"node's prev link cannot be to itself; node={:#?}",
self
);
}
}
}
impl<T: ?Sized> Default for Links<T> {
fn default() -> Self {
Self::new()
}
}
impl<T: ?Sized> fmt::Debug for Links<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("Links")
.field("self", &format_args!("{:p}", self))
.field("next", &FmtOption::new(&self.next()))
.field("prev", &FmtOption::new(&self.prev()))
.finish()
}
}
impl<T: ?Sized> PartialEq for Links<T> {
fn eq(&self, other: &Self) -> bool {
self.next() == other.next() && self.prev() == other.prev()
}
}
unsafe impl<T: Send> Send for Links<T> {}
unsafe impl<T: Sync> Sync for Links<T> {}
impl<'list, T: Linked<Links<T>> + ?Sized> Iterator for Iter<'list, T> {
type Item = &'list T;
fn next(&mut self) -> Option<Self::Item> {
if self.len == 0 {
return None;
}
let curr = self.curr.take()?;
self.len -= 1;
unsafe {
self.curr = T::links(curr).as_ref().next();
Some(curr.as_ref())
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.len();
(len, Some(len))
}
}
impl<'list, T: Linked<Links<T>> + ?Sized> ExactSizeIterator for Iter<'list, T> {
#[inline]
fn len(&self) -> usize {
self.len
}
}
impl<'list, T: Linked<Links<T>> + ?Sized> DoubleEndedIterator for Iter<'list, T> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.len == 0 {
return None;
}
let curr = self.curr_back.take()?;
self.len -= 1;
unsafe {
self.curr_back = T::links(curr).as_ref().prev();
Some(curr.as_ref())
}
}
}
impl<'list, T: Linked<Links<T>> + ?Sized> iter::FusedIterator for Iter<'list, T> {}
impl<'list, T: Linked<Links<T>> + ?Sized> Iterator for IterMut<'list, T> {
type Item = Pin<&'list mut T>;
fn next(&mut self) -> Option<Self::Item> {
if self.len == 0 {
return None;
}
let mut curr = self.curr.take()?;
self.len -= 1;
unsafe {
self.curr = T::links(curr).as_ref().next();
let pin = Pin::new_unchecked(curr.as_mut());
Some(pin)
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.len();
(len, Some(len))
}
}
impl<'list, T: Linked<Links<T>> + ?Sized> ExactSizeIterator for IterMut<'list, T> {
#[inline]
fn len(&self) -> usize {
self.len
}
}
impl<'list, T: Linked<Links<T>> + ?Sized> DoubleEndedIterator for IterMut<'list, T> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.len == 0 {
return None;
}
let mut curr = self.curr_back.take()?;
self.len -= 1;
unsafe {
self.curr_back = T::links(curr).as_ref().prev();
let pin = Pin::new_unchecked(curr.as_mut());
Some(pin)
}
}
}
impl<'list, T: Linked<Links<T>> + ?Sized> iter::FusedIterator for IterMut<'list, T> {}
impl<T: Linked<Links<T>> + ?Sized> fmt::Debug for IntoIter<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("IntoIter").field(&self.list).finish()
}
}
impl<T: Linked<Links<T>> + ?Sized> Iterator for IntoIter<T> {
type Item = T::Handle;
#[inline]
fn next(&mut self) -> Option<T::Handle> {
self.list.pop_front()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(self.list.len, Some(self.list.len))
}
}
impl<T: Linked<Links<T>> + ?Sized> DoubleEndedIterator for IntoIter<T> {
#[inline]
fn next_back(&mut self) -> Option<T::Handle> {
self.list.pop_back()
}
}
impl<T: Linked<Links<T>> + ?Sized> ExactSizeIterator for IntoIter<T> {
#[inline]
fn len(&self) -> usize {
self.list.len
}
}
impl<T: Linked<Links<T>> + ?Sized> iter::FusedIterator for IntoIter<T> {}
impl<T, F> Iterator for DrainFilter<'_, T, F>
where
F: FnMut(&T) -> bool,
T: Linked<Links<T>> + ?Sized,
{
type Item = T::Handle;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.cursor.remove_first(&mut self.pred)
}
fn size_hint(&self) -> (usize, Option<usize>) {
(0, Some(self.cursor.len()))
}
}
impl<T, F> fmt::Debug for DrainFilter<'_, T, F>
where
F: FnMut(&T) -> bool,
T: Linked<Links<T>> + ?Sized,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("DrainFilter")
.field("cursor", &self.cursor)
.field("pred", &format_args!("..."))
.finish()
}
}