UriMatcher 的 match 匹配算法

前言

我们知道创建一个内容提供器 Content Provider 的时候，需要继承 ContentProvider 重写一些方法。外部程序使用我们的内容提供器必须传入一个 URI 对象，一个标准的内容 URI 写法是这样的：

content://cn.blogss.android_study/table1

除此之外，还有以下几种形式：

content://cn.blogss.android_study/table1/1, 调用方期望访问这个应用 table1 表中 id 为 1 的数据
content://cn.blogss.android_study/*, 一个能匹配任意表的内容 URI, (*表示匹配任意长度的任意字符)
content://cn.blogss.android_study/table1/#, 一个能匹配 table1 表中任意一行数据的的内容 URI, (#表示匹配任意长度的数字)

它主要由两部分组成：authority 和 path 。authority 是用于对不同应用程序做区分的。path 则是用于对同一应用程序中不同的表做区分的。通常都会添加到 authority 的后面。如上，cn.blogss.android_study 是应用程序名，table1 是表名。

使用者传入对应的 URI 后，我们需要借助 UriMatcher 的 match(Uri uri) 方法对该 URI 进行匹配，下面对此过程进行分析。

UriMatcher 类结构

addURI 过程

分析源码之前，先上一张存储 URI 的数据结构图。便能更好的理解 addURI 的过程。

public void addURI(String authority, String path, int code)
{
    /*自定义的 code 值必须 >= 0，否则抛出异常*/
    if (code < 0) {
        throw new IllegalArgumentException("code " + code + " is invalid: it must be positive");
    }

    String[] tokens = null;
    if (path != null) {
        String newPath = path;
        // Strip leading slash if present.
        /*
         * 移除字符串头的斜杠 '/'
         * 即 path 的规范传值是不需要以 '/' 开头的，即使你传入的 path 以 '/'开头，该处也会过滤掉
         */
        if (path.length() > 1 && path.charAt(0) == '/') {
            newPath = path.substring(1);
        }
        /*将 newPath 分割为数组*/
        tokens = newPath.split("/");
    }

    /*计算 token 数组的长度，如果传入的 path 是个空字符串，则 numTokens 的长度赋值为 0*/
    int numTokens = tokens != null ? tokens.length : 0;
    UriMatcher node = this;
    /*遍历 tokens 数组，将 tokens 数组的值按层级依次放入 mchildren 中*/
    for (int i = -1; i < numTokens; i++) {/**/
        /*首先处理 authority，i=-1时， token 的值为 authority*/
        String token = i < 0 ? authority : tokens[i];
        ArrayList<UriMatcher> children = node.mChildren;
        int numChildren = children.size();
        UriMatcher child;
        int j;
        /*
        * 遍历当前 UriMatcher 对象的 mChildren, mChildren 是个动态数组，存储的对象类型是UriMatcher
        * 如果当前遍历的 mChildren 中某个 UriMatcher 对象的 mText 与 当前的 token 值相等，说明当前层级该 token
        * 已经存在，直接进入下一个层级比对下一个 token 值
        */
        for (j = 0; j < numChildren; j++) {
            child = children.get(j);
            if (token.equals(child.mText)) {
                /*当前层级有该 token ，node 指向下一个层级*/
                node = child;
                break;
            }
        }

        /*当前层级该 token 不存在，添加这个 token 值*/
        if (j == numChildren) {
            // Child not found, create it
            child = createChild(token);
            node.mChildren.add(child);
            /*node 指向下一个层级*/
            node = child;
        }
    }
    node.mCode = code;
}

match 过程

理解了 addURI 的过程，再回头来看 match 过程就比较简单了。和常规的方法一样，使用两层 for 循环进行遍历，外层循环遍历所有的层级，内层循环遍历当前层级所有的token，进行匹配，时间复杂度是O(n^2)。

public int match(Uri uri){
    final List<String> pathSegments = uri.getPathSegments();
    final int li = pathSegments.size();

    UriMatcher node = this;

    if (li == 0 && uri.getAuthority() == null) {
        return this.mCode;
    }

    for (int i=-1; i<li; i++) {/*遍历所有层级*/
        String u = i < 0 ? uri.getAuthority() : pathSegments.get(i);
        ArrayList<UriMatcher> list = node.mChildren;
        if (list == null) {
            break;
        }
        node = null;
        int lj = list.size();
        /*
        * 遍历当前层级所有的token与当前传入的token进行匹配,匹配成功 node != null 并进入下一个层级
        * 匹配失败 node == null ,直接返回 -1,结束本方法。
        */
        for (int j=0; j<lj; j++) {
            UriMatcher n = list.get(j);
      which_switch:
            switch (n.mWhich) {
                case EXACT:
                    if (n.mText.equals(u)) {
                        node = n;
                    }
                    break;
                case NUMBER:
                    int lk = u.length();
                    for (int k=0; k<lk; k++) {
                        char c = u.charAt(k);
                        if (c < '0' || c > '9') {
                            break which_switch;
                        }
                    }
                    node = n;
                    break;
                case TEXT:
                    node = n;
                    break;
            }
            if (node != null) {
                break;
            }
        }
        if (node == null) {/*当前层级没有对应的token,匹配失败，返回-1*/
            return NO_MATCH;
        }
    }
    return node.mCode;
}