ACM 高手可以自动略过了.
大家好, 我是不知名框架`uRouter`的作者, 前 ACM 铜牌选手, 今天给大家分享一个动态路由匹配算法.
没看过gin这部分源码, 但自己实现一个也不难. 核心是一个字典树的变种, 称之为树形Map或许更为贴切.
package main
import "strings"
const (
defaultSeparator = "/" // 默认路径分隔符
defaultVarPrefix = ':' // 默认变量前缀
)
type (
apiHandler struct {
VPath string // API 路径
Funcs []func() // 处理函数
}
routeTree struct {
Value *apiHandler // 值
Children map[string]*routeTree // 子节点
}
)
func newRouteTree() *routeTree { return new(routeTree) }
// 判断字符串是否为变量
func isVar(s string) bool { return len(s) > 0 && s[0] == defaultVarPrefix }
// 分割字符串; 在原数组的基础上游走, 减少内存分配次数
func split(s string, sep string) []string {
var j = 0
var list = strings.Split(s, sep)
for i, v := range list {
if v != "" {
list[j] = list
j++
}
}
return list[:j]
}
// Set 注册接口
func (c *routeTree) Set(vpath string, funcs []func()) {
var handler = &apiHandler{VPath: vpath, Funcs: funcs}
var list = split(handler.VPath, defaultSeparator)
if len(list) == 0 {
return
}
c.doSet(c, 0, list, handler)
}
func (c *routeTree) doSet(node *routeTree, index int, list []string, handler *apiHandler) {
var segment = list[index]
if isVar(segment) {
segment = "*"
}
var next = node.Children[segment]
if node.Children == nil {
node.Children = make(map[string]*routeTree)
}
if node.Children[segment] == nil {
next = &routeTree{}
node.Children[segment] = next
}
if index+1 == len(list) {
next.Value = handler
} else {
c.doSet(next, index+1, list, handler)
}
}
// Get 查找接口
func (c *routeTree) Get(path string) (*apiHandler, bool) {
var list = split(path, defaultSeparator)
if len(list) == 0 {
return nil, false
}
return c.doGet(c, 0, list)
}
func (c *routeTree) doGet(node *routeTree, index int, list []string) (*apiHandler, bool) {
if index == len(list) {
return node.Value, true
}
var segment = list[index]
if v, ok := node.Children[segment]; ok {
return c.doGet(v, index+1, list)
}
if v, ok := node.Children["*"]; ok {
return c.doGet(v, index+1, list)
}
return nil, false
}
本测试共注册 1024 个接口, 每个接口分为 4 段.
goos: darwin
goarch: arm64
pkg: github.com/lxzan/uRouter
BenchmarkRouteTree_Get-8 6707703 168.2 ns/op 80 B/op 1 allocs/op
PASS
ok github.com/lxzan/uRouter 1.433s
