go語(yǔ)言中HTTPRouter的算法演進(jìn)

更新時(shí)間：2023年08月07日 08:49:31 作者：洋芋編程

這篇文章主要從開發(fā)中常見的應(yīng)用場(chǎng)景?“路由管理”?為例，為大家詳細(xì)介紹一下三種常用的實(shí)現(xiàn)方案背后的數(shù)據(jù)結(jié)構(gòu)和算法，感興趣的小伙伴可以了解一下

概述

本文從開發(fā)中常見的應(yīng)用場(chǎng)景 “路由管理” 為例，介紹三種常用的實(shí)現(xiàn)方案背后的數(shù)據(jù)結(jié)構(gòu)和算法 (代碼實(shí)現(xiàn)為 Go 語(yǔ)言)。

應(yīng)用示例

下面是一個(gè)典型的 REST 風(fēng)格的 API 列表:

Method	URL
GET	/users/list
GET	/users/dbwu
POST	/users
PUT	/users/dbwu
DELETE	/users/dbwu

上面的 API 翻譯為 Go 代碼，大致如下 (忽略方法的具體實(shí)現(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))
}

標(biāo)準(zhǔn)庫(kù)方案

最簡(jiǎn)單的方案就是直接使用 map[string]func() 作為路由的數(shù)據(jù)結(jié)構(gòu)，鍵為具體的路由，值為具體的處理方法。

標(biāo)準(zhǔn)庫(kù)中使用的就是這種方案，我們可以簡(jiǎn)單追蹤一下對(duì)應(yīng)的代碼:

//?路由管理數(shù)據(jù)結(jié)構(gòu)
type?ServeMux?struct?{
?mu????sync.RWMutex??????????//?對(duì)象操作讀寫鎖
?m?????map[string]muxEntry???//?存儲(chǔ)路由映射關(guān)系
}

方法從 http.HandleFunc 方法開始追蹤:

//?注冊(cè)路由處理方法
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?{
??//?如果注冊(cè)的?URL?重復(fù)了，拋出?panic
??panic("http:?multiple?registrations?for?"?+?pattern)
?}
?if?mux.m?==?nil?{
??//?惰性初始化
??mux.m?=?make(map[string]muxEntry)
?}
?//?注冊(cè)完成
?e?:=?muxEntry{h:?handler,?pattern:?pattern}
?mux.m[pattern]?=?e
?...
}

優(yōu)點(diǎn)和不足

使用 map[string]func() 作為路由的數(shù)據(jù)結(jié)構(gòu)，最明顯的優(yōu)點(diǎn)就是:

實(shí)現(xiàn)簡(jiǎn)單: map 是標(biāo)準(zhǔn)庫(kù)內(nèi)置的數(shù)據(jù)結(jié)構(gòu)，可以直接使用并且代碼可讀性高
性能較高: 因?yàn)槁酚蓪懭氩僮髦粫?huì)發(fā)生一次 (注冊(cè)時(shí))，后續(xù)的操作全部是讀取操作，基于標(biāo)準(zhǔn)庫(kù)的 map 性能已經(jīng)足夠優(yōu)秀

同時(shí)，該方案的不足也是顯而易見的:

內(nèi)存浪費(fèi): 即使存在很多前綴相同的路徑 (例如 /users, /users/list, /users/dbwu, 三個(gè)路徑的前綴都是 /users, 這部分是可以復(fù)用的)，map 結(jié)構(gòu)還是會(huì)每個(gè)路徑單獨(dú)映射，浪費(fèi)大量的內(nèi)存
不夠靈活: 難以處理動(dòng)態(tài)路由和正則表達(dá)式匹配等復(fù)雜的路徑 (例如 /users/:id 或 /users/{id:[0-9]+})
無(wú)法處理重復(fù)路徑：如果多個(gè)處理方法綁定到相同的路徑上 (例如 GET /users 和 POST /users)，map 只能存儲(chǔ)一個(gè)鍵值對(duì)，也就是只有最后一個(gè)注冊(cè)的處理函數(shù)會(huì)被調(diào)用
不支持中間件：map 結(jié)構(gòu)不支持中間件，這在現(xiàn)代 Web 開發(fā)中幾乎是不可接受的

基于以上特點(diǎn)，在真實(shí)的項(xiàng)目開發(fā)中不會(huì)使用 map[string]func() 作為路由的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)。

Trie Tree

Trie Tree 也稱為字典樹或前綴樹，是一種用于高效存儲(chǔ)和檢索、用于從某個(gè)集合中查到某個(gè)特定 key 的數(shù)據(jù)結(jié)構(gòu)。這些 key 通常是字符串，節(jié)點(diǎn)之間的父子關(guān)系不是由整個(gè) key 定義，而是由 key 中的單個(gè)字符定義。對(duì)某個(gè) key 對(duì)應(yīng)的元素進(jìn)行相關(guān)操作 (寫入、更新、刪除) 就是一次 DFS (深度優(yōu)先遍歷) 過(guò)程。

算法復(fù)雜度

N: 字符串的數(shù)量

M: 字符串的平均長(zhǎng)度

L: 字符串的長(zhǎng)度

空間復(fù)雜度
O(NM)

操作	時(shí)間復(fù)雜度
插入	O(L)
查找	O(L)
刪除	O(L)

Trie Tree 的核心思想是空間換時(shí)間，利用字符串的公共前綴來(lái)減少字符比較操作，提升查詢效率。

圖示

圖片來(lái)源: https://theoryofprogramming.wordpress.com/2015/01/16/trie-tree-implementation/

如圖所示，是一個(gè)典型的 Trie Tree, 其中包含了如下元素:

"their",?"there",?"this",?"that",?"does",?"did"

本文不再描述算法的具體操作過(guò)程了，讀者可以通過(guò)代碼來(lái)感受一下，如果希望抓住細(xì)節(jié)，可以閱讀維基百科的介紹，或者通過(guò) 這個(gè)可視化在線工具[1] 來(lái)手動(dòng)操作體驗(yàn)。

實(shí)現(xiàn)代碼

首先寫一個(gè)基礎(chǔ)版的 Trie Tree 代碼，對(duì)算法本身做一個(gè)初步認(rèn)識(shí)。

package?trie
//?Trie?Tree?節(jié)點(diǎn)
type?Trie?struct?{
?//?標(biāo)記當(dāng)前節(jié)點(diǎn)是否為有效的路由
?//?例如添加了路由?/users
?//?那么?/user,?/usr?不能算作有效的路由
?//?也就是只有字符?"s"?節(jié)點(diǎn)的?IsPath?字段為?true
?IsPath?bool
?//?當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)
?Children?map[byte]*Trie
}
func?New()?Trie?{
?return?Trie{false,?make(map[byte]*Trie)}
}
//?Add?添加一個(gè)路由到?Trie?Tree
func?(t?*Trie)?Add(path?string)?{
?parent?:=?t
?//?逐個(gè)?byte?加入到?Trie?Tree
?for?i?:=?range?path?{
??if?child,?ok?:=?parent.Children[path[i]];?ok?{
???//?如果子節(jié)點(diǎn)不為空，繼續(xù)向下遍歷
???parent?=?child
??}?else?{
???//?如果子節(jié)點(diǎn)為空，構(gòu)造新的節(jié)點(diǎn)
???newChild?:=?&Trie{false,?make(map[byte]*Trie)}
???parent.Children[path[i]]?=?newChild
???parent?=?newChild
??}
?}
?//?更新當(dāng)前路由的葉子節(jié)點(diǎn)的?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
}

然后對(duì)上面的實(shí)現(xiàn)代碼做一個(gè)簡(jiǎn)單的小測(cè)試:

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)
?}
}

實(shí)現(xiàn)路由管理

現(xiàn)在，我們將剛才的 “算法部分” 代碼配合標(biāo)準(zhǔn)庫(kù)提供的 API 代碼，完成一個(gè)基礎(chǔ)版的路由管理功能。

