1. 前言

net/http的ServeMux提供了一個路由分發(fā)功能涝影，但是功能比較簡單顿肺，主要有以下幾點缺陷:

1. 注冊路由處理函數(shù)時不區(qū)分http方法
2. 在有大量有相同前綴path情況下空間率不高

httprouter為每一種http方法維護一顆路由樹梯影，節(jié)省空間又更加高效，倉庫路徑: https://github.com/julienschmidt/httprouter

2. httprouter使用

package main

import (
    "fmt"
    "github.com/julienschmidt/httprouter"
    "net/http"
)

func handler(writer http.ResponseWriter, request *http.Request, params httprouter.Params) {
    fmt.Fprintf(writer, request.URL.Path)
}

func startHTTPServer(addr string) {
    r := httprouter.New()  // 創(chuàng)建一個Router實例
    r.GET("/home/index", handler)
    http.ListenAndServe(addr, r)
}

func main() {
    startHTTPServer(":10092")
}

Router實現(xiàn)了ServeHTTP(w, r)方法怕篷，所以也是Handler類型捐川，上面代碼只做個兩件事:

1. 創(chuàng)建一個Router實例，并注冊/home/index的處理函數(shù)
2. 啟動http服務(wù)器奋姿，并傳入Router實例

因為傳入了Router實例锄开，所以最終處理http請求的將是Router的ServeHTTP(w, r)方法，先來看看Router類型定義:

// Router is a http.Handler which can be used to dispatch requests to different
// handler functions via configurable routes
type Router struct {
    // Router把GET/POST/PUT等方法的路由掛在獨立的一顆radix(基數(shù)數(shù))上
    // key即為http方法如GET/POST/PUT...
    // node即為radix樹的根節(jié)點
    trees map[string]*node

    // Enables automatic redirection if the current route can't be matched but a
    // handler for the path with (without) the trailing slash exists.
    // For example if /foo/ is requested but a route only exists for /foo, the
    // client is redirected to /foo with http status code 301 for GET requests
    // and 307 for all other request methods.
    // 如果/home匹配不成功称诗，/home/能匹配萍悴，或者/home/匹配不成功，但是/home能匹配
    // 在該值為true的情況下可以把/home重定向到/home/或者把/home/重定向到/home
    RedirectTrailingSlash bool

    // If enabled, the router tries to fix the current request path, if no
    // handle is registered for it.
    // First superfluous path elements like ../ or // are removed.
    // Afterwards the router does a case-insensitive lookup of the cleaned path.
    // If a handle can be found for this route, the router makes a redirection
    // to the corrected path with status code 301 for GET requests and 307 for
    // all other request methods.
    // For example /FOO and /..//Foo could be redirected to /foo.
    // RedirectTrailingSlash is independent of this option.
    // 如果path匹配不成功寓免，在該值為true情況下可以把path先重新清理再重定向癣诱，如:/home../
    // 在清理之后就變成了/，如果/home../匹配不成功袜香，在該值為true時重定向到/
    RedirectFixedPath bool

    // If enabled, the router checks if another method is allowed for the
    // current route, if the current request can not be routed.
    // If this is the case, the request is answered with 'Method Not Allowed'
    // and HTTP status code 405.
    // If no other Method is allowed, the request is delegated to the NotFound
    // handler.
    // 該選項配合下面MethodNotAllowed選項一起使用撕予，如果請求不能被route則調(diào)用MethodNotAllowed
    // 方法處理
    HandleMethodNotAllowed bool

    // If enabled, the router automatically replies to OPTIONS requests.
    // Custom OPTIONS handlers take priority over automatic replies.
    // 該選項配合GlobalOPTIONS選項一起使用，如果該選項為true蜈首，則options請求優(yōu)先
    // 使用GlobalOPTIONS方法處理
    HandleOPTIONS bool

    // An optional http.Handler that is called on automatic OPTIONS requests.
    // The handler is only called if HandleOPTIONS is true and no OPTIONS
    // handler for the specific path was set.
    // The "Allowed" header is set before calling the handler.
    GlobalOPTIONS http.Handler

    // Cached value of global (*) allowed methods
    globalAllowed string

    // Configurable http.Handler which is called when no matching route is
    // found. If it is not set, http.NotFound is used.
    NotFound http.Handler

    // Configurable http.Handler which is called when a request
    // cannot be routed and HandleMethodNotAllowed is true.
    // If it is not set, http.Error with http.StatusMethodNotAllowed is used.
    // The "Allow" header with allowed request methods is set before the handler
    // is called.
    MethodNotAllowed http.Handler

    // Function to handle panics recovered from http handlers.
    // It should be used to generate a error page and return the http error code
    // 500 (Internal Server Error).
    // The handler can be used to keep your server from crashing because of
    // unrecovered panics.
    // 如果設(shè)置了該方法实抡，則http服務(wù)器pandic時調(diào)用該方法
    PanicHandler func(http.ResponseWriter, *http.Request, interface{})
}

