RouterCoreStd 实现

RouterCoreStd是使用Radix算法独立实现的高性能路由器，

Radix基础

RouterCoreStd是基于基数树(Radix)实现，压缩前缀树，是一种更节省空间的Trie（前缀树）。对于基数树的每个节点，如果该节点是唯一的子树的话，就和父节点合并。

如果依次向树添加test、team、api，那么过程应该如下，test和team具有公共前缀te，te是st和am公共前缀。

添加test，只有唯一子节点。

test

添加team，team和test具有相同前缀te，那么提取te为公共前缀，然后子节点有两个，分叉成st和am。

te
--st
--am

添加api，api和te没有相同前缀（首字母不同），给根节点添加一个新的子节点api。

te
--st
--am
api

如果需要查找应该字符串，匹配字符串的和节点字符串是否为查找的字符串前缀，是才表示匹配，然后截取剩余字符串，进行下一步匹配。

如果查找append，根节点只有te、app、interface三个子节点，匹配命中app，剩余未匹配的是le。

然后使用a的子节点le、end，两个子节点匹配恰好le。

te
--st
----22
--am
app
---le
---end
interface

插入和查找的radix实现：

package main

import (
    "strings"
    "testing"
    "fmt"
    "github.com/kr/pretty"
)

func main() {
    tree := NewRadixTree()
    tree.Insert("test", 1)
    // fmt.Printf("%# v\n", pretty.Formatter(tree))
    tree.Insert("test22", 1)
    // fmt.Printf("%# v\n", pretty.Formatter(tree))
    tree.Insert("team", 3)
    tree.Insert("apple", 4)
    tree.Insert("append", 12)
    tree.Insert("app", 5)
    tree.Insert("append", 6)
    tree.Insert("interface", 7)
    fmt.Printf("%# v\n", pretty.Formatter(tree))
    t.Log(tree.Lookup("append"))
}

type (
    radixTree struct {
        root radixNode
    }
    radixNode struct {
        path     string
        children []*radixNode
        key      string
        val      interface{}
    }
)

func NewRadixTree() *radixTree {
    return &radixTree{radixNode{}}
}

// 新增Node
func (r *radixNode) InsertNode(path, key string, value interface{}) {
    if len(path) == 0 {
        // 路径空就设置当前node的值
        r.key = key
        r.val = value
    } else {
        // 否则新增子node
        r.children = append(r.children, &radixNode{path: path, key: key, val: value})
    }
}

// 对指定路径为edgeKey的Node分叉，公共前缀路径为pathKey
func (r *radixNode) SplitNode(pathKey, edgeKey string) *radixNode {
    for i, _ := range r.children {
        // 找到路径为edgeKey路径的Node，然后分叉
        if r.children[i].path == edgeKey {
            // 创建新的分叉Node，路径为公共前缀路径pathKey
            newNode := &radixNode{path: pathKey}
            // 将原来edgeKey的数据移动到新的分叉Node之下
            // 直接新增Node，原Node数据仅改变路径为截取后的后段路径
            newNode.children = append(newNode.children, &radixNode{
                // 截取路径
                path: strings.TrimPrefix(edgeKey, pathKey),
                // 复制数据
                key:      r.children[i].key,
                val:      r.children[i].val,
                children: r.children[i].children,
            })
            // 设置radixNode的child[i]的Node为分叉Node
            // 原理路径Node的数据移到到了分叉Node的child里面，原Node对象GC释放。
            r.children[i] = newNode
            // 返回分叉新创建的Node
            return newNode
        }
    }
    return nil
}

func (t *radixTree) Insert(key string, val interface{}) {
    t.recursiveInsertTree(&t.root, key, key, val)
}

// 给currentNode递归添加，路径为containKey的Node
//
// targetKey和targetValue为新Node数据。
func (t *radixTree) recursiveInsertTree(currentNode *radixNode, containKey string, targetKey string, targetValue interface{}) {
    for i, _ := range currentNode.children {
        // 检查当前遍历的Node和插入路径是否有公共路径
        // subStr是两者的公共路径，find表示是否有
        subStr, find := getSubsetPrefix(containKey, currentNode.children[i].path)
        if find {
            // 如果child路径等于公共最大路径，则该node添加child
            // child的路径为插入路径先过滤公共路径的后面部分。
            if subStr == currentNode.children[i].path {
                nextTargetKey := strings.TrimPrefix(containKey, currentNode.children[i].path)
                // 当前node新增子Node可能原本有多个child，所以需要递归添加
                t.recursiveInsertTree(currentNode.children[i], nextTargetKey, targetKey, targetValue)
            } else {
                // 如果公共路径不等于当前node的路径
                // 则将currentNode.children[i]路径分叉
                // 分叉后的就拥有了公共路径，然后添加新Node
                newNode := currentNode.SplitNode(subStr, currentNode.children[i].path)
                if newNode == nil {
                    panic("Unexpect error on split node")
                }
                // 添加新的node
                // 分叉后树一定只有一个没有相同路径的child，所以直接添加node
                newNode.InsertNode(strings.TrimPrefix(containKey, subStr), targetKey, targetValue)
            }
            return
        }
    }
    // 没有相同前缀路径存在，直接添加为child
    currentNode.InsertNode(containKey, targetKey, targetValue)
}

