quick_cache/

lib.rs

//! Lightweight, high performance concurrent cache. It allows very fast access to the cached items
//! with little overhead compared to a plain concurrent hash table. No allocations are ever performed
//! unless the cache internal state table needs growing (which will eventually stabilize).
//!
//! # Eviction policy
//!
//! The current eviction policy is a modified version of the Clock-PRO algorithm, very similar to the
//! later published S3-FIFO algorithm. It's "scan resistent" and provides high hit rates,
//! significantly better than a LRU eviction policy and comparable to other state-of-the art algorithms
//! like W-TinyLFU.
//!
//! # Thread safety and Concurrency
//!
//! Both `sync` (thread-safe) and `unsync` (non thread-safe) implementations are provided. The latter
//! offers slightly better performance when thread safety is not required.
//!
//! # Equivalent keys
//!
//! The cache uses the [`Equivalent`](https://docs.rs/equivalent/1.0.1/equivalent/trait.Equivalent.html) trait
//! for gets/removals. It can help work around the `Borrow` limitations.
//! For example, if the cache key is a tuple `(K, Q)`, you wouldn't be able to access such keys without
//! building a `&(K, Q)` and thus potentially cloning `K` and/or `Q`.
//!
//! # User defined weight
//!
//! By implementing the [Weighter] trait the user can define different weights for each cache entry.
//!
//! # Atomic operations
//!
//! By using the `get_or_insert` or `get_value_or_guard` family of functions (both sync and async variants
//! are available, they can be mix and matched) the user can coordinate the insertion of entries, so only
//! one value is "computed" and inserted after a cache miss.
//!
//! The `entry` family of functions provide a closure-based API for atomically
//! inspecting and acting on existing entries (keep, remove, or replace) while also coordinating
//! insertion on cache misses.
//!
//! # Lifecycle hooks
//!
//! A user can optionally provide a custom [Lifecycle] implementation to hook into the lifecycle of cache entries.
//!
//! Example use cases:
//! * item pinning, so even if the item occupies weight but isn't allowed to be evicted
//! * send evicted items to a channel, achieving the equivalent to an eviction listener feature.
//! * zero out item weights so they are left in the cache instead of evicted.
//!
//! # Approximate memory usage
//!
//! The memory overhead per entry is `21` bytes.
//!
//! The memory usage of the cache data structures can be estimated as:
//! `(size_of::<K>() + size_of::<V>() + 21) * (length * 1.5).next_power_of_two()`
//!
//! Actual memory usage may vary depending on the cache options and the key and value types, which can have external
//! allocations (e.g. `String`, `Vec`, etc.). The above formula only accounts for the cache's data structures.
//!
//! The `1.5` value in the formula above results from `1 + G`, where `G` is the configured ghost allocation specified
//! in [`OptionsBuilder::ghost_allocation`], which is `0.5` by default.
//!
//! # Hasher
//!
//! By default the crate uses a fast non-cryptographic hasher (currently [foldhash](https://crates.io/crates/foldhash))
//! exposed through the opaque [`DefaultHashBuilder`] type and enabled via the `custom-hasher` feature (on by
//! default). The concrete algorithm is an implementation detail and may change between releases. If the
//! `custom-hasher` feature is disabled the crate falls back to the std lib implementation instead (currently
//! Siphash13). Note that a custom hasher can also be provided via the cache's `B` type parameter if desirable.
//!
//! # Synchronization primitives
//!
//! By default the crate uses [parking_lot](https://crates.io/crates/parking_lot), which is enabled (by default) via
//! a crate feature with the same name. If `parking_lot` is disabled and `sharded-lock` is enabled, the crate uses
//! [`crossbeam_utils::sync::ShardedLock`](https://docs.rs/crossbeam-utils/latest/crossbeam_utils/sync/struct.ShardedLock.html)
//! from [crossbeam-utils](https://crates.io/crates/crossbeam-utils) instead. If both are disabled the crate defaults
//! to the std lib implementation. The `parking_lot` and `sharded-lock` features are mutually exclusive.
//!
//! # Cargo Features
//!
//! | Feature | Default | Description |
//! |---------|---------|-------------|
//! | `custom-hasher` | ✓ | Use the crate's bundled fast non-cryptographic default hasher (currently [foldhash](https://crates.io/crates/foldhash)) behind the opaque [`DefaultHashBuilder`]. When disabled, falls back to std lib's `RandomState` (currently SipHash-1-3). |
//! | `parking_lot` | ✓ | Use [parking_lot](https://crates.io/crates/parking_lot) for synchronization primitives. Mutually exclusive with `sharded-lock`. |
//! | `sharded-lock` | | Use [`crossbeam_utils::sync::ShardedLock`](https://docs.rs/crossbeam-utils/latest/crossbeam_utils/sync/struct.ShardedLock.html) for synchronization primitives. Mutually exclusive with `parking_lot`. |
//! | `shuttle` | | Enable [shuttle](https://crates.io/crates/shuttle) testing support for concurrency testing. |
//! | `stats` | | Enable cache statistics tracking via the `hits()`, `misses()`, and per-item `item_stats()` methods. Overhead: adds an 8-byte per-item access counter (`AtomicU64`) to each resident item — raising per-entry memory by up to 8 bytes, depending on layout — and performs two atomic increments per cache hit and one per miss. |
#![allow(clippy::type_complexity)]
#![cfg_attr(docsrs, feature(doc_cfg))]