上面最重要的就是trees成員欠母，trees圖示:

image.png

接下來還是從示例代碼跟蹤到httprouter里查看相應(yīng)實現(xiàn):

2.1 GET()方法

r.GET("/home/index", handler)

// GET is a shortcut for router.Handle(http.MethodGet, path, handle)
func (r *Router) GET(path string, handle Handle) {
    r.Handle(http.MethodGet, path, handle)
}
// Handle registers a new request handle with the given path and method.
//
// For GET, POST, PUT, PATCH and DELETE requests the respective shortcut
// functions can be used.
//
// This function is intended for bulk loading and to allow the usage of less
// frequently used, non-standardized or custom methods (e.g. for internal
// communication with a proxy).
func (r *Router) Handle(method, path string, handle Handle) {
    if len(path) < 1 || path[0] != '/' {
        panic("path must begin with '/' in path '" + path + "'")
    }

    if r.trees == nil {
        r.trees = make(map[string]*node)
    }

    root := r.trees[method]
    if root == nil {
        root = new(node)
        r.trees[method] = root

        r.globalAllowed = r.allowed("*", "")
    }

    root.addRoute(path, handle)
}

可以看到不管是GET/PUT/POST/HEAD等，內(nèi)部都是調(diào)用Router的Handle方法吆寨，GET方法主要做了如下幾件事:

1. 如果trees為nil則創(chuàng)建它赏淌，如果GET方法對應(yīng)的radix樹根節(jié)點不存在，則創(chuàng)建它
2. 把path和handler添加到路由樹中

其他http方法類似啄清，只是把path六水，handler添加到各自獨立的路由樹結(jié)構(gòu)中，我們知道http服務(wù)器最終是通過注冊Handler來處理http請求的(如果傳入的Handler為nil則用DefaultServeMux)盒延，這里我們傳入的是Router實例缩擂，接下來我們看它的ServeHTTP(w, r)方法實現(xiàn)。

2.2 ServeHTTP(w, r)

// ServeHTTP makes the router implement the http.Handler interface.
func (r *Router) ServeHTTP(w http.ResponseWriter, req *http.Request) {
    // 如果設(shè)置PanicHandler則在defer中會調(diào)用該函數(shù)
    if r.PanicHandler != nil {
        defer r.recv(w, req)
    }

    path := req.URL.Path

    // 通過方法找到radix樹根節(jié)點
    if root := r.trees[req.Method]; root != nil {
        // 在路由樹中找到path對應(yīng)的handler添寺，用它來處理http請求胯盯，正常的話這里就返回了
        // 剩下的就是錯誤處理,注意返回的tsr用來提示對path的請求是否可以滿足重定向
        // 滿足為true，不滿足為false
        if handle, ps, tsr := root.getValue(path); handle != nil {
            handle(w, req, ps)
            return
        } else if req.Method != http.MethodConnect && path != "/" {
            // 判斷是否需要重定向计露，GET/POST重定向分別用301, 307
            code := 301 // Permanent redirect, request with GET method
            if req.Method != http.MethodGet {
                // Temporary redirect, request with same method
                // As of Go 1.3, Go does not support status code 308.
                code = 307
            }
            // 判斷是需要在path添加`/`還是去掉`/`博脑，并重定向
            if tsr && r.RedirectTrailingSlash {
                if len(path) > 1 && path[len(path)-1] == '/' {
                    req.URL.Path = path[:len(path)-1]
                } else {
                    req.URL.Path = path + "/"
                }
                http.Redirect(w, req, req.URL.String(), code)
                return
            }

            // Try to fix the request path
            // 清理path，并在能匹配path情況下重定向
            if r.RedirectFixedPath {
                fixedPath, found := root.findCaseInsensitivePath(
                    CleanPath(path),
                    r.RedirectTrailingSlash,
                )
                if found {
                    req.URL.Path = string(fixedPath)
                    http.Redirect(w, req, req.URL.String(), code)
                    return
                }
            }
        }
    }

    // 以下處理OPTIONS方法票罐、路由不能匹配(NotFound)叉趣、路由不允許(MethodNotAllowed)
    // 有自定義handler則優(yōu)先使用自定義handler處理，沒有的話默認處理
    if req.Method == http.MethodOptions && r.HandleOPTIONS {
        // Handle OPTIONS requests
        if allow := r.allowed(path, http.MethodOptions); allow != "" {
            w.Header().Set("Allow", allow)
            if r.GlobalOPTIONS != nil {
                r.GlobalOPTIONS.ServeHTTP(w, req)
            }
            return
        }
    } else if r.HandleMethodNotAllowed { // Handle 405
        if allow := r.allowed(path, req.Method); allow != "" {
            w.Header().Set("Allow", allow)
            if r.MethodNotAllowed != nil {
                r.MethodNotAllowed.ServeHTTP(w, req)
            } else {
                http.Error(w,
                    http.StatusText(http.StatusMethodNotAllowed),
                    http.StatusMethodNotAllowed,
                )
            }
            return
        }
    }

    // Handle 404
    if r.NotFound != nil {
        r.NotFound.ServeHTTP(w, req)
    } else {
        http.NotFound(w, req)
    }
}

