/rust/registry/src/index.crates.io-1949cf8c6b5b557f/quick_cache-0.6.18/src/unsync.rs

Source
use crate::{
    linked_slab::Token,
    options::*,
    shard::{self, CacheShard, InsertStrategy},
    DefaultHashBuilder, Equivalent, Lifecycle, MemoryUsed, UnitWeighter, Weighter,
};
use std::hash::{BuildHasher, Hash};

/// A non-concurrent cache.
#[derive(Clone)]
pub struct Cache<
    Key,
    Val,
    We = UnitWeighter,
    B = DefaultHashBuilder,
    L = DefaultLifecycle<Key, Val>,
> {
    shard: CacheShard<Key, Val, We, B, L, SharedPlaceholder>,
}

impl<Key: Eq + Hash, Val> Cache<Key, Val> {
    /// Creates a new cache with holds up to `items_capacity` items (approximately).
    pub fn new(items_capacity: usize) -> Self {
        Self::with(
            items_capacity,
            items_capacity as u64,
            Default::default(),
            Default::default(),
            Default::default(),
        )
    }
}

impl<Key: Eq + Hash, Val, We: Weighter<Key, Val>> Cache<Key, Val, We> {
    pub fn with_weighter(
        estimated_items_capacity: usize,
        weight_capacity: u64,
        weighter: We,
    ) -> Self {
        Self::with(
            estimated_items_capacity,
            weight_capacity,
            weighter,
            Default::default(),
            Default::default(),
        )
    }
}

