embed_collections/

lib.rs

#![allow(rustdoc::redundant_explicit_links)]
#![cfg_attr(docsrs, feature(doc_cfg))]
#![cfg_attr(docsrs, allow(unused_attributes))]
#![cfg_attr(not(feature = "std"), no_std)]
//!
//! # embed-collections
//!
//! A collection of memory efficient data structures, for embedding environment and server applications that need tight memory management.
//!
//! This crate provides two categories of modules:
//!
//! - Cache efficient collections:
//!     - [const_vec](crate::const_vec): Fixed capacity inline vec
//!     - [seg_list](#seglist--various):  A cache aware (short-live) list to store elements with adaptive size segments
//!     - [various](#seglist--various): A short-live list wrapping `SegList` with `Option<T>` to delay allocation.
//!     - [btree](#btree): A cache aware B+tree for lone-live and large dataset, optimized for numeric types, with special entry API allows peeking adjacent values.
//!     - [various_map](crate::various_map): A short-live map wrapping BTreeMap (std) with `Option<(K, V)>` to delay allocation.
//!
//! - [Intrusive collections](#intrusive-collections):
//!     - Supports various smart pointer types: owned (Box), multiple ownership (Arc, Rc), raw pointers (`NonNull<T>`, `*const T`, `*mut T`)
//!     - [dlist](crate::dlist): Intrusive Doubly Linked List (Queue / Stack).
//!     - [slist](crate::slist): Intrusive Singly Linked List ( Queue / stack).
//!     - [slist_owned](crate::slist_owned): An intrusive slist but with safe and more compact interface
//!     - [avl](crate::avl): Intrusive AVL Tree (Balanced Binary Search Tree), port to rust from ZFS
//!
//! ## SegList & Various
//!
//! [SegList](crate::seg_list) and [Various](crate::various) is designed for parameter passing.
//!
//! More CPU-cache friendly compared to `LinkedList`. And because it does not re-allocate, it's faster than `Vec::push()` when the number of elements is small.
//! It's nice to the memory allocator (always allocate with fixed size segment).
//!
//! Benchmark: append + drain (x86_64, cache line 128 bytes):
//!
//! (platform: intel i7-8550U)
//!
//! | Elements | SegList | Vec | SegList vs Vec |
//! |----------|---------|-----|----------------|
//! | 10 | 40.5 ns | 147.0 ns | **3.6x faster** |
//! | 32 | 99.1 ns | 237.8 ns | **2.4x faster** |
//! | 100 | 471.1 ns | 464.0 ns | ~1.0x |
//! | 500 | 2.77 µs | 895.5 ns | 3.1x slower |
//!
//! ## B+tree
//!
//! We provide a [BTreeMap](crate::btree) for single-threaded long-term in-memory storage.
//! It's a cache aware b+tree:
//!
//! - Nodes are filled up in 4 cache lines (256 bytes on x86_64).
//!   - Capacity in compile-time determined according to the size of Key, Value.
//!   - Reduce memory fragmentation by alignment.
//! - **Optimised for numeric key**
//!   - Respecting numeric space for sequential insertion.
//!   - Reduce latency for sequential insertion.
//! - Faster iteration and teardown
//! - **Limitation**:
//!   - K should have clone (for propagate into the InterNode during split)
//!   - K & V should <= CACHE_LINE_SIZE - 16
//!     - It make sure InterNode can hold  at least two children.
//!     - If K & V is large you should put into `Box`, for room saving, and for the speed to move value
//! - **Special API**:
//!   - Peak and move to previous/next `Entry` (for modification).
//!   - Alter key of an OccupiedEntry.
//!   - Batch remove with range.
//!   - Movable `Cursor` (for readonly)
//!
//! Compared to std::collections::btree (as of rust 1.94):
//! - The std impl is pure btree (not b+tree) without horizontal links. Each key store only once at either leaf and inter nodes.
//! - The std impl is optimised for point lookup.
//! - The std impl has fixed Cap=11, node size varies according to T. (For T=U64, size is 288B for InterNode and 192B for LeafNode)
//! - The std cursor API is still unstable (as of 1.94) and relatively complex to use.
//!
//! **benchmark**
//!
//! platform: intel i7-8550U, key: u32, value: u32, rust 1.92.
//!
//! Measured in million ops for different size of dataset:
//!
//! insert_seq |btree|std
//! -|-|-
//! 1k|**88.956**|20.001
//! 10k|**75.291**|16.04
//! 100k|**45.959**|11.207
//!
//! insert_rand|btree|std|avl(box)|avl(arc)
//! -|-|-|-|-
//! 1k|**21.311**|17.792|11.172|9.5397
//! 10k|**14.268**|11.587|6.3669|5.651
//! 100k|**5.4814**|3.0691|0.78|0.732
//!
//! get_seq|btree|std
//! -|-|-
//! 1k|**59.448**|34.248
//! 10k|**37.225**|27.571
//! 100k|**30.77**|19.907
//!
//! get_rand|btree|std|avl(box)|avl(arc)
//! -|-|-|-|-
//! 1k|**47.33**|27.651|24.254|23.466
//! 10k|**19.358**|16.868|11.771|10.806
//! 100k|**5.2584**|3.2569|1.4423|1.2712
//!
//! remove_rand |btree|std
//! -|-|-
//! 1k|**20.965**|15.968
//! 10k|**16.073**|11.701
//! 100k|**5.0214**|3.0724
//!
//! iter|btree|std
//! -|-|-
//! 1k|1342.8|346.8
//! 10k|1209.4|303.83
//! 100k|**152.57**|51.147
//!
//! into_iter|btree|std
//! -|-|-
//! 1k|396.07|143.81
//! 10k|397.05|81.389
//! 100k|**360.18**|56.742
//!
//!
//! ## Intrusive Collections
//!
//! intrusive collection is often used in c/c++ code, they does not need extra allocation.
//! But the disadvantages includes: complexity to write, bad for cache hit when the node is too small
//!
//! There're three usage scenarios:
//!
//! 1. Push smart pointer to the list, so that the list hold 1 ref count when the type is `Arc` /
//!    `Rc`, but you have to use UnsafeCell for internal mutation.
//!
//! 2. Push `Box` to the list, the list own the items until they are popped, it's better than std
//!    LinkedList because no additional allocation is needed.
//!
//! 3. Push raw pointer (better use NonNull instead of *const T for smaller footprint) to the list,
//!    for temporary usage. You must ensure the list item not dropped be other refcount
//!    (for example, the item is holding by Arc in other structure).
//!
//!
//! ### Difference to `intrusive-collections` crate
//!
//! This crate choose to use trait instead of c like `offset_of!`, mainly because:
//!
//! - Mangling with offset conversion makes the code hard to read (for people not used to c style coding).
//!
//! - You don't have to understand some complex macro style.
//!
//! - It's dangerous to use pointer offset conversion when the embedded Node not perfectly aligned,
//!   and using memtion to return the node ref is more safer approach.
//!   For example, the default `repr(Rust)` might reorder the field, or you mistakenly use `repr(packed)`.
//!
//! ### instrusive link list example
//!
//! ```rust
//! use embed_collections::{dlist::{DLinkedList, DListItem, DListNode}, Pointer};
//! use std::cell::UnsafeCell;
//! use std::sync::Arc;
//!
//! // The tag structure only for labeling, distinguish two lists
//! struct CacheTag;
//! struct IOTag;
//!
//! struct MyItem {
//!     val: i32,
//!     cache_link: UnsafeCell<DListNode<MyItem, CacheTag>>,
//!     io_link: UnsafeCell<DListNode<MyItem, IOTag>>,
//! }
//!
//! impl MyItem {
//!     fn new(val: i32) -> Self {
//!         Self {
//!             val,
//!             cache_link: UnsafeCell::new(DListNode::default()),
//!             io_link: UnsafeCell::new(DListNode::default()),
//!         }
//!     }
//! }
//!
//! unsafe impl DListItem<CacheTag> for MyItem {
//!     fn get_node(&self) -> &mut DListNode<Self, CacheTag> {
//!         unsafe { &mut *self.cache_link.get() }
//!     }
//! }
//!
//! unsafe impl DListItem<IOTag> for MyItem {
//!     fn get_node(&self) -> &mut DListNode<Self, IOTag> {
//!         unsafe { &mut *self.io_link.get() }
//!     }
//! }
//!
//! let mut cache_list = DLinkedList::<Arc<MyItem>, CacheTag>::new();
//! let mut io_list = DLinkedList::<Arc<MyItem>, IOTag>::new();
//!
//! let item1 = Arc::new(MyItem::new(10));
//! let item2 = Arc::new(MyItem::new(20));
//!
//! // Push the same item to both lists
//! cache_list.push_back(item1.clone());
//! io_list.push_back(item1.clone());
//!
//! cache_list.push_back(item2.clone());
//! io_list.push_back(item2.clone());
//!
//! assert_eq!(cache_list.pop_front().unwrap().val, 10);
//! assert_eq!(io_list.pop_front().unwrap().val, 10);
//! assert_eq!(cache_list.pop_front().unwrap().val, 20);
//! assert_eq!(io_list.pop_front().unwrap().val, 20);
//! ```
//!
//! ## Feature Flags
//!
//! *   **`default`**: Enabled by default. Includes the `std`, `various`, `seglist` features.
//! *   **`std`**: Enables integration with the Rust standard library, including the `println!` macro for debugging. Disabling this feature enables `no_std` compilation.
//! *   **`seglist`**: Enable seg_list module
//! *   **`various`**: Enable various_map module
//! *   **`various` + `seglist`**: Enable various module
//! *   **`slist`**: Enables the singly linked list (`slist`) and owned singly linked list (`slist_owned`) modules.
//! *   **`dlist`**: Enables the doubly linked list (`dlist`) module.
//! *   **`avl`**: Enables the `avl` module.
//! *   **`btree`**: Enable the btree module.
//! *   **`full`**: Enabled by default. Includes `slist`, `dlist`, and `avl`.
//!
//! To compile with `no_std` and only the `slist` module, you would use:
//! `cargo build --no-default-features --features slist`

