salsa 0.26.1

A generic framework for on-demand, incrementalized computation (experimental)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

//! Least Recently Used (LRU) eviction policy.
//!
//! This policy tracks the most recently accessed items and evicts
//! the least recently used ones when the cache exceeds its capacity.

use std::num::NonZeroUsize;

use crate::Id;
use crate::hash::FxLinkedHashSet;
use crate::sync::Mutex;

use super::{EvictionPolicy, HasCapacity};

/// Least Recently Used eviction policy.
///
/// When the number of memoized values exceeds the configured capacity,
/// the least recently accessed values are evicted at the start of each
/// new revision.
pub struct Lru {
    capacity: Option<NonZeroUsize>,
    set: Mutex<FxLinkedHashSet<Id>>,
}

impl Lru {
    #[inline(never)]
    fn insert(&self, id: Id) {
        self.set.lock().insert(id);
    }
}

impl EvictionPolicy for Lru {
    fn new(cap: usize) -> Self {
        Self {
            capacity: NonZeroUsize::new(cap),
            set: Mutex::default(),
        }
    }

    #[inline(always)]
    fn record_use(&self, id: Id) {
        if self.capacity.is_some() {
            self.insert(id);
        }
    }

    fn set_capacity(&mut self, capacity: usize) {
        self.capacity = NonZeroUsize::new(capacity);
        if self.capacity.is_none() {
            self.set.get_mut().clear();
        }
    }

    fn for_each_evicted(&mut self, mut cb: impl FnMut(Id)) {
        let Some(cap) = self.capacity else {
            return;
        };
        let set = self.set.get_mut();
        while set.len() > cap.get() {
            if let Some(id) = set.pop_front() {
                cb(id);
            }
        }
    }
}

impl HasCapacity for Lru {}