#[cfg(all(feature = "parking_lot", feature = "sharded-lock"))]
compile_error!("features `parking_lot` and `sharded-lock` are mutually exclusive");

#[cfg(not(fuzzing))]
mod linked_slab;
#[cfg(fuzzing)]
pub mod linked_slab;
mod options;
#[cfg(not(feature = "shuttle"))]
mod rw_lock;
mod shard;
mod shim;
/// Concurrent cache variants that can be used from multiple threads.
pub mod sync;
mod sync_placeholder;
/// Non-concurrent cache variants.
pub mod unsync;
pub use equivalent::Equivalent;

#[cfg(all(test, feature = "shuttle"))]
mod shuttle_tests;

pub use options::{Options, OptionsBuilder};

#[cfg(feature = "custom-hasher")]
type DefaultHasherImpl = foldhash::quality::RandomState;
#[cfg(not(feature = "custom-hasher"))]
type DefaultHasherImpl = std::collections::hash_map::RandomState;

/// The default [`BuildHasher`](std::hash::BuildHasher) used by the cache.
///
/// The hashing algorithm behind this type is an implementation detail and may
/// change in any release. Name this type — don't rely on the concrete hasher
/// it wraps. The underlying hasher is selected by the `custom-hasher` feature
/// (a fast non-cryptographic hasher when enabled, the std library's
/// `RandomState` otherwise).
#[derive(Clone, Default)]
pub struct DefaultHashBuilder(DefaultHasherImpl);

impl std::hash::BuildHasher for DefaultHashBuilder {
    type Hasher = <DefaultHasherImpl as std::hash::BuildHasher>::Hasher;

    #[inline]
    fn build_hasher(&self) -> Self::Hasher {
        self.0.build_hasher()
    }
}

impl std::fmt::Debug for DefaultHashBuilder {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("DefaultHashBuilder").finish_non_exhaustive()
    }
}

/// Defines the weight of a cache entry.
///
/// # Example
///
/// ```
/// use quick_cache::{sync::Cache, Weighter};
///
/// #[derive(Clone)]
/// struct StringWeighter;
///
/// impl Weighter<u64, String> for StringWeighter {
///     fn weight(&self, _key: &u64, val: &String) -> u64 {
///         // Be cautious about zero weights!
///         val.len() as u64
///     }
/// }
///
/// let cache = Cache::with_weighter(100, 100_000, StringWeighter);
/// cache.insert(1, "1".to_string());
/// ```
pub trait Weighter<Key, Val> {
    /// Returns the weight of the cache item.
    ///
    /// For performance reasons, this function should be trivially cheap as
    /// it's called during the cache eviction routine.
    /// If weight is expensive to calculate, consider caching it alongside the value.
    ///
    /// Zero (0) weight items are allowed and will be ignored when looking for eviction
    /// candidates. Such items can only be manually removed or overwritten.
    ///
    /// Note that it's undefined behavior for a cache item to change its weight.
    /// The only exception to this is when Lifecycle::before_evict is called.
    ///
    /// It's also undefined behavior in release mode if the summing of weights overflows,
    /// although this is unlikely to be a problem in practice.
    fn weight(&self, key: &Key, val: &Val) -> u64;
}