Router的ServeHTTP(w, r)比較簡單该押，主要做如下處理:

1. 根據(jù)http請求方法找到路由樹(radix)疗杉，并通過path找到對應(yīng)handler
2. 如果path匹配不成功，則判斷是否需要重定向
3. 如果path匹配不成功蚕礼，也不滿足重定向烟具，則進行錯誤處理(NotFound或MethodNotAllowed)

可以看到httprouter結(jié)構(gòu)非常簡單，注冊handler到http方法對應(yīng)的路由樹中(radix)奠蹬，在處理http請求時從方法對應(yīng)的路由樹上查找handler朝聋，接下來通過查看代碼了解路由樹是怎么實現(xiàn)的。

3. 路由樹

先來看下節(jié)點結(jié)構(gòu):

type node struct {
    path      string  // 節(jié)點路徑
    wildChild bool  // 子節(jié)點是否是`:`或`*`通配節(jié)點
    nType     nodeType  // 節(jié)點類型
    maxParams uint8  // 最大參數(shù)
    priority  uint32  // 優(yōu)先級
    indices   string  // 子節(jié)點首字母組成的字符串囤躁，方便查找子節(jié)點
    children  []*node  // 子節(jié)點
    handle    Handle  // 處理函數(shù)
}

3.1 insertChild

先來分析insertChild函數(shù)冀痕，因為addRoute(path,handler)在空節(jié)點插入時調(diào)用它:

