您现在的位置是：首页 >技术教程 >【Gee-Web框架】【Day3】【Golang】前缀树路由网站首页技术教程

1. 使用Trie树实现动态路由解析dynamic route
2. 支持两种模式:name和*filepath

一、 Trie树

1. 简要说明

• 用map结构存储路由表，使用map存储键值对，索引非常高效
• 但有一个弊端，键值对的存储方式，只能用来索引静态路由
• 如果想支持类似于/hello/:name的动态路由怎么办
• 动态路由有多种实现方式
• 实现动态路由最常用的数据结构，被称为前缀树Trie树
  • 每一个节点的所有的子节点都拥有相同的前缀
  • 这种结构非常适用于路由匹配
    
• HTTP请求的路径恰好是由/分隔的多段构成的
• 因此，每一段可以作为前缀树的一个节点
• 通过树结构查询，如果中间某一层的节点都不满足条件，那么就说明没有匹配到路由，查询结束

2. Trie树实现

• trie.go
  • 与普通的树不同，为了实现动态路由匹配，加上了isWild这个参数
  • 对于路由来说，最重要的是注册与匹配
  • 开发服务时，注册路由规则，映射handler
  • 访问时，匹配路由规则，查找对应的handler
  • 因此Trie树需要支持节点的插入与查询

  type node struct{
  	pattern string  // 待匹配路由
  	part string  // 路由中的一部分
  	children []*node  // 子节点
  	isWild bool  // 是否精确匹配	
  }
  	
  // 第一个匹配成功的节点，用于插入
  func (n *node) matchChild(part string) *node{
  	for _, child := range n.children{
  		if child.part == part || child.isWild{
  			return child	
  		}
  	}	
  	return nil
  }
  
  // 所有匹配成功的节点，用于查找
  func (n *node) matchChildren(part string)[]*node{
  	nodes := make([]*node, 0)
  	for _, child := range n.children{
  		if child.part == part || child.isWild{
  			nodes = append(nodes, child)	
  		}	
  	}	
  	return nodes
  }
  
  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)
  }
  	
  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
  }
  

二、 Router

1. 简要说明

• Trie树的插入与查找都实现了，接下来将Trie树应用到路由中去
• router.go

  type router struct{
  	roots map[string]*node
  	handlers map[string]HandlerFunc	
  }
  
  func newRouter() *router{
  	return &router{
  		roots: make(map[string]*node),
  		handlers: make(map[string]HandlerFunc),	
  	}	
  }
  
  func parsePattern(pattern string) []string{
  	vs := strings.Split(pattern, "/")
  	parts := make([]string, 0)
  	for _, item := range vs{
  		if item != ""{
  			parts = append(parts, item)
  			if item[0] == "*"{
  				break	
  			}
  		}	
  	}	
  	return parts
  }
  	
  func (r *router) addRoute(method string, pattern string, handler HandlerFunc){
  	parts := parsePattern(pattern)
  	key := method + "-" + pattern
  	_, ok := r.roots[method]
  	if !ok{
  		r.roots[method] = &node{}	
  	}	
  	r.roots[method].insert(pattern, parts, 0)
  	r.handlers[key] = handler
  }
  	
  func (r *router) getRoute(method string, path string)(*node, map[string]string){
  	searchParts := parsePattern(path)
  	params := make(map[string]string)
  	root, ok := r.roots[method]
  	if !ok{
  		return nil, nil	
  	}	
  	n := root.search(searchParts, 0)
  	if n != nil{
  		parts := parsePattern(n.pattern)
  		for index, part := range parts{
  			if part[0] == ":"{
  				params[part[1:]] = searchParts[index]	
  			}	
  			if part[0] == "*" && len(part) > 1{
  				params[part[1:]] = strings.Join(searchParts[index: ], "/")
  				break	
  			}
  		}	
  		return n, params
  	}
  	return nil, nil
  }
  

• context.go

  type Context struct{
  	Writer http.ResponseWriter
  	Req *http.Request
  	Path string
  	Method string
  	Params map[string]string
  	StatusCode int	
  }
  	
  func (c *Context) Param(key string) string{
  	value, _ := c.Params[key]
  	return value	
  }
  

• router.go

  func (r *router) handle(c *Context){
  	n, params := r.getRoute(c.Method, c.Path)
  	if n != nil{
  		c.Parmas = params
  		key := c.Method + "-" + n.pattern
  		r.handlers[key](c)	
  	}else{
  		c.String(http.StatusNotFound, "404 NOT FOUND: %s
  ", c.Path)	
  	}	
  }
  

• main.go

  func main(){
  	r := gee.New()
  	r.GET("/", func(c *gee.Context){
  		c.HTML(http.StatusOK, "<h1>Hello Gee</h1>")	
  	})	
  	r.GET("/hello", func(c *gee.Context){
  		c.String(http.StatusOK, "hello %s, you're at %s
  ", c.Query("name"), c.Path)	
  	})
  	r.GET("/hello/:name", func(c *gee.Context){
  		c.String(http.StatusOK, "hello %s, you're at %s
  ", c.Param("name"), c.Path)	
  	})
  	r.GET("/asserts/*filepath", func(c *gee.Context){
  		c.JSON(http.StatusOK, gee.H{"filepath": c.Param("filepath")})	
  	})
  	r.Run(":9999")
  }
  

参考

1. https://geektutu.com/post/gee-day3.html