package?main
import?(
?"fmt"
?"log"
?"net/http"
)
//?Router?節(jié)點(diǎn)
type?Router?struct?{
?Path???string
?Method?string
?//?標(biāo)記當(dāng)前節(jié)點(diǎn)是否為有效的路由
?//?例如添加了路由?/users
?//?那么?/user,?/usr?不能算作有效的路由
?//?也就是只有字符?"s"?節(jié)點(diǎn)的?IsPath?字段為?true
?IsPath?bool
?//?當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)
?Children?map[byte]*Router
?//?路由處理方法
?Handler?http.HandlerFunc
}
func?NewRouter()?*Router?{
?return?&Router{IsPath:?false,?Children:?make(map[byte]*Router)}
}
//?Add?添加一個(gè)路由到?Router
func?(r?*Router)?Add(method,?path?string,?handler?http.HandlerFunc)?{
?parent?:=?r
?//?逐個(gè)?byte?加入到?Router?Tree
?for?i?:=?range?path?{
??if?child,?ok?:=?parent.Children[path[i]];?ok?{
???//?如果子節(jié)點(diǎn)不為空，繼續(xù)向下遍歷
???parent?=?child
??}?else?{
???//?如果子節(jié)點(diǎn)為空，構(gòu)造新的節(jié)點(diǎn)
???newChild?:=?NewRouter()
???parent.Children[path[i]]?=?newChild
???parent?=?newChild
??}
?}
?parent.Method?=?method
?parent.Handler?=?handler
?//?更新當(dāng)前路由的葉子節(jié)點(diǎn)的?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
}
//?實(shí)現(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)
?}
}
//?處理所有路由的方法
//?輸出請(qǐng)求?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é)省篇幅，這里就不寫測(cè)試代碼了，下面進(jìn)行幾個(gè)簡(jiǎn)單的測(cè)試:

#?啟動(dòng)服務(wù)
$?go?run?main.go
#?測(cè)試兩個(gè)正常的?URL
$?curl?127.0.0.1:8080/hello
#?輸出如下
GET?/hello
$?curl?127.0.0.1:8080/users/list
#?輸出如下
GET?/users/list
#?測(cè)試兩個(gè)不存在的?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)點(diǎn)

Trie Tree 時(shí)間復(fù)雜度低，和一般的樹形數(shù)據(jù)結(jié)構(gòu)相比，Trie Tree 擁有更快的前綴搜索和查詢性能，和查詢時(shí)間復(fù)雜度為 O(1) 常數(shù)的哈希算法相比， Trie Tree 支持前綴搜索，并且可以節(jié)省哈希函數(shù)的計(jì)算開銷和避免哈希值碰撞的情況，最后，Trie Tree 還支持對(duì)關(guān)鍵字進(jìn)行字典排序。

適用場(chǎng)景

排序 : 一組字符串 key 的字典排序，可以通過(guò)為給定 key 構(gòu)建一個(gè) Trie Tree，然后通過(guò)前序方式遍歷樹來(lái)實(shí)現(xiàn), burstsort 是 2007 年最快的字符串排序算法，其基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)就是 Trie Tree

全文索引: 通過(guò)一種特殊的 Trie Tree 實(shí)現(xiàn)，一般稱為后綴樹，可用于索引文本中的所有后綴以執(zhí)行快速全文搜索

搜索引擎: 當(dāng)你在搜索引擎的輸入框中輸入關(guān)鍵字時(shí)，自動(dòng)補(bǔ)全的提示信息

生物信息: 基因序列對(duì)比軟件

路由管理: 網(wǎng)絡(luò) IP 路由表，Web 中的 HTTP Router 管理

不適用場(chǎng)景

字符串公共前綴太少，造成 Trie Tree 節(jié)點(diǎn)稀疏分布，這時(shí)哈希表是更好的選擇

節(jié)點(diǎn)之間的父子節(jié)點(diǎn)使用指針連接，對(duì) CPU 和自帶 GC 語(yǔ)言不太友好

字符集過(guò)大會(huì)造成過(guò)多的存儲(chǔ)空間占用 (Trie Tree 是空間換時(shí)間)

字符串過(guò)長(zhǎng)會(huì)使 Trie Tree 深度變大，這時(shí)應(yīng)該使用接下來(lái)講到的 Radix Tree

Radix Tree

Radix Tree（基數(shù)樹）是一種特殊的數(shù)據(jù)結(jié)構(gòu)，用于高效地存儲(chǔ)和搜索字符串鍵值對(duì)，它是一種基于前綴的樹狀結(jié)構(gòu)，通過(guò)將相同前綴的鍵值對(duì)合并在一起來(lái)減少存儲(chǔ)空間的使用。 Radix Tree 的關(guān)鍵思想是利用公共前綴來(lái)合并節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)代表一個(gè)字符，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑即為一個(gè)字符串鍵，每個(gè)節(jié)點(diǎn)上存儲(chǔ)著一個(gè)字符串的部分子串，并且每個(gè)節(jié)點(diǎn)可以代表多個(gè)鍵值對(duì)。

算法復(fù)雜度

N: 字符串的數(shù)量

M: 字符串的平均長(zhǎng)度

L: 字符串的長(zhǎng)度

空間復(fù)雜度
O(NM)

注意: Radix Tree 的使用場(chǎng)景是樹中有較多節(jié)點(diǎn)擁有相同前綴，所以即使和 Trie Tree 的空間復(fù)雜度一樣，但是實(shí)際應(yīng)用中，Radix Tree 通過(guò)壓縮公共前綴，空間使用要比 Trie Tree 節(jié)省很多。

操作	時(shí)間復(fù)雜度
插入	O(L)
查找	O(L)
刪除	O(L)

操作示例

下面引用維基百科頁(yè)面上的示例圖來(lái)說(shuō)明 Radix Tree 的操作過(guò)程。

初始狀態(tài)下，樹中包含兩個(gè)節(jié)點(diǎn)，分別是字符串 test 和 slow。

1. 將字符串 water 插入到樹中

因?yàn)樽址?water 和已有的兩個(gè)節(jié)點(diǎn)沒有公共前綴，所以直接插入到新的節(jié)點(diǎn)中。

2. 將字符串 slower 插入到樹中

字符串 slower 和已有的節(jié)點(diǎn) slow 存在公共前綴 slow, 所以放在 slow 節(jié)點(diǎn)下面。

3. 將字符串 tester 插入到樹中

字符串 tester 和已有的節(jié)點(diǎn) test 存在公共前綴 test, 所以放在 test 節(jié)點(diǎn)下面。

4. 將字符串 team 插入到樹中

字符串 team 和已有的節(jié)點(diǎn) test 存在公共前綴 te, 將 test 節(jié)點(diǎn)分裂為 st 和 am 兩個(gè)子節(jié)點(diǎn)，兩個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)為 te。

5. 將字符串 toast 插入到樹中

字符串 toast 和已有的節(jié)點(diǎn) te 存在公共前綴 t, 將 te 節(jié)點(diǎn)分裂為 e 和 oast 兩個(gè)子節(jié)點(diǎn)，兩個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)為 t, 將 te 原來(lái)的兩個(gè)子節(jié)點(diǎn)放在 e 節(jié)點(diǎn)下面。

實(shí)現(xiàn)代碼

筆者選擇了開源的組件庫(kù) httprouter[2] 來(lái)作為代碼實(shí)現(xiàn)的學(xué)習(xí)方案，選擇這個(gè)組件的主要原因有兩點(diǎn)：

該組件專注于路由管理，代碼量少且結(jié)構(gòu)簡(jiǎn)單，涉及到 Radix Tree 數(shù)據(jù)結(jié)構(gòu)和算法的代碼已經(jīng)獨(dú)立到一個(gè)文件中，這可以大大降低我們閱讀源代碼的壓力和時(shí)間成本
很多 Web 框架中的路由管理功能都是基于該組件實(shí)現(xiàn)的，比如非常流行的 Gin

