eudore router radix

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)
    
    tree.Insert("test22", 1)
    
    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{}}
}


func (r *radixNode) InsertNode(path, key string, value interface{}) {
    if len(path) == 0 {
        
        r.key = key
        r.val = value
    } else {
        
        r.children = append(r.children, &radixNode{path: path, key: key, val: value})
    }
}


func (r *radixNode) SplitNode(pathKey, edgeKey string) *radixNode {
    for i, _ := range r.children {
        
        if r.children[i].path == edgeKey {
            
            newNode := &radixNode{path: pathKey}
            
            
            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,
            })
            
            
            r.children[i] = newNode
            
            return newNode
        }
    }
    return nil
}

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




func (t *radixTree) recursiveInsertTree(currentNode *radixNode, containKey string, targetKey string, targetValue interface{}) {
    for i, _ := range currentNode.children {
        
        
        subStr, find := getSubsetPrefix(containKey, currentNode.children[i].path)
        if find {
            
            
            if subStr == currentNode.children[i].path {
                nextTargetKey := strings.TrimPrefix(containKey, currentNode.children[i].path)
                
                t.recursiveInsertTree(currentNode.children[i], nextTargetKey, targetKey, targetValue)
            } else {
                
                
                
                newNode := currentNode.SplitNode(subStr, currentNode.children[i].path)
                if newNode == nil {
                    panic("Unexpect error on split node")
                }
                
                
                newNode.InsertNode(strings.TrimPrefix(containKey, subStr), targetKey, targetValue)
            }
            return
        }
    }
    
    currentNode.InsertNode(containKey, targetKey, targetValue)
}


func (t *radixTree) Lookup(searchKey string) (interface{}, bool) {
    return t.recursiveLoopup(&t.root, searchKey)
}


func (t *radixTree) recursiveLoopup(searchNode *radixNode, searchKey string) (interface{}, bool) {
    
    if len(searchKey) == 0 {
        
        return searchNode.val, searchNode.key != ""
    }

    for _, edgeObj := range searchNode.children {
        
        if contrainPrefix(searchKey, edgeObj.path) {
            
            nextSearchKey := strings.TrimPrefix(searchKey, edgeObj.path)
            
            return t.recursiveLoopup(edgeObj, nextSearchKey)
        }
    }

    return nil, false
}


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) {
        
        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路由具有常量、变量、通配符三种匹配节点,因此将三种分开处理。

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方法来实现添加，同时将中间件树匹配到的请求中间件和处理者合并，从全部处理中间件和多个请求处理者合并成一个完整请求处理链。

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方法反之不行。

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

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)
        
        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处理。

func (r *RouterCoreRadix) Match(method, path string, params Params) HandlerFuncs {
    if n := r.getTree(method).recursiveLoopup(path, params); n != nil {
        return n
    }

    
    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 {
        
        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:]

            
            
            for _, edgeObj := range r.Pchildren {
                if n := edgeObj.recursiveLoopup(nextSearchKey, params); n != nil {
                    params.Add(edgeObj.name, searchKey[:pos])
                    return n
                }
            }
        }
    }

    
    
    if r.Wchildren != nil {
        r.Wchildren.AddTagsToParams(params)
        params.Add(r.Wchildren.name, searchKey)
        return r.Wchildren.handlers
    }

    
    
    return nil
}