关于前端:关于-GIN-的路由树

GIN 是一个 golang 罕用的 Web 框架，它对 API 比拟敌对，源码正文也很明确明确，应用起来疾速灵便，还有极高的容错率。题目中的路由咱们能够简略了解为在浏览器中输出的页面地址，而“树”则是一种优化的数据结构。因为在 GIN 这个 Web 框架中的路由树是前缀树，所以咱们明天会围绕前缀树来解说。

前缀树其实就是 Tire 树，是哈希树的变种，通常大家都叫它单词查找树。前缀树多利用于统计，排序和保留大量字符串。因为前缀树可能利用字符串的公共前缀缩小查问工夫，最大限度地缩小不必要的字符串比拟。所以前缀树也常常被搜索引擎零碎用于文本词频统计。前缀树领有以下特点：

根节点不蕴含字符，其余节点都蕴含字符
每一层的节点内容不同
从根节点到某一个节点，门路上通过的字符连接起来，为该节点对应的字符串
每个节点的子节点通常有一个标记位，用来标识单词的完结

以小时候查新华字典为例，咱们来直观认识一下前缀树。置信大家都用过音序查字法这种查找形式，其操作内容如下：

读准字音，依据该字音节确定应查什么字母。
在“汉语拼音音节索引”中找到这一字母，在这一字母相应局部找到该字的音节，看清这个音节旁表明的页码。
按此页码打开字典的注释，按四声程序找出所要查的字。

这整个流程其实能够看做一个粗略的前缀树查找流程 ，比方说要查找成语“心想事成”中的“心想”两字，在字典中即如下构造：

在查找的过程中，咱们依据首字母 x，找到 x 当中的 xi 这一独特局部，而后再依据不同的字母找到所对应的残余局部。放到前缀树查找上，案例中的“心”对应 xi -> n，而“想”则对应 xi -> ang

GIN 中的前缀树相比一般的前缀树缩小了查问的层级，比如说上方咱们想查找的“心想”其中 xi 做为共有的局部，其实能够被调配在同一层同一个节点当中而不是分为两局部：

这样的就是紧凑前缀树，同理如果咱们有如下四个路由，他们所造成的紧凑前缀树就会是这个样子：

r.GET("/", handle1)
r.GET("/product", handle2)
r.GET("/product/:id", handle3)
r.GET("/product/:name", handle4)

在节点中存储信息

通过下面的内容能够看出，GIN 中前缀树整条查问的地址只需通过路由树中每个节点的拼接即可取得。那么 GIN 是如何实现在这些节点的减少的呢，每个节点中又寄存了什么内容？这个问题咱们能够通过 GIN 的源码失去答案。

首先 GIN 中罕用的申明路由的形式如下：

func main(){r := gin.Default()
    r.GET("/", func(context *gin.Context) {
        context.JSON(200, gin.H{"status":"ok",})
    })
    r.Run()}

// default 会初始化一个 engin 实例
func Default() *Engine {debugPrintWARNINGDefault()
    engine := New()
    engine.Use(Logger(), Recovery())
    return engine
}

type Engine struct { 
    RouterGroup
        // type RouterGroup struct {
    //    Handlers HandlersChain
        //    basePath string
        //    engine   *Engine
        //    root     bool
        // }
        // 小写公有的，不凋谢
    trees            methodTrees 
        // ...
}

type methodTrees []methodTree

type methodTree struct {
    method string
    root   *node
}

// trees 路由树这一部分由一个带有 method 和 root 字段的 node 列表保护
// 每个 node 代表了路由树中的每一个节点
// node 所具备的字段内容如下

type node struct {
    path      string // 以后节点的绝对路径
    indices   string // 缓存下一节点的第一个字符 在遇到子节点为通配符类型的状况下,indices=''// 默认是 false，当 children 是 通配符类型时，wildChild 为 true 即 indices=''
    wildChild bool // 默认是 false，当 children 是 通配符类型时，wildChild 为 true

        // 节点的类型，因为在通配符的场景下在查问的时候须要非凡解决，// 默认是 static 类型
        // 根节点为 root 类型
        // 对于 path 蕴含冒号通配符的状况，nType 是 param 类型
        // 对于蕴含 * 通配符的状况，nType 类型是 catchAll 类型
    nType     nodeType
        // 代表了有几条路由会通过此节点，用于在节点
    priority  uint32
        // 子节点列表
    children  []*node // child nodes, at most 1 :param style node at the end of the array
    handlers  HandlersChain
        // 是从 root 节点到以后节点的全副 path 局部；如果此节点为终结节点 handlers 为对应的解决链，否则为 nil；// maxParams 是以后节点到各个叶子节点的蕴含的通配符的最大数量
    fullPath  string
}

