Gin 框架的路由結構剖析

Gingo 語言的一款輕量級框架,風格簡單樸素,支持中間件,動態路由等功能。 gin項目github地址

路由是web框架的核心功能。在沒有讀過 gin 的代碼之前,在我眼裏的路由實現是這樣的:根據路由裏的 / 把路由切分成多個字符串數組,然後按照相同的前子數組把路由構造成樹的結構;尋址時,先把請求的 url 按照 / 切分,然後遍歷樹進行尋址。

比如:定義了兩個路由 /user/get/user/delete ,則會構造出擁有三個節點的路由樹,根節點是 user ,兩個子節點分別是 get delete

上述是一種實現路由樹的方式,且比較直觀,容易理解。對 url 進行切分、比較,時間複雜度是 O(2n)

Gin的路由實現使用了類似前綴樹的數據結構,只需遍歷一遍字符串即可,時間複雜度為 O(n)

當然,對於一次 http 請求來説,這點路由尋址優化可以忽略不計。

Engine

GinEngine 結構體內嵌了 RouterGroup 結構體,定義了 GETPOST 等路由註冊方法。

Engine 中的 trees 字段定義了路由邏輯。 treesmethodTrees 類型(其實就是 []methodTree ), trees 是一個數組,不同請求方法的路由在不同的樹( methodTree )中。

最後, methodTree 中的 root 字段( *node 類型)是路由樹的根節點。樹的構造與尋址都是在 *node 的方法中完成的。

UML 結構圖

Gin 框架的路由結構剖析
Gin 框架的路由結構剖析

trees 是個數組,數組裏會有不同請求方法的路由樹。

Gin 框架的路由結構剖析
Gin 框架的路由結構剖析

node

node 結構體定義如下

type node struct {
    path      string           // 當前節點相對路徑(與祖先節點的 path 拼接可得到完整路徑)
    indices   string           // 所以孩子節點的path[0]組成的字符串
    children  []*node          // 孩子節點
    handlers  HandlersChain    // 當前節點的處理函數(包括中間件)
    priority  uint32           // 當前節點及子孫節點的實際路由數量
    nType     nodeType         // 節點類型
    maxParams uint8            // 子孫節點的最大參數數量
    wildChild bool             // 孩子節點是否有通配符(wildcard)
}

path 和 indices

關於 pathindices ,其實是使用了前綴樹的邏輯。

舉個栗子:

如果我們有兩個路由,分別是 /index/inter ,則根節點為 {path: "/in", indices: "dt"...} ,兩個子節點為 {path: "dex", indices: ""},{path: "ter", indices: ""}

handlers

handlers 裏存儲了該節點對應路由下的所有處理函數,處理業務邏輯時是這樣的:

func (c *Context) Next() {
    c.index++
    for s := int8(len(c.handlers)); c.index < s; c.index++ {
        c.handlers[c.index](c)
    }
}

一般來説,除了最後一個函數,前面的函數被稱為 中間件

如果某個節點的 handlers 為空,則説明該節點對應的路由不存在。比如上面定義的根節點對應的路由 /in 是不存在的,它的 handlers 就是 []

nType

Gin 中定義了四種節點類型:

const (
    static nodeType = iota // 普通節點,默認
    root       // 根節點
    param      // 參數路由,比如 /user/:id
    catchAll   // 匹配所有內容的路由,比如 /article/*key
)

paramcatchAll 使用的區別就是 :* 的區別。 * 會把路由後面的所有內容賦值給參數 key ;但 : 可以多次使用。

比如: /user/:id/:no 是合法的,但 /user/*id/:no 是非法的,因為 * 後面所有內容會賦值給參數 id

wildChild

如果孩子節點是通配符( * 或者 : ),則該字段為 true

一個路由樹的例子

定義路由如下:

r.GET("/", func(context *gin.Context) {})
r.GET("/index", func(context *gin.Context) {})
r.GET("/inter", func(context *gin.Context) {})
r.GET("/go", func(context *gin.Context) {})
r.GET("/game/:id/:k", func(context *gin.Context) {})

得到的路由樹結構圖為:

Gin 框架的路由結構剖析
Gin 框架的路由結構剖析

附一篇前綴樹的文章, 前綴樹和後綴樹

以上。