osiris/types/
list.rs

1use core::marker::PhantomData;
2
3use crate::error::Result;
4
5use super::traits::{Get, GetMut};
6
7#[allow(dead_code)]
8pub struct List<Tag, T: Copy> {
9    head: Option<T>,
10    tail: Option<T>,
11    len: usize,
12    _tag: PhantomData<Tag>,
13}
14
15#[allow(dead_code)]
16pub trait Linkable<Tag, T> {
17    fn links(&self) -> &Links<Tag, T>;
18    fn links_mut(&mut self) -> &mut Links<Tag, T>;
19}
20
21#[allow(dead_code)]
22#[proc_macros::fmt]
23#[derive(Clone, Copy, PartialEq, Eq)]
24pub struct Links<Tag, T> {
25    prev: Option<T>,
26    next: Option<T>,
27    _tag: PhantomData<Tag>,
28}
29
30#[allow(dead_code)]
31impl<Tag, T> Links<Tag, T> {
32    pub const fn new() -> Self {
33        Self {
34            prev: None,
35            next: None,
36            _tag: PhantomData,
37        }
38    }
39}
40
41#[allow(dead_code)]
42impl<Tag, T: Copy + PartialEq> List<Tag, T> {
43    pub const fn new() -> Self {
44        Self {
45            head: None,
46            tail: None,
47            len: 0,
48            _tag: PhantomData,
49        }
50    }
51
52    pub fn head(&self) -> Option<T> {
53        self.head
54    }
55
56    pub fn tail(&self) -> Option<T> {
57        self.tail
58    }
59
60    pub fn len(&self) -> usize {
61        self.len
62    }
63
64    pub fn is_empty(&self) -> bool {
65        self.len == 0
66    }
67
68    pub fn push_front<S: Get<T> + GetMut<T>>(&mut self, id: T, storage: &mut S) -> Result<()>
69    where
70        <S as Get<T>>::Output: Linkable<Tag, T>,
71    {
72        self.detach_links(id, storage)?;
73
74        match self.head {
75            Some(old_head) => {
76                let (new_node, old_head_node) = storage.get2_mut(id, old_head);
77                let (new_node, old_head_node) = (
78                    new_node.ok_or(kerr!(NotFound))?,
79                    old_head_node.unwrap_or_else(|| {
80                        bug!("node linked from list does not exist in storage.");
81                    }),
82                );
83
84                new_node.links_mut().prev = None;
85                new_node.links_mut().next = Some(old_head);
86
87                old_head_node.links_mut().prev = Some(id);
88            }
89            None => {
90                let new_node = storage.get_mut(id).ok_or(kerr!(NotFound))?;
91                new_node.links_mut().prev = None;
92                new_node.links_mut().next = None;
93                self.tail = Some(id);
94            }
95        }
96
97        self.head = Some(id);
98        self.len += 1;
99        Ok(())
100    }
101
102    /// Pushes `id` to the back of the list. If `id` is already in the list, it is moved to the back.
103    ///
104    /// Errors if `id` does not exist in `storage` or if the node corresponding to `id` is linked but not in the list.
105    pub fn push_back<S: Get<T> + GetMut<T>>(&mut self, id: T, storage: &mut S) -> Result<()>
106    where
107        <S as Get<T>>::Output: Linkable<Tag, T>,
108    {
109        self.detach_links(id, storage)?;
110
111        match self.tail {
112            Some(old_tail) => {
113                let (new_node, old_tail_node) = storage.get2_mut(id, old_tail);
114                let (new_node, old_tail_node) = (
115                    new_node.ok_or(kerr!(NotFound))?,
116                    old_tail_node.unwrap_or_else(|| {
117                        bug!("node linked from list does not exist in storage.");
118                    }),
119                );
120
121                new_node.links_mut().next = None;
122                new_node.links_mut().prev = Some(old_tail);
123
124                old_tail_node.links_mut().next = Some(id);
125            }
126            None => {
127                let new_node = storage.get_mut(id).ok_or(kerr!(NotFound))?;
128                new_node.links_mut().next = None;
129                new_node.links_mut().prev = None;
130                self.head = Some(id);
131            }
132        }
133
134        self.tail = Some(id);
135        self.len += 1;
136        Ok(())
137    }
138
139    pub fn pop_front<S: Get<T> + GetMut<T>>(&mut self, storage: &mut S) -> Result<Option<T>>
140    where
141        <S as Get<T>>::Output: Linkable<Tag, T>,
142    {
143        let Some(id) = self.head else {
144            return Ok(None);
145        };
146
147        self.remove(id, storage)?;
148        Ok(Some(id))
149    }
150
151    pub fn pop_back<S: Get<T> + GetMut<T>>(&mut self, storage: &mut S) -> Result<Option<T>>
152    where
153        <S as Get<T>>::Output: Linkable<Tag, T>,
154    {
155        let Some(id) = self.tail else {
156            return Ok(None);
157        };
158
159        self.remove(id, storage)?;
160        Ok(Some(id))
161    }
162
163    /// Removes `id` from the list. Errors if `id` does not exist in `storage` or if the node corresponding to `id` is not linked.
164    pub fn remove<S: Get<T> + GetMut<T>>(&mut self, id: T, storage: &mut S) -> Result<()>
165    where
166        <S as Get<T>>::Output: Linkable<Tag, T>,
167    {
168        let (prev, next, linked) = {
169            let node = storage.get(id).ok_or(kerr!(NotFound))?;
170            let links = node.links();
171            let linked = self.head == Some(id)
172                || self.tail == Some(id)
173                || links.prev.is_some()
174                || links.next.is_some();
175            (links.prev, links.next, linked)
176        };
177
178        if !linked {
179            return Err(kerr!(NotFound));
180        }
181
182        if let Some(prev_id) = prev {
183            let prev_node = storage.get_mut(prev_id).unwrap_or_else(|| {
184                bug!("node linked from list does not exist in storage.");
185            });
186            prev_node.links_mut().next = next;
187        } else {
188            self.head = next;
189        }
190
191        if let Some(next_id) = next {
192            let next_node = storage.get_mut(next_id).unwrap_or_else(|| {
193                bug!("node linked from list does not exist in storage.");
194            });
195            next_node.links_mut().prev = prev;
196        } else {
197            self.tail = prev;
198        }
199
200        let node = storage.get_mut(id).ok_or(kerr!(NotFound))?;
201        node.links_mut().prev = None;
202        node.links_mut().next = None;
203
204        self.len = self.len.saturating_sub(1);
205        Ok(())
206    }
207
208    /// Detaches `id` from any list it is currently in. If `id` is not in any list but is linked, the links are cleared.
209    fn detach_links<S: Get<T> + GetMut<T>>(&mut self, id: T, storage: &mut S) -> Result<()>
210    where
211        <S as Get<T>>::Output: Linkable<Tag, T>,
212    {
213        let linked = {
214            let node = storage.get(id).ok_or(kerr!(NotFound))?;
215            let links = node.links();
216            self.head == Some(id)
217                || self.tail == Some(id)
218                || links.prev.is_some()
219                || links.next.is_some()
220        };
221
222        if linked {
223            self.remove(id, storage)?;
224        } else {
225            let node = storage.get_mut(id).ok_or(kerr!(NotFound))?;
226            node.links_mut().prev = None;
227            node.links_mut().next = None;
228        }
229
230        Ok(())
231    }
232}
233
234#[cfg(test)]
235mod tests {
236    use core::borrow::Borrow;
237
238    use super::{Linkable, Links, List};
239    use crate::types::{
240        array::IndexMap,
241        traits::{Get, ToIndex},
242    };
243
244    #[proc_macros::fmt]
245    #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
246    struct Id(usize);
247
248    impl ToIndex for Id {
249        fn to_index<Q: Borrow<Self>>(idx: Option<Q>) -> usize {
250            idx.as_ref().map_or(0, |k| k.borrow().0)
251        }
252    }
253
254    #[derive(Clone, Copy)]
255    struct TestTag;
256
257    struct Node {
258        links: Links<TestTag, Id>,
259    }
260
261    impl Node {
262        fn new() -> Self {
263            Self {
264                links: Links::new(),
265            }
266        }
267    }
268
269    impl Linkable<TestTag, Id> for Node {
270        fn links(&self) -> &Links<TestTag, Id> {
271            &self.links
272        }
273
274        fn links_mut(&mut self) -> &mut Links<TestTag, Id> {
275            &mut self.links
276        }
277    }
278
279    fn storage() -> IndexMap<Id, Node, 8> {
280        let mut map = IndexMap::new();
281        for i in 0..4 {
282            assert!(map.insert(&Id(i), Node::new()).is_ok());
283        }
284        map
285    }
286
287    #[test]
288    fn push_front_and_remove() {
289        let mut s = storage();
290        let mut list = List::<TestTag, Id>::new();
291
292        list.push_front(Id(1), &mut s).unwrap();
293        list.push_front(Id(2), &mut s).unwrap();
294        list.push_front(Id(3), &mut s).unwrap();
295
296        assert_eq!(list.head(), Some(Id(3)));
297        assert_eq!(list.tail(), Some(Id(1)));
298        assert_eq!(list.len(), 3);
299
300        list.remove(Id(2), &mut s).unwrap();
301        assert_eq!(list.head(), Some(Id(3)));
302        assert_eq!(list.tail(), Some(Id(1)));
303        assert_eq!(list.len(), 2);
304
305        let n3 = s.get(Id(3)).unwrap();
306        let n1 = s.get(Id(1)).unwrap();
307        assert_eq!(n3.links().next, Some(Id(1)));
308        assert_eq!(n1.links().prev, Some(Id(3)));
309    }
310
311    #[test]
312    fn push_back_and_remove() {
313        let mut s = storage();
314        let mut list = List::<TestTag, Id>::new();
315
316        list.push_back(Id(1), &mut s).unwrap();
317        let _ = list.remove(Id(1), &mut s);
318
319        assert_eq!(list.head(), None);
320        assert_eq!(list.tail(), None);
321        assert_eq!(list.len(), 0);
322    }
323
324    #[test]
325    fn push_back_same_id_reinserts() {
326        let mut s = storage();
327        let mut list = List::<TestTag, Id>::new();
328
329        list.push_back(Id(1), &mut s).unwrap();
330        list.push_back(Id(1), &mut s).unwrap();
331
332        assert_eq!(list.head(), Some(Id(1)));
333        assert_eq!(list.tail(), Some(Id(1)));
334        assert_eq!(list.len(), 1);
335
336        let n1 = s.get(Id(1)).unwrap();
337        assert_eq!(n1.links().prev, None);
338        assert_eq!(n1.links().next, None);
339    }
340
341    #[test]
342    fn pop_back_ordered() {
343        let mut s = storage();
344        let mut list = List::<TestTag, Id>::new();
345
346        list.push_back(Id(1), &mut s).unwrap();
347        list.push_back(Id(2), &mut s).unwrap();
348        list.push_back(Id(3), &mut s).unwrap();
349
350        assert_eq!(list.pop_back(&mut s).unwrap(), Some(Id(3)));
351        assert_eq!(list.pop_back(&mut s).unwrap(), Some(Id(2)));
352        assert_eq!(list.pop_back(&mut s).unwrap(), Some(Id(1)));
353        assert_eq!(list.pop_back(&mut s).unwrap(), None);
354        assert!(list.is_empty());
355    }
356
357    #[test]
358    fn pop_front_ordered() {
359        let mut s = storage();
360        let mut list = List::<TestTag, Id>::new();
361
362        list.push_back(Id(1), &mut s).unwrap();
363        list.push_back(Id(2), &mut s).unwrap();
364        list.push_back(Id(3), &mut s).unwrap();
365
366        assert_eq!(list.pop_front(&mut s).unwrap(), Some(Id(1)));
367        assert_eq!(list.pop_front(&mut s).unwrap(), Some(Id(2)));
368        assert_eq!(list.pop_front(&mut s).unwrap(), Some(Id(3)));
369        assert_eq!(list.pop_front(&mut s).unwrap(), None);
370        assert!(list.is_empty());
371    }
372}
osiris/types/list.rs

osiris/types/
list.rs
