1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
use std::{ marker::PhantomData, ptr::NonNull, }; use super::TempArena; // Prior Art: This linked list implementation is heavily inspired by Rust's own `LinkedList` // implementation. Instead of dealing with challenging lifetime issues, we follow suit with // `Option<NonNull<Node<T>>>`. One of the biggest differences, is that we aren't (at the moment) // tracking front and tail nodes, and we don't drop anything pushed to the temp arena. // TODO: This implmentation may change if we introduce a long-term memory arena that can be used as // an allocator. Then, this implementation may need to implement `Drop`. struct Node<T> { pub value: T, pub next: Option<NonNull<Node<T>>>, } impl<T> Node<T> { #[inline] const fn new(value: T, next: Option<NonNull<Node<T>>>) -> Self { Self { value, next } } } /// A simple linked-list implementation that does LIFO stack-based insertions. pub struct List<T> { next: Option<NonNull<Node<T>>>, len: usize, } impl<T> List<T> { /// Creates a new `List<T>`. /// /// # Example /// ``` ///# use ngen::arena::List; /// let mut list = List::<u32>::new(); /// ``` #[inline] pub fn new() -> Self { Self { next: None, len: 0, } } /// Pushes a new element into the list, replacing the head element. /// /// # Example /// ``` ///# use ngen::arena::{List, TempArena}; ///# let mut temp_arena = TempArena::with_capacity(1024).unwrap(); /// let mut list = List::new(); /// list.push(&mut temp_arena, 42); /// ``` #[inline] pub fn push(&mut self, arena: &TempArena, value: T) { let ptr = arena.push(Node::new(value, self.next.take())); self.next = NonNull::new(ptr as *mut _); self.len += 1; } /// Returns an iterator over all elements in the list. /// /// # Example /// ``` ///# use ngen::arena::{List, TempArena}; ///# let mut temp_arena = TempArena::with_capacity(1024).unwrap(); /// let mut list = List::new(); /// for i in 0..42 { /// list.push(&mut temp_arena, i); /// } /// /// // Items in the list are stored in a LIFO manner. /// let mut current = 41; /// for v in list.iter() { /// assert_eq!(v, ¤t); /// current -= 1; /// } /// ``` #[inline] pub fn iter(&self) -> Iter<'_, T> { Iter { next: self.next, marker: PhantomData, } } /// Returns a mutable iterator over all elements in the list. /// /// # Example /// ``` ///# use ngen::arena::{List, TempArena}; ///# let mut temp_arena = TempArena::with_capacity(1024).unwrap(); /// let mut list = List::new(); /// for i in 0..42 { /// list.push(&mut temp_arena, i); /// } /// /// for v in list.iter_mut() { /// *v *= 2; /// } /// ``` #[inline] pub fn iter_mut(&mut self) -> IterMut<'_, T> { IterMut { next: self.next, marker: PhantomData, } } } /// An iterator over a linked list. pub struct Iter<'l, T> { next: Option<NonNull<Node<T>>>, marker: PhantomData<&'l Node<T>>, } impl<'l, T> Iterator for Iter<'l, T> { type Item = &'l T; #[inline] fn next(&mut self) -> Option<Self::Item> { self.next.take().map(|node| unsafe { let node = &*node.as_ptr(); self.next = node.next; &node.value }) } } /// A mutable iterator over a linked list. pub struct IterMut<'l, T> { next: Option<NonNull<Node<T>>>, marker: PhantomData<&'l Node<T>>, } impl<'l, T> Iterator for IterMut<'l, T> { type Item = &'l mut T; #[inline] fn next(&mut self) -> Option<Self::Item> { self.next.take().map(|node| unsafe { let node = &mut *node.as_ptr(); self.next = node.next; &mut node.value }) } }