evict 0.3.1

Page eviction policies: LRU, LRU-k, LIRS, SLRU etc
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

use {
    evict::{EvictError, EvictionPolicy, LruReplacer},
    std::sync::Arc,
};

#[test]
fn basic_ops() {
    let replacer = LruReplacer::new(20);
    assert_eq!(replacer.capacity(), 20);

    // Scenario: unpin six elements, this updates eviction candidate list.
    replacer.unpin(1).unwrap();
    replacer.unpin(2).unwrap();
    replacer.unpin(3).unwrap();
    replacer.unpin(4).unwrap();
    replacer.unpin(5).unwrap();
    replacer.unpin(6).unwrap();
    replacer.unpin(1).unwrap(); // Unpin 1 again. It should have no effect.
    assert_eq!(6, replacer.size());

    // Scenario: get three victims from the lru.
    assert_eq!(replacer.evict(), Some(1));
    assert_eq!(replacer.evict(), Some(2));
    assert_eq!(replacer.evict(), Some(3));

    // Scenario: pin elements in the replacer.
    // Note that 3 has already been victimized, so pinning 3 should have no effect.
    replacer.pin(3).expect("cannot pin 3");
    replacer.pin(4).expect("cannot pin 4");
    assert_eq!(2, replacer.size());

    // Scenario: unpin 4. We expect that the reference bit of 4 will be set to 1.
    replacer.unpin(4).expect("cannot unpin 4");

    // Scenario: continue looking for victims. We expect these victims.
    assert_eq!(replacer.evict(), Some(5));
    assert_eq!(replacer.evict(), Some(6));
    assert_eq!(replacer.evict(), Some(4));
}

#[test]
fn touch() {
    {
        let replacer = LruReplacer::new(20);

        // Scenario: unpin elements, i.e. add them to the replacer.
        replacer.unpin(1).unwrap();
        replacer.unpin(2).unwrap();
        replacer.unpin(3).unwrap();
        assert_eq!(3, replacer.size());

        replacer.unpin(1).expect("cannot unpin 1"); // Unpin 1 again. It should have no effect.
        assert_eq!(3, replacer.size());
        assert_eq!(Some(1), replacer.peek());

        // However, if we access 1, it should be moved to the end of the queue.
        replacer.touch(1).unwrap();
        assert_eq!(Some(2), replacer.peek());

        assert_eq!(replacer.evict(), Some(2));
        assert_eq!(replacer.evict(), Some(3));
        assert_eq!(replacer.evict(), Some(1));
    }

    {
        // The first touch should add the frame to the list of non-pinned frames.
        let replacer = LruReplacer::new(20);

        // Scenario: unpin elements by touching.
        replacer.touch(1).unwrap();
        replacer.touch(2).unwrap();
        replacer.touch(3).unwrap();
        assert_eq!(3, replacer.size());

        replacer.unpin(1).expect("cannot unpin 1"); // Unpin 1 again. It should have no effect.
        assert_eq!(3, replacer.size());
        assert_eq!(Some(1), replacer.peek());

        // However, if we access 1, it should be moved to the end of the queue.
        replacer.touch(1).unwrap();
        assert_eq!(Some(2), replacer.peek());

        assert_eq!(replacer.evict(), Some(2));
        assert_eq!(replacer.evict(), Some(3));
        assert_eq!(replacer.evict(), Some(1));
    }
}

#[test]
fn remove() {
    let replacer = LruReplacer::new(20);

    // Scenario: unpin elements, i.e. add them to the replacer.
    replacer.unpin(1).unwrap();
    replacer.unpin(2).unwrap();
    replacer.unpin(3).unwrap();
    assert_eq!(3, replacer.size());

    // Scenario: remove 2 from the replacer.
    replacer.remove(2).unwrap();
    assert_eq!(2, replacer.size());
    assert_eq!(Some(1), replacer.peek());

    // Scenario: remove 1 from the replacer.
    replacer.remove(1).unwrap();
    assert_eq!(1, replacer.size());
    assert_eq!(Some(3), replacer.peek());

    // Scenario: pin 3 and then try removing it from the replacer.
    replacer.pin(3).unwrap();
    assert_eq!(replacer.remove(3), Err(EvictError::PinnedFrameRemoval(3)));
}

#[test]
fn multi_threaded() {
    use std::thread;

    let n = 100;
    let k = 20;
    let replacer = Arc::new(LruReplacer::new(n * k));
    let replacer_clone = Arc::clone(&replacer);

    // Replacer is thread-safe and can be shared between threads.
    // Spawn `n` threads, each thread concurrently unpins its own set of frames (of
    // size `k`). At the end we check that the size of the replacer is `n * k`.
    let mut handles = vec![];
    for i in 0..n {
        let replacer_clone = Arc::clone(&replacer_clone);
        handles.push(thread::spawn(move || {
            for j in 0..k {
                replacer_clone.unpin(i * k + j).unwrap();
            }
        }));
    }
    for handle in handles {
        handle.join().unwrap();
    }
    assert_eq!(replacer.size(), n * k);
}