impl<Key: Eq + Hash, Val, We: Weighter<Key, Val>, B: BuildHasher, L: Lifecycle<Key, Val>>
    Cache<Key, Val, We, B, L>
{
    /// Creates a new cache that can hold up to `weight_capacity` in weight.
    /// `estimated_items_capacity` is the estimated number of items the cache is expected to hold,
    /// roughly equivalent to `weight_capacity / average item weight`.
    pub fn with(
        estimated_items_capacity: usize,
        weight_capacity: u64,
        weighter: We,
        hash_builder: B,
        lifecycle: L,
    ) -> Self {
        Self::with_options(
            OptionsBuilder::new()
                .estimated_items_capacity(estimated_items_capacity)
                .weight_capacity(weight_capacity)
                .build()
                .unwrap(),
            weighter,
            hash_builder,
            lifecycle,
        )
    }

    /// Constructs a cache based on [OptionsBuilder].
    ///
    /// # Example
    ///
    /// ```rust
    /// use quick_cache::{unsync::{Cache, DefaultLifecycle}, OptionsBuilder, UnitWeighter, DefaultHashBuilder};
    ///
    /// Cache::<(String, u64), String>::with_options(
    ///   OptionsBuilder::new()
    ///     .estimated_items_capacity(10000)
    ///     .weight_capacity(10000)
    ///     .build()
    ///     .unwrap(),
    ///     UnitWeighter,
    ///     DefaultHashBuilder::default(),
    ///     DefaultLifecycle::default(),
    /// );
    /// ```
    pub fn with_options(options: Options, weighter: We, hash_builder: B, lifecycle: L) -> Self {
        let shard = CacheShard::new(
            options.hot_allocation,
            options.ghost_allocation,
            options.estimated_items_capacity,
            options.weight_capacity,
            weighter,
            hash_builder,
            lifecycle,
        );
        Self { shard }
    }

    /// Returns whether the cache is empty.
    pub fn is_empty(&self) -> bool {
        self.shard.len() == 0
    }

    /// Returns the number of cached items
    pub fn len(&self) -> usize {
        self.shard.len()
    }

    /// Returns the total weight of cached items
    pub fn weight(&self) -> u64 {
        self.shard.weight()
    }

    /// Returns the maximum weight of cached items
    pub fn capacity(&self) -> u64 {
        self.shard.capacity()
    }

    /// Returns the number of misses
    #[cfg(feature = "stats")]
    pub fn misses(&self) -> u64 {
        self.shard.misses()
    }

    /// Returns the number of hits
    #[cfg(feature = "stats")]
    pub fn hits(&self) -> u64 {
        self.shard.hits()
    }

    /// Reserver additional space for `additional` entries.
    /// Note that this is counted in entries, and is not weighted.
    pub fn reserve(&mut self, additional: usize) {
        self.shard.reserve(additional);
    }

    /// Check if a key exist in the cache.
    pub fn contains_key<Q>(&self, key: &Q) -> bool
    where
        Q: Hash + Equivalent<Key> + ?Sized,
    {
        self.shard.contains(self.shard.hash(key), key)
    }

    /// Fetches an item from the cache.
    pub fn get<Q>(&self, key: &Q) -> Option<&Val>
    where
        Q: Hash + Equivalent<Key> + ?Sized,
    {
        self.shard.get(self.shard.hash(key), key)
    }

    /// Fetches an item from the cache.
    ///
    /// Note: Leaking the returned RefMut might cause cache weight tracking to be inaccurate.
    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<RefMut<'_, Key, Val, We, B, L>>
    where
        Q: Hash + Equivalent<Key> + ?Sized,
    {
        self.shard.get_mut(self.shard.hash(key), key).map(RefMut)
    }

    /// Peeks an item from the cache. Contrary to gets, peeks don't alter the key "hotness".
    pub fn peek<Q>(&self, key: &Q) -> Option<&Val>
    where
        Q: Hash + Equivalent<Key> + ?Sized,
    {
        self.shard.peek(self.shard.hash(key), key)
    }

    /// Peeks an item from the cache. Contrary to gets, peeks don't alter the key "hotness".
    ///
    /// Note: Leaking the returned RefMut might cause cache weight tracking to be inaccurate.
    pub fn peek_mut<Q>(&mut self, key: &Q) -> Option<RefMut<'_, Key, Val, We, B, L>>
    where
        Q: Hash + Equivalent<Key> + ?Sized,
    {
        self.shard.peek_mut(self.shard.hash(key), key).map(RefMut)
    }

    /// Remove an item from the cache whose key is `key`.
    /// Returns the removed entry, if any.
    pub fn remove<Q>(&mut self, key: &Q) -> Option<(Key, Val)>
    where
        Q: Hash + Equivalent<Key> + ?Sized,
    {
        self.shard.remove(self.shard.hash(key), key)
    }

    /// Remove an item from the cache whose key is `key` if `f(&value)` returns `true` for that entry.
    /// Compared to peek and remove, this method is more efficient as it requires only 1 lookup.
    ///
    /// Returns the removed entry, if any.
    pub fn remove_if<Q, F>(&mut self, key: &Q, f: F) -> Option<(Key, Val)>
    where
        Q: Hash + Equivalent<Key> + ?Sized,
        F: FnOnce(&Val) -> bool,
    {
        self.shard.remove_if(self.shard.hash(key), key, f)
    }

    /// Replaces an item in the cache, but only if it already exists.
    /// If `soft` is set, the replace operation won't affect the "hotness" of the key,
    /// even if the value is replaced.
    ///
    /// Returns `Ok` if the entry was admitted and `Err(_)` if it wasn't.
    pub fn replace(&mut self, key: Key, value: Val, soft: bool) -> Result<(), (Key, Val)> {
        let lcs = self.replace_with_lifecycle(key, value, soft)?;
        self.shard.lifecycle.end_request(lcs);
        Ok(())
    }

    /// Replaces an item in the cache, but only if it already exists.
    /// If `soft` is set, the replace operation won't affect the "hotness" of the key,
    /// even if the value is replaced.
    ///
    /// Returns `Ok` if the entry was admitted and `Err(_)` if it wasn't.
    pub fn replace_with_lifecycle(
        &mut self,
        key: Key,
        value: Val,
        soft: bool,
    ) -> Result<L::RequestState, (Key, Val)> {
        let mut lcs = self.shard.lifecycle.begin_request();
        self.shard.insert(
            &mut lcs,
            self.shard.hash(&key),
            key,
            value,
            InsertStrategy::Replace { soft },
        )?;
        Ok(lcs)
    }

    /// Retains only the items specified by the predicate.
    /// In other words, remove all items for which `f(&key, &value)` returns `false`. The
    /// elements are visited in arbitrary order.
    pub fn retain<F>(&mut self, f: F)
    where
        F: Fn(&Key, &Val) -> bool,
    {
        self.shard.retain(f);
    }

    /// Gets or inserts an item in the cache with key `key`.
    /// Returns a reference to the inserted `value` if it was admitted to the cache.
    ///
    /// See also `get_ref_or_guard`.
    pub fn get_or_insert_with<Q, E>(
        &mut self,
        key: &Q,
        with: impl FnOnce() -> Result<Val, E>,
    ) -> Result<Option<&Val>, E>
    where
        Q: Hash + Equivalent<Key> + ToOwned<Owned = Key> + ?Sized,
    {
        let idx = match self.shard.upsert_placeholder(self.shard.hash(key), key) {
            Ok((idx, _)) => idx,
            Err((plh, _)) => {
                let v = with()?;
                let mut lcs = self.shard.lifecycle.begin_request();
                let replaced = self.shard.replace_placeholder(&mut lcs, &plh, false, v);
                self.shard.lifecycle.end_request(lcs);
                debug_assert!(replaced.is_ok(), "unsync replace_placeholder can't fail");
                plh.idx
            }
        };
        Ok(self.shard.peek_token(idx))
    }

    /// Gets or inserts an item in the cache with key `key`.
    /// Returns a mutable reference to the inserted `value` if it was admitted to the cache.
    ///
    /// See also `get_mut_or_guard`.
    pub fn get_mut_or_insert_with<'a, Q, E>(
        &'a mut self,
        key: &Q,
        with: impl FnOnce() -> Result<Val, E>,
    ) -> Result<Option<RefMut<'a, Key, Val, We, B, L>>, E>
    where
        Q: Hash + Equivalent<Key> + ToOwned<Owned = Key> + ?Sized,
    {
        let idx = match self.shard.upsert_placeholder(self.shard.hash(key), key) {
            Ok((idx, _)) => idx,
            Err((plh, _)) => {
                let v = with()?;
                let mut lcs = self.shard.lifecycle.begin_request();
                let replaced = self.shard.replace_placeholder(&mut lcs, &plh, false, v);
                debug_assert!(replaced.is_ok(), "unsync replace_placeholder can't fail");
                self.shard.lifecycle.end_request(lcs);
                plh.idx
            }
        };
        Ok(self.shard.peek_token_mut(idx).map(RefMut))
    }

    /// Gets an item from the cache with key `key` .
    /// If the corresponding value isn't present in the cache, this functions returns a guard
    /// that can be used to insert the value once it's computed.
    pub fn get_ref_or_guard<Q>(&mut self, key: &Q) -> Result<&Val, Guard<'_, Key, Val, We, B, L>>
    where
        Q: Hash + Equivalent<Key> + ToOwned<Owned = Key> + ?Sized,
    {
        // TODO: this could be using a simpler entry API
        match self.shard.upsert_placeholder(self.shard.hash(key), key) {
            Ok((_, v)) => unsafe {
                // Rustc gets insanely confused about returning from mut borrows
                // Safety: v has the same lifetime as self
                let v: *const Val = v;
                Ok(&*v)
            },
            Err((placeholder, _)) => Err(Guard {
                cache: self,
                placeholder,
                inserted: false,
            }),
        }
    }

    /// Gets an item from the cache with key `key` .
    /// If the corresponding value isn't present in the cache, this functions returns a guard
    /// that can be used to insert the value once it's computed.
    ///
    /// Note: Leaking the returned RefMut might cause cache weight tracking to be inaccurate.
    pub fn get_mut_or_guard<'a, Q>(
        &'a mut self,
        key: &Q,
    ) -> Result<Option<RefMut<'a, Key, Val, We, B, L>>, Guard<'a, Key, Val, We, B, L>>
    where
        Q: Hash + Equivalent<Key> + ToOwned<Owned = Key> + ?Sized,
    {
        // TODO: this could be using a simpler entry API
        match self.shard.upsert_placeholder(self.shard.hash(key), key) {
            Ok((idx, _)) => Ok(self.shard.peek_token_mut(idx).map(RefMut)),
            Err((placeholder, _)) => Err(Guard {
                cache: self,
                placeholder,
                inserted: false,
            }),
        }
    }

    /// Inserts an item in the cache with key `key`.
    pub fn insert(&mut self, key: Key, value: Val) {
        let lcs = self.insert_with_lifecycle(key, value);
        self.shard.lifecycle.end_request(lcs);
    }

    /// Inserts an item in the cache with key `key`.
    pub fn insert_with_lifecycle(&mut self, key: Key, value: Val) -> L::RequestState {
        let mut lcs = self.shard.lifecycle.begin_request();
        let result = self.shard.insert(
            &mut lcs,
            self.shard.hash(&key),
            key,
            value,
            InsertStrategy::Insert,
        );
        // result cannot err with the Insert strategy
        debug_assert!(result.is_ok());
        lcs
    }

    /// Clear all items from the cache
    pub fn clear(&mut self) {
        self.shard.clear();
    }

    /// Iterator for the items in the cache
    pub fn iter(&self) -> impl Iterator<Item = (&'_ Key, &'_ Val)> + '_ {
        // TODO: add a concrete type, impl trait in the public api is really bad.
        self.shard.iter()
    }

    /// Drain all items from the cache
    ///
    /// The cache will be emptied even if the returned iterator isn't fully consumed.
    pub fn drain(&mut self) -> impl Iterator<Item = (Key, Val)> + '_ {
        // TODO: add a concrete type, impl trait in the public api is really bad.
        self.shard.drain()
    }

    /// Sets the cache to a new weight capacity.
    ///
    /// If the new capacity is smaller than the current weight, items will be evicted
    /// to bring the cache within the new limit.
    pub fn set_capacity(&mut self, new_weight_capacity: u64) {
        self.shard.set_capacity(new_weight_capacity);
    }

    #[cfg(any(fuzzing, test))]
    pub fn validate(&self, accept_overweight: bool) {
        self.shard.validate(accept_overweight);
    }

    /// Get total memory used by cache data structures
    ///
    /// It should be noted that if cache key or value is some type like `Vec<T>`,
    /// the memory allocated in the heap will not be counted.
    pub fn memory_used(&self) -> MemoryUsed {
        self.shard.memory_used()
    }
}

