fbr_cache 0.1.1

A cache with frequency-based replacement strategy
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224

use crate::{FbrCache, Region};
use std::sync::atomic::{AtomicUsize, Ordering};

fn s(s: &str) -> String {
    s.to_owned()
}

#[test]
fn smoke() {
    let mut cache = FbrCache::<u32, String, 3>::with_age_threshold(10, 4);

    assert_eq!(cache.get(&1), None);
    assert_eq!(cache.len(), 0);
    assert!(cache.is_empty());
    assert_eq!(cache.iter().collect::<Vec<_>>(), vec![]);

    for i in 0..10 {
        cache.put(i, i.to_string());
    }
    assert_eq!(cache.get(&1), Some(&"1".to_owned()));
    assert_eq!(cache.len(), 10);
    assert!(!cache.is_empty());
    assert_eq!(
        cache.iter().collect::<Vec<_>>(),
        vec![
            (&1, &s("1"), 1, Region::New),
            (&9, &s("9"), 0, Region::New),
            (&8, &s("8"), 0, Region::New),
            (&7, &s("7"), 0, Region::Middle),
            (&6, &s("6"), 0, Region::Middle),
            (&5, &s("5"), 0, Region::Middle),
            (&4, &s("4"), 0, Region::Middle),
            (&3, &s("3"), 0, Region::Old),
            (&2, &s("2"), 0, Region::Old),
            (&0, &s("0"), 0, Region::Old)
        ]
    );

    cache.put(10, "10".to_string());
    assert_eq!(
        cache.iter().collect::<Vec<_>>(),
        vec![
            (&10, &s("10"), 0, Region::New),
            (&1, &s("1"), 1, Region::New),
            (&9, &s("9"), 0, Region::New),
            (&8, &s("8"), 0, Region::Middle),
            (&7, &s("7"), 0, Region::Middle),
            (&6, &s("6"), 0, Region::Middle),
            (&5, &s("5"), 0, Region::Middle),
            (&4, &s("4"), 0, Region::Old),
            (&3, &s("3"), 0, Region::Old),
            (&2, &s("2"), 0, Region::Old),
        ]
    );
}

#[test]
fn evict_1() {
    let mut cache = FbrCache::<u32, String, 3>::with_age_threshold(5, 4);
    cache.put(0, "0".to_owned());
    println!("{:?}", cache.iter().collect::<Vec<_>>());
    cache.put(1, "1".to_owned());
    println!("{:?}", cache.iter().collect::<Vec<_>>());
    cache.get(&0);
    println!("{:?}", cache.iter().collect::<Vec<_>>());
    for i in 0..5 {
        cache.put(i, i.to_string());
        println!("{:?}", cache.iter().collect::<Vec<_>>());
    }
    assert_eq!(
        cache.iter().collect::<Vec<_>>(),
        vec![
            (&4, &s("4"), 0, Region::New),
            (&3, &s("3"), 0, Region::Middle),
            (&2, &s("2"), 0, Region::Middle),
            (&1, &s("1"), 1, Region::Old),
            (&0, &s("0"), 1, Region::Old)
        ]
    );
    cache.get(&1);
    assert_eq!(
        cache.iter().collect::<Vec<_>>(),
        vec![
            (&1, &s("1"), 2, Region::New),
            (&4, &s("4"), 0, Region::Middle),
            (&3, &s("3"), 0, Region::Middle),
            (&2, &s("2"), 0, Region::Old),
            (&0, &s("0"), 1, Region::Old)
        ]
    );
    cache.put(5, "5".to_string());
    assert_eq!(
        cache.iter().collect::<Vec<_>>(),
        vec![
            (&5, &s("5"), 0, Region::New),
            (&1, &s("1"), 2, Region::Middle),
            (&4, &s("4"), 0, Region::Middle),
            (&3, &s("3"), 0, Region::Old),
            (&0, &s("0"), 1, Region::Old),
        ]
    );
}

