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

foyer_memory/eviction/
fifo.rs