func (n *node) insertChild(numParams uint8, path, fullPath string, handle Handle) {
    var offset int // already handled bytes of the path

    // find prefix until first wildcard (beginning with ':'' or '*'')
    // 遍歷path，找到其中的通配符 `:` or `*`
    for i, max := 0, len(path); numParams > 0; i++ {
        c := path[i]
        if c != ':' && c != '*' {
            continue
        }

        // find wildcard end (either '/' or path end)
        // 通配符必須有名稱狸演，并且名稱中不能包含`:` or `*`
        // 比如/home/first:name,這里name為統(tǒng)配符名稱言蛇，該名稱不能為na*me，na:me等
        // 這里遍歷到path末尾或者遍歷到下一個segment(以/分割)
        end := i + 1
        for end < max && path[end] != '/' {
            switch path[end] {
            // the wildcard name must not contain ':' and '*'
            case ':', '*':
                panic("only one wildcard per path segment is allowed, has: '" +
                    path[i:] + "' in path '" + fullPath + "'")
            default:
                end++
            }
        }

        // check if this Node existing children which would be
        // unreachable if we insert the wildcard here
        // 判斷是否和已有的path沖突宵距，比如/home/first:name和/home/firstone就會沖突
        // 其實本質(zhì)上是如果有wildcard子節(jié)點猜极，那么就只能有唯一一個子節(jié)點(就是wildcard節(jié)點)
        if len(n.children) > 0 {
            panic("wildcard route '" + path[i:end] +
                "' conflicts with existing children in path '" + fullPath + "'")
        }

        // check if the wildcard has a name
        // 通配符必須有名字，意味著end在上面for{}必須有變動消玄，所以end - i >= 2
        if end-i < 2 {
            panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
        }

        // 對通配符`:`的處理
        if c == ':' { // param
            // split path at the beginning of the wildcard
            // 截取通配符`:`之前的路徑跟伏，比如/home/first:name，截取的是/home/first
            if i > 0 {
                n.path = path[offset:i]
                offset = i
            }

            // 創(chuàng)建子節(jié)點翩瓜，并設(shè)置當前節(jié)點的wildChild為true受扳，表示添加的是一個包含通配符
            // 的子節(jié)點，添加子節(jié)點后把n替換成子節(jié)點地址
            child := &node{
                nType:     param,
                maxParams: numParams,
            }
            n.children = []*node{child}
            n.wildChild = true
            n = child
            n.priority++
            numParams--

            // if the path doesn't end with the wildcard, then there
            // will be another non-wildcard subpath starting with '/'
            // 如果通配符不是path的最后一個segment兔跌，則更新子節(jié)點路徑勘高，比如:/home/first:name/sub
            // 則把子節(jié)點path設(shè)置為`:name`,注意這里沒有/字符
            // 如果通配符就是path的最后一個segment，如:/home/first:name坟桅，則這里會跳出for{}循環(huán)华望，
            // 那么該通配符子節(jié)點會變成葉子節(jié)點，直接存放path和handler仅乓，在這個函數(shù)最后兩行實現(xiàn)
            if end < max {
                n.path = path[offset:end]
                offset = end

                child := &node{
                    maxParams: numParams,
                    priority:  1,
                }
                n.children = []*node{child}
                n = child
            }

        } else { // catchAll
            // 找到`*`通配符赖舟，該通配符必須是在path的最后一個segment
            if end != max || numParams > 1 {
                panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
            }
            // `*`通配符segment不能以/結(jié)尾，比如：/*name/是錯誤的
            // 但其實這種情況在上面的判斷中就會panic夸楣，感覺是多余的
            if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
                panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
            }

            // currently fixed width 1 for '/'
            // 通配符`*`前面必須是`/`,如：/home/*name, 但是不能為/home/na*me(通配符:可以)
            i--
            if path[i] != '/' {
                panic("no / before catch-all in path '" + fullPath + "'")
            }
            // 注意上面i--操作宾抓，offset定位到`*`前的/
            // 如果path是/home/first:name/sub/*information， 則
            // 節(jié)點path為/sub,注意不是/sub/
            n.path = path[offset:i]
            // first node: catchAll node with empty path
            // 創(chuàng)建一個path為空的子節(jié)點豫喧， 注意該節(jié)點的wildChild=true石洗，標識它有一個wildcard的子節(jié)點
            // 同時又把n設(shè)置為子節(jié)點的地址
            child := &node{
                wildChild: true,
                nType:     catchAll,
                maxParams: 1,
            }
            // update maxParams of the parent node
            if n.maxParams < 1 {
                n.maxParams = 1
            }
            n.children = []*node{child}
            // 這里其實就是賦值/, gin里就直接給賦值/了
            n.indices = string(path[i])
            n = child
            n.priority++

            // second node: node holding the variable
            // 再添加一個子節(jié)點，因為`*`必須是path的最后一個segment紧显，所以它必定為葉子節(jié)點讲衫，葉子節(jié)點中保存
            // path和handler,如果path=/home/first:name/sub/*information，則該節(jié)點的path=/*information
            // 因為是葉子節(jié)點孵班，保存完path和handler后可以直接返回
            child = &node{
                path:      path[i:],
                nType:     catchAll,
                maxParams: 1,
                handle:    handle,
                priority:  1,
            }
            n.children = []*node{child}

            return
        }
    }

    // insert remaining path part and handle to the leaf
    // 把剩余的path和handler保存在葉子節(jié)點中
    // 如path=/home/:name涉兽，這里path=:name
    n.path = path[offset:]
    n.handle = handle
}

注冊如下處理函數(shù)，再畫出路由樹:

func myHandler(writer http.ResponseWriter, request *http.Request, params httprouter.Params) {
    fmt.Fprintf(writer, request.URL.Path)
}

func startHTTPServer(addr string) {
    r := httprouter.New()
    r.GET("/home/first:name/sub/*information", myHandler)
    http.ListenAndServe(addr, r)
}

