foyer_memory/eviction/
fifo.rs

1// Copyright 2025 foyer Project Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::{mem::offset_of, sync::Arc};
16
17use foyer_common::{
18    code::{Key, Value},
19    error::Result,
20    properties::Properties,
21};
22use intrusive_collections::{intrusive_adapter, LinkedList, LinkedListAtomicLink};
23use serde::{Deserialize, Serialize};
24
25use super::{Eviction, Op};
26use crate::record::Record;
27
28/// Fifo eviction algorithm config.
29#[derive(Debug, Clone, Default, Serialize, Deserialize)]
30pub struct FifoConfig {}
31
32/// Fifo eviction algorithm state.
33#[derive(Debug, Default)]
34pub struct FifoState {
35    link: LinkedListAtomicLink,
36}
37
38intrusive_adapter! { Adapter<K, V, P> = Arc<Record<Fifo<K, V, P>>>: Record<Fifo<K, V, P>> { ?offset = Record::<Fifo<K, V, P>>::STATE_OFFSET + offset_of!(FifoState, link) => LinkedListAtomicLink } where K: Key, V: Value, P: Properties }
39
40pub struct Fifo<K, V, P>
41where
42    K: Key,
43    V: Value,
44    P: Properties,
45{
46    queue: LinkedList<Adapter<K, V, P>>,
47}
48
49impl<K, V, P> Eviction for Fifo<K, V, P>
50where
51    K: Key,
52    V: Value,
53    P: Properties,
54{
55    type Config = FifoConfig;
56    type Key = K;
57    type Value = V;
58    type Properties = P;
59    type State = FifoState;
60
61    fn new(_capacity: usize, _config: &Self::Config) -> Self
62    where
63        Self: Sized,
64    {
65        Self {
66            queue: LinkedList::new(Adapter::new()),
67        }
68    }
69
70    fn update(&mut self, _: usize, _: Option<&Self::Config>) -> Result<()> {
71        Ok(())
72    }
73
74    fn push(&mut self, record: Arc<Record<Self>>) {
75        record.set_in_eviction(true);
76        self.queue.push_back(record);
77    }
78
79    fn pop(&mut self) -> Option<Arc<Record<Self>>> {
80        self.queue.pop_front().inspect(|record| record.set_in_eviction(false))
81    }
82
83    fn remove(&mut self, record: &Arc<Record<Self>>) {
84        unsafe { self.queue.remove_from_ptr(Arc::as_ptr(record)) };
85        record.set_in_eviction(false);
86    }
87
88    fn acquire() -> Op<Self> {
89        Op::noop()
90    }
91
92    fn release() -> Op<Self> {
93        Op::noop()
94    }
95}
96
97#[cfg(test)]
98pub mod tests {
99
100    use itertools::Itertools;
101
102    use super::*;
103    use crate::{
104        eviction::test_utils::{assert_ptr_eq, assert_ptr_vec_eq, Dump, TestProperties},
105        record::Data,
106    };
107
108    impl<K, V> Dump for Fifo<K, V, TestProperties>
109    where
110        K: Key + Clone,
111        V: Value + Clone,
112    {
113        type Output = Vec<Arc<Record<Self>>>;
114        fn dump(&self) -> Self::Output {
115            let mut res = vec![];
116            let mut cursor = self.queue.cursor();
117            loop {
118                cursor.move_next();
119                match cursor.clone_pointer() {
120                    Some(record) => res.push(record),
121                    None => break,
122                }
123            }
124            res
125        }
126    }
127
128    type TestFifo = Fifo<u64, u64, TestProperties>;
129
130    #[test]
131    fn test_fifo() {
132        let rs = (0..8)
133            .map(|i| {
134                Arc::new(Record::new(Data {
135                    key: i,
136                    value: i,
137                    properties: TestProperties::default(),
138                    hash: i,
139                    weight: 1,
140                }))
141            })
142            .collect_vec();
143        let r = |i: usize| rs[i].clone();
144
145        let mut fifo = TestFifo::new(100, &FifoConfig {});
146
147        // 0, 1, 2, 3
148        fifo.push(r(0));
149        fifo.push(r(1));
150        fifo.push(r(2));
151        fifo.push(r(3));
152
153        // 2, 3
154        let r0 = fifo.pop().unwrap();
155        let r1 = fifo.pop().unwrap();
156        assert_ptr_eq(&rs[0], &r0);
157        assert_ptr_eq(&rs[1], &r1);
158
159        // 2, 3, 4, 5, 6
160        fifo.push(r(4));
161        fifo.push(r(5));
162        fifo.push(r(6));
163
164        // 2, 6
165        fifo.remove(&rs[3]);
166        fifo.remove(&rs[4]);
167        fifo.remove(&rs[5]);
168
169        assert_ptr_vec_eq(fifo.dump(), vec![r(2), r(6)]);
170
171        fifo.clear();
172
173        assert_ptr_vec_eq(fifo.dump(), vec![]);
174    }
175}
foyer_memory/eviction/fifo.rs

foyer_memory/eviction/
fifo.rs
