j
jaryue
V1
2023/03/27阅读:21主题:默认主题
gowebday3使用 Trie 树实现动态路由(dynamic route)解析。
gowebday3 使用 Trie 树实现动态路由(dynamic route)解析。 支持两种模式:name和*filepath
-
构造树节点
type Node struct {
Pattern string // 准确的 路径//绝对
Part string // 路径的尾(当前的)//相对
Children []*Node // 子节点
IsWild bool // 是否为通配符:或者*
}
-
返回在n中查找首个part字段.,有返回该节点,没有返回空
// 返回在n中查找part字段.,有返回该节点,没有返回空
func (n *Node) MatchChild(part string) *Node {
for _, child := range n.Children {
if child.Part == part || child.IsWild {
return child
}
}
return nil
}
-
还有一个函数就是查找所有的节点字段,,返回node数组,,与前面不同的是它会查找多个值,用于查找
// 查找返回与所有节点;查找n中part字段,返回节点数组(与MatchChild的区别:本函数返回所有匹配的节点而MatchChild返回第一个匹配的节点)
func (n *Node) MatchChildren(part string) []*Node {
nodes := make([]*Node, 0) //建立一个新节点
for _, child := range n.Children { //遍历n中是否有panrt的相对或者绝对路径
if child.Part == part || child.IsWild { //路径相同或者为通配符
nodes = append(nodes, child) //节点赋值
}
}
return nodes //返回节点数组,没有就是空节点
}
-
插入节点:
1). 如果当前处理的 URL 路径部分已经到了最后一部分(即 len(parts) == height),那么说明已经找到了该路由规则对应的叶子节点,将该叶子节点的模式设置为该规则对应的处理器函数 pattern,然后直接返回。
//parts 是一个字符串切片,表示一个 URL 路径经过分割后的每一个部分。比如,对于一个 URL 路径 /users/:id/books/*title,经过分割后的 parts 内容应该是 []string{"users", ":id", "books", "*title"}。
if len(parts) == height {
n.Pattern = pattern
return
}
2).如果当前节点的子节点中有一个子节点的 part 值和当前处理的 URL 路径部分相等,或者是一个通配符(即 child.part == part || child.isWild),那么说明这个子节点可以用于匹配当前 URL 路径部分,就把 height 加一,递归调用 Insert 方法,将处理的 URL 路径部分的索引值向后移动一个位置。
part := parts[height]
child := n.MatchChild(part)
if child == nil {
child = &Node{Part: part, IsWild: part[0] == ':' || part[0] == '*'}
3). 如果找不到符合条件的子节点,说明当前节点的子节点中没有一个子节点能够匹配当前处理的 URL 路径部分,就创建一个新的子节点,将该子节点插入到当前节点的子节点列表中,然后递归调用 Insert 方法。
n.Children = append(n.Children, child)
}
child.Insert(pattern, parts, height+1)
查找节点
-
如果当前处理的 URL 路径部分已经到了最后一部分(即 len(parts) == height),或者当前节点是一个以 * 开头的通配符节点,那么说明已经找到了匹配的叶子节点,如果该叶子节点的模式不为空,就返回该叶子节点,否则返回 nil。
if len(parts) == height || strings.HasPrefix(n.Part, "*") {
if n.Pattern == "" {
return nil
}
return n
}
-
如果当前节点的子节点中有一个子节点的 part 值和当前处理的 URL 路径部分相等,或者是一个通配符(即 child.part == part || child.isWild),那么说明这个子节点可以用于匹配当前 URL 路径部分,就把 height 加一,递归调用 Search 方法,将处理的 URL 路径部分的索引值向后移动一个位置。
part := parts[height]
children := n.MatchChildren(part)
for _, child := range children {
result := child.Search(parts, height+1)
-
如果找不到符合条件的子节点,说明当前节点的子节点中没有一个子节点能够匹配当前处理的 URL 路径部分,就返回 nil。
if result != nil {
return result
}
}
return nil
}
tree.go
package tree
import "strings"
type Node struct {
Pattern string // 准确的 路径//绝对
Part string // 路径的尾(当前的)//相对
Children []*Node // 子节点
IsWild bool // 是否为通配符:或者*
}
// 返回在n中查找part字段.,有返回该节点,没有返回空
func (n *Node) MatchChild(part string) *Node {
for _, child := range n.Children {
if child.Part == part || child.IsWild {
return child
}
}
return nil
}
// 查找返回与所有节点;查找n中part字段,返回节点数组(与MatchChild的区别:本函数返回所有匹配的节点而MatchChild返回第一个匹配的节点)
func (n *Node) MatchChildren(part string) []*Node {
nodes := make([]*Node, 0) //建立一个新节点
for _, child := range n.Children { //遍历n中是否有panrt的相对或者绝对路径
if child.Part == part || child.IsWild { //路径相同或者为通配符
nodes = append(nodes, child) //节点赋值
}
}
return nodes //返回节点数组,没有就是空节点
}
// 如果当前处理的 URL 路径部分已经到了最后一部分(即 len(parts) == height),那么说明已经找到了该路由规则对应的叶子节点,将该叶子节点的模式设置为该规则对应的处理器函数 pattern,然后直接返回。
// 如果当前节点的子节点中有一个子节点的 part 值和当前处理的 URL 路径部分相等,或者是一个通配符(即 child.part == part || child.isWild),那么说明这个子节点可以用于匹配当前 URL 路径部分,就把 height 加一,递归调用 Insert 方法,将处理的 URL 路径部分的索引值向后移动一个位置。
// 如果找不到符合条件的子节点,说明当前节点的子节点中没有一个子节点能够匹配当前处理的 URL 路径部分,就创建一个新的子节点,将该子节点插入到当前节点的子节点列表中,然后递归调用 Insert 方法。
// 插入节点:pattern 为路由,路由的parts为字符串切片,,hight为树的深度.
func (n *Node) Insert(pattern string, parts []string, height int) {
if len(parts) == height {
n.Pattern = pattern
return
}
part := parts[height]
child := n.MatchChild(part)
if child == nil {
child = &Node{Part: part, IsWild: part[0] == ':' || part[0] == '*'}
n.Children = append(n.Children, child)
}
child.Insert(pattern, parts, height+1)
}
// 如果当前处理的 URL 路径部分已经到了最后一部分(即 len(parts) == height),或者当前节点是一个以 * 开头的通配符节点,那么说明已经找到了匹配的叶子节点,如果该叶子节点的模式不为空,就返回该叶子节点,否则返回 nil。
// 如果当前节点的子节点中有一个子节点的 part 值和当前处理的 URL 路径部分相等,或者是一个通配符(即 child.part == part || child.isWild),那么说明这个子节点可以用于匹配当前 URL 路径部分,就把 height 加一,递归调用 Search 方法,将处理的 URL 路径部分的索引值向后移动一个位置。
// 如果找不到符合条件的子节点,说明当前节点的子节点中没有一个子节点能够匹配当前处理的 URL 路径部分,就返回 nil。
func (n *Node) Search(parts []string, height int) *Node {
if len(parts) == height || strings.HasPrefix(n.Part, "*") {
if n.Pattern == "" {
return nil
}
return n
}
part := parts[height]
children := n.MatchChildren(part)
for _, child := range children {
result := child.Search(parts, height+1)
if result != nil {
return result
}
}
return nil
}
//parts 是一个字符串切片,表示一个 URL 路径经过分割后的每一个部分。比如,对于一个 URL 路径 /users/:id/books/*title,经过分割后的 parts 内容应该是 []string{"users", ":id", "books", "*title"}。
实现



作者介绍
j
jaryue
V1