impl<Key, Val, We, B, L> std::fmt::Debug for Cache<Key, Val, We, B, L> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("Cache").finish_non_exhaustive()
    }
}

/// Default `Lifecycle` for the unsync cache.
pub struct DefaultLifecycle<Key, Val>(std::marker::PhantomData<(Key, Val)>);

impl<Key, Val> std::fmt::Debug for DefaultLifecycle<Key, Val> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_tuple("DefaultLifecycle").finish()
    }
}

impl<Key, Val> Default for DefaultLifecycle<Key, Val> {
    #[inline]
    fn default() -> Self {
        Self(Default::default())
    }
}

impl<Key, Val> Clone for DefaultLifecycle<Key, Val> {
    #[inline]
    fn clone(&self) -> Self {
        Self(Default::default())
    }
}

impl<Key, Val> Lifecycle<Key, Val> for DefaultLifecycle<Key, Val> {
    type RequestState = ();

    #[inline]
    fn begin_request(&self) -> Self::RequestState {}

    #[inline]
    fn on_evict(&self, _state: &mut Self::RequestState, _key: Key, _val: Val) {}
}

#[derive(Debug, Clone)]
pub(crate) struct SharedPlaceholder {
    hash: u64,
    idx: Token,
}

pub struct Guard<'a, Key, Val, We, B, L> {
    cache: &'a mut Cache<Key, Val, We, B, L>,
    placeholder: SharedPlaceholder,
    inserted: bool,
}

impl<Key: Eq + Hash, Val, We: Weighter<Key, Val>, B: BuildHasher, L: Lifecycle<Key, Val>>
    Guard<'_, Key, Val, We, B, L>
{
    /// Inserts the value into the placeholder
    pub fn insert(self, value: Val) {
        self.insert_internal(value, false);
    }

    /// Inserts the value into the placeholder
    pub fn insert_with_lifecycle(self, value: Val) -> L::RequestState {
        self.insert_internal(value, true).unwrap()
    }

    #[inline]
    fn insert_internal(mut self, value: Val, return_lcs: bool) -> Option<L::RequestState> {
        let mut lcs = self.cache.shard.lifecycle.begin_request();
        let replaced =
            self.cache
                .shard
                .replace_placeholder(&mut lcs, &self.placeholder, false, value);
        debug_assert!(replaced.is_ok(), "unsync replace_placeholder can't fail");
        self.inserted = true;
        if return_lcs {
            Some(lcs)
        } else {
            self.cache.shard.lifecycle.end_request(lcs);
            None
        }
    }
}

impl<Key, Val, We, B, L> Drop for Guard<'_, Key, Val, We, B, L> {
    #[inline]
    fn drop(&mut self) {
        #[cold]
        fn drop_slow<Key, Val, We, B, L>(this: &mut Guard<'_, Key, Val, We, B, L>) {
            this.cache.shard.remove_placeholder(&this.placeholder);
        }
        if !self.inserted {
            drop_slow(self);
        }
    }
}

pub struct RefMut<'cache, Key, Val, We: Weighter<Key, Val>, B, L>(
    crate::shard::RefMut<'cache, Key, Val, We, B, L, SharedPlaceholder>,
);

impl<Key, Val, We: Weighter<Key, Val>, B, L> std::ops::Deref for RefMut<'_, Key, Val, We, B, L> {
    type Target = Val;

    #[inline]
    fn deref(&self) -> &Self::Target {
        self.0.pair().1
    }
}