添加了個DumpTree方法重父，可以用來遍歷樹:

func DumpTree(r *Router, method string) {
    if r.trees != nil && r.trees[method] != nil {
        r.trees[method].printNode()
    }
}

func (n *node) printNode() {
    if n != nil {
        fmt.Println(n)
        for _, v := range n.children {
            v.printNode()
        }
    }
}

func (n *node) String() string {
    buf := bytes.Buffer{}
    switch n.nType {
    case static:
        buf.WriteString("nodeType: [" + "default" + "]\n")
    case root:
        buf.WriteString("nodeType: [" + "root" + "]\n")
    case param:
        buf.WriteString("nodeType: [" + "param" + "]\n")
    case catchAll:
        buf.WriteString("nodeType: [" + "catchAll" + "]\n")
    default:
        buf.WriteString("nodeType: [" + "unknow" + "]\n")
    }
    buf.WriteString("path: [" + n.path + "]\n")
    buf.WriteString("priority: [" + strconv.Itoa(int(n.priority)) + "]\n")
    buf.WriteString("indices: [" + n.indices + "]\n")
    if n.wildChild {
        buf.WriteString("wildChild: [" + "true" + "]\n")
    } else {
        buf.WriteString("wildChild: [" + "false" + "]\n")
    }
    if n.handle != nil {
        buf.WriteString("handler: [" + runtime.FuncForPC(reflect.ValueOf(n.handle).Pointer()).Name() + "]\n")
    } else {
        buf.WriteString("handler: [" + "nil" + "]\n")
    }

    return buf.String()
}

