Tokio Linked List

LinkedList在 Tokio 中有很多实现，并且在 tokio 的 mpsc 和 task 中都有用到，这里我们来探究下 tokio 中都有那些 linkedlist 的实现和用法。

LikedList#

源代码在src/util/linked_list.rs

//! An intrusive double linked list of data.
//!
//! The data structure supports tracking pinned nodes. Most of the data
//! structure's APIs are `unsafe` as they require the caller to ensure the
//! specified node is actually contained by the list.

在代码头部的注释说明了这个 LinkedList 是一个侵入式的双向链表，由于用到了 unsafe 的特性，所以 caller 要保证safety. 我们看下 LinkedList 的结构定义

侵入式链表#

TODO

LinkedList结构定义#

/// An intrusive linked list.
///
/// Currently, the list is not emptied on drop. It is the caller's
/// responsibility to ensure the list is empty before dropping it.
pub(crate) struct LinkedList<L, T> {
    /// Linked list head
    head: Option<NonNull<T>>,

    /// Linked list tail
    tail: Option<NonNull<T>>,

    /// Node type marker.
    _marker: PhantomData<*const L>,
}

这里的 LinkedList 中只记录了头尾指针，但是 LinkedList 是一个泛型，L和T，其中T应该是链表元素的类型。

这里使用了_marker来标记 LinkedList是!Send + !Sync的。 头尾指针使用Option<NonNull<T>>来表示。

存在一个疑问，那这里的L是什么？

接着在该文件中定义了一个 Link 的 trait

/// Defines how a type is tracked within a linked list.
/// 
/// In order to support storing a single type within multiple lists, accessing 
/// the list pointers is decoupled from the entry type.
///
/// # Safety
/// 
/// Implementations must guarantee that `Target` types are pinned in memory. In
/// other words, when a node is inserted, the value will not be moved as long as
/// it is stored in the list.
unsafe trait Link {
    /// Handle to the list entry.
    ///
    /// This is usually a pointer-ish type.
    type Handle;

    /// Node type
    type Target;

    /// Convert the handle to a raw pointer without consuming the handle.
    fn as_raw(handle: &Self::Handle) -> NonNull<Self::Target>;

    /// Convert the raw pointer to a handle.
    unsafe fn from_raw(ptr: NonNull<Self::Target>) -> Self::Handle;

    /// Return the pointers for a node
    ///
    /// # Safety
    ///
    /// The resulting pointer should have the same tag in the stacked-borrows
    /// stack as the argument. In particular, the method may not create an
    /// intermediate reference in the process of creating the resulting raw
    /// pointers.
    unsafe fn pointers(target: NonNull<Self::Target>) -> NonNull<Pointers<Self::Target>>;
}

Pinters是什么呢？

/// Previus / next pointers.
struct Pointers<T> {
    inner: UnsafeCell<PointersInner<T>>,
}


#[repr(C)]
struct PointersInner<T> {
    prev: Option<NonNull<T>>,

    next: Option<NonNull<T>>,

    _pin: PhantomPinned,
}

impl<T> Pointers<T> {

    pub(crate) fn get_prev(&self) -> Option<NonNull<T>> {
        unsafe {
            let inner = self.inner.get();
            let prev = inner as * const Option<NonNull<T>>;
            ptr::read(prev)
        }
    }

    pub(crate) fn get_next(&self) -> Option<NonNull<T>> {
        unsafe {
            let inner = self.inner.get();
            let prev = inner as *const Option<NonNull<T>>;
            let next = prev.add(1);
            ptr::read(next)
        }
    }

    pub(crate) fn set_prev(&mut self, value: Option<NonNull<T>>) {
        unsafe {
            let inner = self.inner.get();
            let prev = inner as *mut Option<NonNull<T>>;
            ptr::write(prev, value);
        }
    }

    pub(crate) fn set_next(&mut self, value: Option<NonNull<T>>) {
        unsafe {
            let inner = self.inner.get();
            let prev = inner as *mut Option<NonNull<T>>;
            let next = prev.add(1);
            ptr::write(next, value);
        }
    }
}

SharedList#

源代码在src/util/sharded_list.rs

WakeList#

源代码在src/util/wake_list.rs

Channel#

src/sync/mpsc/list.rs

Task#

src/runtime/task/list.rs

References#

[1] (https://gist.github.com/Darksonn/1567538f56af1a8038ecc3c664a42462)[https://gist.github.com/Darksonn/1567538f56af1a8038ecc3c664a42462]