impl<Key, Val, We: Weighter<Key, Val>, B, L> std::ops::DerefMut for RefMut<'_, Key, Val, We, B, L> {
    #[inline]
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.0.value_mut()
    }
}

impl shard::SharedPlaceholder for SharedPlaceholder {
    #[inline]
    fn new(hash: u64, idx: Token) -> Self {
        Self { hash, idx }
    }

    #[inline]
    fn same_as(&self, _other: &Self) -> bool {
        true
    }

    #[inline]
    fn hash(&self) -> u64 {
        self.hash
    }

    #[inline]
    fn idx(&self) -> Token {
        self.idx
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    struct Weighter;

    impl crate::Weighter<u32, u32> for Weighter {
        fn weight(&self, _key: &u32, val: &u32) -> u64 {
            *val as u64
        }
    }

    #[test]
    fn test_zero_weights() {
        let mut cache = Cache::with_weighter(100, 100, Weighter);
        cache.insert(0, 0);
        assert_eq!(cache.weight(), 0);
        for i in 1..100 {
            cache.insert(i, i);
            cache.insert(i, i);
        }
        assert_eq!(cache.get(&0).copied(), Some(0));
        assert!(cache.contains_key(&0));
        let a = cache.weight();
        *cache.get_mut(&0).unwrap() += 1;
        assert_eq!(cache.weight(), a + 1);
        for i in 1..100 {
            cache.insert(i, i);
            cache.insert(i, i);
        }
        assert_eq!(cache.get(&0), None);
        assert!(!cache.contains_key(&0));

        cache.insert(0, 1);
        let a = cache.weight();
        *cache.get_mut(&0).unwrap() -= 1;
        assert_eq!(cache.weight(), a - 1);
        for i in 1..100 {
            cache.insert(i, i);
            cache.insert(i, i);
        }
        assert_eq!(cache.get(&0).copied(), Some(0));
        assert!(cache.contains_key(&0));
    }

    #[test]
    fn test_set_capacity() {
        let mut cache = Cache::new(100);
        for i in 0..80 {
            cache.insert(i, i);
        }
        let initial_len = cache.len();
        assert!(initial_len <= 80);

        // Set to smaller capacity
        cache.set_capacity(50);
        assert!(cache.len() <= 50);
        assert!(cache.weight() <= 50);
        cache.validate(false);

        // Set to larger capacity
        cache.set_capacity(200);
        assert_eq!(cache.capacity(), 200);
        cache.validate(false);

        // Insert more items
        for i in 100..180 {
            cache.insert(i, i);
        }
        assert!(cache.len() <= 180);
        assert!(cache.weight() <= 200);
        cache.validate(false);
    }

    #[test]
    fn test_set_capacity_with_ghosts() {
        // Create a cache that will generate ghost entries
        let mut cache = Cache::new(50);

        // Insert items to fill the cache
        for i in 0..100 {
            cache.insert(i, i);
        }
        cache.validate(false);

        // Set to smaller capacity - should trim both resident and ghost entries
        cache.set_capacity(25);
        assert!(cache.weight() <= 25);
        cache.validate(false);

        // Set back to larger capacity
        cache.set_capacity(100);
        assert_eq!(cache.capacity(), 100);
        cache.validate(false);

        // Insert more items
        for i in 100..150 {
            cache.insert(i, i);
        }
        cache.validate(false);
    }

    #[test]
    fn test_remove_if() {
        let mut cache = Cache::new(100);

        // Insert test data
        cache.insert(1, 10);
        cache.insert(2, 20);
        cache.insert(3, 30);

        // Test removing with predicate that returns true
        let removed = cache.remove_if(&2, |v| *v == 20);
        assert_eq!(removed, Some((2, 20)));
        assert_eq!(cache.get(&2), None);

        // Test removing with predicate that returns false
        let not_removed = cache.remove_if(&3, |v| *v == 999);
        assert_eq!(not_removed, None);
        assert_eq!(cache.get(&3), Some(&30));

        // Test removing non-existent key
        let not_found = cache.remove_if(&999, |_| true);
        assert_eq!(not_found, None);

        cache.validate(false);
    }
}

Coverage Report

Created: 2026-03-31 07:09

Line	Count	Source
1		use crate::{
2		linked_slab::Token,
3		options::*,
4		shard::{self, CacheShard, InsertStrategy},
5		DefaultHashBuilder, Equivalent, Lifecycle, MemoryUsed, UnitWeighter, Weighter,
6		};
7		use std::hash::{BuildHasher, Hash};
8
9		/// A non-concurrent cache.
10		#[derive(Clone)]
11		pub struct Cache<
12		Key,
13		Val,
14		We = UnitWeighter,
15		B = DefaultHashBuilder,
16		L = DefaultLifecycle<Key, Val>,
17		> {
18		shard: CacheShard<Key, Val, We, B, L, SharedPlaceholder>,
19		}
20
21		impl<Key: Eq + Hash, Val> Cache<Key, Val> {
22		/// Creates a new cache with holds up to `items_capacity` items (approximately).
23	0	pub fn new(items_capacity: usize) -> Self {
24	0	Self::with(
25	0	items_capacity,
26	0	items_capacity as u64,
27	0	Default::default(),
28	0	Default::default(),
29	0	Default::default(),
30		)
31	0	}
32		}
33
34		impl<Key: Eq + Hash, Val, We: Weighter<Key, Val>> Cache<Key, Val, We> {
35	0	pub fn with_weighter(
36	0	estimated_items_capacity: usize,
37	0	weight_capacity: u64,
38	0	weighter: We,
39	0	) -> Self {
40	0	Self::with(
41	0	estimated_items_capacity,
42	0	weight_capacity,
43	0	weighter,
44	0	Default::default(),
45	0	Default::default(),
46		)
47	0	}
48		}
49
50		impl<Key: Eq + Hash, Val, We: Weighter<Key, Val>, B: BuildHasher, L: Lifecycle<Key, Val>>
51		Cache<Key, Val, We, B, L>
52		{
53		/// Creates a new cache that can hold up to `weight_capacity` in weight.
54		/// `estimated_items_capacity` is the estimated number of items the cache is expected to hold,
55		/// roughly equivalent to `weight_capacity / average item weight`.
56	0	pub fn with(
57	0	estimated_items_capacity: usize,
58	0	weight_capacity: u64,
59	0	weighter: We,
60	0	hash_builder: B,
61	0	lifecycle: L,
62	0	) -> Self {
63	0	Self::with_options(
64	0	OptionsBuilder::new()
65	0	.estimated_items_capacity(estimated_items_capacity)
66	0	.weight_capacity(weight_capacity)
67	0	.build()
68	0	.unwrap(),
69	0	weighter,
70	0	hash_builder,
71	0	lifecycle,
72		)
73	0	}
74
75		/// Constructs a cache based on [OptionsBuilder].
76		///
77		/// # Example
78		///
79		/// ```rust
80		/// use quick_cache::{unsync::{Cache, DefaultLifecycle}, OptionsBuilder, UnitWeighter, DefaultHashBuilder};
81		///
82		/// Cache::<(String, u64), String>::with_options(
83		/// OptionsBuilder::new()
84		/// .estimated_items_capacity(10000)
85		/// .weight_capacity(10000)
86		/// .build()
87		/// .unwrap(),
88		/// UnitWeighter,
89		/// DefaultHashBuilder::default(),
90		/// DefaultLifecycle::default(),
91		/// );
92		/// ```
93	0	pub fn with_options(options: Options, weighter: We, hash_builder: B, lifecycle: L) -> Self {
94	0	let shard = CacheShard::new(
95	0	options.hot_allocation,
96	0	options.ghost_allocation,
97	0	options.estimated_items_capacity,
98	0	options.weight_capacity,
99	0	weighter,
100	0	hash_builder,
101	0	lifecycle,
102		);
103	0	Self { shard }
104	0	}
105
106		/// Returns whether the cache is empty.
107	0	pub fn is_empty(&self) -> bool {
108	0	self.shard.len() == 0
109	0	}
110
111		/// Returns the number of cached items
112	0	pub fn len(&self) -> usize {
113	0	self.shard.len()
114	0	}
115
116		/// Returns the total weight of cached items
117	0	pub fn weight(&self) -> u64 {
118	0	self.shard.weight()
119	0	}
120
121		/// Returns the maximum weight of cached items
122	0	pub fn capacity(&self) -> u64 {
123	0	self.shard.capacity()
124	0	}
125
126		/// Returns the number of misses
127		#[cfg(feature = "stats")]
128		pub fn misses(&self) -> u64 {
129		self.shard.misses()
130		}
131
132		/// Returns the number of hits
133		#[cfg(feature = "stats")]
134		pub fn hits(&self) -> u64 {
135		self.shard.hits()
136		}
137
138		/// Reserver additional space for `additional` entries.
139		/// Note that this is counted in entries, and is not weighted.
140	0	pub fn reserve(&mut self, additional: usize) {
141	0	self.shard.reserve(additional);
142	0	}
143
144		/// Check if a key exist in the cache.
145	0	pub fn contains_key<Q>(&self, key: &Q) -> bool
146	0	where
147	0	Q: Hash + Equivalent<Key> + ?Sized,
148		{
149	0	self.shard.contains(self.shard.hash(key), key)
150	0	}
151
152		/// Fetches an item from the cache.
153	0	pub fn get<Q>(&self, key: &Q) -> Option<&Val>
154	0	where
155	0	Q: Hash + Equivalent<Key> + ?Sized,
156		{
157	0	self.shard.get(self.shard.hash(key), key)
158	0	}
159
160		/// Fetches an item from the cache.
161		///
162		/// Note: Leaking the returned RefMut might cause cache weight tracking to be inaccurate.
163	0	pub fn get_mut<Q>(&mut self, key: &Q) -> Option<RefMut<'_, Key, Val, We, B, L>>
164	0	where
165	0	Q: Hash + Equivalent<Key> + ?Sized,
166		{
167	0	self.shard.get_mut(self.shard.hash(key), key).map(RefMut)
168	0	}
169
170		/// Peeks an item from the cache. Contrary to gets, peeks don't alter the key "hotness".
171	0	pub fn peek<Q>(&self, key: &Q) -> Option<&Val>
172	0	where
173	0	Q: Hash + Equivalent<Key> + ?Sized,
174		{
175	0	self.shard.peek(self.shard.hash(key), key)
176	0	}
177
178		/// Peeks an item from the cache. Contrary to gets, peeks don't alter the key "hotness".
179		///
180		/// Note: Leaking the returned RefMut might cause cache weight tracking to be inaccurate.
181	0	pub fn peek_mut<Q>(&mut self, key: &Q) -> Option<RefMut<'_, Key, Val, We, B, L>>
182	0	where
183	0	Q: Hash + Equivalent<Key> + ?Sized,
184		{
185	0	self.shard.peek_mut(self.shard.hash(key), key).map(RefMut)
186	0	}
187
188		/// Remove an item from the cache whose key is `key`.
189		/// Returns the removed entry, if any.
190	0	pub fn remove<Q>(&mut self, key: &Q) -> Option<(Key, Val)>
191	0	where
192	0	Q: Hash + Equivalent<Key> + ?Sized,
193		{
194	0	self.shard.remove(self.shard.hash(key), key)
195	0	}
196
197		/// Remove an item from the cache whose key is `key` if `f(&value)` returns `true` for that entry.
198		/// Compared to peek and remove, this method is more efficient as it requires only 1 lookup.
199		///
200		/// Returns the removed entry, if any.
201	0	pub fn remove_if<Q, F>(&mut self, key: &Q, f: F) -> Option<(Key, Val)>
202	0	where
203	0	Q: Hash + Equivalent<Key> + ?Sized,
204	0	F: FnOnce(&Val) -> bool,
205		{
206	0	self.shard.remove_if(self.shard.hash(key), key, f)
207	0	}
208
209		/// Replaces an item in the cache, but only if it already exists.
210		/// If `soft` is set, the replace operation won't affect the "hotness" of the key,
211		/// even if the value is replaced.
212		///
213		/// Returns `Ok` if the entry was admitted and `Err(_)` if it wasn't.
214	0	pub fn replace(&mut self, key: Key, value: Val, soft: bool) -> Result<(), (Key, Val)> {
215	0	let lcs = self.replace_with_lifecycle(key, value, soft)?;
216	0	self.shard.lifecycle.end_request(lcs);
217	0	Ok(())
218	0	}
219
220		/// Replaces an item in the cache, but only if it already exists.
221		/// If `soft` is set, the replace operation won't affect the "hotness" of the key,
222		/// even if the value is replaced.
223		///
224		/// Returns `Ok` if the entry was admitted and `Err(_)` if it wasn't.
225	0	pub fn replace_with_lifecycle(
226	0	&mut self,
227	0	key: Key,
228	0	value: Val,
229	0	soft: bool,
230	0	) -> Result<L::RequestState, (Key, Val)> {
231	0	let mut lcs = self.shard.lifecycle.begin_request();
232	0	self.shard.insert(
233	0	&mut lcs,
234	0	self.shard.hash(&key),
235	0	key,
236	0	value,
237	0	InsertStrategy::Replace { soft },
238	0	)?;
239	0	Ok(lcs)
240	0	}
241
242		/// Retains only the items specified by the predicate.
243		/// In other words, remove all items for which `f(&key, &value)` returns `false`. The
244		/// elements are visited in arbitrary order.
245	0	pub fn retain<F>(&mut self, f: F)
246	0	where
247	0	F: Fn(&Key, &Val) -> bool,
248		{
249	0	self.shard.retain(f);
250	0	}
251
252		/// Gets or inserts an item in the cache with key `key`.
253		/// Returns a reference to the inserted `value` if it was admitted to the cache.
254		///
255		/// See also `get_ref_or_guard`.
256	0	pub fn get_or_insert_with<Q, E>(
257	0	&mut self,
258	0	key: &Q,
259	0	with: impl FnOnce() -> Result<Val, E>,
260	0	) -> Result<Option<&Val>, E>
261	0	where
262	0	Q: Hash + Equivalent<Key> + ToOwned<Owned = Key> + ?Sized,
263		{
264	0	let idx = match self.shard.upsert_placeholder(self.shard.hash(key), key) {
265	0	Ok((idx, _)) => idx,
266	0	Err((plh, _)) => {
267	0	let v = with()?;
268	0	let mut lcs = self.shard.lifecycle.begin_request();
269	0	let replaced = self.shard.replace_placeholder(&mut lcs, &plh, false, v);
270	0	self.shard.lifecycle.end_request(lcs);
271	0	debug_assert!(replaced.is_ok(), "unsync replace_placeholder can't fail");
272	0	plh.idx
273		}
274		};
275	0	Ok(self.shard.peek_token(idx))
276	0	}
277
278		/// Gets or inserts an item in the cache with key `key`.
279		/// Returns a mutable reference to the inserted `value` if it was admitted to the cache.
280		///
281		/// See also `get_mut_or_guard`.
282	0	pub fn get_mut_or_insert_with<'a, Q, E>(
283	0	&'a mut self,
284	0	key: &Q,
285	0	with: impl FnOnce() -> Result<Val, E>,
286	0	) -> Result<Option<RefMut<'a, Key, Val, We, B, L>>, E>
287	0	where
288	0	Q: Hash + Equivalent<Key> + ToOwned<Owned = Key> + ?Sized,
289		{
290	0	let idx = match self.shard.upsert_placeholder(self.shard.hash(key), key) {
291	0	Ok((idx, _)) => idx,
292	0	Err((plh, _)) => {
293	0	let v = with()?;
294	0	let mut lcs = self.shard.lifecycle.begin_request();
295	0	let replaced = self.shard.replace_placeholder(&mut lcs, &plh, false, v);
296	0	debug_assert!(replaced.is_ok(), "unsync replace_placeholder can't fail");
297	0	self.shard.lifecycle.end_request(lcs);
298	0	plh.idx
299		}
300		};
301	0	Ok(self.shard.peek_token_mut(idx).map(RefMut))
302	0	}
303
304		/// Gets an item from the cache with key `key` .
305		/// If the corresponding value isn't present in the cache, this functions returns a guard
306		/// that can be used to insert the value once it's computed.
307	0	pub fn get_ref_or_guard<Q>(&mut self, key: &Q) -> Result<&Val, Guard<'_, Key, Val, We, B, L>>
308	0	where
309	0	Q: Hash + Equivalent<Key> + ToOwned<Owned = Key> + ?Sized,
310		{
311		// TODO: this could be using a simpler entry API
312	0	match self.shard.upsert_placeholder(self.shard.hash(key), key) {
313	0	Ok((_, v)) => unsafe {
314		// Rustc gets insanely confused about returning from mut borrows
315		// Safety: v has the same lifetime as self
316	0	let v: *const Val = v;
317	0	Ok(&*v)
318		},
319	0	Err((placeholder, _)) => Err(Guard {
320	0	cache: self,
321	0	placeholder,
322	0	inserted: false,
323	0	}),
324		}
325	0	}
326
327		/// Gets an item from the cache with key `key` .
328		/// If the corresponding value isn't present in the cache, this functions returns a guard
329		/// that can be used to insert the value once it's computed.
330		///
331		/// Note: Leaking the returned RefMut might cause cache weight tracking to be inaccurate.
332	0	pub fn get_mut_or_guard<'a, Q>(
333	0	&'a mut self,
334	0	key: &Q,
335	0	) -> Result<Option<RefMut<'a, Key, Val, We, B, L>>, Guard<'a, Key, Val, We, B, L>>
336	0	where
337	0	Q: Hash + Equivalent<Key> + ToOwned<Owned = Key> + ?Sized,
338		{
339		// TODO: this could be using a simpler entry API
340	0	match self.shard.upsert_placeholder(self.shard.hash(key), key) {
341	0	Ok((idx, _)) => Ok(self.shard.peek_token_mut(idx).map(RefMut)),
342	0	Err((placeholder, _)) => Err(Guard {
343	0	cache: self,
344	0	placeholder,
345	0	inserted: false,
346	0	}),
347		}
348	0	}
349
350		/// Inserts an item in the cache with key `key`.
351	0	pub fn insert(&mut self, key: Key, value: Val) {
352	0	let lcs = self.insert_with_lifecycle(key, value);
353	0	self.shard.lifecycle.end_request(lcs);
354	0	}
355
356		/// Inserts an item in the cache with key `key`.
357	0	pub fn insert_with_lifecycle(&mut self, key: Key, value: Val) -> L::RequestState {
358	0	let mut lcs = self.shard.lifecycle.begin_request();
359	0	let result = self.shard.insert(
360	0	&mut lcs,
361	0	self.shard.hash(&key),
362	0	key,
363	0	value,
364	0	InsertStrategy::Insert,
365		);
366		// result cannot err with the Insert strategy
367	0	debug_assert!(result.is_ok());
368	0	lcs
369	0	}
370
371		/// Clear all items from the cache
372	0	pub fn clear(&mut self) {
373	0	self.shard.clear();
374	0	}
375
376		/// Iterator for the items in the cache
377	0	pub fn iter(&self) -> impl Iterator<Item = (&'_ Key, &'_ Val)> + '_ {
378		// TODO: add a concrete type, impl trait in the public api is really bad.
379	0	self.shard.iter()
380	0	}
381
382		/// Drain all items from the cache
383		///
384		/// The cache will be emptied even if the returned iterator isn't fully consumed.
385	0	pub fn drain(&mut self) -> impl Iterator<Item = (Key, Val)> + '_ {
386		// TODO: add a concrete type, impl trait in the public api is really bad.
387	0	self.shard.drain()
388	0	}
389
390		/// Sets the cache to a new weight capacity.
391		///
392		/// If the new capacity is smaller than the current weight, items will be evicted
393		/// to bring the cache within the new limit.
394	0	pub fn set_capacity(&mut self, new_weight_capacity: u64) {
395	0	self.shard.set_capacity(new_weight_capacity);
396	0	}
397
398		#[cfg(any(fuzzing, test))]
399	0	pub fn validate(&self, accept_overweight: bool) {
400	0	self.shard.validate(accept_overweight);
401	0	}
402
403		/// Get total memory used by cache data structures
404		///
405		/// It should be noted that if cache key or value is some type like `Vec<T>`,
406		/// the memory allocated in the heap will not be counted.
407	0	pub fn memory_used(&self) -> MemoryUsed {
408	0	self.shard.memory_used()
409	0	}
410		}
411
412		impl<Key, Val, We, B, L> std::fmt::Debug for Cache<Key, Val, We, B, L> {
413	0	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
414	0	f.debug_struct("Cache").finish_non_exhaustive()
415	0	}
416		}
417
418		/// Default `Lifecycle` for the unsync cache.
419		pub struct DefaultLifecycle<Key, Val>(std::marker::PhantomData<(Key, Val)>);
420
421		impl<Key, Val> std::fmt::Debug for DefaultLifecycle<Key, Val> {
422	0	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
423	0	f.debug_tuple("DefaultLifecycle").finish()
424	0	}
425		}
426
427		impl<Key, Val> Default for DefaultLifecycle<Key, Val> {
428		#[inline]
429	0	fn default() -> Self {
430	0	Self(Default::default())
431	0	}
432		}
433
434		impl<Key, Val> Clone for DefaultLifecycle<Key, Val> {
435		#[inline]
436	0	fn clone(&self) -> Self {
437	0	Self(Default::default())
438	0	}
439		}
440
441		impl<Key, Val> Lifecycle<Key, Val> for DefaultLifecycle<Key, Val> {
442		type RequestState = ();
443
444		#[inline]
445	0	fn begin_request(&self) -> Self::RequestState {}
446
447		#[inline]
448	0	fn on_evict(&self, _state: &mut Self::RequestState, _key: Key, _val: Val) {}
449		}
450
451		#[derive(Debug, Clone)]
452		pub(crate) struct SharedPlaceholder {
453		hash: u64,
454		idx: Token,
455		}
456
457		pub struct Guard<'a, Key, Val, We, B, L> {
458		cache: &'a mut Cache<Key, Val, We, B, L>,
459		placeholder: SharedPlaceholder,
460		inserted: bool,
461		}
462
463		impl<Key: Eq + Hash, Val, We: Weighter<Key, Val>, B: BuildHasher, L: Lifecycle<Key, Val>>
464		Guard<'_, Key, Val, We, B, L>
465		{
466		/// Inserts the value into the placeholder
467	0	pub fn insert(self, value: Val) {
468	0	self.insert_internal(value, false);
469	0	}
470
471		/// Inserts the value into the placeholder
472	0	pub fn insert_with_lifecycle(self, value: Val) -> L::RequestState {
473	0	self.insert_internal(value, true).unwrap()
474	0	}
475
476		#[inline]
477	0	fn insert_internal(mut self, value: Val, return_lcs: bool) -> Option<L::RequestState> {
478	0	let mut lcs = self.cache.shard.lifecycle.begin_request();
479	0	let replaced =
480	0	self.cache
481	0	.shard
482	0	.replace_placeholder(&mut lcs, &self.placeholder, false, value);
483	0	debug_assert!(replaced.is_ok(), "unsync replace_placeholder can't fail");
484	0	self.inserted = true;
485	0	if return_lcs {
486	0	Some(lcs)
487		} else {
488	0	self.cache.shard.lifecycle.end_request(lcs);
489	0	None
490		}
491	0	}
492		}
493
494		impl<Key, Val, We, B, L> Drop for Guard<'_, Key, Val, We, B, L> {
495		#[inline]
496	0	fn drop(&mut self) {
497		#[cold]
498	0	fn drop_slow<Key, Val, We, B, L>(this: &mut Guard<'_, Key, Val, We, B, L>) {
499	0	this.cache.shard.remove_placeholder(&this.placeholder);
500	0	}
501	0	if !self.inserted {
502	0	drop_slow(self);
503	0	}
504	0	}
505		}
506
507		pub struct RefMut<'cache, Key, Val, We: Weighter<Key, Val>, B, L>(
508		crate::shard::RefMut<'cache, Key, Val, We, B, L, SharedPlaceholder>,
509		);
510
511		impl<Key, Val, We: Weighter<Key, Val>, B, L> std::ops::Deref for RefMut<'_, Key, Val, We, B, L> {
512		type Target = Val;
513
514		#[inline]
515	0	fn deref(&self) -> &Self::Target {
516	0	self.0.pair().1
517	0	}
518		}
519
520		impl<Key, Val, We: Weighter<Key, Val>, B, L> std::ops::DerefMut for RefMut<'_, Key, Val, We, B, L> {
521		#[inline]
522	0	fn deref_mut(&mut self) -> &mut Self::Target {
523	0	self.0.value_mut()
524	0	}
525		}
526
527		impl shard::SharedPlaceholder for SharedPlaceholder {
528		#[inline]
529	0	fn new(hash: u64, idx: Token) -> Self {
530	0	Self { hash, idx }
531	0	}
532
533		#[inline]
534	0	fn same_as(&self, _other: &Self) -> bool {
535	0	true
536	0	}
537
538		#[inline]
539	0	fn hash(&self) -> u64 {
540	0	self.hash
541	0	}
542
543		#[inline]
544	0	fn idx(&self) -> Token {
545	0	self.idx
546	0	}
547		}
548
549		#[cfg(test)]
550		mod tests {
551		use super::*;
552
553		struct Weighter;
554
555		impl crate::Weighter<u32, u32> for Weighter {
556		fn weight(&self, _key: &u32, val: &u32) -> u64 {
557		*val as u64
558		}
559		}
560
561		#[test]
562		fn test_zero_weights() {
563		let mut cache = Cache::with_weighter(100, 100, Weighter);
564		cache.insert(0, 0);
565		assert_eq!(cache.weight(), 0);
566		for i in 1..100 {
567		cache.insert(i, i);
568		cache.insert(i, i);
569		}
570		assert_eq!(cache.get(&0).copied(), Some(0));
571		assert!(cache.contains_key(&0));
572		let a = cache.weight();
573		*cache.get_mut(&0).unwrap() += 1;
574		assert_eq!(cache.weight(), a + 1);
575		for i in 1..100 {
576		cache.insert(i, i);
577		cache.insert(i, i);
578		}
579		assert_eq!(cache.get(&0), None);
580		assert!(!cache.contains_key(&0));
581
582		cache.insert(0, 1);
583		let a = cache.weight();
584		*cache.get_mut(&0).unwrap() -= 1;
585		assert_eq!(cache.weight(), a - 1);
586		for i in 1..100 {
587		cache.insert(i, i);
588		cache.insert(i, i);
589		}
590		assert_eq!(cache.get(&0).copied(), Some(0));
591		assert!(cache.contains_key(&0));
592		}
593
594		#[test]
595		fn test_set_capacity() {
596		let mut cache = Cache::new(100);
597		for i in 0..80 {
598		cache.insert(i, i);
599		}
600		let initial_len = cache.len();
601		assert!(initial_len <= 80);
602
603		// Set to smaller capacity
604		cache.set_capacity(50);
605		assert!(cache.len() <= 50);
606		assert!(cache.weight() <= 50);
607		cache.validate(false);
608
609		// Set to larger capacity
610		cache.set_capacity(200);
611		assert_eq!(cache.capacity(), 200);
612		cache.validate(false);
613
614		// Insert more items
615		for i in 100..180 {
616		cache.insert(i, i);
617		}
618		assert!(cache.len() <= 180);
619		assert!(cache.weight() <= 200);
620		cache.validate(false);
621		}
622
623		#[test]
624		fn test_set_capacity_with_ghosts() {
625		// Create a cache that will generate ghost entries
626		let mut cache = Cache::new(50);
627
628		// Insert items to fill the cache
629		for i in 0..100 {
630		cache.insert(i, i);
631		}
632		cache.validate(false);
633
634		// Set to smaller capacity - should trim both resident and ghost entries
635		cache.set_capacity(25);
636		assert!(cache.weight() <= 25);
637		cache.validate(false);
638
639		// Set back to larger capacity
640		cache.set_capacity(100);
641		assert_eq!(cache.capacity(), 100);
642		cache.validate(false);
643
644		// Insert more items
645		for i in 100..150 {
646		cache.insert(i, i);
647		}
648		cache.validate(false);
649		}
650
651		#[test]
652		fn test_remove_if() {
653		let mut cache = Cache::new(100);
654
655		// Insert test data
656		cache.insert(1, 10);
657		cache.insert(2, 20);
658		cache.insert(3, 30);
659
660		// Test removing with predicate that returns true
661		let removed = cache.remove_if(&2, \|v\| *v == 20);
662		assert_eq!(removed, Some((2, 20)));
663		assert_eq!(cache.get(&2), None);
664
665		// Test removing with predicate that returns false
666		let not_removed = cache.remove_if(&3, \|v\| *v == 999);
667		assert_eq!(not_removed, None);
668		assert_eq!(cache.get(&3), Some(&30));
669
670		// Test removing non-existent key
671		let not_found = cache.remove_if(&999, \|_\| true);
672		assert_eq!(not_found, None);
673
674		cache.validate(false);
675		}
676		}