//Lookup: Find if seachKey exist in current radix tree and return its value
func (t *radixTree) Lookup(searchKey string) (interface{}, bool) {
    return t.recursiveLoopup(&t.root, searchKey)
}

// 递归获得searchNode路径为searchKey的Node数据。
func (t *radixTree) recursiveLoopup(searchNode *radixNode, searchKey string) (interface{}, bool) {
    // 匹配node，返回数据
    if len(searchKey) == 0 {
        // 如果没有添加节点本身，那么key就是空字符串，表示节点数据不存在。
        return searchNode.val, searchNode.key != ""
    }

    for _, edgeObj := range searchNode.children {
        // 寻找相同前缀node
        if contrainPrefix(searchKey, edgeObj.path) {
            // 截取为匹配的路径
            nextSearchKey := strings.TrimPrefix(searchKey, edgeObj.path)
            // 然后当前Node递归判断
            return t.recursiveLoopup(edgeObj, nextSearchKey)
        }
    }

    return nil, false
}

// 判断字符串str1的前缀是否是str2
func contrainPrefix(str1, str2 string) bool {
    if sub, find := getSubsetPrefix(str1, str2); find {
        return sub == str2
    }
    return false
}

// 获取两个字符串的最大公共前缀，返回最大公共前缀和是否拥有最大公共前缀
func getSubsetPrefix(str1, str2 string) (string, bool) {
    findSubset := false
    for i := 0; i < len(str1) && i < len(str2); i++ {
        if str1[i] != str2[i] {
            retStr := str1[:i]
            return retStr, findSubset
        }
        findSubset = true
    }

    if len(str1) > len(str2) {
        return str2, findSubset
    } else if len(str1) == len(str2) {
        //fix "" not a subset of ""
        return str1, str1 == str2
    }

    return str1, findSubset
}

RouterCoreRadix

RouterCoreRadix实现

RouterCoreRadix相关代码以及移除，当前默认路由核心为RouterCoreStd,由RouterCoreFull重命名，RouterCoreFull为RouterCoreRadix的强化版本。

RouterCoreRadix基于radix tree算法实现，使用节点按类型分类处理，实现匹配优先顺序、易扩展、低代码复杂度的特点，是eudore当前使用的默认路由器。

RouterCoreRadix支持4种路径，'\'结尾的常量、常量、':name'形式的变量、'*'结尾的通配符;第一个路径空格后可以增加额外的匹配命中参数；而RouterCoreFull额外增加了两种校验类型。

一二是常量，三是通配符和附加参数、四是参数、五是通配符。

