3. 前缀树路由

Kesa...大约 4 分钟

1. 前缀树 Trie

使用哈希表的路由表，只能处理静态路由。

对于动态路由，例如：/hello/:name，可以使用前缀树的数据结构实现。

HTTP的请求路径是以/进行分隔的，因此每段可以作为 Trie 的节点。

2. 实现动态路由

使用前缀树实现动态路由的以下功能：

参数匹配:，例如：/:lang/doc，可以匹配/clang/doc,/go/doc
通配符*，例如：/static/*filepath，可以匹配static/fav.ico，static/js/jQuery.js

https://github.com/dreamjz/golang-notes/tree/main/books/7-days-golang/Gee/day3-tire-routeropen in new window

当前项目结构：

DAY3-TIRE-ROUTER
│  go.mod
│  go.work
│  main.go
│
└─gee
        context.go
        gee.go
        go.mod
        router.go
        router_test.go
        trie.go

2.1 Trie

package gee

import "strings"

type trieNode struct {
	pattern  string      // 待匹配的路由
	part     string      // 当前节点的内容
	children []*trieNode // 子节点
	isWild   bool        // 是否进行精准匹配，默认 false
}

// 寻找第一个匹配成功的节点，用于插入
func (n *trieNode) matchChild(part string) *trieNode {
	for _, child := range n.children {
		if child.part == part || child.isWild {
			return child
		}
	}

	return nil
}

// 寻找所有匹配成功的节点，用于查找
func (n *trieNode) matchChildren(part string) []*trieNode {
	nodes := make([]*trieNode, 0)

	for _, child := range n.children {
		if child.part == part || child.isWild {
			nodes = append(nodes, child)
		}
	}

	return nodes
}

// 向前缀树中插入新节点
func (n *trieNode) insert(pattern string, parts []string, depth int) {
	if len(parts) == depth {
		n.pattern = pattern
		return
	}

	part := parts[depth]
	child := n.matchChild(part)
	if child == nil {
		child = &trieNode{part: part, isWild: part[0] == ':' || part[0] == '*'}
		n.children = append(n.children, child)
	}

	child.insert(pattern, parts, depth+1)
}

// 查找指定路由对应的节点
func (n *trieNode) search(parts []string, depth int) *trieNode {
	if len(parts) == depth || strings.HasPrefix(n.part, "*") {
		if n.pattern == "" {
			return nil
		}
		return n
	}

	part := parts[depth]
	children := n.matchChildren(part)

	for _, child := range children {
		res := child.search(parts, depth+1)
		if res != nil {
			return res
		}
	}

	return nil
}

trieNode：前缀树的节点
- pattern：已注册的路由，空字符串表示根节点到此节点的路径不是注册的路由
- isWild：是否使用精准匹配，默认 false
  - 当出现:和*表示此路由为动态路由，为 true

2.2 Router

package gee

import (
	"net/http"
	"strings"
)

type router struct {
	trieRoots map[string]*trieNode
	handlers  map[string]HandlerFunc
}

func newRouter() *router {
	return &router{
		trieRoots: map[string]*trieNode{},
		handlers:  map[string]HandlerFunc{},
	}
}

func parsePattern(pattern string) []string {
	strs := strings.Split(pattern, "/")

	parts := make([]string, 0)
	for _, str := range strs {
		if str != "" {
			parts = append(parts, str)
			if str[0] == '*' { // Only one '*' allowed
				break
			}
		}
	}

	return parts
}

func (r *router) addRoute(method string, pattern string, handler HandlerFunc) {
	parts := parsePattern(pattern)

	_, ok := r.trieRoots[method]
	if !ok {
		r.trieRoots[method] = &trieNode{}
	}
	r.trieRoots[method].insert(pattern, parts, 0)

	key := method + "-" + pattern
	r.handlers[key] = handler
}

func (r *router) handle(c *Context) {
	n, params := r.getRoute(c.Method, c.Path)
	if n != nil {
		c.Params = params
		key := c.Method + "-" + n.pattern
		r.handlers[key](c)
	} else {
		c.String(http.StatusNotFound, "404 NOT FOUND: %s\n", c.Path)
	}
}

func (r *router) getRoute(method string, path string) (*trieNode, map[string]string) {
	root, ok := r.trieRoots[method]
	if !ok {
		return nil, nil
	}

	searchParts := parsePattern(path)
	n := root.search(searchParts, 0)
	if n != nil {
		parts := parsePattern(n.pattern)
		params := make(map[string]string)

		for i, part := range parts {
			if part[0] == ':' {
				params[part[1:]] = searchParts[i]
			}
			if part[0] == '*' && len(part) > 1 {
				params[part[1:]] = strings.Join(searchParts[i:], "/")
				break
			}
		}

		return n, params
	}

	return nil, nil
}

router
- trieRoots：路由前缀树根节点，不同的方法类型对应不同的路由
- hadnlers：路由处理函数，方法类型+请求路径映射到唯一的处理函数
parsePattern：将注册的路由按照/分割为多个部分，不会添加空字符串并且只允许一个通配符*
addRoute：向路由表中添加路由
1. 将路由插入到前缀树中
2. 添加处理函数到哈希表中
getRoute：根据请求路径，获取对应的路由及其路由参数
handle：处理请求，根据请求路径获取绑定的处理函数并调用

2.3 Context

type Context struct {
	Writer http.ResponseWriter
	Req    *http.Request
	// Request info
	Path   string
	Method string
	Params map[string]string // Dynamic route parameters
	// Response info
	StatusCode int
}

Params：当前请求的路由参数哈希表

// Param return dynamic route parameter by key
func (c *Context) Param(key string) string {
	val, _ := c.Params[key]
	return val
}

获取当前请求的路由参数

3. 测试

3.1 单元测试

package gee

import (
	"fmt"
	"reflect"
	"testing"
)

func TestParsePattern(t *testing.T) {
	type args struct {
		pattern string
	}
	tests := []struct {
		name string
		args args
		want []string
	}{
		{name: "Empty String", args: args{pattern: ""}, want: []string{}},
		{name: "Empty Pattern", args: args{pattern: "/"}, want: []string{}},
		{name: "Empty Pattern", args: args{pattern: "//"}, want: []string{}},
		{name: "Dynamic route parameter", args: args{pattern: "p/:name"}, want: []string{"p", ":name"}},
		{name: "Wildcard ", args: args{pattern: "p/*"}, want: []string{"p", "*"}},
		{name: "Multiple wildcards", args: args{pattern: "p/*name/*"}, want: []string{"p", "*name"}},
	}

	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if got := parsePattern(tt.args.pattern); !reflect.DeepEqual(got, tt.want) {
				t.Errorf("parsePattern(%q) = %v, want: %v", tt.args.pattern, got, tt.want)
			}
		})
	}
}

func newTestRouter() *router {
	r := newRouter()
	r.addRoute("GET", "/", nil)
	r.addRoute("GET", "/hello/:name", nil)
	r.addRoute("GET", "/hello/:name/getAge", nil)
	r.addRoute("GET", "/hello/b/c", nil)
	r.addRoute("GET", "/hi/:name", nil)
	r.addRoute("GET", "/assets/*filepath", nil)
	return r
}

func TestGetRoute(t *testing.T) {
	r := newTestRouter()
	n, params := r.getRoute("GET", "/hello/alice")

	switch {
	case n == nil:
		t.Fatal("TrieNode cannot be nil")
	case n.pattern != "/hello/:name":
		t.Fatal("Route should match /hello/:name")
	case params["name"] != "alice":
		t.Fatal("Route parameter name should be alice")
	default:
		fmt.Printf("mathched path: %q, params['name']: %q\n", n.pattern, params["name"])
	}
}

3.2 启动Demo

func main() {
	r := gee.New()

	r.GET("/", func(c *gee.Context) {
		c.HTML(http.StatusOK, "<h1>Welcome</h1>")
	})

	r.GET("/hello", func(c *gee.Context) {
		c.String(http.StatusOK, "Hello %s, you're at %s\n", c.Query("name"), c.Path)
	})

	r.GET("/hello/:name", func(c *gee.Context) {
		c.String(http.StatusOK, "Hello %s, you're at %s\n", c.Param("name"), c.Path)
	})

	r.GET("assets/*filepath", func(c *gee.Context) {
		c.JSON(http.StatusOK, gee.H{"filepath": c.Param("filepath")})
	})

	r.Run(":8000")
}

$ curl http://localhost:8000
<h1>Welcome</h1>
$ curl http://localhost:8000/hello?name=alice
Hello alice, you're at /hello

$ curl http://localhost:8000/hello/alice
Hello alice, you're at /hello/alice

$ curl http://localhost:8000/assets/css/layout.css
{"filepath":"css/layout.css"}

$ curl http://localhost:8000/AA
404 NOT FOUND: /AA

4. 小结

通过前缀树实现了动态路由

Reference

https://geektutu.com/post/gee-day3.htmlopen in new window

昵称

邮箱

网址

按正序
按倒序
按热度

3. 前缀树路由

# 1. 前缀树 Trie

# 2. 实现动态路由

# 2.1 Trie

# 2.2 Router

# 2.3 Context

# 3. 测试

# 3.1 单元测试

# 3.2 启动Demo

# 4. 小结

# Reference

预览:

1. 前缀树 Trie

2. 实现动态路由

2.1 Trie

2.2 Router

2.3 Context

3. 测试

3.1 单元测试

3.2 启动Demo

4. 小结

Reference