添加/home/first:name/sub/*information路由樹

3.2 addRoute

添加路由到路由樹可能會知道以存在的節(jié)點分拆花椭，新節(jié)點添加，路由沖突檢測房午，接下來看代碼如何實現(xiàn):

// addRoute adds a node with the given handle to the path.
// Not concurrency-safe!
func (n *node) addRoute(path string, handle Handle) {
    fullPath := path
    n.priority++
    numParams := countParams(path)

    // non-empty tree
    // 如果路由樹是空的矿辽，則直接走insertChild流程
    // 節(jié)點的path不為空則路由樹肯定不為空
    // 如果第一次添加的path=/*information，則路由樹根節(jié)點path=""郭厌，但子節(jié)點不為nil
    if len(n.path) > 0 || len(n.children) > 0 {
    walk:
        for {
            // Update maxParams of the current node
            if numParams > n.maxParams {
                n.maxParams = numParams
            }

            // Find the longest common prefix.
            // This also implies that the common prefix contains no ':' or '*'
            // since the existing key can't contain those chars.
            // 找到最長的公共部分
            i := 0
            max := min(len(path), len(n.path))
            for i < max && path[i] == n.path[i] {
                i++
            }

            // 說明需要分拆節(jié)點袋倔，提取公共的節(jié)點作為父節(jié)點
            // 節(jié)點path剩余的部門放到新建的節(jié)點中，新建的
            // 節(jié)點除了nodeType折柠，其他屬性和原先節(jié)點一樣
            // Split edge
            if i < len(n.path) {
                child := node{
                    path:      n.path[i:],
                    wildChild: n.wildChild,
                    nType:     static,
                    indices:   n.indices,
                    children:  n.children,
                    handle:    n.handle,
                    priority:  n.priority - 1,
                }

                // Update maxParams (max of all children)
                for i := range child.children {
                    if child.children[i].maxParams > child.maxParams {
                        child.maxParams = child.children[i].maxParams
                    }
                }

                // 把原來的公共部門單獨成一個node宾娜，該node變成一個普通節(jié)點了
                // 并把子節(jié)點path的首字母添加到node.indices中，indices中首字母
                // 按子節(jié)點優(yōu)先級順序排列扇售，方便遍歷前塔，可以遍歷indices快速找到子節(jié)點
                // 在父節(jié)點children成員中的下標
                n.children = []*node{&child}
                // []byte for proper unicode char conversion, see #65
                // 保存子節(jié)點path的首字母
                n.indices = string([]byte{n.path[i]})
                n.path = path[:i]
                n.handle = nil
                n.wildChild = false
            }

            // Make new node a child of this node
            // 新添加的路由去掉path公共部門嚣艇，剩下的保存到新建的節(jié)點中
            if i < len(path) {
                path = path[i:]
                if n.wildChild {
                    n = n.children[0]
                    n.priority++

                    // Update maxParams of the child node
                    if numParams > n.maxParams {
                        n.maxParams = numParams
                    }
                    numParams--

                    // Check if the wildcard matches
                    // 如果子節(jié)點是通配符節(jié)點，那么只有一種情況不報錯
                    // 已存在/home/first:name华弓，添加/home/first:name/xxx食零，其他情況全部panic
                    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
                    } else {
                        // Wildcard conflict
                        var pathSeg string
                        if n.nType == catchAll {
                            pathSeg = path
                        } else {
                            pathSeg = strings.SplitN(path, "/", 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 +
                            "'")
                    }
                }
                // 其實就是子節(jié)點中path的第一個字母
                c := path[0]

                // slash after param
                // 針對有多個:通配符情況，如:已經(jīng)存在/home/first:name/:second/
                // 添加/home/first:name/:second/sub
                if n.nType == param && c == '/' && len(n.children) == 1 {
                    n = n.children[0]
                    n.priority++
                    continue walk
                }

                // Check if a child with the next path byte exists
                // 在節(jié)點的indices中有匹配path首字母的字符存在寂屏，則說明path
                // 還能提供公共的部門贰谣，繼續(xù)往下遍歷
                for i := 0; i < len(n.indices); i++ {
                    if c == n.indices[i] {
                        i = n.incrementChildPrio(i)
                        n = n.children[i]
                        continue walk
                    }
                }

                // Otherwise insert it
                // 最終找到一個節(jié)點下不能再提供公共部門了，就在這個節(jié)點下新增一個節(jié)點
                // 在children成員后面添加迁霎，并按優(yōu)先級重新排序吱抚，indices也重新排序
                if c != ':' && c != '*' {
                    // []byte for proper unicode char conversion, see #65
                    n.indices += string([]byte{c})
                    child := &node{
                        maxParams: numParams,
                    }
                    n.children = append(n.children, child)
                    n.incrementChildPrio(len(n.indices) - 1)
                    n = child
                }
                n.insertChild(numParams, path, fullPath, handle)
                return

            } else if i == len(path) { // Make node a (in-path) leaf
                if n.handle != nil {
                    panic("a handle is already registered for path '" + fullPath + "'")
                }
                n.handle = handle
            }
            return
        }
    } else { // Empty tree
        n.insertChild(numParams, path, fullPath, handle)
        n.nType = root
    }
}

接下來添加兩條路由:

func myHandler(writer http.ResponseWriter, request *http.Request, params httprouter.Params) {
    fmt.Fprintf(writer, request.URL.Path)
}

func startHTTPServer(addr string) {
    r := httprouter.New()
    r.GET("/home/first:name/sub/*information", myHandler)
    r.GET("/home/first:name/second", myHandler)
    r.GET("/house", myHandler)
    httprouter.DumpTree(r, "GET")
    http.ListenAndServe(addr, r)
}

添加/home/first:name/second之后的路由樹，可知在sub和second有公共部分s考廉，提取公共部分s成父節(jié)點秘豹，在該節(jié)點下添加兩個子節(jié)點(子節(jié)點path需要去掉公共部分)，示意圖如下：

添加/home/first:name/second后路由樹

添加/house后路由樹

3.3 getValue

getValue從路由樹中查找path對應(yīng)的handler:

// Returns the handle registered with the given path (key). The values of
// wildcards are saved to a map.
// If no handle can be found, a TSR (trailing slash redirect) recommendation is
// made if a handle exists with an extra (without the) trailing slash for the
// given path.
func (n *node) getValue(path string) (handle Handle, p Params, tsr bool) {
walk: // outer loop for walking the tree
    for {
        if len(path) > len(n.path) {
            if path[:len(n.path)] == n.path {
                path = path[len(n.path):]
                // If this node does not have a wildcard (param or catchAll)
                // child,  we can just look up the next child node and continue
                // to walk down the tree
                // 沿著路由樹往下遍歷怎炊，如果不存在通配符節(jié)點，則node的indices中查看
                // 能否繼續(xù)往下遍歷廓译，如果能則截取path剩余部門繼續(xù)下次循環(huán)评肆，直到匹配成功
                // 匹配成功則返回，不能匹配成功則判斷是否滿足重定向條件
                if !n.wildChild {
                    c := path[0]
                    for i := 0; i < len(n.indices); i++ {
                        if c == n.indices[i] {
                            n = n.children[i]
                            continue walk
                        }
                    }

                    // Nothing found.
                    // We can recommend to redirect to the same URL without a
                    // trailing slash if a leaf exists for that path.
                    tsr = (path == "/" && n.handle != nil)
                    return

                }

                // handle wildcard child
                // 有通配符則需要把通配符名稱作為key非区，真實值作為value保存到參數(shù)p中
                n = n.children[0]
                switch n.nType {
                case param:
                    // find param end (either '/' or path end)
                    end := 0
                    for end < len(path) && path[end] != '/' {
                        end++
                    }

                    // save param value
                    if p == nil {
                        // lazy allocation
                        p = make(Params, 0, n.maxParams)
                    }
                    i := len(p)
                    p = p[:i+1] // expand slice within preallocated capacity
                    // `:`通配符的路徑是:name這種形式瓜挽，所以必須跳過一個字符去取得名字
                    // 值則直接截取到下一個/或者到字符結(jié)尾
                    p[i].Key = n.path[1:]
                    p[i].Value = path[:end]

                    // we need to go deeper!
                    // 如果沒有處理完則要循環(huán)處理
                    if end < len(path) {
                        if len(n.children) > 0 {
                            path = path[end:]
                            n = n.children[0]
                            continue walk
                        }

                        // ... but we can't
                        tsr = (len(path) == end+1)
                        return
                    }

                    // 如果找不到則查看是否存在可重定向的路由
                    if handle = n.handle; handle != nil {
                        return
                    } else if len(n.children) == 1 {
                        // No handle found. Check if a handle for this path + a
                        // trailing slash exists for TSR recommendation
                        n = n.children[0]
                        tsr = (n.path == "/" && n.handle != nil)
                    }

                    return

                case catchAll:
                    // catchAll只能存在path的最后一個segment
                    // save param value
                    if p == nil {
                        // lazy allocation
                        p = make(Params, 0, n.maxParams)
                    }
                    i := len(p)
                    p = p[:i+1] // expand slice within preallocated capacity
                    // catchAll的形式是/*name，所以必須跳過兩個字符才能取到name字符
                    // value直接取到字符串最后就行
                    p[i].Key = n.path[2:]
                    p[i].Value = path

                    handle = n.handle
                    return

                default:
                    panic("invalid node type")
                }
            }
        } else if path == n.path {
            // We should have reached the node containing the handle.
            // Check if this node has a handle registered.
            if handle = n.handle; handle != nil {
                return
            }

            if path == "/" && n.wildChild && n.nType != root {
                tsr = true
                return
            }

            // No handle found. Check if a handle for this path + a
            // trailing slash exists for trailing slash recommendation
            for i := 0; i < len(n.indices); i++ {
                if n.indices[i] == '/' {
                    n = n.children[i]
                    tsr = (len(n.path) == 1 && n.handle != nil) ||
                        (n.nType == catchAll && n.children[0].handle != nil)
                    return
                }
            }

            return
        }

        // Nothing found. We can recommend to redirect to the same URL with an
        // extra trailing slash if a leaf exists for that path
        tsr = (path == "/") ||
            (len(n.path) == len(path)+1 && n.path[len(path)] == '/' &&
                path == n.path[:len(n.path)-1] && n.handle != nil)
        return
    }
}

函數(shù)比較長征绸，主要做了以下幾件事:

1. 沿著樹往下遍歷久橙，如果能匹配節(jié)點的path，則截取參數(shù)path的剩余部門繼續(xù)往下遍歷管怠，通過節(jié)點indices成員知道是否可以繼續(xù)往下遍歷
2. 通配符節(jié)點需要從path中截取真實的值淆衷，把通配符名字作為key，真實值作為value保存到返回參數(shù)p中
3. 如果最終匹配成功渤弛，則返回handler祝拯，匹配不成功則返回的tsr標識能否滿足重定向，true表示滿足重定向她肯，false表示不滿足

比如注冊了/home/佳头，但是http請求路徑是/home鹰贵，則getValue返回tsr為true，并且httproute自動給重定向到/home/

總結(jié):

1. httprouter為每一種http方法維護一棵路由樹康嘉，存在大量路由情況下能提供更好的匹配效率
2. httprouter空間利用率更高(不同保存相同前綴)
3. httprouter不是線程安全的(本質(zhì)上是addRoute(path, handler)不是線程安全的)