/// Each cache entry weights exactly `1` unit of weight.
#[derive(Debug, Clone, Default)]
pub struct UnitWeighter;

impl<Key, Val> Weighter<Key, Val> for UnitWeighter {
    #[inline]
    fn weight(&self, _key: &Key, _val: &Val) -> u64 {
        1
    }
}

/// Hooks into the lifetime of the cache items.
///
/// The functions should be small and very fast, otherwise the cache performance might be negatively affected.
///
/// # Request state
///
/// Operations that may evict items thread a [`RequestState`](Lifecycle::RequestState)
/// through the eviction hooks. It is a per-request accumulator: the cache constructs a
/// fresh one via [`Default`], the `on_evict*`/`before_evict` hooks record into it, and it
/// is finalized by its own [`Drop`] (which, for example, releases evicted items _after_
/// the shard lock is dropped).
///
/// The `_with_lifecycle` cache methods take `&mut RequestState`, letting a caller drive
/// several operations against a single state — e.g. to batch the eviction work or inspect
/// evicted items before dropping it:
///
/// ```ignore
/// let mut lcs = Default::default();
/// cache.insert_with_lifecycle(k1, v1, &mut lcs);
/// cache.insert_with_lifecycle(k2, v2, &mut lcs);
/// // inspect `lcs` here if desired; evicted items are released when it drops
/// ```
pub trait Lifecycle<Key, Val> {
    /// Per-request accumulator threaded through the eviction hooks.
    ///
    /// Constructed via [`Default`] at the start of each request and finalized by its
    /// [`Drop`]. Keep it cheap to create and drop.
    type RequestState: Default;

    /// Returns whether the item is pinned. Items that are pinned can't be evicted.
    /// Note that a pinned item can still be replaced with get_mut, insert, replace and similar APIs.
    ///
    /// Compared to zero (0) weight items, pinned items still consume (non-zero) weight even if they can't
    /// be evicted. Furthermore, zero (0) weight items are separated from the other entries, which allows
    /// having a large number of them without impacting performance, but moving them in/out or the evictable
    /// section has a small cost. Pinning on the other hand doesn't separate entries, so during eviction
    /// the cache may visit pinned entries but will ignore them.
    #[allow(unused_variables)]
    #[inline]
    fn is_pinned(&self, key: &Key, val: &Val) -> bool {
        false
    }

    /// Called when a cache item is about to be evicted.
    /// Note that value replacement (e.g. insertions for the same key) won't call this method.
    ///
    /// This is the only time the item can change its weight. If the item weight becomes zero (0) it
    /// will be left in the cache, otherwise it'll still be removed. Zero (0) weight items aren't evictable
    /// and are kept separated from the other items so it's possible to have a large number of them without
    /// negatively affecting eviction performance.
    #[allow(unused_variables)]
    #[inline]
    fn before_evict(&self, state: &mut Self::RequestState, key: &Key, val: &mut Val) {}

    /// Called when an item is evicted.
    ///
    /// To distinguish evictions from the hot vs cold queues, override
    /// [`Lifecycle::on_evict_hot`] and/or [`Lifecycle::on_evict_cold`] instead;
    /// they default to delegating here.
    ///
    /// If none of `on_evict`, `on_evict_hot`, or `on_evict_cold` is overridden,
    /// eviction notifications are silently dropped.
    ///
    /// Note: items that are rejected without ever being admitted to the cache
    /// (oversized inserts and oversized placeholder values) are routed through
    /// [`Lifecycle::on_evict_cold`], which by default reaches this method.
    #[allow(unused_variables)]
    #[inline]
    fn on_evict(&self, state: &mut Self::RequestState, key: Key, val: Val) {}

