算法分享: Golang HTTP 动态请求路径解析

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[i] 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