path: root/tokio-util/src/sync/intrusive_double_linked_list.rs

//! An intrusive double linked list of data

#![allow(dead_code, unreachable_pub)]

use core::{
    marker::PhantomPinned,
    ops::{Deref, DerefMut},
    ptr::NonNull,
};

/// A node which carries data of type `T` and is stored in an intrusive list
#[derive(Debug)]
pub struct ListNode<T> {
    /// The previous node in the list. `None` if there is no previous node.
    prev: Option<NonNull<ListNode<T>>>,
    /// The next node in the list. `None` if there is no previous node.
    next: Option<NonNull<ListNode<T>>>,
    /// The data which is associated to this list item
    data: T,
    /// Prevents `ListNode`s from being `Unpin`. They may never be moved, since
    /// the list semantics require addresses to be stable.
    _pin: PhantomPinned,
}

impl<T> ListNode<T> {
    /// Creates a new node with the associated data
    pub fn new(data: T) -> ListNode<T> {
        Self {
            prev: None,
            next: None,
            data,
            _pin: PhantomPinned,
        }
    }
}

impl<T> Deref for ListNode<T> {
    type Target = T;

    fn deref(&self) -> &T {
        &self.data
    }
}

impl<T> DerefMut for ListNode<T> {
    fn deref_mut(&mut self) -> &mut T {
        &mut self.data
    }
}

/// An intrusive linked list of nodes, where each node carries associated data
/// of type `T`.
#[derive(Debug)]
pub struct LinkedList<T> {
    head: Option<NonNull<ListNode<T>>>,
    tail: Option<NonNull<ListNode<T>>>,
}

impl<T> LinkedList<T> {
    /// Creates an empty linked list
    pub fn new() -> Self {
        LinkedList::<T> {
            head: None,
            tail: None,
        }
    }

    /// Adds a node at the front of the linked list.
    /// Safety: This function is only safe as long as `node` is guaranteed to
    /// get removed from the list before it gets moved or dropped.
    /// In addition to this `node` may not be added to another other list before
    /// it is removed from the current one.
    pub unsafe fn add_front(&mut self, node: &mut ListNode<T>) {
        node.next = self.head;
        node.prev = None;
        if let Some(mut head) = self.head {
            head.as_mut().prev = Some(node.into())
        };
        self.head = Some(node.into());
        if self.tail.is_none() {
            self.tail = Some(node.into());
        }
    }

    /// Inserts a node into the list in a way that the list keeps being sorted.
    /// Safety: This function is only safe as long as `node` is guaranteed to
    /// get removed from the list before it gets moved or dropped.
    /// In addition to this `node` may not be added to another other list before
    /// it is removed from the current one.
    pub unsafe fn add_sorted(&mut self, node: &mut ListNode<T>)
    where
        T: PartialOrd,
    {
        if self.head.is_none() {
            // First node in the list
            self.head = Some(node.into());
            self.tail = Some(node.into());
            return;
        }

        let mut prev: Option<NonNull<ListNode<T>>> = None;
        let mut current = self.head;

        while let Some(mut current_node) = current {
            if node.data < current_node.as_ref().data {
                // Need to insert before the current node
                current_node.as_mut().prev = Some(node.into());
                match prev {
                    Some(mut prev) => {
                        prev.as_mut().next = Some(node.into());
                    }
                    None => {
                        // We are inserting at the beginning of the list
                        self.head = Some(node.into());
                    }
                }
                node.next = current;
                node.prev = prev;
                return;
            }
            prev = current;
            current = current_node.as_ref().next;
        }

        // We looped through the whole list and the nodes data is bigger or equal
        // than everything we found up to now.
        // Insert at the end. Since we checked before that the list isn't empty,
        // tail always has a value.
        node.prev = self.tail;
        node.next = None;
        self.tail.as_mut().unwrap().as_mut().next = Some(node.into());
        self.tail = Some(node.into());
    }

    /// Returns the first node in the linked list without removing it from the list
    /// The function is only safe as long as valid pointers are stored inside
    /// the linked list.
    /// The returned pointer is only guaranteed to be valid as long as the list
    /// is not mutated
    pub fn peek_first(&self) -> Option<&mut ListNode<T>> {
        // Safety: When the node was inserted it was promised that it is alive
        // until it gets removed from the list.
        // The returned node has a pointer which constrains it to the lifetime
        // of the list. This is ok, since the Node is supposed to outlive
        // its insertion in the list.
        unsafe {
            self.head
                .map(|mut node| &mut *(node.as_mut() as *mut ListNode<T>))
        }
    }

    /// Returns the last node in the linked list without removing it from the list
    /// The function is only safe as long as valid pointers are stored inside
    /// the linked list.
    /// The returned pointer is only guaranteed to be valid as long as the list
    /// is not mutated
    pub fn peek_last(&self) -> Option<&mut ListNode<T>> {
        // Safety: When the node was inserted it was promised that it is alive
        // until it gets removed from the list.
        // The returned node has a pointer which constrains it to the lifetime
        // of the list. This is ok, since the Node is supposed to outlive
        // its insertion in the list.
        unsafe {
            self.tail
                .map(|mut node| &mut *(node.as_mut() as *mut ListNode<T>))
        }
    }

    /// Removes the first node from the linked list
    pub fn remove_first(&mut self) -> Option<&mut ListNode<T>> {
        #![allow(clippy::debug_assert_with_mut_call)]

        // Safety: When the node was inserted it was promised that it is alive
        // until it gets removed from the list
        unsafe {
            let mut head = self.head?;
            self.head = head.as_mut().next;

            let first_ref = head.as_mut();
            match first_ref.next {
                None