syd 3.54.1

//
// Syd: rock-solid application kernel
// src/expiry.rs: Concurrent expiring map backed by scc::HashMap
//
// Copyright (c) 2026 Ali Polatel <alip@chesswob.org>
// Based in part upon expiringmap crate which is:
//   SPDX-License-Identifier: Apache-2.0 OR MIT
//
// SPDX-License-Identifier: GPL-3.0

// SAFETY: This module has been liberated from unsafe code!
#![forbid(unsafe_code)]

//! A concurrent [`ExpiringMap`] backed by [`scc::HashMap`].

use std::{
    borrow::Borrow,
    hash::Hash,
    sync::atomic::{AtomicUsize, Ordering},
    time::Instant,
};

use dur::Duration;
use nix::errno::Errno;

use crate::hash::SydRandomState;

// The minimum size to set `last_size` to so we don't go bananas with vacuums.
const MINIMUM_VACUUM_SIZE: usize = 8;

// A value with expiry metadata.
#[derive(Debug)]
struct ExpiryValue<V> {
    value: V,
    inserted: Instant,
    ttl: Duration,
}

impl<V> ExpiryValue<V> {
    // Returns true if this entry has not yet expired.
    fn not_expired(&self) -> bool {
        self.inserted.elapsed() < self.ttl.into()
    }
}

/// A concurrent map where entries automatically expire after a per-entry TTL.
pub struct ExpiringMap<K, V>
where
    K: Eq + Hash,
{
    inner: scc::HashMap<K, ExpiryValue<V>, SydRandomState>,
    last_size: AtomicUsize,
}

impl<K: Eq + Hash, V> Default for ExpiringMap<K, V> {
    fn default() -> Self {
        Self::new()
    }
}

impl<K: Eq + Hash, V> ExpiringMap<K, V> {
    /// Create a new, empty [`ExpiringMap`].
    pub fn new() -> Self {
        Self {
            inner: scc::HashMap::with_hasher(SydRandomState::new()),
            last_size: AtomicUsize::new(MINIMUM_VACUUM_SIZE),
        }
    }

    /// Remove all expired entries.
    pub fn vacuum(&self) {
        self.inner.retain_sync(|_, expiry| expiry.not_expired());
        let len = self.inner.len();
        if len > MINIMUM_VACUUM_SIZE {
            self.last_size.store(len, Ordering::Relaxed);
        } else {
            self.last_size.store(MINIMUM_VACUUM_SIZE, Ordering::Relaxed);
        }
    }

    /// Execute a vacuum if the map has grown by more than 1.5 times.
    pub fn vacuum_if_needed(&self) {
        let last = self.last_size.load(Ordering::Relaxed);
        let len = self.inner.len();
        if last.saturating_mul(3).saturating_div(2) < len {
            self.vacuum();
        }
    }

    /// Insert a value with a TTL. Returns the old value if it existed and
    /// was not expired.
    ///
    /// Returns `Err(Errno::ENOMEM)` if memory allocation fails.
    pub fn try_insert(&self, key: K, value: V, ttl: Duration) -> Result<Option<V>, Errno> {
        self.vacuum_if_needed();

        // Reserve capacity before insertion.
        let _reserve = self.inner.reserve(1).ok_or(Errno::ENOMEM)?;

        let entry = ExpiryValue {
            value,
            inserted: Instant::now(),
            ttl,
        };

        // Perform atomic upsert.
        match self.inner.entry_sync(key) {
            scc::hash_map::Entry::Occupied(mut occupied) => {
                let old = std::mem::replace(occupied.get_mut(), entry);
                Ok(if old.not_expired() {
                    Some(old.value)
                } else {
                    None
                })
            }
            scc::hash_map::Entry::Vacant(vacant) => {
                vacant.insert_entry(entry);
                Ok(None)
            }
        }
    }

    /// Update a value in place using a closure, if the key exists and
    /// has not expired. Returns the closure's return value, or `None`.
    pub fn update<Q, R, F>(&self, key: &Q, f: F) -> Option<R>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
        F: FnOnce(&mut V) -> R,
    {
        self.inner
            .update_sync(key, |_, v| {
                if v.not_expired() {
                    Some(f(&mut v.value))
                } else {
                    None
                }
            })
            .flatten()
    }

