omega_cache/
admission.rs

1use crate::core::cms::CountMinSketch;
2use crate::core::key::Key;
3use std::borrow::Borrow;
4use std::hash::Hash;
5use std::marker::PhantomData;
6use std::sync::atomic::AtomicUsize;
7use std::sync::atomic::Ordering::{AcqRel, Acquire, Relaxed, Release};
8
9pub trait AdmissionPolicy<K>
10where
11    K: Eq + Hash,
12{
13    fn record<Q>(&self, key: &Q)
14    where
15        Key<K>: Borrow<Q>,
16        Q: Eq + Hash;
17
18    fn admit<Q>(&self, candidate: &Q, victim: &Q) -> bool
19    where
20        Key<K>: Borrow<Q>,
21        Q: Eq + Hash;
22}
23
24pub struct FrequentPolicy<K>
25where
26    K: Eq + Hash,
27{
28    cms: CountMinSketch,
29    count: AtomicUsize,
30    last_decay: AtomicUsize,
31    threshold: usize,
32    _phantom: PhantomData<K>,
33}
34
35impl<K> FrequentPolicy<K>
36where
37    K: Eq + Hash,
38{
39    #[inline]
40    pub fn new(cms_width: usize, cms_depth: usize, threshold: usize) -> Self {
41        Self {
42            cms: CountMinSketch::new(cms_width, cms_depth),
43            count: Default::default(),
44            last_decay: Default::default(),
45            threshold,
46            _phantom: Default::default(),
47        }
48    }
49}
50
51impl<K> FrequentPolicy<K>
52where
53    K: Eq + Hash,
54{
55    fn maybe_decay(&self) {
56        let counter = self.count.fetch_add(1, AcqRel) + 1;
57        let last_decay = self.last_decay.load(Acquire);
58
59        if (counter < last_decay || counter - last_decay >= self.threshold)
60            && self
61                .last_decay
62                .compare_exchange_weak(last_decay, counter, Release, Relaxed)
63                .is_ok()
64        {
65            self.cms.decay();
66        }
67    }
68}
69
70impl<K> AdmissionPolicy<K> for FrequentPolicy<K>
71where
72    K: Eq + Hash,
73{
74    fn record<Q>(&self, key: &Q)
75    where
76        Key<K>: Borrow<Q>,
77        Q: Eq + Hash,
78    {
79        self.cms.increment(key);
80        self.maybe_decay();
81    }
82
83    fn admit<Q>(&self, candidate: &Q, victim: &Q) -> bool
84    where
85        Key<K>: Borrow<Q>,
86        Q: Eq + Hash,
87    {
88        let candidate_frequency = self.cms.get(candidate);
89        let victim_frequency = self.cms.get(victim);
90        candidate_frequency >= victim_frequency
91    }
92}
93
94pub struct AlwaysAdmission<K>
95where
96    K: Eq + Hash,
97{
98    _phantom: PhantomData<K>,
99}
100
101impl<K> Default for AlwaysAdmission<K>
102where
103    K: Eq + Hash,
104{
105    fn default() -> Self {
106        Self::new()
107    }
108}
109
110impl<K> AlwaysAdmission<K>
111where
112    K: Eq + Hash,
113{
114    pub fn new() -> Self {
115        Self {
116            _phantom: Default::default(),
117        }
118    }
119}
120
121impl<K> AdmissionPolicy<K> for AlwaysAdmission<K>
122where
123    K: Eq + Hash,
124{
125    fn record<Q>(&self, _key: &Q)
126    where
127        Key<K>: Borrow<Q>,
128        Q: Eq + Hash,
129    {
130    }
131
132    fn admit<Q>(&self, _: &Q, _: &Q) -> bool
133    where
134        Key<K>: Borrow<Q>,
135        Q: Eq + Hash,
136    {
137        true
138    }
139}
omega_cache/admission.rs

omega_cache/
admission.rs
