V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
YahuiAn
V2EX  ›  问与答

各路大佬们!单 IP, IP 段, CIDR 之间如果做集合运算。

  •  
  •   YahuiAn · 2020-05-22 19:22:23 +08:00 · 1463 次点击
    这是一个创建于 1627 天前的主题,其中的信息可能已经有所发展或是发生改变。

    用户输入支持如下格式:

    10.0.17.35

    192.168.1.1/23

    www.baidu.com

    192.37.3.3-192.168.39.39

    现在有一个黑名单功能,也支持如上的形式,想问问这两个集合如何高效的去重呢?

    😝

    第 1 条附言  ·  2020-06-02 17:50:19 +08:00

    小弟太菜了,在github上找了一个函数,https://github.com/cilium/cilium/blob/master/pkg/ip/ip.go#L122

    5 条回复    2020-05-23 06:43:51 +08:00
    GeruzoniAnsasu
        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 跟插入流程几乎一样的

    当时没有去重合并完还要导出合并结果的需求
    GeruzoniAnsasu
        2
    GeruzoniAnsasu  
       2020-05-22 20:03:26 +08:00 via Android
    还有一种方式是直接把 ip 地址算成线性空间,每个区间有左右界,合并的时候先按左界排序,然后判断
    下一个区间的左界有没有落在前一个区间中,如果在,那么区间右界设成下一个区间右界,如果否,那么第一个区间已处理完毕,可以处理 23 区间
    wbrobot
        3
    wbrobot  
       2020-05-22 21:01:35 +08:00
    ip2long,然后算数
    msg7086
        4
    msg7086  
       2020-05-23 00:36:50 +08:00
    听上去就是个和 trie 差不多的结构。
    singerll
        5
    singerll  
       2020-05-23 06:43:51 +08:00 via Android
    转换为 10 进制?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5747 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 03:27 · PVG 11:27 · LAX 19:27 · JFK 22:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.