    /// Called when an item is evicted from the cold queue.
    ///
    /// By default delegates to [`Lifecycle::on_evict`].
    ///
    /// Note: items that are rejected without ever being admitted to the cache
    /// (oversized inserts and oversized placeholder values) are also reported
    /// via this method.
    #[inline]
    fn on_evict_cold(&self, state: &mut Self::RequestState, key: Key, val: Val) {
        self.on_evict(state, key, val)
    }

    /// Called when an item is evicted from the hot queue.
    ///
    /// By default delegates to [`Lifecycle::on_evict`].
    ///
    /// Note: rejected (never-admitted) items are reported via
    /// [`Lifecycle::on_evict_cold`], not this method.
    #[inline]
    fn on_evict_hot(&self, state: &mut Self::RequestState, key: Key, val: Val) {
        self.on_evict(state, key, val)
    }
}

/// The memory used by the cache
///
/// This struct exposes some implementation details, may change in the future
#[non_exhaustive]
#[derive(Debug, Copy, Clone)]
pub struct MemoryUsed {
    pub entries: usize,
    pub map: usize,
}

impl MemoryUsed {
    pub fn total(&self) -> usize {
        self.entries + self.map
    }
}

/// Per-item statistics returned by `item_stats`.
///
/// Only available with the `stats` feature enabled. Enabling that feature adds an
/// 8-byte per-item access counter to each resident item (raising per-entry memory
/// by up to 8 bytes, depending on layout) and performs two atomic increments per
/// cache hit and one per miss.
#[cfg(feature = "stats")]
#[non_exhaustive]
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub struct ItemStats {
    /// Number of times the item has been accessed (read) since it became resident.
    ///
    /// Incremented on every cache hit (`get`/`get_mut`/`get_value_or_guard`/`entry`).
    /// Unlike the internal eviction counter, this is monotonic per residency and is
    /// not bounded by the eviction policy. It resets to zero if the slot is reused for
    /// a new value (e.g. after eviction and re-insertion).
    pub access_count: u64,
}

#[cfg(test)]
mod tests {
    use std::{
        hash::Hash,
        sync::{atomic::AtomicUsize, Arc},
        time::Duration,
    };

    use super::*;
    #[derive(Clone)]
    struct StringWeighter;

    impl Weighter<u64, String> for StringWeighter {
        fn weight(&self, _key: &u64, val: &String) -> u64 {
            val.len() as u64
        }
    }

    #[test]
    fn test_new() {
        sync::Cache::<(u64, u64), u64>::new(0);
        sync::Cache::<(u64, u64), u64>::new(1);
        sync::Cache::<(u64, u64), u64>::new(2);
        sync::Cache::<(u64, u64), u64>::new(3);
        sync::Cache::<(u64, u64), u64>::new(usize::MAX);
        sync::Cache::<u64, u64>::new(0);
        sync::Cache::<u64, u64>::new(1);
        sync::Cache::<u64, u64>::new(2);
        sync::Cache::<u64, u64>::new(3);
        sync::Cache::<u64, u64>::new(usize::MAX);
    }

    #[test]
    fn test_capacity_one() {
        // Sync cache with capacity 1 should be able to hold one item
        let cache = sync::Cache::<u64, u64>::new(1);
        cache.insert(1, 10);
        assert_eq!(cache.get(&1), Some(10));
        // Inserting a second key should evict the first
        cache.insert(2, 20);
        assert_eq!(cache.get(&2), Some(20));
        assert_eq!(cache.get(&1), None);

        // Unsync cache with capacity 1 should also work
        let mut cache = unsync::Cache::<u64, u64>::new(1);
        cache.insert(1, 10);
        assert_eq!(cache.get(&1), Some(&10));
        cache.insert(2, 20);
        assert_eq!(cache.get(&2), Some(&20));
        assert_eq!(cache.get(&1), None);

        // Capacity 0 should store nothing
        let cache = sync::Cache::<u64, u64>::new(0);
        cache.insert(1, 10);
        assert_eq!(cache.get(&1), None);
    }