extern crate alloc;
#[cfg(any(feature = "std", test))]
extern crate std;

use alloc::boxed::Box;
use alloc::rc::Rc;
use alloc::sync::Arc;
use core::ptr::NonNull;

/// Abstract pointer trait to support various pointer types in collections.
///
/// This trait allows the collections to work with:
/// - `Box<T>`: Owned, automatically dropped.
/// - `Arc<T>`: Shared ownership.
/// - `Rc<T>`: Single thread ownership.
/// - `NonNull<T>`: Raw non-null pointers (manual memory management).
/// - `*const T`: Raw pointers (recommend to use `NonNull<T>` instead)
pub trait Pointer: Sized {
    type Target;

    fn as_ref(&self) -> &Self::Target;

    #[inline(always)]
    fn as_ptr(&self) -> *const Self::Target {
        self.as_ref() as *const Self::Target
    }

    #[allow(clippy::missing_safety_doc)]
    unsafe fn from_raw(p: *const Self::Target) -> Self;

    fn into_raw(self) -> *const Self::Target;
}

pub trait SmartPointer: Pointer {
    fn new(t: Self::Target) -> Self;
}

#[allow(clippy::unnecessary_cast)]
impl<T> Pointer for *const T {
    type Target = T;

    #[inline]
    fn as_ref(&self) -> &Self::Target {
        unsafe { &**self }
    }

