weavatrix-git 0.3.1

use std::{collections::HashMap, hash::Hash};

struct Slot<K, V> {
    key: K,
    value: V,
    bytes: usize,
    referenced: bool,
}

pub(crate) struct ByteCache<K, V> {
    capacity: usize,
    used: usize,
    hand: usize,
    slots: Vec<Option<Slot<K, V>>>,
    positions: HashMap<K, usize>,
}

impl<K: Copy + Eq + Hash, V: Clone> ByteCache<K, V> {
    pub(crate) fn new(capacity: usize) -> Self {
        Self {
            capacity,
            used: 0,
            hand: 0,
            slots: Vec::new(),
            positions: HashMap::new(),
        }
    }

    pub(crate) fn get(&mut self, key: K) -> Option<V> {
        let slot = self.positions.get(&key).copied()?;
        let entry = self.slots.get_mut(slot)?.as_mut()?;
        entry.referenced = true;
        Some(entry.value.clone())
    }

    pub(crate) fn insert(&mut self, key: K, value: V, bytes: usize) {
        if self.capacity == 0 || bytes > self.capacity {
            return;
        }
        if let Some(slot) = self.positions.remove(&key)
            && let Some(old) = self.slots[slot].take()
        {
            self.used -= old.bytes;
        }
        while self.used.saturating_add(bytes) > self.capacity {
            self.evict_one();
        }
        let entry = Slot {
            key,
            value,
            bytes,
            referenced: true,
        };
        if let Some(slot) = self.slots.iter().position(Option::is_none) {
            self.slots[slot] = Some(entry);
            self.positions.insert(key, slot);
        } else {
            let slot = self.slots.len();
            self.slots.push(Some(entry));
            self.positions.insert(key, slot);
        }
        self.used += bytes;
    }

    fn evict_one(&mut self) {
        if self.positions.is_empty() {
            return;
        }
        loop {
            if self.hand >= self.slots.len() {
                self.hand = 0;
            }
            let slot = self.hand;
            self.hand += 1;
            let Some(entry) = self.slots[slot].as_mut() else {
                continue;
            };
            if entry.referenced {
                entry.referenced = false;
                continue;
            }
            let entry = self.slots[slot].take().expect("occupied cache slot");
            self.positions.remove(&entry.key);
            self.used -= entry.bytes;
            return;
        }
    }
}

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

    #[test]
    fn clock_cache_respects_capacity_and_skips_oversized_values() {
        let mut cache = ByteCache::new(6);
        cache.insert(1, "one", 3);
        cache.insert(2, "two", 3);
        assert_eq!(cache.get(1), Some("one"));
        cache.insert(3, "six", 3);
        let retained = [cache.get(1), cache.get(2)].into_iter().flatten().count();
        assert_eq!(retained, 1);
        assert_eq!(cache.get(3), Some("six"));
        cache.insert(4, "oversized", 7);
        assert_eq!(cache.get(4), None);
        let mut disabled = ByteCache::new(0);
        disabled.insert(1, "none", 0);
        assert_eq!(disabled.get(1), None);
    }
}