moka/sync_base/
iter.rs

Help
1use std::{hash::Hash, sync::Arc};
2
3// This trait is implemented by `sync::BaseCache` and `sync::Cache`.
4pub(crate) trait ScanningGet<K, V> {
5    /// Returns the number of segments in the concurrent hash table.
6    fn num_cht_segments(&self) -> usize;
7
8    /// Returns a _clone_ of the value corresponding to the key.
9    ///
10    /// Unlike the `get` method of cache, this method is not considered a cache read
11    /// operation, so it does not update the historic popularity estimator or reset
12    /// the idle timer for the key.
13    fn scanning_get(&self, key: &Arc<K>) -> Option<V>;
14
15    /// Returns a vec of keys in a specified segment of the concurrent hash table.
16    fn keys(&self, cht_segment: usize) -> Option<Vec<Arc<K>>>;
17}
18
19/// Iterator visiting all key-value pairs in a cache in arbitrary order.
20///
21/// Call [`Cache::iter`](./struct.Cache.html#method.iter) method to obtain an `Iter`.
22pub struct Iter<'i, K, V> {
23    keys: Option<Vec<Arc<K>>>,
24    cache_segments: Box<[&'i dyn ScanningGet<K, V>]>,
25    num_cht_segments: usize,
26    cache_seg_index: usize,
27    cht_seg_index: usize,
28    is_done: bool,
29}
30
31impl<'i, K, V> Iter<'i, K, V> {
32    pub(crate) fn with_single_cache_segment(
33        cache: &'i dyn ScanningGet<K, V>,
34        num_cht_segments: usize,
35    ) -> Self {
36        Self {
37            keys: None,
38            cache_segments: Box::new([cache]),
39            num_cht_segments,
40            cache_seg_index: 0,
41            cht_seg_index: 0,
42            is_done: false,
43        }
44    }
45
46    #[cfg(feature = "sync")]
47    pub(crate) fn with_multiple_cache_segments(
48        cache_segments: Box<[&'i dyn ScanningGet<K, V>]>,
49        num_cht_segments: usize,
50    ) -> Self {
51        Self {
52            keys: None,
53            cache_segments,
54            num_cht_segments,
55            cache_seg_index: 0,
56            cht_seg_index: 0,
57            is_done: false,
58        }
59    }
60}
61
62impl<K, V> Iterator for Iter<'_, K, V>
63where
64    K: Eq + Hash + Send + Sync + 'static,
65    V: Clone + Send + Sync + 'static,
66{
67    type Item = (Arc<K>, V);
68
69    fn next(&mut self) -> Option<Self::Item> {
70        if self.is_done {
71            return None;
72        }
73
74        while let Some(key) = self.next_key() {
75            if let Some(v) = self.cache().scanning_get(&key) {
76                return Some((key, v));
77            }
78        }
79
80        self.is_done = true;
81        None
82    }
83}
84
85impl<'i, K, V> Iter<'i, K, V>
86where
87    K: Eq + Hash + Send + Sync + 'static,
88    V: Clone + Send + Sync + 'static,
89{
90    fn cache(&self) -> &'i dyn ScanningGet<K, V> {
91        self.cache_segments[self.cache_seg_index]
92    }
93
94    fn next_key(&mut self) -> Option<Arc<K>> {
95        while let Some(keys) = self.current_keys() {
96            if let key @ Some(_) = keys.pop() {
97                return key;
98            }
99        }
100        None
101    }
102
103    fn current_keys(&mut self) -> Option<&mut Vec<Arc<K>>> {
104        // If keys is none or some but empty, try to get next keys.
105        while self.keys.as_ref().map_or(true, Vec::is_empty) {
106            // Adjust indices.
107            if self.cht_seg_index >= self.num_cht_segments {
108                self.cache_seg_index += 1;
109                self.cht_seg_index = 0;
110                if self.cache_seg_index >= self.cache_segments.len() {
111                    // No more cache segments left.
112                    return None;
113                }
114            }
115
116            let cache_segment = self.cache_segments[self.cache_seg_index];
117            self.keys = cache_segment.keys(self.cht_seg_index);
118            self.num_cht_segments = cache_segment.num_cht_segments();
119
120            self.cht_seg_index += 1;
121        }
122
123        self.keys.as_mut()
124    }
125}
126
127// Clippy beta 0.1.83 (f41c7ed9889 2024-10-31) warns about unused lifetimes on 'a.
128// This seems a false positive. The lifetimes are used in the Send and Sync impls.
129// Let's suppress the warning.
130// https://rust-lang.github.io/rust-clippy/master/index.html#extra_unused_lifetimes
131#[allow(clippy::extra_unused_lifetimes)]
132unsafe impl<'a, K, V> Send for Iter<'_, K, V>
133where
134    K: 'a + Eq + Hash + Send,
135    V: 'a + Send,
136{
137}
138
139// Clippy beta 0.1.83 (f41c7ed9889 2024-10-31) warns about unused lifetimes on 'a.
140// This seems a false positive. The lifetimes are used in the Send and Sync impls.
141// Let's suppress the warning.
142// https://rust-lang.github.io/rust-clippy/master/index.html#extra_unused_lifetimes
143#[allow(clippy::extra_unused_lifetimes)]
144unsafe impl<'a, K, V> Sync for Iter<'_, K, V>
145where
146    K: 'a + Eq + Hash + Sync,
147    V: 'a + Sync,
148{
149}
moka/sync_base/iter.rs

moka/sync_base/
iter.rs
