gin 之 httprouter

一个web框架运行效率是否足够高，很大一部分取决于其路由查找效率，当一个项目注册了数百个路由后，每次请求都要经过几十次甚至上百次的循环查找，这与只需要几次查找的效率是截然不同的。gin 在 golang 的 web 框架里面也是一个性能排在前面的框架，gin实现的路由查找效率也是很高的，它是基于基数树又称压缩前缀树来实现的，本文将会介绍这种数据结构，并通过gin的路由这部分的源码来看看gin是如何基于基数树来构建路由系统的。

基数树

首先需要了解什么是基数树，基数树可看做是以二进制位串为关键字的trie 树，是一种多叉树形结构。基数树支持插入、删除、查找操作。查找包括完全匹配、前缀匹配、前驱查找、后继查找。所有这些操作都是O(k)复杂度，其中k是所有字符串中最大的长度。它的结构如下图所示：

gin中的基数树

来看看gin 当中是怎么定义基数树中的node 数据结构的：

type node struct {
    path      string // 当前节点的路径
    indices   string // 当前节点的所有孩子节点路径的首字母组成的字符串
  wildChild bool   // 如果当前节点的孩子节点是通配符类型的（例如:user 或者 *）则为true，否则为false
  nType     nodeType // 节点类型，一共四种，root表示根节点，param 表示:user 冒号通配符节点，catchAll表示*通配符节点，static则是普通默认节点
    children  []*node  // 当前节点所有孩子节点
  handlers  HandlersChain // 当前节点的handerFunc 数组(如果有则前面的都是中间件，最后一个handerFunc 是注册路由时定义的最终的处理函数)
    fullPath  string //到当前节点的完整路径：父节点fullPath + 当前节点path
}

源代码

这里面每一个字段属性都是路由注册和查找必须的，其中的indeces是一个由当前节点的所有孩子节点路径的首字母组成的字符串，比如上面的基数树om节点，它的indices就是ua，wildChild节点表示是精确匹配还是通配符类型。

gin 中的路由定义

我们平常在使用gin 中是这么定义路由的：

r := gin.Default()

    // Ping test
    r.GET("/ping", func(c *gin.Context) {
        c.String(http.StatusOK, "pong")
    })

    // Get user value
    r.GET("/user/:name", func(c *gin.Context) {
        user := c.Params.ByName("name")
        value, ok := db[user]
        if ok {
            c.JSON(http.StatusOK, gin.H{"user": user, "value": value})
        } else {
            c.JSON(http.StatusOK, gin.H{"user": user, "status": "no value"})
        }
    })

可以看到先gin.Default方法生成默认的gin engine，然后在其上调用GET（或者POST等方法），定义好路径和handler就好了。在这个代码示例中我们注册了两条路由，那么这两条路由到底是怎么注册上去的呢，背后是怎么构建路由节点，然后又是怎么构建路由树的呢？这就需要跟踪到源码了。

路由的注册

路由的注册是在gin engine上调用对应GET 等方法传入路径和处理函数，但本质上是调用了Engine.addRoute方法，Engine.AddRoute方法获取对应路由树（GET路由树或者POST路由树）的根结点，然后在根节点上调用node.addRoute方法添加路由。这个node.addRoutie方法的源代码会比较长，但相信读者结合代码的注释说明和我下面画的路由注册流程图再加上断点追踪代码的运行还是能够理解整个路由的注册流程的。

func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {
  ... // 省略部分次要代码

    root := engine.trees.get(method) // gin 每个http method 一颗独立的路由树（比如POST方法和GET方法是两颗路由树）
    if root == nil { // 如果对应方法的路由树是空的则新建空的根节点（path字段为空）
        root = new(node)
        root.fullPath = "/"
        engine.trees = append(engine.trees, methodTree{method: method, root: root})
    }
    root.addRoute(path, handlers) // 在根节点上调用node.addRoute方法添加路由
}

func (n *node) addRoute(path string, handlers HandlersChain) {
    fullPath := path
    n.priority++

    // 如果是空树则直接插入该节点作为该树的根节点返回即可
    if len(n.path) == 0 && len(n.children) == 0 {
        n.insertChild(path, fullPath, handlers)
        n.nType = root
        return
    }

    parentFullPathIndex := 0

// walk 代码段的功能是一直循环直到在路由树中找到可以插入path路由的节点，在该节点上调用insertChild方法完成路由的注册
walk:
    for {
        // 获取当前节点path 和当前path的最长公共前缀长度（ex：n.path = "/user", path = "/user/2", i = 5）
        i := longestCommonPrefix(path, n.path)

        // 如果当前节点path长度大于最长公共前缀长度则需要分割当前path为两部分作为两个节点，当前节点的path变更为公共前缀部分，公共前缀之后部分作为新节点的path并成为当前节点的孩子节点
        if i < len(n.path) {
            child := node{
                path:      n.path[i:], // 取path非公共前缀的一部分
                wildChild: n.wildChild, // 其他属性继承当前节点
                indices:   n.indices, // 其他属性继承当前节点
                children:  n.children, // 新节点成为当前节点所有孩子的新父节点
                handlers:  n.handlers, // 其他属性继承当前节点 
                fullPath:  n.fullPath, // 其他属性继承当前节点
            }

            n.children = []*node{&child} // 当前节点的孩子节点变更为新节点
            n.indices = bytesconv.BytesToString([]byte{n.path[i]}) // indices 取孩子节点的第一个字符
            n.path = path[:i] // path 变更为公共前缀
            n.handlers = nil // 因为当前节点path经过分割后fullpath已经不是一条完整的路由路径所以handlers置为nil
            n.fullPath = fullPath[:parentFullPathIndex+i] // fullpath变更
        }

        // 如果当前path的长度要大于最长公共前缀长度，则非公共前缀部分要么直接成为当前节点的孩子节点之一（非公共前缀部分和当前节点所有孩子的path完全没有公共部分），要么找到一个和当前path有公共前缀的孩子节点继续walk代码段
        if i < len(path) {
            path = path[i:] // path 变更为非公共后半部分

            if n.wildChild { // 如果当前节点的孩子节点是通配符类型