结束了3天的端午游,阿那亚赞的一笔,就是人忒多了。回来把Gin的核心–Trees补上吧。
待完善~~~
- 一、基数树
- 二、结构
- 三、主要方法介绍
- func (n *node) addChild(child *node)
- func (n *node) incrementChildPrio(pos int)
- func (n *node) addRoute(path string, handlers HandlersChain)
- func (n *node) insertChild(path string, fullPath string, handlers HandlersChain)
- func (n *node) getValue(path string, params *Params, unescape bool) (value nodeValue)
- func (n *node) findCaseInsensitivePath(path string, fixTrailingSlash bool) ([]byte, bool)
- func (n *node) findCaseInsensitivePathRec(path string, ciPath []byte, rb [4]byte, fixTrailingSlash bool) []byte
一、基数树
Gin的路由底层使用的是基数树(Radix Tree,也叫基数特里树或压缩前缀树),或称压缩前缀树,是一种更节省空间的前缀树(Trie Tree)。对于基数树的每个节点,如果该节点是确定的子树的话,就和父节点合并。基数树可用来构建关联数组。(参见基数树)
下图表示了一组单词(sex、seed、sleep、son)在前缀树(Trie tree)和基数树(Radix tree)存储的差别。
二、结构
代码位置:https://github.com/gin-gonic/gin/blob/master/tree.go。
tree文件包含了一个结构体node,这个结构体就是Gin框架路由的核心,是最底层的村存储结构。其所有的方法、属性都是私有的。
1 | type node struct { |
- path: 表示当前节点的path
- indices: 通常情况下维护了children列表的path的各首字符组成的string,之所以是通常情况,是在处理包含通配符的path处理中会有一些例外情况
- wildChil:默认是false,当children是 通配符类型时,wildChild为true
- nType: 是节点的类型,默认是static类型,还包括了root类型,对于path包含冒号通配符的情况,nType是 param类型,对于包含 * 通配符的情况,nType类型是 catchAll 类型
- priority:代表了有几条路由会经过此节点,用于在节点进行排序时使用
- children:子节点
- handlers:处理函数链条(切片)
- fullPath:是从root节点到当前节点的全部path部分;如果此节点为终结节点handlers为对应的处理链,否则为nil;maxParams 是当前节点到各个叶子节点的包含的通配符的最大数量
三、主要方法介绍
1 | func (n *node) addChild(child *node) |
func (n *node) addChild(child *node)
添加子节点,根据子节点是否为通配符类型分别添加子节点。
1 | func (n *node) addChild(child *node) { |
func (n *node) incrementChildPrio(pos int)
1 | func (n *node) incrementChildPrio(pos int) int { |
incrementChildPrio方法用于给子节点进行重新排序。
func (n *node) addRoute(path string, handlers HandlersChain)
1 | func (n *node) addRoute(path string, handlers HandlersChain) { |
addRoute方法是一个非常重要的方法,在程序启动后,Gin的Engine通过最终调用该方法注册路由信息。
Gin的路由中,每一个method(GET、POST等)都对应了一个radix tree。在添加路由时,会选择指定method的radix tree。
- 进入该方法后首先将node的priority自增1,如果当前tree时一颗空树的话,就直接将path和handlers直接插入。
- 随后就进入了walk代码块,在walk代码块中先计算了当前节点的path和添加路由path的最长公共长度。
- 如果最长公共长度小于当前节点的path,则新增子节点。该功能是”分裂边缘”,比如初始path是aabbc,新加入的path是abbc,a就是他们的最长公共前缀,那么a会作为parent节点,增加abbc和bbc作为child节点。
- 如果最长公共长度小于当前插入节点的path,即新添加的节点插入新的parent节点作为子节点。
- 如果当前节点为param类型节点,以’/‘开头并且其子节点个数为1,则指针移动到该子节点重新执行walk代码块。
- 检查path下一个节点的子节点是否存在,比如a的节点是aabbc和bbc,indices为ab,如果新加的路由时aba,那么就是和bbc由匹配的部分b,将继续分裂现在的bbc节点。
- 如果不以’:’、’*’开头并且当前节点类型不是catchAll,增加一个子节点,并且指针移动到这个子节点。
- 如果当前节点不是通配符类型类型,指针移动到最后一个子节点,检查当前节点通配符情况然后重新执行walk代码块。
- 如果有通配符冲突则会panic
- 插入新的子节点
func (n *node) insertChild(path string, fullPath string, handlers HandlersChain)
1 | func (n *node) insertChild(path string, fullPath string, handlers HandlersChain) { |
插入子节点方法会进行一系列的交验检查,递归插入子节点。
func (n *node) getValue(path string, params *Params, unescape bool) (value nodeValue)
1 | func (n *node) getValue(path string, params *Params, unescape bool) (value nodeValue) { |
getValue返回以给定路径(key)注册的handle。通配符的值 通配符的值被保存到一个map中。
如果找不到handle,如果有一个handle在,并且有一个额外的(不含)尾部斜杠的handle,那么将推荐一个TSR(尾部斜杠重定向)。如果在给定的路径中存在一个带有额外的(没有)尾部斜杠的handle,就会提出TSR(尾部斜杠重定向)建议。给定的路径。
该方法在handleHTTPRequest中使用,用于定位请求路由信息。
func (n *node) findCaseInsensitivePath(path string, fixTrailingSlash bool) ([]byte, bool)
对给定的路径进行不区分大小写的查询,并试图找到一个处理程序。
它也可以选择修复尾部的斜线。
它返回经过大小写校正的路径和一个指示查找是否成功的bool 是否成功。
func (n *node) findCaseInsensitivePathRec(path string, ciPath []byte, rb [4]byte, fixTrailingSlash bool) []byte
findCaseInsensitivePath使用的递归不区分大小写的查找功能。