safe_drive/
delta_list.rs

1//! The delta list was originally introduced by [Operating System Design, The Xinu Approach](https://xinu.cs.purdue.edu/)'s
2//! Chapter 13.
3//!
4//! We specified the delta list by using TLA+.
5//! See [the specification](https://github.com/tier4/safe_drive/tree/main/specifications/callback).
6
7use std::{cell::UnsafeCell, time::Duration};
8
9/// Timers are represented by a linked list.
10/// Each element represents the difference of time from parent node.
11///
12/// For example, if `timer = 10 -> 20 -> 5`,
13/// timers will be invoked after 10, 10 + 20 = 30, and 10 + 20 + 5 = 35 seconds later, respectively.
14///
15/// At that time, if `t` is 13, the callback will be invoked 13 seconds later.
16/// To accomplish this, 13 should be inserted between 10 and 20 like
17/// `10 -> 3 (inserted) -> 17 (updated) -> 5`.
18pub enum DeltaList<T> {
19    Cons(Box<UnsafeCell<(Duration, T, DeltaList<T>)>>),
20    Nil,
21}
22
23impl<T> DeltaList<T> {
24    /// Insert a data which will be invoked after `delta` duration.
25    ///
26    /// For example, if a delta list is `10 -> 20 -> 5`,
27    /// and a delta of `15` is inserted,
28    /// the list is updated to `10 -> 5 -> 5 -> 5`.
29    pub fn insert(&mut self, delta: Duration, data: T) {
30        insert_delta(self, delta, data);
31    }
32
33    pub fn front(&self) -> Option<(&Duration, &T)> {
34        if let DeltaList::Cons(e) = self {
35            let elm = unsafe { &(*e.get()) };
36            Some((&elm.0, &elm.1))
37        } else {
38            None
39        }
40    }
41
42    pub fn front_mut(&mut self) -> Option<(&mut Duration, &mut T)> {
43        if let DeltaList::Cons(e) = self {
44            let elm = e.get_mut();
45            Some((&mut elm.0, &mut elm.1))
46        } else {
47            None
48        }
49    }
50
51    pub fn pop(&mut self) -> Option<Self> {
52        if let DeltaList::Cons(e) = self {
53            let next = std::mem::replace(&mut e.get_mut().2, DeltaList::Nil);
54            let head = std::mem::replace(self, next);
55            Some(head)
56        } else {
57            None
58        }
59    }
60
61    pub fn is_empty(&self) -> bool {
62        matches!(self, DeltaList::Nil)
63    }
64
65    pub fn filter<U>(&mut self, f: U)
66    where
67        U: Fn(&T) -> bool,
68    {
69        filter_delta(self, f);
70    }
71}
72
73fn insert_delta<T>(mut list: &mut DeltaList<T>, mut delta: Duration, data: T) {
74    loop {
75        match list {
76            DeltaList::Nil => {
77                *list = DeltaList::Cons(Box::new(UnsafeCell::new((delta, data, DeltaList::Nil))));
78                return;
79            }
80            DeltaList::Cons(e) => {
81                let front = e.get();
82                let d_mut = unsafe { &mut (*front).0 };
83                if delta < *d_mut {
84                    *d_mut -= delta;
85                    let next = std::mem::replace(list, DeltaList::Nil);
86                    *list = DeltaList::Cons(Box::new(UnsafeCell::new((delta, data, next))));
87                    return;
88                } else {
89                    delta -= *d_mut;
90                    list = unsafe { &mut (*front).2 };
91                }
92            }
93        }
94    }
95}
96
97fn filter_delta<T, U>(mut list: &mut DeltaList<T>, f: U)
98where
99    U: Fn(&T) -> bool,
100{
101    loop {
102        match list {
103            DeltaList::Nil => {
104                return;
105            }
106            DeltaList::Cons(e) => {
107                let front = e.get();
108                let d_mut = unsafe { &mut (*front).1 };
109                if f(d_mut) {
110                    list = unsafe { &mut (*front).2 };
111                } else {
112                    let next = unsafe { &mut (*front).2 };
113                    let next = std::mem::replace(next, DeltaList::Nil);
114                    *list = next;
115                }
116            }
117        }
118    }
119}
safe_drive/delta_list.rs

safe_drive/
delta_list.rs