Web Frameworks based on HttpRouter

httprouter 提供的 API 非常簡(jiǎn)潔，例如下面是一個(gè)簡(jiǎn)單的 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))
}

接下來(lái)我們分為兩部分來(lái)學(xué)習(xí) httprouter 組件的源代碼實(shí)現(xiàn):

Radix Tree 數(shù)據(jù)結(jié)構(gòu)和算法的實(shí)現(xiàn)
基于 Radix Tree 的路由管理功能實(shí)現(xiàn)

httprouter UML

重要提示: 下文中的代碼和注釋內(nèi)容較多，讀者如果時(shí)間有限，可以快速瀏覽一下核心對(duì)象及方法和文末的總結(jié)，在需要了解細(xì)節(jié)時(shí)再回來(lái)閱讀。

Radix Tree 實(shí)現(xiàn)

工作原理簡(jiǎn)述

路由管理功能中，底層的數(shù)據(jù)結(jié)構(gòu)是使用公共前綴的樹形結(jié)構(gòu)，也就是基數(shù)樹。在該數(shù)據(jù)結(jié)構(gòu)中，所有具有公共前綴的節(jié)點(diǎn)共享同一個(gè)父節(jié)點(diǎn)，下面是一個(gè)關(guān)于這種數(shù)據(jù)結(jié)構(gòu)的示例 (請(qǐng)求方法為 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>

對(duì)上面的結(jié)構(gòu)圖做一個(gè)簡(jiǎn)單的說(shuō)明:

*<數(shù)字> 代表 Handler 方法指針
search 節(jié)點(diǎn)和 support 節(jié)點(diǎn)擁有共同的父節(jié)點(diǎn) s ，并且 s 沒有對(duì)應(yīng)的 Handle，只有葉子節(jié)點(diǎn)才有 Handler
從 root 節(jié)點(diǎn)開始，一直到葉子節(jié)點(diǎn)，算作一條路由的完整路徑
路徑搜索的順序是從上向下 -> 從左到右，為了快速找到盡可能多的路由，子節(jié)點(diǎn)越多的節(jié)點(diǎn)優(yōu)先級(jí)越高

將上面的結(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 對(duì)象

node 對(duì)象表示 Radix Tree 的單個(gè)節(jié)點(diǎn)。

//?節(jié)點(diǎn)類型
type?nodeType?uint8
const?(
?static?nodeType?=?iota
?root????????//?根節(jié)點(diǎn)
?param???????//?參數(shù)節(jié)點(diǎn)?(例如?/users/:id)
?catchAll????//?通用節(jié)點(diǎn)，匹配任意參數(shù)?(例如?/users/*logs)
)
type?node?struct?{
?path??????string????//?路徑
?wildChild?bool??????//?是否為參數(shù)節(jié)點(diǎn)
?nType?????nodeType??//?節(jié)點(diǎn)類型
?maxParams?uint8?????//?路徑參數(shù)個(gè)數(shù)上限
?priority??uint32????//?優(yōu)先級(jí)
?indices???string????//?導(dǎo)致當(dāng)前節(jié)點(diǎn)和其子節(jié)點(diǎn)分裂的首個(gè)字符?(wildChild?==?true?時(shí),?indices?==?"")
?children??[]*node???//?子節(jié)點(diǎn)
?handle????Handle????//?路由處理方法
}

添加路由

addRoute 方法將給定的路由處理方法綁定到具體的 Path 上面，該方法不是并發(fā)安全的，也就是需要通過(guò)加鎖等機(jī)制將操作串行化。

為了最大化提升讀者的閱讀體驗(yàn)和效率，這里將代碼剖析注解直接貼在源代碼中。

func?(n?*node)?addRoute(path?string,?handle?Handle)?{
?fullPath?:=?path
?//?當(dāng)前節(jié)點(diǎn)優(yōu)先級(jí)?+?1
?n.priority++
?//?計(jì)算路徑中的參數(shù)個(gè)數(shù)
?numParams?:=?countParams(path)
?//?non-empty?tree
?if?len(n.path)?>?0?||?len(n.children)?>?0?{
??//?說(shuō)明當(dāng)前?Radix?Tree?已經(jīng)存在節(jié)點(diǎn)了
??//?接下來(lái)進(jìn)入?walk?循環(huán)標(biāo)簽
?walk:
??for?{
???//?更新當(dāng)前節(jié)點(diǎn)最大參數(shù)個(gè)數(shù)
???if?numParams?>?n.maxParams?{
????n.maxParams?=?numParams
???}
???//?查找當(dāng)前節(jié)點(diǎn)路徑和參數(shù)路徑的最長(zhǎng)公共前綴
???//?公共前綴中不能包含?':'??'*'?通配符?(因?yàn)檫@樣就無(wú)法區(qū)分具體的路徑了)
???//?PS:?查找最長(zhǎng)公共前綴應(yīng)該獨(dú)立為一個(gè)函數(shù)，提高代碼可讀性，編譯器會(huì)自動(dòng)內(nèi)聯(lián)優(yōu)化
???//?????Gin?框架中已經(jīng)獨(dú)立為一個(gè)函數(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++
???}
???//?如果最長(zhǎng)公共前綴長(zhǎng)度小于當(dāng)前節(jié)點(diǎn)路徑長(zhǎng)度
???//?這意味著可能是下列兩種情況之一?:
???//????1.?最長(zhǎng)公共前綴?>?0,?例如當(dāng)前節(jié)點(diǎn)路徑為?/users,?參數(shù)路徑為?/usr
???//????2.?最長(zhǎng)公共前綴?==?0,?例如當(dāng)前節(jié)點(diǎn)路徑為?/users,?參數(shù)路徑為?/books
???//?此時(shí)當(dāng)前節(jié)點(diǎn)就需要分裂成兩個(gè)節(jié)點(diǎn)
???if?i?<?len(n.path)?{
????//?將當(dāng)前節(jié)點(diǎn)路徑中非?“公共前綴”?部分獨(dú)立到一個(gè)新的子節(jié)點(diǎn)中
????child?:=?node{
?????//?路徑為當(dāng)前節(jié)點(diǎn)路徑中非?“公共前綴”?部分
?????path:??????n.path[i:],
?????//?類型待定,?沒有?handler
?????nType:?????static,
?????indices:???n.indices,
????????????????????children:??n.children,
????????????????????handle:????n.handle,
?????//?優(yōu)先級(jí)?-?1
?????priority:??n.priority?-?1,
????}
????//?遍歷新的子節(jié)點(diǎn)的所有子節(jié)點(diǎn)?(也就是當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn))
????//?更新當(dāng)前節(jié)點(diǎn)最大參數(shù)個(gè)數(shù)
????for?i?:=?range?child.children?{
?????if?child.children[i].maxParams?>?child.maxParams?{
??????child.maxParams?=?child.children[i].maxParams
?????}
????}
????//?將新節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)?(當(dāng)前節(jié)點(diǎn)之前的子節(jié)點(diǎn)已經(jīng)被掛載到了新節(jié)點(diǎn)的子節(jié)點(diǎn)上面)
????n.children?=?[]*node{&child}
????//?獲取導(dǎo)致當(dāng)前節(jié)點(diǎn)和其子節(jié)點(diǎn)分裂的首個(gè)字符，并更新?indices?字段
????//?(例如?/users/dbwu?和?/users/dbwt,?更新?indices?字段為?"u")
????n.indices?=?string([]byte{n.path[i]})
????//?更新當(dāng)前節(jié)點(diǎn)的路徑為公共前綴
????n.path?=?path[:i]
????//?刪除當(dāng)前節(jié)點(diǎn)的路由處理方法
????n.handle?=?nil
????//?刪除當(dāng)前節(jié)點(diǎn)的參數(shù)節(jié)點(diǎn)標(biāo)志
????n.wildChild?=?false
???}
???//?如果最長(zhǎng)公共前綴長(zhǎng)度小于參數(shù)路徑長(zhǎng)度
???//?為什么這樣判斷呢？
???//????因?yàn)槿绻铋L(zhǎng)公共前綴長(zhǎng)度大于等于參數(shù)路徑長(zhǎng)度
???//????說(shuō)明參數(shù)路徑本身就是公共前綴的一部分，就沒必要插入這個(gè)新節(jié)點(diǎn)了
???//?將新節(jié)點(diǎn)插入到當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)
???if?i?<?len(path)?{
????//?刪除公共前綴部分，剩余部分的?path?是子節(jié)點(diǎn)的路徑
????path?=?path[i:]
????//?如果當(dāng)前節(jié)點(diǎn)是參數(shù)節(jié)點(diǎn)?(例如?/users/:id)
????if?n.wildChild?{
?????//?代碼執(zhí)行到這里說(shuō)明:?最長(zhǎng)公共前綴長(zhǎng)度大于等于當(dāng)前節(jié)點(diǎn)路徑長(zhǎng)度
?????//?也就是說(shuō):?參數(shù)路徑的長(zhǎng)度要大于當(dāng)前節(jié)點(diǎn)路徑長(zhǎng)度
?????//?(例如?當(dāng)前節(jié)點(diǎn)路徑為?/users/:id,?參數(shù)路徑為?/users/:id/profile)
?????//?獲取到當(dāng)前節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)
?????n?=?n.children[0]
?????//?當(dāng)前節(jié)點(diǎn)要插入一個(gè)新節(jié)點(diǎn)，優(yōu)先級(jí)?+?1
?????n.priority++
?????//?更新當(dāng)前節(jié)點(diǎn)最大參數(shù)個(gè)數(shù)
?????if?numParams?>?n.maxParams?{
??????n.maxParams?=?numParams
?????}
?????numParams--
?????//?檢測(cè)通配符模式是否匹配
?????if?len(path)?>=?len(n.path)?&&?n.path?==?path[:len(n.path)]?&&
??????n.nType?!=?catchAll?&&
??????//?檢測(cè)更長(zhǎng)的通配符匹配
??????//?(例如當(dāng)前節(jié)點(diǎn)的?path?=?name,?子節(jié)點(diǎn)的路徑是?path?=?names)
??????(len(n.path)?>=?len(path)?||?path[len(n.path)]?==?'/')?{
??????//?如果通配符模式匹配，進(jìn)入下一次循環(huán)
??????continue?walk
?????}?else?{
??????//?通配符發(fā)生了沖突
??????//?(例如當(dāng)前節(jié)點(diǎn)的?path?=?/users/:id/profile,?子節(jié)點(diǎn)的路徑是?path?=?/users/:name/profile)
??????var?pathSeg?string
??????//?如果當(dāng)前節(jié)點(diǎn)類型是通用節(jié)點(diǎn)?(通配符類型)
??????if?n.nType?==?catchAll?{
???????pathSeg?=?path
??????}?else?{
???????//?如果當(dāng)前節(jié)點(diǎn)類型不是通用節(jié)點(diǎn)
???????//?將?path?字符串進(jìn)行分割
???????//?(例如?path?=?/users/:id/profile,?分割之后?pathSeg?=?profile)
???????pathSeg?=?strings.SplitN(path,?"/",?2)[0]
??????}
??????//?提取出參數(shù)?path?的前綴
??????//?(例如?fullPath?=?/users/:id/profile,?當(dāng)前節(jié)點(diǎn)?path?=?:id,?prefix?=?/user/:id)
??????prefix?:=?fullPath[:strings.Index(fullPath,?pathSeg)]?+?n.path
??????//?直接拋出一個(gè)?panic
??????//?信息中會(huì)輸出產(chǎn)生沖突的具體通配符?path
??????panic("'"?+?pathSeg?+
???????"'?in?new?path?'"?+?fullPath?+
???????"'?conflicts?with?existing?wildcard?'"?+?n.path?+
???????"'?in?existing?prefix?'"?+?prefix?+
???????"'")
?????}
????}
????c?:=?path[0]
????//?如果當(dāng)前節(jié)點(diǎn)是一個(gè)參數(shù)節(jié)點(diǎn)并且只有一個(gè)子節(jié)點(diǎn)?并且參數(shù)?path?是以?"/"?開頭的
????//?(例如當(dāng)前節(jié)點(diǎn)?path?=?/:name/profile,?參數(shù)?path?=?/:name/setting)
????if?n.nType?==?param?&&?c?==?'/'?&&?len(n.children)?==?1?{
?????//?將當(dāng)前節(jié)點(diǎn)修改為其第一個(gè)子節(jié)點(diǎn)
?????n?=?n.children[0]
?????//?優(yōu)先級(jí)?+?1
?????n.priority++
?????//?進(jìn)入下一次循環(huán)
?????continue?walk
????}
????//?檢測(cè)新增子節(jié)點(diǎn)的?path?的首字母是否存在于當(dāng)前節(jié)點(diǎn)的?indices?字段中
????for?i?:=?0;?i?<?len(n.indices);?i++?{
?????if?c?==?n.indices[i]?{
??????//?更新子節(jié)點(diǎn)的優(yōu)先級(jí)
??????i?=?n.incrementChildPrio(i)
??????//?更新當(dāng)前節(jié)點(diǎn)為對(duì)應(yīng)的子節(jié)點(diǎn)
??????//??(
??????//????例如當(dāng)前節(jié)點(diǎn)?path?=?p,?包含兩個(gè)子節(jié)點(diǎn)?rofile,?assword)
??????//????此時(shí)?indices?字段就包含字符?r?和?a,?正好和兩個(gè)子節(jié)點(diǎn)相對(duì)應(yīng)
??????//????新增子節(jié)點(diǎn)的?path?=?projects,?刪除和當(dāng)前節(jié)點(diǎn)的公共前綴符?p?后，變成了?rojects
??????//????然后當(dāng)前節(jié)點(diǎn)會(huì)被更新為?rofile?子節(jié)點(diǎn)
??????//????最后，跳轉(zhuǎn)到下一次循環(huán)，然后拿?rofile?和?rojects?進(jìn)行對(duì)比
??????//??)
??????n?=?n.children[i]
??????//?進(jìn)入下一次循環(huán)
??????continue?walk
?????}
????}
????//?如果上面的條件都不滿足
????//?直接將新的子節(jié)點(diǎn)插入
????if?c?!=?':'?&&?c?!=?'*'?{
?????//?如果參數(shù)?path?的第一個(gè)字符不是通配符
?????//?將第一個(gè)字符追加到當(dāng)前節(jié)點(diǎn)的?indices?字段
?????n.indices?+=?string([]byte{c})
?????//?初始化一個(gè)新的子節(jié)點(diǎn)
?????child?:=?&node{
??????maxParams:?numParams,
?????}
?????//?將新的子節(jié)點(diǎn)追加到當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)列表中
?????n.children?=?append(n.children,?child)
??????????//?更新子節(jié)點(diǎn)的優(yōu)先級(jí)
?????n.incrementChildPrio(len(n.indices)?-?1)
?????//?更新當(dāng)前節(jié)點(diǎn)為新增的子節(jié)點(diǎn)
?????n?=?child
????}
????n.insertChild(numParams,?path,?fullPath,?handle)
????return
???}?else?if?i?==?len(path)?{
????//?如果公共前綴和參數(shù)?path?長(zhǎng)度相同
????//?說(shuō)明參數(shù)?path?本身就是當(dāng)前節(jié)點(diǎn)?path?的一部分
????if?n.handle?!=?nil?{
?????//?如果當(dāng)前節(jié)點(diǎn)已經(jīng)注冊(cè)了路由處理方法
?????//?那么再次注冊(cè)時(shí)等于重復(fù)注冊(cè)
?????//?直接拋出?panic
?????panic("a?handle?is?already?registered?for?path?'"?+?fullPath?+?"'")
????}
????//?如果當(dāng)前節(jié)點(diǎn)沒有注冊(cè)路由處理方法
????//?說(shuō)明當(dāng)前節(jié)點(diǎn)是作為其子節(jié)點(diǎn)的公共前綴符而存在的
????//?(例如?當(dāng)前節(jié)點(diǎn)?path?=?p,?包含兩個(gè)子節(jié)點(diǎn)?rofile,?assword))
????n.handle?=?handle
???}
???return
??}
?}?else?{
??//?如果當(dāng)前節(jié)點(diǎn)是一個(gè)空節(jié)點(diǎn)
??//?說(shuō)明當(dāng)前?Radix?Tree?沒有任何節(jié)點(diǎn)
??//?直接插入一個(gè)新節(jié)點(diǎn)
??//?并且將插入的新節(jié)點(diǎn)類型標(biāo)記為?root
??//?PS:?筆者認(rèn)為這兩行邊界檢測(cè)代碼應(yīng)該放在函數(shù)開頭部分，提高可讀性
??n.insertChild(numParams,?path,?fullPath,?handle)
??n.nType?=?root
?}
}

incrementChildPrio 方法用于更新給定子節(jié)點(diǎn)的優(yōu)先級(jí)，并在必要的時(shí)候進(jìn)行排序。

func?(n?*node)?incrementChildPrio(pos?int)?int?{
?//?將對(duì)應(yīng)索引的子節(jié)點(diǎn)的優(yōu)先級(jí)?+?1
?n.children[pos].priority++
?prio?:=?n.children[pos].priority
????//?向前移動(dòng)位置
?//?(例如原本的子節(jié)點(diǎn)順序?yàn)?[a,?b,?c,?d],?此時(shí)傳入?yún)?shù)?2,?移動(dòng)之后的子節(jié)點(diǎn)順序?yàn)?[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--
?}
?//?更新當(dāng)前節(jié)點(diǎn)的?indices?字段信息
?//?(例如原本的?indices?字段為?abcd,?此時(shí)傳入?yún)?shù)?2,?移動(dòng)之后的?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'
?}
?//?返回移動(dòng)后的新的位置
?return?newPos
}

