> For the complete documentation index, see [llms.txt](https://docs.eudore.cn/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.eudore.cn/eudore/eudore-router-radix.md).
# 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实现](https://github.com/eudore/eudore/blob/f919218094d32cf319d4ad9a1f33a260b8450014/routerradix.go)
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处理节点类型增加两种导致的，[代码复杂度](https://goreportcard.com/report/github.com/eudore/eudore#gocyclo)
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
}
```