算法分享: 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