insertChild 方法負(fù)責(zé)執(zhí)行將具體的 path 插入到節(jié)點(diǎn)中。

func?(n?*node)?insertChild(numParams?uint8,?path,?fullPath?string,?handle?Handle)?{
?//?參數(shù)?path?已經(jīng)處理完的計(jì)算數(shù)量
?var?offset?int
?//?查找前綴直到第一個(gè)參數(shù)匹配或者通配符?(以?':'?或?'*'?開頭)
?//?參數(shù)匹配?(類似這種形式?:name)
?//?通配符?(類似這種形式?*logs)
?//?為了便于描述，下文中統(tǒng)一將?參數(shù)匹配符號(hào)?和?通配符號(hào)?統(tǒng)稱為?Token
?for?i,?max?:=?0,?len(path);?numParams?>?0;?i++?{
??c?:=?path[i]
??if?c?!=?':'?&&?c?!=?'*'?{
???//?如果不是?':'?或?'*',?直接跳過(guò)
???continue
??}
??//?查找當(dāng)前?Token?結(jié)束符,?也就是下一個(gè)?'/'
??//?(例如?Token?為?/:name/profile,?查找的就是?:name?后面的?/?符號(hào))
??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é)點(diǎn)了，直接?panic
??//?(例如已經(jīng)存在了節(jié)點(diǎn)?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?至少需要一個(gè)字符表示的參數(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?==?':'?{
???//?將當(dāng)前節(jié)點(diǎn)的位置更新為?從?offset?到當(dāng)前索引位置之間的?path，
???if?i?>?0?{
????n.path?=?path[offset:i]
????//?更新?offset
????offset?=?i
???}
???//?根據(jù)參數(shù)初始化一個(gè)新的子節(jié)點(diǎn)
???child?:=?&node{
????nType:?????param,
????maxParams:?numParams,
???}
???//?更新當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)
???n.children?=?[]*node{child}
???//?更新當(dāng)前節(jié)點(diǎn)類型為參數(shù)節(jié)點(diǎn)
???n.wildChild?=?true
???//?當(dāng)前節(jié)點(diǎn)下降為子節(jié)點(diǎn)，繼續(xù)后面的路由處理
???n?=?child
???//?當(dāng)前節(jié)點(diǎn)優(yōu)先級(jí)?+?1
???n.priority++
???//?最大參數(shù)個(gè)數(shù)?-?1
???numParams--
???//?如果?Token?結(jié)束符比參數(shù)?path?長(zhǎng)度要小
???//?說(shuō)明參數(shù)?path?中還有子路徑
???if?end?<?max?{
????//?更新當(dāng)前節(jié)點(diǎn)?path
????n.path?=?path[offset:end]
????//?更新?offset
????offset?=?end
????//?初始化一個(gè)新節(jié)點(diǎn)作為參數(shù)?path?中的子路徑節(jié)點(diǎn)
????child?:=?&node{
?????maxParams:?numParams,
?????priority:??1,
????}
????//?更新當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)
????n.children?=?[]*node{child}
????//?當(dāng)前節(jié)點(diǎn)下降為子節(jié)點(diǎn)，繼續(xù)后面的路由處理
????n?=?child
???}
??}?else?{?//?如果?Token?的類型是通配符
???if?end?!=?max?||?numParams?>?1?{
????//?通配符類型的路徑必須位于路由?path?的最后一部分，否則直接?panic
????//?(
????//???例如?/users/*name?是合法的，但是?/users/*name/profile?不是合法的，因?yàn)檫@樣就無(wú)法區(qū)分其他路由了
????//???例如?path?=?/users/dbwu/profile?是一個(gè)單獨(dú)的?path,?但是卻匹配了?/users/*name?這個(gè)?path
????//???因此獲取到的參數(shù)?name?=?"dbwu/profile"
????//???所以不會(huì)再將后面的?/dbwu/profile?作為單獨(dú)路徑來(lái)處理了
????//?)
????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
????//?(例如一個(gè)已有的?path?=?/users/dbwu,?新定義的?path?=?/users/:name,?如果不終止，后者就會(huì)覆蓋前者)
????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]
???//?初始化一個(gè)新的子節(jié)點(diǎn)，類型為通配符節(jié)點(diǎn)
???child?:=?&node{
????wildChild:?true,
????nType:?????catchAll,
????maxParams:?1,
???}
???//?更新當(dāng)前節(jié)點(diǎn)的最大參數(shù)個(gè)數(shù)
???if?n.maxParams?<?1?{
????n.maxParams?=?1
???}
???//?更新當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)
???n.children?=?[]*node{child}
???//?更新當(dāng)前節(jié)點(diǎn)的?indices?字段
???n.indices?=?string(path[i])
???//?當(dāng)前節(jié)點(diǎn)下降為子節(jié)點(diǎn)，繼續(xù)后面的路由處理
???n?=?child
???//?當(dāng)前節(jié)點(diǎn)優(yōu)先級(jí)?+?1
???n.priority++
???//?初始化一個(gè)新節(jié)點(diǎn)作為參數(shù)?path?中的剩余部分的節(jié)點(diǎn)
???child?=?&node{
????path:??????path[i:],
????nType:?????catchAll,
????maxParams:?1,
????handle:????handle,??//?綁定路由的處理函數(shù)
????priority:??1,
???}
???//?更新當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)
???n.children?=?[]*node{child}
???//?通配符類型的路徑必須位于路由?path?的最后一部分
???//?直接返回即可
???return
??}
?}
?//?更新當(dāng)前節(jié)點(diǎn)的?path
?n.path?=?path[offset:]
?//?更新當(dāng)前節(jié)點(diǎn)的處理函數(shù)
?n.handle?=?handle
}

