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    properties::Properties,
20};
21use intrusive_collections::{intrusive_adapter, LinkedList, LinkedListAtomicLink};
22use serde::{Deserialize, Serialize};
23
24use super::{Eviction, Op};
25use crate::{error::Result, record::Record};
26
27/// Fifo eviction algorithm config.
28#[derive(Debug, Clone, Default, Serialize, Deserialize)]
29pub struct FifoConfig {}
30
31/// Fifo eviction algorithm state.
32#[derive(Debug, Default)]
33pub struct FifoState {
34    link: LinkedListAtomicLink,
35}
36
37intrusive_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 }
38
39pub struct Fifo<K, V, P>
40where
41    K: Key,
42    V: Value,
43    P: Properties,
44{
45    queue: LinkedList<Adapter<K, V, P>>,
46}
47
48impl<K, V, P> Eviction for Fifo<K, V, P>
49where
50    K: Key,
51    V: Value,
52    P: Properties,
53{
54    type Config = FifoConfig;
55    type Key = K;
56    type Value = V;
57    type Properties = P;
58    type State = FifoState;
59
60    fn new(_capacity: usize, _config: &Self::Config) -> Self
61    where
62        Self: Sized,
63    {
64        Self {
65            queue: LinkedList::new(Adapter::new()),
66        }
67    }
68
69    fn update(&mut self, _: usize, _: Option<&Self::Config>) -> Result<()> {
70        Ok(())
71    }
72
73    fn push(&mut self, record: Arc<Record<Self>>) {
74        record.set_in_eviction(true);
75        self.queue.push_back(record);
76    }
77
78    fn pop(&mut self) -> Option<Arc<Record<Self>>> {
79        self.queue.pop_front().inspect(|record| record.set_in_eviction(false))
80    }
81
82    fn remove(&mut self, record: &Arc<Record<Self>>) {
83        unsafe { self.queue.remove_from_ptr(Arc::as_ptr(record)) };
84        record.set_in_eviction(false);
85    }
86
87    fn acquire() -> Op<Self> {
88        Op::noop()
89    }
90
91    fn release() -> Op<Self> {
92        Op::noop()
93    }
94}
95
96#[cfg(test)]
97pub mod tests {
98
99    use itertools::Itertools;
100
101    use super::*;
102    use crate::{
103        eviction::test_utils::{assert_ptr_eq, assert_ptr_vec_eq, Dump, TestProperties},
104        record::Data,
105    };
106
107    impl<K, V> Dump for Fifo<K, V, TestProperties>
108    where
109        K: Key + Clone,
110        V: Value + Clone,
111    {
112        type Output = Vec<Arc<Record<Self>>>;
113        fn dump(&self) -> Self::Output {
114            let mut res = vec![];
115            let mut cursor = self.queue.cursor();
116            loop {
117                cursor.move_next();
118                match cursor.clone_pointer() {
119                    Some(record) => res.push(record),
120                    None => break,
121                }
122            }
123            res
124        }
125    }
126
127    type TestFifo = Fifo<u64, u64, TestProperties>;
128
129    #[test]
130    fn test_fifo() {
131        let rs = (0..8)
132            .map(|i| {
133                Arc::new(Record::new(Data {
134                    key: i,
135                    value: i,
136                    properties: TestProperties::default(),
137                    hash: i,
138                    weight: 1,
139                }))
140            })
141            .collect_vec();
142        let r = |i: usize| rs[i].clone();
143
144        let mut fifo = TestFifo::new(100, &FifoConfig {});
145
146        // 0, 1, 2, 3
147        fifo.push(r(0));
148        fifo.push(r(1));
149        fifo.push(r(2));
150        fifo.push(r(3));
151
152        // 2, 3
153        let r0 = fifo.pop().unwrap();
154        let r1 = fifo.pop().unwrap();
155        assert_ptr_eq(&rs[0], &r0);
156        assert_ptr_eq(&rs[1], &r1);
157
158        // 2, 3, 4, 5, 6
159        fifo.push(r(4));
160        fifo.push(r(5));
161        fifo.push(r(6));
162
163        // 2, 6
164        fifo.remove(&rs[3]);
165        fifo.remove(&rs[4]);
166        fifo.remove(&rs[5]);
167
168        assert_ptr_vec_eq(fifo.dump(), vec![r(2), r(6)]);
169
170        fifo.clear();
171
172        assert_ptr_vec_eq(fifo.dump(), vec![]);
173    }
174}
foyer_memory/eviction/fifo.rs

foyer_memory/eviction/
fifo.rs
