orx_selfref_col/
selfref_col.rs

1use crate::node::Node;
2use crate::{CoreCol, MemoryPolicy, MemoryState, NodeIdx, NodeIdxError, NodePtr, Variant};
3use core::ops::{Deref, DerefMut};
4use orx_pinned_vec::PinnedVec;
5
6/// `SelfRefCol` is a core data structure to conveniently build safe and efficient self referential collections, such as linked lists and trees.
7pub struct SelfRefCol<V, M, P>
8where
9    V: Variant,
10    M: MemoryPolicy<V>,
11    P: PinnedVec<Node<V>>,
12{
13    core: CoreCol<V, P>,
14    policy: M,
15    state: MemoryState,
16}
17
18impl<V, M, P> Default for SelfRefCol<V, M, P>
19where
20    V: Variant,
21    M: MemoryPolicy<V>,
22    P: PinnedVec<Node<V>> + Default,
23{
24    fn default() -> Self {
25        Self::new()
26    }
27}
28
29impl<V, M, P> Deref for SelfRefCol<V, M, P>
30where
31    V: Variant,
32    M: MemoryPolicy<V>,
33    P: PinnedVec<Node<V>>,
34{
35    type Target = CoreCol<V, P>;
36
37    fn deref(&self) -> &Self::Target {
38        &self.core
39    }
40}
41
42impl<V, M, P> DerefMut for SelfRefCol<V, M, P>
43where
44    V: Variant,
45    M: MemoryPolicy<V>,
46    P: PinnedVec<Node<V>>,
47{
48    fn deref_mut(&mut self) -> &mut Self::Target {
49        &mut self.core
50    }
51}
52
53impl<V, M, P> SelfRefCol<V, M, P>
54where
55    V: Variant,
56    M: MemoryPolicy<V>,
57    P: PinnedVec<Node<V>>,
58{
59    /// Creates a new empty collection.
60    pub fn new() -> Self
61    where
62        P: Default,
63    {
64        Self {
65            core: CoreCol::new(),
66            policy: M::default(),
67            state: MemoryState::default(),
68        }
69    }
70
71    /// Breaks the self referential collection into its core collection and memory state.
72    pub fn into_inner(self) -> (CoreCol<V, P>, MemoryState) {
73        let state = self.memory_state();
74        (self.core, state)
75    }
76
77    pub(crate) fn from_raw_parts(core: CoreCol<V, P>, policy: M, state: MemoryState) -> Self {
78        Self {
79            core,
80            policy,
81            state,
82        }
83    }
84
85    pub(crate) fn with_active_nodes(nodes: P) -> Self {
86        Self {
87            core: CoreCol::with_active_nodes(nodes),
88            policy: M::default(),
89            state: MemoryState::default(),
90        }
91    }
92
93    // get
94
95    /// Memory state of the collection.
96    pub fn memory_state(&self) -> MemoryState {
97        self.state
98    }
99
100    /// Memory policy of the collection.
101    pub fn memory(&self) -> &M {
102        &self.policy
103    }
104
105    /// Closes the node with the given `node_ptr`, returns its taken out value,
106    /// and reclaims closed nodes if necessary.
107    pub fn close_and_reclaim(&mut self, node_ptr: NodePtr<V>) -> V::Item {
108        let data = self.core.close(node_ptr);
109
110        let state_changed = M::reclaim_closed_nodes(self, node_ptr);
111        self.update_state(state_changed);
112
113        data
114    }
115
116    /// Succeeding the operation of closing of node with the given `node_ptr`,
117    /// reclaims closed nodes if necessary.
118    ///
119    /// Returns whether the memory state changed.
120    pub fn reclaim_from_closed_node(&mut self, node_ptr: NodePtr<V>) -> bool {
121        let state_changed = M::reclaim_closed_nodes(self, node_ptr);
122        self.update_state(state_changed);
123        state_changed
124    }
125
126    /// If `state_changed` is true, proceeds to the next memory state.
127    #[inline(always)]
128    pub fn update_state(&mut self, state_changed: bool) {
129        if state_changed {
130            self.state = self.state.successor_state();
131        }
132    }
133
134    /// Returns a reference to the node with the given `NodeIdx`;
135    /// returns None if the index is invalid.
136    #[inline(always)]
137    pub fn node_from_idx(&self, idx: NodeIdx<V>) -> Option<&Node<V>> {
138        // SAFETY: it is always safe to call PinnedVec::contains_ptr
139        match idx.is_in_state(self.state) && self.nodes().contains_ptr(unsafe { idx.ptr() }) {
140            // SAFETY: Since both conditions are satisfied, it is safe to dereference the node.
141            true => Some(unsafe { &*idx.ptr() }),
142            false => None,
143        }
144    }
145
146    /// Tries to create a reference to the node with the given `NodeIdx`;
147    /// returns the error if the index is invalid.
148    #[inline(always)]
149    pub fn try_node_from_idx(&self, idx: NodeIdx<V>) -> Result<&Node<V>, NodeIdxError> {
150        // SAFETY: it is always safe to call PinnedVec::contains_ptr
151        match self.nodes().contains_ptr(unsafe { idx.ptr() }) {
152            true => match idx.is_in_state(self.state) {
153                // SAFETY: Since both conditions are satisfied, it is safe to dereference the node.
154                true => Ok(unsafe { &*idx.ptr() }),
155                false => Err(NodeIdxError::ReorganizedCollection),
156            },
157            false => Err(NodeIdxError::OutOfBounds),
158        }
159    }
160
161    /// Returns the node index error if the index is invalid.
162    /// Returns None if it is valid.
163    #[inline(always)]
164    pub fn node_idx_error(&self, idx: NodeIdx<V>) -> Option<NodeIdxError> {
165        match self.try_node_from_idx(idx) {
166            Ok(node) => match node.is_active() {
167                true => None,
168                false => Some(NodeIdxError::RemovedNode),
169            },
170            Err(err) => Some(err),
171        }
172    }
173
174    /// Tries to get a valid pointer to the node with the given `NodeIdx`;
175    /// returns the error if the index is invalid.
176    #[inline(always)]
177    pub fn try_get_ptr(&self, idx: NodeIdx<V>) -> Result<NodePtr<V>, NodeIdxError> {
178        // SAFETY: it is always safe to call PinnedVec::contains_ptr
179        match self.nodes().contains_ptr(unsafe { idx.ptr() }) {
180            true => match idx.is_in_state(self.state) {
181                true => {
182                    // SAFETY: Since both conditions are satisfied, it is safe to dereference the node.
183                    let ptr = unsafe { idx.ptr() };
184                    match unsafe { &*ptr }.is_active() {
185                        true => Ok(NodePtr::new(ptr)),
186                        false => Err(NodeIdxError::RemovedNode),
187                    }
188                }
189                false => Err(NodeIdxError::ReorganizedCollection),
190            },
191            false => Err(NodeIdxError::OutOfBounds),
192        }
193    }
194
195    /// Tries to get a valid pointer to the node with the given `NodeIdx`;
196    /// returns None if the index is invalid.
197    #[inline(always)]
198    pub fn get_ptr(&self, idx: NodeIdx<V>) -> Option<NodePtr<V>> {
199        // SAFETY: it is always safe to call PinnedVec::contains_ptr
200        match self.nodes().contains_ptr(unsafe { idx.ptr() }) {
201            true => match idx.is_in_state(self.state) {
202                true => {
203                    // SAFETY: Since both conditions are satisfied, it is safe to dereference the node.
204                    let ptr = unsafe { idx.ptr() };
205                    match unsafe { &*ptr }.is_active() {
206                        true => Some(NodePtr::new(ptr)),
207                        false => None,
208                    }
209                }
210                false => None,
211            },
212            false => None,
213        }
214    }
215
216    // mut
217
218    /// Clears the collection and changes the memory state.
219    pub fn clear(&mut self) {
220        self.core.clear_core();
221        self.state = self.state.successor_state();
222    }
223
224    /// Returns a mutable reference to the node with the given `NodeIdx`;
225    /// returns None if the index is invalid.
226    #[inline(always)]
227    pub fn node_mut_from_idx(&mut self, idx: NodeIdx<V>) -> Option<&mut Node<V>> {
228        // SAFETY: it is always safe to call PinnedVec::contains_ptr
229        match idx.is_in_state(self.state) && self.nodes().contains_ptr(unsafe { idx.ptr() }) {
230            true => Some(unsafe { &mut *idx.ptr_mut() }),
231            false => None,
232        }
233    }
234
235    /// Tries to create a mutable reference to the node with the given `NodeIdx`;
236    /// returns the error if the index is invalid.
237    #[inline(always)]
238    pub fn try_node_mut_from_idx(&mut self, idx: NodeIdx<V>) -> Result<&mut Node<V>, NodeIdxError> {
239        // SAFETY: it is always safe to call PinnedVec::contains_ptr
240        match self.nodes().contains_ptr(unsafe { idx.ptr() }) {
241            true => match idx.is_in_state(self.state) {
242                true => Ok(unsafe { &mut *idx.ptr_mut() }),
243                false => Err(NodeIdxError::ReorganizedCollection),
244            },
245            false => Err(NodeIdxError::OutOfBounds),
246        }
247    }
248
249    /// Pushes the element with the given `data` and returns its index.
250    pub fn push_get_idx(&mut self, data: V::Item) -> NodeIdx<V> {
251        let node_ptr = self.push(data);
252        NodeIdx::new(self.memory_state(), node_ptr)
253    }
254}
orx_selfref_col/selfref_col.rs

orx_selfref_col/
selfref_col.rs