    #[inline]
    unsafe fn from_raw(p: *const Self::Target) -> Self {
        p as *const T
    }

    #[inline]
    fn into_raw(self) -> *const Self::Target {
        self as *const T
    }
}

#[allow(clippy::unnecessary_cast)]
impl<T> Pointer for *mut T {
    type Target = T;

    #[inline]
    fn as_ref(&self) -> &Self::Target {
        unsafe { &**self }
    }

    #[inline]
    unsafe fn from_raw(p: *const Self::Target) -> Self {
        p as *mut T
    }

    #[inline]
    fn into_raw(self) -> *const Self::Target {
        self as *mut T
    }
}

impl<T> Pointer for NonNull<T> {
    type Target = T;

    #[inline]
    fn as_ref(&self) -> &Self::Target {
        unsafe { self.as_ref() }
    }

    #[inline]
    unsafe fn from_raw(p: *const Self::Target) -> Self {
        unsafe { NonNull::new_unchecked(p as *mut T) }
    }

    #[inline]
    fn into_raw(self) -> *const Self::Target {
        self.as_ptr()
    }
}

impl<T> Pointer for Box<T> {
    type Target = T;

    #[inline]
    fn as_ref(&self) -> &Self::Target {
        self
    }

    #[inline]
    unsafe fn from_raw(p: *const Self::Target) -> Self {
        unsafe { Box::from_raw(p as *mut T) }
    }