/
/index
/api/v1/* version:v1
/:name
/*

RouterCoreRadix代码复杂度均低于15，路由器实现中只存在两处代码复杂度大于15(17,18)，由于RouterCoreRadix处理节点类型增加两种导致的，代码复杂度

Radix树只是基本的字符串匹配，但是Radix路由具有常量、变量、通配符三种匹配节点,因此将三种分开处理。

// radix节点的定义
type radixNode struct {
    // 基本信息
    kind uint8
    path string
    name string
    // 每次类型子节点
    Cchildren []*radixNode
    Pchildren []*radixNode
    Wchildren *radixNode
    // 当前节点的数据
    tags     []string
    vals     []string
    handlers HandlerFuncs
}

radixNode的kind、path、name保存着结点类型、当前匹配路径、匹配的变量名称；CPW（const、param、wildcard）就是三类结点的集合，tags和vals是默认参数、handlers是多个请求处理者。

HandleFunc

HandleFunc注册Any方法会给全部方法树都注册一遍。

调用insertRoute方法来实现添加，同时将中间件树匹配到的请求中间件和处理者合并，从全部处理中间件和多个请求处理者合并成一个完整请求处理链。

// HandleFunc 给路由器注册一个新的方法请求路径。
//
// 如果方法是Any会注册全部方法，同时非Any方法路由和覆盖Any方法路由。
func (r *RouterCoreRadix) HandleFunc(method string, path string, handler HandlerFuncs) {
    switch method {
    case "NotFound", "404":
        r.node404.handlers = handler
    case "MethodNotAllowed", "405":
        r.node405.Wchildren.handlers = handler
    case MethodAny:
        for _, method := range RouterAllMethod {
            r.insertRoute(method, path, true, handler)
        }
    default:
        r.insertRoute(method, path, false, handler)
    }
}

insertRoute方法先拿到对应的基数树，如果方法是不允许的就拿到的405树，就结束了添加。

然后将路由注册路径按结点类型切割成多段，按照常量、变量、字符串三类将路径切割出来，每类结点就是一种结点的类型，当前切割实现对应特殊的正则规则支持不够。

在查找时先匹配全部常量子节点，没有就使用变量子节点，uri本段就是变量内容，剩余进行递归匹配，如果变量子节点不匹配，就检查通配符节点，如果存在就是直接匹配通配符。

因此具有路由具有严格的匹配优先顺序，一定是先常量再变量最后通配符，由匹配函数里面代码段的位置决定了顺序。

如果六条路由是/*，最先注册的，但是api是常量更有效，就会先检查是否是api，不是才会使用通配符，

而/api/:user和/api/:user/info两条，会进一步检查是否是info，如果是/api/eudore/list只会匹配到/api/*。

/*
/api/v1
/api/*
/api/user
/api/:user
/api/:user/info

func getSpiltPath(key string) []string将字符串按Node类型切割。

例如/api/:get/*中:get和*明显是变量和通配符节点。所以两种前后需要切分开来，结果为[/api/ :get / *],/api/增加变量子节点:get，依次添加完成树。

字符串路径切割例子：

/               [/]
/api/note/      [/api/note/]
//api/*         [/api/ *]
//api/*name     [/api/ *name]
/api/get/       [/api/get/]
/api/get        [/api/get]
/api/:get       [/api/ :get]
/api/:get/*     [/api/ :get / *]
/api/:name/info/*       [/api/ :name /info/ *]
/api/:name|^\\d+$/info  [/api/ :name|^\d+$ /info]
/api/*|^0/api\\S+$      [/api/ *|^0 /api\S+$]
/api/*|^\\$\\d+$        [/api/ *|^\$\d+$]

然后给基数树添加结点，如果结点是存在的就返回的存在的，所以要更新当前的根节点，然后依次向下添加。

最后一个结点就是树底了，然后给树底的新结点设置多个请求处理者和默认参数。

如果添加方法是Any，那么kind会增加一个Any的flag，允许非Any方法覆盖Any方法反之不行。

// routerRadix.go
func (r *RouterCoreRadix) insertRoute(method, key string, isany bool, val HandlerFuncs) {
    var currentNode = r.getTree(method)
    if currentNode == &r.node405 {
        return
    }

    // 创建节点
    args := strings.Split(key, " ")
    for _, path := range getSplitPath(args[0]) {
        currentNode = currentNode.InsertNode(path, newRadixNode(path))
    }

    if isany {
        if currentNode.kind&radixNodeKindAnyMethod != radixNodeKindAnyMethod && currentNode.handlers != nil {
            return
        }
        currentNode.kind |= radixNodeKindAnyMethod
    } else {
        currentNode.kind &^= radixNodeKindAnyMethod
    }

    currentNode.handlers = val
    currentNode.SetTags(args)
}

newRadixNode函数就是简单的根据首字符来设置结点的类型和名称。

InsertNode方法就根据结点类型来添加对对应的结点集合中，常量结点需要进行分叉操作，将相同的前缀提取出来。

// 创建一个Radix树Node，会根据当前路由设置不同的节点类型和名称。
//
// '*'前缀为通配符节点，':'前缀为参数节点，其他未常量节点。
func newRadixNode(path string) *radixNode {
    newNode := &radixNode{path: path}
    switch path[0] {
    case '*':
        newNode.kind = radixNodeKindWildcard
        if len(path) == 1 {
            newNode.name = "*"
        } else {
            newNode.name = path[1:]
        }
    case ':':
        newNode.kind = radixNodeKindParam
        newNode.name = path[1:]
    default:
        newNode.kind = radixNodeKindConst
    }
    return newNode
}

// 给当前节点路径下添加一个子节点。
//
// 如果新节点类型是常量节点，寻找是否存在相同前缀路径的结点，
// 如果存在路径为公共前缀的结点，直接添加新结点为匹配前缀结点的子节点；
// 如果只是两结点只是拥有公共前缀，则先分叉然后添加子节点。
//
// 如果新节点类型是参数结点，会检测当前参数是否存在，存在返回已处在的节点。
//
// 如果新节点类型是通配符结点，直接设置为当前节点的通配符处理节点。
func (r *radixNode) InsertNode(path string, nextNode *radixNode) *radixNode {
    if len(path) == 0 {
        return r
    }
    nextNode.path = path
    switch nextNode.kind &^ radixNodeKindAnyMethod {
    case radixNodeKindConst:
        for i := range r.Cchildren {
            subStr, find := getSubsetPrefix(path, r.Cchildren[i].path)
            if find {
                if subStr != r.Cchildren[i].path {
                    r.Cchildren[i].path = strings.TrimPrefix(r.Cchildren[i].path, subStr)
                    r.Cchildren[i] = &radixNode{
                        path:      subStr,
                        Cchildren: []*radixNode{r.Cchildren[i]},
                    }
                }
                return r.Cchildren[i].InsertNode(strings.TrimPrefix(path, subStr), nextNode)
            }
        }
        r.Cchildren = append(r.Cchildren, nextNode)
        // 常量node按照首字母排序。
        for i := len(r.Cchildren) - 1; i > 0; i-- {
            if r.Cchildren[i].path[0] < r.Cchildren[i-1].path[0] {
                r.Cchildren[i], r.Cchildren[i-1] = r.Cchildren[i-1], r.Cchildren[i]
            }
        }
    case radixNodeKindParam:
        for _, i := range r.Pchildren {
            if i.path == path {
                return i
            }
        }
        r.Pchildren = append(r.Pchildren, nextNode)
    case radixNodeKindWildcard:
        r.Wchildren = nextNode
    default:
        panic("Undefined radix node type")
    }
    return nextNode
}

Match

Match是匹配方法，先使用getTree方法获得请求方法对应的树进行查找，如果405就方法的405树，只会匹配405的结果；如果其他方法树就进行路由匹配，匹配结果非空则返回；如果查找的结果是空，就使用404处理。

// 匹配一个请求，如果方法不不允许直接返回node405，未匹配返回node404。
func (r *RouterCoreRadix) Match(method, path string, params Params) HandlerFuncs {
    if n := r.getTree(method).recursiveLoopup(path, params); n != nil {
        return n
    }

    // 处理404
    r.node404.AddTagsToParams(params)
    return r.node404.handlers
}

recursiveLoopup方法递归查找主要分为四步。

第一步检测当前节点是否匹配，匹配则添加参数然后返回。

第二步检测当前节点的常量子节点是否和匹配路径前缀，有前缀表示有可能匹配到了，然后截取路径递归匹配，然后不为空就表示匹配命中，返回对象

第三步检测当前节点的变量子节点是否匹配，直接截取两个‘/’间路径为当前的变量匹配内容，然后检测进一步匹配。

第四步检测当前节点是否拥有通配符结点，如果有直接执行通配符匹配。

最后如果前面四步没有匹配名字，返回nil。

// 按照顺序匹配一个路径。
//
// 依次检查常量节点、参数节点、通配符节点，如果有一个匹配就直接返回。
func (r *radixNode) recursiveLoopup(searchKey string, params Params) HandlerFuncs {
    // 如果路径为空，当前节点就是需要匹配的节点，直接返回。
    if len(searchKey) == 0 && r.handlers != nil {
        r.AddTagsToParams(params)
        return r.handlers
    }

    if len(searchKey) > 0 {
        // 遍历常量Node匹配，寻找具有相同前缀的那个节点
        for _, edgeObj := range r.Cchildren {
            if edgeObj.path[0] >= searchKey[0] {
                if len(searchKey) >= len(edgeObj.path) && searchKey[:len(edgeObj.path)] == edgeObj.path {
                    nextSearchKey := searchKey[len(edgeObj.path):]
                    if n := edgeObj.recursiveLoopup(nextSearchKey, params); n != nil {
                        return n
                    }
                }
                break
            }
        }

        if len(r.Pchildren) > 0 {
            pos := strings.IndexByte(searchKey, '/')
            if pos == -1 {
                pos = len(searchKey)
            }
            nextSearchKey := searchKey[pos:]

            // Whether the variable Node matches in sequence is satisfied
            // 遍历参数节点是否后续匹配
            for _, edgeObj := range r.Pchildren {
                if n := edgeObj.recursiveLoopup(nextSearchKey, params); n != nil {
                    params.Add(edgeObj.name, searchKey[:pos])
                    return n
                }
            }
        }
    }

    // If the current Node has a wildcard processing method that directly matches, the result is returned.
    // 若当前节点有通配符处理方法直接匹配，返回结果。
    if r.Wchildren != nil {
        r.Wchildren.AddTagsToParams(params)
        params.Add(r.Wchildren.name, searchKey)
        return r.Wchildren.handlers
    }

    // can't match, return nil
    // 无法匹配，返回空
    return nil
}

反馈和交流请加群组：QQ群373278915。