embed_collections/
lib.rs

1#![cfg_attr(docsrs, feature(doc_cfg))]
2#![cfg_attr(docsrs, allow(unused_attributes))]
3
4//! # Embed Collections
5//!
6//! `embed-collections` provides intrusive data structures for Rust. Unlike standard collections,
7//! intrusive collections require the elements to store the node data (links) themselves.
8//! This allows for:
9//!
10//! - **Memory Efficiency**: No extra allocation for nodes.
11//! - **Deterministic Memory Management**: You control where the node lives.
12//! - **Flexibility**: Works with various pointer types (`Box`, `Arc`, `Rc`, `NonNull`, raw pointers).
13//!
14//! ## Modules
15//!
16//! - [`dlist`]: Intrusive Doubly Linked List.
17//! - [`slist`]: Intrusive Singly Linked List (FIFO Queue).
18//!
19//! ## Example
20//!
21//! ```rust
22//! use embed_collections::{dlist::{DLinkedList, ListItem, ListNode}, Pointer};
23//! use std::cell::UnsafeCell;
24//!
25//! struct MyItem {
26//!     val: i32,
27//!     link: UnsafeCell<ListNode<MyItem, ()>>,
28//! }
29//!
30//! impl MyItem {
31//!     fn new(val: i32) -> Self {
32//!         Self {
33//!             val,
34//!             link: UnsafeCell::new(ListNode::default()),
35//!         }
36//!     }
37//! }
38//!
39//! unsafe impl ListItem<()> for MyItem {
40//!     fn get_node(&self) -> &mut ListNode<Self, ()> {
41//!         unsafe { &mut *self.link.get() }
42//!     }
43//! }
44//!
45//! let mut list = DLinkedList::<Box<MyItem>, ()>::new();
46//! list.push_back(Box::new(MyItem::new(10)));
47//! list.push_back(Box::new(MyItem::new(20)));
48//!
49//! assert_eq!(list.pop_front().unwrap().val, 10);
50//! assert_eq!(list.pop_front().unwrap().val, 20);
51//! ```
52
53use std::mem;
54use std::ptr::NonNull;
55
56/// Abstract pointer trait to support various pointer types in collections.
57///
58/// This trait allows the collections to work with:
59/// - `Box<T>`: Owned, automatically dropped.
60/// - `Arc<T>`: Shared ownership.
61/// - `Rc<T>`: Single thread ownership.
62/// - `NonNull<T>`: Raw non-null pointers (manual memory management).
63/// - `*const T`: Raw pointers (recommend to use `NonNull<T>` instead)
64pub trait Pointer: Sized {
65    type Target;
66
67    fn as_ref(&self) -> &Self::Target;
68
69    unsafe fn from_raw(p: *const Self::Target) -> Self;
70
71    fn into_raw(self) -> *const Self::Target;
72}
73
74impl<T> Pointer for *const T {
75    type Target = T;
76
77    #[inline]
78    fn as_ref(&self) -> &Self::Target {
79        unsafe { mem::transmute(*self) }
80    }
81
82    unsafe fn from_raw(p: *const Self::Target) -> Self {
83        p as *const T
84    }
85
86    fn into_raw(self) -> *const Self::Target {
87        self as *const T
88    }
89}
90
91impl<T> Pointer for NonNull<T> {
92    type Target = T;
93
94    #[inline]
95    fn as_ref(&self) -> &Self::Target {
96        unsafe { self.as_ref() }
97    }
98
99    unsafe fn from_raw(p: *const Self::Target) -> Self {
100        unsafe { NonNull::new_unchecked(p as *mut T) }
101    }
102
103    fn into_raw(self) -> *const Self::Target {
104        self.as_ptr()
105    }
106}
107
108impl<T> Pointer for Box<T> {
109    type Target = T;
110
111    #[inline]
112    fn as_ref(&self) -> &Self::Target {
113        &**self
114    }
115
116    unsafe fn from_raw(p: *const Self::Target) -> Self {
117        unsafe { Box::from_raw(p as *mut T) }
118    }
119
120    fn into_raw(self) -> *const Self::Target {
121        Box::into_raw(self)
122    }
123}
124
125impl<T> Pointer for std::rc::Rc<T> {
126    type Target = T;
127
128    #[inline]
129    fn as_ref(&self) -> &Self::Target {
130        &**self
131    }
132
133    unsafe fn from_raw(p: *const Self::Target) -> Self {
134        unsafe { std::rc::Rc::from_raw(p) }
135    }
136
137    fn into_raw(self) -> *const Self::Target {
138        std::rc::Rc::into_raw(self)
139    }
140}
141
142impl<T> Pointer for std::sync::Arc<T> {
143    type Target = T;
144
145    #[inline]
146    fn as_ref(&self) -> &Self::Target {
147        &**self
148    }
149
150    unsafe fn from_raw(p: *const Self::Target) -> Self {
151        unsafe { std::sync::Arc::from_raw(p) }
152    }
153
154    fn into_raw(self) -> *const Self::Target {
155        std::sync::Arc::into_raw(self)
156    }
157}
158
159#[cfg(feature = "dlist")]
160pub mod dlist;
161#[cfg(feature = "slist")]
162pub mod slist;
embed_collections/lib.rs

embed_collections/
lib.rs
