intrusive_doubly_list/
lib.rs

1//! # Intrusive Doubly Linked List
2//!
3//! An efficient, zero-allocation, circular intrusive doubly linked list implementation.
4//!
5//! ## Features
6//! - **Zero Allocation**: Nodes are managed by the caller; the list itself performs no heap allocations.
7//! - **Circular Structure**: Supports seamless rotation and circular traversal.
8//! - **Ownership Validation**: Uses a `link_state` flag to prevent nodes from being inserted into multiple lists simultaneously.
9//! - **Lifetime-Bounded Iterators**: Provides safe iteration over nodes stored in the list.
10//!
11//! ## Design
12//! In an intrusive list, the "links" (the next and previous pointers) are stored inside the
13//! data structure itself. This requires the data type to implement the [`DoublyLinkPointer`] trait.
14//!
15//! ## Example
16//!
17//! ```rust, ignore
18//! use intrusive_doubly_list::{IntrusiveDLinkList, DoublyLinkPointer};
19//! use core::ptr::NonNull;
20//!
21//! struct MyNode {
22//!     next: Option<NonNull<MyNode>>,
23//!     last: Option<NonNull<MyNode>>,
24//!     linked: bool,
25//!     value: i32,
26//! }
27//!
28//! impl DoublyLinkPointer<MyNode> for MyNode {
29//!     fn get_next(&self) -> Option<NonNull<MyNode>> { self.next }
30//!     fn get_last(&self) -> Option<NonNull<MyNode>> { self.last }
31//!     fn set_next(&mut self, next: Option<NonNull<MyNode>>) { self.next = next; }
32//!     fn set_last(&mut self, last: Option<NonNull<MyNode>>) { self.last = last; }
33//!     fn set_link_state(&mut self, state: bool) { self.linked = state; }
34//!     fn is_linked(&self) -> bool { self.linked }
35//! }
36//!
37//! // Usage:
38//! let mut list = IntrusiveDLinkList::new();
39//!
40//! // Assume we have a Box or a pinned stack allocation
41//! let mut node = Box::new(MyNode {
42//!     next: None, last: None, linked: false, value: 42
43//! });
44//! let node_ptr = NonNull::new(Box::into_raw(node)).unwrap();
45//!
46//! // Initialize and push
47//! IntrusiveDLinkList::init_node(node_ptr);
48//! list.push(node_ptr);
49//!
50//! assert_eq!(list.len(), 1);
51//! ```
52//!
53//! ## Safety
54//! This crate uses `unsafe` internally to manage raw pointers. Users must ensure that:
55//! 1. Nodes are not dropped while they are still members of a list.
56//! 2. Node pointers provided to the list are valid and properly aligned.
57//! 3. The `link_state` is correctly managed via the trait implementation to prevent multiple insertions.
58
59#![no_std]
60
61mod dlink_list;
62mod doubly_link_pointer;
63mod ext;
64mod iterator;
65
66pub use dlink_list::IntrusiveDLinkList;
67pub use doubly_link_pointer::DoublyLinkPointer;
intrusive_doubly_list/lib.rs

intrusive_doubly_list/
lib.rs
