prefix-trie 0.10.0

Prefix trie (tree) datastructure (both a set and a map) that provides exact and longest-prefix matches.
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

//! Validation/Verification logic for rkyv

use std::cmp::Ordering;

use crate::{
    rkyv::{ArchiveError::*, ArchivedPrefixMap},
    table::K,
    Prefix,
};
use rkyv::{
    bytecheck::Verify,
    rancor::{Fallible, Source},
    Archive,
};

unsafe impl<P, T, C> Verify<C> for ArchivedPrefixMap<P, T>
where
    P: Prefix,
    T: Archive,
    C: Fallible + ?Sized,
    C::Error: Source,
{
    fn verify(&self, _context: &mut C) -> Result<(), C::Error> {
        if self.nodes.len() > 1 << 32 {
            Err(C::Error::new(NodeIndexOverflow))? // coverage-exclude
        }
        if self.data.len() > 1 << 32 {
            Err(C::Error::new(DataIndexOverflow))? // coverage-exclude
        }
        if self.nodes.is_empty() {
            Err(C::Error::new(MissingRootNode))? // coverage-exclude
        }

        let mut child_cursor = 1;
        let mut data_cursor = 0;
        let mut cur_depth = 0;
        let mut next_depth = 1u32;

        let max_depth = P::num_bits();

        for i in 0..self.nodes.len() {
            let node = &self.nodes[i];
            // check non-empty (allow empty roots though)
            if i > 0 && node.data_bitmap == 0 && node.child_bitmap == 0 {
                Err(C::Error::new(ContainsEmptyNode))? // coverage-exclude
            }

            // check the depth count
            if i as u32 == next_depth {
                cur_depth += K;
                next_depth = node.children_idx.to_native();
                if cur_depth > max_depth {
                    Err(C::Error::new(DepthExceedsPrefixRepr))? // coverage-exclude
                }
            }

            // check max depth
            let max_allowed = u32::min(K - 1, max_depth - cur_depth);
            let denied_mask = DENIED_DEPTH_MASK[max_allowed as usize];
            if node.data_bitmap & denied_mask != 0 {
                Err(C::Error::new(DepthExceedsPrefixRepr))? // coverage-exclude
            }

            if node.data_idx != data_cursor {
                Err(C::Error::new(DataListInconsistent))? // coverage-exclude
            }
            data_cursor += node.data_bitmap.to_native().count_ones();
            if node.children_idx != child_cursor {
                Err(C::Error::new(NodeListInconsistent))? // coverage-exclude
            }
            child_cursor += node.child_bitmap.to_native().count_ones();
        }

        match child_cursor.cmp(&(self.nodes.len() as u32)) {
            Ordering::Less => Err(C::Error::new(NodeListTooShort))?, // coverage-exclude
            Ordering::Equal => {}
            Ordering::Greater => Err(C::Error::new(NodeListTooLong))?, // coverage-exclude
        }
        match data_cursor.cmp(&(self.data.len() as u32)) {
            Ordering::Less => Err(C::Error::new(DataListTooShort))?, // coverage-exclude
            Ordering::Equal => {}
            Ordering::Greater => Err(C::Error::new(DataListTooLong))?, // coverage-exclude
        }

        Ok(())
    }
}

const DENIED_DEPTH_MASK: [u32; K as usize] = [
    !((1u32 << 1) - 1),  // m = 0: allow bit 0
    !((1u32 << 3) - 1),  // m = 1: allow bits 0..=2
    !((1u32 << 7) - 1),  // m = 2: allow bits 0..=6
    !((1u32 << 15) - 1), // m = 3: allow bits 0..=14
    !((1u32 << 31) - 1), // m = 4: allow bits 0..=30 (bit 31 denied = stray-bit check)
];