查找路由處理方法

getValue 方法根據(jù)指定的 path，查找并返回對(duì)應(yīng)的路由處理方法。

返回值列表順序如下:

handle : path 對(duì)應(yīng)的處理方法，如果沒有找到，返回 nil
p : 如果 path 對(duì)應(yīng)的節(jié)點(diǎn)類型是參數(shù)節(jié)點(diǎn)，會(huì)將參數(shù)返回
tsr : 路由是否可以被重定向

func?(n?*node)?getValue(path?string)?(handle?Handle,?p?Params,?tsr?bool)?{
?//?循環(huán)標(biāo)簽
walk:
?for?{
??//?如果要查找的?path?長(zhǎng)度大于當(dāng)前節(jié)點(diǎn)的?path?長(zhǎng)度
??//?除了根路徑?/,?其他?path?應(yīng)該都可以滿足這個(gè)條件
??if?len(path)?>?len(n.path)?{
???//?如果當(dāng)前節(jié)點(diǎn)的?path?是要查找的?path?的前綴
???if?path[:len(n.path)]?==?n.path?{
????//?那么就將前綴去掉，查找剩余的部分
????path?=?path[len(n.path):]
????//?如果當(dāng)前節(jié)點(diǎn)類型不是參數(shù)節(jié)點(diǎn)
????//?直接在其子節(jié)點(diǎn)中查找即可
????if?!n.wildChild?{
?????//?通過(guò)要查找?path?的首字母快速匹配對(duì)應(yīng)的子節(jié)點(diǎn)
?????c?:=?path[0]
?????for?i?:=?0;?i?<?len(n.indices);?i++?{
??????if?c?==?n.indices[i]?{
???????//?更新當(dāng)前節(jié)點(diǎn)
???????n?=?n.children[i]
???????//?跳轉(zhuǎn)到下一個(gè)循環(huán)
???????continue?walk
??????}
?????}
?????//?代碼執(zhí)行到這里，說(shuō)明沒有匹配到子節(jié)點(diǎn)
?????//?如果路徑剩余的部分正好是?'/',?并且當(dāng)前節(jié)點(diǎn)注冊(cè)了路由處理方法
?????//?更新?tsr?重定向標(biāo)記為?true
?????//?(例如查找的?path?=?/users/,?當(dāng)前節(jié)點(diǎn)?path?=?/users,?那么就重定向到?/users)
?????tsr?=?(path?==?"/"?&&?n.handle?!=?nil)
?????return
????}
????//?如果當(dāng)前節(jié)點(diǎn)類型是參數(shù)節(jié)點(diǎn)或者通配符節(jié)點(diǎn)
????//?那么當(dāng)前節(jié)點(diǎn)只會(huì)有一個(gè)子節(jié)點(diǎn)
????//?更新當(dāng)前節(jié)點(diǎn)為其第一個(gè)子節(jié)點(diǎn)
????n?=?n.children[0]
????switch?n.nType?{
????//?如果當(dāng)前節(jié)點(diǎn)類型是參數(shù)節(jié)點(diǎn)
????//?參數(shù)匹配?(類似這種形式?:name)
????case?param:
?????//?查找路徑中的參數(shù)結(jié)束符或者?'/'
?????end?:=?0
?????for?end?<?len(path)?&&?path[end]?!=?'/'?{
??????end++
?????}
?????if?p?==?nil?{
??????//?惰性初始化參數(shù)返回值
??????//?注意初始化的時(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é)點(diǎn)下面還存在子節(jié)點(diǎn)
?????//?(例如?path?=?/users/:name/:setting,?當(dāng)前匹配到?:name,?發(fā)現(xiàn)其還有子節(jié)點(diǎn))
???? if?len(n.children)?>?0?{
???????//?更新查找路徑
???????path?=?path[end:]
???????//?更新當(dāng)前節(jié)點(diǎn)為其第一個(gè)子節(jié)點(diǎn)
???????n?=?n.children[0]
???????//?跳轉(zhuǎn)到下一個(gè)循環(huán)
???????continue?walk
??????}
??????//?沒有查到到對(duì)應(yīng)到路由處理函數(shù)
??????//?直接返回
??????tsr?=?(len(path)?==?end+1)
??????return
?????}
?????if?handle?=?n.handle;?handle?!=?nil?{
???? //?如果當(dāng)前節(jié)點(diǎn)有對(duì)應(yīng)到路由處理函數(shù)
?????//?直接返回
??????return
?????}?else?if?len(n.children)?==?1?{
??????//?如果當(dāng)前節(jié)點(diǎn)沒有對(duì)應(yīng)到路由處理函數(shù)
??????//?確認(rèn)其子節(jié)點(diǎn)是否為?'/'?并且子節(jié)點(diǎn)有對(duì)應(yīng)到路由處理函數(shù)
??????//?這樣就可以進(jìn)行進(jìn)行重定向了
??????n?=?n.children[0]
??????tsr?=?(n.path?==?"/"?&&?n.handle?!=?nil)
?????}
?????return
?????//?如果當(dāng)前節(jié)點(diǎn)類型是通配符節(jié)點(diǎn)
????//?通配符?(類似這種形式?*logs)
????case?catchAll:
?????if?p?==?nil?{
??????//?惰性初始化參數(shù)返回值
??????//?注意初始化的時(shí)候已經(jīng)指定了切片容量
??????p?=?make(Params,?0,?n.maxParams)
?????}
?????//?通配符不會(huì)有子節(jié)點(diǎn)，直接賦值后返回即可
?????//?為參數(shù)返回值賦值
?????i?:=?len(p)
?????p?=?p[:i+1]
?????p[i].Key?=?n.path[2:]
?????p[i].Value?=?path
?????handle?=?n.handle
?????return
????default:
?????//?代碼執(zhí)行到這里
?????//?說(shuō)明當(dāng)前節(jié)點(diǎn)的類型不在枚舉范圍內(nèi)，直接?panic
?????panic("invalid?node?type")
????}
???}
??}?else?if?path?==?n.path?{
???//?如果要查找的?path?等于當(dāng)前節(jié)點(diǎn)的?path
???//?檢測(cè)當(dāng)前節(jié)點(diǎn)是否有路由處理函數(shù)，如果有的話，直接返回即可
???if?handle?=?n.handle;?handle?!=?nil?{
????return
???}
???//?如果要查找的?path?等于?/?并且當(dāng)前節(jié)點(diǎn)類型不是?root,?并且當(dāng)前節(jié)點(diǎn)是參數(shù)節(jié)點(diǎn)
???//?允許重定向
???if?path?==?"/"?&&?n.wildChild?&&?n.nType?!=?root?{
????tsr?=?true
????return
???}
???//?當(dāng)前節(jié)點(diǎn)沒有路由處理函數(shù)，但是有一個(gè)子節(jié)點(diǎn)的路徑為?'/',?這時(shí)允許重定向
???//?(例如當(dāng)前節(jié)點(diǎn)的?path?=?/users/,?但是查找的?path?=?/users,?此時(shí)就允許重定向到?/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
??}
??//?沒有查到到對(duì)應(yīng)到路由處理函數(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
?}
}