    #[inline]
    fn into_raw(self) -> *const Self::Target {
        Box::into_raw(self)
    }
}

impl<T> SmartPointer for Box<T> {
    #[inline]
    fn new(inner: T) -> Self {
        Box::new(inner)
    }
}

impl<T> Pointer for Rc<T> {
    type Target = T;

    #[inline]
    fn as_ref(&self) -> &Self::Target {
        self
    }

    #[inline]
    unsafe fn from_raw(p: *const Self::Target) -> Self {
        unsafe { Rc::from_raw(p) }
    }

    #[inline]
    fn into_raw(self) -> *const Self::Target {
        Rc::into_raw(self)
    }
}

impl<T> SmartPointer for Rc<T> {
    #[inline]
    fn new(inner: T) -> Self {
        Rc::new(inner)
    }
}

impl<T> Pointer for Arc<T> {
    type Target = T;

    #[inline]
    fn as_ref(&self) -> &Self::Target {
        self
    }

    #[inline]
    unsafe fn from_raw(p: *const Self::Target) -> Self {
        unsafe { Arc::from_raw(p) }
    }

    #[inline]
    fn into_raw(self) -> *const Self::Target {
        Arc::into_raw(self)
    }
}

impl<T> SmartPointer for Arc<T> {
    #[inline]
    fn new(inner: T) -> Self {
        Arc::new(inner)
    }
}

impl<T> Pointer for &T {
    type Target = T;

    #[inline]
    fn as_ref(&self) -> &Self::Target {
        self
    }

    #[inline]
    unsafe fn from_raw(p: *const Self::Target) -> Self {
        unsafe { &*p }
    }

    #[inline]
    fn into_raw(self) -> *const Self::Target {
        self as *const T
    }
}

#[cfg(feature = "avl")]
pub mod avl;
pub mod const_vec;
pub use const_vec::ConstVec;
#[cfg(feature = "dlist")]
pub mod dlist;
#[cfg(feature = "seglist")]
pub mod seg_list;
#[cfg(feature = "seglist")]
pub use seg_list::SegList;
#[cfg(feature = "slist")]
pub mod slist;
#[cfg(feature = "slist")]
pub mod slist_owned;
#[cfg(all(feature = "various", feature = "seglist"))]
pub mod various;
#[cfg(all(feature = "various", feature = "seglist"))]
pub use various::Various;
#[cfg(feature = "various")]
#[allow(private_interfaces)]
pub mod various_map;
#[cfg(feature = "various")]
pub use various_map::VariousMap;
#[cfg(feature = "btree")]
pub mod btree;
#[cfg(feature = "btree")]
pub use btree::BTreeMap;

#[cfg(test)]
pub mod test;

/// Cache line size in bytes
#[cfg(any(
    target_arch = "x86_64",
    target_arch = "aarch64",
    target_arch = "arm64ec",
    target_arch = "powerpc64",
))]
pub const CACHE_LINE_SIZE: usize = 64;
#[cfg(not(any(
    target_arch = "x86_64",
    target_arch = "aarch64",
    target_arch = "arm64ec",
    target_arch = "powerpc64",
)))]
pub const CACHE_LINE_SIZE: usize = 32;

/// logging macro for development
#[macro_export(local_inner_macros)]
macro_rules! trace_log {
    ($($arg:tt)+)=>{
        #[cfg(feature="trace_log")]
        {
            log::debug!($($arg)+);
        }
    };
}

/// logging macro for development
#[macro_export(local_inner_macros)]
macro_rules! print_log {
    ($($arg:tt)+)=>{
        #[cfg(feature="trace_log")]
        {
            log::debug!($($arg)+);
        }
        #[cfg(not(feature="trace_log"))]
        {
            std::println!($($arg)+);
        }
    };
}