/rust/registry/src/index.crates.io-1949cf8c6b5b557f/prefix-trie-0.7.0/src/lib.rs
Line | Count | Source |
1 | | //! This crate provides a simple prefix tree for IP prefixes. Any lookup performs longest-prefix |
2 | | //! match. This crate supports both IPv4 and IPv6 (from either [ipnet](https://docs.rs/ipnet/2.10.0) |
3 | | //! or [ipnetwork](https://crates.io/crates/ipnetwork) or [cidr](https://crates.io/crates/cidr)). |
4 | | //! It also supports any tuple `(R, u8)`, where `R` is any unsigned primitive integer (`u8`, `u16`, |
5 | | //! `u32`, `u64`, `u128`, or `usize`). |
6 | | //! |
7 | | //! # Comparison with related projects |
8 | | //! |
9 | | //! [`ip_network_table-deps-treebitmap`](https://crates.io/crates/ip_network_table-deps-treebitmap) |
10 | | //! provides an IP lookup table, similar to [`PrefixMap`]. |
11 | | //! |
12 | | //! The following compares the two approaches in the case of *dense* or *sparse* maps. Each test |
13 | | //! case performs 100'000 modifications or lookups. However, the dense cases randomly picks any IPv4 |
14 | | //! address, while the sparse case only pick 20 different IPv4 addresses. See `benches/benchmark.rs` |
15 | | //! for more details. |
16 | | //! |
17 | | //! | Operation | Mode | `PrefixMap` | `treebitmap` | factor | |
18 | | //! |-----------------|--------|-------------|--------------|--------| |
19 | | //! | Insert & Remove | dense | **31.78ms** | 47.52ms | ~1.5x | |
20 | | //! | Lookup | dense | 32.36ms | **8.409ms** | ~0.25x | |
21 | | //! | Insert & Remove | sparse | **6.645ms** | 7.329ms | ~1.1x | |
22 | | //! | Lookup | sparse | **8.394ms** | 12.30ms | ~1.5x | |
23 | | //! |
24 | | //! |
25 | | //! In addition, `prefix-trie` includes a [`PrefixSet`] analogous to `std::collections::HashSet`, |
26 | | //! including union, intersection and difference operations that are implemented as simultaneous |
27 | | //! tree traversals. Further, `prefix-trie` has an interface similar to `std::collections`, and |
28 | | //! offers a general longest-prefix match that is not limited to individual addresses. Finally, |
29 | | //! `prefix-trie` allows you to (mutably) borrow a sub-trie using views. |
30 | | //! |
31 | | //! # Description of the Tree |
32 | | //! |
33 | | //! The tree is structured as follows: Each node consists of a prefix, a container for a potential |
34 | | //! value (`Option`), and two optional children. Adding a new child, or traversing into the tree is |
35 | | //! done as follows: we look at the most significant bit that is **not** part of the prefix |
36 | | //! itself. If it is not set, then we take the left branch, and otherwise, we take the right one. |
37 | | //! |
38 | | //! # Traversals |
39 | | //! |
40 | | //! Any iteration over all elements in the tree is implemented as a graph traversal that will yield |
41 | | //! elements in lexicographic order. |
42 | | //! |
43 | | //! The library offers set operations of different maps or sets. We implement a union, intersection, |
44 | | //! difference, and covering_difference. These iterators are implemented using simultaneous tree |
45 | | //! traversals. They will yield elements in lexicographic order. Whenever appropriate, the yielded |
46 | | //! items will also include the longest prefix match. |
47 | | //! |
48 | | //! # [`TrieView`] and [`TrieViewMut`] |
49 | | //! |
50 | | //! You can create a view of a (sub)-trie. Such a view has an any node as its root. Any operations |
51 | | //! on that view will only traverse that node and all its children. You can iterate over all |
52 | | //! children, search in that sub-trie, and perform set operations (union, intersection, difference, |
53 | | //! or the covering difference) on them. |
54 | | //! |
55 | | //! A view can point to one of three possible nodes: |
56 | | //! - A node in the tree that is actually present in the map, |
57 | | //! - A branching node that does not exist in the map, but is needed for the tree structure (or that |
58 | | //! was deleted using the function `remove_keep_tree`) |
59 | | //! - A virtual node that does not exist as a node in the tree. This is only the case if you call |
60 | | //! [`TrieView::find`] or [`AsView::view_at`] with a node that is not present in the tree, but |
61 | | //! that contains elements present in the tree. Virtual nodes are treated as if they are actually |
62 | | //! present in the tree as branching nodes. |
63 | | //! |
64 | | //! # Operations on the tree |
65 | | //! |
66 | | //! There are several operations one can do on the tree. Regular inserts are handled using the |
67 | | //! `Entry` structure. An `Entry` is a pointer to a location in the tree to either insert a value or |
68 | | //! modify an existing one. Removals however are different. |
69 | | //! |
70 | | //! The following are the computational complexities of the functions, where `n` is the number of |
71 | | //! elements in the tree. |
72 | | //! |
73 | | //! | Operation | Complexity | |
74 | | //! |--------------------------------------------|------------| |
75 | | //! | `entry`, `insert` | `O(log n)` | |
76 | | //! | `remove`, `remove_keep_tree` | `O(log n)` | |
77 | | //! | `remove_children` (calling `drop` on `T`) | `O(n)` | |
78 | | //! | `get`, `get_lpm`, `get_mut` | `O(log n)` | |
79 | | //! | `retain` | `O(n)` | |
80 | | //! | `clear` (calling `drop` on `T`) | `O(n)` | |
81 | | //! | Operations on [`map::Entry`] | `O(1)` | |
82 | | //! | `len` and `is_empty` | `O(1)` | |
83 | | //! | `union`, `intersection`, `difference`, ... | `O(n)` | |
84 | | //! |
85 | | //! There are three kinds of removals you! can do: |
86 | | //! |
87 | | //! - [`PrefixMap::remove`] will remove an entry from the tree and modify the tree structure as if |
88 | | //! the value was never inserted before. [`PrefixMap::remove`] will always exactly revert the |
89 | | //! operation of [`PrefixMap::insert`]. When only calling this function to remove elements, you |
90 | | //! are guaranteed that the tree structure is indistinguishable to a different tree where you |
91 | | //! only inserted elements. |
92 | | //! - [`PrefixMap::remove_children`] will remove all entries that are contained within the given |
93 | | //! prefix. This operation will search for the node with the shortest prefix length that is |
94 | | //! contained within the given prefix and remove it, including all of its children. |
95 | | //! - [`PrefixMap::remove_keep_tree`] will not change anything in the tree structure. It will only |
96 | | //! remove a value from a node. As soon as you call `remove_keep_tree` once on a tree structure, |
97 | | //! the tree will no longer be optimal. |
98 | | //! |
99 | | //! # TODO |
100 | | //! |
101 | | //! Migrate to a TreeBitMap, described by |
102 | | //! [W. Eatherton, Z. Dittia, G. Varghes](https://doi.org/10.1145/997150.997160). |
103 | | |
104 | | #![allow(clippy::collapsible_else_if)] |
105 | | #![deny(missing_docs)] |
106 | | |
107 | | mod fmt; |
108 | | #[cfg(test)] |
109 | | mod fuzzing; |
110 | | pub(crate) mod inner; |
111 | | mod prefix; |
112 | | #[cfg(feature = "serde")] |
113 | | mod serde; |
114 | | #[cfg(feature = "ipnet")] |
115 | | #[cfg(test)] |
116 | | mod test; |
117 | | |
118 | | pub mod map; |
119 | | pub mod set; |
120 | | pub mod trieview; |
121 | | |
122 | | pub use map::PrefixMap; |
123 | | pub use prefix::Prefix; |
124 | | pub use set::PrefixSet; |
125 | | pub use trieview::{AsView, AsViewMut, TrieView, TrieViewMut}; |
126 | | |
127 | | #[inline(always)] |
128 | 0 | pub(crate) fn to_right<P: Prefix>(branch_p: &P, child_p: &P) -> bool { |
129 | 0 | child_p.is_bit_set(branch_p.prefix_len()) |
130 | 0 | } Unexecuted instantiation: prefix_trie::to_right::<ipnet::ipnet::Ipv4Net> Unexecuted instantiation: prefix_trie::to_right::<ipnet::ipnet::Ipv6Net> Unexecuted instantiation: prefix_trie::to_right::<_> |