[](https://github.com/tiborschneider/prefix-trie/actions)
[](https://codecov.io/gh/tiborschneider/prefix-trie)
[](https://crates.io/crates/prefix-trie)
[](https://crates.io/crates/prefix-trie)
[](https://docs.rs/prefix-trie/latest/prefix_trie/)
[](https://crates.io/crates/prefix-trie)
[](https://crates.io/crates/prefix-trie)
# 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.
| `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)` where `m` is the removed subtrie size |
| 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.
## Comparison with related projects
[`ip_network_table-deps-treebitmap`](https://crates.io/crates/ip_network_table-deps-treebitmap)
provides the same data structure (in the following called `TreeBitMap`) and uses a similar
algorithm. The following table compares the performance and memory of the two libraries, and
relates them to the `HashMap` and `BTreeMap` of the standard library. Throughput is reported
relative to `HashMap` (1.00x = HashMap speed), with absolute throughput in parentheses. **Bold**
marks the fastest implementation per row. See `benches/benchmark.rs` for details.
All benchmarks use IPv4 prefixes from a RIPE RIS peer snapshot (1,042,024 IPv4 prefixes or
246,174 IPv6 prefixes). See `benches/benchmark.rs` and `benches/memory.rs` for details. The
benchmark results below were obtained on an AMD EPYC server.
| *Lookup* | | | | |
| -> Random access | | | | |
| ---> IPv4 | 1.00x (7.4 Mops) | **1.92x (14.2 Mops)** | 1.15x (8.5 Mops) | 0.46x (3.4 Mops) |
| ---> IPv6 | **1.00x (11.0 Mops)** | 0.97x (10.7 Mops) | 0.58x (6.4 Mops) | 0.45x (4.9 Mops) |
| -> RIS updates | | | | |
| ---> IPv4 | 1.00x (17.5 Mops) | **1.69x (29.5 Mops)** | 0.78x (13.7 Mops) | 0.47x (8.2 Mops) |
| ---> IPv6 | **1.00x (24.8 Mops)** | 0.63x (15.7 Mops) | 0.33x (8.2 Mops) | 0.32x (7.9 Mops) |
| *Insert & Remove* | | | | |
| -> Random access | | | | |
| ---> IPv4 | 1.00x (7.4 Mops) | **1.04x (7.7 Mops)** | 0.89x (6.6 Mops) | 0.43x (3.2 Mops) |
| ---> IPv6 | **1.00x (10.8 Mops)** | 0.48x (5.2 Mops) | 0.44x (4.7 Mops) | 0.39x (4.3 Mops) |
| -> RIS updates | | | | |
| ---> IPv4 | **1.00x (17.1 Mops)** | 0.88x (15.0 Mops) | 0.71x (12.2 Mops) | 0.47x (8.0 Mops) |
| ---> IPv6 | **1.00x (25.0 Mops)** | 0.33x (8.3 Mops) | 0.29x (7.3 Mops) | 0.31x (7.7 Mops) |
| *Create* | | | | |
| -> Random order | | | | |
| ---> IPv4 | 1.00x (7.8 Mops) | **1.13x (8.8 Mops)** | 0.95x (7.4 Mops) | 0.55x (4.3 Mops) |
| ---> IPv6 | **1.00x (11.4 Mops)** | 0.52x (5.9 Mops) | 0.43x (4.9 Mops) | 0.42x (4.8 Mops) |
| -> Sorted order | | | | |
| ---> IPv4 | 1.00x (10.3 Mops) | **1.45x (14.9 Mops)** | 1.04x (10.7 Mops) | 0.85x (8.8 Mops) |
| ---> IPv6 | **1.00x (11.7 Mops)** | 0.70x (8.2 Mops) | 0.55x (6.5 Mops) | 0.51x (6.0 Mops) |
| -> Scattered order | | | | |
| ---> IPv4 | 1.00x (10.3 Mops) | **1.02x (10.5 Mops)** | 0.76x (7.8 Mops) | 0.34x (3.4 Mops) |
| ---> IPv6 | **1.00x (11.6 Mops)** | 0.59x (6.9 Mops) | 0.47x (5.5 Mops) | 0.46x (5.4 Mops) |
| **Memory** | | | | |
| -> IPv4 | 26.0 mB | 12.0 mB (set: 4.0 mB) | **11.0 mB** | 16.4 mB |
| -> IPv6 | 12.5 mB | 6.0 mB (set: 4.0 mB) | **4.3 mB** | 8.1 mB |
Besides better performance than the `TreeBitMap`, `prefix-trie` includes a `PrefixSet` analogous
to `std::collections::HashSet`. Set operations are exposed through composable trie views, so
operations such as union, intersection, difference, covering union, and covering difference can
be combined without building temporary maps. `prefix-trie` has an interface similar to
`std::collections`, and its longest-prefix matching is not limited to individual host addresses.
## Migrate to version 0.9
Releases up to 0.8.4 used a binary tree representation.
With version 0.9, this crate migrated to a TreeBitMap, described by
[W. Eatherton, Z. Dittia, and G. Varghes](https://dl.acm.org/doi/10.1145/997150.997160). This
yields significant performance improvements (~8x faster inserts & lookups for all IPv4 addresses
in internet routing tables) and memory reduction (~4x less).
However, this also comes with significant changes in the interface:
- Prefixes are reconstructed from the tree location and no longer stored.
Consequently, information in the host part of an address is no longer maintained.
Additionally, the function yields prefixes by value instead of by reference.
If you wish to store the host-bits as well, consider constructing a type `PrefixMap<P, (P, T)>`.
- Mutable views of the tree can no longer modify the tree structure (to maintain memory safety).
This is because one can construct two mutable views pointing to branches within the same
multi-bit node.
- Thanks to bitmaps, set operations can now be chained (as we can define a common interface for
them to return their bitmaps).