// 具体节点类型如下
const (static nodeType = iota // default，动态节点，一般匹配 (/user)
    root                   // 根节点 (/)
    param                 // 参数节点 (/user/:id)
    catchAll              // 通用匹配，匹配任意参数 (*user)
)

增加路由则能够通过以下操作：

// 在创立路由的过程中，每一个办法都会最终都会被解析后丢给 handle 函数去解决
func main(){r := gin.Default()
    r.GET("/", func(context *gin.Context) {
        context.JSON(200, gin.H{"status":"ok",})
    })
    r.Run()}

func (group *RouterGroup) GET(relativePath string, handlers ...HandlerFunc) IRoutes {return group.handle(http.MethodGet, relativePath, handlers)
}
func (group *RouterGroup) POST(relativePath string, handlers ...HandlerFunc) IRoutes {return group.handle(http.MethodPost, relativePath, handlers)
}

//  handle 函数中会将绝对路径转换为相对路径
//  并将 申请办法、相对路径、解决办法 传给 addRoute
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()}


// 路由的增加次要在 addRoute 这个函数中实现
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")

   // 如果开启了 gin 的 debug 模式，则对应解决
   debugPrintRoute(method, path, handlers)
   // 依据申请形式获取对应的树的根
   // 每一个申请办法都有本人对应的一颗紧凑前缀树，这里通过申请办法拿到最顶部的根
   root := engine.trees.get(method)
   // 如果根为空，则示意这是第一个路由，则本人创立一个以 / 为 path 的根节点
   if root == nil {
      // 如果没有就创立
      root = new(node)
      root.fullPath = "/"
      engine.trees = append(engine.trees, methodTree{method: method, root: root})
   }
   // 此处的 path 是子路由
   // 以上内容是做了一层预校验，防止书写不标准导致的申请查问不到
   // 接下来是增加路由的注释
   root.addRoute(path, handlers)
}

// addRoute adds a node with the given handle to the path.
// Not concurrency-safe! 并发不平安
func (n *node) addRoute(path string, handlers HandlersChain) {
    fullPath := path
        // 增加实现后，通过此节点的路由条数将会 +1
    n.priority++

    // Empty tree
        // 如果为空树，即只有一个根节点 "/" 则插入一个子节点，并将以后节点设置为 root 类型的节点
    if len(n.path) == 0 && len(n.children) == 0 {n.insertChild(path, fullPath, handlers)
        n.nType = root
        return
    }

    parentFullPathIndex := 0

walk:
    for {
        // Find the longest common prefix.
        // This also implies that the common prefix contains no ':' or '*'
        // since the existing key can't contain those chars.
                // 找到最长的共有前缀的长度 即到 i 地位 path[i] == n.path[i]
        i := longestCommonPrefix(path, n.path)

        // Split edge
                // 假如以后节点存在的前缀信息为 hello
                // 现有前缀信息为 heo 的结点进入，则以后节点须要被拆分
                // 拆分成为 he 节点 以及 (llo 和 o 两个子节点)
        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,
                fullPath:  n.fullPath,
            }

            n.children = []*node{&child}
            // []byte for proper unicode char conversion, see #65
            n.indices = bytesconv.BytesToString([]byte{n.path[i]})
            n.path = path[:i]
            n.handlers = nil
            n.wildChild = false
            n.fullPath = fullPath[:parentFullPathIndex+i]
        }

        // Make new node a child of this node
                // 将新来的节点插入新的 parent 节点作为子节点
        if i < len(path) {path = path[i:]
            c := path[0]

            // '/' after param
                        // 如果是参数节点 形如 /:i
            if n.nType == param && c == '/' && len(n.children) == 1 {parentFullPathIndex += len(n.path)
                n = n.children[0]
                n.priority++
                continue walk
            }

            // Check if a child with the next path byte exists
            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
                }
            }

            // Otherwise insert it
            if c != ':' && c != '*' && n.nType != catchAll {// []byte for proper unicode char conversion, see #65
                n.indices += bytesconv.BytesToString([]byte{c})
                child := &node{fullPath: fullPath,}
                n.addChild(child)
                n.incrementChildPrio(len(n.indices) - 1)
                n = child
            } else if n.wildChild {
                // inserting a wildcard node, need to check if it conflicts with the existing wildcard
                n = n.children[len(n.children)-1]
                n.priority++

                // Check if the wildcard matches
                if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
                    // Adding a child to a catchAll is not possible
                    n.nType != catchAll &&
                    // Check for longer wildcard, e.g. :name and :names
                    (len(n.path) >= len(path) || path[len(n.path)] == '/') {continue walk}

                // Wildcard conflict
                pathSeg := path
                if n.nType != catchAll {pathSeg = strings.SplitN(pathSeg, "/", 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 +"'")
            }

            n.insertChild(path, fullPath, handlers)
            return
        }

        // Otherwise add handle to current node
                // 设置处理函数，如果曾经存在，则报错
        if n.handlers != nil {panic("handlers are already registered for path'" + fullPath + "'")
        }
        n.handlers = handlers
        n.fullPath = fullPath
        return
    }
}

