foyer_memory/eviction/
mod.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::sync::Arc;
16
17use foyer_common::code::{Key, Value};
18use serde::{de::DeserializeOwned, Serialize};
19
20use crate::{
21    error::Result,
22    record::{CacheHint, Record},
23};
24
25pub trait Hint: Send + Sync + 'static + Clone + Default + From<CacheHint> + Into<CacheHint> {}
26impl<T> Hint for T where T: Send + Sync + 'static + Clone + Default + From<CacheHint> + Into<CacheHint> {}
27
28pub trait State: Send + Sync + 'static + Default {}
29impl<T> State for T where T: Send + Sync + 'static + Default {}
30
31pub trait Config: Send + Sync + 'static + Clone + Serialize + DeserializeOwned + Default {}
32impl<T> Config for T where T: Send + Sync + 'static + Clone + Serialize + DeserializeOwned + Default {}
33
34/// Wrapper for one of the three kind of operations for the eviction container:
35///
36/// 1. no operation
37/// 2. immutable operation
38/// 3. mutable operation
39#[expect(clippy::type_complexity)]
40pub enum Op<E>
41where
42    E: Eviction,
43{
44    /// no operation
45    Noop,
46    /// immutable operation
47    Immutable(Box<dyn Fn(&E, &Arc<Record<E>>) + Send + Sync + 'static>),
48    /// mutable operation
49    Mutable(Box<dyn FnMut(&mut E, &Arc<Record<E>>) + Send + Sync + 'static>),
50}
51
52impl<E> Op<E>
53where
54    E: Eviction,
55{
56    /// no operation
57    pub fn noop() -> Self {
58        Self::Noop
59    }
60
61    /// immutable operation
62    pub fn immutable<F>(f: F) -> Self
63    where
64        F: Fn(&E, &Arc<Record<E>>) + Send + Sync + 'static,
65    {
66        Self::Immutable(Box::new(f))
67    }
68
69    /// mutable operation
70    pub fn mutable<F>(f: F) -> Self
71    where
72        F: FnMut(&mut E, &Arc<Record<E>>) + Send + Sync + 'static,
73    {
74        Self::Mutable(Box::new(f))
75    }
76}
77
78/// Cache eviction algorithm abstraction.
79///
80/// [`Eviction`] provides essential APIs for the plug-and-play algorithm abstraction.
81///
82/// [`Eviction`] is needs to be implemented to support a new cache eviction algorithm.
83///
84/// # Safety
85///
86/// The pointer can be dereferenced as a mutable reference ***iff*** the `self` reference is also mutable.
87/// Dereferencing a pointer as a mutable reference when `self` is immutable will cause UB.
88pub trait Eviction: Send + Sync + 'static + Sized {
89    /// Cache eviction algorithm configurations.
90    type Config: Config;
91    /// Cache key. Generally, it is supposed to be a generic type of the implementation.
92    type Key: Key;
93    /// Cache value. Generally, it is supposed to be a generic type of the implementation.
94    type Value: Value;
95    /// Hint for a cache entry. Can be used to support priority at the entry granularity.
96    type Hint: Hint;
97    /// State for a cache entry. Mutable state for maintaining the cache eviction algorithm implementation.
98    type State: State;
99
100    /// Create a new cache eviction algorithm instance with the given arguments.
101    fn new(capacity: usize, config: &Self::Config) -> Self;
102
103    /// Update the arguments of the ache eviction algorithm instance.
104    fn update(&mut self, capacity: usize, config: Option<&Self::Config>) -> Result<()>;
105
106    /// Push a record into the cache eviction algorithm instance.
107    ///
108    /// The caller guarantees that the record is NOT in the cache eviction algorithm instance.
109    ///
110    /// The cache eviction algorithm instance MUST hold the record and set its `IN_EVICTION` flag to true.
111    fn push(&mut self, record: Arc<Record<Self>>);
112
113    /// Push a record from the cache eviction algorithm instance.
114    ///
115    /// The cache eviction algorithm instance MUST remove the record and set its `IN_EVICTION` flag to false.
116    fn pop(&mut self) -> Option<Arc<Record<Self>>>;
117
118    /// Remove a record from the cache eviction algorithm instance.
119    ///
120    /// The caller guarantees that the record is in the cache eviction algorithm instance.
121    ///
122    /// The cache eviction algorithm instance MUST remove the record and set its `IN_EVICTION` flag to false.
123    fn remove(&mut self, record: &Arc<Record<Self>>);
124
125    /// Remove all records from the cache eviction algorithm instance.
126    ///
127    /// The cache eviction algorithm instance MUST remove the records and set its `IN_EVICTION` flag to false.
128    fn clear(&mut self) {
129        while self.pop().is_some() {}
130    }
131
132    /// `acquire` is called when an external caller acquire a cache entry from the cache.
133    ///
134    /// The entry can be EITHER in the cache eviction algorithm instance or not.
135    fn acquire() -> Op<Self>;
136
137    /// `release` is called when the last external caller drops the cache entry.
138    ///
139    /// The entry can be EITHER in the cache eviction algorithm instance or not.
140    fn release() -> Op<Self>;
141}
142
143pub mod fifo;
144pub mod lfu;
145pub mod lru;
146pub mod s3fifo;
147
148#[cfg(test)]
149pub mod test_utils;
foyer_memory/eviction/mod.rs

foyer_memory/eviction/
mod.rs
