发布于：，更新于：

04.Mygin实现动态路由

本篇是Mygin的第四篇

目的

  • 使用 Trie 树实现动态路由解析。
  • 参数绑定

前缀树

本篇比前几篇要复杂一点，原来的路由是用map实现，索引非常高效，但是有一个弊端，键值对的存储的方式，只能用来索引静态路由。遇到类似hello/:name这动态路由就无能为力了，实现动态路由最常用的数据结构，被称为前缀树。这种结构非常适用于路由匹配。比如我们定义了如下路由：

  • /a/b/c
  • /a/b
  • /a/c
  • /a/b/c/d
  • /a/:name/c
  • /a/:name/c/d
  • /a/b/:name/e

在前缀树中的结构体
tree

HTTP请求的路径是由/分隔的字符串构成的,所以用/拆分URL字符串，得到不同的树节点，且有对应的层级关系。

代码实现

  • Mygin/tree.go 首先看tree中node结构定义
    1
    2
    3
    4
    5
    6
    7
    8
    type node struct {
    	children  []*node //子节点
    	part      string  //树节点
    	wildChild bool    //是否是精确匹配
    	handlers  HandlersChain //路由回调，实际的请求
    	nType     nodeType  //节点类型 默认static params
    	fullPath  string  //完整路径
    }
    与普通的树不同，为了实现动态路由匹配，加上了wildChild这个参数。即当我们匹配 /a/scott/c这个路由时，第一层节点，a精准匹配到了b，第二层节点，b模糊匹配到:name，那么将会把name这个参数赋值为scott，继续下一层匹配。我们将匹配的逻辑，包装为一个辅助函数。
  • Mygin/tree.go 具体实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    package mygin

    import (
    	"strings"
    )

    type nodeType uint8

    // 路由的类型
    const (
    	static nodeType = iota
    	root
    	param
    	catchAll
    )

    // 不同的method 对应不同的节点树 定义
    type methodTree struct {
    	method string
    	root   *node
    }

    // Param 参数的类型key=> value
    type Param struct {
    	Key   string
    	Value string
    }

    // Params 切片
    type Params []Param

    type methodTrees []methodTree

    type node struct {
    	children  []*node
    	part      string
    	wildChild bool
    	handlers  HandlersChain
    	nType     nodeType
    	fullPath  string
    }

    // Get 获取 参数中的值
    func (ps Params) Get(name string) (string, bool) {
    	for _, entry := range ps {
    		if entry.Key == name {
    			return entry.Value, true
    		}
    	}
    	return "", false
    }

    // ByName 通过ByName获取参数中的值 会忽略掉错误，默认返回 空字符串
    func (ps Params) ByName(name string) (v string) {
    	v, _ = ps.Get(name)
    	return
    }

    // 根据method获取root
    func (trees methodTrees) get(method string) *node {
    	for _, tree := range trees {
    		if tree.method == method {
    			return tree.root
    		}
    	}
    	return nil
    }

    // 添加路径时
    func (n *node) addRoute(path string, handlers HandlersChain) {

    	//根据请求路径按照'/'划分
    	parts := n.parseFullPath(path)

    	//将节点插入路由后，返回最后一个节点
    	matchNode := n.insert(parts)

    	//最后的节点，绑定执行链
    	matchNode.handlers = handlers

    	//最后的节点，绑定完全的URL，后续param时有用
    	matchNode.fullPath = path

    }

    // 按照 "/" 拆分字符串
    func (n *node) parseFullPath(fullPath string) []string {
    	splits := strings.Split(fullPath, "/")
    	parts := make([]string, 0)
    	for _, part := range splits {
    		if part != "" {
    			parts = append(parts, part)
    			if part == "*" {
    				break
    			}
    		}
    	}
    	return parts
    }

    // 根据路径 生成节点树
    func (n *node) insert(parts []string) *node {
    	part := parts[0]
    	//默认的字节类型为静态类型
    	nt := static
    	//根据前缀判断节点类型
    	switch part[0] {
    	case ':':
    		nt = param
    	case '*':
    		nt = catchAll
    	}

    	//插入的节点查找
    	var matchNode *node
    	for _, childNode := range n.children {
    		if childNode.part == part {
    			matchNode = childNode
    		}
    	}

    	//如果即将插入的节点没有找到，则新建一个
    	if matchNode == nil {
    		matchNode = &node{
    			part:      part,
    			wildChild: part[0] == '*' || part[0] == ':',
    			nType:     nt,
    		}
    		//新子节点追加到当前的子节点中
    		n.children = append(n.children, matchNode)
    	}

    	//当最后插入的节点时，类型赋值，且返回最后的节点
    	if len(parts) == 1 {
    		matchNode.nType = nt
    		return matchNode
    	}

    	//匹配下一部分
    	parts = parts[1:]
    	//子节点继续插入剩余字部分
    	return matchNode.insert(parts)
    }

    // 根据路由 查询符合条件的节点
    func (n *node) search(parts []string, searchNode *[]*node) {
    	part := parts[0] //a

    	allChild := n.matchChild(part) //b c :name

    	if len(parts) == 1 {
    		// 如果到达路径末尾，将所有匹配的节点加入结果
    		*searchNode = append(*searchNode, allChild...)
    		return
    	}

    	parts = parts[1:] //b

    	for _, n2 := range allChild {
    		// 递归查找下一部分
    		n2.search(parts, searchNode)
    	}

    }

    // 根据part 返回匹配成功的子节点
    func (n *node) matchChild(part string) []*node {

    	allChild := make([]*node, 0)
    	for _, child := range n.children {
    		if child.wildChild || child.part == part {
    			allChild = append(allChild, child)
    		}
    	}

    	return allChild
    }

