data-pile 0.6.1

A simple and fast append-only data store
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

pub struct PageIndex {
    bounds: Vec<usize>,
}

#[derive(Debug, Eq, PartialEq)]
pub struct PageDescriptor {
    pub len: usize,
    pub offset: usize,
    pub number: usize,
}

impl PageIndex {
    pub fn new() -> Self {
        Self { bounds: Vec::new() }
    }

    pub fn add_page(&mut self, end: usize) {
        let start = self.bounds.last().copied().unwrap_or(0);
        assert!(start < end);

        if self.bounds.is_empty() {
            self.bounds.push(0);
        }

        self.bounds.push(end);
    }

    pub fn find(&self, address: usize) -> Option<PageDescriptor> {
        find_impl(&self.bounds, 0, address)
    }

    pub fn memory_size(&self) -> usize {
        self.bounds.last().copied().unwrap_or(0)
    }
}

fn find_impl(bounds: &[usize], offset: usize, address: usize) -> Option<PageDescriptor> {
    if bounds.len() < 2 {
        return None;
    }

    let end_position = bounds.len() / 2;
    let start_position = end_position - 1;

    if bounds[start_position] <= address && address < bounds[end_position] {
        Some(PageDescriptor {
            len: bounds[end_position] - bounds[start_position],
            offset: bounds[start_position],
            number: offset + start_position,
        })
    } else if address < bounds[start_position] {
        find_impl(&bounds[..end_position], offset, address)
    } else {
        find_impl(&bounds[end_position..], offset + end_position, address)
    }
}

#[cfg(test)]
mod tests {
    use super::{PageDescriptor, PageIndex};

    #[test]
    fn index() {
        let data = [34, 42, 67, 96, 103, 420];
        let mut index = PageIndex::new();

        for i in 0..data.len() {
            index.add_page(data[i]);
        }

        assert_eq!(
            Some(PageDescriptor {
                len: 34,
                offset: 0,
                number: 0,
            }),
            index.find(10)
        );
        assert_eq!(
            Some(PageDescriptor {
                len: 29,
                offset: 67,
                number: 3,
            }),
            index.find(80)
        );
        assert_eq!(
            Some(PageDescriptor {
                len: 7,
                offset: 96,
                number: 4,
            }),
            index.find(102)
        );
        assert_eq!(
            Some(PageDescriptor {
                len: 317,
                offset: 103,
                number: 5,
            }),
            index.find(103)
        );
        assert_eq!(
            Some(PageDescriptor {
                len: 317,
                offset: 103,
                number: 5,
            }),
            index.find(200)
        );
        assert_eq!(None, index.find(420));
        assert_eq!(None, index.find(1000));
    }
}