路由管理實(shí)現(xiàn)

相比于上面 Radix Tree 的實(shí)現(xiàn)，路由管理功能實(shí)現(xiàn)要簡(jiǎn)單的多，這里分析一下核心的代碼。

Router 對(duì)象

Router 對(duì)象表示全局的路由管理對(duì)象，可以將不同的 HTTP Method + Path 請(qǐng)求分發(fā)給不同的路由處理函數(shù)。

type?Router?struct?{
????//?路由管理的核心字段，每個(gè)?HTTP?Method?對(duì)應(yīng)一個(gè)?Radix?Tree?結(jié)構(gòu)
????//?例如
????//???GET?=>?Radix?Tree
????//???POST?=>?Radix?Tree
????//???DELETE?=>?Radix?Tree
????//???...
???trees?map[string]*node
????//?是否啟用請(qǐng)求的自動(dòng)重定向
????//?(例如當(dāng)前請(qǐng)求為?/foo/,?但是路由管理注冊(cè)的路徑只有?/foo,?此時(shí)就將?/foo/?重定向到?/fooo)
????//?(重定向時(shí)，GET?請(qǐng)求的響應(yīng)碼為?301，?其他請(qǐng)求的為?307)
???RedirectTrailingSlash?bool
????//?是否啟用自動(dòng)修復(fù)路徑
????//?首先會(huì)刪除路徑中多余的部分，例如?../?和?//
????//?然后再次查找路徑?(這一次不區(qū)分大小寫)，看是否可以匹配到對(duì)應(yīng)的路徑處理方法
????//?如果能匹配到路徑，就進(jìn)行重定向
????//?(重定向時(shí)，GET?請(qǐng)求的響應(yīng)碼為?301，?其他請(qǐng)求的為?307)
????RedirectFixedPath?bool
????//?是否啟用?Method?Not?Allowed
????//?啟用機(jī)制后，如果當(dāng)前路徑?jīng)]有匹配到對(duì)應(yīng)的路徑處理方法
????//???查看其他當(dāng)前路徑是否注冊(cè)了其他?HTTP?請(qǐng)求類型的路徑處理方法
????//???如果注冊(cè)了，返回?405?狀態(tài)碼
????//?如果沒有開啟機(jī)制，當(dāng)前路徑?jīng)]有匹配到對(duì)應(yīng)的路徑處理方法
????//???返回?404?狀態(tài)碼
????HandleMethodNotAllowed?bool
???//?是否啟用?OPTIONS?請(qǐng)求響應(yīng)
????HandleOPTIONS?bool
????//?404?響應(yīng)方法
???//?如果沒有設(shè)置，就使用標(biāo)準(zhǔn)庫(kù)的?404?方法
????NotFound?http.Handler
????//?405?響應(yīng)方法
????//?如果沒有設(shè)置，就使用標(biāo)準(zhǔn)庫(kù)的?Error?方法
????//???其中響應(yīng)文本為?Method?Not?Allowed，狀態(tài)碼為?405
????MethodNotAllowed?http.Handler
????//?用于捕獲并處理?panic?錯(cuò)誤的方法，返回錯(cuò)誤碼?500?(Internal?Server?Error)
????//?保證程序因?yàn)闆]有捕獲?panic?而崩潰退出
????PanicHandler?func(http.ResponseWriter,?*http.Request,?interface{})
}
//?通過(guò)編譯期間保證?Router?必須實(shí)現(xiàn)?http.Handler?接口
var?_?http.Handler?=?New()
//?創(chuàng)建并返回一個(gè)路由管理實(shí)例
func?New()?*Router?{
?return?&Router{
??RedirectTrailingSlash:??true,
??RedirectFixedPath:??????true,
??HandleMethodNotAllowed:?true,
??HandleOPTIONS:??????????true,
?}
}

