所有完整实现代码: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的匹配

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

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

在对域名匹配时，如对 www.play.google.com 匹配：

没有 www，跳过
没有 play，跳过
有 google，继续
有 com 且域名已为最后一个节点，判断trie中是否为最后的一个子树；是则匹配成功

这里有一个明显的问题：
比如我们同时插入了 music.126.com 和 163.com，然后查询 music.163.com 是否被匹配，无法被匹配。因为包含 music，会匹配到 music.126.com 这条线，而不是 163.com。

这里有个很简单的解决方法，就是把域名倒过来插入、倒过来匹配，就跟 JAVA 包名那样。

这样就能被正确匹配了，而且会缩短时间，不会去完整匹配整个域名，只匹配后面有的就行了。

trie树类似上述结构

trie树节点可以这样表示：