#[test]
fn evict_3() {
    let mut cache = FbrCache::<u32, String, 3>::with_age_threshold(5, 4);
    for _ in 0..4 {
        for i in 0..5 {
            cache.put(i, i.to_string());
        }
    }
    cache.put(5, "5".to_string());
    assert_eq!(
        cache.iter().collect::<Vec<_>>(),
        vec![
            (&5, &s("5"), 0, Region::New),
            (&4, &s("4"), 3, Region::Middle),
            (&3, &s("3"), 3, Region::Middle),
            (&2, &s("2"), 3, Region::Old),
            (&1, &s("1"), 3, Region::Old)
        ]
    );
}

#[test]
fn aging() {
    let mut cache = FbrCache::<u32, String, 3>::with_age_threshold(5, 4);
    for n in 0usize..5 {
        for i in 1..6 {
            cache.put(i, i.to_string());
            assert_eq!(
                cache.total_count,
                (n * 5 + i as usize).saturating_sub(5),
                "n={} i={}",
                n,
                i
            );
        }
    }
    assert_eq!(
        cache.iter().collect::<Vec<_>>(),
        vec![
            (&5, &s("5"), 4, Region::New),
            (&4, &s("4"), 4, Region::Middle),
            (&3, &s("3"), 4, Region::Middle),
            (&2, &s("2"), 4, Region::Old),
            (&1, &s("1"), 4, Region::Old)
        ]
    );
    assert_eq!(cache.total_count, 20);

    cache.get(&1);
    assert_eq!(
        cache.iter().collect::<Vec<_>>(),
        vec![
            (&1, &s("1"), 2, Region::New),
            (&5, &s("5"), 2, Region::Middle),
            (&4, &s("4"), 2, Region::Middle),
            (&3, &s("3"), 2, Region::Old),
            (&2, &s("2"), 2, Region::Old),
        ]
    );
    assert_eq!(cache.total_count, 10);

    for _ in 0..4 {
        for i in 1..4 {
            cache.put(i, i.to_string());
        }
    }
    assert_eq!(
        cache.iter().collect::<Vec<_>>(),
        vec![
            (&3, &s("3"), 3, Region::New),
            (&2, &s("2"), 3, Region::Middle),
            (&1, &s("1"), 2, Region::Middle),
            (&5, &s("5"), 1, Region::Old),
            (&4, &s("4"), 1, Region::Old),
        ]
    );
}

#[test]
fn clear() {
    struct X<'a>(&'a AtomicUsize);
    impl<'a> Drop for X<'a> {
        fn drop(&mut self) {
            self.0.fetch_add(1, Ordering::Relaxed);
        }
    }

    let counter = AtomicUsize::new(0);
    let mut cache = FbrCache::<u32, X, 3>::with_age_threshold(5, 4);
    for i in 0..6 {
        cache.put(i, X(&counter));
    }
    assert_eq!(counter.load(Ordering::Relaxed), 1);
    cache.clear();
    assert_eq!(counter.load(Ordering::Relaxed), 6);
    for i in 0..6 {
        cache.put(i, X(&counter));
    }
    assert_eq!(counter.load(Ordering::Relaxed), 7);
    drop(cache);
    assert_eq!(counter.load(Ordering::Relaxed), 12);
}

#[test]
fn prio() {
    let mut cache = FbrCache::<u32, String, 3>::with_age_threshold(5, 4);
    cache.put_prio(0, 0.to_string());
    for i in 1..6 {
        cache.put(i, i.to_string());
    }
    assert_eq!(
        cache.iter().collect::<Vec<_>>(),
        vec![
            (&5, &s("5"), 0, Region::New),
            (&4, &s("4"), 0, Region::Middle),
            (&3, &s("3"), 0, Region::Middle),
            (&2, &s("2"), 0, Region::Old),
            (&0, &s("0"), 1, Region::Old),
        ]
    );
}