钉钉事件订阅前缀树算法gin框架解析

当钉钉监测到发生一些事件，如下图

此处举例三个事件user_add_org、user_change_org、user_leave_org，传统的做法是，我们写三个if条件，类似下图

这样字符串匹配效率比较低，于是联想到gin框架中的路由匹配算法，可以借鉴模仿gin框架的实现方式。

用实际需求驱动开发，掌握知识的同时还能应用知识，理解得会更加深入。

gin框架源代码解析

gin框架根据路由字符串建树

无论是POST、还是GET底层都是下方代码

func (group *RouterGroup) POST(relativePath string, handlers ...HandlerFunc) IRoutes {
	return group.handle(http.MethodPost, relativePath, handlers)
}


func (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {
	absolutePath := group.calculateAbsolutePath(relativePath)
    // 把这个新的handlefunc和之前的handlefunc（比如说中间件中的）加在一起
	handlers = group.combineHandlers(handlers)
    // 给这个POST请求去建树
	group.engine.addRoute(httpMethod, absolutePath, handlers)
	return group.returnObj()
}

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)
    # 取出POST方法的树
	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)
}

树的节点结构如下：

type node struct {
	path      string
	indices   string
	wildChild bool
	nType     nodeType
	priority  uint32
	children  []*node // child nodes, at most 1 :param style node at the end of the array
	handlers  HandlersChain // 此处就是对应路径要执行的HandleFunc
	fullPath  string
}

type HandlersChain []HandlerFunc

type HandlerFunc func(*Context)

gin框架在请求到来时具体查树执行逻辑

func (engine *Engine) ServeHTTP(w http.ResponseWriter, req *http.Request) {
	c := engine.pool.Get().(*Context) // 取出一个context对象
	c.writermem.reset(w)
	c.Request = req
	c.reset()
    // 关键处理函数
	engine.handleHTTPRequest(c)

	engine.pool.Put(c)
}

func (engine *Engine) handleHTTPRequest(c *Context) {
	httpMethod := c.Request.Method
	rPath := c.Request.URL.Path
	unescape := false
	if engine.UseRawPath && len(c.Request.URL.RawPath) > 0 {
		rPath = c.Request.URL.RawPath
		unescape = engine.UnescapePathValues
	}

	if engine.RemoveExtraSlash {
		rPath = cleanPath(rPath)
	}

	// Find root of the tree for the given HTTP method
    // 找到对应请求方法的前缀树
	t := engine.trees
	for i, tl := 0, len(t); i < tl; i++ {
		if t[i].method != httpMethod {
			continue
		}
		root := t[i].root
		// Find route in tree
        // 去前缀树中取值
		value := root.getValue(rPath, c.params, c.skippedNodes, unescape)
		if value.params != nil {
			c.Params = *value.params
		}
		if value.handlers != nil {
            // 找到所有的handlerfunc
			c.handlers = value.handlers
			c.fullPath = value.fullPath
            // 具体去执行handlerfunc
			c.Next()
			c.writermem.WriteHeaderNow()
			return
		}
        ......
    }
}



func (c *Context) Next() {
	c.index++
	for c.index < int8(len(c.handlers)) {
		c.handlers[c.index](c) // 依次调用handlefunc，让c（context）在不同的func中传递
		c.index++
	}
}