| // Copyright 2018 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| use std::{collections::vec_deque, time::Duration}; |
| |
| pub trait SizeOf { |
| /// Size in bytes of an object. Makes no distinction between stack and heap allocated memory. |
| fn size_of(&self) -> usize; |
| } |
| |
| /// An implementor has some concept of the time at which it was created and knows how to retreive |
| /// that time. |
| pub trait CreatedAt { |
| /// Return the `Duration` since the Unix Epoch that represents when `self` was created. |
| fn created_at(&self) -> Duration; |
| } |
| |
| /// Mutable Iterator over the elements in a `BoundedQueue` |
| type IterMut<'a, T> = vec_deque::IterMut<'a, T>; |
| |
| /// A `BoundedQueue` is a collection that holds elements with eviction minimums on the size (in |
| /// bytes) of the collection and how long it will hold elements. If both the `eviction_size_minimum` |
| /// and the `eviction_age_minimum` are exceeded, the oldest elements will be dropped until either |
| /// the size of the collection or the age of the oldest element no longer exceed the requested |
| /// minimum. |
| /// |
| /// The `BoundedQueue` only supports inserting new elements to the end of the queue. |
| pub(crate) struct BoundedQueue<T> { |
| eviction_age_minimum: Duration, |
| eviction_size_minimum: usize, |
| current_size: usize, |
| inner: vec_deque::VecDeque<T>, |
| } |
| |
| impl<T> BoundedQueue<T> |
| where |
| T: SizeOf + CreatedAt, |
| { |
| /// Create an empty `BoundedQueue` with the specified eviction minimums. |
| pub fn new(eviction_size_minimum: usize, eviction_age_minimum: Duration) -> BoundedQueue<T> { |
| BoundedQueue { |
| eviction_age_minimum, |
| eviction_size_minimum, |
| current_size: 0, |
| inner: vec_deque::VecDeque::new(), |
| } |
| } |
| |
| /// Calculate whether adding `item` would make this queue large enough to evict old packets. |
| fn eviction_size_minimum_reached(&self, item: &T) -> bool { |
| self.current_size + item.size_of() > self.eviction_size_minimum |
| } |
| |
| /// When `item` is added, returns true if the oldest item will be too old. |
| fn oldest_item_will_expire(&self, item: &T) -> bool { |
| if self.inner.is_empty() { return false; } |
| (item.created_at() - self.inner[0].created_at()) > self.eviction_age_minimum |
| } |
| |
| /// Insert a new item to the end of the `BoundedQueue`, removing items as needed to make room. |
| pub fn insert(&mut self, item: T) { |
| while self.eviction_size_minimum_reached(&item) && self.oldest_item_will_expire(&item){ |
| self.current_size -= self.inner.pop_front().map(|item| item.size_of()).unwrap_or(0); |
| } |
| self.current_size += item.size_of(); |
| self.inner.push_back(item); |
| } |
| |
| /// Return an `Iterator` over mutable references to elements ordered from oldest to newest. |
| pub fn iter_mut(&mut self) -> IterMut<T> { |
| self.inner.iter_mut() |
| } |
| } |
| |
| #[cfg(test)] |
| mod tests { |
| use { |
| std::time::Duration, |
| super::*, |
| }; |
| |
| // Dummy struct that implements the SizeOf and CreatedAt traits required for elements of |
| // a `BoundedQueue` |
| #[derive(Debug)] |
| struct Record { |
| created_at: Duration, |
| value: u64 |
| } |
| |
| impl From<u64> for Record { |
| fn from(value: u64) -> Self { |
| Record { created_at: Duration::from_secs(value), value: value } |
| } |
| } |
| |
| impl SizeOf for Record { |
| fn size_of(&self) -> usize { |
| std::mem::size_of::<Record>() |
| } |
| } |
| |
| impl CreatedAt for Record { |
| fn created_at(&self) -> Duration { self.created_at } |
| } |
| |
| // Return a vec of the values of a record. For use in asserting the state of a `BoundedQueue` in |
| // tests. |
| fn to_values(queue: &mut BoundedQueue<Record>) -> Vec<u64> { |
| queue.iter_mut().map(|n| n.value).collect() |
| } |
| |
| #[test] |
| fn test_bounded_queue() { |
| // create a queue with age 0 and test inserting elements into it |
| let mut queue: BoundedQueue<Record> = |
| BoundedQueue::new(3 * std::mem::size_of::<Record>(), Duration::new(0, 0)); |
| assert!(!queue.eviction_size_minimum_reached(&0.into())); |
| assert_eq!(to_values(&mut queue), vec![]); |
| queue.insert(0.into()); |
| assert!(!queue.eviction_size_minimum_reached(&1.into())); |
| queue.insert(1.into()); |
| queue.insert(2.into()); |
| assert!(queue.eviction_size_minimum_reached(&3.into())); |
| assert_eq!(to_values(&mut queue), vec![0, 1, 2]); |
| queue.insert(3.into()); |
| assert!(queue.eviction_size_minimum_reached(&4.into())); |
| assert_eq!(to_values(&mut queue), vec![1, 2, 3]); |
| queue.insert(4.into()); |
| assert_eq!(to_values(&mut queue), vec![2, 3, 4]); |
| |
| // create a queue with size 0 and test inserting elements into it |
| let mut queue: BoundedQueue<Record> = |
| BoundedQueue::new(0, Duration::new(2, 0)); |
| assert!(!queue.oldest_item_will_expire(&0.into())); |
| assert_eq!(to_values(&mut queue), vec![]); |
| queue.insert(0.into()); |
| assert!(!queue.oldest_item_will_expire(&1.into())); |
| queue.insert(1.into()); |
| queue.insert(2.into()); |
| assert!(queue.oldest_item_will_expire(&3.into())); |
| assert_eq!(to_values(&mut queue), vec![0, 1, 2]); |
| queue.insert(3.into()); |
| assert!(queue.oldest_item_will_expire(&4.into())); |
| assert_eq!(to_values(&mut queue), vec![1, 2, 3]); |
| queue.insert(4.into()); |
| assert_eq!(to_values(&mut queue), vec![2, 3, 4]); |
| |
| // Create a queue with some size and some age test inserting elements into it |
| let mut queue: BoundedQueue<Record> = |
| BoundedQueue::new(3 * std::mem::size_of::<Record>(), Duration::new(3, 0)); |
| assert_eq!(to_values(&mut queue), vec![]); |
| queue.insert(0.into()); |
| queue.insert(1.into()); |
| queue.insert(2.into()); |
| assert_eq!(to_values(&mut queue), vec![0, 1, 2]); |
| queue.insert(3.into()); |
| assert_eq!(to_values(&mut queue), vec![0, 1, 2, 3]); |
| |
| // Both space and age limits are exceeded. |
| // The expected behavior is to evict old items as new ones are added |
| assert!(queue.eviction_size_minimum_reached(&4.into())); |
| assert!(queue.oldest_item_will_expire(&4.into())); |
| queue.insert(4.into()); |
| assert_eq!(to_values(&mut queue), vec![1, 2, 3, 4]); |
| queue.insert(6.into()); |
| assert_eq!(to_values(&mut queue), vec![3, 4, 6]); |
| queue.insert(Record { created_at: Duration::new(6, 1), value: 7 }); |
| assert_eq!(to_values(&mut queue), vec![4, 6, 7]); |
| |
| // Only space limit is exceeded. |
| // The expected behavior is to keep all items even as new items are added. |
| // Space is allowed to grow to contain elements that are within the time limit. |
| let record = Record { created_at: Duration::new(6, 2), value: 8 }; |
| assert!(queue.eviction_size_minimum_reached(&record)); |
| assert!(!queue.oldest_item_will_expire(&record)); |
| queue.insert(record); |
| assert_eq!(to_values(&mut queue), vec![4, 6, 7, 8]); |
| queue.insert(Record { created_at: Duration::new(6, 3), value: 9 }); |
| assert_eq!(to_values(&mut queue), vec![4, 6, 7, 8, 9]); |
| |
| // Both space and age limits are exceeded. |
| // The expected behavior is to evict old items as new ones are added |
| assert!(queue.eviction_size_minimum_reached(&10.into())); |
| assert!(queue.oldest_item_will_expire(&10.into())); |
| queue.insert(10.into()); |
| assert_eq!(to_values(&mut queue), vec![8, 9, 10]); |
| |
| let mut queue: BoundedQueue<Record> = |
| BoundedQueue::new(2 * std::mem::size_of::<Record>(), Duration::new(3, 0)); |
| queue.insert(0.into()); |
| // Only age limit is exceeded. |
| // The expected behavior is to keep all items even as new items are added. |
| // Space is allowed to grow to contain elements that are still within the space limit. |
| assert!(!queue.eviction_size_minimum_reached(&4.into())); |
| assert!(queue.oldest_item_will_expire(&4.into())); |
| queue.insert(4.into()); |
| assert_eq!(to_values(&mut queue), vec![0, 4]); |
| |
| // Both space and age limit is exceeded. |
| // The expected behavior is to evict old items as new ones are added |
| assert!(queue.eviction_size_minimum_reached(&5.into())); |
| assert!(queue.oldest_item_will_expire(&5.into())); |
| queue.insert(5.into()); |
| assert_eq!(to_values(&mut queue), vec![4, 5]); |
| } |
| } |