On the routing tree of gin

GIN It's a golang frequently-used Web frame , It's right API friendly , The source code comments are also very clear , It is fast and flexible to use , And high fault tolerance . The route in the title can be simply understood as the page address entered in the browser , and “ Trees ” It is An optimized data structure . Because in GIN This Web The routing tree in the framework is a prefix tree , So today we will focus on prefix tree .

What is a prefix tree

The prefix tree is actually Tire Trees , It's a variant of hash tree , Usually people call it word search tree . Prefix trees are often used for statistics , Sort and save a large number of strings . Because the prefix tree can reduce the query time by using the common prefix of the string , Minimize unnecessary string comparisons . Therefore, prefix tree is often used by search engine system for text word frequency statistics . Prefix trees have the following characteristics ：

• The root node contains no characters , Other nodes contain characters

• The node contents of each layer are different

• From the root node to a node , The characters passing through the path are concatenated , Is the string corresponding to the node

• The child nodes of each node usually have a flag bit , Used to mark the end of a word

Take looking up Xinhua Dictionary as an example , Let's have a visual look at the prefix tree . I believe everyone has used the word search method of phonetic order , The operation contents are as follows ：

• Accurate pronunciation , Determine what letter to look up according to the syllable of the word .

• stay “ Chinese phonetic syllable index ” Find this letter in , Find the syllable of the word in the corresponding part of the letter , Read the page number next to the syllable .

• Open the body of the dictionary according to this page number , Find the word you want to look up in four tone order .

The whole process can be seen as a rough prefix tree lookup process , For example, to find idioms “ May all your wishes come true ” Medium “ assume ” Two words , In the dictionary, there is the following structure ：

In the process of searching , We use the initials x, find x In the middle of xi This common part , Then find the corresponding rest according to different letters . Put it on the prefix tree , In the case of “ heart ” Corresponding xi -> n, and “ Want to ” It corresponds to xi -> ang

GIN Prefix tree in - Compact prefix tree

GIN Compared with the common prefix tree, the prefix tree in reduces the query level , For example, what we want to find above “ assume ” among xi As a common part , In fact, it can be allocated to the same node on the same layer instead of being divided into two parts ：

This is the compact prefix tree , Similarly, if we have the following four routes , The compact prefix tree they form will look like this ：

r.GET("/", handle1)r.GET("/product", handle2)r.GET("/product/:id", handle3)r.GET("/product/:name", handle4)

Store information in nodes

You can see from the above ,GIN The address of the entire query in the prefix tree can be obtained by splicing each node in the routing tree . that GIN How to complete the addition of these nodes , What is stored in each node ？ We can solve this problem through GIN Source code to get the answer .

First GIN The common way to declare a route in is as follows ：

func main(){    r := gin.Default()    r.GET("/", func(context *gin.Context) {        context.JSON(200, gin.H{            "status":"ok",        })    })    r.Run()}// default Will initialize a engin example func Default() *Engine {    debugPrintWARNINGDefault()    engine := New()    engine.Use(Logger(), Recovery())    return engine}type Engine struct {     RouterGroup        // type RouterGroup struct {    //    Handlers HandlersChain        //    basePath string        //    engine   *Engine        //    root     bool        // }        //  Lowercase private , Not open     trees            methodTrees         // ...}type methodTrees []methodTreetype methodTree struct {    method string    root   *node}// trees  This part of the routing tree consists of a method  and root Field node List maintenance //  Every node Represents each node in the routing tree // node The fields are as follows type node struct {    path      string //  The absolute path of the current node     indices   string //  Cache the first character of the next node   When the child node is of wildcard type ,indices=''        //  The default is  false, When  children  yes   Wildcard type ,wildChild  by  true  namely  indices=''    wildChild bool //  The default is  false, When  children  yes   Wildcard type ,wildChild  by  true        //  The type of node , Because in the case of wildcards, special processing is required when querying ,         //  The default is static type         //  The root node is  root type         //  about  path  Cases that contain colon wildcards ,nType  yes  param  type         //  To contain  *  Wildcards ,nType  The type is  catchAll  type     nType     nodeType        //  It means that there are several routes passing through this node , Used on nodes     priority  uint32        //  List of child nodes     children  []*node // child nodes, at most 1 :param style node at the end of the array    handlers  HandlersChain        //  It's from  root  All from node to current node  path  part ; If this node is the end node  handlers  For the corresponding processing chain , Otherwise  nil;        // maxParams  Is the maximum number of wildcards from the current node to each leaf node     fullPath  string}//  The specific node types are as follows const (    static nodeType = iota // default,  Static nodes , Normal match (/user)    root                   //  The root node  (/)    param                 //  Parameter node (/user/:id)    catchAll              //  Universal matching , Match any parameter (*user))

