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

wlancfg_lib/util/
historical_list.rs