    /// Update an existing non-expired entry or insert a new one atomically.
    ///
    /// If the key exists and has not expired, calls `update_fn` on the
    /// value and returns `Ok(Some(R))` with the closure's result.  If
    /// the key does not exist or has expired, inserts `value` with the
    /// given `ttl` and returns `Ok(None)`.
    ///
    /// Returns `Err(Errno::ENOMEM)` on allocation failure.
    pub fn try_upsert<R, F>(
        &self,
        key: K,
        update_fn: F,
        value: V,
        ttl: Duration,
    ) -> Result<Option<R>, Errno>
    where
        F: FnOnce(&mut V) -> R,
    {
        self.vacuum_if_needed();

        let _reserve = self.inner.reserve(1).ok_or(Errno::ENOMEM)?;

        match self.inner.entry_sync(key) {
            scc::hash_map::Entry::Occupied(mut occupied) => {
                let ev = occupied.get_mut();
                if ev.not_expired() {
                    Ok(Some(update_fn(&mut ev.value)))
                } else {
                    // Replace with new entry on expiry.
                    *ev = ExpiryValue {
                        value,
                        inserted: Instant::now(),
                        ttl,
                    };
                    Ok(None)
                }
            }
            scc::hash_map::Entry::Vacant(vacant) => {
                vacant.insert_entry(ExpiryValue {
                    value,
                    inserted: Instant::now(),
                    ttl,
                });
                Ok(None)
            }
        }
    }

    /// Returns true if the key exists and has not expired.
    pub fn contains_key<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        self.inner
            .read_sync(key, |_, v| v.not_expired())
            .unwrap_or(false)
    }

    /// Get a copy of the value if the key exists and has not expired.
    pub fn get<Q>(&self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
        V: Copy,
    {
        self.inner
            .read_sync(
                key,
                |_, v| {
                    if v.not_expired() {
                        Some(v.value)
                    } else {
                        None
                    }
                },
            )
            .flatten()
    }

    /// Remove a key. Returns true if the entry existed and was not expired.
    pub fn remove<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq,
    {
        self.inner
            .remove_sync(key)
            .map(|(_, v)| v.not_expired())
            .unwrap_or(false)
    }

    /// Returns true if the map contains no entries.
    ///
    /// Note: This may include logically expired entries that haven't been
    /// vacuumed yet. Call [`vacuum`](Self::vacuum) first for an accurate count.
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }

    /// Returns the number of entries in the map (including expired ones
    /// that haven't been vacuumed).
    pub fn len(&self) -> usize {
        self.inner.len()
    }
}

#[cfg(test)]
mod tests {
    use std::{sync::Arc, thread};

    use dur::Duration;

    use super::*;

    #[test]
    fn test_expirymap_1() {
        let map: ExpiringMap<String, u8> = ExpiringMap::new();
        assert!(map.is_empty());
        assert_eq!(map.len(), 0);
    }

    #[test]
    fn test_expirymap_2() {
        let map = ExpiringMap::new();
        assert!(map
            .try_insert("key", "value", Duration::from_secs(5))
            .unwrap()
            .is_none());
        assert_eq!(map.get(&"key"), Some("value"));
    }

    #[test]
    fn test_expirymap_3() {
        let map = ExpiringMap::new();
        map.try_insert("key", "value", Duration::from_millis(50))
            .unwrap();
        assert_eq!(map.get(&"key"), Some("value"));
        thread::sleep(Duration::from_millis(75).into());
        assert!(map.get(&"key").is_none());
    }

    #[test]
    fn test_expirymap_4() {
        let map = ExpiringMap::new();
        map.try_insert("key", 42u8, Duration::from_secs(5)).unwrap();
        assert!(map.contains_key(&"key"));
        assert!(!map.contains_key(&"other"));
    }

    #[test]
    fn test_expirymap_5() {
        let map = ExpiringMap::new();
        map.try_insert("key", 42u8, Duration::from_millis(50))
            .unwrap();
        thread::sleep(Duration::from_millis(75).into());
        assert!(!map.contains_key(&"key"));
    }

    #[test]
    fn test_expirymap_6() {
        let map = ExpiringMap::new();
        map.try_insert("key", 42u8, Duration::from_secs(5)).unwrap();
        assert!(map.remove(&"key"));
        assert!(!map.contains_key(&"key"));
    }

    #[test]
    fn test_expirymap_7() {
        let map: ExpiringMap<&str, u8> = ExpiringMap::new();
        assert!(!map.remove(&"key"));
    }

