场景
在公司的实际业务需求中，碰到了下面这个问题。所以本篇博文算是记录，以便后续查阅。
如下面代码所示，在shiro环境中，将一部分路由配置相关的权限规则。现在有一个需求是，给一个任意的路由，要根据它去判断它是否在权限规则中有配置。
例如: 在下面配置好的规则的前提下，/xx/yy 肯定 属于 /xx
public static boolean whetherPattern(String url, List auth) {
String[] urlStrings = url.split("/");
for (String pattern : auth) {
if (pattern.equals(url)) {
return true;
}
String[] patternStrings = pattern.split("/");
int length = urlStrings.length >= patternStrings.length ? urlStrings.length : patternStrings.length;
for (int i = 1; i < length; i ++) {
if (urlStrings.length <= i || patternStrings.length <= i) {
break;
}
if (patternStrings[i].equals("*") || patternStrings[i].equals("**")) {
return true;
}
if (! patternStrings[i].equals(urlStrings[i])) {
break;
}
}
}
return false;
}
二、前缀树算法实现路由匹配
对于这颗树，它需要具备以下几个特点。1、确认是否是树的终点 2、记录权限配置的值 3、包含所有的子节点
需要注意的一点是就算到了树的终点位置，它也不一定是叶子节点。例如配置了路由/a/b 和 /a/b/c/d不同的权限规则，虽然这里b是终点，但不是叶子节点。
2.1 树的结构
TreeNode.java
class TreeNode {
// 当前路径值
private String path;
// 路由终点
private boolean last;
// 所有子节点
private Map childMap;
public TreeNode(String path, boolean last, Map childMap) {
this.path = path;
this.childMap = childMap;
this.last = last;
}
public String getPath() {
return path;
}
public void setPath(String path) {
this.path = path;
}
public boolean isLast() {
return last;
}
public void setLast(boolean last) {
this.last = last;
}
public Map getChildMap() {
return childMap;
}
public void setChildMap(Map childMap) {
this.childMap = childMap;
}
}
2.2 构造树
构造方法是buildTrie(Map pattern) ，这里把路由"/"也考虑进去了。代码中维护了线程安全的单个对象instance
最后的效果图如下
PrefixTreeUtil.java
public class PrefixTreeUtil {
public static TreeNode instance;
public static synchronized TreeNode getInstance() {
if (instance == null) {
synchronized (PrefixTreeUtil.class) {
if (instance == null) {
instance = new TreeNode("/", false, null);
}
}
}
return instance;
}
public static void buildTrie(Map pattern) {
for (String str : pattern.keySet()) {
// 每次都重新获取一次根节点
TreeNode rootNode = getInstance();
String[] strings = getSpitUrl(str);
// 路径为 / 的情况
if (str.equals("/")) {
rootNode.setAuthValue(pattern.get(str));
rootNode.setLast(true);
} else {
// 对指定路径进行切割
for (int i = 1; i < strings.length; i ++) {
// 获取所有叶子节点封装对象
Map map = rootNode.getChildMap();
if (map != null && map.containsKey(strings[i])) {
rootNode = map.get(strings[i]);
if (i == strings.length - 1) {
rootNode.setLast(true);
rootNode.setAuthValue(pattern.get(str));
}
} else {
TreeNode sonNode = new TreeNode(strings[i], false, null);
if (rootNode.getChildMap() == null) {
rootNode.setChildMap(new HashMap());
}
rootNode.getChildMap().put(strings[i], sonNode);
if (i == strings.length - 1) {
sonNode.setLast(true);
sonNode.setAuthValue(pattern.get(str));
} else {
sonNode.setLast(false);
}
rootNode = sonNode;
}
}
}
}
}
private static String[] getSpitUrl(String url) {
if (url == null || url.equals("")) {
return null;
}
if (url.equals("/")) {
return new String[]{"/"};
}
return url.split("/");
}
}
2.3 深度优先的前缀树算法
matchUrl(TreeNode treeNode, String url)中的参数treeNode是2.2中构建好的那棵树。url是需要去匹配的路由。路由匹配规则包含了多种情况,关键地方都有注释。特殊的包括路由"/"、"/**"、“a/b"和”/a/b/*"的组合
从算法中可以看出是深度优先且按词匹配。
1、如果树的最深处且树的终点标记是true和路由的终点匹配上，则代码全匹配。如：路由/a/b去匹配/a/b
2、如果路由没有走完的情况，而树走完或者当前树的叶子不匹配当前路由节点的值时，则返回父节点去通配符情况，如果还是匹配补上，则循环该操作。如:路由/a/b/c/d 去匹配 /a/b/**
3、如果路由走完，但是不是树的终点。如：路由/a/b 去匹配 /a/b/c
4、特殊情况，路由直接是"/"
…
public static String matchUrl(TreeNode treeNode, String url) {
if (treeNode == null || url == null) {
return null;
}
if (url.equals("/")) {
if (treeNode.isLast()) {
return treeNode.getAuthValue();
}
} else {
Stack stack = new Stack();
stack.push(treeNode);
// 用路径值匹配，如果路径值匹配不到，则之后全部用 * 或 **
boolean wordMatch = false;
int i = 1;
String[] paths = getSpitUrl(url);
while (treeNode.getChildMap() != null) {
Map childMap = treeNode.getChildMap();
if (wordMatch || i == paths.length) {
// 这里加判断的是针对 /* 这一种情况
if (stack.isEmpty()) {
if (fullMatch(childMap)) {
return getUrlAuthValue(childMap);
} else {
return null;
}
}
// 这里加 i != paths.length 是因为没有进行出栈的时候，这里会有bug,例如 /a/b 去匹配 /a/b/*
if(i != paths.length && fullMatch(childMap)) {
return getUrlAuthValue(childMap);
}
wordMatch = true;
treeNode = stack.pop();
continue;
}
TreeNode sonNode = childMap.get(paths[i]);
if (sonNode != null) {
// 代表完全匹配
if (sonNode.isLast() && i == paths.length - 1) {
return childMap.get(paths[i]).getAuthValue();
}
else if (sonNode.isLast() || i == paths.length - 1) {
if(fullMatch(childMap)) {
return getUrlAuthValue(childMap);
}
// 这里判断的原因是防止 配置的路径是 /a/b /a/b/* 这样子 /a/b/c/d 去匹配会得到错误的结果
if (sonNode.getChildMap() == null) {
treeNode = stack.pop();
wordMatch = true;
continue;
}
}
stack.push(sonNode);
treeNode = sonNode;
i ++;
} else {
if (! stack.isEmpty()) {
wordMatch = true;
treeNode = stack.pop();
}
}
}
}
return null;
}
private static boolean fullMatch(Map childMap) {
if (childMap == null) {
return false;
} else {
return (childMap.get("**") != null || childMap.get("*") != null);
}
}
private static String getUrlAuthValue(Map childMap) {
if (childMap == null) {
return null;
}
TreeNode treeNode = childMap.get("**") != null ? childMap.get("**") : childMap.get("*");
return treeNode.getAuthValue();
}
总结
整体实现并不难，就是先构建一棵树，然后利用算法去这颗树中搜索。这里需要给树维护单例对象，其目的是保证每个路径的起点一致，而且可复用。
作为程序员来讲，能将所学的知识运用起来，就是最快乐的事情了。最近深有感触的就算，要多去学习，广泛的学习，当时不一定用得上，后面可能帮大忙。
