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

//! This crate provides a simple prefix tree for IP prefixes. Any lookup performs longest-prefix
//! match.
//!
//! # 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 (with the exception of mutable iteration of the
//! [`PrefixMap`]). This also includes the iteration over the union, intersection, or difference of
//! two [`PrefixSet`]s, which are implemented as simultaneous tree traversals. Further, calling
//! `retain` will also traverse the tree only once, removing elements during the traversal.
//!
//! # 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)`     |
//!
//! 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.

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

mod fmt;
mod prefix;
#[cfg(feature = "serde")]
mod serde;
#[cfg(test)]
mod test;

pub mod map;
pub mod set;

pub use map::PrefixMap;
pub use prefix::Prefix;
pub use set::PrefixSet;

#[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())
}