    #[test]
    fn test_custom_cost() {
        let cache = sync::Cache::with_weighter(100, 100_000, StringWeighter);
        cache.insert(1, "1".to_string());
        cache.insert(54, "54".to_string());
        cache.insert(1000, "1000".to_string());
        assert_eq!(cache.get(&1000).unwrap(), "1000");
    }

    #[test]
    fn test_change_get_mut_change_weight() {
        let mut cache = unsync::Cache::with_weighter(100, 100_000, StringWeighter);
        cache.insert(1, "1".to_string());
        assert_eq!(cache.get(&1).unwrap(), "1");
        assert_eq!(cache.weight(), 1);
        let _old = {
            cache
                .get_mut(&1)
                .map(|mut v| std::mem::replace(&mut *v, "11".to_string()))
        };
        let _old = {
            cache
                .get_mut(&1)
                .map(|mut v| std::mem::replace(&mut *v, "".to_string()))
        };
        assert_eq!(cache.get(&1).unwrap(), "");
        assert_eq!(cache.weight(), 0);
        cache.validate(false);
    }

    #[derive(Debug, Hash)]
    pub struct Pair<A, B>(pub A, pub B);

    impl<A, B, C, D> PartialEq<(A, B)> for Pair<C, D>
    where
        C: PartialEq<A>,
        D: PartialEq<B>,
    {
        fn eq(&self, rhs: &(A, B)) -> bool {
            self.0 == rhs.0 && self.1 == rhs.1
        }
    }

    impl<A, B, X> Equivalent<X> for Pair<A, B>
    where
        Pair<A, B>: PartialEq<X>,
        A: Hash + Eq,
        B: Hash + Eq,
    {
        fn equivalent(&self, other: &X) -> bool {
            *self == *other
        }
    }

    #[test]
    fn test_equivalent() {
        let mut cache = unsync::Cache::new(5);
        cache.insert(("square".to_string(), 2022), "blue".to_string());
        cache.insert(("square".to_string(), 2023), "black".to_string());
        assert_eq!(cache.get(&Pair("square", 2022)).unwrap(), "blue");
    }

    #[test]
    fn test_borrow_keys() {
        let cache = sync::Cache::<(Vec<u8>, Vec<u8>), u64>::new(0);
        cache.get(&Pair(&b""[..], &b""[..]));
        let cache = sync::Cache::<(String, String), u64>::new(0);
        cache.get(&Pair("", ""));
    }

    #[test]
    #[cfg_attr(miri, ignore)]
    fn test_get_or_insert() {
        use rand::prelude::*;
        for _i in 0..2000 {
            dbg!(_i);
            let mut entered = AtomicUsize::default();
            let cache = sync::Cache::<(u64, u64), u64>::new(100);
            const THREADS: usize = 100;
            let wg = std::sync::Barrier::new(THREADS);
            let solve_at = rand::rng().random_range(0..THREADS);
            std::thread::scope(|s| {
                for _ in 0..THREADS {
                    s.spawn(|| {
                        wg.wait();
                        let result = cache.get_or_insert_with(&(1, 1), || {
                            let before = entered.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
                            if before == solve_at {
                                Ok(1)
                            } else {
                                Err(())
                            }
                        });
                        assert!(matches!(result, Ok(1) | Err(())));
                    });
                }
            });
            assert_eq!(*entered.get_mut(), solve_at + 1);
        }
    }

    #[test]
    fn test_get_or_insert_unsync() {
        let mut cache = unsync::Cache::<u64, u64>::new(100);
        let guard = cache.get_ref_or_guard(&0).unwrap_err();
        guard.insert(0);
        assert_eq!(cache.get_ref_or_guard(&0).ok().copied(), Some(0));
        let guard = cache.get_mut_or_guard(&1).err().unwrap();
        guard.insert(1);
        let v = *cache.get_mut_or_guard(&1).ok().unwrap().unwrap();
        assert_eq!(v, 1);
        let result = cache.get_or_insert_with::<_, ()>(&0, || panic!());
        assert_eq!(result, Ok(Some(&0)));
        let result = cache.get_or_insert_with::<_, ()>(&1, || panic!());
        assert_eq!(result, Ok(Some(&1)));
        let result = cache.get_or_insert_with::<_, ()>(&3, || Ok(3));
        assert_eq!(result, Ok(Some(&3)));
        let result = cache.get_or_insert_with::<_, ()>(&4, || Err(()));
        assert_eq!(result, Err(()));
    }

