god_gragh/node/
mod.rs

1//! 节点索引和节点引用模块
2//!
3//! 提供稳定的节点索引机制，使用 generation 计数防止 ABA 问题
4
5use core::fmt;
6use core::hash::{Hash, Hasher};
7
8#[cfg(feature = "serde")]
9use serde::{Serialize, Deserialize};
10
11/// 节点索引：稳定引用节点的句柄
12///
13/// 包含槽位索引和 generation 计数，确保删除后不会错误访问新节点
14#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
15#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
16pub struct NodeIndex {
17    /// 在 Arena 中的槽位索引
18    pub(crate) index: usize,
19    /// Generation 计数器，防止 ABA 问题
20    pub(crate) generation: u32,
21}
22
23impl NodeIndex {
24    /// 创建新的 NodeIndex（内部使用）
25    #[inline]
26    pub(crate) fn new(index: usize, generation: u32) -> Self {
27        Self { index, generation }
28    }
29
30    /// 获取槽位索引
31    #[inline]
32    pub fn index(&self) -> usize {
33        self.index
34    }
35
36    /// 获取 generation 计数
37    #[inline]
38    pub fn generation(&self) -> u32 {
39        self.generation
40    }
41
42    /// 检查索引是否有效（用于内部验证）
43    #[inline]
44    #[allow(dead_code)]
45    pub(crate) fn is_valid(&self) -> bool {
46        self.index != usize::MAX
47    }
48
49    /// 创建无效索引
50    #[inline]
51    #[allow(dead_code)]
52    pub(crate) fn invalid() -> Self {
53        Self {
54            index: usize::MAX,
55            generation: 0,
56        }
57    }
58}
59
60impl fmt::Debug for NodeIndex {
61    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
62        write!(f, "NodeIndex({}, {})", self.index, self.generation)
63    }
64}
65
66impl fmt::Display for NodeIndex {
67    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
68        write!(f, "{}", self.index)
69    }
70}
71
72impl Hash for NodeIndex {
73    fn hash<H: Hasher>(&self, state: &mut H) {
74        self.index.hash(state);
75        self.generation.hash(state);
76    }
77}
78
79/// 节点引用：对图中节点的借用引用
80///
81/// 包含节点索引和对节点数据的引用，生命周期与图绑定
82pub struct NodeRef<'a, T> {
83    /// 节点索引
84    pub index: NodeIndex,
85    /// 节点数据引用
86    pub data: &'a T,
87}
88
89impl<'a, T> NodeRef<'a, T> {
90    /// 创建新的 NodeRef
91    #[inline]
92    pub fn new(index: NodeIndex, data: &'a T) -> Self {
93        Self { index, data }
94    }
95
96    /// 获取节点索引
97    #[inline]
98    pub fn index(&self) -> NodeIndex {
99        self.index
100    }
101
102    /// 获取节点数据引用
103    #[inline]
104    pub fn data(&self) -> &'a T {
105        self.data
106    }
107
108    /// 解引用到节点数据
109    #[inline]
110    pub fn get(&self) -> &'a T {
111        self.data
112    }
113}
114
115impl<'a, T> Clone for NodeRef<'a, T> {
116    fn clone(&self) -> Self {
117        *self
118    }
119}
120
121impl<'a, T> Copy for NodeRef<'a, T> {}
122
123impl<'a, T> fmt::Debug for NodeRef<'a, T>
124where
125    T: fmt::Debug,
126{
127    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
128        f.debug_struct("NodeRef")
129            .field("index", &self.index)
130            .field("data", self.data)
131            .finish()
132    }
133}
134
135/// 节点存储槽位
136///
137/// 包含 generation 计数和可选数据，支持安全的删除和复用
138/// 使用 64 字节对齐，避免 false sharing
139#[derive(Debug)]
140#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
141#[cfg_attr(feature = "serde", serde(bound(
142    serialize = "T: Serialize",
143    deserialize = "T: Deserialize<'de>"
144)))]
145#[repr(align(64))]
146pub(crate) struct NodeSlot<T> {
147    /// Generation 计数器，每次分配递增
148    pub generation: u32,
149    /// 节点数据，None 表示已删除
150    pub data: Option<T>,
151}
152
153impl<T> Clone for NodeSlot<T> {
154    fn clone(&self) -> Self {
155        Self {
156            generation: self.generation,
157            data: None, // 不克隆数据，因为 Clone 通常用于图结构克隆
158        }
159    }
160}
161
162impl<T> NodeSlot<T> {
163    /// 创建新的节点槽位
164    #[inline]
165    pub(crate) fn new(generation: u32, data: T) -> Self {
166        Self {
167            generation,
168            data: Some(data),
169        }
170    }
171
172    /// 创建已删除的槽位
173    #[inline]
174    #[allow(dead_code)]
175    pub(crate) fn deleted(generation: u32) -> Self {
176        Self {
177            generation,
178            data: None,
179        }
180    }
181
182    /// 检查槽位是否被占用
183    #[inline]
184    pub(crate) fn is_occupied(&self) -> bool {
185        self.data.is_some()
186    }
187
188    /// 获取数据引用
189    #[inline]
190    pub(crate) fn data(&self) -> Option<&T> {
191        self.data.as_ref()
192    }
193
194    /// 获取数据可变引用
195    #[inline]
196    #[allow(dead_code)]
197    pub(crate) fn data_mut(&mut self) -> Option<&mut T> {
198        self.data.as_mut()
199    }
200}
201
202#[cfg(test)]
203mod tests {
204    use super::*;
205
206    #[test]
207    fn test_node_index_creation() {
208        let idx = NodeIndex::new(42, 1);
209        assert_eq!(idx.index(), 42);
210        assert_eq!(idx.generation(), 1);
211        assert!(idx.is_valid());
212    }
213
214    #[test]
215    fn test_node_index_invalid() {
216        let idx = NodeIndex::invalid();
217        assert!(!idx.is_valid());
218        assert_eq!(idx.index(), usize::MAX);
219    }
220
221    #[test]
222    fn test_node_index_hash() {
223        use core::hash::{Hash, Hasher};
224        use std::collections::hash_map::DefaultHasher;
225
226        let idx1 = NodeIndex::new(42, 1);
227        let idx2 = NodeIndex::new(42, 1);
228        let idx3 = NodeIndex::new(42, 2);
229
230        let mut h1 = DefaultHasher::new();
231        let mut h2 = DefaultHasher::new();
232        let mut h3 = DefaultHasher::new();
233
234        idx1.hash(&mut h1);
235        idx2.hash(&mut h2);
236        idx3.hash(&mut h3);
237
238        assert_eq!(h1.finish(), h2.finish());
239        assert_ne!(h1.finish(), h3.finish());
240    }
241
242    #[test]
243    fn test_node_slot() {
244        let mut slot = NodeSlot::new(1, "test");
245        assert!(slot.is_occupied());
246        assert_eq!(slot.data(), Some(&"test"));
247        assert_eq!(slot.data_mut(), Some(&mut "test"));
248
249        let deleted: NodeSlot<&str> = NodeSlot::deleted(1);
250        assert!(!deleted.is_occupied());
251        assert_eq!(deleted.data(), None);
252    }
253}
god_gragh/node/mod.rs

god_gragh/node/
mod.rs
