gin 框架原理

Gin的路由原理

Gin的路由基于Trie树和压缩字典树算法，什么是Trie树？其实很好理解，看下图：

单词at，bee，ben，bt，q组成的Trie树如下：

每个字母的父亲节点就是它的前一个字母

Trie树的三个性质：

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
• 每个节点的所有子节点包含的字符都不相同

也就是按照各个词的前缀，将所有的词拆解组成一颗树的结构。

那么有了这样的一颗树，查找单词就变得很简单，从根节点开始向下匹配，如果匹配到单词的前缀就沿着该节点接着往下匹配，直到完全匹配到单词。

但是trie树的每个节点只能存储一个字符，这意味着面对较长的字符串仍然要向下探寻多个节点，这存在着浪费，因此就有了压缩字典树，

压缩字典树，是trie树的一种，也称单词查找树、前缀树，善于进行字符串的检索、取字符串最长公共前缀、以及排序，常应用在搜索引擎中例如百度输入某个字可能自动弹出能匹配到的单词出来。

下面分别是/,/bear,/bell,/bid,/bull,/buy,/sell,/stock,/stop 的标准tire 和压缩 tire

压缩字典树的特质使得其用于单词前缀查找时更快。这也恰巧就是一个高性能的路由匹配算法需要的。因此Gin使用其作为路由算法。

gin的压缩trie树结构如下：

type node struct {
	path      string // 存储着节点的字符串
	indices   string // 存储着下级子节点的前缀索引
	wildChild bool   
	nType     nodeType 
// nType 节点类型：
// static nodeType = iota // default，默认类型
// root 根节点
// param 参数，例如:id这样的通配符
// catchAll 全匹配
	priority  uint32  // 优先级
	children  []*node // 子节点, 至少有一个， :param 类型的节点会在列表的末尾
	handlers  HandlersChain // 匹配该节点的路由的处理函数
	fullPath  string        // 从根节点到该节点的完整路径
}

当使用gin注册路由时：

	g.Handle("GET", "/hi/:p", func(ctx *gin.Context) {
		ctx.String(http.StatusOK, "h*")
	})

就会调用addRoute向tire压缩树增加节点：

func (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {
	absolutePath := group.calculateAbsolutePath(relativePath)
	handlers = group.combineHandlers(handlers)
// 调用addRoute增加节点
	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")

	debugPrintRoute(method, path, handlers)

// gin的路由不止是一颗tire树，而是一个method对应一颗tire树
	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
	}
}

插入操作
下面图解一串子串插入压缩trie过程，/,/serach,/support,/blog , 在httprouter上截的一段例子，我们只插到/blog

插入/

插入/serach

插入/support

插入/blog

查询操作

1、先找共同前缀。
2、再找目录。
3、循环上面两步，直到当前path相等。

参考：https://blog.csdn.net/forever_dreams/article/details/81009580
https://blog.csdn.net/qq_17308321/article/details/89736691