    #[tokio::test]
    async fn test_get_or_insert_sync() {
        use crate::sync::*;
        let cache = sync::Cache::<u64, u64>::new(100);
        let GuardResult::Guard(guard) = cache.get_value_or_guard(&0, None) else {
            panic!();
        };
        guard.insert(0).unwrap();
        let GuardResult::Value(v) = cache.get_value_or_guard(&0, None) else {
            panic!();
        };
        assert_eq!(v, 0);
        let Err(guard) = cache.get_value_or_guard_async(&1).await else {
            panic!();
        };
        guard.insert(1).unwrap();
        let Ok(v) = cache.get_value_or_guard_async(&1).await else {
            panic!();
        };
        assert_eq!(v, 1);

        let result = cache.get_or_insert_with::<_, ()>(&0, || panic!());
        assert_eq!(result, Ok(0));
        let result = cache.get_or_insert_with::<_, ()>(&3, || Ok(3));
        assert_eq!(result, Ok(3));
        let result = cache.get_or_insert_with::<_, ()>(&4, || Err(()));
        assert_eq!(result, Err(()));
        let result = cache
            .get_or_insert_async::<_, ()>(&0, async { panic!() })
            .await;
        assert_eq!(result, Ok(0));
        let result = cache
            .get_or_insert_async::<_, ()>(&4, async { Err(()) })
            .await;
        assert_eq!(result, Err(()));
        let result = cache
            .get_or_insert_async::<_, ()>(&4, async { Ok(4) })
            .await;
        assert_eq!(result, Ok(4));
    }

    #[test]
    fn test_retain_unsync() {
        let mut cache = unsync::Cache::<u64, u64>::new(100);
        let ranges = 0..10;
        for i in ranges.clone() {
            let guard = cache.get_ref_or_guard(&i).unwrap_err();
            guard.insert(i);
            assert_eq!(cache.get_ref_or_guard(&i).ok().copied(), Some(i));
        }
        let small = 3;
        cache.retain(|&key, &val| val > small && key > small);
        for i in ranges.clone() {
            let actual = cache.get(&i);
            if i > small {
                assert!(actual.is_some());
                assert_eq!(*actual.unwrap(), i);
            } else {
                assert!(actual.is_none());
            }
        }
        let big = 7;
        cache.retain(|&key, &val| val < big && key < big);
        for i in ranges {
            let actual = cache.get(&i);
            if i > small && i < big {
                assert!(actual.is_some());
                assert_eq!(*actual.unwrap(), i);
            } else {
                assert!(actual.is_none());
            }
        }
    }

    #[tokio::test]
    async fn test_retain_sync() {
        use crate::sync::*;
        let cache = Cache::<u64, u64>::new(100);
        let ranges = 0..10;
        for i in ranges.clone() {
            let GuardResult::Guard(guard) = cache.get_value_or_guard(&i, None) else {
                panic!();
            };
            guard.insert(i).unwrap();
            let GuardResult::Value(v) = cache.get_value_or_guard(&i, None) else {
                panic!();
            };
            assert_eq!(v, i);
        }
        let small = 4;
        cache.retain(|&key, &val| val > small && key > small);
        for i in ranges.clone() {
            let actual = cache.get(&i);
            if i > small {
                assert!(actual.is_some());
                assert_eq!(actual.unwrap(), i);
            } else {
                assert!(actual.is_none());
            }
        }
        let big = 8;
        cache.retain(|&key, &val| val < big && key < big);
        for i in ranges {
            let actual = cache.get(&i);
            if i > small && i < big {
                assert!(actual.is_some());
                assert_eq!(actual.unwrap(), i);
            } else {
                assert!(actual.is_none());
            }
        }
    }

