arena_graph/
raw.rs

1use std::marker::PhantomData;
2use std::ops::Deref;
3use std::ptr::NonNull;
4use typed_arena::Arena;
5
6pub struct Graph<N> {
7    graph: Arena<N>,
8}
9
10pub struct GraphGuard<'gg, N> {
11    inside: &'gg Graph<N>,
12    invariant: PhantomData<&'gg mut &'gg ()>,
13}
14
15impl<'gg, N> GraphGuard<'gg, N> {
16    pub fn insert(&self, node: N) -> NodeGuard<'gg, N> {
17        let node_ref = self.inside.graph.alloc(node);
18        NodeGuard {
19            inside: node_ref,
20            invariant: self.invariant,
21        }
22    }
23
24    pub unsafe fn lookup_ptr(&self, NodePtr(ptr): NodePtr<N>) -> NodeGuard<'gg, N> {
25        NodeGuard {
26            inside: &*ptr.as_ptr(),
27            invariant: self.invariant,
28        }
29    }
30}
31
32pub struct NodeGuard<'gg, N> {
33    inside: &'gg N,
34    invariant: PhantomData<&'gg mut &'gg ()>,
35}
36
37impl<N> Clone for NodeGuard<'_, N> {
38    fn clone(&self) -> Self {
39        Self {
40            inside: self.inside,
41            invariant: self.invariant,
42        }
43    }
44}
45
46impl<N> Copy for NodeGuard<'_, N> {}
47
48impl<N> Clone for GraphGuard<'_, N> {
49    fn clone(&self) -> Self {
50        Self {
51            inside: self.inside,
52            invariant: self.invariant,
53        }
54    }
55}
56
57impl<N> Copy for GraphGuard<'_, N> {}
58
59impl<'gg, N> Deref for NodeGuard<'gg, N> {
60    type Target = N;
61    fn deref(&self) -> &N {
62        self.inside
63    }
64}
65
66impl<N> Graph<N> {
67    pub fn new() -> Self {
68        Graph {
69            graph: Arena::new(),
70        }
71    }
72
73    pub fn with<F: for<'any> FnOnce(GraphGuard<'any, N>) -> R, R>(&self, func: F) -> R {
74        func(GraphGuard {
75            inside: self,
76            invariant: PhantomData,
77        })
78    }
79
80    pub unsafe fn with_unchecked<'gg, 'slf>(&'slf self) -> GraphGuard<'gg, N>
81    where
82        'slf: 'gg,
83    {
84        GraphGuard {
85            inside: self,
86            invariant: PhantomData,
87        }
88    }
89}
90
91pub struct NodePtr<N>(NonNull<N>);
92
93impl<N> Clone for NodePtr<N> {
94    fn clone(&self) -> Self {
95        Self(self.0)
96    }
97}
98impl<N> Copy for NodePtr<N> {}
99
100use std::fmt;
101impl<N> fmt::Debug for NodePtr<N> {
102    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
103        f.debug_struct("NodePtr").finish()
104    }
105}
106impl<N> fmt::Debug for NodeGuard<'_, N> {
107    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
108        f.debug_struct("NodeGuard").finish()
109    }
110}
111
112impl<N> NodePtr<N> {
113    pub fn ptr_eq(self, other: Self) -> bool {
114        std::ptr::eq(self.0.as_ptr(), other.0.as_ptr())
115    }
116
117    pub unsafe fn lookup_unchecked<'gg>(&self) -> NodeGuard<'gg, N> {
118        NodeGuard {
119            inside: &*self.0.as_ptr(),
120            invariant: PhantomData,
121        }
122    }
123}
124
125use std::hash::{Hash, Hasher};
126impl<N> Hash for NodePtr<N> {
127    fn hash<H: Hasher>(&self, state: &mut H) {
128        self.0.hash(state);
129    }
130}
131
132use std::cmp::Ordering;
133impl<N> PartialOrd for NodePtr<N> {
134    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
135        Some(self.cmp(other))
136    }
137}
138impl<N> Ord for NodePtr<N> {
139    fn cmp(&self, other: &Self) -> Ordering {
140        self.0.cmp(&other.0)
141    }
142}
143
144impl<N> PartialEq for NodePtr<N> {
145    fn eq(&self, other: &Self) -> bool {
146        self.0 == other.0
147    }
148}
149impl<N> Eq for NodePtr<N> {}
150
151impl<'gg, N> NodeGuard<'gg, N> {
152    pub unsafe fn make_ptr(&self) -> NodePtr<N> {
153        // ideally would not have to cast to *mut N, but will need to until we get NonNullConst
154        NodePtr(NonNull::new_unchecked(self.inside as *const N as *mut N))
155    }
156
157    pub unsafe fn lookup_ptr(&self, NodePtr(ptr): NodePtr<N>) -> NodeGuard<'gg, N> {
158        NodeGuard {
159            inside: &*ptr.as_ptr(),
160            invariant: self.invariant,
161        }
162    }
163
164    pub fn node(&self) -> &'gg N {
165        self.inside
166    }
167}
168
169impl<N> PartialEq for NodeGuard<'_, N> {
170    fn eq(&self, other: &Self) -> bool {
171        std::ptr::eq(self.inside, other.inside)
172    }
173}
arena_graph/raw.rs

arena_graph/
raw.rs
