prefix-trie 0.8.3

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
127
128
129
130
131
132
133
134

//! This crate provides a simple prefix tree for IP prefixes. Any lookup performs longest-prefix
//! match. This crate supports both IPv4 and IPv6 (from either [ipnet](https://docs.rs/ipnet/2.10.0)
//! or [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`).
//!
//! This crate also provides a [`joint::JointPrefixMap`] and [`joint::JointPrefixSet`] that contains
//! two tables, one for IPv4 and one for IPv6.
//!
//! # Comparison with related projects
//!
//! [`ip_network_table-deps-treebitmap`](https://crates.io/crates/ip_network_table-deps-treebitmap)
//! provides an IP lookup table, similar to [`PrefixMap`].
//!
//! The following compares the two approaches in the case of *dense* or *sparse* maps. Each test
//! case performs 100'000 modifications or lookups. However, the dense cases randomly picks any IPv4
//! address, while the sparse case only pick 20 different IPv4 addresses. See `benches/benchmark.rs`
//! for more details.
//!
//! | Operation       | Mode   | `PrefixMap` | `treebitmap` | factor |
//! |-----------------|--------|-------------|--------------|--------|
//! | Insert & Remove | dense  | **31.78ms** | 47.52ms      | ~1.5x  |
//! | Lookup          | dense  | 32.36ms     | **8.409ms**  | ~0.25x |
//! | Insert & Remove | sparse | **6.645ms** | 7.329ms      | ~1.1x  |
//! | Lookup          | sparse | **8.394ms** | 12.30ms      | ~1.5x  |
//!
//!
//! In addition, `prefix-trie` includes a [`PrefixSet`] analogous to `std::collections::HashSet`,
//! including union, intersection and difference operations that are implemented as simultaneous
//! tree traversals. Further, `prefix-trie` has an interface similar to `std::collections`, and
//! offers a general longest-prefix match that is not limited to individual addresses. Finally,
//! `prefix-trie` allows you to (mutably) borrow a sub-trie using views.
//!
//! # Description of the Tree
//!
//! The tree is structured as follows: Each node consists of a prefix, a container for a potential
//! value (`Option`), and two optional children. Adding a new child, or traversing into the tree is
//! done as follows: we look at the most significant bit that is **not** part of the prefix
//! itself. If it is not set, then we take the left branch, and otherwise, we take the right one.
//!
//! # Traversals
//!
//! Any iteration over all elements in the tree is implemented as a graph traversal that will yield
//! elements in lexicographic order.
//!
//! The library offers set operations of different maps or sets. We implement a union, intersection,
//! difference, and covering_difference. These iterators are implemented using simultaneous tree
//! traversals. They will yield elements in lexicographic order. Whenever appropriate, the yielded
//! items will also include the longest prefix match.
//!
//! # [`TrieView`] and [`TrieViewMut`]
//!
//! You can create a view of a (sub)-trie. Such a view has an any node as its root. Any operations
//! on that view will only traverse that node and all its children. You can iterate over all
//! children, search in that sub-trie, and perform set operations (union, intersection, difference,
//! or the covering difference) on them.
//!
//! A view can point to one of three possible nodes:
//! - A node in the tree that is actually present in the map,
//! - A branching node that does not exist in the map, but is needed for the tree structure (or that
//!   was deleted using the function `remove_keep_tree`)
//! - A virtual node that does not exist as a node in the tree. This is only the case if you call
//!   [`TrieView::find`] or [`AsView::view_at`] with a node that is not present in the tree, but
//!   that contains elements present in the tree. Virtual nodes are treated as if they are actually
//!   present in the tree as branching nodes.
//!
//! # Operations on the tree
//!
//! There are several operations one can do on the tree. Regular inserts are handled using the
//! `Entry` structure. An `Entry` is a pointer to a location in the tree to either insert a value or
//! modify an existing one. Removals however are different.
//!
//! The following are the computational complexities of the functions, where `n` is the number of
//! elements in the tree.
//!
//! | Operation                                  | Complexity |
//! |--------------------------------------------|------------|
//! | `entry`, `insert`                          | `O(log n)` |
//! | `remove`, `remove_keep_tree`               | `O(log n)` |
//! | `remove_children` (calling `drop` on `T`)  | `O(n)`     |
//! | `get`, `get_lpm`, `get_mut`                | `O(log n)` |
//! | `retain`                                   | `O(n)`     |
//! | `clear` (calling `drop` on `T`)            | `O(n)`     |
//! | Operations on [`map::Entry`]               | `O(1)`     |
//! | `len` and `is_empty`                       | `O(1)`     |
//! | `union`, `intersection`, `difference`, ... | `O(n)`     |
//!
//! There are three kinds of removals you! can do:
//!
//! - [`PrefixMap::remove`] will remove an entry from the tree and modify the tree structure as if
//!   the value was never inserted before. [`PrefixMap::remove`] will always exactly revert the
//!   operation of [`PrefixMap::insert`]. When only calling this function to remove elements, you
//!   are guaranteed that the tree structure is indistinguishable to a different tree where you
//!   only inserted elements.
//! - [`PrefixMap::remove_children`] will remove all entries that are contained within the given
//!   prefix. This operation will search for the node with the shortest prefix length that is
//!   contained within the given prefix and remove it, including all of its children.
//! - [`PrefixMap::remove_keep_tree`] will not change anything in the tree structure. It will only
//!   remove a value from a node. As soon as you call `remove_keep_tree` once on a tree structure,
//!   the tree will no longer be optimal.
//!
//! # TODO
//!
//! Migrate to a TreeBitMap, described by
//! [W. Eatherton, Z. Dittia, G. Varghes](https://doi.org/10.1145/997150.997160).

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

mod fmt;
#[cfg(test)]
mod fuzzing;
pub(crate) mod inner;
mod prefix;
#[cfg(feature = "serde")]
mod serde;
#[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, AsViewMut, TrieView, TrieViewMut};

#[inline(always)]
pub(crate) fn to_right<P: Prefix>(branch_p: &P, child_p: &P) -> bool {
    child_p.is_bit_set(branch_p.prefix_len())
}