10个版本
| 0.4.2 | 2024年7月3日 |
|---|---|
| 0.4.1 | 2024年5月21日 |
| 0.3.0 | 2024年3月10日 |
| 0.2.5 | 2024年1月11日 |
| 0.2.0 | 2022年12月30日 |
#406 in 网络编程
9,929 monthly downloads
在 5 crates (4 directly) 中使用
160KB
3K SLoC
Prefix-Trie
此Crate提供了一个简单的IP前缀前缀树。任何查找都执行最长前缀匹配。
与相关项目的比较
ip_network_table-deps-treebitmap提供了一个IP查找表，类似于PrefixMap。
以下比较了两种方法在密集或稀疏映射的情况下的情况。每个测试用例执行100,000次修改或查找。但是，密集情况随机选择任何IPv4地址，而稀疏情况只选择20个不同的IPv4地址。有关更多详细信息，请参阅benches/benchmark.rs。
| 操作 | 模式 | PrefixMap |
treebitmap |
因子 |
|---|---|---|---|---|
| 插入 & 删除 | 密集 | 31.78ms | 47.52ms | ~1.5x |
| 查找 | 密集 | 32.36ms | 8.409ms | ~0.25x |
| 插入 & 删除 | 稀疏 | 6.645ms | 7.329ms | ~1.1x |
| 查找 | 稀疏 | 8.394ms | 12.30ms | ~1.5x |
此外，prefix-trie包括一个类似于std::collections::HashSet的PrefixSet，包括并集、交集和差集操作，这些操作作为同时树遍历实现。此外，prefix-trie具有类似于std::collections的接口，并包括访问节点所有子节点的方法。最后，它提供了一个通用的最长前缀匹配，不仅限于单个地址。
树的描述
树的结构如下：每个节点由一个前缀、一个潜在值（Option的容器）和两个可选子节点组成。添加新子节点或遍历树的操作如下：我们查看不属于前缀本身的最重要位。如果没有设置，则选择左分支，否则选择右分支。
遍历
对树中所有元素的任何迭代都实现为图遍历，将产生字典序元素（PrefixMap的可变迭代除外）。这还包括对两个PrefixSet的并集、交集或差集的迭代，这些操作都是通过同时遍历树来实现的。此外，调用retain也将只遍历树一次，在遍历过程中删除元素。
树上的操作
可以在树上执行几个操作。常规插入使用Entry结构处理。一个Entry是指向树中位置的指针，用于插入值或修改现有值。但是删除操作有所不同。
以下函数的计算复杂度，其中n是树中元素的数量。
| 操作 | 复杂度 |
|---|---|
entry、insert |
O(log n) |
remove、remove_keep_tree |
O(log n) |
remove_children（在T上调用drop） |
O(n) |
get、get_lpm、get_mut |
O(log n) |
retain |
O(n) |
clear（在T上调用drop） |
O(n) |
map::Entry的操作 |
O(1) |
len和is_empty |
O(1) |
你可以进行三种删除操作
PrefixMap::remove将从树中删除一个条目并修改树结构，好像值从未插入过一样。PrefixMap::remove将始终恰好撤销PrefixMap::insert的操作。当你只调用此函数来删除元素时，你可以保证树结构与仅插入元素的另一棵树不可区分。PrefixMap::remove_children将删除包含在给定前缀中的所有条目。此操作将搜索包含在给定前缀中的具有最短前缀长度的节点，并删除它及其所有子节点。PrefixMap::remove_keep_tree不会改变树结构。它只会从一个节点中删除一个值。一旦在树结构上调用一次remove_keep_tree，树将不再是最优的。
待办事项
迁移到由W. Eatherton, Z. Dittia, G. Varghes描述的TreeBitMap。
依赖关系
~200–455KB