kernel/collections/
list.rs

Help
1// Licensed under the Apache License, Version 2.0 or the MIT License.
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3// Copyright Tock Contributors 2022.
4
5//! Linked list implementation.
6
7use core::cell::Cell;
8
9pub struct ListLink<'a, T: 'a + ?Sized>(Cell<Option<&'a T>>);
10
11impl<'a, T: ?Sized> ListLink<'a, T> {
12    pub const fn empty() -> ListLink<'a, T> {
13        ListLink(Cell::new(None))
14    }
15}
16
17pub trait ListNode<'a, T: ?Sized> {
18    fn next(&'a self) -> &'a ListLink<'a, T>;
19}
20
21pub struct List<'a, T: 'a + ?Sized + ListNode<'a, T>> {
22    head: ListLink<'a, T>,
23}
24
25pub struct ListIterator<'a, T: 'a + ?Sized + ListNode<'a, T>> {
26    cur: Option<&'a T>,
27}
28
29impl<'a, T: ?Sized + ListNode<'a, T>> Iterator for ListIterator<'a, T> {
30    type Item = &'a T;
31
32    fn next(&mut self) -> Option<&'a T> {
33        match self.cur {
34            Some(res) => {
35                self.cur = res.next().0.get();
36                Some(res)
37            }
38            None => None,
39        }
40    }
41}
42
43impl<'a, T: ?Sized + ListNode<'a, T>> List<'a, T> {
44    pub const fn new() -> List<'a, T> {
45        List {
46            head: ListLink(Cell::new(None)),
47        }
48    }
49
50    pub fn head(&self) -> Option<&'a T> {
51        self.head.0.get()
52    }
53
54    pub fn push_head(&self, node: &'a T) {
55        node.next().0.set(self.head.0.get());
56        self.head.0.set(Some(node));
57    }
58
59    pub fn push_tail(&self, node: &'a T) {
60        node.next().0.set(None);
61        match self.iter().last() {
62            Some(last) => last.next().0.set(Some(node)),
63            None => self.push_head(node),
64        }
65    }
66
67    pub fn pop_head(&self) -> Option<&'a T> {
68        let remove = self.head.0.get();
69        match remove {
70            Some(node) => self.head.0.set(node.next().0.get()),
71            None => self.head.0.set(None),
72        }
73        remove
74    }
75
76    pub fn iter(&self) -> ListIterator<'a, T> {
77        ListIterator {
78            cur: self.head.0.get(),
79        }
80    }
81}
kernel/collections/list.rs

kernel/collections/
list.rs
