| builder |
|
|
| byte_phf |
|
|
| cursor.rs |
Types for walking stepwise through a trie.
For examples, see the `.cursor()` functions
and the `Cursor` types in this module. |
16532 |
| error.rs |
|
1062 |
| helpers.rs |
|
3420 |
| lib.rs |
A data structure offering zero-copy storage and retrieval of byte strings, with a focus
on the efficient storage of ASCII strings. Strings are mapped to `usize` values.
[`ZeroTrie`] does not support mutation because doing so would require recomputing the entire
data structure. Instead, it supports conversion to and from [`LiteMap`] and [`BTreeMap`].
There are multiple variants of [`ZeroTrie`] optimized for different use cases.
# Examples
```
use zerotrie::ZeroTrie;
let data: &[(&str, usize)] = &[("abc", 11), ("xyz", 22), ("axyb", 33)];
let trie: ZeroTrie<Vec<u8>> = data.iter().copied().collect();
assert_eq!(trie.get("axyb"), Some(33));
assert_eq!(trie.byte_len(), 18);
```
# Internal Structure
To read about the internal structure of [`ZeroTrie`], build the docs with private modules:
```bash
cargo doc --document-private-items --all-features --no-deps --open
```
[`LiteMap`]: litemap::LiteMap
[`BTreeMap`]: alloc::collections::BTreeMap |
2582 |
| options.rs |
Options for building and reading from a ZeroTrie.
These options are internal to the crate. A small selection of options
are exported by way of the different public types on this crate. |
4628 |
| reader.rs |
|
26526 |
| serde.rs |
|
23762 |
| varint.rs |
Varint spec for ZeroTrie:
- Lead byte: top M (2 or 3) bits are metadata; next is varint extender; rest is value
- Trail bytes: top bit is varint extender; rest are low bits of value
- Guaranteed uniqueness of varint by adding "latent value" for each extender byte
- No maximum, but high bits will be dropped if they don't fit in the platform's `usize`
This is best shown by examples.
```txt
xxx0'1010 = 10
xxx0'1111 = 15 (largest single-byte value with M=3)
xxx1'0000 0000'0000 must be 16 (smallest two-byte value with M=3)
xxx1'0000 0000'0001 = 17
xxx1'1111 0111'1111 = 2063 (largest two-byte value with M=3)
xxx1'0000 1000'0000 0000'0000 must be 2064 (smallest three-byte value with M=3)
xxx1'0000 1000'0000 0000'0001 = 2065
```
The latent values by number of bytes for M=3 are:
- 1 byte: 0
- 2 bytes: 16 = 0x10 = 0b10000
- 3 bytes: 2064 = 0x810 = 0b100000010000
- 4 bytes: 264208 = 0x40810 = 0b1000000100000010000
- 5 bytes: 33818640 = 0x2040810 = 0b10000001000000100000010000
- …
For M=2, the latent values are:
- 1 byte: 0
- 2 bytes: 32 = 0x20 = 0b100000
- 3 bytes: 4128 = 0x1020 = 0b1000000100000
- 4 bytes: 524320 = 0x81020 = 0b10000001000000100000
- 5 bytes: 67637280 = 0x4081020 = 0b100000010000001000000100000
- … |
16205 |
| zerotrie.rs |
|
32361 |