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::{
18    code::{Key, Value},
19    error::Result,
20    properties::Properties,
21};
22use serde::{de::DeserializeOwned, Serialize};
23
24use crate::record::Record;
25
26pub trait State: Send + Sync + 'static + Default {}
27impl<T> State for T where T: Send + Sync + 'static + Default {}
28
29pub trait Config: Send + Sync + 'static + Clone + Serialize + DeserializeOwned + Default {}
30impl<T> Config for T where T: Send + Sync + 'static + Clone + Serialize + DeserializeOwned + Default {}
31
32/// Wrapper for one of the three kind of operations for the eviction container:
33///
34/// 1. no operation
35/// 2. immutable operation
36/// 3. mutable operation
37#[expect(clippy::type_complexity)]
38pub enum Op<E>
39where
40    E: Eviction,
41{
42    /// no operation
43    Noop,
44    /// immutable operation
45    Immutable(Box<dyn Fn(&E, &Arc<Record<E>>) + Send + Sync + 'static>),
46    /// mutable operation
47    Mutable(Box<dyn FnMut(&mut E, &Arc<Record<E>>) + Send + Sync + 'static>),
48}
49
50impl<E> Op<E>
51where
52    E: Eviction,
53{
54    /// no operation
55    pub fn noop() -> Self {
56        Self::Noop
57    }
58
59    /// immutable operation
60    pub fn immutable<F>(f: F) -> Self
61    where
62        F: Fn(&E, &Arc<Record<E>>) + Send + Sync + 'static,
63    {
64        Self::Immutable(Box::new(f))
65    }
66
67    /// mutable operation
68    pub fn mutable<F>(f: F) -> Self
69    where
70        F: FnMut(&mut E, &Arc<Record<E>>) + Send + Sync + 'static,
71    {
72        Self::Mutable(Box::new(f))
73    }
74}
75
76/// Cache eviction algorithm abstraction.
77///
78/// [`Eviction`] provides essential APIs for the plug-and-play algorithm abstraction.
79///
80/// [`Eviction`] is needs to be implemented to support a new cache eviction algorithm.
81///
82/// # Safety
83///
84/// The pointer can be dereferenced as a mutable reference ***iff*** the `self` reference is also mutable.
85/// Dereferencing a pointer as a mutable reference when `self` is immutable will cause UB.
86pub trait Eviction: Send + Sync + 'static + Sized {
87    /// Cache eviction algorithm configurations.
88    type Config: Config;
89    /// Cache key. Generally, it is supposed to be a generic type of the implementation.
90    type Key: Key;
91    /// Cache value. Generally, it is supposed to be a generic type of the implementation.
92    type Value: Value;
93    /// Properties for a cache entry, it is supposed to be a generic type of the implementation.
94    ///
95    /// Can be used to support priority at the entry granularity.
96    type Properties: Properties;
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;
147pub mod sieve;
148
149#[cfg(any(test, feature = "test_utils"))]
150pub mod test_utils;
foyer_memory/eviction/mod.rs

foyer_memory/eviction/
mod.rs
