qp-trie 0.8.2

An idiomatic and fast QP-trie implementation in pure Rust, written with an emphasis on safety.
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

use core::cmp;

// Get the "nybble index" corresponding to the `n`th nybble in the given slice.
//
// This is `1 + b` where `b` is the `n`th nybble, unless the given slice has less than `n / 2`
// elements, in which case `0` is returned.
#[inline]
pub fn nybble_index(n: usize, slice: &[u8]) -> u8 {
    let byte_idx = n / 2;

    if byte_idx < slice.len() {
        let byte = slice[byte_idx];

        // If the index is even, return the lower nybble. Odd, the higher nybble.
        // In both cases, increment by one. The zero-index is reserved for the "head" of the sparse
        // array.
        if n & 1 == 0 {
            1 + (byte & 0x0F)
        } else {
            1 + (byte >> 4)
        }
    } else {
        // If the nybble is out-of-range, we return zero. This is not some sort of weird
        // convention which would be clearer served by an `Option`; instead, we're actually
        // returning the "head" index of the sparse array. In the case that our trie `Branch` node
        // here - say it's branching at the `nth` nybble - contains a single entry of exactly `n /
        // 2` bytes long, then we have to have someplace to put it - the head. Essentially the head
        // is where leaf nodes which do not live at the fringes of the tree are stored.
        0
    }
}

// Find the nybble at which the two provided slices mismatch. If no such nybble exists and the
// slices are the same length, `None` is returned; if no such nybble exists but the slices are
// *not* the same length, then the point at which one slice has a byte and the other has ended is
// considered the mismatch point.
#[inline]
pub fn nybble_mismatch(left: &[u8], right: &[u8]) -> Option<usize> {
    let mut difference;

    for (i, (l, r)) in left.iter().cloned().zip(right.iter().cloned()).enumerate() {
        difference = l ^ r;

        if difference != 0 {
            if difference & 0x0F == 0 {
                return Some(1 + i * 2);
            } else {
                return Some(i * 2);
            }
        }
    }

    if left.len() == right.len() {
        None
    } else {
        Some(cmp::min(left.len(), right.len()) * 2)
    }
}

#[inline]
pub fn nybble_get_mismatch(left: &[u8], right: &[u8]) -> Option<(u8, usize)> {
    let mut difference;

    for (i, (l, r)) in left.iter().cloned().zip(right.iter().cloned()).enumerate() {
        difference = l ^ r;

        if difference != 0 {
            if difference & 0x0F == 0 {
                return Some((1 + (l >> 4), 1 + i * 2));
            } else {
                return Some((1 + (l & 0x0F), i * 2));
            }
        }
    }

    if left.len() == right.len() {
        None
    } else {
        let idx = cmp::min(left.len(), right.len()) * 2;

        Some((nybble_index(idx, left), idx))
    }
}

#[cfg(test)]
mod test {
    use alloc::vec::Vec;

    use quickcheck::TestResult;

    use super::*;

    quickcheck! {
        fn nybble(nybs: Vec<u8>) -> TestResult {
            for &nyb in &nybs {
                if nyb > 15 {
                    return TestResult::discard();
                }
            }

            let mut bytes = Vec::new();

            for chunk in nybs.chunks(2) {
                if chunk.len() == 2 {
                    bytes.push(chunk[0] | (chunk[1] << 4));
                } else {
                    bytes.push(chunk[0]);
                }
            }

            for (i, nyb) in nybs.into_iter().enumerate() {
                assert_eq!(nyb + 1, nybble_index(i, &bytes));
            }

            TestResult::passed()
        }
    }
}