如何逐步解析Gin框架的路由源码与radix tree基数树实现？

本文共计1729个文字，预计阅读时间需要7分钟。

Gin简介：Gin是一个用Go（Golang）编写的HTTP web框架。它拥有类似Martini的API，性能更优——最高可达40倍。若需卓越性能，选择Gin。信息来源：GitHub上的Gin简介。

Gin 简介

Gin is a HTTP web framework written in Go (Golang). It features a Martini-like API with much better performance -- up to 40 times faster. If you need smashing performance, get yourself some Gin.

-- 这是来自 github 上 Gin 的简介

Gin 是一个用 Go 写的 HTTP web 框架，它是一个类似于 Martini 框架，但是 Gin 用了 gin-gonic.com/

github.com/gin-gonic/gin

gin-gonic.com/zh-cn/docs/ 中文文档

Gin 快速入门 Demo

我以前也写过一些关于 Gin 应用入门的 demo，在这里。

Gin v1.7.0 , Go 1.16.11

官方的一个 quickstart：

package main import "github.com/gin-gonic/gin" // gin-gonic.com/docs/quickstart/ func main() { r := gin.Default() r.GET("/ping", func(c *gin.Context) { c.JSON(200, gin.H{ "message": "pong", }) }) r.Run() // 监听在默认端口8080， 0.0.0.0:8080 }

上面就完成了一个可运行的 Gin 程序了。

分析上面的 Demo 第一步：gin.Default()

Engine struct 是 Gin 框架里最重要的一个结构体，包含了 Gin 框架要使用的许多字段，比如路由(组)，配置选项，HTML等等。

New() 和 Default() 这两个函数都是初始化 Engine 结构体。

RouterGroup struct 是 Gin 路由相关的结构体，路由相关操作都与这个结构体有关。

• A. Default() 函数

这个函数在 gin.go/Default()，它实例化一个 Engine，调用 New() 函数:

// github.com/gin-gonic/gin/blob/v1.7.0/gin.go#L180 // 实例化 Engine，默认带上 Logger 和 Recovery 2 个中间件，它是调用 New() // Default returns an Engine instance with the Logger and Recovery middleware already attached. func Default() *Engine { debugPrintWARNINGDefault() // debug 程序 engine := New() // 新建 Engine 实例，原来 Default() 函数是最终是调用 New() 新建 engine 实例 engine.Use(Logger(), Recovery()) // 使用一些中间件 return engine }

Engine 又是什么？

• B. Engine struct 是什么和 New() 函数:

gin.go/Engine:

Engine 是一个 struct 类型，里面包含了很多字段，下面代码只显示主要字段：

// github.com/gin-gonic/gin/blob/v1.7.0/gin.go#L57 // gin 中最大的一个结构体，存储了路由，设置选项和中间件 // 调用 New() 或 Default() 方法实例化 Engine struct // Engine is the framework's instance, it contains the muxer, middleware and configuration settings. // Create an instance of Engine, by using New() or Default() type Engine struct { RouterGroup // 组路由(路由相关字段) ... ... HTMLRender render.HTMLRender FuncMap template.FuncMap allNoRoute HandlersChain allNoMethod HandlersChain noRoute HandlersChain noMethod HandlersChain pool sync.Pool trees methodTrees maxParams uint16 trustedCIDRs []*net.IPNet } type HandlersChain []HandlerFunc

gin.go/New() 实例化 gin.go/Engine struct，简化的代码如下：

这个 New 函数，就是初始化 Engine struct，

// github.com/gin-gonic/gin/blob/v1.7.0/gin.go#L148 // 初始化 Engine，实例化一个 engine // New returns a new blank Engine instance without any middleware attached. // By default the configuration is: // - RedirectTrailingSlash: true // - RedirectFixedPath: false // - HandleMethodNotAllowed: false // - ForwardedByClientIP: true // - UseRawPath: false // - UnescapePathValues: true func New() *Engine { debugPrintWARNINGNew() engine := &Engine{ RouterGroup: RouterGroup{ Handlers: nil, basePath: "/", root: true, }, FuncMap: template.FuncMap{}, ... ... trees: make(methodTrees, 0, 9), delims: render.Delims{Left: "{{", Right: "}}"}, secureJSONPrefix: "while(1);", } engine.RouterGroup.engine = engine // RouterGroup 里的 engine 在这里赋值，下面分析 RouterGroup 结构体 engine.pool.New = func() interface{} { return engine.allocateContext() } return engine }