注冊(cè)路由處理方法

Router 提供了常見的 HTTP 請(qǐng)求路由處理方法注冊(cè)的 API, 每個(gè)方法的內(nèi)部都是調(diào)用了 Handle 方法，下面是 GET 方法和 POST 方法的實(shí)現(xiàn)代碼。

//?注冊(cè)?GET?請(qǐng)求處理方法
func?(r?*Router)?GET(path?string,?handle?Handle)?{
?r.Handle(http.MethodGet,?path,?handle)
}
//?注冊(cè)?POST?請(qǐng)求處理方法
func?(r?*Router)?POST(path?string,?handle?Handle)?{
????r.Handle(http.MethodPost,?path,?handle)
}
...

Handle 方法將指定的 HTTP Method + Path 和路由處理方法進(jìn)行綁定。

func?(r?*Router)?Handle(method,?path?string,?handle?Handle)?{
?if?len(path)?<?1?||?path[0]?!=?'/'?{
??//?如果路徑為空或者路徑第一個(gè)字符不等于?'/'
??//?這種路徑格式就是不合法的，直接?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?方法對(duì)應(yīng)的?Radix?Tree?結(jié)構(gòu)
??root?=?new(node)
??r.trees[method]?=?root
??r.globalAllowed?=?r.allowed("*",?"")
?}
?//?添加路由的注冊(cè)方法
?//?詳情見前文對(duì)于?addRoute?方法的注解
?root.addRoute(path,?handle)
}

ServeHTTP 實(shí)現(xiàn)

