用户输入支持如下格式:
10.0.17.35
192.168.1.1/23
192.37.3.3-192.168.39.39
现在有一个黑名单功能,也支持如上的形式,想问问这两个集合如何高效的去重呢?
😝
小弟太菜了,在github上找了一个函数,https://github.com/cilium/cilium/blob/master/pkg/ip/ip.go#L122
1
GeruzoniAnsasu 2020-05-22 19:57:53 +08:00 via Android
首先不考虑域名和 url
我当时的实现大概这样 一个 - 指定的范围可以解析成若干个 cidr 或 ip 那现在只需要考虑 cidr 一种情况( ip 可以看做 /32 ) 用二叉 trie 来存这些 cidr,在深度为 N 的节点有一个 cidr 对象表示这个 cidr 是 /N 如果某个节点左右子树都存在则递归向上合并节点 插入过程中途遇到某个节点说明这节点已经包含了待插入地址,跳过 然后就没有去重这一说了,匹配就是走这个 trie 跟插入流程几乎一样的 当时没有去重合并完还要导出合并结果的需求 |
2
GeruzoniAnsasu 2020-05-22 20:03:26 +08:00 via Android
还有一种方式是直接把 ip 地址算成线性空间,每个区间有左右界,合并的时候先按左界排序,然后判断
下一个区间的左界有没有落在前一个区间中,如果在,那么区间右界设成下一个区间右界,如果否,那么第一个区间已处理完毕,可以处理 23 区间 |
3
wbrobot 2020-05-22 21:01:35 +08:00
ip2long,然后算数
|
4
msg7086 2020-05-23 00:36:50 +08:00
听上去就是个和 trie 差不多的结构。
|
5
singerll 2020-05-23 06:43:51 +08:00 via Android
转换为 10 进制?
|