gin的路由算法

gin的是路由算法其实就是一个Trie树(也就是前缀树). 有关数据结构的可以自己去网上找相关资料查看.

注册路由预处理

我们在使用gin时通过下面的代码注册路由

普通注册

router.GET("/ping", func(context *gin.Context) {

    context.JSON(http.StatusOK, gin.H{"message": "pong"})

})

使用中间件

router.Use(gin.Recovery())

使用Group

v1 := router.Group("v1")

v1.GET("/ping", func(context *gin.Context) {

	context.JSON(http.StatusOK, gin.H{"message": "pong"})

})

具体实现

func (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {

	absolutePath := group.calculateAbsolutePath(relativePath)

	handlers = group.combineHandlers(handlers)

	group.engine.addRoute(httpMethod, absolutePath, handlers)

	return group.returnObj()

}

在调用POST, GET, HEAD等路由HTTP相关函数时, 会调用handle函数

如果调用了中间件的话, 会调用下面函数

// Use adds middleware to the group, see example code in GitHub.

func (group *RouterGroup) Use(middleware ...HandlerFunc) IRoutes {

	group.Handlers = append(group.Handlers, middleware...)

	return group.returnObj()

}

如果使用了Group的话, 会调用下面函数

func (group *RouterGroup) Group(relativePath string, handlers ...HandlerFunc) *RouterGroup {

	return &RouterGroup{

		Handlers: group.combineHandlers(handlers),

		basePath: group.calculateAbsolutePath(relativePath),

		engine:   group.engine,

	}

}

重点关注下面两个函数:

// routergroup.go:L208-217

func (group *RouterGroup) combineHandlers(handlers HandlersChain) HandlersChain {

    finalSize := len(group.Handlers) + len(handlers)

    if finalSize >= int(abortIndex) {

        panic("too many handlers")

    }

    mergedHandlers := make(HandlersChain, finalSize)

    copy(mergedHandlers, group.Handlers)

    copy(mergedHandlers[len(group.Handlers):], handlers)

    return mergedHandlers

}

func (group *RouterGroup) calculateAbsolutePath(relativePath string) string {

    return joinPaths(group.basePath, relativePath)

}

func joinPaths(absolutePath, relativePath string) string {

    if relativePath == "" {

        return absolutePath

    }

    finalPath := path.Join(absolutePath, relativePath)

    appendSlash := lastChar(relativePath) == '/' && lastChar(finalPath) != '/'

    if appendSlash {

        return finalPath + "/"

    }

    return finalPath

}

综合来看, 在预处理阶段

1.在调用中间件的时候, 是将某个路由的handler处理函数和中间件的处理函数都放在了Handlers的数组中 2.在调用Group的时候, 是将路由的path上面拼上Group的值. 也就是/user/:name, 会变成v1/user:name

真正注册

func (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {

	absolutePath := group.calculateAbsolutePath(relativePath)

	handlers = group.combineHandlers(handlers)

	group.engine.addRoute(httpMethod, absolutePath, handlers)

	return group.returnObj()

}

调用group.engine.addRoute(httpMethod, absolutePath, handlers)将预处理阶段的结果注册到gin Engine的trees上

gin路由树简单介绍

gin的路由树算法是一棵前缀树. 不过并不是只有一颗树, 而是每种方法(POST, GET ...)都有自己的一颗树

func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {

	assert1(path[0] == '/', "path must begin with '/'")

	assert1(method != "", "HTTP method can not be empty")

	assert1(len(handlers) > 0, "there must be at least one handler")

	debugPrintRoute(method, path, handlers)

	root := engine.trees.get(method)

	if root == nil {

		root = new(node)

		root.fullPath = "/"

		engine.trees = append(engine.trees, methodTree{method: method, root: root})

	}

	root.addRoute(path, handlers)

	// Update maxParams

	if paramsCount := countParams(path); paramsCount > engine.maxParams {

		engine.maxParams = paramsCount

	}

	if sectionsCount := countSections(path); sectionsCount > engine.maxSections {

		engine.maxSections = sectionsCount

	}

}

gin 路由最终的样子大概是下面的样子

type node struct {

	path      string

	indices   string

	wildChild bool

	nType     nodeType

	priority  uint32

	children  []*node // child nodes, at most 1 :param style node at the end of the array

	handlers  HandlersChain

	fullPath  string

}

其实gin的实现不像一个真正的树, children []*node所有的孩子都放在这个数组里面, 利用indices, priority变相实现一棵树

获取路由handler

当服务端收到客户端的请求时, 根据path去trees匹配到相关的路由, 拿到相关的处理handlers

...

	// Find root of the tree for the given HTTP method

	t := engine.trees

	for i, tl := 0, len(t); i < tl; i++ {

		if t[i].method != httpMethod {

			continue

		}

		root := t[i].root

		// Find route in tree

		value := root.getValue(rPath, c.params, c.skippedNodes, unescape)

		if value.params != nil {

			c.Params = *value.params

		}

		if value.handlers != nil {

			c.handlers = value.handlers  // 看这里

			c.fullPath = value.fullPath

			c.Next()

			c.writermem.WriteHeaderNow()

			return

		}

		if httpMethod != "CONNECT" && rPath != "/" {

			if value.tsr && engine.RedirectTrailingSlash {

				redirectTrailingSlash(c)

				return

			}

			if engine.RedirectFixedPath && redirectFixedPath(c, root, engine.RedirectFixedPath) {

				return

			}

		}

		break

	}

...

主要在下面这个函数里面调用程序注册的路由处理函数

func (c *Context) Next() {

	c.index++

	for c.index < int8(len(c.handlers)) {

		c.handlers[c.index](c)

		c.index++

	}

}

参考链接

巴特西

gin的源码解读4-gin的路由算法