go語言中HTTPRouter的算法演進
更新時間：2023年08月07日 08:49:31 作者：洋芋編程
這篇文章主要從開發(fā)中常見的應用場景?“路由管理”?為例，為大家詳細介紹一下三種常用的實現(xiàn)方案背后的數(shù)據(jù)結(jié)構(gòu)和算法，感興趣的小伙伴可以了解一下
概述
本文從開發(fā)中常見的應用場景 “路由管理” 為例，介紹三種常用的實現(xiàn)方案背后的數(shù)據(jù)結(jié)構(gòu)和算法 (代碼實現(xiàn)為 Go 語言)。
應用示例
下面是一個典型的 REST 風格的 API 列表:
| Method | URL |
|---|---|
| GET | /users/list |
| GET | /users/dbwu |
| POST | /users |
| PUT | /users/dbwu |
| DELETE | /users/dbwu |
上面的 API 翻譯為 Go 代碼，大致如下 (忽略方法的具體實現(xiàn)):
package?main
import?(
?"log"
?"net/http"
)
func?main()?{
?http.HandleFunc("/users/list",?nil)
?http.HandleFunc("/users/dbwu",?nil)
?http.HandleFunc("/users",?nil)
?http.HandleFunc("/users/dbwu",?nil)
?http.HandleFunc("/users/dbwu",?nil)
?log.Fatal(http.ListenAndServe(":8080",?nil))
}標準庫方案
最簡單的方案就是直接使用 map[string]func() 作為路由的數(shù)據(jù)結(jié)構(gòu)，鍵為具體的路由，值為具體的處理方法。
標準庫中使用的就是這種方案，我們可以簡單追蹤一下對應的代碼:
//?路由管理數(shù)據(jù)結(jié)構(gòu)
type?ServeMux?struct?{
?mu????sync.RWMutex??????????//?對象操作讀寫鎖
?m?????map[string]muxEntry???//?存儲路由映射關(guān)系
}方法從 http.HandleFunc 方法開始追蹤:
//?注冊路由處理方法
func?HandleFunc(pattern?string,?handler?func(ResponseWriter,?*Request))?{
?DefaultServeMux.HandleFunc(pattern,?handler)
}
func?(mux?*ServeMux)?HandleFunc(pattern?string,?handler?func(ResponseWriter,?*Request))?{
?mux.Handle(pattern,?HandlerFunc(handler))
}
func?(mux?*ServeMux)?Handle(pattern?string,?handler?Handler)?{
?mux.mu.Lock()
?defer?mux.mu.Unlock()
?...
?if?_,?exist?:=?mux.m[pattern];?exist?{
??//?如果注冊的?URL?重復了，拋出?panic
??panic("http:?multiple?registrations?for?"?+?pattern)
?}
?if?mux.m?==?nil?{
??//?惰性初始化
??mux.m?=?make(map[string]muxEntry)
?}
?//?注冊完成
?e?:=?muxEntry{h:?handler,?pattern:?pattern}
?mux.m[pattern]?=?e
?...
}優(yōu)點和不足
使用 map[string]func() 作為路由的數(shù)據(jù)結(jié)構(gòu)，最明顯的優(yōu)點就是:
- 實現(xiàn)簡單: map 是標準庫內(nèi)置的數(shù)據(jù)結(jié)構(gòu)，可以直接使用并且代碼可讀性高
- 性能較高: 因為路由寫入操作只會發(fā)生一次 (注冊時)，后續(xù)的操作全部是讀取操作，基于標準庫的 map 性能已經(jīng)足夠優(yōu)秀
同時，該方案的不足也是顯而易見的:
- 內(nèi)存浪費: 即使存在很多前綴相同的路徑 (例如 /users, /users/list, /users/dbwu, 三個路徑的前綴都是 /users, 這部分是可以復用的)，map 結(jié)構(gòu)還是會每個路徑單獨映射，浪費大量的內(nèi)存
- 不夠靈活: 難以處理動態(tài)路由和正則表達式匹配等復雜的路徑 (例如 /users/:id 或 /users/{id:[0-9]+})
- 無法處理重復路徑：如果多個處理方法綁定到相同的路徑上 (例如 GET /users 和 POST /users)，map 只能存儲一個鍵值對，也就是只有最后一個注冊的處理函數(shù)會被調(diào)用
- 不支持中間件：map 結(jié)構(gòu)不支持中間件，這在現(xiàn)代 Web 開發(fā)中幾乎是不可接受的
基于以上特點，在真實的項目開發(fā)中不會使用 map[string]func() 作為路由的實現(xiàn)數(shù)據(jù)結(jié)構(gòu)。
Trie Tree
Trie Tree 也稱為字典樹或前綴樹，是一種用于高效存儲和檢索、用于從某個集合中查到某個特定 key 的數(shù)據(jù)結(jié)構(gòu)。 這些 key 通常是字符串，節(jié)點之間的父子關(guān)系不是由整個 key 定義，而是由 key 中的單個字符定義。 對某個 key 對應的元素進行相關(guān)操作 (寫入、更新、刪除) 就是一次 DFS (深度優(yōu)先遍歷) 過程。
算法復雜度
N: 字符串的數(shù)量
M: 字符串的平均長度
L: 字符串的長度
| 空間復雜度 |
|---|
| O(NM) |
| 操作 | 時間復雜度 |
|---|---|
| 插入 | O(L) |
| 查找 | O(L) |
| 刪除 | O(L) |
Trie Tree 的核心思想是空間換時間，利用字符串的公共前綴來減少字符比較操作，提升查詢效率。
圖示
圖片來源: https://theoryofprogramming.wordpress.com/2015/01/16/trie-tree-implementation/
如圖所示，是一個典型的 Trie Tree, 其中包含了如下元素:
"their",?"there",?"this",?"that",?"does",?"did"
本文不再描述算法的具體操作過程了，讀者可以通過代碼來感受一下，如果希望抓住細節(jié)，可以閱讀維基百科的介紹， 或者通過 這個可視化在線工具[1] 來手動操作體驗。
實現(xiàn)代碼
首先寫一個基礎(chǔ)版的 Trie Tree 代碼，對算法本身做一個初步認識。
package?trie
//?Trie?Tree?節(jié)點
type?Trie?struct?{
?//?標記當前節(jié)點是否為有效的路由
?//?例如添加了路由?/users
?//?那么?/user,?/usr?不能算作有效的路由
?//?也就是只有字符?"s"?節(jié)點的?IsPath?字段為?true
?IsPath?bool
?//?當前節(jié)點的子節(jié)點
?Children?map[byte]*Trie
}
func?New()?Trie?{
?return?Trie{false,?make(map[byte]*Trie)}
}
//?Add?添加一個路由到?Trie?Tree
func?(t?*Trie)?Add(path?string)?{
?parent?:=?t
?//?逐個?byte?加入到?Trie?Tree
?for?i?:=?range?path?{
??if?child,?ok?:=?parent.Children[path[i]];?ok?{
???//?如果子節(jié)點不為空，繼續(xù)向下遍歷
???parent?=?child
??}?else?{
???//?如果子節(jié)點為空，構(gòu)造新的節(jié)點
???newChild?:=?&Trie{false,?make(map[byte]*Trie)}
???parent.Children[path[i]]?=?newChild
???parent?=?newChild
??}
?}
?//?更新當前路由的葉子節(jié)點的?IsPath?字段
?parent.IsPath?=?true
}
//?Find?返回指定路由是否存在于?Trie?Tree?中
func?(t?*Trie)?Find(path?string)?bool?{
?parent?:=?t
?for?i?:=?range?path?{
??if?child,?ok?:=?parent.Children[path[i]];?ok?{
???parent?=?child
??}?else?{
???return?false
??}
?}
?return?parent.IsPath
}然后對上面的實現(xiàn)代碼做一個簡單的小測試:
package?trie
import?"testing"
func?TestTrie(t?*testing.T)?{
?trieTree?:=?New()
?if?got?:=?trieTree.Find("hello");?got?!=?false?{
??t.Errorf("Get()?=?%v,?want?%v",?got,?false)
?}
?trieTree.Add("hello")
?if?got?:=?trieTree.Find("hello");?got?!=?true?{
??t.Errorf("Get()?=?%v,?want?%v",?got,?true)
?}
?if?got?:=?trieTree.Find("he");?got?!=?false?{
??t.Errorf("Get()?=?%v,?want?%v",?got,?false)
?}
?trieTree.Add("he")
?if?got?:=?trieTree.Find("he");?got?!=?true?{
??t.Errorf("Get()?=?%v,?want?%v",?got,?true)
?}
}實現(xiàn)路由管理
現(xiàn)在，我們將剛才的 “算法部分” 代碼配合標準庫提供的 API 代碼，完成一個基礎(chǔ)版的路由管理功能。
package?main
import?(
?"fmt"
?"log"
?"net/http"
)
//?Router?節(jié)點
type?Router?struct?{
?Path???string
?Method?string
?//?標記當前節(jié)點是否為有效的路由
?//?例如添加了路由?/users
?//?那么?/user,?/usr?不能算作有效的路由
?//?也就是只有字符?"s"?節(jié)點的?IsPath?字段為?true
?IsPath?bool
?//?當前節(jié)點的子節(jié)點
?Children?map[byte]*Router
?//?路由處理方法
?Handler?http.HandlerFunc
}
func?NewRouter()?*Router?{
?return?&Router{IsPath:?false,?Children:?make(map[byte]*Router)}
}
//?Add?添加一個路由到?Router
func?(r?*Router)?Add(method,?path?string,?handler?http.HandlerFunc)?{
?parent?:=?r
?//?逐個?byte?加入到?Router?Tree
?for?i?:=?range?path?{
??if?child,?ok?:=?parent.Children[path[i]];?ok?{
???//?如果子節(jié)點不為空，繼續(xù)向下遍歷
???parent?=?child
??}?else?{
???//?如果子節(jié)點為空，構(gòu)造新的節(jié)點
???newChild?:=?NewRouter()
???parent.Children[path[i]]?=?newChild
???parent?=?newChild
??}
?}
?parent.Method?=?method
?parent.Handler?=?handler
?//?更新當前路由的葉子節(jié)點的?IsPath?字段
?parent.IsPath?=?true
}
//?Find?返回指定路由是否存在于?Router?中
func?(r?*Router)?Find(method,?path?string)?(http.HandlerFunc,?bool)?{
?parent?:=?r
?for?i?:=?range?path?{
??if?child,?ok?:=?parent.Children[path[i]];?ok?{
???parent?=?child
??}?else?{
???return?nil,?false
??}
?}
?return?parent.Handler,?parent.IsPath?&&?parent.Method?==?method
}
//?實現(xiàn)?http.Handler?接口
func?(r?*Router)?ServeHTTP(w?http.ResponseWriter,?req?*http.Request)?{
?handler,?ok?:=?r.Find(req.Method,?req.URL.Path)
?if?ok?{
??handler(w,?req)
?}?else?{
??http.NotFound(w,?req)
?}
}
//?處理所有路由的方法
//?輸出請求?Method?和?URL
func?allHandler(w?http.ResponseWriter,?req?*http.Request)?{
?_,?_?=?fmt.Fprintln(w,?req.Method,?req.URL)
}
func?main()?{
?r?:=?NewRouter()
?r.Add("GET",?"/hello",?allHandler)
?r.Add("GET",?"/users/list",?allHandler)
?log.Fatal(http.ListenAndServe(":8080",?r))
}為了節(jié)省篇幅，這里就不寫測試代碼了，下面進行幾個簡單的測試:
#?啟動服務(wù) $?go?run?main.go #?測試兩個正常的?URL $?curl?127.0.0.1:8080/hello #?輸出如下 GET?/hello $?curl?127.0.0.1:8080/users/list #?輸出如下 GET?/users/list #?測試兩個不存在的?URL $?curl?127.0.0.1:8080 #?輸出如下 404?page?not?found $?curl?127.0.0.1:8080/users/123456 #?輸出如下 404?page?not?found
優(yōu)點
Trie Tree 時間復雜度低，和一般的樹形數(shù)據(jù)結(jié)構(gòu)相比，Trie Tree 擁有更快的前綴搜索和查詢性能，和查詢時間復雜度為 O(1) 常數(shù)的哈希算法相比， Trie Tree 支持前綴搜索，并且可以節(jié)省哈希函數(shù)的計算開銷和避免哈希值碰撞的情況，最后，Trie Tree 還支持對關(guān)鍵字進行字典排序。
適用場景
排序 : 一組字符串 key 的字典排序，可以通過為給定 key 構(gòu)建一個 Trie Tree， 然后通過前序方式遍歷樹來實現(xiàn), burstsort 是 2007 年最快的字符串排序算法，其基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)就是 Trie Tree
全文索引: 通過一種特殊的 Trie Tree 實現(xiàn)，一般稱為后綴樹，可用于索引文本中的所有后綴以執(zhí)行快速全文搜索
搜索引擎: 當你在搜索引擎的輸入框中輸入關(guān)鍵字時，自動補全的提示信息
生物信息: 基因序列對比軟件
路由管理: 網(wǎng)絡(luò) IP 路由表，Web 中的 HTTP Router 管理
不適用場景
字符串公共前綴太少，造成 Trie Tree 節(jié)點稀疏分布，這時哈希表是更好的選擇
節(jié)點之間的父子節(jié)點使用指針連接，對 CPU 和自帶 GC 語言不太友好
字符集過大會造成過多的存儲空間占用 (Trie Tree 是空間換時間)
字符串過長會使 Trie Tree 深度變大，這時應該使用接下來講到的 Radix Tree
Radix Tree
Radix Tree（基數(shù)樹）是一種特殊的數(shù)據(jù)結(jié)構(gòu)，用于高效地存儲和搜索字符串鍵值對，它是一種基于前綴的樹狀結(jié)構(gòu)，通過將相同前綴的鍵值對合并在一起來減少存儲空間的使用。 Radix Tree 的關(guān)鍵思想是利用公共前綴來合并節(jié)點，每個節(jié)點代表一個字符，從根節(jié)點到葉子節(jié)點的路徑即為一個字符串鍵，每個節(jié)點上存儲著一個字符串的部分子串，并且每個節(jié)點可以代表多個鍵值對。
算法復雜度
N: 字符串的數(shù)量
M: 字符串的平均長度
L: 字符串的長度
| 空間復雜度 |
|---|
| O(NM) |
注意: Radix Tree 的使用場景是樹中有較多節(jié)點擁有相同前綴，所以即使和 Trie Tree 的空間復雜度一樣，但是實際應用中，Radix Tree 通過壓縮公共前綴， 空間使用要比 Trie Tree 節(jié)省很多。
| 操作 | 時間復雜度 |
|---|---|
| 插入 | O(L) |
| 查找 | O(L) |
| 刪除 | O(L) |
操作示例
下面引用維基百科頁面上的示例圖來說明 Radix Tree 的操作過程。
初始狀態(tài)下，樹中包含兩個節(jié)點，分別是字符串 test 和 slow。
1. 將字符串 water 插入到樹中
因為字符串 water 和已有的兩個節(jié)點沒有公共前綴，所以直接插入到新的節(jié)點中。
2. 將字符串 slower 插入到樹中
字符串 slower 和已有的節(jié)點 slow 存在公共前綴 slow, 所以放在 slow 節(jié)點下面。
3. 將字符串 tester 插入到樹中
字符串 tester 和已有的節(jié)點 test 存在公共前綴 test, 所以放在 test 節(jié)點下面。
4. 將字符串 team 插入到樹中
字符串 team 和已有的節(jié)點 test 存在公共前綴 te, 將 test 節(jié)點分裂為 st 和 am 兩個子節(jié)點，兩個子節(jié)點的父節(jié)點為 te。
5. 將字符串 toast 插入到樹中
字符串 toast 和已有的節(jié)點 te 存在公共前綴 t, 將 te 節(jié)點分裂為 e 和 oast 兩個子節(jié)點，兩個子節(jié)點的父節(jié)點為 t, 將 te 原來的兩個子節(jié)點放在 e 節(jié)點下面。
實現(xiàn)代碼
筆者選擇了開源的組件庫 httprouter[2] 來作為代碼實現(xiàn)的學習方案，選擇這個組件的主要原因有兩點：
- 該組件專注于路由管理，代碼量少且結(jié)構(gòu)簡單，涉及到 Radix Tree 數(shù)據(jù)結(jié)構(gòu)和算法的代碼已經(jīng)獨立到一個文件中，這可以大大降低我們閱讀源代碼的壓力和時間成本
- 很多 Web 框架中的路由管理功能都是基于該組件實現(xiàn)的，比如非常流行的 Gin
Web Frameworks based on HttpRouter
httprouter 提供的 API 非常簡潔，例如下面是一個簡單的 Demo :
package?main
import?(
????"net/http"
????"log"
????"github.com/julienschmidt/httprouter"
)
func?main()?{
????router?:=?httprouter.New()
????router.GET("/",?someHandle)
????router.GET("/hello/:name",?someHandle)
????log.Fatal(http.ListenAndServe(":8080",?router))
}接下來我們分為兩部分來學習 httprouter 組件的源代碼實現(xiàn):
- Radix Tree 數(shù)據(jù)結(jié)構(gòu)和算法的實現(xiàn)
- 基于 Radix Tree 的路由管理功能實現(xiàn)
httprouter UML
重要提示: 下文中的代碼和注釋內(nèi)容較多，讀者如果時間有限，可以快速瀏覽一下核心對象及方法和文末的總結(jié)，在需要了解細節(jié)時再回來閱讀。
Radix Tree 實現(xiàn)
工作原理簡述
路由管理功能中，底層的數(shù)據(jù)結(jié)構(gòu)是使用公共前綴的樹形結(jié)構(gòu)，也就是基數(shù)樹。在該數(shù)據(jù)結(jié)構(gòu)中，所有具有公共前綴的節(jié)點共享同一個父節(jié)點， 下面是一個關(guān)于這種數(shù)據(jù)結(jié)構(gòu)的示例 (請求方法為 GET)。
Priority Path Handle
9 \ *<1>
3 ├s nil
2 |├earch\ *<2>
1 |└upport\ *<3>
2 ├blog\ *<4>
1 | └:post nil
1 | └\ *<5>
2 ├about-us\ *<6>
1 | └team\ *<7>
1 └contact\ *<8>
對上面的結(jié)構(gòu)圖做一個簡單的說明:
- *<數(shù)字> 代表 Handler 方法指針
- search 節(jié)點和 support 節(jié)點擁有共同的父節(jié)點 s ，并且 s 沒有對應的 Handle， 只有葉子節(jié)點才有 Handler
- 從 root 節(jié)點開始，一直到葉子節(jié)點，算作一條路由的完整路徑
- 路徑搜索的順序是從上向下 -> 從左到右，為了快速找到盡可能多的路由，子節(jié)點越多的節(jié)點優(yōu)先級越高
將上面的結(jié)構(gòu)圖轉(zhuǎn)換代碼:
router.GET("/",?func1)
router.GET("/search/",?func2)
router.GET("/support/",?func3)
router.GET("/blog/:post/",?func5)
router.GET("/about-us/",?func6)
router.GET("/about-us/team/",?func7)
router.GET("/contact/",?func8)node 對象
node 對象表示 Radix Tree 的單個節(jié)點。
//?節(jié)點類型
type?nodeType?uint8
const?(
?static?nodeType?=?iota
?root????????//?根節(jié)點
?param???????//?參數(shù)節(jié)點?(例如?/users/:id)
?catchAll????//?通用節(jié)點，匹配任意參數(shù)?(例如?/users/*logs)
)
type?node?struct?{
?path??????string????//?路徑
?wildChild?bool??????//?是否為參數(shù)節(jié)點
?nType?????nodeType??//?節(jié)點類型
?maxParams?uint8?????//?路徑參數(shù)個數(shù)上限
?priority??uint32????//?優(yōu)先級
?indices???string????//?導致當前節(jié)點和其子節(jié)點分裂的首個字符?(wildChild?==?true?時,?indices?==?"")
?children??[]*node???//?子節(jié)點
?handle????Handle????//?路由處理方法
}添加路由
addRoute 方法將給定的路由處理方法綁定到具體的 Path 上面，該方法不是并發(fā)安全的，也就是需要通過加鎖等機制將操作串行化。
為了最大化提升讀者的閱讀體驗和效率，這里將代碼剖析注解直接貼在源代碼中。
func?(n?*node)?addRoute(path?string,?handle?Handle)?{
?fullPath?:=?path
?//?當前節(jié)點優(yōu)先級?+?1
?n.priority++
?//?計算路徑中的參數(shù)個數(shù)
?numParams?:=?countParams(path)
?//?non-empty?tree
?if?len(n.path)?>?0?||?len(n.children)?>?0?{
??//?說明當前?Radix?Tree?已經(jīng)存在節(jié)點了
??//?接下來進入?walk?循環(huán)標簽
?walk:
??for?{
???//?更新當前節(jié)點最大參數(shù)個數(shù)
???if?numParams?>?n.maxParams?{
????n.maxParams?=?numParams
???}
???//?查找當前節(jié)點路徑和參數(shù)路徑的最長公共前綴
???//?公共前綴中不能包含?':'??'*'?通配符?(因為這樣就無法區(qū)分具體的路徑了)
???//?PS:?查找最長公共前綴應該獨立為一個函數(shù)，提高代碼可讀性，編譯器會自動內(nèi)聯(lián)優(yōu)化
???//?????Gin?框架中已經(jīng)獨立為一個函數(shù)?longestCommonPrefix
???//?????https://github.com/gin-gonic/gin/blob/d4a64265f21993368c90602c18e778bf04ef36db/tree.go#L75C6-L75C6
???i?:=?0
???max?:=?min(len(path),?len(n.path))
???for?i?<?max?&&?path[i]?==?n.path[i]?{
????i++
???}
???//?如果最長公共前綴長度小于當前節(jié)點路徑長度
???//?這意味著可能是下列兩種情況之一?:
???//????1.?最長公共前綴?>?0,?例如當前節(jié)點路徑為?/users,?參數(shù)路徑為?/usr
???//????2.?最長公共前綴?==?0,?例如當前節(jié)點路徑為?/users,?參數(shù)路徑為?/books
???//?此時當前節(jié)點就需要分裂成兩個節(jié)點
???if?i?<?len(n.path)?{
????//?將當前節(jié)點路徑中非?“公共前綴”?部分獨立到一個新的子節(jié)點中
????child?:=?node{
?????//?路徑為當前節(jié)點路徑中非?“公共前綴”?部分
?????path:??????n.path[i:],
?????//?類型待定,?沒有?handler
?????nType:?????static,
?????indices:???n.indices,
????????????????????children:??n.children,
????????????????????handle:????n.handle,
?????//?優(yōu)先級?-?1
?????priority:??n.priority?-?1,
????}
????//?遍歷新的子節(jié)點的所有子節(jié)點?(也就是當前節(jié)點的所有子節(jié)點)
????//?更新當前節(jié)點最大參數(shù)個數(shù)
????for?i?:=?range?child.children?{
?????if?child.children[i].maxParams?>?child.maxParams?{
??????child.maxParams?=?child.children[i].maxParams
?????}
????}
????//?將新節(jié)點作為當前節(jié)點的子節(jié)點?(當前節(jié)點之前的子節(jié)點已經(jīng)被掛載到了新節(jié)點的子節(jié)點上面)
????n.children?=?[]*node{&child}
????//?獲取導致當前節(jié)點和其子節(jié)點分裂的首個字符，并更新?indices?字段
????//?(例如?/users/dbwu?和?/users/dbwt,?更新?indices?字段為?"u")
????n.indices?=?string([]byte{n.path[i]})
????//?更新當前節(jié)點的路徑為公共前綴
????n.path?=?path[:i]
????//?刪除當前節(jié)點的路由處理方法
????n.handle?=?nil
????//?刪除當前節(jié)點的參數(shù)節(jié)點標志
????n.wildChild?=?false
???}
???//?如果最長公共前綴長度小于參數(shù)路徑長度
???//?為什么這樣判斷呢？
???//????因為如果最長公共前綴長度大于等于參數(shù)路徑長度
???//????說明參數(shù)路徑本身就是公共前綴的一部分，就沒必要插入這個新節(jié)點了
???//?將新節(jié)點插入到當前節(jié)點的子節(jié)點
???if?i?<?len(path)?{
????//?刪除公共前綴部分，剩余部分的?path?是子節(jié)點的路徑
????path?=?path[i:]
????//?如果當前節(jié)點是參數(shù)節(jié)點?(例如?/users/:id)
????if?n.wildChild?{
?????//?代碼執(zhí)行到這里說明:?最長公共前綴長度大于等于當前節(jié)點路徑長度
?????//?也就是說:?參數(shù)路徑的長度要大于當前節(jié)點路徑長度
?????//?(例如?當前節(jié)點路徑為?/users/:id,?參數(shù)路徑為?/users/:id/profile)
?????//?獲取到當前節(jié)點的第一個子節(jié)點
?????n?=?n.children[0]
?????//?當前節(jié)點要插入一個新節(jié)點，優(yōu)先級?+?1
?????n.priority++
?????//?更新當前節(jié)點最大參數(shù)個數(shù)
?????if?numParams?>?n.maxParams?{
??????n.maxParams?=?numParams
?????}
?????numParams--
?????//?檢測通配符模式是否匹配
?????if?len(path)?>=?len(n.path)?&&?n.path?==?path[:len(n.path)]?&&
??????n.nType?!=?catchAll?&&
??????//?檢測更長的通配符匹配
??????//?(例如當前節(jié)點的?path?=?name,?子節(jié)點的路徑是?path?=?names)
??????(len(n.path)?>=?len(path)?||?path[len(n.path)]?==?'/')?{
??????//?如果通配符模式匹配，進入下一次循環(huán)
??????continue?walk
?????}?else?{
??????//?通配符發(fā)生了沖突
??????//?(例如當前節(jié)點的?path?=?/users/:id/profile,?子節(jié)點的路徑是?path?=?/users/:name/profile)
??????var?pathSeg?string
??????//?如果當前節(jié)點類型是通用節(jié)點?(通配符類型)
??????if?n.nType?==?catchAll?{
???????pathSeg?=?path
??????}?else?{
???????//?如果當前節(jié)點類型不是通用節(jié)點
???????//?將?path?字符串進行分割
???????//?(例如?path?=?/users/:id/profile,?分割之后?pathSeg?=?profile)
???????pathSeg?=?strings.SplitN(path,?"/",?2)[0]
??????}
??????//?提取出參數(shù)?path?的前綴
??????//?(例如?fullPath?=?/users/:id/profile,?當前節(jié)點?path?=?:id,?prefix?=?/user/:id)
??????prefix?:=?fullPath[:strings.Index(fullPath,?pathSeg)]?+?n.path
??????//?直接拋出一個?panic
??????//?信息中會輸出產(chǎn)生沖突的具體通配符?path
??????panic("'"?+?pathSeg?+
???????"'?in?new?path?'"?+?fullPath?+
???????"'?conflicts?with?existing?wildcard?'"?+?n.path?+
???????"'?in?existing?prefix?'"?+?prefix?+
???????"'")
?????}
????}
????c?:=?path[0]
????//?如果當前節(jié)點是一個參數(shù)節(jié)點并且只有一個子節(jié)點?并且參數(shù)?path?是以?"/"?開頭的
????//?(例如當前節(jié)點?path?=?/:name/profile,?參數(shù)?path?=?/:name/setting)
????if?n.nType?==?param?&&?c?==?'/'?&&?len(n.children)?==?1?{
?????//?將當前節(jié)點修改為其第一個子節(jié)點
?????n?=?n.children[0]
?????//?優(yōu)先級?+?1
?????n.priority++
?????//?進入下一次循環(huán)
?????continue?walk
????}
????//?檢測新增子節(jié)點的?path?的首字母是否存在于當前節(jié)點的?indices?字段中
????for?i?:=?0;?i?<?len(n.indices);?i++?{
?????if?c?==?n.indices[i]?{
??????//?更新子節(jié)點的優(yōu)先級
??????i?=?n.incrementChildPrio(i)
??????//?更新當前節(jié)點為對應的子節(jié)點
??????//??(
??????//????例如當前節(jié)點?path?=?p,?包含兩個子節(jié)點?rofile,?assword)
??????//????此時?indices?字段就包含字符?r?和?a,?正好和兩個子節(jié)點相對應
??????//????新增子節(jié)點的?path?=?projects,?刪除和當前節(jié)點的公共前綴符?p?后，變成了?rojects
??????//????然后當前節(jié)點會被更新為?rofile?子節(jié)點
??????//????最后，跳轉(zhuǎn)到下一次循環(huán)，然后拿?rofile?和?rojects?進行對比
??????//??)
??????n?=?n.children[i]
??????//?進入下一次循環(huán)
??????continue?walk
?????}
????}
????//?如果上面的條件都不滿足
????//?直接將新的子節(jié)點插入
????if?c?!=?':'?&&?c?!=?'*'?{
?????//?如果參數(shù)?path?的第一個字符不是通配符
?????//?將第一個字符追加到當前節(jié)點的?indices?字段
?????n.indices?+=?string([]byte{c})
?????//?初始化一個新的子節(jié)點
?????child?:=?&node{
??????maxParams:?numParams,
?????}
?????//?將新的子節(jié)點追加到當前節(jié)點的子節(jié)點列表中
?????n.children?=?append(n.children,?child)
??????????//?更新子節(jié)點的優(yōu)先級
?????n.incrementChildPrio(len(n.indices)?-?1)
?????//?更新當前節(jié)點為新增的子節(jié)點
?????n?=?child
????}
????n.insertChild(numParams,?path,?fullPath,?handle)
????return
???}?else?if?i?==?len(path)?{
????//?如果公共前綴和參數(shù)?path?長度相同
????//?說明參數(shù)?path?本身就是當前節(jié)點?path?的一部分
????if?n.handle?!=?nil?{
?????//?如果當前節(jié)點已經(jīng)注冊了路由處理方法
?????//?那么再次注冊時等于重復注冊
?????//?直接拋出?panic
?????panic("a?handle?is?already?registered?for?path?'"?+?fullPath?+?"'")
????}
????//?如果當前節(jié)點沒有注冊路由處理方法
????//?說明當前節(jié)點是作為其子節(jié)點的公共前綴符而存在的
????//?(例如?當前節(jié)點?path?=?p,?包含兩個子節(jié)點?rofile,?assword))
????n.handle?=?handle
???}
???return
??}
?}?else?{
??//?如果當前節(jié)點是一個空節(jié)點
??//?說明當前?Radix?Tree?沒有任何節(jié)點
??//?直接插入一個新節(jié)點
??//?并且將插入的新節(jié)點類型標記為?root
??//?PS:?筆者認為這兩行邊界檢測代碼應該放在函數(shù)開頭部分，提高可讀性
??n.insertChild(numParams,?path,?fullPath,?handle)
??n.nType?=?root
?}
}incrementChildPrio 方法用于更新給定子節(jié)點的優(yōu)先級，并在必要的時候進行排序。
func?(n?*node)?incrementChildPrio(pos?int)?int?{
?//?將對應索引的子節(jié)點的優(yōu)先級?+?1
?n.children[pos].priority++
?prio?:=?n.children[pos].priority
????//?向前移動位置
?//?(例如原本的子節(jié)點順序為?[a,?b,?c,?d],?此時傳入?yún)?shù)?2,?移動之后的子節(jié)點順序為?[c,?a,?b,?d])
?newPos?:=?pos
?for?newPos?>?0?&&?n.children[newPos-1].priority?<?prio?{
??n.children[newPos-1],?n.children[newPos]?=?n.children[newPos],?n.children[newPos-1]
??newPos--
?}
?//?更新當前節(jié)點的?indices?字段信息
?//?(例如原本的?indices?字段為?abcd,?此時傳入?yún)?shù)?2,?移動之后的?indices?字段為?cabd
?if?newPos?!=?pos?{
??n.indices?=?n.indices[:newPos]?+?//?unchanged?prefix,?might?be?empty
???n.indices[pos:pos+1]?+?//?the?index?char?we?move
???n.indices[newPos:pos]?+?n.indices[pos+1:]?//?rest?without?char?at?'pos'
?}
?//?返回移動后的新的位置
?return?newPos
}insertChild 方法負責執(zhí)行將具體的 path 插入到節(jié)點中。
func?(n?*node)?insertChild(numParams?uint8,?path,?fullPath?string,?handle?Handle)?{
?//?參數(shù)?path?已經(jīng)處理完的計算數(shù)量
?var?offset?int
?//?查找前綴直到第一個參數(shù)匹配或者通配符?(以?':'?或?'*'?開頭)
?//?參數(shù)匹配?(類似這種形式?:name)
?//?通配符?(類似這種形式?*logs)
?//?為了便于描述，下文中統(tǒng)一將?參數(shù)匹配符號?和?通配符號?統(tǒng)稱為?Token
?for?i,?max?:=?0,?len(path);?numParams?>?0;?i++?{
??c?:=?path[i]
??if?c?!=?':'?&&?c?!=?'*'?{
???//?如果不是?':'?或?'*',?直接跳過
???continue
??}
??//?查找當前?Token?結(jié)束符,?也就是下一個?'/'
??//?(例如?Token?為?/:name/profile,?查找的就是?:name?后面的?/?符號)
??end?:=?i?+?1
??for?end?<?max?&&?path[end]?!=?'/'?{
???switch?path[end]?{
???//?如果?Token?中嵌套?Token，直接?panic
????????????//?(例如?/:name:id)
???case?':',?'*':
????panic("only?one?wildcard?per?path?segment?is?allowed,?has:?'"?+
?????path[i:]?+?"'?in?path?'"?+?fullPath?+?"'")
???default:
????end++
???}
??}
??//?如果?Token?所在的索引位置已經(jīng)有節(jié)點了，直接?panic
??//?(例如已經(jīng)存在了節(jié)點?path?=?/users/dbwu,?就不能再定義?path?=?/user/:name)
??if?len(n.children)?>?0?{
???panic("wildcard?route?'"?+?path[i:end]?+
????"'?conflicts?with?existing?children?in?path?'"?+?fullPath?+?"'")
??}
??//?Token?至少需要一個字符表示的參數(shù)名稱,?否則直接?panic
??//?(例如?:name,?:id?中的?name?和?id?就是?Token?的參數(shù)名稱)
??if?end-i?<?2?{
???panic("wildcards?must?be?named?with?a?non-empty?name?in?path?'"?+?fullPath?+?"'")
??}
??//?如果?Token?的類型是參數(shù)匹配符
??if?c?==?':'?{
???//?將當前節(jié)點的位置更新為?從?offset?到當前索引位置之間的?path，
???if?i?>?0?{
????n.path?=?path[offset:i]
????//?更新?offset
????offset?=?i
???}
???//?根據(jù)參數(shù)初始化一個新的子節(jié)點
???child?:=?&node{
????nType:?????param,
????maxParams:?numParams,
???}
???//?更新當前節(jié)點的子節(jié)點
???n.children?=?[]*node{child}
???//?更新當前節(jié)點類型為參數(shù)節(jié)點
???n.wildChild?=?true
???//?當前節(jié)點下降為子節(jié)點，繼續(xù)后面的路由處理
???n?=?child
???//?當前節(jié)點優(yōu)先級?+?1
???n.priority++
???//?最大參數(shù)個數(shù)?-?1
???numParams--
???//?如果?Token?結(jié)束符比參數(shù)?path?長度要小
???//?說明參數(shù)?path?中還有子路徑
???if?end?<?max?{
????//?更新當前節(jié)點?path
????n.path?=?path[offset:end]
????//?更新?offset
????offset?=?end
????//?初始化一個新節(jié)點作為參數(shù)?path?中的子路徑節(jié)點
????child?:=?&node{
?????maxParams:?numParams,
?????priority:??1,
????}
????//?更新當前節(jié)點的子節(jié)點
????n.children?=?[]*node{child}
????//?當前節(jié)點下降為子節(jié)點，繼續(xù)后面的路由處理
????n?=?child
???}
??}?else?{?//?如果?Token?的類型是通配符
???if?end?!=?max?||?numParams?>?1?{
????//?通配符類型的路徑必須位于路由?path?的最后一部分，否則直接?panic
????//?(
????//???例如?/users/*name?是合法的，但是?/users/*name/profile?不是合法的，因為這樣就無法區(qū)分其他路由了
????//???例如?path?=?/users/dbwu/profile?是一個單獨的?path,?但是卻匹配了?/users/*name?這個?path
????//???因此獲取到的參數(shù)?name?=?"dbwu/profile"
????//???所以不會再將后面的?/dbwu/profile?作為單獨路徑來處理了
????//?)
????panic("catch-all?routes?are?only?allowed?at?the?end?of?the?path?in?path?'"?+?fullPath?+?"'")
???}
???if?len(n.path)?>?0?&&?n.path[len(n.path)-1]?==?'/'?{
????//?新定義的通配符和已有的通配符沖突了，直接?panic
????//?(例如一個已有的?path?=?/users/dbwu,?新定義的?path?=?/users/:name,?如果不終止，后者就會覆蓋前者)
????panic("catch-all?conflicts?with?existing?handle?for?the?path?segment?root?in?path?'"?+?fullPath?+?"'")
???}
???i--
???if?path[i]?!=?'/'?{
????//?如果通配符前面沒有?'/',?直接?panic
????panic("no?/?before?catch-all?in?path?'"?+?fullPath?+?"'")
???}
???n.path?=?path[offset:i]
???//?初始化一個新的子節(jié)點，類型為通配符節(jié)點
???child?:=?&node{
????wildChild:?true,
????nType:?????catchAll,
????maxParams:?1,
???}
???//?更新當前節(jié)點的最大參數(shù)個數(shù)
???if?n.maxParams?<?1?{
????n.maxParams?=?1
???}
???//?更新當前節(jié)點的子節(jié)點
???n.children?=?[]*node{child}
???//?更新當前節(jié)點的?indices?字段
???n.indices?=?string(path[i])
???//?當前節(jié)點下降為子節(jié)點，繼續(xù)后面的路由處理
???n?=?child
???//?當前節(jié)點優(yōu)先級?+?1
???n.priority++
???//?初始化一個新節(jié)點作為參數(shù)?path?中的剩余部分的節(jié)點
???child?=?&node{
????path:??????path[i:],
????nType:?????catchAll,
????maxParams:?1,
????handle:????handle,??//?綁定路由的處理函數(shù)
????priority:??1,
???}
???//?更新當前節(jié)點的子節(jié)點
???n.children?=?[]*node{child}
???//?通配符類型的路徑必須位于路由?path?的最后一部分
???//?直接返回即可
???return
??}
?}
?//?更新當前節(jié)點的?path
?n.path?=?path[offset:]
?//?更新當前節(jié)點的處理函數(shù)
?n.handle?=?handle
}查找路由處理方法
getValue 方法根據(jù)指定的 path，查找并返回對應的路由處理方法。
返回值列表順序如下:
- handle : path 對應的處理方法，如果沒有找到，返回 nil
- p : 如果 path 對應的節(jié)點類型是參數(shù)節(jié)點，會將參數(shù)返回
- tsr : 路由是否可以被重定向
func?(n?*node)?getValue(path?string)?(handle?Handle,?p?Params,?tsr?bool)?{
?//?循環(huán)標簽
walk:
?for?{
??//?如果要查找的?path?長度大于當前節(jié)點的?path?長度
??//?除了根路徑?/,?其他?path?應該都可以滿足這個條件
??if?len(path)?>?len(n.path)?{
???//?如果當前節(jié)點的?path?是要查找的?path?的前綴
???if?path[:len(n.path)]?==?n.path?{
????//?那么就將前綴去掉，查找剩余的部分
????path?=?path[len(n.path):]
????//?如果當前節(jié)點類型不是參數(shù)節(jié)點
????//?直接在其子節(jié)點中查找即可
????if?!n.wildChild?{
?????//?通過要查找?path?的首字母快速匹配對應的子節(jié)點
?????c?:=?path[0]
?????for?i?:=?0;?i?<?len(n.indices);?i++?{
??????if?c?==?n.indices[i]?{
???????//?更新當前節(jié)點
???????n?=?n.children[i]
???????//?跳轉(zhuǎn)到下一個循環(huán)
???????continue?walk
??????}
?????}
?????//?代碼執(zhí)行到這里，說明沒有匹配到子節(jié)點
?????//?如果路徑剩余的部分正好是?'/',?并且當前節(jié)點注冊了路由處理方法
?????//?更新?tsr?重定向標記為?true
?????//?(例如查找的?path?=?/users/,?當前節(jié)點?path?=?/users,?那么就重定向到?/users)
?????tsr?=?(path?==?"/"?&&?n.handle?!=?nil)
?????return
????}
????//?如果當前節(jié)點類型是參數(shù)節(jié)點或者通配符節(jié)點
????//?那么當前節(jié)點只會有一個子節(jié)點
????//?更新當前節(jié)點為其第一個子節(jié)點
????n?=?n.children[0]
????switch?n.nType?{
????//?如果當前節(jié)點類型是參數(shù)節(jié)點
????//?參數(shù)匹配?(類似這種形式?:name)
????case?param:
?????//?查找路徑中的參數(shù)結(jié)束符或者?'/'
?????end?:=?0
?????for?end?<?len(path)?&&?path[end]?!=?'/'?{
??????end++
?????}
?????if?p?==?nil?{
??????//?惰性初始化參數(shù)返回值
??????//?注意初始化的時候已經(jīng)指定了切片容量
??????p?=?make(Params,?0,?n.maxParams)
?????}
?????//?為參數(shù)返回值賦值
?????i?:=?len(p)
?????p?=?p[:i+1]
?????p[i].Key?=?n.path[1:]
?????p[i].Value?=?path[:end]
?????//?如果路徑還沒有匹配完，
?????if?end?<?len(path)?{
?????//?如果子節(jié)點下面還存在子節(jié)點
?????//?(例如?path?=?/users/:name/:setting,?當前匹配到?:name,?發(fā)現(xiàn)其還有子節(jié)點)
???? if?len(n.children)?>?0?{
???????//?更新查找路徑
???????path?=?path[end:]
???????//?更新當前節(jié)點為其第一個子節(jié)點
???????n?=?n.children[0]
???????//?跳轉(zhuǎn)到下一個循環(huán)
???????continue?walk
??????}
??????//?沒有查到到對應到路由處理函數(shù)
??????//?直接返回
??????tsr?=?(len(path)?==?end+1)
??????return
?????}
?????if?handle?=?n.handle;?handle?!=?nil?{
???? //?如果當前節(jié)點有對應到路由處理函數(shù)
?????//?直接返回
??????return
?????}?else?if?len(n.children)?==?1?{
??????//?如果當前節(jié)點沒有對應到路由處理函數(shù)
??????//?確認其子節(jié)點是否為?'/'?并且子節(jié)點有對應到路由處理函數(shù)
??????//?這樣就可以進行進行重定向了
??????n?=?n.children[0]
??????tsr?=?(n.path?==?"/"?&&?n.handle?!=?nil)
?????}
?????return
?????//?如果當前節(jié)點類型是通配符節(jié)點
????//?通配符?(類似這種形式?*logs)
????case?catchAll:
?????if?p?==?nil?{
??????//?惰性初始化參數(shù)返回值
??????//?注意初始化的時候已經(jīng)指定了切片容量
??????p?=?make(Params,?0,?n.maxParams)
?????}
?????//?通配符不會有子節(jié)點，直接賦值后返回即可
?????//?為參數(shù)返回值賦值
?????i?:=?len(p)
?????p?=?p[:i+1]
?????p[i].Key?=?n.path[2:]
?????p[i].Value?=?path
?????handle?=?n.handle
?????return
????default:
?????//?代碼執(zhí)行到這里
?????//?說明當前節(jié)點的類型不在枚舉范圍內(nèi)，直接?panic
?????panic("invalid?node?type")
????}
???}
??}?else?if?path?==?n.path?{
???//?如果要查找的?path?等于當前節(jié)點的?path
???//?檢測當前節(jié)點是否有路由處理函數(shù)，如果有的話，直接返回即可
???if?handle?=?n.handle;?handle?!=?nil?{
????return
???}
???//?如果要查找的?path?等于?/?并且當前節(jié)點類型不是?root,?并且當前節(jié)點是參數(shù)節(jié)點
???//?允許重定向
???if?path?==?"/"?&&?n.wildChild?&&?n.nType?!=?root?{
????tsr?=?true
????return
???}
???//?當前節(jié)點沒有路由處理函數(shù)，但是有一個子節(jié)點的路徑為?'/',?這時允許重定向
???//?(例如當前節(jié)點的?path?=?/users/,?但是查找的?path?=?/users,?此時就允許重定向到?/users/?上面)
???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
??}
??//?沒有查到到對應到路由處理函數(shù)
??//?根據(jù)條件更新是否允許重定向字段
??tsr?=?(path?==?"/")?||
???(len(n.path)?==?len(path)+1?&&?n.path[len(path)]?==?'/'?&&
????path?==?n.path[:len(n.path)-1]?&&?n.handle?!=?nil)
??return
?}
}路由管理實現(xiàn)
相比于上面 Radix Tree 的實現(xiàn)，路由管理功能實現(xiàn)要簡單的多，這里分析一下核心的代碼。
Router 對象
Router 對象表示全局的路由管理對象，可以將不同的 HTTP Method + Path 請求分發(fā)給不同的路由處理函數(shù)。
type?Router?struct?{
????//?路由管理的核心字段，每個?HTTP?Method?對應一個?Radix?Tree?結(jié)構(gòu)
????//?例如
????//???GET?=>?Radix?Tree
????//???POST?=>?Radix?Tree
????//???DELETE?=>?Radix?Tree
????//???...
???trees?map[string]*node
????//?是否啟用請求的自動重定向
????//?(例如當前請求為?/foo/,?但是路由管理注冊的路徑只有?/foo,?此時就將?/foo/?重定向到?/fooo)
????//?(重定向時，GET?請求的響應碼為?301，?其他請求的為?307)
???RedirectTrailingSlash?bool
????//?是否啟用自動修復路徑
????//?首先會刪除路徑中多余的部分，例如?../?和?//
????//?然后再次查找路徑?(這一次不區(qū)分大小寫)，看是否可以匹配到對應的路徑處理方法
????//?如果能匹配到路徑，就進行重定向
????//?(重定向時，GET?請求的響應碼為?301，?其他請求的為?307)
????RedirectFixedPath?bool
????//?是否啟用?Method?Not?Allowed
????//?啟用機制后，如果當前路徑?jīng)]有匹配到對應的路徑處理方法
????//???查看其他當前路徑是否注冊了其他?HTTP?請求類型的路徑處理方法
????//???如果注冊了，返回?405?狀態(tài)碼
????//?如果沒有開啟機制，當前路徑?jīng)]有匹配到對應的路徑處理方法
????//???返回?404?狀態(tài)碼
????HandleMethodNotAllowed?bool
???//?是否啟用?OPTIONS?請求響應
????HandleOPTIONS?bool
????//?404?響應方法
???//?如果沒有設(shè)置，就使用標準庫的?404?方法
????NotFound?http.Handler
????//?405?響應方法
????//?如果沒有設(shè)置，就使用標準庫的?Error?方法
????//???其中響應文本為?Method?Not?Allowed，狀態(tài)碼為?405
????MethodNotAllowed?http.Handler
????//?用于捕獲并處理?panic?錯誤的方法，返回錯誤碼?500?(Internal?Server?Error)
????//?保證程序因為沒有捕獲?panic?而崩潰退出
????PanicHandler?func(http.ResponseWriter,?*http.Request,?interface{})
}
//?通過編譯期間保證?Router?必須實現(xiàn)?http.Handler?接口
var?_?http.Handler?=?New()
//?創(chuàng)建并返回一個路由管理實例
func?New()?*Router?{
?return?&Router{
??RedirectTrailingSlash:??true,
??RedirectFixedPath:??????true,
??HandleMethodNotAllowed:?true,
??HandleOPTIONS:??????????true,
?}
}注冊路由處理方法
Router 提供了常見的 HTTP 請求路由處理方法注冊的 API, 每個方法的內(nèi)部都是調(diào)用了 Handle 方法，下面是 GET 方法和 POST 方法的實現(xiàn)代碼。
//?注冊?GET?請求處理方法
func?(r?*Router)?GET(path?string,?handle?Handle)?{
?r.Handle(http.MethodGet,?path,?handle)
}
//?注冊?POST?請求處理方法
func?(r?*Router)?POST(path?string,?handle?Handle)?{
????r.Handle(http.MethodPost,?path,?handle)
}
...Handle 方法將指定的 HTTP Method + Path 和路由處理方法進行綁定。
func?(r?*Router)?Handle(method,?path?string,?handle?Handle)?{
?if?len(path)?<?1?||?path[0]?!=?'/'?{
??//?如果路徑為空或者路徑第一個字符不等于?'/'
??//?這種路徑格式就是不合法的，直接?panic
??panic("path?must?begin?with?'/'?in?path?'"?+?path?+?"'")
?}
?if?r.trees?==?nil?{
??//?初始化?trees?字段
??r.trees?=?make(map[string]*node)
?}
?root?:=?r.trees[method]
?if?root?==?nil?{
??//?初始化參數(shù)?HTTP?方法對應的?Radix?Tree?結(jié)構(gòu)
??root?=?new(node)
??r.trees[method]?=?root
??r.globalAllowed?=?r.allowed("*",?"")
?}
?//?添加路由的注冊方法
?//?詳情見前文對于?addRoute?方法的注解
?root.addRoute(path,?handle)
}ServeHTTP 實現(xiàn)
ServeHTTP 方法負責處理 HTTP 請求并返回響應，同時實現(xiàn)了標準庫中的 http.Handler 接口。
//?net/http/server.go
type?Handler?interface?{
?ServeHTTP(ResponseWriter,?*Request)
}func?(r?*Router)?ServeHTTP(w?http.ResponseWriter,?req?*http.Request)?{
?if?r.PanicHandler?!=?nil?{
??//?將?panic?錯誤處理函數(shù)注冊到?defer?函數(shù)
??defer?r.recv(w,?req)
?}
?//?獲取當前請求路徑
?path?:=?req.URL.Path
?//?檢測當前請求方法是否存在對應的?Radix?Tree?結(jié)構(gòu)
?if?root?:=?r.trees[req.Method];?root?!=?nil?{
??if?handle,?ps,?tsr?:=?root.getValue(path);?handle?!=?nil?{
???//?如果當前請求路徑有對應的處理方法，直接調(diào)用即可
???handle(w,?req,?ps)
???return
??}?else?if?req.Method?!=?http.MethodConnect?&&?path?!=?"/"?{
???//?PS:?上面的?if?條件分支都已經(jīng)直接返回了
???//?????這里實在沒必要再寫一個?else?條件分支
???//?????整個庫的代碼，可讀性比較低?～
???//?如果當前請求路徑?jīng)]有對應的處理方法
???//?將響應狀態(tài)碼設(shè)置為?301?(永久重定向，針對?GET?方法)
???code?:=?301
???if?req.Method?!=?http.MethodGet?{
????//?如果當前請求不是?GET?方法
????//?將響應狀態(tài)碼設(shè)置為?307?(臨死重定向，針對非?GET?方法)
????//?為什么不使用?301?呢？
????//?因為?308?和?307?不允許請求從?POST?修改為?GET
????//?Temporary?redirect,?request?with?same?method
????//?As?of?Go?1.3,?Go?does?not?support?status?code?308.
????code?=?307
???}
???//?如果請求路徑需要重定向并且路由支持重定向
???if?tsr?&&?r.RedirectTrailingSlash?{
????//?如果路徑的長度大于?1?并且路徑是以?'/'?字符結(jié)尾的
????//?就將末尾的?'/'?字符刪除
????if?len(path)?>?1?&&?path[len(path)-1]?==?'/'?{
?????req.URL.Path?=?path[:len(path)-1]
????}?else?{
?????//?在路徑的結(jié)尾加一個?'/'?字符
?????req.URL.Path?=?path?+?"/"
????}
????//?返回重定向響應
????http.Redirect(w,?req,?req.URL.String(),?code)
????return
???}
???//?如果當前請求路徑?jīng)]有對應的處理方法?并且?也沒有符合規(guī)則的重定向條件
???//?嘗試修復請求路徑
???if?r.RedirectFixedPath?{
????//?去除路徑中的多余部分并返回經(jīng)過修正后是否有匹配的路徑
????fixedPath,?found?:=?root.findCaseInsensitivePath(
?????CleanPath(path),
?????r.RedirectTrailingSlash,
????)
????if?found?{
?????//?如果經(jīng)過修正，可以找到匹配的路徑
?????//?直接重定向
?????req.URL.Path?=?string(fixedPath)
?????http.Redirect(w,?req,?req.URL.String(),?code)
?????return
????}
???}
??}
?}
?//?代碼執(zhí)行到了這里
?//?說明上面的幾個條件都不符合，當前請求路徑還是沒有找到對應的處理方法
?if?req.Method?==?http.MethodOptions?&&?r.HandleOPTIONS?{
??//?如果請求方法是?OPTIONS,?并且路由管理允許響應?OPTIONS
??//?返回一個?OPTIONS?響應
??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?{
??//?如果請求方法不是?OPTIONS,?或者路由管理不允許響應?OPTIONS
??//?返回一個?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
??}
?}
?if?r.NotFound?!=?nil?{
??//?如果路由管理中注冊了?404?處理函數(shù)
??//?直接調(diào)用
??r.NotFound.ServeHTTP(w,?req)
?}?else?{
??//?如果路由管理中沒有注冊?404?處理方法
??//?調(diào)用標準庫中的?404?處理方法
??http.NotFound(w,?req)
?}
}優(yōu)點
Radix Tree 通過合并公共前綴來降低存儲空間的開銷，避免了 Trie Tree 字符串過長和字符集過大時導致的存儲空間過多問題，同時公共前綴優(yōu)化了路徑層數(shù)，提升了插入、查詢、刪除等操作效率。
適用場景
字典和前綴匹配 ：適合用作字典或關(guān)聯(lián)數(shù)組的底層數(shù)據(jù)結(jié)構(gòu)，可以快速找到以給定前綴開頭的所有鍵，例如 Redis 中的某個前綴 key
IP 路由表 ：可以高效地存儲和搜索 IP 地址及其對應的路由表信息
文件系統(tǒng)和目錄 ：每個節(jié)點可以表示一個目錄或文件，節(jié)點之間的關(guān)系通過共同的路徑前綴進行連接
編譯器 ：可以用于編譯器中的符號表管理，符號表存儲了程序中定義的變量、函數(shù)名和類型等信息，Radix Tree 可以快速查找和更新符號表項，支持高效的名稱解析和類型檢查
不適用場景
字符串公共前綴太少，造成 Radix Tree 節(jié)點稀疏分布 (退化到 Trie Tree)，這時哈希表是更好的選擇 (這個問題在 Trie Tree 中同樣存在)
字符集過小，可以直接使用其他簡單的數(shù)據(jù)結(jié)構(gòu)
動態(tài)數(shù)據(jù)集，也就是數(shù)據(jù)集需要頻繁地進行插入和刪除操作，由于 Radix Tree 的節(jié)點需要合并和路徑重組，動態(tài)修改樹結(jié)構(gòu)可能引起較大的開銷，在這種情況下，這時平衡二叉搜索樹結(jié)構(gòu)（AVL 樹、紅黑樹）更適合
節(jié)點之間的父子節(jié)點使用指針連接，對 CPU 和自帶 GC 語言不太友好 (這個問題在 Trie Tree 中同樣存在)
Trie Tree 對比 Radix Tree
下面是插入 4 個單詞 [PLAN, PLAY, POLL, POST] 后的結(jié)果 (粗體字符表示節(jié)點字符，圓圈內(nèi)字符串表示該節(jié)點表示的值)。
小結(jié)
本文從開發(fā)中常見的 “路由管理” 功能為出發(fā)點，探索了實現(xiàn)背后用到的數(shù)據(jù)結(jié)構(gòu)和算法，并先后分析了各解決方案的優(yōu)化過程，分別是 Go 標準庫、手動實現(xiàn) Trie Tree、開源的 Radix Tree, 希望讀者在讀完文章后，能準確地理解 Trie Tree 和 Radix Tree 的差異及其適用場景，如果在此基礎(chǔ)上還有興趣和時間，可以深入了解下由這兩種數(shù)據(jù)結(jié)構(gòu)演變出的其他數(shù)據(jù)結(jié)構(gòu)和算法。
到此這篇關(guān)于go語言中HTTPRouter的算法演進的文章就介紹到這了,更多相關(guān)go HTTPRouter內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
在日常開發(fā)中,我們可能會遇到需要延遲執(zhí)行或周期性地執(zhí)行一些任務(wù),這個時候就需要用到 Go 語言中的定時器,本文將會對這兩種定時器類型進行介紹,感興趣的朋友一起看看吧2024-07-07
Go本身不支持模板，因此在以往需要使用模板的場景下往往就需要使用反射(reflect). 反射使用多了以后會容易上癮，有些人甚至會形成一種莫名其妙的鄙視鏈。下面這篇文章就給大家介紹了如何正確使用Go語言中的反射以及在使用前的注意，有需要的朋友們下面來一起看看吧。2016-12-12
這篇文章主要為大家介紹了使用Go語言來解決Scan空格結(jié)束輸入問題，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步2021-11-11
最近有讀者留言說，平時在寫代碼的過程中，是會對字符串進行修改的，但網(wǎng)上都說 Go 語言字符串是不可變的，這是為什么呢，本文就來和大家簡單講講2023-05-05
go高并發(fā)時append方法偶現(xiàn)錯誤解決分析
這篇文章主要為大家介紹了go高并發(fā)時append方法偶現(xiàn)錯誤解決分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-10-10
golang中strconv.ParseInt函數(shù)用法示例
這篇文章主要介紹了golang中strconv.ParseInt函數(shù)用法,實例分析了strconv.ParseInt函數(shù)將字符串轉(zhuǎn)換為數(shù)字的簡單使用方法,需要的朋友可以參考下2016-07-07
這篇文章主要為大家介紹了詳解以go思想去處理js異常拋棄trycatch，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-03-03
go實現(xiàn)一個內(nèi)存緩存系統(tǒng)的示例代碼
本文主要介紹了go實現(xiàn)一個內(nèi)存緩存系統(tǒng)的示例代碼,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-10-10
這篇文章主要介紹了用go寫的五子棋預測算法的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-12-12
本文主要介紹了golang常見接口限流算法的實現(xiàn),包含固定窗口、滑動窗口、漏桶和令牌桶,具有一定的參考價值,感興趣的可以了解一下2025-03-03