To add a route, you can do the following ：

//  In the process of creating a route ,  Each method will eventually be parsed and thrown to handle Function to handle func main(){    r := gin.Default()    r.GET("/", func(context *gin.Context) {        context.JSON(200, gin.H{            "status":"ok",        })    })    r.Run()}func (group *RouterGroup) GET(relativePath string, handlers ...HandlerFunc) IRoutes {    return group.handle(http.MethodGet, relativePath, handlers)}func (group *RouterGroup) POST(relativePath string, handlers ...HandlerFunc) IRoutes {    return group.handle(http.MethodPost, relativePath, handlers)}//  handle The function converts an absolute path to a relative path //   And will   Request method 、 Relative paths 、 processing method   Pass to addRoutefunc (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {    absolutePath := group.calculateAbsolutePath(relativePath)    handlers = group.combineHandlers(handlers)    group.engine.addRoute(httpMethod, absolutePath, handlers)    return group.returnObj()}//  Routing is mainly added in addRoute This function completes func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {   //  check    //  The path must be in  /  start    //  The request method cannot be empty    //  Processing method cannot be empty    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")   //  If it's on gin Of debug Pattern , Then the corresponding processing    debugPrintRoute(method, path, handlers)   //  Get the root of the corresponding tree according to the request method    //  Each request method has its own corresponding compact prefix tree , Here we get the top root through the request method    root := engine.trees.get(method)   //  If the root is empty , This means that this is the first route , Create one by yourself  /  by path The root node    if root == nil {      //  If not, create       root = new(node)      root.fullPath = "/"      engine.trees = append(engine.trees, methodTree{method: method, root: root})   }   //  Here path It's a sub route    //  The above content is a layer of pre verification , Avoid non-standard writing, which will cause the request query to fail    //  The next step is to add the body of the route    root.addRoute(path, handlers)}

// addRoute adds a node with the given handle to the path.// Not concurrency-safe!  Concurrency is not secure func (n *node) addRoute(path string, handlers HandlersChain) {    fullPath := path        //  When I'm done , The number of routes passing through this node will be +1    n.priority++    // Empty tree        //  If the tree is empty ,  That is, there is only one root node "/"  Insert a child node ,  And set the current node to root Node of type     if len(n.path) == 0 && len(n.children) == 0 {        n.insertChild(path, fullPath, handlers)        n.nType = root        return    }    parentFullPathIndex := 0walk:    for {        // Find the longest common prefix.        // This also implies that the common prefix contains no ':' or '*'        // since the existing key can't contain those chars.                //  Find the length of the longest common prefix   That is to i Location  path[i] == n.path[i]        i := longestCommonPrefix(path, n.path)        // Split edge                //  Assume that the prefix information of the current node is  hello                //  The existing prefix information is heo The node of ,  The current node needs to be split                 //  Split into  he node   as well as  (llo  and  o  Two child nodes )        if i < len(n.path) {            child := node{                                //  Remove the common prefix section , The rest of the content acts as child nodes                 path:      n.path[i:],                wildChild: n.wildChild,                indices:   n.indices,                children:  n.children,                handlers:  n.handlers,                priority:  n.priority - 1,                fullPath:  n.fullPath,            }            n.children = []*node{&child}            // []byte for proper unicode char conversion, see #65            n.indices = bytesconv.BytesToString([]byte{n.path[i]})            n.path = path[:i]            n.handlers = nil            n.wildChild = false            n.fullPath = fullPath[:parentFullPathIndex+i]        }        // Make new node a child of this node                //  Insert the new node into the new node parent Node as a child node         if i < len(path) {            path = path[i:]            c := path[0]            // '/' after param                        //  If it is a parameter node   Form like /:i            if n.nType == param && c == '/' && len(n.children) == 1 {                parentFullPathIndex += len(n.path)                n = n.children[0]                n.priority++                continue walk            }            // Check if a child with the next path byte exists            for i, max := 0, len(n.indices); i < max; i++ {                if c == n.indices[i] {                    parentFullPathIndex += len(n.path)                    i = n.incrementChildPrio(i)                    n = n.children[i]                    continue walk                }            }            // Otherwise insert it            if c != ':' && c != '*' && n.nType != catchAll {                // []byte for proper unicode char conversion, see #65                n.indices += bytesconv.BytesToString([]byte{c})                child := &node{                    fullPath: fullPath,                }                n.addChild(child)                n.incrementChildPrio(len(n.indices) - 1)                n = child            } else if n.wildChild {                // inserting a wildcard node, need to check if it conflicts with the existing wildcard                n = n.children[len(n.children)-1]                n.priority++                // Check if the wildcard matches                if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&                    // Adding a child to a catchAll is not possible                    n.nType != catchAll &&                    // Check for longer wildcard, e.g. :name and :names                    (len(n.path) >= len(path) || path[len(n.path)] == '/') {                    continue walk                }                // Wildcard conflict                pathSeg := path                if n.nType != catchAll {                    pathSeg = strings.SplitN(pathSeg, "/", 2)[0]                }                prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path                panic("'" + pathSeg +                    "' in new path '" + fullPath +                    "' conflicts with existing wildcard '" + n.path +                    "' in existing prefix '" + prefix +                    "'")            }            n.insertChild(path, fullPath, handlers)            return        }        // Otherwise add handle to current node                //  Set processing function , If it already exists , False report         if n.handlers != nil {            panic("handlers are already registered for path '" + fullPath + "'")        }        n.handlers = handlers        n.fullPath = fullPath        return    }}

