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

fuchsia_inspect_contrib/nodes/
lru_cache.rs
