domain-lookup-tree

概述

DomainLookupTree 是一种数据结构，它提供了带有通配符支持的域名查找匹配的高效实现。

此实现的必要条件

• 给定一个域名，确定它是否与树中的条目匹配
• 树中的条目数量可以无限增长
• 条目可以是绝对匹配，例如：www.google.com
• 条目可能是通配符条目，这通过在条目中提供前导点来表示，例如：.twitter.com, .en.wikipedia.org, .giggl.app
• 通配符条目不能嵌套

为了实现这一点，我们实现了一种简单的树状结构，它包含一个根结构，该结构包含一个节点向量。这些节点可以包含其他节点后代，并且也可以标记为 "通配符"，这意味着存在一个匹配该域名级别及其所有后代的规则。

如果在查找时域名包含比通配符匹配更深的段，它将继续遍历树，直到耗尽查找选项。到那时，如果未找到绝对匹配，将返回找到的最深通配符条目。

值得注意的是，在遍历树时，域名按顶级域到无限 n 级的顺序排序，或者换句话说，以反向顺序。这意味着如果在树中查找 "google.com"，它将按 "." 分割，反转向量，然后首先对 "com" 进行根节点查找，依此类推。

树遍历的故事 - 查找的故事：假设我们有一个包含条目 ".giggl.app" 的 DomainLookupTree，这意味着树看起来像这样

app
└── giggl [通配符]

请求对 "canary.giggl.app" 进行规则查找。首先，"app" 匹配，但它不是通配符，所以忽略它。我们现在检查 "app" 的后代以查找 "giggl" - 它匹配，并且是通配符匹配，所以我们将其存储在查找的上下文中。此查找现在将 100% 返回匹配，即使它不是绝对匹配。无论如何，我们现在检查 "giggl" 的后代以查找 "canary"，尽管它不存在，遍历结束。现在，我们没有找到绝对匹配，但我们在早期有一个通配符匹配 ".giggl.app"，所以我们成功从查找函数返回结果 ".giggl.app"。

用法

首先，将 domain-lookup-tree 添加到您的 Cargo.toml 中

[dependencies]
domain-lookup-tree = "0.1"

现在您可以导入和使用 domain_lookup_tree::DomainLookupTree 类型

extern crate domain_lookup_tree;
use domain_lookup_tree::DomainLookupTree;

let mut tree = DomainLookupTree::new();


// Insert some domains
tree.insert(".google.com"); // prefix with a dot to denote a wildcard entry
tree.insert("api.twitter.com");
tree.insert("phineas.io");

// Perform lookups

tree.lookup("www.google.com");
// => Some(".google.com")

tree.lookup("twitter.com");
// => None

tree.lookup("api.twitter.com");
// => Some("api.twitter.com")