Priority priority

In order to quickly find and combine complete routes ,GIN While adding routes , Will be added to each node Priority This attribute . When searching, it is based on Priority Sort , Common node ( The node with the largest number of times ) At the front , And at the same level Priority The bigger the value is. , The more priority is given to matching .

Why should we 9 Two request methods are placed in slice instead of map in

This is because 9 Request methods correspond to 9 Routing tree , and GIN All corresponding request methods maintain a routing tree , At the same time, these key information are wrapped in Node In vivo structure , And placed in an array instead of map in . This is to fix the number of requests , At the same time, the request method will be maintained in memory after the project is started , Use fixed length slice So as to ensure a certain query efficiency and reduce memory consumption .

type methodTrees []methodTreefunc (trees methodTrees) get(method string) *node {    for _, tree := range trees {        if tree.method == method {            return tree.root        }    }    return nil}

Find the route

After the routing tree is built ,GIN You can start to receive requests normally . The first step is from ServeHTTP Start to resolve the routing address , The processing logic of the search process is as follows ：

• Request a piece of memory to fill the response body

• Processing request information

• from trees Traverse the comparison request method in , Get the routing tree of the most corresponding request method

• Get root node

func (engine *Engine) ServeHTTP(w http.ResponseWriter, req *http.Request) {    c := engine.pool.Get().(*Context)    c.writermem.reset(w)    c.Request = req    c.reset()    //  Really start processing requests     engine.handleHTTPRequest(c)    engine.pool.Put(c)}

func (engine *Engine) handleHTTPRequest(c *Context) {    // ...    t := engine.trees    for i, tl := 0, len(t); i < tl; i++ {        //  Judge according to the request method         if t[i].method != httpMethod {            continue        }        root := t[i].root        //  Find the route on the method tree         value := root.getValue(rPath, c.params, unescape)        if value.params != nil {            c.Params = *value.params        }        //  Execute processing functions         if value.handlers != nil {            c.handlers = value.handlers            c.fullPath = value.fullPath            c.Next() //  involves gin Middleware mechanism             //  When you get here , The request has been processed , The returned results are also stored in the corresponding structure             c.writermem.WriteHeaderNow()            return        }        // ...      break   }   if engine.HandleMethodNotAllowed {    for _, tree := range engine.trees {        if tree.method == httpMethod {            continue        }        if value := tree.root.getValue(rPath, nil, c.skippedNodes, unescape); value.handlers != nil {            c.handlers = engine.allNoMethod            serveError(c, http.StatusMethodNotAllowed, default405Body)            return        }    }    }}

It's about GIN Some experience sharing of routing tree , I hope I can help you .

Recommended reading

Interviewer asked ：Go Whether the parameters in are passed by value or by reference ？

Golang Singleton pattern of common design patterns