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
#![cfg_attr(docsrs, doc = include_str!("../README.md"))]
#![cfg_attr(docsrs, feature(doc_cfg, doc_auto_cfg, doc_cfg_hide))]
#![cfg_attr(docsrs, deny(missing_docs))]
#![cfg_attr(not(any(feature = "std", test)), no_std)]
#![allow(unused_unsafe)]
#[cfg(feature = "alloc")]
extern crate alloc;
#[cfg(test)]
extern crate std;
macro_rules! feature {
(
#![$meta:meta]
$($item:item)*
) => {
$(
#[cfg($meta)]
$item
)*
}
}
pub mod list;
#[doc(inline)]
pub use list::List;
pub mod mpsc_queue;
#[doc(inline)]
pub use mpsc_queue::MpscQueue;
pub(crate) mod loom;
pub(crate) mod util;
use core::ptr::NonNull;
/// Trait implemented by types which can be members of an [intrusive collection].
///
/// In order to be part of an intrusive collection, a type must contain a
/// `Links` type that stores the pointers to other nodes in that collection. For
/// example, to be part of a [doubly-linked list], a type must contain the
/// [`list::Links`] struct, or to be part of a [MPSC queue], a type must contain
/// the [`mpsc_queue::Links`] struct.
///
/// # Safety
///
/// This is unsafe to implement because it's the implementation's responsibility
/// to ensure that types implementing this trait are valid intrusive collection
/// nodes. In particular:
///
/// - Implementations **must** ensure that implementorss are pinned in memory while they
/// are in an intrusive collection. While a given `Linked` type is in an intrusive
/// data structure, it may not be deallocated or moved to a different memory
/// location.
/// - The type implementing this trait **must not** implement [`Unpin`].
/// - Additional safety requirements for individual methods on this trait are
/// documented on those methods.
///
/// Failure to uphold these invariants will result in corruption of the
/// intrusive data structure, including dangling pointers.
///
/// [intrusive collection]: crate#intrusive-data-structures
/// [`Unpin`]: core::marker::Unpin
/// [doubly-linked list]: crate::list
/// [MSPC queue]: crate::mpsc_queue
pub unsafe trait Linked<L> {
/// The handle owning nodes in the linked list.
///
/// This type must have ownership over a `Self`-typed value. When a `Handle`
/// is dropped, it should drop the corresponding `Linked` type.
///
/// A quintessential example of a `Handle` is [`Box`].
///
/// [`Box`]: alloc::boxed::Box
type Handle;
/// Convert a [`Self::Handle`] to a raw pointer to `Self`, taking ownership
/// of it in the process.
fn into_ptr(r: Self::Handle) -> NonNull<Self>;
/// Convert a raw pointer to `Self` into an owning [`Self::Handle`].
///
/// # Safety
///
/// This function is safe to call when:
/// - It is valid to construct a [`Self::Handle`] from a`raw pointer
/// - The pointer points to a valid instance of `Self` (e.g. it does not
/// dangle).
unsafe fn from_ptr(ptr: NonNull<Self>) -> Self::Handle;
/// Return the links of the node pointed to by `ptr`.
///
/// # Safety
///
/// This function is safe to call when:
/// - It is valid to construct a [`Self::Handle`] from a`raw pointer
/// - The pointer points to a valid instance of `Self` (e.g. it does not
/// dangle).
unsafe fn links(ptr: NonNull<Self>) -> NonNull<L>;
}