1 个不稳定版本
使用旧的 Rust 2015
| 0.5.0 | 2020 年 3 月 30 日 |
|---|
#1651 在 网络编程
90,479 每月下载量
用于 22 个 crate（直接使用 8 个）
87KB
2K SLoC
Tree-Bitmap：IPv4/IPv6 前缀的快速查找表
此 crate 提供了一种快速 IP 地址查找的数据结构。它旨在实现快速查找时间和合理的内存占用。
内部数据结构基于 W. Eatherton、Z. Dittia、G. Varghes 描述的 Tree-bitmap 算法。
文档
Rustdoc: https://docs.rs/ip_network_table-deps-treebitmap/
插图
一个示例插图，展示了一个表示包含 0.0.0.0/0 (foo)，10.0.0.0/8 (bar)，172.16.0.0/12 (baz) 和 192.168.0.0/16 (quux) 的路由表的 trie。
内部 trie 数据结构基础
Node 使用位图编码结果和子节点指针。
trie 节点在作为“结束节点”时可以编码最多 31 个结果，在作为正常/内部节点时可以编码 15 个结果和 16 个子树/子节点。
位图中每个位表示一个匹配模式
| 位 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 匹配 | * | 0* | 1* | 00* | 01* | 10* | 11* | 000* |
| 位 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|
| 匹配 | 001* | 010* | 011* | 100* | 101* | 110* | 111* | 结束节点位 |
这里最后一个位不表示模式。它表示此节点是否是“结束节点”。结束节点携带双倍的结果数量，但不能编码任何子指针。
| 位 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
|---|---|---|---|---|---|---|---|---|
| 匹配 | 0000* | 0001* | 0010* | 0011* | 0100* | 0101* | 0110* | 0111* |
| 位 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
|---|---|---|---|---|---|---|---|---|
| 匹配 | 1000* | 1001* | 1010* | 1011* | 1100* | 1101* | 1110* | 1111* |
结果值的存储位置是通过将基指针 result_ptr 和其位集中的位置相加来计算的。
如果末端节点位没有被设置，最后16位编码了指向子节点的指针。如果位N被设置，则表示存在具有段值N的子节点。子节点指针的计算方法是将基指针 child_ptr 和其位集中的位置相加。