所有完整实现代码:match

CIDR

我们知道cidr对ip匹配时,只要cidr的mask长度的前几位与要匹配的ip相同,则可以说匹配成功.

假设有一个cidr为128.0.0.1/24转换为二进制 1000 0000.0000 0000.0000 0000.0000 0001/24可以知道要匹配ip的前24为与cidr的前24(1000 0000.0000 0000.0000 0000)位相同则匹配成功假设有一个ip 128.0.0.128 二进制为 1000 0000.0000 0000.0000 0000.1000 0000可以看到前24位与cidr相同 则匹配成功

域名

域名就比较简单了,直接按点分割就行了

前缀树

通过上述规则我们可以使用前缀树实现CIDR对ip的匹配

            root           /    \          0      1         / \    / \        0   1  0   1       /    当ip匹配到此处,此处已无任何子树,且是某一cidr的末尾时则匹配成功    若此处节点为null(golang为nil)且不是某一cidr的末尾时则匹配失败

域名的前缀树相同,只不过域名不再是只有0和1,而且在匹配的时候还需要跳过前面的那些前缀.

        +---------+        |  root   |        +---------+       /     /      \facebook   google   twitter  ...  /        /   \       \com      com   mail    com   ...                \               com 在对域名匹配时如对 www.play.google.com匹配:    没有www  跳过    没有play 跳过    有google 继续    有com 且 域名已为最后一个节点 -> 判断trie中是否为最后的一个子树 -> 是 -> 匹配成功 这里有一个明显的问题	比如我们同时插入了music.126.com和163.com	然后我们需要查询music.163.com是否被匹配	是不是发现了问题,无法被匹配,因为包含music,我们会匹配到music.126.com这条线,而不是163.com 这里有个很简单的解决方法,就是把域名倒过来插入,倒过来匹配,就跟JAVA包名那样        +---------+        |  root   |        +---------+             /            com        ...           /   \         163   126     ...                 \                music 这样就能被正确匹配了,而且会缩短时间,不会去完整匹配整个域名,只匹配后面有的就行了

trie树类似上述结构

trie树节点我们可以这样写