wlan_common/
historical_list.rs

1// Copyright 2023 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use log::warn;
6use std::collections::VecDeque;
7
8/// Trait for time function, for use in HistoricalList functions
9pub trait Timestamped {
10    fn time(&self) -> fuchsia_async::MonotonicInstant;
11}
12
13/// Struct for list that stores historical data in a VecDeque, up to the some number of most
14/// recent entries.
15#[derive(Clone, Debug, PartialEq)]
16pub struct HistoricalList<T: Timestamped, const N: usize>(pub VecDeque<T>);
17
18impl<T, const N: usize> HistoricalList<T, N>
19where
20    T: Timestamped + Clone,
21{
22    pub fn new() -> Self {
23        Self(VecDeque::with_capacity(N))
24    }
25
26    /// Add a new entry, purging the oldest if at capacity. Entry must be newer than the most recent
27    /// existing entry.
28    pub fn add(&mut self, historical_data: T) {
29        if let Some(newest) = self.0.back()
30            && historical_data.time() < newest.time()
31        {
32            warn!("HistoricalList entry must be newer than existing elements.");
33            return;
34        }
35        if self.0.len() == N {
36            let _ = self.0.pop_front();
37        }
38        self.0.push_back(historical_data);
39    }
40
41    #[allow(clippy::needless_return, reason = "mass allow for https://fxbug.dev/381896734")]
42    /// Retrieve list of entries with a time more recent than earliest_time, sorted from oldest to
43    /// newest. May be empty.
44    pub fn get_recent(&self, earliest_time: fuchsia_async::MonotonicInstant) -> Vec<T> {
45        let i = self.0.partition_point(|data| data.time() < earliest_time);
46        return self.0.iter().skip(i).cloned().collect();
47    }
48
49    #[allow(clippy::needless_return, reason = "mass allow for https://fxbug.dev/381896734")]
50    /// Retrieve list of entries with a time before than latest_time, sorted from oldest to
51    /// newest. May be empty.
52    pub fn get_before(&self, latest_time: fuchsia_async::MonotonicInstant) -> Vec<T> {
53        let i = self.0.partition_point(|data| data.time() <= latest_time);
54        return self.0.iter().take(i).cloned().collect();
55    }
56
57    /// Retrieve list of entries inclusively between latest_time and earliest_time, sorted from
58    /// oldest to newest. May be empty.
59    pub fn get_between(
60        &self,
61        earliest_time: fuchsia_async::MonotonicInstant,
62        latest_time: fuchsia_async::MonotonicInstant,
63    ) -> Vec<T> {
64        let i = self.0.partition_point(|data| data.time() < earliest_time);
65        let j = self.0.partition_point(|data| data.time() <= latest_time);
66        match j.checked_sub(i) {
67            Some(diff) => self.0.iter().skip(i).take(diff).cloned().collect(),
68            _ => {
69                warn!(
70                    "Invalid time bounds - earliest time: {:?}, latest time: {:?}",
71                    earliest_time, latest_time
72                );
73                vec![]
74            }
75        }
76    }
77}
78
79impl<T, const N: usize> Default for HistoricalList<T, N>
80where
81    T: Timestamped + Clone,
82{
83    fn default() -> Self {
84        Self::new()
85    }
86}
87
88// Allow for storing just timestamps
89impl Timestamped for zx::MonotonicInstant {
90    fn time(&self) -> fuchsia_async::MonotonicInstant {
91        fuchsia_async::MonotonicInstant::from_zx(*self)
92    }
93}
94impl Timestamped for fuchsia_async::MonotonicInstant {
95    fn time(&self) -> fuchsia_async::MonotonicInstant {
96        *self
97    }
98}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103    use zx::MonotonicDuration;
104
105    const EARLIEST_TIME: fuchsia_async::MonotonicInstant =
106        fuchsia_async::MonotonicInstant::from_nanos(1_000_000_000);
107    fn create_test_list(
108        earlist_time: fuchsia_async::MonotonicInstant,
109    ) -> HistoricalList<fuchsia_async::MonotonicInstant, 4> {
110        HistoricalList(VecDeque::from_iter([
111            earlist_time,
112            earlist_time + MonotonicDuration::from_seconds(1),
113            earlist_time + MonotonicDuration::from_seconds(3),
114            earlist_time + MonotonicDuration::from_seconds(5),
115        ]))
116    }
117
118    #[fuchsia::test]
119    fn test_historical_list_capacity() {
120        let mut historical_list = create_test_list(EARLIEST_TIME);
121
122        // Verify that the list did not exceed capacity, and purged the oldest entry.
123        historical_list.add(EARLIEST_TIME + MonotonicDuration::from_seconds(10));
124        assert_eq!(historical_list.0.len(), 4);
125        assert!(!historical_list.0.contains(&EARLIEST_TIME));
126
127        // Verify that you cannot add a value older than the most recent entry.
128        let t = historical_list.clone();
129        historical_list.add(EARLIEST_TIME);
130        assert_eq!(historical_list, t);
131    }
132
133    #[fuchsia::test]
134    fn test_get_recent() {
135        let historical_list = create_test_list(EARLIEST_TIME);
136
137        assert_eq!(
138            historical_list.get_recent(EARLIEST_TIME + MonotonicDuration::from_seconds(1)),
139            vec![
140                EARLIEST_TIME + MonotonicDuration::from_seconds(1),
141                EARLIEST_TIME + MonotonicDuration::from_seconds(3),
142                EARLIEST_TIME + MonotonicDuration::from_seconds(5)
143            ]
144        );
145
146        assert_eq!(
147            historical_list.get_recent(
148                EARLIEST_TIME
149                    + MonotonicDuration::from_seconds(5)
150                    + MonotonicDuration::from_millis(1)
151            ),
152            vec![]
153        );
154    }
155
156    #[fuchsia::test]
157    fn test_get_before() {
158        let historical_list = create_test_list(EARLIEST_TIME);
159
160        assert_eq!(
161            historical_list.get_before(EARLIEST_TIME + MonotonicDuration::from_seconds(3)),
162            vec![
163                EARLIEST_TIME,
164                EARLIEST_TIME + MonotonicDuration::from_seconds(1),
165                EARLIEST_TIME + MonotonicDuration::from_seconds(3),
166            ]
167        );
168
169        assert_eq!(
170            historical_list.get_before(EARLIEST_TIME - MonotonicDuration::from_millis(1)),
171            vec![]
172        );
173    }
174
175    #[fuchsia::test]
176    fn test_get_between() {
177        let historical_list = create_test_list(EARLIEST_TIME);
178
179        assert_eq!(
180            historical_list.get_between(
181                EARLIEST_TIME + MonotonicDuration::from_seconds(1),
182                EARLIEST_TIME + MonotonicDuration::from_seconds(5)
183            ),
184            vec![
185                EARLIEST_TIME + MonotonicDuration::from_seconds(1),
186                EARLIEST_TIME + MonotonicDuration::from_seconds(3),
187                EARLIEST_TIME + MonotonicDuration::from_seconds(5),
188            ]
189        );
190
191        assert_eq!(historical_list.get_between(EARLIEST_TIME, EARLIEST_TIME), vec![EARLIEST_TIME]);
192
193        assert_eq!(
194            historical_list.get_between(
195                EARLIEST_TIME + MonotonicDuration::from_seconds(10),
196                EARLIEST_TIME + MonotonicDuration::from_seconds(10)
197            ),
198            vec![]
199        );
200
201        assert_eq!(
202            historical_list.get_between(
203                EARLIEST_TIME + MonotonicDuration::from_seconds(10),
204                EARLIEST_TIME + MonotonicDuration::from_seconds(11)
205            ),
206            vec![]
207        );
208
209        // Verify that an empty list is returned for equal and invalid time bounds.
210        assert_eq!(
211            historical_list
212                .get_between(EARLIEST_TIME + MonotonicDuration::from_seconds(3), EARLIEST_TIME),
213            vec![]
214        );
215    }
216}
wlan_common/historical_list.rs

wlan_common/
historical_list.rs
