zipora 3.1.7

High-performance Rust implementation providing advanced data structures and compression algorithms with memory safety guarantees. Features LRU page cache, sophisticated caching layer, fiber-based concurrency, real-time compression, secure memory pools, SIMD optimizations, and complete C FFI for migration from C++.
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

use crate::containers::FastVec;
use crate::succinct::RankSelectOps;
use crate::StateId;
use crate::containers::specialized::UintVector;
use std::collections::{HashMap, VecDeque};

/// Internal storage implementations for different strategies
#[derive(Debug)]
pub(super) enum TrieStorage<R>
where
    R: RankSelectOps,
{
    /// Patricia trie storage with path compression
    Patricia {
        nodes: FastVec<PatriciaNode>,
        edge_data: FastVec<u8>,
        compressed_paths: HashMap<StateId, Vec<u8>>,
    },
    /// Critical-bit trie storage
    CriticalBit {
        nodes: FastVec<CritBitNode>,
        keys: FastVec<Vec<u8>>,
        critical_cache: HashMap<usize, u8>,
    },
    /// Double array trie storage
    DoubleArray {
        base: FastVec<u32>,
        check: FastVec<u32>,
        free_list: VecDeque<StateId>,
        state_count: usize,
    },
    /// LOUDS trie storage with succinct structures
    Louds {
        louds: R,
        is_link: R,
        next_link: UintVector,
        label_data: FastVec<u8>,
        core_data: FastVec<u8>,
        next_trie: Option<Box<super::trie::ZiporaTrie<R>>>,
    },
    /// Compressed sparse trie storage
    CompressedSparse(crate::fsa::cspp_trie::CsppTrie),
}

/// Patricia trie node with path compression (compact representation)
#[derive(Debug, Clone, Default)]
pub(super) struct PatriciaNode {
    /// Compact children storage: sorted Vec of (symbol, StateId) pairs
    pub(super) children: Vec<(u8, StateId)>,
    /// Compressed path data offset
    pub(super) _path_offset: u32,
    /// Compressed path length
    pub(super) _path_length: u16,
    /// Whether this node represents a complete key
    pub(super) is_final: bool,
    /// Node flags for optimization
    pub(super) _flags: u8,
}

/// Critical-bit trie node
#[repr(align(64))]
#[derive(Debug, Clone)]
pub(super) struct CritBitNode {
    /// Critical byte position
    pub(super) _crit_byte: usize,
    /// Critical bit position (0-7)
    pub(super) _crit_bit: u8,
    /// Left child (bit = 0)
    pub(super) _left_child: Option<StateId>,
    /// Right child (bit = 1)
    pub(super) _right_child: Option<StateId>,
    /// Key stored at this node (for leaves)
    pub(super) _key_index: Option<u32>,
    /// Whether this is a final state
    pub(super) is_final: bool,
}

/// Sparse trie node for compressed sparse storage
#[derive(Debug, Clone)]
pub(super) struct SparseNode {
    /// Sparse children map
    pub(super) children: HashMap<u8, StateId>,
    /// Compressed edge label
    pub(super) _edge_label: Option<u32>,
    /// Final state flag
    pub(super) is_final: bool,
}