Router

目标

  • 使用 Trie 树实现动态路由(dynamic route)解析。
  • 支持两种模式:name和*filepath。

Trie树

  • 前面使用map构建路由表，通过map索引只能实现简单的静态路由。但是动态路由就需要用另一种方法（trie树）。

  • 在之前学习算法的时候每个节点存放的是一个字符，这个路由无非就是把每个节点存放路由对应的字符串（路由中的一部分）。并且添加两种模式参数匹配:name和通配*filepath。

image-20221203205818813

trie.go

每个节点结构体信息

1
2
3
4
5
6
type node struct {
	pattern  string // 待匹配路由，例如 /p/:lang
	part     string // 路由中的一部分，例如 :lang
	children []*node // 子节点，例如 [doc, tutorial, intro]
	isWild   bool // 是否精确匹配，part 含有 : 或 * 时为true
}

匹配函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 第一个匹配成功的节点，用于插入
func (n *node) matchChild(part string) *node {
   for _, child := range n.children {
      if child.part == part || child.isWild {
         return child
      }
   }
   return nil
}

// 所有匹配成功的节点，用于查找
func (n *node) matchChildren(part string) []*node {
   nodes := make([]*node, 0)
   for _, child := range n.children {
      if child.part == part || child.isWild {
         nodes = append(nodes, child)
      }
   }
   return nodes
}

插入和查找函数

  • 插入：递归查找每一层的节点，如果没有匹配到当前part的节点，则新建一个。
  • 查找：递归查询每一层的节点，退出规则是，匹配到了*，匹配失败，或者匹配到了第len(parts)层节点。
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
// 插入节点
func (n *node) insert(pattern string, parts []string, height int) {
   // 如果height已经到达字符串数组末尾直接返回
   if len(parts) == height {
      n.pattern = pattern
      return
   }

   // 当前节点对应的part
   part := parts[height]
   child := n.matchChild(part) // 第一个匹配成功的节点
   if child == nil {
      // 新建一个结点加入到当前节点的孩子数组中去
      child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
      n.children = append(n.children, child)
   }
   child.insert(pattern, parts, height+1) // 继续往下找
}

// 查找节点
func (n *node) search(parts []string, height int) *node {
   // 如果是height已经遍历完parts或者n.part包含字符*前缀就直接返回当前节点
   if len(parts) == height || strings.HasPrefix(n.part, "*") {
      if n.pattern == "" {
         return nil
      }
      return n
   }

   part := parts[height]
   children := n.matchChildren(part) // 当前节点的孩子节点的数组

   for _, child := range children {
      result := child.search(parts, height+1) // 递归往下找节点
      if result != nil {
         return result
      }
   }

   return nil
}

Router路由

将Trie树应用到路由中

  • roots存储每种请求方式的Trie树的根节点
  • handlers存储每种请求方式的HandlerFunc
1
2
3
4
type router struct {
	roots    map[string]*node
	handlers map[string]HandlerFunc
}

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
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
func newRouter() *router {
   return &router{
      roots:    make(map[string]*node),
      handlers: make(map[string]HandlerFunc),
   }
}

// 将pattern拆分并返回一个parts字符串数组
func parsePattern(pattern string) []string {
   vs := strings.Split(pattern, "/") // 按照"/"拆分

   parts := make([]string, 0)
   for _, item := range vs {
      if item != "" {
         parts = append(parts, item)
         if item[0] == '*' {
            break
         }
      }
   }
   return parts
}

// 添加路由信息，并将路由信息映射到对应的处理函数
func (r *router) addRoute(method string, pattern string, handler HandlerFunc) {
   parts := parsePattern(pattern) // 获取路径数组

   key := method + "-" + pattern
   _, ok := r.roots[method] // 检查这个方法是否有对应的根节点，没有就创建一个根节点
   if !ok {                 // 如果不存在
      r.roots[method] = &node{}
   }
   r.roots[method].insert(pattern, parts, 0) // 将路径插入到trie树中去
   r.handlers[key] = handler                 // 将路由信息映射到对应的处理函数
}

// 获取路由信息
func (r *router) getRoute(method string, path string) (*node, map[string]string) {
   searchParts := parsePattern(path) // 获取路径数组
   params := make(map[string]string)
   root, ok := r.roots[method]

   if !ok {
      return nil, nil
   }

   n := root.search(searchParts, 0) // 从根节点往下查询，直至查找到节点

   if n != nil {
      parts := parsePattern(n.pattern)
      for index, part := range parts {
         if part[0] == ':' { // 模糊匹配
            params[part[1:]] = searchParts[index] // 查找下去
         }
         if part[0] == '*' && len(part) > 1 { // 直接匹配到*
            params[part[1:]] = strings.Join(searchParts[index:], "/")
            break
         }
      }
      return n, params
   }

   return nil, nil
}

func (r *router) getRoutes(method string) []*node {
   root, ok := r.roots[method]
   if !ok {
      return nil
   }
   nodes := make([]*node, 0)
   root.travel(&nodes)
   return nodes
}

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)
   }
}

context.go

需要对 Context 对象增加一个属性和方法，来提供对路由参数的访问。我们将解析后的参数存储到Params中，通过c.Param("lang")的方式获取到对应的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type Context struct {
	// origin objects
	Writer http.ResponseWriter
	Req    *http.Request
	// request info
	Path   string
	Method string
	Params map[string]string
	// response info
	StatusCode int
}

func (c *Context) Param(key string) string {
	value, _ := c.Params[key]
	return value
}

main.go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func main() {
   r := gee.New()
   r.GET("/", func(c *gee.Context) {
      c.HTML(http.StatusOK, "<h1>Hello Gee</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(":9999")
}