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

use alloc::{boxed::Box, vec::Vec};
use core::hash::{BuildHasher, Hash};

use fnv::FnvBuildHasher;

#[allow(clippy::module_name_repetitions)]
pub struct DirectMappedCache<T: Hash + PartialEq, S: BuildHasher = FnvBuildHasher> {
    cache: Box<[Option<T>]>,
    build_hasher: S,
}

impl<T: Hash + PartialEq> DirectMappedCache<T, FnvBuildHasher> {
    #[must_use]
    pub fn with_capacity(capacity: usize) -> Self {
        Self::with_capacity_and_hasher(capacity, FnvBuildHasher::default())
    }
}

impl<T: Hash + PartialEq, S: BuildHasher> DirectMappedCache<T, S> {
    #[must_use]
    pub fn with_capacity_and_hasher(capacity: usize, build_hasher: S) -> Self {
        let mut cache = Vec::with_capacity(capacity);
        cache.resize_with(capacity, || None);

        Self {
            cache: cache.into_boxed_slice(),
            build_hasher,
        }
    }
}

impl<T: Hash + PartialEq, B: BuildHasher> DirectMappedCache<T, B> {
    #[must_use]
    pub fn capacity(&self) -> usize {
        self.cache.len()
    }

    #[must_use]
    pub fn insert(&mut self, value: T) -> bool {
        if self.capacity() == 0 {
            return true;
        }

        let hash = self.build_hasher.hash_one(&value);

        #[allow(clippy::cast_possible_truncation)]
        let index = (hash % (self.capacity() as u64)) as usize;

        let bucket = &mut self.cache[index];
        let insert = bucket.as_ref().map_or(true, |old| old != &value);
        *bucket = Some(value);

        insert
    }
}