侧边栏壁纸
博主头像
hanlibaby博主等级

念念不忘,必有回响

  • 累计撰写 59 篇文章
  • 累计创建 92 个标签
  • 累计收到 20 条评论

Golang Web(三) 路由(Trie树)

hanlibaby
2022-04-26 / 1 评论 / 0 点赞 / 44 阅读 / 6,998 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-04-27,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

前言

上一篇文章中通过将 Router 抽离出来,并设计封装了上下文,提供 GetPost 请求参数的获取,JSONStringHTML 等返回类型的支持。

目标

  • 使用 Trie 树实现路由的解析。

当前先简单的完成使用 Trie 树进行路由的存储与解析。

Trie 树

之前,我们通过使用了一个非常简单的 哈希表(map)结构存储了路由表,使用map 存储键值对,查询非常高效,但是有一个缺点,就是键值对的存储方式,无法用来处理动态路由。如果我们需要支持类似 /user/*/user/${userId} 这样的动态路由要怎么办?例如 /user/* 可以匹配 /user/aaa/user/bbb等。

字典树(Trie树)是实现动态路由最常用的数据结构,不了解 Trie 树的同学可以先看看我之前写的 Trie树总结

由于 HTTP 请求的路径正好是由 / 分隔多段构成的,因此,每一段可以作为 Trie树 的一个节点。

实现

代码结构

image.png

trie.go

首先先设计树节点上应该存储哪些信息。

route用于保存子路由,path 用于记录整条路由

type (
	// Node record url params and executes a handler
	Node struct {
		// route record router part, eg:router:/user/a, route user
		route string

		// path record router
		path string

		// handle router handler
		handle HandleFunc

		// children record router parts
		children map[string]*Node
	}

	Trie struct {
		// root router root, usually is "/"
		root *Node
	}
)

编写两个辅助函数,用于处理前缀和分隔路由

func trimPathPrefix(pattern string) string {
	return strings.TrimPrefix(pattern, "/")
}

func splitPattern(pattern string) []string {
	return strings.Split(pattern, "/")
}

对于路由来说,最重要的就是注册节点和匹配了,开发服务时,注册路由规则,映射 handler;访问时,匹配路由规则,查找对应的 handler

Trie 树支持节点的插入和查询,插入时从根节点开始,依此查找每一层子节点,如果没有与当前子路由匹配的节点,则新建一个。查询功能同样是依次查找每一层节点,如果找到了与当前路由相匹配的节点则返回。

// insert register a router as nodes into trie
func (t *Trie) insert(pattern string, handle HandleFunc) {
	cur := t.root
	if pattern != cur.route {
		pattern = trimPathPrefix(pattern)
		routes := splitPattern(pattern)
		for _, route := range routes {
			node, ok := cur.children[route]
			if !ok {
				node = NewNode(route)
				cur.children[route] = node
			}
			cur = node
		}
	}

	cur.handle = handle
	cur.path = pattern
}

// search return a match node from trie
func (t *Trie) search(pattern string) *Node {
	cur := t.root

	if pattern == cur.path {
		return cur
	}

	pattern = trimPathPrefix(pattern)
	routes := splitPattern(pattern)

	for _, route := range routes {
		if child, ok := cur.children[route]; ok {
			if child.path == pattern {
				return child
			}
		}
	}

	return nil
}

完整代码

package router

import (
	"strings"
)

type (
	// Node record url params and executes a handler
	Node struct {
		// route record router part, eg:router:/user/a, route user
		route string

		// path record router
		path string

		// handle router handler
		handle HandleFunc

		// children record router parts
		children map[string]*Node
	}

	Trie struct {
		// root router root, usually is "/"
		root *Node
	}
)

func NewNode(route string) *Node {
	return &Node{
		route:    route,
		children: make(map[string]*Node),
	}
}

func NewTrie() *Trie {
	return &Trie{
		root: NewNode("/"),
	}
}

func trimPathPrefix(pattern string) string {
	return strings.TrimPrefix(pattern, "/")
}

func splitPattern(pattern string) []string {
	return strings.Split(pattern, "/")
}

// insert register a router as nodes into trie
func (t *Trie) insert(pattern string, handle HandleFunc) {
	cur := t.root
	if pattern != cur.route {
		pattern = trimPathPrefix(pattern)
		routes := splitPattern(pattern)
		for _, route := range routes {
			node, ok := cur.children[route]
			if !ok {
				node = NewNode(route)
				cur.children[route] = node
			}
			cur = node
		}
	}

	cur.handle = handle
	cur.path = pattern
}

// search return a match node from trie
func (t *Trie) search(pattern string) *Node {
	cur := t.root

	if pattern == cur.path {
		return cur
	}

	pattern = trimPathPrefix(pattern)
	routes := splitPattern(pattern)

	for _, route := range routes {
		if child, ok := cur.children[route]; ok {
			if child.path == pattern {
				return child
			}
			cur = child
		}
	}

	return nil
}

Router

Trie 树的插入和查找都实现了,接下来就是将 Trie 树应用到路由中去。

  • 首先定义了一个请求方法类型集合,记录所有请求类型,用于判断当前请求是否有效
  • Router 中使用一个 map 存储请求方法相对应的 Trie 树,每种请求方法对应一棵树
  • AddRoute 方法首先先判断请求方法类型是否有效,有效则找到对应的Trie 树,注册该路由
  • Handler 方法通过上下文获取请求路径和请求方法类型,去对应的Trie 树中查询,查询到则调用节点保存的handle进行处理
package router

import (
	"fmt"
	"lwjppz.cn/guru/context"
	"net/http"
)

var (
	// methods the collection of request method
	methods = map[string]struct{}{
		http.MethodGet:    {},
		http.MethodPost:   {},
		http.MethodPut:    {},
		http.MethodDelete: {},
		http.MethodPatch:  {},
		http.MethodHead:   {},
	}
)

type (
	// HandleFunc request handler function
	HandleFunc func(ctx *context.Context)

	// Router a http router that parse a request path
	Router struct {
		// trees the routing tree corresponding to the request method
		// eg: GET -> a trie; POST -> a trie...
		trees map[string]*Trie
	}
)

func NewRouter() *Router {
	return &Router{
		trees: make(map[string]*Trie),
	}
}

// AddRoute add routing nodes to the corresponding tree
func (r *Router) AddRoute(method, path string, handle HandleFunc) {
	if _, ok := methods[method]; !ok {
		panic(fmt.Errorf("invalid method:%4s", method))
	}

	trie, ok := r.trees[method]
	if !ok {
		trie = NewTrie()
		r.trees[method] = trie
	}

	trie.insert(path, handle)
}

// Handle find the corresponding routing node to process the request
func (r *Router) Handle(ctx *context.Context) {
	var (
		requestURL = ctx.Request.URL.Path
		method     = ctx.Request.Method
	)

	if node := r.trees[method].search(requestURL); node != nil {
		if node.handle != nil {
			if node.path == requestURL || node.path == requestURL[1:] {
				node.handle(ctx)
			}
		}
	}
}

框架入口

新增了对 PUT、PATCH、DELETE、HEAD方法的支持,变化不大。

package guru

import (
	"log"
	"lwjppz.cn/guru/context"
	"lwjppz.cn/guru/router"
	"net/http"
)

type (
	// ServeHandler A handler that accepts all requests
	ServeHandler struct {
		router *router.Router
	}

	HandleFunc = router.HandleFunc
)

// New Constructor of guru.ServeHandler
func New() *ServeHandler {
	return &ServeHandler{router: router.NewRouter()}
}

func (serveHandler *ServeHandler) addRoute(methodKey, router string, handleFunc HandleFunc) {
	serveHandler.router.AddRoute(methodKey, router, handleFunc)
}

// GET define a get request
func (serveHandler *ServeHandler) GET(router string, handleFunc HandleFunc) {
	serveHandler.router.AddRoute(http.MethodGet, router, handleFunc)
}

// POST define a post request
func (serveHandler *ServeHandler) POST(router string, handleFunc HandleFunc) {
	serveHandler.router.AddRoute(http.MethodPost, router, handleFunc)
}

// PUT define a put request
func (serveHandler *ServeHandler) PUT(router string, handleFunc HandleFunc) {
	serveHandler.router.AddRoute(http.MethodPut, router, handleFunc)
}

// DELETE define a delete request
func (serveHandler *ServeHandler) DELETE(router string, handleFunc HandleFunc) {
	serveHandler.router.AddRoute(http.MethodDelete, router, handleFunc)
}

// PATCH define a patch request
func (serveHandler *ServeHandler) PATCH(router string, handleFunc HandleFunc) {
	serveHandler.router.AddRoute(http.MethodPatch, router, handleFunc)
}

// HEAD define a head request
func (serveHandler *ServeHandler) HEAD(router string, handleFunc HandleFunc) {
	serveHandler.router.AddRoute(http.MethodHead, router, handleFunc)
}

func (serveHandler *ServeHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
	c := context.NewContext(w, r)
	serveHandler.router.Handle(c)
}

// Run define a method to start http server
func (serveHandler *ServeHandler) Run(addr string) {
	err := http.ListenAndServe(addr, serveHandler)
	if err != nil {
		log.Println("server start error")
	}
}

使用

使用方式和之前的一样

package main

import (
	"lwjppz.cn/guru"
	"lwjppz.cn/guru/context"
	"net/http"
)

type User struct {
	Username string `json:"username"`
	Password string `json:"password"`
}

func main() {
	server := guru.New()

	server.GET("/", func(c *context.Context) {
		c.HTML(http.StatusOK, "<h1>Hello Guru!</h1>")
	})

	server.GET("/hello", func(c *context.Context) {
		c.String(http.StatusOK, "hello!, you're at %s\n", c.Path)
	})

	server.POST("/loginForm", func(c *context.Context) {
		c.JSON(http.StatusOK, context.M[string, any]{
			"username": c.PostForm("username"),
			"password": c.PostForm("password"),
		})
	})

	server.POST("/loginJson", func(c *context.Context) {
		c.JSON(http.StatusOK, c.BindJson(&User{}))
	})

	server.Run(":8080")
}
0

评论区