一文搞懂gin框架httprouter路由实现原理
站长
· 阅读数 15
路由原理
压缩字典树Radix Tree
gin框架中采用的路由库是基于httprouter做的,httprouter的实现原理是使用了一个radix tree（压缩字典树）来管理请求Url的。基数树是一种更节省空间的前缀树，对于基数树的每个节点，如果该节点是唯一的子树的话，就和父节点合并。
httprouter会对每种http方法(post,get等)都会生成一颗基数树，树是由一个个节点构成的，其中树节点node结构如下：
type node struct {
// 保存这个节点上的URL路径
// 例如上图中的search和support, 共同的parent节点的path="s"
// 后面两个节点的path分别是"earch"和"upport"
path string
// 判断当前节点路径是不是参数节点, 例如上图的:post部分就是wildChild节点
wildChild bool
// 节点类型包括static, root, param, catchAll
// static: 静态节点, 例如上面分裂出来作为parent的s
// root: 如果插入的节点是第一个, 那么是root节点
// catchAll: 有*匹配的节点
// param: 除上面外的节点
nType nodeType
// 记录路径上最大参数个数
maxParams uint8
// 和children[]对应, 保存的是分裂的分支的第一个字符
// 例如search和support, 那么s节点的indices对应的"eu"
// 代表有两个分支, 分支的首字母分别是e和u
indices string
// 保存孩子节点
children []*node
// 当前节点的处理函数
handle Handle
// 优先级, 看起来没什么卵用的样子@_@
priority uint32
}
注册路由
注册路由主要涉及到两个函数，addRoute和insetChild,下面主要看看这两个函数：
addRoute
// tree.go
// addRoute 将具有给定句柄的节点添加到路径中。
// 不是并发安全的
func (n *node) addRoute(path string, handlers HandlersChain) {
// 构造路由树
fullPath := path
n.priority++
numParams := countParams(path) // 数一下参数个数
// Empty tree 空树直接插入当前节点
if len(n.path) == 0 && len(n.children) == 0 {
// 构造基数树
n.insertChild(path, fullPath, handlers)
n.nType = root
return
}
parentFullPathIndex := 0
walk:
for {
// 更新当前节点的最大参数个数
if numParams > n.maxParams {
n.maxParams = numParams
}
// 找到最长的通用前缀
// 这也意味着公共前缀不包含“:”"或“*” /
// 因为现有键不能包含这些字符。
i := longestCommonPrefix(path, n.path)
// 分裂边缘（此处分裂的是当前树节点）
// 例如一开始path是search，新加入support，s是他们通用的最长前缀部分
// 那么会将s拿出来作为parent节点，增加earch和upport作为child节点
if i < len(n.path) {
child := node{
path: n.path[i:], // 公共前缀后的部分作为子节点
wildChild: n.wildChild,
indices: n.indices,
children: n.children,
handlers: n.handlers,
priority: n.priority - 1, //子节点优先级-1
fullPath: n.fullPath,
}
// Update maxParams (max of all children)
for _, v := range child.children {
if v.maxParams > child.maxParams {
child.maxParams = v.maxParams
}
}
n.children = []*node{&child}
// []byte for proper unicode char conversion, see #65
n.indices = string([]byte{n.path[i]})
n.path = path[:i]
n.handlers = nil
n.wildChild = false
n.fullPath = fullPath[:parentFullPathIndex+i]
}
// 将新来的节点插入新的parent节点作为子节点
if i < len(path) {
path = path[i:]
if n.wildChild { // 如果是参数节点
parentFullPathIndex += len(n.path)
n = n.children[0]
n.priority++
// Update maxParams of the child node
if numParams > n.maxParams {
n.maxParams = numParams
}
numParams--
// 检查通配符是否匹配
if len(path) >= len(n.path) && n.path == path[:len(n.path)] {
// 检查更长的通配符, 例如 :name and :names
if len(n.path) >= len(path) || path[len(n.path)] == '/' {
continue walk
}
}
pathSeg := path
if n.nType != catchAll {
pathSeg = strings.SplitN(path, "/", 2)[0]
}
prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
panic("'" + pathSeg +
"' in new path '" + fullPath +
"' conflicts with existing wildcard '" + n.path +
"' in existing prefix '" + prefix +
"'")
}
// 取path首字母，用来与indices做比较
c := path[0]
// 处理参数后加斜线情况
if n.nType == param && c == '/' && len(n.children) == 1 {
parentFullPathIndex += len(n.path)
n = n.children[0]
n.priority++
continue walk
}
// 检查路path下一个字节的子节点是否存在
// 比如s的子节点现在是earch和upport，indices为eu
// 如果新加一个路由为super，那么就是和upport有匹配的部分u，将继续分列现在的upport节点
for i, max := 0, len(n.indices); i < max; i++ {
if c == n.indices[i] {
parentFullPathIndex += len(n.path)
i = n.incrementChildPrio(i)
n = n.children[i]
continue walk
}
}
// 否则就插入
if c != ':' && c != '*' {
// []byte for proper unicode char conversion, see #65
// 注意这里是直接拼接第一个字符到n.indices
n.indices += string([]byte{c})
child := &node{
maxParams: numParams,
fullPath: fullPath,
}
// 追加子节点
n.children = append(n.children, child)
n.incrementChildPrio(len(n.indices) - 1)
n = child
}
n.insertChild(numParams, path, fullPath, handlers)
return
}
// 已经注册过的节点
if n.handlers != nil {
panic("handlers are already registered for path '" + fullPath + "'")
}
n.handlers = handlers
return
}
}
上面函数的目的是找到插入节点的位置，需要啊注意如果存在common前缀，name需要将节点进行分裂，然后再插入child节点，路有树构造的过程如下：
insertChild
// tree.go
func (n *node) insertChild(numParams uint8, path string, fullPath string, handlers HandlersChain) {
// 找到所有的参数
for numParams > 0 {
// 查找前缀直到第一个通配符
wildcard, i, valid := findWildcard(path)
if i < 0 { // 没有发现通配符
break
}
// 通配符的名称必须包含':' 和 '*'
if !valid {
panic("only one wildcard per path segment is allowed, has: '" +
wildcard + "' in path '" + fullPath + "'")
}
// 检查通配符是否有名称
if len(wildcard) < 2 {
panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
}
// 检查这个节点是否有已经存在的子节点
// 如果我们在这里插入通配符，这些子节点将无法访问
if len(n.children) > 0 {
panic("wildcard segment '" + wildcard +
"' conflicts with existing children in path '" + fullPath + "'")
}
if wildcard[0] == ':' { // param
if i > 0 {
// 在当前通配符之前插入前缀
n.path = path[:i]
path = path[i:]
}
n.wildChild = true
child := &node{
nType: param,
path: wildcard,
maxParams: numParams,
fullPath: fullPath,
}
n.children = []*node{child}
n = child
n.priority++
numParams--
// 如果路径没有以通配符结束
// 那么将有另一个以'/'开始的非通配符子路径。
if len(wildcard) < len(path) {
path = path[len(wildcard):]
child := &node{
maxParams: numParams,
priority: 1,
fullPath: fullPath,
}
n.children = []*node{child}
n = child // 继续下一轮循环
continue
}
// 否则我们就完成了。将处理函数插入新叶子中
n.handlers = handlers
return
}
// catchAll
if i+len(wildcard) != len(path) || numParams > 1 {
panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
}
if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
}
// currently fixed width 1 for '/'
i--
if path[i] != '/' {
panic("no / before catch-all in path '" + fullPath + "'")
}
n.path = path[:i]
// 第一个节点:路径为空的catchAll节点
child := &node{
wildChild: true,
nType: catchAll,
maxParams: 1,
fullPath: fullPath,
}
// 更新父节点的maxParams
if n.maxParams < 1 {
n.maxParams = 1
}
n.children = []*node{child}
n.indices = string('/')
n = child
n.priority++
// 第二个节点:保存变量的节点
child = &node{
path: path[i:],
nType: catchAll,
maxParams: 1,
handlers: handlers,
priority: 1,
fullPath: fullPath,
}
n.children = []*node{child}
return
}
// 如果没有找到通配符，只需插入路径和句柄
n.path = path
n.handlers = handlers
n.fullPath = fullPath
}
insertChild函数是根据path本身进行分隔，将/分开的部分分别作为节点保存，行程一颗数结构。参数匹配中的:和*的区别是，前者是匹配一个字段，而后者是匹配后面所有的路径。
路由匹配
路由匹配过程其实就是匹配每个child的path，walk直到path最后。
gin框架处理请求的入口函数ServeHttp
// gin.go
func (engine *Engine) ServeHTTP(w http.ResponseWriter, req *http.Request) {
// 这里使用了对象池,从对象池中获取一个对象，减少gc,内存申请的频率,
c := engine.pool.Get().(*Context) // 类型断言，强制转换Context指针
// 这里有一个细节就是Get对象后做初始化
c.writermem.reset(w)
c.Request = req
c.reset()
engine.handleHTTPRequest(c) // 我们要找的处理HTTP请求的函数
engine.pool.Put(c) // 处理完请求后将对象放回池子
}
// gin.go
func (engine *Engine) handleHTTPRequest(c *Context) {
// ...
// 根据请求方法找到对应的路由树
t := engine.trees
for i, tl := 0, len(t); i < tl; i++ {
if t[i].method != httpMethod {
continue
}
root := t[i].root
// 在路由树中根据path查找
value := root.getValue(rPath, c.Params, unescape)
if value.handlers != nil {
c.handlers = value.handlers
c.Params = value.params
c.fullPath = value.fullPath
c.Next() // 执行函数链条
c.writermem.WriteHeaderNow()
return
}
// ...
c.handlers = engine.allNoRoute
serveError(c, http.StatusNotFound, default404Body)
}
路由匹配是由节点的getValue方法实现的，getValue根据给定的路径返回nodeValue值，保存注册的处理函数和匹配到的路径参数数据。
如果找不到任何处理函数，则会常识TSR（尾随斜杠重定向）。
// tree.go
type nodeValue struct {
handlers HandlersChain
params Params // []Param
tsr bool
fullPath string
}
// ..
func (n *node) getValue(path string, po Params, unescape bool) (value nodeValue) {
value.params = po
walk: // Outer loop for walking the tree
for {
prefix := n.path
if path == prefix {
// 我们应该已经到达包含处理函数的节点。
// 检查该节点是否注册有处理函数
if value.handlers = n.handlers; value.handlers != nil {
value.fullPath = n.fullPath
return
}
if path == "/" && n.wildChild && n.nType != root {
value.tsr = true
return
}
// 没有找到处理函数 检查这个路径末尾+/ 是否存在注册函数
indices := n.indices
for i, max := 0, len(indices); i < max; i++ {
if indices[i] == '/' {
n = n.children[i]
value.tsr = (len(n.path) == 1 && n.handlers != nil) ||
(n.nType == catchAll && n.children[0].handlers != nil)
return
}
}
return
}
if len(path) > len(prefix) && path[:len(prefix)] == prefix {
path = path[len(prefix):]
// 如果该节点没有通配符(param或catchAll)子节点
// 我们可以继续查找下一个子节点
if !n.wildChild {
c := path[0]
indices := n.indices
for i, max := 0, len(indices); i < max; i++ {
if c == indices[i] {
n = n.children[i] // 遍历树
continue walk
}
}
// 没找到
// 如果存在一个相同的URL但没有末尾/的叶子节点
// 我们可以建议重定向到那里
value.tsr = path == "/" && n.handlers != nil
return
}
// 根据节点类型处理通配符子节点
n = n.children[0]
switch n.nType {
case param:
// find param end (either '/' or path end)
end := 0
for end < len(path) && path[end] != '/' {
end++
}
// 保存通配符的值
if cap(value.params) < int(n.maxParams) {
value.params = make(Params, 0, n.maxParams)
}
i := len(value.params)
value.params = value.params[:i+1] // 在预先分配的容量内扩展slice
value.params[i].Key = n.path[1:]
val := path[:end]
if unescape {
var err error
if value.params[i].Value, err = url.QueryUnescape(val); err != nil {
value.params[i].Value = val // fallback, in case of error
}
} else {
value.params[i].Value = val
}
// 继续向下查询
if end < len(path) {
if len(n.children) > 0 {
path = path[end:]
n = n.children[0]
continue walk
}
// ... but we can't
value.tsr = len(path) == end+1
return
}
if value.handlers = n.handlers; value.handlers != nil {
value.fullPath = n.fullPath
return
}
if len(n.children) == 1 {
// 没有找到处理函数. 检查此路径末尾加/的路由是否存在注册函数
// 用于 TSR 推荐
n = n.children[0]
value.tsr = n.path == "/" && n.handlers != nil
}
return
case catchAll:
// 保存通配符的值
if cap(value.params) < int(n.maxParams) {
value.params = make(Params, 0, n.maxParams)
}
i := len(value.params)
value.params = value.params[:i+1] // 在预先分配的容量内扩展slice
value.params[i].Key = n.path[2:]
if unescape {
var err error
if value.params[i].Value, err = url.QueryUnescape(path); err != nil {
value.params[i].Value = path // fallback, in case of error
}
} else {
value.params[i].Value = path
}
value.handlers = n.handlers
value.fullPath = n.fullPath
return
default:
panic("invalid node type")
}
}
// 找不到，如果存在一个在当前路径最后添加/的路由
// 我们会建议重定向到那里
value.tsr = (path == "/") ||
(len(prefix) == len(path)+1 && prefix[len(path)] == '/' &&
path == prefix[:len(prefix)-1] && n.handlers != nil)
return
}
}