• C. RouterGroup

gin.go/Engine struct 里的 routergroup.go/RouterGroup struct 这个与路由有关的字段，它也是一个结构体，代码如下：

//github.com/gin-gonic/gin/blob/v1.7.0/routergroup.go#L41 // 配置存储路由 // 路由后的处理函数handlers(中间件) // RouterGroup is used internally to configure router, a RouterGroup is associated with // a prefix and an array of handlers (middleware). type RouterGroup struct { Handlers HandlersChain // 存储处理路由 basePath string engine *Engine // engine root bool } // github.com/gin-gonic/gin/blob/v1.7.0/gin.go#L34 type HandlersChain []HandlerFunc github.com/gin-gonic/gin/blob/v1.7.0/gin.go#L31 // HandlerFunc defines the handler used by gin middleware as return value. type HandlerFunc func(*Context) 第二步：r.GET()

r.GET() 就是路由注册和路由处理handler。

routergroup.go/GET()，handle() -> engine.go/addRoute()

// github.com/gin-gonic/gin/blob/v1.7.0/routergroup.go#L102 // GET is a shortcut for router.Handle("GET", path, handle). func (group *RouterGroup) GET(relativePath string, handlers ...HandlerFunc) IRoutes { return group.handle(github.com/gin-gonic/gin/blob/v1.7.0/routergroup.go#L72 func (group *RouterGroup) handle(github.com/gin-gonic/gin/blob/v1.7.0/gin.go#L276 func (engine *Engine) addRoute(method, path string, handlers HandlersChain) { ... ... // 每一个baike.baidu.com/item/字典树/9825209)

trie 树的代码实现：baike.baidu.com/item/字典树/9825209#5

Radix Tree基数树 认识基数树：

Radix Tree，基数特里树或压缩前缀树，是一种更节省空间的 Trie 树。它对 trie 树进行了压缩。

看看是咋压缩的，假如有下面一组数据 key-val 集合：

{ "def": "redisio", "dcig":"mysqlio", "dfo":"linux", "dfks":"tdb", "dfkz":"dogdb", }

用上面数据中的 key 构造一颗 trie 树：

现在压缩 trie 树(Compressed Trie Tree)中的唯一子节点，就可以构建一颗 radix tree 基数树。

父节点下第一级子节点数小于 2 的都可以进行压缩，把子节点合并到父节点上，把上图 <2 子节点数压缩，变成如下图：

把 c，f 和 c，i，g 压缩在一起，这样就节省了一些空间。压缩之后，分支高度也降低了。

这个就是对 trie tree 进行压缩变成 radix tree。

在另外看一张出现次数比较多的 Radix Tree 的图：

(图Radix_tree 来自：en.wikipedia.org/wiki/Radix_tree)

基数树唯一子节点都与其父节点合并，边沿(edges)既可以存储多个元素序列也可以存储单个元素。比如上图的 r, om，an，e。

基数树的图最下面的数字对应上图的排序数字，比如 ，就是 ruber 字符，
。

什么时候使用基数树合适：

字符串元素个数不是很多，且有很多相同前缀时适合使用基数树这种数据结构。

基数树的应用场景：

github.com/julienschmidt/github.com/julienschmidt/github.com/julienschmidt/github.com/julienschmidt/github.com/julienschmidt/github.com/julienschmidt/github.com/julienschmidt/www.cs.usfca.edu/~galles/visualization/RadixTree.html

radix tree 的算法操作可以看这里，动态展示。

参考

• github.com/gin-gonic/gin/tree/v1.7.0 gin 源码
• github.com/julienschmidt/github.com/julienschmidt/gin-gonic.com/docs/quickstart/ gin doc
• www.cs.usfca.edu/~galles/visualization/RadixTree.html radix tree算法步骤可视化
• baike.baidu.com/item/字典树/9825209 百科基数树
• 《算法》 5.2 单词查找树 trie tree