lora-store 0.27.0

In-memory graph store with property indexes for LoraDB.
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

//! LEB128 varints: seven bits per byte, low bits first, the high bit set
//! on every byte but the last. Used by the record encoding
//! ([`crate::encoded`]) and the length prefixes of the in-memory record
//! store.
//!
//! The bytes read are ones this crate wrote, so a malformed varint is a
//! bug, reported by the slice index.
//!
//! Every function is `#[inline(always)]`: they are a few instructions
//! each and sit in the record decoder's inner loops.

/// Bytes `value` takes as a varint.
#[inline(always)]
pub(crate) fn len(value: u64) -> usize {
    (64 - (value | 1).leading_zeros() as usize).div_ceil(7)
}

/// Append `value` to `out`.
#[inline(always)]
pub(crate) fn push(out: &mut Vec<u8>, mut value: u64) {
    while value >= 0x80 {
        out.push(value as u8 | 0x80);
        value >>= 7;
    }
    out.push(value as u8);
}

/// Write `value` into `out` at `*pos`, advancing it. `out` must have
/// [`len`]`(value)` bytes there.
#[inline(always)]
pub(crate) fn write(out: &mut [u8], pos: &mut usize, mut value: u64) {
    while value >= 0x80 {
        out[*pos] = value as u8 | 0x80;
        *pos += 1;
        value >>= 7;
    }
    out[*pos] = value as u8;
    *pos += 1;
}

/// Read a varint at `*pos`, advancing it.
#[inline(always)]
pub(crate) fn read(bytes: &[u8], pos: &mut usize) -> u64 {
    let first = bytes[*pos];
    *pos += 1;
    if first < 0x80 {
        return u64::from(first);
    }
    let mut value = u64::from(first & 0x7f);
    let mut shift = 7;
    loop {
        let byte = bytes[*pos];
        *pos += 1;
        value |= u64::from(byte & 0x7f) << shift;
        if byte < 0x80 {
            return value;
        }
        shift += 7;
    }
}

/// [`read`] for a length prefix, as a `usize`. A plain loop: where the
/// record store reads a record's length, it measured faster than
/// `read`'s one-byte fast path (raw `with_node`, 2M nodes: 47 against
/// 58 ns).
#[inline(always)]
pub(crate) fn read_len(bytes: &[u8], pos: &mut usize) -> usize {
    let mut value = 0usize;
    let mut shift = 0;
    loop {
        let byte = bytes[*pos];
        *pos += 1;
        value |= ((byte & 0x7f) as usize) << shift;
        if byte < 0x80 {
            return value;
        }
        shift += 7;
    }
}

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

    #[test]
    fn varints_round_trip_through_both_writers() {
        for value in [0u64, 1, 127, 128, 16_383, 16_384, u32::MAX as u64, u64::MAX] {
            let mut pushed = Vec::new();
            push(&mut pushed, value);
            assert_eq!(pushed.len(), len(value), "{value}");
            let mut written = vec![0; len(value) + 2];
            let mut end = 1;
            write(&mut written, &mut end, value);
            assert_eq!(&written[1..end], &pushed[..]);
            let mut pos = 0;
            assert_eq!(read(&pushed, &mut pos), value);
            assert_eq!(pos, pushed.len());
            if let Ok(value) = usize::try_from(value) {
                let mut pos = 0;
                assert_eq!(read_len(&pushed, &mut pos), value);
                assert_eq!(pos, pushed.len());
            }
        }
    }
}