ServeHTTP 方法負(fù)責(zé)處理 HTTP 請(qǐng)求并返回響應(yīng)，同時(shí)實(shí)現(xiàn)了標(biāo)準(zhǔn)庫(kù)中的 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?錯(cuò)誤處理函數(shù)注冊(cè)到?defer?函數(shù)
??defer?r.recv(w,?req)
?}
?//?獲取當(dāng)前請(qǐng)求路徑
?path?:=?req.URL.Path
?//?檢測(cè)當(dāng)前請(qǐng)求方法是否存在對(duì)應(yīng)的?Radix?Tree?結(jié)構(gòu)
?if?root?:=?r.trees[req.Method];?root?!=?nil?{
??if?handle,?ps,?tsr?:=?root.getValue(path);?handle?!=?nil?{
???//?如果當(dāng)前請(qǐng)求路徑有對(duì)應(yīng)的處理方法，直接調(diào)用即可
???handle(w,?req,?ps)
???return
??}?else?if?req.Method?!=?http.MethodConnect?&&?path?!=?"/"?{
???//?PS:?上面的?if?條件分支都已經(jīng)直接返回了
???//?????這里實(shí)在沒必要再寫一個(gè)?else?條件分支
???//?????整個(gè)庫(kù)的代碼，可讀性比較低?～
???//?如果當(dāng)前請(qǐng)求路徑?jīng)]有對(duì)應(yīng)的處理方法
???//?將響應(yīng)狀態(tài)碼設(shè)置為?301?(永久重定向，針對(duì)?GET?方法)
???code?:=?301
???if?req.Method?!=?http.MethodGet?{
????//?如果當(dāng)前請(qǐng)求不是?GET?方法
????//?將響應(yīng)狀態(tài)碼設(shè)置為?307?(臨死重定向，針對(duì)非?GET?方法)
????//?為什么不使用?301?呢？
????//?因?yàn)?308?和?307?不允許請(qǐng)求從?POST?修改為?GET
????//?Temporary?redirect,?request?with?same?method
????//?As?of?Go?1.3,?Go?does?not?support?status?code?308.
????code?=?307
???}
???//?如果請(qǐng)求路徑需要重定向并且路由支持重定向
???if?tsr?&&?r.RedirectTrailingSlash?{
????//?如果路徑的長(zhǎng)度大于?1?并且路徑是以?'/'?字符結(jié)尾的
????//?就將末尾的?'/'?字符刪除
????if?len(path)?>?1?&&?path[len(path)-1]?==?'/'?{
?????req.URL.Path?=?path[:len(path)-1]
????}?else?{
?????//?在路徑的結(jié)尾加一個(gè)?'/'?字符
?????req.URL.Path?=?path?+?"/"
????}
????//?返回重定向響應(yīng)
????http.Redirect(w,?req,?req.URL.String(),?code)
????return
???}
???//?如果當(dāng)前請(qǐng)求路徑?jīng)]有對(duì)應(yīng)的處理方法?并且?也沒有符合規(guī)則的重定向條件
???//?嘗試修復(fù)請(qǐng)求路徑
???if?r.RedirectFixedPath?{
????//?去除路徑中的多余部分并返回經(jīng)過(guò)修正后是否有匹配的路徑
????fixedPath,?found?:=?root.findCaseInsensitivePath(
?????CleanPath(path),
?????r.RedirectTrailingSlash,
????)
????if?found?{
?????//?如果經(jīng)過(guò)修正，可以找到匹配的路徑
?????//?直接重定向
?????req.URL.Path?=?string(fixedPath)
?????http.Redirect(w,?req,?req.URL.String(),?code)
?????return
????}
???}
??}
?}
?//?代碼執(zhí)行到了這里
?//?說(shuō)明上面的幾個(gè)條件都不符合，當(dāng)前請(qǐng)求路徑還是沒有找到對(duì)應(yīng)的處理方法
?if?req.Method?==?http.MethodOptions?&&?r.HandleOPTIONS?{
??//?如果請(qǐng)求方法是?OPTIONS,?并且路由管理允許響應(yīng)?OPTIONS
??//?返回一個(gè)?OPTIONS?響應(yīng)
??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?{
??//?如果請(qǐng)求方法不是?OPTIONS,?或者路由管理不允許響應(yīng)?OPTIONS
??//?返回一個(gè)?405?響應(yīng)
??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?{
??//?如果路由管理中注冊(cè)了?404?處理函數(shù)
??//?直接調(diào)用
??r.NotFound.ServeHTTP(w,?req)
?}?else?{
??//?如果路由管理中沒有注冊(cè)?404?處理方法
??//?調(diào)用標(biāo)準(zhǔn)庫(kù)中的?404?處理方法
??http.NotFound(w,?req)
?}
}

優(yōu)點(diǎn)

Radix Tree 通過(guò)合并公共前綴來(lái)降低存儲(chǔ)空間的開銷，避免了 Trie Tree 字符串過(guò)長(zhǎng)和字符集過(guò)大時(shí)導(dǎo)致的存儲(chǔ)空間過(guò)多問(wèn)題，同時(shí)公共前綴優(yōu)化了路徑層數(shù)，提升了插入、查詢、刪除等操作效率。

適用場(chǎng)景

字典和前綴匹配：適合用作字典或關(guān)聯(lián)數(shù)組的底層數(shù)據(jù)結(jié)構(gòu)，可以快速找到以給定前綴開頭的所有鍵，例如 Redis 中的某個(gè)前綴 key

IP 路由表：可以高效地存儲(chǔ)和搜索 IP 地址及其對(duì)應(yīng)的路由表信息

文件系統(tǒng)和目錄：每個(gè)節(jié)點(diǎn)可以表示一個(gè)目錄或文件，節(jié)點(diǎn)之間的關(guān)系通過(guò)共同的路徑前綴進(jìn)行連接

編譯器：可以用于編譯器中的符號(hào)表管理，符號(hào)表存儲(chǔ)了程序中定義的變量、函數(shù)名和類型等信息，Radix Tree 可以快速查找和更新符號(hào)表項(xiàng)，支持高效的名稱解析和類型檢查

不適用場(chǎng)景

字符串公共前綴太少，造成 Radix Tree 節(jié)點(diǎn)稀疏分布 (退化到 Trie Tree)，這時(shí)哈希表是更好的選擇 (這個(gè)問(wèn)題在 Trie Tree 中同樣存在)

字符集過(guò)小，可以直接使用其他簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)

動(dòng)態(tài)數(shù)據(jù)集，也就是數(shù)據(jù)集需要頻繁地進(jìn)行插入和刪除操作，由于 Radix Tree 的節(jié)點(diǎn)需要合并和路徑重組，動(dòng)態(tài)修改樹結(jié)構(gòu)可能引起較大的開銷，在這種情況下，這時(shí)平衡二叉搜索樹結(jié)構(gòu)（AVL 樹、紅黑樹）更適合

節(jié)點(diǎn)之間的父子節(jié)點(diǎn)使用指針連接，對(duì) CPU 和自帶 GC 語(yǔ)言不太友好 (這個(gè)問(wèn)題在 Trie Tree 中同樣存在)

Trie Tree 對(duì)比 Radix Tree

下面是插入 4 個(gè)單詞 [PLAN, PLAY, POLL, POST] 后的結(jié)果 (粗體字符表示節(jié)點(diǎn)字符，圓圈內(nèi)字符串表示該節(jié)點(diǎn)表示的值)。

小結(jié)

本文從開發(fā)中常見的 “路由管理” 功能為出發(fā)點(diǎn)，探索了實(shí)現(xiàn)背后用到的數(shù)據(jù)結(jié)構(gòu)和算法，并先后分析了各解決方案的優(yōu)化過(guò)程，分別是 Go 標(biāo)準(zhǔn)庫(kù)、手動(dòng)實(shí)現(xiàn) Trie Tree、開源的 Radix Tree, 希望讀者在讀完文章后，能準(zhǔn)確地理解 Trie Tree 和 Radix Tree 的差異及其適用場(chǎng)景，如果在此基礎(chǔ)上還有興趣和時(shí)間，可以深入了解下由這兩種數(shù)據(jù)結(jié)構(gòu)演變出的其他數(shù)據(jù)結(jié)構(gòu)和算法。

到此這篇關(guān)于go語(yǔ)言中HTTPRouter的算法演進(jìn)的文章就介紹到這了,更多相關(guān)go HTTPRouter內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

国产无遮挡裸体免费直播视频,久久精品国产蜜臀av,动漫在线视频一区二区,欧亚日韩一区二区三区,久艹在线免费视频,国产精品美女网站免费,正在播放 97超级视频在线观看,斗破苍穹年番在线观看免费,51最新乱码中文字幕

go語(yǔ)言中HTTPRouter的算法演進(jìn)

目錄

概述

應(yīng)用示例

標(biāo)準(zhǔn)庫(kù)方案

優(yōu)點(diǎn)和不足

Trie Tree

算法復(fù)雜度

圖示

實(shí)現(xiàn)代碼

實(shí)現(xiàn)路由管理

優(yōu)點(diǎn)

適用場(chǎng)景

不適用場(chǎng)景

Radix Tree

算法復(fù)雜度

操作示例

實(shí)現(xiàn)代碼

Radix Tree 實(shí)現(xiàn)

查找路由處理方法

路由管理實(shí)現(xiàn)

優(yōu)點(diǎn)

適用場(chǎng)景

不適用場(chǎng)景

Trie Tree 對(duì)比 Radix Tree

小結(jié)

相關(guān)文章

最新評(píng)論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

国产无遮挡裸体免费直播视频,久久精品国产蜜臀av,动漫在线视频一区二区,欧亚日韩一区二区三区,久艹在线 免费视频,国产精品美女网站免费,正在播放 97超级视频在线观看,斗破苍穹年番在线观看免费,51最新乱码中文字幕

go語(yǔ)言中HTTPRouter的算法演進(jìn)

目錄

概述

應(yīng)用示例

標(biāo)準(zhǔn)庫(kù)方案

優(yōu)點(diǎn)和不足

Trie Tree

算法復(fù)雜度

圖示

實(shí)現(xiàn)代碼

實(shí)現(xiàn)路由管理

優(yōu)點(diǎn)

適用場(chǎng)景

不適用場(chǎng)景

Radix Tree

算法復(fù)雜度

操作示例

實(shí)現(xiàn)代碼

Radix Tree 實(shí)現(xiàn)

查找路由處理方法

路由管理實(shí)現(xiàn)

優(yōu)點(diǎn)

適用場(chǎng)景

不適用場(chǎng)景

Trie Tree 對(duì)比 Radix Tree

小結(jié)

相關(guān)文章

最新評(píng)論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

国产无遮挡裸体免费直播视频,久久精品国产蜜臀av,动漫在线视频一区二区,欧亚日韩一区二区三区,久艹在线免费视频,国产精品美女网站免费,正在播放 97超级视频在线观看,斗破苍穹年番在线观看免费,51最新乱码中文字幕