又一个 Golang 但零分配并且泛型的动态路由 Tree

[ClarkAbe]

首先上 Benchmark

[neno@ArchOxO tux]$ go test -benchmem -run=^$ -bench ^(BenchmarkRouteTree_Get|BenchmarkRouteTree_Set)$ github.com/ClarkQAQ/tux/tree

goos: linux
goarch: amd64
pkg: github.com/ClarkQAQ/tux/tree
cpu: AMD Ryzen 7 5800H with Radeon Graphics         
BenchmarkRouteTree_Get-16    	130589565	         9.593 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouteTree_Set-16    	12670129	        93.20 ns/op	       1 B/op	       0 allocs/op
PASS
ok  	github.com/ClarkQAQ/tux/tree	4.477s

然后...你们可以喷我了

只是昨天看到 链接 的 uRouter 才想起来我也还有一个 Web 框架...

核心路由树 (不到百行)

由于想法过于疯狂导致半年前我朋友骂我是不是可乐喝多了脑袋坏了, 但是事实证明他是工作的而且还很快

package tree

import "unsafe"

const (
	asterisk = '*' // 通配符
	colon    = ':' // 冒号 (路径参数)
	slash    = '/' // 斜杠
)

// 路由树
type Tree[T any] struct {
	children [255]*Tree[T] // 子路由节点
	vpath    []uint8       // 注册的路由路径
	value    T             // 路由方法 (methodTyp 类型)
}

// 设置路由
func (t *Tree[T]) Set(route string, value T) {
	a := toByte(route)

	for i := 0; i < len(a); i++ {
		if t.children[a[i]] == nil {
			t.children[a[i]] = &Tree[T]{}
		}

		t = t.children[a[i]]

		// 判断是否为路径参数 (例如: :name *name)
		if a[i] == colon {
			i = slashReader(a, i)
		} else if a[i] == asterisk {
			break
		}
	}

	t.value = value
	t.vpath = a
}

// 斜杠读取器
// 读取到下一个斜杠或者结束, 然后返回下标位置
func slashReader(a []uint8, i int) int {
	for ; i < len(a) && a[i] != slash; i++ {
	}

	return i
}

// 获取路由
func (t *Tree[T]) Get(route string) (T, []uint8) {
	a := toByte(route)

	for i := 0; i < len(a); i++ {
		if t.children[asterisk] != nil { // 通配路径参数 (例如: *name)
			t = t.children[asterisk]
			break
		} else if t.children[colon] != nil { // 路径参数 (例如: :name)
			t = t.children[colon]
			i = slashReader(a, i)
		} else {
			if t.children[a[i]] == nil { // 路由不存在
				var v T
				return v, nil
			}

			t = t.children[a[i]]
		}
	}

	return t.value, t.vpath
}

// 转换为字节切片
func toByte(s string) []uint8 {
	return *(*[]uint8)(unsafe.Pointer(&s))
}

// 以下为转换为字节切片的另一种方式, 但是效率较低, 使用他将会比前者慢 4 ns/op
// func toByte(s string) []uint8 {
// 	return []uint8(s)
// }