moka/common/concurrent/
deques.rs

Help
1use super::{arc::MiniArc, KeyHashDate, ValueEntry};
2use crate::common::{
3    deque::{DeqNode, Deque},
4    CacheRegion,
5};
6
7use std::ptr::NonNull;
8use tagptr::TagNonNull;
9
10pub(crate) struct Deques<K> {
11    pub(crate) window: Deque<KeyHashDate<K>>, //    Not used yet.
12    pub(crate) probation: Deque<KeyHashDate<K>>,
13    pub(crate) protected: Deque<KeyHashDate<K>>, // Not used yet.
14    pub(crate) write_order: Deque<KeyHashDate<K>>,
15}
16
17#[cfg(feature = "future")]
18// TODO: https://github.com/moka-rs/moka/issues/54
19#[allow(clippy::non_send_fields_in_send_ty)]
20// Multi-threaded async runtimes require base_cache::Inner to be Send, but it will
21// not be without this `unsafe impl`. This is because DeqNodes have NonNull
22// pointers.
23unsafe impl<K> Send for Deques<K> {}
24
25impl<K> Default for Deques<K> {
26    fn default() -> Self {
27        Self {
28            window: Deque::new(CacheRegion::Window),
29            probation: Deque::new(CacheRegion::MainProbation),
30            protected: Deque::new(CacheRegion::MainProtected),
31            write_order: Deque::new(CacheRegion::Other),
32        }
33    }
34}
35
36impl<K> Deques<K> {
37    pub(crate) fn select_mut(
38        &mut self,
39        selector: CacheRegion,
40    ) -> (&mut Deque<KeyHashDate<K>>, &mut Deque<KeyHashDate<K>>) {
41        match selector {
42            CacheRegion::Window => (&mut self.window, &mut self.write_order),
43            CacheRegion::MainProbation => (&mut self.probation, &mut self.write_order),
44            CacheRegion::MainProtected => (&mut self.protected, &mut self.write_order),
45            CacheRegion::Other => unreachable!(),
46        }
47    }
48
49    pub(crate) fn push_back_ao<V>(
50        &mut self,
51        region: CacheRegion,
52        khd: KeyHashDate<K>,
53        entry: &MiniArc<ValueEntry<K, V>>,
54    ) {
55        let node = Box::new(DeqNode::new(khd));
56        let node = match region {
57            CacheRegion::Window => self.window.push_back(node),
58            CacheRegion::MainProbation => self.probation.push_back(node),
59            CacheRegion::MainProtected => self.protected.push_back(node),
60            CacheRegion::Other => unreachable!(),
61        };
62        let tagged_node = TagNonNull::compose(node, region as usize);
63        entry.set_access_order_q_node(Some(tagged_node));
64    }
65
66    pub(crate) fn push_back_wo<V>(
67        &mut self,
68        kd: KeyHashDate<K>,
69        entry: &MiniArc<ValueEntry<K, V>>,
70    ) {
71        let node = Box::new(DeqNode::new(kd));
72        let node = self.write_order.push_back(node);
73        entry.set_write_order_q_node(Some(node));
74    }
75
76    pub(crate) fn move_to_back_ao<V>(&mut self, entry: &MiniArc<ValueEntry<K, V>>) {
77        if let Some(tagged_node) = entry.access_order_q_node() {
78            let (node, tag) = tagged_node.decompose();
79            let p = unsafe { node.as_ref() };
80            match tag.into() {
81                CacheRegion::Window if self.window.contains(p) => {
82                    unsafe { self.window.move_to_back(node) };
83                }
84                CacheRegion::MainProbation if self.probation.contains(p) => {
85                    unsafe { self.probation.move_to_back(node) };
86                }
87                CacheRegion::MainProtected if self.protected.contains(p) => {
88                    unsafe { self.protected.move_to_back(node) };
89                }
90                _ => unreachable!(),
91            }
92        }
93    }
94
95    pub(crate) fn move_to_back_ao_in_deque<V>(
96        deq_name: &str,
97        deq: &mut Deque<KeyHashDate<K>>,
98        entry: &MiniArc<ValueEntry<K, V>>,
99    ) {
100        if let Some(tagged_node) = entry.access_order_q_node() {
101            let (node, tag) = tagged_node.decompose();
102            let p = unsafe { node.as_ref() };
103            assert_eq!(
104                deq.region(),
105                tag,
106                "move_to_back_ao_in_deque - node is not a member of {deq_name} deque. {p:?}"
107            );
108            if deq.contains(p) {
109                unsafe { deq.move_to_back(node) };
110            }
111        }
112    }
113
114    pub(crate) fn move_to_back_wo<V>(&mut self, entry: &MiniArc<ValueEntry<K, V>>) {
115        if let Some(node) = entry.write_order_q_node() {
116            let p = unsafe { node.as_ref() };
117            if self.write_order.contains(p) {
118                unsafe { self.write_order.move_to_back(node) };
119            }
120        }
121    }
122
123    pub(crate) fn move_to_back_wo_in_deque<V>(
124        deq: &mut Deque<KeyHashDate<K>>,
125        entry: &MiniArc<ValueEntry<K, V>>,
126    ) {
127        if let Some(node) = entry.write_order_q_node() {
128            let p = unsafe { node.as_ref() };
129            if deq.contains(p) {
130                unsafe { deq.move_to_back(node) };
131            }
132        }
133    }
134
135    pub(crate) fn unlink_ao<V>(&mut self, entry: &MiniArc<ValueEntry<K, V>>) {
136        if let Some(node) = entry.take_access_order_q_node() {
137            self.unlink_node_ao(node);
138        }
139    }
140
141    pub(crate) fn unlink_ao_from_deque<V>(
142        deq_name: &str,
143        deq: &mut Deque<KeyHashDate<K>>,
144        entry: &MiniArc<ValueEntry<K, V>>,
145    ) {
146        if let Some(node) = entry.take_access_order_q_node() {
147            unsafe { Self::unlink_node_ao_from_deque(deq_name, deq, node) };
148        }
149    }
150
151    pub(crate) fn unlink_wo<V>(deq: &mut Deque<KeyHashDate<K>>, entry: &MiniArc<ValueEntry<K, V>>) {
152        if let Some(node) = entry.take_write_order_q_node() {
153            Self::unlink_node_wo(deq, node);
154        }
155    }
156
157    pub(crate) fn unlink_node_ao(&mut self, tagged_node: TagNonNull<DeqNode<KeyHashDate<K>>, 2>) {
158        unsafe {
159            match tagged_node.decompose_tag().into() {
160                CacheRegion::Window => {
161                    Self::unlink_node_ao_from_deque("window", &mut self.window, tagged_node);
162                }
163                CacheRegion::MainProbation => {
164                    Self::unlink_node_ao_from_deque("probation", &mut self.probation, tagged_node);
165                }
166                CacheRegion::MainProtected => {
167                    Self::unlink_node_ao_from_deque("protected", &mut self.protected, tagged_node);
168                }
169                CacheRegion::Other => unreachable!(),
170            }
171        }
172    }
173
174    unsafe fn unlink_node_ao_from_deque(
175        deq_name: &str,
176        deq: &mut Deque<KeyHashDate<K>>,
177        tagged_node: TagNonNull<DeqNode<KeyHashDate<K>>, 2>,
178    ) {
179        let (node, tag) = tagged_node.decompose();
180        let p = node.as_ref();
181        assert_eq!(
182            deq.region(),
183            tag,
184            "unlink_node - node is not a member of {deq_name} deque. {p:?}"
185        );
186        if deq.contains(p) {
187            // https://github.com/moka-rs/moka/issues/64
188            deq.unlink_and_drop(node);
189        }
190    }
191
192    pub(crate) fn unlink_node_wo(
193        deq: &mut Deque<KeyHashDate<K>>,
194        node: NonNull<DeqNode<KeyHashDate<K>>>,
195    ) {
196        unsafe {
197            let p = node.as_ref();
198            if deq.contains(p) {
199                // https://github.com/moka-rs/moka/issues/64
200                deq.unlink_and_drop(node);
201            }
202        }
203    }
204}
205
206// TODO: Add tests and run Miri with them.
moka/common/concurrent/deques.rs

moka/common/concurrent/
deques.rs
