prefix-trie 0.9.4

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

#![cfg_attr(docsrs, feature(doc_notable_trait, doc_cfg))]

//! # Prefix-Trie
//!
//! This crate provides prefix-map and prefix-set collections for IP prefixes and other fixed-width
//! prefix types. `PrefixMap` is backed by a compact TreeBitMap-style trie and supports exact,
//! longest-prefix, and shortest-prefix matches. The crate supports both IPv4 and IPv6 (from either
//! [ipnet](https://docs.rs/ipnet/2.10.0), [ipnetwork](https://crates.io/crates/ipnetwork), or
//! [cidr](https://crates.io/crates/cidr)). It also supports any tuple `(R, u8)`, where `R` is any
//! unsigned primitive integer (`u8`, `u16`, `u32`, `u64`, `u128`, or `usize`).
//!
//! Prefixes are not stored verbatim. They are reconstructed from their trie position when returned
//! from map and set operations, so host bits outside the prefix length are not preserved.
//!
//! This crate also provides a `JointPrefixMap` and `JointPrefixSet` that contains two tables, one
//! for IPv4 and one for IPv6.
//!
//! ## Description of the Tree
//!
//! `PrefixMap` stores the logical binary prefix trie in multi-bit nodes, as described by
//! [W. Eatherton, Z. Dittia, and G. Varghes](https://dl.acm.org/doi/10.1145/997150.997160). Each
//! internal node covers five consecutive binary-trie levels. A node at depth `d` can hold values
//! for prefixes with lengths `d..=d+4`, and it has up to 32 child slots for subtries rooted at
//! depth `d+5`.
//!
//! Each node stores two bitmaps: one for the value slots that are present in the node, and one for
//! the child slots that are present below it. The allocators store multi-bit nodes and value cells
//! in compact, linearized arrays, which improves cache locality and keeps lookup and traversal
//! decisions local to a node. Physical slots are derived from the bitmaps with a popcount, avoiding
//! one pointer per possible branch.
//!
//! A stored entry is identified by its path through the trie and by a value bit inside the final
//! multi-bit node. The prefix object passed to `insert` is not stored alongside the value. Returned
//! prefixes are therefore reconstructed and canonicalized to the prefix length.
//!
//! ## Trie Views and Set Operations
//!
//! `TrieView` is a trait for immutable, mutable, and composed cursors into a trie. Concrete leaf
//! views are `TrieRef` (created from `&PrefixMap` or `&PrefixSet`) and `TrieRefMut` (created from
//! mutable references). Both are obtained through the `AsView` trait: call `map.view()` for a
//! full-trie view or `map.view_at(&prefix)` for a non-empty subtrie.
//!
//! Views and iterators traverse the logical prefix trie in lexicographic order and yield
//! reconstructed owned prefixes together with references or owned values.
//!
//! Set operations use the same view infrastructure. `union`, `intersection`, `difference`,
//! `covering_union`, and `covering_difference` simultaneously traverse the involved trie views and
//! yield results in lexicographic order. Covering variants also report longest-prefix matches from
//! the opposite side where appropriate. The result of such a set operation is not the finished
//! traversal, but a struct that implements `TrieView` and describes the traversal. Thus, you can
//! chain multiple set operations and compute them in a single traversal of the original tries.
//!
//! ## Aggregation
//!
//! Both `PrefixMap` and `PrefixSet` can be aggregated, that is, finding a compact representation
//! of the Trie to yield the same result for longest-prefix matches. For both the map and the set,
//! this library has two versions of the aggregation: `aggregate_consistent` and `aggregate`. The
//! consistent variant only drops nodes that are covered by an ancestor. Thus, `get_lpm` always
//! returns the same value for any prefix. The non-consistent variant is also allowed to merge
//! siblings with the same value. Thus, `get_lpm` is only guaranteed to return the same value for
//! addresses (i.e., /32 prefixes for IPv4).
//!
//! The `PrefixMap::aggregate`, `PrefixMap::aggregate_fill`, and `PrefixMap::aggregate_fill_default`
//! implement the Reduced Routing Table Construction algorithm, described by
//! [R. P. Draves, C. King, S. Venkatachary, and B. D. Zill](https://doi.org/10.1109/INFCOM.1999.749256).
//! The result is a minimal routing table. The `fill` variants will also add the root prefix (i.e.,
//! 0.0.0.0/0), and fill holes with the default value.
//!
//! ## Other operations on the Tree
//!
//! Most operations are bounded by prefix width, not by the number of stored entries. Let `w` be
//! the number of bits in the prefix representation, and let `h = ceil((w + 1) / 5)` be the maximum
//! number of multi-bit nodes on a search path. For IPv4, `h <= 7`; for IPv6, `h <= 26`. Let `n` be
//! the number of stored entries, and let `v` be the number of trie nodes visited by a traversal.
//!
//! | Operation                                      | Complexity                                   |
//! |------------------------------------------------|----------------------------------------------|
//! | `len`, `is_empty`, `mem_size`                  | `O(1)`                                       |
//! | `get`, `get_mut`, `contains_key`               | `O(h)`                                       |
//! | `get_lpm`, `get_spm`, `cover`                  | `O(h)`                                       |
//! | `entry`, `insert`                              | `O(h)`                                       |
//! | `remove`, `remove_keep_tree`                   | `O(h)`                                       |
//! | `children`, `view_at`                          | `O(h)` to create, then linear in the subtrie |
//! | `iter`, `keys`, `values`                       | `O(n + v)` for a complete traversal          |
//! | `retain`, `clear`                              | `O(n + v)`                                   |
//! | `remove_children`                              | `O(h + m)` with the removed subtrie size `m` |
//! | Operations on an occupied `map::Entry`         | `O(1)` after the entry lookup                |
//! | Inserting through a vacant `map::Entry`        | `O(h)` worst case                            |
//!
//! There are three removal styles:
//!
//! - `PrefixMap::remove` will remove an entry from the tree and modify the tree structure as if
//!   the value was never inserted before. It may remove now-empty multi-bit nodes and compact their
//!   allocator blocks.
//! - `PrefixMap::remove_children` will remove all entries that are contained within the given
//!   prefix, including entries stored in the same multi-bit node and in child nodes below it.
//! - `PrefixMap::remove_keep_tree` removes only the value and leaves the existing node structure in
//!   place, which can make reinserting the same prefix cheaper but may leave empty internal nodes
//!   for future traversals to pass through.

#![allow(clippy::collapsible_else_if)]
#![deny(missing_docs)]

mod aggregate;
mod allocator;
mod fmt;
#[cfg(test)]
mod fuzzing;
mod node;
mod prefix;
#[cfg(feature = "serde")]
mod serde;
mod table;
#[cfg(feature = "ipnet")]
#[cfg(test)]
mod test;

pub mod joint;
pub mod map;
pub mod set;
pub mod trieview;

pub use map::PrefixMap;
pub use prefix::Prefix;
pub use set::PrefixSet;
pub use trieview::{AsView, TrieRef, TrieRefMut, TrieView};