    #[test]
    fn test_expirymap_8() {
        let map = ExpiringMap::new();
        map.try_insert("key", 42u8, Duration::from_millis(50))
            .unwrap();
        thread::sleep(Duration::from_millis(75).into());
        assert!(!map.remove(&"key"));
    }

    #[test]
    fn test_expirymap_9() {
        let map = ExpiringMap::new();
        assert!(map
            .try_insert("key", "x", Duration::from_secs(5))
            .unwrap()
            .is_none());
        assert_eq!(
            map.try_insert("key", "y", Duration::from_secs(5)).unwrap(),
            Some("x")
        );
        assert_eq!(map.get(&"key"), Some("y"));
    }

    #[test]
    fn test_expirymap_10() {
        let map = ExpiringMap::new();
        map.try_insert("key", "x", Duration::from_secs(0)).unwrap();
        assert!(map
            .try_insert("key", "y", Duration::from_secs(5))
            .unwrap()
            .is_none());
        assert_eq!(map.get(&"key"), Some("y"));
    }

    #[test]
    fn test_expirymap_11() {
        let map = ExpiringMap::new();
        map.try_insert("key", 1u8, Duration::from_secs(5)).unwrap();
        let result = map.update(&"key", |v| {
            *v = v.saturating_add(1);
            *v
        });
        assert_eq!(result, Some(2));
        assert_eq!(map.get(&"key"), Some(2));
    }

    #[test]
    fn test_expirymap_12() {
        let map = ExpiringMap::new();
        map.try_insert("key", 1u8, Duration::from_millis(50))
            .unwrap();
        thread::sleep(Duration::from_millis(75).into());
        let result = map.update(&"key", |v| {
            *v = v.saturating_add(1);
            *v
        });
        assert!(result.is_none());
    }

    #[test]
    fn test_expirymap_13() {
        let map: ExpiringMap<&str, u8> = ExpiringMap::new();
        let result = map.update(&"key", |v| {
            *v = v.saturating_add(1);
            *v
        });
        assert!(result.is_none());
    }

    #[test]
    fn test_expirymap_14() {
        let map = ExpiringMap::new();
        map.try_insert("key", (), Duration::from_secs(50)).unwrap();
        map.vacuum();
        assert!(map.contains_key(&"key"));
    }

    #[test]
    fn test_expirymap_15() {
        let map = ExpiringMap::new();
        map.try_insert("key", (), Duration::from_millis(50))
            .unwrap();
        thread::sleep(Duration::from_millis(75).into());
        map.vacuum();
        assert!(map.is_empty());
    }

    #[test]
    fn test_expirymap_16() {
        let map = ExpiringMap::new();
        for i in 0..13 {
            map.try_insert(i, (), Duration::from_millis(10)).unwrap();
        }
        thread::sleep(Duration::from_millis(50).into());
        map.try_insert(100, (), Duration::from_secs(5)).unwrap();
        assert!(map.contains_key(&100));
        assert!(!map.contains_key(&0));
    }

    #[test]
    fn test_expirymap_17() {
        let map: ExpiringMap<&str, u8> = ExpiringMap::new();
        assert!(map.is_empty());
        map.try_insert("key", 1, Duration::from_secs(5)).unwrap();
        assert!(!map.is_empty());
    }

    #[test]
    fn test_expirymap_18() {
        let map = ExpiringMap::new();
        map.try_insert("key", 1u8, Duration::from_secs(5)).unwrap();
        map.remove(&"key");
        assert!(map.is_empty());
    }

    #[test]
    fn test_expirymap_19() {
        let map: ExpiringMap<String, usize> = ExpiringMap::new();
        map.try_insert(String::from("x"), 1, Duration::from_secs(5))
            .unwrap();
        assert_eq!(map.get("x"), Some(1));
        assert_eq!(map.get(&String::from("x")), Some(1));
        assert!(map.contains_key("x"));
        assert!(map.contains_key(&String::from("x")));
    }

    #[test]
    fn test_expirymap_20() {
        let map = Arc::new(ExpiringMap::new());

        let handles: Vec<_> = (0..4)
            .map(|t| {
                let map = Arc::clone(&map);
                thread::spawn(move || {
                    for i in 0..100 {
                        let key = t * 100 + i;
                        map.try_insert(key, key, Duration::from_secs(5)).unwrap();
                    }
                })
            })
            .collect();

        for h in handles {
            h.join().unwrap();
        }

        for i in 0..400 {
            assert!(map.contains_key(&i), "missing key {i}");
        }
    }
}