fuchsia_inspect_contrib/nodes/
lru_cache.rs

1// Copyright 2024 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_inspect::Node;
6use fuchsia_inspect_derive::Unit;
7use lru_cache::LruCache;
8use std::hash::Hash;
9
10use crate::nodes::NodeTimeExt;
11
12/// A Inspect node that holds an ordered, bounded set of data. When a new unique
13/// item needs to be inserted, the least-recently-used item is evicted.
14pub struct LruCacheNode<T: Unit + Eq + Hash> {
15    node: Node,
16    items: LruCache<T, CacheItem<T>>,
17}
18
19impl<T: Unit + Eq + Hash> LruCacheNode<T> {
20    pub fn new(node: Node, capacity: usize) -> Self {
21        Self { node, items: LruCache::new(capacity) }
22    }
23
24    /// Insert |item| into `LruCacheNode`.
25    ///
26    /// If |item| already exists in the cache, its entry is retrieved and the entry's index
27    /// is returned.
28    /// If |item| has not already existed in the cache, the item is recorded with the current
29    /// timestamp and its index in the cache is returned. If the cache is already full,
30    /// recording the new item would evict the least-recently-used item.
31    pub fn insert(&mut self, item: T) -> usize {
32        match self.items.get_mut(&item) {
33            Some(entry) => entry.index,
34            None => {
35                let index = if self.items.len() < self.items.capacity() {
36                    self.items.len()
37                } else {
38                    self.items.remove_lru().map(|entry| entry.1.index).unwrap_or(0)
39                };
40                let child = self.node.create_child(index.to_string());
41                NodeTimeExt::<zx::BootTimeline>::record_time(&child, "@time");
42                let data = item.inspect_create(&child, "data");
43                self.items.insert(item, CacheItem { index, _node: child, _data: data });
44                index
45            }
46        }
47    }
48}
49struct CacheItem<T: Unit> {
50    index: usize,
51    _node: Node,
52    _data: <T as Unit>::Data,
53}
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58    use diagnostics_assertions::{assert_data_tree, AnyNumericProperty};
59    use fuchsia_inspect::Inspector;
60
61    #[fuchsia::test]
62    fn test_insert() {
63        let inspector = Inspector::default();
64        let cache_node = inspector.root().create_child("cache");
65        let mut cache_node = LruCacheNode::new(cache_node, 3);
66        // Insert unique items
67        assert_eq!(cache_node.insert(111), 0);
68        assert_eq!(cache_node.insert(222), 1);
69        assert_eq!(cache_node.insert(333), 2);
70        assert_data_tree!(inspector, root: {
71            cache: {
72                "0": { "@time": AnyNumericProperty, "data": 111i64},
73                "1": { "@time": AnyNumericProperty, "data": 222i64},
74                "2": { "@time": AnyNumericProperty, "data": 333i64},
75            }
76        });
77
78        // Insert item that already exists does not change the Inspect data
79        assert_eq!(cache_node.insert(222), 1);
80        assert_eq!(cache_node.insert(111), 0);
81        assert_eq!(cache_node.insert(333), 2);
82        assert_data_tree!(inspector, root: {
83            cache: {
84                "0": { "@time": AnyNumericProperty, "data": 111i64},
85                "1": { "@time": AnyNumericProperty, "data": 222i64},
86                "2": { "@time": AnyNumericProperty, "data": 333i64},
87            }
88        });
89
90        // Now that the node is full, inserting new item would replace the least recently used
91        assert_eq!(cache_node.insert(444), 1);
92        assert_data_tree!(inspector, root: {
93            cache: {
94                "0": { "@time": AnyNumericProperty, "data": 111i64},
95                "1": { "@time": AnyNumericProperty, "data": 444i64},
96                "2": { "@time": AnyNumericProperty, "data": 333i64},
97            }
98        });
99
100        // Value that had been evicted is considered to be a new value if they are inserted again
101        assert_eq!(cache_node.insert(222), 0);
102        assert_data_tree!(inspector, root: {
103            cache: {
104                "0": { "@time": AnyNumericProperty, "data": 222i64},
105                "1": { "@time": AnyNumericProperty, "data": 444i64},
106                "2": { "@time": AnyNumericProperty, "data": 333i64},
107            }
108        });
109    }
110
111    #[derive(PartialEq, Eq, Hash, Unit)]
112    struct Item {
113        num: u64,
114        string: String,
115    }
116
117    #[fuchsia::test]
118    fn test_insert_custom_struct() {
119        let inspector = Inspector::default();
120        let cache_node = inspector.root().create_child("cache");
121        let mut cache_node = LruCacheNode::new(cache_node, 3);
122        assert_eq!(cache_node.insert(Item { num: 1337u64, string: "42".to_string() }), 0);
123        assert_eq!(cache_node.insert(Item { num: 1337u64, string: "43".to_string() }), 1);
124        assert_data_tree!(inspector, root: {
125            cache: {
126                "0": {
127                    "@time": AnyNumericProperty,
128                    "data": { num: 1337u64, string: "42".to_string() }
129                },
130                "1": {
131                    "@time": AnyNumericProperty,
132                    "data": { num: 1337u64, string: "43".to_string() }
133                },
134            }
135        });
136    }
137}
fuchsia_inspect_contrib/nodes/lru_cache.rs

fuchsia_inspect_contrib/nodes/
lru_cache.rs