Priority 优先级

为了能疾速找到并组合残缺的路由，GIN 在增加路由的同时，会在每个节点中增加 Priority 这个属性。在查找时依据 Priority 进行排序，罕用节点 (通过次数实践最多的节点) 在最前，并且同一层级外面 Priority 值越大，越优先进行匹配。

为何要将 9 种申请办法放在 slice 而不是 map 中

这是因为 9 个申请办法对应 9 棵路由树，而 GIN 对应的所有申请办法都保护了一颗路由树，同时这些要害信息都被包裹在 Node 构造体内，并被搁置在一个数组当中而非 map 中。这样是为了固定申请数量，同时在我的项目启动后申请办法会被保护在内存当中，采纳固定长度的 slice 从而在保障肯定查问效率的同时缩小内存占用。

type methodTrees []methodTree

func (trees methodTrees) get(method string) *node {
    for _, tree := range trees {
        if tree.method == method {return tree.root}
    }
    return nil
}

查找路由

路由树构建结束之后，GIN 即可开始失常接管申请。第一步是从 ServeHTTP 开始解析路由地址，而查找的过程解决逻辑如下：

申请一块内存用来填充响应体
解决申请信息
从 trees 中遍历比拟申请办法，拿到最对应申请办法的路由树
获取根节点

func (engine *Engine) ServeHTTP(w http.ResponseWriter, req *http.Request) {c := engine.pool.Get().(*Context)
    c.writermem.reset(w)
    c.Request = req
    c.reset()

    // 真正开始解决申请
    engine.handleHTTPRequest(c)

    engine.pool.Put(c)
}

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
        // 在该办法树上查找路由
        value := root.getValue(rPath, c.params, unescape)
        if value.params != nil {c.Params = *value.params}
        // 执行处理函数
        if value.handlers != nil {
            c.handlers = value.handlers
            c.fullPath = value.fullPath
            c.Next() // 波及到 gin 的中间件机制
            // 到这里时，申请曾经处理完毕，返回的后果也存储在对应的构造体中了
            c.writermem.WriteHeaderNow()
            return
        }
        // ...
      break
   }
   if engine.HandleMethodNotAllowed {
    for _, tree := range engine.trees {
        if tree.method == httpMethod {continue}
        if value := tree.root.getValue(rPath, nil, c.skippedNodes, unescape); value.handlers != nil {
            c.handlers = engine.allNoMethod
            serveError(c, http.StatusMethodNotAllowed, default405Body)
            return
        }
    }
    }
}

下面就是对于 GIN 路由树的一些教训分享，心愿可能帮忙到大家。

面试官问：Go 中的参数传递是值传递还是援用传递？

Golang 常见设计模式之单例模式

关于前端:关于-GIN-的路由树

什么是前缀树

GIN 中的前缀树 - 紧凑前缀树

举荐浏览

Just My Socks（注册教程内含优惠码）

关于前端:关于-GIN-的路由树

什么是前缀树

GIN 中的前缀树 - 紧凑前缀树

举荐浏览

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）