web框架-前缀路由树

极客兔兔的web框架，该框架是参考gin的造轮子项目。前缀路由树这篇注释太少，不易于理解，个人写了写自己的理解。

树结构

// 前缀路由树-树节点
type node struct {
    pattern  string  // 待匹配路由 /p/:lang
    part     string  // 路由的一部分 :lang，或者叫该节点存储的子路由好一点,在路由中是以 / 字符分隔的最小单位
    children []*node // 子节点
    isWild   bool    //是否精确匹配，part 含有 : 或 * 时为true，否则为false
}

注册路由

匹配子节点的方法，可以先看下面的insert方法再倒回来看

// 匹配成功的节点，用于插入；插入时只会有一个节点的part匹配
func (n *node) matchChild(part string) *node {
    // 遍历节点的子节点，子节点的part与要匹配的part相同
    for _, child := range n.children {
        if child.part == part || child.isWild {
            //返回匹配的节点
            return child
        }
    }
    return nil
}

插入节点的方法

// 注册路由规则
// 对pattern解析，以 / 为分隔符分解为 parts 数组，递归插入路由树，height为插入树的高度
// 例: pattern   -   "/p/:lang/doc"
//  parts   -   []string{“p”,“lang”,“doc”}
func (n *node) insert(pattern string, parts []string, height int) {
    // n节点所在树的高度与分解的part数是否相等，即判断 part 是否全部插入完毕
    if len(parts) == height {
        // 只有最后一个节点才会设置pattern，用于查询时匹配，这之前的节点该pattern字段均为空
        // 确保只有相同层级的相同part才能匹配
        n.pattern = pattern
        return
    }
    part := parts[height]
    // 在子节点中查找匹配 part 的第一个节点，然后判断是否存在匹配 part的节点
    // 存在则将其作为子节点，继续下一步
    child := n.matchChild(part)
    if child == nil {
        // 不存在，则构建新节点，将part写入，根据该part第一个字符是否有:和*，设置isWild
        child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
        // 将该节点作为n节点的子节点插入树中
        n.children = append(n.children, child)
    }
    // 继续查找child的子节点，插入下一个part，直到把parts数组的part全部插入为止
    child.insert(pattern, parts, height+1)
}

查询路由

同样，你可以先看下面的search方法再倒回来看这个

// 所有匹配成功的节点，用于查找；与插入时匹配不同的是，有可能存在多个part能匹配的节点,例如动态路由 /:xxx
func (n *node) matchChildren(part string) []*node {
    nodes := make([]*node, 0)
    // 遍历节点的子节点，子节点的part与要匹配的part相同
    for _, child := range n.children {
        if child.part == part || child.isWild {
            nodes = append(nodes, child)
        }
    }
    // 返回所有匹配的节点
    return nodes
}

search方法

// 查询匹配路由
func (n *node) search(parts []string,height int)*node{
    // n节点所在树的高度与分解的part数相等，或n节点的part字段以字符 * 开头，则匹配完毕
    if len(parts)==height||strings.HasPrefix(n.part,"*"){
        // 注册路由插入该节点的最大高度并不是该层级，pattern字段为空，也无法匹配(详见insert方法的第一个if语句)
        if n.pattern==""{
            return nil
        }
        // 匹配到了，返回该节点
        return n
    }
    part:=parts[height]
    // 在n节点的子节点中查找所有与part匹配的节点
    chirldren:=n.matchChildren(part)

    for _,child:=range chirldren{
        // 继续递归查询子节点，匹配下一个part，直到parts数组的part完全匹配为止
        result:=child.search(parts,height+1)
        if result!=nil{
            return result
        }
    }
    return nil
}