kernel/collections/
list.rs

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
// Licensed under the Apache License, Version 2.0 or the MIT License.
// SPDX-License-Identifier: Apache-2.0 OR MIT
// Copyright Tock Contributors 2022.

//! Linked list implementation.

use core::cell::Cell;

pub struct ListLink<'a, T: 'a + ?Sized>(Cell<Option<&'a T>>);

impl<'a, T: ?Sized> ListLink<'a, T> {
    pub const fn empty() -> ListLink<'a, T> {
        ListLink(Cell::new(None))
    }
}

pub trait ListNode<'a, T: ?Sized> {
    fn next(&'a self) -> &'a ListLink<'a, T>;
}

pub struct List<'a, T: 'a + ?Sized + ListNode<'a, T>> {
    head: ListLink<'a, T>,
}

pub struct ListIterator<'a, T: 'a + ?Sized + ListNode<'a, T>> {
    cur: Option<&'a T>,
}

impl<'a, T: ?Sized + ListNode<'a, T>> Iterator for ListIterator<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<&'a T> {
        match self.cur {
            Some(res) => {
                self.cur = res.next().0.get();
                Some(res)
            }
            None => None,
        }
    }
}

impl<'a, T: ?Sized + ListNode<'a, T>> List<'a, T> {
    pub const fn new() -> List<'a, T> {
        List {
            head: ListLink(Cell::new(None)),
        }
    }

    pub fn head(&self) -> Option<&'a T> {
        self.head.0.get()
    }

    pub fn push_head(&self, node: &'a T) {
        node.next().0.set(self.head.0.get());
        self.head.0.set(Some(node));
    }

    pub fn push_tail(&self, node: &'a T) {
        node.next().0.set(None);
        match self.iter().last() {
            Some(last) => last.next().0.set(Some(node)),
            None => self.push_head(node),
        }
    }

    pub fn pop_head(&self) -> Option<&'a T> {
        let remove = self.head.0.get();
        match remove {
            Some(node) => self.head.0.set(node.next().0.get()),
            None => self.head.0.set(None),
        }
        remove
    }

    pub fn iter(&self) -> ListIterator<'a, T> {
        ListIterator {
            cur: self.head.0.get(),
        }
    }
}