钉钉事件订阅前缀树算法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      stringindices   stringwildChild boolnType     nodeTypepriority  uint32children  []*node // child nodes, at most 1 :param style node at the end of the arrayhandlers  HandlersChain // 此处就是对应路径要执行的HandleFuncfullPath  string
}type HandlersChain []HandlerFunctype 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 = reqc.reset()// 关键处理函数engine.handleHTTPRequest(c)engine.pool.Put(c)
}func (engine *Engine) handleHTTPRequest(c *Context) {httpMethod := c.Request.MethodrPath := c.Request.URL.Pathunescape := falseif engine.UseRawPath && len(c.Request.URL.RawPath) > 0 {rPath = c.Request.URL.RawPathunescape = engine.UnescapePathValues}if engine.RemoveExtraSlash {rPath = cleanPath(rPath)}// Find root of the tree for the given HTTP method// 找到对应请求方法的前缀树t := engine.treesfor 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 {// 找到所有的handlerfuncc.handlers = value.handlersc.fullPath = value.fullPath// 具体去执行handlerfuncc.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++}
}