上诉路由中，实现了插入insert和匹配search时的功能，插入时安装拆分后的子节点，递归查找每一层的节点，如果没有匹配到当前part的节点，则新建一个。查询功能，同样也是递归查询每一层的节点。

  • Mygin/router.go

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    package mygin

    import (
    	"net/http"
    )

    type Router struct {
    	trees methodTrees
    }

    // 添加路由方法
    func (r *Router) addRoute(method, path string, handlers HandlersChain) {
    	//根据method获取root
    	rootTree := r.trees.get(method)

    	//如果root为空
    	if rootTree == nil {
    		//初始化一个root
    		rootTree = &node{part: "/", nType: root}
    		//将初始化后的root 加入tree树中
    		r.trees = append(r.trees, methodTree{method: method, root: rootTree})

    	}

    	rootTree.addRoute(path, handlers)

    }

    // Get Get方法
    func (r *Router) Get(path string, handlers ...HandlerFunc) {
    	r.addRoute(http.MethodGet, path, handlers)
    }

    // Post  Post方法
    func (e *Engine) Post(path string, handlers ...HandlerFunc) {
    	e.addRoute(http.MethodPost, path, handlers)
    }

  • router中修改不大

  • Mygin/engine.go

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    package mygin

    import (
    	"net/http"
    )

    // HandlerFunc 定义处理函数类型
    type HandlerFunc func(*Context)
    // HandlersChain 定义处理函数链类型
    type HandlersChain []HandlerFunc

    // Engine 定义引擎结构，包含路由器
    type Engine struct {
    	Router
    }

    // ServeHTTP 实现http.Handler接口的方法，用于处理HTTP请求
    func (e *Engine) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    	// 获取对应HTTP方法的路由树的根节点
    	root := e.trees.get(r.Method)
    	// 解析请求路径
    	parts := root.parseFullPath(r.URL.Path)

    	// 查找符合条件的节点
    	searchNode := make([]*node, 0)
    	root.search(parts, &searchNode)

    	// 没有匹配到路由
    	if len(searchNode) == 0 {
    		w.Write([]byte("404 Not found!\n"))
    		return
    	}

    	// 参数赋值
    	params := make([]Param, 0)
    	searchPath := root.parseFullPath(searchNode[0].fullPath)
    	for i, sp := range searchPath {
    		if sp[0] == ':' {
    			params = append(params, Param{
    				Key:   sp[1:],
    				Value: parts[i],
    			})
    		}
    	}

    	// 获取处理函数链
    	handlers := searchNode[0].handlers
    	if handlers == nil {
    		w.Write([]byte("404 Not found!\n"))
    		return
    	}

    	// 执行处理函数链
    	for _, handler := range handlers {
    		handler(&Context{
    			Request: r,
    			Writer:  w,
    			Params:  params,
    		})
    	}
    }

    // Default 返回一个默认的引擎实例
    func Default() *Engine {
    	return &Engine{
    		Router: Router{
    			trees: make(methodTrees, 0, 9),
    		},
    	}
    }

    // Run 启动HTTP服务器的方法
    func (e *Engine) Run(addr string) error {
    	return http.ListenAndServe(addr, e)
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package main

import (
	"gophp/mygin"
)

func main() {
	// 创建一个默认的 mygin 实例
	r := mygin.Default()

	// 定义路由处理函数
	handleABC := func(context *mygin.Context) {
		context.JSON(map[string]interface{}{
			"path": context.Request.URL.Path,
		})
	}

	// 注册路由
	r.Get("/a/b/c", handleABC)
	r.Get("/a/b", handleABC)
	r.Get("/a/c", handleABC)

	// 注册带参数的路由
	r.Get("/a/:name/c", func(context *mygin.Context) {
		name := context.Params.ByName("name")
		path := "/a/" + name + "/c"
		context.JSON(map[string]interface{}{
			"path": path,
		})
	})

	r.Get("/a/:name/c/d", func(context *mygin.Context) {
		name := context.Params.ByName("name")
		path := "/a/" + name + "/c/d"
		context.JSON(map[string]interface{}{
			"path": path,
		})
	})

	r.Get("/a/b/:name/e", func(context *mygin.Context) {
		name := context.Params.ByName("name")
		path := "/a/b" + name + "/e"
		context.JSON(map[string]interface{}{
			"path": path,
		})
	})

	r.Get("/a/b/c/d", handleABC)

	// 启动服务器并监听端口
	r.Run(":8088")
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
curl -i http://localhost:8088/a/b/c
HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8
Date: Tue, 23 Jan 2024 05:43:50 GMT
Content-Length: 18

{"path":"/a/b/c"}
➜  ~ curl -i http://localhost:8088/a/b
HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8
Date: Tue, 23 Jan 2024 05:43:53 GMT
Content-Length: 16

{"path":"/a/b"}
➜  ~ curl -i http://localhost:8088/a/c
HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8
Date: Tue, 23 Jan 2024 05:43:57 GMT
Content-Length: 16

{"path":"/a/c"}
➜  ~ curl -i http://localhost:8088/a/b/c/d
HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8
Date: Tue, 23 Jan 2024 05:44:05 GMT
Content-Length: 20

{"path":"/a/b/c/d"}

➜  ~ curl -i http://localhost:8088/a/scott/c
HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8
Date: Tue, 23 Jan 2024 05:45:16 GMT
Content-Length: 22

{"path":"/a/scott/c"}
➜  ~ curl -i http://localhost:8088/a/scott/c/d
HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8
Date: Tue, 23 Jan 2024 05:45:22 GMT
Content-Length: 24

{"path":"/a/scott/c/d"}
➜  ~ curl -i http://localhost:8088/a/b/scott/e
HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8
Date: Tue, 23 Jan 2024 05:45:32 GMT
Content-Length: 23

{"path":"/a/bscott/e"}
许可协议

本文由scott-pb编写

快来参与讨论吧


本站由 [PengBin](/) 使用 [Stellar 1.26.3](https://github.com/xaoxuu/hexo-theme-stellar/tree/1.26.3) 主题创建。 本博客所有文章除特别声明外，均采用 [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/) 许可协议，转载请注明出处。