matecito 0.1.6

Concurrent LRU Cache (experimental)
Documentation 
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

use std::hash::{Hash, Hasher};
use twox_hash::XxHash64;

pub(crate) struct BloomFilter {
    hash_functions: Vec<XxHash64>,
    counters: Vec<u64>,
    array_size: u64,
    // approximate value
    pub max_count: u64,
}

impl BloomFilter {
    pub fn new(num_elements: u64, array_size: u64) -> Self {
        let num_hash_functions =
            BloomFilter::optimal_hash_functions(num_elements, array_size).round();
        let mut hash_functions = Vec::new();
        for i in 0..(num_hash_functions as usize) {
            hash_functions.push(XxHash64::with_seed(i as u64))
        }
        let counters = vec![0; array_size as usize];
        // Generate independent
        Self {
            hash_functions,
            counters,
            array_size,
            max_count: 0,
        }
    }

    #[inline]
    fn optimal_hash_functions(_n: u64, _m: u64) -> f64 {
        7f64 // TODO: find out what's the best way to define this for counteer bloom filters.
    }

    fn get_indices<K: std::hash::Hash>(&self, key: &K) -> Vec<u64> {
        self.hash_functions
            .iter()
            .map(|h| {
                let mut hh = h.clone();
                key.hash(&mut hh);
                hh.finish() % self.array_size
            })
            .collect()
    }

    pub fn count_present<K: Hash>(&self, key: &K) -> u64 {
        let indices = self.get_indices(key);
        indices
            .iter()
            .map(|idx| {
                let idx = *idx as usize;
                self.counters[idx]
            })
            .min()
            .unwrap()
    }

    pub fn increment<K: Hash>(&mut self, key: &K) -> () {
        let indices = self.get_indices(key);
        indices.iter().for_each(|idx| {
            self.counters[*idx as usize] += 1;
            if self.counters[*idx as usize] > self.max_count {
                self.max_count = self.counters[*idx as usize];
            }
        })
    }

    pub fn decrement<K: Hash>(&mut self, key: K) -> () {
        let indices = self.get_indices(&key);
        indices
            .iter()
            .for_each(|idx| self.counters[*idx as usize] -= 1)
    }

    pub fn halve(&mut self) {
        for el in self.counters.iter_mut() {
            *el = *el / 2;
        }
    }
}

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

    #[test]
    fn init_bloom_filter() {
        BloomFilter::new(10_000, 1000);
    }

    #[test]
    fn init_bloom_filter_insert_and_check_presence() {
        let mut bf = BloomFilter::new(10_000, 100);
        let key = b"asd";
        bf.increment(key);
        assert_eq!(0, bf.count_present(&b"123"));
        assert_eq!(1, bf.count_present(&b"asd"));
    }

    #[test]
    fn init_bloom_filter_insert_decrement_and_check_presence() {
        let mut bf = BloomFilter::new(10_000, 100);
        let key = b"asd";
        bf.increment(key);
        assert_eq!(0, bf.count_present(&b"123"));
        assert_eq!(1, bf.count_present(&b"asd"));

        bf.decrement(key);
        assert_eq!(0, bf.count_present(&b"asd"));
        assert_eq!(0, bf.count_present(&b"123"));
    }

    #[test]
    fn init_bloom_increment_ten_times_then_halve() {
        let mut bf = BloomFilter::new(10_000, 100);
        let key = b"asd";

        for _ in 0..10 {
            bf.increment(key);
        }
        bf.halve();
        assert_eq!(5, bf.count_present(&b"asd"));
        assert_eq!(0, bf.count_present(&b"123"));
        bf.halve();
        assert_eq!(2, bf.count_present(&b"asd"));
        bf.halve();
        assert_eq!(1, bf.count_present(&b"asd"));
        bf.halve();
        assert_eq!(0, bf.count_present(&b"asd"));
    }
}