httprouter源码解析

背景

gin框架采用了httprouter进行路由匹配，所以废话少说，这篇文章来帮你了解他的源码实现

树

httprouter的路由匹配功能是基于radix tree(前缀树/基数树)这种数据结构实现的：
img
有读者可能会有疑问：为什么不按照RUL分隔符切割的来分割，每个segment作为一个节点，而是要用公共前缀来分割？针对这个疑问，了解树的开发者都知道，树的高度是影响查找效率的重要因素，高度越高，查找效率越低。两张图片来对比一下:
img
img

源码

demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import (
    "fmt"
    "net/http"
    "log"

    "github.com/julienschmidt/httprouter"
)

func Index(w http.ResponseWriter, r *http.Request, _ httprouter.Params) {
    fmt.Fprint(w, "Welcome!\n")
}

func Hello(w http.ResponseWriter, r *http.Request, ps httprouter.Params) {
    fmt.Fprintf(w, "hello, %s!\n", ps.ByName("name"))
}

func main() {
    router := httprouter.New()
    router.GET("/", Index)
    router.GET("/hello/:name", Hello)

    log.Fatal(http.ListenAndServe(":8080", router))
}

首先看到 httprouter.New()，因为它返回一个router实例：

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
func New() *Router {
	return &Router{
		RedirectTrailingSlash:  true,
		RedirectFixedPath:      true,
		HandleMethodNotAllowed: true,
		HandleOPTIONS:          true,
	}
}

// Router is a http.Handler which can be used to dispatch requests to different
// handler functions via configurable routes
type Router struct {
	trees map[string]*node

	paramsPool sync.Pool
	maxParams  uint16
	SaveMatchedRoutePath bool
	RedirectTrailingSlash bool
	RedirectFixedPath bool
	HandleMethodNotAllowed bool
	HandleOPTIONS bool
	GlobalOPTIONS http.Handler
	globalAllowed string
	NotFound http.Handler
	MethodNotAllowed http.Handler
	PanicHandler func(http.ResponseWriter, *http.Request, interface{})
}

它实现了 ServeHTTP 这个函数，因此符合 net/http.Handler 接口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// ServeHTTP makes the router implement the http.Handler interface.
func (r *Router) ServeHTTP(w http.ResponseWriter, req *http.Request) {
	if r.PanicHandler != nil {
		defer r.recv(w, req)
	}

	path := req.URL.Path

	if root := r.trees[req.Method]; root != nil {
		if handle, ps, tsr := root.getValue(path, r.getParams); handle != nil {
			if ps != nil {
				handle(w, req, *ps)
				r.putParams(ps)
			} else {
				handle(w, req, nil)
			}
			return
    ...
}

这就是处理请求的时候，查找路由树及handler的那部分，root.getValue就是查找路由树的具体函数，不过细节此处不表。

我们接下来看看注册路由的那部分：

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
// GET is a shortcut for router.Handle(http.MethodGet, path, handle)
func (r *Router) GET(path string, handle Handle) {
	r.Handle(http.MethodGet, path, handle)
}

// 跟进 r.Handle 函数之后发现调用了 addRoute 函数

// addRoute adds a node with the given handle to the path.
// Not concurrency-safe!
func (n *node) addRoute(path string, handle Handle) {
	fullPath := path
	n.priority++

	// Empty tree
	if len(n.path) == 0 && len(n.indices) == 0 {
		n.insertChild(path, fullPath, handle)
		n.nType = root
		return
	}

walk:
	for {
    ...
}

而 addRoute 函数就是实现radix tree这个数据结构的函数了，它会先找到共同的部分，然后考虑是否把路由切分为字节点，最后 把handler写上去(调用 insertChild 函数)。

1
2
3
4
5
6
7
8
9
type node struct {
	path      string // URL
	indices   string // 字节点的首字母拼成的string，顺序与 children 一致
	wildChild bool // 是否是泛匹配
	nType     nodeType // 节点类型
	priority  uint32 // 优先级
	children  []*node // 子节点
	handle    Handle // 处理函数
}

node就是保存这些资料的radix tree的节点