    #[test]
    #[cfg_attr(miri, ignore)]
    fn test_value_or_guard() {
        use crate::sync::*;
        use rand::prelude::*;
        for _i in 0..2000 {
            dbg!(_i);
            let mut entered = AtomicUsize::default();
            let cache = sync::Cache::<(u64, u64), u64>::new(100);
            const THREADS: usize = 100;
            let wg = std::sync::Barrier::new(THREADS);
            let solve_at = rand::rng().random_range(0..THREADS);
            std::thread::scope(|s| {
                for _ in 0..THREADS {
                    s.spawn(|| {
                        wg.wait();
                        loop {
                            match cache.get_value_or_guard(&(1, 1), Some(Duration::from_millis(1)))
                            {
                                GuardResult::Value(v) => assert_eq!(v, 1),
                                GuardResult::Guard(g) => {
                                    let before =
                                        entered.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
                                    if before == solve_at {
                                        g.insert(1).unwrap();
                                    }
                                }
                                GuardResult::Timeout => continue,
                            }
                            break;
                        }
                    });
                }
            });
            assert_eq!(*entered.get_mut(), solve_at + 1);
        }
    }

    #[tokio::test(flavor = "multi_thread")]
    #[cfg_attr(miri, ignore)]
    async fn test_get_or_insert_async() {
        use rand::prelude::*;
        for _i in 0..5000 {
            dbg!(_i);
            let entered = Arc::new(AtomicUsize::default());
            let cache = Arc::new(sync::Cache::<(u64, u64), u64>::new(100));
            const TASKS: usize = 100;
            let wg = Arc::new(tokio::sync::Barrier::new(TASKS));
            let solve_at = rand::rng().random_range(0..TASKS);
            let mut tasks = Vec::new();
            for _ in 0..TASKS {
                let cache = cache.clone();
                let wg = wg.clone();
                let entered = entered.clone();
                let task = tokio::spawn(async move {
                    wg.wait().await;
                    let result = cache
                        .get_or_insert_async(&(1, 1), async {
                            let before = entered.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
                            if before == solve_at {
                                Ok(1)
                            } else {
                                Err(())
                            }
                        })
                        .await;
                    assert!(matches!(result, Ok(1) | Err(())));
                });
                tasks.push(task);
            }
            for task in tasks {
                task.await.unwrap();
            }
            assert_eq!(cache.get(&(1, 1)), Some(1));
            assert_eq!(
                entered.load(std::sync::atomic::Ordering::Relaxed),
                solve_at + 1
            );
        }
    }

    #[tokio::test(flavor = "multi_thread")]
    #[cfg_attr(miri, ignore)]
    async fn test_value_or_guard_async() {
        use rand::prelude::*;
        for _i in 0..5000 {
            dbg!(_i);
            let entered = Arc::new(AtomicUsize::default());
            let cache = Arc::new(sync::Cache::<(u64, u64), u64>::new(100));
            const TASKS: usize = 100;
            let wg = Arc::new(tokio::sync::Barrier::new(TASKS));
            let solve_at = rand::rng().random_range(0..TASKS);
            let mut tasks = Vec::new();
            for _ in 0..TASKS {
                let cache = cache.clone();
                let wg = wg.clone();
                let entered = entered.clone();
                let task = tokio::spawn(async move {
                    wg.wait().await;
                    loop {
                        match tokio::time::timeout(
                            Duration::from_millis(1),
                            cache.get_value_or_guard_async(&(1, 1)),
                        )
                        .await
                        {
                            Ok(Ok(r)) => assert_eq!(r, 1),
                            Ok(Err(g)) => {
                                let before =
                                    entered.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
                                if before == solve_at {
                                    g.insert(1).unwrap();
                                }
                            }
                            Err(_) => continue,
                        }
                        break;
                    }
                });
                tasks.push(task);
            }
            for task in tasks {
                task.await.unwrap();
            }
            assert_eq!(cache.get(&(1, 1)), Some(1));
            assert_eq!(
                entered.load(std::sync::atomic::Ordering::Relaxed),
                solve_at + 1
            );
        }
    }
}