generational_cache/collections/
list.rs

1//! Module providing abstractions for a linked list implementation.
2
3use core::fmt::{self, Debug, Display};
4
5use crate::{
6    arena::{Arena, ArenaError, Entry, Index},
7    vector::Vector,
8};
9
10/// Represents a link to node in the linked list.
11#[derive(Clone, Copy, PartialEq, Debug)]
12pub struct Link {
13    pub index: Index,
14}
15
16/// Represents a node in a linked list.
17#[derive(Clone, Copy, PartialEq, Debug)]
18pub struct Node<T> {
19    pub value: T,
20
21    pub next: Option<Link>,
22    pub prev: Option<Link>,
23}
24
25impl<T> Node<T> {
26    pub fn with_value(value: T) -> Self {
27        Self {
28            value,
29            next: None,
30            prev: None,
31        }
32    }
33}
34
35impl<T> Default for Node<T>
36where
37    T: Default,
38{
39    fn default() -> Self {
40        Self {
41            value: Default::default(),
42            next: Default::default(),
43            prev: Default::default(),
44        }
45    }
46}
47
48/// A double-linked linked list implementation using a generational [`Arena`] for allocation.
49pub struct LinkedList<V, T> {
50    backing_arena: Arena<V, Node<T>>,
51
52    head: Option<Link>,
53    tail: Option<Link>,
54
55    len: usize,
56}
57
58/// Error type associated with list operations.
59#[derive(Debug)]
60pub enum ListError<VE> {
61    /// Used when there is an error in an operation performed on the underlying arena.
62    ArenaError(ArenaError<VE>),
63
64    /// Used when a link is not associated with a node in the underlying arena.
65    LinkBroken,
66
67    /// Used when attempting to remove items from an empty list.
68    ListEmpty,
69}
70
71impl<VE> Display for ListError<VE>
72where
73    VE: Debug,
74{
75    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
76        write!(f, "{self:?}")
77    }
78}
79
80/// Type alias for arena entries corresponding to [`LinkedList`] [`Node`] instances.
81pub type LinkedListArenaEntry<T> = Entry<Node<T>>;
82
83impl<V, T> LinkedList<V, T>
84where
85    V: Vector<Entry<Node<T>>>,
86{
87    /// Creates a new [`LinkedList`] with given the backing [`Vector`] for the underlying [`Arena`].
88    pub fn with_backing_vector(vector: V) -> Self {
89        Self {
90            backing_arena: Arena::with_vector(vector),
91            head: None,
92            tail: None,
93            len: 0,
94        }
95    }
96
97    /// Removes all elements from this [`LinkedList`].
98    pub fn clear(&mut self) -> Result<(), ListError<V::Error>> {
99        self.backing_arena.clear().map_err(ListError::ArenaError)?;
100
101        self.head = None;
102        self.tail = None;
103        self.len = 0;
104
105        Ok(())
106    }
107
108    /// Reserves memory for the give number of additional elements in this [`LinkedList`].
109    pub fn reserve(&mut self, additional: usize) -> Result<(), ListError<V::Error>> {
110        let remaining = self.capacity() - self.len();
111
112        if remaining >= additional {
113            return Ok(());
114        }
115
116        self.backing_arena
117            .reserve(additional)
118            .map_err(ListError::ArenaError)
119    }
120
121    /// Returns the number of elements this [`LinkedList`] is capable of storing.
122    ///
123    /// Since this [`LinkedList`] uses an [`Arena`] for allocation, it's capacity is subject to the
124    /// capacity of the underlying [`Arena`].
125    pub fn capacity(&self) -> usize {
126        self.backing_arena.capacity()
127    }
128
129    /// Returns the number of elements stored in this [`LinkedList`].
130    pub fn len(&self) -> usize {
131        self.len
132    }
133
134    /// Returns whether this [`LinkedList`] is empty.
135    pub fn is_empty(&self) -> bool {
136        self.head.is_none()
137    }
138
139    /// Returns a mutable reference to the [`Node`] referenced by the given [`Link`].
140    fn get_node_mut(&mut self, link: &Link) -> Option<&mut Node<T>> {
141        self.backing_arena.get_mut(&link.index)
142    }
143
144    /// Returns an immutable reference to the [`Node`] referenced by the given [`Link`].
145    fn get_node(&self, link: &Link) -> Option<&Node<T>> {
146        self.backing_arena.get(&link.index)
147    }
148
149    /// Returns a mutable reference to the element stored in the [`Node`] at the given [`Link`].
150    pub fn get_mut(&mut self, link: &Link) -> Option<&mut T> {
151        Some(&mut self.get_node_mut(link)?.value)
152    }
153
154    /// Returns an imutable reference to the element stored in the [`Node`] at the given [`Link`].
155    pub fn get(&self, link: &Link) -> Option<&T> {
156        Some(&self.get_node(link)?.value)
157    }
158
159    fn link_head(&mut self, link: Link) -> Option<()> {
160        self.get_node_mut(&link)?.next = self.head;
161
162        if let Some(head_link) = self.head {
163            self.get_node_mut(&head_link)?.prev = Some(link);
164        } else {
165            self.tail = Some(link);
166        }
167
168        self.head = Some(link);
169
170        self.len += 1;
171
172        Some(())
173    }
174
175    fn link_tail(&mut self, link: Link) -> Option<()> {
176        self.get_node_mut(&link)?.prev = self.tail;
177
178        if let Some(tail_link) = self.tail {
179            self.get_node_mut(&tail_link)?.next = Some(link);
180        } else {
181            self.head = Some(link);
182        }
183
184        self.tail = Some(link);
185
186        self.len += 1;
187
188        Some(())
189    }
190
191    /// Pushes the given element to the front of this [`LinkedList`].
192    pub fn push_front(&mut self, value: T) -> Result<Link, ListError<V::Error>> {
193        let node_index = self
194            .backing_arena
195            .insert(Node::with_value(value))
196            .map_err(ListError::ArenaError)?;
197
198        let node_link = Link { index: node_index };
199
200        self.link_head(node_link).ok_or(ListError::LinkBroken)?;
201
202        Ok(node_link)
203    }
204
205    /// Pushes the given element to the back of this [`LinkedList`].
206    pub fn push_back(&mut self, value: T) -> Result<Link, ListError<V::Error>> {
207        let node_index = self
208            .backing_arena
209            .insert(Node::with_value(value))
210            .map_err(ListError::ArenaError)?;
211
212        let node_link = Link { index: node_index };
213
214        self.link_tail(node_link).ok_or(ListError::LinkBroken)?;
215
216        Ok(node_link)
217    }
218
219    /// Peeks the element at the front of this list.
220    pub fn peek_front(&self) -> Option<&T> {
221        self.get(self.head.as_ref()?)
222    }
223
224    /// Peeks the element at the back of this list.
225    pub fn peek_back(&self) -> Option<&T> {
226        self.get(self.tail.as_ref()?)
227    }
228
229    fn unlink_head(&mut self) -> Option<Link> {
230        let head_link = self.head?;
231        self.head = self.get_node(&head_link)?.next;
232
233        let to_unlink = match self.head {
234            Some(new_head_link) => &mut self.get_node_mut(&new_head_link)?.prev,
235            None => &mut self.tail,
236        };
237
238        *to_unlink = None;
239
240        self.len -= 1;
241
242        Some(head_link)
243    }
244
245    fn unlink_tail(&mut self) -> Option<Link> {
246        let tail_link = self.tail?;
247        self.tail = self.get_node(&tail_link)?.prev;
248
249        let to_unlink = match self.tail {
250            Some(new_tail_link) => &mut self.get_node_mut(&new_tail_link)?.next,
251            None => &mut self.head,
252        };
253
254        *to_unlink = None;
255
256        self.len -= 1;
257
258        Some(tail_link)
259    }
260
261    fn unlink(&mut self, link: &Link) -> Option<Link> {
262        match Some(link) {
263            link if link == self.head.as_ref() => self.unlink_head(),
264            link if link == self.tail.as_ref() => self.unlink_tail(),
265            _ => {
266                let node = self.get_node_mut(link)?;
267
268                let prev_link = node.prev?;
269                let next_link = node.next?;
270
271                node.next = None;
272                node.prev = None;
273
274                self.get_node_mut(&prev_link)?.next = Some(next_link);
275                self.get_node_mut(&next_link)?.prev = Some(prev_link);
276
277                self.len -= 1;
278
279                Some(*link)
280            }
281        }
282    }
283
284    fn reclaim(&mut self, link: &Link) -> Option<T> {
285        let node = self.backing_arena.remove(&link.index)?;
286        Some(node.value)
287    }
288
289    /// Removes the element referenced by the given link.
290    pub fn remove(&mut self, link: &Link) -> Option<T> {
291        let link = self.unlink(link)?;
292        self.reclaim(&link)
293    }
294
295    /// Removes the element at the front of this list.
296    pub fn pop_front(&mut self) -> Option<T> {
297        let link = self.unlink_head()?;
298        self.reclaim(&link)
299    }
300
301    /// Removes the element at the back of this list.
302    pub fn pop_back(&mut self) -> Option<T> {
303        let link = self.unlink_tail()?;
304        self.reclaim(&link)
305    }
306
307    /// Shifts the element at the given [`Link`] to the front of this list.
308    pub fn shift_push_front(&mut self, link: &Link) -> Option<()> {
309        let link = self.unlink(link)?;
310        self.link_head(link)
311    }
312
313    /// Shifts the element at the given [`Link`] to the back of this list.
314    pub fn shift_push_back(&mut self, link: &Link) -> Option<()> {
315        let link = self.unlink(link)?;
316        self.link_tail(link)
317    }
318
319    /// Returns an iterator to iterate over the elements in this list.
320    pub fn iter(&self) -> Iter<'_, V, T> {
321        Iter {
322            list: self,
323            cursor: self.head.as_ref(),
324        }
325    }
326}
327
328impl<V, T> Default for LinkedList<V, T>
329where
330    V: Default + Vector<Entry<Node<T>>>,
331{
332    fn default() -> Self {
333        Self::with_backing_vector(V::default())
334    }
335}
336
337/// Iterator implementation to iterate over the items in a [`LinkedList`].
338pub struct Iter<'a, V, T> {
339    list: &'a LinkedList<V, T>,
340    cursor: Option<&'a Link>,
341}
342
343impl<'a, V, T> Iterator for Iter<'a, V, T>
344where
345    V: Vector<Entry<Node<T>>>,
346{
347    type Item = (&'a Link, &'a T);
348
349    fn next(&mut self) -> Option<Self::Item> {
350        let cursor = self.cursor.take()?;
351        let cursor_node = self.list.get_node(cursor)?;
352
353        self.cursor = cursor_node.next.as_ref();
354
355        Some((cursor, &cursor_node.value))
356    }
357}
358
359impl<'a, V, T> IntoIterator for &'a LinkedList<V, T>
360where
361    V: Vector<Entry<Node<T>>>,
362{
363    type Item = (&'a Link, &'a T);
364
365    type IntoIter = Iter<'a, V, T>;
366
367    fn into_iter(self) -> Self::IntoIter {
368        self.iter()
369    }
370}
371
372#[doc(hidden)]
373pub mod tests {
374    use super::{
375        super::super::{
376            arena::{ArenaError, Entry},
377            collections::list::ListError,
378            vector::Vector,
379        },
380        LinkedList, Node,
381    };
382    use core::fmt::Debug;
383
384    pub fn _test_list_invariants<T, V>(mut list: LinkedList<V, T>)
385    where
386        V: Vector<Entry<Node<T>>>,
387        T: Debug + PartialEq + Default,
388    {
389        list.clear().unwrap();
390
391        let capacity = list.capacity();
392
393        assert!(list.is_empty());
394
395        assert_eq!(list.peek_front(), None);
396        assert_eq!(list.peek_back(), None);
397
398        for _ in 0..capacity {
399            list.push_back(T::default()).unwrap();
400        }
401
402        assert!(list.len() == list.capacity());
403
404        let mut i = 0;
405        for (_, t) in &list {
406            assert_eq!(t, &T::default());
407            i += 1;
408        }
409
410        assert_eq!(i, list.len());
411
412        assert_eq!(list.peek_front(), Some(&T::default()));
413        assert_eq!(list.peek_back(), Some(&T::default()));
414
415        match list.push_front(T::default()) {
416            Err(ListError::ArenaError(ArenaError::OutOfMemory)) => {}
417            _ => unreachable!("Out of memory not triggered"),
418        };
419
420        match list.push_back(T::default()) {
421            Err(ListError::ArenaError(ArenaError::OutOfMemory)) => {}
422            _ => unreachable!("Out of memory not triggered"),
423        };
424
425        const ADDITIONAL: usize = 5;
426
427        let result = list.reserve(ADDITIONAL);
428
429        for _ in 0..ADDITIONAL {
430            if result.is_ok() {
431                list.push_front(T::default()).unwrap();
432            }
433        }
434
435        let result = list.reserve(ADDITIONAL);
436
437        for _ in 0..ADDITIONAL {
438            if result.is_ok() {
439                list.push_front(T::default()).unwrap();
440            }
441        }
442
443        list.clear().unwrap();
444
445        assert!(list.is_empty());
446    }
447
448    pub fn _test_list_front_push_peek_pop_consistency<V>(mut list: LinkedList<V, i32>)
449    where
450        V: Vector<Entry<Node<i32>>>,
451    {
452        list.clear().unwrap();
453
454        let capacity = list.capacity();
455
456        assert!(list.is_empty());
457        assert_eq!(list.peek_front(), None);
458        assert_eq!(list.pop_front(), None);
459
460        for ele in 0..capacity {
461            list.push_front(ele as i32).unwrap();
462        }
463
464        match list.push_front(0) {
465            Err(ListError::ArenaError(ArenaError::OutOfMemory)) => {}
466            _ => unreachable!("Out of memory not triggered"),
467        };
468
469        assert_eq!(list.peek_front().unwrap(), &(capacity as i32 - 1));
470
471        let mut i = capacity as i32 - 1;
472        for (_, ele) in &list {
473            assert_eq!(ele, &i);
474            i -= 1;
475        }
476        assert_eq!(i, -1);
477
478        let mut i = capacity as i32 - 1;
479        while let Some(ele) = list.pop_front() {
480            assert_eq!(ele, i);
481            i -= 1;
482        }
483        assert_eq!(i, -1);
484
485        assert!(list.is_empty());
486    }
487
488    pub fn _test_list_back_push_peek_pop_consistency<V>(mut list: LinkedList<V, i32>)
489    where
490        V: Vector<Entry<Node<i32>>>,
491    {
492        list.clear().unwrap();
493
494        let capacity = list.capacity();
495
496        assert!(list.is_empty());
497        assert_eq!(list.peek_back(), None);
498        assert_eq!(list.pop_back(), None);
499
500        for ele in 0..capacity {
501            list.push_back(ele as i32).unwrap();
502        }
503
504        match list.push_back(0) {
505            Err(ListError::ArenaError(ArenaError::OutOfMemory)) => {}
506            _ => unreachable!("Out of memory not triggered"),
507        };
508
509        assert_eq!(list.peek_back().unwrap(), &(capacity as i32 - 1));
510
511        let mut i = 0;
512        for (_, ele) in &list {
513            assert_eq!(ele, &i);
514            i += 1;
515        }
516        assert_eq!(i as usize, capacity);
517
518        let mut i = capacity as i32 - 1;
519        while let Some(ele) = list.pop_back() {
520            assert_eq!(ele, i);
521            i -= 1;
522        }
523        assert_eq!(i, -1);
524
525        assert!(list.is_empty());
526    }
527
528    pub fn _test_list_remove<V>(mut list: LinkedList<V, i32>)
529    where
530        V: Vector<Entry<Node<i32>>>,
531    {
532        let capacity = list.capacity();
533
534        assert!(capacity >= 3, "Test not valid for lists with capacity < 3 ");
535
536        list.clear().unwrap();
537        assert!(list.is_empty());
538
539        for ele in 0..capacity {
540            list.push_back(ele as i32).unwrap();
541        }
542
543        let link = *list.iter().find(|&(_, value)| value & 1 == 1).unwrap().0;
544
545        list.remove(&link).unwrap();
546
547        assert!(list.remove(&link).is_none());
548
549        assert!(list.get(&link).is_none());
550
551        assert_eq!(list.len(), list.capacity() - 1);
552
553        for (_, ele) in &list {
554            assert_ne!(ele, &1);
555        }
556
557        let link = *list.iter().find(|&(_, value)| value & 1 == 0).unwrap().0;
558
559        list.remove(&link).unwrap();
560
561        assert_eq!(list.peek_front(), Some(&2));
562
563        assert_eq!(list.len(), list.capacity() - 2);
564
565        let mut link = None;
566
567        for (l, _) in &list {
568            link = Some(l);
569        }
570
571        let link = *link.unwrap();
572
573        list.remove(&link).unwrap();
574
575        assert_eq!(list.len(), list.capacity() - 3);
576    }
577
578    pub fn _test_list_shift_push<V>(mut list: LinkedList<V, i32>)
579    where
580        V: Vector<Entry<Node<i32>>>,
581    {
582        let capacity = list.capacity();
583
584        assert!(capacity >= 3, "Test not valid for lists with capacity < 3 ");
585
586        list.clear().unwrap();
587        assert!(list.is_empty());
588
589        for ele in 0..capacity {
590            list.push_back(ele as i32).unwrap();
591        }
592
593        assert_eq!(list.peek_front(), Some(&0));
594
595        let link = *list.iter().find(|&(_, value)| value & 1 == 1).unwrap().0;
596
597        assert_eq!(list.len(), list.capacity());
598
599        list.shift_push_front(&link).unwrap();
600
601        assert_eq!(list.len(), list.capacity());
602
603        assert_eq!(list.peek_front(), Some(&1));
604
605        for (i, j) in list
606            .iter()
607            .take(3)
608            .map(|(_, value)| value)
609            .zip([1, 0, 2].iter())
610        {
611            assert_eq!(i, j);
612        }
613
614        let link = *list.iter().find(|&(_, value)| value & 1 == 0).unwrap().0;
615
616        assert_eq!(list.get(&link), Some(&0));
617
618        assert_ne!(list.peek_back(), Some(&0));
619
620        assert_eq!(list.len(), list.capacity());
621
622        list.shift_push_back(&link).unwrap();
623
624        assert_eq!(list.peek_back(), Some(&0));
625
626        assert_eq!(list.len(), list.capacity());
627    }
628}
generational_cache/collections/list.rs

generational_cache/collections/
list.rs
