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

foyer_memory/eviction/
mod.rs
